Лекция 4. ОСНОВНЫЕ КОНЦЕПЦИИ ТЕОРИИ ОС

4.1. ПОНЯТИЕ ПРОЦЕССА

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

Процесс, выполняемый на центральном процессоре (внутренний процесс), представляет собой программу. При исполнении программ на центральном процессоре выделяются следующие допустимые состояния:

1. порождение – подготавливаются условия для первого исполнения программы на процессоре;

2. активность – программа исполняется на процессоре;

3. ожидание – программа не исполняется на процессоре из-за отсутствия какого-либо требуемого ресурса;

4. готовность – программа не исполняется, имея все необходимые ресурсы, кроме ЦП;

5. окончание – нормальное или аварийное завершение программы, после чего ЦП и другие ресурсы ей не предоставляются.

Интервал времени между порождением и завершением называется интервалом существования процесса.

Допустимые состояния процесса и переходы между ними удобно изображать в виде графа существования процесса (рис. 1).

Рис.1. Граф существования процесса

Рассмотрим классификацию процессов по ряду признаков (рис. 2).

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

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

3. Остальные процессы называются пакетными.

Процессы, развивающиеся на ЦП, называется внутренними, или программными. Процессы, развивающиеся на других процессорах, отличных от ЦП, называются внешними (процессы ввода-вывода).

Программные процессы, в свою очередь, делятся на системные (исполняется программа из состава ОС) и пользовательские (исполняется прикладная программа).

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

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

Если между процессами возникают связи всевозможных типов (функциональные, пространственно-временные, управляющие, информационные и т.д.), то процессы являются взаимосвязанными.

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

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

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

Рис.2. Схема классификации процессов

Допустимые отношения между взаимосвязанными процессами определяются тремя синхронизирующими правилами:

1. Отношение предшествования. Первый из двух процессов должен переходить в активное состояние всегда раньше второго.

2. Отношение приоритетности. Процесс, имеющий приоритет P, активизируется при соблюдении двух условий:

• в состоянии готовности нет процессов с большим приоритетом;

• процессор либо свободен, либо используется менее приоритетным, чем Р процессом.

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

4.2. ПОНЯТИЕ РЕСУРСА

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

Под ресурсом часто понимается показатель надежности некоторого объекта. В данном случае мы будем использовать это слово в другом его значении.

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

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

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

Рассмотрим классификацию ресурсов по ряду признаков (рис. 3).

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

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

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

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

Рис. 3. Схема классификации ресурсов

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

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

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

Если после прохождения цепочки «освобождение-запрос-использование» ресурс изымается из сферы потребления, то он называется потребляемым.

4.3. КОНЦЕПЦИЯ ВИРТУАЛИЗАЦИИ

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

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

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

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

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

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

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

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

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

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

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

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

• бесконечная по объему память с произвольно выбираемым наиболее удобным для пользователя способом доступа к хранимым в ней объектам;

• один или несколько процессоров, способных выполнять действия, выраженные в терминах, понятных пользователю;

• произвольное количество внешних устройств с удобным способом доступа и представлением информации.

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

4.4. ДИСЦИПЛИНЫ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ НА ОСНОВЕ ОЧЕРЕДЕЙ

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

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

• статический – приоритеты назначаются до выполнения задания;

• динамический – приоритеты определяются в процессе выполнения пакета программ. Рассмотрим наиболее распространенные дисциплины обслуживания очередей.

Одноочередные дисциплины обслуживания.

а) FIFO (First In -- First Out) – дисциплина обслуживания в порядке поступления. Все заявки поступают в конец очереди. Первыми обслуживаются заявки, находящиеся в начале очереди. Схематически эта дисциплина показана на рис. 4а.

б) LIFO (Last In -- First Out) – дисциплина обслуживания в порядке, обратном порядку поступления. Эта дисциплина является основой построения стековой памяти. Схема дисциплины представлена на рис.4б.

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

в) Дисциплина обслуживания по круговому циклическому алгоритму. Схема данной дисциплины показана на рис.4в.

а )

б)

в )

Рис.4. Схемы одноочередных дисциплин обслуживания процессов:

а – первый пришел – первый обслужился;

б – последний пришел – первый обслужился;

в – круговой циклический алгоритм

Эта дисциплина используется, в частности, при реализации режима разделения времени. В ее основе лежит дисциплина FIFO. Квант времени обслуживания t_k (квант мультиплексирования) ограничивает длительность обслуживания процесса. Если заявка не успевает обслужиться за время t_k, то ее обслуживание прерывается, и она поступает в конец очереди. Здесь имеет место «дискриминация» – в наиболее благоприятных условиях оказываются короткие заявки, они имеют меньшие времена ожидания. Степень благоприятствования коротким заявкам тем больше, чем меньше длительность кванта мультиплексирования. Однако уменьшение t_k ведет к увеличению накладных расходов, необходимых для обработки прерываний и перераспределения ресурса.

Многоочередная дисциплина обслуживания. Схема данной дисциплины приведена на рис. 5.

Рис.5. Схема многоочередной дисциплины обслуживания

Здесь N очередей, все новые заявки поступают в конец первой очереди. Первая заявка из очереди i (1 < i  N) поступает на обслуживание лишь тогда, когда все очереди от 1-й до (i-1)-й пустые. Если за время t_k обслуживание процесса завершается полностью, то он покидает систему. В противном случае недообслуженная заявка поступает в конец очереди с номером i+1. После обслуживания заявки из очереди i система выбирает для обслуживания запрос из непустой очереди с самым младшим номером. Если система выходит на обслуживание заявок из очереди N, то они обслуживаются либо по дисциплине FIFO, либо по круговому алгоритму. Данная система наиболее быстро обслуживает все короткие запросы. Недостаток системы заключается в непроизводительных затратах времени на перемещение заявок из одной очереди в другую.