1.8. Вопросы к защите

«Принципы организации системы планирования мультизадачной ОС»:

1. Суть и необходимость многозадачности в однопроцессорной системе.

2. Концепция процесса. БУП, диаграмма состояний процесса, варианты и условия изменения состояний. Особенности организации информационных структур, используемых ОС для управления процессом.

3. Планировщик. Назначение планировщика. Приоритетность по отношению к пользовательским процессам (зачем и за счет каких механизмов организуется). Схема работы планировщика с процессами.

4. Механизм прерываний. Назначение механизма прерываний. Алгоритм обработки прерываний. Смена контекста. Классификация прерываний. Приоритет.

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

Группа заданий №2

Задача управления взаимодействием параллельных процессов в мультизадачной или мультипрограммной ОС

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

2.1. Цель работы

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

2. Теоретические сведения

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

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

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

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

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

Требования правила взаимного исключения:

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

• ни один процесс не должен бесконечно долго находиться в своей критической секции

• процесс, работающий вне своей критической секции, не должен блокировать критическую секцию другого процесса

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

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

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

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

• учитывалось состояние общей области памяти с точки зрения возможности или невозможности посылки (принятия) очередного сообщения.

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

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

Задача «читатели-писатели».Эта задача решается, например, при построении файловых систем. Параллельные процессы, работающие с некоторой областью памяти, делятся на два типа:

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

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

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

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

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

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

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

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

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