Классические проблемы синхронизации

Проблема ограниченного буфера

С этой задачей мы уже встречались, рассматривая схему «производитель-потребитель». Она обычно используется для иллюстрации возможностей примитивов синхронизации. Представим общую структуру этой схемы, не вдаваясь в детали реализации.

Считаем, что буфер имеет емкость n элементов. Семафор mutex используется для организации взаимно исключаемого доступа к буферу и инициализирован значением 1. Семафоры empty и full подсчитывают число пустых и заполненных элементов буфера, соответственно. Начальное значение empty равно n, а начальное значение full – 0.

Общая схема работы производителя и потребителя представлена ниже.

Производитель: repeat ... produce an item ti nextp ... wait(empty); wait(mutex); ... add nextp to buffer ... signal(mutex); signal(empty); ...   until false;

Потребитель repeat ... wait(full) wait(mutex); ... remove an item from buffer to nextc ... signal(mutex); signal(full); ... consume the item in nextc ... until false;

Заметим очевидную симметрию решения.

Проблема читателей и писателей

Данные (например, файлы или записи) могут разделяться между несколькими параллельными процессами. Некоторые из этих процессов могут только считывать содержимое данных, в то время как другие процессы могут их изменять. Подчеркнем различие между двумя этими типами процессов, назвав первые читателями, а вторые – писателями. Легко видеть, что два читателя могут иметь доступ к данным одновременно безо всякого ущерба. Однако писатель и любой другой процесс не должны иметь такой возможности, так как это может привести к хаосу. Чтобы избежать подобных трудностей, потребуем, чтобы писатель имел исключительный доступ к разделяемому объекту.

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

Заметим, что решение каждой из задач может привести к зависанию. В первом случае могут зависать писатели, а во втором читатели.

Рассмотрим решение первой задачи. В этом решении используются следующие структуры данных:

var mutex, wrt: semaphore;

readcount: integer;

Первоначально семафоры установлены в 1, а переменная readcount в 0. Семафор mutex используется для организации взаимного исключения на момент изменения переменной readcount. Переменная readcount обозначает число процессов, читающих объект в данный момент. Переменная wrt используется для взаимного исключения писателей.

Писатель: wait(wrt); ... writing is performed ... signal(wrt);

Читатель: wait(mutex); readcount:= readcount + 1; if readcount = 1 then wait(wrt); signal(mutex); ... reading is performed ... wait(mutex); readcount:= readcount - 1; if readcount = 0 then signal(wrt); signal(mutex);

Задача об обедающих философах

Представим пять философов, проводящих свою жизнь в раздумьях и еде. Они разделяют общий круглый стол с пятью стульями вокруг, каждый из которых принадлежит одному философу. В центре стола находится блюдо с рисом, между тарелками лежат одиночные палочки для риса. Когда философ думает, он не общается с коллегами. Время от времени, проголодавшись, философ пытается схватить две палочки, лежащие слева и справа от его тарелки. Философ может взять за один прием только одну палочку. Естественно, он не может взять палочку, если она в руках у соседа. Приступить к еде философ может только, если у него в руках две палочки. Когда философ заканчивает еду, то он кладет обе палочки на место и снова начинает думать.

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

Простейшее решение – представить каждую палочку в виде семафора. Философ пытается захватить палочку выполнением операции wait, а освобождает ее с помощью операции signal.

var chopstick: array [0..4] of semaphore;

Каждый элемент массива первоначально инициализируется значением 1.

Схема работы i-го философа будет следующей:

Repeat

wait(chopstick[i]);

wait(chopstick[(i+1) mod 5]);

...

eat

...

signal(chopstick[i]);

signal(chopstick[(i+1) mod 5]);

...

think

...

until false;

Такое решение гарантирует, что два соседа не смогут одновременно есть. Но оно не может быть принято, так как может привести к тупику. Представим, что все пять философов проголодались одновременно и, успели взять по одной палочке. Вторую палочку они уже не смогут взять никогда, так как соответствующий семафор будет иметь значение 0.

Перечислим возможные решения проблемы:

­ разрешить не более, чем четырем философам одновременно садиться за стол;

­ разрешить философу брать палочки, только если обе палочки свободны (появится критический участок);

­ использовать асимметричное решение: нечетный философ сначала берет левую палочку, а четный – правую.

Кроме того, любое решение задачи должно учитывать возможность, что один из философов может умереть от голода. Решение, не допускающее тупика, не обязательно исключает подобную развязку.

Двоичные семафоры

Двоичный семафор – это переменная, которая может принимать только два значения: 0 и 1. Такой семафор проще для реализации с точки зрения компьютерной системы. Однако такие семафоры сложнее для использования.

Рассмотрим, каким образом можно реализовать считающий семафор через двоичный. Нам понадобится переменная для хранения счетчика и три семафора для организации взаимного исключения при доступе к счетчику и блокировок процессов.

var s1,s2,s3: binary_semaphore;

c: integer;

Начальное значение семафоров s1 и s3 – 1, семафора s2 – 0, начальное значение переменной c равно начальному значению счетчика.

Тогда операцию wait можно выразить следующим образом:

wait(s3);

wait(s1);

с:= c - 1;

if c<0 then

Begin

signal(s1);

wait(s2);

End

Else

signal(s1);

signal(s3);

Операция signal будет описываться так:

wait(s1);

с:= c + 1;

if c<=0 then

signal(s2);

signal(s1);

Заметим, что двоичный семафор s2 влияет только на работу операции wait.

Сигналы

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

Примером асинхронного сигнала является сигнал с терминала. Во многих ОС предусматривается оперативное снятие процесса с выполнения. Для этого пользователь может нажать некоторую комбинацию клавиш (Ctrl+C, Ctrl+Break), в результате чего ОС вырабатывает сигнал и направляет его активному процессу. Сигнал может поступить в любой момент выполнения процесса, то есть он является асинхронным, требуя от процесса немедленного завершения работы. В данном случае реакцией на сигнал является безусловное завершение процесса.

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

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

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

Контрольные вопросы

1. Что такое состояние состязания?

2. Что означает термин «взаимное исключение»?

3. Что такое критический участок (секция)?

4. Почему для обеспечения взаимного исключения недостаточно логической переменной?

5. Как команда test and set помогает обеспечить взаимное исключение?

6. Что такое семафор? Как реализуются семафоры?

 

ТУПИКОВЫЕ СИТУАЦИИ

Мультипрограммный режим работы предполагает, что несколько процессов могут конкурировать за получение доступа к конечному количеству ресурсов. Если требуемый ресурс недоступен, то процесс переходит в состояние ожидания. Может случиться, что некоторые процессы так и не выйдут из состояния ожидания, поскольку будут взаимно удерживать необходимые друг другу ресурсы. Такая ситуация называется тупиковой или тупиком (deadlock).