Наименьшее оставшееся время выполнение

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

6.2.4 Трехуровневое планирование

Трехуровневое планирование

Планировщик доступа выбирает задачки хорошим образом(к примеру: процессы, ограниченные микропроцессором и вводом/выводом).

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

Планирование в интерактивных системах

6.3.1 Повторяющееся планирование

Самый обычный метод планирования и нередко применяемый.

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


Пример повторяющегося планирования

Достоинства:

Недочеты:

6.3.2 Приоритетное планирование

Каждому процессу присваивается ценность, и управление передается процессу с самым высочайшим ценностью.

Ценность может быть динамический Наименьшее оставшееся время выполнение и статический.

Динамический ценность может устанавливаться так:

П=1/Т, где Т- часть использованного в последний раз кванта

Если применено 1/50 кванта, то ценность 50.

Если применен весь квант, то ценность 1.

Т.е. процессы, ограниченные вводом/вывода, будут иметь ценность над процессами ограниченными микропроцессором.

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

Приоритетное планирование 4-х групп

6.3.3 Способы разделения процессов на группы

Группы с различным квантом времени

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

Процесс или завершает работу, или перебегает в другую группу

Этот способ припоминает метод - "Кратчайшая задачка - 1-ая".

Группы с различным предназначением процессов

Процесс, отвечающий на запрос, перебегает в группу с наивысшим ценностью.

Таковой механизм позволяет повысить ценность работы с клиентом.

Гарантированное планирование

В системе Наименьшее оставшееся время выполнение с n-процессами, каждому процессу будет предоставлено 1/n времени микропроцессора.

Лотерейное планирование

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

Справедливое планирование

Процессорное время распределяется посреди юзеров, а не процессов Наименьшее оставшееся время выполнение. Это справедливо если у 1-го юзера несколько процессов, а у другого один.

Планирование в системах реального времени

Системы реального времени делятся на:

Наружные действия, на которые система должна реагировать, делятся:

ß

Что бы систему реального времени можно было планировать, необходимо чтоб производилось условие:

m - число периодическихсобытий

i - номер действия

P(i) - период поступления действия

T(i) - время, которое уходит на обработку действия

Т.е. перегруженная система реального времени является непланируемой.

Планирование однородных процессов

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

Т.к. все процессы важны, можно использовать повторяющееся планирование.

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

6.4.2 Общее планирование реального времени

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

Планировщик должен знать:

Разглядим пример из 3-х процессов.

Процесс Азапускается каждые 30мс, обработка кадра 10мс

Процесс Вчастота 25 кадров, т.е. каждые 40мс, обработка кадра 15мс

Процесс Счастота 20 кадров, т.е. каждые 50мс, обработка кадра 5мс

Три Наименьшее оставшееся время выполнение повторяющихся процесса

Проверяем, можно ли планировать эти процессы.

10/30+15/40+5/50=0.808<1

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

Будем планировать эти процессы статическим(ценность заблаговременно назначается каждому процессу) и динамическимспособами.

6.4.3 Статический метод планирования RMS (Rate Monotonic Scheduling)

Процессы должны удовлетворять условиям:

Ценность в этом методе пропорционален частоте.

Процессу А он равен 33 (частота кадров)

Процессу В он равен 25

Процессу С он равен 20

Процессы производятся по приоритету.

Статический метод планирования RMS (Rate Monotonic Scheduling)

6.4.4 Динамический метод планирования EDF (Earliest Deadline First Наименьшее оставшееся время выполнение)

Больший ценность выставляется процессу, у которого осталось меньшее время выполнения.

При огромных загрузках системы EDFимеет достоинства.

Разглядим пример, когда процессу А требуется для обработки кадра - 15мс.

Проверяем, можно ли планировать эти процессы.

15/30+15/40+5/50=0.975<1

Загрузка системы 97.5%

Динамический метод планирования EDF (Earliest Deadline First)

Метод планированияRMSтерпит беду.


naibolee-aktualnoj-dannaya-programma-yavlyaetsya-dlya-prepodavatelej-kotorie-v-201314-uchebnom-godu-budut-vesti-uchebnie-disciplini-na-pervom-kurse-bakalavriata-i-pervom-kurse-magistraturi.html
naibolee-chastim-perelomom-proksimalnogo-otdela-plecha-yavlyaetsya-perelom.html
naibolee-chasto-poseshaemie-predpriyatiya-pitaniya-g-moskva.html