Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 68
Текст из файла (страница 68)
Мы просто-напросто сериализуем исходную процедуруexchange сериализаторами обоих счетов:(define (serialized-exchange account1 account2)(let ((serializer1 (account1 ’serializer))(serializer2 (account2 ’serializer)))((serializer1 (serializer2 exchange))account1account2)))Упражнение 3.43.Предположим, что значения баланса на трех счетах вначале равны 10, 20 и 30 долларам, и чтонесколько процессов занимаются обменом значений баланса. Покажите, что если эти процессы выполняются последовательно, то после любого количества обменов значения баланса по-прежнемубудут равны 10, 20 и 30 долларам, в каком-то порядке.
Нарисуйте временную диаграмму вроде той,которая изображена на рис. 3.29, и покажите, что указанное условие может нарушаться, если работает первая версия процедуры обмена из этого раздела. Покажите, с другой стороны, что даже спервой программой exchange общая сумма балансов на счетах сохранится. Нарисуйте временнуюдиаграмму, показывающую, что если бы мы не сериализовали транзакции по отдельным счетам,это условие тоже могло бы нарушаться.Упражнение 3.44.Рассмотрим задачу переноса денег с одного счета на другой. Бен Битобор утверждает, что ее можно решить с помощью следующей процедуры, даже в тех случаях, когда много людей одновременноперемещают деньги между различными счетами, если использовать при этом какой-то механизм,сериализующий операции занесения на счет и снятия со счета, например, версию make-accountиз нашего текста.(define (transfer from-account to-account amount)((from-account ’withdraw) amount)((to-account ’deposit) amount))Хьюго Дум считает, что с этой версией возникнут проблемы и что нужно использовать болеесложный подход, вроде того, который требуется при решении задачи обмена.
Прав ли он? Еслинет, то в чем состоит существенная разница между задачей перевода денег и задачей обменасчетов? (Нужно предположить, что значение баланса на from-account по крайней мере равноamount.)Упражнение 3.45.Хьюго Дум полагает, что теперь, когда операции снятия денег со счета и занесения их на счет перестали сериализовываться автоматически, система банковских счетов стала неоправданно сложнойсчетом автоматически.294Глава 3. Модульность, объекты и состояниеи работать с ней правильным образом чересчур трудно.
Он предлагает сделать так, чтобы makeaccount-and-serializer экспортировал сериализатор (для использования в процедурах вродеserialized-exchange), и вдобавок сам использовал его для сериализации простых операцийсо счетом, как это делал make-account. Он предлагает переопределить объект-счет так:(define (make-account-and-serializer balance)(define (withdraw amount)(if (>= balance amount)(begin (set! balance (- balance amount))balance)"Недостаточно денег на счете"))(define (deposit amount)(set! balance (+ balance amount))balance)(let ((balance-serializer (make-serializer)))(define (dispatch m)(cond ((eq? m ’withdraw) (balance-serializer withdraw))((eq? m ’deposit) (balance-serializer deposit))((eq? m ’balance) balance)((eq? m ’serializer) balance-serializer)(else (error "Неизвестный запрос -- MAKE-ACCOUNT"m))))dispatch))(define (deposit account amount)((account ’deposit) amount))Объясните, в чем Хьюго ошибается.
В частности, рассмотрите, что происходит при вызовеserialized-exchange.Реализация сериализаторовМы реализуем сериализаторы на основе более примитивного механизма синхронизации, называемого мьютекс (mutex). Мьютекс — это объект, который поддерживаетдве операции: его можно захватить (acquire), и его можно освободить (release). Когдамьютекс захвачен, никакая другая операция захвата того же самого мьютекса произойтине может, пока его не освободят44 . В нашей реализации каждый сериализатор содержитпо мьютексу. Получая процедуру p, сериализатор возвращает процедуру, которая захватывает мьютекс, выполняет p, и затем освобождает мьютекс.
Благодаря этому, толькоодна из процедур, порожденных сериализатором, может исполняться в каждый моментвремени. Именно такого поведения мы и хотели добиться от сериализации.44 Название«мьютекс» происходит от английского mutual exclusion «взаимное исключение». Общая проблема построения механизма, который позволил бы параллельным процессам безопасно разделять ресурсы,называется проблемой взаимного исключения. Наши мьютексы являются простым вариантом механизма семафоров (semaphores) (см.
упражнение 3.47), которые впервые появились в Системе МультипрограммированияTHE, разработанной в Эйндховенском Техническом Университете и названной по первым буквам голландскогоназвания этого учебного заведения (Dijkstra 1968a). Операции захвата и освобождения изначально называлисьP и V, от голландских глаголов passeren (пройти) и vrijgeven (освободить), употребляемых по отношению к семафорам на железных дорогах.
Классическое описание Дейкстры (Dijkstra 1968b) было одним из первых ясныхизложений вопросов управления параллелизмом, и там было показано, как решаются при помощи семафоровразличные задачи.3.4. Параллелизм: время имеет значение295(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)true(begin (set-car! cell true)false)))Однако эта реализация test-and-set!, как она есть, не годится. Здесь есть важная тонкость, и именно здесь управление параллелизмом становится частью системы:операция test-and-set! должна производиться атомарно (atomically). Это значит,что мы должны гарантировать, что когда процесс протестировал ячейку и убедился, чтоее значение ложь, значение будет установлено в истину прежде, чем какой-либо еще процесс успеет проверить ячейку. Если мы такую гарантию не обеспечим, мьютекс можетсломаться таким же образом, как банковский счет на рис. 3.29. (См.
упражнение 3.46.)45 В большинстве систем разделения времени процессы, блокированные на мьютексе, не тратят время в«занятом ожидании», как это описано здесь. Вместо этого система назначает на исполнение другой процесс,пока первый ждет, а когда мьютекс освобождается, она будит заблокированный процесс.Глава 3.
Модульность, объекты и состояние296Реализация test-and-set! зависит от того, как наша система на самом деле управляет параллельными процессами. Например, мы можем выполнять параллельные процессы на последовательном процессоре при помощи механизма разделения времени, которыйперебирает процессы по очереди, дает каждому из них выполняться в течение небольшого промежутка времени, а затем прерывает его и переходит к следующему процессу.В таком случае test-and-set! может запрещать смену процесса в момент между проверкой и присваиванием46.
С другой стороны, в многопроцессорных компьютерах бываюткоманды, которые обеспечивают атомарные операции прямо на уровне аппаратуры47 .Упражнение 3.46.Допустим, что мы реализуем test-and-set в виде обыкновенной процедуры, как показано втексте, не пытаясь сделать ее атомарной. Нарисуйте временную диаграмму, подобную диаграммена рис. 3.29, и покажите, как реализация мьютекса может ошибиться и позволить двум процессамодновременно захватить мьютекс.Упражнение 3.47.Семафор (размера n) представляет собой обобщение мьютекса. Подобно мьютексу, семафор поддерживает операции захвата и освобождения, но захватить его одновременно могут до n процессов.Прочие процессы, которые попытаются захватить семафор, должны будут ждать освобождения.Дайте реализацию семафорова.
в терминах мьютексов.б. в терминах атомарных операций test-and-set!.ТупикТеперь, когда мы рассмотрели, как реализуются сериализаторы, мы убеждаемся, чтос обменом счетов по-прежнему связаны проблемы, даже с вышеописанной процедуройserialized-exchange. Допустим, что Петр хочет обменять a1 и a2, а Павел в то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 Есть много вариантов таких команд — включая проверку-и-установку, проверку-и-сброс, обмен, сравнениеи-обмен, загрузку с резервированием и условную запись, — и их форма должна точно соответствовать интерфейсу между процессором и памятью в данной машине.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
