Понятие операционной системы; эволюция развития операционных систем; функции операционных систем и подходы к построению операционных систем



страница3/15
Дата14.04.2017
Размер0.56 Mb.
Просмотров4433
Скачиваний3
1   2   3   4   5   6   7   8   9   ...   15

Уровни планирования процессов в операционных системах. Основные цели и критерии планирования и параметры, на которых оно основывается. Алгоритмы планирования.


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

Планирование процессов включает в себя решение следующих задач:



  • определение момента времени для смены выполняемого процесса;

  • выбор процесса на выполнение из очереди готовых процессов;

  • переключение контекстов "старого" и "нового" процессов.

Диспетчеризация – реализация решения, найденного в результате планирования.

Задачи диспетчеризации:



  • сохранение контекста текущего потока

  • загрузка контекста нового потока

  • запуск нового потока на выполнение

Выделяют следующие уровни планирования:

  • долгосрочное

  • краткосрочное

  • среднесрочное

Долгосрочное планирование

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

  • осуществляется достаточно редко

  • оказывает влияние на функционирование вычислительной системы на протяжении достаточно длительного времени

  • в некоторых ОС сведено к минимуму или отсутствует вовсе

Краткосрочное планирование

  • осуществляется, как правило, не реже одного раза в 100 миллисекунд.

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

  • при планировании использования процессора

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

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



Критерии планирования и требования к алгоритмам

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



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

Справедливость

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



Эффективность

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

В реальных вычислительных системах загрузка процессора: 40% - 90%

Сокращение полного времени выполнения (turnaround time)

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



Сокращение времени ожидания (waiting time)

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



Сокращение времени отклика (response time)

Минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя



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

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

Свойства алгоритмов планирования

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



  • Предсказуемость. - Одно и то же задание должно выполняться приблизительно за одно и то же время.

  • Минимальные накладные расходы. tисполнения процесса>>tвыбора процесса Если на каждые 100 миллисекунд, выделенные процессу для использования процессора, будет приходиться 200 миллисекунд на определение того, какой именно процесс получит процессор в свое распоряжение, и на переключение контекста, то такой алгоритм, очевидно, применять не стоит. Независимо от целей планирования алгоритмы должны обладать следующими свойствами: Алгоритмы планирования

First-Come, First-Served (FCFS)

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


(+) : простота реализации

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

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

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

t1=13, t2=4, t3=1 => среднее время ожидания: (0+13+17)/3=10 единиц времени

среднее полное время выполнения: (13+17+18)/3=16 единиц времени

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



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

Среднее время ожидания: (5+1+0)/3=2 (в 5 раз <)

Среднее полное время выполнения: (18+5+1)/3=8 (в 2 раза <)

Round Robin (RR)

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



процессы на карусели
Процессы на карусели

На производительность алгоритма RR сильно влияет величина кванта времени:

при очень больших величинах кванта алгоритм RR вырождается в алгоритм FCFS

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

~ 1/n от производительности реального процессора.

Shortest-Job-First (SJF) Если выбирать процесс не по порядку (как в FCFS и RR), а основываясь на его минимальном времени непрерывного использования процессора, то это позволит повысить производительность алгоритма планирования использования процесса. Описанный алгоритм получил название «кратчайшая работа первой».

Основную сложность при реализации алгоритма SJF представляет невозможность точного значения времени выполнения очередного процесса.




  1. Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9   ...   15


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал