Проблемы синхронизации (тупики) и способы их разрешения
Тупик возникает при перестановке местами операций P(e) и P(b) в примере с процессами “читатель” и “писатель”, рассмотренном выше – ни один из этих потоков не сможет завершить начатую работу и возникнет тупиковая ситуация, которая не может разрешиться без внешнего воздействия.
Тупиковые ситуации следует отличать от простых очередей хотя те и другие возникают при совместном использовании ресурсов и внешне выглядят схоже.
Однако очередь – неотъемлемый признак высокого коэффициента использования ресурсов при случайном поступлении запросов а тупик – “неразрешимая” ситуация.
Проблема тупиков требует решения следующих задач:
-распознавание тупиков,
-предотвращение тупиков,
-восстановление системы после тупиков.
Распознавание тупиков
В случаях, когда тупиковая ситуация образована многими процессами, использующими много ресурсов, распознавание тупика является не тривиальной задачей. Существуют формальные, программно-реализованные методы распознавания тупиков, основанные на ведении таблиц распределения ресурсов и таблиц запросов к занятым ресурсам, анализ которых позволяет обнаружить взаимные блокировки.
Предотвращение тупиков
Тупики могут быть предотвращены на стадии проектирования и разработки программного обеспечения, чтобы тупик не мог возникнуть ни при каком соотношении взаимных скоростей процессов.
Существует подход динамического предотвращения тупиков, заключающийся в использовании определенных правил при назначении ресурсов процессам (например, ресурсы могут выделяться в определенной последовательности, общей для всех процессов, как диск и принтер в примере).
Восстановление системы после тупиков
При возникновении тупиковой ситуации не обязательно снимать с выполнения все заблокированные процессы, а можно:
снять только часть из них, при этом освобождая ресурсы, ожидаемые остальными процессами
вернуть некоторые процессы в область «свопинга»
совершить «откат» некоторых процессов до т.н. контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места.
Контрольные точки расставляются в программе в местах, после которых возможно возникновение тупика.
Распределение памяти: общие принципы управления памятью в однопрограммных ос, распределение памяти фиксированными, динамическими, перемещаемыми разделами.
Распределение памяти в однопрограммных ОС:
Непрерывное
Оверлейное (структура с перекрытием)
Непрерывное распределение – это самая простая и распространенная схема, согласно которой вся память условно может быть разделена на три области:
Область, занимаемая ОС
Область, в которой размещается исполняемый процесс
Свободная область памяти
Такая схема распределения влечет за собой два вида потерь вычислительных ресурсов:
Потерю процессорного времени, потому что процессор простаивает, пока задача ожидает завершения операций ввода-вывода
Потерю самой ОП, потому что далеко не каждая программа использует всю память, а режим работы в этом случае однопрограммный
(+)
Недорогая реализация, которая позволяет отказаться от многих второстепенных функций ОС, например, защита памяти – единственное, что следует защищать - программные модули и области памяти самой ОС)
Оверлейное распределение. Если логическое адресное пространство программы должно быть больше, чем свободная область памяти, или весь возможный объем ОП, то вся программа может быть разбита на главный и второстепенные сегменты, а в ОП одновременно могут находится только ее главная часть и один или несколько неперекрывающихся сегментов (структуры с перекрытием)
Образное представление организации памяти с использованием структуры с перекрытием
П
оочередно
можно загружать в память ветви А-В, А-С-D
и А-С-Е программы
Мультипрограммные ОС
Для организации мультипрограммного режима необходимо обеспечить одновременное расположение в ОП нескольких задач (целиком или частями)
При решении этой задачи ОС должна учитывать целый ряд моментов:
Следует ли назначать каждому процессу одну непрерывную область физической памяти или фрагментами
Должны ли сегменты программы, загруженные в память, находится в одном месте в течении всего периода выполнения процесса или можно ее время от времени сдвигать
Что следует предпринять, если сегменты программы не помещаются в имеющуюся память
Распределение памяти фиксированными разделами
Простейший способ управления ОП состоит в том, что память разбивается на несколько областей фиксированной величины, называемых разделами. Разбиение может быть выполнено вручную оператором во время старта системы или во время ее установки.
В каждом разделе и в каждый момент времени может располагаться по одной задаче, и к каждому разделу в отдельности можно применить методы, используемые при распределении памяти в однопрограммных ОС.
Очередной новый процесс, поступивший на выполнение помещается либо в общую очередь(а), либо в очередь к некоторому разделу(б)
Подсистема управления памятью в этом случае выполняет следующие задачи:
Сравнивает объем памяти, требуемый для вновь поступившего процесса, с размерами свободных разделов и выбирает подходящий раздел
Осуществляет загрузку программы в один из разделов и настройку и настойку адресов
(+): простота
(-):Существенные потери памяти от внутренней фрагментации
Учитывая то, что в каждом разделе может выполняться только один процесс, то уровень мультипрограммирования заранее ограничен числом разделов, так как независимо от размера программы она будет занимать весь раздел
Применялся в ранних мультипрограммных ОС, сейчас – в ОСРВ за счет детерминированности вычислительного процесса и небольших затрат на реализацию
Распределение памяти Перемещаемыми разделами
Чтобы уменьшить потери от внутренней фрагментации, целесообразно размещать в ОП задачи «плотно», одну за другой, выделяя ровно столько памяти, сколько задача потребует (распределение памяти динамическими разделами)
Обобщенный алгоритм:
Вся память свободна. Каждому вновь поступающему процессу выделяется вся необходимая память (если достаточный объем памяти отсутствует, то процесс не создается)
После завершения процесса память освобождается, и на это место может быть загружен другой процесс
Задачами операционной системы при реализации данного метода управления памятью является:
ведение таблиц свободных и занятых областей, в которых указываются начальные адреса и размеры участков памяти,
при поступлении новой задачи - анализ запроса, просмотр таблицы свободных областей и выбор раздела, размер которого достаточен для размещения поступившей задачи,
загрузка задачи в выделенный ей раздел и корректировка таблиц свободных и занятых областей,
после завершения задачи корректировка таблиц свободных и занятых областей.
Выбор раздела для вновь поступившей задачи может осуществляться по разным правилам. Например:
"первый попавшийся раздел достаточного размера"(first fit)
"раздел, имеющий наименьший достаточный размер"(best fit)
"раздел, имеющий наибольший достаточный размер"(worst fit)
(+)
Значительная гибкость
(-)
Внешняя фрагментация памяти – наличие большого числа несмежных участков свободной память небольшого
Распределение памяти динамическими разделами
Одним из методов борьбы с фрагментацией является перемещение всех занятых участков («сжатие», «уплотнение», «дефрагментация») в сторону старших либо в сторону младших адресов, так, чтобы вся свободная память образовывала единую свободную область (рисунок).
Дефрагментация может выполняться:
При каждом завершении задачи (меньше однократной вычислительной работы)
В случае, когда для вновь поступившей задачи нет свободного раздела достаточного размера (процедура выполняется реже)
(+) более эффективное использование памяти
(-) требует значительных временных затрат