24512

Планирование и диспетчеризация процессов и потоков. Вытесняющие и невытесняющие алгоритмы планирования

Доклад

Информатика, кибернетика и программирование

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

Русский

2013-08-09

26.96 KB

53 чел.

Вопрос 17. Планирование и диспетчеризация процессов и потоков. Вытесняющие и невытесняющие алгоритмы планирования.

§4.2.3.Планирование и диспетчеризация потоков

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

Переход от выполнения одного потока к другому осуществляется в результате планирования и диспетчеризации.

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

- определение момента времени для смены текущего активного потока;

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

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

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

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

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

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

- сохранение контекста текущего потока, который требуется сменить;

- загрузка контекста нового потока, выбранного в результате планирования;

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

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

В состоянии выполнения в однопроцессорной системе может находиться не более одного потока, а в каждом из состояний ожидания и готовности – несколько потоков. Эти потоки образуют очереди соответственно ожидающих и готовых потоков. Очереди потоков организуются путем объединения в списки описателей отдельных потоков. Каждый описатель потока, кроме всего прочего, содержит по крайней мере одну ссылку на другой описатель, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать потоки, переводить потоки из одного состояния в другое. В качестве примера на рис. 4.4 показана очередь готовых потоков, для которой запланированный порядок выполнения выглядит так: А, В, Е, D, С.

Рис. 4.4. Очередь потоков

§4.2.4.Вытесняющие и невытесняющие алгоритмы планирования

Алгоритмы планирования можно разделить на невытесняющие или вытесняющие.

Невытесняющие (non-preemptive) алгоритмы основаны на том, что активный поток выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление диспетчеру ОС, для того, чтобы тот выбрал из очереди другой, готовый к выполнению поток;

Вытесняющие (preemptive) алгоритмы основаны на том, что решение о переключении процессора с выполнения одного протока на выполнение другого потока принимается диспетчером ОС, а не самим активным потоком (Windows NT, OS/2, UNIX).

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

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

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

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

Вытесняющие алгоритмы планирования могут быть основаны на квантовании, приоритетах и сочетании квантования и приоритетов.


 

А также другие работы, которые могут Вас заинтересовать

37627. МЕТОДЫ СОРТИРОВКИ 22.16 KB
  ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №1 Тема: МЕТОДЫ СОРТИРОВКИ ОТЧЕТ ВЫПОЛНИЛ СТУДЕНТ ГР. Постановка задачи Выполнить сравнение трех видов сортировки: метод вставки метод стандартного обмена метод пузырька и метод простого выбора. Метод вставки
37628. Теоретично-експериментальні дослідження продуктивності стрілового крана на лабораторній моделі діючого комплексу 1.46 MB
  Стрілові крани – являють собою вантажопідйомні машини загальнопромислового і спеціального призначення. Вони можуть бути стаціонарними, пересувними, повно поворотними, неповно поворотними.
37629. Циклы в Pascal 25.7 KB
  Теоретическое введение Операторы цикла Операторы цикла используются для вычислений повторяющихся многократно. Блок ради выполнения которого и организуется цикл называется телом цикла. Проверка условия продолжения цикла и модификация параметра цикла. Один проход цикла называется итерацией.
37630. Табличный процессор MS EXCEL. Создание таблицы с расчетными формулами. Использование мастера функций 128 KB
  В левой части строки формул находится поле имен где содержится адрес выделенной ячейки или размер выделяемого диапазона. В средней части строки формул расположены три кнопки предназначенные для ввода и последующей обработки содержимого ячейки. Первая кнопка с крестиком позволяет отменить последнее действие по вводу или редактированию содержимого ячейки. Правая часть предназначена для отображения содержимого выделенной ячейки.
37631. Текстовый редактор MS WORD, дополнительные возможности 38.86 KB
  Цель работы – изучение редактора формул Microsoft Eqution; создание связанных и внедренных объектов в документе Word. Одним из таких средств в программе Microsoft Word является редактор формул Microsoft Eqution 3. Он позволяет создавать формульные объекты и вставлять их в текстовый документ. Простейшие формулы в Microsoft Word можно создавать используя различные атрибуты формата символов верхний индекс нижний индекс и др.
37632. Операционная система WINDOWS 33.63 KB
  Смоленске Кафедра информатики Отчет По лабораторной работе № 2 Тема: Операционная система WINDOWS По курсу: Экономическая информатика Студент: Скобелева М. Смоленск 2011 Теоретическое введение Терминология Windows Файл ответов файл содержащий ответы для набора диалоговых окон графического интерфейса пользователя. Файл ответов для программы установки Windows обычно имеет имя Unttend. Файл ответов можно создавать и изменять с помощью диспетчера установки...
37633. Основы работы в Norton Commander 25.44 KB
  CTRLO – гасит восстанавливает окна CTRLP – гасит восстанавливает неактивное окно CTRLU – меняет окна местами CTRLL – вызов отмена справки и состоянии диска CTRLENTER – копирует в командную строку имя на котором стоит курсор Чтобы войти в выбранный каталог достаточно поставить на него курсор и нажать ENTER или CTRL PgDn. Для выхода из каталога необходимо установить курсор на каталог две точки клавишей Home и нажать Enter. Для перехода в корневой каталог необходимо нажать CTRL†â€. Установить курсор в нужное окно и нажать F7...
37634. Засоби механізації для переміщеня вагонів 227.61 KB
  Під час розвантаження навалочних вантажів з вагонів часто виникає необхідність переміщення їх вздовж розвантажувальних фронтів. Переміщення вагонів можливе за допомогою: малої механізації маневрові ломиручні лебідки; маневрових локомотивів; механічного приводу електричні лебідки маневрові тягачі спеціальні маневрові прилади. Маневрові пристрої застосовуються для переміщення вагонів вздовж розвантажувальних фронтів взамін на локомотиви застосування яких недоцільне при обмежених вантажопотоках.
37635. Ввести массив A(n) 105.45 KB
  Отдельная ячейка данных массива называется элементом массива. Элементами массива могут быть данные любого типа. В зависимости от количества измерений массивы делятся на одномерные массивы двумерные массивы трёхмерные массивы и так далее до nмерного массива. Одномерный массив – массив с одним параметром характеризующим количество элементов одномерного массива.