1. Параллельные процессы: взаимодействие, обоснование необходимости монопольного доступа к разделяемым переменным, способы взаимоисключения. Мониторы: определение; примеры - простой монитор и монитор кольцевой буфер
2. Средства межпроцессорного взаимодействия (IPC) операционной системы UNIX System V: очереди сообщений и программные каналы – сравнение, примеры (для программных каналов пример из лабораторной работы с сигналами).
Параллельные процессы: взаимодействие, обоснование необходимости монопольного доступа к разделяемым переменным, способы взаимоисключения.
IPC - средства межпроцессорного взаимодействия ОС UNIX System V (см. вопрос 2).
Необходимость монопольного доступа к разделяемым переменным при взаимодействии параллельных процессов обусловлена тем, что при немонопольном доступе возможно возникновение потерянного обновления (ситуация, когда при одновременном изменении одной переменной разными процессами теряются все изменения, кроме последнего). Рассмотрим данную ситуацию на примере:
Пусть есть 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, таким образом разблокируется потребитель.
Средства межпроцессорного взаимодействия (IPC) операционной системы UNIX System V: очереди сообщений и программные каналы – сравнение
В распределенных системах вся передача данных - с помощью сообщений. Очереди сообщений - средства взаимодействия на отдельной машине, характерны и для распределенных системах.
Таблица очередей сообщений (системная таблица) содержит дескрипторы всех очередей сообщений в системе.
Связный список типа очередь, каждый элемент указывает на следующий.
Дескриптор очереди сообщений - struct msgid_ds. Элемент очереди не содержит текста сообщения, содержит ссылку на текст сообщения в области данных ядра системы.
Сообщение имеет тип и текст.
Когда процесс передает сообщение в очередь, ядро создает для него новую запись и помещает ее в конец связного списка соотвующих записей. В каждой такой записи указывается тип сообщения, число байт, указатель на другую область данных .
Ядро копирует сообщение из пространства отправителя в область данных ядра системы, чтобы процесс отправитель мог завершиться, а его сообщение осталось доступным для чтения другим процессам.
Когда процесс выбирает сообщение из очереди, ядро копирует это сообщение в адресное пространство процесса-получателя сообщения, после этого сообщение удаляется.
Процесс может выбрать сообщение несколькими способами:
- Взять самое старое сообщение, независимо от его типа
- Взять сообщение, если идентификатор сообщения совпадает с идентификатором, который указал процесс. Если существует несколько сообщений с данным идентификатором, то процесс возьмет самое старое сообщение.
- Выбрать из очереди сообщение, числовое значение которого является наименьшим из меньших или равным значению типу указанного в процессе. Если этому условию соответствует несколько сообщений в очереди, то процесс возьмет самое старое.
Когда сообщение выбрано из очереди, сообщение перестает существовать.
На сообщениях определены следующие системные вызовы:
msgget()msgctl()msgsnd()msgrev()
Для сообщений характерно копирование. При посылке - сообщение копируется из адресного пространства процесса в адресное пространство ядра. При получении, наоборот - сообщение копируется из адресного пространства ядра в адресное пространство процесса. В отличие от разделяемой памяти, так как разделяемый сегмент подключается в адресное пространство сегмента. Поэтому разделяемая память обеспечивает более быстрый способ взаимодействия - за счет отсутствия копирования.
Когда процесс отправляет сообщение в очередь, сообщение копируется из адресного пространства процесса отправителя в адресное пространство ядра - процесс отправитель не должен блокироваться, дожидаясь получения сообщения другим процессом.
Очереди сообщений позволяют исключить блокировку при посылки.
Процесс не блокируется в ожидании получения сообщения - не блокируется при отправке, не блокируется при получении.
В современных ОС UNIX существуют программные каналы, которые принято называть pipe - именованные и неименованные.
Передача данных в одном направлении (потоковая передача данных). Если надо передавать данные в обе стороны, то нужна вторая труба, в которой движение информации будет противоположно первому.
Именованные программные каналы и неименованные - два типа программных каналов, которые поддерживаются современными ОС.
mknode - создание именованного программного канала
При создании именованного программного канала, это будет труба типа FIFO (тип потоковой передачи данных)
Являются в системе специальными файлами и видны в файловой системе, более того - они имеют идентификатор в файловой системе. Любой процесс, который знает идентификатор именованного программного канала, может работать с этим программным каналом.
Не имеют идентификатора, но поддерживаются средствами файловой системы, имеют дескриптор.
Неименованными программными каналами могут пользоваться процессы-родственники, тк процессы потомки наследуют от предка дескрипторы открытых файлов.
Создание канала:
int fd[2];
pipe(fd);В канал нельзя писать, если из него читают, из канала нельзя читать, если в него пишут.
(Канал закрывается на чтение при записи и закрывается на запись при чтении)
Труба буферизуется на трех уровнях
Программные каналы буферизуются в системной памяти (в области данных ядра системы)
При переполнении системной памяти, буфера, имеющие наибольшее время существования переписываются на диск. Используются стандартные функции работы с памятью.
Если процесс записывает в пайп больше 4096 байт, то труба будет буферизоваться по времени, приостанавливая процесс, который записывает в трубу до тех пор, пока данные не будут прочитаны.
Ограничение значений канала (4096) - повысить эффективность операции обмена. При операции обмена ОС выделяет системные буферы. Если его размер не превышает 4096, то такой канал может целиком разместиться в системном буфере. (Это важная мысль)
Чтение из памяти одиночной переменной только на 30% быстрее, чем передача одной страницы. Это связано с тем, что в системе оптимизируется передача страниц (буфера соответствуют размеру страницы).
(здесь код без сигналов, но из лабы с сигналами (требуется показать pipe))
#define BUFFER_LEN 100
#define N 2
const char* SECRET_MSGS[N] = { "secret message 1", "secret message 2" };
void err_sys(const char* x)
{
perror(x);
exit(1);
}
int main()
{
int fd[2];
int pid;
if (pipe(fd) == -1) {
err_sys("Something went wrong with pipe!")
}
for (size_t i = 0; i < N; i++) {
if ((pid = fork()) == -1) {
err_sys("Error fork()");
} else if (pid == 0) {
close(fd[0]);
size_t written = write(fd[1], SECRET_MSGS[i], strlen(SECRET_MSGS[i]));
printf("Sent message to parent! (written %zu bytes)\n", written);
exit(0);
}
}
for (size_t i = 0; i < N; i++) {
int status;
pid_t child_pid;
child_pid = wait(&status);
printf("Child has finished: PID = %d, status = %d\n", child_pid, status);
int stat_val;
if (WIFEXITED(stat_val))
printf("Child exited with code %d\n", WEXITSTATUS(stat_val));
else
printf("Child terminated abnormally\n");
}
char buffer[BUFFER_LEN] = { 0 };
close(fd[1]);
size_t buf_len = read(fd[0], buffer, BUFFER_LEN);
printf("Received message (size: %zu): %s!\n", buf_len, buffer);
return 0;
}