Архитектура операционной системы UNIX


         

Примеры алгоритмов


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

12.3.3.1 Выделение буфера

Обратимся еще раз к алгоритму getblk, рассмотренному нами в . Алгоритм работает с тремя структурами данных: заголовком буфера, хеш-очередью буферов и списком свободных буферов. Ядро связывает семафор со всеми экземплярами каждой структуры. Другими словами, если у ядра имеются в распоряжении 200 буферов, заголовок каждого из них включает в себя семафор, используемый для захвата буфера; когда процесс выполняет над семафором операцию P, другие процессы, тоже пожелавшие захватить буфер, приостанавливаются до тех пор, пока первый процесс не исполнит операцию V. У каждой хеш-очереди буферов также имеется семафор, блокирующий доступ к очереди. В однопроцессорной системе блокировка хеш-очереди не нужна, ибо процесс никогда не переходит в состояние приостанова, оставляя очередь в несогласованном (неупорядоченном) виде. В многопроцессорной системе, тем не менее, возможны ситуации, когда с одной и той же хеш-очередью работают два процесса; в каждый момент времени семафор открывает доступ к очереди только для одного процесса. По тем же причинам и список свободных буферов нуждается в семафоре для защиты содержащейся в нем информации от искажения.

алгоритм getblk /* многопроцессорная версия */ входная информация: номер файловой системы номер блока выходная информация: захваченный буфер, предназначенный для обработки содержимого блока { выполнять (пока буфер не будет обнаружен) { P(семафор хеш-очереди); если (блок находится в хеш-очереди) { если (операция CP(семафор буфера) завершается не- удачно) /* буфер занят */ { V(семафор хеш-очереди); P(семафор буфера); /* приостанов до момен- * та освобождения */ если (операция CP(семафор хеш-очереди) заверша- ется неудачно) { V(семафор буфера); продолжить; /* выход в цикл "выполнять" */ } в противном случае если (номер устройства или номер блока изменились) { V(семафор буфера); V(семафор хеш-очереди); } } выполнять (пока операция CP(семафор списка свобод- ных буферов) не завершится успешно) ; /* "кольцевой цикл" */ пометить буфер занятым; убрать буфер из списка свободных буферов; V(семафор списка свободных буферов); V(семафор хеш-очереди); вернуть буфер; } в противном случае /* буфер отсутствует в хеш- * очереди */ /* здесь начинается выполнение оставшейся части алго- * ритма */ } }



Содержание  Назад  Вперед