Основы операционных систем

Основы операционных систем

Курс лекций. Учебное пособие

Издание второе, дополненное и исправленное

В.Е. Карпов К.А. Коньков

под редакцией члена-корреспондента РАН В.П. Иванникова

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

Серия «Основы информационных технологий» Курс разработан при поддержке компании Intel

Интернет-Университет Информационных Технологий

www.intuit.ru

Москва, 2005

УДК 004.451(075.8) ББК 32.973.26-018.2я73-2 К26

К-26 Основы операционных систем. Курс лекций. Учебное пособие / В.Е. Карпов, К.А. Коньков / Под редакцией В.П. Иванникова. -- М.: ИНТУИТ.РУ «Интернет-Университет Информационных Технологий», 2005. -- 536 с. ISBN 5-9556-0044-2

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

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

Библиогр. 19

Курс разработан при поддержке компании Intel.

Издание осуществлено при финансовой и технической поддержке издательства «Открытые Системы», «РМ Телеком» и Kraftway Computers.

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

© Интернет-Университет Информационных Технологий, www.intuit.ru, 2005

ISBN 5-9556-0044-2

О проекте

Интернет-Университет Информационных Технологий -- это первое в России высшее учебное заведение, которое предоставляет возможность получить дополнительное образование во Всемирной сети. Web-сайт университета находится по адресу www.intuit.ru.

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

Обучение в университете ведется по собственным учебным планам, разработанным ведущими российскими специалистами на основе международных образовательных стандартов Computer Curricula 2001 Computer Science. Изучать учебные курсы можно самостоятельно по учебникам или на сайте Интернет-университета, задания выполняются только на сайте. Для обучения необходимо зарегистрироваться на сайте университета. Удостоверение об окончании учебного курса или специальности выдается при условии выполнения всех заданий к лекциям и успешной сдачи итогового экзамена.

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

Добро пожаловать в Интернет-Университет Информационных Технологий!

Анатолий Шкред anatoli@shkred.ru

Предисловие

Операционные системы (ОС) появились в учебных университетских курсах (вначале фрагментарно) в 1960-х годах. Например, в курсе по системному программированию, прочитанном Н. Виртом в Стенфордском университете. В 1970-х ОС становится одной.из самостоятельных дисциплин в разделе информатики.

В зависимости от специализации курс операционных систем занимает один или несколько семестров. На сегодня издано уже множество книг по ОС. Среди них хотелось бы выделить две: «Операционные системы», Д. Цикритис и Ф. Бернстайн, изданную в 1977 году и широко использовавшуюся в преподавании и самостоятельном изучении на протяжении многих лет, и великолепную недавнюю монографию «Современные операционные системы» Э. Таненбаума.

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

В основу книги положен курс ОС МФТИ третьего семестра, читаемый в течение последних пяти лет. Ему предшествуют два семестровых курса: «Введение в алгоритмы» и «Введение в архитектуру вычислительных систем». Знания и навыки, приобретаемые студентами за первые два семестра, используются в курсе «Введение в операционные системы». Наиболее важными являются структуры данных, в особенности организация очередей и таблиц, оценка сложности алгоритмов (первый семестр); организация памяти, система прерываний, машинные инструкции и отображение конструкций языков программирования в систему команд (второй семестр).

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

В. П. Иванников, профессор, член-корреспондент РАН

Об авторах

Карпов Владимир Ефимович

Кандидат физико-математических наук, доцент кафедры информатики Московского физико-технического института, сопредседатель секции «Компьютеры в науке и образовании» ежегодной международной конференции «Математика, компьютер, образование». Сотрудничал в разработке разнообразных программных систем с компаниями Рагакс, АТ&Т. Автор ряда статей и международных докладов по параллельному программированию и распараллеливанию задач математической физики.

Коньков Константин Алексеевич

Кандидат физико-математических наук, старший научный сотрудник Института Автоматизации проектирования РАН, доцент кафедры математических и информационных технологий Московского физико-технического института, директор по научной работе ООО «Физтех-софт». Область научных интересов: операционные системы, разработка системного программного обеспечения. Принимал участие в создании операционной системы РТ8-008, системы защиты информации 81гогщО!8к и ряда других системных продуктов.

Лекции

Лекция 1. Введение

Лекция 2. Процессы

Лекция 3. Планирование процессов

Лекция 4. Кооперация процессов и основные аспекты ее логической организации

Лекция 5. Алгоритмы синхронизации

Лекция 6. Механизмы синхронизации

Лекция 7. Тупики

Лекция 8. Организация памяти компьютера. Простейшие схемы управления памятью

Лекция 9. Виртуальная память. Архитектурные средства поддержки виртуальной памяти

Лекция 10. Аппаратно-независимый уровень управления виртуальной памятью

Лекция 11. Файлы с точки зрения пользователя

Лекция 12. Реализация файловой системы

Лекция 13. Система управления вводом-выводом

Лекция 14. Сети и сетевые операционные системы

Лекция 15. Основные понятия информационной безопасности

Лекция 16. Защитные механизмы операционных систем

Семинары 1-2. Введение в курс практических занятий. Знакомство с операционной системой UNIX.	Основываются на лекции 1
Семинары 3-4. Процессы в операционной системе UNIX.	Основываются на лекции 2
Семинар 5. Организация взаимодействия процессов через pipe и FIFO в UNIX.	Основывается на лекции 4
Семинары 6-7. Средства System V IPC. Организация работы с разделяемой памятью в UNIX. Понятие нитей исполнения (thread).	Основываются на лекциях 4 и 5
Семинар 8. Семафоры в UNIX как средство синхронизации процессов.	Основывается на лекциях 5 и 6
Семинар 9. Очереди сообщений в UNIX.	Основывается на лекциях 4 и 6
Семинары 10-11. Организация файловой системы в UNIX. Работа с файлами и директориями. Понятие о memory mapped файлах.	Основываются на лекциях 10, 11 и 12
Семинары 12-13. Организация ввода-вывода в UNIX. Файлы устройств. Аппарат прерываний. Сигналы в UNIX.	Основываются на лекциях 12 и 13
Семинары 14-15. Семейство протоколов TCP/IP. Сокеты (sockets) в UNIX и основы работы с ними.	Основываются на лекции 14

Содержание

Часть I. Обзор

Лекция 1. Введение

Что такое операционная система

Краткая история эволюции вычислительных систем

Основные понятия, концепции ОС

Архитектурные особенности ОС

Классификация ОС

Заключение

Часть II. Процессы и их поддержка в операционной системе

Лекция 2. Процессы

Понятие процесса

Состояния процесса

Операции над процессами и связанные с ними понятия

Заключение

Лекция 3. Планирование процессов

Уровни планирования

Критерии планирования и требования к алгоритмам

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

Вытесняющее и невытесняющее планирование

Алгоритмы планирования

Заключение

Лекция 4. Кооперация процессов и основные аспекты ее логической организации

Взаимодействующие процессы

Категории средств обмена информацией

Логическая организация механизма передачи информации

Нити исполнения

Заключение

Лекция 5. Алгоритмы синхронизации

Interleaving, race condition и взаимоисключения

Критическая секция

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

Аппаратная поддержка взаимоисключений

Заключение

Лекция 6. Механизмы синхронизации

Семафоры

Мониторы

Сообщения

Эквивалентность семафоров, мониторов и сообщений

Заключение

Лекция 7. Тупики

Введение

Условия возникновения тупиков

Основные направления борьбы с тупиками

Игнорирование проблемы тупиков

Способы предотвращения тупиков

Обнаружение тупиков

Восстановление после тупиков

Заключение

Часть III. Управление памятью

Лекция 8. Организация памяти компьютера. Простейшие схемы управления памятью

Введение

Простейшие схемы управления памятью

Страничная память

Сегментная и сегментно-страничная организация памяти

Заключение

Лекция 9. Виртуальная память. Архитектурные средства поддержки виртуальной памяти

Понятие виртуальной памяти

Архитектурные средства поддержки виртуальной памяти

Заключение

Лекция 10. Аппаратно-независимый уровень управления виртуальной памятью

Исключительные ситуации при работе с памятью

Стратегии управления страничной памятью

Алгоритмы замещения страниц

Управление количеством страниц, выделенным процессу

Модель рабочего множества

Страничные демоны

Программная поддержка сегментной модели памяти процесса

Отдельные аспекты функционирования менеджера памяти

Заключение

Часть IV. Файловые системы

Лекция 11. Файлы с точки зрения пользователя

Введение

Общие сведения о файлах

Организация файлов и доступ к ним

Операции над файлами

Директории. Логическая структура файлового архива

Операции над директориями

Защита файлов

Заключение

Лекция 12. Реализация файловой системы

Общая структура файловой системы

Управление внешней памятью

Реализация директорий

Монтирование файловых систем

Связывание файлов

Кооперация процессов при работе с файлами

Надежность файловой системы

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

Реализация некоторых операций над файлами

Современные архитектуры файловых систем

Заключение

Часть V. Ввод-вывод

Лекция 13. Система управления вводом-выводом

Физические принципы организации ввода-вывода

Логические принципы организации ввода-вывода

Алгоритмы планирования запросов к жесткому диску

Заключение

Часть VI. Сети и сетевые операционные системы

Лекция 14. Сети и сетевые операционные системы

Для чего компьютеры объединяют в сети

Сетевые и распределенные операционные системы

Взаимодействие удаленных процессов как основа работы вычислительных сетей

Основные вопросы логической организации передачи информации между удаленными процессами

Понятие протокола

Многоуровневая модель построения сетевых вычислительных систем

Проблемы адресации в сети

Проблемы маршрутизации в сетях

Связь с установлением логического соединения и передача данных с помощью сообщений

Синхронизация удаленных процессов

Заключение

Часть VII. Проблемы безопасности операционных систем

Лекция 15. Основные понятия информационной безопасности

Введение

Угрозы безопасности

Формализация подхода к обеспечению информационной безопасности

Криптография как одна из базовых технологий безопасности ОС

Заключение

Лекция 16. Защитные механизмы операционных систем

Идентификация и аутентификация

Авторизация. Разграничение доступа к объектам ОС

Выявление вторжений. Аудит системы защиты

Анализ некоторых популярных ОС с точки зрения их защищенности

Заключение

Семинары

Семинары 1--2. Введение в курс практических занятий

Знакомство с операционной системой UNIX

Семинары 3--4. Процессы в операционной системе UNIX

Семинар 5. Организация взаимодействия процессов через pipe и FIFO в UNIX

Семинары 6--7. Средства System V IPC. Организация работы с разделяемой памятью в UNIX

Понятие нитей исполнения (thread)

Семинар 8. Семафоры в UNIX как средство синхронизации процессов

Семинар 9. Очереди сообщений в UNIX

Семинары 10--11. Организация файловой системы в UNIX. Работа с файлами и директориями.

Понятие о memory mapped файлах

Семинары 12--13. Организация ввода-вывода в UNIX

Файлы устройств. Аппарат прерываний. Сигналы в UNIX

Семинары 14--15. Семейство протоколов TCP/IP

Сокеты (sockets) в UNIX и основы работы с ними

Литература

Часть I. Обзор

Лекция 1. Введение

В данной лекции вводится понятие операционной системы; рассматривается эволюция развития операционных систем; описываются функции операционных систем и подходы к построению операционных систем.

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

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

Что такое операционная система Структура вычислительной системы

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

Во-вторых, вычислительная система состоит из программного обеспечения. Все программное обеспечение принято делить на две части: прикладное и системное. К прикладному программному обеспечению, как правило, относятся разнообразные банковские и прочие бизнес-программы, игры, текстовые процессоры и т. п. Под системным программным обеспечением обычно понимают программы, способствующие функционированию и разработке прикладных программ. Надо сказать, что деление на прикладное и системное программное обеспечение является отчасти условным и зависит от того, кто осуществляет такое деление. Так, обычный пользователь, неискушенный в программировании, может считать Microsoft Word системной программой, а, сточки зрения программиста, это -- приложение. Компилятор языка Си для обычного программиста -- системная программа, а для системного -- прикладная. Несмотря на эту нечеткую грань, данную ситуацию можно отобразить в виде последовательности слоев (см. рис 1.1), выделив отдельно наиболее общую часть системного программного обеспечения -- операционную систему:

L

Пользователь

Прикладные программы

Прочие системные программы

Системные "программы

Программное "обеспечение"

Операционная система

Техническое обеспечение

Рис. 1.1 Слои программного обеспечения компьютерной системы

Что такое ОС

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

Операционная система как виртуальная машина

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

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

Операционная система как менеджер ресурсов

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

Операционная система как защитник пользователей и программ

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

Операционная система как постоянно функционирующее ядро

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

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

Краткая история эволюции вычислительных систем

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

Первый период (1945-1955 гг.). Ламповые машины. Операционных систем нет

Мы начнем исследование развития компьютерных комплексов с появления электронных вычислительных систем (опуская историю механических и электромеханических устройств).

Первые шаги в области разработки электронных вычислительных машин были предприняты в конце Второй Мировой войны. В середине 1940-х годов были созданы первые ламповые вычислительные устройства и появился принцип программы, хранящейся в памяти машины (John Von Neumann, июнь 1945 г.). В то время одна и та же группа людей участвовала и в проектировании, и в эксплуатации, и в программировании вычислительной машины. Это была скорее научно-исследовательская работа в области вычислительной техники, а не регулярное использование компьютеров в качестве инструмента решения каких-либо практических задач из других прикладных областей. Программирование осуществлялось исключительно на машинном языке. Об операционных системах не было и речи, все задачи организации вычислительного процесса решались вручную каждым программистом с пульта управления. За пультом мог находиться только один пользователь. Программа загружалась в память машины в лучшем случае с колоды перфокарт, а обычно -- с помощью панели переключателей.

Вычислительная система выполняла одновременно только одну операцию (ввод-вывод или собственно вычисления). Отладка программ велась с пульта управления с помощью изучения состояния памяти и регистров машины. В конце этого периода появляется первое системное программное обеспечение: в 1951-1952 гг. возникают прообразы первых компиляторов с символических языков (Fortran и др.), а в 1954 г. Nat Rochester разрабатывает Ассемблер для 1ВМ-701.

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

Второй период (1955 г. - начало 1960-х гг.). Компьютеры на основе транзисторов. Пакетные операционные системы

С середины 1950-х годов начался следующий период в эволюции вычислительной техники, связанный с появлением новой технической базы -- полупроводниковых элементов. Применение транзисторов вместо часто перегоравших электронных ламп привело к повышению надежности компьютеров. Теперь машины могли непрерывно работать достаточно долго, чтобы на них можно было возложить выполнение практически важных задач. Снизилось потребление вычислительными машинами электроэнергии, усовершенствовались системы охлаждения. Размеры компьютеров уменьшились. Снизилась стоимость эксплуатации и обслуживания вычислительной техники. Началось использование ЭВМ коммерческими фирмами. Одновременно наблюдается бурное развитие алгоритмических языков (LISP, COBOL, ALGOL-60, PL-1 и т.д.). Появляются первые настоящие компиляторы, редакторы связей, библиотеки математических и служебных подпрограмм. Упрощается процесс программирования. Пропадает необходимость взваливать на одних и тех же людей весь процесс разработки и использования компьютеров. Именно в этот период происходит разделение персонала на программистов и операторов, разработчиков вычислительных машин и специалистов по эксплуатации.

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

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

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

Третий период (начало 1960-х - 1980 г.). Компьютеры на основе интегральных микросхем. Первые многозадачные ОС

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

Повышению эффективности использования процессорного времени мешает низкая скорость работы механических устройств ввода-вывода (быстрый считыватель перфокарт мог обработать 1200 перфокарт в минуту, принтеры печатали до 600 строк в минуту). Вместо непосредственного чтения пакета заданий с перфокарт в память, начинают использовать его предварительную запись, сначала на магнитную ленту, а затем и на диск. Когда в процессе выполнения задания требуется ввод данных, они читаются с диска. Точно так же выходная информация сначала копируется в системный буфер и записывается на ленту или диск, а печатается только после завершения задания. Вначале действительные операции ввода-вывода осуществлялись в режиме off-line, то есть с использованием других, более простых, отдельно стоящих компьютеров. В дальнейшем они начинают выполняться на том же компьютере, который производит вычисления, то есть в режиме on-line. Такой прием получает название spooling (сокращение от Simultaneous Peripheral Operation On Line) или подкачки-откачки данных. Введение техники подкачки-откачки в пакетные системы позволило совместить реальные операции ввода-вывода одного задания с выполнением другого задания, но потребовало разработки аппарата прерываний для извещения процессора об окончании этих операций.

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

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

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

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

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

Развитие параллелизма в архитектуре. Прямой доступ к памяти и организация каналов ввода-вывода позволили освободить центральный процессор от рутинных операций.

Не менее важна в организации мультипрограммирования роль операционной системы. Она отвечает за следующие операции:

* Организация интерфейса между прикладной программой и ОС при помощи системных вызовов.

Организация очереди из заданий в памяти и выделение процессора одному из заданий требует планирования использования процессора.

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

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

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

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

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

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

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

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

Параллельно внутренней эволюции вычислительных систем происходила и внешняя их эволюция. До начала этого периода вычислительные комплексы были, как правило, несовместимы. Каждый имел собственную операционную систему, свою систему команд и т. д. В результате программу, успешно работающую на одном типе машин, необходимо было полностью переписывать и заново отлаживать для выполнения на компьютерах другого типа. В начале третьего периода появилась идея создания семейств программно совместимых машин, работающих под управлением одной и той же операционной системы. Первым семейством программно совместимых компьютеров, построенных на интегральных микросхемах, стала серия машин IBM/360. Разработанное в начале 1960-х годов, это семейство значительно превосходило машины второго поколения по критерию цена/производительность. За ним последовала линия компьютеров PDP, несовместимых с линией IBM, и лучшей моделью в ней стала PDP-11.

Сила «одной семьи» была одновременно и ее слабостью. Широкие возможности этой концепции (наличие всех моделей: от мини-компьютеров до гигантских машин; обилие разнообразной периферии; различное окружение; различные пользователи) порождали сложную и громоздкую операционную систему. Миллионы строчек Ассемблера, написанные тысячами программистов, содержали множество ошибок, что вызывало непрерывный поток публикаций о них и попыток исправления. Только в операционной системе OS/360 содержалось более 1 ООО известных ошибок. Тем не менее идея стандартизации операционных систем была широко внедрена в сознание пользователей и в дальнейшем получила активное развитие.

Четвертый период (с 1980 г. по настоящее время) Персональные компьютеры. Классические, сетевые и распределенные системы

Следующий период в эволюции вычислительных систем связан с появлением больших интегральных схем (БИС). В эти годы произошло резкое возрастание степени интеграции и снижение стоимости микросхем. Компьютер, не отличающийся по архитектуре от РЭР-11, по цене и простоте эксплуатации стал доступен отдельному человеку, а не только отделу предприятия или университета. Наступила эра персональных компьютеров. Первоначально персональные компьютеры предназначались для использования одним пользователем в однопрограммном режиме, что повлекло за собой деградацию архитектуры этих ЭВМ и их операционных систем (в частности, пропала необходимость защиты файлов и памяти, планирования заданий и т. п.).

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

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

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

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

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

В дальнейшем автономные операционные системы мы будем называть классическими операционными системами.

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

Планирование заданий и использования процессора.

Обеспечение программ средствами коммуникации и синхронизации.

Управление памятью.

Управление файловой системой.

Управление вводом-выводом.

Обеспечение безопасности.

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

Основные понятия, концепции ОС

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

Системные вызовы

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

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

Основное отличие состоит в том, что при системном вызове задача переходит в привилегированный режим или режим ядра (kernel mode). Поэтому системные вызовы иногда еще называют программными прерываниями, в отличие от аппаратных прерываний, которые чаще называют просто прерываниями.

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

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

Прерывания

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

Исключительные ситуации

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

Файлы

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

Главная задача файловой системы (file system) -- скрыть особенности ввода-вывода и дать программисту простую абстрактную модель файлов, независимых от устройств. Для чтения, создания, удаления, записи, открытия и закрытия файлов также имеется обширная категория системных вызовов (создание, удаление, открытие, закрытие, чтение и т. д.). Пользователям хорошо знакомы такие связанные с организацией файловой системы понятия, как каталог, текущий каталог, корневой каталог, путь. Для манипулирования этими объектами в операционной системе имеются системные/вызовы. Файловая система ОС описана в лекциях 11-12.

Процессы, НИТИ

Концепция процесса в ОС -- одна из наиболее фундаментальных. Процессы подробно рассмотрены в лекциях 2-7. Там же описаны нити, или легковесные процессы.

Архитектурные особенности ОС

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

Монолитное ядро

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

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

Монолитное ядро -- старейший способ организации операционных систем. Примером систем с монолитным ядром является большинство Unix-систем.

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

Многоуровневые системы (Layered systems)

Продолжая структуризацию, можно разбить всю вычислительную систему на ряд более мелких уровней с хорошо определенными связями между ними, так чтобы объекты уровня N могли вызывать только объекты уровня N-1. Нижним уровнем в таких системах обычно является hardware, верхним уровнем -- интерфейс пользователя. Чем ниже уровень, тем более привилегированные команды и действия может выполнять модуль, находящийся на этом уровне. Впервые такой подход был применен при создании системы THE (Technishe Hogeschool Eindhoven) Дейкстрой (Dijkstra) и его студентами в 1968 г. Эта система имела следующие уровни:

5	Интерфейс пользователя
4	Управление вводом-выводом
3	Драйвер устройства связи оператора и консоли
2	Управление памятью
1	Планирование задач и процессов
0	Hardware

Рис. 1.2. Слоеная система ТНЕ

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