Вытесняющий алгоритм, основанный на приоритетах.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· произошла ошибка,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вообще говоря, понятие виртуального устройства шире, нежели использование этого термина для обозначения спулинга (SPOOLing — simultaneous peripheral operation on-line, то есть имитация работы с устройством в режиме «он-лайн»). Главная задача спулинга — создать видимость параллельного разделения устрой­ства ввода/вывода с последовательным доступом, которое фактически должно использоваться только монопольно и быть закрепленным.

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