Лекция №19
Тема: «Алгоритмы планирования процессов в операционной системе»
Цель: ознакомить с различными методами планирования процессов в операционной системе.
Существует 2 вида планирования в вычислительных системах:
- планирование заданий;
- планирование использования процессора.
Термин «планирование заданий» возник в пакетных системах после того, как для хранения сформированных пакетов заданий стали использоваться магнитные диски — устройства прямого доступа, поэтому появилась возможность выбирать задания для загрузки в систему не в том порядке, в котором они были загружены в систему, а в – произвольном.
Термин «планирование использования процессора» появился в мультипрограммных операционных системах, когда в состоянии готовности может оказаться несколько процессов и тогда для того, чтобы решить какому именно из готовых процессов предоставить процессор и перевести этот процесс в состояние исполнения, операционная система должна прибегать к процедуре планирования. Планирование заданий – это долгосрочное планирование процессов.
При планировании операционная система решает, какое очередное задание, из стоящих в очереди на загрузку в вычислительную систему, должно быть в неё помещено.
Поэтому долгосрочное планирование определяет степень мультипрограммирования в вычислительной системе, т.е. количество процессов, которые одновременно в ней находятся.
Планирование использования процессора выступает в качестве краткосрочного планирования процессов. Наиболее часто краткосрочное планирование процессов используется в системах разделения времени: когда мы должны предоставить по истечении определенного промежутка времени процессор другому процессу.
Помимо краткосрочного и долгосрочного уровней планирования процесса, существует системы, в которых вводится понятие среднего уровня. Предположим, что у вас в системе исполняется некоторое количество процессов и в это время поступает задание первоочередной важности.
Для того чтобы можно было это задание поместить в систему, можно взять некоторый частично выполнившийся процесс и все содержимое памяти и весь контекст, относящийся к данному процессу выкачать куда-нибудь временно на диск, тем самым освободив место для загрузки очень важного задания.
После того как очень важное задание будет выполнено, можно вернуть информацию из диска обратно в оперативную память и продолжим выполнять тот процесс, который был у нас временно приостановлен. Такая процедура получила наименование свопинг (в переводе — перекачка).
Алгоритмы планирования
Алгоритм FSFC — алгоритм невытесняющего планирования. Идея заключается в следующем: тот процесс, который поступил первым в очередь готовых процессов, первым же и получит процессор в свое собственное распоряжение до тех пор, пока не закончится его CPU BIRST.
Давайте посмотрим для того, чтобы понять, как алгоритм работает, следующий пример: пусть у нас с вами есть три процесса в состоянии готовности, а процессы называются Р0, Р1 и Р2.
Процессу Р0 требуется 13 условных единиц времени, процессу Р1 – 4 условные единицы времени и процессу Р2 – одна условная единица времени.
Среднее время нахождения процесса в системе, т.е. среднее turnaround time, и среднее время ожидания, т.е. waiting time.
Алгоритм расчета Turnaround time
Первый процесс находился в вычислительной системе 13 единиц времени. Второй процесс в вычислительной системе находился 17 единиц времени. А третий – 18 единиц времени. Суммируем и делим на 3, получается 16.
Среднее время ожидания – это время, когда у нас процесс находился в состоянии готовности, мог исполняться, но не исполнялся. Для процесса Ро это время равняется 0, для процесса Р1 – это 13 единиц времени, для процесса Р2 – это 17 единиц времени, делим на 3, получаем 10.
Рассмотрим, как будет работать тот же самый алгоритм, если у нас порядок нахождения в очереди готовых изменится на противоположное, т.е. все процессы те же самые только сначала в очередь готовых поступил процесс Р2, потом Р1, а далее Р0.
Среднее время нахождения процесса в системе изменилось, turnaround time теперь составляет для процесса Р2 – 1 единица, для процесса Р1 – 5 единиц, для процесса Ро – 18 единиц. 24/3=8.
Что происходит с waiting time? Процесс Р2 waiting time =0, процесс Р1 waiting time = 1, процесс Ро waiting time = 5. Соответственно, после изменения порядка процессов в очереди готовых, среднее время ожидания сократилось в 5 раз.
Принцип работы алгоритма Round Robin
В переводе с английского – «детская карусель». Процессы находятся в очереди FIFO и на исполнение выбирается процесс, который находится в голове этой очереди, но исполняется теперь он не до тех пор, пока не истечет его CPU BIRST, а до тех пор, пока не истечет выделенный процессором данному процессу квант времени.