50254 (Разработка операционных систем), страница 7

Хорошо известным примером подсказок являются указатели 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 лет. Разумеется, для хранения такого количества данных потребуется очень много дисков, но впервые в истории ограничивающим фактором стали физические возможности дисков, а не адресное пространство.

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