Алгоритмы обнаружения тупиков. Редукция графа распределения ресурсов.
Обнаружение тупиков
Обнаружение тупика — это установление факта, что возникла тупиковая ситуация, и определение процессов и ресурсов, вовлеченных в эту тупиковую ситуацию. Алгоритмы обнаружения тупиков, как правило, применяются в системах, где выполняются первые три необходимых условия возникновения тупиковой ситуации. Эти алгоритмы затем определяют, не создался ли режим кругового ожидания.
Применение алгоритмов обнаружения тупиков сопряжено с определенными дополнительными затратами машинного времени. Таким образом, здесь мы снова сталкиваемся с необходимостью прибегать к компромиссным решениям, столь распространенным в операционных системах. Будут ли накладные расходы, связанные с реализацией алгоритмов обнаружения тупиковых ситуаций, в достаточной степени оправданы потенциальными выгодами от локализации и устранения тупиков? В данный момент мы этот вопрос рассматривать не будем, а лучше сосредоточим свое внимание на описании алгоритмов, позволяющих обнаруживать тупики.
Обнаружение тупиков
Обнаружение взаимоблокировки сводится к фиксации тупиковой ситуации и выявлению вовлеченных в нее процессов. Для этого производится проверка наличия циклического ожидания в случаях, когда выполнены первые три условия возникновения тупика. Методы обнаружения активно используют графы распределения ресурсов.
Рассмотрим модельную ситуацию.
Процесс P1 ожидает ресурс R1.
Процесс P2 удерживает ресурс R2 и ожидает ресурс R1.
Процесс P3 удерживает ресурс R1 и ожидает ресурс R3.
Процесс P4 ожидает ресурс R2.
Процесс P5 удерживает ресурс R3 и ожидает ресурс R2.
Вопрос состоит в том, является ли данная ситуация тупиковой, и если да, то какие процессы в ней участвуют. Для ответа на этот вопрос можно сконструировать граф ресурсов, как показано на рис. 7.3. Из рисунка видно, что имеется цикл, моделирующий условие кругового ожидания, и что процессы P2,P3,P5, а может быть, и другие находятся в тупиковой ситуации.
Рис. 7.3. Граф ресурсов
Визуально легко обнаружить наличие тупика, но нужны также формальные алгоритмы, реализуемые на компьютере.
Один из таких алгоритмов описан в [Таненбаум, 2002], там же можно найти ссылки на другие алгоритмы.
Существуют и другие способы обнаружения тупиков, применимые также в ситуациях, когда имеется несколько ресурсов каждого типа. Так в [Дейтел, 1987] описан способ, называемый редукцией графа распределения ресурсов, а в [Таненбаум, 2002] – матричный алгоритм.
Организация памяти. Стратегии управления памятью. Связное и несвязное распределение памяти.
Понятие памяти и функции ОС по управлению памятью
В данном модуле будем рассматривать основную память компьютера. Ее также называют временной, оперативной, первичной, физической, реальной. В английской технической литературе память обозначается синонимами memory и storage. Основная память является внутренней по отношению к вычислительной системе. Организация и управление основной памятью вычислительной машины — один из самых важных факторов, определяющих построение операционных систем. Для непосредственного выполнения программ или обращения к данным необходимо, чтобы они размещались в основной памяти. Этим и объясняется особая роль памяти, необходимость тщательного управления ею.
Вторичная, или внешняя память — это, как правило, накопители на магнитных дисках (жесткие диски или винчестеры, дискеты), магнитных лентах — имеет гораздо большую емкость, стоит дешевле и позволяет хранить множество программ и данных, которые должны быть наготове для обработки.
В отличие от внешней памяти, современной полупроводниковой оперативной памяти для сохранения информации требуется постоянное электропитание.
В ранних ОС управление памятью сводилось просто к загрузке программы и ее данных из некоторого внешнего накопителя (перфоленты, магнитной ленты или магнитного диска) в основную память. С появлением мультипрограммирования у ОС появились функции, связанные с распределением имеющейся памяти между несколькими одновременно выполняющимися программами:
· отслеживание свободной и занятой памяти;
· выделение памяти процессам и освобождение памяти по завершении процессов;
· вытеснение кодов и данных процессов из оперативной памяти на диск (полное или частичное), когда размеры основной памяти не достаточны для размещения в ней всех процессов, и возвращение их в оперативную память, когда в ней освобождается место;
· настройка адресов программы на конкретную область физической памяти; динамическое распределение памяти, т.е. выполнение запросов процессов на выделение им дополнительной памяти во время их выполнения;
· дефрагментация памяти, т.е. ликвидация свободных участков памяти, разбросанных по всему пулу памяти после динамического выделения и освобождения памяти;
· создание новых служебных информационных структур, таких как описатели процессов, различные таблицы распределения ресурсов, буферы, используемые процессами для обмена данными и т. п. Все эти системные объекты требуют памяти. В некоторых ОС заранее (во время установки) резервируется некоторый фиксированный объем памяти для системных нужд. В других же ОС используется более гибкий подход, при котором память для системных целей выделяется динамически;
· защита памяти — задача операционной системы, состоящая в том, чтобы не позволить выполняемому процессу записывать или читать данные из памяти, назначенной другому процессу. Эта функция, как правило, реализуется программными модулями ОС в тесном взаимодействии с аппаратными средствами.
Связное и несвязное распределение памяти
Под распределением памяти будем понимать то, каким образом представляется и используется основная память различными процессами. Располагается ли в ней несколько программ одновременно или только одна? Если в основной памяти размещается несколько пользовательских программ сразу, то предоставляется ли каждой из них одинаковое количество ячеек или основная память разбивается на части, так называемые разделы, различных размеров? Разбивается ли основная память жестким образом, когда разделы определяются на достаточно длительные периоды времени, либо предусмотрено более динамичное разбиение, позволяющее вычислительной машине быстро реагировать на изменения потребностей процессов в ресурсах? Должна ли программа помещаться в одном непрерывном разделе памяти или может занимать несколько различных областей?
Самые первые вычислительные машины требовали связного распределения памяти, при котором каждая программа должна занимать один сплошной блок ячеек памяти.
При несвязном распределении памяти программа разбивается на ряд блоков, или сегментов, которые могут размещаться в основной памяти в участках, не обязательно соседствующих друг с другом. Операционной системе гораздо сложнее обеспечить несвязное распределение памяти, однако подобный подход обладает важным преимуществом: если основная память имеет ряд небольших свободных участков вместо одного большого, то, как правило, операционная система все же может загрузить и выполнить программу, которой в противном случае пришлось бы ждать.
4.3.1 Связное распределение памяти в однопрограммных системах
На самых первых вычислительных машинах в каждый момент времени мог работать только один человек, и все ресурсы машины оказывались в распоряжении этого пользователя.
Первоначально каждый пользователь сам писал всю программу, необходимую для реализации конкретной прикладной задачи, включая подробные процедуры ввода-вывода в машинных кодах. Но очень скоро коды программ, необходимых для реализации базовых функций ввода-вывода, начали объединяться в так называемые системы управления вводом-выводом (Input-Output Control System - IOCS). Благодаря этому у пользователей, которым требовались определенные операции ввода-вывода, отпала необходимость самим непосредственно кодировать эти операции, — они получили возможность вызывать соответствующие подпрограммы ввода-вывода, эффективно выполняющие реальную работу. Тем самым было обеспечено существенное упрощение и ускорение процесса кодирования программ. Создание систем управления вводом-выводом можно, по-видимому, считать началом развития концепции современных операционных систем. Организация памяти в типичном случае связного распределения для одного пользователя показана на рис. 4.2. Это самое простое — непрерывное распределение памяти.
стратегии управления ОП:
· стратегия выборки:
по запросу (запросам) - из ОП считывается блок информации и помещается в кэш;
упреждающей выборки - сначала обращается к кэш, а затем выполняется.
· стратегия размещения. ОЗУ может представляться в виде объединения n-участков, способных хранить одинаковое количество информации и взаимодействовать с ЦП независимо друг от друга. При этом адресное пространство ЭВМ организовано таким образом, что подряд идущие ячейки памяти (адреса) находятся в смежных участках памяти (блоках). Так как программа состоит из линейных участков, то можно организовать буфер в ЦП, который можно заполнять вперед, т. е. за одно обращение можно считать n-команд. Стратегия размещения позволяет определить, в какое место в ОП необходимо поместить поступающую информацию.
Возможны 3 стратегии размещения:
участок памяти наиболее подходящий;
первый подходящий участок памяти;
наименее подходящий участок памяти.