- •1. Определение и функции ос. Классификация многозадачных ос. Принципиальные отличия требований к системам реального времени и к обычными системами разделения времени.
- •1 Вопрос. Определение и функции ос.
- •2 Вопрос. Три подхода к определению ос:
- •3 Вопрос. Классификация многозадачных ос
- •2. Ядро ос. Подходы к определению ядра ос (классический и по Василенко). Причины неоднозначности. Режим ядра и режим пользователя. Системный вызов и его реализация (на примере любой ос/архитектуры).
- •4 Вопрос. Подходы к определению ядра ос
- •7 Вопрос. Понятие процесса. Адресное пространство процесса
- •8 Вопрос. Контекст процесса. Регистровый контекст
- •9 Вопрос. Системный контекст
- •10 Вопрос. Контекст процесса.
- •Создание и завершение процесса
- •11 Вопрос. Создание и завершение процесса
- •12 Вопрос. Граф состояний процесса. Причины перехода между состояниями.
- •Все возможные причины блокировки процесса
- •4. Вытесняющая многозадачность. Цели алгоритма планирования и их противоречивость. Основные алгоритмы планирования и их модификации.
- •13 Вопрос. Вытесняющая многозадачность
- •14 Вопрос. Задачи алгоритмов планирования
- •15 Вопрос. Планирование в системах пакетной обработки данных
- •17 Вопрос. Наименьшее оставшееся время выполнения. Трехуровневое планирование
- •18 Вопрос. Планирование в интерактивных системах
- •19 Вопрос. Несколько очередей. "Самый короткий процесс - следующий"
- •20 Вопрос. Гарантированное планирование. Лотерейное планирование. Справедливое планирование
- •21 Вопрос. Планирование в системах реального времени
- •22 Вопрос. Иерархия классов в Linux: rt, cfs, idle, stats.
- •23 Вопрос. Реальные алгоритмы планирования
- •24 Вопрос. Проблема балансировки нагрузки в smp-системах
- •Область применения нитей и процессов.
- •Реализация потоков в ядре
- •7. Синхронизация процессов и нитей (в т.Ч. Ядерных). Основные примитивы синхронизации. Различия семафоров и спин-блокировки. Ограничения использования семафоров в ядре (сюда же can_sleep()).
- •25 Вопрос. Примитивы межпроцессного взаимодействия
- •Спин-блокировки:
- •26 Вопрос. Семафоры
- •27 Вопрос. Мьютексы
- •[Крищенко: метода sys_linux]
- •28 Вопрос. Виртуальная память
- •Задачи, решаемые виртуальной памятью:
- •Вопросы из лекций:
- •29 Вопрос. Страничная организация виртуальной памяти
- •30 Вопрос. Сегментная и сегментно-страничная организации виртуальной памяти
- •31 Вопрос. Преобразование виртуального адреса в физический при страничном преобразовании
- •32 Вопрос. Tlb и его назначение. Моменты сброса tlb.
- •Адресное пространство процесса
- •Разделы адресного пространства процесса (32 разряда)
- •Выделение памяти процессу и освобождение им памяти. Связь функций выделения памятью стандартной библиотеки и системных вызовов, необходимость менеджера памяти режима пользователя
- •11. Виды межпроцессного взаимодействия и их классификация. Виды ipc в стандартах posix. Использование сокетов tcp/ip при большом количестве соединений Методы межпроцессного взаимодействия.
- •Виды ipc в стандартах posix
- •Использование сокетов tcp/ip при большом количестве соединений
- •32 Вопрос. Ввод-вывод и обработка прерываний.
- •33 Вопрос. Первичная и отложенная обработка прерываний, необходимость такого разделения. Реализация отложенной обработки.
- •13. Планировщик ввода-вывода для дисковых устройств. Алгоритмы планирования ввода-вывода для дискового устройства. Буферизация запросов.
- •34 Вопрос. Структура системы ввода-вывода
- •35 Вопрос. Алгоритмы планирования
- •36 Вопрос. Механизм ввода-вывода
- •36. Вопрос. Дескрипторы очереди запросов. Дескриптор запроса. Процесс планирования ввода-вывода
- •Процесс планирования ввода-вывода
- •14. Подсистема виртуальной фс в ядре ос. Кеширование. Ввод-вывод и прямой доступ к памяти на примере дискового устройства. Необходимость в уровне буферов (на примере Линукс)
- •Основные структуры
- •Уровень виртуальной файловой системы
- •Менеджер ввода-вывода
- •Стратегии организации ввода-вывода:
- •Ещё заметка про уровень буфферов
- •37 Вопрос. Основные структуры файловой системы.
- •Задачи файловой системы (from wiki)
- •38 Вопрос. Различные подходы к организации структур фс
- •39 Вопрос. Неразрывные файлы
- •40 Вопрос. Связанные списки. Связанные списки с индексацией
- •Связанные списки с индексацией
- •41 Вопрос. Индексные узлы
- •42 Вопрос. Реализация простой фс (предлагаю на примере minix file system).
- •43 Вопрос. Битовые карты, индексные узлы в minix 3
- •Индексные узлы
- •44 Вопрос. Журналируемые фс.
- •45 Вопрос. Физическая организация fat
- •46 Вопрос. Физическая организация s5 и ufs
- •47 Вопрос. Поиск адреса файла по его символьному имени
- •49 Вопрос. Физическая организация ntfs
- •50 Вопрос. Первый отрезок mft
- •51 Вопрос. Структура файлов ntfs
- •52 Вопрос. Виды файлов в ntfs
- •53 Вопрос. Каталоги ntfs
- •54 Вопрос. Файловые операции
- •55 Вопрос. Открытие файла
- •56 Вопрос. Обмен данными с файлом
- •57 Вопрос. Блокировки файлов
- •58 Вопрос. Стандартные файлы ввода и вывода, перенаправление вывода
- •59 Вопрос. Контроль доступа к файлам
- •60 Вопрос. Механизм контроля доступа
- •61 Вопрос. Организация контроля доступа в ос unix
- •62 Вопрос. Организация контроля доступа в ос Windows nt
- •63 Вопрос. Разрешения на доступ к каталогам и файлам
- •64 Вопрос. Встроенные группы пользователей и их права
- •65 Вопрос. Выводы
- •16. Сетевая подсистема ос и её функции. Причины включения tcp/ip в ядро ос. Реализация сетевых файловых систем.
- •Реализация сетевых файловых систем
- •Таненбаум Файловая система nfs
- •17. Идея микроядра. Недостатки и достоинства концепции микроядра (см. Qnx, Hurd, Minix, использование Mach в Mac os X). Идея микроядра
- •Достоинства:
- •Недостатки:
- •Более подробно о микроядре на примерах:
- •18. Идея ос на базе jit-vm. Недостатки, достоинства, ограничения концепции (смотреть, например, Singularity)
- •20. Существующие стандарты на интерфейсы ос. Группа стандартов Posix. Достоинства и недостатки реализации нестандартных интерфейсов (на примере WinApi). Реализация интерфейсов "чужеродных" ос.
- •Основные идеи стандарта posix
- •Api операционных систем. Проблемы, связанные с многообразием api (статья Wikipedia: Интерфейс программирования приложений)
- •21. Графическая подсистема и её место в ос на примере x11/Cocoa/WinApi. Достоинства и недостатки различных подходов.
43 Вопрос. Битовые карты, индексные узлы в minix 3
MINIX 3 следит за свободными и занятыми индексными узлами и зонами при помощи двух битовых карт. Когда удаляется файл, несложно подсчитать, какой бит в битовой карте соответствует освободившемуся индексному узлу, и найти его при помощи обычного механизма кэширования. В найденном блоке бит, соответствующий освободившемуся индексному узлу, сбрасывается. Зоны освобождаются точно так же, только используется битовая карта зон. Логически, при создании файла файловая система должна последовательно просмотреть битовые карты, чтобы найти первый свободный индексный узел, который будет выделен новому файлу. Фактически же, хранящийся в памяти суперблок содержит поле, указывающее на следующий свободный индексный узел, поэтому требуется искать свободный индексный узел, начиная с этого положения (зачастую свободным оказывается следующий узел). Аналогичным образом, когда индексный узел освобождается, проверяется, есть ли перед ним другие свободные, и при необходимости обновляется значение указателя. Если оказалось, что все индексные узлы на диске заняты, процедура поиска указывает на 0-й элемент. Именно поэтому 0-й индексный узел не используется (другими словами, он является индикатором заполнения диска). (Когда программа mkfs создает новую файловую систему, она обнуляет индексный узел 0 и устанавливает младший бит в битовой карте, соответственно, файловая система никогда не пытается выделить этот блок.) Все, что только что было сказано для индексных узлов, относится и к зонам. Когда необходимо дисковое пространство, логически ищется первая свободная зона, начиная с начала, а чтобы избежать ненужного последовательного поиска, поддерживается указатель на первую свободную зону.
Индексные узлы
Схема индексного узла MINIX показана на рис. 5.31. Она практически совпадает со строением индексного узла в UNIX. Имеются девять 32-разрядных указателей на зоны диска, из которых семь прямых и два косвенных. В MINIX 3 индексный узел занимает 64 байта, как и в стандартной системе UNIX, поэтому остается место для дополнительного десятого указателя (тройного уровня косвенности), хотя в текущей версии файловой системы он не поддерживается. Время последнего доступа, модификации и изменения индексного узла в MINIX 3 хранятся стандартным образом, как в UNIX. Последний из этих параметров обновляется практически при каждой операции, за исключением чтения файла.
К огда файл открывается, его индексный узел считывается в память и помещается в таблицу индексных узлов, где остается до закрытия файла. Записи в этой таблице имеют несколько дополнительных полей, которых нет на диске. Например, благодаря номеру индексного узла и номеру устройства, откуда он считан, файловая система знает, куда перезаписать индексный узел, если он изменен в памяти. Кроме того, у каждого индексного узла имеется счетчик. Если файл открывается дважды, вторая копия индексного узла в память не копируется, вместо этого увеличивается на единицу значение счетчика. При закрытии файла счетчик декрементируется, и только тогда, когда он достигает нуля, индексный узел удаляется из таблицы в памяти. Если за время нахождения в памяти он был изменен, он записывается на диск.
Главное предназначение индексного узла в том, чтобы хранить сведения о положении блоков файла на диске.
Cтруктуру, представленную на рис. 5.31, можно изменять для различных целей. Пример, используемый в MINIX 3, — индексные узлы для блочных и символьных устройств, которым не нужны указатели зон, так как не требуется ссылаться на области данных диска. Главный и вспомогательный номера устройств хранятся в пространстве нулевой зоны. Индексный узел также можно использовать для хранения данных небольшого файла (непосредственного файла), хотя эта возможность в MINIX 3 не реализована.
Для повышения производительности файловой системы в MINIX 3 применяется кэширование блоков