Сложности при использовании множественных разделяемых ресурсов

Сериализаторы предоставляют нам мощную абстракцию, которая позволяет изолировать сложности выполнения параллельных программ, так что мы получаем возможность работать с ними аккуратно (и, будем надеяться, без ошибок). Однако, хотя при работе только с одним разделяемым ресурсом (например, с одним банковским счетом) использовать сериализаторы относительно просто, при наличии множественных разделяемых ресурсов параллельное программирование может быть предательски сложным.

Чтобы проиллюстрировать одну из ряда трудностей, которые могут возникнуть, предположим, что нам требуется поменять местами балансы на двух банковских счетах. Мы читаем каждый счет, чтобы узнать баланс, вычисляем разницу между балансами, снимаем ее с одного счета и кладем на другой. Это можно реализовать следующим образом:41

(define (exchange accountl account2)

(let ((difference (- (accountl balance)

(account2 balance)))) ((accountl withdraw) difference) ((account2 deposit) difference)))

Эта процедура работает правильно в том случае, когда только один процесс пытается осуществить обмен. Допустим, однако, что Петр и Павел имеют доступ к совместным счетам al, a2 и a3, и что Петр меняет местами al и a2, а Павел в то же время обменивает al и a3. Даже если снятие и занесение денег на отдельные счета сериализованы (как в процедуре make-account из предыдущего раздела), exchange может привести к неверным результатам. Например, может оказаться, что Петр посчитает разницу между al и a2, но Павел изменит баланс на al прежде, чем Петр закончит обмен.42 Чтобы добиться правильного поведения, мы должны устроить так, чтобы процедура exchange блокировала всякий параллельный доступ к счетам на все время обмена.

Один из способов этого достичь - сериализовать всю процедуру exchange сериализаторами обоих счетов. Ради этого мы откроем доступ к сериализато-рам счетов. Обратите внимание, что, раскрывая сериализатор, мы намеренно ломаем модульное построение объекта-банковского счета. Следующая версия процедуры make-account идентична исходной версии из раздела 3.1.1, за исключением того, что имеется сериализатор для защиты переменной баланса, и он экспортируется через передачу сообщений:

(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))

41 Мы упростили exchange, пользуясь тем, что наше сообщение deposit может принимать отрицательные суммы. (Для банковской системы это серьезная ошибка!)

42Если балансы на счетах вначале равны 10, 20 и 30 долларам, то после любого количества параллельных обменов балансы должны по прежнему быть 10, 20 и 30, в каком-то порядке. Се-риализации доступа к отдельным счетам недостаточно, чтобы это гарантировать. См. упр. 3.43.

balance)

(let ((balance-serializer (make-serializer))) (define (dispatch m)

(cond ((eq? m withdraw) withdraw) ((eq? m deposit) deposit) ((eq? m balance) balance) ((eq? m serializer) balance-serializer) (else (error "Неизвестный запрос -- MAKE-ACCOUNT"

m))))

dispatch))

С помощью этой версии мы можем выполнять сериализованное занесение и снятие денег. Заметим, однако, что, в отличие от предыдущей версии сери-ализованного счета, теперь каждый пользователь объектов-банковских счетов должен явным образом управлять сериализацией, например, так:43

(define (deposit account amount) (let ((s (account serializer)) (d (account deposit))) ((s d) amount)))

Экспорт сериализатора дает нам достаточно гибкости, чтобы реализовать се-риализованную программу обмена. Мы просто-напросто сериализуем исходную процедуру exchange сериализаторами обоих счетов:

(define (serialized-exchange account1 account2) (let ((serializer1 (account1 serializer)) (serializer2 (account2 serializer))) ((serializer1 (serializer2 exchange)) account1 account2)))

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

Предположим, что значения баланса на трех счетах вначале равны 10, 20 и 30 долларам, и что несколько процессов занимаются обменом значений баланса. Покажите, что если эти процессы выполняются последовательно, то после любого количества обменов значения баланса по-прежнему будут равны 10, 20 и 30 долларам, в каком-то порядке. Нарисуйте временную диаграмму вроде той, которая изображена на рис. 3.29, и покажите, что указанное условие может нарушаться, если работает первая версия процедуры обмена из этого раздела. Покажите, с другой стороны, что даже с первой программой exchange общая сумма балансов на счетах сохранится. Нарисуйте временную диаграмму, показывающую, что если бы мы не сериализовали транзакции по отдельным счетам, это условие тоже могло бы нарушаться.

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

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

43 В упражнении 3.45 рассматривается вопрос, почему занесение и снятие денег теперь не сериа-лизуются счетом автоматически.

(define (transfer from-account to-account amount) ((from-account withdraw) amount) ((to-account deposit) amount))

Хьюго Дум считает, что с этой версией возникнут проблемы и что нужно использовать более сложный подход, вроде того, который требуется при решении задачи обмена. Прав ли он? Если нет, то в чем состоит существенная разница между задачей перевода денег и задачей обмена счетов? (Нужно предположить, что значение баланса на from-account по крайней мере равно amount.)

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

Хьюго Дум полагает, что теперь, когда операции снятия денег со счета и занесения их на счет перестали сериализовываться автоматически, система банковских счетов стала неоправданно сложной и работать с ней правильным образом чересчур трудно. Он предлагает сделать так, чтобы make-account-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 В нашей

44Название «мьютекс» происходит от английского mutual exclusion «взаимное исключение». Общая проблема построения механизма, который позволил бы параллельным процессам безопасно разделять ресурсы, называется проблемой взаимного исключения. Наши мьютексы являются про-