Шпаргалка по "Операционные системы и среды "

Избежание взаимоблокировок.

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

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

Алгоритм  планирование- алгоритм банкира.

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

Метод предотвращения тупиков. 

Существуют еще  случаи взаимоблокировки:

- двухфазное блокирование. Частично завершает процесс из того, что ресурс недоступен

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

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

Вопрос 14. Управление памятью.  

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

Систему управления памятью  можно разделить  на два класса:

1. Перемещающая  процессы между ОП и диском во время их выполнения (свопинг, страничная подкачка).
2. Не перемещающая процессы.

Функции ОС по управлению памяти.

1. Распределение в памяти в однозадачной системе. В каждый момент времени работает только одна программа.  При этом основная память делиться на две части: в одной ОС, в другой- выполняющаяся программа.
2. Распределение памяти в мультипрограммных системах.

 
 
 

Основные функции:

- отслеживание ( учет  свободной и занятой памяти).

- настройка адресов  программы на конкретную область  физич. памяти.

- полное или частичное  вытеснение кодов и данных  процессов из ОП на диск, когда  размеры ОП не достаточны для  размещения всех процессов и  возвращение их в ОП.

- дефрагментация  памяти.

Распределение памяти. Существуют ряд вопросов управления памятью, которые в различных ОС решаются по разному:

- выделять процессу  непрерывную область в   памяти  или участками.

-сегменты программы  могут находится в одном месте или в разных.

- что делать, если  сегменты не помещаются в выделенную  память.

- как сократить  затраты ресурсов системы на  управление памятью.

Классификация методов распределения  памяти: Без использования внешней памяти- с фиксированными разделами, динамические разделы, перемещающие размеры. С использованием внешней памяти- страничное распределение, сегментное распределение, странично- сегментное распределение.  

Сегментное  распределение памяти.

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

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

Виртуальный адрес  при сегментной организации может  быть представлен парой чисел  g и S, где g-  номер сегмента, S- смещение с сегменте.

Главным недостатком  данной системы является медленное  преобразование адреса.

Странично- сегментное распределение памяти.

Этот метод представляет собой комбинацию выше описанных  методов и включает их достоинства.

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

Распределение памяти с фиксированными разделами. Любой процесс, размер которого не превышает размер раздела, может быть  загружен в любой раздел. ОС может легко загружать и выгружать процессы в разделы, обеспечивая работой процессор.

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

Разделы разных размеров более удобны. Процессы могут загружаться в разделы в одну очередь или несколько. В первом случае возникает очередь, что требует время, во втором- неэкономичное использование  памяти.

Схемы с фиксированными разделами относительно просты, предъявляют  минимальные требования к ОС, не большие  расходы работы процессора на распределение памяти.

Распределение памяти динамическими  разделами.

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

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

Динамическое  распределение памяти перемещающими разделами.

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

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

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

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

При выполнении процесса относительные адреса обрабатываются процессором  в два этапа:

1. Сначала к относительному адресу прибавляется значение базового регистра для получения абсолютного адреса.
2. Абсолютный адрес сравнивается со значением в граничном регистре. Если полученный абсолютный адрес принадлежит данному процессу, команда выполняется, в противном случае- генерируется соответствующие данной ошибки прерывания.

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

Если процесс статичен, ОС предоставляет ему необходимое  кол-во памяти, с учетом увеличения. Если памяти все же становится недостаточно, процесс переносится на другое более  свободное место или выгружается  на диск, до появления свободного места, или прекращается работа процесса.

При использовании  многозадачности появляется эффективность  загрузки ЦП. Степень загрузки ЦП равно  Z= 1-p*n, где p-  время процесса в ожидании завершении операции ввода- вывода, n- степень ,  кол-во находящихся в памяти процессов. Степень многозадачности называется зависимость использования ЦП от числа n.

Два способа учета  использования памяти: битовые массивы  и связные списки.  

Управление  памятью с помощью  битовых массивов.

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

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

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

Существует  несколько алгоритмов ля предоставления памяти процессу:

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

 

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

5. Быстрый подходящий. Поддерживает отдельные списки некоторых наиболее часто запрашиваемых размеров.

Недостаток всех этих алгоритмов: если не производить  слияние всех свободных областей, то память будет разбиваться на большое  число маленьких свободных фрагментов. 

Вопрос 15. Виртуальная память.

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