Операционные системы 09.02.03 2 курс. Автономной некоммерческой образовательной организации профессионального образования

• Название: Автономной некоммерческой образовательной организации профессионального образования
• Дата: 17.02.2021
• Размер: 0.57 Mb.
• Имя файла: Операционные системы 09.02.03 2 курс.doc
• Тип: Лекция; #177186
• страница: 11 из 20

Лекция №10

Активность:

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

Условие Бейстрайна:

Для каждой атомарной операции берется набор входных (рейд) и выходных (райд) данных.

W

Q

1. 
   Если W(p) и W(R) пересекаются пусто раз
   
2. 
   Пересечение W(p) и W(Q) пусто
   
3. 
   Пересечение R(p) и W(Q) также пусто
   

Следовательно, выполнение операций W(p) и W(Q) детерминировано.

Для организации взаимодействия процессов, имеющих критическую секцию, существует условие:

1. 
   Задача должна быть решена чисто программным способом, не используя специфических команд
   
2. 
   Не должно существовать никаких предположений относительно скоростей выполнения процессов
   
3. 
   Если какой-то i – процесс выполняется в критической секции, то не должны существовать процессы, выполняющие в свободной критической секции
   
4. 
   Процессы, находящиеся не в своей критической секции, не должны мешать другим процессам входить в критическую секцию
   
5. 
   Не должно возникать бесконечного ожидания для входа в критическую секцию
   

Должна существовать аппаратная команда: проверить и установить.
Про тупики:
Виды к тупикам:

1. 
   ……
   
2. 
   Использовать
   
3. 
   Освобождение
   

4 условия возникновения тупиков:

1. 
   Взаимоисключение: каждый ресурс выделен одному процессу (монопольное использование ресурсов)
   
2. 
   Ожидание: процесс удерживает за собой ресурсы, уже выделенные им, может при этом ожидать выделение дополнительных ресурсов
   
3. 
   Неперераспределяемость: ресурс, выделенный процессу, не может быть принудительно отдан, процесс отдает сам.
   
4. 
   Круговое ожидание: существует кольцевая цепь процессов, из которой каждый процесс удерживает один или несколько ресурсов, требующихся другому процессу.
   

Для тупиковой ситуации необходимо все 4 условия.

Борьба с тупиками:

1. 
   игнорирование (алгоритм Страуса)
   
2. 
   обнаружение тупиков
   
3. 
   восстановление после тупиков системы
   
4. 
   предотвращение условий возникновения
   

Условия:

Процесс А удерживает ресурс R и ожидает ресурс S

Процесс B претендует на ресурс Т

Процесс С претендует на ресурс S

Процесс D удерживает ресурс U и ожидает ресурсы S и T

Процесс E удерживает ресурс T и ожидает ресурс V

Процесс F удерживает ресурс W и ожидает ресурс S

Процесс G удерживает ресурс V и ожидает ресурс U

Является ли ситуация тупиковой?






– процесс
D, E, G в тупиковой ситуации

– ресурс
Есть процессы, вовлеченные в тупиковую ситуацию.
3) 1 способ: принудительный вывод процесса из системы для последующего использования его ресурсов.

2 способ: восстановление через откат назад. В ряде систем существует средство RESTART с контрольной точки.

3 способ: восстановление через ликвидацию одного из процессов.

Можно избежать тупика, если рационально использовать распределение ресурсов.

Алгоритм банкира:

Пусть у системы n ресурсов.

1. 
   ОС принимает запрос от пользовательского процесса, если его максимальная потребность не превышает n.
   
2. 
   Пользователь гарантирует, если ОС в состоянии удовлетворить его запрос, то устройства будут возвращены системе в конечное время.
   
3. 
   Текущее состояние системы называется надежной, если ОС может обеспечить выполнение всех процессов в течение конечного времени.
   
4. 
   Выделение устройств возможно, только если состояние системы остается надежным.
   

Ненадежное состояние не означает, что возникнет тупик.
Пусть 12 устройств, 3 процесса, 3 пользователя.

1 пользователь получил 1 устройство, максимально может потребоваться четыре.

2 пользователь получил 4 устройства, максимально может потребоваться шесть.

3 пользователь получил 5 устройств, максимально может потребоваться восемь.

Состояние системы надежно.
Недостатки:

1. 
   Алгоритм исходит из конечного числа устройств.
   
2. 
   Число пользователей должно быть постоянно.
   
3. 
   Алгоритм требует, чтобы запросы выполнялись за конкретные периоды времени, но отсутствуют данные о значении.
   
4. 
   Алгоритм требует, чтобы клиенты возвращали……………
   
5. 
   Требуется, чтобы пользователи заранее указали свои максимальные потребности.
   

Нарушение условия ожидания дополнительных ресурсов:

1. 
   Каждый процесс должен запрашивать все требуемые ресурсы сразу; не выполняется, пока не будут доставлены все ресурсы.
   
2. 
   Если процесс, удерживая ресурс, получает отказ в выделении ему дополнительные ресурсов, то он должен освободить первоначальные ресурсы, а потом запросить их вновь вместе с дополнительными.
   

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

Про виртуальную память:

Время фиктивного доступа для присутствия страницы складывается:

1. 
   Из времени обслуживания
   
2. 
   Из времени чтения страницы из вторичной (внешней) памяти
   
3. 
   Времени рестарта процесса
   

Все алгоритмы замещения страниц: локальные (отв. стр. у свободного процесса); глобальные (всех страниц).