- •Что такое операционная система Структура вычислительной системы
- •Что такое ос
- •Операционная система как виртуальная машина
- •Операционная система как менеджер ресурсов
- •Операционная система как защитник пользователей и программ
- •Операционная система как постоянно функционирующее ядро
- •Краткая история эволюции вычислительных систем
- •Первый период (1945–1955 гг.). Ламповые машины. Операционных систем нет
- •Второй период (1955 г.–начало 60-х). Компьютеры на основе транзисторов. Пакетные операционные системы
- •Третий период (начало 60-х – 1980 г.). Компьютеры на основе интегральных микросхем. Первые многозадачные ос
- •Четвертый период (с 1980 г. По настоящее время). Персональные компьютеры. Классические, сетевые и распределенные системы
- •Основные понятия, концепции ос
- •Системные вызовы
- •Прерывания
- •Исключительные ситуации
- •Процессы, нити
- •Архитектурные особенности ос
- •Монолитное ядро
- •Многоуровневые системы (Layered systems)
- •Виртуальные машины
- •Микроядерная архитектура
- •Смешанные системы
- •Классификация ос
- •Реализация многозадачности
- •Поддержка многопользовательского режима
- •Многопроцессорная обработка
- •Системы реального времени
- •Заключение
- •Приложение 1. Некоторые сведения об архитектуре компьютера
- •Взаимодействие с периферийными устройствами
- •2. Лекция: Процессы
- •Понятие процесса
- •Состояния процесса
- •Операции над процессами и связанные с ними понятия Набор операций
- •Process Control Block и контекст процесса
- •Одноразовые операции
- •Многоразовые операции
- •Переключение контекста
- •Заключение
- •3. Лекция: Планирование процессов
- •Уровни планирования
- •Критерии планирования и требования к алгоритмам
- •Параметры планирования
- •Вытесняющее и невытесняющее планирование
- •Алгоритмы планирования
- •First-Come, First-Served (fcfs)
- •Round Robin (rr)
- •Shortest-Job-First (sjf)
- •Гарантированное планирование
- •Приоритетное планирование
- •Многоуровневые очереди (Multilevel Queue)
- •Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)
- •Заключение
- •4. Лекция: Кооперация процессов и основные аспекты ее логической организации
- •Взаимодействующие процессы
- •Категории средств обмена информацией
- •Логическая организация механизма передачи информации
- •Как устанавливается связь?
- •Информационная валентность процессов и средств связи
- •Особенности передачи информации с помощью линий связи
- •Буферизация
- •Поток ввода/вывода и сообщения
- •Надежность средств связи
- •Как завершается связь?
- •Нити исполнения
- •Заключение
- •5. Лекция: Алгоритмы синхронизации
- •Interleaving, race condition и взаимоисключения
- •Критическая секция
- •Программные алгоритмы организации взаимодействия процессов Требования, предъявляемые к алгоритмам
- •Запрет прерываний
- •Переменная-замок
- •Строгое чередование
- •Флаги готовности
- •Алгоритм Петерсона
- •Алгоритм булочной (Bakery algorithm)
- •Аппаратная поддержка взаимоисключений
- •Команда Test-and-Set (проверить и присвоить 1)
- •Команда Swap (обменять значения)
- •Заключение
- •6. Лекция: Механизмы синхронизации
- •Семафоры
- •Концепция семафоров
- •Решение проблемы producer-consumer с помощью семафоров
- •Мониторы
- •Сообщения
- •Эквивалентность семафоров, мониторов и сообщений
- •Реализация мониторов и передачи сообщений с помощью семафоров
- •Реализация семафоров и передачи сообщений с помощью мониторов
- •Реализация семафоров и мониторов с помощью очередей сообщений
- •Заключение
- •7. Лекция: Тупики Введение
- •Условия возникновения тупиков
- •Основные направления борьбы с тупиками
- •Игнорирование проблемы тупиков
- •Способы предотвращения тупиков
- •Способы предотвращения тупиков путем тщательного распределения ресурсов. Алгоритм банкира
- •Предотвращение тупиков за счет нарушения условий возникновения тупиков
- •Нарушение условия взаимоисключения
- •Нарушение условия ожидания дополнительных ресурсов
- •Нарушение принципа отсутствия перераспределения
- •Hарушение условия кругового ожидания
- •Обнаружение тупиков
- •Восстановление после тупиков
- •Заключение
- •8. Лекция: Организация памяти компьютера. Простейшие схемы управления памятью Введение
- •Физическая организация памяти компьютера
- •Локальность
- •Логическая память
- •Связывание адресов
- •Функции системы управления памятью
- •Простейшие схемы управления памятью
- •Один процесс в памяти
- •Оверлейная структура
- •Динамическое распределение. Свопинг
- •Страничная память
- •Сегментная и сегментно-страничная организация памяти
- •Заключение
- •9. Лекция: Виртуальная память. Архитектурные средства поддержки виртуальной памяти
- •Понятие виртуальной памяти
- •Архитектурные средства поддержки виртуальной памяти
- •Страничная виртуальная память
- •Сегментно-страничная организации виртуальной памяти
- •Структура таблицы страниц
- •Ассоциативная память
- •Инвертированная таблица страниц
- •Размер страницы
- •Заключение
- •10. Лекция: Аппаратно-независимый уровень управления виртуальной памятью
- •Исключительные ситуации при работе с памятью
- •Стратегии управления страничной памятью
- •Алгоритмы замещения страниц
- •Алгоритм fifo. Выталкивание первой пришедшей страницы
- •Аномалия Билэди (Belady)
- •Оптимальный алгоритм (opt)
- •Выталкивание дольше всего не использовавшейся страницы. Алгоритм lru
- •Выталкивание редко используемой страницы. Алгоритм nfu
- •Другие алгоритмы
- •Управление количеством страниц, выделенным процессу. Модель рабочего множества
- •Трешинг (Thrashing)
- •Модель рабочего множества
- •Страничные демоны
- •Программная поддержка сегментной модели памяти процесса
- •Отдельные аспекты функционирования менеджера памяти
- •Заключение
- •11. Лекция: Файлы с точки зрения пользователя Введение
- •Общие сведения о файлах Имена файлов
- •Типы файлов
- •Атрибуты файлов
- •Организация файлов и доступ к ним
- •Последовательный файл
- •Файл прямого доступа
- •Другие формы организации файлов
- •Операции над файлами
- •Директории. Логическая структура файлового архива
- •Разделы диска. Организация доступа к архиву файлов.
- •Операции над директориями
- •Защита файлов
- •Контроль доступа к файлам
- •Списки прав доступа
- •Заключение
- •12. Лекция: Реализация файловой системы
- •Общая структура файловой системы
- •Управление внешней памятью
- •Методы выделения дискового пространства
- •Выделение непрерывной последовательностью блоков
- •Связный список
- •Индексные узлы
- •Управление свободным и занятым дисковым пространством
- •Учет при помощи организации битового вектора
- •Учет при помощи организации связного списка
- •Размер блока
- •Структура файловой системы на диске
- •Монтирование файловых систем
- •Связывание файлов
- •Кооперация процессов при работе с файлами
- •Примеры разрешения коллизий и тупиковых ситуаций
- •Hадежность файловой системы
- •Целостность файловой системы
- •Порядок выполнения операций
- •Журнализация
- •Проверка целостности файловой системы при помощи утилит
- •Управление "плохими" блоками
- •Производительность файловой системы
- •Кэширование
- •Оптимальное размещение информации на диске
- •Реализация некоторых операций над файлами
- •Системные вызовы, работающие с символическим именем файла Системные вызовы, связывающие pathname с дескриптором файла
- •Связывание файла
- •Удаление файла
- •Системные вызовы, работающие с файловым дескриптором
- •Функции ввода-вывода из файла
- •Современные архитектуры файловых систем
- •Заключение
- •13. Лекция: Система управления вводом-выводом
- •Физические принципы организации ввода-вывода
- •Общие сведения об архитектуре компьютера
- •Структура контроллера устройства
- •Опрос устройств и прерывания. Исключительные ситуации и системные вызовы
- •Прямой доступ к памяти (Direct Memory Access – dma)
- •Логические принципы организации ввода-вывода
- •Структура системы ввода-вывода
- •Систематизация внешних устройств и интерфейс между базовой подсистемой ввода-вывода и драйверами
- •Функции базовой подсистемы ввода-вывода
- •Блокирующиеся, неблокирующиеся и асинхронные системные вызовы
- •Буферизация и кэширование
- •Spooling и захват устройств
- •Обработка прерываний и ошибок
- •Планирование запросов
- •Алгоритмы планирования запросов к жесткому диску
- •Строение жесткого диска и параметры планирования
- •Алгоритм First Come First Served (fcfs)
- •Алгоритм Short Seek Time First (sstf)
- •Алгоритмы сканирования (scan, c-scan, look, c-look)
- •Заключение
- •14. Лекция: Сети и сетевые операционные системы
- •Для чего компьютеры объединяют в сети
- •Сетевые и распределенные операционные системы
- •Взаимодействие удаленных процессов как основа работы вычислительных сетей
- •Основные вопросы логической организации передачи информации между удаленными процессами
- •Понятие протокола
- •Многоуровневая модель построения сетевых вычислительных систем
- •Проблемы адресации в сети
- •Одноуровневые адреса
- •Двухуровневые адреса
- •Удаленная адресация и разрешение адресов
- •Локальная адресация. Понятие порта
- •Полные адреса. Понятие сокета (socket)
- •Проблемы маршрутизации в сетях
- •Связь с установлением логического соединения и передача данных с помощью сообщений
- •Синхронизация удаленных процессов
- •Заключение
- •15. Лекция: Основные понятия информационной безопасности Введение
- •Угрозы безопасности
- •Формализация подхода к обеспечению информационной безопасности
- •Криптография как одна из базовых технологий безопасности ос
- •Шифрование с использованием алгоритма rsa
- •Теорема Эйлера
- •Заключение
- •16. Лекция: Защитные механизмы операционных систем
- •Идентификация и аутентификация
- •Пароли, уязвимость паролей
- •Шифрование пароля
- •Авторизация. Разграничение доступа к объектам ос
- •Домены безопасности
- •Матрица доступа
- •Список прав доступа. Access control list
- •Мандаты возможностей. Capability list
- •Другие способы контроля доступа
- •Смена домена
- •Недопустимость повторного использования объектов
- •Выявление вторжений. Аудит системы защиты
- •Анализ некоторых популярных ос с точки зрения их защищенности
- •NetWare, IntranetWare
- •Windows nt/2000/xp
- •Заключение
- •Список литературы
Гарантированное планирование
При интерактивной работе Nпользователей в вычислительной системе можно применить алгоритмпланирования, который гарантирует, что каждый из пользователей будет иметь в своем распоряжении~1/Nчасть процессорного времени. Пронумеруем всех пользователей от1доN. Для каждого пользователя с номеромiвведем две величины:Ti– время нахождения пользователя в системе или, другими словами, длительность сеанса его общения с машиной иτi– суммарное процессорное время уже выделенное всем его процессам в течение сеанса. Справедливым для пользователя было бы получениеTi/Nпроцессорного времени. Если
τi<<Ti/N
то i-й пользователь несправедливо обделен процессорным временем. Если же
τi>>Ti/N
то система явно благоволит к пользователю с номером i. Вычислим для процессов каждого пользователя значение коэффициента справедливости
τiN/Ti
и будем предоставлять очередной квант времениготовому процессу с наименьшей величиной этого отношения. Предложенный алгоритм называют алгоритмомгарантированного планирования. К недостаткам этого алгоритма можно отнести невозможность предугадать поведение пользователей. Если некоторый пользователь отправится на пару часов пообедать и поспать, не прерывая сеанса работы, то по возвращении его процессы будут получать неоправданно много процессорного времени.
Приоритетное планирование
Алгоритмы SJFигарантированного планированияпредставляют собой частные случаиприоритетного планирования. Приприоритетном планированиикаждому процессу присваивается определенное числовое значение –приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковымиприоритетамипланируются в порядкеFCFS. Дляалгоритма SJFв качестве такогоприоритета выступаетоценка продолжительности следующегоCPU burst. Чем меньше значение этой оценки, тем более высокийприоритетимеет процесс. Для алгоритмагарантированного планирования приоритетомслужит вычисленный коэффициент справедливости. Чем он меньше, тем больше у процессаприоритет.
Алгоритмы назначения приоритетовпроцессов могут опираться как на внутренние параметры, связанные с происходящим внутри вычислительной системы, так и на внешние по отношению к ней. К внутренним параметрам относятся различные количественные и качественные характеристики процесса такие как: ограничения по времени использования процессора, требования к размеру памяти, число открытых файлов и используемых устройств ввода-вывода, отношение средних продолжительностейI/O burstкCPU burstи т. д. Алгоритмы SJF и гарантированного планирования используют внутренние параметры. В качестве внешних параметров могут выступать важность процесса для достижения каких-либо целей, стоимость оплаченного процессорного времени и другие политические факторы. Высокий внешнийприоритетможет быть присвоен задаче лектора или того, кто заплатил $100 за работу в течение одного часа.
Планированиес использованиемприоритетовможет быть каквытесняющим, так иневытесняющим. Привытесняющем планированиипроцесс с более высокимприоритетом, появившийся в очереди готовых процессов, вытесняет исполняющийся процесс с более низкимприоритетом. В случаеневытесняющего планированияон просто становится в начало очереди готовых процессов. Давайте рассмотрим примеры использования различных режимовприоритетного планирования.
Пусть в очередь процессов, находящихся в состоянии готовность, поступают те же процессы, что и в примере для вытесняющего алгоритма SJF, только им дополнительно еще присвоеныприоритеты(см.табл. 3.8.). В вычислительных системах не существует определенного соглашения, какое значениеприоритета–1или4считать болееприоритетным. Во избежание путаницы, во всех наших примерах мы будем предполагать, что большее значение соответствует меньшемуприоритету, т. е. наиболееприоритетнымв нашем примере является процессp3, а наименееприоритетным– процессp0.
Таблица 3.8. | |||
Процесс |
Время появления в очереди |
Продолжительность очередного CPU burst |
Приоритет |
p0 |
0 |
6 |
4 |
p1 |
2 |
2 |
3 |
p2 |
6 |
7 |
2 |
p3 |
0 |
5 |
1 |
Как будут вести себя процессы при использовании невытесняющего приоритетного планирования? Первым для выполнения в момент времениt = 0выбирается процессp3, как обладающий наивысшимприоритетом. После его завершения в момент времениt = 5в очереди процессов, готовых к исполнению, окажутся два процессаp0иp1. Большийприоритетиз них у процессаp1, он и начнет выполняться (см.табл. 3.9.). Затем в момент времениt = 8для исполнения будет избран процессp2, и лишь потом – процессp0.
Таблица 3.9. | ||||||||||||||||||||
Время |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
p0 |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
И |
И |
И |
И |
И |
И |
p1 |
|
|
Г |
Г |
Г |
И |
И |
|
|
|
|
|
|
|
|
|
|
|
|
|
p2 |
|
|
|
|
|
|
Г |
И |
И |
И |
И |
И |
И |
И |
|
|
|
|
|
|
p3 |
И |
И |
И |
И |
И |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Иным будет предоставление процессора процессам в случае вытесняющего приоритетного планирования(см.табл. 3.10.). Первым, как и в предыдущем случае, начнет исполняться процессp3, а по его окончании – процессp1. Однако в момент времениt = 6он будет вытеснен процессомp2и продолжит свое выполнение только в момент времениt = 13. Последним, как и раньше, будет исполняться процессp0.
Таблица 3.10. | ||||||||||||||||||||
Время |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
p0 |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
И |
И |
И |
И |
И |
И |
p1 |
|
|
Г |
Г |
Г |
И |
Г |
Г |
Г |
Г |
Г |
Г |
Г |
И |
|
|
|
|
|
|
p2 |
|
|
|
|
|
|
И |
И |
И |
И |
И |
И |
И |
|
|
|
|
|
|
|
p3 |
И |
И |
И |
И |
И |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В рассмотренном выше примере приоритетыпроцессов с течением времени не изменялись. Такиеприоритетыпринято называть статическими. Механизмы статическойприоритетностилегко реализовать, и они сопряжены с относительно небольшими издержками на выбор наиболееприоритетногопроцесса. Однако статическиеприоритетыне реагируют на изменения ситуации в вычислительной системе, которые могут сделать желательной корректировку порядка исполнения процессов. Более гибкими являются динамическиеприоритеты процессов, изменяющие свои значения по ходу исполнения процессов. Начальное значение динамическогоприоритета, присвоенное процессу, действует в течение лишь короткого периода времени, после чего ему назначается новое, более подходящее значение. Изменение динамическогоприоритета процессаявляется единственной операцией над процессами, которую мы до сих пор не рассмотрели. Как правило, изменениеприоритета процессовпроводится согласованно с совершением каких-либо других операций: при рождении нового процесса, при разблокировке или блокировании процесса, по истечении определенногокванта времениили по завершении процесса. Примерами алгоритмов с динамическимиприоритетамиявляютсяалгоритм SJFи алгоритмгарантированного планирования. Схемы с динамической приоритетностью гораздо сложнее в реализации и связаны с большими издержками по сравнению со статическими схемами. Однако их использование предполагает, что эти издержки оправдываются улучшением работы системы.
Главная проблема приоритетного планированиязаключается в том, что при ненадлежащем выборе механизма назначения и измененияприоритетовнизкоприоритетные процессы могут не запускаться неопределенно долгое время. Обычно случается одно из двух. Или они все же дожидаются своей очереди на исполнение (в девять часов утра в воскресенье, когда все приличные программисты ложатся спать). Или вычислительную систему приходится выключать, и они теряются (при остановке IBM 7094 в Массачусетском технологическом институте в 1973 году были найдены процессы, запущенные в 1967 году и ни разу с тех пор не исполнявшиеся). Решение этой проблемы может быть достигнуто с помощью увеличения со временем значенияприоритета процесса, находящегося в состоянии готовность. Пусть изначально процессам присваиваютсяприоритетыот128до255. Каждый раз по истечении определенного промежутка времени значенияприоритетовготовых процессов уменьшаются на1. Процессу, побывавшему в состоянии исполнение, присваивается первоначальное значениеприоритета. Даже такая грубая схема гарантирует, что любому процессу в разумные сроки будет предоставлено право на исполнение.