Ноутбук Ультрабук  Нетбук   Моноблок Настольный ПК Планшет Смартфон
Главная » Статьи » Планировщик операционной системы

Планировщик операционной системы


Простая модель планировщика ОС

Не так давно пытался найти здесь какую-нибудь информацию о планировщике Windows и к своему удивлению не нашёл ничего конкретного о планировщиках вообще, поэтому решил запостить вот этот пример планировщика, надеюсь кому-то он окажется полезен. Код написан на Turbo Pascal со вставками ассемблера 8086.

Что собственно планирует планировщик?
Планировщик — часть операционной системы, которая отвечает за (псевдо)параллельное выполнения задач, потоков, процессов. Планировщик выделяет потокам процессорное время, память, стек и прочие ресурсы. Планировщик может принудительно забирать управление у потока (например по таймеру или при появлении потока с большим приоритетом), либо просто ожидать пока поток сам явно(вызовом некой системной процедуры) или неявно(по завершении) отдаст управление планировщику. Первый вариант работы планировщика называется реальным или вытесняющим(preemptive), второй, соответственно, не вытесняющим (non-preemptive).
Алгоритмы планирования
Существует несколько алгоритмов как вытесняющего, так и невытесняющего планировщика. Для начала давайте разберёмся какой механизм лучше? На первый взгляд очевидным кажется, что вытесняющая многозадачность всегда лучше невытесняющей. Но это не совсем так. Невытесняющая многозадачность даёт большую фору вытесняющей там, где необходимо, чтобы процессор постоянно был занят именно решением задач, а не их переключением, подготовкой, ожиданием. Пример — системы пакетной обработки данных. А во современные пользовательские ОС трудно представить без вытесняющей многозадачности (хотя до выхода Windows NT, все вполне обходились без неё). Итак рассмотрим основные алгоритмы невытесняющей планировки:
  • FIFO
  • Самые короткие — вперёд!
  • Самые выполнившиеся вперёд!
Насчёт первого думаю всё итак понятно: первый пришёл — первый ушёл. Самые простой но, к сожалению не самый эффективный алгоритм, так как из-за решения чьего нибудь километрового интеграла одним потоком, другой будет час ждать очереди, чтобы сложить два числа.

Очевидный способ повысить эффективность — пропускать короткие потоки вперёд в очереди. Так, сначала выполнятся все потоки которым нужно посчитать 2*2, и только потом начнёт вычисляться тот километровый интеграл. Правда тут тоже имеются свои недостатки: например, длинный поток прервавшийся на ввод/вывод снова будет помещён в конец очереди. Третий алгоритм исключает такую ситуацию: потоки которым на данный момент нужно меньше всего времени помещаются в начало очереди. В системах пакетной обработки данных обычно используется три уровня планирования: в начале очередь заданий формируется в дисковой памяти (планирование памяти), оттуда потоки попадают в оперативную память, где по одному из вышеперечисленных алгоритмов тоже выстраиваются в очередь. Тут, возможно ситуация, когда процессов слишком много, тогда какие-то процессы возвращаются обратно на диск (планировщик доступа). Собственно, организацией доступа потоков к управлению процессором занимается третий планировщик — планировщик процессов. Что очевидно — невытесняющая многозадачность не пригодна для операционных систем, в которых требуется моментальный отклик на любые действия пользователя. Кроме того, такой механизм требует от программиста понимания внутреннего устройства системы, и возлагает ответственность не только за работу программы, но и за работу всей системы в целом. Ведь никто не захочет пользоваться вашим продуктом, если он вешает систему на неделю, правда? Рассмотрим несколько алгоритмов вытесняющей планировки:
  • Циклическая
  • С приоритетом по времени
  • С приоритетом по назначению
Первый алгоритм — прямой аналог очереди, а точнее это и есть очередь: первый пришёл — первый получил свой квант времени, снова встал в конец очереди. Всего один очевидный, но очень обидный минус — поток, который использует 1/10 кванта времени будет есть столько же процессорного времени сколько поток использующий квант целиком. Второй алгоритм решает эту проблему: каждому потоку назначается приоритет обратно пропорциональный использованной доле кванта. Поток с большем приоритетом располагается в очереди раньше. Третий алгоритм характерен для интерактивных (серверных) ОС, в которых во главе угла стоит обработка запросов пользователя. Приоритет потокам назначается в зависимости от выполняемой ими задачи. Тут, например, наивысший приоритет будет иметь обработка http запросов, чуть меньший — обработка команд оператора и т. д. При применении такого алгоритма возможно восполнение нечастой передачи управления потоку, выделением ему большего кванта времени. Так поток, который имеет меньший приоритет и потенциально дольше всего ожидающий в очереди получит больше всего процессорного времени. Вытесняющая многозадачность не требует от программиста понимания тонкостей работы планировщика но тоже имеет подводные камни.
Критические секции
C процессорным временем или стеком вроде бы всё просто, а что если потоку требуется например напечатать на принтере котёнка? А что если таких потоков два? При невытесняющей многозадачности всё пройдёт как по маслу: один поток отпечатает котёнка, завершится и отдаст управление планировщику, который позволит печатать второму потоку. Но если многозадачность вытесняющая, планировщик может переключить потоки в момент, когда те ещё не завершили печать и получится что-то вроде этого:

Чтобы такого не происходило вводится механизм критических секций. Поток, которой хочет занять некий неразделяемый ресурс, сообщает об этом планировщику. Если ресурс ещё не занят другим потоком — планировщик разрешает потоку продолжить работу, а сам помечает ресурс, как занятый. Если же ресурс занят — поток помещается в очередь, где он ожидает, когда тот освободится. По завершении работы с таким ресурсом поток должен сообщить планировщику о том что ресурс теперь могут использовать другие потоки. Эти два действия: попытка захватить ресурс и сообщение о прекращении работы с ним называются критическими скобками. Кстати при неумелой их расстановке может возникнуть ситуация взаимной блокировки потоков, которая не всегда хорошо и быстро диагностируется и может вызвать неиллюзорный батхёрт у разработчика и пользователя уже после релиза продукта.
Взаимная блокировка
Допустим у нас есть неразделяемые ресурсы А и Б и потоки Х, Y, которые хотят задействовать эти ресурсы. Если некий криворукий недостаточно компетентный программист расставит критические скобки вот так: … Поток X Занять Ресурс(А) Занять Ресурс(Б) … Отдать Ресурс(А) Отдать Ресурс(Б) Поток Y Занять Ресурс(Б) Занять Ресурс(А) … Отдать Ресурс(Б) Отдать Ресурс(А) через некоторое время возникнет вот такая ситуация:

Сладенькое
Ну и собственно то ради чего это всё писалось. Как уже было сказано код нашего планировщика будет выполнен на языке Turbo Pascal. Механизм критических секций реализован в процедурах EnterCritical(), LeaveCritical(). Вспомним ещё раз: чтобы войти в критическую секцию — нужно проверить не занята ли она, и по результату — либо занять её и разрешить потоку ей пользоваться, либо поставить поток в очередь и передать управление кому-то другому.procedure EnterCritical(num:TCriticalNum); {Войти в критическую секцию} begin asm cli end; if num0 do begin {Пока КС занята кем-то} {отдать управление другому процессу и ждать освобождения КС} asm sti end; SwitchThreads; asm cli end; end; dec(criticalTableWait[num]); end; criticalTable[num]:=1; end; asm sti end; end; C LeaveCritical() вроде бы и так всё ясно:procedure LeaveCritical(num:TCriticalNum); {Покинуть критическую секцию} begin asm cli end; if num0 then {Если кто-то ждет КС} switchThreads; end; Сама процедура переключения потоков написана с использованием ассемблерных вставок, поэтому можно увидеть момент переключения потоков от одного к другому с точностью до машинной команды:procedure TimerHandler(flags,cs,ip,ax,bx,cx,dx,si,di,ds,es,bp:word); interrupt; {Следующие типизированные константы являются на самом деле статическими локальными переменными, которые размещаются в сегменте данных и сохраняют свои значения между вызовами процедуры} const ThreadNumber:byte=0; const NumPrev:byte=0; const tsoffset:word=0; mainSP:word=0; mainSS:word=0; begin if not DisableHardwareEvents then begin asm pushf end; oldvec8; {Вызван старый обработчик прерывания от таймера. Он сбросил контроллер прерываний.} end; if preemptiveSwitch or DisableHardwareEvents then if (ThreadsRegistered> 1) or (parallelStart) then begin {Зарегистрировано более одной задачи} asm cli end; if ParallelStart then begin {Если идет запуск процесса параллельных вычислений} StepCount:=0; asm mov ParallelFinished,false {Сброс флага завершения} mov mainsp,bp {Стек главного потока для возврата по окончании} mov mainss,ss {исполнения параллельных потоков} end; end; inc(StepCount); if {ts[ThreadNumber].active and} not ParallelStart then begin {Сохранение состояния текущего (прерванного) потока. Не производится при взведенном флаге ParallelStart, т.к. предполагается, что в этом случае была прервана основная программа} {Смещение текущнго потока в таблице зарегистрированных потоков} tsoffset:=ThreadNumber*sizeof(TThreadStateWord); asm push ds {нет гарантий, что при прерывании DS указывает на сегмент данных программы!} mov ax,seg ts mov es,ax mov di,offset ts add di,tsoffset mov ax,ss mov ds,ax mov si,bp {ds:si указывает на регистры, сохраненные в стеке} cld mov cx,12 rep movsw {сохранение состояния прерванного потока (кроме стека)} pop ds {es:di продвинулось на 24 байта вперед и указывает на место для сохранения состояния стека} mov ax,bp {BP содержит состояние стека после 12 сохранений регистров} add ax,12*2 stosw {SP задачи} mov ax,ss stosw {SS задачи} end; end; {Поиск следующей активной задачи} NumPrev:=ThreadNumber; repeat ThreadNumber:=(ThreadNumber+1) mod ThreadsRegistered; until (ThreadNumber=NumPrev) or TS[ThreadNumber].active; if ts[ThreadNumber].active and ((ThreadNumberNumPrev) or parallelStart) then begin {Восстановление новой задачи, если она отлична от прежней. Производится при взведенном флаге ParallelStart, даже если задача совпадает с якобы прежней, т.к. может оказаться, что единственной активной задачей в очереди является задача номер 0} tsOffset:=(ThreadNumber+1)*sizeof(TThreadStateWord) - 3; asm mov dx,ds mov ax,seg TS mov ds,ax mov si,offset TS add si,tsOffset {ds:si указывает на состояние активизируемого потока} std lodsw mov ss,ax lodsw mov sp,ax mov bp,ax {Переключение на стек нового потока} sub bp,12*2 {Подмена регистров в стеке на сосотояние нового потока. После возврата из процедуры будет исполняться код с той точки, где он был прерван при деактивации активизируемого сейчас потока} mov cx,12 @m1: lodsw push ax loop @m1 cld mov ds,dx end; end else if (not ts[Threadnumber].active) and (Threadnumber=NumPrev) then begin {Все задачи завершены} setintvec($8,@oldvec8); asm mov parallelfinished,true mov ax,mainss mov ss,ax mov bp,mainsp mov sp,bp end; end; parallelstart:=false; end; DisableHardwareEvents:=false; end; Сама процедура скомпилирована с директивой interrupt, то есть является обработчиком прерывания. Которое может быть спровоцировано как аппаратно, так и программно вызовом int 08h, вот так:procedure SwitchThreads; begin if not parallelFinished then asm cli mov DisableHardwareEvents,1 int 08h sti end; end; Так же необходимо описать сами процедуры регистрации, включения и остановки потоков. Если кому-то интересно — можно посмотреть в исходниках процедуры RegistrThread, RunThread, StopThread. Вот и всё! Наш планировщик готов.

Исходники вместе примером многопоточной программы написаной под этот планировщих и досовским турбиком можно скачать здесь. Можно поиграться и посмотреть как по разному будут выполняться потоки при вытесняющей и невытесняющей многозадачности (процедура ExecuteRegisterThreads(true/false)), смоделировать ситуацию взаимной блокировки и убедиться в том, что она не всегда диагностируема (я однажды минуту ждал пока возникнет дедлок).

Запускать в системах новее Win98 советую из под DOSbox. Теги:
  • OS
  • ОС
  • планировщик
  • низкий уровень

habr.com

Планировщик. Планирование. Алгоритмы планирования в операционной системе - презентация онлайн

Планировщик – это часть операционной системы, выбирающая между активными процессами, желающими получить доступ к процессору Алгоритмом планирования – алгоритм, в соответствии с которым процессор осуществляет этот выбор Планировщик также должен заботиться об эффективном использовании процессора, поскольку переключение между процессами требует затрат: 1. Необходимо переключиться из режима пользователя в режим ядра. 2. Сохранить состояние текущего процесса, включая сохранение регистров в таблице процессов, чтобы их можно было загрузить заново позже. 3. Нужно выбрать следующий процесс, запустив алгоритм планирования. перезапустить блок управления памятью с картой памяти нового процесса. 4. Запустить новый процесс.Практически все процессы чередуют периоды вычислений с операциями (дисковыми) ввода-вывода. Обычно процессор некоторое время работает без остановки, затем происходит системный вызов на чтение из файла или запись в файл. После выполнения системного вызова процессор опять считает, пока ему не понадобятся новые данные или не потребуется записать полученные данные и т.1. Когда создается новый процесс, необходимо решить, какой процесс запустить: родительский или дочерний. 2. Когда процесс завершает работу. Этот процесс уже не существует, следовательно, необходимо из набора готовых процессов выбрать и запустить следующий 3. Когда процесс блокируется на операции ввода-вывода, семафоре, или по какой-либо другой причине, необходимо выбрать и запустить другой процесс 4. При появлении прерывания ввода-вывода. Планировщик должен выбрать, какой процесс запустить: новый, тот, который был остановлен прерыванием, или какой-то другой.согласно их поведению после прерываний. 1. Алгоритмы планирования без переключений (неприоритетное планирование), выбирают процесс и позволяют ему работать вплоть до блокировки (в ожидании ввода-вывода или другого процесса), либо вплоть до того момента, когда процесс сам не отдаст процессор. Процесс не будет прерван, даже если он работает часами. 2. Алгоритмы планирования с переключениями (приоритетное планирование), выбирают процесс и позволяют ему работать некоторое максимально возможное фиксированное время.1. Системы пакетной обработки данных - нет пользователей, сидящих за терминалами и ожидающих ответа. В таких системах приемлемы алгоритмы без переключений или с переключениями, но с большим временем, отводимым каждому процессу. Такой метод уменьшает количество переключений между процессами и улучшает эффективность. 2. Интерактивные системы - В интерактивных системах необходимы алгоритмы планирования с переключениями, чтобы предотвратить захват процессора одним процессом. Даже если ни один процесс не захватывает процессор на неопределенно долгий срок намеренно, из-за ошибки в программе один процесс может заблокировать остальные. 3. Системы реального времени - процессы знают, что их время ограничено, и быстро выполняют работу, а затем блокируются. работают только программы, предназначенные для содействия конкретным приложениям.Для всех систем свойственны: Справедливость — предоставление каждому процессу справедливой доли процессорного времени Принудительное применение политики — контроль за выполнением принятой политики Баланс — поддержка занятости всех частей системы Системы пакетной обработки данных Пропускная способность — максимальное количество задач в час Оборотное время — минимизация времени, затрачиваемого на ожидание обслуживания и обработку задачи Использование процессора — поддержка постоянной занятости процессора Интерактивные системы Время отклика — быстрая реакция на запросы Соразмерность — выполнение пожеланий пользователя Системы реального времени Окончание работы к сроку — предотвращение потери данных Предсказуемость — предотвращение деградации качества в мультимедийных системахПроцессам предоставляется доступ к процессору в том порядке, в котором они его запрашивают. Чаще всего формируется единая очередь ждущих процессов. Когда текущий процесс блокируется, запускается следующий в очереди, а когда блокировка снимается, процесс попадает в конец очереди. Достоинства: 1. Легко понять и столь же легко программировать. 2. Все процессы в состоянии готовности контролируются одним связным списком. Недостаток: 1. Представьте себе, что есть один процесс, ограниченный возможностями процессора, который каждый раз работает ровно 1 с, и много процессов, ограниченных возможностями устройств ввода-вывода, каждый из которых очень в небольшой мере использует процессор, но должен выполнить 1000 обращений к диску.Временные отрезки работы известны заранее. Если в очереди есть несколько одинаково важных задач, планировщик выбирает первой самую короткую задачу. У нас есть четыре задачи: Л, Л, С и D, со временем выполнения 8, 4, 4 и 4 мин соответственно. Если мы запустим их в данном порядке, оборотное время задачи Л будет 8 мин, В — 12 мин, С — 16 мин и D — 20 мин, и среднее время будет равно 14 мин. а) запуск четырех задач в исходном порядке б) запуск в соответствии с алгоритмом планирования Недостаток: Схема работает лишь в случае одновременного наличия задач.Планировщик каждый раз выбирает процесс с наименьшим оставшимся временем выполнения. Когда поступает новая задача, ее полное время выполнения сравнивается с оставшимся временем выполнения текущей задачи. Если время выполнения новой задачи меньше, текущий процесс приостанавливается и управление передается новой задаче. Достоинство: Позволяет быстро обслуживать короткие запросы. Недостатки: Необходимо заранее знать время выполнения задачПо мере поступления в систему новые задачи сначала помещаются в очередь, хранящуюся на диске. Впускной планировщик выбирает задание и передает его системе. Остальные задания остаются в очереди Как только задание попало в систему, для него будет создан соответствующий процесс, и он может тут же вступить в борьбу за доступ к процессору. Второй уровень планирования определяет, какие процессы можно хранить в памяти, а какие — на диске. Этим занимается планировщик памяти. Степень многозадачности - количество процессов, одновременно находящихся в памяти,Каждому процессу предоставляется некоторый интервал времени процессора, так называемый квант времени. Если к концу кванта времени процесс все еще работает, он прерывается, а управление передается другому процессу. Планировщику нужно всего лишь поддерживать список процессов в состоянии готовности. Когда процесс исчерпал свой лимит времени, он отправляется в конец списка. Если установленное значение кванта больше среднего интервала работы процессора, переключение процессов будет происходить редко. Напротив, большинство процессов будут совершать блокирующую операцию прежде, чем истечет длительность кванта, вызывая переключение процессов. Устранение принудительных переключений процессов улучшает производительность системы, так как переключения процессов будут происходить только тогда, когда это логически необходимо, то есть когда процесс заблокировался и не может продолжать работу.Каждому процессу присваивается приоритет, и управление передается готовому к работе процессу с самым высоким приоритетом. Чтобы предотвратить бесконечную работу процессов с высоким приоритетом, планировщик может уменьшать приоритет процесса при каждом прерыванииПроцессам класса с высшим приоритетом выделялся один квант, процессам следующего класса — два кванта, следующего — четыре кванта и т. д. Когда процесс использовал все отведенное ему время, он перемещался на класс ниже.Основывается на оценке длины процесса, базирующейся на предыдущем поведении процесса. При этом запускается процесс, у которого оцененное время самое маленькое. Метод оценки следующего значения серии через взвешенное среднее предыдущего значения и предыдущей оценки часто называют старением. Этот метод применим во многих ситуациях, где необходима оценка по предыдущим значениям.Система должна отслеживать распределение процессора между процессами с момента создания каждого процесса. Затем система рассчитывает количество ресурсов процессора, на которое процесс имеет право, например время с момента создания, деленное на п. Теперь можно сосчитать отношение времени, предоставленного процессу, к времени, на которое он имеет право. Полученное значение 0,5 означает, что процессу выделили только половину положенного, а 2,0 означает, что процессу досталось в два раза больше, чем положено. Затем запускается процесс, у которого это отношение наименьшее, пока оно не станет больше, чем у его ближайшего соседа.В основе алгоритма лежит раздача процессам лотерейных билетов на доступ к различным ресурсам, в том числе и к процессору. Когда планировщику необходимо принять решение, выбирается случайным образом лотерейный билет, и его обладатель получает доступ к ресурсу. «Лотерея» может происходить 50 раз в секунду, и победитель получает 20 мс времени процессора. Достоинство: 1. Обладает высокой отзывчивостью. 2. Взаимодействующие процессы могут при необходимости обмениваться билетами. 3. Позволяет решать задачи, которые не решить с помощью других алгоритмов. 4. Можно реализовать загрузку процессора в желаемой пропорцииВ такой модели каждому пользователю достается некоторая доля процессора, и планировщик выбирает процесс в соответствии с этим фактом. Если в нашем примере каждому из пользователей было обещано по 50 % процессора, то им достанется по 50 % процессора, независимо от количества процессов.1. На жесткие системы реального времени, что означает наличие жестких сроков для каждой задачи (в них обязательно надо укладываться), 2. На гибкие системы реального времени, в которых нарушения временного графика нежелательны, но допустимы. Внешние события, на которые система должна реагировать, можно разделить на: 1. Периодические (возникающие через регулярные интервалы времени) 2. Непериодические (возникающие непредсказуемо).Алгоритмы планирования для систем реального времени могут быть 1. Статическими. Решения планирования принимаются заранее, еще до запуска системы. Статическое планирование применимо только при наличии достоверной информации о работе, которую необходимо выполнить, и о временном графике, которого нужно придерживаться. 2. Динамическими. Решения планирования принимаются по ходу дела. Динамическое планирование не нуждается в ограниченияхПоскольку ядро не знает о существовании потоков, оно выполняет обычное планирование, выбирая процесс Л и предоставляя ему квант времени. Планировщик потоков внутри процесса Л выбирает поток, например А1. В качестве алгоритма планирования для системы поддержки исполнения программ можно взять любой из уже рассмотренных нами.ядро выбирает следующий поток. При этом ядро не обязано принимать во внимание, какой поток принадлежит какому процессу, хотя у него есть такая возможность. Потоку предоставляется квант времени и по истечении этого кванта управление передается другому потоку.

ppt-online.org

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

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

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

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

Переключения контекста это не есть операция планирования, это техническая операция.

  • Происходит прерывание;
  • Поток вызывает исключение или ловушку (trap);
  • После этого выбирается другой поток.

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

Классы планировщиков

  1. Пакетный – ориентирован на длительные задачи, которые требуют больших вычислительных ресурсов, где не требуется частое прерывание. Т.е. подразумевают обработку больших задач большими пакетами, нет ограничения на время выполнения.
  2. Интерактивный – ориентирован на снижение времени отклика, т.е. чтобы система казалась”отзывчивой”. Обычные абонентские системы на ПК – это интерактивные системы, когда в ответ на действие пользователя (например перемещение мыши) ОС что-то делает. И всегда пользователю хочется, чтобы этот ответ происходил как можно быстрее. Главное чтобы на поступающий в систему запрос был получен максимально быстро ответ. Запрос – это любое взаимодействие с компьютером.
  3. Реального времени – специализированные класс, ориентированный на дедлайн – предельный срок завершения какой-либо работы.Главное, чтобы определенное действие завершалось к определенному сроку, это понятие называется дедлайн.Поступающий запрос должен быть обработан не более, чем в определенный промежуток времени.Классический пример СРВ – управление ядерным реактором, в котором превышение времени отклика приведет к аварийной ситуации.

Уровни планирования

  • Долговременное(догосрочное) – решает какие новые задачи будут добавлены (концептуальные вопросы).
  • Среднесрочное – решает нужно ли временно выгружать программу во вторичную память (какую и вообще нужно ли это).
  • Краткосрочный – решает, какому потоку дать следующий квант процессорного времени и какой длины. Координирует выполняющиеся потоки на разных ЦП.

Основной задачей планирования процессов в ОС является обеспечение высокой производительности ОС.

Существуют разные метрики, которыми оценивается эта производительность. Эти метрики зачастую противоречивы.

Что концептуально требуется при проектировании планировщика ОС:

  • Максимизировать использование ЦП (чтобы он максимально работал на задачах)
  • Максимизировать пропускную способность(число выполненных запросов в единицу времени)
  • Минимизировать среднее время отклика (среднее время от подачи запроса до завершения обработки ответа)
  •  Минимизировать среднее время ожидания (среднее время от подачи запроса до начала его выполнения)
  •  Минимизировать энергии (джоулей на инструкцию)

Метрики планирования

На следующем рисунке рассмотрим пример метрики планирования.

Метрики планирования

ta— время поступления процесса (когда процесс становится готовым к выполнению);

Tw – время ожидания (которое тратит процесс в очереди на выполнение);

Ts – время выполнения ЦП;

Tr – время оборота (общее время на ожидание и выполнение).

На схеме 5 и 6 процессы поступили в очередь готовых процессов.

5 задержался из-за 1-4 процесов. Для пятого процесса Tw – время ожидания Ts – время выполнения ЦП.

Время оборота это время от момента его поступления до момента, когда завершилось его выполнение Tr=Tw+Ts.

При планировании процессов главным остается вопрос: Как выбрать какой процесс будет работать дольше и дальше?

Существуют следующие алгоритмы планирования процессов:

  • FIFO— классика – первым пришел, первым ушел
  • Кратчайшая работа следующей, т.е. следующей выбирается работа, которая требует наименьшего времени завершения
  • Round-robin 
  • Многоуровневая очередь 
  • Многоуровневая очередь с обратной связью

Рассмотрим названные алгоритмы планирования процессов.

FIFO

В данном случае мы будем его понимать как невытесняющую многозадачность

  • Процессы планируются по мере их поступления;
  • Время выполнения не учитывается (никак совсем);
  • Другие процесс с меньшим временем Tr вынуждены ждать (снижается отзывчивость системы);
  • Когда процесс переходит в состояние готовности он перемещается в конец очереди.

Пример FIFO

Допустим есть три процесса, которые пребывают в одно и тоже время t=0 в порядке P1,P2,P3.

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

  • Burst(Р1)=24 (усл.ед.времени)
  • Burst(Р2)=3
  • Burst(Р3)=3

Тогда Время ожидания

  • Wait(P1)=0
  • Wait(P2)=24
  • Wait(P3)=27

Среднее время ожидания = 17

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

Допустим процессы поступают в порядке Р2,Р3,Р1

Тогда время ожидания

Среднее время ожидания =3

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

За данным простым примером скрыта вся мощь и важность алгоритмов планирования процессов в ОС.

Обобщения по FIFO:

  • Он больше других подходит для длительных, требовательных к времени ЦП процессов;
  • Плохое использование ЦП и устройств ввода/вывода;
  • Среднее время ожидание сильно варьируется.

Кратчайшая работа следующей

Условимся, имеется в виду невытесняющая политика планирования – сколько квант времени запрашивает процесс, столько ему и выделяется.

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

Сложности:

Нужно оценивать требуемое время обработки для каждого процесса.

  • Для пакетных заданий на основе предыдущего опыта или вручную (нет гарантии, что повторится)
  • Для интерактивных заданий на основе затраченного времени

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

Кратчайшая работа следующей вытесняющий вариант

Существует вытесняющий вариант метода кратчайшей работы следующего.

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

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

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

А те процессы, которым еще долго работать, оставить на потом и заняться ими “в плотную”. Логика в этом есть.

Обобщение по «Кратчайшая работа следующей»:

  • Процессы, уже выполняющиеся на ЦП вытесняются самым близким к завершению заданием;
  • Меньше общее время оборота процесса;
  • Меньше время ожидания ЦП.

 Планирование с приоритетами

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

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

Проблема старвации – это проблема “зависания”,“голодания” – если процессу с высоким приоритетом приспичит выполнить очень длительную работу, то все остальные процессы будут “висеть” и ждать.

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

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

Проявляется в алгоритме КРС. Низкоприоритетные запросы могут никогда не выполниться.

Решение проблемы:

Ввести понятие «старения»: по мере течения времени увеличивать приоритет процесса.

Приоритет = Оценочное время выполнение на ЦП – время ожидания

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

Round-robin

Данный алгоритм планирования обозначает циклический алгоритм с вытесняющим планированием.

  • Каждый процесс получает фиксированный квант процессорного времени (фиксированную единицу процессорного времени).
  • После истечения кванта времени процесс принудительно вытесняется и помещается в очередь готовых к выполнению.
  • Процесс всегда планируются в том же порядке и каждый процесс получает одинаковый квант времени
  • Не сложно подсчитать: если квант времени равен q и n-процессов в очереди, то каждый получит 1/n времени ЦП, кусками максимум по q
  • Никакой из процессов не ожидает больше, чем  (n-1)*q единиц времени

Производительность Round-robin(RR)

  • Если q большое(стремиться к ∞), то RR перерождается в алгоритм FIFO;
  • Если q малое (но не стремится к 0, иначе ПК будет только переключать процессы и больше не выполнять вообще ничего), то все хорошо;
  • Нет старвации;
  • Появляется высокая отзывчивость системы;
  • Равное распределение времени;
  • Если q меньше, чем время, затрачиваемое на переключение контекста, тогда диспетчер будет неэффективным.

Недостаток Round-robin

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

Недостаток Round-robin

Есть 2 процесса Р1 и Р2

Процесс Р1 ожидает ввод/вывод в точке (●), пока этот вв/выв не завершится часть отмеченного штриховкой времени процесс Р1 потратит «впустую», он вытиснится только в зеленой точке по истечении кванта времени.

Р2 в это время активно использует ЦП, например, считает.

Проблема RR в том, что не учитываются задержки, и полезное время работы Р1 составляет только 10%.

Многоуровневые очереди

Выделяется несколько разных очередей, например:

  • Очередь интерактивных процессов, т.е. тех, которые требуют малого времени отклика;
  • Очередь фоновых процессов, требующих много выч.ресурсов, но для которых не важно быстрое время отклика(пакетная обработка), нужно много повычислять.

У каждой очереди сопоставляется свой алгоритм планирования, таким образом имеем некий «баланс сил»:

  • у интерактивных процессов RR;
  • у фоновых — FIFO.

Но в случае многоуровневых очередей нужно планирование не просто внутри каждой очереди, но и планирование между очередями. Получается «накрученный» планировщик, можно предложить много вариантов:

1) Планирование с фиксированным приоритетом 

  • Вначале обслужить все интерактивные процессы, потом все фоновые
  • Возможна старвация

2) Разделение времени

Каждой очереди выделяется часть времени ЦП, которую она может распланировать между своими процессами. Например 80% времени ЦП на интерактивные процессы через RR, 20% на фоновые через FIFO.

3) Многоуровневая очередь с обратной связью

Многоуровневая очередь с обратной связью

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

Многоуровневая очередь с обратной связью

Если он выполнился достаточно быстро, то он попадает в первую очередь «быстрых» процессов.

Если он средний по времени выполнения, то в среднюю.

Если он требует много времени вычислительных ресурсов, то он помещается в последнюю очередь FIFO.

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

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

  • Числом очередей;
  • Алгоритмами планирования в каждой очереди;
  • Методом, используемым для определения принадлежности процесса к той или иной очереди.

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

Есть три очереди:

  • Q0 –RR с квантом времени t=16мс
  • Q1 –RR с квантом времени t=32мс
  • Q2 –FIFO

Планирование:

Новый процесс помещается в конец первой очереди Q0

  • Когда процесс из этой очереди получает ЦП, то выделяется квант времени t=16мс
  • Если процесс выполняется дольше, не вернул управление ОС, то он принудительно вытесняется и помещается в конец очереди Q1

В очереди Q1

  • Когда процесс из этой очереди получает ЦП, то выделяется квант времени t=32мс
  • Если процесс выполняется дольше, то он принудительно вытесняется и помещается в конец очереди Q2 и выполняется по FIFO пока не закончится

 Скачать презентацию по теме «Планирование процессов»

Скачать тест по теме «Планирование процессов»

Понравилась статья, рекомендуйте Вашим друзьям!
↑Как установить такие кнопки?↑
Давайте дружить!

komputercnulja.ru

61.Что такое планировщик, какие функции выполняет долговременный планировщик и т.д

Что такое планировщик? Какие функции выполняет долговременный планировщик? Какие функции выполняет кратковременный планировщик? Какие функции выполняет планировщик откачки и подкачки? Какой из планировщиков определяет степень мультипрограммирования ОС?

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

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

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

Кратковременный планировщик (планировщик процессора) – определяет, какие процессы должны быть выполнены следующими и каким процессам должен быть предоставлен процессор.

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

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

Схема работы системы, включающей такой планировщик

Долговременный планировщик определяет степень (коэффициент) мультипрограммирования – число процессов, которое обслуживает система в единицу времени.

studfiles.net

Смотрите также