2. Изучить алгоритмы планирования (кроме FCFS, RR)

Раздел:
Тема:
Количество часов:
Задачи:
Порядок выполнения работы:

Shortest-Job-First (SJF)

При рассмотрении алгоритмов FCFS и RR мы видели, насколько существенным для них является порядок расположения процессов в очереди процессов, готовых к исполнению. Если короткие задачи расположены в очереди ближе к ее началу, то общая производительность этих алгоритмов значительно возрастает. Если бы мы знали время следующих CPU burst для процессов, находящихся в состоянии готовность, то могли бы выбрать для исполнения не процесс из начала очереди, а процесс с минимальной длительностью CPU burst. Если же таких процессов два или больше, то для выбора одного из них можно использовать уже известный нам алгоритм FCFS. Квантование времени при этом не применяется. Описанный алгоритм получил название "кратчайшая работа первой" или Shortest Job First (SJF).

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

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

Рассмотрим пример работы невытесняющего алгоритма SJF. Пусть в состоянии готовность находятся четыре процесса, p0, p1, p2 и p3, для которых известны времена их очередных CPU burst. Эти времена приведены в таблице 3.4. Как и прежде, будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка CPU burst, что процессы не совершают операций ввода-вывода и что временем переключения контекста можно пренебречь.

Таблица 3.4.

Процесс	Продолжительность очередного CPU burst
p0	5
p1	3
p2	7
p3	1

Основы операционных систем 34

При использовании невытесняющего алгоритма SJF первым для исполнения будет выбран процесс p3, имеющий наименьшее значение продолжительности очередного CPU burst. После его завершения для исполнения выбирается процесс p1, затем p0 и, наконец, p2. Эта картина отражена в таблице 3.5.

Таблица 3.5.

Время	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
p0	Г	Г	Г	Г	И	И	И	И	И
p1	Г	И	И	И
p2	Г	Г	Г	Г	Г	Г	Г	Г	Г	И	И	И	И	И	И	И
p3	И

Как мы видим, среднее время ожидания для алгоритма SJF составляет (4 + 1 + 9 + 0)/4 = 3,5 единицы времени. Легко посчитать, что для алгоритма FCFS при порядке процессов p0, p1, p2, p3 эта величина будет равняться (0 + 5 + 8 + 15)/4 = 7 единицам времени, т. е. будет в два раза больше, чем для алгоритма SJF. Можно показать, что для заданного набора процессов (если в очереди не появляются новые процессы) алгоритм SJF является оптимальным с точки зрения минимизации среднего времени ожидания среди класса невытесняющих алгоритмов.

Для рассмотрения примера вытесняющего SJF планирования мы возьмем ряд процессов p0, p1, p2 и p3 с различными временами CPU burst и различными моментами их появления в очереди процессов, готовых к исполнению (см. табл. 3.6.).

Таблица 3.6.

Процесс	Время появления в очереди	Продолжительность CPU burst
p0	0	6
p1	2	2
p2	6	7
p3	0	5

В начальный момент времени в состоянии готовность находятся только два процесса, p0 и p3. Меньшее время очередного CPU burst оказывается у процесса p3, поэтому он и выбирается для исполнения (см. таблицу 3.7.). По прошествии 2 единиц времени в систему поступает процесс p1. Время его CPU burst меньше, чем остаток CPU burst у процесса p3, который вытесняется из состояния исполнение и переводится в состояние готовность. По прошествии еще 2 единиц времени процесс p1 завершается, и для исполнения вновь выбирается процесс p3. В момент времени t = 6 в очереди процессов, готовых к исполнению, появляется процесс p2, но поскольку ему для работы нужно 7 единиц времени, а процессу p3 осталось трудиться всего 1 единицу времени, то процесс p3 остается в состоянии исполнение. После его завершения в момент времени t = 7 в очереди находятся процессы p0 и p2, из которых выбирается процесс p0. Наконец, последним получит возможность выполняться процесс p2.

Таблица 3.7.

Время	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
p0	Г	Г	Г	Г	Г	Г	Г	И	И	И	И	И	И
p1		И	И
p2						Г	Г	Г	Г	Г	Г	Г	Г	И	И	И	И	И	И	И
p3	И	И	Г	Г	И	И	И

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

Основы операционных систем 35

может не досчитаться до конца. Таким образом, в пакетных системах решение задачи оценки времени использования процессора перекладывается на плечи пользователя. При краткосрочном планировании мы можем делать только прогноз длительности следующего CPU burst, исходя из предыстории работы процесса. Пусть τ(n) -- величина n-го CPU burst, T(n + 1) -- предсказываемое значение для n + 1-го CPU burst, α -- некоторая величина в диапазоне от 0 до 1.

Определим рекуррентное соотношение: T(n+1) = α * τ(n) + (1-α) * T(n)

T(0) положим произвольной константой. Первое слагаемое учитывает последнее поведение процесса, тогда как второе слагаемое учитывает его предысторию. При α = 0 мы перестаем следить за последним поведением процесса, фактически полагая: T(n) = T(n+1) = ... = T(0)

т. е. оценивая все CPU burst одинаково, исходя из некоторого начального предположения.

Положив α = 1, мы забываем о предыстории процесса. В этом случае мы полагаем, что время очередного CPU burst будет совпадать со временем последнего CPU burst: T(n+1) = τ(n)

Обычно выбирают α = 1/2 для равноценного учета последнего поведения и предыстории. Надо отметить, что такой выбор удобен и для быстрой организации вычисления оценки T(n + 1). Для подсчета новой оценки нужно взять старую оценку, сложить с измеренным временем CPU burst и полученную сумму разделить на 2, например, сдвинув ее на 1 бит вправо. Полученные оценки T(n + 1) применяются как продолжительности очередных промежутков времени непрерывного использования процессора для краткосрочного SJF-планирования.

Гарантированное планирование

При интерактивной работе N пользователей в вычислительной системе можно применить алгоритм планирования, который гарантирует, что каждый из пользователей будет иметь в своем распоряжении ~1/N часть процессорного времени. Пронумеруем всех пользователей от 1 до N. Для каждого пользователя с номером i введем две величины: Ti -- время нахождения пользователя в системе или, другими словами, длительность сеанса его общения с машиной и τi -- суммарное процессорное время уже выделенное всем его процессам в течение сеанса. Справедливым для пользователя было бы получение Ti/N процессорного времени. Если τi << Ti/N то i-й пользователь несправедливо обделен процессорным временем. Если же τi >> Ti/N то система явно благоволит к пользователю с номером i. Вычислим для процессов каждого пользователя значение коэффициента справедливости: τi * N / Ti и будем предоставлять очередной квант времени готовому процессу с наименьшей величиной этого отношения. Предложенный алгоритм называют алгоритмом гарантированного планирования. К недостаткам этого алгоритма можно отнести невозможность предугадать поведение пользователей. Если некоторый пользователь отправится на пару часов пообедать и поспать, не прерывая сеанса работы, то по возвращении его процессы будут получать неоправданно много процессорного времени.

Основы операционных систем 36

Приоритетное планирование

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

Алгоритмы назначения приоритетов процессов могут опираться как на внутренние параметры, связанные с происходящим внутри вычислительной системы, так и на внешние по отношению к ней. К внутренним параметрам относятся различные количественные и качественные характеристики процесса такие как: ограничения по времени использования процессора, требования к размеру памяти, число открытых файлов и используемых устройств ввода-вывода, отношение средних продолжительностей I/O burst к CPU burst и т. д. Алгоритмы SJF и гарантированного планирования используют внутренние параметры. В качестве внешних параметров могут выступать важность процесса для достижения каких-либо целей, стоимость оплаченного процессорного времени и другие политические факторы. Высокий внешний приоритет может быть присвоен задаче лектора или того, кто заплатил $100 за работу в течение одного часа.

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

Пусть в очередь процессов, находящихся в состоянии готовность, поступают те же процессы, что и в примере для вытесняющего алгоритма SJF, только им дополнительно еще присвоены приоритеты (см. табл. 3.8.). В вычислительных системах не существует определенного соглашения, какое значение приоритета -- 1 или 4 считать более приоритетным. Во избежание путаницы, во всех наших примерах мы будем предполагать, что большее значение соответствует меньшему приоритету, т. е. наиболее приоритетным в нашем примере является процесс p3, а наименее приоритетным -- процесс p0.

Таблица 3.8.

Процесс	Время появления в очереди	Продолжительность очередного CPU burst	Приоритет
p0	0	6	4
p1	2	2	3
p2	6	7	2
p3	0	5	1

Как будут вести себя процессы при использовании невытесняющего приоритетного планирования? Первым для выполнения в момент времени t = 0 выбирается процесс p3, как обладающий наивысшим приоритетом. После его завершения в момент времени t = 5 в очереди процессов, готовых к исполнению, окажутся два процесса p0 и p1. Больший приоритет из них у процесса p1, он и начнет выполняться (см. табл. 3.9.). Затем в момент времени t = 8 для исполнения будет избран процесс p2, и лишь потом -- процесс p0.

Таблица 3.9.

Время	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
p0	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г	И	И	И	И	И
p1	Г	Г	Г	И	И
p2								Г	И	И	И	И	И	И	И	И
p3	И	И	И	И	И

Основы операционных систем 37

Иным будет предоставление процессора процессам в случае вытесняющего приоритетного планирования (см. табл. 3.10.). Первым, как и в предыдущем случае, начнет исполняться процесс p3, а по его окончании -- процесс p1. Однако в момент времени t = 6 он будет вытеснен процессом p2 и продолжит свое выполнение только в момент времени t = 13. Последним, как и раньше, будет исполняться процесс p0.

Таблица 3.10.

Время	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
p0	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г	И	И	И	И	И
p1	Г	Г	Г	И	Г	Г	Г	Г	Г	Г	Г	И
p2						И	И	И	И	И	И	И
p3	И	И	И	И	И

В рассмотренном выше примере приоритеты процессов с течением времени не изменялись. Такие приоритеты принято называть статическими. Механизмы статической приоритетности легко реализовать, и они сопряжены с относительно небольшими издержками на выбор наиболее приоритетного процесса. Однако статические приоритеты не реагируют на изменения ситуации в вычислительной системе, которые могут сделать желательной корректировку порядка исполнения процессов. Более гибкими являются динамические приоритеты процессов, изменяющие свои значения по ходу исполнения процессов. Начальное значение динамического приоритета, присвоенное процессу, действует в течение лишь короткого периода времени, после чего ему назначается новое, более подходящее значение. Изменение динамического приоритета процесса является единственной операцией над процессами, которую мы до сих пор не рассмотрели. Как правило, изменение приоритета процессов проводится согласованно с совершением каких-либо других операций: при рождении нового процесса, при разблокировке или блокировании процесса, по истечении определенного кванта времени или по завершении процесса. Примерами алгоритмов с динамическими приоритетами являются алгоритм SJF и алгоритм гарантированного планирования.

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

Главная проблема приоритетного планирования заключается в том, что при ненадлежащем выборе механизма назначения и изменения приоритетов низкоприоритетные процессы могут не запускаться неопределенно долгое время. Обычно случается одно из двух. Или они все же дожидаются своей очереди на исполнение (в девять часов утра в воскресенье, когда все приличные программисты ложатся спать). Или вычислительную систему приходится выключать, и они теряются (при остановке IBM 7094 в Массачусетском технологическом институте в 1973 году были найдены процессы, запущенные в 1967 году и ни разу с тех пор не исполнявшиеся). Решение этой проблемы может быть достигнуто с помощью увеличения со временем значения приоритета процесса, находящегося в состоянии готовность. Пусть изначально процессам присваиваются приоритеты от 128 до 255. Каждый раз по истечении определенного промежутка времени значения приоритетов готовых процессов уменьшаются на 1. Процессу, побывавшему в состоянии исполнение, присваивается первоначальное значение приоритета. Даже такая грубая схема гарантирует, что любому процессу в разумные сроки будет предоставлено право на исполнение.

Многоуровневые очереди (Multilevel Queue)

Для систем, в которых процессы могут быть легко рассортированы по разным группам, был разработан другой класс алгоритмов планирования. Для каждой группы процессов создается своя очередь процессов, находящихся в состоянии готовность (см. рис. 3.5). Этим очередям приписываются фиксированные приоритеты. Например, приоритет очереди системных процессов устанавливается выше, чем приоритет очередей пользовательских процессов. А приоритет очереди процессов, запущенных студентами, ниже, чем для очереди процессов, запущенных преподавателями. Это значит, что ни один пользовательский процесс не будет выбран для исполнения, пока есть хоть один готовый системный процесс, и ни один студенческий процесс не получит в свое распоряжение процессор, если есть процессы преподавателей, готовые к исполнению. Внутри этих очередей для планирования могут применяться самые разные алгоритмы. Так, например, для больших счетных процессов, не требующих взаимодействия с пользователем (фоновых процессов), может использоваться алгоритм FCFS, а для интерактивных процессов -- алгоритм

Основы операционных систем 38

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

+-----------------+
| Очередь 0 (RR)  |<-- Высший приоритет
| Системные       |
+-----------------+
| Очередь 1 (RR)  |
| Интерактивные   |
+-----------------+
| Очередь 2 (FCFS)|
| Фоновые         |
+-----------------+
| Очередь 3 (FCFS)|<-- Низший приоритет
| Пакетные        |
+-----------------+

Рис. 3.5. Несколько очередей планирования

Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)

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

Для простоты рассмотрим ситуацию, когда процессы в состоянии готовность организованы в 4 очереди, как на рисунке 3.6. Планирование процессов между очередями осуществляется на основе вытесняющего приоритетного механизма. Чем выше на рисунке располагается очередь, тем выше ее приоритет. Процессы в очереди 1 не могут исполняться, если в очереди 0 есть хотя бы один процесс. Процессы в очереди 2 не будут выбраны для выполнения, пока есть хоть один процесс в очередях 0 и 1. И наконец, процесс в очереди 3 может получить процессор в свое распоряжение только тогда, когда очереди 0, 1 и 2 пусты.

Если при работе процесса появляется другой процесс в какой-либо более приоритетной очереди, исполняющийся процесс вытесняется новым. Планирование процессов внутри очередей 0--2 осуществляется с использованием алгоритма RR, планирование процессов в очереди 3 основывается на алгоритме FCFS.

Основы операционных систем 39

+-----------------+  Квант 8  +-----------------+  Квант 16 +-----------------+  Квант 32 +-----------------+
| Очередь 0 (RR)  |<----------| Очередь 1 (RR)  |<----------| Очередь 2 (RR)  |<----------| Очередь 3 (FCFS)|
| Высший приор.   |           |                 |           |                 |           | Низший приор.  |
+-----------------+           +-----------------+           +-----------------+           +-----------------+
      ^                               ^                               ^                               ^
      |                               |                               |                               |
      +-------------------------------+-------------------------------+-------------------------------+
                                      Миграция процессов при исчерпании кванта времени

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

Родившийся процесс поступает в очередь 0. При выборе на исполнение он получает в свое распоряжение квант времени размером 8 единиц. Если продолжительность его CPU burst меньше этого кванта времени, процесс остается в очереди 0. В противном случае он переходит в очередь 1. Для процессов из очереди 1 квант времени имеет величину 16. Если процесс не укладывается в это время, он переходит в очередь 2. Если укладывается -- остается в очереди 1. В очереди 2 величина кванта времени составляет 32 единицы. Если для непрерывной работы процесса и этого мало, процесс поступает в очередь 3, для которой квантование времени не применяется и, при отсутствии готовых процессов в других очередях, может исполняться до окончания своего CPU burst. Чем больше значение продолжительности CPU burst, тем в менее приоритетную очередь попадает процесс, но тем на большее процессорное время он может рассчитывать.

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

Миграция процессов в обратном направлении может осуществляться по различным принципам. Например, после завершения ожидания ввода с клавиатуры процессы из очередей 1, 2 и 3 могут помещаться в очередь 0, после завершения дисковых операций ввода-вывода процессы из очередей 2 и 3 могут помещаться в очередь 1, а после завершения ожидания всех других событий -- из очереди 3 в очередь 2. Перемещение процессов из очередей с низкими приоритетами в очереди с высокими приоритетами позволяет более полно учитывать изменение поведения процессов с течением времени.

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

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

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

На этом мы прекращаем рассмотрение различных алгоритмов планирования процессов, ибо, как было сказано: "Нельзя объять необъятное".

Заключение

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

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

Основы операционных систем 40

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

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

Цель работы

Изучить основные алгоритмы планирования процессов, понять их принципы работы, сравнить эффективность, а также получить практические навыки анализа и настройки планировщика в GNU/Linux.

---

Часть 1. Теоретический обзор

1. Введение

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

Планировщики делятся по:

• Длительности действия: долгосрочное, среднесрочное, краткосрочное.
• Режиму работы: вытесняющий (процесс может быть прерван) и невытесняющий (процесс отдает CPU добровольно).

---

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

1. FCFS (First-Come, First-Served)

• Простой, невытесняющий.
• Процессы выполняются в порядке поступления.
• Недостаток: конвоя (long process в начале блокирует короткие).

2. RR (Round Robin)

• Вытесняющий, используется в системах разделения времени.
• Каждый процесс получает квант времени (например, 10 мс).
• При истечении кванта процесс переходит в конец очереди.
• Плюс: справедливость. Минус: высокие накладные расходы при малом кванте.

3. SJF (Shortest Job First)

• Невытесняющий или вытесняющий (SRTF — Shortest Remaining Time First).
• Выбирается процесс с наименьшей оценкой CPU burst.
• Оптимален по среднему времени ожидания (для невытесняющего случая).
• Проблема: невозможно точно знать длительность CPU burst.

Как оценить CPU burst?
Используется экспоненциальное сглаживание:
[ T(n+1) = \alpha \cdot \tau(n) + (1 - \alpha) \cdot T(n) ] где:

• ( T(n) ) — предыдущая оценка,
• ( \tau(n) ) — фактическая длительность n-го CPU burst,
• ( \alpha ) — вес (обычно 0.5).

---

4. Приоритетное планирование

• Каждому процессу присваивается приоритет.
• Выполняется процесс с наивысшим приоритетом (в нашем случае — меньшее число = выше приоритет).
• Может быть вытесняющим или невытесняющим.
• Проблема: голодание низкоприоритетных процессов.
• Решение: старение (aging) — постепенное повышение приоритета ожидающих процессов.

Примеры приоритетов:

• Внутренние: длина CPU burst, отношение I/O к CPU.
• Внешние: оплата, важность задачи.

---

5. Гарантированное планирование

• Цель: каждый пользователь получает ~1/N процессорного времени.
• Приоритет = ( \frac{\tau_i \cdot N}{T_i} ), где:
  • ( \tau_i ) — CPU время, выделенное пользователю,
  • ( T_i ) — общее время его сессии.
• Чем меньше коэффициент — тем выше приоритет.
• Подходит для многопользовательских систем.

---

6. Многоуровневые очереди (Multilevel Queue)

• Процессы делятся на группы (например: системные, интерактивные, фоновые).
• Каждая группа — своя очередь с фиксированным приоритетом.
• Внутри очередей — свой алгоритм (RR, FCFS и т.д.).

Пример структуры:

Очередь 0: системные процессы (RR)
Очередь 1: интерактивные (RR)
Очередь 2: фоновые (FCFS)
Очередь 3: пакетные (FCFS)

---

7. Многоуровневые очереди с обратной связью (MLFQ)

• Процессы могут перемещаться между очередями.
• Цель: дать коротким/интерактивным процессам высокий приоритет, а долгим — низкий.
• Пример:
  • Новый процесс → очередь 0 (квант 8).
  • Если не уложился → переходит в очередь 1 (квант 16).
  • И так далее.
  • После I/O — возвращается в высокоприоритетную очередь.

MLFQ — наиболее гибкий, но сложный в настройке.

---

Часть 2. Практическое задание (GNU/Linux)

Задание 1. Анализ текущего планировщика

1. Узнайте, какой планировщик используется по умолчанию:

   cat /sys/block/sda/queue/scheduler

   Примечание: это планировщик дискового ввода-вывода, но он тоже важен. Для CPU планировщика в Linux используется CFS (Completely Fair Scheduler) — современная реализация идеи гарантированного планирования.

2. Посмотрите, какие процессы работают и их приоритеты:

   ps -eo pid,ppid,cmd,pcpu,ni --sort=-pcpu | head -10

   • NI — nice-уровень (от -20 до 19). Чем меньше — тем выше приоритет.
   • PCPU — использование CPU.

3. Запустите процесс с низким приоритетом:

   nice -n 10 sleep 60 &

   Проверьте его nice:

   ps -o pid,cmd,ni -C sleep

4. Повысьте приоритет работающего процесса:

   renice -5 <PID>

---

Задание 2. Моделирование SJF (ручное)

Даны процессы:

Процесс	Время поступления	CPU burst
P1	0	8
P2	1	4
P3	2	2
P4	3	1

Задача:

1. Постройте временную диаграмму выполнения для вытесняющего SJF (SRTF).
2. Рассчитайте:
   • Время завершения каждого процесса.
   • Время ожидания (Waiting Time = время завершения – время поступления – CPU burst).
   • Среднее время ожидания.

Подсказка: на каждом шаге выбирайте процесс с наименьшим оставшимся временем выполнения.

---

Задание 3. Сравнение алгоритмов

Для тех же процессов постройте диаграммы и рассчитайте среднее время ожидания для:

• FCFS
• RR (квант = 2)
• SJF (вытесняющий)

Сравните результаты. Какой алгоритм оказался самым эффективным по среднему времени ожидания?

---

Задание 4. Эксперимент с nice и приоритетами

1. Создайте два скрипта:

   #!/bin/bash
   # cpu_intensive.sh
   for i in {1..1000000}; do
     expr $i + 1 > /dev/null
   done

   Сохраните как cpu_intensive.sh, сделайте исполняемым:

   chmod +x cpu_intensive.sh

2. Запустите два процесса:

   nice -n 19 ./cpu_intensive.sh &
   nice -n 0 ./cpu_intensive.sh &

3. Откройте второй терминал и следите за загрузкой:

   top

   Наблюдайте, какой процесс получает больше CPU времени.

4. Сделайте вывод: как влияет nice на распределение ресурсов?

---

Часть 3. Контрольные вопросы

1. В чем разница между вытесняющим и невытесняющим планированием?
2. Почему SJF считается оптимальным по среднему времени ожидания?
3. Как оценивается длина следующего CPU burst в реальных системах?
4. Что такое "голодание процессов"? Как его избежать?
5. Чем отличается MLFQ от обычной многоуровневой очереди?
6. Как в Linux управлять приоритетом процесса? Какие команды используются?
7. Что такое CFS в Linux? Как он связан с идеей "гарантированного планирования"?

---

Часть 4. Дополнительное задание (по желанию)

Напишите простую программу на Python, которая моделирует работу планировщика SRTF для заданного набора процессов. Программа должна:

• Принимать список процессов (PID, время поступления, CPU burst).
• Выводить порядок выполнения.
• Строить Gantt-диаграмму (в текстовом виде).
• Рассчитывать среднее время ожидания.

Пример входных данных:

processes = [
    {'pid': 'P1', 'arrival': 0, 'burst': 8},
    {'pid': 'P2', 'arrival': 1, 'burst': 4},
    {'pid': 'P3', 'arrival': 2, 'burst': 2},
    {'pid': 'P4', 'arrival': 3, 'burst': 1}
]

---

Вывод

Алгоритмы планирования — фундаментальная часть ОС, определяющая её отзывчивость, производительность и справедливость. От простого FCFS до сложного MLFQ — выбор зависит от типа системы (интерактивная, пакетная, реального времени). Современные ОС (включая Linux) используют адаптивные, гибридные подходы (например, CFS), сочетающие идеи SJF, приоритетов и справедливого распределения.

---

Литература и ресурсы

• Silberschatz A., Galvin P., Gagne G. Operating System Concepts
• Документация ядра Linux: https://www.kernel.org
• man nice, man renice, man ps

Введение

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

Теоретическая часть

Вопросы для самопроверки

1. В чем заключается основная идея алгоритма Shortest-Job-First (SJF)? Чем отличается невытесняющий SJF от вытесняющего?

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

3. Как решается проблема прогнозирования продолжительности следующего CPU burst в краткосрочном планировании? Опишите рекуррентное соотношение для вычисления T(n+1).

4. Что представляет собой алгоритм гарантированного планирования? Как вычисляется коэффициент справедливости?

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

6. В чем заключается проблема "голодания" в приоритетном планировании и как ее можно решить?

7. Опишите принцип работы многоуровневых очередей (Multilevel Queue). Какие преимущества дает такой подход?

8. Чем отличается многоуровневые очереди с обратной связью (Multilevel Feedback Queue) от обычных многоуровневых очередей? Как происходит миграция процессов между очередями?

Расчетная часть

Задача 1. Невытесняющий SJF

Даны четыре процесса с указанными временами CPU burst:

Процесс	Продолжительность очередного CPU burst
p0	8
p1	4
p2	9
p3	5

1. Постройте диаграмму Ганта для невытесняющего алгоритма SJF.
2. Вычислите среднее время ожидания процессов.
3. Сравните результат с алгоритмом FCFS при порядке процессов p0, p1, p2, p3.

Задача 2. Вытесняющий SJF

Даны процессы с временами появления и продолжительностями CPU burst:

Процесс	Время появления в очереди	Продолжительность CPU burst
p0	0	7
p1	2	4
p2	4	1
p3	5	4

1. Постройте диаграмму Ганта для вытесняющего алгоритма SJF.
2. Вычислите среднее время ожидания процессов.
3. Какой процесс будет выполняться в моменты времени t=3, t=6 и t=8?

Задача 3. Приоритетное планирование

Даны процессы с временами появления, продолжительностями CPU burst и приоритетами (меньшее значение означает более высокий приоритет):

Процесс	Время появления	Продолжительность CPU burst	Приоритет
p0	0	6	3
p1	1	3	1
p2	3	4	4
p3	5	2	2

1. Постройте диаграмму Ганта для невытесняющего приоритетного планирования.
2. Постройте диаграмму Ганта для вытесняющего приоритетного планирования.
3. Вычислите среднее время ожидания для обоих случаев.

Задача 4. Многоуровневые очереди с обратной связью

Рассмотрим систему с четырьмя очередями, где:

• Очередь 0: квант времени 4, алгоритм RR
• Очередь 1: квант времени 8, алгоритм RR
• Очередь 2: квант времени 16, алгоритм RR
• Очередь 3: алгоритм FCFS

Правила миграции:

• Процесс переходит в следующую очередь, если исчерпал квант времени
• После операции ввода-вывода процесс перемещается в очередь 0

Даны процессы:

• p0: появляется в момент 0, CPU burst = 5
• p1: появляется в момент 2, CPU burst = 12
• p2: появляется в момент 6, CPU burst = 3
• p3: появляется в момент 10, CPU burst = 25

1. Постройте диаграмму Ганта для данной системы.
2. Определите, в каких очередях находились процессы в разные моменты времени.
3. Какой процесс получит процессор в моменты времени t=7, t=15 и t=22?

Практическая часть (GNU/Linux)

Задание 1. Изучение приоритетов процессов

1. Откройте терминал и выполните команду ps -el для просмотра списка всех процессов.
2. Обратите внимание на колонки PRI (приоритет) и NI (nice value).
3. Найдите процесс с наименьшим и наибольшим значением приоритета (PRI).
4. Объясните, как связаны значения PRI и NI. Какой диапазон значений NI допустим в системе?

Задание 2. Работа с nice и renice

1. Запустите процесс с низким приоритетом:

   nice -n 10 sleep 60 &

   Обратите внимание на символ & — он запускает процесс в фоновом режиме.

2. Запустите еще один процесс с высоким приоритетом (требуются права суперпользователя):

   sudo nice -n -5 sleep 60 &

3. Проверьте приоритеты запущенных процессов с помощью:

   ps -o pid,nice,cmd -C sleep

4. Измените приоритет одного из процессов с помощью renice:

   renice 5 -p <PID>

   где <PID> — идентификатор процесса, который можно найти в выводе предыдущей команды.

5. Проверьте, что приоритет изменился:

   ps -o pid,nice,cmd -p <PID>

6. Напишите вывод: как изменение приоритета влияет на распределение процессорного времени между процессами?

Задание 3. Работа с планировщиком реального времени (chrt)

1. Установите утилиту chrt (если не установлена):

   sudo apt-get install util-linux

2. Посмотрите доступные политики планирования:

   chrt -m

3. Запустите процесс с политикой SCHED_FIFO (реального времени):

   chrt -f 50 sleep 30 &

   Здесь 50 — приоритет в диапазоне от 1 до 99.

4. Проверьте политику и приоритет процесса:

   chrt -p <PID>

5. Попробуйте запустить процесс с политикой SCHED_RR:

   chrt -r 30 sleep 30 &

6. Напишите вывод: в чем разница между политиками SCHED_FIFO и SCHED_RR? Когда целесообразно использовать каждую из них?

Задание 4. Анализ использования процессора

1. Установите утилиту htop (если не установлена):

   sudo apt-get install htop

2. Запустите htop и изучите информацию о процессах:

   • Какие процессы используют больше всего процессорного времени?
   • Как распределены приоритеты среди процессов?

3. С помощью htop найдите процессы с высоким и низким приоритетом.

4. Создайте нагрузку на процессор с помощью утилиты stress:

   sudo apt-get install stress
   stress --cpu 2 --timeout 120 &

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

6. Напишите вывод: как система реагирует на высокую загрузку процессора? Как меняется поведение планировщика?

Заключение

1. Какой алгоритм планирования, по вашему мнению, наиболее эффективен для интерактивных систем? Обоснуйте свой ответ.

2. В каких случаях использование алгоритма SJF может быть нецелесообразным? Почему?

3. Как вы думаете, какие алгоритмы планирования используются в современных десктопных системах (например, Ubuntu, Fedora)? Какие алгоритмы используются в серверных системах?

4. Какие ограничения имеют алгоритмы с динамическими приоритетами по сравнению со статическими? Приведите примеры ситуаций, когда динамические приоритеты дают преимущества.

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

Дополнительные материалы для изучения

1. Документация по планировщику в ядре Linux: man 7 sched
2. Статья "Completely Fair Scheduler" (CFS) — современный планировщик в ядре Linux
3. Документация по использованию chrt: man chrt
4. Статья "Understanding the Linux Kernel" — глава о планировании процессов

Примечание: При выполнении практической части работы будьте внимательны при изменении приоритетов системных процессов. Изменение приоритетов критически важных процессов может привести к нестабильной работе системы. Все эксперименты с приоритетами реального времени следует проводить на тестовых процессах (например, sleep, stress).