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

Рисунок 3.7. Второй случай выделения буфера

Если при выполнении алгоритма getblk имеет место случай 3, ядро так же должно выделить буфер из списка свободных буферов. Однако, оно обнаруживает, что удаляемый из списка буфер был помечен для отложенной переписи, поэтому прежде чем использовать буфер ядро должно переписать его содержимое на диск. Ядро приступает к асинхронной записи на диск и пытается выделить другой буфер из списка. Когда асинхронная запись заканчивается, ядро освобождает буфер и помещает его в начало списка свободных буферов. Буфер сам продвинулся от конца списка свободных буферов к началу списка. Если после асинхронной переписи ядру бы понадобилось поместить буфер в конец списка, буфер получил бы «зеленую улицу» по всему списку свободных буферов, результат такого перемещения противоположен действию алгоритма поиска буферов, к которым наиболее долго не было обращений. Например, если обратиться к Рисунку 3.8, ядро не смогло обнаружить блок 18, но когда попыталось выделить первые два буфера (по очереди) в списке свободных буферов, то оказалось, что они оба помечены для отложенной переписи. Ядро удалило их из списка, запустило операции переписи на диск в соответствующие блоки, и выделило третий буфер из списка, блок 4. Далее ядро присвоило новые значения полям буфера «номер устройства» и «номер блока» и включило буфер, получивший имя «блок 18», в новую хеш-очередь.

В четвертом случае (Рисунок 3.9) ядро, работая с процессом A, не смогло найти дисковый блок в соответствующей хеш-очереди и предприняло попытку выделить из списка свободных буферов новый буфер, как в случае 2. Однако, в списке не оказалось ни одного буфера, поэтому процесс A приостановился до тех пор, пока другим процессом не будет выполнен алгоритм brelse, высвобождающий буфер. Планируя выполнение процесса A, ядро вынуждено снова просматривать хеш-очередь в поисках блока. Оно не в состоянии немедленно выделить буфер из списка свободных буферов, так как возможна ситуация, когда свободный буфер ожидают сразу несколько процессов и одному из них будет выделен вновь освободившийся буфер, на который уже нацелился процесс A. Таким образом, алгоритм поиска блока снова гарантирует, что только один буфер включает содержимое дискового блока. На Рисунке 3.10 показана конкуренция между двумя процессами за освободившийся буфер.

Последний случай (Рисунок 3.11) наиболее сложный, поскольку он связан с комплексом взаимоотношений между несколькими процессами. Предположим, что ядро, работая с процессом A, ведет поиск дискового блока и выделяет буфер, но приостанавливает выполнение процесса перед освобождением буфера. Например, если процесс A попытается считать дисковый блок и выделить буфер, как в случае 2, то он приостановится до момента завершения передачи данных с диска. Предположим, что пока процесс A приостановлен, ядро активизирует второй процесс, B, который пытается обратиться к дисковому блоку, чей буфер был только что заблокирован процессом A. Процесс B (случай 5) обнаружит этот захваченный блок в хеш-очереди. Так как использовать захваченный буфер не разрешается и, кроме того, нельзя выделить для одного и того же дискового блока второй буфер, процесс B помечает буфер как «запрошенный» и затем приостанавливается до того момента, когда процесс A освободит данный буфер.

В конце концов процесс A освобождает буфер и замечает, что он запрошен. Тогда процесс A «будит» все процессы, приостановленные по событию «буфер становится свободным», включая и процесс B. Когда же ядро вновь запустит на выполнение процесс B, процесс B должен будет убедиться в том, что буфер свободен. Возможно, что третий процесс, C, ждал освобождения этого же буфера, и ядро запланировало активизацию процесса C раньше B; при этом процесс C мог приостановиться и оставить буфер заблокированным. Следовательно, процесс B должен проверить то, что блок действительно свободен.

Рисунок 3.8. Третий случай выделения буфера

Рисунок 3.9. Четвертый случай выделения буфера

Процесс B также должен убедиться в том, что в буфере содержится первоначально затребованный дисковый блок, поскольку процесс C мог выделить данный буфер другому блоку, как в случае 2. При выполнении процесса B может обнаружиться, что он ждал освобождения буфера не с тем содержимым, поэтому процессу B придется вновь заниматься поисками блока. Если же его настроить на автоматическое выделение буфера из списка свободных буферов, он может упустить из виду возможность того, что какой-либо другой процесс уже выделил буфер для данного блока.

Рисунок 3.10. Состязание за свободный буфер

В конце концов, процесс B найдет этот блок, при необходимости выбрав новый буфер из списка свободных буферов, как в случае 2. Пусть некоторый процесс, осуществляя поиск блока 99 (Рисунок 3.11), обнаружил этот блок в хеш-очереди, однако он оказался занятым. Процесс приостанавливается до момента освобождения блока, после чего он запускает весь алгоритм с самого начала. На Рисунке 3.12 показано содержимое занятого буфера.

Алгоритм выделения буфера должен быть надежным; процессы не должны «засыпать» навсегда и рано или поздно им нужно выделить буфер. Ядро гарантирует такое положение, при котором все процессы, ожидающие выделения буфера, продолжат свое выполнение, благодаря тому, что ядро распределяет буферы во время обработки обращений к операционной системе и освобождает их перед возвратом управления процессам.[9] В режиме задачи процессы непосредственно не контролируют выделение буферов ядром системы, поэтому они не могут намеренно «захватывать» буферы. Ядро теряет контроль над буфером только тогда, когда ждет завершения операции ввода-вывода между буфером и диском. Было задумано так, что если дисковод испорчен, он не может прерывать работу центрального процессора, и тогда ядро никогда не освободит буфер. Дисковод должен следить за работой аппаратных средств в таких случаях и возвращать ядру код ошибки, сообщая о плохой работе диска. Короче говоря, ядро может гарантировать, что процессы, приостановленные в ожидании буфера, в конце концов возобновят свое выполнение.

Рисунок 3.11. Пятый случай выделения буфера

Можно также представить себе ситуацию, когда процесс «зависает» в ожидании получения доступа к буферу. В четвертом случае, например, если несколько процессов приостанавливаются, ожидая освобождения буфера, ядро не гарантирует, что они получат доступ к буферу в той очередности, в которой они запросили доступ. Процесс может приостановить и возобновить свое выполнение, когда буфер станет свободным, только для того, чтобы приостановиться вновь из — за того, что другой процесс получил управление над буфером первым. Теоретически, так может продолжаться вечно, но практически такой проблемы не возникает в связи с тем, что в системе обычно заложено большое количество буферов.

3.4 ЧТЕНИЕ И ЗАПИСЬ ДИСКОВЫХ БЛОКОВ

Теперь, когда алгоритм выделения буферов нами уже рассмотрен, будет легче понять процедуру чтения и записи дисковых блоков. Чтобы считать дисковый блок (Рисунок 3.13), процесс использует алгоритм getblk для поиска блока в буферном кеше. Если он там, ядро может возвратить его немедленно без физического считывания блока с диска. Если блок в кеше отсутствует, ядро приказывает дисководу «запланировать» запрос на чтение и приостанавливает работу, ожидая завершения ввода-вывода. Дисковод извещает контроллер диска о том, что он собирается считать информацию, и контроллер тогда передает информацию в буфер. Наконец, дисковый контроллер прерывает работу процессора, сообщая о завершении операции ввода-вывода, и программа обработки прерываний от диска возобновляет выполнение приостановленного процесса; теперь содержимое дискового блока находится в буфере. Модули, запросившие информацию данного блока, получают ее; когда буфер им уже не потребуется, они освободят его для того, чтобы другие процессы получили к нему доступ.

Рисунок 3.12. Состязание за свободный буфер

В главе 5 будет показано, как модули более высокого уровня (такие как подсистема управления файлами) могут предчувствовать потребность во втором дисковом блоке, когда процесс читает информацию из файла последовательно. Эти модули формируют запрос на асинхронное выполнение второй операции ввода-вывода, надеясь на то, что информация уже будет в памяти, когда вдруг возникнет необходимость в ней, и тем самым повышая быстродействие системы. Для этого ядро выполняет алгоритм чтения блока с продвижением breada (Рисунок 3.14). Ядро проверяет, находится ли в кеше первый блок, и если его там нет, приказывает дисководу считать этот блок. Если в буферном кеше отсутствует и второй блок, ядро дает команду дисководу считать асинхронно и его. Затем процесс приостанавливается, ожидая завершения операции ввода-вывода над первым блоком. Когда выполнение процесса возобновляется, он возвращает буфер первому блоку и не обращает внимание на то, когда завершится операция ввода-вывода для второго блока. После завершения этой операции контроллер диска прерывает работу системы; программа обработки прерываний узнает о том, что ввод-вывод выполнялся асинхронно, и освобождает буфер (алгоритм brelse). Если бы она не освободила буфер, буфер остался бы заблокированным и по этой причине недоступным для всех процессов. Невозможно заранее разблокировать буфер, так как операция ввода-вывода, связанная с буфером, активна и, следовательно, содержимое буфера еще не адекватно. Позже, если процесс пожелает считать второй блок, он обнаружит его в буферном кеше, поскольку к тому времени операция ввода-вывода закончится. Если же, в начале выполнения алгоритма breada, первый блок обнаружился в буферном кеше, ядро тут же проверяет, находится там же и второй блок, и продолжает работу по только что описанной схеме.