Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Требования к взаимным исключениям
|
|
Содержание
Требования к взаимным исключениям.. 2
1.1. Взаимоисключения: Программный подход. 2
1.1.1. Алгоритм Деккера. 3
1.1.2. Алгоритм Петерсона. 7
1.1.3. Алгоритм булочной (Bakery algorithm) 9
1.2. Взаимоисключения: Аппаратная поддержка. 9
1.2.1. Отключение прерываний. 9
1.2.2. Специальные машинные команды.. 10
1.3. Мониторы.. 12
1.3.1. Мониторы с сигналами. 13
1.3.2. Мониторы с оповещением и широковещанием.. 15
1.4. Сообщения. 16
1.4.1. Синхронизация. 17
1.4.2. Адресация. 18
1.4.3. Формат сообщения. 19
1.4.4. Принцип работы очереди. 19
Таблица. Взаимодействие процессов
| Степень осведомленности | Взаимосвязь | Влияние одного процесса на другой | Потенциальные проблемы |
| Процессы не осведомлены друг о друге | Конкуренция | – Результат работы одного процесса не зависит от действий других – Возможно влияние одного процесса на время работы другого | – Взаимоисключения – Взаимоблокировки(возобновляемые ресурсы) – Голодание |
| Процессы косвенно осведомлены о наличии друг друга | Сотрудничество с использованием разделения | – Результат работы одного процесса может зависеть от информации, полученной от других – Возможно влияние одного процесса на время работы другого | – Взаимоисключения Взаимоблокировки (возобновляемые ресурсы) – Голодание – Связь данных |
| Процессы непосредственно осведомлены о наличии друг друга | Сотрудничество с использованием связи | – Результат работы одного процесса может зависеть от информации, полученной от других – Возможно влияние одного процесса на время работы другого | – Взаимоблокировки(расходуемые ресурсы) Голодание |
Требования к взаимным исключениям
Любая возможность обеспечения поддержки взаимных исключений должна соответствовать следующим требованиям.
· Взаимоисключения должны осуществляться в принудительном порядке. В любой момент времени из всех процессов, имеющих критический раздел для одного и того же ресурса или разделяемого объекта, в этом разделе может находиться лишь только один процесс.
· Процесс, завершающий работу в некритическом разделе, не должен влиять на другие процессы.
· Не должна возникать ситуация бесконечного ожидания доступа к критическому разделу (т.е. не должны появляться взаимоблокировки и голодание).
· Когда в критическом разделе нет ни одного процесса, любой процесс, запросивший возможность входа в него, должен немедленно ее получить.
· Не делается никаких предположений о количестве процессов или их относительных скоростях работы.
· Процесс остается в критическом разделе только в течение ограниченного времени.
1.1. Взаимоисключения: Программный подход
Программный подход может быть реализован для параллельных процессов, которые выполняются как в однопроцессорной, так и в многопроцессорной системе с разделяемой основной памятью. Обычно такие подходы предполагают элементарные взаимоисключения на уровне доступа к памяти — т.е. одновременный доступ (чтение и/или запись) к одной и той же ячейке основной памяти упорядочивается при помощи некоторого механизма (при этом порядок предоставления доступа не определяется порядком обращения процессов за доступом к памяти). Никакой иной поддержки со стороны аппаратного обеспечения, операционной системы или языка программирования не предполагается.