КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Критическая секция
Из-за чего произошла путаница в предыдущем примере? Очевидно, что из-за того, что процесс прервали тогда, когда он еще не закончил работу с разделяемым ресурсом. Что же делать? Первый ответ – не прерывать процесс во время работы с разделяемым ресурсом. Действительно, проблема, описанная выше, в таком случае не возникнет, но могут возникнуть другие (ведь мы не случайно только что решили, что более защищенной является система с вытесняющей многозадачностью!). Введем понятие синхронизации процессов - "критическая секция" программы. Критическая секция - это часть программы, в которой осуществляется доступ к некоторым разделяемым данным. Чтобы исключить эффект гонок по отношению к некоторому ресурсу, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этим ресурсом, находился максимум один процесс. Этот прием называют взаимным исключением. Таким образом, в заданный момент времени с каждым ресурсом связывается критическая секция не более чем одного процесса (то есть одного или ни одного). Получается, что количество критических секций зависит от количества работающих процессов и от количества ресурсов. Как уже было сказано выше, простейший способ обеспечить взаимное исключение - позволить процессу, находящемуся в критической секции, запрещать все прерывания. Однако этот способ непригоден, так как опасно доверять управление системой пользовательскому процессу; он может надолго занять процессор, а при крахе процесса в критической области крах потерпит вся система, потому что прерывания никогда не будут разрешены. Другим способом является использование блокирующих переменных. С каждым разделяемым ресурсом связывается двоичная переменная, которая принимает значение 1, если ресурс свободен (то есть ни один процесс не находится в данный момент в критической секции, связанной с данным процессом), и значение 0, если ресурс занят. На рисунке 3 показан фрагмент алгоритма процесса, использующего для реализации взаимного исключения доступа к некоторому разделяемому ресурсу блокирующую переменную РЕСУРС_1. Перед входом в критическую секцию процесс проверяет, свободен ли ресурс РЕСУРС_1. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной РЕСУРС_1 устанавливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом, значение переменной РЕСУРС_1 снова устанавливается равным 1.
Рисунок 3 - Реализация критических секций с использованием блокирующих переменных Заметим, что блокирующие переменные должны быть внешними по отношению к процессам (глобальными), следовательно, это могут быть некоторые общие данные (например, общий файл на диске). С обычными ресурсами - устройствами операционная система сама может связать некоторые переменные, доступные всем процессам. Обычно подобные переменные называются «переменные окружения».
Если все процессы написаны с использованием вышеописанных соглашений, то взаимное исключение гарантируется. Следует заметить, что здесь операция проверки и установки блокирующей переменной должна быть неделимой. Поясним это. Пусть в результате проверки переменной процесс определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 0, был прерван. За время его приостановки другой процесс занял ресурс, вошел в свою критическую секцию, но также был прерван, не завершив работы с разделяемым ресурсом. Когда управление было возвращено первому процессу, он, считая ресурс свободным, установил признак занятости и начал выполнять свою критическую секцию. Таким образом, был нарушен принцип взаимного исключения, что потенциально может привести к нежелательным последствиям. Во избежание таких ситуаций в системе команд машины желательно иметь единую команду "проверка-занятие", или же реализовывать системными средствами соответствующие программные примитивы (системные вызовы, системные функции), которые бы запрещали прерывания на протяжении всей операции проверки и установки. Реализация критических секций с использованием блокирующих переменных имеет существенный недостаток: в течение времени, когда один процесс находится в критической секции, другой процесс, которому требуется тот же ресурс, будет выполнять рутинные действия по опросу блокирующей переменной, бесполезно тратя процессорное время, так как, очевидно, что в это время ресурс не может освободиться! Нерациональное использование процессора может происходить в течение одного или нескольких квантов времени. Заметим, что бывают ситуации, при которых ресурс, не занимаемый работающим в данный момент процессом, освобождается. Придумайте такую ситуацию. Для устранения таких нежелательных потерь может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по-своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор некоторого события. На рисунке 4 показан фрагмент алгоритма процесса, использующего эти функции. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие, заключающееся в освобождении ресурса d. Функция WAIT(D) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс d, после выхода из критической секции вызывает системную функцию POST(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние ГОТОВНОСТЬ.
Рассмотрим пример. Пусть два процесса пишут поочередно сообщения в «почтовый ящик». Ящик считаем безразмерным. Сообщение может быть и длинным и коротким, очевидно, что два сообщения нельзя перемешивать. Заводим блокирующую переменную «МОЖНОПИСАТЬ», сигнализирующую о том, можно ли писать в настоящий момент в «почтовый ящик» (1 – можно писать, 0 – ящик занят). Процессы вводят сообщения от пользователя. Признаком конца сообщения является нажатие клавиши ENTER. Почтовым ящиком сделаем файл Р. Признаком конца всех сообщений F10. Описание процессов А и В приведены ниже (они одинаковы!)
Рисунок 4 - Реализация критической секции с использованием системных функций WAIT(D) и POST(D) Обобщающее средство синхронизации процессов предложил Дейкстра, который ввел два новых примитива. В абстрактной форме эти примитивы, обозначаемые P и V, оперируют над целыми неотрицательными переменными, называемыми семафорами. Пусть S такой семафор. Операции определяются следующим образом:
V(S): переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции. P(S): уменьшение S на 1, если это возможно. Если S=0, то невозможно уменьшить S и остаться в области целых неотрицательных значений, в этом случае процесс, вызывающий P-операцию, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также является неделимой операцией. В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную. Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания, в то время как V-операция может при некоторых обстоятельствах активизировать другой процесс, приостановленный операцией P (сравните эти операции с системными функциями WAIT и POST). Применение семафоров необходимо тогда, когда требуется определить степень занятости некоторого ресурса, а не просто получить ответ на вопрос «занят ресурс или свободен». Рассмотрим использование семафоров на классическом примере взаимодействия двух процессов, выполняющихся в режиме мультипрограммирования, один из которых пишет данные в буферный пул (список) в конец, а другой считывает их из буферного пула с первой записи списка и удаляет. Пусть буферный пул состоит из N записей. Процесс "писатель" должен приостанавливаться, когда все записи буфера оказываются занятыми, и активизироваться при освобождении хотя бы одной записи. Напротив, процесс "читатель" приостанавливается, когда все записи пусты, и активизируется при появлении хотя бы одной записи. Введем два семафора: e - число пустых буферов и f - число заполненных буферов. Предположим, что запись в буфер и считывание из буфера являются критическими секциями (как в примере с принт-сервером в начале данного раздела). Введем также двоичный семафор b, используемый для обеспечения взаимного исключения. Тогда процессы могут быть описаны следующим образом:
#define N 256 /* Глобальные переменные int e = N, f = 0, b = 1;
void Writer (){ while(1){ PrepareNextRecord(); /* подготовка новой записи */ P(e); /* Уменьшить число свободных буферов, если они есть */ /* в противном случае - ждать, пока они освободятся */ P(b); /* Вход в критическую секцию */ AddToBuffer(); /* Добавить новую запись в буфер */ V(b); /* Выход из критической секции */ V(f); /* Увеличить число занятых буферов */ } }
void Reader (){ while(1){ P(f); /* Уменьшить число занятых буферов, если они есть */ /* в противном случае ждать, пока они появятся */ P(b); /* Вход в критическую секцию */ GetFromBuffer(); /* Взять запись из буфера */ V(b); /* Выход из критической секции */ V(e); /* Увеличить число свободных буферов */ ProcessRecord(); /* Обработать запись */ } } Важно, что введение понятия семафоров иногда позволяют вообще избавиться от критической секции, если дополнительно обеспечить, чтобы всегда работа шла с разными «частями» разделяемого ресурса. В приведенном примере этого можно было бы добиться, если потребовать, чтобы в буфере всегда была, по крайней мере, одна запись. Правда, такое требование может привести к тому, что последняя запись вообще останется не обработанной. Итак, оба процесса могут работать с разделяемым ресурсом одновременно! Не забывайте про относительность одновременности в многопроцессной ОС. Рассмотрим еще пример. Пусть Вам надо запрограммировать следующую задачу: пусть процесс ВВОД вводит с клавиатуры очередное слово на русском языке, конец слова определяется по символу ENTER. Признаком завершения ввода является ввод подряд двух ENTER. Это слово заносится в некоторый буфер, например, текстовый файл. Процесс ПЕРЕВОД выбирает по одному слова из файла, переводит их на английский язык и показывает на экране пользователя. Запись в файл сделаем ограниченной, то есть разрешим записывать не более чем N слов. Тогда процесс писатель должен приостановиться, если файл уже заполнен. Процесс перевод, выбирающий слова из файла, наоборот, должен приостановиться, если слов в файле не осталось. Таким образом, нам потребуется два семафора: «КВОСЛОВ» (количество слов) и «КВОСВМЕСТА» (количество свободного места).
Дата добавления: 2014-12-07; Просмотров: 490; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |