SICP - упражнение 3.43 - проблемы параллелизма и сериализации
От SICP
Существует процедура, называемая make-account. Он создает объект, состояние которого называется балансом, а внутренние процедуры снятия и внесения. Существует еще одна процедура, называемая exchange, которая обменивает остаток на счетах.
Упражнение 3.43. Предположим, что остатки на трех счетах начинаются с 10, 20 и 30 долларов, и выполняется несколько процессов, обменивающих остатки на счетах. Утверждают, что если процессы выполняются последовательно, после любого количества одновременных обменов, остатки на счетах должны составлять 10, 20 и 30 долларов в некотором порядке. Нарисуйте временную диаграмму, подобную приведенной на рис. 3.29, чтобы показать, как это условие может быть нарушено, если обмены будут реализованы с использованием первой версии программы обмена учетными записями в этом разделе. С другой стороны, утверждают, что даже с этой программой обмена сумма остатков на счетах будет сохранена. Нарисуйте временную диаграмму, чтобы показать, как было бы нарушено даже это условие, если бы мы не сериализовали транзакции на отдельных счетах.
Мои ответы:
Предположим, что сальдо в трех учетных записях начинаются с 10, 20 и 30 долл. США, и выполняется несколько процессов, обменивающих остатки на счетах. Утверждают, что если процессы выполняются последовательно, после любого количества одновременных обменов, остатки на счетах должны составлять 10, 20 и 30 долларов в некотором порядке.
Вот текущая сериализованная процедура.
(define (serialized-exchange account1 account2)
(let ((serializer1 (account1 'serializer))
(serializer2 (account2 'serializer)))
((serializer1 (serializer2 exchange))
account1
account2)))
Я не понимаю, о чем спорить. Я думаю, что это совершенно очевидно. Если процессы, выполняющие обмен, являются последовательными, они выполняются один за другим, поэтому чередования не может произойти. Теперь, если они запускаются одновременно, я не думаю, что есть какая-либо разница. Этот код:
(serializer1 (serializer2 exchange))
сериализует всю процедуру обмена. Таким образом, поскольку существует только 3 учетных записи, никакой другой сериализованный обмен не может работать до тех пор, пока текущий обмен не будет завершен. Таким образом, процессы все еще работают последовательно, даже если они работают параллельно.
Нарисуйте временную диаграмму, подобную приведенной на рис. 3.29, чтобы показать, как это условие может быть нарушено, если обмены будут реализованы с использованием первой версии программы обмена учетными записями в этом разделе. С другой стороны, утверждают, что даже с этой программой обмена сумма остатков на счетах будет сохранена.
Я не могу рисовать диаграммы, поэтому я проигнорировал это. Вот первая версия процедуры.
(define (exchange account1 account2)
(let ((difference (- (account1 'balance)
(account2 'balance))))
((account1 'withdraw) difference)
((account2 'deposit) difference)))
(define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance
(- balance amount))
balance)
"Insufficient funds"))
(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 "Unknown request:
MAKE-ACCOUNT"
m))))
dispatch))
В первой версии вывод и депозит сериализуются. Это единственные процедуры, которые изменяют баланс с помощью set!. Проблема с запуском двух процедур с set! S параллельно без сериализации установлена!1, возможно, обновляет баланс до нового значения, не зная, что set!2 уже обновил баланс между set!1, получающим доступ к балансу и обновляющим его. Итак, установка! 2 обновление потеряно. Таким образом, хотя недостаточно просто сериализовать отдельные учетные записи, поскольку порядок пополнения и снятия может чередоваться, деньги не будут потеряны, они просто могут оказаться на разных счетах из-за порядка пополнения и снятия. Я думаю, что худшее, что может случиться, это то, что 1 аккаунт имеет 60, а 2 других имеют 0.
Верны ли мои ответы? Благодарю.