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

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

Для вывода на печать своих файлов процессы должны записать их имена в общедоступный разделяемый файл. Впоследствии отдельный процесс («принт-сервер» отправляет на печать файлы с вписан файл заказов.

Процесс, стремящиеся распечатать файл, выполняет действия:

· Читает значения переменной next. Указывающий номер свободной записи в файле заказов.

· Записывает в эту позицию имя файла

· Наращивает значение next.

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

Такая ситуация, когда 2 или более процессов отрабатывают разделяемые данные (файлы) и конечный результат зависит от скоростей процессов, называется эффектом «гонок».

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

Методывзаимоисключения:

· Запрещение прерываний при входе в критическую область. Разрешения прерываний после выхода.

+ Простота реализации.

- Монополизация процессора

- Возможен крах ОС

- Невозможность использования в многопроцессорных системах

· Блокирующая переменная.

С критическим ресурсом связывается логическая переменная, принимающая значение 1 (true), если ресурс свободен, и 0 (занят).

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

- Дополнительные затраты на время.

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

· Использование системных функций входа в критическую секцию.

+ Исключается потеря времени процессора на циклическую проверку освобождения занятого ресурса

- Растут накладные расходы ОС по реализации функции входа в критическую секцию и выхода из нее

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

Семафор: переменная S, примитивы P (proberen – проверка; down) и V (verhogen – увеличение, up)

V(S) – переменная S увеличивается на 1 единым действием. Выборка, наращивание и запоминание не могут быть прерваны. К переменной S нет доступа во время выполнения этой операции.

P(S) – переменная S уменьшается на 1, если это возможно, оставаясь в области неотрицательных значений. Если S уменьшить невозможно, поток, выполняющий операцию P, ждет, пока это уменьшение станет возможным. Операция P неделима.

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

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

Операция V может при некоторых обстоятельствах активизировать процесс, приостановленный операцией P.

Проблема тупиков

Тупик - множество заблокированных процессов, каждый из которых владеет некоторым ресурсом и ожидает ресурса, которым владеет какой-либо другой процесс из этого множества.

Пример

Система имеет два внешних устройства.

Поток А запрашивает сначала принтер; а затем порт, а поток В запрашивает устройства в обратном порядке. В зависимости от cоотношения скоростей потоков они могут либо взаимно блокировать друг друга - тупик (б), либо образовывать очереди к разделяемым ресурсам (в), либо совершенно независимо использовать разделяемые ресурсы (г).

Условия возникновения взаимоблокировки (тупиковой ситуации):

1. Взаимное исключение. Каждый ресурс в данный момент или отдан ровно одному процессу, или недоступен.

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

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

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

Стратегии борьбы с взаимоблокировками:

1. Пренебрежение проблемой в целом.

2. Обнаружение и устранение взаимоблокировок (восстановление).

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

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