гуд работа. Курс лекций теория вычислительных процессов
 Скачать 1.54 Mb.
|
|
Синхронизация нижнего уровня. Большинство важнейших элементарных приемов, применяемых для синхронизации процессов, тесно связанны с аппаратурой: блокировка памяти, операции «проверка» и «установка», семафоры. Для реа- лизации взаимного исключения достаточно выбрать любой из этих приемов. Блокировка памяти Взаимное исключение реализуют аппаратно, сделав операции над памятью неделимыми. То есть, если каждый из двух процессов пытаются поместить какие-то значения в одну и туже ячейку, то спор разре- шается на аппаратном уровне : − одному процессу разрешается выполнить операцию засылки немедленно; − другому процессу приходится ждать, пока первый не закончит. Такое разрешение спора называется блокировкой памяти и дает возможность реализации взаимного ис- ключения двух и более процессов. Рассмотрим простейший случай разделяемого объекта: флаговую переменную, которая может прини- мать значения True и False. Такая переменная, в частности, может использоваться для реализации вза- имного исключения в секции, работающей с более сложной структурой данных. Если в критической секции не находится ни одной нити, переменная равна False, иначе — True. При входе в секцию нам необходимо проверить значение переменной и, если блокируемый участок свобо- ден, присвоить ей True. Данный пример любопытен не только своей простотой, но и тем, что совмещает в себе оба типа критических секций: изменение разделяемых данных и анализ данных, которые могут параллельно модифицироваться кем-то еще. Наивный способ работы с такой переменной приведен в примере 7.1 (пример реализован на паскалепо- добном псевдокоде. Операторы parbegin/parend символизируют параллельное исполнение заключенных между ними операторов). Казалось бы, трудно представить себе более простую программу, однако именно благодаря простоте легко понять, что она никуда не годится: проверка флага и его установка реализуются двумя различными операторами, в промежутке между которыми другой процесс может получить управление и также установить флаговую переменную! Окно, в котором происходит соревнование, составляет всего две-три команды, но при попадании обоих процессов в это окно мы получаем как раз то, чего стремились избежать: оба процесса могут войти в критическую секцию одновременно. Пример 7.1. Наивная реализация взаимного исключения на основе флаговой переменной 36 program флаг; var flag: Boolean; procedure процессодин; begin while True do begin while flag do; flag := True; критическаясекция!; flag := False; end end; procedure процессдва; begin while True do begin while flag do; flag := True; критическаясекция2; flag := False; end end; oegin flag:= False; parbegin процессодин; процессдва; parend еnd. Примитивы взаимоисключения В классической работе Г. М. Дейтела [Дейтел 1987] предлагается несколько последовательных усовер- шенствований механизма взаимоисключений, основанного на флаговых переменных, и как завершаю- щий этап этого анализа приводится алгоритм взаимоисключений Деккера (пример 7.2). Пример 7.2. Алгоритм Деккера (цит. по [Дейтел 1987]) program АлгоритмДеккера; var избранныйпроцесс: (первый, второй); п!хочетвойти, п2хочетвойти: Boolean; procedure процессодин; begin while true do begin п1хочетвойти := True; while п2хочетвойти do if избранныйпроцесс=второй then begin п1хочетвойти := False; while избранныйпроцесс=второй do; п!хочетвойти := True; end критическийучасток1; избранныйпроцесс := второй; п!хочетвойти := False; end end 37 procedure процессдва; begin while true do begin п2хочетвойти := True; while п1хочетвойти do if избранныйпроцесс=первый then begin п2хочетвойти := False; while избранныйпроцесс=первый do; п2хочетвойти := True; end критическийучасток2 ; избранныйпроцесс := первый; п2хочетвойти := False; end end D begin п1хочетвойти := False; п2хочетвойти := False; избранныйпроцесс := первый; parbegin процессодин; процессдва; parend end. Недостатки этого решения очевидны. Первый из них — для доступа к одной и той же критической сек- ции из третьей нити мы должны значительно сложнить код обеих нитей. Нa практике, для решения проблемы работы с флаговыми и другими ска-ярными переменными в мно- гопроцессорных конфигурациях большинство овременных процессоров предоставляют аппаратные примитивы взаимоисключения: средства, позволяющие процессору монопольно захватить шину : вы- полнить несколько операций над памятью. Реализации этих примитивов различны у разных процессо- ров. Например, у х86 это специальный код операции, префикс захвата шины, который сам по себе не совершает никаких действий, но зато исполняет следующую за ним операцию в монопольном режиме. Существует прием синхронизации, позволяющий организовать процесс ожидания, не прибегая к актив- ному ожиданию. Семафоры. В 1968 г. Э. Дейкстра предложил удобную форму механизма захвата/освобождения ресурсов, ко- торую он назвал операциями P и V над считающими семафорами. Считающим семафором называют целочисленную переменную, выполняющую те же функции, что и байт блокировки. Однако в отличие от последнего она может принимать кроме "0" и "1" и другие целые положительные значения. Семафоры – это часть абстракции, поддерживающая очередь постоянно ожидающих процессов. Операции P и V над семафором S могут быть определены следующим образом. P(S): 1. Уменьшить значение S на 1, т. е. S : = S – 1. 2. Если S < 0, выполнить ОЖИДАНИЕ (S). V(S): 1. Увеличить значение S на 1, т. е. S : = S + 1. 2. Если S ≥ 0, выполнить ОПОВЕЩЕНИЕ (S). Операция ОЖИДАНИЕ (S) (WAIT) блокирует обслуживание процесса, делает соответствующую отметку об этом и связывает процесс со значением переменной S. Операция ОПОВЕЩЕНИЕ (S) (SIGNAL) просматривает связанный с переменной S список бло- кированных процессов. Если в списке есть процессы, ожидающие освобождения некоторого ресурса, управляемого (сигнализируемого) S, один из них переводится в состояние готовности, а в соответст- вующей ему записи делается отметка. С этого момента процесс становится опять доступным плани- ровщику. . Это действительно похоже на работу железнодорожного семафо. ра, контролирующего движение по- ездов по одноколейной ветке (рис. 7.6) Рис. 7.6. Железнодорожный семафор По определению, ожидание, связанное с операцией P(S), не является ожиданием "зависания", так как ожидающие процессы не используют центральный процессор. Так как несколько процессов могут ожидать операцию P(S) над отдельным семафором, во время приращения должен быть осуществлен выбор, какую контрольную точку процесса сделать доступной. Алгоритм выбора не определен, за исключением требования равнодоступности процессов, т. е. никакой процесс не может быть "забыт". Типичным примером использования алгоритма семафоров является задача производи- тель/потребитель. Задается максимальная емкость хранилища. Производитель не должен переполнять его, а потребитель не должен пытаться брать продукцию из пустого хранилища. Наиболее употребительные операции над семафорами: • создать семафор; • запросить состояние семафора; • изменить состояние семафора; • уничтожить семафор. Операции над семафорами в силу своей неделимости позволяют блокировать или активизиро- вать процессы при освобождении или запросах ресурсов любого типа (памяти, процессоров, устройств ввода-вывода и т. п.). Наиболее показательно аппарат семафоров можно применить на следующей задаче. Три курильщика сидят за столом. У одного есть табак, у другого – бумага, у третьего – спички. На столе могут появиться извне два из трех упомянутых предмета. Появившиеся предметы забирает тот курильщик, у которого будет полный набор предметов. Он сворачивает папиросу, раскуривает ее и ку- рит. Новые два предмета могут появиться на столе только после того, как он кончит курить. Другие ку- рильщики в это время не могут начать курение. Задание. Описать с помощью P и V – операций над семафорами – систему процессов, которая моделирует взаимодействия этих курильщиков. Указание. Выделить шесть процессов, три из которых соответствуют трем курильщикам X, Y, Z, а три других имеют следующее назначение: А – поставляет спички и бумагу, В – табак и спички, С – бумагу и табак. Требование. Процессы-поставщики не знают, какие предметы находятся у курильщиков. Проблема взаимоисключения включает в себя нахождение протокола, который может использо- ваться отдельными процессами в момент входа в критический раздел или выхода из него. Наиболее простым случаем семафора является двоичный семафор. Начальное значение флаговой пере- менной такого семафора равно 1, и вообще она может принимать только значения 1 и 0. Двоичный се- мафор соответствует случаю, когда с разделяемым ресурсом в каждый момент времени может работать только одна нить. Для 2-х процессов S принимает значения 1,0 или -1: − если S=1, это значит, что ни один из процессов не находится в своем критическом участке; 38 39 − если S=0, это значит, что один процесс находится в своем критическом участке; − если S=-1, это значит, что один процесс находится в своем критическом участке и один, – в очереди к семафору S, где он ждет разрешения войти в свой критический участок. Семафоры общего вида могут принимать любые неотрицательные значения. В современной литературе такие семафоры называют семафорами-счетчиками (counting semaphore). Это соответствует случаю, когда несколько нитей могут работать с объектом одновременно, или когда объект состоит из несколь- ких независимых, но равноценных частей — например, несколько одинаковых принтеров. При работе с такими семафорами часто разрешают процессам вычитать и добавлять к флаговой переменной значе- ния, большие единицы. Это соответствует захвату/освобождению нескольких частей ресурса. Многие системы предоставляют также сервисы, позволяющие просмотреть состояние семафора без его изменения и произвести "неблокируюшуюся" форму захвата, которая возвращает ошибку в ситуации, когда нормальный захват семафора привел бы к блокировке. Теоретики не очень любят такие примити- вы, но при разработке сложных сценариев взаимодействия с участием многих семафоров они бывают полезны. Во многих современных книгах и операционных системах семафорами называются только семафоры общего вида, двоичные же семафоры носят более краткое и выразительное имя мутекс (mutex — от MUTnal EXclusion, взаимное исключение). Проследить генезис этого названия автору не удалось, но можно с уверенностью сказать, что оно вошло в широкое употребление не ранее конца 80-х. Так, в раз- рабатывавшейся в середине 80-х годов OS/2 1.0, двоичные семафоры еще называются семафорами, а в Win32, разработка которой происходила в начале 90-х, уже появляется название mutex. Операции над мутексом называются захватом (acquire) (соответствует входу в критическую секцию) и освобождени- ем (release) (соответствует выходу из нее). Многие ОС предоставляют для синхронизации семафоры Дейкстры или похожие на них механизмы. Синхронизация верхнего уровня. Механизмы блокировки памяти и семафоры достаточно эффективны, но эти элементарные способы нижнего уровня приводят к сложным, весьма чувствительным конструкциям, а также к незначительным изменениям программы. Приемы верхнего уровня позволяют изящно решить проблемы общения процессов. Почтовый ящик – информационная структура, для которой задаются правила, описывающие ее работу. Она состоит из: − головного элемента (отделения), в котором находится описание данного почтового ящика; − нескольких гнезд, в которые помещаются сообщения. Размеры и количество гнезд, являющиеся параметрами почтового ящика, задаются при инсталляции ящика. Правила работы могут быть различными в зависимости от сложности почтового ящика: например, про- цесс Р1 может посылать сообщения до тез пор, пока имеются свободные гнезда, – если все гнезда за- полнены, то процесс Р1 либо ждет, либо занимается другими делами и пытается послать сообщения позже. Процесс Р2 может получать сообщения до тех пор, пока имеются заполненные гнезда. Если сообщений нет, то он может либо ждать, либо продолжать свою работу. Можно усложнить правила общения и ввести двустороннюю связь. Почтовое отделение Забирает сообщения и оставляет подтверждения получе- ния. 40 Еще более сложные правила при построении многовходовых отделений. Почтовое отделение Р1 Р3 Р2 Р4 Для достижения гибкости обслуживания в многовходовых отделениях функция управления выносится в специальные переключатели – порты, управляющие потоками запросов к ресурсам. Почтовое отделение Р1 Р2 Рn Порт Р2 Р1 Управление и правила игры Мониторы и серверы транзакций Захват участков файла теоретически позволяет реализовать любую требуемую структуру взаимоис- ключения для процессов, работающих с этим файлом. Однако, практически, при работе с файлом боль- шого количества нитей (например, многопользовательской системы управления базами данных), раз- личные нити часто оказываются вынуждены ждать друг друга, что приводит к резкому увеличению времени реакции системы. С этим явлением хорошо знакомы разработчики и пользователи файловых СУБД, таких, как FoxPro или dBase IV. В случае СУБД решение состоит в создании сервера БД, или сервера транзакций, который вместо при- митивов захвата участков файлов или таблиц предоставляет пользователям понятие транзакции. Если пользовательская сессия объявила начало транзакции, изменения, которые она вносит в таблицы, непосредственно в таблицах не отражаются, и другие сессии, которые обращаются к вовлеченным в транзакцию данным, получают их исходные значения. Завершив модификацию, пользовательская сес- сия объявляет завершение транзакции. Транзакция может завершиться как выполнением (commit), так и откатом (rollback). В случае отката измененные данные просто игнорируются. В случае же выполнения сервер вносит из- менения в таблицы, однако во время изменений он все равно предоставляет другим нитям данные в том состоянии, в котором они были до начала транзакции. Такой подход увеличивает потребности в опера- тивной и дисковой памяти (все данные, изменяемые в ходе транзакции, должны храниться минимум дважды: в измененном и в исходном видах), но обеспечивает резкое сокращение времени реакции и оп- ределенное упрощение кодирования: программист теперь не должен явно перечислять все данные, ко- 41 торые ему надо заблокировать в ходе транзакции. Кроме того, Двойное хранение данных позволяет вос- становить либо результат транзакции, либо состояние данных до ее начала, после сбоя системы. Современные серверы СУБД представляют собой сложные программные Комплексы, которые, кроме собственно "развязки" транзакций предоставляют сложные сервисы оптимизации запросов, индексации и кэширования Данных. Да и точное описание понятия транзакции в современных языках запросов к реляционным СУБД (SQL, RPG и др.) несколько сложнее при-Веденного выше. Однако детальное об- суждение этого вопроса увело бы нас Далеко в сторону от темы книги. Читателю, интересующемуся этой темой, Можно порекомендовать книги [Дейт 1999, Бобровски 1998]. Аналогичный серверам транзакций подход нередко используется и в более простых случаях межпро- цессного взаимодействия. С разделяемым ресурсом ассоциируется специальная нить, называемая мо- нитором ресурса. Остальны нити не могут обращаться к ресурсу напрямую и взаимодействуют только с монитором. Монитор может предоставлять нитям-клиентам непротиворечивые состояния контролируе- мого им ресурса (необязательно совпадающие с текущим состоянием ресурса) и устанавливать очеред- ность запросов на модификацию. Даже при довольно простой стратегии управления ресурсом, монитор полезен тем, что скрывает (ин- капсулирует) структуру и особенности реализации разделяемого ресурса от клиентских нитей. Типич- ный пример мониторного процесса — драйвер внешнего устройства в многозадачных ОС. Монитор – совокупность (набор) процедур и информационных структур, которым пользуются процес- сы в режиме разделения, причем в каждый момент времени им может пользоваться только один про- цесс. Например, имеем ресурс и его распределяет программа-планировщик. Каждый запрос на обслуживание попадает к планировщику. Программа-планировщик разделяет все процессы и поэтому на входе может одновременно появиться ряд процессов, но она обслуживает не бо- лее одного процесса. Монитор с помощью операций «ждать» и «сигнал» блокирует обратившийся процесс, если нужный ре- сурс занят, – команда «ждать».После выполнения условия «ресурс не занят» планировщик вырабатыва- ет «сигнал» и если есть процессы, ожидающие появления этого сигнала, то один из них пробуждается и получает разрешение продолжить свою работу. В мониторе ожидающих процессов может быть несколько. Простой порядок обслуживания очереди со- стоящий в том, что освобождается процесс, ожидающий дольше всех, гарантирует, что ни один из обра- тившихся процессов не будет задержан на неопределенное время. По сравнению с семафорами мониторы не представляют собой более мощного инструмента, у них есть определенные преимущества перед более примитивными синхронизирующими средствами. Во-первых, мониторы очень гибки. В них можно реализовать не только семафоры, но и многие другие синхронизирующие операции: − механизм почтовых ящиков легко запрограммировать в виде монитора; − мониторы дают процессам возможность совместного использования программы, представ- ляющей собой критический участок. Тупики. Хотя каждый процесс, выполняемый в мультипрограммном режиме, имеет доступ к общим ре- сурсам, существует некоторая область, которую в фиксированный момент времени может использовать лишь один процесс. Нарушение этого условия приведет к неизвестному порядку обработки процессов. Назовем такую область критической. При использовании критической области возникают различные проблемы, среди которых можно выделить проблемы состязания (гонок) и тупиков (клинчей). Условие состязания возникает, когда процессы настолько связаны между собой, что порядок их выполнения влияет на результат операции. Условие тупиков появляется, если два взаимосвязанных процесса блокируют друг друга при об- ращении к критической области. В системах, допускающих перераспределение любых ресурсов в произвольной последовательно- сти, но имеющей и неосвобожденные ресурсы, время от времени должны возникать тупиковые ситуа- ции. Пример. Пусть программе А нужен ресурс R1. Она запрашивает его и получает. Программе В нужен ресурс R2. Она запрашивает его и получает (рис. 5.6). Далее, пусть программа А, не отпуская R1, запрашивает R2, а программа В, не отпуская R2, запрашивает R1. Налицо типичный клинч, если только один из ресурсов R1 или R2 не может быть освобожден до момента завершения обработки соответст- вующего процесса. Рис. 5.6. Пример тупиковой ситуации Для разрешения подобных проблем наиболее часто используют простейшие приемы синхрони- зации процессов, тесно связанные с аппаратным оборудованием. Простейший прием – стандартные операции типа WAIT (ЖДАТЬ) и SIGNAL (ОПОВЕСТИТЬ). Операция WAIT позволяет: временно заблокировать процесс, а SIGNAL информирует систему о необ- ходимости разблокирования процесса, задержанного из-за невыполнения условия. Следует отметить такие приемы, как БЛОКИРОВКА ПАМЯТИ (для реализации взаимного исключения одному процессу разрешается выполнить операцию над памятью, а другому ждать, пока первый не завершит работу); ПРОВЕРКА и УСТАНОВКА (аппаратная операция, к которой обращаются с двумя параметрами: ЛО- КАЛЬНЫЙ И ОБЩИЙ). Эти приемы хотя и решают задачу взаимного исключения, однако неэффек- тивно используют процессорное время из-за необходимости пребывания в активном состоянии процес- са, ожидающего разрешения продолжить работу. Наиболее эффективным и простым средством синхро- низации процессов, исключающим состояние "активного" ожидания, является семафор. Существует 3 основных подхода разрешения тупиковых ситуаций: 1.предотвращение; 2.автоматическое обнаружение; 3.обнаружение при участии оператора. Схема предотвращения – систему нельзя допускать до опасного состояния, поэтому при создании про- цессом запроса, который может привести к тупику, система принимает меры для избежания опасного состояния: либо не удовлетворяет этот запрос, либо отбирает ресурс у другого процесса для исключе- ния возможности попадания в тупик. Преимущество данного метода в том, что он всегда предотвраща- ет тупиковые ситуации. Однако, ресурсы часто простаивают, т.к. запросы на имеющиеся в распоряже- нии системы ресурсы иногда отклоняются с целью предотвратить попадание в опасное состояние. Метод автоматического обнаружения тупиков допускает, что система попадает в тупиковые ситуации, а когда это действительно происходит, система обнаруживает тупик программным способом. Затем система может отобрать ресурсы у некоторых процессов, чтобы заставить другие процессы сдвинуться с места. В последнем примере с процессами Р1 и Р2 система допустила бы ситуацию тупика, но для выхода из ситуации отобрала печатающее устройство у процесса Р2 и отдала его процессу Р1. Процесс Р2 по-прежнему оставался бы заблокированным, но оба эти процесса не находились бы в тупике. Метод автоматического обнаружения позволяет добиться большей загруженности ресурсов, чем схема предот- вращения тупиковых ситуаций. Третий метод основан на следующей точке зрения: тупиковые ситуации возникают слишком редко, 42 |