Сериализаторы в Scheme

Чтобы сделать это описание более конкретным, предположим, что мы расширили язык Scheme, добавив в него процедуру parallel-execute:

(parallel-execute (pi) (p.) ... (pk))

Каждый из (p) должен быть процедурой без аргументов. Parallel-execute создает для каждого (p) отдельный процесс, который выполняет (p) (с пустым набором аргументов). Все эти процессы выполняются параллельно.40

Чтобы продемонстрировать, как эта процедура используется, рассмотрим

(define x 10)

(parallel-execute (lambda () (set! x (* x x)))

(lambda () (set! x (+ x 1))))

Здесь создаются два параллельных процесса - Pi, который присваивает x значение x умножить на x, и P2, который увеличивает x на единицу. После того, как вычисление закончено, x может иметь одно из пяти значений, в зависимости от чередования событий в P1 и P2:

•101: P1 делает x равным 100, затем P2 его увеличивает.

•121: P2 увеличивает x, делая его равным 11, затем P1 присваивает ему значение x умножить на x.

•110: P2 изменяет x с 10 на 11 в промежутке между двумя обращениями к x из P1 во время вычисления (* x x).

•11: P2 читает x, затем P1 присваивает ему значение 100, затем P1 пишет

x

•100: P1 читает x (дважды), затем P2 присваивает ему значение 11, затем P1 записывает значение x.

Мы можем ограничить параллелизм, используя сериализованные процедуры, которые создаются сериализаторами (serializers). Сериализаторы порождаются процедурой make-serializer, реализация которой дана ниже. Сериали-затор принимает в качестве аргумента процедуру, и возвращает сериализован-ную процедуру с таким же поведением. Все вызовы сериализатора порождают сериализованные процедуры, принадлежащие одному множеству.

Таким образом, в отличие от предыдущего примера, выполнение

(define x 10)

(define s (make-serializer))

(parallel-execute (s (lambda () (set! x (* x x)))) (s (lambda () (set! x (+ x 1)))))

может иметь только два результата, 101 и 121. Остальные возможности отбрасываются, поскольку выполнение P1 и P2 не может чередоваться.

Ниже приведена версия процедуры make-account из раздела 3.1.1, в которой помещение денег на счет и снятие их со счета сериализованы:

40Parallel-execute не входит в стандартную Scheme, но такая процедура может быть реализована в MIT Scheme. В нашей реализации новые процессы выполняются параллельно еще и с исходным Scheme-процессом. Кроме того, в нашей реализации значение, которое возвращает parallel-execute, представляет собой специальный управляющий объект, с помощью которого можно остановить все новосозданные процессы.

(define (make-account balance) (define (withdraw amount) (if (>= balance amount)

(begin (set! balance (- balance amount))

balance) "Недостаточно денег на счете")) (define (deposit amount)

(set! balance (+ balance amount)) balance)

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

(cond ((eq? m withdraw) (protected withdraw)) ((eq? m deposit) (protected deposit)) ((eq? m balance) balance)

(else (error "Неизвестный запрос -- MAKE-ACCOUNT"

m))))

dispatch))

В такой реализации два процесса не могут параллельно помещать деньги на счет или снимать их. Таким образом устраняется источник ошибки, показанной на рис. 3.29, где Петр изменяет баланс на счете в промежутке между моментами, когда Павел считывает значение баланса, и когда он производит присваивание. С другой стороны, у каждого счета свой собственный сериализатор, так что операции с различными счетами могут происходить параллельно.

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

Какие из пяти возможных исходов параллельного выполнения сохраняются, если мы сериализуем выполнение таким образом:

(define x l0)

(define s (make-serializer))

(parallel-execute (lambda () (set! x ((s (lambda () (* x x))))))

(s (lambda () (set! x (+ x l)))))

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

Укажите все возможные значения x при выполнении (define x l0)

(parallel-execute (lambda () (set! x (* x x)))

(lambda () (set! x (* x x x))))

Какие из них сохраняются, если вместо этого мы выполняем сериализованные процедуры:

(define x l0)

(define s (make-serializer))

(parallel-execute (s (lambda () (set! x (* x x))))

(s (lambda () (set! x (* x x x)))))

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

Бен Битобор считает, что лучше было бы реализовать банковский счет таким образом (измененная строка отмечена комментарием):

(define (make-account balance) (define (withdraw amount) (if (>= balance amount)

(begin (set! balance (- balance amount))

balance) "Недостаточно денег на счете")) (define (deposit amount)

(set! balance (+ balance amount)) balance)

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

(cond ((eq? m withdraw) (protected withdraw)) ((eq? m deposit) (protected deposit)) ((eq? m balance)

((protected (lambda () balance)))) ; сериализовано (else (error "Неизвестный запрос -- MAKE-ACCOUNT"

m))))

dispatch))

поскольку несериализованный доступ к банковскому счету может привести к неправильному поведению. Вы согласны? Существует ли сценарий, который демонстрирует обоснованность беспокойства Бена?

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

Бен Битобор говорит, что слишком расточительно в ответ на каждое сообщение withdraw и deposit создавать по новой сериализованной процедуре. Он говорит, что можно изменить make-account так, чтобы все вызовы protected происходили вне процедуры dispatch. Таким образом, счет будет возвращать одну и ту же сериализованную процедуру (созданную тогда же, когда и сам счет) каждый раз, когда у него просят процедуру снятия денег:

(define (make-account balance) (define (withdraw amount) (if (>= balance amount)

(begin (set! balance (- balance amount))

balance) "Недостаточно денег на счете")) (define (deposit amount)

(set! balance (+ balance amount)) balance)

(let ((protected (make-serializer)))

(let ((protected-withdraw (protected withdraw)) (protected-deposit (protected deposit))) (define (dispatch m)

(cond ((eq? m withdraw) protected-withdraw) ((eq? m deposit) protected-deposit) ((eq? m balance) balance)

(else (error "Неизвестный запрос -- MAKE-ACCOUNT"

m))))

dispatch)))

Безопасно ли такое изменение? В частности, есть ли разница в том, в каком порядке может происходить параллельное выполнение в этих двух версиях make-account?