Контекст и дескриптор процесса

Мультизадачность

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

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

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

Процессы

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

Контекст и дескриптор процесса

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

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

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

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

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

- создать информационные структуры, описывающие данный процесс, то есть его дескриптор и контекст;

- включить дескриптор нового процесса в очередь готовых процессов;

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

Нити

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

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

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

Для этих целей современные ОС предлагают использовать сравнительно новый механизм многонитевой обработки (multithreading). При этом вводится новое понятие "нить" (thread), а понятие "процесс" в значительной степени меняет смысл.

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

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

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

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

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

Итак, нити имеют собственные:

- программный счетчик,

- стек,

- регистры,

- нити-потомки,

- состояние.

Нити разделяют:

- адресное пространство,

- глобальные переменные,

- открытые файлы,

- таймеры,

- семафоры,

- статистическую информацию.

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

Широкое применение находит многонитевая обработка в распределенных системах.

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

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

3.3.2.2. Состав алгоритмов внутреннего планирования

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

- алгоритм управления количеством процессов в рабочей смеси;

- алгоритм планирования очередности выбора задач для исполнения их на ЦП;

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

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

3.3.2.3. Алгоритм управления количеством процессов
в рабочей смеси

Управление служит для повышения производительности системы на основе рационального использования аппаратуры ЭВМ. Для режима вытесняющей мультизадачности количество процессов, одновременно допускаемых в систему, представляет собой объем рабочей смеси N. Выбор значения N осуществляется с учетом величины кванта и длительности цикла. Введем следующие обозначения: q_i – величина кванта процессорного времени, отводимого i-му процессу; T_i – длительность одного цикла обработки для i-го процесса; T_зi, Tвi – длительность перемещения i-го процесса из ОЗУ в ВЗУ и обратно при его вытеснении и восстановлении; T_ci – затраты времени ОС на организацию работы i-го процесса.

Тогда имеем:

Т_{цi =} Т_зi + T_вi + q_i + T_ci.

Если T_зi=T_вi=T_п; T_ci=T_c; q_i=q, i=1,...,N,

то

T = (2T_п+q+T_c)N; N=T/(2T_п+q+T_c ). (3.1)

Нетрудно рассчитать также эффективность загрузки центрального процессора на одном цикле для одного процесса: полезное время процессора q_i; непроизводительные затраты времени Т_нi = Т_зi + T_пi + T_ci; показатель загрузки процессора полезной работой

(3.2)

Для всех N процессов получим:

(3.3)

где b=T_н/Q – относительная величина потерь времени на переключение между процессами.

Увеличение количества задач, одновременно решаемых системой, связанное с увеличением значения N (выражение (3.1)), можно осуществить четырьмя методами: увеличением общей длительности интервала цикла Т; уменьшением затрат времени ОС на организацию мультипрограммирования Т_с; уменьшением затрат времени на перемещение процессов из ОЗУ в ВЗУ и обратно при их вытеснении и восстановлении Т_з и Т_в; сокращением длительности квантов времени, отводимых для выполнения процессов q.

Сокращение длительности квантов времени q_i, отводимых для выполнения процессов, автоматически вызывает увеличение длительности нахождения процессов в системе (см. выражение (3.3.)), из-за чего этот способ имеет ограниченное применение.

Наиболее продуктивным являются методы, приводящие к сокращению затрат времени операционной системы Т_с и, в особенности, затрат времени на перемещение процессов из ОЗУ в ВЗУ и обратно при их вытеснении и восстановлении.

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

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

3.3.2.4. Алгоритмы выбора очередности обработки

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

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

- алгоритм циклической обработки;

- алгоритм очередей с обратной связью;

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

- алгоритм выбора с приоритетом по характеру блокировки.

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

- если предшествующий процесс закончился, то выполняются действия по его выводу из системы:

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

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

- если предшествующий процесс исчерпал выделенный ему квант времени, то он поступает в очередь готовых процессов;

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

Логика работы всех алгоритмов планирования очередности обработки практически совпадает. Различаются они лишь реализациями блоков “Выбор длины кванта” и “Выбор очередного процесса”.

Рассмотрим алгоритмы реализации блока “выбор очередного процесса”.

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

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

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

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

3.3.2.5. Алгоритмы выбора величины кванта

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

- алгоритм равномерного квантования;

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

- алгоритм минимизации количества переключений между процессами.

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

Алгоритм квантования по приоритету процесса осуществляет регулирование длительности кванта q_i для i-го процесса в зависимости от его текущего приоритета p_i. Функциональная зависимость q_i=q_i(p_i) может иметь любой допустимый вид и должна иметь следующие основные свойства: монотонность; положительная определенность; ограниченность.

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

На практике применяют также различные сочетания описанных алгоритмов.

3.4. Взаимосвязанные и конкурирующие задачи

3.4.1. Средства управления ресурсами

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

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

Основными функциями управления ресурсами являются:

- учет наличия и состояния ресурсов;

- прием и учет заявок на ресурсы от задач и процессов;

- распределение ресурсов между задачами и процессами;

- организация использования ресурсов, выделенных каждой задаче или процессу;

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

Для реализации функций управления ресурсами в ОС формируются информационные таблицы, в которых отражаются следующие основные данные:

для ресурсов:

- учетная информация о ресурсе (идентификатор, класс, количество каналов и т.п.);

- код состояния ресурса;

- идентификатор процесса-владельца и т.п.;

для заявок на ресурсы:

- идентификатор процесса-заявителя;

- приоритет процесса;

- идентификатор и требуемый объем ресурса и т.п.

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

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

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

Системная тупиковая ситуация, или ситуация “зависания” системы – это ситуация, когда один или более процессов оказываются в состоянии тупика.

Рис.3.1. Простая тупиковая ситуация.

Cформулированы следующие четыре необходимых условия наличия тупика:

- процессы требуют предоставления им монопольного права управления ресурсом, которые им выделяются (условие взаимоисключения);

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

- ресурсы нельзя отобрать у процессов, удерживающих их, эти ресурсы не будут использованы для завершения работы (условие неперераспределяемости);

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

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

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

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

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

3.4.2. Механизмы синхронизации процессов

3.4.2.1. Параллельные процессы и критические участки

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

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

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

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

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

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

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

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

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

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

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

- при обращении нескольких процессов к одному разделяемому ресурсу только одному из них разрешено воспользоваться этим ресурсом;

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

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

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

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

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

3.4.2.2. Примитивы взаимоисключения

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

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

· примитив вход_взаимоисключения, с помощью которого фиксируется захват критического ресурса данным процессом и устанавливается запрет на использование его другими процессами;

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

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

Рис.3.2. Схема применения примитивов взаимоисключения.

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

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

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

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

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

- не должно быть никаких предположений об относительных скоростях выполнения асинхронных параллельных процессов;

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

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

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

3.4.2.4. Реализация примитивов взаимоисключения
с использованием аппаратных средств

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

Подобная команда в настоящее время существует практически во всех ЭВМ и обычно имеет мнемоническое обозначение testandset (проверить_и_установить). Неделимая команда с двумя операндами testandset(a, b) читает значения логической переменной b, копирует его в a, а затем устанавливает для b значение истина, и все это в рамках одной непрерывной операции. Пример применения testandset приведен на рис.3.4.

Рис.3.3. Программная реализация примитивов взаимоисключения.

Рис.3.4. Реализация взаимоисключения с применением команды
проверить_и_установить.

3.4.2.5. Семафоры

Семафор это защищенная переменная, значение которой можно опрашивать и изменять только при помощи операции инициализация_семафора и двух специальных операций P и V.

Операция P над семафором S записывается как P(S) и выполняется по правилам:

если S > 0 то S: = S-1 иначе (ожидать на S).

Операция V над семафором S записывается как V(S) и выполняется по правилам:

если (один или более процессов ожидают на S)

то (разрешить одному из процессов продолжить работу) иначе S:= S+1.

Различают два вида семафоров: двоичные семафоры, у которых S может принимать значения 0 и 1, и считающие семафоры, где S может принимать неотрицательные целые значения.

Подобно операции проверить_и_установить, операции инициализация_семафора, P(S) и V(S) являются неделимыми. Участки взаимоисключения по семафору S обрамляются операциями P(S) и V(S). Если одновременно несколько процессов попытаются выполнить операцию P(S), то только одному из них будет позволено это сделать, а остальным придется ждать.

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

Рис.3.5. Обеспечение взаимоисключения с помощью семафора.

3.4.2.6. Мониторы

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

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

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

Если процесс обращается к некоторой процедуре монитора и обнаруживается, что соответствующий ресурс уже занят, то эта процедура монитора выдает процессу команду WAIT (ЖДАТЬ). Процесс, получивший такую команду, переводится в режим ожидания вне монитора.

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

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

WAIT (имя_условие)

SIGNAL (поле_условие)

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

Рис.3.6. Распределение ресурса при помощи монитора

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

3.4.3.1. Вводные замечания

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

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

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

3.4.3.2. Алгоритм предоставления ресурса по первому обращению

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

Независимо от места выдачи запроса на ресурс (пакет заданий или выполняющаяся в системе программа) ОС выполняет следующие действия:

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

- распределяет конкретное физическое устройство, соответствующее этому имени, источнику запроса;

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

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

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

3.4.3.3. Алгоритмы предотвращения тупиков

Поиск по сайту: