- •Функции и механизмы программ-диспетчеров, предшественников операционных систем.
- •Функции и механизмы мультипрограммных операционных систем.
- •Функции и механизмы сетевых и мобильных операционных систем.
- •Задачи и механизмы организации интерфейса между пользовательскими приложениями и аппаратным обеспечением вычислительной системы.
- •Методы организации эффективного использования ресурсов компьютера. Критерии эффективности. Управление ресурсами.
- •Принципы управления процессами, памятью, файлами.
- •Принципы разработки архитектуры современной операционной системы.
- •Виды архитектур ядер операционных систем.
- •Монолитная архитектура ядра операционной системы.
- •Многослойная архитектура ядра операционной системы.
- •Микроядерная архитектура операционной системы.
- •Понятие процесса, потока, нити, задания.
- •Функции подсистемы управления процессами.
- •1. К созданию процесса приводят пять основных событий:
- •Методы создания процессов.
- •Модель жизненного цикла процесса.
- •Виды планирования и их место в жизненном цикле процесса.
- •Алгоритмы планирования процессов
- •Вытесняющие и невытесняющие алгоритмы планирования
- •Критерии эффективности и свойства методов планирования процессов, параметры планирования процессов. Критерии планирования и требования к алгоритмам
- •Параметры планирования
- •Дисциплины обслуживания без внешнего управления приоритетами (fcfs, rr, sjf), гарантированное планирование. First-Come, First-Served (fcfs)
- •Round Robin (rr)
- •Shortest-Job-First (sjf)
- •Гарантированное планирование
- •Приоритетное планирование с внешним управлением приоритетами, многоуровневые очереди. Приоритетное планирование
- •Многоуровневые очереди (Multilevel Queue)
- •3.5.7. Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)
- •Организация планирования процессов в Microsoft Windows Vista и gnu/Linux.
- •Проблемы взаимодействующих процессов.
- •Алгоритмы реализации взаимоисключений. Требования, предъявляемые к алгоритмам
- •5.3.4. Строгое чередование
- •5.3.5. Флаги готовности
- •5.3.6. Алгоритм Петерсона
- •Семафоры Дейкстра. Решение проблемы «производитель-потребитель» с помощью семафоров. Семафоры
- •Концепция семафоров
- •Решение проблемы producer-consumer с помощью семафоров
- •Тупики. Условия возникновения и направления борьбы с тупиками.
- •Условия возникновения тупиков
- •Основные направления борьбы с тупиками
- •Игнорирование проблемы тупиков
- •Обнаружение тупиков
- •Восстановление после тупиков
- •Принципы управления памятью вычислительной системы. Виртуальная память и преобразование адресов.
- •Концепция виртуальной памяти
- •Методы распределения оперативной памяти без использования внешней памяти.
- •Распределение памяти фиксированными разделами
- •Распределение памяти разделами переменной величины
- •Перемещаемые разделы
- •Страничная организация виртуальной памяти.
- •Методы выделения дискового пространства и записи последовательности блоков данных: непрерывная последовательность блоков, связный список, таблица размещения файлов.
- •Связный список
- •Методы выделения дискового пространства и записи последовательности блоков данных: индексные дескрипторы.
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. | ||||
Процесс |
p0 |
p1 |
p2 |
p3 |
Продолжительность очередного CPU burst |
5 |
3 |
7 |
1 |
При использовании невытесняющегоалгоритма 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-планирования. Если пользователь укажет больше времени, чем ему нужно, он будет ждать результата дольше, чем мог бы, так как задание будет загружено в систему позже. Если же он укажет меньшее количество времени, задача может не досчитаться до конца. Таким образом, впакетных системахрешение задачи оценки времени использования процессора перекладывается на плечи пользователя. Прикраткосрочном планированиимы можем делать только прогноз длительности следующегоCPU burst, исходя из предыстории работы процесса. Пусть– величина n -гоCPU burst, T(n + 1) – предсказываемое значение для n + 1 -гоCPU burst,– некоторая величина в диапазоне от 0 до 1.
Определим рекуррентное соотношение
T(0) положим произвольной константой. Первое слагаемое учитывает последнее поведение процесса, тогда как второе слагаемое учитывает его предысторию. При мы перестаем следить за последним поведением процесса, фактически полагая
T(n)= T(n+1)=...=T(0)
т. е. оценивая все CPU burstодинаково, исходя из некоторого начального предположения.
Положив , мы забываем о предыстории процесса. В этом случае мы полагаем, что время очередногоCPU burstбудет совпадать со временем последнегоCPU burst:
Обычно выбирают для равноценного учета последнего поведения и предыстории. Надо отметить, что такой выборудобен и для быстрой организации вычисления оценки T(n + 1). Для подсчета новой оценки нужно взять старую оценку, сложить с измеренным временемCPU burstи полученную сумму разделить на 2, например, сдвинув ее на 1 бит вправо. Полученные оценки T(n + 1) применяются как продолжительности очередных промежутков времени непрерывного использования процессора длякраткосрочного SJF-планирования.