- •Информация о курсе
- •5. Тупики
- •6. Организация памяти компьютера. Схемы управления памятью.
- •7. Аппаратно-независимый уровень управления виртуальной памятью
- •1. Лекция: Введение
- •Что такое операционная система Структура вычислительной системы
- •Что такое ос
- •Операционная система как виртуальная машина
- •Операционная система как менеджер ресурсов
- •Операционная система как защитник пользователей и программ
- •Операционная система как постоянно функционирующее ядро
- •Краткая история эволюции вычислительных систем
- •Первый период (1945–1955 гг.). Ламповые машины. Операционных систем нет
- •Второй период (1955 г.–начало 60-х). Компьютеры на основе транзисторов. Пакетные операционные системы
- •Третий период (начало 60-х – 1980 г.). Компьютеры на основе интегральных микросхем. Первые многозадачные ос
- •Четвертый период (с 1980 г. По настоящее время). Персональные компьютеры. Классические, сетевые и распределенные системы
- •Основные понятия, концепции ос
- •Системные вызовы
- •Прерывания
- •Исключительные ситуации
- •Архитектурные особенности ос
- •Монолитное ядро
- •Многоуровневые системы (Layered systems)
- •Виртуальные машины
- •Микроядерная архитектура
- •Смешанные системы
- •Классификация ос
- •Реализация многозадачности
- •Поддержка многопользовательского режима
- •Многопроцессорная обработка
- •Системы реального времени
- •Заключение
- •Приложение 1. Некоторые сведения об архитектуре компьютера
- •Взаимодействие с периферийными устройствами
- •2. Лекция: Процессы
- •Понятие процесса
- •Состояния процесса
- •Операции над процессами и связанные с ними понятия Набор операций
- •Process Control Block и контекст процесса
- •Одноразовые операции
- •Многоразовые операции
- •Переключение контекста
- •Заключение
- •3. Лекция: Планирование процессов
- •Уровни планирования
- •Критерии планирования и требования к алгоритмам
- •Параметры планирования
- •Вытесняющее и невытесняющее планирование
- •Алгоритмы планирования
- •Гарантированное планирование
- •Приоритетное планирование
- •Многоуровневые очереди (Multilevel Queue)
- •Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)
- •Заключение
- •4. Лекция: Кооперация процессов. Алгоритмы синхронизации
- •Взаимодействующие процессы
- •Категории средств обмена информацией
- •Сигнальные
- •Канальные
- •Разделяемая память
- •Логическая организация механизма передачи информации
- •Как устанавливается связь?
- •Информационная валентность процессов и средств связи
- •Особенности передачи информации с помощью линий связи
- •Буферизация
- •Поток ввода/вывода и сообщения
- •Надежность средств связи
- •Как завершается связь?
- •Алгоритмы синхронизации
- •Interleaving, race condition и взаимоисключения
- •Достаточные условия Бернстайна
- •Механизмы синхронизации
- •Критическая секция
- •Алгоритмы организации взаимодействия процессов Требования, предъявляемые к алгоритмам
- •Запрет прерываний
- •Переменная-замок
- •Аппаратная поддержка взаимоисключений
- •Команда Test-and-Set (проверить и присвоить 1)
- •Команда Swap (обменять значения)
- •Заключение
- •5. Лекция: Тупики Введение
- •Условия возникновения тупиков
- •Основные направления борьбы с тупиками
- •Игнорирование проблемы тупиков
- •Способы предотвращения тупиков
- •Способы предотвращения тупиков путем тщательного распределения ресурсов. Алгоритм банкира
- •Предотвращение тупиков за счет нарушения условий возникновения тупиков
- •Нарушение условия взаимоисключения
- •Нарушение условия ожидания дополнительных ресурсов
- •Нарушение принципа отсутствия перераспределения
- •Hарушение условия кругового ожидания
- •Обнаружение тупиков
- •Восстановление после тупиков
- •Заключение
- •6. Лекция: Организация памяти компьютера. Простейшие схемы управления памятью Введение
- •Физическая организация памяти компьютера
- •Локальность
- •Логическая память
- •Связывание адресов
- •Функции системы управления памятью
- •Простейшие схемы управления памятью
- •Один процесс в памяти
- •Оверлейная структура
- •Динамическое распределение. Свопинг
- •Страничная память
- •Сегментная и сегментно-страничная организация памяти
- •Понятие виртуальной памяти
- •Архитектурные средства поддержки виртуальной памяти
- •Страничная виртуальная память
- •Сегментно-страничная организации виртуальной памяти
- •Структура таблицы страниц
- •Ассоциативная память
- •Инвертированная таблица страниц
- •Размер страницы
- •Заключение
- •7. Лекция: Аппаратно-независимый уровень управления виртуальной памятью
- •Исключительные ситуации при работе с памятью
- •Стратегии управления страничной памятью
- •Алгоритмы замещения страниц
- •Алгоритм fifo. Выталкивание первой пришедшей страницы
- •Аномалия Билэди (Belady)
- •Оптимальный алгоритм (opt)
- •Выталкивание дольше всего не использовавшейся страницы. Алгоритм lru
- •Выталкивание редко используемой страницы. Алгоритм nfu
- •Другие алгоритмы
- •Управление количеством страниц, выделенным процессу. Модель рабочего множества
- •Трешинг (Thrashing)
- •Модель рабочего множества
- •Страничные демоны
- •Заключение
Заключение
Для достижения поставленной цели различные процессы могут исполняться псевдопараллельно на одной вычислительной системе или параллельно на разных вычислительных системах, взаимодействуя между собой. Причинами для совместной деятельности процессов обычно являются: необходимость ускорения решения задачи, совместное использование обновляемых данных, удобство работы или модульный принцип построения программных комплексов. Процессы, которые влияют на поведение друг друга путем обмена информацией, называют кооперативными или взаимодействующими процессами, в отличие от независимых процессов, не оказывающих друг на друга никакого воздействия и ничего не знающих о взаимном существовании в вычислительной системе.
Для обеспечения корректного обмена информацией операционная система должна предоставить процессам специальные средства связи. По объему передаваемой информации и степени возможного воздействия на поведение процесса, получившего информацию, их можно разделить на три категории: сигнальные, канальные и разделяемую память. Через канальные средства коммуникации информация может передаваться в виде потока данных или в виде сообщений и накапливаться в буфере определенного размера. Для инициализации «общения» процессов и его прекращения могут потребоваться специальные действия со стороны операционной системы. Процессы, связываясь друг с другом, могут использовать непрямую, прямую симметричную и прямую асимметричную схемы адресации. Существуют одно- и двунаправленные средства передачи информации. Средства коммуникации обеспечивают надежную связь, если при общении процессов не происходит потери и повреждения информации, не появляется лишней информации, не нарушается порядок данных.
Последовательное выполнение некоторых действий, направленных на достижение определенной цели, называется активностью. Активности состоят из атомарных операций, выполняемых неразрывно, как единичное целое. При исполнении нескольких активностей в псевдопараллельном режиме атомарные операции различных активностей могут перемешиваться между собой с соблюдением порядка следования внутри активностей. Это явление получило название interleaving (чередование). Если результаты выполнения нескольких активностей не зависят от варианта чередования, то такой набор активностей называется детерминированным. В противном случае он носит название недетерминированного. Существует достаточное условие Бернстайна для определения детерминированности набора активностей, но оно накладывает очень жесткие ограничения на набор, требуя практически не взаимодействующих активностей. Про недетерминированный набор активностей говорят, что он имеет race condition (условие гонки, состязания). Устранение race condition возможно при ограничении допустимых вариантов чередований атомарных операций с помощью синхронизации поведения активностей. Участки активностей, выполнение которых может привести к race condition, называют критическими участками. Необходимым условием для устранения race condition является организация взаимоисключения на критических участках: внутри соответствующих критических участков не может одновременно находиться более одной активности.
Для эффективных программных алгоритмов устранения race condition помимо условия взаимоисключения требуется выполнение следующих условий: алгоритмы не используют специальных команд процессора для организации взаимоисключений, алгоритмы ничего не знают о скоростях выполнения процессов, алгоритмы удовлетворяют условиям прогресса и ограниченного ожидания.
Применение специальных команд процессора, выполняющих ряд действий как атомарную операцию, – Test-and-Set, Swap – позволяет существенно упростить алгоритмы синхронизации процессов.