Алгоритм планирования использования процессорного времени — это алгоритм определения того, какой процесс будет использовать центральный процессор (ЦП) для своего исполнения, пока другой процесс будет находиться в режиме ожидания.
Введение
Планированием является обеспечение поочередности доступа разных процессов к одному центральному процессору. А планировщиком является реализующая эту операцию часть операционной системы, которая выполняет используемый алгоритм для планирования.
Планирование необходимо осуществлять:
- в случае формирования процесса,
- в случае, когда осуществляется завершение работы процесса,
- в случае, когда процесс заблокирован на операции ввода-вывода и так далее,
- в случае прерывания операции ввода-вывода.
Алгоритмом планирования без переключений (неприоритетным) является алгоритм, который не требует прерывания по аппаратному таймеру, процесс прекращается лишь тогда, когда блокируется или завершает работу.
Алгоритмом планирования с переключениями (приоритетным) является алгоритм, который требует прерывание по аппаратному таймеру, то есть, процесс работает лишь в отведенный период времени, после чего он должен быть приостановлен по таймеру для передачи управления планировщику.
Необходимость использования алгоритма планирования определяется задачами, для которых будет применяться операционная система. Основными считаются следующие варианты систем:
- Системы пакетной обработки, которые способны применять неприоритетный и приоритетный алгоритмы, к примеру, для программ расчетного типа.
- Интерактивные системы, которые способны применять лишь приоритетный алгоритм, то есть, не допускается чтобы один процесс занял надолго процессор. К примеру, это может быть сервер общего доступа или персональный компьютер.
- Системы реального времени, которые способны применять как неприоритетный, так и приоритетный алгоритмы.
Реализация алгоритмов планирования использования процессорного времени
Известно достаточно большое количество самых различных алгоритмов планирования, предназначенных для достижения разных целей. Рассмотрим некоторые самые распространенные из них.
Самым простым является алгоритм планирования First-Come, First-Served (FCFS), то есть, кто первым пришел, тот первым и обслуживается. Когда процесс переходит в состояние готовности, то ссылка на его обслуживание перемещается в конец очереди. Выбор очередного процесса для выполнения реализуется из начала очереди с ликвидацией там ссылки на его обслуживание.
Очередь такого типа обладает в программировании специальным наименованием, а именно, First In, First Out (FIFO), то есть, первым вошел, первым вышел. Этот алгоритм выбора процесса реализует не вытесняющее планирование. Процесс, который получил в свое распоряжение процессор, может занимать его до момента истечения текущего CPU burst, то есть, промежутка времени непрерывного использования процессора.
После этого для исполнения должен быть выбран очередной процесс из начала очереди. Основным достоинством алгоритма FCFS считается легкость его реализации, однако при этом у него имеется и ряд недостатков. Поскольку среднее время ожидания и среднее полное время исполнения для данного алгоритма в значительной степени зависят от порядка местоположения процессов в очереди, то процессы, которые перешли в состояние готовность, затем должны долго ожидать начала своего исполнения. По этой причине алгоритм не следует применять для систем разделения времени.
Модификацией алгоритма FCFS является алгоритм циклического планирования Round Robin (RR), то есть, это аналог вида детской карусели в США. Данный алгоритм реализуется в режиме вытесняющего планирования. Готовые к выполнению процессы проходят процесс организации в циклы и подвергаются вращению так, чтобы каждый процесс располагался около процессора в течение небольшого фиксированного отрезка времени, как правило, это от десяти до ста миллисекунд. Пока процесс располагается рядом с процессором, он может получить процессор в свое распоряжение и выполняться.
Реализовать данный алгоритм можно так же, как и предыдущий, при помощи организации процессов, которые находятся в состоянии готовность, в виде очереди FIFO. Планировщик должен выбрать для очередного выполнения процесс, который расположен в начале очереди, и установить таймер для генерации прерывания по истечении определенного периода времени. При исполнении процесса возможны следующие варианты:
- Интервал времени CPU burst меньше или равен длительности необходимого периода времени. В таком случае процесс сам должен освободить процессор до истечения заданного периода времени, а на выполнение подается новый процесс из начала очереди и таймер начинает снова отсчет периода.
- Интервал времени CPU burst процесса больше выделенного периода времени. В данном случае по истечении выделенного периода времени процесс должен быть прерван таймером и помещен в конец очереди процессов, которые готовы к выполнению, а процессор предоставляется для использования процессу, расположенному в начале очереди.
На производительность алгоритма RR может влиять величина выделенного периода времени. При больших значениях этого периода времени, когда все процессы успевают завершить свой CPU burst до появления прерывания по времени, алгоритм RR переформируется в алгоритм FCFS. При малых величинах выделенного периода времени может возникнуть иллюзия, что любой из n процессов функционирует на собственном виртуальном процессоре, обладающем производительностью примерно 1/n от производительности фактически используемого процессора.
Помимо этого, при частом переключении контекста накладные расходы на выполнение переключений резко понижают производительность системы. Алгоритмы FCFS и RR имеют зависимость от порядка местоположения в очереди процессов, которые готовы к выполнению. Когда короткие задачи располагаются в очереди ближе к ее началу, то общая производительность таких алгоритмов способна существенно возрасти.
