Можно процессы разделить на группы по своим приоритетам.
Механизм с обратной связью:
0 – высокоприоритетный, 1 – низкоприоритетный.
Всего 4 группы:
Сначала новый процесс идет в 0, получает квант времени. Если квант меньше отведенного, то завершается. Если нет, то поступает в первую очередь, где время в два раза больше. Если времени хватает, благополучно завершается. Нет – поступает во вторую группу.
Данные для реализации:
1. количество очередей
2. алгоритм планирования, действующий между очередями
3. алгоритм планирования, действующий внутри очереди
4. правила появления нового процесса в очередь
5. правила перевода процесса из одной очереди в другую
Активность:
Набор активностей детерминирован, если каждый раз при ……….. выполнения для одного и того же набора данных будут получаться одинаковые входные данные.
Условие Бейстрайна:
Для каждой атомарной операции берется набор входных (рейд) и выходных (райд) данных.
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. Времени рестарта процесса
Все алгоритмы замещения страниц: локальные (отв. стр. у свободного процесса); глобальные (всех страниц).
D, E, G в тупиковой ситуации