Файл: Debian Таненбаум Бос.pdf

1106  

 Глава 12. Разработка операционных систем 

всех встроенных системах работает только ограниченный набор программ, известных 
заранее, можно запретить оптимизацию в универсальных системах.

Расширяемые операционные системы (например, Paramecium и Exokernel) оказывают-
ся многообещающей идеей для встроенных систем. Их можно сделать легковесными 
или тяжеловесными в зависимости от потребностей конкретного приложения, при 
этом, правда, следует добиваться непротиворечивости между приложениями. Посколь-
ку встроенные системы будут производиться сотнями миллионов, это станет главным 
рынком для операционных систем.

12.7. Краткие выводы

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

Система должна быть хорошо структурированной, для чего может быть использована 
одна из нескольких известных технологий, таких как многоуровневые системы или 
архитектуры «клиент–сервер». Внутренние компоненты должны быть ортогональными 
друг к другу. Кроме того, следует четко отделить политику от механизма. Следует также 
уделить существенное внимание таким вопросам, как выбор между статическими или 
динамическими структурами данных, именование, время связывания, а также порядок 
реализации модулей.

Производительность является важным вопросом, но следует тщательно выбирать спо-
соб оптимизации, чтобы не нарушить структуру операционной системы. Часто имеет 
смысл заниматься оптимизацией по скорости или по занимаемой памяти, кэширова-
нием, подсказками, использовать локальность, а также оптимизировать общий случай.

Создание системы группой из двух-трех человек отличается от разработки большой си-
стемы командой из 300 сотрудников. В последнем случае в успехе или неуспехе проекта 
главную роль играют такие вопросы, как структура команды и управление проектом.

Наконец, операционные системы претерпевают изменения, чтобы подстраиваться 
под новые веяния и отвечать новым вызовам. К ним могут относиться системы на 
основе гипервизоров, многоядерные системы, системы с 64-разрядным адресным 
пространством, мобильные компьютеры с беспроводной связью и встроенные систе-
мы. Несомненно, ближайшие годы будут весьма интересными для проектировщиков 
операционных систем.

Вопросы

1.  Закон Мура описывает явление экспоненциального роста, сходного с ростом 

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

Вопросы  

1107

2.  В листинге 12.1 показаны две парадигмы — алгоритмическая и движимая событи-

ями. Какую парадигму проще всего применить для каждой из следующих типов 
программ:

1) компилятор;

2)  программа редактирования фотографий;

3)  программа составления платежной ведомости.

3.  Иерархические имена файлов всегда начинаются с вершины дерева. Рассмотрим, 

к примеру, имя файла 

/usr/ast/books/mos2/chap-12

, сравнив его с 

chap-12/mos2/

books/ast/usr

. Различие в том, что DNS-имена начинаются с самой нижней части 

дерева и идут вверх. Существует ли какая-либо фундаментальная причина для 
столь разных подходов?

4.  Правило Корбато утверждает, что система должна предоставлять минимальный 

механизм. Далее приводится список вызовов стандарта POSIX, присутствовавших 
и в системе UNIX Version 7. Какие из них являются избыточными, то есть могут 
быть удалены без потери функциональности, так как та же работа может быть 
выполнена при помощи простой комбинации остальных вызовов примерно с той 
же производительностью? Access, alarm, chdir, chmod, chown, chroot, close, creat, dup, 
exec, exit, fcntl, fork, fstat, ioctl, kill, link, lseek, mkdir, mknod, open, pause, pipe, read, stat, 
time, times, umask, unlink, utime, wait и write.

5.  Предположим, что уровни 3 и 4 на рис 12.1 поменялись местами. Как это повлияет 

на конструкцию системы?

6.  В микроядерной системе «клиент–сервер», основанной на микроядре, микроядро 

занимается только передачей сообщений. Могут ли процессы пользователя, несмо-
тря на это, создавать и использовать семафоры? Если да, то как? Если нет, почему?

7.  Аккуратная оптимизация может повысить производительность системных вы-

зовов. Рассмотрим случай, в котором каждые 10 мс выполняется один системный 
вызов. Среднее время вызова составляет 2 мс. Насколько ускорится процесс, за-
нимавший 10 с, если ускорить выполнение системных вызовов в два раза?

8.  Операционные системы часто поддерживают два уровня именования: внешнее 

и внутреннее. В чем различие этих имен в плане:

• длины;

• уникальности;

• иерархии?

9.  Один из способов работы с таблицами, размер которых не известен заранее, заклю-

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

10.  В листинге 12.2 флаг found используется для определения того, был ли найден 

PID. Можно ли не сохранять флаг found в цикле, а просто проверить значение 
переменной p в конце цикла, чтобы определить, был ли найден процесс с данным 
идентификатором?

1108  

 Глава 12. Разработка операционных систем 

11. В листинге 12.3 различия между процессорами x86 и UltraSPARC скрыты при 

помощи условной компиляции. Может ли использоваться тот же метод для того, 
чтобы скрыть различия между компьютером с процессором x86 и жестким диском 
с интерфейсом IDE и компьютером с процессором x86 и жестким диском с интер-
фейсом SCSI? Будет ли это удачной идеей?

12.  Косвенность представляет собой метод увеличения гибкости алгоритма. Есть ли 

у этого метода недостатки, и если да, то какие?

13.  Могут ли у реентерабельных процедур быть статические глобальные переменные? 

Аргументируйте ответ.

14.  Макрос в листинге 12.4, б очевидно является более эффективным, чем процедура 

в листинге 12.4, а. Однако этот макрос труден для восприятия. Есть ли у него 
другие недостатки? Если да, то какие?

15.  Допустим, нам нужен способ определить, является ли количество битов в 32-раз-

рядном слове четным или нечетным. Разработайте алгоритм, позволяющий 
определять это как можно быстрее. При необходимости можете использовать для 
таблиц до 256 Кбайт ОЗУ. Напишите макрос, выполняющий данный алгоритм. 

Дополнительное задание

: напишите процедуру, вычисляющую то же значение, 

перебирая 32 бита в цикле. Измерьте, во сколько раз макрос быстрее процедуры.

16.  На рис. 12.3 показано, как файлы формата GIF используют 8-разрядные значе-

ния индексов в палитре цветов. Ту же идею можно использовать с 16-разрядной 
палитрой цветов. При каких обстоятельствах, если таковые вообще существуют, 
использование 24-разрядной палитры цветов может быть удачной идеей?

17.  Один из недостатков формата GIF состоит в том, что изображение должно содер-

жать палитру цветов, увеличивающую размер файла. При каком минимальном 
размере файла использование 8-разрядной палитры цветов не увеличит размеры 
файла? А для 16-разрядной палитры цветов?

18. В тексте было показано, как кэширование путей к файлам может существенно 

ускорить поиск файлов по имени. Другой иногда применяемый метод заключается 
в использовании демона, открывающего все файлы корневого каталога и постоян-
но хранящего их в открытом состоянии, чтобы их i-узлы постоянно присутствова-
ли в памяти. Ускоряет ли данный метод поиск файлов по имени?

19.  Даже если удаленный файл не был удален с того момента, когда была записана 

подсказка, он мог быть изменен с момента последнего доступа к нему. Какую еще 
информацию было бы полезно записывать?

20.  Рассмотрим систему, накапливающую ссылки к удаленным файлам в виде подска-

зок, например, в формате (имя, удаленный хост, удаленное имя). Может случиться 
так, что файл будет удален, а затем заменен другим файлом. При этом подсказка 
может указывать на неверный файл. Как можно снизить вероятность появления 
этой проблемы?

21.  В тексте указывалось, что локальность часто можно использовать для увеличения 

производительности. Но рассмотрим случай, в котором программа читает входные 
данные из одного источника и постоянно выводит данные в один или несколько 
файлов. Может ли попытка использования локальности в файловой системе при-
вести в данном случае к снижению производительности? Есть ли способ борьбы 
с этим?

Вопросы  

1109

22.  Фред Брукс заявляет, что программист может написать за год всего 1000 строк 

отлаженного кода, однако первая версия системы MINIX (13 000 строк кода) 
была создана одним человеком менее чем за три года. Как вы объясните это не-
соответствие?

23.  Основываясь на формуле Брукса о 1000 строк кода на программиста в год, оцените 

количество денежных средств, потраченных на создание операционной системы 
Windows 8. Предположим, что программист обходится компании в 100 000 долла-
ров в год (включая такие накладные расходы, как компьютеры, офисное простран-
ство, секретарская поддержка и руководство). Правдоподобный ли получился 
ответ? Если нет, то какое из предположений могло быть неверно?

24.  Память компьютеров становится все дешевле и дешевле, и уже можно представить 

себе компьютер с большой памятью, питающейся от батарей, вместо жесткого дис-
ка. При текущих ценах сколько может стоить такой персональный компьютер? 
Предположим, что для самой дешевой машины достаточно 100-гигабайтного 
RAM-диска. Будет ли такая машина конкурентоспособной на рынке?

25.  Назовите несколько особенностей обычной операционной системы, которые не 

нужны во встроенной системе, используемой внутри прибора.

26.  Напишите на языке С процедуру, складывающую два заданных параметра с двой-

ной точностью. Напишите процедуру, используя условную компиляцию, таким 
образом, чтобы эта процедура работала как на 16-разрядных, так и на 32-разрядных 
компьютерах.

27.  Напишите программу, помещающую случайно сформированные короткие строки 

в массив, а затем находящую заданную строку в массиве при помощи:

•  простого линейного поиска (метод грубой силы);

•  более сложного метода по вашему выбору. 

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

28. Напишите 

программу, моделирующую находящуюся в памяти файловую систему.

Гл а в а   13

.

Библиография

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

Помимо этих списков литературы стоит обратить внимание на симпозиумы, ор-
ганизуемые ACM по нечетным годам (Symposium on Operating Systems Principles 
(SOSP)) и USENIX — по четным годам (Symposium on Operating Systems Design 
and Implementation (OSDI)). Еще одним источником высококачественной информа-
ции могут стать ежегодные конференции Eurosys. Можно обратить внимание на ACM 
Transactions on Computer Systems и ACM SIGOPS Operating Systems Review — журналы, 
в которых довольно часто появляются статьи по этой тематике. Кроме того, ACM, IEEE 
и USENIX проводят много конференций по более узкой тематике.

13.1. Дополнительная литература

В этом разделе будут даны некоторые рекомендации для дальнейшего чтения. Эти 
ссылки в значительной степени представляют собой ознакомительную или учебную 
литературу и могут использоваться для освещения материала, представленного в дан-
ной книге, с иной точки зрения или с иными акцентами.

13.1.1. Введение и общие труды

1.  Silberschatz et al., Operating System Concepts, 9th ed.

Общее руководство по операционным системам. В нем обсуждаются процессы, 
вопросы управления памятью, управление хранением данных, распределенные 
системы и защита. Рассматриваются два конкретных примера: Linux и Windows 7. 
Вся обложка покрыта рисунками динозавров. Изображения древних животных 
должны подчеркивать, что в операционные системы заложены весьма древние 
решения.

2. Stallings, Operating Systems, 7th ed.

Еще один учебник по операционным системам. В нем описываются все традицион-
ные темы, а также включено небольшое количество материала по распределенным 
системам.

3. Stevens, Advanced Programming in the UNIX Environment.

Эта книга сообщает, как написать программы на языке C, использующие интер-
фейс системных вызовов UNIX и стандартную библиотеку C. Примеры основаны