(IPC - interprocess communication, again...)

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

Для того чтобы с помощью программных каналов создать дуплексную связь надо иметь два программных канала.

02:31

В распределенных системах вся передача данных - с помощью сообщений. Очереди сообщений - средство взаимодействия процессов на отдельной стоящей машине, отдельные свойства сообщений также характерны и для сообщений в распределенных системах.

Для поддержки очередей сообщений в системе имеется системная таблица - таблица очередей сообщений. Эта таблицы содержит дескрипторы всех созданных в системе очередей сообщений. Является связным списком типа очередь, каждый элемент этой очереди имеет указатель на следующий элемент очереди. Последний элемент очереди имеет указатель NULL. Есть два указателя msg_first и msg_last.

Дескриптор очереди сообщений описывается структурой struct msgid_ds (библиотека <sys/msg.h>). Элемент очереди не содержит текста сообщения, содержит ссылку на текст сообщения в области данных ядра системы.

struct msgid_ds
{
    long mytype,
    char mytext[MSGMAX];
}

Каждое сообщение имеет тип и текст.

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

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

Когда процесс выбирает сообщение из очереди, ядро копирует это сообщение в адресное пространство процесса-получателя сообщения, после этого сообщение удаляется.

Процесс может выбрать сообщение несколькими способами:

1. Взять самое старое сообщение, независимо от его типа
2. Взять сообщение, если идентификатор сообщения совпадает с идентификатором, который указал процесс. Если существует несколько сообщений с данным идентификатором, то процесс возьмет самое старое сообщение.
3. Выбрать из очереди сообщение, числовое значение типа которого является наименьшим из меньших или равным значению типа указанного в процессе. Если этому условию соответствует несколько сообщений в очереди, то процесс возьмет самое старое.

Когда сообщение выбрано из очереди, сообщение перестает существовать.
На сообщениях определены следующие системные вызовы:

1. msgget()
2. msgctl()
3. msgsnd()
4. msgrev()

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

Когда процесс отправляет сообщение в очередь, сообщение копируется из адресного пространства процесса отправителя в адресное пространство ядра системы, соответственно элемент описывающий это сообщение добавляется в конец очереди, а процесс отправитель может завершится, т.е процесс отправитель не должен блокироваться, дожидаясь получения сообщения другим процессом.

Очереди сообщений позволяют исключить блокировку при посылки.

Процесс не блокируется в ожидании получения сообщения - не блокируется при отправке, не блокируется при получении.

16:00

#include <stdio.h>
#include <string.h>
#include <sys/ipc.h>
#include <sys/msg.h>

// определяем максимальный размер текста сообщения
#ifndef MSGMAX
#define MSGMAX 1024
#endif

struct mbuf
{
    long mtype; // тип сообщения
    char mtext[MSGMAX]  // сообщение 
} mobj = {15, "Hello"};
        
int main()
{
    // file descriptor
    // очередь сообщений с id = 100
    int fd = msgget(100, IPC_CREATE | IPC_EXCL | 0642);  // 0642 - права доступа 
    
    if (fd == -1 || msgsnd(fd, &mobj, strlen(mobj.mtext) + 1, IPC_NOWAIT));
        perror("message");
    return 0;

    // IPC_NOWAIT -- процесс не блокируется при посылке
}

Очереди сообщений обеспечивают дуплексную связь одной очередью --- в очередь можно писать, из очереди можно читать. Кроме этого, имеется возможно извлекать сообщения из очереди не только по FIFO, но и используя систему приоритетов.

28:43

Тупик (deadlock) становится проблемой, когда он возникает.

Одно из трех негативных состояний в системе.

Рассмотрим простейший случай. Пусть два процесса монопольно владеют ресурсами r1 и r2. В процессе выполнения каждому из этих процессов требуется получить дополнительно:

• первому r2
• второму r1

31:24

Это можно записать следующей последовательностью запросов для каждого процесса

Процессы удерживают полученные ими ресурсы и запрашивают дополнительный ресурс, который занят другим процессом. Процесс P1 не может получить R2, P2 не может получить R1 - оба процесса не могут продолжить своего выполнения, находятся в тупике.

33:37

Графовая модель Холта - двудольный направленный граф (петля запросов/замкнутая цепь запросов) - на рисунке ниже граф тупика на единичных ресурсах.

Если ресурсов n единиц, граф будет выглядеть - иначе , маленькие кружочки - единица ресурса.

P1 может сформировать сообщение R3, получив сообщение R1 от процесса P3. Аналогично для других процессов. Такая схема распространена в распределённых системах.

Все три процесса заблокированы в ожидании сообщений.

43:08

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

1. повторно используемые ресурсы
2. потребляемые ресурсы

Наиболее подробно теория тупиков изложена в книге Шоу "Логическое проектирования ОС".

Глава Тупики этой книги - самое полное описание утройства тупиков.

Повторно используемые ресурсы - многократно используется, использование такого ресурса не изменяет качества и характеристики этого ресурса.

К потребляемым ресурсам относится аппаратная часть - память, каналы, внешние устройства, процессор, сообщения.

(Попробуйте прочитать из программного канала сообщение более одного раза, на экзамене расскажете (см. конец файла))

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

Реентерабельные коды - коды чистых процедур, использование процедуры не изменяет ее, такая процедура может быть использована несколькими процессами одновременно.

К потребляемым ресурсам относятся сообщения (получено -> перестало существовать).

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

55:05

Свойства повторно используемых ресурсов:

1. Число единиц повторно используемых ресурсов ограничено и постоянно (изменение возможно, но редко (внешнее устройство вышло из строя); скорее исключение)
2. При использовании этого ресурса его свойства не изменяются

4 условия возникновения тупика (в любой системе):

1. Взаимоисключение. Возникает, когда процессы монопольно используют ресурсы (mutual exclusion).
2. Ожидание. Когда процессы удерживают занятые ими ресурсы, ожидая предоставления им дополнительных ресурсов (Hold and wait).

3. Неперераспределяемость. Когда ресурсы нельзя отобрать у процесса до их завершения, или как говорят, добровольного особождения этих ресурсов (надпись: ресурсы у процесса нельзя принудительно отобрать). (no preemtion)
4. Круговое ожидание. Возникает замкнутая цепь запросов процессов на дополнительные ресурсы. В этой замкнутой цепи каждый процесс занимает ресурс необходимый для продолжения выполнения следующему процессу в данной цепи.

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

69:00

Три основных подхода к тому, чтобы тупики в системе не возникали, или их можно было распознать и ликвидировать.

1. Предотвращение или недопущение (или исключение самой возможности возникновения тупика)
2. Обход или недопущение
3. Обнаружение и восстановление

Он показал, что возникновение тупика невозможно, если нарушено хотя бы одно из 4 условий возникновения тупика.

1. Опережающее требование

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

   Вопрос: какое из условий возникновения тупика исключает данный подход? (Какое условие возникновение тупика нарушается? (Насколько я понимаю, тут не будет Hold and wait, так как все есть изначально))

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

2. Упорядочивание ресурсов (Иерархическое распределение).

   Ресурсы делятся на классы, каждому из которых присваивается номер. Процесс может запрашивать ресурсы только в порядке возрастания их номеров. Вопрос: Какое из условий возникновения тупика исключает данный подход? (2 (есть добровольное освобождение) и 4 (например, если мне нужно 5, а у меня есть 3, то тот, у кого 5 и кому требуется 3 - отдаст 5, чтобы запросить в возрастающем порядке (то есть не может быть кругового ожидания)))

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

   Несмотря на то, что запрашивание ресурсов в порядке их нумерации решает проблему тупиков, часто невозможно определить справедливый порядок нумерации. Справедливый = удовлетворяющий все выполняемые процессы. Это связано с тем, что в системе большое количество ресурсов, в том числе, системные таблицы, объекты ядра: семафоры, мьютексы, разделяемая память. Число ресурсов, которые потенциально может затребовать процесс и число вариантов их использования огромно - это основаная проблема для иерархического распределения ресурсов. Но исключать такую возможность нельзя - в хорошо изученных системах, с хорошо изученными процессами, к которым относятся системы разделения времени, такой подход может использоваться.

3. Устранение условия неперераспределяемости. Если запрос процесса на некоторый ресурс не может быть сразу удовлетворен, то процесс возвращает системе занимаемые им ресурсы (может быть часть). И затем опять пытается их запросить. В результате процесс запрашивает и освобождает одни и те же ресурсы - это увеличивает нагрузку на систему, ресурсы используются неэффективно.

97:00

Тупики возможны, но система анализа системы работает таким образом, чтобы не допустить возникновение тупика.

Правила Дейкстры выделения ресурсов.

Система удовлетворяет запрос процесса на дополнительный ресурс только тогда, когда её состояние после выделения этого ресурса останется надёжным.

Задача банкира решить кому выделять ссуду, а кому нет. Система делает примерно тоже самое.

При выделении ресурсов процессам состояние системы останется надежным. В качестве банкира выступает менеджер ресурсов, заемщиками являются процессы, которые делают заявки на ресурсы.

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

Для успешного выполнения алгоритма необходимо выполнение следующих условий:

1. Процесс не может требовать ресурсов больше, чем имеется в системе
2. Процесс не модет получить ресурсов больше, чем указано в его заявке
3. Сумма всех удерживаемых единиц ресурса одного класса отражает количество распределенных единиц ресурса данного класса. И не может превышать общего число единиц ресура данного класса, имеющегося в системе.

Менеджер ресурсов работает следующим образом: каждый запрос проверяется по отношению к количеству свободных единиц ресурса в системе. При этом сравнивается количество свободных единиц ресурса и максимальная потребность процесса в единицах ресурса данного класса.

107:57

Пример (таблица)

Таблица ниже отражает рапределение одного типа ресурса (надёжное состояние)

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

Процесс P2 не может запросить больше 2 единиц ресурса, потому что в заявке указал максимальную потребность 5, 3 единицы он удерживает - может гарантированно завершиться.

Завершившись, P2 вернет системе ресурсы, суммарно, они смогут удовлетворить макс потребность процесса P1. Завершившись, P1 вернет ресурсы, суммарно они смогут удовлетворить максимальную потребность процесса P3. Следовательно, существует последовательность процессов, в которой все процессы могут гарантированно завершиться. P2->P1->P3

Таблица ниже отражает рапределение одного типа ресурса (ненадёжное состояние)

Ненадежная ситуация в системе.

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

Формальное определение безопасного состояния системы

Состояние системы является безопасным, если существует последовательность процессов такая, что:

1. Первый процесс последовательности обязательно завершиться, так как даже если он запросит максимально заявленное кол-во свободных единиц ресурса, у системы имеется необходимое кол-во единиц ресурса для удовлетворения запроса этого процесса

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

   ...

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

Чтобы найти оптимальную последовательность, необходимо исследовать $n!$ последовательностей (т.е. он скорее теоритический, а не практический)

Ну типа пробуем 2 раза почитать

Код взят из man pipe почти под чистую: просто добавлено повторное чтение и поменяны местами родитель и ребенок (так удобнее в отладчике работать)

#include <stdlib.h>
#include <unistd.h>

int main()
{
    int fildes[2];
    const int BSIZE = 100;
    char buf[BSIZE];
    ssize_t nbytes;
    int status;

    status = pipe(fildes);
    if (status == -1) {
        exit(1);
    }

    switch (fork()) {
    case -1: /* Handle error */
        break;

    case 0:                                    /* Child - writes to pipe */
        close(fildes[0]);                      /* Read end is unused */
        write(fildes[1], "Hello world\n", 12); /* Write data on pipe */
        close(fildes[1]);                      /* Child will see EOF */
        exit(EXIT_SUCCESS);

    default:                                  /* Parent - reads from pipe */
        close(fildes[1]);                     /* Write end is unused */
        nbytes = read(fildes[0], buf, BSIZE); /* Get data from pipe */
        nbytes = read(fildes[0], buf, BSIZE); /* Get data from pipe, x2, oh shit, ryaz_nu no*/
        /* At this point, a further read would see end-of-file ... */
        close(fildes[0]); /* Finished with pipe */
        exit(EXIT_SUCCESS);
    }
}

Breakpoint 1, main () at double.c:29
29	        nbytes = read(fildes[0], buf, BSIZE); /* Get data from pipe */
(gdb) n
30	        nbytes = read(fildes[0], buf, BSIZE); /* Get data from pipe, x2*/

(gdb) p nbytes
$1 = 12
(gdb) n
32	        close(fildes[0]); /* Finished with pipe */
(gdb) p nbytes
$2 = 0
(gdb)