Деревянко А.С., Солощук М.Н. Операционные системы.Часть I. Построение и функционирование операционных систем

Подождите немного. Документ загружается.

261

Ограничимся здесь только общими замечаниями к этому алгоритму.

Процессы нумеруются от 0 до N-1. Мы вводим два массива для

переменных состояния, размеры массивов на 1 больше числа процессов.

Последние элементы каждого из массивов соответствуют

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

"другой" процесс. Понятие "конкурент" здесь заменяется понятием

"претендент" (clainmant). Процесс становится претендентом, входя в

функцию csBegin (строка 6). В отличие от "желания" "претензия" процесса

не снимается до тех пор, пока она не будет удовлетворена (строка 18).

Если преимущественное право на вход в критическую секцию

принадлежит другому процессу, но этот другой процесс не является

претендентом, то наш процесс забирает это право себе (строки 7 - 11). При

выполнении этих действий наш процесс, однако, отказывается от своего

"желания", давая тем самым возможность участвовать в состязании за

захват секции другим процессам (строка 9). Получив право, процесс

заявляет о своем "желании" (строка 12). В последующем цикле for

проверяются "желания" других процессов (строки 13 - 14). Если есть

другие "желающие", то повторяется получение права и т.д. (строки 7 - 15).

Если же в цикле for другие желающие не выявлены (строка 15), наш

процесс входит в критическую секцию. При выходе из секции процесс

сбрасывает свои "претензию" и "желание" (строка 18) и передает право

несуществующему N-му процессу (строка 19).

АЛГОРИТМ ПИТЕРСОНА

Более компактная и изящная модификация алгоритма Деккера

известна как алгоритм Питерсона. Вот его вариант для двух процессов:

262

static int right;

static char wish[2] = { 0,0 };

void csBegin ( int proc ) {

int competitor;

if ( proc == 0 ) competitor = 1;

else competitor = 0;

wish[proc] = 1;

right = competitor;

while ( wish[competitor] && ( right ==

competitor );

}

void csEnd ( int proc ) {

wish[proc] = 0;

}

При входе в критическую секцию процесс заявляет о своем

"желании" (строка 7) и отказывается от своего преимущественного права

(строка 8). Процесс будет ожидать, если его конкурент заявил свое

"желание" и имеет преимущественное право (строка 9). Если нет интереса

конкурента или если независимо от интереса конкурента наш процесс

имеет преимущественное право, то наш процесс входит в критическую

секцию. Если наш процесс отказался от своего права в строке 8, то как же

это право может к нему вернуться? Право нашего процесса может быть

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

csBegin своего кода и выполнит строку 8. При выходе из критической

секции процесс просто снимает свой интерес и тогда его конкурент,

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

строки 9 по первой части условия.

263

Общие положительные свойства алгоритмов, основывающихся на

неальтернативных переключателях (Деккера и Питерсона), следующие:

• они корректны как для одно-, так и для многопроцессорных систем;

• они либеральны, так как позволяют более быстрым процессам входить

в свои критические секции чаще, чем медленным;

• они не ограничивают количество обслуживаемых ими процессов;

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

критической секции.

Но существуют и сложности:

• решения не просты для понимания и ошибиться в их реализации очень

легко;

• процессы используют занятое ожидание при входе в критическую

секцию.

8.4. Команда testAndSet и блокировки

Взаимное исключение при помощи переменных-переключателей

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

это делает решение универсальным как для одно-, так и для

многопроцессорных систем. Но большинство архитектур компьютеров

имеет в составе своей системы команд специальные команды с

расширенной атомарностью обращений к памяти, при помощи которых

можно реализовать взаимное исключение и быстрее, и проще. Общее

название таких команд: testAndSet – проверить и установить. Действия

такой команды могут быть описаны функцией:

int atomic testAndSet ( char *lock ) {

char var;

264

var = *lock;

*lock = 1;

return var;

}

(Здесь и далее мы, следуя правилам языка С, в котором параметры

передаются по значению, вынуждены передавать в функции указатели,

чтобы функции могли изменять значения параметров).

Команда проверяет (возвращает) значение некоторой переменной, а

затем устанавливает ее значение в 1. Введенный нами описатель функции

atomic показывает, что функция непрерываемая, во время ее выполнения

никакой другой процесс не имеет доступа к той памяти, с которой работает

функция (к переменной lock). Функция, как мы видим, выполняет два

обращения к переменной lock, но оба они выполняются как одна

транзакция.

Возможно, первые включения команд типа testAndSet в системы

команд диктовались иными соображениями, но сейчас возможность

выполнения подобных команд является обязательной для процессоров,

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

комплексах. В микропроцессорах Intel-Pentium, например, имеются

следующие команды, которые представляют собой "вариации на тему"

testAndSet:

• XCHG – перестановка;

• BTS – проверка и установка бита;

• BTR – проверка и сброс бита;

• BTC – проверка бита и установка противоположного значения;

• CMPXCHG – сравнить и заменить;

• XADD – заменить и сложить.

265

Так, для реализации "канонической" функции testAndSet при

помощи команды XCHG нужны две команды:

MOV al,1

XCHG AL,LOCK

Переменная lock устанавливается в 1, а ее прежнее значение

сохраняется в регистре AL.

Непрерываемость операций с памятью при использовании этих

команд в многопроцессорных системах обеспечивается сигналом LOCK#,

появляющимся на выходе микропроцессора. Причем команда XCHG, когда

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

LOCK# автоматически. Для других названных команд активизация этого

сигнала может явным образом задаваться программистом – при помощи

префикса LOCK.

Наличие в арсенале программиста команды testAndSet позволяет

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

помощи переменной-замка:

void csBegin ( char *lock ) {

while ( testAndSet( lock ) );

}

void csEnd ( char *lock ) {

*lock = 0;

}

Команда testAndSet (строка 2) будет возвращать 1 до тех пор,

пока другой процесс находится в критической секции, защищенной

замком. Как только этот другой процесс выйдет из критической секции и

установит замок в 0 (строка 5), наш процесс тут же вновь установит его в 1

266

и выйдет из цикла. Вследствие атомарности testAndSet никакой другой

процесс не сможет изменить состояние замка между теми моментами,

когда наш процесс считает его нулевое значение и установит его значение

в 1.

Каждый ресурс , к которому происходит совместный доступ (например,

каждая разделяемая переменная), может быть защищен своим замком.

Это обеспечит запрет только конфликтующих критических секций,

позволяя разным процессам одновременно использовать разные

разделяемые ресурсы.

При наличии двух и более групп ресурсов, со своим замком каждая,

возможны тупики. Как мы помним из главы 5, наиболее либеральной

политикой их предотвращения, не требующей априорной информации,

является иерархическая – ее рекомендуется применять и в данном случае.

Замки, обеспечиваемые командой testAndSet, обладают,

следовательно, такими свойствами:

• они применимы для любого числа процессов и любого числа

процессоров;

• они просты для понимания и для верификации;

• они либеральны, так как не запрещают другим процессам

выполняться и даже одновременно входить в неконфликтующие

критические секции;

• они допускают бесконечное откладывание, так как выбор

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

мы ничего не знаем о его критериях арбитража;

• они используют занятое ожидание.

8.5. Семафоры

267

Все рассмотренные выше методы используют занятое ожидание: если

процесс не может войти в критическую секцию, он зацикливается на

опросе переменных состояния. Следующие методы используют

блокировку ожидающего процесса – перевод его из списка процессов,

планируемых на выполнение (готовых) в список ожидающих

(заблокированных). Этим экономится процессорное время, в противном

случае попусту растрачиваемое в занятом ожидании, а затраты сводятся

к переключению процессов.

Такая возможность обеспечивается:

• введением специальных целочисленных общих переменных,

которые называются семафорами;

• добавлением к набору элементарных действий, из которых

строятся процессы, операций над семафорами: V-операции и P-

операции.

V-операция есть операция с одним операндом, который должен быть

семафором. Выполнение операции состоит в увеличении значения

аргумента на 1, это действие должно быть атомарным.

P-операция есть операция с одним операндом, который должен быть

семафором. Выполнение операции состоит в уменьшении значения

аргумента на 1, если только это действие не приведет к отрицательному

значению операнда. Выполнение P-операции, т.е. принятие решения о том,

что момент является подходящим для уменьшения аргумента, и

последующее его уменьшение должно быть атомарным.

Атомарность P-операции и является потенциальной задержкой: если

процесс пытается выполнить P-операцию над семафором, значение

которого в данный момент нулевое, данная P-операция не может

завершиться пока другой процесс не выполнит V-операцию над этим

семафором. Несколько процессов могут начать одновременно P-операцию

268

над одним и тем же семафором. Тогда при установке семафора в 1 только

одна из P-операций завершится, какая именно – мы обсудим позже.

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

Каждый ресурс защищается своим семафором, значение которого может

быть 1 – свободен или 0 – занят. Процесс, выполняющий доступ к ресурсу,

инициирует P-операцию (эквивалент csBegin). Если ресурс занят –

процесс задерживается в своей P-операции до освобождения ресурса.

Когда ресурс освобождается, P-операция процесса завершается и процесс

занимает ресурс. При освобождении ресурса процесс выполняет V-

операцию (эквивалент csEnd).

Э.Дейкстра [11], вводя семафорные примитивы для синхронизации и

взаимного исключения, исходил из гипотезы о том, что P- и V-операции

реализованы в нашей вычислительной системе аппаратно. На самом же

деле, в составе любого набора команд таких операций нет – и это

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

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

делать на аппаратном уровне.

В соответствии с общей методикой нашего подхода,

сосредотачивающей внимание на механизмах реализации взаимного

исключения, рассмотрим реализацию семафоров и операций над ними.

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

typedef struct {

int value;

char mutEx;

process *waitList;

} semaphore;

269

Здесь value – та самая целочисленная переменная, которая

представляет значение семафора в приведенном выше определении.

mutEx – переменная взаимного исключения, которая обеспечивает, как мы

увидим ниже, атомарность операций над семафорами. waitList –

указатель на список процессов, ожидающих установления этого семафора

в 1. (Здесь мы предполагаем линейный однонаправленный список, но

очередь ожидающих процессов может быть представлена и любым другим

образом.)

Мы начинаем рассмотрение с так называемых двоичных семафоров,

для которых допустимые значения – 0 и 1. Если семафор защищает

критическую секцию, то начальное значение поля value – 1. Начальные

значения других полей: mutEx = 0; waitList = NULL.

Операции над семафорами можно представить в виде следующих

функций:

void P ( semaphore *s ) {

csBegin (&s->mutEx);

if (!s->value) block(s);

else {

s->value--;

csEnd (&s->mutEx);

}

void V ( semaphore *s ) {

csBegin (&s->mutEx);

if(s->waitList!= NULL) unBlock(s);

else s->value++;

csEnd (&s->mutEx);

}

270

В нашей реализации вы видите "скобки критической секции" как

элементарные операции. Они обеспечивают атомарность выполнения

семафоров и могут быть реализованы любым из описанных выше

корректных способов. Здесь мы ориентируемся на команду testAndSet с

использованием поля семафора mutEx в качестве замка, но это может

быть и любая другая корректная реализация (в многопроцессорных

версиях Unix, например, используется алгоритм Деккера). Вопрос: в чем

же мы выигрываем, если в csBegin все равно используется занятое

ожидание? Дело в том, что это занятое ожидание не может быть долгим.

Этими "скобками критической секции" защищается не сам ресурс, а только

связанный с ним семафор. Выполнение же семафорных операций

происходит быстро, следовательно, и потери на занятое ожидание будут

минимальными.

Если при выполнении P-операции оказывается, что значение

семафора нулевое, выдается системный вызов block, который блокирует

активный процесс – переводит его в список ожидающих, в тот самый

список, который связан с данным семафором. Важно, что процесс

прервется именно в контексте строки 3 своей P-операции и впоследствии

он возобновится в том же контексте. Поскольку заблокированный таким

образом процесс не успеет закончить критическую секцию, это должен

сделать за него системный вызов block, чтобы другие процессы получили

доступ к семафору.

Когда процесс выполняет V-операцию (освобождает ресурс),

проверяется очередь ожидающих процессов и разблокируется один из них.

В системном вызове unBlock можно реализовать любую дисциплину

обслуживания очереди, в том числе и такую, которая предупреждает

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