Чтение онлайн

на главную - закладки

Жанры

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

3.7 УПРАЖНЕНИЯ

1. Рассмотрим функцию хеширования применительно к Рисунку 3.3. Наилучшей функцией хеширования является та, которая единым образом распределяет блоки между хеш-очередями. Что Вы могли бы предложить в качестве оптимальной функции хеширования? Должна ли эта функция в своих расчетах использовать логический номер устройства?

2. В алгоритме getblk, если ядро удаляет буфер из списка свободных буферов, оно должно повысить приоритет прерывания работы процессора так, чтобы блокировать прерывания до проверки списка. Почему?

*3. В алгоритме getblk ядро должно повысить приоритет прерывания

работы процессора так, чтобы блокировать прерывания до проверки занятости блока. (Это не показано в тексте.) Почему?

4. В алгоритме brelse ядро помещает буфер в «голову» списка свободных буферов, если содержимое буфера неверно. Если содержимое буфера неверно, должен ли буфер появиться в хеш-очереди?

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

*6. Если несколько процессов оспаривают буфер, ядро гарантирует, что ни один из них не приостановится навсегда, но не гарантирует, что процесс не «зависнет» и дождется получения буфера. Переделайте алгоритм getblk так, чтобы процессу было в конечном итоге гарантировано получение буфера.

7. Переделайте алгоритмы getblk и brelse так, чтобы ядро следовало не схеме замещения буферов, к которым наиболее долго не было обращений, а схеме «первым пришел — первым вышел». Повторите то же самое со схемой замещения редко используемых буферов.

8. Опишите ситуацию в алгоритме bread, когда информация в буфере уже верна.

*9. Опишите различные ситуации, встречающиеся в алгоритме breada. Что произойдет в случае следующего выполнения алгоритма bread или breada, когда текущий блок прочитан с продвижением? В алгоритме breada, если первый или второй блок отсутствует в кеше, в дальнейшем при проверке правильности содержимого буфера предполагается, что блок мог быть в буферном пуле. Как это может быть?

10. Опишите алгоритм, запрашивающий и получающий любой свободный буфер из буферного пула. Сравните этот алгоритм с getblk.

11. В различных системных операциях, таких как umount и sync (глава 5), требуется, чтобы ядро перекачивало на диск содержимое всех буферов, которые помечены для «отложенной записи» в данной файловой системе. Опишите алгоритм, реализующий перекачку буферов. Что произойдет с очередностью расположения буферов в списке свободных буферов в результате этой операции? Как ядро может гарантировать, что ни один другой процесс не подберется к буферу с пометкой «отложенная запись» и не сможет переписать его содержимое в файловую систему, пока процесс перекачки приостановлен в ожидании завершения операции ввода-вывода?

12. Определим время реакции системы как среднее время выполнения системного вызова. Определим пропускную способность системы как количество процессов, которые система может выполнять в данный период времени. Объясните, как буферный кеш может способствовать повышению реакции системы. Способствует ли он с неизбежностью увеличению пропускной способности системы?

ГЛАВА 4. ВНУТРЕННЕЕ ПРЕДСТАВЛЕНИЕ ФАЙЛОВ

Как уже было замечено в главе 2, каждый файл в системе UNIX имеет уникальный индекс. Индекс содержит информацию, необходимую любому процессу для того, чтобы обратиться к файлу, например, права собственности на файл, права доступа к файлу, размер файла и расположение данных файла в файловой системе. Процессы обращаются к файлам, используя четко определенный набор системных вызовов и идентифицируя файл строкой символов, выступающих в качестве составного имени файла. Каждое составное имя однозначно определяет файл, благодаря чему ядро системы преобразует это имя в индекс файла.

Эта глава посвящена описанию внутренней структуры файлов в операционной системе UNIX, в следующей же главе рассматриваются обращения к операционной системе, связанные с обработкой файлов. Раздел 4.1 касается индекса и работы с ним ядра, раздел 4.2 — внутренней структуры обычных файлов и некоторых моментов, связанных с чтением и записью ядром информации файлов. В разделе 4.3 исследуется строение каталогов — структур данных, позволяющих ядру организовывать файловую систему в виде иерархии файлов, раздел 4.4 содержит алгоритм преобразования имен пользовательских файлов в индексы. В разделе 4.5 дается структура суперблока, а в разделах 4.6 и 4.7 представлены алгоритмы назначения файлам дисковых индексов и дисковых блоков. Наконец, в разделе 4.8 идет речь о других типах файлов в системе, а именно о каналах и файлах устройств.

Алгоритмы, описанные в этой главе, уровнем выше по сравнению с алгоритмами управления буферным кешем, рассмотренными в предыдущей главе (Рисунок 4.1). Алгоритм iget возвращает последний из идентифицированных индексов с возможностью считывания его с диска, используя буферный кеш, а алгоритм iput освобождает индекс. Алгоритм bmap устанавливает параметры ядра, связанные с обращением к файлу. Алгоритм namei преобразует составное имя пользовательского файла в имя индекса, используя алгоритмы iget, iput и bmap. Алгоритмы alloc и free выделяют и освобождают дисковые блоки для файлов, алгоритмы ialloc и ifree назначают и освобождают для файлов индексы.

Алгоритмы работы с файловой системой на нижнем уровне
namei alloc free ialloc ifree
iget iput bmap
алгоритмы работы с буферами
getblk brelse bread breada bwrite

Рисунок 4.1. Алгоритмы файловой системы

4.1 ИНДЕКСЫ

4.1.1 Определение

Индексы существуют на диске в статической форме и ядро считывает их в память прежде, чем начать с ними работать. Дисковые индексы включают в себя следующие поля:

• Идентификатор владельца файла. Права собственности разделены между индивидуальным владельцем и «групповым» и тем самым помогают определить круг пользователей, имеющих права доступа к файлу. Суперпользователь имеет право доступа ко всем файлам в системе.

• Тип файла. Файл может быть файлом обычного типа, каталогом, специальным файлом, соответствующим устройствам ввода-вывода символами или блоками, а также абстрактным файлом канала (организующим обслуживание запросов в порядке поступления, «первым пришел — первым вышел»).

Поделиться:
Популярные книги

Архил…? Книга 3

Кожевников Павел
3. Архил...?
Фантастика:
фэнтези
попаданцы
альтернативная история
7.00
рейтинг книги
Архил…? Книга 3

Сила рода. Том 3

Вяч Павел
2. Претендент
Фантастика:
фэнтези
боевая фантастика
6.17
рейтинг книги
Сила рода. Том 3

Прометей: владыка моря

Рави Ивар
5. Прометей
Фантастика:
фэнтези
5.97
рейтинг книги
Прометей: владыка моря

Гром над Академией. Часть 1

Машуков Тимур
2. Гром над миром
Фантастика:
фэнтези
боевая фантастика
5.25
рейтинг книги
Гром над Академией. Часть 1

Хозяйка дома на холме

Скор Элен
1. Хозяйка своей судьбы
Любовные романы:
любовно-фантастические романы
5.00
рейтинг книги
Хозяйка дома на холме

Газлайтер. Том 10

Володин Григорий
10. История Телепата
Фантастика:
боевая фантастика
5.00
рейтинг книги
Газлайтер. Том 10

Последний Паладин

Саваровский Роман
1. Путь Паладина
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Последний Паладин

Мастер 6

Чащин Валерий
6. Мастер
Фантастика:
боевая фантастика
попаданцы
аниме
5.00
рейтинг книги
Мастер 6

Столичный доктор. Том III

Вязовский Алексей
3. Столичный доктор
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Столичный доктор. Том III

Наследник и новый Новосиб

Тарс Элиан
7. Десять Принцев Российской Империи
Фантастика:
городское фэнтези
попаданцы
аниме
5.00
рейтинг книги
Наследник и новый Новосиб

Вперед в прошлое 5

Ратманов Денис
5. Вперед в прошлое
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Вперед в прошлое 5

Последняя Арена 10

Греков Сергей
10. Последняя Арена
Фантастика:
боевая фантастика
рпг
5.00
рейтинг книги
Последняя Арена 10

Релокант

Ascold Flow
1. Релокант в другой мир
Фантастика:
фэнтези
попаданцы
рпг
5.00
рейтинг книги
Релокант

Совок-8

Агарев Вадим
8. Совок
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Совок-8