Планирование процессов БОП БВП Обработка ЦП Завершение 1 4 Ожидание начала обработки 0 Ожидания операции в/в 2 3 Очередь на выполнение 5 6 Диск свопинг Типовой граф управления процессами:

Планирование процессов Характеристики, используемые для оценки эффективности: степень загрузки ЦП (CPU utilization); пропускная способность (throughput) – количество процессов, завершающихся в единицу времени; полное время выполнения (turnaround time) – суммарное время пребывания процесса в системе; время ожидания (waiting time) – суммарное время, которое процесс провел в очереди готовых процессов время отклика (response time) – время, между поступлением запроса от пользователя и началом его обработки процессами Приоритет процесса – числовая характеристика, соответствующая степени доступности процесса к тем или иным ресурсам ВС по сравнению с другими процессами. Priority = f({ресурсы ВС},User,…)

Планирование буфера ввода процессов - предельное количество процессов, размещенных на БВП Смесь процессов -Если i < j, то процесс сформирован раньше Будем считать, что все ресурсы, запрашиваемые каждым Процессом доступны (в противном случае схема несколько сложнее).

FIFO очередь.... Очередь с приоритетами процессов.... для i > j :

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

Многоуровневая очередь объем заказанных ресурсов ВС (например, предельное время ЦП); критерий пользователя, сформировавшего процесс;... - очередь процессов организованная как: - FIFO - очередь процессов с приоритетами Каждая из очередей может иметь свой приоритет

Перевод процесса из БВП в буфер готовых к исполнению (БОП) 1. Поддержание заданного уровня многопроцессности. При завершении выполнения очередного процесса, запрашивается очередной из БВП. В случае представления БВП как М очередей, используются приоритеты очередей. 2. Поддержание заданных квот на количество обрабатываемых процессов, поступивших из тех или иных входных очередей.

Планирование очереди (буфера) готовых к исполнению процессов, планирование использования ЦП Квант времени работы ЦП. Цикл счета: непрерывный промежуток времени, Использованный процессом с момента выделения ЦП до его освобождения. Задачи планирования: - определение стратегии квантования; - стратегия обслуживания готовых к исполнению процессов; Невытесняющее планирование времени ЦП (планирование без переключений, неприоритетное планирование) – процесс выполняется либо до завершения, либо до возникновения блокировки.

Планирование очереди (буфера) готовых к исполнению процессов, планирование использования ЦП Вытесняющее планирование (планирование с переключениями, приоритетное планирование) – процесс начинает выполнятся и выполняется до исчерпания выделенного кванта времени, либо до завершения, либо до возникновения блокировки. Моменты принятия решений планировщиком: - завершение выполнения процесса; - исчерпание выделенного процессу кванта времени; - блокировка процесса (обмен, синхронизация,...); - прерывание от внешних устройств.

Планирование в системах пакетной обработки FCFS (first-come, first-served) – первым пришел, первым обслужен Процесс Цикл счета (время счета) Время ожидания Среднее время ожидания Процесс Цикл счета (время счета) Время ожидания Среднее время ожидания9

Планирование в системах пакетной обработки Эффект сопровождения 1. Один «вычислительный» процесс и «много» процессов, занимающихся обменом. 2. Вычислительный процесс на «длительное» время занимает ЦП, у остальных процессов завершаются обмены – ждут выделения процесса. 3. Вычислительный процесс блокируется по обмену. Остальные «быстро» используют свои «короткие» промежутки времени использования ЦП и вновь блокируются по обмену.. Процессы, занимающиеся обменом в ожидании завершения вычислительного процесса. FCFS – алгоритм может быть вытесняющим или невытесняющим.

Планирование в системах пакетной обработки SPF (shortest-process-first) SPF (shortest-process-first) – кратчайший процесс – первым Выбирается процесс с минимальным следующим циклом счета. Цикл счета Время ожидания SPFFCFS Среднее время ожидания Оптимален по минимизации среднего времени ожидания.

Планирование в системах пакетной обработки Невозможность точного определения размеров циклов счета. «Предсказание» следующего цикла счеты. Использование экспоненциального среднего:, где - реальная длина n-ого цикла. - n-ое приближение длины n-ого цикла -весовой коэффициент последнего прогнозирования - последняя информация игнорируется - прогнозирование игнорируется Значимость начального приближения со временем уменьшается

Планирование в системах пакетной обработки Вытесняющий алгоритм SDF. Текущий процесс исполняется, а новый процесс с более коротким циклом счета чем остаток у текущего попадает в очередь. Прерывание текущего процесса. Время поступления Цикл счета Среднее время ожидания ((10-1)+(1-1)+(17-2)+(5-3))/4 = 6.5 SPF без Вытеснения – 7.5

Планирование в системах пакетной обработки SRT (Shortest remaining time) – наименьшее остающееся время Выбор процесса с минимальным ожидаемым временем до завершения процесса., где лимит времени ЦП для i-ого процесса; j-й использованный i-ым процессом цикл счета. Вариант с вытеснением и вариант без вытеснения.