Задание №2. Организация, синхронизация процессов с помощью семафоров.
Семафоры являются обобщением блокирующих переменных. Вместо двоичных переменных Дийкстра (Dijkstra) предложил использовать переменные, которые могут принимать целые неотрицательные значения. Такие переменные, используемые для синхронизации вычислительных процессов, получили название семафоров.
Для работы с семафорами вводятся два примитива, обозначаемых Р и V. Пусть переменная S представляет собой семафор. Тогда действия V(S) и P(S) определяются следующим образом.
V(S) - переменная S увеличивается на 1 единым действием. Выборка, наращивание и запоминание не могут быть прерваны. К переменной S нет доступа другим потокам во время выполнения этой операции.
P(S) – переменная S уменьшается на 1, если это возможно. Если S=0 и невозможно уменьшить S, оставаясь в области целых неотрицательных значений, то в этом случае поток, вызывающий операцию Р, ждет пока это уменьшение станет возможным. Проверка и уменьшение также являются неделимой операцией. В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную, которую по этой причине часто называют двоичным семафором (мьютексом). Операция Р заключает в себе потенциальную возможность перехода потока, который ее выполняет, в состояние ожидания, в то время как операция V может при некоторых обстоятельства активизировать другой поток, приостановленный операцией Р.
Рассмотрим использование семафоров на классическом примере взаимодействия двух выполняющихся в режиме мультипрограммирования потоков, один из которых пишет данные в буферный пул, а другой считывает их из буферного пула. Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись. В общем случае поток-писатель и поток-читатель могут иметь различные скорости и обращаться к буферному пулу с переменой интенсивностью. В один период скорость записи может превышать скорость чтения, в другой – наоборот. Для правильной совместной работы поток-писатель должен приостанавливаться, когда все буферы оказываются занятыми, и активизироваться при освобождении хотя бы одного буфера. Напротив, поток-читатель должен приостанавливаться, когда все буферы пусты, и активизироваться при появлении хотя бы одной записи.
Введем два семафора: е – число пустых буферов и f – число заполненных буферов, причем в исходном состоянии е=N, а f=0. Тогда работа потоков с общим буферным пулом может быть описана следующим образом (рис.3.3).
Поток-писатель прежде всего выполняет операцию P(e), с помощью которой он проверяет, имеются ли в буферном пуле незаполненные буферы. В соответствии с семантикой операции Р, если семафор е=0 (то есть свободных буферов в данный момент нет), то поток-писатель переходит в состояние ожидания.
Если же значением е является положительное число, то он уменьшает число свободных буферов, записывает данные в очередной свободный буфер и после этого наращивает число занятых буферов операцией V(f). Поток-читатель действует аналогичным образом, с той разницей, что он начинает работу с проверки наличия заполненных буферов, а после чтения данных наращивает количество свободных буферов.
Семафор может использоваться и в качестве блокирующей переменной. В рассмотренном выше примере, для того чтобы исключить коллизии при работе с разделяемой областью памяти, будем считать, что запись в буфер и считывание из буфера являются критическими секциями.
Взаимное исключение будем обеспечивать с помощью двоичного семафора b.
Оба потока после проверки доступности буферов должны выполнить проверку доступности критической секции.
Отличие семафоров и блокирующих переменных в том, что в семафорах есть «пассивное ожидание».
Инициализация семафора включает в себя имя семафора и начальное значение: InitSem (имя семафора, начальное значение).
P(S): S:=S – 1;
If S<0 then {ставит процесс в очередь семафора S}
V(S): If S<0 then {поместить один из ожидающих процессов очереди семафора S в очередь готовности}
S:=S+1.
Разработаем программу взаимной синхронизации процесса-писателя и процесса-читателя при доступе к буферному пулу. Задачу решить на основе семафоров.
Программа организации синхронизации процессов на основе семафоров выглядит следующим образом:
#define N 100 /* количество сегментов в буфере */
typedef int semaphore; /* семафоры - особый вид целочисленных переменных */
semaphore mutex - 1: /* контроль доступа в критическую область */
semaphore empty - N; /* число пустых сегментов буфера */
semaphore full - 0: /* число полных сегментов буфера */
void producer(void)
{
int item;
while (TRUE) { /* TRUE - константа, равная 1*/
item - produce_item(); /* создать данные, помещаемые в буфер */
down(Sempty); /* уменьшить счетчик пустых сегментов буфера */
down(&mutex); /* вход в критическую область */
insert_item(item); /* поместить в буфер новый элемент */
up(&mutex); /* выход из критической области */
upC&fulI): /* увеличить счетчик полных сегментов буфера */}}
void consumer(void)
{
int item;
while (TRUE) { /* бесконечный цикл */
down(SfuTI); /* уменьшить числа полных сегментов буфера */
down(&mutex): /* вход в критическую область */
item = remove_item(); /* удалить элемент из буфера */
up(&mutex); /* выход из критической области */
up(&empty): /* увеличить счетчик пустых сегментов буфера */
consume_item(item); /* обработка элемента */
} }
В представленном решении используются три семафора: один для подсчета заполненных сегментов буфера {full), другой для подсчета пустых сегментов {empty), а третий предназначен для исключения одновременного доступа к буферу производителя и потребителя {mutex). Значение счетчика full исходно равно нулю, счетчик empty равен числу сегментов в буфере, a mutex равен 1. Семафоры, исходное значение которых равно 1, используемые для исключения одновременного нахождения в критической области двух процессов, называются двоичными семафорами. Взаимное исключение обеспечивается, если каждый процесс выполняет операцию down перед входом в критическую область и up после выхода из нее.
Достоинство семафора: ожидание пассивное и может синхронизировать несколько процессов.
При одновременном доступе нескольких процессов (или нескольких потоков одного процесса) к какому-либо ресурсу возникает проблема синхронизации. Поскольку поток в Win32 может быть остановлен в любой, заранее ему неизвестный момент времени, возможна ситуация, когда один из потоков не успел завершить модификацию ресурса (например, отображенной на файл области памяти), но был остановлен, а другой поток попытался обратиться к тому же ресурсу. В этот момент ресурс находится в несогласованном состоянии, и последствия обращения к нему могут быть самыми неожиданными — от порчи данных до нарушения защиты памяти.
Синхронизация с помощью семафоров ОС Windows приведена ниже.
Семафор представляет собой счетчик, содержащий целое число в диапазоне от 0 до максимальной величины, заданной при его создании. Счетчик уменьшается каждый раз, когда поток успешно завершает функцию ожидания, использующую семафор, и увеличивается путем вызова функции ReleaseSemaphore. При достижении семафором значения 0 он переходит в несигнальное состояние, при любых других значениях счетчика его состояние — сигнальное. Такое поведение позволяет использовать семафор в качестве ограничителя доступа к ресурсу, поддерживающему заранее заданное количество подключений.
Для создания семафора служит функция CreateSemaphore:
function CreateSemaphore(
lpSemaphoreAttributes: PSecurityAttributes; // Адрес структуры
// TSecurityAttributes
lInitialCount, // Начальное значение счетчика
lMaximumCount: Longint; // Максимальное значение счетчика
lpName: PChar // Имя объекта
): THandle; stdcall;
Функция возвращает идентификатор созданного семафора либо 0, если создать объект не удалось.
Параметр lMaximumCount задает максимальное значение счетчика семафора, lInitialCount задает начальное значение счетчика и должен быть в диапазоне от 0 до lMaximumCount. lpName задает имя семафора. Если в системе уже есть семафор с таким именем, то новый не создается, а возвращается идентификатор существующего семафора. В случае если семафор используется внутри одного процесса, можно создать его без имени, передав в качестве lpName значение NIL. Имя семафора не должно совпадать с именем уже существующего объекта типов event, mutex, waitable timer, job или file-mapping.
Идентификатор ранее созданного семафора может быть также получен функцией OpenSemaphore:
function OpenSemaphore(
dwDesiredAccess: DWORD; // Задает права доступа к объекту
bInheritHandle: BOOL; // Задает, может ли объект наследоваться
// дочерними процессами
lpName: PChar // Имя объекта
): THandle; stdcall;
Параметр dwDesiredAccess может принимать одно из следующих значений:
|
SEMAPHORE_ALL_ACCESS |
Поток получает все права на семафор |
|
SEMAPHORE_MODIFY_STATE |
Поток может увеличивать счетчик семафора функцией ReleaseSemaphore |
|
SYNCHRONIZE |
Только для Windows NT — поток может использовать семафор в функциях ожидания |
Для увеличения счетчика семафора используется функция ReleaseSemaphore:
function ReleaseSemaphore(
hSemaphore: THandle; // Идентификатор семафора
lReleaseCount: Longint; // Счетчик будет увеличен на эту величину
lpPreviousCount: Pointer // Адрес 32-битной переменной,
// принимающей предыдущее значение
// счетчика
): BOOL; stdcall;
Если значение счетчика после выполнения функции превысит заданный для него функцией CreateSemaphore максимум, то ReleaseSemaphore возвращает FALSE и значение семафора не изменяется. В качестве параметра lpPreviousCount можно передать NIL, если это значение нам не нужно.
Рассмотрим пример приложения, запускающего на выполнение несколько заданий в отдельных потоках (например, программа для фоновой загрузки файлов из Internet). Если количество одновременно выполняющихся заданий будет слишком велико, то это приведет к неоправданной загрузке канала. Поэтому реализуем потоки, в которых будет выполняться задание, таким образом, чтобы когда их количество превышает заранее заданную величину, то поток бы останавливался и ожидал завершения работы ранее запущенных заданий:
unit LimitedThread;
interface
uses Classes;
type
TLimitedThread = class(TThread)
procedure Execute; override;
end;
implementation
uses Windows;
const
MAX_THREAD_COUNT = 10;
var
Semaphore: THandle;
procedure TLimitedThread.Execute;
begin
// Уменьшаем счетчик семафора. Если к этому моменту уже запущено
// MAX_THREAD_COUNT потоков — счетчик равен 0 и семафор в
// несигнальном состоянии. Поток будет заморожен до завершения
// одного из запущенных ранее.
WaitForSingleObject(Semaphore, INFINITE);
// Здесь располагается код, отвечающий за функциональность потока,
// например загрузка файла
...
// Поток завершил работу, увеличиваем счетчик семафора и позволяем
// начать обработку другим потокам.
ReleaseSemaphore(Semaphore, 1, NIL);
end;
initialization
// Создаем семафор при старте программы
Semaphore := CreateSemaphore(NIL, MAX_THREAD_COUNT,
MAX_THREAD_COUNT, NIL);
finalization
// Уничтожаем семафор по завершении программы
CloseHandle(Semaphore);
end;