Ставрополь операционные системы

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

(или процесс перешел в состояние ожидания, или произошла ошибка, или процесс завершился и покинул систему).

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

Ввод-вывод завершен

Рисунок 2.6 – Граф состояний процесс в системе с квантованием

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

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

Время ожидания процессом 1 следующего кванта: q(n-1)

Процессор

Рисунок 2.7 – Режим разделения времени.

Приведем некоторые весьма грубые оценки.

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

31

Тогда процесс проводит в ожидании следующего кванта время, равное q(n-1). Чем больше процессов в системе, тем больше эта величина и меньше возможность вести интерактивную работу с пользователями. Однако если величина кванта очень невелика, то время ожидания все равно будет приемлемым для пользователей. Типичное значение кванта в системах разделения времени составляет десятки миллисекунд.

Если квант короткий (т.е. в общем случае B >> q и процесс многократно участвует в цикле обработки), то суммарное время, которое процесс проводит в ожидании процессора, прямо пропорционально B.

Действительно, необходимое для процесса количество циклов выполнения равно B/q, и тогда общее время ожидания равно (q(n-1))*( B/q), или в итоге – B(n-1).

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

· Варианты алгоритмов квантования с изменяющимся квантом.

-Пусть первоначально каждому процессу назначается достаточно большой квант,

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

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

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

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

Процесс завершен или произошла ошибка

Назначен

квант Назначен Требуется ввод-вывод

квант

Вновь созданные процессы

Очередь 2

готовых процессов

Ввод-вывод завершен

Рисунок 2.8 – Квантование с предпочтением процессов, интенсивно обращающихся к вводу-выводу

32

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

·Очереди готовых процессов также могут быть организованы по-разному: по правилу «первый пришел – первый обслужился» (FIFO) или по правилу «последний пришел – первый обслужился» (LIFO).

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

Алгоритмы, основанные на приоритетах (классификация по принципу выбо-

ра процесса на выполнение из очереди)

·Приоритет – это число, характеризующее степень привилегированности про-

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

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

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

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

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

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

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

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

цесс, приоритет которого выше приоритета активного процесса. В этом случае прерванный процесс переходит в состояние готовности (рисунок 2.9, б).

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

33

процесс; наличие явного указания пользователя на присвоение процессу определенного уровня приоритета.

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

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

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

Ввод-вывод завершен

Создание процесса

Рисунок 2.9 – Графы состояний процессов в системах с относительными и абсолютными приоритетами

На смешанных алгоритмах основано планирование в системах Windows NT и Unix System V Release 4. И в одной, и в другой системе реализована дисциплина вытесняющей многозадачности, основанная на использовании абсолютных приоритетов и квантования. Эти системы используем как основу для рассмотрения смешанных алгоритмов. Обобщенный граф состояния процессов (потоков) в этом случае имеет вид, представленный на рис. 2.10.

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

34

Создание процесса

Рисунок 2.10 – Граф состояний процессов (потоков) в системах

спланированием на основе абсолютных приоритетов и квантования

·Часть диапазона отведена для процессов (потоков) с переменными приоритетами, часть – для процессов (потоков) с фиксированными приоритетами. К последним относятся процессы реального времени, наиболее критичные ко времени и имеющие самые высокие приоритеты.

·При планировании процессов (потоков) с динамическими приоритетами приоритет процесса (потока), полностью исчерпавшего свой очередной квант времени, снижается; напротив, если квант полностью не исчерпан, приоритет повышается.

2.4. Синхронизация процессов

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

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

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

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

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

-с синхронизацией процесса с внешними событиями (например, с нажатием комбинации клавиш).

35

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

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

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

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

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

1.Считать из файла базы данных в буфер запись о клиенте.

2.Изменить запись (поток А заносит данные о заказе, поток В – об оплате).

3.Вернуть измененную запись в файл.

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

Пусть в некоторый момент поток А обновляет данные о заказе в записи о клиенте, выполняет шаги А1 и А2, но выполнить шаг А3 (занести содержимое буфера в запись базы) не успевает вследствие завершения кванта времени.

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

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

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

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

Критическая секция

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

36

Рисунок 2.11 – Возникновение гонок при доступе к разделяемым данным

Рисунок 2.12 – Пошаговое выполнение и результаты потоков в ситуации гонок

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

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

Средства синхронизации процессов и потоков

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

37

Рисунок 2.13 – Влияние относительных скоростей потоков на результат решения задачи

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

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

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

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

D связывается двоичная переменная F(D), которая принимает следующие значения:

1, если ресурс свободен (то есть ни один процесс не находится в данный момент F(D) = в критической секции, связанной с данным процессом);

0, если ресурс занят.

На рис. 2.14 показан фрагмент алгоритма процесса, использующего блокирующую переменную.

Перед входом в критическую секцию процесс проверяет, свободен ли ресурс D. Если он занят, (F(D) = 0), то проверка циклически повторяется. Если же ресурс свободен (F(D) = 1), то значение переменной F(D) устанавливается в 0 и процесс входит в критическую секцию. После того как процесс выполнит все действия с разделяемым ресурсом D, значение переменной F(D) снова устанавливается равным 1.

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

38

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

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

Пусть в результате проверки переменной процесс определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 0, был прерван. За время его приостановки другой процесс занял ресурс, вошел в свою критическую секцию, но также был прерван, не завершив работы с разделяемым ресурсом. В итоге первый процесс полагает ресурс свободным, тогда как второй его занял. При возврате управления первому процессу он, считая ресурс свободным, установил признак занятости и начал выполнять свою критическую секцию. Таким образом, был нарушен принцип взаимного исключения, что потенциально может привести к нежелательным последствиям. Во избежание таких ситуаций в системе команд машины желательно иметь единую операцию “проверка-установка логической переменной” (например, это возможно реализовать посредством команд BTC, BTR и BTS процессоров x86) или же реализовывать системными средствами соответствующие программные примитивы (базовые функции ОС), которые бы запрещали прерывания на протяжении всей операции проверки и установки.

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

Попытка доступа

к разделяемому ресурсу D

Ресурс свободен:

Неделимая операция F(D)=1? нет, занят «проверка-установка»

да, свободен

Занять ресурс: F(D):=0

Критическая секция (работа с ресурсом D)

Освободить ресурс: F(D):=1

Продолжение вычислений

Рисунок 2.14 – Реализация критических секций с использованием блокирующих переменных

39

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

Специальные системные вызовы для работы с критическими секциями по-

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

На рисунке 2.15 показана реализация взаимного исключения при синхронизации потоков с помощью таких функций в ОС Windows NT.

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

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

да, свободен

Установить блокирующую перемен- ную в состояние «занято»: F(D):=0

Критическая секция (работа с ресурсом D)

Системный вызов

LeaveCriticalSection ()

Установить блокирующую перемен- ную в состояние «свободно»: F(D):=1

Перевести поток, ожидающий ресурс D, в состояние готовность

Продолжение вычислений

Рисунок 2.15 – Реализация взаимного исключения с использованием системных функций входа в критическую секцию и выхода из нее

40