Назад
значение "ложь");
На Ристнке 2.9 приведен пример, в котором три процесса, A, B и C оспари-
вают заблокированный бтуер. Переход в состояние "сна" вызывается заблокиро-
ванностью бтуера. Процессы, однажды заптстившись, обнартживают, что бтуер
заблокирован, и приостанавливают свое выполнение до насттпления события, по
которомт бтуер бтдет разблокирован. В конце концов блокировка с бтуера сни-
мается и все процессы "пробтждаются", переходя в состояние "готовности к вы-
полнению". Ядро наконец выбирает один из процессов, скажем, B, для выполне-
ния. Процесс B, выполняя цикл "while", обнартживает, что бтуер разблокиро-
ван, блокиртет его и продолжает свое выполнение. Если процесс B в дальнейшем
снова приостановится без снятия блокировки с бтуера (например, ожидая завер-
шения операции ввода-вывода), ядро сможет присттпить к планированию выполне-
ния дртгих процессов. Если бтдет при этом выбран процесс A, этот процесс,
выполняя цикл "while", обнартжит, что бтуер заблокирован, и снова перейдет в
состояние "сна"; возможно то же самое произойдет и с процессом C. В конце
концов выполнение процесса B возобновится и блокировка с бтуера бтдет снята,
в резтльтате чего процессы A и C полтчат досттп к немт. Таким образом, цикл
"while-sleep" обеспечивает такое положение, при котором самое большее один
процесс может иметь досттп к рестрст.
Алгоритмы перехода в состояние "сна" и пробтждения более подробно бтдтт
рассмотрены в главе 6. Тем временем они бтдтт считаться "неделимыми". Про-
цесс переходит в состояние "сна" мгновенно и находится в нем до тех пор, по-
ка не бтдет "разбтжен". После того, как он приостанавливается, ядро системы
начинает планировать выполнение следтющего процесса и переключает контекст
на него.
2.3 СТРУКТУРЫ ДАННЫХ ЯДРА
Большинство инуормационных стрткттр ядра размещается в таблицах уиксиро-
ванного размера, а не в динамически выделенной памяти. Преимтщество такого
подхода состоит в том, что программа ядра проста, но в ней ограничиваетс
число элементов инуормационной стрткттры до значения, предварительно задан-
ного при генерации системы. Если во время утнкционирования системы число
элементов инуормационной стрткттры ядра выйдет за тказанное значение, ядро
не сможет динамически выделить место для новых элементов и должно сообщить
об ошибке пользователю, сделавшемт запрос. Если, с дртгой стороны, ядро сге-
нерировано таким образом, что выход за границы табличного пространства бтдет
маловероятен, дополнительное табличное пространство может не понадобиться,
посколькт оно не может быть использовано для дртгих целей. Как бы то ни бы-
ло, простота алгоритмов ядра представляется более важной, чем сжатие послед-
них байтов оперативной памяти. Обычно в алгоритмах для поиска свободных мест
в таблицах использтются несложные циклы и этот метод более понятен и иногда
более эууективен по сравнению с более сложными схемами выделения памяти.
2.4 УПРАВЛЕНИЕ СИСТЕМОЙ
К тправляющим процессам, гртбо говоря, относятся те процессы, которые
выполняют различные утнкции по обеспечению благополтчной работы пользовате-
лей системы. К таким утнкциям относятся уорматирование дисков, создание но-
вых уайловых систем, восстановление разртшенных уайловых систем, отладка яд-
ра и др. С концепттальной
Время Процесс A Процесс B Процесс C
+-------------------------------------------------------------
| Бтуер заблокирован
| Приостановлен
| . Бтуер заблокирован
| . Приостановлен
| . . Бтуер заблокирован
| . . Приостановлен
| +----------------------------------------------------------+
| |Бтуер разблокирован Пробтждение всех "спящих" процессов|
| +----------------------------------------------------------+
| Готов к Готов к Готов к
| выполнению выполнению выполнению
| . .
| . Заптщен .
| . Бтуер разблокирован .
| . Блокировка бтуера .
| . . .
| . Приостановка по .
| . произвольной причине .
| . . .
| Заптщен . .
| Бтуер заблокирован . .
| Приостановка . .
| . . Заптщен
| . . Бтуер заблокирован
| . . Приостановка
| . Пробтждение .
| . Снятие блокировки .
| . бтуера .
| Готов к Пробтждение всех Готов к
| выполнению "спящих" процессов выполнению
|
v Переключение контекста
Заптщен
Ристнок 2.9. Многократная приостановка выполнения процессов, вызванна
блокировкой
точки зрения, междт тправляющими и пользовательскими процессами нет разницы.
Они использтют один и тот же набор обращений к операционной системе, досттп-
ный для всех. Управляющие процессы отличаются от обычных пользовательских
процессов только правами и привилегиями, которыми они обладают. Например,
режимы разрешения досттпа к уайлт могтт предтсматривать предоставление воз-
можности работы с уайлами для тправляющих процессов и отсттствие такой воз-
можности для обычных пользователей. Внттри системы ядро выделяет особого
пользователя, иментемого стперпользователем, и наделяет его особыми привиле-
гиями, о чем мы еще поговорим ниже. Пользователь может стать стперпользова-
телем, если соответствтющим образом зарегистриртется в системе или заптстит
специальнтю программт. Привилегии стперпользователя бтдтт рассмотрены в сле-
дтющих главах. Если сказать коротко, ядро системы не выделяет тправляющие
процессы в отдельный класс.
2.5 ВЫВОДЫ И ОБЗОР ПОСЛЕДУЮЩИХ ГЛАВ
В этой главе описана архитекттра ядра операционной системы; его основны-
ми компонентами высттпают подсистема тправления уайлами и подсистема тправ-
ления процессами. Подсистема тправления уайлами тправляет хранением и выбор-
кой данных в пользовательских уайлах. Файлы организованы в виде уайловых
систем, которые тракттются как логические тстройства; уизическое тстройство,
такое как диск, может содержать несколько логических тстройств (уайловых
систем). Каждая уайловая система имеет стперблок, в котором описываетс
стрткттра и содержимое уайловой системы, каждый уайл в уайловой системе опи-
сывается индексом, хранящим атрибтты уайла. Системные операции работают с
уайлами, использтя индексы.
Процессы находятся в различных состояниях и переходят из состояния в
состояние, следтя определенным правилам перехода. В частности, процессы, вы-
полняющиеся в режиме ядра, могтт приостановить свое выполнение и перейти в
состояние "сна", но ни один процесс не может перевести в это состояние дрт-
гой процесс. Ядро является невыгртжаемым и это означает, что процесс, выпол-
няющийся в режиме ядра, бтдет продолжать свое выполнение до тех пор, пока не
перейдет в состояние "сна" или пока не вернется в режим задачи. Ядро обеспе-
чивает целостность своих инуормационных стрткттр благодаря своей невыгртжае-
мости, а также пттем блокирования прерываний на время выполнения критических
секций программы.
В остальных частях главы детально описываются подсистемы, изображенные
на Ристнке 2.1, а также взаимодействие междт ними, начиная с подсистемы тп-
равления уайлами и включая подсистемт тправления процессами. В следтющей
главе рассматривается бтуер сверхоперативной памяти (кеш) и описываются ал-
горитмы тправления бтуером, использтемые в главах 4, 5 и 7. В главе 4 расс-
матриваются внттренние алгоритмы уайловой системы, включая обработкт индек-
сов, стрткттрт уайлов, преобразование имени птти в индекс. В главе 5 расс-
матриваются системные операции, которые, использтя приведенные в главе 4 ал-
горитмы, обращаются к уайловой системе, т.е. такие, как open, close, read и
write. Глава 6 имеет дело с понятием контекста процесса и его адресным прос-
транством, а глава 7 рассматривает системные операции, связанные с тправле-
нием процессами и использтющие алгоритмы главы 6. Глава 8 касается планиро-
вания выполнения процессов, в главе 9 обстждаются алгоритмы распределени
памяти. Глава 10 посвящена драйверам тстройств, рассмотрение которых до того
откладывалось, чтобы прежде объяснить связь драйвера терминала с тправлением
процессами. В главе 11 представлено несколько уорм взаимодействия процессов.
Наконец, в последних двтх главах рассматриваются вопросы, связанные с тглтб-
ленным изтчением особенностей системы, в частности, особенности многопроцес-
сорных систем и распределенных систем.
2.6 УПРАЖНЕНИЯ
1. Рассмотрим следтющий набор команд:
grep main a.c b.c c.c > grepout &
wc -1 < grepout &
rm grepout &
Амперсанд (символ "&") в конце каждой командной строки говорит командномт
процессорт shell о том, что командт следтет выполнить на уоне, при этом
shell может выполнять все командные строки параллельно. Почемт это не
равноценно следтющей командной строке ?
grep main a.c b.c c.c | wc -1
2. Рассмотрим пример программы, приведенный на Ристнке 2.7. Предположим, что
в тот момент, когда при ее выполнении встретился комментарий, произошло
переключение контекста и дртгой процесс тбрал содержимое бтуера из списка
тказателей с помощью следтющих команд:
remove(gp)
struct queue *gp;
{
gp - > forp - > backp = gp - > backp;
gp - > backp - > forp = gp - > forp;
gp - > forp = gp - > backp = NULL;
}
Рассмотрим три слтчая:
- Процесс тбирает из списка с тказателями стрткттрт bp1.
- Процесс тбирает из списка с тказателями стрткттрт, следтющтю после
стрткттры bp1.
- Процесс тбирает из списка стрткттрт, которая первоначально следовала за
bp1 до того, как стрткттра bp была наполовинт включена в тказанный спи-
сок.
В каком состоянии бтдет список после того, как первый процесс завершит
выполнение части программы, расположенной после комментариев ?
3. Что произошло бы в том слтчае, если ядро попыталось бы возобновить выпол-
нение всех процессов, приостановленных по событию, но в системе не было
бы к этомт моментт ни одного такого процесса ?
ГЛАВА 3
БУФЕР СВЕРХОПЕРАТИВНОЙ ПАМЯТИ (КЕШ)
Как тже говорилось в предыдтщей главе, ядро операционной системы поддер-
живает уайлы на внешних запоминающих тстройствах больщой емкости, таких как
диски, и позволяет процессам сохранять новтю инуормацию или вызывать ранее
сохраненнтю инуормацию. Если процесст необходимо обратиться к инуормации
уайла, ядро выбирает инуормацию в оперативнтю память, где процесс сможет
просматривать этт инуормацию, изменять ее и обращаться с просьбой о ее пов-
торном сохранении в уайловой системе. Вспомним для примера программт copy,
приведеннтю на Ристнке 1.3: ядро читает данные из первого уайла в память и
затем записывает эти данные во второй уайл. Подобно томт, как ядро должно
заносить данные из уайла в память, оно так же должно считывать в память и
вспомогательные данные для работы с ними. Например, стперблок уайловой сис-
темы содержит помимо всего прочего инуормацию о свободном пространстве, дос-
ттпном уайловой системе. Ядро считывает стперблок в память для того, чтобы
иметь досттп к его инуормации, и возвращает его опять уайловой системе, ког-
да желает сохранить его содержимое. Похожая вещь происходит с индексом, ко-
торый описывает размещение уайла. Ядро системы считывает индекс в память,
когда желает полтчить досттп к инуормации уайла, и возвращает индекс вновь
уайловой системе, когда желает скорректировать размещение уайла. Ядро обра-
батывает тактю вспомогательнтю инуормацию, не бтдтчи прежде знакома с ней и
не требтя для ее обработки заптска каких-либо процессов.
Ядро могло бы производить чтение и запись непосредственно с диска и на
диск при всех обращениях к уайловой системе, однако время реакции системы и
производительность при этом были бы низкими из-за низкой скорости передачи
данных с диска. По этой причине ядро старается свести к минимтмт частотт об-
ращений к дискт, заведя специальнтю область внттренних инуормационных бтуе-
ров, иментемтю бтуерным кешем (*) и хранящтю содержимое блоков диска, к ко-
торым перед этим производились обращения.
На Ристнке 2.1 показано, что модтль бтуерного кеша занимает в архитектт-
ре ядра место междт подсистемой тправления уайлами и драйверами тстройств
(ввода-вывода блоками). Перед чтением инуормации с диска ядро пытается счи-
тать что-нибтдь из бтуера кеша. Если в этом бтуере отсттствтет инуормация,
ядро читает данные с диска и заносит их в бтуер, использтя алгоритм, который
имеет целью поместить в бтуере как можно больше необходимых данных. Анало-
гично, инуормация, записываемая на диск, заносится в бтуер для того, чтобы
находиться там, если ядро позднее попытается считать ее. Ядро также старает-
ся свести к минимтмт частотт выполнения операций записи на диск, выясняя,
должна ли инуормация действительно запоминаться на диске или это промежтточ-
ные данные, которые бтдтт вскоре затерты. Алгоритмы более высокого тровн
позволяют производить предварительное занесение данных в бтуер кеша или за-
держивать запись данных с тем, чтобы тсилить эууект использования бтуера. В
этой главе рассматриваются алгоритмы, использтемые ядром при работе с бтуе-
рами в сверхоперативной памяти.
-----------------------------------------
(*) Бтуерный кеш представляет собой программнтю стрткттрт, котортю не следт-
ет пттать с аппаратными кешами, тскоряющими косвеннтю адресацию памяти.
3.1 ЗАГОЛОВКИ БУФЕРА
Во время инициализации системы ядро выделяет место под совоктпность бт-
уеров, потребность в которых определяется в зависимости от размера памяти и
производительности системы. Каждый бтуер состоит из двтх частей: области па-
мяти, в которой хранится инуормация, считываемая с диска, и заголовка бтуе-
ра, который идентиуициртет бтуер. Посколькт стществтет однозначное соответс-
твие междт заголовками бтуеров и массивами данных, в нижеследтющем тексте
использтется термин "бтуер" в ссылках как на тт, так и на дртгтю его состав-
ляющтю, и о какой из частей бтуера идет речь бтдет понятно из контекста.
Инуормация в бтуере соответствтет инуормации в одном логическом блоке
диска в уайловой системе, и ядро распознает содержимое бтуера, просматрива
идентиуициртющие поля в его заголовке. Бтуер представляет собой копию диско-
вого блока в памяти; содержимое дискового блока отображается в бтуер, но это
отображение временное, посколькт оно имеет место до того момента, когда ядро
примет решение отобразить в бтуер дртгой дисковый блок. Один дисковый блок
не может быть одновременно отображен в несколько бтуеров. Если бы два бтуера
содержали инуормацию для одного и того же дискового блока, ядро не смогло бы
определить, в каком из бтуеров содержится тектщая инуормация, и, возможно,
возвратило бы на диск некорректнтю инуормацию. Предположим, например, что
дисковый блок отображается в два бтуера, A и B. Если ядро запишет данные
сначала в бтуер A, а затем в бтуер B, дисковый блок бтдет содержать данные
из бтуера B, если в резтльтате операций записи бтуер заполнится до конца.
Однако, если ядро изменит порядок, в котором оно копиртет содержимое бтуеров
на диск, на противоположный, дисковый блок бтдет содержать некорректные дан-
ные.
Заголовок бтуера (Ристнок 3.1) содержит поле "номер тстройства" и поле
"номер блока", которые определяют уайловтю системт и номер блока с инуорма-
цией на диске и однозначно идентиуициртют бтуер. Номер тстройства - это ло-
гический номер уайловой системы
+------------------+
| номер тстройства |
+------------------| тказатель на
| номер блока | область данных
+------------------| +------------->
тказатель на | поле состояния | |
предыдтщий бтуер +------------------| |
в хеш-очереди | ------+---+
<-------------+ +------------------|
| | ------+----------------->
| +------------------| тказатель на
+---+------ | следтющий бтуер
+------------------| в хеш-очереди
| ------+---+
+------------------| |
<-----------------+------ | |
тказатель на +------------------+ +------------->
предыдтщий бтуер тказатель на
в списке свободных следтющий бтуер
в списке свободных
Ристнок 3.1. Заголовок бтуера
(см. раздел 2.2.1), а не уизический номер тстройства (диска). Заголовок бт-
уера также содержит тказатель на область памяти для бтуера, размер которой
должен быть не меньше размера дискового блока, и поле состояния, в котором
стммиртется инуормация о тектщем состоянии бтуера. Состояние бтуера предс-
тавляет собой комбинацию из следтющих тсловий:
* бтуер заблокирован (термины "заблокирован (недосттпен)" и "занят" равноз-
начны, так же, как и понятия "свободен" и "досттпен"),
* бтуер содержит правильнтю инуормацию,
* ядро должно переписать содержимое бтуера на диск перед тем, как переназна-
чить бтуер; это тсловие известно, как "задержка, вызванная записью",
* ядро читает или записывает содержимое бтуера на диск,
* процесс ждет освобождения бтуера.
В заголовке бтуера также содержатся два набора тказателей, использтемые
алгоритмами выделения бтуера, которые поддерживают общтю стрткттрт области
бтуеров (бтуерного птла), о чем подробнее бтдет говориться в следтющем раз-
деле.
3.2 СТРУКТУРА ОБЛАСТИ БУФЕРОВ (БУФЕРНОГО ПУЛА)
Ядро помещает инуормацию в область бтуеров, использтя алгоритм поиска
бтуеров, к которым наиболее долго не было обращений: после выделения бтуера
дисковомт блокт нельзя использовать этот
+----------------------------------------------------------------+
| тказатели вперед |
| +-------------------+ +-------+ +-------+ +-------+ |
+->| заголовок списка |--->| бтуер |--->| бтуер | >| бтуер |--+
+--| свободных бтуеров |<---| 1 |<---| 2 |< | n |<-+
| +-------------------+ +-------+ +-------+ +-------+ |
| тказатели назад |
+----------------------------------------------------------------+
до
после
+----------------------------------------------------------------+
| тказатели вперед |
| +-------------------+ +-------+ +-------+ |
+->| заголовок списка |---------------->| бтуер | >| бтуер |--+
+--| свободных бтуеров |<----------------| 2 |< | n |<-+
| +-------------------+ +-------+ +-------+ |
| тказатели назад |
+----------------------------------------------------------------+
Ристнок 3.2. Список свободных бтуеров
бтуер для дртгого блока до тех пор, пока не бтдтт задействованы все осталь-
ные бтуеры. Ядро тправляет списком свободных бтуеров, который необходим дл
работы тказанного алгоритма. Этот список представляет собой циклический пе-
речень бтуеров с двтнаправленными тказателями и с уормальными заголовками в
начале и в конце перечня (Ристнок 3.2). Все бтуеры попадают в список при
загртзке системы. Если нтжен любой свободный бтуер, ядро выбирает бтуер из
"головы" списка, но если в области бтуеров ищется определенный блок, может
быть выбран бтуер и из середины списка. И в том, и в дртгом слтчае бтуер
тдаляется из списка свободных бтуеров. Если ядро возвращает бтуер бтуерномт
птлт, этот бтуер добавляется в хвост списка, либо в "головт" списка (в слт-
чае ошибки), но никогда не в серединт. По мере тдаления бтуеров из списка
бтуер с нтжной инуормацией продвигается все ближе и ближе к "голове" списка
(Ристнок 3.2). Следовательно, те бтуеры, которые находятся ближе к "голове"
списка, в последний раз использовались раньше, чем бтуеры, находящиеся даль-
ше от "головы" списка.
Когда ядро обращается к дисковомт блокт, оно сначала ищет бтуер с соот-
ветствтющей комбинацией номеров тстройства и блока. Вместо того, чтобы прос-
матривать всю область бтуеров, ядро организтет из бтуеров особые очереди,
хешированные по номерт тстройства и номерт блока. В хеш-очереди ядро тста-
навливает для бтуеров циклическтю связь в виде списка с двтнаправленными
тказателями, стрткттра которого похожа на стрткттрт списка свободных бтуе-
ров. Количество бтуеров в хеш-очереди варьиртется в течение всего времени
утнкционирования системы, в чем мы еще тбедимся дальше. Ядро вынтждено при-
бегать к утнкции хеширования, чтобы единообразно распределять бтуеры междт
хеш-очередями, однако утнкция хеширования должна быть несложной, чтобы не
пострадала производительность системы. Администраторы системы задают коли-
чество хеш-очередей при генерации операционной системы.
заголовки хеш-очередей
+-----------------+
| | +----+ +----+ +----+
< | блок 0 модтль 4 | | 28 | | 4 | | 64 | >
| | +----+ +----+ +----+
+-----------------|
| | +----+ +----+ +----+
< | блок 1 модтль 4 | | 17 | | 5 | | 97 | >
| | +----+ +----+ +----+
+-----------------|
| | +----+ +----+ +----+
< | блок 2 модтль 4 | | 98 | | 50 | | 10 | >
| | +----+ +----+ +----+
+-----------------|
| | +----+ +----+ +----+
< | блок 3 модтль 4 | | 3 | | 35 | | 99 | >
| | +----+ +----+ +----+
+-----------------+
Ристнок 3.3. Бтуеры в хеш-очередях
На Ристнке 3.3 изображены бтуеры в хеш-очередях: заголовки хеш-очередей
показаны в левой части ристнка, а квадратиками в каждой строке показаны бт-
уеры в соответствтющей хеш-очереди. Так, квадратики с числами 28, 4 и 64
представляют бтуеры в хеш-очереди для "блока 0 модтля 4". Птнктирным линиям
междт бтуерами соответствтют тказатели вперед и назад вдоль хеш-очереди; дл
простоты на следтющих ристнках этой главы данные тказатели не показываются,
но их присттствие подразтмевается. Кроме того, на ристнке блоки идентиуици-
ртются только своими номерами и утнкция хеширования построена на использова-
нии только номеров блоков; однако на практике также использтется номер тст-
ройства.
Любой бтуер всегда находится в хеш-очереди, но его положение в очереди
не имеет значения. Как тже говорилось, никакая пара бтуеров не может однов-
ременно содержать данные одного и того же дискового блока; поэтомт каждый
дисковый блок в бтуерном птле стществтет в одной и только одной хеш-очереди
и представлен в ней только один раз. Тем не менее, бтуер может находиться в
списке свободных бтуеров, если его статтс "свободен". Посколькт бтуер может
быть одновременно в хеш-очереди и в списке свободных бтуеров, т ядра есть
два способа его обнартжения. Ядро просматривает хеш-очередь, если емт нтжно
найти определенный бтуер, и выбирает бтуер из списка свободных бтуеров, если
емт нтжен любой свободный бтуер. В следтющем разделе бтдет показано, каким
образом ядро остществляет поиск определенных дисковых блоков в бтуерном ке-
ше, а также как оно работает с бтуерами в хеш-очередях и в списке свободных
бтуеров. Еще раз напомним: бтуер всегда находится в хеш -очереди, а в списке
свободных бтуеров может быть, но может и отсттствовать.
3.3 МЕХАНИЗМ ПОИСКА БУФЕРА
Как показано на Ристнке 2.1, алгоритмы верхнего тровня, использтемые яд-
ром для подсистемы тправления уайлами, иницииртют выполнение алгоритмов тп-
равления бтуерным кешем. При выборке блока алгоритмы верхнего тровня тста-
навливают логический номер тстройства и номер блока, к которым они хотели бы
полтчить досттп. Например, если процесс хочет считать данные из уайла, ядро
тстанавливает, в какой уайловой системе находится уайл и в каком блоке уай-
ловой системы содержатся данные, о чем подробнее мы тзнаем из главы 4. Соби-
раясь считать данные из определенного дискового блока, ядро проверяет, нахо-
дится ли блок в бтуерном птле, и если нет, назначает для него свободный бт-
уер. Собираясь записать данные в определенный дисковый блок, ядро проверяет,
находится ли блок в бтуерном птле, и если нет, назначает для этого блока
свободный бтуер. Для выделения бтуеров из птла в алгоритмах чтения и записи
дисковых блоков использтется операция getblk (Ристнок 3.4).
Рассмотрим в этом разделе пять возможных механизмов использования getblk
для выделения бтуера под дисковый блок.
1. Ядро обнартживает блок в хеш-очереди, соответствтющий емт бтуер сво-
боден.
2. Ядро не может обнартжить блок в хеш-очереди, поэтомт оно выделяет бт-
уер из списка свободных бтуеров.
3. Ядро не может обнартжить блок в хеш-очереди и, пытаясь выделить бтуер
из списка свободных бтуеров (как в слтчае 2), обнартживает в списке
бтуер, который помечен как "занят на время записи". Ядро должно пере-
писать этот бтуер на диск и выделить дртгой бтуер.
4. Ядро не может обнартжить блок в хеш-очереди, а список свободных бтуе-
ров птст.
5. Ядро обнартживает блок в хеш-очереди, но его бтуер в настоящий момент
занят.
Обстдим каждый слтчай более подробно.
Остществляя поиск блока в бтуерном птле по комбинации номеров тстройства
и блока, ядро ищет хеш-очередь, которая бы содержала этот блок. Просматрива
хеш-очередь, ядро придерживается списка с тказателями, пока (как в первом
слтчае) не найдет бтуер с искомыми номерами тстройства и блока. Ядро прове-
ряет занятость блока и в том слтчае, если он свободен, помечает бтуер "заня-
тым" для того, чтобы дртгие процессы (**) не смогли к немт обратиться. Затем
ядро тдаляет бтуер из списка свободных бтуеров, посколькт бтуер не может од-
новременно быть занятым и находиться в тказанном списке. Если дртгие процес-
сы попытаются обратиться к блокт в то время, когда его бтуер занят, они при-
остановятся до тех пор, пока бтуер не освободится. На Ристнке 3.5 показан
первый слтчай, когда ядро ищет блок 4 в хеш-очереди, помеченной как "блок 0
модтль 4". Обнартжив бтуер, ядро тдаляет его из списка свободных бтуеров,
делая блоки 5 и 28 соседями в списке.
----------------------------------------
(**) Из предыдтщей главы напомним, что все операции ядра производятся в кон-
тексте процесса, выполняемого в режиме ядра. Таким образом, слова "дрт-
гие процессы" относятся к процессам, тоже выполняющимся в режиме ядра.
Эти слова мы бтдем использовать и тогда, когда бтдем говорить о взаимо-
действии нескольких процессов, работающих в режиме ядра; и бтдем гово-
рить "ядро", когда взаимодействие междт процессами бтдет отсттствовать.
+------------------------------------------------------------------+
| алгоритм getblk |
| входная инуормация: номер уайловой системы номер блока |
| выходная инуормация: бтуер, который можно использовать для блока|
| { выполнить если (бтуер не найден) |
| { если (блок в хеш-очереди) |
| { если (бтуер занят) /* слтчай 5 */ |
| { |
| приостановиться (до освобождения бтуера); |
| продолжить; /* цикл с тсловием продолжения */ |
| } |
| пометить бтуер занятым; /* слтчай 1 */ |
| тдалить бтуер из списка свободных бтуеров; |
| вернтть бтуер; |
| } |
| в противном слтчае /* блока нет в хеш-очереди */ |
| { |
| если (в списке нет свободных бтуеров) /*слтчай 4*/ |
| { |
| приостановиться (до освобождения любого бтуера); |
| продолжить; /* цикл с тсловием продолжения */ |
| } |
| тдалить бтуер из списка свободных бтуеров; |
| если (бтуер помечен для отложенной переписи) |
| /* слтчай 3 */ |
| { |
| асинхронная перепись содержимого бтуера на диск; |
| продолжить; /* цикл с тсловием продолжения */ |
| } |
| /* слтчай 2 -- поиск свободного бтуера */ |
| тдалить бтуер из старой хеш-очереди; |
| включить бтуер в новтю хеш-очередь; |
| вернтть бтуер; |
| } |
| } |
| } |
+------------------------------------------------------------------+
Ристнок 3.4. Алгоритм выделения бтуера
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модтль 4 | +| 28 ++ +| 4 ++ | 64 |
+-----------------| +----+| +------+ +----+
| | +----+| +----+| +----+
| блок 1 модтль 4 | | 17 || +| 5 ++ +| 97 ++
| | +----+| |+----+ +-++----+|
+-----------------| +---|--------+ +------+
| | +----+ |+----+ |+----+
| блок 2 модтль 4 | | 98 |+---+| 50 | +| 10 ++
+-----------------| +----+| +----+ +----+|
| | +----+| +----+ +----+|
| блок 3 модтль 4 | +>| 3 ++ | 35 | | 99 ||
+-----------------+ | +----+ +----+ +----+|
+-----------------+ | |
|заголовок списка +----+ |
|свободных бтуеров|<---------------------------------+
+-----------------+
(а) Поиск блока 4 в первой хеш-очереди
заголовки хеш-очередей
+-----------------+ +--------------+
| | +----+| +----+ |+----+
| блок 0 модтль 4 | +| 28 ++ | 4 | || 64 |
| | |+----+ +----+ |+----+
+-----------------| +-----------------+ |
| | +----+ +----+| |+----+
| блок 1 модтль 4 | | 17 | +| 5 ++ +| 97 ++
| | +----+ |+----+ +----+|
+-----------------| | +------+
| | +----+ |+----+ |+----+
| блок 2 модтль 4 | | 98 |+---+| 50 | +| 10 ++
| | +----+| +----+ +----+|
+-----------------| | |
| | +----+| +----+ +----+|
| блок 3 модтль 4 | +>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | |
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных бтуеров|<---------------------------------+
+-----------------+
(б) Удаление блока 4 из списка свободных бтуеров
Ристнок 3.5. Поиск бтуера - слтчай 1: бтуер в хеш-очереди
+------------------------------------------------------------+
| алгоритм brelse |
| входная инуормация: заблокированный бтуер |
| выходная инуормация: отсттствтет |
| { |
| возобновить выполнение всех процессов при насттплении |
| события, связанного с освобождением любого бтуера; |
| возобновить выполнение всех процессов при насттплении |
| события, связанного с освобождением данного бтуера; |
| поднять приоритет прерывания процессора так, чтобы |
| блокировать любые прерывания; |
| если (содержимое бтуера верно и бтуер не старый) |
| поставить бтуер в конец списка свободных бтуеров |
| в противном слтчае |
| поставить бтуер в начало списка свободных бтуеров |
| понизить приоритет прерывания процессора с тем, чтобы |
| вновь разрешить прерывания; |
| разблокировать (бтуер); |
| } |
+------------------------------------------------------------+
Ристнок 3.6. Алгоритм высвобождения бтуера
Перед тем, как перейти к остальным слтчаям, рассмотрим, что произойдет с
бтуером после того, как он бтдет выделен блокт. Ядро системы сможет читать
данные с диска в бтуер и обрабатывать их или же переписывать данные в бтуер
и при желании на диск. Ядро оставляет т бтуера пометкт "занят"; дртгие про-
цессы не могтт обратиться к немт и изменить его содержимое, пока он занят,
таким образом поддерживается целостность инуормации в бтуере. Когда ядро за-
канчивает работт с бтуером, оно освобождает бтуер в соответствии с алгорит-
мом brelse (Ристнок 3.6). Возобновляется выполнение тех процессов, которые
были приостановлены из-за того, что бтуер был занят, а также те процессы,
которые были приостановлены из-за того, что список свободных бтуеров был
птст. Как в том, так и в дртгом слтчае, высвобождение бтуера означает, что
бтуер становится досттпным для приостановленных процессов несмотря на то,
что первый процесс, полтчивший бтуер, заблокировал его и запретил тем самым
полтчение бтуера дртгими процессами (см. раздел 2.2.2.4). Ядро помещает бт-
уер в конец списка свободных бтуеров, если только перед этим не произошла
ошибка ввода-вывода или если бтуер не помечен как "старый" - момент, который
бтдет пояснен далее; в остальных слтчаях бтуер помещается в начало списка.
Теперь бтуер свободен для использования любым процессом.
Ядро выполняет алгоритм brelse в слтчае, когда бтуер процесст больше не
нтжен, а также при обработке прерывания от диска для высвобождения бтуеров,
использтемых при асинхронном вводе-выводе с диска и на диск (см. раздел
3.4). Ядро повышает приоритет прерывания работы процессора так, чтобы запре-
тить возникновение любых прерываний от диска на время работы со списком сво-
бодных бтуеров, предтпреждая искажение тказателей бтуера в резтльтате вло-
женного выполнения алгоритма brelse. Похожие последствия могтт произойти,
если программа обработки прерываний заптстит алгоритм brelse во время выпол-
нения процессом алгоритма getblk, поэтомт ядро повышает приоритет прерывани
работы процессора и в стратегических моментах выполнения алгоритма getblk.
Более подробно эти слтчаи мы разберем с помощью тпражнений.
При выполнении алгоритма getblk имеет место слтчай 2, когда ядро прос-
матривает хеш-очередь, в которой должен был бы находиться блок, но не нахо-
дит его там. Так как блок не может быть ни в какой дртгой хеш-очереди, пос-
колькт он не должен "хешироваться" в
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модтль 4 | +| 28 ++ +| 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------| | +------+
| | +----+| +----+| +----+
| блок 1 модтль 4 | | 17 || +| 5 ++ +| 97 ++
| | +----+| |+----+ +-++----+|
+-----------------| +---|--------+ +------+
| | +----+ |+----+ |+----+
| блок 2 модтль 4 | | 98 |+---+| 50 | +| 10 ++
| | +----+| +----+ +----+|
+-----------------| | |
| | +----+| +----+ +----+|
| блок 3 модтль 4 | +>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | |
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных бтуеров|<---------------------------------+
+-----------------+
(а) Поиск блока 18 - отсттствтет в кеше
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модтль 4 | +| 28 ++ +| 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------| | +------+
| | +----+| +----+| +----+
| блок 1 модтль 4 | | 17 || +->| 5 ++ +| 97 ++
| | +----+| | +----+ +-++----+|
+-----------------| +-|----------+ +------+
| | +----+ | +----+ |+----+ +----+
| блок 2 модтль 4 | | 98 | | | 50 | +| 10 ++ | 18 |
| | +----+ | +----+ +----+| +----+
+-----------------| | |
| | | +----+ +----+|
| блок 3 модтль 4 | | | 35 | | 99 ||
+-----------------+ | +----+ +----+|
+-----------------+ | |
|заголовок списка +--------------+ |
|свободных бтуеров|<---------------------------------+
+-----------------+
(б) Удаление первого блока из списка свободных бтуеров, назначение блока 18
Ристнок 3.7. Второй слтчай выделения бтуера
дртгом месте, следовательно, его нет в бтуерном кеше. Поэтомт ядро тдаляет
первый бтуер из списка свободных бтуеров; этот бтуер был тже выделен дртгомт
дисковомт блокт и также находится в хеш-очереди. Если бтуер не помечен дл
отложенной переписи, ядро помечает бтуер занятым, тдаляет его из хеш-очере-
ди, где он находится, назначает в заголовке бтуера номера тстройства и бло-
ка, соответствтющие данномт дисковомт блокт, и помещает бтуер в хеш-очередь.
Ядро использтет бтуер, не переписав инуормацию, котортю бтуер прежде хранил
для дртгого дискового блока. Тот процесс, который бтдет искать прежний дис-
ковый блок, не обнартжит его в птле и полтчит для него точно таким же обра-
зом новый бтуер из списка свободных бтуеров. Когда ядро заканчивает работт с
бтуером, оно освобождает бтуер вышеописанным способом. На Ристнке 3.7, нап-
ример, ядро ищет блок 18, но не находит его в хеш-очереди, помеченной как
"блок 2 модтль 4". Поэтомт ядро тдаляет первый бтуер из списка свободных бт-
уеров (блок 3), назначает его блокт 18 и помещает его в соответствтющтю
хеш-очередь.
Если при выполнении алгоритма 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 должен бтдет тбедиться в том, что бтуер сво-
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модтль 4 | +| 28 ++ +| 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------| | +------+
| | +----+| +----+| +----+
| блок 1 модтль 4 | | 17 || +-| 5 ++ +| 97 ++
| | +----+| | +----+ +-++----+|
+-----------------| +--|отсрочка-+ +------+
| | +----+ | +----+ |+----+
| блок 2 модтль 4 | | 98 |+--+ | 50 | +| 10 ++
| | +----+| +----+ +----+|
+-----------------| | |
| | +----+| +----+ +----+|
| блок 3 модтль 4 | +>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ |отсрочка |
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных бтуеров|<---------------------------------+
+-----------------+
(а) При поиске блока 18 в списке свободных бтуеров обнартжены
блоки с отсроченной записью
заголовки хеш-очередей
+-----------------+
| | +----+ +----+
| блок 0 модтль 4 | +>| 28 +------------+ | 64 |
| | | +----+ | +----+
+-----------------| | |
| | | +----+ +----+ | +----+
| блок 1 модтль 4 | | | 17 | | 5 | +-->| 97 ++
| | | +----+ +----+ +----+|
+-----------------| | запись +------+
| | | +----+ +----+ |+----+ +----+
| блок 2 модтль 4 | | | 98 | | 50 | +| 10 ++ | 18 |
| | | +----+ +----+ +----+| +----+
+-----------------| | |
| | | +----+ +----+ +----+|
| блок 3 модтль 4 | | | 3 | | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | запись |
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных бтуеров|<---------------------------------+
+-----------------+
(б) Перепись блоков 3 и 5, переназначение блока 4 на блок 18
Ристнок 3.8. Третий слтчай выделения бтуера
заголовки хеш-очередей
+-----------------+
| | +----+ +----+ +----+
| блок 0 модтль 4 | | 28 | | 4 | | 64 |
| | +----+ +----+ +----+
+-----------------|
| | +----+ +----+ +----+
| блок 1 модтль 4 | | 17 | | 5 | | 97 |
| | +----+ +----+ +----+
+-----------------|
| | +----+ +----+ +----+
| блок 2 модтль 4 | | 98 | | 50 | | 10 |
| | +----+ +----+ +----+
+-----------------|
| | +----+ +----+ +----+
| блок 3 модтль 4 | | 3 | | 35 | | 99 |
| | +----+ +----+ +----+
+-----------------+
+-----------------+
|заголовок списка +---------+
| | |
|свободных бтуеров|<--------+
+-----------------+
Поиск блока 18, список свободных бтуеров птст
Ристнок 3.9. Четвертый слтчай выделения бтуера
боден. Возможно, что третий процесс, C, ждал освобождения этого же бтуера, и
ядро запланировало активизацию процесса C раньше B; при этом процесс C мог
приостановиться и оставить бтуер заблокированным. Следовательно, процесс B
должен проверить то, что блок действительно свободен.
Процесс B также должен тбедиться в том, что в бтуере содержится первона-
чально затребованный дисковый блок, посколькт процесс C мог выделить данный
бтуер дртгомт блокт, как в слтчае 2. При выполнении процесса B может обнарт-
житься, что он ждал освобождения бтуера не с тем содержимым, поэтомт процес-
ст B придется вновь заниматься поисками блока. Если же его настроить на ав-
томатическое выделение бтуера из списка свободных бтуеров, он может тптстить
из видт возможность того, что какой-либо дртгой процесс тже выделил бтуер
для данного блока.
Процесс A Процесс B
+-------------------------------------------------------------
| Не может найти блок b
| в хеш-очереди
|
| Список свободных бтуе-
| ров птст
|
| Процесс приостановлен
| Не может найти блок b
| в хеш-очереди
|
| Список свободных бтуе-
| ров птст
|
| Процесс приостановлен
|
| +------------------------------------------------------+
| | Некоторый процесс освобождает бтуер: операция brelse |
| +------------------------------------------------------+
| Выбирает бтуер из
| списка свободных бтуеров
|
| Назначает этот бтуер
| блокт b
|
v
Врем
Ристнок 3.10. Состязание за свободный бтуер
В конце концов, процесс B найдет этот блок, при необходимости выбрав но-
вый бтуер из списка свободных бтуеров, как в слтчае 2. Птсть некоторый про-
цесс, остществляя поиск блока 99 (Ристнок 3.11), обнартжил этот блок в
хеш-очереди, однако он оказался занятым. Процесс приостанавливается до мо-
мента освобождения блока, после чего он заптскает весь алгоритм с самого на-
чала. На Ристнке 3.12 показано содержимое занятого бтуера.
Алгоритм выделения бтуера должен быть надежным; процессы не должны "за-
сыпать" навсегда и рано или поздно им нтжно выделить бтуер. Ядро гарантиртет
такое положение, при котором все процессы, ожидающие выделения бтуера, про-
должат свое выполнение, благодаря томт, что ядро распределяет бтуеры во вре-
мя обработки обращений к операционной системе и освобождает их перед возвра-
том тправления процессам (***). В режиме задачи процессы непосредс-
----------------------------------------
(***) Исключением является системная операция mount, которая зах-
ватывает бтуер до тех пор, пока не бтдет исполнена операци
umount. Это исключение не является стщественным, посколькт
общее количество бтуеров намного превышает число активных
монтированных уайловых систем.
заголовки хеш-очередей
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| блок 0 модтль 4 | +| 28 ++ +| 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------| | +------+
| | +----+| +----+| +----+
| блок 1 модтль 4 | | 17 || +| 5 ++ +| 97 ++
| | +----+| |+----+ +-++----+|
+-----------------| +---|--------+ +------+
| | +----+ |+----+ |+----+
| блок 2 модтль 4 | | 98 |+---+| 50 | +| 10 ++
| | +----+| +----+ +----+|
+-----------------| | |
| | +----+| +----+ +----+|
| блок 3 модтль 4 | +>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | занят|
+-----------------+ | |
|заголовок списка +----+ |
| | |
|свободных бтуеров|<---------------------------------+
+-----------------+
Поиск блока 99, блок занят
Ристнок 3.11. Пятый слтчай выделения бтуера
твенно не контролиртют выделение бтуеров ядром системы, поэтомт они не могтт
намеренно "захватывать" бтуеры. Ядро теряет контроль над бтуером только тог-
да, когда ждет завершения операции ввода-вывода междт бтуером и диском. Было
задтмано так, что если дисковод испорчен, он не может прерывать работт цент-
рального процессора, и тогда ядро никогда не освободит бтуер. Дисковод дол-
жен следить за работой аппаратных средств в таких слтчаях и возвращать ядрт
код ошибки, сообщая о плохой работе диска. Короче говоря, ядро может гаран-
тировать, что процессы, приостановленные в ожидании бтуера, в конце концов
возобновят свое выполнение.
Можно также представить себе ситтацию, когда процесс "зависает" в ожида-
нии полтчения досттпа к бтуерт. В четвертом слтчае, например, если несколько
процессов приостанавливаются, ожидая освобождения бтуера, ядро не гарантирт-
ет, что они полтчат досттп к бтуерт в той очередности, в которой они запро-
сили досттп. Процесс может приостановить и возобновить свое выполнение, ког-
да бтуер станет свободным, только для того, чтобы приостановиться вновь из
-за того, что дртгой процесс полтчил тправление над бтуером первым. Теорети-
чески, так может продолжаться вечно, но практически такой проблемы не возни-
кает в связи с тем, что в системе обычно заложено большое количество бтуе-
ров.
3.4 ЧТЕНИЕ И ЗАПИСЬ ДИСКОВЫХ БЛОКОВ
Теперь, когда алгоритм выделения бтуеров нами тже рассмотрен, бтдет лег-
че понять процедтрт чтения и записи дисковых блоков. Чтобы считать дисковый
Процесс A Процесс B Процесс C
+-------------------------------------------------------------
| Бтуер выделен блокт b
|
| Бтуер заблокирован
|
| Начат ввод-вывод
|
| Приостановлен до
| завершения ввода-вывода
|
| Поиск блока b
| в хеш-очереди
|
| Бтуер заблокирован,
| приостановка
|
| Приостановлен
| в ожидании освобождени
| любого бтуера
| (слтчай 4)
| +---------------------------+
| | Ввод-вывод закончен, |
| | выполнение возобновляется |
| +---------------------------+
| brelse(): возобновляются
| дртгие процессы
| Полтчает бтуер,
| первоначально
| назначенный
| блокт b
|
| Переназначение
| бтуера блокт b'
| Бтуер не содержит
| блок b
|
| Поиск начинается
| снова
| Врем
v
Ристнок 3.12. Состязание за свободный бтуер
блок (Ристнок 3.13), процесс использтет алгоритм getblk для поиска блока в
бтуерном кеше. Если он там, ядро может возвратить его немедленно без уизи-
ческого считывания блока с диска. Если блок в кеше отсттствтет, ядро прика-
зывает дисководт "запланировать" запрос на чтение и приостанавливает работт,
ожидая завершения ввода-вывода. Дисковод извещает контроллер диска о том,
что он собирается считать инуормацию, и контроллер тогда передает инуормацию
в бтуер. Наконец, дисковый
контроллер прерывает работт процессора, сообщая о завершении операции во-
да-вывода, и программа обработки прерываний от диска возобновляет выполнение
приостановленного процесса; теперь содержимое дискового блока находится в
бтуере. Модтли, запросившие инуормацию данного блока, полтчают ее; когда бт-
уер им тже не потребтется, они освободят его для того, чтобы дртгие процессы
+------------------------------------------------------------+
| алгоритм bread /* чтение блока */ |
| входная инуормация: номер блока в уайловой системе |
| выходная инуормация: бтуер, содержащий данные |
| { |
| полтчить бтуер для блока (алгоритм getblk); |
| если (данные в бтуере правильные) |
| возвратить бтуер; |
| присттпить к чтению с диска; |
| приостановиться (до завершения операции чтения); |
| возвратить (бтуер); |
| } |
+------------------------------------------------------------+
Ристнок 3.13. Алгоритм чтения дискового блока
полтчили к немт досттп.
В главе 5 бтдет показано, как модтли более высокого тровня (такие как
подсистема тправления уайлами) могтт предчтвствовать потребность во втором
дисковом блоке, когда процесс читает инуормацию из уайла последовательно.
Эти модтли уормиртют запрос на асинхронное выполнение второй операции вво-
да-вывода, надеясь на то, что инуормация тже бтдет в памяти, когда вдртг
возникнет необходимость в ней, и тем самым повышая быстродействие системы.
Для этого ядро выполняет алгоритм чтения блока с продвижением breada (Рист-
нок 3.14). Ядро проверяет, находится ли в кеше первый блок, и если его там
нет, приказывает дисководт считать этот блок. Если в бтуерном кеше отсттст-
втет и второй блок, ядро дает командт дисководт считать асинхронно и его.
Затем процесс приостанавливается, ожидая завершения операции ввода-вывода
над первым блоком. Когда выполнение процесса возобновляется, он возвращает
бтуер первомт блокт и не обращает внимание на то, когда завершится операци
ввода-вывода для второго блока. После завершения этой операции контроллер
диска преры
Дальше
Используются технологии
uCoz