Планирование загрузки центрального процессора

Уровни планирования процессов
Долгосрочное планирование – планирование заданий.
Среднесрочное планирование – swapping.
Краткосрочное планирование – планирование использования процессора.

Цели планирования
Справедливость
Эффективность
Сокращение полного времени выполнения (turnaround time)
Сокращение времени ожидания (waiting time)
Сокращение времени отклика (response time)

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

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

Параметры планирования
Долгосрочное планирование:
Статические и динамические параметры вычислительной системы и статические параметры процесса. Среднесрочное планирование:
Статические и динамические параметры вычислительной системы и статические и динамические параметры процесса.
Краткосрочное планирование:
Статические и динамические параметры вычислительной системы, статические и динамические параметры процесса , CPU burst, I/O burst.

CPU burst и I/O burst
Важные динамические параметры процесса
a=1
b=2
read c
Ожидание окончания
ввода
a=a+c∗b
print a
Ожидание окончания
вывода
CPU burst
CPU burst
I/O burst
I/O burst

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

Алгоритмы планирования
FCFS (First Come – First Served)
t
18
17
13
0
P0
P1
P2
исполнение
готовность
исполнение
исполнение
готовность
1
5
18

Алгоритмы планирования
FCFS (First Come – First Served)
t
18
17
13
0
P0
P1
P2
исполнение
готовность
исполнение
исполнение
готовность
1
5
18

Алгоритмы планирования
RR (Round Robin)
Процесс 1
Процесс 2
Процесс 3
Процесс 4
готовность
готовность
готовность
исполнение
Процессор
Процесс 3
Процесс 3
Процесс 4
исполнение
готовность
готовность
готовность
готовность
Процесс 4
Процесс 1
готовность
готовность
Процесс 3
Процесс 2
исполнение
готовность
Процесс 4
готовность
Процесс 3
Процесс 1
Процесс 2
исполнение
Процесс 1
Процесс 2
готовность

Алгоритмы планирования
Остаток времени CPU burst <= кванта времени:
процесс освобождает процессор до истечения кванта;
на исполнение выбираем новый процесс из начала очереди готовых;
Остаток времени CPU burst >= кванта времени:
По окончании кванта процесс помещается в конец очереди готовых к исполнению процессов;
на исполнение выбираем новый процесс из начала очереди готовых.
RR (Round Robin)

Алгоритмы планирования
RR (Round Robin)
Величина кванта времени – 4
И
И
И
И
Г
Г
Г
Г
Г
Г
Г
Г
P0
P1
P2
Очередь готовых
P0
исполнение
P1
P2
P0
P1
P2
P0
И
И
И
И
Г
Г
Г
Г
Г
Г
Г
Г
P2
P0
И
Г
P0
И
И
И
И
И
И
И
И
И

Алгоритмы планирования
RR (Round Robin)
Величина кванта времени – 1
И
Г
Г
P0
P1
P2
Очередь готовых
P0
исполнение
P1
P2
P0
P2
P0
P0
P1
И
Г
Г
P1
P2
P1
И
Г
Г
P0
P1
И
Г
P1
И
Г
И
Г
И
Г
И
Г
И
Г
И
И
И
И
И
И
И
И
И

Алгоритмы планирования
SJF (Shortest Job First)
невытесняющий
И
Г
Г
Г
И
И
И
Г
Г
Г
Г
Г
Г
И
И
И
И
И
Г
Г
Г
Г
Г
И
И
И
И
И
И
И
P0
P1
P2
готовность
P3
исполнение
P3
P1
P0
P2

Алгоритмы планирования
SJF (Shortest Job First)
вытесняющий
И
Г
P0
P1
P2
готовность
P3
исполнение
P3
P1
P0
P2
Г
И
И
И
Г
Г
Г
Г
И
И
Г
Г
И
Г
Г
И
И
И
И
И
Г
Г
Г
Г
Г
И
И
И
И
И
И

Алгоритмы планирования
τ(n) – величина n-го CPU burst
T(n+1) – предсказание для n+1-го CPU burst
α – параметр от 0 до 1
T(n+1)= α τ(n) + (1 – α)T(n),
T(0) – произвольно
Если α = 0, то T(n+1) = T(n) =…= T(0),
нет учета последнего поведения
Если α = 1, то T(n+1) = τ(n),
нет учета предыстории
SJF (Shortest Job First)
приближение

Алгоритмы планирования
В системе разделения времени N пользователей:
Ti – время нахождения i-го пользователя в системе
τi – суммарное процессорное время процессов i-го пользователя
τi ‹‹ Ti /N
τi ›› Ti /N
(τi N) / Ti – коэффициент справедливости.
На исполнение выбираются готовые процессы пользователя с наименьшим коэффициентом справедливости
Гарантированное планирование
– пользователь обделен
– пользователю благоволят

Алгоритмы планирования
Приоритетное планирование
Каждому процессу процессор выделяется в соответствии с приписанным к нему числовым значением - приоритетом
Параметры для назначения приоритета бывают:
-внешние
-внутренние
Политика изменения приоритета:
-статический приоритет
-динамический приоритет

Алгоритмы планирования
Приоритетное планирование
невытесняющий
И
Г
P0
P1
P2
готовность
P3
исполнение
P3
P1
P0
P2
Г
И
И
И
Г
Г
И
И
Г
Г
И
Г
И
И
И
И
И
Г
Г
Г
Г
Г
И
И
И
И
И
И
Г
Г
Г
Г

Алгоритмы планирования
Приоритетное планирование
вытесняющий
И
Г
P0
P1
P2
готовность
P3
исполнение
P3
P1
P0
P2
Г
И
И
И
Г
Г
И
И
Г
Г
И
Г
И
И
И
И
И
Г
Г
Г
Г
Г
И
И
И
И
И
И
Г
Г
Г
Г
Г
Г
Г
Г

Алгоритмы планирования
Многоуровневые очереди
(Multilevel Queue)
Системные процессы приоритет 0
Процессы ректората приоритет 1
Процессы преподавателей приоритет 2
Фоновые процессы приоритет 3
Процессы студентов приоритет 4
FCFS
RR
RR
RR
RR

Алгоритмы планирования
Многоуровневые очереди с обратной связью
(Multilevel Feedback Queue)
Очередь 0 – Приоритет 0
Очередь 1 – Приоритет 1
Очередь 2 – Приоритет 2
Очередь 3 – Приоритет 3
RR с квантом времени 8
RR с квантом времени 16
RR с квантом времени 32
FCFS
Клавиатурный ввод
Дисковый I/O

Алгоритмы планирования
Многоуровневые очереди с обратной связью
(Multilevel Feedback Queue)
Для полного описания необходимо задать
- количество очередей в состоянии готовность
- алгоритм планирования между очередями
- алгоритмы планирования внутри очередей
- куда помещается родившийся процесс
- правила перевода процессов из одной очереди в другую

Квантование времени для задач

Планирование Windows NT

Приоритеты Windows NT

Классы приоритета процессов
Относительный приоритет задач

Функции Win32API для управления приоритетами задач и процессов
CreateProcess – создание процесса
BOOL CreateProcess(
LPCTSTR lpApplicationName, // указатель на имя исполняемого
// модуля
LPTSTR lpCommandLine, // указатель на командную строку
LPSECURITY_ATTRIBUTES lpProcessAttributes, // указатель на
// атрибуты защиты процесса
LPSECURITY_ATTRIBUTES lpThreadAttributes, // указатель на
// атрибуты защиты задачи
BOOL bInheritHandles, // флаг наследования идентификатора
DWORD dwCreationFlags,// флаги создания процесса
LPVOID lpEnvironment, // указатель на блок среды выполнения
LPCTSTR lpCurrentDirectory, // указатель на имя текущего
// каталога
LPSTARTUPINFO lpStartupInfo, // указатель на структуру
// STARTUPINFO
LPPROCESS_INFORMATION lpProcessInformation); // указатель на
// структуру PROCESS_INFORMATION

Функции Win32API для управления приоритетами задач и процессов
CreateThread – создание задачи (потока, цепочки)
HANDLE CreateThread(
LPSECURITY_ATTRIBUTES lpThreadAttributes,// атрибуты защиты
DWORD dwStackSize, // начальный размер стека в байтах
LPTHREAD_START_ROUTINE lpStartAddress,// адрес функции
// задачи
LPVOID lpParameter, // параметры для задачи
DWORD dwCreationFlags, // параметры создания задачи
LPDWORD lpThreadId); // адрес переменной для
// идентификатора задачи

Функции Win32API для управления приоритетами задач и процессов
Управление запущенными задачами
BOOL SetThreadPriority(
HANDLE hThread, // идентификатор задачи
int nPriority); // новый уровень приоритета задачи
int GetThreadPriority(HANDLE hThread);
DWORD SuspendThread(HANDLE hThread);
DWORD ResumeThread(HANDLE hThread);
VOID Sleep(DWORD cMilliseconds); // время в миллисекундах
VOID ExitThread(DWORD dwExitCode);
BOOL TerminateThread(
HANDLE hThread, // идентификатор завершаемой задачи
DWORD dwExitCode); // код завершения

Традиционное планирование UNIX