Презентация на тему Планирование процессов. (Лекция 6)

Содержание

Слайды и текст этой презентации

Слайд 1Планирование процессов Лекция 6

Планирование процессов  Лекция 6

Слайд 2Понятия: задание, процесс, планирование процесса
Процесс – это минимальный программный объект, обладающий

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

Слайд 3Состояния существования процесса
Различают следующие состояния процесса:
новый (процесс только что создан);
выполняемый (команды

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

Состояния существования процессаРазличают следующие состояния процесса:новый (процесс только что создан);выполняемый (команды программы

Слайд 4Типовая диаграмма переходов для состояний процессов.
Состояния существования процесса

Типовая диаграмма переходов для состояний процессов.Состояния существования процесса

Слайд 5Диспетчеризация процесса
Диспетчеризация процессов (задач) – это определение очередности получения процессора для процессов

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

Слайд 6Способ выбора процесса для диспетчеризации
Наиболее важные дисциплины диспетчеризации.
FCFS (first come –

first served – первым пришёл, первым обслужился ) – прежде процессор получает та задача, которая раньше перешла в состояние готовности. Данная дисциплина проста в реализации, равноправна по отношению как к “длинным ” так и к “коротким” процессам, среднее время пребывания в очереди готовности весьма значительное.
SJN (shortest job next – следующий с кратчайшим заданием) – прежде процессор получает та задача, которая имеет минимальное заказное время обслуживания. Данная дисциплина требует, чтобы для каждой задачи была известна оценка потребности в машинном времени, значение которой задаётся как параметр задачи. Такая дисциплина более сложна в реализации по сравнению с FCFS, она дискриминационна по отношению к “длинным процессам”, среднее время пребывания в очереди готовности меньше чем для FCFS. SJN имеет существенный недостаток. Задачи, которые были временно заблокированы (например, ожидали завершения ввода/вывода), в результате попадут в конец очереди готовности, даже если для их выполнения требуется небольшое процессорное время.

Способ выбора процесса для диспетчеризацииНаиболее важные дисциплины диспетчеризации.FCFS (first come – first

Слайд 7SRT (shortest remaining time) – прежде процессор получает задача, которая имеет

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

Способ выбора процесса для диспетчеризации

SRT (shortest remaining time) – прежде процессор получает задача, которая имеет меньше

Слайд 8Рассмотрим некоторые основные вытесняющие дисциплины диспетчеризации:
RR (round robin) – циклическая (карусельная)

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

Способ выбора процесса для диспетчеризации

Рассмотрим некоторые основные вытесняющие дисциплины диспетчеризации:RR (round robin) – циклическая (карусельная) дисциплина.

Слайд 9Дисциплины на основе абсолютных приоритетов задач. Каждая задача имеет приоритет, выраженный конкретным значением,

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

Способ выбора процесса для диспетчеризации

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

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

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

Способ выбора процесса для диспетчеризации

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

Слайд 11Блок состояния процесса
Время жизни процесса можно теоретически разбить на несколько состояний,

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

Слайд 12Процесс возвращен из привилегированного режима (режима ядра) в непривилегированный (режим задачи),

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

Блок состояния процесса

Процесс возвращен из привилегированного режима (режима ядра) в непривилегированный (режим задачи), ядро

Слайд 13Алгоритмы диспетчеризации
Алгоритм разделения времени
Простейший алгоритм диспетчеризации процессов (или потоков) состоит в

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

Слайд 14Алгоритм родственного планирования
Основная идея данного алгоритма заключается в том, чтобы поток

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

Алгоритмы диспетчеризации

Алгоритм родственного планированияОсновная идея данного алгоритма заключается в том, чтобы поток был

Слайд 15Алгоритм родственного планирования
Двухуровневое планирование обладает тремя преимуществами:
Оно довольно равномерно распределяет нагрузку

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

Алгоритмы диспетчеризации

Алгоритм родственного планированияДвухуровневое планирование обладает тремя преимуществами:Оно довольно равномерно распределяет нагрузку среди

Слайд 16Совместное использование пространства (процессоров)
Другой подход к планированию мультипроцессоров может быть использован,

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

Алгоритмы диспетчеризации

Совместное использование пространства (процессоров)Другой подход к планированию мультипроцессоров может быть использован, если

Слайд 17Совместное использование пространства (процессоров)
Каждый поток выполняется на своем процессоре вплоть до

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

Алгоритмы диспетчеризации

Совместное использование пространства (процессоров)Каждый поток выполняется на своем процессоре вплоть до завершения,

Слайд 18Совместное использование пространства (процессоров)
В этой простой модели разбиения процессоров на группы

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

Алгоритмы диспетчеризации

Совместное использование пространства (процессоров)В этой простой модели разбиения процессоров на группы процесс

Слайд 19Бригадное планирование
Множество потоков процесса распределяются для одновременного выполнения на множестве процессоров,

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

Алгоритмы диспетчеризации

Бригадное планированиеМножество потоков процесса распределяются для одновременного выполнения на множестве процессоров, по

Слайд 20Бригадное планирование
Бригадное планирование состоит из трех частей:
Группы связанных потоков планируются как одно целое,

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

Алгоритмы диспетчеризации

Бригадное планированиеБригадное планирование состоит из трех частей:Группы связанных потоков планируются как одно целое, бригада.Все

Слайд 21Понятие события. Блок состояния события

Понятие события. Блок состояния события

Слайд 22Механизм установления соответствия между процессом и событием

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

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

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


Для правообладателей

Яндекс.Метрика