Алгоритмы сканирования (SCAN, LOOK)

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

63 55 31 23 14 10 7 0 67 84

и всего головки переместятся на 147 цилиндров.

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

63 55 31 23 14 10 7 67 84

и всего головки переместятся на 133 цилиндра. Полученная модификация алгоритма SCAN получила название LOOK.

 

Управление процессами. Основные состояния процесса

Процесс (process) это программа пользователя при ее выполнении. При своей работе операционная системы исполняет множество классов программ: пакетные задания; пользовательские программы в режиме разделения времени; системные программы и процессы. Имеется несколько схожих терминов, характеризующих пользовательские программы: процесс (process), задание (job), задача (task) Однако не будем здесь преувеличивать различие между ними: для лучшего понимания специфики процессов и управления ими в ОС, мы можем считать приведенные термины синонимами, как и считается во многих учебниках по ОС.

Важная особенность процесса: это единица вычислений, которая должна выполняться последовательно, т.е. каждый процесс имеет свой последовательный поток управления (control flow) – последовательность выполняемых процессом команд.

Процесс при его создании и управлении им операционной системой включает следующую основную информацию:

· Счетчик команд (program counter - PC) – адрес текущей выполняемой команды процесса; обычно хранится в специальном системном регистре аппаратуры;

· Стек (stack) – резидентная область основной памяти, выделяемая операционной системой при создании процесса, в которой хранятся локальные данные процедур процесса, их параметры (аргументы) и связующая информация между ними, необходимая для организации вычислений. При запуске очередной процедуры в стеке отводится запись активации (activation record),называемая также стековым фреймом (stack frame) и областью локальных данных (local data area) для хранения локальных данных текущего поколения (запуска) процедуры. По окончании ее выполнения запись активации удаляется из стека;

Секция данных (data section) – статическая (постоянно выделенная, неизменного размера) область основной памяти, выделяемая операционной системой процессу, в которой хранятся его глобальные переменные, массивы, структуры, объекты.

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

 

Состояния процесса

При исполнении процесс может изменять свое состояние следующим образом:

Новый (new):Процесс создается операционной системой, но еще не начал выполняться.

Исполняемый (running):Исполняются команды процесса на процессоре или процессорах компьютерной системы под управлением ОС.

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

Готовый к выполнению (ready):Процесс ожидает получения ресурсов процессора для его исполнения. В состояние готовности к выполнению процесс попадает обычно либо при его создании, либо после завершения ввода-вывода (из состояния ожидания).

Завершенный (terminated):Исполнение процесса завершено.

Как видно из схемы, новый процесс, созданный в системе, проходит стадию допущен (admitted) – включается операционной системой в очередь всех процессов в системе, после чего ОС переводит его в состояние готовности к выполнению. Отметим сразу, что очередь готовых к выполнению процессов – одна из наиболее часто используемых системных структур для управления процессами. Из состояния готовности в состояние выполнения процесс переводится планировщиком ОС в результате диспетчеризации – выделения кванта процессорного времени. При выполнении процесс может быть прерван (по таймеру, в результате ошибки и т.п.), а после обработки прерывания операционной системой переходит снова в состояние готовности к выполнению. Если в процессе выполняется синхронный ввод-вывод, либо процесс должен ожидать наступления некоторого события (например, определенного момента времени), процесс переходит в состояние ожидания. При завершении ввода-вывода или при наступлении ожидаемого события процесс не получает сразу же квант процессорного времени, а переходит в состояние готовности к выполнению. Процесс переходит в завершенное состояние при завершении работы программы процесса - например, в результате системного вызова exit(c), где c – код завершения. Если c = 0,процесс считается благополучно завершенным.

 

 

30. Планирование процессов (задач). Алгоритмы планирования

Планирование заданий используется в качестве долгосрочного планирования процессов. Оно отвечает за порождение новых процессов в системе, определяя ее степень мультипрограммирования, т. е. количество процессов, одновременно находящихся в ней. Если степень мультипрограммирования системы поддерживается постоянной, т. е. среднее количество процессов в компьютере не меняется, то новые процессы могут появляться только после завершения ранее загруженных. Поэтому долгосрочное планирование осуществляется достаточно редко, между появлением новых процессов могут проходить минуты и даже десятки минут. Решение о выборе для запуска того или иного процесса оказывает влияние на функционирование вычислительной системы на протяжении достаточно длительного времени. Отсюда и название этого уровня планирования – долгосрочное. В некоторых операционных системах долгосрочное планирование сведено к минимуму или отсутствует вовсе. Так, например, во многих интерактивных системах разделения времени порождение процесса происходит сразу после появления соответствующего запроса. Поддержание разумной степени мультипрограммирования осуществляется за счет ограничения количества пользователей, которые могут работать в системе, и особенностей человеческой психологии. Если между нажатием на клавишу и появлением символа на экране проходит 20–30 секунд, то многие пользователи предпочтут прекратить работу и продолжить ее, когда система будет менее загружена.

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

Цели планирования:

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

· Эффективность – постараться занять процессор на все 100% рабочего времени, не позволяя ему простаивать в ожидании процессов, готовых к исполнению. В реальных вычислительных системах загрузка процессора колеблется от 40 до 90%.

· Сокращение полного времени выполнения (turnaround time) – обеспечить минимальное время между стартом процесса или постановкой задания в очередь для загрузки и его завершением.

· Сокращение времени ожидания (waiting time) – сократить время, которое проводят процессы в состоянии готовность и задания в очереди для загрузки.

· Сокращение времени отклика (response time) – минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя.

 

Алгоритмы планирования:

· First-Come, First-Served (FCFS) (первым пришел, первым обслужен)

· Round Robin(RR)(тот же но реализованный в режиме вытесняющего планирования)

· Shortest-Job-First (SJF) (может быть и вытесняющим и невытесняющим)

· Гарантированное планирование(гарантир.что Пользов-ль буд. Иметь 1/Nчасть процесс.времени)

· Приоритетное планирование(каждому процессу присваивается определенное числовое значение – приоритет, в соответствии с которым ему выделяется процессор.)

· Многоуровневые очереди (Multilevel Queue)

· Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)

 

 

Дисциплина диспетчеризации процессов (задач) FCFS

Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS по первым буквам его английского названия – First-Come, First-Served (первым пришел, первым обслужен). Представим себе, что процессы, находящиеся в состоянии готовность, выстроены в очередь. Когда процесс переходит в состояние готовность, он, а точнее, ссылка на его PCB помещается в конец этой очереди. Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на его PCB. Очередь подобного типа имеет в программировании специальное наименование – FIFO, сокращение от First In, First Out (первым вошел, первым вышел).

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

Таблица 3.1.
Процесс	p0	p1	p2
Продолжительность очередного CPU burst

Преимуществом алгоритма FCFS является легкость его реализации, но в то же время он имеет и много недостатков. Рассмотрим следующий пример. Пусть в состоянии готовность находятся три процесса p₀, p₁ и p₂, для которых известны времена их очередных CPU burst. Эти времена приведены в таблице 3.1. в некоторых условных единицах. Для простоты будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка CPU burst, что процессы не совершают операций ввода-вывода и что время переключения контекста так мало, что им можно пренебречь.

Если процессы расположены в очереди процессов, готовых к исполнению, в порядке p₀, p₁, p₂, то картина их выполнения выглядит так, как показано на рисунке 3.2. Первым для выполнения выбирается процесс p₀, который получает процессор на все время своего CPU burst, т. е. на 13 единиц времени. После его окончания в состояние исполнение переводится процесс p₁, он занимает процессор на 4 единицы времени. И, наконец, возможность работать получает процесс p₂. Время ожидания для процесса p₀ составляет 0единиц времени, для процесса p₁ – 13 единиц, для процесса p₂ – 13 + 4 = 17 единиц. Таким образом, среднее время ожидания в этом случае – (0 + 13 + 17)/3 = 10 единиц времени. Полное время выполнения для процесса p₀ составляет 13 единиц времени, для процесса p₁ – 13 + 4 = 17 единиц, для процесса p₂ – 13 + 4 + 1 = 18 единиц. Среднее полное время выполнения оказывается равным (13 + 17 + 18)/3 = 16 единицам времени.

Рис. 3.2. Выполнение процессов при порядке p0,p1,p2

 

 

Дисциплина диспетчеризации процессов (задач) RR

Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin (Round Robin – это вид детской карусели в США) или сокращенно RR. По сути дела, это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованным циклически – процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10 – 100 миллисекунд (см. рис. 3.4.). Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.

Рис. 3.4. Процессы на карусели

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

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

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

Первым для исполнения выбирается процесс p₀. Продолжительность его CPU burst больше, чем величина кванта времени, и поэтому процесс исполняется до истечения кванта, т. е. в течение 4 единиц времени. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид p₁, p₂, p₀. Следующим начинает выполняться процесс p₁. Время его исполнения совпадает с величиной выделенного кванта, поэтому процесс работает до своего завершения. Теперь очередь процессов в состоянии готовность состоит из двух процессов, p₂ и p₀. Процессор выделяется процессу p₂. Он завершается до истечения отпущенного ему процессорного времени, и очередные кванты отмеряются процессу p₀ – единственному не закончившему к этому моменту свою работу. Время ожидания для процесса p₀ (количество символов "Г" в соответствующей строке) составляет 5единиц времени, для процесса p₁ – 4 единицы времени, для процесса p₂ – 8 единиц времени. Таким образом, среднее время ожидания для этого алгоритма получается равным (5 + 4 + 8)/3 = 5,6(6) единицы времени. Полное время выполнения для процесса p₀ (количество непустых столбцов в соответствующей строке) составляет 18 единиц времени, для процесса p₁ – 8 единиц, для процесса p₂ – 9 единиц. Среднее полное время выполнения оказывается равным (18 + 8 + 9)/3 = 11,6(6) единицы времени.