Lecture
1.Проблемы межпроцессного взаимодействия.
а)Состояние состязания;
б)Критические секции;
2. Метод синхронизации -Взаимное исключение с активным ожиданием
а) запрет всех прерываний ;
б)переменные блокировки;
в)строгое чередование;
г)Алгоритм Петерсона.
3.Примитивы межпроцессного взаимодействия. Семафоры.
а)Проблема производителя и потребителя;
б) Мьютексы;
1. Проблемы межпроцессного взаимодействия
Проблема межпроцессного взаимодействия разбивается на три пункта:
1) передача информации от одного процесса к другому;
2) контроль за тем, чтобы два процесса не пересекались в критических ситуациях. Например, два процесса пытаются завладеть одной и той же областью памяти;
3) Синхронизация. Например, если процесс А должен поставлять данные, а процесс В должен подождать и не начинать печатать, пока не поступят данные от процесса А.
Два из трех пунктов относятся и к потокам. Первый – передача информации потоков не касается, поскольку у потоков общее адресное пространство. Мы будем рассматривать эти ситуации в контексте процессов, но эти же рассуждения применимы и для потоков.
Большинство практически применяемых структур должны соответствовать критерию целостности. Например, в упорядоченном массиве каждый элемент должен больше (меньше) предыдущего или равен ему. Основной способ модификации – вставка дополнительного элемента.( метод « пузырька», «вставки»…) Важно, что любой способ вставки происходит не мгновенно, и все время работы этой процедуры массив не является упорядоченным. Если вставка происходила в основном потоке прерывания, обработчик прерывания, который в это время пытается работать с массивом как с упорядоченным, будет жестоко разочарован.
Ошибки такого рода в литературе называются race condition (ошибка соревнования). Единственный способ избежать ошибок соревнования – НЕ ДЕЛАТЬ ИХ.
Состояние соревнования. Процессы, работающие совместно могут сообща использовать некоторое хранилище данных. Каждый из процессов может считывать из общего хранилища данных и записывать туда информацию. Хранилищем, например, может быть файл общего доступа или участок оперативной памяти. Ситуации, в которых два (и более процесса считывают или записывают данные одновременно, и конечный результат зависит от того, какой из них был первым, называются ситуациями соревнования.
Критические секции. Общепринятое взаимодействие между различными процессами АСИНХРОННОЕ взаимодействие, в противоположность СИНХРОННОМУ взаимодействию между различными модулями последовательно исполняемой программы. Проблема возникает только тогда, когда модификации подвергается объект, разделяемый несколькими процессами. Для возникновения проблемы достаточно, чтобы только один процесс занимался модификацией, а все остальные учитывали состояние объекта.
Основной способ предотвращения проблем в этой и другой ситуации, связанной с совместным использованием памяти, файлов и чего-либо еще, является запрет одновременной записи и чтения разделенных данных более, чем одни процессом. То есть необходимо взаимное исключение. Это значит, когда один процесс использует разделенные данные, другому процессу это будет делать запрещено.
Часть программы, в которой есть обращение к совместно используемым данным, называется критической областью или критической секцией. Если нам удается избежать одновременного нахождения двух процессов в критических областях, мы сможем избежать соревнований.. Для этого необходимо выполнение четырех условий:
2. Методы синхронизации
Взаимное исключение с активным ожиданием. Как возможный вариант – 1) запрет всех прерываний при входе процесса в критическую область, в том числе и прерываний по таймеру, то есть мы не сможем снять процесс с выполнения – отключить процессор. Однако давать такие полномочия пользовательскому процессу опасно. Если отключены все прерывания, а в результате сбоя не включить их обратно – операционная система разрушена.
2)Переменные блокировки. Для каждой критической области – одна совместно используемая переменная блокировки, так называемая, флаговая переменная. Процессы, прежде чем войти в критическую область, проверяют эту переменную. Недостаток: состязание процессов за переменную блокировки.
Представьте, что один процесс считывает переменную блокировки, обнаруживает, что она равна 0, но прежде, чем он успевает изменить ее на 1, управление получает другой процесс, тоже изменяющий ее на 1. Когда первый процесс снова получит управление, он успешно заменит переменную блокировки на 1, и два процесса одновременно окажутся в критических областях.
Листинг 4.1. Наивная реализация взаимного исключения на основе флаговой переменной.
PR1: while(1){
while (turn!=0) ;/* loop*/
turn=1;
critical_region ();
turn=0;
noncritical_region ();
}
PR2: while(1){
while (turn!=0) ; /* loop*/
turn=1;
critical_region ();
turn=0;
noncritical_region ();
}
Именно благодаря простоте программа никуда не годится: проверка флага и его установка реализуются двумя разными операторами, в промежутке между которыми другой процесс может получить управление и также установить флаговую переменную! Окно, в котором происходит соревнование, составляет всего 2-3 команды, но при попадании обоих процессов в это окно, мы получаем как раз то, чего стремились избежать: оба процесса могут войти в критическую секцию.
3) Строгое чередование:
while(1){
while (turn!=0)/* loop*/
critical_region ();
turn=1;
noncritical_region ();
}
Процесс 0 вначале проверяет значение turn, считывает 0 и входит в критическую область.
while(1){
while (turn==0)/* loop*/
critical_region ();
turn=0;
noncritical_region ();
}
Процесс 1 также проверяет значение turn, считывает 0 и после этого входит в бесконечный цикл, ожидая когда же значение turn изменится. Постоянная проверка значения переменной называется активным ожиданием. Недостаток : бесцельная трата процессорного времени. Блокировка, использующая активное ожидание называется спин-блокировкой.
Эта ситуация нарушает третье из сформулированных нами условий: один процесс блокирован другим, не находящимся в критической области.
4) Алгоритм Петерсона.
#define FALSE 0
#define TRUE 1
#define N 2 /*количество процессов */
int turn; /*чья сейчас очередь */
int inerested[N]; /*все переменные изначально равны нулю */
void enter_region(int process); /*Процесс 0 или 1 */
{
int other; /* номер второго процесса */
other =1- process; / * противоположный процесс */
interested[process] = TRUE; / * индикатор интереса*/
turn= process; / * установка флага*/
while (turn==process && interested[other] ==TRUE) / * Пустой оператор */
}
void leave_region (int process) / * процесс, покидающий критическую область */
{
interested[process] = FALSE; / * индикатор выхода из критической области */
}
Исходно оба процесса находятся вне критических областей. Процесс 0 вызывает enter_region , задает элементы массива устанавливает переменную turn равной 0. Поскольку процесс 1 не заинтересован в попадании в критическую область, процедура возвращается. Теперь, если процесс 1 вызовет enter_region, ему придется подождать, пока interested[0] примет значение FALSE, а это произойдет только в тот момент, когда процесс 0 вызовет процедуру leave_region, чтобы покинуть критическую область.
Если оба сразу вызовут enter_region одновременно. Оба сохранят свои номера в turn. Сохранится номер того процесса, который был вторым, а предыдущий номер был утерян. Предположим, что вторым был процесс 1, так что значение turn равно 1. Когда оба процесса дойдут до оператора while, процесс 0 войдет в критическую область, а процесс1 останется в цикле и будет ждать, пока процесс 0 выйдет из критической области.
2. Примитивы межпроцессного взаимодействия
Алгоритм Петерсона корректен, но он обладает одним недостатком – использованием активного ожидания. Реализует следующий алгоритм: перед входом в критическую область проверяет, можно ли это сделать. Если нельзя, то входит в тугой цикл ожидания – бесцельная растрата процессорного времени.
.
Семафоры. В 1965 году Дейкстра предложил использовать целую переменную для подсчета сигналов запуска . Этот новый тип переменных – семафор, значение может быть нулем или некоторым положительным числом. Две операции down и up. Операция down сравнивает значения семафора с нулем. Если значение семафора больше нуля, то down уменьшает его и возвращает управление. Если равно нулю, то процедура down не возвращает управления процессу, а переводит его в состояние ожидания. Операции: 1) проверки значения семафора; 2)изменения семафора или перевода процесса в состояние ожидания выполняются как единое и неделимое элементарное действие. Так называемое атомарное действие. Таким образом, за счет атомарности, гарантируется, что после начала операции ни один процесс не получит доступа к семафору до окончания или блокирования операции.
Вообще говоря, группа операций модификации разделяемой структуры данных, которая происходит атомарно, не прерываясь никакими другими операциями с той же структурой данных, называется транзакцией.
Операция up увеличивает значение семафора. Если с этим семафором связаны один семафора 1 или несколько ожидающих процессов, которые не могут завершить более раннюю операцию down, один из них выбирается системой. Таким образом, после выполнения операции up над семафором, связанным с несколькими ожидающими процессами, значение семафора так и останется равным 0, но число ожидающих процессов уменьшится на единицу. Операция увеличения семафора и активизации процесса тоже неделима. Ни один процесс не может быть блокирован во время выполнения операции up.
Пытаясь пройти через семафор, процесс пытается вычесть из значения семафора 1 . Если значение семафора больше или равно 1, процесс проходит сквозь семафор успешно – семафор открыт. Если процесс равен нулю (семафор закрыт), процесс останавливается и становится в очередь.
Закрытие семафора соответствует захвату или объекту или ресурса, доступ, к которому контролируется этим семафором. Если объект захвачен, то остальные процессы вынуждены ждать его освобождения. Закончив работу с объектом (выйдя из критической секции), процесс увеличивает значение семафора на единицу, открывая его. При первый, из стоявших в очереди процессов активизируется, вычитает из семафора единицу, снова закрывая семафор. Если же очередь была пуста, то ничего не происходит, просто семафор остается открытым. Это похоже на работу железнодорожного семафора, контролирующего движение по одноколейной ветке.
Мьютексы. Mutual exclusion – взаимное исключение или двоичный семафор (0 и 1). Этот семафор соответствует случаю, когда с разделяемым ресурсом в каждый момент времени может работать только один процесс.
Реализация его проста и эффективна, используется для синхронизации потоков.
Значение мьютекса устанавливается двумя процедурами : mutex_lock и mutex_unlock .
Семафоры общего вида. Могут принимать любые неотрицательные значения, еще называются счетчиками. Это соответствует случаю, когда несколько процессов могут работать с объектом одновременно или объект состоит из нескольких независимых, но равноценных частей - например, нескольких одинаковых принтеров.
Проблема производителя и потребителя. Два процесса используют буфер ограниченного размера. Один из них, производитель, помещает туда данные, а другой потребитель – считывает их оттуда. Нужна переменная count для отслеживания количества элементов в буфере. Каждый из процессов должен проверять значение count: производитель, чтобы не переполнить буфер, а потребитель, чтобы уйти в состояние ожидание, если count=0. В случае необходимости один процесс активизирует другой.
На уровне ОС неделимость операций down и up реализуется путем запрета прерываний. Поскольку для выполнения этих действий требуется всего лишь несколько команд процессора , запрет прерываний не приносит никакого вреда.
Листинг 5.3. Проблема производителя и потребителя с семафорами
#define N 100 /*количество сегментов в буфере*/
typedef int semaphore; /* семафоры – особый вид переменных*/
semaphore mutex =1; /* контроль доступа в критическую область*/
semaphore empty =N; /* число пустых сегментов буфера*/
semaphore full=0; /* число полных сегментов буфера*/
void producer (void)
{int item;
while (1){
item=pr(); /* создать данные помещаемые в буфер */
down(&empty); /* уменьшить счетчик пустых сегментов буфера*/
down(&mutex); /* вход в критическую область */
insert_item(item) /* поместить в буфер новый элемент */
up((&mutex); /*выход из критической области */
up(&full); /* увеличить счетчик полных сегментов буфера */
}}
void consumer (void)
{int item;
while (1){
down(&full); /* уменьшить счетчик полных сегментов буфера*/
down(&mutex); /* вход в критическую область */
item=rm(); /* удалить элемент из буфера */
up((&mutex); *выход из критической области */
up(&empty); /* увеличить счетчик пустых сегментов буфера */
consum(); /* обработка элемента */
}}
Семафоры использовались в программе двумя различными способами: 1) mutex – для взаимного исключения, а остальные семафоры использовались для синхронизации. В нашем случае они гарантируют, что производитель прекращает работу, когда буфер полон, а потребитель прекращает работу, когда буфер пуст.
пример простейшей синхронизации взаимодействующих процессов-разделение ресурса времени (процессора). Можно использовать семафорные операции для решения таких задач, в которых успешное завершение одного процесса связано с ожиданием завершения другого. Предположим, что существуют два процесса ПР1 и ПР2. Необходимо, чтобы процесс ПР1 запускал процесс ПР2 с ожиданием его выполнения, то есть ПР1 не продолжал бы выполняться до тех пор, пока процесс ПР2 до конца не выполнит свою работу.
Пример синхронизации процессов
var S: semaphore;
begin
Init Sem(S,0);
ПР1: begin
ПР11: {первая часть ПР1}
ON (ПР2); {поставить на выполнение ПР2}
P(S);
ПР12; {оставшаяся часть ПР1}
STOP
end
ПР2: begin
ПР2: {вся работа программы ПР2}
V(S);
STOP
end
end
Начальное значение семафора равно нулю. Если процесс ПР1 начал выполняться первым, то через некоторое время он поставит на выполнение процесс ПР2, после чего выполнит операцию P(S) и «заснет» на семафоре, перейдет в состояние пассивного ожидания. Процесс ПР2, осуществив все необходимые действия, выполнит примитив V(S) и откроет семафор, после чего процесс ПР1 будет готов к дальнейшему выполнению.
решение задачи «читатели – писатели. Разделение ресурса места (памяти на жестком диске). «Читатели» - процессы, которые могут параллельно считывать информацию из некоторой общей области памяти, являющейся критическим ресурсом. «Писатели» - процессы, записывающие информацию в эту область памяти, исключая при этом и друг друга, и процессы «читатели». Имеются различные варианты взаимодействия между «писателями» и «читателями».
Например, если хотя бы один «читатель» пользуется ресурсом, то он закрыт для использования всем «писателям» и доступен для использования всем «читателям». Во втором варианте, наоборот, больший приоритет у процессов «писатели». При появления запроса от «писателя» необходимо закрыть дальнейший доступ всем тем процессам «читателям», которые выдадут запрос на критический ресурс после него.
Другим примером может служить система автоматизированной продажи билетов. Процессы «читатели» обеспечивают нас справочной информацией о наличии свободных билетов на тот или иной рейс. Процессы «писатели» запускаются с пульта кассира, когда он оформляет для нас билет. Имеется большое количество как «читателей» так и «писателей».
Пример. Решение задачи «читатели – писатели» с приоритетом в доступе к критическому ресурсу «читателей».
var R, W: semaphore;
NR: Integer;
procedure READER
begin
P(R);
Inc(NR); {NR:=NR+1}
if NR = 1 then P (W);
V(R);
Read_Data; {kritikal interval}
P(R);
Dec(NR);
if NR=0 then V(W);
V( R );
end
procedure WRITER
begin
P(W);
Write_Data; {kritikal interval}
V(W)
end
begin
NR:=0;
Init Sem(R, 1); Init Sem(W, 1);
begin
while true do READER
and
while true do READER
and
while true do READER
………………………
and
while true do WRITER
and
while true do WRITER
end; end;
При решении данной задачи используются два семафора R и W и переменная NR, предназначенная для подсчета текущего числа процессов типа «читатели», находящихся в критическом интервале. Доступ к разделяемой памяти осуществляется через семафор W. Семафор R используется для взаимоисключения процессов типа «читатели».
Если критический ресурс не используется, то первый появившийся процесс при входе в критический интервал выполнит операцию P(W) и закроет семафор. Если процесс является «читателем», то переменная NR будет увеличена на единицу и последующие «читатели» будут обращаться к ресурсу, не проверяя значение семафора W, что обеспечивает параллельность их доступа к памяти. Последний «читатель», покидающий критический интервал, является единственным, кто выполнит операцию V(W) и откроет семафор W. Семафор R предохраняет от некорректного изменения значения NR, а также от выполнения «читателями» операций P(W) и V(W). Если в критическом интервале находится «писатель», то на семафоре W может быть заблокирован только один «читатель», все остальные будут блокироваться на семафоре R.
Другие писатели блокируются на семафоре W.
Когда «писатель» выполняет операцию V(W), неясно какого типа процесс войдет в критический интервал. Чтобы гарантировать процессам читателям получение более «свежей» информации необходимо при постановке в очередь готовности учитывать более высокий приоритет писателей. Однако этого оказывается недостаточно, ибо если в критическом интервале продолжает находиться, по крайней мере, один «читатель», то он не даст обновить данные, но и не воспрепятствует вновь приходящим процессам «читателям» войти в свою критическую секцию. Необходим дополнительный семафор.
Пример. Решение задачи «читатели – писатели» с приоритетом в доступе к критическому ресурсу «читателей» с дополнительным семафором.
var R, W, S: semaphore;
NR: Integer;
procedure READER
begin
P(S);P(R);
Inc(NR); {NR:=NR+1}
V(S);V(R);
Read_Data; {kritikal interval}
P(R);
Dec(NR);
if NR=0 then V(W);
V( R );
end
procedure WRITER
begin
P(S);P(W);
Write_Data; {kritikal interval}
V(S);V(W);
end
begin
NR:=0;
Init Sem(S, 1); Init Sem(W, 1); Init Sem(R, 1);
begin
while true do READER
and
while true do READER
and
while true do READER
………………………
and
while true do WRITER
and
while true do WRITER
end;end
Семафор S блокирует приход новых читателей, если появился хотя бы один процесс «писатель». В процедуре читатель использование семафора S необходимо только при входе в критический интервал. После выполнения чтения уже категорически нельзя использовать этот семафор, он тут же заблокировать первого «читателя», если хотя бы один писатель вошел в свою критическую секцию. И получится, так называемая тупиковая ситуация, потому что «писатель» не сможет войти в свою критическую секцию, поскольку в ней уже находится читатель. А «читатель» не сможет покинуть критическую секцию, потому что процесс «писатель» желает войти в свой критический интервал.
Пример. Синхронизация процессов «читатели» и «писатели» без взаимного исключения
var V1, V2: integer;
procedure WRITER
begin
Inc(V1);
Write _Data; {kritikal interval}
V2:=V1;
end;
procedure READER
var V: integer;
Begin
Repeat V:=V2;
Read Date
Until V1=V
End;
Begin
V1:=0;
V2:=0;
Begin
while true do READER
and
while true do READER
………………………
and
while true do READER
and
while true do WRITER
end;end.
Этот алгоритм использует для данных два номера версий, которым соответствуют переменные V1 V2. Перед записью пoрции новых данных процесс писатель увеличивает на 1 значение переменной V1, а после записи – переменную V2. «Читатель» обращается к V2 перед чтением данных, а к V1 – после. Если при этом V1 и V2 равны, то очевидно получена правильная версия данных. Если же данные обновлялись во время чтения, то операция повторяется. Данный алгоритм можно использовать в том случае, если нежелательно заставлять процесс писатель ждать, пока «читатели» закончат операцию чтения, или если вероятность повторения операции чтения достаточно мала и обусловленное повторными операциями снижение эффективности меньше потерь, связанных с избыточностью решения при использовании взаимного исключения. Существует вероятность зацикливания чтения при высокой интенсивности операций записи. Наконец, само чтение представляет собой довольно длительную операцию, то оператор V1:=V2 для процесса «читатель» может быть заменен на оператор
Repeat V:=V2; Until V1=V.
Это предотвращает выполнение «читатели» операции чтение, если «писатель» уже начал запись
Пример. Использования API семафоров .
#include <stdio.h>
#include <unistd.h>
#include <wait.h>
#include <iostream.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <signal.h>
#include <errno.h>
#define sss 16
int main () {
int i, s , m[20];
struct sembuf buf[1] = {0, -1, 0};
struct sembuf buf2[1] = {0, 1, 0};
for (i=0; i < 20; i ++) {
if ((m[i] = fork()) != 0) continue;
s = semget (sss, 1, IPC_CREAT | IPC_EXCL | 0666);
if (s == -1) {
if (errno != EEXIST) { perror("ERROR"); _exit(1); }
s = semget (sss, 1, 0666);
if (s == -1) { perror("ERROR"); _exit(1); }
cout << "connect "<< i << endl;
} else {
// master
if (semctl (s, 0, SETVAL, 1) == -1) perror ("CTRL");
}
while (1) {
semop (s, buf, 1);
cout << "task " << i << endl;
sleep(1);
semop (s, buf2, 1);
}
_exit (0);
}
sleep (20);
for (i=0;i<20;i++) { kill ( m[i], SIGKILL ); wait(&st); }
_exit (0);
}
Контрольные вопросы.
1. Сравните между собой такие методы синхронизации как строгое чередование и алгоритм Петерсона.
2. Какие действия составляют атомарную операцию проверки значения семафора down.
3. Какие действия составляют атомарную операцию проверки значения семафора up.
4. Определение мьютекса.
5. Определение считающего семафора.
6. Алгоритм синхронизации доступа к ресурсу процессора.
7. Алгоритм синхронизации доступа к ресурсу оперативной памяти.
8. Пример алгоритма синхронизации доступа к ресурсу файла на диске.
9. Как определить количество семафоров в наборе, необходимое для решения той или иной задачи.
10. Какие из предложенных ниже методов синхронизации доступа к ресурсу относятся к реализуемым на пользовательском уровне, а какие на системном: алгоритм Петеросона, строгое чередование, флаги, семафоры.
Comments
To leave a comment
Operating Systems and System Programming
Terms: Operating Systems and System Programming