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

Вытесняющее и невытесняющее планирование

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

1. Когда процесс переводится из состояния исполнение в состояние закончил исполнение.

2. Когда процесс переводится из состояния исполнение в состояние ожидание.

3. Когда процесс переводится из состояния исполнение в состояние готовность (например, после прерывания от таймера).

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

В случаях 1 и 2 процесс, находившийся в состоянии исполнение, не может дальше исполняться, и операционная система вынуждена осуществлять планирование выбирая новый процесс для выполнения. В случаях 3 и 4 планирование может как проводиться, так и не проводиться, планировщик не вынужден обязательно принимать решение о выборе процесса для выполнения, процесс, находившийся в состоянии исполнение может просто продолжить свою работу. Если в операционной системе планирование осуществляется только в вынужденных ситуациях, говорят, что имеет место невытесняющее (nonpreemptive) планирование. Если планировщик принимает и вынужденные, и невынужденные решения, говорят о вытесняющем (preemptive) планировании. Термин «вытесняющее планирование» возник потому, что исполняющийся процесс помимо своей воли может быть вытеснен из состояния исполнение другим процессом.

Невытесняющее планирование используется, например, в MS Windows 3.1 и ОС Apple Macintosh. При таком режиме планирования процесс занимает столько процессорного времени, сколько ему необходимо. При этом переключение процессов возникает только при желании самого исполняющегося процесса передать управление (для ожидания завершения операции ввода-вывода или по окончании работы). Этот метод планирования относительно просто реализуем и достаточно эффективен, так как позволяет выделить большую часть процессорного времени для работы самих процессов и до минимума сократить затраты на переключение контекста. Однако приневытесняющем планировании возникает проблема возможности полного захвата процессора одним процессом, который вследствие каких-либо причин (например, из-за ошибки в программе) зацикливается и не может передать управление другому процессу. В такой ситуации спасает только перезагрузка всей вычислительной системы.

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

First-Come, First-Served (FCFS)

Round Robin (RR)

Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin (Round Robin – это вид детской карусели в США) или сокращенно RR. По сути дела, это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованным циклически – процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10– 100 миллисекунд (см. рис. 3.4.). Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.

image037

Рис. 3.4. Процессы на карусели

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

Легко увидеть, что среднее время ожидания и среднее полное время выполнения для обратного порядка процессов не отличаются от соответствующих времен для алгоритма FCFS и составляют 2 и 8 единиц времени соответственно.На производительность алгоритма RR сильно влияет величина кванта времени. При очень больших величинах кванта времени, когда каждый процесс успевает завершить свой CPU burst до возникновения прерывания по времени, алгоритм RRвырождается в алгоритм FCFS. При очень малых величинах создается иллюзия того, что каждый из n процессов работает на собственном виртуальном процессоре с производительностью

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

edugr4

Shortest-Job-First (SJF)

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

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

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

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Источник

Алгоритмы планирования

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

1.Алгоритм FCFS. Простейшим алгоритмом планирования является алгоритм First-Come, First-Served, FCFS – первым пришел, первым обслужен. Когда процесс переходит в состояние готовность, то ссылка на его РСВ помещается в конец очереди. Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на его РСВ. Очередь подобного типа имеет в программировании специальное наименование – First In, First Out (FIFO), первым вошел, первым вышел. Данный алгоритм выбора процесса осуществляет невытесняющее планирование. Процесс, получивший в свое распоряжение процессор, занимает его до истечения текущего CPU burst (промежуток времени непрерывного использования процессора). После этого для выполнения выбирается новый процесс из начала очереди. Преимуществом алгоритма FCFS является легкость реализации, но в то же время он имеет и много недостатков. Так как среднее время ожидания и среднее полное время выполнения для этого алгоритма существенно зависят от порядка расположения процессов в очереди, то процессы, перешедшие в состояние готовность, будут долго ждать начала выполнения. Поэтому алгоритм неприменим для систем разделения времени.

2.Алгоритм RR (циклическое планирование). Модификацией алгоритма FCFS является алгоритм Round Robin, RR (вид детской карусели в США). Этот алгоритм реализован в режиме вытесняющего планирования. Готовые к исполнению процессы организованны циклически и вращаются так, чтобы каждый процесс находился около процессора небольшой фиксированный квант времени, обычно 10 – 100 миллисекунд. Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться. Реализуется алгоритм так же, как и предыдущий, с помощью организации процессов, находящихся в состоянии готовность, в очередь FIFO. Планировщик выбирает для очередного исполнения процесс, расположенный в начале очереди, и устанавливает таймер для генерации прерывания по истечении определенного кванта времени. При выполнении процесса возможны два варианта:

CPU burst меньше или равно продолжительности кванта времени; в этом случае процесс по своей воле освобождает процессор до истечения кванта времени, на исполнение поступает новый процесс из начала очереди и таймер начинает отсчет кванта заново;

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

На производительность алгоритма RR влияет величина кванта времени. При больших величинах кванта времени, когда каждый процесс успевает завершить свой CPU burst до возникновения прерывания по времени, алгоритм RR преобразуется в алгоритм FCFS. При малых величинах – создается иллюзия, что каждый из n процессов работает на собственном виртуальном процессоре с производительностью

1/n от производительности реального процессора. Кроме того, при частом переключении контекста накладные расходы на переключение резко снижают производительность системы. Алгоритмы FCFS и RR зависят от порядка расположения в очереди процессов, готовых к исполнению. Если короткие задачи расположены в очереди ближе к ее началу, то общая производительность этих алгоритмов значительно возрастает.

3.Алгоритм SJF. Алгоритм краткосрочного планирования Shortest-Job-First, SJF (кратчайшая работа первой) может быть как вытесняющим, так и невытесняющим. При невытесняющем SJF-планировании процессор предоставляется избранному процессу на все необходимое ему время, независимо от событий, происходящих в вычислительной системе. При вытесняющем SJF-планировании учитывается появление новых процессов в очереди готовых к исполнению (из числа вновь родившихся или разблокированных) во время работы выбранного процесса. Если CPU burst нового процесса меньше, чем остаток CPU burst у исполняющегося процесса, то исполняющийся процесс вытесняется новым процессом. Основную сложность при реализации алгоритма SJF представляет невозможность точного знания времени очередного CPU burst для исполняющихся процессов. В пакетных системах количество процессорного времени, необходимое заданию для выполнения, указывает пользователь при формировании задания. Если пользователь укажет больше времени, то он будет ждать результата дольше, если меньшее – то задача может не досчитаться до конца.

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

Справедливым для пользователя будет получение Ti / n процессорного времени. Если ti > Ti / n, то i – тый пользователь получает больше расчетного времени процессора. Поэтому для каждого пользовательского процесса вводится значение коэффициента справедливости ti n / Ti и процессу с наименьшей величиной коэффициента предоставляется очередной квант времени. Недостатком алгоритма является невозможность предугадать поведение пользователей. Если пользователь некоторое время не работает с системой, то по возвращению к работе его процессы будут получать неоправданно много процессорного времени.

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

edugr4

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

— на внешние критерии, к которым относятся: параметры важности процесса для достижения каких-либо целей; параметры стоимости оплаченного процессорного времени и др.

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

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

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

Читайте также:  Что может быть твердым как камень и легким как воздух

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

7.Алгоритм многоуровневые очереди с обратной связью (Multilevel Feedback Queue). Дальнейшим развитием алгоритма многоуровневых очередей является добавление к нему механизма обратной связи, благодаря которому процесс может мигрировать из одной очереди в другую в зависимости от своего поведения. Планирование процессов между очередями осуществляется на основе вытесняющего приоритетного механизма. Процессы в очереди 1 не могут исполняться, если в очереди 0 есть хотя бы один процесс. Процессы в очереди 2 не будут выбраны для выполнения, пока есть хоть один процесс в очередях 0 и 1 и т.д. Если при работе процесса появляется другой процесс в более приоритетной очереди, исполняющийся процесс вытесняется новым. Планирование процессов внутри очередей 0 – 2 осуществляется с использованием алгоритма RR, в очереди 3 – алгоритма FCFS.

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

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

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

— количество очередей для процессов, находящихся в состоянии готовность.

— алгоритм планирования, действующий между очередями;

— алгоритмы планирования, действующие внутри очередей;

— правила помещения родившегося процесса в одну из очередей;

— правила перевода процессов из одной очереди в другую.

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

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

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

image008

Если n потокам процесса А предоставить равное количество времени t/n из отведенного кванта времени процессу А, то каждый из них будет выполнять свою работу в течении времени t/n и возвращать процессор планировщику потоков. Это приведет к следующей цепочке: А1, А2, А3Аn; А1, А2, A3Аn, А1… Аn, после чего управление будет передано следующему процессу (рис 3.8.). В качестве алгоритма планирования наиболее часто используются алгоритмы циклического и приоритетного планирования. Единственной проблемой является отсутствие таймера, который прерывал бы затянувшуюся работу потока.

В случае поддержки потоков на уровне ядра, (рис. 3.9.) ядро выбирает следующий поток, не принимая во внимание, какой поток принадлежит какому процессу. Потоку предоставляется квант времени и по истечении этого кванта управление передается другому потоку. Например: А1, А2,…Аn; возможно: А1, В1, А2, В2, А3, В3,…Аn, Bn.

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

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Источник

Модели многозадачности.

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

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

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

1) Режим переключения задач.

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

2) Невытесняющая многозадачность.

Это диспетчеризация без перераспределения процессорного времени. При реализации данной модели планировщик встраивался в ОС в этом случае предоставление процессорного времени каждому приложению или задаче осуществлялся по схеме на
Рис. 6.

image008

Рис. 6. Невытесняющая многозадачность.

Не вытесняющая многозадачность реализована в операционной системе Windows 3x и ранних версиях OS/2, и суть заключается в том, что не операционная система, а сами процессы освобождают процессорное время другим процессам.

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

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

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

Например, в ныне уже забытой операционной среде Windows 3.x приложения этой системы разделяли между собой процессорное время именно таким образом. И программисты сами должны были обеспечивать «дружественное» отношение своей программы к другим выполняемым одновременно с ней программам, достаточно часто отдавая управление ядру системы.

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

3) Вытесняющая многозадачность.

Диспетчеризация с перераспределением процессорного времени между задачами появился в месте с 32 разрядными операционными системами OS/2 и Windows 9x, Windows NT. Её суть заключается в том, что операционная система сама предоставляет запущенным процессом квант времени. Формированием квантов времени занимается системный таймер, который обеспечивает переключение между процессами 20 или 50 раз в секунду (Рис. 7).

image009

Рис. 7. Вытесняющая многозадачность.

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

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

ha

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

image010

Рис. 8. Синхронизация последовательности выполнения потоков.

Рассмотрим выполнение двух задач, которые разделены на потоки (Рис. 8). Если запустить одновременно сразу все потоки от 1 до 7, то это приведёт к не предсказуемым результатам. Поэтому необходимо синхронизировать последовательность выполнения потоков. О приемах синхронизации будет подробнее изложено в главе 4.

Глава 3. Планирование процессов

Уровни планирования

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

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

Читайте также:  По белорусскому медведь как будет

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

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

Для каждого уровня планирования процессов можно предложить много различных алгоритмов. Выбор конкретного алгоритма определяется классом задач, решаемых вычислительной системой, и целями, которых мы хотим достичь, используя планирование. Это позволяет гарантировать каждому заданию или процессу определенную часть времени использования процессора в компьютерной системе, стараясь не допустить возникновения ситуации, когда процесс одного пользователя постоянно занимает процессор, в то время как процесс другого пользователя фактически не приступал к выполнению. Для повышения эффективности использования вычислительной систем необходимо постараться занять процессор на все 100% рабочего времени, не позволяя ему простаивать в ожидании процессов готовых к исполнению. В реальных вычислительных системах загрузка процессора колеблется от 40 до 90%.

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

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

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

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

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

Параметры планирования

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

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

К статическим параметрам процессов относятся характеристики, как правило, присущие заданиям уже на этапе загрузки:

1) Каким пользователем запущен процесс или сформировано задание.

2) Насколько важной является поставленная задача, т. е. каков приоритет ее выполнения.

3) Сколько процессорного времени запрошено пользователем для решения задачи.

4) Каково соотношение процессорного времени и времени, необходимого для осуществления операций ввода-вывода.

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

Алгоритмы долгосрочного планирования используют в своей работе статические и динамические параметры вычислительной системы и статические параметры процессов (динамические параметры процессов на этапе загрузки заданий еще не известны). Алгоритмы краткосрочного и среднесрочного планирования дополнительно учитывают и динамические характеристики процессов. Для среднесрочного планирования в качестве таких характеристик может выступать следующая информация:

1) Сколько времени прошло со времени выгрузки процесса на диск или его загрузки в оперативную память.

2) Сколько оперативной памяти занимает процесс.

3) Сколько процессорного времени было уже предоставлено процессу.

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

Вытесняющее и невытесняющее планирование

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

В случаях 1 и 2 процесс, находившийся в состоянии исполнение, не может дальше исполняться, и для выполнения всегда необходимо выбрать новый процесс. В случаях 3 и 4 планирование может не проводиться, процесс, который исполнялся до прерывания, может продолжать свое выполнение после обработки прерывания. Если планирование осуществляется только в случаях 1 и 2, говорят, что имеет место невытесняющее планирование. В противном случае говорят о вытесняющем планировании. Термин “вытесняющее планирование” возник потому, что исполняющийся процесс помимо своей воли может быть вытеснен из состояния исполнение другим процессом.

Невытесняющее планирование используется, например, в MS Windows 3.1 и ОС Apple Macintosh. При таком режиме планирования процесс занимает столько процессорного времени, сколько ему необходимо. При этом переключение процессов возникает только при желании самого исполняющегося процесса передать управление (для ожидания завершения операции ввода-вывода или по окончании работы). Этот метод планирования относительно просто реализуем и достаточно эффективен, так как позволяет использовать большую часть процессорного времени на работу самих процессов и до минимума сократить затраты на переключение контекста. Однако при невытесняющем планировании возникает проблема возможности полного захвата процессора одним процессом, который вследствие каких-либо причин (например, из-за ошибки в программе) зацикливается и не может передать управление другому процессу. В такой ситуации спасает только перезагрузка всей вычислительной системы.

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

Алгоритмы планирования

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

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

Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS по первым буквам его английского названия — First Come, First Served (первым пришел, первым обслужен). Представим себе, что процессы, находящиеся в состоянии готовность, организованы в очередь. Когда процесс переходит в состояние готовность, он помещается в конец этой очереди. Выбор нового процесса для исполнения осуществляется из начала очереди. Очередь подобного типа имеет в программировании специальное наименование FIFO — сокращение от First In, First Out (первым вошел, первым вышел). Надо отметить, что аббревиатура FCFS используется для этого алгоритма планирования вместо стандартной аббревиатуры FIFO для механизмов подобного типа для того, чтобы подчеркнуть, что организация готовых процессов в очередь FIFO возможна и при других алгоритмах планирования (например, для Round Robin, смотри далее). Такой алгоритм выбора процесса осуществляет невытесняющее планирование. Процесс, получивший в свое распоряжение процессор, занимает его до истечения своего текущего процессорного времени. После этого для выполнения выбирается новый процесс из начала очереди.

Процесс П П1 П2
Процессорное время

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

Если процессы расположены в очереди процессов готовых к исполнению в порядке П, П1, П2, то картина их выполнения выглядит так, как показано на рисунке 9а. Первым для выполнения выбирается процесс П, который получает процессор на все время своего ПВ, т. е. на 13 единиц времени. После его окончания в состояние исполнение переводится процесс П1, занимая процессор на 4 единицы времени. И, наконец, возможность работать получает процесс П2. Время ожидания для процесса П составляет 0 единиц времени, для процесса П1 — 13 единиц, для процесса П2 — 13 + 4 = 17 единиц. Таким образом, среднее время ожидания в этом случае — (0 + 13 + 17)/3 = 10 единиц времени. Полное время выполнения для процесса П составляет 13 единиц времени, для процесса П1 — 13 + 4 = 17 единиц, для процесса П2 — 13 + 4 + 1 = 18 единиц. Среднее полное время выполнения оказывается равным (13 + 17 + 18)/3 = 16 единицам времени.

image012

Рис. 9. Работа алгоритма планирования FCFS для процессов из Таблицы 1 в прямом (а) и обратном (б) порядке.

Если те же самые процессы расположены в порядке П2, П1, П, то картина их выполнения будет соответствовать рисунку 9б. Время ожидания для процесса П равняется 5 единицам времени, для процесса П1 — 1 единице, для процесса П2 — 0 единиц. Среднее время ожидания составит (5 + 1 + 0)/3 = 2 единицы времени. Это в 5 (!) раз меньше, чем в предыдущем случае. Полное время выполнения для процесса П получается равным 18 единицам времени, для процесса П1 — 5 единицам, для процесса П2 — 1 единице. Среднее полное время выполнения составляет (18 + 5 + 1)/3 = 6 единиц времени, что почти в 2,7 раза меньше чем при первой расстановке процессов.

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

3.4.2. Round Robin (RR)

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

Рассмотрим предыдущий пример с порядком процессов П, П1, П2 и величиной кванта времени равной 4 (Рис. 10а). Первым для исполнения выбирается процесс П. Продолжительность его ПВ больше, чем величина кванта времени, и поэтому процесс исполняется до истечения кванта, т. е. в течение 4 единиц времени. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид П1, П2, П. Следующим начинает выполняться процесс П1. Время его исполнения совпадает с величиной выделенного кванта, поэтому процесс работает до своего завершения. Теперь очередь процессов в состоянии готовность состоит из двух процессов П2, П. Процессор выделяется процессу П2. Он завершается до истечения отпущенного ему процессорного времени, и очередные кванты отмеряются процессу П — единственному, не закончившему к этому моменту свою работу. Время ожидания для процесса П составляет 5 единиц времени, для процесса П1 — 4 единицы времени, для процесса П2 — 8 единиц времени. Таким образом, среднее время ожидания для этого алгоритма получается равным (5 + 4 + 8)/3 = 5,6(6) единицы времени. Полное время выполнения для процесса П составляет 18 единиц времени, для процесса П1 — 8 единиц, для процесса П2 — 9 единиц. Среднее полное время выполнения оказывается равным (18 + 8 + 9)/3 = 11,6(6) единицам времени.

Читайте также:  Стало быть как пишется

image014

Рис. 10. Работа алгоритма планирования RR при длительности кванта времени равной 4 мс (а) и 1 мс (б).

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

На производительность алгоритма RR сильно влияет величина кванта времени. Рассмотрим тот же самый пример c порядком процессов П, П1, П2 для величины кванта времени равной 1 (Рис. 10б). Время ожидания для процесса П составит 5 единиц времени, для процесса П1 — тоже 5 единиц, для процесса П2 — 2 единицы. В этом случае среднее время ожидания получается равным (5 + 5 + 2)/3 = 4 единицам времени. Среднее полное время исполнения составит (18 + 9 + 3)/3 = 10 единиц времени.

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

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

3.4.3. Shortest-Job-First (SJF)

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

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

Рассмотрим пример работы невытесняющего алгоритма SJF. Пусть в состоянии готовность находятся четыре процесса П, П1, П2 и П3, для которых известны времена их очередных ПВ. Эти времена приведены в таблице 2. Как и прежде, будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка ПВ, что процессы не совершают операций ввода-вывода, и что время переключения контекста пренебрежимо мало.

Процесс П П1 П2 П3
Продолжительность ПВ

При использовании невытесняющего алгоритма SJF первым для исполнения будет выбран процесс П3, имеющий наименьшее значение очередного ПВ (Рис. 11а). После его завершения для исполнения выбирается процесс П1, затем П и, наконец, П2.

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

Для рассмотрения примера вытесняющего SJF планирования мы возьмем ряд процессов П, П1, П2 и П3 с различными ПВ и различными моментами их появления в очереди процессов готовых к исполнению (см. таблицу 3).

Процесс Время появления в очереди Продолжительность ПВ
П
П1
П2
П3

В начальный момент времени в состоянии готовность находятся только два процесса П и П4. Меньшее ПВ оказывается у процесса П3, поэтому он и выбирается для исполнения (см. Рис. 11б). По прошествии 2-х единиц времени в систему поступает процесс П1. Его ПВ меньше, чем остаток ПВ у процесса П3, который вытесняется из состояния исполнение и переводится в состояние готовность. По прошествии еще 2-х единиц времени процесс П1 завершается, и для исполнения вновь выбирается процесс П3. В момент времени t = 6 в очереди процессов готовых к исполнению появляется процесс П2, но поскольку ему для работы нужно 7 единиц времени, а процессу П3 осталось трудиться всего 2 единицы времени, то процесс П3 остается в состоянии исполнение. После его завершения в момент времени t = 7 в очереди находятся процессы П и П2, из которых выбирается процесс П. Наконец, последним получит возможность выполняться процесс П2.

image016

Рис. 11. Реализация невытесняющего (а) и вытесняющего (б) алгоритма SJF.

Основную сложность при реализации алгоритма SJF представляет невозможность точного знания ПВ для исполняющихся процессов. В пакетных системах количество процессорного времени, требующееся заданию для выполнения, указывает пользователь при формировании задания. Мы можем брать эту величину для осуществления долгосрочного SJF планирования. Если пользователь укажет больше времени, чем ему нужно, он будет ждать получения результата дольше, чем мог бы, так как задание будет загружено в систему позже. Если же он укажет меньшее количество времени, задача может не досчитаться до конца. Таким образом, в пакетных системах решение задачи оценки времени использования процессора перекладывается на плечи пользователя. При краткосрочном планировании мы можем делать только прогноз длительности следующего ПВ, исходя из предыстории работы процесса. Пусть t(n) – величина n-го ПВ, T(n + 1)– предсказываемое значение для n + 1-го ПВ, α – некоторая величина в диапазоне от 0 до 1.

Определим рекуррентное соотношение

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

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

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

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

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

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

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

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

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

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

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

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

Процесс Время появления в очереди Продолжительность ПВ Приоритет
П
П1
П2
П3

Как будут вести себя процессы при использовании невытесняющего приоритетного планирования? Первым для выполнения в момент времени t = 0 выбирается процесс П3, как обладающий наивысшим приоритетом (Рис. 12). После его завершения в момент времени t = 5 в очереди процессов готовых к исполнению окажутся два процесса П и П1. Больший приоритет из них у процесса П1 он и начнет выполняться (см. таблицу 4). Затем в момент времени t = 8 для исполнения будет избран процесс П2 и лишь потом процесс П.

Иным будет предоставление процессора процессам в случае вытесняющего приоритетного планирования (Рис. 13). Первым, как и в предыдущем случае, исполняться начнет процесс П3, а по его окончании процесс П1. Однако в момент времени t = 6 он будет вытеснен процессом П2 и продолжит свое выполнение только в момент времени t = 13. Последним, как и раньше будет исполнен процесс П.

image018

Рис. 12. Невытесняющее приоритетное планирование.

image020

Рис. 13. Вытесняющее приоритетное планирование.

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

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

Дата добавления: 2014-11-13 ; просмотров: 40 ; Нарушение авторских прав

Источник

Adblock
detector