The design of the UNIX Operating System 4 страница
При очень больших величинах кванта времени, когда каждый процесс успевает завершить свой CPU burst до возникновения прерывания по времени, алгоритм RR вырождается в алгоритм FCFS. При очень малых величинах создается иллюзия того, что каждый из n процессов работает на собственном виртуаль-ном процессоре с производительностью ~ 1/n от производительности реального процессора. Правда, это справедливо лишь при теоретическом анализе при условии пренебрежения временами переключения контекста процессов. В реальных условиях при слишком малой величине кванта времени и, соответст-венно, слишком частом переключении контекста накладные расходы на переключение резко снижают производительность системы.
|
|
|
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 p1 p2 p3 | |||
| 5 | 3 | 7 | 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 | |
| p 0 | Г Г Г Г И И И И И | |||||||||
| p 1 | Г И И И | |||||||||
| p 2 | Г Г Г Г Г Г Г Г Г И И И И И И И | |||||||||
| p 3 | И | |||||||||
Дата добавления: 2021-01-21; просмотров: 101; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!