- •1 Операционная система. Определение. Назначение. Функции ос.
- •2 История ос. Развитие операционных систем.
- •3 Классификация операционных систем.
- •4 Специальные регистры центрального процессора (счетчик команд, указатель стека, rsw)
- •5 Конвейерная и скалярная конструкция процессора
- •6 Устройство памяти. Виды памяти.
- •7 Базовый и предельный регистры. Диспетчер памяти.
- •8 Драйвера устройств ввода-вывода. Способы установки драйверов.
- •9 Три способа организации ввода-вывода.
- •10 Шины и их назначение.
- •11 Процесс. Характеристики процесса. Понятия, связанные с процессом (таблица процессов, оболочка и т.Д.)
- •12 Взаимоблокировки. Определение. Примеры.
- •13 Файловые системы. Определение. Понятия, связанные с файловыми системами.
- •14 Код защиты файлов в unix.
- •15 Оболочка. Определение. Командный интерпретатор unix.
- •16 Системные вызовы. Назначение, схема работы системного вызова.
- •17 Основные системные вызовы posix.
- •18 Системные вызовы для управления процессами. Работа, примеры.
- •19 Системные вызовы для управления файлами. Работа. Примеры.
- •20 Системные вызовы для управления каталогами. Работа. Примеры.
- •21 Системные вызовы в unix и windows сравнение.
- •22 Структура ос. Монолитные ос.
- •23 Многоуровневые ос.
- •24 Виртуальные машины.
- •25 Экзоядро. Модель клиент-сервер.
- •26 Многозадачность. Создание и завершение процесса.
- •27 Состояния процессов.
- •28 Последовательность обработки прерываний нижним уровнем ос.
- •29 Поток. Определение. Отличие потока от процесса. Примеры применения потоков.
- •30 Реализация потоков в пространстве пользователя и в ядре. Схема и отличия.
- •31 Всплывающие потоки. Проблемы при переводе программы из однопоточной в многопоточную.
- •32 Межпроцессорное взаимодействие. Состояние состязания. Примеры. 4 условия для эффективной совместной работы процессов.
- •33 Методы решения проблем межпроцессорного взаимодействия с активным ожиданием. Запрещение прерываний, переменные блокировки, строгое чередование.
- •34 Алгоритм Петерсона и команда tsl.
- •35 Примитивы межпроцессорного взаимодействия. Проблема производителя и потребителя.
- •36 Семафоры. Решение проблемы производителя и потребителя с помощью семафоров.
- •37 Мьютексы и мониторы.
- •38 Передача сообщений и барьеры.
- •40 Планирование. Назначение. Поведение процессов. Категории алгоритмов планирования.
- •41 Планирование в системах пакетной обработки: «Первым пришел – первым обслужен», «Кратчайшая задача – первая».
- •42 Алгоритмы планирования: Наименьшее оставшееся время выполнения, трехуровневое планирование.
- •43 Циклическое планирование и приоритетное планирование.
- •44 Алгоритмы планирования: «Самый короткий процесс – следующий», Гарантированное планирование, Лотерейное планирование.
- •45 Справедливое планирование и планирование в системах реального времени.
- •46 Выгружаемые и невыгружаемые ресурсы. Условия взаимоблокировки.
- •47 Моделирование взаимоблокировок.
- •48 Четыре стратегии избегания взаимоблокировок. Страусовый алгоритм.
- •49 Обнаружение взаимоблокировки при наличии одного ресурса каждого типа.
- •51 Выходы из взаимоблокировки. Траектории ресурсов.
- •52 Безопасные и небезопасные состояния. Алгоритм банкира. Предотвращение взаимоблокировок.
44 Алгоритмы планирования: «Самый короткий процесс – следующий», Гарантированное планирование, Лотерейное планирование.
Поскольку алгоритм « Кратчайшая задача — первая«» минимизирует среднее оборотное время в системах пакетной обработки, хотелось бы использовать его и в интерактивных системах. В известной степени это возможно. Интерактивные процессы чаше всего следуют схеме «ожидание команды, исполнение команды, ожидание команды, исполнение команды...» Если рассматривать выполнение каждой команды как отдельную задачу, можно минимизировать общее среднее время отклика, запуская первой самую короткую задачу. Единственная проблема состоит в том, чтобы понять, какой из ожидающих процессов самый короткий. Один из методов основывается на оценке длины процесса, базирующейся на предыдущем поведении процесса. При этом запускается процесс, у которого оцененное время самое маленькое. Метод оценки следующего значения серии через взвешенное среднее предыдущего значения и предыдущей оценки часто называют старением. Этот метод применим во многих ситуациях, где необходима оценка по предыдущим значениям. Проще всего реализовать старение при а - 1/2. На каждом шаге нужно всего лишь добавить к текущей оценке новое значение и разделить сумму пополам (сдвинув вправо на 1 бит).
Гарантированное планирование
Принципиально другим подходом к планированию является предоставление пользователям реальных обещаний и затем их выполнение. Вот одно обещание, которое легко произнести и легко выполнить: если вместе с вами процессором пользуются n пользователей, вам будет предоставлено 1 /n мощности процессора. И в системе с одним пользователем и п запущенными процессорами каждому достанется 1 /n циклов Процессора. Чтобы выполнить это обещание, система должна отслеживать распределение процессора между процессами с момента создания каждого процесса. Затем система рассчитывает количество ресурсов процессора, на которое процесс имеет право, например время с момента создания, деленное на п. Теперь можно сосчитать отношение времени, предоставленного процессу, к времени, на которое он имеет право.
Лотерейное планирование
Процессам раздаются "лотерейные билеты" на доступ к ресурсам. Планировщик может выбрать любой билет, случайным образом. Чем больше билетов у процесса, тем больше у него шансов захватить ресурс. (Если перефразировать Джорджа Оруэлла: «Все процессы равны, но некоторые равнее других».) Лотерейное планирование характеризуется несколькими интересными свойствами: Например, если при создании процессу достается несколько билетов, то уже в следующей лотерее его шансы на выигрыш пропорциональны количеству билетов (высокая отзывчивость). Взаимодействующие процессы могут при необходимости обмениваться билетами. Так, если клиентский процесс посылает сообщение серверному процессу и затем блокируется, он может передать все свои билеты серверному процессу, чтобы увеличить шанс запуска сервера. Когда серверный процесс заканчивает работу, он может вернуть все билеты обратно. В качестве примера можно привести видеосервер, на котором несколько процессов передают своим клиентам потоки видеоинформации с различной частотой кадров. Предположим, что процессы используют частоты 10, 20 и 25 кадров в секунду. Предоставив процессам соответственно 10,20 и 25 билетов, можно реализовать загрузку процессора в желаемой пропорции 10:20:25.