Общие понятия о процессах и их планировании

Лекция 3. ОБЩИЕ ПОНЯТИЯ О ПРОЦЕССАХ И ИХ ПЛАНИРОВАНИИ 1. Понятие процесса и блока управления 2. Понятие одноразовых операций 3. Понятие многоразовых операций 4. Контекст и дескриптор процесса 5. Планирование процессов 6. Цели и критерии планирования процессов 7. Свойства и параметры алгоритмов планирования процессов 8. Алгоритмы планирования процессов 9. 1. Понятие процесса и блока управления Понятие процесса характеризует некоторую совокупность набора исполняющихся команд, ассоциированных с ними ресурсов (выделенная память, адресное пространство, стеки и т.д.). и текущего момента его выполнения находящуюся под управлением ОС. Не существует взаимно - однозначного соответствия между процессами и программами, обрабатываемыми вычислительными системами. Информация, необходимая для выполнения операций хранится в одной структуре данных. Эту структуру будем называть PCB (Process control Block) или блоком управления. Блок управления является моделью процесса для операционной системы. Содержимое всех регистров процессора будем называть регистровым контекстом процесса, а все остальные – системным контекстом процесса. Код и данные, находящиеся в адресном пространстве процесса, будем называть пользовательским контекстом. Совокупность регистрового, системного и пользовательского контекстов назовем контекстом процесса. 2. Понятие одноразовых операций Путь прохождения процесса в компьютере начинается с его рождения. Инициатором рождения процесса после старта операционной системы может выступать либо процесс пользователя, либо сама операционная система. Процесс, инициировавший создание нового процесса называют процессом - родителем, а вновь созданный процесс называется процессом – ребенком. Процессы дети могут порождать своих детей. При рождении процесса система заводит новый PCB с состоянием рождение и начинает его заполнять. Процесс 1 Процесс 2 Процесс 12 Процесс 255 Процесс 4 Процесс 23 Процесс 3 Процесс 24 Процесс 14 Процесс 15 Процесс 128 Рис. Упрощенный генеалогический лес процессов Новый процесс получает собственный уникальный идентификационный номер, учитывая, что для хранения такого номера операционной системой отводится ограниченное число бит. Для соблюдения уникальности номеров количество одновременной присутствующих в ней процессов должно быть ограничено. После завершения процесса его освободившийся идентификатор может быть повторно использован для другого процесса. Для выполнения своих функций процесс – ребенок требует определенных ресурсов. Выделение ресурсов может производиться двумя путями. 1.Новый процесс может получить в свое распоряжение некоторую часть родительских ресурсов возможно, разделяя с процессом - родителем и другими процессами – детьми права на них; 2. Возможно получение своих ресурсов непосредственно от операционной системы. После наделения процесса - ребенка ресурсами в адресное пространство заносится его программный код, значения данных, устанавливается программный счетчик. Это также может производится двумя путями: а) в первом случае процесс – ребенок становится дубликатом процесса- родителя по регистровому и пользовательскому контекстам. При этом должен существовать способ определения кто для кого из процессов – двойников является родителем. б) Во втором случае процесс ребенок загружается новой программой из какого – либо файла. Порождение нового процесса как дубликата процесса – родителя приводит к возможности существования исполняемых файлов для работы которых организуется более одного процесса. После того как процесс наделен содержанием, в PСB дописывается оставшаяся информация и состояние нового процесса изменяется на готовность. Процесс – родитель может продолжать свое выполнение одновременно с выполнением процесса – ребенка, а может ожидать завершения работы некоторых или всех своих детей. После того как процесс завершил свою работу операционная система переводит его в состояние закончил исполнение. Все ресурсы освобождаются, при этом делается соответствующая запись в блоке управления процессом. Сам блок не уничтожается. Он остается в системе некоторое время. Это связано с тем, что процесс – родитель может запросить операционную систему после завершения работы процесса – ребенка причину его «смерти». Такая информация хранится в PCB отработавшего процесса. Одноразовые операции приводят к изменению количества процессов, находящихся под управлением операционной системы и всегда связаны с выделением или освобождением определенных ресурсов. 3. Понятие многоразовых операций Многоразовые операции не приводят к изменению количества процессов в операционной системе и не обязаны быть связаны с выделением или освобождением ресурсов. Основные действия, которые производит операционная система при выполнении многоразовых операций: Запуск процесса; Приостановка процесса; Блокирование процесса; Разблокирование процесса. Сл .10. Запуск процесса. Из процессов, находящихся в состоянии готовность операционная система выбирает один процесс для последующего исполнения. Для избранного процесса ОС обеспечивает наличие в оперативной памяти информации, необходимой для дальнейшего выполнения. Далее, состояние процесса изменяется на исполнение. Восстанавливаются значения регистров для данного процесса, и управление передается команде, на которую указывает счетчик команд процесса. Все данные, необходимые для восстановления контекста, извлекаются из PCB процесса, над которым совершается операция. Сл. 11. Приостановка процесса. Работа процесса, находящегося в состоянии исполнение приостанавливается в результате какого – либо прерывания. Процессор автоматически сохраняет счетчик команд и, возможно один или несколько регистров в стеке исполняемого процесса, затем, управление передается по специальному адресу обработки данного прерывания. По этому адресу располагается одна из частей операционной системы. Она сохраняет динамическую часть системного и регистрового контекстов процесса в его PCB. Процесс переводится в состояние готовность и приступает к обработке прерывания, т.е. к выполнению определенных действий, связанных с возникшим прерыванием. Сл.12. Блокирование процесса. Процесс блокируется, когда он не может продолжить работу, не дождавшись возникновения какого – либо события в вычислительной системе. Для этого он обращается к ОС с помощью определенного системного вызова. ОС обрабатывает системный вызов, при необходимости сохраняет нужную часть контекста в его PCB, переводит процесс из состояния исполнение в состояние ожидание. Сл. 13. Разблокировка процесса. После возникновения в системе какого – либо события, операционной системе нужно точно определить какое именно событие произошло. Далее, ОС проверяет находился ли процесс в состоянии ожидание для данного события и если находился, то переводит его в состояние готовность. 4. Контекст и дескриптор процесса На протяжении существования процесса его выполнение может быть многократно прервано и продолжено. Для того, чтобы возобновить выполнение процесса, необходимо восстановить состояние его операционной среды. Состояние операционной среды отображается состоянием регистров и программного счетчика, режимом работы процессора, указателями на открытые файлы, информацией о незавершенных операциях ввода-вывода, кодами ошибок выполняемых данным процессом системных вызовов и т.д. Эта информация называется контекстом процесса. Кроме этого, операционной системе для реализации планирования процессов требуется дополнительная информация: идентификатор процесса, состояние процесса, данные о степени привилегированности процесса, место нахождения кодового сегмента и другая информация. В некоторых ОС (например, в ОС UNIX) информацию такого рода, используемую ОС для планирования процессов, называют дескриптором процесса. Дескриптор процесса по сравнению с контекстом содержит более оперативную информацию, которая должна быть легко доступна подсистеме планирования процессов. Контекст процесса содержит менее актуальную информацию и используется операционной системой только после того, как принято решение о возобновлении прерванного процесса. Очереди процессов представляют собой дескрипторы отдельных процессов, объединенные в списки. Таким образом, каждый дескриптор, кроме всего прочего, содержит по крайней мере один указатель на другой дескриптор, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать процессы, переводить процессы из одного состояния в другое. Программный код только тогда начнет выполняться, когда для него операционной системой будет создан процесс. Создать процесс - это значит: 1. создать информационные структуры, описывающие данный процесс, то есть его дескриптор и контекст; 2. включить дескриптор нового процесса в очередь готовых процессов; 3. загрузить кодовый сегмент процесса в оперативную память или в область свопинга. Переключение контекста. Переключение контекста. В результате обработки информации об окончании операции ввода – вывода возможна смена процесса, находящегося в состоянии исполнение. Для корректного переключения процессора с одного процесса на другой необходимо сохранить контекст исполнявшегося процесса и восстановить контекст процесса, на который будет переключен процессор. Такая процедура сохранения/восстановления работоспособности процессоров называется переключением контекста. Время, затраченное на переключение контекста не используется ОС для совершения полезной работы, и представляет собой накладные расходы, снижающие производительность системы. Оно колеблется в диапазоне от 1 до 1000 микросекунд. Сократить накладные расходы в современных операционных системах позволяет расширенная модель процессов, включающая в себя понятие Threads of execution (нити исполнения). 5. Планирование процессов Мы говорили о двух видах планирования в вычислительных системах: планировании заданий и планировании использования процессора. Планирование заданий появилось в пакетных системах после того, как для хранения сформированных пакетов заданий начали использоваться магнитные диски. Магнитные диски, являясь устройствами прямого доступа, позволяют загружать задания в компьютер в произвольном порядке, а не только в том, в котором они были записаны на диск. Изменяя порядок загрузки заданий в вычислительную систему, можно повысить эффективность ее использования. Процедуру выбора очередного задания для загрузки в машину, т. е. для порождения соответствующего процесса, мы и назвали планированием заданий. Планирование использования процессора впервые возникает в мультипрограммных вычислительных системах, где в состоянии готовность могут одновременно находиться несколько процессов. Именно для процедуры выбора из них одного процесса, который получит процессор в свое распоряжение, т. е. будет переведен в состояние исполнение, мы использовали это словосочетание. Теперь, познакомившись с концепцией процессов в вычислительных системах, оба вида планирования (заданий и процессов) мы будем рассматривать как различные уровни планирования процессов. Планирование заданий используется в качестве долгосрочного планирования процессов. Оно отвечает за порождение новых процессов в системе, определяя ее степень мультипрограммирования, т. е. количество процессов, одновременно находящихся в ней. Если степень мультипрограммирования системы поддерживается постоянной, т. е. среднее количество процессов в компьютере не меняется, то новые процессы могут появляться только после завершения ранее загруженных. Поэтому долгосрочное планирование осуществляется достаточно редко, между появлением новых процессов могут проходить минуты и даже десятки минут. Решение о выборе для запуска того или иного процесса оказывает влияние на функционирование вычислительной системы на протяжении достаточно длительного времени. Отсюда и название этого уровня планирования – долгосрочное. В некоторых операционных системах долгосрочное планирование сведено к минимуму или отсутствует вовсе. Так, например, во многих интерактивных системах разделения времени порождение процесса происходит сразу после появления соответствующего запроса. Поддержание разумной степени мультипрограммирования осуществляется за счет ограничения количества пользователей, которые могут работать в системе, и особенностей человеческой психологии. Если между нажатием на клавишу и появлением символа на экране проходит 20–30 секунд, то многие пользователи предпочтут прекратить работу и продолжить ее, когда система будет менее загружена. Планирование использования процессора применяется в качестве краткосрочного планирования процессов. Оно проводится, к примеру, при обращении исполняющегося процесса к устройствам ввода-вывода или просто по завершении определенного интервала времени. Поэтому краткосрочное планирование осуществляется, как правило, не реже одного раза в 100 миллисекунд. Выбор нового процесса для исполнения оказывает влияние на функционирование системы до наступления очередного аналогичного события, т. е. в течение короткого промежутка времени, чем и обусловлено название этого уровня планирования – краткосрочное. Краткосрочное планирование осуществляется не реже одного раза в 100 миллисекунд. В некоторых вычислительных системах бывает выгодно для повышения производительности временно удалить какой-либо частично выполнившийся процесс из оперативной памяти на диск, а потом вернуть его обратно на исполнение. Такая процедура получила название swapping – перекачка. 6. Цели и критерии планирования процессов Выборы конкретного алгоритма определяется целями, которые мы хотим достичь, используя планирование. К числу целей относятся следующие: Справедливость – гарантировать каждому заданию или процессу определенную часть времени использования процессора в компьютерной системе, стараясь не допустить возникновения ситуации, когда процесс одного пользователя занимает процессор, в то время как процесс другого пользователя так и не начал выполняться. Эффективность – постараться занять процессор на все 100% рабочего времени, не позволяя ему простаивать в ожидании процессов, готовых к исполнению. В реальных вычислительных системах загрузка процессора колеблется от 40 до 90 %. Сокращение полного времени выполнения – обеспечить минимальное время между стартом процесса или постановкой задания в очередь для загрузки и его завершением. Сокращение времени отклика – минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя. Используются следующие критерии, позволяющие сравнивать алгоритмы краткосрочных планировщиков: 1. утилизация CPU (использование). Утилизация CPU теоретически может находиться пределах от 0 до 100%. В реальных системах утилизация CPU колеблется в пределах 40% для легко загруженного CPU, 90% для тяжело загруженного CPU. 2. пропускная способность CPU throughput. Пропускная способность CPU может измеряться количеством процессов, которые выполняются в единицу времени. 3. время оборота (turnaround time) для некоторых процессов важным критерием является полное время выполнения, то есть интервал от момента появления процесса во входной очереди до момента его завершения. Это время названо временем оборота и включает время ожидания во входной очереди, время ожидания в очереди готовых процессов, время ожидания в очередях к оборудованию, время выполнения в процессоре и время ввода - вывода. 4. время ожидания (waiting time). под временем ожидания понимается суммарное время нахождения процесса в очереди готовых процессов. 5. время отклика (response time) для сугубо интерактивных программ важным показателем является время отклика или время, прошедшее от момента попадания процесса во входную очередь до момента первого обращения к терминалу. Очевидно, что простейшая стратегия краткосрочного планировщика должна быть направлена на максимизацию средних значений загруженности и пропускной способности, времени ожидания и времени отклика. В ряде случаев используются сложные критерии, например так называемый минимаксный критерий, то есть вместо простого критерия минимум среднего времени отклика используется следующий — минимум максимального времени отклика. 7. Свойства и параметры алгоритмов планирования процессов Предсказуемость. Одно и тоже задание должно выполняться приблизительно за одно и то же время. Минимальные накладные расходы. Если на 100 миллисекунд, выделенные процессу для исполнения процессора, будет приходиться 200 миллисекунд на определение того, какой процесс получит процессор в свое распоряжение, и на переключение контекста, то такой алгоритм применять не стоит. Равномерная загрузке ресурсов вычислительной системы. Предпочтение должно отдаваться тем процессам, которые будут занимать малоиспользуемые ресурсы. Масштабируемость. Процессы не должны сразу терять работоспособность при увеличении нагрузки. Например, рост количества процессов в два раза не должно приводить к увеличению полного времени выполнения процессов на порядок. Все параметры планирования делятся на две группы: статические и динамические. Статические параметры не изменяются в ходе функционирования вычислительной системы, динамические – подвержены постоянным изменениям. К статическим параметрам относятся предельные значения ресурсов системы (размер ОЗУ, количество подключенных устройств ввода – вывода и др.). динамические параметры системы описывают количество свободных ресурсов на данный момент времени. К статическим параметрам процессов относятся характеристики, которые присущи заданиям на этапе загрузки: сл.14. 1. Каким пользователем загружен процесс или сформировано задание. 2. Важность поставленной задачи и ее приоритет. 3. Сколько процессорного времени запрошено пользователем для решения задачи. 4. Каково соотношение процессорного времени и времени, необходимого для осуществления операций ввода – вывода. 5. Какие ресурсы вычислительной системы и в каком количестве необходимы заданию. Алгоритмы долгосрочного планирования используют в своей работе статические и динамические параметры вычислительной системы и статические параметры процессов (динамические параметры процессов на этапе загрузки задания еще не известны). Алгоритмы краткосрочного и среднесрочного планирования дополнительно учитывают и динамические характеристики процессов. Для среднесрочного планирования в качестве характеристик может выступать следующая информация: (картинка) 1. Сколько времени прошло с момента выгрузки процесса на диск или его загрузки в оперативную память; 2. Сколько оперативной памяти занимает процесс; 3. Сколько процессорного времени уже предоставлено процессу. Сл.15. А=2 В=2 CPU burst Read c Ожидание окончания ввода I/O burst A=a+c*b Print a CPU burst Ожидание окончания вывода I/O burst Фрагмент деятельности процесса с выделением промежутков непрерывного использования процессора и ожидания ввода – вывода. CPU burst – промежуток времени непрерывного использования процессора. I/O burst – промежуток времени непрерывного ожидания ввода - вывода. Вытесняющее и не вытесняющее планирование. Процесс планирования осуществляется частью операционной системы, которая называется планировщик. Операционная система, обеспечивающая режим мультипрограммирования, обычно включает два планировщика — долгосрочный (long term scheduler) и краткосрочный (short term scheduler/CPU scheduler). Планировщик может принимать решения о выборе для исполнения нового процесса из числа находящихся в состоянии готовность в следующих четырех случаях: (картинка). Сл. 16 1. когда процесс переводится из состояния исполнение в состояние завершил исполнение. 2. когда процесс переводится из состояния исполнение в состояние ожидание ( например, после прерывания по таймеру). 3. когда процесс переводится из состояния исполнение в состояние готовность (завершение операции ввода –вывода). 4. Когда процесс переводится из состояния ожидание в состояние готовность (завершилась операция ввода-вывода или произошло другое событие). В случаях 1 и 2 процесс, находившийся в состоянии исполнение, не может дальше исполняться и для выполнения необходимо выбрать новый процесс. В случаях 3 и 4 планирование может не проводиться, процесс, который исполняется до прерывания, может продолжить свое выполнение после обработки прерывания. Если планирование осуществляется только в случаях 1 и 2 говорят, что имеет место невытесняющее планирование. В противном случае говорят о вытесняющем планировании. Термин, вытесняющее планирование возник потому что исполняющийся процесс помимо своей воли может быть вытеснен из состояния исполнение другим процессом. Невытесняющее планирование используется в ОС Windows 3.1. при таком режиме планирования процесс занимает столько процессорного времени, сколько ему необходимо. При этом переключение процессов возникает только при желании самого исполняющего процесса передать управление. Вытесняющее планирование обычно используется в системах разделения времени. В этом режиме планирования процесс может быть приостановлен в любой момент исполнения. ОС устанавливает специальный таймер для генерации сигнала прерывания по истечении некоторого промежутка времени- квант. После прерывания процессор передается в распоряжение другого процесса. Временные прерывания помогают гарантировать приемлемое время отклика процессов для пользователей, работающих в диалоговом режиме и предотвращают зависание компьютерной системы из – за зацикливания какой – либо программы. 8. Алгоритмы планирования процессов Алгоритм First=Come, First – Server (FCFS). Простейший алгоритм планирования – обозначает – первый пришел, первым обслужен. предположим, что процессы, находящиеся в состоянии ГОТОВНОСТЬ выстроены в очередь. Когда процесс переходит в состояние ГОТОВНОСТЬ, то ссылка на всю информацию необходимую для совершения операций над ним помещается в конец этой очереди. Будем называть ссылку блоком управления процессом (PCB- Process Control Block). Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на его PCB.очередь такого типа имеет специальное название – FIFO – First In, First Out. Такой алгоритм выбора процесса осуществляет невытесняющее планирование. Процесс, получивший в свое распоряжение процессор, занимает его до истечении текущего CPU burst. (прерывание). После этого, для выполнения выбирается новый процесс из начала очереди. Преимуществом алгоритма FCFS является легкость его реализации. Стратегии FCFS присущ так называемый “эффект конвоя”. В том случае, когда в компьютере имеется один большой процесс и несколько малых, то все процессы собираются в начале очереди готовых процессов, а затем в очереди к оборудованию. Таким образом, “эффект конвоя” приводит к снижению загруженности как процессора, так и периферийного оборудования. Для демонстрации недостатков рассмотрим пример: Сл. 17.Пусть в состоянии ГОТОВНОСТЬ находятся три процесса p0,p1,p2, для которых известно время их прерываний. Это время представлено в некоторых условных единицах. Таблица 1. Процесс Р0 Р1 Р2 Продолжительность очередного CPU burst 13 4 1 Для простоты будем предполагать, что деятельность процессов ограничивается использованием только одного промежутка CPU burst, что процессы не выполняют операции ввода – вывода и что время переключения контекста так мало. Что им можно пренебречь. Если процессы расположены в очередь процессов, то картина их исполнения показана на рис. 1. Первым для выполнения выбирается процесс р0, который получает процессор на все время своего CPU burst – на 13 единиц. После его окончания в состояние ИСПОЛНЕНИЕ переводится процесс р1, он занимает процессор 4 единицы времени, далее в состояние исполнение переводится процесс р2. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Р0 И И И И И И И И И И И И И Р1 Г Г Г Г Г Г Г Г Г Г Г Г Г И И И И Р2 Г Г Г Г Г Г Г Г Г Г Г Г Г Г Г Г Г И Рис. 1. Выполнение процессов при порядке р0, р1, р2. Время ожидания для процесса р0 составляет 0 единиц, для процесса р1 – 13 единиц, для процесса р2 – 17 единиц (13+4). Таким образом, среднее время ожидания = (0+13+17)/3=10 единиц. Полное время выполнения для процесса р0 составляет 13 единиц, для процесса р1 – 17 единиц, для процесса р2 – 18 единиц. Среднее время выполнения равно (13+17+18)/3=16 единиц. Если те же самые процессы расположены в порядке р2,р1,р0, то картина их выполнения будет другая (рис.2). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Р0 Г Г Г Г Г И И И И И И И И И И И И И Р1 Г И И И И Р2 И Рис. 2. Выполнение процессов при порядке р2,р1,р0. Время ожидания для процесса р0 равняется 5 единицам времени (4+1), для процесса р1 – 1, для процесса р2 – 0. среднее время ожидания составит (5+1+0)/3=2 единицы времени. Это в пять раз меньше, чем в предыдущем случае. Полное время выполнения для процесса р0 равно 18 единицам, для процесса р1 – 5 единицам, для процесса р2 – 1 единице. Среднее полное время выполнения составляет (18+5+1)/3=8 единицам. Это в два раза меньше, чем при первой расстановке процессов. Следовательно, среднее время ожидания и среднее полное время выполнения для этого алгоритма зависит от порядка расположения процессов в очереди. Если имеются процессы с длительным CPU burst, то короткие процессы, перешедшие в состояние ГОТОВНОСТЬ после длительного процесса будут долго ждать начала выполнения. Поэтому этот алгоритм неприменим для систем разделения времени. Алгоритм Round Robin (RR) По сути, это тот же самый алгоритм, только реализован в режиме вытесняющего планирования. Round Robin стратегия применяется в системах разделения времени. Можно представить себе множество готовых процессов организованных циклически – по принципу карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно около 10-100 миллисекунд. (рис.3). пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться. Реализуется этот алгоритм так же, как и предыдущий, с помощью организации процессов, находящихся в состоянии ГОТОВНОСТЬ, в очередь FIFO.планировщик выбирает для очередного исполнения процесс, расположенных в начале очереди и устанавливает таймер для генерации прерывания по истечении определенного кванта времени. При выполнении процесса возможны два варианта. 1 вариант: время непрерывного использования процессора, необходимое процессу (остаток текущего CPU burst, меньше или равно продолжительности кванта времени. Тогда процесс по своей воле освобождает процессор до истечения кванта времени, на исполнение поступает новый процесс из начала очереди, и таймер начинает отчет кванта заново. Готовность Готовность Процесс 1 Процесс 3 Готовность готовность готовность готовность Процесс 3 Процесс 2 Процесс 4 процесс 1 Исполнение Исполнение Процесс 4 Процесс 2 Процессор Процессор Начальный момент времени По прошествии кванта Рис. 3. Процессы на карусели 2 вариант : продолжительность остатка текущего CPU burst процесса больше, чем квант времени. Тогда, по истечении этого кванта процесс прерывается таймером и помещается в конец очереди процессов, готовых к исполнению, а процессор выделяется для использования процессу, находящемуся в ее начале. Рассмотрим предыдущий пример с порядком процессов р0, р1, р2 и величина кванта времени равной 4. выполнение этих процессов иллюстрируется таблицей 2. и- исполнение, г – готовность, пустые ячейки соответствуют завершившимся процессам. Состояние процессов показаны на протяжении соответствующей единицы времени, т.е. колонка с номером 1 соответствует промежутку времени от 0 до 1. Таблица 3. Время 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Р0 И И И И Г Г Г Г Г И И И И И И И И И Р1 Г Г Г Г И И И И Р2 Г Г Г Г Г Г Г Г И Первым для исполнения выбирается процесс р0. продолжительность его CPU burst больше, чем величина кванта времени, и поэтому процесс исполняется до истечении кванта, т.е. в течение 4 единиц времени. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид р1,р2,р0. Следующим начинает выполняться процесс р1. время его исполнения совпадает с величиной выделенного кванта, поэтому, процесс работает до своего завершения. Теперь очередь процессоров в состоянии ГОТОВНОСТЬ р2 и р0. процессор выделяется процессу р2. Он завершается до истечения отпущенного ему процессорного времени, и очередные кванты отмеряются процессу р0- единственному процессу, не закончившему к этому времени свою работу. Время ожидания для процесса р0 составляет 5 единиц, для процесса р1 – 4 единицы, для процесса р2 – 8 единиц. Среднее время ожидания равно (5+4+8)/3=5,6 единиц времени. Полное время выполнения для процесса р0 – 18 единиц времени (нет пустых клеток), для процесса р1 – 8 единиц, для процесса р2 -9 единиц. Среднее полное время выполнения процесса равно (18+8+9)/3 = 11,6 единиц. На производительность алгоритма RR сильно влияет величина кванта времени. Рассмотрим тот же пример, с порядком процессов р0, р1, р2 для величины кванта времени равной 1(иабл.40. Таблица 4 Время 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Р0 И Г Г И Г И Г И Г И И И И И И И И И Р1 Г И Г Г И Г И Г И Р2 Г Г И Время ожидания для процесса р0 составляет 5 единиц, для процесса р1 – 5 единиц, для процесса р2 – 2 единицы. Среднее время ожидания равно (5+5+2)3=4. среднее полное время исполнения равно (18+9+3)/3=10 единиц. При очень больших величинах кванта времени, когда каждый процесс успевает завершить свой CPU burst до возникновения прерывания по времени алгоритм RR вырождается в алгоритм FCFS. При очень малых величинах создается иллюзия того, что каждый из n процессов работает на собственном виртуальном процессоре с производительностью 1/n от производительности реального процессора. Алгоритм Shortest –Job – First (SJF) При рассмотрении предыдущих алгоритмов видно, что для них существенным является порядок расположения процессов в очереди. Если короткие задачи расположены в очереди ближе к ее началу, то общая производительность их исполнения значительно возрастает. Если бы знать время следующих CPU burst для процессов, находящихся в состоянии ГОТОВНОСТЬ , то могли бы выбрать для исполнения не процесс из начала очереди, а процесс с минимальной длительностью CPU burst. Если же таких процессов два или больше, то для выбора одного из них можно было использовать FCFS. Квантирование времени при этом не применяется. Описанный алгоритм получил название «кратчайшая работа первой». SJF- Алгоритм является одним из методов борьбы с “эффектом конвоя” , позволяющая процессу из очереди выполняться первым если он имеет кратчайшее время исполнения. Алгоритм краткосрочного планирования может быть как вытесняющим, так и не вытесняющим. При невытесняющем SJF- планировании процессор предоставляется избранному процессу на все необходимое ему время, независимо от событий, происходящих в вычислительной системе. При вытесняющем SJF- планировании учитывается появление новых процессов в очереди готовых к исполнению (из числа вновь родившихся или разблокированных) во время работы выбранного процесса. Если CPU burst нового процесса меньше, чем остаток CPU burst у исполняющегося. То исполняющий процесс вытесняется новым. Рассмотрим пример работы невытесняющего алгоритма SJF. Пусть в состоянии готовность находятся четыре процесса р0, р1, р2, р3 для которых известны времена их очередных CPU burst. (табл.4) Таблица 5. Процесс Р0 Р1 Р2 Р3 Продолжительность очередного CPU burst 5 3 7 1 При использовании невытесняющего алгоритма SJF первым для исполнения будет выбран процесс р3, имеющий наименьшее значение очередного CPU burst. После его завершения выбирается процесс р1, затем, р0, и. наконец, р2 (табл.5). Таблица 5. Время 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Р0 Г Г Г Г И И И И И Р1 Г И И И Р2 Г Г Г Г Г Г Г Г Г И И И И И И И И И Р3 И Среднее время ожидания для алгоритма составляет (4+1+9)/4=3,5 единиц времени. Задание на лекции. Самостоятельно подсчитать среднее время ожидания для алгоритма FCFS (ответ – 7 единиц) (0+5+8+15)/4. это время в два раза больше, чем у алгоритма SJF. Можно показать, что для заданного набора процессов (если в очереди не появляются новые процессы) алгоритм SJF является оптимальным с точки зрения минимизации среднего времени ожидания среди класса невытесняющих алгоритмов. Для примера возьмем четыре процесса с различных временем CPU burst и различными моментами их появления в очереди процессов, готовых к исполнению (табл.6). Таблица 6 Процесс Время появления в очереди очередного CPU burst Продолжительность Р0 6 Р1 2 2 Р2 6 7 Р3 5 В начальным момент времени в состоянии готовность находятся только два процесса р0 и р3. меньшее время очередного CPU burst оказывается у процесса р3 (5), поэтому он выбирается для исполнения. По прошествии двух единиц времени в систему поступает процесс р1. время его CPU burst меньше чем остаток CPU burst у процесса р3, который вытесняется из состояния ИСПОЛНЕНИЕ и переводится в состояние ГОТОВНОСТЬ. По прошествии еще 2 единиц времени процесс р1 завершается, и для исполнения выбирается процесс р3. в момент времени t=6 в очереди процессов, готовых к исполнению, появляется процесс р2, но поскольку ему для исполнения нужно еще 7 единиц времени, а процессу р3 осталось трудится только 1 единицу времени, то процесс р3 остается в состоянии ИСПОЛНЕНИЕ. После его завершения в момент времени t=7 в очереди находятся процессы р0 и р2, из которых выбирается процесс р0. последним получит возможность выполняться процесс р2. Таблица 7. Время 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Р0 Г Г Г Г Г Г Г И И И И И И Р1 И И Р2 Г Г Г Г Г Г Г И И И И И Р3 И И Г Г И И И Основную сложность при реализации алгоритма SJF представляет невозможность точного знания времени очередного CPU burst для исполняющих процессов. В пакетных системах количество процессорного времени , необходимое заданию для исполнения указывает пользователь при формировании задания. Эту величину можно использовать для долгосрочного SJF – планирования. Если пользователь укажет больше времени, чем ему нужно, то он будет ждать результата дольше, чем мог бы, т.к. задание будет загружено в систему позже. Если он укажет меньше время исполнения, то задача может быть обсчитана не до конца. При краткосрочном планировании можно делать только прогноз длительности следующего CPU-burst исходя из предыстории работы процесса. Пусть (n) - величина n-го CPU-burst, T(n+1) – предсказываемое значение для n+1 CPU-burst,  - некоторая величина в диапазоне от 0 до1. определим рекуррентное соотношение: T(n+1)= (n)+(1-) T(n). T(0) – положим произвольной константой. Первое слагаемое учитывает последнее поведение процесса. Второе слагаемое учитывает его предысторию. При =0 мы имеем только предысторию. Фактически это выглядит так: T(n+1)= T(n)… T(0) Если =1, тогда получаем: T(n+1)= (n). В этом случае полагаем, что время очередного CPU burst будет совпадать со временем последнего CPU burst. Обычно выбирают =1/2 для равноценного учета последнего поведения и предыстории. Гарантированное планирование. При интерактивной работе N пользователей в вычислительной системе можно применить алгоритм планирования, который гарантирует, что каждый из пользователей будет иметь в своем распоряжении 1/N часть процессорного времени. Пронумеруем всех пользователей от 1 до N, для каждого пользователя введем две величины Ti – время нахождения пользователей в системе (длительность сеанса), i – суммарное процессорное время уже выделенное всем его процессам в течение сеанса. Справедливым для пользователя было бы получение Ti/N процессорного времени. Если: . то i- тый пользователь несправедливо обделен процессорным временем. Если же , то система благоволит к пользователю с номером i. вычислим для каждого пользовательского процесса значение коэффициента справедливости: и будем представлять очередной квант времени процессу с наименьшей величиной отношения. Этот алгоритм называют алгоритм гарантированного планирования. К недостаткам этого алгоритма относят невозможность предугадать поведение пользователей. Приоритетное планирование. При приоритетном планировании каждому процессу присваивают определенное числовое значение – приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FCFS. Для алгоритма SJF в качестве приоритета выступает оценка продолжительности следующего CPU Burst. Чем меньше значение этой оценки, тем более высокий приоритет имеет процесс. Для алгоритма гарантированного планирования приоритетом служит вычисленный коэффициент справедливости. Чем он меньше, тем больше у процесса приоритет. Приоритет - это число, характеризующее степень привилегированности процесса при использовании ресурсов вычислительной машины, в частности, процессорного времени: чем выше приоритет, тем выше привилегии. Приоритет может выражаться целыми или дробными, положительным или отрицательным значением.Чем выше привилегии процесса, тем меньше времени он будет проводить в очередях. Приоритет может назначаться директивно администратором системы в зависимости от важности работы или внесенной платы, либо вычисляться самой ОС по определенным правилам, он может оставаться фиксированным на протяжении всей жизни процесса либо изменяться во времени в соответствии с некоторым законом. В последнем случае приоритеты называются динамическими. Существует две разновидности приоритетных алгоритмов: алгоритмы, использующие относительные приоритеты, и алгоритмы, использующие абсолютные приоритеты. В обоих случаях выбор процесса на выполнение из очереди готовых осуществляется одинаково: выбирается процесс, имеющий наивысший приоритет. По разному решается проблема определения момента смены активного процесса. В системах с относительными приоритетами активный процесс выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ОЖИДАНИЕ (или же произойдет ошибка, или процесс завершится). В системах с абсолютными приоритетами выполнение активного процесса прерывается еще при одном условии: если в очереди готовых процессов появился процесс, приоритет которого выше приоритета активного процесса. В этом случае прерванный процесс переходит в состояние готовности. Планирование с использованием приоритетов может быть вытесняющим и невытесняющим. При вытесняющем планировании процесс с более высоким приоритетом, появившийся в очереди готовых к исполнению процессов, вытесняет исполняющийся процесс с более низким приоритетом. В случае невытесняющего планирования он становится в начало очереди готовых процессов. Пример. (табл.1) Процесс Время появления в очереди Продолжительность очередного CPU Burst Приоритет P0 6 4 P1 2 2 3 P2 6 7 2 P3 5 1 Пусть в очередь процессов, находящихся в состоянии готовность, поступают те же процессы, что и в примере для вытесняющего алгоритма SJF, только им дополнительно присвоены приоритеты (табл.1). Пример для не вытесняющего планирования. Будем считать что большее значение соответствует наименьшему приоритету. Наибольший приоритет у процесса Р3, наименьший – у процесса Р0. Время 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Р0 Г Г Г Г Г Г Г Г Г Г Г Г Г Г И И И И И И Р1 Г Г Г И И Р2 Г И И И И И И И Р3 И И И И И Первым для выполнения в момент времени т=0 выбирается процесс 3. т.к. обладает наибольшим приоритетом. После его завершения в момент времени 5 в очередь готовых процессов выступают процессы Р0 и Р1. больший приоритет у процесса Р1 и он начинает исполняться. Затем в момент времени = 8 начинает исполняться процесс р2 и лишь потом процесс р0. В случае вытесняющего планирования : Время 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Р0 Г Г Г Г Г Г Г Г Г Г Г Г Г Г И И И И И И Р1 Г Г Г И Г Г Г Г Г Г Г И Р2 И И И И И И И Р3 И И И И И Первым, как И В Предыдущем Случае будет выполняться процесс Р3. затем будет выполняться процесс Р1, но в момент времени =6 он будет вытеснен процессор Р2 и продолжит свое выполнение только в момент времени =13 он вновь продолжит свое исполнение. Последним, как и раньше будет исполняться процесс Р0. Главная проблема приоритетного планирования заключается в том, что при ненадлежащем выборе механизма назначения и изменения приоритетов низкоприоритетные процессы могут не запускаться неопределенно долгое время. Обычно случается одно из двух: или они все дожидаются своей очереди на исполнение или вычислительную систему приходится выключать и они теряются.