|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[93] Сложности при использовании множественных разделяемых ресурсов Сериализаторы предоставляют нам мощную абстракцию, которая позволяет изолировать сложности выполнения параллельных программ, так что мы получаем возможность работать с ними аккуратно (и, будем надеяться, без ошибок). Однако, хотя при работе только с одним разделяемым ресурсом (например, с одним банковским счетом) использовать сериализаторы относительно просто, при наличии множественных разделяемых ресурсов параллельное программирование может быть предательски сложным. Чтобы проиллюстрировать одну из ряда трудностей, которые могут возникнуть, предположим, что нам требуется поменять местами балансы на двух банковских счетах. Мы читаем каждый счет, чтобы узнать баланс, вычисляем разницу между балансами, снимаем ее с одного счета и кладем на другой. Это можно реализовать следующим образом: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 «взаимное исключение». Общая проблема построения механизма, который позволил бы параллельным процессам безопасно разделять ресурсы, называется проблемой взаимного исключения. Наши мьютексы являются про- |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||