1. Взаимодействие параллельных процессов: монопольное использование – реализация; типы реализации взаимоисключения. Мониторы определение, примеры: простой монитор, монитор «кольцевой буфер» и монитор «читатели-писатели». Пример реализации монитора Хоара «читатели-писатели» для ОС Windows.
2. Процессы Unix: создание процесса в ОС Unix и запуск новой программы. Примеры из лабораторной работы (код).
Необходимость монопольного доступа к разделяемым переменным при взаимодействии параллельных процессов обусловлена тем, что при немонопольном доступе возможно возникновение потерянного обновления (ситуация, когда при одновременном изменении одной переменной разными процессами теряются все изменения, кроме последнего). Рассмотрим данную ситуацию на примере:
Пусть есть 2 процесса: P1, P2.
Пусть у них имеются следующие участки кодов (myvar - разделяемая переменная):
| P1 | P2 |
|---|---|
| mov eax, myvar | mov eax, myvar |
| inc eax | inc eax |
| mov myvar, eax | mov myvar, eax |
При выполнении этих 2 процессов параллельно (или квазипараллельно) возможен следующий порядок команд:
| Команды P1 | eax | myvar | eax | Команды P2 |
|---|---|---|---|---|
| 0 | ||||
| mov eax, myvar | 0 | 0 | ||
| 0 | 0 | 0 | mov eax, myvar | |
| 0 | 0 | 1 | inc eax | |
| 0 | 1 | 1 | mov myvar, eax | |
| inc eax | 1 | 1 | 1 | |
| mov myvar, eax | 1 | 1 | 1 |
(myvar должен был стать 2, но стал 1)
Действия, подобные описанным, называются критическими. Секции кода - критическими секциями. Необходимо обеспечить монопольное использование разделяемых параллельными процессами ресурсов. Монопольный доступ к разделяемому ресурсу обеспечивается методами взаимоисключения, то есть если одни процесс находится в критической секции по некоторой разделяемой переменной, другой процесс не может войти в критическую секцию по той же переменной, пока 1 не освободит её.
Способы взаимоисключения:
- Программный
- Аппаратный
- Семафоры
- Мониторы
типы реализации взаимоисключения. Мониторы – определение, примеры: простой монитор, монитор «кольцевой буфер» и монитор «читатели-писатели».
Монопольный доступ осуществляется методом взаимоисключения. Нельзя войти в критическую секцию, пока другой поток не освободит ее. Существуют следующие способы взаимоисключения:
- программный;
- аппаратный;
- с помощью семафоров;
- с использованием мониторов.
Из тетради: Задача мониторов - решения задачи взаимодействия при параллельной реализации. Мониторы придуманы для структурирования средств взаимоисключения.
Ассинхронные параллельные процессы - процессы, которые выполняются с собственной скоростью.
Мониторы - средство организации взаимодействия и взаимоисключения параллельных асинхронных процессов. Монитор содержит как данные, так и подпрограммы, которые обрабатывают эти данные. Доступ к данны возможен только с помощью функция монитора. Монитор защищает свои данные, так как изменить данные монитора можно только с помощью процедур монитора.
В основе монитора лежат два системных вызова:
- wait;
- signal.
Простой монитор. обеспечивает выделение единственного ресурса произвольному числу процессов.
RESOURCE: MONITOR;
var
busy: logical;
x: conditional;
procedure require // Захватить.
begin
if busy then
wait(X);
busy := true;
end;
procedure release // Освободить.
begin
busy := false;
signal(x);
end;
begin // Начальные установки.
busy := false;
end.Монитор обслуживает произвольное число процессов, кол-во которых ограничено длинной очереди. Когда к монитору обращаются целью захватить ресурсы используется процедура require. Если busy == true, то по переменной x выполняется команда wait. Если busy == false, то процесс, вызвавший require получит доступ к ресурсу и установит busy := true и другой процесс не сможет получить ресурс, пока не вызовется release. Далее, при вызове release, signal активизирует процесс из очереди. (проверяет очередь процессов к монитору и выбирает один для запуска на выполнение.). Освободить ресурс может только тот, кто его взял.
Монитор «кольцевой буфер» (Задача производства-потребления).
Особенность: два типа процессов.
- Производители производят (кладут в буфер).
- Потребители потребляют (берут из буфера).
RESOURCE: MONITOR;
var
bcircle: array [0,...,n-1] of type;
pos: 0,...,n; // Текущая позиция.
j: 0,...,n - 1; // Заполняемая позиция.
k: 0,...,n - 1; // Освобождаемая позиция.
bufferfull , bufferempty: conditional;
procedure producer (data : type)
begin
if pos = n then
wait(bufferempty);
bcircle[j] := data;
pos := pos+1;
j := (j+1) mod n; // mod - буфер кольцевой.
signal(bufferfull);
end;
procedure consumer (var data : type)
begin
if pos = 0 then
wait (bufferfull);
data := bcircle[k];
pos := pos-1;
k := (k+1) mod n; // mod - буфер кольцевой.
signal(bufferempty);
end;
begin // Начальные установки.
pos := 0;
j := 0;
k := 0;
end.Производитель будет блокирован, если буфер полон. Потребитель вызывает функцию signal, таким образом разблокируется производитель. Потребитель будет блокирован, если буфер пуст. Производитель вызывает функцию signal, таким образом разблокируется потребитель.
Монитор «читатели-писатели»
Характерно наличие двух типов процессов.
- Читатели могут читать одну и туже информацию параллельно.
- Писатель может изменять информацию. Писатель должен работать в монопольном режиме. (т.е. в то время, когда один писатель пишет, ни писатели, ни читатели не могут иметь доступ к разделяемой памяти).
RESOURCE: MONITOR;
var
nr : int; // Кол-во активных читателей.
wrt : logical; // Активный писатель.
can_read , can_write : conditional;
procedure start_read;
begin
if wrt or turn(can_write) then // Очередь ждущий писателей.
wait(can_read);
nr := nr +1;
signal(can_read);
end;
procedure stop_read;
begin
nr := nr - 1;
if (nr == 0) then
signal(can_write);
end;
procedure start_write;
begin
if nr > 0 or wrt then // Если есть читатели или активный писатель.
wait(can_write);
wrt := true;
end;
procedure stop_write;
begin
wrt := false;
if (turn(can_read)) then
signal(can_read);
else
signal(can_write);
end;
begin
nr := 0;
wrt := false;
end;Когда число читателей равно 0, процесс писатель получает возможность начать работу. Новый процесс читатель не сможет начать свою работу пока работает процесс писатель и не появится истинное значение условия can_read. Писатель может начать свою работу, когда условие can_write станет равно истине (true). Когда процессу читателю нужно выполнить чтение, он вызывает процедуру start_read. Если читатель заканчивает читать, то он вызывает процедуру stop_read. При входе в процедуру star_read новый процесс читатель сможет начать работать, если нет процесса писателя, изменяющего данные, в которых заинтересован читатель, и нет писателей, ждущих свою очередь (turn(can_write)), чтобы изменить эти данные. Второе условие нужно для предотвращения бесконечного откладывания процессов писателей в очереди писателей.
Процедура start_read завершается выдачей сигнала signal(can_read), чтобы следующий читатель в очереди читателей смог начать чтение. Каждый следующий читатель, начав чтение выдает signal(can_read), активизирует следующего читателя в очереди читателей. В результате возникает цепная реакция активизации читателей и она будет идти до тех пор, пока не активизируются все ожидающие читатели. «Цепная реакция» читателей является отличительной особенностью данного решения, которое эффективно «запускает» параллельное выполнение читателей. Процедура stop_read уменьшает количество активных читателей: читателей, начавших чтение. После ее многократного выполнения количество читателей может стать равным нулю. Если число читателей равно нулю, выполняется signal(can_write), активизирующий писателя из очереди писателей. Когда писателю необходимо выполнить запить, он вызывает процедуру start_write. Для обеспечения монопольного доступа писателя к разделяемым данным, если есть читающие процессы или другой активный писатель, то писателю придется подождать, когда будет установлено значение «истина» в переменной типа условие can_write. Когда писатель получает возможность работать логической переменной can_write присваивается значение «истина», что заблокирует доступ других процессов писателей к разделяемым данным. Когда писатель заканчивает работу, предпочтение отдается читателям при условии, что очередь ждущих читателей не пуста. Иначе для писателей устанавливается переменная can_write. Таким образом исключается бесконечное откладывание читателей.
4 функции монитора Хоары:
- start read;
- stop read;
- start write;
- stop write.
HANDLE canRead;
HANDLE canWrite;
HANDLE mutex;
LONG waitingWritersCount = 0;
LONG waitingReadersCount = 0;
LONG activeReadersCount = 0;
bool writing = false;
bool turn(HANDLE event)
{
// Если функция возвращает WAIT_OBJECT_0, объект свободен.
return WaitForSingleObject(event, 0) == WAIT_OBJECT_0;
}
void StartRead()
{
// Увеличиваем кол-во ждущих читателей.
InterlockedIncrement(&waitingReadersCount);
// Процесс читатель сможет начать работать,
// Если нет активного писателя,
// И нет писателей, ждущих свою очередь.
if (writing || turn(canWrite))
WaitForSingleObject(canRead, INFINITE);
WaitForSingleObject(mutex, INFINITE);
// Уменьшаем кол-во ждущих читателей.
InterlockedDecrement(&waitingReadersCount);
// Увеличиваем кол-во активных читателей.
InterlockedIncrement(&activeReadersCount);
// Выдаем сигнал canRead,
// Чтобы следующий читатель в очереди
// Читателей смог начать чтение
SetEvent(canRead);
ReleaseMutex(mutex);
}
void StopRead()
{
// Уменьшаем количество активных читателей.
InterlockedDecrement(&activeReadersCount);
// Если число читателей равно нулю,
// Выполняется signal(can_write),
// активизирующий писателя из очереди писателей.
if (!activeReadersCount)
SetEvent(canWrite);
}
void StartWrite()
{
// Увеличиваем кол-во ждущих писателей.
InterlockedIncrement(&waitingWritersCount);
// Процесс писатель сможет начать работать,
// Если нет читающих процессов
// И нет другого активного писателя.
if (activeReadersCount > 0 || writing)
WaitForSingleObject(canWrite, INFINITE);
// Уменьшаем кол-во ждущих писателей.
InterlockedDecrement(&waitingWritersCount);
// Писатель пишет.
writing = true;
}
void StopWrite()
{
writing = false;
// Предпочтение отдается читателям при условии,
// Что очередь ждущих читателей не пуста.
if (waitingReadersCount)
SetEvent(canRead);
else
SetEvent(canWrite);
}Процесс - программа в стадии выполнения. Процесс в Linux (как и в UNIX) это - программа, которая выполняется в отдельном защищенном виртуальном адресном пространстве. В Unix используется иерархия процессов, которая строится в отношении предок-потомок.
Для создания процессов используется системный вызов fork().
pid_t fork(void);Системный вызов fork() создает новый процесс, который является копией процесса-предка: процесс-потомок наследует адресное пространство процесса-предка, дескрипторы всех открытых файлов и сигнальную маску и т.д.
Системный вызов fork() возвращает дочернему процессу число 0, а родительскому — PID (Process IDentifier — идентификатор процесса) дочернего процесса. Если вызов fork() завершается аварийно, он возвращает -1. Далее можно проанализировать значение переменной errno.
Процесс-потомок имеет идентичные с родителем области данных и стека. Процесс-потомок начинает работу в режиме задачи после возвращения из системного вызова fork().
В современных системах применяется, так называемая, оптимизация fork() или, как говорят, «умный» fork: для процесса потомка создаются собственные карты трансляции адресов (таблицы страниц), но они ссылаются на адресное пространство процесса-предка (на страницы предка). При этом для страниц адресного пространства предка права доступа меняются на only-read и устанавливается флаг – copy-on-write. Если или предок или потомок попытаются изменить страницу, возникнет исключение по правам доступа. Выполняя это исключение супервизор обнаружит флаг copy-on-write и создаст копию страницы в адресном пространстве того процесса, который пытался ее изменить. Таким образом код процесса-предка не копируется полностью, а создаются только копии страниц, которые редактируются. Если потомок вызовет exec() или exit(), то защита страниц памяти вновь станет обычной, и флаг «копирования при записи» будет сброшен.
При системном вызове exec() адресное пространство процесса будет заменено на адресное пространство новой программы, а сам процесс будет возвращен в режим задачи с установкой указателя команд на первую выполняемую инструкцию этой программы.
В итоге exec() запускает новую программу.
// Суффикс l (список):
// Аргументы командной строки передаются в форме списка arg0, arg1.... argn, NULL.
// В случае успеха функция exec не возвращает значения. При неудаче возвращается значение —1
int execl(char *name, char *arg0, ... /*NULL*/);Пример использования exec(). Запуск в linux.
- Этап 1. Создается новый процесс (fork).
- Этап 2. Программа передается exec'у в качестве параметров (начинает выполняться).
int main()
{
int childpid_1;
int status;
pid_t child_pid;
if ((childpid_1 = fork()) == -1)
{
// Если при порождении процесса произошла ошибка.
perror("Can\'t fork.\n");
return 1;
}
else if (childpid_1 == 0) // Это процесс потомок.
{
// p - определяет, что функция будет искать "дочернюю"
// программу в директориях, определяемых
// переменной среды DOS PATH. Без суффикса p поиск
// будет производиться только в рабочем каталоге.
printf("First child: id: %d ppid: %d pgrp: %d\n", getpid(), getppid(), getpgrp());
if (execlp("cat", "cat", "text1.txt", NULL) == -1)
{
perror("First child can\'t exec");
exit(1);
}
exit(0);
}
child_pid = wait(&status);
printf("Parent: id: %d pgrp: %d child1: %d\n", getpid(), getpgrp(), childpid_1);
return 0;
}