24513

Алгоритмы планирования, основанные на квантовании, приоритетах, смешанные алгоритмы

Доклад

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

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

Русский

2013-08-09

92.27 KB

43 чел.

Вопрос 18. Алгоритмы планирования, основанные на квантовании, приоритетах, смешанные алгоритмы.

§4.2.5.Алгоритмы планирования, основанные на квантовании.

В основе многих вытесняющих алгоритмов планирования лежит концепция квантования. В соответствии с этой концепцией каждому потоку поочередно для выполнения предоставляется ограниченный непрерывный период процессорного времени – квант. Смена активного потока происходит, в следующих случаях:

- поток завершился и покинул систему;

- произошла ошибка;

- поток перешел в состояние ожидания;

- исчерпан квант процессорного времени, отведенный данному потоку.

Поток, который исчерпал свой квант, переводится в состояние «готовность» и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый поток из очереди готовых. Таким образом, ни один поток не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени. Граф состояний потока для алгоритма диспетчеризации, основанного на квантовании, изображен на рис. 4.5.

Рис. 4.5. Граф состояний потока в системах с квантованием

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

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

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

Алгоритмы планирования, основанные на приоритетах.

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

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

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

Например, в операционной системе Windows NT определено 32 уровня приоритетов и два класса потоков – потоки реального времени и потоки с переменными приоритетами. Диапазон от 1 до 15 отведен для потоков с переменными приоритетами, а от 16 до 31 – для потоков реального времени (приоритет 0 зарезервирован для системных целей).

Существует две разновидности приоритетного обслуживания:

- обслуживание с относительными приоритетами;

- обслуживание с абсолютными приоритетами.

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

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

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

Графы состояний потока для алгоритмов с относительными и абсолютными приоритетами показаны на рис. 4.6.

 а)

б)

Рис. 4.6. Графы состояний потока в системах

с относительными (а) и абсолютными (б) приоритетами

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

В системах с абсолютными приоритетами время ожидания потока с самым высоким приоритетом в очередях может сведено к минимуму. Это делает планирование на основе абсолютных приоритетов подходящим для систем управления объектами, в которых важна быстрая реакция на событие.

Смешанные алгоритмы планирования.

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

Например, в Windows NT приоритеты потоков могут динамически меняться системой в определенном диапазоне относительно заданного значения.


 

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

32496. ТРЕБОВАНИЯ К ПОДГОТОВКЕ СОВРЕМЕННОГО УЧИТЕЛЯ ИНФОРМАТИКИ 102.5 KB
  03 Элементы абстрактной и компьютерной алгебры Понятие группы кольца поля булевой алгебры.04 Теория алгоритмов Понятие вычислимой функции. Понятие программы. Общее понятие исчисления.
32497. ОБОРУДОВАНИЕ ШКОЛЬНОГО КАБИНЕТА ИНФОРМАТИКИ 59.5 KB
  Оборудование школьного кабинета информатики Введение в учебный план средней школы нового предмета Основы информатики и вычислительной техники потребовало разрешения проблемы обеспечения взаимодействия учащихся с ЭВМ. КВТ предназначен также для использования в преподавании различных учебных предметов трудового обучения в организации общественно полезного и производительного труда учащихся для эффективного управления учебновоспитательным процессом. КВТ может использоваться также и для организации компьютерных клубов учащихся других форм...
32498. УЧЕБНЫЕ И МЕТОДИЧЕСКИЕ ПОСОБИЯ ПО ИНФОРМАТИКЕ 90.5 KB
  Теория и методика обучения информатики УЧЕБНЫЕ И МЕТОДИЧЕСКИЕ ПОСОБИЯ ПО ИНФОРМАТИКЕ. Некомпьютерные средства обучения информатике Понятие и дидактические функции технических средств обучения Еще основоположник классноурочной системы обучения Ян Амос Коменский отмечал: . Наиболее высокое качество усвоения достигается при непосредственном сочетании слова учителя и предъявляемого учащимся с помощью технических средств обучения ТСО изображения в процессе передачи учебной информации. Техническими средствами обучения называют проекционную...
32499. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ПО КУРСУ ИНФОРМАТИКИ 49.5 KB
  В систему средств обучения наряду с учебниками учебными и методическими материалами и программным обеспечением для компьютеров входят и сами компьютеры образующие единую комплексную среду которая и позволяет учителю достигать поставленных целей обучения. Вот перечень основных компонентов рекомендуемой системы средств обучения информатике в школе: программнометодическое обеспечение курса информатики включающее как программные средства для поддержки преподавания так и инструментальные программные средства ИПС обеспечивающие учителю...
32500. ОСНОВНЫЕ ФОРМЫ ОРГАНИЗАЦИИ ОБУЧЕНИЯ ИНФОРМАТИКЕ В СРЕДНЕЙ ШКОЛЕ 68 KB
  Все это приемлемо и на уроках по информатике. Применение ИКТ может существенно изменять характер школьного урока что делает еще более актуальным поиск новых организационных форм обучения которые должны наилучшим образом обеспечивать образовательный и воспитательный процесс. Главный признак урока это его дидактическая цель показывающая к чему должен стремиться учитель. Цель  тип урока  содержание урока  методы  форму познавательной деятельности учащихся  результат Основные типы уроков: урок формирования знаний; урок закрепления...
32501. МЕТОДЫ И ПРИЕМЫ ФОРМИРОВАНИЯ СИСТЕМНО-НАУЧНЫХ ПОНЯТИЙ НА УРОКАХ ИНФОРМАТИКИ И ВО ВНЕУРОЧНОЕ ВРЕМЯ 48 KB
  Теория и методика обучения информатики МЕТОДЫ И ПРИЕМЫ ФОРМИРОВАНИЯ СИСТЕМНОНАУЧНЫХ ПОНЯТИЙ НА УРОКАХ ИНФОРМАТИКИ И ВО ВНЕУРОЧНОЕ ВРЕМЯ. Методы и приемы формирования системноинформационных понятий на уроках информатики и во внеурочной работе со школьниками Философские аспекты современного школьного курса информатики Проблема существования и бытия человека в полностью технизированном и информатизированном мире не могла не занимать философов что вызвало к жизни концепцию информационного общества. Пропедевтика методов системного анализа...
32502. ОБЩИЕ МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПРИ ИЗУЧЕНИИ ИНФОРМАТИКИ, МЕТОДЫ ОБУЧЕНИЯ С ИСПОЛЬЗОВАНИЕМ ИНФОРМАЦИОННО-КОММУНИКАЦИОННЫХ ТЕХНОЛОГИЙ 84.5 KB
  Теория и методика обучения информатики ОБЩИЕ МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПРИ ИЗУЧЕНИИ ИНФОРМАТИКИ МЕТОДЫ ОБУЧЕНИЯ С ИСПОЛЬЗОВАНИЕМ ИНФОРМАЦИОННО-КОММУНИКАЦИОННЫХ ТЕХНОЛОГИЙ. Общие методические рекомендации и принципы обучения информатике. Принцип освоения методики самообучения. Методы обучения с использованием ИКТ Методы обучения – система взаимодействия преподавателя и обучаемого с использованием ИКТ обеспечивающая усвоение образовательной программы.
32503. ОРГАНИЗАЦИЯ ПРОВЕРКИ И ОЦЕНКИ РЕЗУЛЬТАТОВ ОБУЧЕНИЯ. ПРИНЦИПЫ ПОСТРОЕНИЯ СИСТЕМЫ И ХАРАКТЕРИСТИКА МЕТОДОВ КОНТРОЛЯ. ОСНОВНЫЕ ФОРМЫ КОНТРОЛЯ. МОДЕЛЬ НЕПРЕРЫВНОГО КОНТРОЛЯ. ШКАЛЫ ОЦЕНОК 92.5 KB
  ПРИНЦИПЫ ПОСТРОЕНИЯ СИСТЕМЫ И ХАРАКТЕРИСТИКА МЕТОДОВ КОНТРОЛЯ. ОСНОВНЫЕ ФОРМЫ КОНТРОЛЯ. МОДЕЛЬ НЕПРЕРЫВНОГО КОНТРОЛЯ. В ходе контроля оценивается степень и уровень обученности.
32504. ПРЕПОДАВАНИЕ ПРОПЕДЕВТИЧЕСКОГО КУРСА ИНФОРМАТИКИ В НАЧАЛЬНЫХ КЛАССАХ СРЕДНИХ УЧЕБНЫХ ЗАВЕДЕНИЙ 58 KB
  Целью курса информатики в начальной школе является формирование первоначальных базовых понятий информатики что обеспечит дальнейшее создание информационной картины мира представлений о свойствах информации способах работы с ней формирование представления о компьютере как универсальной информационной машине развитие информационной культуры ребенка и интеллектуальных способностей учащихся. В соответствии с целями обучения информатике в начальной школе выделяется ряд задач на которые нужно опираться при проведении уроков информатики в...