Основной алгоритм приоритетного планирования напоминает простое круговое планирование, однако круговая очередь активных процессов формируется отдельно для каждого уровня приоритета. Пока есть хоть один активный процесс в очереди с самым высоким приоритетом, процессы с более низкими приоритетами не могут получить управление. Только когда все процессы с высшим приоритетом заблокированы либо завершены, планировщик выбирает процесс из очереди с более низким приоритетом.
Приоритет, присваиваемый процессу при создании, называется статическим приоритетом. Дисциплина планирования, использующая только статические приоритеты, имеет один существенный недостаток: низкоприоритетные процессы могут надолго оказаться полностью отлученными от процессора. Иногда это приемлемо (если высокоприоритетные процессы несравнимо важнее, чем низкоприоритетные), однако чаще хотелось бы, чтобы и на низкие приоритеты хоть что-нибудь перепадало, пусть даже реже и в меньшем количестве, чем на высокие. Для решения этой задачи предложено множество разных алгоритмов планирования процессов, основанных на идее динамического приоритета.
Динамический приоритет процесса – это величина, автоматически рассчитываемая системой на основе двух основных факторов: статического приоритета и степени предыдущего использования процессора данным процессом. Общая идея следующая: если процесс слишком долго не получал процессорного времени, то его приоритет следует повысить, чтобы дать процессу шанс на будущее. Наоборот, если процесс слишком часто и долго работал, есть смысл временно понизить его приоритет, чтобы пропустить вперед изголодавшихся конкурентов.
Могут учитываться и другие соображения, влияющие на динамический приоритет. Например, если процесс ведет диалог с пользователем, то имеет смысл повысить его приоритет, чтобы сократить время реакции и избежать досадных задержек при нажатии клавиш. Если процесс в последнее время часто блокировался, не использовав до конца выделенный ему квант времени, то это тоже основание для повышения приоритета: вполне возможно, процесс и впредь будет так же неприхотлив.
4.3.1. Изоляция процессов и их взаимодействие
Одна из важнейших целей, которые ставятся при разработке многозадачных систем, заключается в том, чтобы разные процессы, одновременно работающие в системе, были как можно лучше изолированы друг от друга. Это означает, что процессы (в идеале) не должны ничего знать даже о существовании друг друга. Для каждого процесса ОС предоставляет виртуальную машину, т.е. полный набор ресурсов, имитирующий выполнение процесса на отдельном компьютере.
Изоляция процессов, во-первых, является необходимым условием надежности и безопасности многозадачной системы. Один процесс не должен иметь возможности вмешаться в работу другого или получить доступ к его данным, ни по случайной ошибке, ни намеренно.
Во-вторых, проектирование и отладка программ чрезвычайно усложнились бы, если бы программист должен был учитывать непредсказуемое влияние других процессов.
С другой стороны, есть ситуации, когда взаимодействие необходимо. Процессы могут совместно обрабатывать общие данные, обмениваться сообщениями, ждать ответа и т.п. Система должна предоставлять в распоряжение процессов средства взаимодействия. Это не противоречит тому, что выше было сказано об изоляции процессов. Чтобы взаимодействие не привело к полному хаосу, оно должно выполняться только с помощью тех хорошо продуманных средств, которые предоставляет процессам ОС. За пределами этих средств действует изоляция процессов.
Это как граница государств – пересекать ее в произвольных местах запрещено, но должна быть хорошо обустроенная система пропускных пунктов, где легко проконтролировать соблюдение правил пересечения границы.
Понятие взаимодействия процессов включает в себя несколько видов взаимодействия, основными из которых являются:
· синхронизация процессов, т.е., упрощенно говоря, ожидание одним процессом каких-либо событий, связанных с работой других процессов;
· обмен данными между процессами.
Набор средств, предназначенных для взаимодействия процессов, часто обозначают аббревиатурой IPC (InterProcessCommunication). Состав функций и методов обусловлен многолетним опытом как программистов-практиков, так и теоретиков, рассматривающих проблемы взаимодействия параллельных процессов.
Следует еще раз отметить, что проблемы взаимодействия процессов не зависят от способа реализации параллельной работы процессов в конкретной ОС. Большая часть этих проблем имеет место в равной степени и для квазипараллельной реализации, и для истинной параллельности с использованием нескольких процессоров. Средства решения проблем, правда, могут зависеть от реализации.
4.3.2. Проблема взаимного исключения процессов
Серьезная проблема возникает в ситуации, когда два (или более) процесса одновременно пытаются работать с общими для них данными, причем хотя бы один процесс изменяет значение этих данных.
Проблему часто поясняют на таком, немного условном, примере. Пусть имеется система резервирования авиабилетов, в которой одновременно работают два процесса. Процесс A обеспечивает продажу билетов, процесс B – возврат билетов. Не углубляясь в детали, будем считать, что оба процесса работают с переменной N – числом оставшихся билетов, причем соответствующие фрагменты программ на псевдокоде выглядят примерно так:
| Процесс A: | Процесс B: |
| . . .R1 := N;R1 := R1 - 1;N := R1;. . . | . . .R2 := N;R2 := R2 + 1;N := R2;. . . |
Представим себе теперь, что при квазипараллельной реализации процессов в ходе выполнения этих трех операторов происходит переключение процессов. В результате, в зависимости от непредсказуемых случайностей, порядок выполнения операторов может оказаться различным, например:
1) R1 := N; R2 := N; R2 := R2 + 1; N := R2; R1 := R1 - 1; N := R1;
2)R2 := N; R2 := R2 + 1; R1 := N; R1 := R1 - 1; N := R1; N := R2;
3) R1 := N; R1 := R1 - 1; N := R1; R2 := N; R2 := R2 + 1; N := R2;
Ну и что? А то, что в случае 1 значение N в результате окажется уменьшенным на 1, в случае 2 – увеличенным на 1, и только в случае 3 значение N, как и положено, не изменится.
Можно привести менее экзотические примеры.
· Если два процесса одновременно пытаются отредактировать одну и ту же запись базы данных, то в результате разные поля одной записи могут оказаться несогласованными.
· Если один процесс добавляет сообщение в очередь, а другой в это время пытается взять сообщение из очереди для обработки, то он может прочесть не полностью сформированное сообщение.
· Если два процесса одновременно пытаются обратиться к диску, каждый со своим запросом, то что именно каждый из них в результате прочтет или запишет на диск – сказать трудно.
Ситуация понятна: нельзя разрешать двум процессам одновременно обращаться к одним и тем же данным, если при этом происходит изменение этих данных.
То, что мы рассматривали квазипараллельную реализацию процессов, не столь существенно. Для процессов, работающих на разных процессорах, но одновременно обращающихся к одним и тем же данным, ситуация примерно та же.
Задолго до создания многозадачных систем разработчики средств автоматики столкнулись с неприятным эффектом зависимости результата операции от случайного и непредсказуемого соотношения скоростей распространения разных сигналов в электронных схемах. Этот эффект они назвали «гонками». Мы здесь ведем речь, в сущности, о том же.
Для более четкого описания ситуации было введено понятие критической секции.
Критической секцией процесса по отношению к некоторому ресурсу называется такой участок программы процесса, при прохождении которого необходимо, чтобы никакой другой процесс не находился в своей критической секции по отношению к тому же ресурсу.
В примере с билетами приведенные три оператора в каждом из процессов составляют критическую секцию этого процесса по отношению к общей переменной N. Алгоритм работы каждого процесса в отдельности правилен, но правильная работа двух процессов в совокупности может быть гарантирована, только если они не сунутся одновременно каждый в свою критическую секцию.
А как им это запретить?
На первый взгляд кажется, что эта проблема (ее называют проблемой взаимного исключения процессов) решается просто. Например, можно ввести булеву переменную Free, доступную обоим процессам и имеющую смысл «критическая область свободна». Каждый процесс перед входом в свою критическую область должен ожидать, пока эта переменная не станет истинной, как показано ниже:
| Процесс A: | Процесс B: |
| . . .while not Free do;Free := false;(критическая секция A)Free := true;. . . | . . .while not Free do;Free := false;(критическая секция B)Free := true;. . . |
В обоих процессах цикл while не делает ничего, кроме ожидания, пока другой процесс выйдет из своей критической секции.
А не нужно ли было что-нибудь сделать с переменной Free еще до запуска процессов A и B?
Прежде всего, отметим, что предложенное решение использует такую неприятную вещь, как активное ожидание: процессорное время растрачивается на многократную проверку переменной Free. Но это полбеды.
Беда в том, что такое решение ничего не решает. Если реализовать его на практике, то «неприятности» станут реже, но не исчезнут. В первом, бесхитростном варианте программы угрожаемыми участками были критические секции обоих процессов. Теперь же уязвимый участок сузился до одной точки, отмеченной в программе каждого процесса штриховой линией. Это точка между проверкой переменной Free и изменением этой переменной. Если переключение процессов произойдет, когда вытесняемый процесс будет находиться именно в этой точке, то сначала в критическую секцию войдет (с полным правом на это) другой процесс, а потом, когда управление вернется к первому процессу, он без дополнительной проверки тоже войдет в свою критическую секцию.