15

1. Межпроцессорное взаимодействие в Unix System V (IPC): сигналы, программные каналы, семафоры и разделяемая память; примеры использования из лабораторных работ

2. Синхронизация и взаимоисключение параллельных процессов в распределенных системах: централизованный и распределенные алгоритмы – сравнение

Сигналы

(Внешнее по отношению к процессу асинхронное событие)

Сигналы в UNIX соответствуют каким-либо событиям. Механизм сигналов позволяет процессам реагировать на события, причем эти события могут происходить как вне процесса, так и внутри; как правило, получение процессом сигнала указывает ему на необходимость завершиться. Важнейшим событием в системе является завершение процесса. Несмотря на то, что в системе определены реакции на определённые события процессов, процесс может сам определить собственную реакцию на получаемый сигнал.

Сигналы описаны в библиотеке <signal.h>

Описание нескольких наиболее важных сигналов.

#define SIGINT 2 // ctrl + C
#define SIGKILL 9
#define SIGSEGV 11 // нарушение сегментации
#define SIGCLD 18 // завершился процесс потомок
#define SIGPWR 19 // авария питания
#define SIG_DFL(int((*)())) 0 // все установки будут использоваться по умолчанию
#define SIG_IGN(int((*)())) 1 // приписывает игнорирование сигнала

Средства посылки и обработки сигналов

Средствами посылки и обработки сигналав UNIX служат два системных вызова: kill, signal.

Системный вызов kill (посылка сигнала)

int kill(int pid, int sig); //  два формальных параметра: идентификатор процесса и сигнал.

int pid не обязательно должен быть равен идентификатору процесса. Например, если параметр pid <= 1, то сигнал sig будет послан к группе процессов.

Если pid == 0, то sig будет послан всем процессам с id группы совпадающими с id группы процесса, который осуществил системный вызов kill, кроме процессов с pid 0 и 1.

Пример:

kill(getpid(), SIGALARM) // означает, что сигнал побудки будет послан самому процессу, вызвавшему kill

Сиcтемный вызов signal (обработка сигнала)

void (*signal(int sig, void (*handler()(int)))(int)

Для того, чтобы замаскировать сигнал, необходимо в программе вызвать signal(SIGINT, SIG_IGN).

signal(SIGNINT, SIG_DFL) - вернуть реакцию по умолчанию.

Программные каналы

В современных ОС UNIX существуют программные каналы, которые принято называть pipe - именованные и неименованные.

Почему pipe (труба)?

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

Именованные программные каналы и неименованные - два типа программных каналов, которые поддерживаются современными ОС.

Именованные программные каналы

mknode - создание именованного программного канала

При создании именованного программного канала, это будет труба типа FIFO (тип потоковой передачи данных)

Являются в системе специальными файлами и видны в файловой системе, более того - они имеют идентификатор в файловой системе. Любой процесс, который знает идентификатор именованного программного канала, может работать с этим программным каналом.

Неименованные программные каналы

Не имеют идентификатора, но поддерживаются средствами файловой системы, имеют дескриптор.

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

Создание канала:

int fd[2];
pipe(fd);

В канал нельзя писать, если из него читают, из канала нельзя читать, если в него пишут.

(Канал закрывается на чтение при записи и закрывается на запись при чтении)

Важно (на самом деле не очень: не успеваешь - не пиши этот блок!)

Труба буферизуется на трех уровнях

Программные каналы буферизуются в системной памяти (в области данных ядра системы)

При переполнении системной памяти, буфера, имеющие наибольшее время существования переписываются на диск. Используются стандартные функции работы с памятью.

Если процесс записывает в пайп больше 4096 байт, то труба будет буферизоваться по времени, приостанавливая процесс, который записывает в трубу до тех пор, пока данные не будут прочитаны.

Ограничение значений канала (4096) - повысить эффективность операции обмена. При операции обмена ОС выделяет системные буферы. Если его размер не превышает 4096, то такой канал может целиком разместиться в системном буфере. (Это важная мысль)

Чтение из памяти одиночной переменной только на 30% быстрее, чем передача одной страницы. Это связано с тем, что в системе оптимизируется передача страниц (буфера соответствуют размеру страницы).

Семафоры

Типы семафоров:

• бинарный
• считающий
• множественный

Наборы считающих семафоров - этот тип поддерживают все современные ОС.

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

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

Одной неделимой операцией можно изменить весь или часть набора семафоров.

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

Дескриптор набора семафоров:

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

Семантические наборы семафоров представляются как массивы, первый семафор имеет индекс 0.

Каждый отдельный семафор имеет набор параметров. Дескриптор отдельного семафора:

• Значение семафора
• Идентификатор процесса, который оперировал семафором в последний раз
• Число процессов, заблокированных на семафоре

Таблица семафоров

Каждый элемент этой таблицы описывает структуры struct semid_ds (<sys/sem.h>)

Каждая строка таблицы описывает отдельный набор семафоров

Каждый семафор описан структурой struct sem.

На семафорах определены следующие системные вызовы:

• semget() - создаёт набор семафоров
• semctl() - позволяет изменять управляющие параметры набора семафоров
• semop() - изменяет значение семафора - отдельного, набора или части набора семафоров

на семафоре определена структура

struct sembuf {
    unsigned short sem_num; // - индекс семафора
    short sem_op; // - операция на семафоре
    short sem_flg; // - флаги, определенные на семафоре
};

В отличие от классических семафров Дейкстры (у него две операции), на семафоре UNIX определены три операции

1. sem_op > 0 освобождение ресурса
2. sem_op == 0 - ожидание ресурса без захвата
3. sem_op < 0 - захват ресурса

Декрементировать семафор можно только если семафор имеет положительное значение.

На семафорах определны специальные флаги:

• IPC_NOWAIT - информирует ядро системы о нежелании процесса переходить в состояние ожидания
• SEM_UNDO - указывает ядру, что оно должно отслеживать изменение значения семафора в результате системного вызова semop() и при завершении процесса, вызвавшего semop(), ядро ликвидирует сделанные изменения для того, чтобы процессы не были заблокированы на семафоре навечно.

Разделяемая память

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

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

Существует таблица разделяемых сегментов.

<sys/shm.h> - дескриптор описывается структурой struct shmid_ds

Особенностью разделяемых сегментов является то, что процесс получает указатель на разделяемый сегмент

Для разделяемой памяти определены системные вызовы:

• shmget() - создает разделяемый сегмент
• shmctl() - изменяет упр параметры сегмента
• shmat() - (attach) получение указателя на разделяемый сегмент
• shmdt() - (detach) отделение сегмента от адресного пространства процесса

Системное ограничение	значение
SHMMNI	максимальное число разделяемых сегментов
SHMMIN	минимально возможный размер разд сегмента в байтах
SHMMAX	максимально возможный размер разд сегмента в байтах

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

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

Примеры из ЛР

Пример создания программного канала:

int fd[2];
int pid;
if (pipe(fd) == -1) {
    printf("Something went wrong with pipe!");
return 1;

Пример чтения/записи с помощью программного канала:

const char* SECRET_MSGS[2] = { "secret message 1", "secret message 2" };
...
size_t written = write(fd[1], SECRET_MSGS[0], strlen(SECRET_MSGS[0])); // запись
...
char buffer[BUFFER_LEN] = { 0 };
size_t buf_len = read(fd[0], buffer, BUFFER_LEN); // чтение

Пример регистрации сигнала:

#define QUITE_MODE 0
int MODE = QUITE_MODE;
...
void parent_callback(int sig_number) {
    MODE = LOUD_MODE;
}
...
signal(SIGINT, parent_callback);

Пример использования разделяемой памяти:

#define BUFFER_SIZE 64
...
// Создание сегмента разделяемой памяти
int fd = shmget(IPC_PRIVATE, BUFFER_SIZE * size_of(char), IPC_CREAT | PERMS); 
if (fd == -1) {
    perror("Failed to create shared memory!");
    exit(1);
}
...
char *buffer;
if ((buffer = (char*)shmat(fd, 0, 0)) == (void*)-1) { 
    perror("Failed to shmat!");
    exit(1);
}

Пример создания и инициализации набора семафоров:

#define SEMS_AMOUNT 3
#define N 64
#define FREE 1
...
int sid = semget(KEY, SEMS_AMOUNT, IPC_CREAT | PERMS);
if (sid == -1) {
    perror("Can't create array of semaphores!");
    return SEMGET_FAILED;
}
semctl(sid, BIN_SEM, SETVAL, FREE);
semctl(sid, BUF_EMPTY, SETVAL, N);
semctl(sid, BUF_FULL, SETVAL, 0);

Пример захвата доступа к ресурсу с помощью семафора:

struct sembuf PRODUCE_LOCK[2] = { { BUF_EMPTY, -1, 0 }, { BIN_SEM, -1, 0 } };
...
if (semop(sid, PRODUCE_LOCK, 2) == -1) {
    perror("Something went wrong with produce lock!");
    exit(PRODUCE_LOCK_FAILED);
}

Централизованный алгоритм

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

Рассмотрим ситуацию, когда каждый процесс может выполнить роль координатора. В этом случае, если какой-то процесс обнаружил, что координатор отсутствует (если прошел timeout, то он может считать, что координатор отсутствует (здесь может использоваться специальный протокол)). Тогда такой процесс может инициализировать процесс выбора нового координатора. Посылается специальный запрос, в котором процесс указывает свой номер всем процессам. Если у принимающего процесса больший номер, то он инициирует такой запрос сам. В результате останется один процесс с наибольшим номером. Он становится координатором.

Распределенный алгоритм

Второй тип алгоритма это распределенный алгоритм.

Алгоритм формулируется следующим образом:

1. Когда процесс хочет войти в критическую секцию, он формирует сообщение.
   • В этом сообщении он указывает:
     • идентификатор нужной ему критической секции;
     • свой номер (идентификатор);
     • время формирования сообщения по своим локальным часам.
   • Предполагается, что передача сообщения надёжна: получение каждого сообщения сопровождает подтверждение.
   • Протокол - соглашение о том, какие действия выполняют процессы при передаче и получении сообщения. Надёжный протокол всегда предполагает подтверждение получения сообщения.
2. Это сообщение, сформированное процессом, процесс рассылает всем взаимодействующим процессам (то есть n - 1 сообщение)
3. Получив такое сообщение, процесс проверяет, в какой ситуации он сам находится по отношению к критической секции.
   • Возможны 3 ситуации:
     1. получивший сообщение процесс не собирается входить в данную критическую секцию (и не находится в ней). В этом случае процесс посылает сообщение-ответ с разрешением войти в критический участок;
     2. процесс, получивший сообщение, находится в данной критической секции. В этом случае никакое сообщение не посылается;
     3. Процесс, получивший сообщение, сам формировал сообщение запрос на вход в данную критическую секцию, но еще не успел это сделать.
        • (на доске: хочет войти в ту же критическую секцию). Тогда процесс проверяет временную метку создания своего сообщения, сравнивает ее с временной меткой полученного сообщения. Если его сообщение было сформировано раньше, то никакого сообщения-ответа процесс не посылает. Если в результате таких рассылок процесс получает n - 1 сообщение подтверждения входа в критический участок, то процесс может войти в критический участок. Если он не получает хотя бы одно сообщение, то в критический участок процесс войти не может.

В этом случае процесс должен послать n - 1 сообщение-запрос и в ответ получить n - 1 сообщение-разрешение на вход, иначе войти не может.

Алгоритм Токен Ринг (Token Ring)

(еще один распределенный алгоритм)

Смысл заключается в том, что процессы создают логическое кольцо - замкнутую цепочку.

Каждый процесс в логическом кольце знает идентификатор следующего процесса в этом логическом кольце. По данному логическому кольцу передается так называемый токен. Это специальное сообщение, которое содержит идентификатор конкретной критической секции. Этот токен переходит от n-ого процесса к n + 1-ому процессу, циркулирует по логическому кольцу. Когда процесс получает токен, он анализирует, нужно ли ему войти в данную критическую секцию. Если нужно, получив токен, он входит в критическую секцию и токен удерживает. Выйдя из критической секции, процесс отправляет токен следующему в цепи процессу. Пока процесс находится в критической секции он удерживает токен. Если ни один процесс не заинтересован во вхождении в критическую секцию токена, такой токен быстро циркулирует по цепочке.

Сравнение приведенных алгоритмов

Самый надежный алгоритм: централизованный алгоритм. За счет возможности выбора нового координатора.

В случае распреденного алгоритма: Если какой-то из процессов перестал существовать, то процесс, разославший n - 1 сообщение-запрос, не сможет получить n - 1 сообщение-ответ: потеря работоспособности по конкретной критической секции.

В случае Токен Ринг: если какой-то процесс перестает существовать, то цепь разрывается. Чтобы ее восстановить, надо предпринять соответствующие действия. Если циркулирование токена по каким-то причинам прервано, то есть только одно средство определения: таймаут.