Примитивы межпроцессного взаимодействия. Решение проблемы производителя и потребителя с использованием примитивов межпроцессорного взаимодействия

Простейшими примитивами являются sleep и wakeup. Sleep - системный запрос, в результате которого процесс блокируется пока его не запустит другой процесс. Wakeup – в качестве параметра содержит процесс, который следует запустить. Проблема состоит в следующем 2 процесса используют буфер ограниченного размера. Один -производитель помещает данные в этот буфер. Трудность возникает когда производитель хочет поместить в буфер очередную информацию и обнаружив, что он полон и будет ожидать. Другой потребитель будет ожидать пока буфер не будет заполнен в случае если захочет забрать из буфера данные, а буфер пуст.

Для решения этой проблемы вводим переменную (count) для отслеживания колич-ва элементов в буфере (N). Если соunt = N, то производитель уходит в состояние ожидания, в противном случае данные помещаются в буфер и count увеличивается. При соunt =0, потребитель уходит в состояние ожидания. В противном случае оттуда извлекается информация и значение count уменьшается. Производитель может активизировать потребителя с помощью вызова Wakeup в тот момент, когда потребитель не находится в состоянии ожидания.

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

shared enum {false, true} choosing[n];

shared int number[n];

Изначально элементы этих массивов инициируются значениями false и 0 соответственно. Введем следующие обозначения

(a,b) < (c,d), если a < c или если a == c и b < d

max(a0, a1,...., an) — это число k такое, что k >= ai для всех i = 0,...,n

Структура процесса Pi для алгоритма булочной приведена ниже

while (some condition) {

choosing[i] = true;

number[i] = max(number[0],..., number[n-1]) + 1;

choosing[i] = false;

for(j = 0; j < n; j++){

while(choosing[j]);

while(number[j]!= 0 && (number[j],j) < (number[i],i));

}

critical section

number[i] = 0;

remainder section

}

Семафорные примитивы Дейкстры. Решение проблемы производителя и потребителя с помощью семафора

Семафор – целочисленная не отрицательная перемен доступ любого процесса к которой за исключением момента ее инициализац может осущ только через 2 атамарные операции P V(Proberen Verhogen) (привер\ увелич). При выполнении операции Р, над семафором, сначала проверяется его значение. Если оно больше нуля, то из него вычитают 1 и продолжается работа процесса. Если оно равно 0, то процесс переходит в состояние блокировки или ожидания до тех пор, пока значение не станет больше нуля. После этого из него вычит 1 и продолжается работа процесса. При выполнении операции V к значению семаф прибавляется 1. в момент инициализации, семафору может быть присвоено любое значение. Мьютекс (mutex)- двоичный семафор (только 0 и 1). Семафор принимает значение 0 и 1. 1-свободно, 0-занято. Операция V над мьют не увеличивает его значение не больше чем на 1.    

Монитор Хоара как примитив синхронизации высокого уровня

Монитор – особый тип данных, обладающий внутренними переменными описывающ (определяющ) его состояние. Значение этих переменных из вне могут быть изменены только с помощью вызова функц методов этого монитора. Монитор представляет собой особые конструкции языка программ и компилятора обрабат методы мониторов специальным образом, добавляя к ним пролог и эпилог, таким образом реализуется взаимоисключение. Достоинство: вероятность ошибок программ значительно меньше. Условные переменные – если функц не может выполняться дальше, пока не наступит некоторое событие. Она выполняет операцию wait над условной переменной. При этом процесс блокируется и в монитор может выйти другой процесс. Когда событие происходит, другой процесс выполняет операц. c.signal от этого ранее заблокированный процесс становится активным. Если на этой перемен блокировалось несколько процессов, то активизируется только один из них. Условные переменные в отличии от семафора не помнят предысторию. Соответ, если произведена операция signal над условн перемен которые которые никто не заблокиров, то данный сигнал будет утерян и никем не использован. Сообщение – используется два примитива. Оба имеют скрытый механизм взаимоисключ и блокировка из чтения пустого буфера и запись в переполнен. Решение задачи произв\потреб с помощью сообщ тривиально.   

Поняие виртуального и физического адреса.

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