Управление процессами

Размещено на http://www.allbest.ru/

Лекция

Управление процессами

1. Определение процесса. Классификация процессов

процесс диспетчеризация стратегия

Понятие процесса является базовым, но системные и прикладные программисты определяют его по-разному. Архитектура любой ЭВМ многопроцессорная, т.к. процессор - это устройство в составе ЭВМ, способное самостоятельно выполнять некоторые действия по хранимой в памяти информации, кроме МП существуют контроллеры ББУ и т.д. Процесс -- некоторая деятельность, связанная с исполнением программы на МП.

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

Процессы, имеющие tоткл.<=tоткл.мах.=const называются интерактивными (текстовые редакторы). Остальные процессы называются пакетными.

2) Порождающий - тот, который создаёт новый процесс. Если порождённый процесс порождает ещё один, то он является и порождающим.

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

4) Если процессы не пересекаются во времени, то они называются последовательными, иначе - параллельными.

5) На ЦП исполняются программы, называемые внутренними процессами, а на процессорах, отличных от ЦП (контроллеры), под управлением ОС идут внешние процессы.

6) По выполняемым функциям:

а) системные;

б) пользовательские;

7) По взаимодействию:

а) изолированные;

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

в) косвенные; При косвенном взаимодействии, например, какой-нибудь внешний процесс может процесс может изменять трассу внутреннего. Порождающий процесс всегда связан с порождённым, при этом они могут быть информационно-независимыми.

8) По приоритету.

9) По использованию неделимых ресурсов (принтер):

а) взаимоисключающие;

б) совместные;

2. Этапы развития процессов

Любой процесс - динамическое явление ОС, которое характеризуется следующими стадиями развития:

1) Порождение (создание) - подготовка условий для выполнения действий на процессоре (выделение необходимых ресурсов, ввод данных и т.д.).

2) Активное состояние - исполнение программы на процессоре.

3) Состояние блокировки - программа не выполняется по причине занятости какого-либо ресурса.

4) Состояние готовности - программа не выполняется, но ей предоставлены все ресурсы, кроме времени ЦП.

5) Завершение - нормальное или аварийное завершение программы с изъятием всех ресурсов.

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

После выделения всех ресурсов и считывания программы в ОЗУ (пакетные процессы) или разрешения войти в систему (интерактивные) процесс создаётся и по (1) переходит в состояние готовности. В состоянии готовности сразу находятся несколько процессов, образующих очередь. По определённому алгоритму им выделяется время ЦП (tцп), и они по (2) переходят в активное состояние, выйти из которого можно по одной из 3 веток. По (6) процесс завершается. По (3) процесс блокирует себя, выдав запрос на дополнительный ресурс или на ввод/вывод, который необходимо сделать прежде чем процесс сможет продолжать своё выполнение. По (4) процесс снимается управляющей программой по окончании выделенных ему квантов времени и возвращается в состояние готовности. Это пример перераспределения ресурсов. Кроме tцп могут перераспределяться ОЗУ, ПУ и т.д. Процесс находится в блокировке, пока не будут выполняться ожидаемые действия. После этого управляющая программа по (5) переводит его в состояние готовности. Если деблокируемый процесс имеет высокий приоритет, то он может по (9) перейти в активное состояние, а текущий активный процесс - в готовность. Кроме того, по (6),(7),(8) процесс может аварийно завершаться. При управлении процессами ОС для каждого из них создаёт дескриптор процесса, где хранится вся необходимая информация о нём. Они хранятся в виде списков.

Наиболее вероятные состояния для процессов:

Пакетные процессы.

Обменные процессы.

Процессы реального времени (высокий приоритет).

3. Общие вопросы управления процессами

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

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

Диспетчер управляет выделением tцп готовому процессу. Этот процесс называется диспетчеризацией процесса.

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

4. Диспетчеризация процессов в системе с одной очередью

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

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

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

Усредняя времена для конкретного процесса можно получить среднее время ожидания. Усредняя эти времена по всем процессам можно получить общее время ожидания. Характеристика системы.

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

Наиболее простой способ реализации этого - обслуживание процессов в порядке их появления позволяет каждому из них выполниться до конца. Эта стратегия не переключает ЦП между задачами. Когда бывает блокировка, активной может на короткое время стать другая задача (First Come, First Served - FCFS). Очередь поддерживается в порядке увеличения времени создания процесса.

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

1) Среднее время ожидания может неограниченно увеличиваться по мере приближения системы к пределу своей загруженности.

2) С увеличением дисперсии времени выполнения увеличивается среднее время ожидания процесса. Например есть 3 задачи с временем. С t_цп.=1_сек, и одна с t_уп.=10_сек.

Чтобы избавиться от этих недостатков, нужно минимизировать общее среднее время ожидания. Для этого приоритет диспетчеризации должен основываться не на времени создания, а на времени его выполнения. Чем меньше tцп, тем выше приоритет (Shortest Job Next - SJN). Она как и FCFS не переключает ЦП между задачами.

Преимущества:

Она уменьшает общее среднее время ожидания, увеличивает количество задач, решаемых в единицу времени за счёт коротких процессов, но при этом увеличивается среднее время ожидания для длинных процессов и увеличивается дисперсия времени ожидания, поэтому трудно предсказать, когда процесс будет обслужен, что иногда бывает важно. В SJN можно ввести перераспределение процесса, удаляя активный процесс при появлении более короткого (например, после блокировки). Нелогично снимать с выполнения почти закончившийся процесс ради другого, у которого меньшее заказанное время по сравнению с активным процессом. В этом случае можно ориентироваться на оставшееся время. Такая стратегия называется Shortest Remaining Time - SRT. В этой стратегии всегда перераспределяется процессор, иначе она превращается в SJN. Можно показать, что при SRT достигается минимально возможное общее среднее время ожидания.

Все эти стратегии не подходят для интерактивных процессов. При запросе небольшого времени процесс получает большой приоритет, поэтому у пользователя может возникнуть желание искусственно занизить время. Для борьбы с этим можно либо удалять процесс из системы по окончанию заказанного времени, либо увеличивать стоимость дополнительного времени сверх заказанного. Существует проблема процессов с бесконечным циклом, поэтому почти всегда для процесса устанавливается максимально допустимое время выполнения. Можно более высоким приоритетом наделять процессы, требующие с определённой вероятностью малого процессорного времени - процессы с большим числом обменов, чем чаще обмены, тем чаще процесс находится в блокировке, поэтому очередь можно выстроить с увеличением времени с момента последнего обмена. Во всех этих стратегиях для снижения общего среднего времени ожидания задерживаются к выполнению длинные процессы, в некоторых системах они могут задерживаться навсегда. Поэтому необходимо к минимизации времени добавить требования гарантированного завершения всех процессов. Отсюда получается ряд новых стратегий. Наиболее популярная стратегия - Round Robin (RR).

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

q Каждый отрезок - процесс

Для этого любой процесс получает 1/n времени обхода круга, кроме того существуют системные затраты на переключение. Из-за расходов на переключение (S) общее время ожидания может быть больше, чем у FCFS (например), но при большой дискретизации времени выполнения оно может быть и меньше. RR широко применяется в интерактивных системах.

Важно правильно выбрать q. При большом q:

увеличивается время отклика;

при создании или деблокировании процесса отклик может сильно увеличиваться - неравномерность обслуживания;

Уменьшение q приводит к увеличению системных потерь. Оптимальное q зависит от физических особенностей человека (реакции) для интерактивных систем. Для реальных q = 100..2000 мс. В интерактивных системах важным параметром является время отклика (tоткл <= tоткл.max.)

Для систем с n процессами время отклика определяется:

tоткл.=(n-1)*(q+S)+S;

При увеличении n увеличивается tоткл.

n=( tоткл. -S)/(q+S)+1;

Для предотвращения больших потерь, предельным случаем будем предполагать q=S (q<=S), тогда максимальное число процессов:

nmax=(tоткл.max-S)/(2*S)+1= tоткл.max/(2*S)-1/2=1/2*( tоткл.max/S-1)

Если nmax меньше требуемого, нужно увеличить tоткл.max.

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

Ещё одно средство, гарантирующее выполнение длинных процессов - увеличение их приоритета с течением времени - учёт старения. В этом случае приоритет зависит от (tтекущее-tсоздания).

5. Планирование работ

Основная функция планировщика - управление ресурсами. Для интерактивных процессов планировщик решает, пускать ли нового пользователя в систему. Иногда число интерактивных пользователей ограничено физическими ресурсами (ОЗУ, число ПУ и т.д.).

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

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

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

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

установка максимального количества невыбирающих просмотров по достижению максимального процесс создаётся по специальному приоритету;

учёт старения;

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

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

Более общий - позволяет процессу создавать дочерний с использованием родительских ресурсов.

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

6. Системы с несколькими очередями

Возможен вариант:

Здесь организованно N очередей. Новый процесс поступает в конец 1-ой очереди. Запрос из очереди i поступает на обслуживание только тогда, когда очереди от 1 да i-1 пусты, тогда он переходит в активное состояние и ему выделяется квант времени q. Если он успевает завершиться, то переходит в стадию завершения, то переходит в стадию завершения, в противном случае он помещается в конец очереди i+1. Новый запрос всегда поступает в очередь 1. Для каждой очереди могут использоваться SCFS, RR и др. После блокировки номер очереди, как правило, уменьшается.

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

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

Абсолютный приоритет: Этот вариант используются во второй схеме. Если при обслуживании запроса из очереди i в систему поступает более приоритетный процесс, например i-1, обслуживание процесса i прерывается и система начинает обслуживать процесс i-1, а по завершению снова возвращается к процессу i. Эта схема ещё больше увеличивает дискретизацию между длинными и короткими процессами по отношению ко времени ожидания. Время обслуживания высокоприоритетных заявок уменьшается за счёт увеличения времени обслуживания низкоуровневых заявок. Достоинства: большая предсказуемость, определённость поведения. Недостатки: более сложная схема, усложнение системы из-за незапланированных прерываний для обработки и перераспределения ресурсов. При большой частоте могут сильно увеличиваться системные затраты. Проблема учёта не до конца использованного ресурса.

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

Размещено на Allbest.ru