1. Взаимодействие параллельных процессов: проблемы; монопольный доступ и взаимоисключение; взаимодействие в распределенных системах - особенности; централизованный алгоритм, распределенный алгоритм; синхронизация логических часов (алгоритм Лампорта)
Монопольный доступ процессов к разделеяемым переменным ресурсам обеспечивается с помощью методов взаимоисключения. Участки кода, в которых выполняется обращение к разделяемым ресурсам называются критическими. Только один процесс может получить доступ к данным в определенный момент, и, соотвественно находиться в критическом участке.
Необходимость монопольного доступа к разделяемым переменным при взаимодействии параллельных процессов обусловлена тем, что при немонопольном доступе возможно возникновение потерянного обновления (ситуация, когда при одновременном изменении одной переменной разными процессами теряются все изменения, кроме последнего). Рассмотрим данную ситуацию на примере:
Пусть есть 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 не освободит её.
Способы взаимоисключения:
- Программный способ
- Аппаратный способ
- С помощью семафоров
- С использованием мониторов
В распределенных системах (системы, где ресурсы рассредоточены) процессы не имеют общей памяти и могу синхронизироваться только сообщениями, взаимодействие по системе "клиент-сервер".
Когда процессы взаимодействую друг с другом, часто возникает проблема синхронизации процессов. Данная проблема связана с некорректным разделением критических ресурсов несколькими процессами и в следствии их утратой. Для решения этой проблемы, необходимо обеспечить процессу монопольный доступ к критическому ресурсу, до тех пор, пока процесс его не овободит.
В распределенных системах существуют алгоритмы взаимного исключения (ниже).
- Существует процесс-координатор. Когда процесс хочет в критический участок, он отправляет запрос координатору с именем этого участка.
- Координатор анализирует, не находится какой-либо процесс в данной критической секции. В случае, если находится, то запрос ставится в очередь. В обратном случае, процесс получает разрешение на вход в критический участок.
- Если два процесса одновременно хотят войти в критический участок, то выбор происходит с помощью алгоритма Лампорта.
Минус: процесс-координатор может прекратить свое существование.
В случае, если какой-либо процесс обнаружит отсутствие координатора (таймаут), то он ининцирует выборы нового. Процесс посылает сообщение с предложением выбора нового координатора всем процессам, указывая свой собственный. Если процесс получатель обнаруживает, что его номер больше, то он посылает назад подтверждение приема такого сообщения и сам иницирует новые выборы.
В результате выполнения останется один процесс с самым большим номером, который становится координатором
- Когда процесс хочет войти в критическую секцию, он формирует сообщение.
- В этом сообщении он указывает:
- идентификатор нужной ему критической секции;
- свой номер (идентификатор);
- время формирования сообщения по своим локальным часам.
- Предполагается, что передача сообщения надёжна: получение каждого сообщения сопровождает подтверждение.
- Протокол - соглашение о том, какие действия выполняют процессы при передаче и получении сообщения. Надёжный протокол всегда предполагает подтверждение получения сообщения.
- В этом сообщении он указывает:
- Это сообщение, сформированное процессом, процесс рассылает всем взаимодействующим процессам (то есть n - 1 сообщение)
- Получив такое сообщение, процесс проверяет, в какой ситуации он сам находится по отношению к критической секции.
- Возможны 3 ситуации:
- получивший сообщение процесс не собирается входить в данную критическую секцию (и не находится в ней). В этом случае процесс посылает сообщение-ответ с разрешением войти в критический участок;
- процесс, получивший сообщение, находится в данной критической секции. В этом случае никакое сообщение не посылается;
- Процесс, получивший сообщение, сам формировал сообщение запрос на вход в данную критическую секцию, но еще не успел это сделать. В этом случае процесс проверяет временную метку создания своего сообщения, сравнивает ее с временной меткой полученного сообщения. Если его сообщение было сформировано раньше, то никакого сообщения-ответа процесс не посылает. Если в результате таких рассылок процесс получает n - 1 сообщение подтверждения входа в критический участок, то процесс может войти в критический участок. Если он не получает хотя бы одно сообщение, то в критический участок процесс войти не может.
- Возможны 3 ситуации:
В этом случае процесс должен послать n - 1 сообщение-запрос и в ответ получить n - 1 сообщение-разрешение на вход, иначе войти не может.
Централизованный алгоритм надежнее чем распределенный, за счет возможности выбора нового координатора.
В случае распреденного алгоритма: Если какой-то из процессов перестал существовать, то процесс, разославший n - 1 сообщение-запрос, не сможет получить n - 1 сообщение-ответ: потеря работоспособности по конкретной критической секции.
Алгоритм Лампорта применяется для синхронизации временных ответок (для соблюдения отношения "случилось до / случилось после")
- Процесс, отправивший сообщение, так же отправляет время отправки по локальным часам.
- В случае, если время процесса меньше, чем время отправления, то он сам устанавливает время отправления: пришедшее + 1.
2. Процессы в UNIX: системные вызовы fork(), exec(), wait(), signal() - примеры из лабораторных работ.
Процесс создается системным вызовов fork(). В результате этого вызова создается процесс-потомок. В UNIX используется иерархия процессов, которая строится в отношении предок-потомок. В старых UNIX процесс-потомок полностью копировал код предка в свое адресное пространство.
В современных системах применяется оптимизация fork(): у процесса-потомка создаются собственные карты трансляции адресов, но они ссылаются на адресное пространство процесса-предка. Для страниц адресного пространства предка права доступа меняются на read-only и устанавливается флаг copy-on-write. Если предок или потом попытаются изменить страницу, возникнет исключение по правам доступам, и, выполняя это исключение, супервизор создаст копию страницы в адресном постранстве того процесса, который попытался ее изменить. Такая оптимизация позволяет не копировать страницы полностью, а только при их изменении.
Вызов fork() возвращает 0 для потомка и ID потомка для родителя. -1 в случае если ветвление невозможно. Любой процесс имет предка (кроме демонов). В UNIX так же существует понятие group: процесс предок создает группу. Основная группа - терминальная, в ней предком всех процессов является процесс с id = 1.
При завершении процесса ОС проверяет, не осталось ли у него незавершенных потомков (с помощью дескриптора процесса). Если такие остались, то выполняется процесс усыновления (изменение указателей): процесс-потомк получается указатель на нового процесса-предка.
Процесс-сирота — процесс с завершенным предком. Если предок завершен, процесс сирота усыновляется терминальным процессом (id = 1).
Пример fork из ЛР (создание двух дочерних процессов):
int child[N];
printf("Parent process. PID: %d, GROUP: %d\n", getpid(), getpgrp());
for (int i = 0; i < 2; i++)
{
int pid = fork();
if (-1 == pid)
{
return 1;
}
else if (0 == pid) // дочерний код
{
sleep(2);
printf("Child process #%d. PID: %d, PPID: %d, GROUP: %d\n", i + 1, getpid(), getppid(), getpgrp());
return 0;
}
else // родительский код
{
child[i] = pid;
}
}
printf(Parent process. Children ID: %d, %d.\nParent process is dead.\n", child[0], child[1]);Системный вызов wait(&status) блокирует родительский процесс до того момента, пока не будет завершен дочерний. При завершении, процесс получает статус завершения потомка. Интерпретировать информацию о состоянии процесса можно с помощью специальных макросов объявленных sys/wait.h.
Пример вызова wait из ЛР:
...
int status, statval = 0;
pid_t childpid = wait(&status);
printf("Child process (PID %d) finished. Status: %d\n", childpid, status);
if (WIFEXITED(statval))
{
printf("Child process #%d finished with code: %d\n", i + 1, WEXITSTATUS(statval));
}
else if (WIFSIGNALED(statval))
{
printf("Child process #%d finished from signal with code: %d\n", i + 1, WTERMSIG(statval));
}
else if (WIFSTOPPED(statval))
{
printf("Child process #%d finished stopped with code: %d\n", i + 1, WSTOPSIG(statval));
}
...Чаще всего нет смысла в выполнении двух одинаковых процессов. Поэтому, потомок выполняет системный вызов exec(), параметрами которого является имя исполняемого файла и, если нужно, параметры, которые будут переданы этой программе.
Системный вызов exec() создает низкоуровневый процесс: создаются таблицы страниц для адресного пространства программы, указанной в exec(), но программа на выполнение не запускается, так как это не полноценный процесс, имеющий идентификатор и дескриптор. exec() создает таблицу страниц для адресного пространства программы, переданной ему в качестве параметра, а затем заменяет старый адрес новой таблицы страниц.
В результате системного вызова exec() адресное пространство процесса будет заменено на адресное пространство новой программы, а сам процесс будет возвращен в режим задачи с установкой указателя команд на первую выполняемую инструкцию этой программы.
Процесс-зомби – процесс, у которого отобраны все ресурсы, кроме последнего – строки в таблице процессов. Это сделано для того, чтобы процесс-предок, вызвавший системный вызов wait(), не был заблокирован навсегда.
Пример вызова exec из ЛР (вызов потомками команд ls и pwd):
int child[2];
int pid;
const char *const commands[N] = { "ls", "pwd" };
printf("Parent process. PID: %d, GROUP: %d\n", getpid(), getpgrp());
for (size_t i = 0; i < 2; i++)
{
pid = fork();
if (-1 == pid)
{
return 1;
}
else if (0 == pid)
{
sleep(2);
int rc = execlp(commands[i], commands[i], 0);
if (-1 == rc)
{
return 1;
}
return 0;
}
else
{
child[i] = pid;
}
}Сигнал — способ информирования процесса ядром о проишествии какого-либо события. При возникновении нескольких однотипных событий, процессу передается только один сигнал. То есть сигнал означает, что событие произошло, но не уточняется, сколько таких событий произошло.
Процесс может установить собственную реакцию на получаемых сигнал. Это делается с помощью системного вызова signal(snum, f).
snum - номер сигнала, f - адрес функции, которая должна быть выполнена при поступлении указанного сигнала.
Возвращает указатель на предыдущий обработчик данного сигнала, который можно использовать для восстановления обработчика сигнала.
Пример регистрации сигнала из ЛР (изменение реакции на сигнал Ctrl-C):
#define QUITE_MODE 0
int MODE = QUITE_MODE;
...
void parent_callback(int sig_number)
{
MODE = LOUD_MODE;
}
...
signal(SIGINT, parent_callback);