Лекция 10 (05.11.2020) - chrislvt/OS GitHub Wiki

**** ПРЕДИСЛОВИЕ ****

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

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

На самом деле система пыхтит, совершая огромное кол-во действий, но при этом полезная работа не выполняется. Мы с вами обобщили всю информацию, сказав, что в самом общем виде такие все системные вызовы это все системные вызовы (lock и unlock). Часто они называются wait и signal. И в общем-то сделали мы это для того, чтобы показать, что в разных системах такие системные вызовы могут иметь разные названия, но смысл будет один и тот же

Обращаю ваше внимание на материал, который мы назвали семафоры против мьютексов, которые раскрывают различия между такими системным вызовами или, как принято говорить, такими примитивами как семафоры и мьютексы. Различия между ними с точки зрения системы огромные. У семафора нет хозяина. Освободить семафор может совсем не тот процесс, который захватил семафор. В этом, собственно, проблема семафоров в системе. Поэтому системы поддерживают наборы считающих семафоров и именно поэтому на наборе семафоров определено важное свойство: одной неделимой операцией можно изменить все или часть семафоров в наборе. Но безусловно использование отдельных примитивов, связанных со взаимоисключением, требует от разработчика определенных навыков и понимания того, что он делает. Такие программы крайне сложно отлаживать. Крайне сложно определить ситуацию, когда такие процессы могут попасть в тупиковую ситуацию. Поэтому, безусловно, у разработчиков было стремление уйти от таких действий. И в итоге, ну в интернете по-разному называются, я назову одну фамилию - Хоар. Почитаете, там указываются еще разные авторы, но это говорит лишь о том, что проблема была очень важная, животрепещущая и, безусловно, привлекла внимание большого числа исследователей и разработчиков. Я вам предлагаю следующее: если не согласны, ради бога, расширьте эту информацию.

**** Конец предисловия ****

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

В основе мониторов, как правило, лежат два системных вызова: wait и signal, которые определены на переменной типа условие (conditional). По своей структуре похож на класс. Но мониторы появились раньше.

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

Мы сказали, что переменные типа wait и signal изменены на переменные типа условие Переменные типа условие - это особые переменные, к которым в системе организуется очередь или, другими словами, очередь организуется на переменной типа условие.
 Для каждой отдельно взятой причины, по которой процесс может быть переведен в состояние ожидания, назначается своя переменная типа условие. Простой монитор обеспечивает выделение единственного ресурса произвольному числу процессов.

resource: monitor;
var	
    busy: logical;
    x: conditional;
    
    procedure acquire:  
	begin	
            if busy then wait(x);
	    busy:= true;
	end;

    procedure release;
	begin
	    busy :=false;
	    signal(x);
	end;

begin
    busy := false;
end.

Монитор обслуживает произвольное число процессов, ограниченное только размером очереди. В мониторе только две процедуры acquire (приобретать) и release (освобождать). Когда к монитору обращаются для захвата ресурса, то используется функция acquire. Если логическая переменная busy = истина, то по переменной x типа условие выполняется команда wait() и значение логической переменной busy не меняется. Ну системный вызов wait блокирует процесс на переменной x. Само слово wait означает блокировку. Если значение busy = ложь, то процесс, вызвавший acquire, получит доступ к ресурсу без задержки и для переменной busy установит значение true. Таким образом, уже другой процесс не сможет получить доступ к ресурсу пока процесс, захвативший ресурс не вызовет функцию release, в которой сбрасывается флаг busy и вызывается функция signal, которая активизирует процесс, который первым находится в очереди к переменной x типа условие. Здесь развивается принцип, который был заложен Дейкстрой в семафорах, но с помощью других системных вызовов.
Освободить ресурс может только процесс, который его захватил, в отличие от семафоров.


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

процессов-потребителей, которые только выбирают информацию из буфера и процессов-производителей, которые только производят единицу информации и помещают ее в буфер. (ПОДЧЕКНУТЬ ЖИРНЫМ)

resource : monitor;
var	
    circle: array[0, .., n - 1] of type;
    pos : 0 .. n; // текущая позиция
    j  : 0 .. n -1; // заполняемая позиция
    k : 0 .. n - 1; // освобождаемая позиция	
    bufferfull, bufferempty : conditional;

    procedure produces(data : type);
	begin
            if pos = n then wait(bufferempty);
            circle[j] := data;
            pos := pos + 1;
            j := (j + 1) mod n;
            signal(bufferfull);
	end;
	
    procedure consumes (var data : type);
	begin 
            if pos = 0 then wait(bufferfull);
            data := circle[k];
            pos  := pos - 1;
            k := (k + 1) mod n;
            signal(bufferempty);
	end;
begin
    pos := 0;
    j := 0;
    k := 0;
end.

То что буфер кольцевой говорит строка

j := (j + 1) mod n; // именоо mod n, то есть идет зацикливание

Если внимательно посмотреть, то это решение очень сильно коррелируют с решением Дейкстры.

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

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

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

Третий рассматриваем монитор - читатели/писатели. Рассмотрим монитор, предложенный Хоаром. Бытовой пример - покупка билетов на самолет/поезд онлайн. Для этих систем характерны процессы двух типов: процессы-читатели - могут только читать одну и ту же информацию параллельно и процессы-писатели - могут изменять информацию, поля баз данных, при этом писатель должен работать в режиме монопольного доступа, то есть, если писатель получил доступ к разделяемой переменной, то другие писатели не могут получить доступ к ней, а читатели не могут читать значение этой переменной так как они могут прочитать неверное значение. То есть если писатель изменяет значение разделяемой переменной, то ни читать ни писать нельзя.

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

В мониторе Хоара 4 функции (это характерно для монитора Хоара): start read, stop read, start write, stop write.

resource : monitor;
var
    nr : integer; // количество читателей
    wrt : logical; // активный писатель 
    c_read, c_write : condition;

    procedure startread;
	begin   
            if wrt or turn(c_write) then wait(c_read); 		// turn(c_write) - очередь ждущих писателей
            nr := nr + 1;
            signal(c_read);
        end;

    procedure stopread;
	begin
            nr := nr - 1;
            if nr = 0 then signal(c_write);			// signal(c_write) - можно писать 
	end;

    procedure startwrite;
	begin
            if nr > 0 or wrt then wait(c_write);
            wrt := true;
	end;

    procedure stopwrite;
	begin
	    wrt := false;
	    if (turn(c_read)) then signal(c_read)
	    else signal(c_write);
        end;
begin
    nr := 0;
    wrt := false;
end.

Счетчик ждущих читателей, ждущих писателей, активных читателей В Windows потоки В UNIX процессы

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

Завершая чтение, читатель вызывает функцию stopread(). Уменьшается число активных читателей и если число активных читателей равно 0, то есть все читатели прочитали, то вызывается функция signal(c_write) - можно писать, то есть активизируется писатель. Читатель активизирует писателя, таким образом исключается бесконечное откладывание писателей, но не раньше, чем заинтересованные читатели прочитают.

Если есть активный писатель и ждущие писатели, тем самым исключается бесконечное откладывание писателей. Если процесс хочет изменить запись, то он вызывает функцию startwrite(). Он может начать писать, если нет другого активного писателя или нет читающих читателей. Если такие есть, то процесс блокируется в ожидании на переменной c_write. Если таких нет, то писатель устанавливает переменную wrt = истина, указывая тем самым, что ресурс занят.

Завершив редактирование, писатель вызывает функцию stopwrite(). Устанавливается wtr = ложь, но при этом если есть ждущие читатели, вызывается функция signal(c_read), иначе, вызывается функция signal(c_write), то есть активизируется следующий писатель. Таким образом исключается бесконечное откладывание читателей.

На СИ это реализуется через 3 счетчика:

1. Счетчик ждущих читателей;
2. Счетчик активных читателей;
3. Счетчик ждущих писателей. Активный писатель может быть один на определенной переменной.

*** Передача сообщений ***

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

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

’’’ Монитор читатель/писатель - взаимоисключение Монитор потребитель/производитель - синхронизация ’’’

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

В какой-то момент времени, выполняя свой код, процесс p1 посылает сообщение-запрос процессу p2. (Обычно самыми общими названиями таких системных вызовов являются send и recieve. Но для того, чтобы отдельно отметить, что посылается ответ на запрос, применяется ключевое слово reply.) В результате системный вызов send() посылает какие-то параметры. Процесс p2 выполняется с собственно скоростью - это асинхронный процессы, и чтобы принять такое сообщение-запрос, процесс должен вызвать системный вызов recieve(). Если он не готов вызвать recieve(), то процесс p1 будет блокирован до того момента, пока другой процесс не сможет принять его сообщение. Получив сообщение-запрос, процесс p2 обрабатывает какое-то время пришедший запрос с пришедшими данными и, когда он готов, он вызывает relpy.

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

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

Если один процесс заинтересован в работе другого процесса, то они должны быть синхронизированы, то есть тут возможны три типа блокировок:

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

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