Самодел 1 (1114716), страница 24

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

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

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

Квантование с предпочтением процессам, интенсивно обращающихся к вводу/выводу

Дисциплина обслуживания очередей следующая: сначала выбирается процесс из очереди процессов, закончивших ввод/вывод.

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

Рассмотренные алгоритмы, основанные на квантовании, не используют никакой предварительной информации о процессах.

Рассмотренные примеры алгоритмов относятся к классу вытесняющих.

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

Алгоритмы, основанные на приоритетах

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

Вычисление приоритета основывается на статических и динамических характеристиках. Изменение приоритета может происходить по инициативе процесса, пользователя, ОС. Правила назначения приоритета процессов определяют эффективность работы системы.

Планирование по наивысшему приоритету (highest priority first - HPF).

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

Возможно два варианта:

- относительный приоритет (ожидание исчерпания кванта у текущего процесса)

Смена ппроцесса происходит либо в тот же момент, когда приоритет произвольного процесса стал больше чем

приоритет считающегося. Хорошо для пакетных систем.

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

Смена ппроцесса происходит после того, когда закончится квант времени считающегося. Хорошо для тех систем,

где необходима быстрвая реакция на что-ибо

Задача выбора/постановки процесса с наивысшим приоритетом зависит от организации очереди (упорядочена/неупорядочена).

Возможно наличие очередей с одинаковым приоритетом.

Пример использования стратегии HPF.

Выбор самого короткого задания (shortest job first - SJF).

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

Этот вариант

удобен для “коротких” процессов.

Класс подходов, использующих линейно возрастающий приоритет.

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

Из выбора A и В - разные правила планирования:

- Если 0<A<=B обслуживание очереди по дисциплине FIFO

- Если 0>B>=A обслуживание очереди по дисциплине LIFO

Нелинейные функции изменения приоритета

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

В частности, метод SJF можно модифицировать, добавляя приоритет длинным процессам после некоторого времени ожидания.

Разновидности круговорота.

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

Простой круговорот (RR – round robin) не использует никакой статистической или динамической информации о приоритетах.

При круговороте со смещением каждому процессу соответствует своя длина кванта, пропорциональная его приоритету.

«Эгоистический» круговорот. Если параметры A и B : 0<=B<A.

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

Приоритет выполняемых процессов увеличивается с коэффициентом B<A, следовательно, ожидающие процессы их догонят.

При B=0 «эгоистический» круговорот практически сводится к простому.

Очереди с обратной связью (feedback – FB).

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

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

«-» Работа с несколькими очередями – издержки.

«+» Удобны для коротких заданий: не требуется предварительная информация о времени выполнения процессов.

Смешанные алгоритмы планирования

На практике концепции квантования и приоритетов часто используются совместно.

К примеру, в основе – концепция квантования, а определение кванта и/или дисциплина обслуживания очередей базируется на приоритетах.

Планирование в системах реального времени

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

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

Системы реального времени бывают “Жесткие” и ”мягкие ”.

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

Это может быть обеспечено за счет :

- полного тестирования всевозможных сценариев

- построения статического расписания

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

Периодические запросы – все моменты запроса периодического процесса можно определить заранее.

Пусть {Ti} набор периодических процессов с периодами – pi , предельными сроками выполнения di и требованиями ко времени выполнения ci.

Расписание удается построить не всегда.

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

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

Необходимое условие наличия расписания:

Сумма коэффициентов использования m=S ci / pi <= k, где k - количество доступных процессоров.

Классический алгоритм для жестких систем реального времени с одним процессором

Используются периодические запросы на выполнение процессов,

срок выполнения каждого процесса равен его периоду p_i, все процессы независимы максимальное время выполнения каждого процесса с_i известно и постоянно, игнорируется время переключения контекста, вводится ограничение на суммарный коэффициент загрузки процессора S c_i / p_i, при существовании n задач не превосходит n(2^1/n-1). Эта величина при n равна ln 2, то есть 0.7

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

Суть алгоритма:

Процессы получают статические приоритеты в соответствии с величиной их периодов выполнения, при этом самый высший приоритет получает самая короткая задача.

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

Алгоритмы с динамическим изменением приоритетов.

Параметр deadline – конечный срок выполнения.

Выбор процесса на выполнение по правилу:

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

Перепланировка – функция ОС. Планировщик – программа, которая реализует некоторый алгоритм.

Перепланировка происходит после одного из следующих событий:

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

2.выполнение системного вызова, а ресурс занят

3. системный вызов, связанный с освобождением ресурса. Если какой-то процесс ждет этот ресурс, то освобождение подождет.

Общие критерии для сравнения алгоритмов планирования

Планирование бывает краткосрочное, среднесрочное и долгосрочное

- использование времени ЦП

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

- время ожидания (в очереди готовых) – влияет на приоритет процесса

- время оборота (полное время от момента поступления до завершения)

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

терминалу

- предельный срок выполнения процесса

и т.д.

Планирование в ОС UNIX

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

Если процесс не завершается или не блокируется в рамках 1 секунды – он вытесняется.

В общем случае значение приоритета есть функция

P=F (CPU, nice), т.е. в вычислении приоритета используются две изменяемые составляющие – CPU (системная) и nice (пользовательская). Учитывается история выполнения, величины CPU и nice ограничены.

Пересчет приоритета процесса происходит в момент выбора процесса для выполнения на ЦП 1 раз в секунду.

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

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

Группы приоритетов

(в порядке убывания)

- программа свопинга

- управление блочными устройствами ввода/вывода

- управление файлами

- управление байт-ориентированными устройствами ввода/вывода

- пользовательские процессы

Иерархия обеспечивает эффективное использование устройств ввода/вывода

СPU_j (i) - время использования ЦП процессом j за время i;

P_j (i) - приоритет процесса j в начале кванта i (приоритет выше, если значение меньше);

Base_j - базовый приоритет j-го процесса (необходим для разделения процессов на фиксированные группы уровней приоритетов);

nice_j - пользовательская составляющая приоритета (значение может только увеличиваться до некоторого уровня).

Пример традиционного планирования процессов в ОС Unix

Рассмотрим на примере, как это все работает. Предполагается, что есть три процесса, которые создаются одновременно с одним и тем же базовым приоритетом (в данном случае – это число 60). Таймер прерывает выполнение процесса 60 раз в секунду. Предполагается, что не один процессов не блокируется сам, и нет других процессов, готовых к выполнению. Для простоты пользовательская составляющая nice_j игнорируется. Происходит пересчет времени и приоритетов.

Рассмотрим, как работает первый процесс. Он проработал 1 секунду (счетчик 060) – 60 раз его прерывали, по первой формуле получаем: 60/2=30, соответственно приоритет будет пересчитан по второй формуле, и полученное значение будет равно 75. После этого начинает работать второй процесс - третий процесс пока стоит. Когда проработает второй процесс, у него произойдет точно такой же пересчет, как и у первого, потому что они начинали с одинаковых позиций. У первого процесса время, которое он использовал, будет: 30/2=15, и приоритет: 60+15/2=67. У второго процесса приоритет соответственно 75, третий начал работать. Когда третий процесс дойдет до конца своего кванта времени – у него будет приоритет 75. У первого процесса приоритет составит 63.

Планирование в Windows NT.

Квантование сочетается с использованием динамических абсолютных приоритетов.

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

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