Добавлен: 29.10.2018
Просмотров: 48128
Скачиваний: 190
376
Глава 4. Файловые системы
16. Рассмотрим i-узел, показанный на рис. 4.10. Каков может быть максимальный
размер файла, если этот узел содержит 10 прямых адресов по 8 байтов каждый,
а все дисковые блоки имеют размер 1024 Кбайт?
17. Записи студентов для заданного класса хранятся в файле. Доступ к записям и их
обновление происходят в произвольном порядке. Предположим, что запись каждо-
го студента имеет фиксированный размер. Какая из трех схем размещения (непре-
рывная, связанная или табличная индексированная) будет наиболее подходящей?
18. Представьте себе файл, чей размер варьируется за время его существования между
4 Кбайт и 4 Мбайт. Какая из трех схем размещения (непрерывная, связанная или
табличная индексированная) будет для него наиболее подходящей?
19. Поступило предложение для увеличения эффективности использования и эко-
номии дискового пространства хранить данные коротких файлов прямо в i-узлах.
Сколько байтов данных может храниться в i-узле, показанном на рис. 4.10?
20. Две изучающие информатику студентки, Кэролин и Элинор, обсуждают i-узлы.
Кэролин утверждает, что оперативная память стала настолько большой по объему
и настолько дешевой, что при открытии файла проще и быстрее считать новую
копию i-узла в таблицу i-узлов, чем искать этот i-узел по всей таблице. Элинор не
согласна. Кто из них прав?
21. Назовите одно преимущество жестких связей над символическими ссылками
и одно преимущество символических ссылок над жесткими связями.
22. Объясните, чем жесткие ссылки отличаются от символьных ссылок в соответствии
с распределениями i-узлов.
23. Возьмем диск объемом 4 Тбайт, который использует блоки размером 4 Кбайт
и метод списка свободных блоков. Сколько адресов блоков может храниться
в одном блоке?
24. Учет свободного дискового пространства может осуществляться с помощью свя-
занных списков или битовых массивов. Дисковые адреса состоят из D бит. При
каком условии для диска из B блоков, F из которых свободны, список свободных
блоков займет меньше места, чем битовый массив? Выразите ваш ответ в процен-
тах от дискового пространства, которое должно быть свободным, для D = 16 бит.
25. После
первого форматирования дискового раздела начало битового массива учета
свободных блоков выглядит так: 1000 0000 0000 0000 (первый блок используется
для корневого каталога). Система всегда ищет свободные блоки от начала раздела,
поэтому после записи файла A, занимающего 6 блоков, битовый массив принимает
следующий вид: 1111 1110 0000 0000. Покажите, как будет выглядеть битовый
массив после каждого из следующих действий:
а) записи файла B размером 5 блоков;
б) удаления файла A;
в) записи файла C размером 8 блоков;
г) удаления файла B.
26. Что произойдет, если битовый массив или список свободных блоков окажется
полностью потерян в результате сбоя? Есть ли способ восстановления системы
после такого сбоя или с диском можно уже попрощаться? Дайте ответ отдельно
для файловых систем UNIX и FAT-16.
Вопросы
377
27. Ночная работа Оливера «Совы» в университете состоит в смене лент, используе-
мых для архивации данных. Ожидая окончания записи на каждую ленту, Оливер
пишет статью, в которой доказывает, что пьесы Шекспира были созданы инопла-
нетными пришельцами. За неимением ничего другого его текстовый процессор
работает прямо в архивируемой системе. Возникают ли проблемы, связанные
с этими обстоятельствами?
28. В этой главе рассматривались некоторые аспекты инкрементного архивирования.
В системе Windows вопрос о том, нужно ли архивировать файл, решить довольно
просто, поскольку у каждого файла есть специальный архивный бит. А вот в систе-
ме UNIX такого бита нет. Как программа архивации в системе UNIX определяет,
для какого файла следует создать резервную копию?
29. Допустим, что файл 21 на рис. 4.22 не изменялся со времени последней архивации.
Как при этом изменятся четыре битовых массива на рис. 4.23?
30. Было
внесено предложение, чтобы первая часть каждого файла в UNIX хранилась
в том же дисковом блоке, что и его i-узел. В чем польза этого предложения?
31. Посмотрите на рис. 4.23. Может ли быть такое, чтобы для какого-то конкретного
номера блока счетчики в обоих списках имели значение 2? Как избавиться от этой
проблемы?
32. Производительность файловой системы зависит от степени удачных обращений
к кэшу (доли блоков, найденных в кэше). Если на удовлетворение запроса к кэшу
уходит 1 мс, а на удовлетворение запроса к диску, если потребуется чтение с дис-
ка, — 40 мс, выведите формулу для вычисления среднего времени удовлетворения
запроса, если степень удачных обращений равна h. Нарисуйте график этой функ-
ции для значений h от 0 до 1,0.
33. Что больше подойдет для внешнего жесткого USB-диска, подключенного к ком-
пьютеру, — кэш со сквозной записью или блочное кэширование?
34. Рассмотрим приложение, в котором записи студентов сохраняются в файле. При-
ложение получает в качестве ввода идентификатор студента, а затем последова-
тельно проводит чтение, обновление и запись соответствующей записи студента,
и все это повторяется до завершения работы приложения. Пригодится ли здесь
технология опережающего чтения блока?
35. Предположим, что имеется диск, у которого есть 10 блоков данных, начиная с бло-
ка 14 и заканчивая блоком 23. Пускай на диске будет два файла, f1 и f2. В структуре
каталога показано, что первыми блоками данных f1 и f2 являются соответственно
22 и 16. Используя показанные далее записи таблицы FAT, покажите, какие блоки
данных выделены f1 и f2.
(14,18); (15,17); (16,23); (17,21); (18,20); (19,15); (20, −1); (21, −1); (22,19);
(23,14).
Показанная выше система записи (x,y) означает, что значение, сохраненное в запи-
си таблицы x, указывает на блок данных y.
36. Воспользуйтесь графиком на рис. 4.17 применительно к диску, имеющему среднее
время поиска цилиндра 6 мс, скорость вращения диска 15 000 об/мин и дорожки
по 1 048 576 байт. Чему равна скорость передачи данных для блоков, имеющих
размер 1, 2 и 4 Кбайт?
378
Глава 4. Файловые системы
37. Некая файловая система использует 4-килобайтные дисковые блоки. Средний раз-
мер файлов составляет 1 Кбайт. Если бы все файлы имели размер 1 Кбайт, какая
часть диска терялась бы понапрасну? Как вы думаете, потери в реальной системе
выше этого числа или ниже? Обоснуйте ответ.
38. Какой самый большой размер файла (в байтах) может быть доступен с исполь-
зованием 10 прямых адресов и одного косвенного блока, если размер дискового
блока составляет 4 Кбайт, а значение адреса указателя блока составляет 4 байта?
39. В системе MS-DOS файлам приходится бороться за место в таблице FAT-16,
хранящейся в оперативной памяти. Если один файл использует k элементов, то
существуют k элементов, недоступных никаким другим файлам. Какие ограниче-
ния это накладывает на общую длину всех остальных файлов?
40. Файловая система UNIX имеет блоки размером 4 Кбайт и 4-байтовые дисковые
адреса. Чему равен максимальный размер файла, если i-узлы содержат 10 прямых
адресов и по одному из адресов однократного, двукратного и трехкратного кос-
венных блоков?
41. Сколько понадобится дисковых операций для считывания i-узла файла
/usr/ast/
courses/os/handout.t
? Предположим, что кроме i-узла корневого каталога в опе-
ративной памяти больше нет ничего относящегося к этому пути. Предположим
также, что все каталоги занимают по одному дисковому блоку.
42. Во многих версиях системы UNIX i-узлы хранятся в начале диска. Альтернатив-
ный вариант предусматривает выделение i-узла при создании файла и помещение
его в начале первого блока файла. Приведите все аргументы за и против альтер-
нативного варианта.
43. Напишите программу, меняющую порядок байтов в файле на обратный так, чтобы
последний байт стал первым, а первый — последним. Программа должна работать
с файлами произвольной длины, но постарайтесь добиться от нее эффективной
работы.
44. Напишите программу, которая начинает работу в заданном каталоге и спускается
по дереву каталогов, записывая размеры всех найденных ею файлов. Когда про-
грамма выполнит эту задачу, она должна вывести на печать гистограмму размеров
файлов, используя в качестве параметра шаг столбца (например, при шаге 1024
файлы размером от 0 до 1023 попадают в один столбец, от 1024 до 2047 — в другой
столбец и т. д.).
45. Напишите программу, сканирующую все каталоги файловой системы UNIX, оты-
скивающую и определяющую местонахождение всех i-узлов с двумя и более жест-
кими связями. Для каждого файла, фигурирующего в жестких связях, программа
должна собрать в единый список все имена файлов, указывающих на этот файл.
46. Напишите новую версию программы ls для системы UNIX. Эта версия должна
принимать в качестве аргумента одно или несколько имен каталогов и для каждого
каталога выдавать список всех файлов, содержащихся в этом каталоге, по одной
строке на файл. Каждое поле должно форматироваться в соответствии с его ти-
пом. Укажите в списке только первый дисковый адрес или не указывайте вообще
никаких адресов.
47. Создайте программу для измерения влияния размеров буфера на уровне при-
ложения на процесс чтения. Эта программа использует запись в большой файл
Вопросы
379
(скажем, размером 2 Гбайт) и чтение из него. Также в ней изменяется размер
буфера приложения (скажем, от 64 байт до 4 Кбайт). Используйте процедуры
измерения времени (например, gettimeofday и getitimer в UNIX), чтобы измерить
время, затрачиваемое при различных размерах буфера. Проанализируйте резуль-
таты и сообщите о своих изысканиях: вносит ли размер буфера разницу в общее
время записи и во время каждой записи?
48. Создайте смоделированную файловую систему, которая полностью помещалась
бы в отдельный обычный файл, сохраненный на диске. В этом дисковом файле
должны содержаться каталоги, i-узлы, информация о свободных блоках, блоки
файловых данных и т. д. Выберите подходящий алгоритм для сохранения ин-
формации о свободных блоках и для размещения блоков данных (непрерывного,
индексированного, связанного). Ваша программа должна воспринимать посту-
пающие от пользователя системные команды на создание и удаление каталогов,
создание, удаление и открытие файлов, чтение выбранного файла и записи его на
диск, а также вывод содержимого каталога.
Гл а в а 5
.
Ввод и вывод информации
Кроме предоставления таких абстракций, как процессы, адресные пространства и фай-
лы, операционная система также управляет всеми устройствами ввода-вывода, подклю-
ченными к компьютеру. Она должна выдавать команды устройствам, перехватывать
прерывания и обрабатывать ошибки. Также она должна предоставить простой и легкий
в использовании интерфейс между устройствами и всей остальной системой. По мере
возможности интерфейс должен быть единообразным для всех устройств (независи-
мым от конкретного устройства). Код подсистемы ввода-вывода представляет собой
существенную часть всей операционной системы. Эта глава посвящена тому, как опе-
рационная система управляет устройствами и процессом ввода-вывода.
Структура главы следующая. Сначала будут рассмотрены некоторые основы аппара-
туры ввода-вывода, а затем в общих чертах — программное обеспечение ввода-вывода.
Программное обеспечение ввода-вывода может быть систематизировано по уровням,
у каждого из которых есть вполне определенная задача. Изучение этих уровней по-
зволит составить представление о том, что на них делается и как они согласуются друг
с другом. Затем будут подробно рассмотрены некоторые устройства ввода-вывода:
диски, часы, клавиатуры и дисплеи. Применительно к каждому устройству пойдет раз-
говор о его аппаратной и программной составляющих. В конце главы будет затронут
вопрос управления энергопотреблением.
5.1. Основы аппаратного обеспечения
ввода-вывода
У разных специалистов свой взгляд на оборудование ввода-вывода. Инженеры-
электронщики обращают внимание на микросхемы, провода, блоки питания, дви-
гатели и все остальные физические компоненты, из которых состоит оборудование.
Программисты обращают внимание на предоставляемый программный интерфейс —
команды, воспринимаемые оборудованием, выполняемые им функции и ошибки,
о которых оно может сообщить. В этой книге нас интересует программирование
устройств ввода-вывода, а не их конструкция, создание или обслуживание, поэтому
мы ограничимся вопросом программирования оборудования, а не его внутренней
работой. Тем не менее программирование многих устройств ввода-вывода зачастую
тесно соприкасается с их внутренним функционированием. В следующих трех раз-
делах будет предоставлено небольшое изложение основ аппаратуры ввода-вывода
в части, касающейся программирования. Этот материал можно рассматривать в каче-
стве обзорного и как расширение вводного материала из раздела «Обзор аппаратного
обеспечения компьютера» главы 1.