Реферат: Разработка операционных систем

Отделениетехники и технологий

РЕФЕРАТ

На тему

«Разработкаоперационных систем»

Содержание

Введение

1. Разработка интерфейса

2. Руководящие принципы

3. Парадигмы

1) Парадигмы интерфейсапользователя

2) Парадигмыпользователя

3) Парадигмы данных

4. Интерфейс системных вызовов

5. Реализация.

6. Структура системы

7. Многоуровневые системы

8. Экзоядра

9. Системы клиент-сервер

10. Расширяемые системы

11. Потоки ядра

12. Механизм и политика

13. Ортогональность

14. Время связывания

15. Реализация системы сверху вниз иснизу вверх

16. Полезные методы

17. Скрытие аппаратур

18. Косвенность

19. Повторное использование

20. Рентабельность

21. Метод грубой силы

22. Проверка на ошибки

23. Производительность

24. Кэширование

25. Подсказки

26. Использование локальности

27. Оптимизируйте общий случай

28. Управление проектом

29. Мифический человеко-месяц

30. Роль опыта

31. Тенденции и проектирование ОС

32. ОС с большим адреснымпространством

33. Сеть

34. Параллельные и распределенныесистемы

35. Мультимедиа

Заключение

Введение

В среде разработчиковоперационных систем ходит множество изустных преданий о том, что такое хорошо ичто такое плохо, однако на удивление малое количество из этих историй записано.Наиболее важной книгой можно назвать классический труд Фреда Брукса, в которомавтор делится своим опытом проектирования и реализации операционной системы IBMOS/360. Материал выпущенного к 20-летней годовщине издания был пересмотрен, ктому же в содержание книги было включено несколько новых глав. Вероятно,единственной книгой по операционным системам, в которой серьезно обсуждаетсятема проектирования.

Тремя классическимитрудами по проектированию операционных систем являются как и книги Брукса, этитри статьи успешно пережили время, прошедшее с момента их написания. Большаячасть рассматриваемых в них вопросов сохранила свою актуальность и в наши дни.

Данная глава основана насодержимом этих источников, кроме того, в ней используется личный опыт участияавтора в проектировании трех систем: Amoeba, MINIX и Globe. Поскольку средиразработчиков операционных систем нет единого мнения по вопросу о том, каклучше всего проектировать операционные системы, эта глава будет носить болееличный характер, более умозрительный и, несомненно, более противоречивый, чемпредыдущие главы.

Природа проблемыпроектирования

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

Цели.

Чтобы проект операционнойсистемы был успешным, разработчики должны иметь четкое представление о том,чего они хотят. При отсутствии цели очень трудно принимать последующие решения.Чтобы этот вопрос стал понятнее, полезно взглянуть на два языкапрограммирования, PL/I и С++. Язык PL/I был разработан корпорацией IBM в 60-егоды, так как поддерживать одновременно FORTRAN и COBOL и слушать при этом заспиной ворчание ученых о том, что Algol лучше, чем FORTRAN и COBOL вместевзятые, было невыносимо. Поэтому был создан комитет для создания нового языка,удовлетворяющего запросам всех программистов: PL/I. Этот язык обладалнекоторыми чертами языка FORTRAN, некоторыми особенностями языка COBOL инекоторыми свойствами языка Algol. Проект потерпел неудачу, потому что емунедоставало единой концепции. Проект представлял собой лишь набор свойств,конфликтующих друг с другом, к тому же язык PL/I был слишком громоздким инеуклюжим, чтобы программы на нем можно было эффективно компилировать.

Теперь взглянем на языкС++. Он был спроектирован всего одним человеком (Деннисом Ритчи) дляединственной цели (системного программирования). Успех его был колоссален, иэто не в последнюю очередь объяснялось тем, что Ритчи знал, чего хотел и чегоне хотел. В результате спустя десятилетия после своего появления этот язык всееще широко распространен. Наличие четкого представления о своих целях являетсярешающим.

Чего же хотятразработчики операционных систем? Очевидно, ответ варьируется от системы ксистеме и будет разным для встроенных систем и серверных систем

Для универсальныхоперационных систем основными являются следующие четыре пункта:

1. Определениеабстракций.

2. Предоставлениепримитивных операций.

3. Обеспечение изоляции.

4. Управлениеаппаратурой.

Ниже будет рассмотренкаждый из этих пунктов.

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

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

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

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

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

Почему так сложноспроектировать операционную систему?

Закон Мура гласит, чтоаппаратное обеспечение компьютера увеличивает свою производительность в 100 разкаждые десять лет. Никто, к сожалению, так и не сформулировал ничего подобногодля программного обеспечения. Никто и не говорит, что операционные системывообще совершенствуются с годами. В самом деле, можно утверждать, что некоторыеиз них даже стали хуже в определенных аспектах (таких как надежность), чем,например, операционная система UNIX Version 7 образца 70-х годов.

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

Во-первых, операционныесистемы стали крайне громоздкими программами. Никто в одиночку не может, засевза персональный компьютер на несколько месяцев, написать операционную систему.Все современные версии UNIX превосходят1 млн строк исходного текста. Операционная система Windows 2000 состоит из 29 млн строк кода. Ни один человек наЗемле не способен понять даже одного миллиона строк, не говоря уже о 29миллионах. Если вы создаете продукт, который ни один из разработчиков не можетдаже надеяться понять целиком, не удивительно, что результаты часто оказываютсядалеки от оптимальных.

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

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

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

В-шестых, у разработчиковоперационной системы на самом деле нет четкого представления о том, как будетиспользоваться их система, поэтому они должны обеспечить достаточную степеньуниверсальности. При проектировании таких систем, как UNIX или Windows2000, не предполагалось их использование для работы с электронной почтой илизапуск web-браузера под их управлением, однакомногие современные компьютеры в основном только для этого и используются.Трудно себе представить проектировщика морского судна, который не знал бы, чтоон проектирует: рыболовецкое судно, пассажирское судно или военный корабль.

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

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

Разработка интерфейса

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

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

Руководящие принципы

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

Принцип 1. Простота.

Простой интерфейс легчепонять и реализовать без ошибок. Всем разработчикам систем следует помнить этузнаменитую цитату французского летчика и писателя Антуана де Сент-Экзюпери:

Совершенство достигаетсяне тогда, когда уже больше нечего добавить, а когда больше нечего убавить. Этотпринцип утверждает, что лучше меньше, чем больше, по крайней мере,применительно к операционным системам. Другими словами, этот принцип может бытьвыражен следующей аббревиатурой, предлагающей программисту, в чьих мыслительныхспособностях возникают сомнения, не усложнять систему: KISS (Keep It Simple,Stupid).

Принцип 2. Полнота.

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

Другими словами,операционная система должна выполнять то, что от нее требуется, но не болеетого. Если пользователю нужно хранить данные, операционная система должнапредоставлять для этого некий механизм. Если пользователям необходимо общатьсядруг с другом, операционная система должна предоставлять механизм общения и т.д. В своей речи по поводу получения награды Turing Award один из разработчиковсистем CTSS и MULTICS Фернандо Корбато объединил понятия простоты и полноты исказал:

Во-первых, важноподчеркнуть значение простоты и элегантности, так как сложность приводит кнагромождению противоречий и, как мы уже видели, появлению ошибок. Я быопределил элегантность как достижение заданной функциональности при помощиминимума механизма и максимума ясности. Если какая-либо функция (или системныйвызов) не может быть реализована эффективно, вероятно, ее не следуетреализовывать. Программист должен интуитивно представлять стоимость реализациии использования каждого системного вызова. Например, программисты, пишущиепрограммы в системе UNIX, считают, что системный вызов 1 seek дешевлесистемного вызова read, так как первый системный вызов просто изменяетсодержимое указателя, хранящегося в памяти, тогда как второй системный вызоввыполняет операцию дискового ввода-вывода. Если интуиция подводит программиста,программист создает неэффективные программы.

Парадигмы

Когда цели установлены,можно начинать проектирование. Можно начать, например, со следующего: подумать,как будет представать система перед пользователями. Один из наиболее важныхвопросов заключается в том, чтобы все функции системы хорошо согласовывалисьдруг с другом и обладали тем, что часто называют архитектурнойсогласованностью. При этом важно различать два типа «пользователей»операционной системы. С одной стороны, существуют пользователи,взаимодействующие с прикладными программами; с другой стороны, естьпрограммисты, пишущие эти прикладные программы. Первые большей частью имеютдело с графическим интерфейсом пользователя, тогда как последние в основномвзаимодействуют с интерфейсом системных вызовов. Если задача заключается в том,чтобы иметь единый графический интерфейс пользователя, заполняющий всю систему,как, например, в системе Macintosh, тогда разработку следует начать отсюда.Если же цель состоит в том, чтобы обеспечить поддержку различных возможныхграфических интерфейсов пользователя, как в системе UNIX, тогда в первуюочередь должен быть разработан интерфейс системных вызовов. Начало разработкисистемы с графического интерфейса пользователя представляет собой, по сути,проектирование сверху вниз. Вопрос заключается в том, какие функции будет этотинтерфейс иметь, как будет пользователь с ними взаимодействовать и как следуетспроектировать систему для их поддержки. Например, если большинство программотображает на экране значки, а затем ждет, когда пользователь щелкнет на нихмышью, это предполагает использование управляемой событиями модели дляграфического интерфейса пользователя и, возможно, для операционной системы. Сдругой стороны, если экран в основном заполнен текстовыми окнами, тогда,вероятно, лучшей представляется модель, в которой процессы считывают символы склавиатуры.

Реализация в первуюочередь интерфейса системных вызовов представляет собой проектирование снизувверх. Здесь вопросы заключаются в том, какие функции нужны программистам. Вдействительности для поддержки графического интерфейса пользователя требуетсяне так уж много специальных функций. Например, оконная система под названием XWindows, используемая в UNIX, представляет собой просто большую программу наязыке С, которая обращается к клавиатуре, мыши и экрану с системными вызовамиread и write. Оконная система X Windows была разработана значительно позжеоперационной системы UNIX, но для ее работы не потребовалось большогоколичества изменений в операционной системе. Это подтверждает тот факт, чтосистема UNIX обладает полнотой в достаточной степени.

Парадигмы интерфейсапользователя.

Как для интерфейса уровняграфического интерфейса пользователя, так и для интерфейса системных вызововнаиболее важный аспект заключается в наличии хорошей парадигмы (иногданазываемой метафорой или модельным представлением), обеспечивающей наглядныйзрительный образ интерфейса Эта парадигма используется в интерфейсе дляобеспечения согласованности таких идиом, как щелчок и двойной щелчок мышью,перетаскивание и т. д. Часто к программам применяются дополнительныетребования, такие как наличие строки меню с пунктами Файл, Правка и т. д.,каждый из которых содержит хорошо знакомые пункты меню. Таким образом,пользователи, знакомые с одной программой, легко могут освоить другуюпрограмму.

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

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

Парадигмы исполнения.

Архитектурнаясогласованность важна на уровне пользователя, но в равной мере она важна науровне интерфейса системных вызовов. Здесь часто полезно различать парадигмуисполнения от парадигмы данных, поэтому мы рассмотрим и ту и другую, начав спервой.

Широкое распространениеполучили две парадигмы: алгоритмическая и движимая событиями. Алгоритмическаяпарадигма основана на идее, что программа запускается для выполнения некоторойфункции, известной заранее или задаваемой в виде параметров. Эта функция можетзаключаться в компиляции программы, составлении ведомости или пилотированиисамолета до Сан-Франциско. Базовая логика жестко прошита в код программы, приэтом программа время от времени обращается к системным вызовам, чтобы получитьввод пользователя, обратиться к системным службам и т. д.

Другая парадигмаисполнения представляет собой парадигму управления событиями (листинг 12.1, б).Здесь программа выполняет определенную инициализацию, например, отображаеткакое-либо окно, а затем ждет, когда операционная система сообщит ей о первомсобытии. Этим событием может быть нажатие клавиши или перемещение мыши. Такаясхема полезна для программ, активно взаимодействующих с пользователем.

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

Парадигмы данных.

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

Первая карта представляласобой инструкцию для оператора. Он должен был достать из шкафа бобину номер 781и установить ее на накопителе 8. Вторая карта являлась командой операционнойсистеме запустить только что откомпилированную с языка FORTRAN программу,отображая INPUT (означающий устройство чтения перфокарт) на логическую ленту 1,дисковый файл MYDATA на логическую ленту 2, принтер OUTPUT на логическую ленту3, перфоратор PUNCH на логическую ленту 4 и физический накопитель на магнитнойленте ТАРЕ08 на логическую ленту 5.

Синтаксис языка FORTRANпозволяет читать и писать логические ленты. При чтении с логической ленты 1программа получает ввод с перфокарт. При помощи записи на логическую ленту 3программа может вывести результаты на принтер. Обращаясь к логической ленте 5,программа может читать и писать магнитную ленту 781 и т. д. Обратите внимание,что идея магнитной ленты представляла собой всего лишь парадигму (модель) дляобъединения устройства чтения перфокарт, принтера, перфоратора, дисковых файлови магнитофонов. В данном примере только логическая лента 5 была физическойлентой. Все остальное представляло собой обычные файлы для подкачки данных. Этобыла примитивная парадигма, но она была шагом в правильном направлении.

Затем появиласьоперационная система UNIX, которая пошла значительно дальше в этом направлении,используя модель «все суть файлы». При использовании этой парадигмы всеустройства ввода-вывода рассматриваются как файлы, которые можно открывать иуправлять ими, как обычными файлами. Операторы на языке С открывают настоящийдисковый файл и терминал пользователя. Последующие операторы могут использоватьдескрипторы файлов fd1 и fd2, чтобы читать из этих файлов и писать в них. Сэтого момента нет разницы между доступом к файлу и доступом к терминалу, несчитая того, что при обращении к терминалу не разрешается операция перемещенияуказателя в файле.

Операционная система UNIXне только объединяет файлы и устройства ввода-вывода, но также позволяетполучать доступ к другим процессам через каналы, как к файлам. Более того, еслиподдерживается отображение файлов на адресное пространство памяти, процессможет обращаться к своей виртуальной памяти так, как если бы это был файл.Наконец, в версиях UNIX, поддерживающих файловую систему /рrос, строка на языкеС позволяет процессу (попытаться) получить доступ к памяти процесса 501 длячтения и записи при помощи дескриптора файла fd3, что может быть полезно,например, при отладке программы.

Операционная системаWindows 2000 идет в использовании этой модели еще дальше, представляя все, чтоесть в системе, в виде объектов. Получив дескриптор файла, процесса, семафора,почтового ящика или другого объекта ядра, процесс может выполнять с этимобъектом различные действия. Эта парадигма является еще более общей, чемиспользуемая в UNIX, и значительно более общей, чем в FORTRAN.

Объединяющие парадигмытакже встречаются в других контекстах. Следует отметить один из них: Всемирнуюпаутину (Web). Используемая в Паутине парадигма состоит в том, что всекиберпространство заполнено документами, у каждого их которых есть свой адрес URL.Обратившись по соответствующему указателю URL (введя его с клавиатуры илищелкнув мышью по ссылке), вы получаете этот документ. В действительности многие«документы» вовсе не являются документами, но формируются программой илисценарием оболочки, когда поступает запрос. Например, когда пользовательзапрашивает в Интернет-магазине список компакт-дисков конкретного исполнителя,документ создается на лету программой. Он совершенно точно не существовал дотого, как был получен запрос.

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

Интерфейс системныхвызовов

Если исходить извысказанного Корбато принципа минимального механизма, тогда операционнаясистема должна предоставлять настолько мало системных вызовов, насколько этовозможно (необходимый минимум), и каждый системный вызов должен быть настолькопрост, насколько это возможно (но не проще). Объединяющая парадигма данныхможет играть главную роль в этом. Например, если файлы, процессы, устройстваввода-вывода и прочее будут выглядеть как файлы или объекты, все они могутчитаться при помощи всего одного системного вызова read. В противном случаепришлось бы иметь различные системные вызовы, такие как read_file, read_proc,read_tty и т. д.

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

exec(name. argp. envp);

Данный системный вызовзагружает исполняемый файл пате и передает ему аргументы, на которые указываетargp, и список переменных окружения, на который указывает envp.

Эти процедуры всего лишьпомещают аргументы в массив, после чего обращаются к системному вызову exec,который и выполняет всю работу. Такая схема является лучшей в обоих смыслах:благодаря единственному простому системному вызову операционная системасохраняет свою простоту, в то же самое время программист получает возможностьобращаться к системному вызову exec различными способами.

Разумеется, пытаясьиспользовать один-единственный системный вызов для всех случаев жизни, легкодойти до крайностей. Для создания процесса в операционной системе UNIXтребуется два системных вызова: fork, за которым следует exec. У первого вызованет параметров; у второго вызова три параметра. Для сравнения: у вызова Win32API для создания процесса, CreateProcess, 10 параметров, один из которыхпредставляет собой указатель на структуру с дополнительными 18 параметрами.Давным-давно следовало задать вопрос: «Произойдет ли катастрофа, если мыопустим что-нибудь из этого?» Правдивый ответ должен был звучать так: «Внекоторых случаях программист будет вынужден совершить больше работы длядостижения определенного эффекта, зато мы получим более простую, компактную инадежную операционную систему». Конечно, человек, предлагающий версию с этими10 + 18 параметрами, мог добавить: «Но пользователи любят все эти возможности».Возразить на это можно было бы так: «Еще больше им нравятся системы, которыеиспользуют мало памяти и никогда не ломаются». Компромисс, заключающийся вбольшей функциональности за счет использования большего объема памяти, покрайне мере, виден невооруженным глазом и ему можно дать оценку (так какстоимость памяти известна). Однако трудно оценить количество дополнительныхсбоев в год, которые появятся благодаря внедрению новой функции. Кроме того,неизвестно, сделали бы пользователи тот же выбор, если им заранее была известнаэта скрытая цена. Этот эффект можно резюмировать первым законом программногообеспечения Таненбаума:

При увеличении размерапрограммы количество содержащихся в ней ошибок также увеличивается.

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

Простота является неединственным принципом, которым следует руководствоваться при разработкесистемных вызовов. Следует также помнить о фразе, сказанной Б. Лэмпсоном в 1984году: Не скрывай мощь.

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

При проектированиисистемы возникает также вопрос использования ориентированных на соединениевызовов или вызовов, не использующих соединений. Стандартные системные вызовыUNIX и Win32 для чтения файлов являются ориентированными на соединение. Сначалавы открываете файл, затем читаете его и, наконец, закрываете файл. Некоторыепротоколы работы с удаленными файлами также являются ориентированными насоединение. Например, чтобы использовать протокол FTP, пользователь сначаларегистрируется на удаленной машине, читает файлы, а затем выходит из системы.

С другой стороны,некоторые протоколы удаленного доступа к файлам не требуют соединений.Например, протокол NFS не требует соединений, как было показано в главе 10.Каждый вызов NFS является независимым, поэтому файлы не открываются до ихчтения или записи, разумеется, файлы не нужно закрывать после чтения илизаписи. Всемирная паутина также не требует соединений: чтобы прочитатьweb-страницу, вы просто запрашиваете ее. Не требуется никаких предварительныхнастроек (TCP-соединение все-таки требуется, но оно представляет собой болеенизкий уровень протокола; протокол HTTP, используемый для доступа к самойweb-странице, не требует соединений).

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

Другой вопрос,возникающий при проектировании интерфейса системных вызовов, заключается в егооткрытости. Список системных вызовов, определяемых стандартом POSIX, легконайти. Эти системные вызовы поддерживаются всеми системами UNIX, как инебольшое количество других вызовов, но полный список всегда публикуется.Корпорация Microsoft, напротив, никогда не публиковала список системных вызововWindows 2000. Вместо этого публикуются функции интерфейса Win32 API, а такжевызовы других интерфейсов; эти списки содержат огромное количество библиотечныхвызовов (более 13 000 в Windows 2000), но только малое их число являетсянастоящими системными вызовами. Аргумент в пользу открытости системных вызововзаключается в том, что программистам становится известна цена использованияфункций. Функции, исполняемые в пространстве пользователя, выполняются быстрее,чем те, которые требуют переключения в режим ядра. Закрытость системных вызововтакже имеет свои преимущества, заключающиеся в том, что в результатедостигается гибкость в реализации библиотечных процедур. То есть разработчикиоперационной системы получают возможность изменять действительные системныевызовы, сохраняя при этом работоспособность прикладных программ.

Реализация

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

Структура системы

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

Многоуровневые системы

Разумный подход,установившийся с годами, заключается в создании многоуровневых систем. СистемаTHE, разработанная Э. Дейкстрой, была первой многоуровневой системой. Уоперационных систем UNIX (см. рис. 10.2) и Windows 2000 также естьмногоуровневая структура, но уровни в них в большей степени представляют собойспособ описания системы, чем фактический руководящий принцип, использованныйпри ее построении.

При создании новойсистемы разработчики должны сначала очень тщательно выбрать уровни и определитьфункциональность каждого уровня. Нижний уровень всегда должен пытаться скрытьсамые неприятные особенности аппаратуры, как это делает уровень HAL. Вероятно,следующий уровень должен обрабатывать прерывания, заниматься переключениемконтекста и работать с блоком управления памятью MMU, так что выше этого уровнякод оказывается в основном машинно-независимым. На еще более высоких уровняхвсе зависит от вкусов и предпочтений разработчиков. Один вариант заключается втом, чтобы уровень 3 управлял потоками, включая планирование и синхронизациюпотоков.При этом, начиная с уровня 4, мы получаем правильные потоки, которыенормально планируются и синхронизируются при помощи стандартного механизма(например, мьютексов).

На уровне 4 мы обнаружимдрайверы устройств, каждый из которых работает как отдельный поток, со своимсостоянием, счетчиком команд, регистрами и т. д., возможно (но не обязательно),в адресном пространстве ядра. Такое устройство может существенно упроститьструктуру ввода-вывода, потому что когда возникает прерывание, оно может бытьпреобразовано в системный вызов unlock на мьютексе и обращение к планировщику,чтобы (потенциально) запустить новый готовый поток, который был блокированмьютексом. Этот подход используется в системе MINIX, но в операционных системахUNIX, Linux и Windows 2000 обработчики прерываний реализованы как независимаячасть системы, а не потоки, которые сами могут управляться планировщиком, приостанавливатьсяи т. д. Поскольку основная сложность любой операционной системы заключается вовводе-выводе, заслуживает внимания любой способ сделать его более удобным дляобработки и более инкапсулированным.

Над уровнем 4, скореевсего, мы обнаружим виртуальную память, одну или несколько файловых систем иобработчики системных вызовов. Если виртуальная память расположена на болеенизком уровне, чем файловые системы, тогда блочный кэш может быть выгружаемым,что позволяет менеджеру виртуальной памяти динамически определять, как следуетраспределять физическую память между страницами пользователей и страницамиядра, включая кэш. Подобным образом работает операционная система Windows 2000.

Экзоядра

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

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

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

Сквозной аргумент можетбыть расширен почти до пределов всей операционной системы. Он утверждает, чтооперационная система не должна делать того, что пользовательская программаможет сделать сама. Например, зачем нужна файловая система? Почему бы непозволить пользователю просто читать и писать участки диска защищеннымспособом? Конечно, большинству пользователей нравится работать с файлами, но,согласно сквозному аргументу, файловая система должна быть библиотечнойпроцедурой, которую можно скомпоновать с любой программой, нуждающейся вфайлах. Этот подход позволяет различным программам использовать различныефайловые системы. Такая цепь рассуждений приводит к выводу, что операционнаясистема должна только обеспечивать безопасное распределение ресурсов (например,процессорного времени или дисков) среди соревнующихся за них пользователей.Экзоядро представляет собой операционную систему, построенную в соответствии сосквозным аргументом [111].

Системы клиент-сервер

Компромиссом междуоперационной системой, которая делает все, и операционной системой, не делающейничего, является операционная система, делающая кое-что. Результатом такогодизайна является схема микроядра, при которой большая часть операционнойсистемы представляет собой серверные процессы, работающие на уровнепользователя (см. рис. 1.23). Такое устройство обладает наибольшей модульностьюи гибкостью по сравнению с другими схемами. Предел гибкости заключается в том,чтобы каждый драйвер устройства также работал в виде пользовательскогопроцесса, полностью защищенного от ядра и других драйверов. Удаление драйверовиз ядра позволяет устранить наибольший источник нестабильности в любойоперационной системе – полные ошибок драйверы, написанные третьими фирмами.

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

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

Такой метод защищаетструктуры данных ядра от изучения и повреждения их драйверами устройств, что(по большей части) хорошо. Возможно создание аналогичного набора вызовов,позволяющим драйверам устройств читать и писать таблицы ядра, но только подконтролем ядра и с его одобрения.

Главная проблема такогоподхода, и проблема микроядер вообще, заключается в снижениипроизводительности, вызываемом дополнительными переключениями контекста. Однакопрактически вся работа по созданию микроядер была выполнена много лет назад,когда центральные процессоры были значительно медленнее. Сегодня не так ужмного приложений, использующих каждую каплю мощности процессора, которые немогут смириться с малейшей потерей производительности. В конце концов, когдаработает текстовый редактор или web-браузер, центральный процессор простаиваетоколо 90 % времени. Если операционная система, основанная на микроядре,превращает систему с процессором, работающем на частоте 900 МГц, в надежнуюсистему, аналогичную по производительности системе с частотой 800 МГц, мало ктоиз пользователей станет жаловаться. Большинство пользователей были простосчастливы всего несколько лет назад, когда приобрели свой предыдущий компьютерс потрясающей тогда частотой процессора в 100 МГц.

Расширяемые системы

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

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

Потоки ядра

Еще один вопрос, имеющийотношение к данной теме, независимо от выбора структурной модели – этосистемные потоки. Иногда бывает удобно позволить существовать потокам ядраотдельно от пользовательских процессов. Эти потоки могут работать в фоновомрежиме, записывая «грязные» страницы на диск, занимаясь свопингом процессов ит. д. На самом деле ядро само может целиком состоять из таких потоков. Когдапользователь обращается к системному вызову, пользовательский поток невыполняется в режиме ядра, а блокируется и передает управление потоку ядра,который принимает управление для выполнения работы.

Помимо потоков ядра,работающих в фоновом режиме, большинство систем также запускают в фоновомрежиме множество процессов-демонов. Хотя они и не являются частью операционнойсистемы, они часто выполняют «системные» функции. Это может быть получение иотправка электронной почты, а также обслуживание различных запросов удаленныхпользователей, как, например, FTP или web-страницы.

Механизм и политика

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

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

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

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

Вторым примером являетсястраничная подкачка. Механизм включает в себя управление блоком MMU, поддержкусписка занятых и свободных страниц, а также программу для перемещения страниц сдиска в память и обратно. Политика в данном случае заключается в принятиирешения о выполняемых действиях при возникновении страничного прерывания.Политика может быть локальной или глобальной, основываться на алгоритме LRU,FIFO или каком-либо другом алгоритме, но она может (и должна) быть полностьюотделена от механики фактической работы со страницами.

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

Ортогональность

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

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

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

Другое применение ортогональности– разделение понятий процесса и потока в Windows 2000. Процесс представляетсобой контейнер для ресурсов, не более и не менее. Поток представляет собойобъект планирования. Когда один процесс получает дескриптор от другогопроцесса, не имеет значения, сколько потоков у него есть. Когда планировщиквыбирает поток, не важно, какому процессу он принадлежит. Эти понятияортогональны.

Наш последний примерортогональности возьмем из операционной системы UNIX. Создание процессапроисходит здесь в два этапа: при помощи системных вызовов fork и exec.Создание нового адресного пространства и заполнение его новым образом памяти вданном случае разделены, что позволяет выполнить определенные действия междуэтими этапами. В операционной системе Windows 2000 эти два этапа нельзяразделить, то есть концепции создания нового адресного пространства и егозаполнения новым образом памяти не являются ортогональными в этой системе.Последовательность системных вызовов clone и exec в системе Linux является ещеболее ортогональной, так как в данном случае возможно еще более детальноеуправление этими действиями. Общее правило может быть сформулировано следующимобразом: наличие небольшого количества ортогональных элементов, которые могуткомбинироваться различными способами, позволяет создать небольшую простую иэлегантную систему.

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

Имена, создаваемые дляиспользования их людьми, представляют собой символьные строки формата ASCII илиUnicode и, как правило, являются иерархическими. Так, иерархия отчетливо виднана примере путей файлов, например, путь /usr/ast/books/mos2/chap-12 состоит изимен каталогов, поиск которых следует начинать в корневом каталоге. Адреса URLтакже являются иерархическими. Например, URL www.cs.vu.nl/~ast/ указывает наопределенную машину (www) определенного факультета (cs) определенногоуниверситета (vu) определенной страны (nl). Участок URL после косой чертыобозначает определенный файл на указанной машине, в данном случае по умолчаниюэто файл www/index.html в домашнем каталоге пользователя ast. Обратитевнимание, что URL (а также адреса DNS вообще, включая адреса электронной почты)пишутся «задом наперед», начинаясь с нижнего уровня дерева, в отличие от именфайлов, начинающихся с вершины дерева. На это можно взглянуть и по-другому,если положить дерево горизонтально. При этом в одном случае дерево будетначинаться слева и расти направо, а в другом случае, наоборот, будет начинатьсясправа и расти влево.

Часто используетсядвухуровневое именование: внешнее и внутреннее. Например, к файлам всегда можнообратиться по имени, представляющему собой символьную строку. Кроме этого,почти всегда существует внутреннее имя, используемое системой. В операционнойсистеме UNIX реальным именем файла является номер его i-узла. Имя в форматеASCII вообще не используется внутри системы. В действительности это имя даже неявляется уникальным, так как на файл может указывать несколько ссылок. А воперационной системе Windows 2000 в качестве внутреннего имени используетсяиндекс файла в таблице MFT. Работа каталога заключается в преобразованиивнешних имен во внутренние.

Во многих случаях (такихкак приведенный выше пример с именем файла) внутреннее имя файла представляетсобой уникальное целое число, служащее индексом в таблице ядра. Другие примерыимен-индексов: дескрипторы файлов в системе UNIX и дескрипторы объектов вWindows 2000. Обратите внимание, что ни у одного из данных примеров имен нетвнешнего представления. Они предназначены исключительно для внутреннегоиспользования системой и работающими процессами. В целом использование длявременных имен табличных индексов, не сохраняющихся после перезагрузки системы,является удачным замыслом.

Время связывания

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

Чтобы внести ясность впонятие времени связывания, давайте рассмотрим некоторые примеры из реальногомира. Примером раннего связывания может быть практика некоторых колледжей,позволяющих родителям зачислять своего ребенка в колледж с момента рождения ивносить плату за его обучение заранее. Когда спустя 18 лет студент приходит вколледж, его обучение уже полностью оплачено, независимо от стоимости обученияна данный момент.

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

Языками программированиячасто поддерживаются различные виды связывания для переменных. Глобальныепеременные связывает с конкретным виртуальным адресом компилятор. Это примерраннего связывания. Локальным переменным процедуры виртуальные адресаназначаются (в стеке) во время выполнения процедуры. Это пример промежуточногосвязывания. Переменным, хранящимся в куче (память для которых выделяется припомощи процедуры malloc в программах на языке С или процедуры new в программахна языке Java), виртуальный адрес назначается только на время их фактическогоиспользования. Это пример позднего связывания.

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

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

Разработчики операционныхсистем постоянно вынуждены выбирать между статическими и динамическимиструктурами данных. Статические структуры всегда проще для понимания, легче дляпрограммирования и быстрее в использовании. Динамические структуры обладаютбольшей гибкостью. Очевидный пример – таблица процессов. В ранних системах длякаждого процесса просто выделялся фиксированный массив структур. Если таблицапроцесса состояла из 256 элементов, тогда в любой момент могло существовать неболее 256 процессов. Попытка создания 257-го процесса заканчивалась неудачей попричине отсутствия места в таблице. Аналогичные соображения были справедливыдля таблицы открытых файлов (как для каждого пользователя в отдельности, так идля системы в целом) и различных других таблиц ядра.

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

Альтернативный методзаключается в использовании таблицы фиксированного размера, но с выделением,когда эта таблица заполнится, новой таблицы фиксированного размера, например, вдва раза большей. При этом текущие записи копируются из старой таблицы в новую,а память, которая была занята старой таблицей, возвращается в пул. Такимобразом, таблица всегда остается непрерывной, а не связной. Недостаток этогоподхода состоит в том, что требуется определенное управление памятью, крометого, адрес таблицы будет переменным вместо константы.

То же самое относится кстекам ядра. Когда поток переключается в режим ядра или когда запускается потокв режиме ядра, этому потоку требуется стек в адресном пространстве ядра. Дляпотоков пользователя стек можно инициализировать так, чтобы он рос вниз отвершины виртуального адресного пространства. При этом его размер можно заранеене указывать. Для потоков ядра размер стека должен быть указан заранее, так какстек занимает часть виртуального адресного пространства ядра, кроме того,стеков может быть несколько. Вопрос заключается в следующем: сколько памятиследует выделить для каждого стека? Преимущества и недостатки различныхподходов здесь примерно такие же, как и в случае с таблицей процессов.

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

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

Реализация системы сверхувниз и снизу вверх

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

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

Затем можно реализоватьмногозадачность вместе с простым планировщиком (например, запускающим процессыв порядке циклической очереди). Уже в этот момент система может бытьпротестирована, чтобы проверить, правильно ли она управляет несколькимипроцессами. Если все работает нормально, можно приступить к детальной разработкеразличных таблиц и структур данных, необходимых системе, особенно тех, которыеуправляют процессами и потоками, а также памятью. Ввод-вывод и файловую системуможно отложить на потом, реализовав поначалу лишь примитивный ввод с клавиатурыи вывод на экран для тестирования и отладки. В некоторых случаях следуетзащитить ключевые низкоуровневые структуры данных, разрешив доступ к ним толькос помощью специальных процедур доступа – в результате мы получаемобъектно-ориентированное программирование, независимо от того, какой языкпрограммирования применяется в действительности. Когда нижние уровни созданы,они могут быть тщательно протестированы. Таким образом, система создается снизувверх, подобно тому, как строятся высокие здания.

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

Полезные методы.

Итак, мы только чтообсудили некоторые абстрактные идеи, применяющиеся при проектировании иконструировании операционных систем. Теперь мы рассмотрим несколько конкретныхметодов, полезных при реализации систем. Разумеется, существует также множестводругих методов, но объем книги не позволяет нам рассмотреть все методы.

Скрытие аппаратуры

Большое количествоаппаратуры весьма неудобно в использовании. Его следует скрывать на раннейстадии реализации системы (если только оно не предоставляет особыхвозможностей). Некоторые детали самого нижнего уровня могут быть скрыты уровнемвроде HAL. Однако есть детали, которые таким способом скрыть невозможно.

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

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

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

Большинство операционныхсистем спроектировано так, чтобы работать на различных платформах. Этиплатформы могут отличаться центральными процессорами, блоками MMU, длиноймашинного слова, объемом оперативной памяти и другими параметрами, которыетрудно замаскировать уровнем HAL или его эквивалентом. Тем не менее желательноиметь единый набор исходных файлов, используемых для формирования всех версий.В противном случае каждую обнаруженную ошибку придется исправлять много раз вомногих исходных файлах. При этом возникает опасность, что исходные файлы будутотличаться друг от друга все больше и больше.

С некоторыми различиями аппаратуры,такими как объем ОЗУ, можно бороться, оформив этот параметр в виде переменной иопределяя его значение во время загрузки системы. Например, переменная,содержащая объем оперативной памяти, может использоваться программой,предоставляющей память процессам, а также для определения размера блока кэша,таблиц страниц и т. д. Даже размер статических таблиц, таких как таблицапроцессов, может задаваться при загрузке, в зависимости от общего объемаоперативной памяти.

Однако другие различия,такие как различия в центральных процессорах, не могут быть скрыты при помощиединого двоичного кода, определяющего при загрузке тип процессора. Один изспособов решения данной проблемы состоит в использовании условной трансляцииединого исходного кода. В исходных файлах для различных конфигурацийиспользуются определенные флаги компиляции, позволяющие получать из единогоисходного текста различные двоичные файлы в зависимости от центральногопроцессора, длины слова, блока MMU и т. д. Представьте себе операционную систему,которая должна работать на компьютерах с процессорами Pentium и UltraSPARC,требующих различных программ инициализации. В зависимости от значения константыCPU, определяемой в заголовочном файле config.h, будет выполняться либо одинтип инициализации, либо другой. Поскольку в двоичном файле содержится толькоодин вариант программы, потери эффективности не происходит.

В качестве второгопримера предположим, что нам требуется тип данных Register, который долженсостоять из 32 бит на компьютере с процессором Pentium и 64 бит на компьютере спроцессором UltraSPARC. Этого можно добиться при помощи условного кода влистинге 12.3,6 (при условии, что компилятор воспринимает тип int, как32-разрядное целое, а тип long – как 64-разрядное). Как только это определениедано (возможно, в заголовочном файле, включаемом во все остальные исходныефайлы), программист может просто объявить переменные типа Register и бытьуверенным, что эти переменные имеют правильный размер.

Разумеется, заголовочныйфайл config.h должен быть определен корректно. Для процессора Pentium он можетвыглядеть примерно так:

Чтобы откомпилироватьоперационную систему для процессора UltraSPARC, нужно использовать другой файлconfig.h, содержащий правильные значения для процессора UltraSPARC, возможно,что-то вроде

Некоторые читатели могутудивиться, почему переменные CPU и WORD_LENGTH управляются различнымимакросами. В определении константы Register можно сделать ветвление программы,устанавливая ее значение в зависимости от значения константы CPU, то естьустанавливая значение константы Register равной 32 бит для процессора Pentium и64 бит для процессора UltraSPARC. Однако эта идея не слишком удачна. Чтопроизойдет, если позднее мы соберемся переносить систему на 64-разрядныйпроцессор Intel Itanium? Для этого нам пришлось бы добавить третий условныйоператор, для процессора Itanium. При том, как это было сделано, нужно толькодобавить строку в файл config.h для процессора Itanium.

Этот пример иллюстрируетобсуждавшийся ранее принцип ортогональности. Участки системы, зависящие от типацентрального процессора, должны компилироваться с использованием условнойкомпиляции, в зависимости от значения константы CPU, а для участков системы,зависимых от размера слова, должен использоваться макрос WORD_LENGTH. Те жесоображения справедливы и для многих других параметров.

Косвенность

Иногда говорят, что неттакой проблемы в кибернетике, которую нельзя решить на другом уровнекосвенности. Хотя это определенное преувеличение, во фразе имеется и доля истины.Рассмотрим несколько примеров. В системах на основе процессора Pentium принажатии клавиши аппаратура формирует прерывание и помещает в регистр устройстване символ ASCII, а скан-код клавиши. Более того, когда позднее клавишаотпускается, генерируется второе прерывание, также с номером клавиши. Такаякосвенность предоставляет операционной системе возможность использовать номерклавиши в качестве индекса в таблице, чтобы получить по его значению символASCII. Этот способ облегчает обработку разных клавиатур, существующих вразличных странах. Наличие информации как о нажатии, так и об отпускании клавишпозволяет использовать любую клавишу в качестве регистра, так как операционнойсистеме известно, в котором порядке нажимались и отпускались клавиши.

Косвенность такжеиспользуется при выводе данных. Программы могут выводить на экран символыASCII, но эти символы могут интерпретироваться как индексы в таблице,содержащей текущий отображаемый шрифт. Элемент таблицы содержит растровоеизображение символа. Такая форма косвенности позволяет отделить символы отшрифта.

Еще одним примеромкосвенности служит использование старших номеров устройств в UNIX. В ядресодержатся две таблицы, одна для блочных устройств и одна для символьных,индексированные старшим номером устройства. Когда процесс открывает специальныйфайл, например /dev/hd0, система извлекает из i-узла информацию о типеустройства (блочное или символьное), а также старший и младший номера устройстви, используя их в качестве индексов, находит в таблице драйверовсоответствующий драйвер. Такой вид косвенности облегчает реконфигурациюсистемы, так как программы имеют дело с символьными именами устройств, а не сфактическими именами драйверов.

Еще один примеркосвенности встречается в системах передачи сообщений, указывающих в качествеадресата не процесс, а почтовый ящик. Таким образом достигается существеннаягибкость (например, секретарша может принимать почту своего шефа).

В определенном смыслеиспользование макросов, как, например, также представляет собой одну из формкосвенности, так как программист может написать программу, не зная фактическойвеличины таблицы. Считается хорошей практикой давать символьные имена всемконстантам (иногда кроме –1, 0 и 1) и помещать их в заголовки ссоответствующими комментариями.

Повторное использование

Часто возникаетвозможность использовать повторно ту же самую программу в несколько отличномконтексте. Это позволяет уменьшить размер двоичных файлов, а кроме тогоозначает, что такую программу потребуется отлаживать всего один раз. Например,предположим, что для учета свободных блоков на диске используются битовыемассивы. Дисковыми блоками можно управлять при помощи процедур alloc и free.

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

Реентерабельность

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

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

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

Метод грубой силы

Применение простыхрешений под названием метода грубой силы с годами приобрело негативный оттенок,однако простота решения часто оказывается преимуществом. В каждой операционнойсистеме есть множество процедур, которые редко вызываются или которые оперируюттаким небольшим количеством данных, что оптимизировать их нет смысла. Например,в системе часто приходится искать какой-либо элемент в таблице или массиве.Метод грубой силы в данном случае заключается в том, чтобы оставить таблицу втом виде, в каком она есть, никак не упорядочивая элементы, и производить поискв ней линейно от начала к концу. Если число элементов в таблице невелико(например, не более 100), выигрыш от сортировки таблицы или применениякэширования будет невелик, но программа станет гораздо сложнее и,следовательно, вероятность содержания в ней ошибок резко возрастет. Разумеется,для функций, находящихся в критических участках системы, например в процедуре,занимающейся переключением контекста, следует предпринять все меры для ихускорения, возможно даже писать их (Боже упаси!) на ассемблере. Но большаячасть системы не находится в критическом участке. Так, ко многим системнымвызовам редко обращаются. Если системный вызов fork выполняется раз в 10 с, аего выполнение занимает 10 мс, тогда, даже если удастся невозможное –оптимизация, после которой выполнение системного вызова fork будет занимать 0мс, – общий выигрыш составит всего 0,1 %. Если после оптимизации код станетбольше и будет содержать больше ошибок, то в данном случае лучше оптимизацией незаниматься.

Проверка на ошибки преждевсего

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

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

Если системному вызовуудается пробраться сквозь все тесты, тогда становится ясно, что он завершитсяуспешно. В этот момент ему можно выделять ресурсы.

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

Многие системы страдаютподобными «заболеваниями» в форме утечки памяти. Довольно часто программыобращаются к процедуре malloc, чтобы получить память, но забывают позднееобратиться к функции free, чтобы освободить ее. Вся память системы постепенноисчезает, пока система не зависает.

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

Производительность

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

Кэширование

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

Мы уже наблюдалииспользование кэша в файловой системе, где он хранит некоторое количествонедавно использовавшихся блоков диска, что позволяет избежать обращения к дискупри чтении блока. Однако кэширование может также применяться и для другихцелей. Например, обработка путей к файлам отнимает удивительно много процессорноговремени. Рассмотрим снова пример из системы UNIX.Чтобы найти файл/usr/ast/mbox, потребуется выполнить следующие обращения к диску:

1. Прочитать i-узелкорневого каталога (i-узел 1).

2. Прочитать корневойкаталог (блок 1).

3. Прочитать i-узелкаталога /usr (i-узел 6).

4. Прочитать каталог /usr(блок 132).

5. Прочитать i-узелкаталога /usr/ast (i-узел 26).

6. Прочитать каталог/usr/ast (блок 406).

Чтобы просто определитьномер i-узла искомого файла, нужно как минимум шесть раз обратиться к диску. Еслиразмер файла меньше размера блока (например, 1024 байт), то, чтобы прочитатьсодержимое файла, нужно восемь обращений к диску.

В некоторых операционныхсистемах обработка путей файлов оптимизируется при помощи кэширования пар(путь, i-узел).

Когда файловая системадолжна найти файл по пути, обработчик путей сначала обращается к кэшу и ищет внем самую длинную подстроку, соответствующую обрабатываемому пути. Еслиобрабатывается путь /usr/ast/grants/stw, кэш отвечает, что номер i-узлакаталога /usr/ast равен 26, так что поиск может быть начат с этого места иколичество обращений к диску может быть уменьшено на четыре. Недостатоккэширования путей состоит в том, что соответствие имени файла номеру его i-узлане является постоянным. Представьте, что файл /usr/ast/mbox удаляется и егоi-узел используется для другого файла, владельцем которого может быть другойпользователь. Затем файл /usr/ast/mbox создается снова, но на этот раз онполучает i-узел с номером 106. Если не предпринять специальных мер, запись кэшабудет указывать на неверный номер i-узла. Поэтому при удалении файла иликаталога следует удалять из кэша запись, соответствующую этому файлу, а еслиудаляется каталог, то следует удалить также все записи для содержавшихся в этомкаталоге файлов и подкаталогов*.

Кэшироваться могут нетолько блоки дисков и пути к файлам. Можно кэшировать также i-узлы. Если дляобработки прерываний используются временные потоки, для каждого из нихтребуется стек и некоторый дополнительный механизм. Эти использовавшиеся ранеепотоки также можно кэшировать, так как обновить уже использовавшийся потоклегче, чем создать новый (применение кэша позволяет избежать необходимости ввыделении новому процессу памяти). Кэширование может применяться почти длявсего, что трудновоспроизводимо.

Подсказки

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

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

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

Использование локальности

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

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

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

Оптимизируйте общийслучай

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

В качестве первогопримера рассмотрим вхождение в критическую область. В большинстве случаевпроцессу будет удаваться вход в критическую область, особенно если внутри этойобласти процессы не проводят много времени. Операционная система Windows 2000использует это преимущество, предоставляя вызов Win32 API EnterCriticalSection,который является атомарной функцией, проверяющей флаг в режиме пользователя (спомощью команды процессора TSL или ее эквивалента). Если тест проходит успешно,процесс просто входит в критическую область, для чего не требуется обращения кядру. Если же результат проверки отрицательный, библиотечная процедуравыполняет на семафоре операцию down, чтобы заблокировать процесс. Такимобразом, в нормальном случае обращение к ядру не требуется.

В качестве второгопримера рассмотрим установку будильника (использующего сигналы UNIX). Если втекущий момент ни один будильник не заведен, то просто создается запись ипомещается в очередь таймеров. Однако если будильник уже заведен, его следуетнайти и удалить из очереди таймера. Так как системный вызов alarm не указывает,установлен ли уже будильник, система должна предполагать худшее, то есть что онуже заведен. Однако в большинстве случаев будильник не будет заведен, ипоскольку удаление существующего будильника представляет собой дорогоеудовольствие, то следует различать эти два случая.

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

Управление проектом

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

Мифический человеко-месяц

В своей классическойкниге Фред Брукс, один из разработчиков системы OS/360, занявшийся впоследствиинаучной деятельностью, рассматривает вопрос, почему так трудно построитьбольшую операционную систему [44, 46]. Когда большинство программистоввстречаются с его утверждением, что специалисты, работающие над большимипроектами, могут за год произвести всего лишь 1000 строк отлаженного кода, ониудивляются, не прилетел ли профессор Брукс из космоса, с планеты Баг. В концеконцов, большинство из них помнит, как они создавали программу из 1000 строквсего за одну ночь. Как же этот объем исходного текста может составлять годовуюнорму для любого программиста, чей IQ превышает 50?

Брукс отмечает, чтобольшие проекты, в которых задействованы сотни программистов, принципиальноотличаются от небольших проектов и что результаты, достигнутые при работе наднебольшим проектом, нельзя переносить на большой проект. В большом проектеогромное количество времени тратится на планирование того, как разделить работуна отдельные модули. При этом нужно детально расписать работу модулей иинтерфейсы к ним, а также попытаться представить себе, как эти модуливзаимодействуют, причем до того, как начнется само программирование. Затеммодули по отдельности создаются и отлаживаются. Наконец, модули собираютсявместе и вся система в целом тестируется. Как правило, при этом собранная изработающих по отдельности модулей система работать не хочет, и после сборки изапуска немедленно рушится. Брукс оценивает количество работ следующим образом:

1/3 планирование;

1/6 кодирование;

1/4 тестирование модулей;

1/4 тестирование системы.

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

Заголовком книги Бруксобращает внимание читателя на собственное утверждение о том, что люди и времяне взаимозаменяемы. Такой единицы, как человеко-месяц, в программировании несуществует. Если в проекте участвуют 15 человек, и на всю работу у них уходит 2года, то отсюда не следует, что 360 человек справятся с этой работой за одинмесяц, и вряд ли 60 человек выполнят эту работу за 6 месяцев.

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

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

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

Брукс подводит итогисвоего опыта знакомства с большими проектами, формулируя следующий закон (законБрукса): Добавление к программному проекту на поздней стадии дополнительныхлюдских сил приводит к увеличению сроков выполнения проекта.

Недостаток введения впроект новых людей состоит в том, что их необходимо обучать, модули нужноделить заново, чтобы их число соответствовало числу программистов, требуетсяпровести множество собраний, чтобы скоординировать работу отдельных групп и программистови т.д. Абдель-Хамид и Мэдник [1] получили экспериментальное подтверждение этогозакона. Слегка фривольный вариант закона Брукса звучит так: Если собрать девятьрожениц в одной комнате, то они не родят через один месяц.

Роль опыта

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

Решение, предложенноеБруксом, заключается в отказе от классической модели разработки. Принципсостоит в том, чтобы сначала написать главный модуль программы, который простовызывает процедуры верхнего уровня. Вначале эти процедуры представляют собойзаглушки. Начиная уже с первого дня система будет транслироваться изапускаться, хотя делать она ничего не будет. Постепенно в систему будутустанавливаться модули. Результат применения такого метода заключается в том,что сборка системы проверяется постоянно, поэтому ошибки в проектеобнаруживаются значительно раньше. Таким образом, процесс обучения на собственныхошибках также начинается значительно раньше.

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

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

Тенденции в проектированииоперационных систем

Предсказывать всегдатрудно, особенно будущее. Например, в 1899 году Чарльз Дьюэл, возглавлявшийтогда Бюро патентов США, предложил тогдашнему президенту США Мак-Кинлиликвидировать патентное бюро (а также и рабочее место Чарльза Дьюэла!),поскольку, как он писал, «все, что можно было изобрести, уже изобретено». Темне менее прошло всего несколько лет, и на пороге патентного бюро показалсяТомас Эдисон с заявками на электрические лампы, фонограф и кинопроектор. Сменимбатарейки в нашем кристальном шаре и попытаемся угадать, что станет соперационными системами в ближайшем будущем.

Операционные системы сбольшим адресным пространством

По мере того как на смену32-разрядным машинам приходят 64-разрядные, становится возможным главноеизменение в строении операционных систем. 32-разрядное адресное пространство насамом деле не так уж велико. Если попытаться разделить 232 байт на всех жителейЗемли, то каждому достанется менее одного байта. В то же время 264 примерноравно 2×1019. При этом каждому жителю планеты в 64-разрядном адресномпространстве можно выделить фрагмент размером в 3 Гбайт.

Что можно сделать садресным пространством в 2×1019 байт? Для начала мы можем отказаться отконцепции файловой системы. Вместо этого все файлы можно постоянно хранить впамяти (виртуальной). В конце концов, в ней достаточно места для более чеммиллиарда полнометражных фильмов, сжатых до 4 Гбайт. Другая возможностьзаключается в использовании перманентных объектов. Объекты могут создаваться вадресном пространстве и храниться в нем до тех пор, пока не будут удалены всессылки на объект, после чего сам объект автоматически удаляется. Такие объектыбудут сохраняться в адресном пространстве даже после выключения и перезагрузкикомпьютера. Чтобы заполнить все 64-разрядное адресное пространство, нужносоздавать объекты со скоростью 100 Мбайт/с в течение 5000 лет. Разумеется, дляхранения такого количества данных потребуется очень много дисков, но впервые вистории ограничивающим фактором стали физические возможности дисков, а неадресное пространство.

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

Еще один системныйаспект, который придется пересмотреть при введении 64-разрядных адресов, этовиртуальная память. При 264 байт виртуального адресного пространства и8-килобайтных страницах у нас будет 251 страниц. Работать с обычными таблицамистраниц такого размера будет непросто, поэтому потребуется другое решение.Возможно использование инвертированных таблиц страниц, однако такжепредлагались и другие идеи [321]. В любом случае появление 64-разрядныхоперационных систем создает новую большую область исследований.

Сеть

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

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

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

Параллельные ираспределенные системы

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

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

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

Мультимедиа

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

Что следуетоптимизировать?

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

Вот правдивая история отом, как оптимизация принесла больше вреда, чем пользы. Один из студентовавтора (имени студента мы здесь называть не будем) написал программу mkfs длясистемы MINIX. Эта программа создает пустую файловую систему на только чтоотформатированном диске. На оптимизацию этой программы студент затратил около 6месяцев. Когда он попытался запустить эту программу, оказалось, что она неработает, после чего потребовалось еще 6 дополнительных месяцев на ее отладку.На жестком диске эту программу, как правило, запускают всего лишь один раз, приустановке системы. Она также только раз запускается для каждого гибкого диска –после его форматирования. Каждый запуск программы занимает около 2 с. Даже еслибы работа неоптимизированной версии занимала 1 мин, то затрата такого большоговремени на оптимизацию столь редко используемой программы являлась бынепроизводительным расходованием ресурсов.

Лозунг, применимый коптимизации производительности, мог бы звучать так: лучшее – враг хорошего

Под этим мыподразумеваем, что как только удается достичь приемлемого уровняпроизводительности, то попытки выжать последние несколько процентов, видимо,уже не стоят затрачиваемых усилий и усложнения программы. Если алгоритмпланирования достаточно хорош и обеспечивает 90-прцентную загрузку центральногопроцессора, возможно, этого достаточно. Разработка значительно более сложногоалгоритма, на 5 % лучше имеющегося, не всегда представляет собой удачную идею.Аналогично, если частота подкачки страниц достаточно низка, то есть подкачка непредставляет собой узкое место, то, как правило, нет смысла лезть из кожи вон,чтобы добиться оптимальной производительности. Недопущение сбоев в работесистемы представляется намного более важной задачей, нежели достижениеоптимальной производительности, особенно если алгоритм, оптимальный при одномуровне загруженности компьютера, может оказаться неоптимальным при другомуровне.

Литература:

www.5-ka.ru

Wikipedia.

Кузнецов Ю.В. «Теория операционныхсистем».

www.students.ru