Модель жизненного цикла процесса
(изменить направление стрелочки из исполнения в ожидание!!) исполнение ->ожидание (необходим недоступный ресурс) Готов->исполнение (процесс попал на выполнение) исполнение->готов (конец периода выполнения) исполнение->завершение (ошибка или обычное завершение программы) ожидание->готов (ресурс доступен, пользователь ввел данные и т.п.) исполнение->исключительная ситуация (например эксепшин) исключительная ситуация-> готовность (исключение обработано) исключительная ситуация->смерть (исключение не обработано) смерть->завершение (процесс завершил выполнение и отдал родительскому процессу код завершения) смерть->зомби (когда процесс присутствует в списке процессов, но завершил свое выполнение) зомби->завершение (вручную администратором)
Виды планирования и их место в жизненном цикле процесса. a. Долгосрочное (решение, какую из программ поставить в очередь, чтобы было меньше конфликтов в борьбе за ресурсы) b. Среднесрочное (решение, об изъятии процесса из ОЗУ на диск (с последующим возвратом), что бы повысить производительность) c. Краткосрочное (диспетчеризация, то есть организация очереди процессов на вычисление)
Критерии эффективности и свойства методов планирования процессов, параметры планирования процессов. Критерии планирования процессов: 1. Справедливость. 2. Эффективность. 3. Сокращение полного времени выполнения. Между стартом процесса и его завершением проходило наименьшее количество времени. 4. Сокращение времени ожидания. 5. Сокращение времени отклика. Характерен для система реального времени и интерактивных систем. Сокращение времени между операциями ввода и вывода.
Параметры планирования: - статические (Размер RAM, размер подкачки, устройства I/O). Кем запущен процесс, приоритет, права доступа, первичные запрошенные ресурсы. - динамические (Свободные ресурсы на текущий момент). Сколько памяти занимает процесс, сумма процессорного времени, сумма времени I/O операций, CPU burst (время ожидаемого использования процессора), I/O burst (время ожидаемого использования I/O). Алгоритмы (методы) планирования: Вытесняющее планирование (процесс может быть снят с вычисления) Не вытесняющее планирование (процесс может выйти с вычисления только по собственному желанию)
Дисциплины обслуживания без внешнего управления приоритетами (FCFS, RR, SJF), гарантированное планирование. FCFS Первый пришел - первый выполнился. Минус: если первым пришел процесс, требующий большого времени выполнения, то остальные процессы должны долго ждать (большое время ожидания).
Round Robin Процессы выполняются по очереди в течение заданного кванта времени (вытесняющий алгоритм). Минус: При больших квантах - большое время ожидания, при маленьких - большие накладные расходы при переключении регистров и т.п.
Shortest Job First Первыми выполняются самые короткие процессы Минус: Если постоянно имеются в наличии процессы более короткие, чем какой-либо другой процесс, то он может вечно ожидать своего выполнения. Гарантированное планирование При N пользователях каждый получает ~1/N процессорного времени. T i-тое - время пользователя в системе 1 <= i <= N Тау i-тое - суммарное время исполнения процессов
Каждый процесс (обделенный) получает процессорное время.
- Отношение реального времени к идеальному.
Требования к алгоритмам планирования: 1. Алгоритм должен быть предсказуем. В близких ситуациях алгоритм должен выдавать сходный результат. 2. Минимизация накладных расходов. Сам алгоритм должен вычисляться быстро и с малым требованием памяти. 3. Маштабируемость алгоритма. Алгоритм должен при увеличении количества процессов должен удовлетворять требованиям 1 и 2.
Приоритетное планирование с внешним управлением приоритетами, многоуровневые очереди. Алгоритмы SJF и гарантированного планирования представляют собой частные случаи приоритетного планирования. Каждому П присваивается определенное числовое значение – приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FCFS. Для алгоритма SJF в качестве такого приоритета выступает оценка продолжительности следующего CPU burst (внутренний параметр). Чем меньше значение этой оценки, тем более высокий приоритет имеет процесс. Для алгоритма гарантированного планирования приоритетом служит вычисленный коэффициент справедливости. Чем он меньше, тем больше приоритет. Планирование с использованием приоритетов мб как вытесняющим, так и невытесняющим. При вытесняющем планировании процесс с более высоким приоритетом, появившийся в очереди готовых П, вытесняет исполняющийся П с более низким приоритетом. В случае невытесняющего планирования он просто становится в начало очереди готовых П. Главная проблема приоритетного планирования - при ненадлежащем выборе механизма назначения и изменения приоритетов низкоприоритетные процессы могут не запускаться неопределенно долгое время. - Многоуровневые очереди(преподы и студенты) Для систем, в которых П мб рассортированы по группам, для каждой группы П создается своя очередь П, находящихся в готовности. Этим очередям приписываются фиксированные приоритеты. Например, приоритет очереди системных П устанавливается выше, чем приоритет очередей пользовательских П. Ни один пользовательский П не будет выбран для исполнения, пока есть хоть один готовый системный П. - Многоуровневые очереди с обратной связью Развитием алгоритма многоуровневых очередей является добавление механизма обратной связи. П не постоянно приписан к определенной очереди, а может мигрировать из одной в другую. Планирование процессов между очередями осуществляется на основе вытесняющего приоритетного механизма. П в очереди менее приоритетной очереди не могут исполняться, если в более есть хотя бы один П. Если при работе П появляется другой процесс в какой-либо более приоритетной очереди, исполняющийся процесс вытесняется новым. МО наиболее трудны в реализации, но обладают наибольшей гибкостью. Необходимо указать: · Количество очередей для процессов, находящихся в состоянии готовность. · Алгоритм планирования, действующий между очередями. · Алгоритмы планирования, действующие внутри очередей. · Правила помещения родившегося процесса в одну из очередей. · Правила перевода процессов из одной очереди в другую.
20. Организация планирования процессов в Microsoft Windows Vista и GNU/Linux. Linux: невытесняющие приоритетные очереди в системных процессах, вытесняющие приоритетные очереди для остальных процессов. Для процессов с одинаковым приоритетом - Round Robin:
|
