Литература
Almasi, G. S., and A. Gottlieb. 1994. Highly Parallel Computing. 2nd ed. Menlo Park, CA: Benja-min/Cummings.
Bacon, J. 1998. Concurrent Systems: Operating Systems, Database and Distributed Systems: An Integrated Approach. 2nded. Reading, MA: Addison-Wesley.
Bernstein, A. J., and P. M. Lewis. 1993. Concurrency in Programming and Database Systems. Boston, MA' Jones and Bartlett.
Andrews, G. R. 1991. Concurrent Programming: Principles and Practice. Menlo Park, CA: Benjamin/ Cum-mings.
Ashcroft, E. and Z. Manna. 1971. Formalization of properties of parallel programs. Machine Intelligence 6:17—41.
Bernstein, A. J. 1966. Analysis of programs for parallel processing. IEEE Trans, on Computers EC-IS, 5 (October): 757-762.
Dijkstra, E. W, 1965. Solution of a problem in concurrent programming control. Comm. ACM 8, 9 (September): 569.
Dijkstra, E. W. 1968. Cooperating sequential processes. In F. Genuys, ed. Programming Languages. New York: Academic Press, pp. 43-112. (Э. Дейкстра. Взаимодействующие последовательные процессы. В сб. "Языки программирования" под ред. Ф. Женюи — М.: Мир, 1972.)
Dijkstra, E. W. 1977. On two beautiful solutions designed by Martin Rem. EWD 629. Reprinted in E. W. Dijkstra. Selected Writings on Computing: A Personal Perspective. New York: Springer-Verlag, 1982, pp. 313-318.
Floyd, R. W. 1967. Assigning meanings to programs. Proc. Amer. Math. Society Symp. in Applied Mathematics 19: 19-31.
Francez, N. 1986. Fairness. New York: Springer-Verlag.
Hoare, C. A. R. 1969. An axiomatic basis for computer programming. Comm. ACM 12, 10 (October) 576-580, 583.
Hoare, C. A. R. 1972. Towards a theory of parallel programming. In C. A. R. Hoare and R. H. Perrott, eds. Operating Systems Techniques. New York: Academic Press.
Hofstadter, D. J. 1979. Gddel, Escher, Bach: An Eternal Golden Braid. New York: Vintage Books.
Глава 2. Процессы и синхронизация 79
Lamport, L. 1977a. Proving the correctness of multiprocess programs. IEEE Trans, on Software Engr. SE-3, 2 (March): 125-143.
Lamport, L. 1977b. Concurrent reading and writing. Cumm.ACM2Q, 11 (November): 806-811.
Lehman, D., A. Pnueli, and J. Stavii. 1981. Impartiality, justice, and fairness: The ethics of concurrent termination. Proc. Eighth Cotton, on Automata, Langs., and Prog., Lecture Notes in Computer Science Vol. 115.
Andrews, G. R., and J. R. McGraw. 1977. Language features for process interaction. Proc. ACM Conference on Language Design for Reliable Software. SIGPLA.N Notices 12, 3 (March): 114-127.
Brinch Hansen, P. 1972. Structured multiprogramming. Comm. ACM 15, 7 (July), 574-578. Brinch Hansen, P. 1973. Operating System Principles. Englewood Cliffs. NJ: Prentice-Hall.
Brinch Hansen, P. 1975. The programming language Concurrent Pascal. IEEE Trans, on Software Engr. SE-1,2 (June): 199-206.
206 Часть 1. Программирование с разделяемыми переменными
5.2. Рассмотрим монитор Shortest_Job_Next в листинге 5.5. Будет ли этот монитор правильно работать при порядке сигнализации "сигнализировать и ожидать"? Если да, объясните, почему. Если нет, внесите необходимые изменения.
5.3. Рассмотрим следующее решение задачи распределения ресурсов со стратегией планирования "кратчайшее задание" из раздела 5.2.
monitor SJN {
bool free = true; cond turn;
procedure request(int time) {
if (Ifree)
wait(turn, time);
free = false; }
procedure release() { free = true; signal(turn); } }
Правильно ли это решение при порядке "сигнализировать и продолжить"? Правильно ли оно при порядке "сигнализировать и ожидать"? Обоснуйте свои ответы.
' 5.4. Следующие задачи касаются монитора в листинге 5.4. Предположим, что во всех четырех задачах использована семантика "сигнализировать и продолжить":
а) пусть нет операции signal_all. Измените решение, чтобы использовалась только операция signal;
б) измените решение, чтобы преимущество получали писатели, а не читатели;
в) измените решение, чтобы при одновременной попытке доступа к базе данных писатели и читатели работали с ней по очереди;
г) измените решение, чтобы читатели и писатели получали право доступа к базе данных в порядке FCFS (first come, first served — первым пришел, первым обслужен). Разрешите читателям параллельно работать с базой данных, если это не нарушает порядка FCFS получения права доступа.
