Самодел 2 (1114717), страница 9

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

Текст из файла (страница 9)

Нити “реального” времени (16-31] – высокоприоритетные нити. Критичны по времени выполнения.

Нити с переменными приоритетами

Изначально процессу присваивается базовый приоритет.

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

Нить получает значение приоритета из диапазона базового приоритета.

Приоритет нити может отклоняться от своего базового приоритета, и это может быть не связано с изменением базового приоритета процесса ( см. диапазон значений динамического приоритета нитей).

Например, ОС повышает приоритет нити, если до конца не использован квант времени, и уменьшает в противном случае.

Суть планирования (алгоритма):

• Поддерживается группа очередей (для нитей с переменными приоритетами ) – по одной для каждого приоритета. Система просматривает очереди, начиная с самой приоритетной.

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

• Если нить исчерпала квант – ее приоритет понижается на единицу и она перемещается в соответствующую очередь

• Повышается значение приоритета – при выходе из состояния ожидания окончания ввода-вывода

Планирование свопинга в ОС Unix

Область свопинга - специально выделенное системой пространство внешней памяти

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

Работа диспетчерского процесса.

• Поиск процесса для ввода в оперативную память. Иначе выбирается процесс с максимальным значением p_time (обозначим outage). Если (outage < 3), то процесс не загружается.

• Если места в ОП нет, диспетчерский процесс определяет кандидата на выгрузку, прежде всего среди процессов в системной фазе, ждущих завершения сравнительно медленных операций. (По определению их приоритет > PZERO). Из них – занимающий наибольшее место. Если такого нет – с максимальным значением p_time (обозначим inage). При (inage < 2) процесс не выгружается.

• При отказе загрузки (нет претендентов) / выгрузки (невозможен выбор) диспетчерский процесс переходит в состояние ожидания

Планирование обработки прерываний

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

Рассмотрим пример, в котором обработчик прерываний принтера блокирует на длительное время обработку прерываний от таймера, в результате чего системное время на некоторое время «замирает», и один из процессов (2), критически важный для пользователя, не получат управление в запланированное время.

Н
еупорядоченная обработка прерываний

Упорядоченное планирование прерываний

Механизм прерываний поддерживает приоритезацию и маскирование прерываний.

Источники прерываний делятся на классы – каждому классу свой уровень приоритета запроса на прерывание.

Дисциплина обслуживания приоритетов

- относительная (выбор по наивысшему приоритету, но далее обработка не может быть отложена)

- абсолютная (происходит переход к обработке более приоритетного с откладыванием текущего)

Механизм маскирования запросов.

В схеме с абсолютными приоритетами заложено маскирование, так как запрещаются запросы с равными или более низкими приоритетами.

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

Последовательность действий

Упорядочивание работы обработчиков прерываний – механизм приоритетных очередей.

Наличие в ОС программного модуля – диспетчера прерываний.

При возникновении прерывания – вызов диспетчера.

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

Планирование обработки прерываний в Windows NT

Все источники прерываний делятся на несколько классов, и каждому уровню присваивается уровень запроса прерывания – Interrupt Request Level (IRQL). Этот уровень и представляет приоритет данного класса.

Поступление запроса на прерывание/исключение – вызов диспетчера прерываний, который

• Запоминает информацию об источнике прерывания

• Анализирует его приоритет

Если приоритет <= IRQL прерванного, то отложить в очередь, иначе текущий обработчик – в очередь, управление - новому

Реализация диспетчера прерываний в Windows NT

Особенности планирования ввода/ вывода

Одна из важных задач планирования – обеспечение занятости внешних устройств

Для этого можно присваивать процессам высокий приоритет в периоды, когда они интенсивно используют ввод/ вывод

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

Применяется стратегия HPF.

2.3. Взаимодействие процессов: синхронизация, тупики

Параллельные процессы

Параллельные процессы – процессы, выполнение которых хотя бы частично перекрывается по времени.

• Независимые процессы используют независимое множество ресурсов

на работу такого процесса не влияют другие процессы

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

Разделение ресурсов

Разделение ресурса – совместное использование несколькими процессами ресурса ВС, когда каждый из процессов некоторое время владеет ресурсом. Разделению подлежат как аппаратные, так программные ресурсы.

Критические ресурсы – разделяемые ресурсы, которые должны быть доступны в текущий момент времени только одному процессу. Таковыми ресурсами могут быть, как внешнее устройство, так и некая переменная, значение которой может изменяться разными процессами.

Важнейшие задачи

• Распределение ресурсов между процессами

• Организация защиты ресурсов, выделенных определенному процессу, от неконтролируемого доступа со стороны других процессов

Т
ребование мультипрограммирования

Рассмотрим пример ситуации, в которой нарушается требование мультипрограммирования.

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

Такие ситуации называются гонками (race conditions) между процессами, а процессы – конкурирующими.

Взаимное исключение

Гонки (race conditions) между процессами

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

Критическая секция (или критический интервал) - часть программы (фактически набор операций), в которой осуществляется работа с критическим ресурсом.

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

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

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

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

Проблемы организации взаимного исключения

• Тупики (deadlocks)

• Блокирование (дискриминация)

Тупики (deadlocks)

При организации взаимного исключения могут возникнуть тупики (deadlocks), ситуации в которой конкурирующие за критический ресурс процессы вступают в клинч – безвозвратно блокируются.

Есть два процесса А и В, каждому из которых в некоторый момент требуется иметь доступ к двум ресурсам R1 и R2. Процесс А получил доступ к ресурсу R1, и следовательно, никакой другой процесс не может иметь к нему доступ, пока процесс А не закончит с ним работать. Одновременно процесс В завладел ресурсом R2. В этой ситуации каждый из процессов ожидает освобождения недостающего ресурса, но оба ресурса никогда не будут освобождены, и процессы никогда не смогут выполнить необходимые действия.

Блокирование (дискриминация)

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

Способы реализации взаимного исключения

• Запрещение прерываний и специальные инструкции

• Алгоритм Петерсона

• Активное ожидание

• Семафоры Дейкстры

• Мониторы

• Обмен сообщениями

Семафоры Дейкстры

S – переменная целого типа

Операции над S

• Down(S) (или P(S))

• Up(S) (или V(S))

Вводится тип данных, именуемый семафором. Семафор представляет собой переменную целого типа S, над которой определены две операции: down(s) (или P(S)) и up(S) (или V(S)). Оригинальные обозначения P и V, данные Дейкстрой и получившие широкое распространение в литературе, являются сокращениями голландских слов proberen – проверить и verhogen – увеличить.

down(S) проверяет значение семафора, и если оно больше нуля, то уменьшает его на 1. Если же это не так, процесс блокируется, причем операция down считается незавершенной. Вся операция является неделимой, т. е. проверка значения, его уменьшение и, возможно, блокирование процесса производится как одно атомарное действие, которое не может быть прервано.

up(S) увеличивает значение семафора на 1. При этом, если в системе присутствуют процессы, блокированные ранее при выполнении down на этом семафоре, ОС разблокирует один из них с тем, чтобы он завершил выполнение операции down, т. е. вновь уменьшил значение семафора. Увеличение значения семафора и, возможно, разблокирование одного из процессов и уменьшение значения являются атомарной неделимой операцией.

Пример.

Представим себе супермаркет, посетители которого прежде чем войти в торговый зал должны обязательно взять себе инвентарную тележку. В момент открытия магазина на входе имеется N свободных тележек – это начальное значение семафора. Каждый посетитель забирает одну из тележек (уменьшая тем самым количество оставшихся на 1) и проходит в торговый зал – это аналог операции down. При выходе посетитель возвращает тележку на место, увеличивая количество тележек на 1 – это аналог операции up. Теперь представим себе, что очередной посетитель обнаруживает, что свободных тележек нет – он вынужден блокироваться на входе в ожидании появления тележки. Когда один из посетителей, находящихся в торговом зале, покидает его, посетитель, ожидающий тележку, разблокируется, забирает тележку и проходит в зал. Таким образом, наш семафор в виде тележек позволяет находиться в торговом зале (аналоге критической секции) не более чем N посетителям одновременно. Положив N=1, получим реализацию взаимного исключения.

Использование двоичного семафора для организации взаимного исключения

Характеристики

Список файлов лекций