Планирование ЦП Algorithms in OperaТинговые системы
Натаниэль Брукс
⚡ Умное резюме
Планирование ЦП определяет, какой из готовых процессов операционная система запустит следующим.ping Процессор занят, и производительность повышается за счет таких алгоритмов, как «первым пришел — первым обслужен», «кратчайшее задание — первым обслужен», «приоритет» и «круговое распределение».
Что такое планирование процессора?
Планирование ЦП Планирование ЦП — это процесс определения того, какой процесс будет использовать ЦП для выполнения, пока другой процесс находится в режиме ожидания. Главная задача планирования ЦП — гарантировать, что всякий раз, когда ЦП остается свободным, ОС выбирает для выполнения хотя бы один из процессов, доступных в очереди готовых к выполнению процессов. Процесс выбора осуществляется планировщиком ЦП, который выбирает один из процессов в памяти, готовых к выполнению.
Типы планирования ЦП
Существует два типа методов планирования:
Упреждающее планирование
При вытесняющем планировании задачи, как правило, назначаются с учетом их приоритетов. Иногда важно выполнить задачу с более высоким приоритетом до выполнения задачи с более низким приоритетом, даже если последняя еще выполняется. Задача с более низким приоритетом приостанавливается на некоторое время и возобновляет выполнение после завершения задачи с более высоким приоритетом.
Невытесняющее планирование
При таком методе планирования ресурсы ЦП выделяются конкретному процессу. Процесс, который занимает ЦП, освобождает его либо путем переключения контекста, либо путем завершения работы. Это единственный метод, который можно использовать на различных аппаратных платформах, поскольку он не требует специального оборудования (например, таймера), как вытесняющее планирование.
В каких случаях планирование является прерывистым, а в каких — нет?
Чтобы определить, является ли планирование вытесняющим или невытесняющим, следует рассмотреть следующие четыре параметра:
- Процесс переключается из состояния выполнения в состояние ожидания.
- Определенный процесс переключается из состояния выполнения в состояние готовности.
- Определенный процесс переключается из состояния ожидания в состояние готовности.
- Процесс завершает свое выполнение и прекращает работу.
Если выполняются только условия 1 и 4, планирование называется невытесняющим. Все остальные ситуации планирования являются вытесняющими.
Важные термины планирования ЦП
- Время взрыва/время выполнения: Время, необходимое для завершения выполнения процесса. Его также называют временем выполнения.
- Время прибытия: Время, когда процесс переходит в состояние готовности.
- Время окончания: Время, когда процесс завершается и выходит из системы.
- Мультипрограммирование: В памяти одновременно может находиться несколько программ.
- Вакансии: Тип программы, не предполагающий никакого взаимодействия с пользователем.
- Пользователь: Это тип программы, предполагающий взаимодействие с пользователем.
- Процесс: Эта ссылка используется как для обозначения вакансии, так и для обозначения пользователя.
- Пакетный цикл CPU/IO: Характеризует выполнение процесса, которое чередуется между работой процессора и вводом-выводом. Время работы процессора обычно короче, чем время работы ввода-вывода.
Критерии планирования ЦП
Алгоритм планирования ЦП пытается максимизировать и минимизировать следующее:
Максимизировать
Загрузка процессора: Загрузка ЦП — это основная задача, в которой операционная система должна обеспечить максимальную загрузку процессора. Она может варьироваться от 0 до 100 процентов. Однако для RTOS она может составлять от 40 процентов для низкоуровневой системы до 90 процентов для высокоуровневой системы.
Пропускная способность: Количество процессов, завершающих свое выполнение за единицу времени, называется пропускной способностью. Таким образом, когда ЦП занят выполнением процесса, выполняется работа, и объем работы, выполненной за единицу времени, называется пропускной способностью.
Минимизировать
Время ожидания: Время ожидания — это время, которое конкретный процесс должен провести в очереди готовых процессов.
Время ответа: Это промежуток времени с момента подачи запроса до получения первого ответа.
Время оборота: Время выполнения — это время, необходимое для выполнения конкретного процесса. Это общее время, затраченное на ожидание доступа к памяти, ожидание в очереди и выполнение на процессоре. Период между моментом отправки процесса и временем его завершения называется временем выполнения.
Интервальный таймер
Прерывание по таймеру — это метод, тесно связанный с упреждением. Когда определенный процесс получает выделение ЦП, таймер может быть установлен на указанный интервал. И прерывание таймера, и вытеснение вынуждают процесс вернуть ЦП до того, как его пакетная нагрузка ЦП будет завершена.
В большинстве многозадачных операционных систем используется таймер, предотвращающий бесконечное зависание системы из-за какого-либо процесса.
Что такое Диспетчер?
Диспетчер — это модуль, который обеспечивает управление процессором для процесса. Диспетчер должен быть быстрым, чтобы он мог выполняться при каждом переключении контекста. Задержка диспетчеризации — это время, необходимое планировщику ЦП для остановки одного процесса и запуска другого.
Функции, выполняемые диспетчером:
- Переключение контекста.
- Переключение в пользовательский режим.
- Перемещение в правильное место во вновь загруженной программе.
Типы планирования ЦП Algorithms
В основном существует шесть типов алгоритмы планирования процессов:
- Первое прибытие - первое обслуживание (FCFS)
- Планирование с приоритетом самого короткого задания (SJF)
- Кратчайшее оставшееся время
- Приоритетное планирование
- Планирование с циклическим перебором
- Многоуровневое планирование очередей
Календарное Планирование Algorithms
Первый пришел первый обслужен
FCFS означает Первый пришел первый обслуженЭто самый простой и лёгкий алгоритм планирования ЦП. В этом алгоритме процесс, запрашивающий ЦП, получает выделение ЦП первым. Этот метод планирования может управляться с помощью очереди FIFO.
Когда процесс попадает в очередь готовых процессов, его блок управления процессом (PCB) связывается с концом очереди. Таким образом, когда процессор освобождается, он должен быть назначен процессу из начала очереди.
Характеристики метода FCFS
- Это алгоритм планирования без вытеснения.
- Задания всегда выполняются в порядке очереди.
- Его легко реализовать и использовать.
- Однако этот метод имеет низкую производительность, а общее время ожидания довольно велико.
Кратчайшее оставшееся время
Полное название SRT — Shortest Remaining Time (кратчайшее оставшееся время). Этот метод также известен как вытесняющее планирование SJF. При таком методе процесс назначается задаче, которая ближе всего к завершению. Это предотвращает задержку завершения более старого процесса из-за наличия более нового процесса в состоянии готовности.
Характеристики метода планирования SRT
- Этот метод в основном применяется в пакетных средах, где приоритет отдается коротким заданиям.
- Этот метод не является идеальным для реализации в системе с общим доступом, где требуемое процессорное время неизвестно.
- Каждому процессу соответствует продолжительность следующего цикла работы процессора, поэтому операционная система использует эти параметры для планирования процесса с максимально коротким временем выполнения.
Планирование на основе приоритетов
Приоритетное планирование Это метод планирования процессов на основе приоритета. В этом методе планировщик выбирает задачи для выполнения в соответствии с их приоритетом.
Приоритетное планирование также помогает операционной системе назначать приоритеты. Процессы с более высоким приоритетом выполняются первыми, в то время как задания с равным приоритетом выполняются по принципу «первым пришел — первым обслужился» или «сразу после назначений». Приоритет может определяться на основе требований к памяти, временных требований и других факторов.
Круговое планирование
По-круговой Это один из старейших и простейших алгоритмов планирования. Название алгоритма происходит от принципа кругового распределения, когда каждый по очереди получает равную долю чего-либо. Он в основном используется для планирования в многозадачных системах. Этот метод помогает добиться выполнения процессов без «голодания».
Характеристики циклического планирования
- Модель циклического распределения нагрузки (Round Robin) — это гибридная модель, работающая на основе тактового сигнала.
- Временной интервал, отведенный на обработку конкретной задачи, должен быть минимальным. Однако он может варьироваться для разных процессов.
- Она работает как система разделения времени, реагируя на каждый процесс в течение определенного временного интервала.
Кратчайшее задание - сначала
SJF (Shortest Job First) — это алгоритм планирования, при котором для выполнения выбирается процесс с наименьшим временем выполнения. Этот метод планирования может быть вытесняющим или невытесняющим. Он значительно сокращает среднее время ожидания для других процессов, ожидающих выполнения.
Характеристики планирования SJF
- Для выполнения каждой задачи отводится определённое количество времени.
- При таком способе, когда процессор свободен, первым выполняется следующий процесс или задача с наименьшим временем выполнения.
- Она реализуется с применением политики, исключающей возможность упреждения.
- Этот алгоритм полезен для пакетной обработки, где ожидание завершения заданий не является критически важным.
- Это повышает производительность труда за счет выполнения в первую очередь более коротких заданий, которые, как правило, имеют более короткое время выполнения.
Планирование многоуровневых очередей
Этот алгоритм разделяет очередь готовых процессов на несколько отдельных очередей. В этом методе процессы назначаются в очередь на основе определенного свойства процесса, такого как приоритет процесса, размер памяти и так далее.
Однако это не самостоятельный алгоритм планирования, поскольку для планирования заданий ему необходимо использовать другие типы алгоритмов.
Характеристики планирования в многоуровневых очередях
- Для процессов с общими характеристиками следует поддерживать несколько очередей.
- Каждая очередь может иметь свой собственный алгоритм планирования.
- Каждой очереди присваивается приоритет.
Назначение алгоритма планирования
Вот причины использования алгоритма планирования:
- ЦП использует планирование для повышения своей эффективности.
- Это помогает распределять ресурсы между конкурирующими процессами.
- Максимальное использование ресурсов ЦП достигается за счет многозадачности.
- Процессы, подлежащие выполнению, хранятся в очереди готовности.
