Файл: Курс лекций по дисциплине Операционные системы 2 Содержание.pdf

37
А, Д С и Д а у второго пользователя только один процесс — Е. Если используется циклическое планирование, то возможная последовательность планируемых процессов, соответствующая всем ограничениям, будет иметь следующий вид:
AEBECEDEAEBECEDE...
Но если первому пользователю предоставлено вдвое большее время, чем второму, то мы можем получить следующую последовательность:
ABECDEABECDE...
Разумеется, существует масса других возможностей, используемых в зависимости от применяемых понятий справедливости.
4. Планирование в системах реального времени
Системы реального времени относятся к тому разряду систем, в которых время играет очень важную роль. Обычно одно или несколько физических устройств, не имеющих отношения к компьютеру, генерируют входные сигналы, а компьютер в определенный промежуток времени должен соответствующим образом на них реагировать. К примеру, компьютер в проигрывателе компакт-дисков получает биты от привода и должен превращать их в музыку за очень короткий промежуток времени. Если вычисления занимают слишком много времени, музыка приобретет довольно странное звучание. Другими системами реального времени являются отслеживание параметров пациента в палате интенсивной терапии, автопилот воздушного судна, управление промышленными роботами на автоматизированном предприятии. Во всех этих случаях получение верного результата, но с запозданием, зачастую так же неприемлемо, как и неполучение его вообще.
Системы реального времени обычно делятся на жесткие системы реального
времени (системы жесткого реального времени), в которых соблюдение всех крайних сроков является обязательным, и гибкие системы реального времени (системы мягкого реального времени), в которых нерегулярные несоблюдения крайних сроков нежелательны, но вполне допустимы. В обоих случаях режим реального времени достигается за счет разделения программы на несколько процессов, поведение каждого из которых вполне предсказуемо и заранее известно. Эти процессы являются, как правило, быстротечными и способными успешно завершить свою работу за секунду. При обнаружении внешнего события планировщик должен так спланировать работу процессов, чтобы были соблюдены все крайние сроки.
События, на которые должна реагировать система реального времени, могут быть далее категорированы как периодические (происходящие регулярно) или апериодические
(происходящие непредсказуемо). Возможно, системе придется реагировать на несколько периодических потоковых событий. В зависимости от времени, необходимого на обработку каждого события, с обработкой всех событий система может даже не справиться. Например, если происходит m периодических событий, событие i возникает с периодом Р
i и для обработки каждого события требуется С
i секунд процессорного ремени, то поступающая информация может быть обработана только в том случае, если



m
i
i
i
P
С
1 1
Системы реального времени, отвечающие этому критерию, называются
планируемыми.
В качестве примера рассмотрим гибкую систему реального времени с тремя периодическими событиями с периодами 100, 200 и 500 мс соответственно. Если на обработку каждого из этих событий требуется соответственно 50, 30 и 100 мс процессорного времени, работа системы может быть спланирована, поскольку 0,5 + 0,15 +
0,2 < 1. Если будет добавлено четвертое событие с периодом 1 с, то система будет сохранять планируемость до тех пор, пока на обработку этого события не потребуется

38 более 150 мс процессорного времени. В этом вычислении подразумевается, что издержки на переключение контекста настолько малы, что ими можно пренебречь.
Алгоритмы планирования работы систем реального времени могут быть статическими или динамическими. Первый из них предусматривает принятие решений по планированию еще до запуска системы, а второй — их принятие в реальном масштабе времени. Статическое планирование работает только при условии предварительного обладания достоверной информацией о выполняемой работе и о крайних сроках, которые нужно соблюсти. Алгоритмы динамического планирования подобных ограничений не имеют.
5. Планирование потоков
Когда есть несколько процессов и у каждого есть несколько потоков, у нас появляется два уровня параллелизма: процессы и потоки. Планирование в таких системах существенно зависит от того, на каком уровне поддерживаются потоки: на пользовательском, на уровне ядра или на обоих уровнях.
Сначала рассмотрим потоки на уровне пользователя. Поскольку ядро о существовании потоков не знает, оно работает в обычном режиме, выбирая процесс, скажем, А, и передает процессу А управление до истечения его кванта времени.
Планировщик потоков внутри процесса А решает, какой поток запустить, скажем, А1. Из- за отсутствия таймерных прерываний для многозадачных потоков этот поток может продолжать работу сколько ему понадобится. Если он полностью израсходует весь квант времени, отведенный процессу, ядро выберет для запуска другой процесс.
Когда процесс А будет наконец-то снова запущен, поток А1 также возобновит свою работу. Он продолжит расходовать все отведенное процессу А время, пока не закончит свою работу. Но его недружелюбное поведение никак не отразится на других процессах.
Они получат то, что планировщик посчитает их долей, независимо от того, что происходит внутри процесса А.
Теперь рассмотрим случай, когда потоки процесса
А выполняют непродолжительную относительно доли выделенного процессорного времени работу, например работу с продолжительностью в 5 мс при кванте времени в 50 мс.
Следовательно, каждый из них запускается на небольшой период времени, возвращая затем центральный процессор планировщику потоков. При этом, перед тем как ядро переключится на процесс В, может получиться следующая последовательность: А1, А2,
A3, А1, А2, A3, А1, А2, A3, А1. Эта ситуация показана на рис. 4, а.
Рис. 4. Возможный вариант планирования потоков: на уровне пользователя с
квантом времени в 50 мс и потоками, работающими по 5 мс при работе ЦП в пределах
этого кванта (а); на уровне ядра с теми же характеристиками (б)

39
Алгоритм планирования, используемый системой поддержки исполнения программ, может быть любым из ранее рассмотренных. На практике наиболее распространены циклическое и приоритетное планирование. Единственным ограничением будет отсутствие таймерного прерывания в отношении потока, выполняемого слишком долго.
Теперь рассмотрим ситуацию с потоками, реализованными на уровне ядра. Здесь конкретный запускаемый поток выбирается ядром. Ему не нужно учитывать принадлежность этого потока конкретному процессу, но если понадобится, то он может это сделать. Потоку выделяется квант времени, по истечении которого его работа приостанавливается. Если выделен квант в 50 мс, а запущен поток, который блокируется через 5 мс, то очередность потоков на период продолжительностью 30 мс может быть следующей: А1,В1, А2, В2, A3, ВЗ, что невозможно получить при таких параметрах на пользовательском уровне. Эта ситуация частично показана на рис. 4, б.
Потоки на уровне пользователя и потоки на уровне ядра различаются в основном производительностью работы. Для переключения потоков, реализованных на уровне, требуется лишь небольшое количество машинных команд, а для потоков на уровне ядра требуется полное контекстное переключение, смена карты памяти и аннулирование кэша, что делается на несколько порядков медленнее. С другой стороны, у потоков на уровне ядра, если поток заблокирован на операции ввода-вывода, он не вызывает приостановку всего процесса, как у потоков на уровне пользователя. Поскольку ядру известно, что на переключение с потока из процесса А на поток из процесса В тратится больше времени, чем на запуск второго потока из процесса А (из-за необходимости изменения карты памяти и обесценивания кэша памяти), то оно может учесть эти сведения при принятии решения. К примеру, если взять два равнозначных во всем остальном потока, один из которых принадлежит тому процессу, чей поток был только что заблокирован, а второй принадлежит другому процессу, предпочтение может быть отдано первому потоку.
Другой важный фактор заключается в том, что потоки, реализованные на уровне пользователя, могут использовать планировщик потоков, учитывающий особенности приложения. Рассмотрим, к примеру, веб-сервер. Предположим, что рабочий поток был только что заблокирован, а поток диспетчера и два рабочих потока находятся в состоянии готовности. Какой из потоков должен быть запущен следующим? Система поддержки исполнения программ, владеющая информацией о том, чем занимаются все потоки, может без труда выбрать следующим для запуска диспетчер, чтобы тот запустил следующий рабочий процесс. Эта стратегия доводит до максимума степень параллелизма в среде, где рабочие потоки часто блокируются на дисковых операциях ввода-вывода. Когда потоки реализованы на уровне ядра, само ядро никогда не будет обладать информацией, чем занимается каждый поток (хотя им могут быть присвоены разные приоритеты). Но в целом планировщики потоков, учитывающие особенности приложений, могут лучше подстроиться под приложение, чем ядро.
6. Приоритетное планирование потоков в ОС Windows
В ОС Windows реализовано вытесняющее приоритетное планирование, когда каждому потоку присваивается определенное числовое значение – приоритет, в соответствии с которым ему выделяется процессор.
В системе предусмотрено 32 уровня приоритетов. Шестнадцать значений приоритетов (16-31) соответствуют группе приоритетов реального времени, пятнадцать значений (1-15) предназначены для обычных потоков, и значение 0 зарезервировано для системного потока обнуления страниц (см. рис. 2).

40
Рис. 2. Приоритеты потоков
Чтобы избавить пользователя от необходимости запоминать числовые значение приоритетов и иметь возможность модифицировать планировщик, разработчики введи в систему слой абстрагирования приоритетов. Например, класс приоритета для всех потоков конкретного процесса можно задать с помощью констант-параметров функции
SetPriorutyClass, которые могут иметь следующие значения:
• реального времени (REALTIME_PRIORITY_CLASS),
• высокий (HIGH_PTIORITY_CLASS),
• выше нормы (ABOVE_NORMAL_PRIORITY_CLASS),
• нормальный (NORMAL_PRIOROTY_CLASS),
• ниже нормы (BELOW_NORMAL_PRIORITY_CLASS),
• неработающий (IDLE_PRIORITY_CLASS).
Относительный приоритет потока устанавливается аналогичными параметрами функции
SetThreadPriority:
• критичный по времени (THREAD_PRIORITY_TIME_CRITICAL),
• самый высокий (THREAD_PRIORITY_HIGHEST),
• выше нормы (THRAD_PRIORITY_ABOVE_NORMAL),
• нормальный (THREAD_PRIORITY_NORMAL),
• ниже нормы (THRAD_PRIORITY_BELOW_NORMAL),
• самый низкий (THREAD_PRIORITY_LOWEST),
• неработающий (THREAD_PRIORITY_IDLE).
Совокупность из шести классов приоритетов процессов и семи классов приоритетов потоков образует 42 возможные комбинации и позволяет сформировать так называемый базовый приоритет потока (см. табл. 1).
Таблица 1. Формирование базового приоритета из класса приоритета процесса и относительного приоритета потока
Приоритеты потоков
К
ла сс ы при ор ит ет ов проц ес сов
Кр ити чны й ко вр ем ен и
С
ам ый в
ы сок ий
В
ыше н
орм ы
Норм аль ный
Ни же н
орм ы
С
ам ый н
из ки й
Не ра бот аю щи й
Неработающий
15 6
5 4
3 2
1
Ниже нормы
15 8
7 6
5 4
1
Нормальный
15 10 9
8 7
6 1
Выше нормы
15 12 11 10 9 8
1
Высокий
15 15 14 13 12 11 1
Реального времени 15 26 25 24 23 22 16
Базовый приоритет процесса и первичного потока по умолчанию равен значению из середины диапазонов приоритетов процессов (24, 13, 10, 8, 6 или 4). Смена приоритета процесса влечет за собой смену приоритетов всех его потоков, при этом их относительные приоритеты остаются без изменений.
0 1
15 16 31 приоритеты обычных потоков приоритеты потоков реального времени

41
Лекция 5