Теоретические сведения. «Семафоры и синхронизация процессов»

Лабораторная работа №1

«Семафоры и синхронизация процессов»

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

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

В простейшем случае семафор (S) представляет собой целочисленную переменную, принимающую неотрицательные значения. Над ней определены две атомарные операции (примитивы, которые нельзя прервать): P(S) и V(S). Операция P(S): уменьшение переменной S на 1 (декремент), если возможно. Если S = 0, то уменьшить S невозможно. Тогда процесс, вызывающий операцию P(S), ждёт, пока уменьшение станет возможно. Успешная проверка и уменьшение S – неделимая операция, т. е. она не может быть прервана, и в момент её выполнения другие процессы не имеют доступа к S. Операция V(S): увеличение переменной S на 1 (инкремент), это действие также неделимо. Стандартно эти две операции поддерживаются ядром операционной системы.

Использование семафорных операций заключается в следующем. Предположим, имеется некоторый вычислительный ресурс, к которому может быть предоставлен доступ лишь одному процессу единовременно. С каждым вычислительным ресурсом связывается индивидуальный семафор. Предполагается, что ресурс может быть после своего освобождения повторно использован. Пусть процесс А обращается к семафору ресурса и запрашивает выполнение операции P(S) (хочет получить доступ к ресурсу). Если S был в ненулевом состоянии, то он получит значение 0, и ресурс будет занят процессом А. Пусть через некоторое время процесс В обратится к тому же ресурсу с операцией P(S). Считаем, что семафор может иметь только два значения: 0 и 1. Следовательно, дальнейшее уменьшение для S невозможно. Ресурс считается занятым. Поэтому процесс В должен быть заблокирован. Для этого выполняется операция WAIT, которая переводит процесс в очередь приостановленных процессом к данному ресурсу (это очередь блокированных процессов). Когда процесс А освобождает ресурс, он выполняет операцию V(S). После этого выполняется функция SIGNAL, которая оповещает, что S > 0. Следовательно, можно выбрать с помощью диспетчера очереди один из процессов, ожидающих ресурс. Он может повторить операцию P(S) и получить ресурс.

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

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

В простейшем случае структура данных ресурса включает: семафор ресурса S; идентификатор ресурса ID[S]; список доступности Avail[S]; список ожидающих процессов Waiters[S]; точка входа в распределитель (диспетчер) Blocator[S]. Ссылка Avail[S] указывает на начало списка доступности или опись для семафора ресурса. Список в заголовке может содержать также указатели (точки входа) для двух стандартных программ. Одна – для вставки новых элементов (освобождённых ресурсов), другая – для удаления распределённых ресурсов. Таким образом, здесь предполагается, что список содержит несколько идентичных единиц ресурса. Список ожидающих процессов содержит все процессы, заблокированные на семафоре ресурса. Списки ожидания могут иметь различный вид. Запись о каждом процессе содержит его идентификатор и информацию о запросе на ресурс. В простейшем случае список содержит один элемент. Часто указатель на список в очереди Waiter[S] показывает на очередь (типа FIFO). Вид этой очереди содержит заголовок очереди с последующими элементами очереди.

Заголовок очереди: точка входа в стандартную программу вставки – Insert[q]; точка входа в стандартную программу удаления – Remove[q]; первый элемент – First[q]; последний элемент – Last[q].

Элемент очереди представляется в виде: идентификатор процесса – pi (часто указатель на дескриптор процесса); элемент di – дополнительные сведения о запросе; ячейка ai, куда должна быть помещена информация о распределении в момент, когда запрос будет удовлетворён.

В простейшем случае диспетчер процессов имеет форму Allocator(r, k, L), где k и L это выходные параметры со значениями: k – число незаблокированных процессов, которым распределены ресурсы, k > 0; L[i], i = 1, …, k – список процессов, которым распределены ресурсы (определён, когда k > 0); r – имя семафора ресурсов.

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

Исходные допущения: есть два процесса p1 и p2 и один ресурс R; процессы p1 и p2 обращаются к R раздельно. Обращение процессов к R и освобождение R моделируется пользователем с экрана в некоторой последовательности, определённой пользователем.

Вариант задания 18