Понятие операционной системы; эволюция развития операционных систем; функции операционных систем и подходы к построению операционных систем



страница5/15
Дата14.04.2017
Размер0.56 Mb.
Просмотров4431
Скачиваний3
1   2   3   4   5   6   7   8   9   ...   15

Специальные механизмы синхронизации – семафоры Дейкстры, мониторы Хора, очереди сообщений.


Семафоры

Для устранения этого недостатка во многих ОС предусма-триваются специальные системные вызовы (аппарат для работы с критическими секциями.

В разных ОС аппарат событий реализован по своему, но в любом случае используются системные функции, которые условно называют WAIT(x) и POST(x), где x – идентификатор некоторого события (например, освобождение ресурса).

Обобщающее средство синхронизации процессов предложил Дейкстра, который ввел новые примитивы, обозначаемые V (“открытие”) и P (“закрытие”), оперирующие над целыми неотрицательными переменными, называемыми семафорами.

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

Смысл P(S) заключается в проверке текущего значения семафора S, и если S>0, то осуществляется переход к следующей за примитивом операции, иначе процесс переходит в состояние ожидания. P(S): Пока S==0 Процесс блокируется; S=S-1; Операция V(S) связана с увеличением значения S на 1 и переводом одного или нескольких процессов в состояние готовности к исполнению процессором. V(S): S=S+1; В простом случае, когда семафор работает в режиме 2-х состояний (S>0 и S=0), ео алгоритм работы полностью совпадает с алгоритмом работs мьютекса, а S выполняет роль блокирующей переменной.

“+”: пассивное ожидание (постановка в очередь и автоматическая выдача ресурсов)


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

“-”: не указывают непосредственно на критический ресурс

  • некорректное использование операций может привести к нарушению работоспособности (например, переставив местами операции P(e) и P(b) в функции Writer()). Мониторы

Для облегчения работы программистов при создании параллельных программ без усилий на доказательства правильности алгоритмов и отслеживание взаимосвязанных объектов (что характерно при использовании семафоров) предложено высокоуровневое средство синхронизации, называемое мониторами. Мониторы – тип данных, обладающий собственными переменными, значения которых могут быть изменены только с помощью вызова функций-методов монитора. Функции-методы могут использовать в работе только данные, находящиеся внутри монитора, и свои параметры. Доступ к мониторам в каждый момент времени имеет только один процесс. Для организации не только взаимоисключений, но и очередности процессов, подобно семафорам f(full) и e(empty), было введено понятие условных переменных, над которыми можно совершать две операции wait и signal, отчасти похожие на операции P и V над семафорами. Функция монитора выполняет операцию wait над какой-либо условной переменной. При этом процесс, выполнивший операцию wait, блокируется, становится неактивным, и другой процесс получает возможность войти в монитор. Когда ожидаемое событие происходит, другой процесс внутри функции совершает операцию signal над той же самой условной переменной. Это приводит к пробуждению ранее заблокированного процесса, и он становится активным. Исключение входа нескольких процессов в монитор реализуется компилятором, а не программистом, что делает ошибки менее вероятными. Требуются специальные языки программирования и компиляторы (встречаются в языках, “параллельный Евклид”,”параллельный Паскаль”,Java). Следует отметить, что условные переменные мониторов не запоминают предысторию, поэтому операцию signal всегда должна выполняться после операции wait(иначе выполнение операции wait всегда будет приводить к блокированию процесса). Очереди сообщений

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

Очередь сообщений представляет возможность использовать несколько дисциплин обработки сообщений (FIFO, LIFO, приоритетный доступ, произвольный доступ).

При чтении сообщения из очереди удаления сообщения из очереди не происходит, и сообщение может быть прочитано несколько раз.

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

Основные функции управления очередью:



  • Создание новой очереди

  • Открытие существующей очереди

  • Чтение и удаление сообщений из очереди

  • Чтение без последующего удаления

  • Добавление сообщения в очередь

  • Завершение использование очереди

  • Удаление из очереди всех сообщений

  • Определение числа элементов в очереди



  1. Взаимоблокировки, тупиковые ситуации, "зависания" системы


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

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

  • Транзакция А создает общую блокировку строки 1.

  • Транзакция Б создает общую блокировку строки 2.

  • Транзакция А теперь запрашивает монопольную блокировку строки 2 и блокируется до того, как транзакция Б закончится и освободит общую блокировку строки 2.

  • Транзакция Б теперь запрашивает монопольную блокировку строки 1 и блокируется до того, как транзакция A закончится и освободит общую блокировку строки 1.

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

Тупик возникает при перестановке местами операций P(e) и P(b) в примере с процессами “читатель” и “писатель”, рассмотренном выше – ни один из этих потоков не сможет завершить начатую работу и возникнет тупиковая ситуация, которая не может разрешиться без внешнего воздействия.

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

Однако очередь – неотъемлемый признак высокого коэффициента использования ресурсов при случайном поступлении запросов а тупик – “неразрешимая” ситуация.

Проблема тупиков требует решения следующих задач:

-распознавание тупиков,

-предотвращение тупиков,

-восстановление системы после тупиков.

Распознавание тупиков

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

Предотвращение тупиков

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

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

Восстановление системы после тупиков

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



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

  • вернуть некоторые процессы в область «свопинга»

  • совершить «откат» некоторых процессов до т.н. контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места.

Контрольные точки расставляются в программе в местах, после которых возможно возникновение тупика.


  1. Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9   ...   15


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал