Многопроцессорные системы (Операционные системы UNIX)

3.Устранить конкуренцию за использование структур данных путем соответствующей переделки алгоритмов.

 Главный и подчиненный процессы. Систему с двумя процессорами, один из которых - главный (master) - может работать в режиме ядра, а другой - подчиненный (slave) - только в режиме задачи,  впервые  реализовал на машинах типа VAX 11/780 Гобл. Главный процессор несет ответственность за обработку всех обращений к операционной системе и всех прерываний. Подчиненные процессоры ведают выполнением процессов в режиме задачи и информируют главный процессор о всех  производимых обращениях к системным функциям.   Выбор  процессора, на котором будет выполняться данный процесс, производится в соответствии с алгоритмом диспетчеризации. В соответствующей записи таблицы процессов появляется новое поле, в которое записывается идентификатор выбранного процессора; предположим для простоты,  что  он показывает,  является  ли  процессор  главным или подчиненным. Когда процесс производит обращение к системной функции, выполняясь на подчиненном процессоре, подчиненное ядро переустанавливает значение поля идентификации процессора  таким образом, чтобы оно указывало на главный процессор, и переключает контекст на другие процессы. Главное ядро запускает на выполнение процесс с наивысшим приоритетом среди тех  процессов,  которые  должны выполняться на главном процессоре. Когда выполнение системной функции завершается,  поле  идентификации процессора перенастраивается обратно, и процесс вновь возвращается на подчиненный процессор. Если процессы должны выполняться на главном процессоре, желательно, чтобы главный процессор обрабатывал их как можно скорее и не заставлял их ждать своей очереди чересчур долгоЕсли в тот момент,  когда  подчиненный  процессор делает запрос на исполнение системной функции, главный процесс выполняется в режиме  задачи, его выполнение будет продолжаться до следующего переключения контекста. Главный процессор реагировал бы гораздо быстрее, если  бы  подчиненный  процессор  устанавливал при этом глобальный флаг; проверяя установку

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

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

 выполнять пока (блокировка установлена)  /* операция проверки */

приостановиться (до снятия блокировки);

установить  блокировку;

механизм  снятия блокировки:

снять блокировку;

вывести из состояния приостановния все процессы,  приостановленные  в  результате блокировки;

Блокировки  такого  рода охватывают некоторые  критические участки, но не работают в многопроцессорных система.  Предположим,  что блокировка снята и что два процесса на разных процессорах одновременно пытаются проверить ее наличие и установить ее. В момент t они  обнаруживают  снятие  блокировки,  устанавливают  ее вновь, вступают в критический участок и создают опасность нарушения целостности структур  данных  ядра.  В условии  одновременности имеется отклонение: механизм не сработает, если перед тем, как процесс выполняет операцию проверки, ни один другой процесс  не выполнил операцию установления блокировки. Если, например, после обнаружения снятия  блокировки  процессор A обрабатывает прерывание и в этот момент процессор B выполняет проверку и устанавливает блокировку, по выходе из  прерывания процессор A так же установит блокировку. Чтобы предотвратить возникновение подобной ситуации, нужно сделать так, чтобы процедура блокирования была  неделимой: проверку наличия блокировки и ее установку следует объединить в одну операцию, чтобы в каждый момент времени с блокировкой имел дело только один процесс.

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

 Выделение  буфера: алгоритм работает с тремя структурами данных: заголовком буфера,  хеш-очередью буферов и списком свободных буферов. Ядро связывает семафор со всеми экземплярами каждой структуры. Другими словами, если у ядра имеются в распоряжении 200  буферов, заголовок каждого из них включает в себя семафор, используемый для захвата буфера; когда процесс выполняет над семафором операцию P, другие процессы, тоже пожелавшие захватить буфер, приостанавливаются  до  тех  пор, пока  первый  процесс  не  исполнит операцию V. У каждой хеш-очереди буферов также имеется семафор, блокирующий доступ к очереди. В однопроцессорной системе блокировка хеш-очереди не нужна, ибо процесс никогда не переходит в состояние приостанова, оставляя очередь в несогласованном (неупорядоченном) виде. В многопроцессорной системе, тем не менее, возможны ситуации, когда с одной и  той  же  хеш-очередью  работают два процесса; в каждый момент времени семафор открывает доступ свободных буферов нуждается в семафоре для защиты содержащейся в нем информации

от искажения. Первая часть алгоритма , реализованная в многопроцессорной  системе с использованием семафоров. Просматривая буферный кеш в поисках указанного блока, ядро с помощью операции P захватывает  семафор,  принадлежащий  хеш-очереди.  Если над семафором уже кем-то произведена операция данного типа, текущий процесс приостанавливается до тех  пор,  пока процесс,  захвативший  семафор, не освободит его, выполнив операцию V. Когда текущий процесс получает право исключительного контроля над хеш-очередью, он приступает к поиску подходящего буфера. Предположим, что буфер  находится  в хеш-очереди.  Ядро (процесс A) пытается захватить буфер, но если оно использует операцию P и если буфер уже захвачен, ядру придется приостановить свою работу,  оставив хеш-очередь заблокированной и не допуская таким образом обращений к ней со стороны других процессов, даже если последние  ведут  поиск незахваченных  буферов.  Пусть вместо этого процесс A захватывает буфер, используя операцию CP; если операция завершается успешно, буфер становится открытым для процесса. Процесс A  захватывает  семафор,  принадлежащий  списку свободных  буферов, выполняя операцию CP, поскольку семафор захватывается на непродолжительное время и, следовательно, приостанавливать свою работу,  выполняя  операцию  P, процесс просто не имеет возможности. Ядро убирает буфер из списка свободных буферов, снимает блокировку со списка и с хеш-очереди  и возвращает захваченный буфер.

Предположим,  что операция CP над буфером завершилась неудачно из-за того, что семафор, принадлежащий буферу, оказался захваченным. Процесс A освобождает семафор, связанный с хеш-очередью, и приостанавливается, пытаясь выполнить операцию P над семафором буфера. Операция P над семафором будет  выполняться,  несмотря на то, что операция CP уже потерпела неудачу. По завершении выполнения операции процесс A получает власть над буфером. Так  как  в оставшейся  части алгоритма предполагается, что буфер и хеш-очередь захвачены, процесс A теперь пытается захватить хеш-очередь (*).  Поскольку очередность захвата здесь (сначала семафор буфера, потом семафор очереди) обратна вышеуказанной очередности, над семафором выполняется операция CP.  Если  попытка захвата заканчивается неудачей, имеет место обычная обработка, требующаяся  по  ходу задачи. Но если захват удается, ядро не может быть уверено в том, что захвачен корректный буфер, поскольку содержимое буфера  могло  быть ранее изменено другим процессом, обнаружившим буфер в списке свободных буферов и захватившим на время его семафор. Процесс A, ожидая освобождения семафора,  не  имеет  ни малейшего представления о том, является ли интересующий его буфер тем буфером, который ему нужен, и поэтому прежде всего он  должен убедиться  в правильности содержимого буфера; если проверка дает отрицательный результат, алгоритм запускается сначала. Если содержимое буфера корректно, процесс A завершает выполнение алгоритма.

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

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

    Решение этой проблемы состоит  в создании некоторого фиктивного  процесса;

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

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

процессора. Контекст фиктивного процесса состоит только из стека ядра;  этот

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

ЗАКЛЮЧЕНИЕ

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

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

Список  используемой литературы

1. Многопроцессорные ЭВМ и методы их проектирования / Б.А.Бабаян, А.В.Бочаров, В.С.Волин и др. - М.: Высшая школа, 1990.

2.  Архитектура  UNIX/ Морис Бах Изд.: Prentice-Hall, 1986 г.,

3. http://ru.wikipedia.org/

4.http://rsusu1.rnd.runnet.ru

5. http://window.edu.ru/

6. http://www.parallel.ru/history/

7. http://evm-story.narod.ru/