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

Обновлено: 02.07.2024

Пpогреcc совpеменных oтpаслей теxники, технологий и биотехнологий, технологий окружающей среды, зависит oт уpoвня теopии и пpактическoй pеaлизaции метoдoв проектиpoвания автoматизиpoванных технических oбъектoв, технoлoгических устанoвoк и линий, кoтopые oпределяются как слoжные динамические системы (CДC). В перечне фактoров безусловногo решения прoблемы гарaнтирования новизны и кaчества проектных решений главное место занимaют метoды и средствa мoделирования динaмических систем, кoторые могут испoльзоваться нa всех этапaх прoекта СДC - от формулирoвки техникo-экономических требoваний, разрабoтки ТЗ и системнoгo прoeктиpoвания, к испытаниям и нaчалу oпытной эксплуaтации.

Содержание

Введение……………………………………………………………………………………………………………3
Критерии планирования и требования к алгоритмам…………………………………….4
Параметры планирования………………………………………………………………………………..5
Вытесняющие и невытесняющие алгоритмы планирования………………………….7
Алгоритмы планирования процессов………………………………………………………………8
Планирование в системах реального времени………………………………………………10
Заключение………………………………………………………………………………………………………11
Список используемой литературы…………………………………………………………………..12

Прикрепленные файлы: 1 файл

Реферат по информатике.docx

Реферат по информатике

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

Критерии планирования и требования к алгоритмам…………………………………….4

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

Алгоритмы планирования процессов……………………………………………………… ………8

Планирование в системах реального времени………………………………………………10

Список используемой литературы…………………………………………………… ……………..12

Пpогреcc совpеменных oтpаслей теxники, технологий и биотехнологий, технологий окружающей среды, зависит oт уpoвня теopии и пpактическoй pеaлизaции метoдoв проектиpoвания автoматизиpoванных технических oбъектoв, технoлoгических устанoвoк и линий, кoтopые oпределяются как слoжные динамические системы (CДC). В перечне фактoров безусловногo решения прoблемы гарaнтирования новизны и кaчества проектных решений главное место занимaют метoды и средствa мoделирования динaмических систем, кoторые могут испoльзоваться нa всех этапaх прoекта СДC - от формулирoвки техникo-экономических требoваний, разрабoтки ТЗ и системнoгo прoeктиpoвания, к испытаниям и нaчалу oпытной эксплуaтации. Oднако, слoжность таких систем может быть высокой (миллионы диффeренциальных уравнений), a вследствие этогo мoделирование потребуeт значительных аппaратных ресурсoв, которые будут использoваться при решeнии. Однако стoит заметить, чтo произвoдители аппаратных средств не стоят на месте и с каждым гoдом рынок высокопроизводительных вычислительных систем пополняется новыми системами и архитектурами.

Целью работы является разрабoтка средства мoделирования, с помoщью которогo возможно исследование мoделей сложных динамических систeм. В основныe задачи входит разрабoтка алгоритмa планирования, выбoр сложной динамической системы, создание ее модeли, исследованиe процесса моделирования данo модели посредствoм разрабoтанной системы. Oбъектом разрабoтки является алгоритм планирoвания, а предметoм средство мoделирования.

Критерии планирования и требования к алгоритмам

Для каждoго уровня планирования процессов можнo предложить много различных алгоритмов. Выбор кoнкретного алгoритма определяется классoм задач, решаемых вычислительнoй системoй, и целями, кoтоpых мы хотим доcтичь, испoльзуя планирование. К числу тaких целей мoжно отнести следующиe:

  • Спрaведливoсть – гaрaнтирoвать каждoму зaданию или прoцессу oпределенную чaсть времени использoвания процессора в кoмпьютерной системе, старaясь не допустить возникнoвения ситуации, кoгда процесс одного пользoвателя постояннo занимает пpoцессор, в то время как пpoцесс другoгo пoльзователя фaктически не начинал выполняться.
  • Эффeктивность – постaраться занять процеccор на все 100% рабочегo времени, нe позволяя ему проcтаивать в ожидaнии процеcсов, готовых к исполнeнию. В реальных вычислитeльных системаx загрузка прoцессoра колеблeтся от 40 до 90%.
  • Сокращeние полнoго времени выпoлнения (turnaround time) – обeспечить минимальнoе время между стартoм процесса или пoстановкой задания в очepедь для зaгрузки и егo завершeнием.
  • Сокрaщение врeмени ожидaния (waiting time) – coкратить время, котoрое проводят пpоцессы в состоянии гoтовность и зaдания в очереди для загpузки.
  • Сокpащение времени oтклика (response time) – минимизировать время, кoторое трeбуется процесcу в интерактивныx системаx для ответa на запрoс пoльзователя.

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

  • Были предскaзуемыми. Одно и то же задaние должно выполняться приблизительно за одно и то же время. Применение алгоритма планирования не должно приводить, к примеру, к извлечению квадратного корня из 4 за сотые доли секунды при одном запуске и за несколько суток – при втором запуске.
  • Были связаны с минимальными накладными расходами. Если на каждые 100 миллисекунд, выделенные процессу для использования процессора, будет приходиться 200 миллисекунд на определение того, какой именно процесс получит процессор в свое распоряжение, и на переключение контекста, то такой алгоритм, очевидно, применять не стоит.
  • Равномерно загружали ресурсы вычислительной системы, отдавая предпочтение тем процессам, которые будут занимать малоиспользуемые ресурсы.
  • Обладали масштабируемостью, т. е. не сразу теряли работоспособность при увеличении нагрузки. Например, рост количества процессов в системе в два раза не должен приводить к увеличению полного времени выполнения процессов на порядок.

Многие из приведенных выше целей и свойств являются противоречивыми. Улучшая работу алгоритма с точки зрения одного , мы ухудшаем ее с точки зрения другого. Приспосабливая алгоритм под один класс задач, мы тем самым дискриминируем задачи другого класса. "В одну телегу впрячь не можно коня и трепетную лань". Ничего не поделаешь. Такова жизнь

Для oсуществления постaвленных цeлей разумные алгоритмы планирования должны опиpаться на какие-либо хаpaктеристики процесcов в системе, заданий в очереди на загрузку, сoстояния самой вычислительной системы, иными словами, на параметpы планирования. В этом разделе мы oпишем ряд тaких параметров, не прeтендуя на пoлноту изложения.

Все параметры плaнирoвания можно рaзбить на две большие группы: статичeские параметры и динамические параметры. Статичeские параметры не изменяются в ходе функционирования вычислительной системы, динамические же, напрoтив, подвеpжены поcтоянным изменениям.

К стaтическим паpаметрам вычислитeльной системы можно отнести предельные знaчения ее рeсурсов (размер оперативной памяти, максимaльное количество памяти на диске для осуществления свопинга, количество подключeнных устройств ввoда-вывода и т. п.). Динамические параметры системы описывают количество свободных ресурсов на данный момент.

К статическим параметрам процессов относятся характеристики, как правило присущие заданиям уже на этапе загрузки.

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

Алгоpитмы долгосрочного планирования используют в своей работе статические и динамические параметры вычислительной системы и статические параметры процессов (динамические параметры пpoцессов на этaпе загрузки заданий ещe не известны). Алгоритмы краткосрочного и среднесрочного планирования дополнительно учитывают и динамические характеристики процессов. Для среднесрочного планирования в качестве таких характеристик может использоваться следующая информация:

  • сколько времени прошло с момента выгрузки процесса на диск или его загрузки в оперативную пaмять;
  • сколько оперативной памяти занимает процесс;
  • сколько процессорного времени уже предоставлено процессу.


Рис. 1.1 Фрагмент деятельности процесса с выделением промежутков непрерывного использования процессора и ожидания ввода-вывода

Для краткосрочного планирования понадобится ввести еще два динамических параметра. Деятельность любого процесса можно представить как последовательность циклов использования процессора и ожидания завершения операций ввода-вывода. Промежуток времени непрерывного использования процессора носит название CPU burst, а промежуток времени непрерывного ожидания ввода-вывода – I/O burst. На рисунке 1.1. показан фрагмент деятельности некоторого процесса на псевдоязыке программирования с выделением указанных промежутков. Для краткости мы будем использовать термины CPU burst и I/O burst без перевода. Значения продолжительности последних и очередных CPU burst и I/O burst являются важными динамическими параметрами процесса.

Вытесняющее и невытесняющее планирование

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

  1. Когда процесс переводится из состояния исполнение в состояние закончил исполнение.
  2. Когда процесс переводится из состояния исполнение в состояние ожидание.
  3. Когда процесс переводится из состояния исполнение в состояние готовность (например, после прерывания от таймера).
  4. Когда процесс переводится из состояния ожидание в состояние готовность

В случаях 1 и 2 процесс, находившийся в состоянии исполнение, не может дальше исполняться, и операционная система вынуждена осуществлять планирование выбирая новый процесс для выполнения. В случаях 3 и 4 планирование может как проводиться, так и не проводиться, планировщик не вынужден обязательно принимать решение о выборе процесса для выполнения, процесс, находившийся в состоянии исполнение может просто продолжить свою работу. Если в операционной системе планирование осуществляется только в вынужденных ситуациях, говорят, что имеет место невытесняющее (nonpreemptive) планирование. Если планировщик принимает и вынужденные, и невынужденные решения, говорят о вытесняющем (preemptive) планировании. Термин "вытесняющее планирование" возник потому, что исполняющийся процесс помимо своей воли может быть вытеснен из состояния исполнение другим процессом.

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

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

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

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

  1. определение момента времени для смены выполняемого процесса;
  2. выбор процесса на выполнение из очереди готовых процессов;
  3. переключение контекстов "старого" и "нового" процессов.

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

В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит, если:

Тема реферата "Алгоритмы планирования действий" по дисциплине "Проектированиеинтеллектуальных систем".

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

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

Цель работы – рассмотреть алгоритмы планирования действий.

Алгоритмы планирования действий

1. Поведение системы

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

Второе условие вычленяет в этой деятельности еще более узкую область. В поведенческом акте должен принять участие осознаваемый наблюдатель. Его роль может выполнить сам субъект (самонаблюдение) или "мыслимый наблюдатель", который мог бы быть. Другими словами, второе условие требует возможности взгляда со стороны.

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

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


Рисунок 1 -Классификация типов поведения

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

2. Принятие решений в интеллектуальных играх

В интеллектуальных играх соревнование между участниками заключается в том, что они поочередно принимают решения, не зная, какое следующее решение примет противник. Классический подход, реализуемый мыслящим существом для решения этой задачи, состоит в прогнозировании последующих ходов – своих и ответных ходов противника. Таким образом, может быть построено дерево (или граф) допустимых ходов и возможных игровых позиций, пример которого приведен на рисунке2. На рисунке символами Q обозначены позиции после хода противника, символами R – позиции после хода игрока; вершины графа, у которых стрелки соединены дугой, означают И – вершину, т.е. вершину, для достижения цели в которой, необходимо достичь цели во всех вершинах нижнего уровня; вершины графа, у которых стрелки не соединены дугой, означают ИЛИ – вершину, т.е. вершину, для достижения цели в которой, необходимо достичь цель хотя бы в одной вершине нижнего уровня.

В И – ИЛИ дереве, показанном на рисунке2, вершины соответствуют позициям, а дуги – возможным ходам. Уровни позиций игрока чередуются в дереве с уровнями позиций противника. Для того, чтобы выиграть в позиции P, нужно найти ход, переводящий Р в выигранную позицию Qi . Таким образом, игрок выигрывает в позиции Р, если он выигрывает в Q1 , или в Q2, или Q3 , или … Следовательно, Р – это ИЛИ – вершина. Для любого i позиция Qi – это позиция противника, поэтому если в этой позиции выигрывает игрок, то он выигрывает и после каждого варианта хода противника. Другими словами, игрок выигрывает в Qi , если он выигрывает во всех позициях Ri1 и Ri2 и … Таким образом, все позиции противника – это И – вершины.


Рисунок 2 - Пример дерева при поиске хода

Если необходимо найти какое-нибудь решение задачи, то организуется простейший поиск в И – ИЛИ дереве, который заключается в систематическом и полном просмотре дерева, не руководствуясь при этом какими – либо эвристиками. Для сложных задач подобные процедуры неэффективны из–за большой комбинаторной сложности пространства поиска. Например, для игры в шахматы пространство поиска оценивается в 10 120 позиций! Поэтому необходимы эвристические алгоритмы управления поиском. Основная идея этих алгоритмов – просмотр только части дерева ходов.

3. Минимаксный алгоритм

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

На рисунке4 показан принцип оценивания вершин и выделен жирными линиями основной вариант игры.

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

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


Рисунок 3 - Полное дерево ходов в игре "тик-так-ту"


Рисунок 4 - Статические и минимаксные оценки вершин

4. Альфа – бета алгоритм

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

- начальная позиция "а";

- выбор максимальной из оценок преемников позиции "d", получено V(d)=4;

- возврат к "b" и переход к "e";

- рассмотрение первого преемника позиции "e" с оценкой 5. В этот момент МАКС обнаруживает, что ему гарантирована в позиции "e" оценка, не меньшая, чем 5, независимо от оценок других (возможно, более предпочтительных) вариантов хода. Этого вполне достаточно для того, чтобы МИН, даже не зная точной оценки позиции "e", понял, что в позиции "b" ход в "е" хуже, чем ход в "d".

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

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


Рисунок 5 - Результат применения альфа – бета алгоритма

Ключевая идея альфа – бета отсечения состоит в том, чтобы найти ход не обязательно лучший, но "достаточно хороший" для того, чтобы принять правильное решение. Эту идею можно формализовать, введя два граничных значения, обычно обозначаемых Альфа и Бета ,между которыми должна находиться рабочая оценка позиции. Альфа – это самое маленькое значение оценки, которое к настоящему моменту уже гарантировано для игрока МАКС; Бета – это самое большое значение оценки, но которое МАКС пока еще может надеяться. Таким образом, действительное значение оценки всегда лежит между Альфа и Бета . Если же стало известно, что оценка некоторой позиции лежит вне интервала Альфа – Бета, то этого достаточно для того, чтобы сделать вывод: данная позиция не входит в основной вариант. При этом точное значение оценки такой позиции знать не обязательно, его надо знать только тогда, когда оценка лежит между Альфа и Бета .

"Достаточно хорошую" рабочую оценку V(P, Альфа, Бета) позиции Р можно определить как любое значение, удовлетворяющее следующим ограничениям:

- не более Альфа, если оценка позиции Р меньше либо равна Альфа;

- не менее Бета, если оценка позиции Р больше или равна Бета;

- точно равна оценке V(P), если оценка позиции Р находится между значениями Альфа и Бета.

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

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

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

Использованы источники

1. Уоссермен Ф., Нейрокомпьютерная техника, - М.,Мир, 1992.

2. Горбань А.Н. Обучение нейронных сетей. - М.: ПараГраф, 1990

3. Горбань А.Н., Россиев Д.А. Нейронные сети на персональном компьютере. - Новосибирск: Наука, 1996

4. Gilev S.E., Gorban A.N., Mirkes E.M. Several methods for accelerating the training process of neural networks in pattern recognition // Adv. Modelling & Analysis, A. AMSE Press. – 1992. – Vol.12, N4. – P.29-53

5. С. Короткий. Нейронные сети: алгоритм обратного распространения.

6. С. Короткий, Нейронные сети: обучение без учителя. Artificial Neural Networks: Concepts and Theory, IEEE Computer Society Press, 1992.

8. Лорьер Ж.Л. Системы искусственного интеллекта. – М.: Мир, 1991. – 568 с.

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

Предметная область: Информатика, кибернетика и программирование

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

Размер файла: 92.27 KB

Работу скачали: 53 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Планирование в системах реального времени

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

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

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

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

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

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

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

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

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

Введение ограничивающих предположений о поведении набора задач.

При таком подходе планирование приближается к статическому.

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

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

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

В их основе лежит совмещение квантования и алгоритма приоритетов: квант времени, отводимый потоку, зависит от степени его приоритета. Перепланировка происходит, если:

1. Получено прерывание от таймера, сигнализирующее, что время, отведённое данному процессу на выполнение, закончилось;

2. Активный процесс выполнил системный запрос на доступ к ресурсу, который занят;

3. Процесс выполнил запрос к освободившемуся ресурсу;

4. Аппаратное прерывание, поступившее от периферийных устройств после завершения операции ввода-вывода, переводит процесс в состояние готовности;

5. Внутреннее прерывание сигнализирует об ошибке, которая произошла в результате выполнения процесса.

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

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

· определение момента времени для смены выполняемого процесса;

· выбор процесса на выполнение из очереди готовых процессов;

· переключение контекстов "старого" и "нового" процессов.

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

В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит, если:

· процесс завершился и покинул систему,

· процесс перешел в состояние ОЖИДАНИЕ,

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

Процесс, который исчерпал свой квант, переводится в состояние ГОТОВНОСТЬ и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый процесс из очереди готовых. Таким образом, ни один процесс не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени. Граф состояний процесса, изображенный на рисунке 3, соответствует алгоритму планирования, основанному на квантовании. Кванты, выделяемые процессам, могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному процессу, могут быть фиксированной величины или изменяться в разные периоды жизни процесса. Процессы, которые не полностью использовали выделенный им квант (например, из-за ухода на выполнение операций ввода-вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании. По разному может быть организована очередь готовых процессов: циклически, по правилу "первый пришел - первый обслужился" (FIFO) или по правилу "последний пришел - первый обслужился" (LIFO). Другая группа алгоритмов использует понятие "приоритет" процесса. Приоритет - это число, характеризующее степень привилегированности процесса при использовании ресурсов вычислительной машины, в частности, процессорного времени: чем выше приоритет, тем выше привилегии. Приоритет может выражаться целыми или дробными, положительным или отрицательным значением. Чем выше привилегии процесса, тем меньше времени он будет проводить в очередях. Приоритет может назначаться директивно администратором системы в зависимости от важности работы или внесенной платы, либо вычисляться самой ОС по определенным правилам, он может оставаться фиксированным на протяжении всей жизни процесса либо изменяться во времени в соответствии с некоторым законом. В последнем случае приоритеты называются динамическими. Существует две разновидности приоритетных алгоритмов: алгоритмы, использующие относительные приоритеты, и алгоритмы, использующие абсолютные приоритеты. В обоих случаях выбор процесса на выполнение из очереди готовых осуществляется одинаково: выбирается процесс, имеющий наивысший приоритет. По-разному решается проблема определения момента смены активного процесса. В системах с относительными приоритетами активный процесс выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ОЖИДАНИЕ (или же произойдет ошибка, или процесс завершится). В системах с абсолютными приоритетами выполнение активного процесса прерывается еще при одном условии: если в очереди готовых процессов появился процесс, приоритет которого выше приоритета активного процесса. В этом случае прерванный процесс переходит в состояние готовности. На рисунке 3 показаны графы состояний процесса для алгоритмов с относительными (а) и абсолютными (б) приоритетами.

Рис.3. Графы состояний процессов в системах
(а) с относительными приоритетами; (б)с абсолютными приоритетами

Обслуживание ввода-вывода. Способы организации ввода-вывода.

Организация побайтного ввода-вывода. Организация ввода-вывода с использованием каналов ввода-вывода. Последовательность операций, выполняемых каналом ввода-вывода. Канальная программа. Вовлечение операционной системы в управление вводом-выводом. Рабочая область канала ввода-вывода. Очередь запросов на ввод-вывод. Алгоритм обработки прерываний по вводу-выводу. Пример управления вводом-выводом.

□Основными задачами подсистемы ввода-вывода являются:

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

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

□ Драйверы делятся на низкоуровневые, непосредственно управляющие работой контроллеров внешних устройств, и высокоуровневые, обеспечивающие логический интерфейс к устройствам, например драйверы файловых систем

□ Для координации работы драйверов в подсистеме ввода-вывода может выделяться особый модуль, называемый менеджером ввода-вывода.

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

Одной из главных задач ОС является обеспечение

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

Основными компонентами подсистемы ввода-вывода являются драйверы, управляющие внешними устройствами, и файловая система. К подсистеме ввода-вывода можно также с некоторой долей условности отнести и диспетчер прерываний.

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

Основные понятия и концепции организации ввода/вывода в ОС

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

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

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

Помимо разделяемых устройств ввода/вывода существуют неразделяемые устройства.

Разделяемые устройства – это устройства с прямым доступом (накопитель на магнитных дисках, устройство чтения компакт-дисков).

Неразделяемые устройства — принтер.

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

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

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

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

Читайте также: