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

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

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

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

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

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

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

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

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

 

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

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

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

Алгоритм Деккера

Если два процесса пытаются перейти в критическую секцию одновременно, алгоритм позволит это только одному из них, основываясь на том, чья в этот момент очередь. Если один процесс уже вошёл в критическую секцию, другой будет ждать, пока первый покинет её. Это реализуется при помощи использования двух флагов (индикаторов «намерения» войти в критическую секцию) и переменной turn (показывающей, очередь какого из процессов наступила).

Семафоры Дейкстры

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

Структура процесса в UNIX. Контекст процесса. Основные состояния процесса в UNIX. Порождение процессов.

Под пользовательским контекстом процесса понимают код и данные, расположенные в адресном пространстве процесса. Все данные подразделяются на:

· инициализируемые неизменяемые данные (например, константы);

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

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

· стек пользователя;

· данные, расположенные в динамически выделяемой памяти (например, с помощью стандартных библиотечных C функций malloc(), calloc(), realloc()).

Под понятием "контекст ядра" объединяются системный контекст и регистровый контекст.

Основные события, приводящие к созданию процесса (вызов fork или CreateProcess):

· загрузка системы;

· работающий процесс подает системный вызов на создание процесса;

· запрос пользователя на создание процесса.

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

· Выполнение – состояние, когда процесс занимает процессор, т. е. состояние активности процесса.

· Готовность – состояние, когда процесс временно приостановлен, чтобы позволить выполняться другому процессу; приостановленный процесс состоит из собственного адресного пространства, называемого образом памяти (core image), и компонентов таблицы процессов – в числе компонентов и его регистры.

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

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

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

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

Файловая система ОС. Назначение и основные функции. Имена и типы файлов. Каталоги. Логическая и физическая организация файла.

Современные архитектуры организации файловых систем ОС.

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