реализации каждый сериализатор содержит по мьютексу. Получая процедуру p, сериализатор возвращает процедуру, которая захватывает мьютекс, выполняет p, и затем освобождает мьютекс. Благодаря этому, только одна из процедур, порожденных сериализатором, может исполняться в каждый момент времени. Именно такого поведения мы и хотели добиться от сериализации.

(define (make-serializer) (let ((mutex (make-mutex))) (lambda (p)

(define (serialized-p . args) (mutex acquire) (let ((val (apply p args))) (mutex release)

val))

serialized-p)))

Мьютекс - изменяемый объект (здесь мы используем одноэлементный список, который будем называть ячейкой (cell)), способный хранить значение истина или ложь. Когда значение ложно, мьютекс можно захватывать. Когда значение истинно, мьютекс недоступен, и процесс, который попытается его захватить, вынужден будет ждать.

Конструктор мьютекса make-mutex для начала присваивает содержимому ячейки значение ложь. Для захвата мьютекса мы проверяем значение ячейки. Если мьютекс доступен, мы делаем значение истинным и идем дальше. Если нет, мы входим в цикл ожидания, все время пытаясь захватить мьютекс, пока он не окажется свободным.45 Чтобы освободить мьютекс, мы присваиваем значению ячейки ложь.

(define (make-mutex)

(let ((cell (list false)))

(define (the-mutex m) (cond ((eq? m acquire)

(if (test-and-set! cell) (the-mutex acquire))) ((eq? m release) (clear! cell)))) the-mutex))

Test-and-set! проверяет ячейку и возвращает результат проверки. Помимо того, если значение было ложным, test-and-set! устанавливает значение в истину, прежде чем вернуть ложь. Мы можем описать это поведение так:

(define (test-and-set! cell) (if (car cell)

стым вариантом механизма семафоров (semaphores) (см. упражнение 3.47), которые впервые появились в Системе Мультипрограммирования THE, разработанной в Эйндховенском Техническом Университете и названной по первым буквам голландского названия этого учебного заведения (Dijkstra 1968a). Операции захвата и освобождения изначально назывались P и V, от голландских глаголов passeren (пройти) и vrijgeven (освободить), употребляемых по отношению к семафорам на железных дорогах. Классическое описание Дейкстры (Dijkstra 1968b) было одним из первых ясных изложений вопросов управления параллелизмом, и там было показано, как решаются при помощи семафоров различные задачи.

45 В большинстве систем разделения времени процессы, блокированные на мьютексе, не тратят время в «занятом ожидании», как это описано здесь. Вместо этого система назначает на исполнение другой процесс, пока первый ждет, а когда мьютекс освобождается, она будит заблокированный процесс.

true

(begin (set-car! cell true)

false)))

Однако эта реализация test-and-set!, как она есть, не годится. Здесь есть важная тонкость, и именно здесь управление параллелизмом становится частью системы: операция test-and-set! должна производиться атомарно (atomically). Это значит, что мы должны гарантировать, что когда процесс протестировал ячейку и убедился, что ее значение ложь, значение будет установлено в истину прежде, чем какой-либо еще процесс успеет проверить ячейку. Если мы такую гарантию не обеспечим, мьютекс может сломаться таким же образом, как банковский счет на рис. 3.29. (См. упражнение 3.46.)

Реализация test-and-set! зависит от того, как наша система на самом деле управляет параллельными процессами. Например, мы можем выполнять параллельные процессы на последовательном процессоре при помощи механизма разделения времени, который перебирает процессы по очереди, дает каждому из них выполняться в течение небольшого промежутка времени, а затем прерывает его и переходит к следующему процессу. В таком случае test-and-set! может запрещать смену процесса в момент между проверкой и присваива-нием.46 С другой стороны, в многопроцессорных компьютерах бывают команды, которые обеспечивают атомарные операции прямо на уровне аппаратуры. 47

Упражнение 3.46.

Допустим, что мы реализуем test-and-set в виде обыкновенной процедуры, как показано в тексте, не пытаясь сделать ее атомарной. Нарисуйте временную диаграмму, подобную диаграмме на рис. 3.29, и покажите, как реализация мьютекса может ошибиться и позволить двум процессам одновременно захватить мьютекс.

Упражнение 3.47.

Семафор (размера n) представляет собой обобщение мьютекса. Подобно мьютексу, семафор поддерживает операции захвата и освобождения, но захватить его одновременно

46В MIT Scheme на однопроцессорной системе можно реализовать test-and-set! следующим образом:

(define (test-and-set! cell) (without-interrupts (lambda ()

(if (car cell) true

(begin (set-car! cell true)

false)))))

Without-interrupts запрещает прерывания по таймеру, пока выполняется его процедурный аргумент.

47Есть много вариантов таких команд - включая проверку-и-установку, проверку-и-сброс, обмен, сравнение-и-обмен, загрузку с резервированием и условную запись, - и их форма должна точно соответствовать интерфейсу между процессором и памятью в данной машине. Один из возникающих вопросов состоит в том, что происходит, когда два процесса пытаются получить один и тот же ресурс в точности одновременно при помощи такой команды. Тут требуется какой-то механизм, принимающий решение, который из процессов получает управление. Такой механизм называется арбитром (arbiter). Обычно арбитры представляют собой аппаратные устройства. К сожалению, можно доказать, что нельзя построить справедливого арбитра, работающего в 100% случаев, если не позволять арбитру принимать решение неопределенно долгое время. Сущность этого явления была открыта французским философом XIV века Жаном Буриданом в комментарии к De caelo Аристотеля. Буридан указал, что идеально разумная собака, помещенная между двумя одинаково привлекательными кусками еды, должна умереть от голода, поскольку она не сможет решить, к какому куску идти в первую очередь.

могут до n процессов. Прочие процессы, которые попытаются захватить семафор, должны будут ждать освобождения. Дайте реализацию семафоров

a.в терминах мьютексов.

b.в терминах атомарных операций test-and-set! . Тупик

Теперь, когда мы рассмотрели, как реализуются сериализаторы, мы убеждаемся, что с обменом счетов по-прежнему связаны проблемы, даже с вышеописанной процедурой serialized-exchange. Допустим, что Петр хочет обменять al и а2, а Павел в то же время пытается обменять а2 и al. Допустим, что процесс Петра доходит до некоторой точки внутри сериализованной процедуры, защищающей а1, и сразу вслед за этим процесс Павла входит в се-риализованную процедуру, защищающую а2. Теперь Петр не может двигаться дальше (ему надо войти в сериализованную процедуру для а2), пока Павел не выйдет из сериализованной процедуры для а2. Точно так же Павел не может двигаться дальше, пока Петр не выйдет из сериализованной процедуры для а1. Оба процесса замирают навеки в ожидании друг друга. Такая ситуация называется тупик (deadlock). В любой системе, которая предоставляет доступ к множественным разделяемым ресурсам, существует опасность тупика.

В этой ситуации можно избежать тупика, если присвоить каждому счету уникальный идентификационный номер, и переписать serialized-exchange так, чтобы процесс всегда пытался сначала войти в процедуру, которая защищает счет с наименьшим номером. Хотя для задачи обмена это решение работает хорошо, бывают и другие ситуации, в которых требуются более развитые методы избежания тупиков, или где тупика нельзя избежать в принципе. (См. упражнения 3.48 и 3.49.)48

Упражнение 3.48.

Подробно объясните, почему метод избежания тупиков, описанный выше (т. е. счета нумеруются, и каждый процесс сначала пытается захватить счет с меньшим номером), в самом деле позволяет избежать тупика в задаче обмена балансов. Перепишите serialized-exchange с использованием этой идеи. (Придется также изменить make-account, так, чтобы каждый счет создавался вместе с номером, и чтобы этот номер можно было считать, послав соответствующее сообщение.)

Упражнение 3.49.

Опишите сценарий, в котором вышеописанный механизм избежания тупиков не работает. (Подсказка: в задаче обмена счетов каждый процесс заранее знает, к каким счетам ему нужен будет доступ. Рассмотрите ситуацию, в которой процессу нужно сначала получить доступ к каким-то разделяемым ресурсам, прежде чем он сможет определить, какие ресурсы ему потребуются дополнительно.)

48Общий метод избежания тупиков путем нумерации разделяемых ресурсов и захвата их по порядку придумал Хейвендер (Havender 1968). В ситуациях, где тупика нельзя избежать, нужны меры по выходу из тупика (deadlock recovery), когда от процессов требуется «откатиться» из тупикового состояния и повторить попытку. Механизмы выхода из тупика широко используются в системах управления базами данных. Эта тема детально рассматривается у Грея и Рейтера (Gray

and Reuter 1993).