Интервальный таймер или прерывающие часы-будильник

 

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

 

Операционная система устанавливает часы или интервальный таймер с целью генерации сигнала прерывания в некоторый конкретный момент времени в будущем (или по истечении некоторого интервала времени в будущем). После прерывания ЦП передается в распоряжение следующего процесса. Этот процесс сохраняет управление центральным процессором до тех пор, пока он добровольно не освободит ЦП, или не произойдет временное прерывание или какое-то другое прерывание не потребует внимания ЦП. Если работает программа пользователя и происходит временное прерывание, это прерывание вызывает включение в работу операционной системы. Операционная система при этом решает, какому процессу следует предоставить далее ЦП.

 

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

 

Приоритеты. Планирование по сроку завершения.

 

Приоритеты

 

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

 

11.6.1. Статические и динамические приоритеты

 

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

 

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

 

 

11.7 Планирование по сроку завершения

 

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

 

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

 

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

 

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

 

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

 

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

 

11.8 Планирование по принципу FIFO («first in - first out» — «первый пришедший обслуживается первым»)

 

По-видимому, наиболее простой дисциплиной планирования является принцип FIFO («первый пришедший обслуживается первым») (рис. 11.2). Центральный процессор предоставляется процессам в порядке их прихода в очередь готовности. После того, как процесс получает ЦП в свое распоряжение, он выполняется до завершения.

 

 

Планирование по принципу FIFO. Размер кванта.

 

Планирование по принципу FIFO («первый пришедший обслуживается первым»)

 

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

 

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

 

Планирование по принципам SJF, SRT и HRN.

Планирование по принципу SJF («кратчайшее задание — первым»)

Принцип SJF («кратчайшее задание — первым») — это дисциплина планирования без переключения, согласно которой следующим для выполнения выбирается ожидающее задание (или процесс) с минимальным оценочным рабочим временем, остающимся до завершения. Принцип SJF обеспечивает уменьшение среднего времени ожидания по сравнению с дисциплиной FIFO. Однако времена ожидания при этом колеблются в более широких пределах (т. е. менее предсказуемы), чем в случае FIFO, особенно при больших заданиях.

 

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

 

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

 

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

 

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

 

Планирование по принципу SRT («по наименьшему остающемуся времени»)

 

Принцип SRT — это аналог принципа SJF, но с переключением, применимый в системах с разделением времени. По принципу SRT всегда выполняется процесс, имеющий минимальное оценочное время до завершения, причем с учетом новых поступающих процессов. По принципу SJF задание, которое запущено в работу, выполняется до завершения. По принципу SRT выполняющийся процесс может быть прерван при поступлении нового процесса, имеющего более короткое оценочное время работы. Чтобы механизм SRT был эффективным, опять-таки нужны достаточно точные оценки будущего, причем разработчик системы должен позаботиться о мерах против неправильного использования прикладными программистами особенностей стратегий планирования.

 

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

 

Реализация принципа SRT требует, чтобы регистрировались истекшие времена обслуживания, а это приводит к увеличению накладных расходов. Теоретически принцип SRT обеспечивает минимальные времена ожидания. Однако из-за издержек на переключения может оказаться так, что в определенных ситуациях в действительности лучшие показатели будет иметь SJF.

 

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

 

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

 

Планирование по принципу HRN («по наибольшему относительному времени реакции»)

 

Стратегия планирования HRN (highest-response-ratio-next, «по наибольшему относительному времени ответа») компенсирует некоторые из слабостей, присущих дисциплине SJF, в частности чрезмерное предубеждение против длинных заданий и чрезмерную благосклонность по отношению к коротким новым заданиям. HRN — это дисциплина планирования без переключения, согласно которой приоритет каждого задания является не только функцией времени обслуживания этого задания, но также времени, затраченного заданием на ожидание обслуживания. После того как задание получает в свое распоряжение ЦП, оно выполняется до завершения. Динамические приоритеты при дисциплине HRN вычисляются по формуле

 

Приоритет = (время ожидания + время обслуживания)/(время обслуживания)

 

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

 

время ожидания + время обслуживания

 

есть время ответа системы для данного задания, если бы это задание инициировалось немедленно.