Лекция 13

Базовые принципы функционирования вычислительных систем

Список литературы

Вильям Столлингс. Операционные системы. Москва. Издательский дом ``Вильямс’’. 2002.

С.В.Зубков. Ассемблер для DOS, Windows и UNIX.

Михаил Гук. Аппаратные средства IBM PC.

Системы реального времени. Многопоточность. Потоки и процессы

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

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

К системам реального времени применимо требование многопоточности. С общим понятием `задачи’ обычно ассоциируются два понятия: поток (= нить = thread) и процесс. Обычно, под потоком понимают диспетчирезуемую единицу работы, с которой связывается контекст процессора (например, регистр флагов), собственный стек (который обычно задается регистром стека). Обычно потоки внутри одного процесса имеют одно адресное пространство. Процесс является объединением некоторого количества потоков вместе с набором ресурсов, связанных с потоками. В отличие от потоков, различные процессы, вообще говоря, должны иметь различные адресные пространства. Одна задача, вообще говоря, может состоять из нескольких процессов, в каждом из которых может быть несколько нитей.

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

Обычно к операционным системам реального времени предъявляют следующие требования:

1. ОС должна быть многонитевой и прерываемой.

2. Должно существовать понятие приоритета нити. Нить с высшим приоритетом должна иметь возможность прервать выполнение нити с низшим приоритетом.

3. ОС должна обеспечивать предсказуемые механизмы синхронизации задач (блокировка и посылка сигналов).

4. Должна существовать система наследования приоритетов. Это понятие связано с понятием инверсии приоритетов. Пусть запущено три процесса. Процесс с низшим из трех приоритетов может захватить некоторый ресурс А. Пусть сразу после этого запускается второй процесс с большим приоритетом, который вытесняет первый процесс. Далее запускается третий процесс с самым большим приоритетом и он тоже требует ресурс А. В результате получается блокировка: третий процесс не может продолжать работу, пока не первый процесс не освободит ресурс А, а первый процесс вынужден ждать завершения работы второго процесса. Т.о. на работу процесса с высшим приоритетом оказывает влияние процесс с низшим приоритетом. Эта ситуация называется инверсией приоритетов. Отметим, что эта ситуация весьма часто встречается в различных версиях Windows (в ранних версиях чаще, в более новых - реже).

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

5. Поведение ОС должно быть известно. Например, должны быть известны времена выполнения всех системных вызовов, времена задержки от поступления прерывания до выполнения соответствующей процедуры и т.д.

Состояния процессов

В этом раздел мы не будем разделять понятия потока и процесса. Постараемся описать некоторые модели взаимодействия процессов, обеспечивающих их взаимосуществование. Будем предполагать, что система однопроцессорная, т.е. в один момент времени реально может выполняться только один процесс. Здесь имеется в виде, что в ОС существует понятие диспетчера. Под диспетчером подразумевается часть ОС, осуществляющая контроль за основным ресурсом ЭВМ – процессорным временем. Диспетчер с некоторой периодичностью передает право на использование процессора от одного процесса к другому.

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

Простейшая модель из двух состояний

Пусть в системе одновременно находятся как минимум два процесса. Как мы договорились, в каждый момент времени может выполняться только один процесс. Тогда первое, что приходит в голову, это – ввести два основных состояния процессов: выполняется и не выполняется.

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

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

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

Классическая модель из пяти состояний

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

Кроме этого, полезно выделить еще два важных состояния: новый и завершающийся.

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

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

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

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

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

Понятие свопинга. Модель из шести или семи состояний

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

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

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

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

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

Основные принципы параллельных вычислений

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

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

· Проблемы, возникающие при некорректном разделении доступа к глобальным объектам

· Проблемы, связанные со сложностью для ОС оптимального разделения ресурсов между процессами; при неоптимальном распределении ресурсов возможны явления, имеющие названия взаимоблокировки и голодание

· Сложность устойчивого повтора создавшихся ситуаций при отладке программ

Первую проблему можно проиллюстрировать следующим примером:

char *num2str(int n){static char s[100]; sprintf(s,”%d”,n); return s;}

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

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

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

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

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

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

Конкуренция процессов в борьбе за ресурсы

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

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

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

Сотрудничество с использованием разделения

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

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

void NInc(){n=n+1;}

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

положить переменную n в регистр

увеличить переменную n на 1

положить значение регистра в переменную n

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

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

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

void NInc2(){n1=n1+1;n2=n2+1;}

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

Следующий пример еще более неприятен:

В одном процессе выполняется функция

void Add1(){n1++; n2++;}

а в другом:

void Mult2(){n1*=2; n2*=2;}

Применение каждой функции не нарушает условие равенства переменных. Однако их одновременное применение может привести к следующей последовательности действий:

n1++;

n1*=2;

n2*=2;

n2++;

а в этом случае переменные перестанут быть равными.

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

Сотрудничество с использованием связи

Пусть есть два или более процессов, которые знают идентификаторы друг друга и могут активно друг с другом общаться. Даже в этом случае возможны конфликты. Например, процесс P1 постоянно обменивается данными с процессами P2, P3. Голодание может возникнуть от того, что процесс P1 будет постоянно обмениваться данными с процессом P2, а процесс P3 будет сколь угодно долго ждать своей очереди.

Программная реализация. Алгоритм Деккера

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

void CriticalBegin();

void CriticalEnd();

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

Попытка 1.

int Num=0;//указывает номер процесса, занимающего критический ресурс

//Процесс 1:

void CriticalBegin()

{

while(Num==1);

}

void CriticalEnd();

{

Num=1;

}

//Процесс 2:

void CriticalBegin()

{

while(Num==0);

}

void CriticalEnd();

{

Num=0;

}

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

Попытка 2.

//указывает занятость ресурса, соответственно, первым и вторым процессами

int flag[2]={0,0};

//Процесс 1:

void CriticalBegin()

{

while(flag[1]==1);//пока ресурс занят вторым процессом

flag[0]=1;//занять ресурс первым процессом

}

void CriticalEnd();

{

flag[0]=0;//освободить ресурс первым процессом

}

//Процесс 2:

void CriticalBegin()

{

while(flag[0]==1);//пока ресурс занят первым процессом

flag[1]=1;//занять ресурс вторым процессом

}

void CriticalEnd();

{

flag[1]=0;//освободить ресурс вторым процессом

}

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

Попытка 3.

//указывает занятость ресурса, соответственно, первым и вторым процессами

int flag[2]={0,0};

//Процесс 1:

void CriticalBegin()

{

flag[0]=1;//занять ресурс первым процессом

while(flag[1]==1);//пока ресурс занят вторым процессом

}

void CriticalEnd();

{

flag[0]=0;//освободить ресурс первым процессом

}

//Процесс 2:

void CriticalBegin()

{

flag[1]=1;//занять ресурс вторым процессом

while(flag[0]==1);//пока ресурс занят первым процессом

}

void CriticalEnd();

{

flag[1]=0;//освободить ресурс вторым процессом

}

возможна ситуация, когда два процесса одновременно установят флаги и далее произойдет взаимная блокировка.

Попытка 4.

//указывает занятость ресурса, соответственно, первым и вторым процессами

int flag[2]={0,0};

//Процесс 1:

void CriticalBegin()

{

flag[0]=1;//занять ресурс первым процессом

while(flag[1]==1)//пока ресурс занят вторым процессом

{//попали в коллизию

flag[0]=0;//освободим на время ресурс

sleep(1);

flag[0]=1;//опять займем ресурс

}

void CriticalEnd();

{

flag[0]=0;//освободить ресурс первым процессом

}

//Процесс 2:

void CriticalBegin()

{

flag[1]=1;//занять ресурс вторым процессом

while(flag[0]==1)//пока ресурс занят первым процессом

{//попали в коллизию

flag[1]=0;//освободим на время ресурс

sleep(1);

flag[1]=1;//опять займем ресурс

}

void CriticalEnd();

{

flag[1]=0;//освободить ресурс вторым процессом

}

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

Алгоритм Деккера.

//указывает занятость ресурса, соответственно, первым и вторым процессами

int flag[2]={0,0};

int Num=0;

//Процесс 1:

void CriticalBegin()

{

flag[0]=1;//занять ресурс первым процессом

while(flag[1]==1)//пока ресурс занят вторым процессом

if(Num==1)//если надо уступить второму процессу

{

flag[0]=0;//освободим ресурс

while(Num==1);//подождем завершения второго процесса

flag[0]=1;//займем ресурс

}

void CriticalEnd();

{

Num=1;

flag[0]=0;//освободить ресурс первым процессом

}

//Процесс 2:

void CriticalBegin()

{

flag[1]=1;//занять ресурс вторым процессом

while(flag[0]==1)//пока ресурс занят первым процессом

if(Num==0)//если надо уступить первому процессу

{

flag[1]=0;//освободим ресурс

while(Num==0);//подождем завершения первого процесса

flag[1]=1;//займем ресурс

}

void CriticalEnd();

{

Num=0;

flag[1]=0;//освободить ресурс вторым процессом

}

Лекция 14

Базовые принципы функционирования вычислительных систем

Список литературы

Вильям Столлингс. Операционные системы. Москва. Издательский дом ``Вильямс’’. 2002.

С.В.Зубков. Ассемблер для DOS, Windows и UNIX.

Михаил Гук. Аппаратные средства IBM PC.

Взаимоисключения

Программная реализация. Алгоритм Деккера

void CriticalBegin();

void CriticalEnd();

Попытка 1.

int Num=0;//указывает номер процесса, занимающего критический ресурс

//Процесс 1:

void CriticalBegin()

{

while(Num==1);

}

void CriticalEnd();

{

Num=1;

}

//Процесс 2:

void CriticalBegin()

{

while(Num==0);

}

void CriticalEnd();

{

Num=0;

}

Попытка 2.

//указывает занятость ресурса, соответственно, первым и вторым процессами

int flag[2]={0,0};

//Процесс 1:

void CriticalBegin()

{

while(flag[1]==1);//пока ресурс занят вторым процессом

flag[0]=1;//занять ресурс первым процессом

}

void CriticalEnd();

{

flag[0]=0;//освободить ресурс первым процессом

}

//Процесс 2:

void CriticalBegin()

{

while(flag[0]==1);//пока ресурс занят первым процессом

flag[1]=1;//занять ресурс вторым процессом

}

void CriticalEnd();

{

flag[1]=0;//освободить ресурс вторым процессом

}

Попытка 3.

//указывает занятость ресурса, соответственно, первым и вторым процессами

int flag[2]={0,0};

//Процесс 1:

void CriticalBegin()

{

flag[0]=1;//занять ресурс первым процессом

while(flag[1]==1);//пока ресурс занят вторым процессом

}

void CriticalEnd();

{

flag[0]=0;//освободить ресурс первым процессом

}

//Процесс 2:

void CriticalBegin()

{

flag[1]=1;//занять ресурс вторым процессом

while(flag[0]==1);//пока ресурс занят первым процессом

}

void CriticalEnd();

{

flag[1]=0;//освободить ресурс вторым процессом

}

возможна ситуация, когда два процесса одновременно установят флаги и далее произойдет взаимная блокировка.

Попытка 4.

//указывает занятость ресурса, соответственно, первым и вторым процессами

int flag[2]={0,0};

//Процесс 1:

void CriticalBegin()

{

flag[0]=1;//занять ресурс первым процессом

while(flag[1]==1)//пока ресурс занят вторым процессом

{//попали в коллизию

flag[0]=0;//освободим на время ресурс

sleep(1);

flag[0]=1;//опять займем ресурс

}

void CriticalEnd();

{

flag[0]=0;//освободить ресурс первым процессом

}

//Процесс 2:

void CriticalBegin()

{

flag[1]=1;//занять ресурс вторым процессом

while(flag[0]==1)//пока ресурс занят первым процессом

{//попали в коллизию

flag[1]=0;//освободим на время ресурс

sleep(1);

flag[1]=1;//опять займем ресурс

}

void CriticalEnd();

{

flag[1]=0;//освободить ресурс вторым процессом

}

Алгоритм Деккера.

//указывает занятость ресурса, соответственно, первым и вторым процессами

int flag[2]={0,0};

int Num=0;

//Процесс 1:

void CriticalBegin1()

{

flag[0]=1;//занять ресурс первым процессом

while(flag[1]==1)//пока ресурс занят вторым процессом

if(Num==1)//если надо уступить второму процессу

{

flag[0]=0;//освободим ресурс

while(Num==1);//подождем завершения второго процесса

flag[0]=1;//займем ресурс

}

void CriticalEnd1();

{

Num=1;

flag[0]=0;//освободить ресурс первым процессом

}

//Процесс 2:

void CriticalBegin2()

{

flag[1]=1;//занять ресурс вторым процессом

while(flag[0]==1)//пока ресурс занят первым процессом

if(Num==0)//если надо уступить первому процессу

{

flag[1]=0;//освободим ресурс

while(Num==0);//подождем завершения первого процесса

flag[1]=1;//займем ресурс

}

void CriticalEnd2();

{

Num=0;

flag[1]=0;//освободить ресурс вторым процессом

}

Программная реализация. Алгоритм Петерсона.

Алгоритм Петерсона представляет более простую реализацию взаимоисключений.

//указывает занятость ресурса, соответственно, первым и вторым процессами

int flag[2]={0,0};

int Num=0;

//Процесс 1:

void CriticalBegin1()

{

/*1.1*/ flag[0]=1;//занять ресурс первым процессом

/*1.2*/ Num=1;//уступка права на критич.ресурс второму процессу

/*1.3*/ while(flag[1]==1&&Num==1);//пока ресурс занят вторым процессом

}

void CriticalEnd1();

{

flag[0]=0;//освободить ресурс первым процессом

}

//Процесс 2:

void CriticalBegin2()

{

/*2.1*/ flag[1]=1;//занять ресурс вторым процессом

/*2.2*/ Num=0;//уступка права на критич.ресурс первому процессу

/*2.3*/ while(flag[0]==1&&Num==0);//пока ресурс занят первым процессом

}

void CriticalEnd2();

{

flag[1]=0;//освободить ресурс вторым процессом

}

Докажем, что оба процесса не могут одновременно попасть в критическую секцию. Допустим это так. Тогда рассмотрим три варианта.

1. При выполнении в последний раз сравнения в /*1.3*/ и /*2.3*/ сравнения производились одновременно (многопроцессорный случай). Тогда при сравнении выполнялось flag[0]==1 и flag[1]==1, но тогда либо Num==0 либо Num==1. Следовательно, одно из условий было истинным и выхода из цикла произойти не могло.

2. При выполнении в последний раз сравнения в /*1.3*/ и /*2.3*/ сравнение в /*1.3*/ выполнялось раньше. Тогда при этом выполнялось хотя бы одно из двух условий:

2.a. Num==0. Тогда до выхода из критической секции в первом процессе значение Num не могло смениться на 1, при этом, flag[0]==1. Следовательно во втором цикле выхода из цикла /*2.3*/ в течение этого времени произойти не могло.

2.б. flag[1]==0. Тогда операторы /*2.1*/ и /*2.2*/ должны были выполниться после сравнения в /*1.3*/. Т.о., при сравнении в /*2.3*/ должно выполняться Num==0 и flag[0]==1. Следовательно, во втором цикле выхода из цикла /*2.3*/ в течение этого времени произойти не могло.

3. При выполнении в последний раз сравнения в /*1.3*/ и /*2.3*/ сравнение в /*2.3*/ выполнялось раньше. Случай аналогичен случаю 2.

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

Осталось доказать, что для данного алгоритма невозможна взаимоблокировка, но это очевидно, т.к. условия циклов /*1.3*/ и /*2.3*/ не могут выполняться одновременно и измениться в самих циклах эти условия тоже не могут.

Аппаратная реализация. Отключение прерываний

Для случая однопроцессорной ЭВМ достаточно запретить прерывания при выполнении критической секции, что гарантирует, что в процессе ее выполнения перехода к другому процессу не произойдет.

Недостатки очевидны: подход неприменим для многопроцессорного случая. Кроме того, при зависании или зацикливании процесса в критической секции зависает вся система.

Аппаратная реализация. Использование машинных команд

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

Например, пусть в системе есть атомарная команда изменения значения переменной вместе со сравнением ее с нулем:

int TestInc(int *v)

{

if(*v==0){*v=1; return 1;}

else return 0;

}

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

int num=0;//глобальная переменная

//…

{

while(TestInc(&num)==0);//ждем освобождения ресурса

//критическая секция

num=0; //освобождаем ресурс

}

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

Семафоры

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

Семафор следует рассматривать как объект, содержащий целую переменную Count и очередь процессов ProcQueue. Над семафором можно совершать только три атомарных операции:

1. Инициализация переменной семафора Count неотрицательным числом.

2. Если значение Count меньше или равно 0, то блокировка текущего процесса и помещение его в очередь процессов ProcQueue Уменьшение переменной семафора Count на 1;.

3. Увеличение переменной семафора Count на 1; если значение Count становится меньше или равно 0, то из очереди процессов ProcQueue извлекается и разблокируется очередной процесс.

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

int sem_init(sem_t *sem, int pshared, unsigned int Count);

int sem_wait(sem_t * sem);

int sem_trywait(sem_t * sem);

int sem_post(sem_t * sem);

int sem_getvalue(sem_t * sem, int * sval);

int sem_destroy(sem_t * sem);

Функции описаны в файле semaphore.h.

Идентификатором семафора является объект типа sem_t.

Инициализируется семафор функцией sem_init. В ней задаются:

· семафор, который следует инициализировать (указатель на sem_t),

· целая переменная pshared указывает на то, что семафор используется в различных процессах (pshared=1) или внутри одного процесса в различных нитях (pshared=0),

· целая переменная Count задает начальное значение семафора

Функция sem_wait проверяет значение семафора. Если значение семафора меньше или равно 0, то процесс (нить) блокируется. Далее функция уменьшает на 1 значение семафора.

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

Дополнительные функции это:

int sem_trywait(sem_t * sem);

Если Count==0, то возвращает !0, иначе уменьшает Count на 1 и возвращает 0.

int sem_getvalue(sem_t * sem, int * sval);

Возвращает значение семафора.

int sem_destroy(sem_t * sem);

Очищает память из-под структуры данных, созданной sem_init.

Легко увидеть, что механизм взаимных исключений элементарно реализовать с помощью семафоров:

sem_t sem;

main()

{//инициализация семафора:

sem_init(&sem,0,1);

//…

}

//функция начала критической секции:

void CriticalBegin()

{

sem_wait(&sem);

}

//функция конца критической секции:

void CriticalEnd()

{

sem_post(&sem);

}

Задача о производителях и потребителях

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

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

Пусть производитель производит целые числа, а склад реализован в виде очереди на основе бесконечного массива целых чисел m. Переменная in указывает на номер ячейки в массиве m, куда производитель должен класть очередное число. После помещения числа в массив in должна увеличиваться на 1. Переменная out указывает на номер ячейки в массиве m, откуда потребитель должен забирать очередное число. После извлечения числа из массива out должна увеличиваться на 1.

m₀

m₁

m₂

m₃

m₄

…

out in

Выделены элементы массива, лежащие на складе.

Попробуем написать программу, реализующую описанную ситуацию. Чтобы не связываться с массивом=складом и переменными in/out введем целую переменную n=in-out, которая будет указывать на количество товара на складе. Будем использовать следующие рабочие функции:

Produce(); //произвести единицу товара

Append(); //занести единицу произведенного товара на склад

Take(); //взять единицу произведенного товара со склада

Consume(); //использовать товар по назначению

Неудачная попытка.

Будем использовать два семафора: один - отвечающий за блокировку при обращении к складу (prod), другой - позволяющий потребителю спать, пока на складе ничего нет (cons).

Инициализация семафоров:

sem_t prod,cons; int n=0;

main()

{

sem_init(&prod,0,1);//изначально склад готов к обслуживанию товара

sem_init(&cons,0,0);//изначально потребителю нечего потреблять

//…
}

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

void P0()

{

while(1)//вечно производить

{

Produce(); //произвести единицу товара

sem_wait(&prod);//начало критической секции

Append(); //занести единицу произведенного товара на склад

n++;

if(n==1)//при поступлении первого товара разблокировать потребителя

sem_post(&cons);

sem_post(&prod); //конец критической секции

}

функция, отвечающая за потребление в процессе-потребителе может иметь следующий вид:

void P1()

{

sem_wait(&cons);//ждать первого товара на складе

while(1)//вечно потреблять

{

sem_wait(&prod);//начало критической секции

Take(); //изъять единицу произведенного товара со склада

n--;

sem_post(&prod); //конец критической секции

Consume(); //употребить единицу товара

if(n==0)//при отсутствии товара на складе заблокировать потребление

sem_wait(&cons);

}

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

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

· произвели товар ( Þ n==1 ; значение cons == 1 )

· изъяли товар со склада и потребляем его в функции Consume(); ( Þ n==0 )

· снова произвели товар ( Þ n==1 ; значение cons == 2)

· проверили в P1 условие if(n==0); оно оказалось ложью, поэтому значение cons не изменилось

· потребили товар ( Þ n==0 ; значение cons == 2)

· проверили в P1 условие if(n==0); оно оказалось истиной, поэтому значение cons уменьшилось ( Þ n==0 ; значение cons == 1), но блокировка для cons не наступила, т.к. cons > 0

· пытаемся снова потребить товар, но склад пуст. Неприятности.

Правильное решение.

Проблема в предыдущем примере заключалась в том, что у нас нарушился баланс между инкрементациями и декрементациями семафора. Мы инкрементировали семафор каждый раз, когда выполнялось n==1 и должны были декрементировать его каждый раз, когда выполнялось n==0, но последнее требование мы не выполнили.

Чтобы не пропустить случай n==0 , мы можем ввести временную переменную n1 и присвоить ей значение n внутри критической секции. Теперь нулевое значение n не пропадет, т.к. сравнение if(n==0) мы заменим на сравнение if(n1==0).

Итого, правильный вариант функции, отвечающей за потребление:

void P1()

{int n1;

sem_wait(&cons);//ждать первого товара на складе

while(1)//вечно потреблять

{

sem_wait(&prod);//начало критической секции

Take(); //изъять единицу произведенного товара со склада

n--; n1=n;

sem_post(&prod); //конец критической секции

Consume(); //употребить единицу товара

if(n1==0)//при отсутствии товара на складе заблокировать потребление

sem_wait(&cons);

}

Более короткое решение.

На самом деле, переменная n является лишней, т.к. семафор cons сам является счетчиком. Поэтому функции могут иметь следующий вид:

void P0()

{

while(1)//вечно производить

{

Produce(); //произвести единицу товара

sem_wait(&prod);//начало критической секции

Append(); //занести единицу произведенного товара на склад

sem_post(&prod); //конец критической секции

sem_post(&cons);//добавить 1 к семафору потребителя

}

void P1()

{

while(1)//вечно потреблять

{

sem_wait(&cons);//ждать товара на складе

sem_wait(&prod);//начало критической секции

Take(); //изъять единицу произведенного товара со склада

sem_post(&prod); //конец критической секции

Consume(); //употребить единицу товара

}

Отметим, перестановка sem_post(&prod); и sem_post(&cons); в P0 ничего не изменит, т.к.для изъятия товара надо разблокировать оба семафора. А вот перестановка sem_wait(&cons); и sem_wait(&prod); в P1 приведет к неприятным последствиям. В этом случае, если потребитель войдет в критическую секцию при пустом складе, то производитель уже никогда не сможет воспользоваться складом. Возникнет взаимоблокировка.