модуль 2 бос. 1. Планирование и диспетчеризация процессов и задач
 Скачать 24.26 Kb.
|
|
1.Планирование и диспетчеризация процессов и задач. Способы распределения времени центрального процессора между выполняющимися задачами влияют как на скорость выполнения отдельных вычислений, так и на общую эффективность вычислительной системы. Основной подход в организации методов управления процессами, обеспечивающий эффективную загрузку ресурсов — это организация очередей процессов и ресурсов. Решение вопросов, связанных с тем какой задаче следует предоставить процессорное время в данный момент, возлагается на диспетчер задач. Вопросы подбора вычислительных процессов, которые целесообразно решать параллельно, возлагается на планировщика процессов. Если взять набор процессов, который не будет конкурировать между собой за неразделяемые ресурсы при своем параллельном выполнении, то скорее всего процессы смогут выполняться быстрее, и имеющиеся в системе ресурсы будут использоваться более эффективно. Возникает задача подбора такого множества процессов, которые при своем выполнении будут как можно реже конфликтовать за имеющиеся в системе ресурсы. Такая задача называется планировщиком вычислительных процессов. На сегодняшний день на первый план вышли задачи динамического (краткосрочного) планирования, то есть текущего наиболее эффективного распределения ресурсов. Задачи динамического планирования называют диспетчеризацией. Планирование процессов осуществляется гораздо реже, чем текущее распределение ресурсов между уже выполняющимися задачами. Долгосрочный планировщик решает, какой из процессов, находящийся во входной очереди в случае освобождения ресурсов памяти, должен быть переведен в очередь процессов готовых к выполнению. Он выбирает процесс из входной очереди с целью создания неоднородной мультипрограммной смеси. Поэтому в очереди готовых к выполнению процессов должны находиться в разной пропорции процессы, ориентированные на ввод/вывод, и процессы, ориентированные на активное использование центрального процессора. Практические все ОС стараются учесть это требование. Краткосрочный планировщик решает какая из задач, находящихся в очереди готовых к выполнению, должна быть передана на исполнение. В большинстве современных ОС долгосрочный планировщик отсутствует. 2.Планирование вычислительных процессов и стратегии планирования. При рассмотрении стратегии планирования, как правило, речь идет о краткосрочном планировании, то есть о диспетчеризации. Стратегия планирования определяет какие процессы планируются на выполнение для того, чтобы достичь поставленной цели. Стратегии выбора процессов: Заканчивать вычисления в том же самом порядке, в котором они были начаты; Отдавать предпочтение более коротким вычислительным задачам; Предоставлять всем пользователям или процессам пользователей одинаковые услуги, в том числе одинаковое время ожидания. На сегодняшний день абсолютное большинство компьютеров – это персональные IBM-совместимые компьютеры, работающие на платформе Windows, Linux. Это однопользовательские диалоговые мультипрограммные и мультизадачные системы. Система, ориентированная на однопользовательский режим, должна обеспечивать хорошую реакцию системы на запросы от того приложения, с которой сейчас работает пользователь. Поэтому, по умолчанию, для задачи, с которой пользователь непосредственно работает, и которую называют задачей переднего плана, система устанавливает более высокий уровень приоритета. В результате процессорное время прежде всего предоставляется текущей задаче пользователя. Для обеспечения надлежащей работы коммуникационных процессов и для возможности выполнять системные функции, приоритет задач пользователя должен быть ниже, чем у тех задач, которые реализуют операции ввода/вывода и иные управляющие функции. 3.Дисциплины диспетчеризации. Классификация: 1) Бесприоритетные – выбор задач производится в некотором заранее установленном порядке, без учета их относительной важности и времени обслуживания. 1.1. Линейные 1.1.1. В порядке очереди 1.1.2. Случайный выбор 1.2. Циклические 1.2.1. С применением циклического алгоритма. 1.2.2. С применением многоприоритетного алгоритма. 2) Приоритетные – отдельным задачам предоставляется преимущественное право попасть в состояние исполнения. 2.1. С фиксированным приоритетом – приоритет присвоенной задачей является постоянной величиной. 2.1.1. Многоприоритетный циклический алгоритм. 2.1.2. С относительными приоритетами. 2.1.3. С абсолютными приоритетами. 2.1.4. Адаптивное обслуживание. 2.2. С динамическим приоритетом – приоритет изменяется в течение времени решения задачи. 2.2.1. Адаптивное обслуживание 2.2.2. Приоритет зависит от времени ожидания. 2.2.3. Приоритет зависит от времени обслуживания. Во многих ОС реального времени используются методы диспетчеризации на основе абсолютных приоритетов. Самая простая в реализации дисциплина FCFS - задачи обслуживаются в порядке их появления. Задачи, заблокированные в процессе работы, после перехода в состояние готовности вновь добавляются в эту очередь готовности. При этом возможны два варианта: 1. Ставить разблокированную задачу в конец очереди готовых к выполнению задач. 2. Диспетчер помещает разблокированную задачу перед теми задачами, которые еще не выполнялись. В этом случае образуется две очереди: одна очередь образуется из новых задач, а вторая очередь - из ранее выполнявшихся, но попавших в состояние ожидания. Эта дисциплина обслуживания не требует внешнего вмешательства в ход вычислений, при ней не происходит перераспределения процессорного времени. Достоинства: простота реализации и малые расходы системных ресурсов на формирование очереди задач. Недостатки: при увеличении загрузки вычислительной системы растет и среднее время ожидания обслуживания. Избежать этого недостатка позволяют дисциплины SJN и SRT. Дисциплина обслуживания SJN требует, чтобы для каждого задания была известна оценка в потребностях машинного времени. Дисциплина предполагает, что имеется только одна очередь заданий, готовых к выполнению. Недостатки: задания, которым требовалось немного времени для своего завершения, вынуждены были ожидать процессор наравне с длительными работами. Для устранения этого недостатка и была предложена дисциплина SRT - следующим выполняется задание, которому осталось меньше всего выполняться на процессоре. Все эти три дисциплины обслуживания могут использоваться для пакетных режимов обработки, когда пользователю не нужно ждать реакции системы — он просто передает свое задание и получает результаты вычислений. Для интерактивных вычислений желательно обеспечить приемлемое время реакции системы. Дисциплина RR (карусельная) предполагает, что каждая задача получает процессорное время квантами времени q. После окончания кванта времени q задача снимается с процессора, и он передается следующей задаче. Снятая задача ставится в конец очереди задач, готовых к выполнению. Дисциплина карусельной диспетчеризации более всего подходит для случая, когда все задачи имеют одинаковые права на использование ресурсов центрального процессора. Диспетчеризация без перераспределения процессорного времени (невытесняющая) — это такой способ диспетчеризации задач, при котором активная задача выполняется до тех пор, пока она сама не отдаст управление диспетчеру задач для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс или поток. Дисциплины обслуживания FCFS, SJN, SRT относятся к невытесняющим. Диспетчеризация с перераспределением процессорного времени — это такой способ, при котором решение о переключении процессора с выполнения одной задачи на выполнение другой принимается диспетчером задач, а не самой активной задачей. Дисциплина RR и многие другие, построенные на ее основе, относятся к вытесняющим. 4. Качество диспетчеризации и гарантии обслуживания Проблемой при выборе подходящей дисциплины обслуживания является гарантия обслуживания. В некоторых дисциплинах низкоприоритетные процессы получают малое количество многих ресурсов, некоторые процессы и задачи вообще могут быть не выполнены к заданному сроку. Жестким требованием к системе является его гарантированное завершение за указанный интервал времени. Основным недостатком простого упорядочения является то, что задача может быть обслужена быстрее, чем это ей реально необходимо. Чтобы избежать этого, проще всего процессорное время выделять квантами. Гарантировать обслуживание можно, например, следующими тремя способами: • Выделять минимальную долю процессорного времени некоторому классу процессов, если, по крайней мере, один из них готов к исполнению. • Выделять минимальную долю процессорного времени некоторому конкретному процессу, если он готов к выполнению. • Выделять столько процессорного времени некоторому процессу, чтобы он мог выполнить свои вычисления к сроку. Для сравнения алгоритмов диспетчеризации обычно используются следующие критерии: • Загрузка центрального процессора (CPU utilization). • Пропускная способность центрального процессора (CPU throughput). • Время оборота (turnaround time). • Время ожидания (waiting time). • Время отклика (response time). В случае мультипроцессорных систем применяются следующие методы повышения производительности системы: • совместное планирование, при котором все потоки одного приложения (неблокированные) одновременно ставятся на выполнение процессорами и одновременно снимаются с выполнения (для сокращения переключений контекста); • планирование, при котором находящиеся в критической секции задачи не прерываются, а активно ожидающие входа в критическую секцию задачи не ставятся на выполнение до тех пор, пока вход в секцию не освободится; • планирование с учетом так называемых подсказок (hints) программы, например, указания о том процессе, который должен быть выбран взамен текущего. Одним из основных методов гарантии обслуживания является использование динамических приоритетов. 5. Диспетчеризация задач с использованием динамических приоритетов При выполнении программ, реализующих какие-нибудь задачи контроля и управления, может возрасти время ожидания некоторых задач из-за возросшей нагрузки в вычислительной системе. Потери, связанные с невыполнением таких задач, могут оказаться больше, чем потери от невыполнения программ с более высоким приоритетом. При этом оказывается целесообразным временно изменить приоритет задач, для которых истекает опущение для них время обработки. После выполнения этих задач их приоритет восстанавливается. Механизм динамических приоритетов в операционной системе UNIX: Основная стратегия обслуживания — равенство в обслуживании и обеспечение приемлемого времени реакции системы. Это обеспечивается за счет дисциплины диспетчеризации RR с несколькими очередями и механизма динамических приоритетов. В вычислении приоритета участвуют значение, устанавливаемое пользователем или системой программирования, и значение, формируемое диспетчером задач (текущий приоритет). Процессу, ожидающему недоступного в данный момент ресурса, система определяет значение приоритета сна. Когда процесс пробуждается, ядро устанавливает значение текущего приоритета процесса равным приоритету сна. После завершения системного вызова перед возвращением в режим задачи, ядро восстанавливает приоритет режима задачи, сохраненный перед выполнением системного вызова. Для принятия решения о выборе следующего запускаемого процесса планировщику необходима информация об использовании процессора. Пока процесс выполняется в режиме задачи, его текущий приоритет линейно уменьшается. Каждую секунду ядро пересчитывает текущие приоритеты порогового значения процессов, готовых к запуску, приоритеты которых меньше некоторого порогового значения, последовательно увеличивая их за счет последовательного уменьшения отрицательного компонента времени использования процессора. Как результат, эти действия приводят к перемещению процессов в более приоритетные очереди и повышению вероятности их последующего выполнения. В операционных системах Windows диспетчер задач поддерживает 32 уровня приоритета. Задачи делятся на два класса: реального времени и переменного приоритета. Задачи реального времени, имеющие приоритеты от 16 до 31 — это высокоприоритетные потоки, используемые программами, критическими по времени выполнения. Для системных модулей, функционирующих в статусе задачи, зарезервирована очередь с номером 0. Большинство задач в системе относятся к классу переменного приоритета с уровнями приоритета от 1 до 15. Диспетчер приостанавливает исполнение текущей задачи после того, как та израсходует свой квант времени. При этом если прерванная задача — это поток переменного приоритета, то диспетчер задач понижает приоритет этого потока выполнения на единицу. Таким образом, приоритет задачи постепенно понижается (до значения его базового приоритета). С другой стороны, диспетчер повышает приоритет задачи после ее освобождения из состояния ожидания. |