Лекция: Двухфазовое блокирование, тупики без ресурсов и голодание

Двухфазное блокирование

Одним из алгоритмов планирования является двухфазное блокирование. Он предназначен (применяется) для работы с базами данных.

Этот алгоритм состоит из двух фаз:

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

Обновление и освобождение блокировок.

Никакой настоящей работы на первом этапе не совершается.

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

Тупики без ресурсов

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

Голодание

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