Диспетчеризация процессов

Диспетчеризация процессов

Стратегии планирования. Дисциплины диспетчеризации. Вытесняющие и невытесняющие алгоритмы. Алгоритмы плани- рования без переключений. Циклическое и приоритетное планирование. Динамические приоритеты. Планирование в систе- мах реального времени. Планирование потоков. Гарантии обслуживания процесса

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

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

Планирование необходимо в следующих случаях:

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

2.  Завершение процесса. Необходимо выбрать из очереди готовых процессов.

3.  При блокировке процесса. Требуется выбор, какой процесс следующий. Иногда причина блокировки может влиять на вы- бор. Если А – высокоприоритетный процесс, и он блокируется в ожидании выхода процесса В из КС, то можно запустить процесс В, чтобы быстрее продолжил работу А.

4.  При прерывании в/в. Если прерывание пришло от устройства, завершившего операцию, можно запустить процесс, ожи- дающий именно этого устройства.

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

-          отдавать предпочтение коротким процессам

-          всем процесса предоставлять одинаковое время ожидания.

Дисциплина диспетчеризации – совокупность правил, в соответствии с которыми формируется очередь готовых к выпол- нению задач. Дисциплины диспетчеризации могут быть разбиты на 2 класса: вытесняющие и невытесняющие. Если после выбора процесса он работает вплоть до блокировки или пока сам не отдаст управление другому процессу, это невытеснящая многозадачность. Другими словами, используются алгоритмы планирования без переключений. В случае, когда принуди- тельно средствами ОС выполняется переключение между задачами, речь идет о вытесняющей многозадачности. При этом используются алгоритмы с переключениями. В современных ОС реализуется как правило вытесняющая многозадачность. Процесс выбирается и ему предоставляется какое-то количество времени. Если за этот отрезок процесс не завершил работы, он приостанавливается, и запускается другой процесс. Как правило, для организации переключений используется прерыва- ние от таймера. В случае вытесняющей многозадачности механизм диспетчеризации целиком сосредоточен в ОС, что снима- ет с программиста обязанность о передаче управления другим процессам системы, т.е. он может программировать задачу так, как если бы задача запускалась в однопроцессной системе. При невытесняющей многозадачности управление системой может теряться на некоторый (в общем случае на достаточно большой) период времени, величина которого в значительной мере зависит от степени эффективной передачи управления иным процессам. Примером такой системы может служить Windows 3.x.

Для сравнения алгоритмов диспетчеризации используют следующие критерии:

-          Загрузка центрального процессора. В большинстве персональных систем средняя загрузка процессора не превышает 2-3%, на серверах – до 20-40%

-          Пропускная способность. Измеряется количеством выполненных процессов за час

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

-          Время ожидания. Суммарное время нахождения процесса в очереди готовых процессов

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

Выбор конкретного алгоритма определяется классом решаемых задач и целями, которых стараются достичь. К таким целям относятся:

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

-          Эффективность. Процессор должен быть максимально нагружен. В идеальном варианте на 100%.

-          Сокращение полного времени выполнения -    Сокращение времени ожидания

-          Сокращение времени отклика.

Кроме того, желательно, чтобы алгоритмы обладали следующими свойствами:

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

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

-          равномерная загрузка ресурсов системы

-          масштабируемость, т.е. при увеличении нагрузки не должна теряться работоспособность алгоритма.

Классификация дисциплин диспетчеризации:

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

Диспетчеризация FCFS (First Come First Served) – в порядке очереди. Самый простой вариант, использует невытесняющие алгоритмы (без переключений). Задачи обслуживаются в том порядке, в котором они возникли. Как правило, формируется общая очередь задач. Задачи, которые были заблокированы в процессе выполнения, после окончания ожидания (блокировки) ставятся в очередь перед теми процессами, которые еще не выполнялись либо в конец очереди. В итоге реализуется страте- гия завершения процессов в том порядке, в котором они были начаты. Дисциплина не требует внешнего вмешательства в процесс вычислений, не происходит перераспределение процессорного времени. Эта дисциплина достаточно просто реали- зуются, требует малых затрат на реализацию очереди задач. Однако при увеличении нагрузки на систему, среднее время ожидания обслуживания возрастает. При этом короткие задачи ожидают столько же, сколько и длинные. Например, запус- каются три задачи, время выполнения которых составляет 13, 4, 1 квант машинного времени. Тогда время ожидания процес- сов составит: 0, 13, 13+4=17 квантов, а полное время выполнения 0+13=13, 13+4=17, 17+1=18 квантов, соответственно сред- нее время ожидания 0+13+17=30/3=10 квантов, среднее время выполнения 13+17+18=48/3=16 квантов. Т.о. среднее время ожидания и среднее полное время выполнения зависят от порядка расположения процессов, поэтому алгоритм практически неприменим в системах разделения времени – т.к. среднее время отклика велико.

Дисциплина SJN (shortest job next) – следующим выполняется кратчайшее задание. Для задач должна быть известна оценка потребностей в машинном времени. Необходимость сообщать ОС о потребности задач в машинном времени привела и к по- явлению соответствующих языков, например, JCL (job control language). Пользователи указывали предполагаемое время, а чтобы не было явно заниженных оценок, использовался подсчет реальных потребностей. Диспетчер сравнивал заявленное время и расчетное, и если оценка явно занижалась, задача попадала не в начало, а в конец очереди. Заблокированные в про- цессе выполнения задачи попадают в конец очереди готовых к выполнению задач. Невытесняющая. Для того же примера: время ожидания составит 0, 1, 1+4=5, полное время выполнения 0+1=1, 1+4=5, 5+13=18, среднее время ожидания 0+1+5=6/3=2, среднее время выполнения 1+5+18=24/3=8.

Дисциплина SRT (shortest remaining time) – следующее задание требует наименьшего времени для завершения. В отличие от предыдущего случая, после блокировки задача может попасть в начало очереди, если для завершения требует минимум времени. При поступлении новой задачи ее время выполнения сравнивается с оставшимся временем до завершения текущей задачи, и если пришедшая задача короче, текущий процесс останавливается, а управление переходит новой задаче. Невытес- няющая.

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

Дисциплина RR (Round Robin). Циклическая. Предполагает, что каждый процесс получает время порциями (квантами). По- сле окончания выделенного кванта времени (или при блокировке процесса), задача снимается с выполнения и запускается следующая. Снятая задача ставится в конец очереди готовых задач. Рассмотрим тот же пример, при условии, что квант вре- мени постоянен и равен 4.

Время ожидания 5, 4, 8. Полное время исполнения – 5+13=18, 4+4=8, 8+1=9. Среднее время ожидания 5+4+8=17/3=5.67. Среднее полное время выполнения 18+8+9=35/3=11.67. Величина кванта влияет на производительность. Пусть квант равен

1:

Время ожидания 5, 5, 2. Полное время исполнения – 5+13=18, 5+4=9, 2+1=3. Среднее время ожидания 5+5+2=12/3=4. Сред- нее полное время выполнения 18+9+3=30/3=10. Для оптимальной работы системы требуется правильно выбрать закон, по которому распределяются кванты времени. Величина кванта выбирается как компромисс между приемлемой реакцией сис- темы на действия пользователя и накладными расходами на смену контекста задачи. В случае, если квант достаточно мал, реакция системы будет высокой, однако частая смена контекста снизит производительность системы. Если же квант велик, то при высокой производительности значительно снижается реакция системы. В некоторых ОС величина кванта указывается явно. Например, OS/2 имела переменную в системном файле конфигурации TIMESLICE, которая позволяла указывать ми- нимальную и максимальную величину кванта. Если процесс прервался из-за окончания кванта времени, то новый выделяе- мый ему квант будет увеличен на время одно периода таймера, и так до тех пор, пока она не сравняется с максимальной. Это позволяет эффективнее распределять время для длительных задач. Циклическая дисциплина одна из самых распространен- ных.

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

Использование динамических приоритетов.

Часто используется две составляющих приоритета – первая, заданная жестко при создании процесса, и вторая, формируемая диспетчером задач, и изменяемая в зависимости от текущей ситуации. Чтобы высокоприоритеные процессы не работали по- стоянно, не предоставляя время низкоприоритетным, с течением времени, по прошествии каждого кванта, приоритет про- цесса снижается. В то же время, периодически ядро пересчитывает текущие приоритеты процессов, готовых к запуску, уве- личивая их. В итоге приоритет текущего процесса оказывается меньше, чем у одного из очереди, и происходит переключе- ние. При динамическом назначении приоритетов для процессов, активно использующих устройства вв, т.е. требующих мало процессорного времени, приоритет может выбираться как 1/f, где f – часть использованного времени кванта, т.е. если про- цесс использовал 1/10 часть кванта, то приоритет назначается 10, если 1/25, то 25. Часто удобно группировать приоритеты по классам, используя приоритетное планирование между классами, но циклическое внутри класса. Пока в классе с высшими приоритетами есть задачи, они запускаются согласно циклическому планированию. Если их нет, обрабатывается очередь процессов более низкого приоритета. Во всех ОС имеются средства для изменения приоритета процесса.

Многоуровневые очереди с обратной связью. Развитие систем с динамическим приоритетом, в которых задачи разбива- ются на классы приоритетов. В данном методе задачи могут перемещаться между классами. Например, класс с наивысшим приоритетом имеет квант, равный 8. Следующий по приоритетности класс – 16, следующий – 32, и последний класс обслу- живается не циклически, а в порядке очереди. Задача изначально поступает в класс с максимальным приоритетом. Если про- цесс отработал эти кванты и требует еще времени, он переводится в менее приоритетный класс, если и там ему не хватило времени, то в еще менее приоритетный класс. В итоге слишком длинные задачи попадут в последний класс. В результате, чем длиннее процесс, тем в более низкий по приоритету класс он попадет, в результате время ожидания увеличивается, но зато количество предоставляемых квантов увеличивается. При завершении ожидания (например, от устройств в/в) процессы могут помещаться в более приоритетный класс задач.

Гарантированное планирование. При этом варианте гарантируется предоставление процессу определенной доли процес- сорного времени, тогда как в системе с приоритетами нет гарантии обслуживания.

Лотерейное. Процессам предоставляются “лотерейные билеты” на доступ к различным ресурсам, в т.ч. и к процессору. Ко- гда планировщику необходимо принять решение, случайным образом выбирается лотерейный билет, и его обладатель полу- чает доступ. Для важных процессов раздается больше лотерейных билетов, повышая шанс на выигрыш. В итоге каждый процесс в среднем получает такую долю ресурса, какая доля билетов у него находится. Взаимодействующие процессы могут обмениваться лотерейными билетами. Например, если клиент посылает запрос серверу и блокируется в ожидании, он может предварительно передать все билеты серверу, чтобы ускорить получение ответа. Сервер, выполнив запрос, возвращает лоте- рейные билеты.

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

В системах реального времени время является самым важным критерием. Задача разделяется на несколько процессов, ка- ждый из которых предсказуем, как правило это очень короткие процессы. При этом могут возникать внешние сигналы, как периодические (с определенной частотой), так и непериодические. Может случиться так, что система не в состоянии обрабо- тать все возникшие события за необходимое время. Если в систему поступает m периодических событий, событие i поступа- ет с периодом Pi, и обрабатывается за Ci секунд, то все потоки могут быть обработаны только при следующем условии:

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

            информации о работе и временных ограничениях. Динамическое планирование не требует этого.           Ci / Pi  1

i1

Основная проблема при диспетчеризации – это гарантия обслуживания, поскольку, например, при приоритетном планирова- нии низкоприоритетные процессы могут бесконечно долго ожидать своей очереди. Более жестким требование является не просто гарантия обслуживания, а обслуживание за указанный период времени или к указанному моменту.

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

-          Выделять минимальную долю процессорного времени некоторому классу процессов, если по крайней мере один из них готов к выполнению

-          Выделять минимальную долю процессорного времени некоторому конкретному процессу, если он готов к выполнению - Выделять столько процессорного времени готовому процессу, чтобы он мог завершить работу к указанному моменту вре- мени

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

-          совместное планирование, при котором все потоки одного приложения одновременно выбираются для выполнения про- цессорами и одновременно снимаются с них:

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

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

либо процесса.

Рассмотрим потоки на уровне пользователя. Пусть есть 2 процесса, у каждого из них по три потока. Ядро не знает о сущест- вовании потоков пользователя, выполняет обычное планирование, выбирает процесс и предоставляет ему время. Планиров- щик потоков внутри процесса выбирает поток и запускает его. Если потоку требуется время, меньшее, чем выделенный квант, он отработает и вернет управление планировщику потоков. Если нет – будет работать до конца выделенного кванта. Т.о. в течение кванта времени могут быть запущены потоки по следующей схеме: А1, А2, А3, А1, А2, А3… В случае потоков на уровне ядра, ядро выбирает не процесс, а поток, не беспокоясь о том, какому процессу этот поток принадлежит. В резуль- тате цепочка запуска потоков может выглядеть так: А1, В1, А2, В2, А3, В3…, что невозможно на уровне пользователя. Од- нако на уровне пользователя для переключения потоков требуется несколько машинных команд, тогда как для переключе- ния потоков на уровне ядра требуется полное переключение контекста с заменой карты памяти и перегрузкой кэша. По- скольку ядро знает, что при переключение от потока процесса А к потоку процесса В будет затрачено больше времени за счет карты памяти и кэша, это может учитываться. Например, при наличии двух одинаково важных потоков, один из кото- рых принадлежит текущему процессу, а другой – нет, логичнее запустить поток текущего процесса.

ОС UNIX. Ядро в традиционной системе UNIX является невытесняющим. Если процесс выполняется в режиме ядра, то он не может быть прерван. Имеется два поля дескриптора процесса – p_nice и p_cpu. Первое назначается пользователем явно или формируется системой программирования. Второе – это текущий приоритет, изменяемый диспетчером задач. Процес- сам, выполняющимся в режиме задачи назначается приоритет ниже, чем для задач режима ядра. Например, для режима за- дач диапазон приоритетов может быть 0-65, для режима ядра 66-95, а диапазон 96-127 используется для процессов с фикси- рованным приоритетом для поддержки приложений реального времени. Процессу, ожидающему доступ к ресурсу, система определяет приоритет сна, выбираемый ядром из диапазона системных приоритетов и связанный с событием вызвавшим состояние ожидания. Поскольку этот приоритет из системного диапазона, то после активизации процесса вероятность запус- ка его на выполнение высока. После отработки с таким приоритетом, восстанавливается сохраненный ранее приоритет зада- чи, что снижает приоритет процесса. С каждым тиком таймера текущий приоритет активной задачи снижается на 1. Ежесе- кундно ядро пересчитывает приоритет процессов режима задачи, готовых к запуску. Планировщик содержит несколько оче- редей, каждая из которых соответствует 4 соседним приоритетам. Процесс с наивысшим приоритетом запускается всегда, если только текущий процесс не выполняется в режиме ядра.

WIN NT 5.х. Здесь каждый поток имеет базовый приоритет, который может быть в пределах +/-2 уровня относительно роди- тельского процесса. Диспетчер направляет на выполнение потоки с высоким приоритетом раньше потоков с низким приори- тетом. Текущий поток прерывается, если появляется готовый к выполнение поток с более высоким приоритетом.

Для каждо- го уровня приоритета существует своя очередь. Приоритеты от 16 до 31 – это потоки реального времени. Диспетчер задач просматривает очереди, начиная с самой приоритетной. Если она пуста, просматривается следующая. Для системных моду- лей, работающих в режиме задач, зарезервирована очередь с номером 0. Большинство пользовательских потоков имеют уро- вень приоритета 1-15. Для этих очередей, диспетчер по окончании кванта времени снижает приоритет на 1 и перемещает в другую очередь. В тоже время при выходе из состояния ожидания диспетчер увеличивает приоритет потока. По умолчанию величина кванта – 2 тика, для систем Server – 12. Ключ реестра Hkey_Local_Machine\System\CurrentControlSet\Control\Priority Control\Win32PrioritySeparation позволяет настраивать величину кванта. Два старших бита определяют, короткие или длин- ные кванты (2 или 12 тиков – значения 1 и 2 соответственно), 0 и 3 интерпретируется как по умолчанию. Два средних бита указывают, переменные или фиксированные кванты у активного процесса. 1 – переменные, 2 – фиксированные, 0 или 3 – по умолчанию (переменные, Server - фиксированные). Младшие два бита указывают величину приращения кванта активного процесса – 0,1,2. Значение 3 интерпретируется как 2. Величина (в тиках) определяется по таблице:

OS/2.Имеет 4 класса задач. У каждого класса своя группа приоритетов с номерами 0-31. Задачи наивысшего приоритета на- зываются критическими. Это задачи реального времени. Типичный пример – обслуживание каналов связи, например, после- довательный порт, сеть и т.д. Второй класс называется приоритетный или серверный. К этому классу относятся задачи, ко- торые по отношению к другим играют роль сервера. Их приоритет должен быть выше, чтобы запросы к серверу выполня- лись достаточно быстро. Третий класс – регулярный или стандартный. Это обычные пользовательские задачи. ; класс – оста- точный, это фоновые задачи. Они получают время только тогда когда нет задач из других классов. Внутри каждого класса обслуживание происходит по циклической дисциплине. Система сама меняет приоритет задачи 1. увеличение приоритета, когда задача становится активной, 2. По завершении операции вв задача получает самый высокий приоритет своего класса 3. увеличение приоритета забытых задач. Если задача не получает управление в течение времени большем чем указано в MAXWAIT, задача временно получает приоритет вплоть до уровня задач 1 класса, по истечении кванта времени, приоритет задачи восстанавливается. Такая схема гарантирует, что за время MAXWAIT задача запустится хотя бы 1 раз.