Планирование работы процессора критерии для сравнения планировщиков работы процессора

Обновлено: 03.07.2024

Глава 3 Планирование процессора и взаимоблокировка ---- 2, часто используемые алгоритмы планирования

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

Такие как Система пакетной обработки Чтобы позаботиться о многих коротких работах, вы должны использовать Короткий приоритет работы Алгоритм планирования

Такие как Система разделения времени Чтобы система имела разумное время отклика, ее следует использовать Круглый Робин Выполните планирование.

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

1. Первоочередное обслуживание службы планирования FCFS (First Come First Service)

Один из самых простых алгоритмов планирования, планирование по порядку. Его можно использовать как для планирования заданий, так и для планирования процессов.

В соответствии с представлением на работу, или процесс становится готовым порядок Назначить процессор;

Новая работа только тогда, когда текущая работа или процесс Закончено или заблокировано Прежде чем запустить процессор

есть пробуждение Задание или процесс не возобновляют выполнение немедленно, обычно до тех пор, пока текущее задание или процесс не перейдут в ЦП. (Таким образом, по умолчанию используется метод без вытеснения)

* Не способствует короткой работе (процесс)
Примеры анализа времени:

Не достаточно: Взвешенное время оборота для короткой работы C достигает 100, что недопустимо, в то время как взвешенное время оборота для длинной работы D составляет всего 1,99.

О приложении: Способствует интенсивной работе процессора и Не способствует I / O занят Работа (процессы).

С точки зрения размера программы, общие операции ввода-вывода заняты Время обработки CPU относительно короткое, а задание типа занятости CPU относительно длинное. FCFS не подходит для коротких заданий. Как только занятые операции ввода / вывода ставятся в очередь, они оказываются в невыгодном положении.

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

В настоящее время большая часть обработки транзакций относится к операциям ввода-вывода.

2. Алгоритм планирования приоритетов коротких заданий (процессов) SJF / SPF (сначала самое короткое задание) ИЛИ (сначала самый короткий процесс)

Преимущества:

Из приведенной выше таблицы видно, что при использовании алгоритма SJF / SPF среднее время оборота и средневзвешенное время оборота значительно улучшились. Алгоритм планирования SJF / SPF может эффективно сократить работу Среднее время ожидания ， Улучшить пропускную способность системы 。

Метод:

Есть два метода вытеснения и без вытеснения.

Инструмент описания процесса планирования

Gantt( Ганта ) Рисунок: Горизонтальные отрезки часто используются для описания хода каждого процесса. Он может указывать время начала и время завершения каждого процесса, а длина отрезка представляет время, необходимое для завершения процесса.

Недостатки SJF / SPF:

1. даКороткая работаЭто выгодно, но в то же время невыгодно для длительных операций.

2. Из-за продолжительности работы (процесса)Субъективные факторыМожет не быть в состоянии действительно достичь приоритета короткой работы.

3. Не считая домашнее заданиеСтепень срочностиСледовательно, он не может гарантировать своевременную обработку срочных задач (процессов).

3. Высокоприоритетный алгоритм планирования приоритетов HPF Highest Priority First

Алгоритм планирования введен, чтобы заботиться о срочной работе и заставить ее получить приоритетное лечение Обычно используется в алгоритмах планирования заданий в системах пакетной обработки и алгоритмах планирования процессов в нескольких операционных системах

1) Есть два способа: Алгоритм без вытеснения приоритетов Алгоритм приоритетного приоритета Ключевой момент: когда создается новая работа

2) Типы приоритетов

Статический приоритет： При создании процесса убедитесь, что он останется неизменным на протяжении всего цикла. Обычно он выражается целым числом в определенном диапазоне, также называемом номером приоритета.

Динамический приоритет： Приоритет, данный при создании процесса, может меняться по мере его продвижения или увеличения времени ожидания.

По определению приоритета процесса? Основа заключается в следующем:

1) Тип процесса Вообще говоря, системный процесс выше, чем пользовательский процесс.

2) Требования к ресурсам процесса Такие, как предполагаемое время процесса и объем требуемой памяти, дают более высокий приоритет процессу, который требует меньше.

3) Требования пользователя : Приоритет определяется срочностью процесса пользователя и тем, сколько пользователь платит.

3+ Алгоритм высокоприоритетного планирования приоритетов HRRN Highest Response Raito Next

Алгоритм с коротким приоритетом работы - это лучший алгоритм (эквивалентный алгоритму статического приоритета, установленному в соответствии с продолжительностью работы), который подходит для пакетных систем с большим количеством коротких работ, его основным недостатком является то, что длинная работа не может быть гарантирована ,

HRRN Ввести для каждой работы Динамический приоритет , Так что приоритет задания увеличивается со скоростью по мере увеличения времени ожидания a Улучшение:

приоритет = (Время ожидания + Запрос времени обслуживания )/ Запрос времени обслуживания = Время отклика / Запрос времени обслуживания

* Позаботься о разных задачах *

1. Задания, прибывающие в одно и то же время, имеют одинаковый приоритет.

Начальное t = 0, поскольку время увеличивается, если время ожидания t одинаково, чем короче время выполнения, тем выше приоритет, Способствует короткой работе 。

Для длинных заданий приоритет задания может быть увеличен при увеличении времени ожидания, а процессор может быть получен, когда время ожидания достаточно велико. Долгосрочный уход 。

2. Когда задания с одинаковым временем выполнения, приоритет определяется продолжительностью их ожидания, которая составляет Первым пришел первым обслужен 。

Когда рассчитывается приоритет коэффициента отклика каждого процесса?

Когда нужны параметры планирования, сравните их приоритеты

Когда работа завершена

Когда генерируется новое задание (приоритетное, не приоритетное)

Когда временной интервал завершен

Когда процесс заблокирован

3. Алгоритм циклического планирования RR на основе временного интервала (Round Robin)

Новый спрос на систему разделения времени： Ответить вовремя Пользовательский запрос, основанный на Временной интервал Алгоритм планирования процесса циклического перебора.

Ранняя система разделения времени, используемая Простое вращение среза Широко принятый в 1990-х Многоуровневый алгоритм планирования очередей обратной связи 。

Два метода вводятся отдельно, а производительность сравнивается ниже.

(1) алгоритм вращения среза

1. Следите за всеми готовыми процессами в системе FCFS Принципы, выстроены очередь 。

2. ЦП выделяется для каждого планирования Руководитель группы Пусть Выполнить отрезок времени , Временной интервал длина От нескольких мс до сотен мс.

3. В конце отрезка времени происходит Прерывание часов 。

4. Планировщик соответственно Приостановить выполнение текущего процесса Отправь это Конец готовой очереди И переключаться через контекст Выполнить готовый в настоящий момент процесс руководителя группы 。

Когда возникает ситуация блокировки процесса, Вы должны продать, прежде чем закончится время Процессор может ответить вовремя, но не учитывает продолжительность работы и другие вопросы.

О длине отрезка времени

Длина отрезка времени Выбор для Сравнимо со временем, необходимым для завершения основного процесса взаимодействия , Чтобы гарантировать, что основной интерактивный процесс может быть завершен во временном интервале.

Неправильные настройки приведут к длительному времени отклика.

Что произойдет, если это будет слишком долго? --FCFS Что будет, если оно будет слишком коротким? -Частое переключение

Основные факторы, влияющие на длительность отрезка времени

Производительность системы и статус загрузки системы。（ Продолжительность временного интервала определяется в соответствии с возможностями обработки системы, так что пользовательский ввод обычно может обрабатываться во временном интервале, в противном случае время отклика, среднее время оборота и средневзвешенное время оборота увеличиваются. Чтобы обеспечить время отклика взаимодействия с пользователем при различных условиях нагрузки, продолжительность временного интервала должна быть соответствующим образом скорректирована. ）

полемика: Если одновременно имеется временной интервал для отказа от процесса ЦП, процесс новой готовности Б, как упорядочить два в очереди готовности.

Дайте единые предположения при решении проблем, Если новый процесс готов быть относительно быстрым, он будет поставлен в очередь в очередь готовности в порядке BA.

Если старый процесс должен быть установлен все быстрее и быстрее, то он будет отсортирован AB равномерно

(2) Алгоритм многоуровневой очереди обратной связи FB (Multiple-level Feed Back Queue)

Особенности:Несколько готовых очередей, круговая обратная связь Динамический приоритет, вращение временного интервала

1 ) Настройте несколько готовых очередей, каждая очередь имеет Разные приоритеты , Приоритет понижается с первой очереди.

2 ) Дайте каждому процессу очереди Размер отрезка времени выполнения отличается, Чем выше приоритет, тем короче интервал времени 。

3) Когда новый процесс входит в память, запускается процесс планирования

1. Подготовка к планированию: сначала поместите его в конец первой очереди, нажмите FCFS В принципе, ждать в очереди для планирования.

2. Завершенный в течение интервала IF, вы можете подготовиться к эвакуации системы;

3. Если временной интервал IF не завершится, планировщик перенесет процесс в Вторая очередь По окончании ожидания должно быть запланировано выполнение снова.

4. Когда все процессы в первой очереди выполнены, система нажимает FCFS Отправьте вторую очередь в принципе. Это все еще не закончено в немного более длинном отрезке времени второй очереди, и затем поместите это в очередь Третья очередь.

5. После спуска в n-ю очередь по очереди, в N-я очередь Будут приняты в Повернуть по срезу времени Выполнить путь.

Примечание:

Временной интервал каждой когорты постепенно увеличивается. Приоритет постепенно уменьшается

Только если Очередь с высоким приоритетом (например, первая очередь) свободна Когда планировщик планирует Вторая очередь Процесс в запущен, только если первый 1

（ i-1 ) Очередь Когда оба пусты, первый i Процесс в очереди запущен.

Проблема приоритетного вытеснения:

первый i Очередь занята процессом CPU И новый процесс входит в очередь с более высоким приоритетом (в команде 1st

Прерванный процесс помещается обратно в конец исходной очереди готовности;

* Производительность алгоритма многоуровневого планирования очереди обратной связи *

Алгоритм многоуровневого планирования очереди с обратной связью имеет лучшую производительность и может лучше удовлетворять потребности различных типов пользователей.

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

Пользователи коротких пакетных заданий , Время выполнения заказа по-прежнему мало и может быть выполнено не более чем во второй-третьей очередях.

Длинные пользователи пакетной работы , Он будет выполняться по очереди в очереди уровня 1

n, не беспокоясь о том, что задание не будет обрабатываться в течение длительного времени.

Краткосрочный планировщик выбирает процессы из очереди готовых процессов и передает их на выполнение в CPU. Существуют различные алгоритмы или стратегии решения этой задачи, отличающиеся отношением к критериям планирования.

2.1. Критерии планирования процессора.

Используются следующие критерии, позволяющие сравнивать алгоритмы краткосрочных планировщиков:

утилизация CPU (использование) CPU utilization. Утилизация CPU теоретически может находиться пределах от 0 до 100%. В реальных системах утилизация CPU колеблется в пределах 40% для легко загруженного CPU, 90% для тяжело загруженного CPU.

пропускная способность CPU throughput. Пропускная способность CPU может измеряться количеством процессов, которые выполняются в единицу времени.

время оборота (turnaround time) для некоторых процессов важным критерием является полное время выполнения, то есть интервал от момента появления процесса во входной очереди до момента его завершения. Это время названо временем оборота и включает время ожидания во входной очереди, время ожидания в очереди готовых процессов, время ожидания в очередях к оборудованию, время выполнения в процессоре и время ввода - вывода.

время ожидания (waiting time). Под временем ожидания понимается суммарное время нахождения процесса в очереди готовых процессов.

время отклика (response time) для сугубо интерактивных программ важным показателем является время отклика или время, прошедшее от момента попадания процесса во входную очередь до момента первого обращения к терминалу.

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

В ряде случаев используются сложные критерии, например, так называемый минимаксный критерий, то есть вместо простого критерия минимум среднего времени отклика используется следующий — минимум максимального времени отклика.

2.2. Стратегии планирования процессора.

2.2.1.Первый пришел - первый обслуживается FIFO. first come - first served (FCFS).

На рисунке схематически показано, каким образом операционная система использует process control block для переключения процессора с одного процесса на другой.

FCFS является наиболее простой стратегией планирования процессов и заключается в том, что процессор передается тому процессу, который раньше всех других его запросил.

Когда процесс попадает в очередь готовых процессов, process control block присоединяется к хвосту очереди.

Среднее время ожидания для стратегии FCFS часто весьма велико и зависит от порядка поступления процессов в очередь готовых процессов.

Пусть три процесса попадают в очередь одновременно в момент 0 и имеют следующие значения времени последующего обслуживания в CPU.

Краткосрочный планировщик выбирает процессы из очереди готовых процессов и передает их на выполнение в CPU. Существуют различны алгоритмы или стратегии решения этой задачи, отличающиеся отношением к критериям планирования.

3.4.1. Критерии планирования процессора.

Используются следующие критерии, позволяющие сравнивать алгоритмы краткосрочных планировщиков:

утилизация CPU (использование) CPU utilization. утилизация CPU теоретически может находиться пределах от 0 до 100%. В реальных системах утилизация CPU колеблется в пределах 40% для легко загруженного CPU, 90% для тяжело загруженного CPU.

время ожидания (waiting time). под временем ожидания понимается суммарное время нахождения процесса в очереди готовых процессов.

В ряде случаев используются сложные критерии, например так называемый минимаксный критерий, то есть вместо простого критерия минимум среднего времени отклика используется следующий — минимум максимального времени отклика.

3.4.2. Стратегии планирования процессора. Первый пришел – первый обслуживается (fifo). First Come – First Served (fcfs)

Когда процесс попадает в очередь готовых процессов, process control block присоединяется к хвосту очереди.

Стратегии FCFS присущ так называемый “эффект конвоя”. В том случае, когда в компьютере имеется один большой процесс и несколько малых, то все процессы собираются в начале очереди готовых процессов, а затем в очереди к оборудованию. Таким образом, “эффект конвоя” приводит к снижению загруженности как процессора, так и периферийного оборудования.

Стратегия наиболее короткая работа —sjf

SJF — Shortest Job First. Одним из методов борьбы с “эффектом конвоя” является стратегия, позволяющая процессу из очереди выполняться первым.

Сратегия SJF снижает время ожидания очереди. Наибольшая трудность в практической реализации SJF заключается в невозможности заранее определить величину времени последующего обслуживания.

Поэтому стратегия SJF часто применяется в долгосрочных планировщиках, обслуживающих пакетный режим. В этом случае вместо величины времени последующего обслуживания используется допустимое максимальное время выполнения задания, которое программист должен специфицировать перед отправкой задания в пакет.

Презентацию к данной лекции Вы можете скачать здесь.

Введение

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

Основные понятия диспетчеризации процессов
Критерии диспетчеризации
Алгоритмы диспетчеризации
Диспетчеризация нескольких процессоров
Диспетчеризация в реальном времени
Многоуровневые очереди .

Основные понятия диспетчеризации процессов

Диспетчеризация процессора – распределение его времени между процессами в системе. Цель диспетчеризации – максимальная загрузка процессора , достигаемая с помощью мультипрограммирования .

Исполнение любого процесса можно рассматривать как цикл CPU / I-O – чередование периодов использования процессора и ожидания ввода-вывода.

Распределение периодов активности процессора ( bursts ) и ввода-вывода изображено на рис. 11.1.

Рис. 11.1. Последовательность активных фаз процессора и фаз ввода-вывода.

На рис. 11.2 изображена примерная гистограмма периодов активности процессора, основанная на анализе реального поведения процессов в операционных системах.

Рис. 11.2. Гистограмма периодов активности процессора.

Из схемы видно, что чем короче период активности, тем выше частота таких периодов, и наоборот, т.е. частота периодов активности обратно пропорциональна их длительности.

Планировщик процессора

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

Решения по диспетчеризации могут быть приняты в случаях, если процесс:

Переключается из состояния выполнения в состояние ожидания.
Переключается из состояния выполнения в состояние готовности к выполнению.
Переключается из состояния ожидания в состояние готовности.
Завершается.

Диспетчеризация типов 1 и 4 обозначается термином диспетчеризация без прерывания процесса (non-preemptive).

Диспетчеризация типов 2 и 3 обозначается термином диспетчеризация с прерыванием процесса (preemptive).

Собственно диспетчер процессора

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

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

Скрытая активность (латентность) диспетчера (dispatch latency) – время, требуемое для диспетчера, чтобы остановить один процесс и стартовать другой. Разумеется, система должна стремиться минимизировать это время, однако набор критериев диспетчеризации более сложен.

Читайте также: