Использование хеш-таблиц.

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

Еще одним решением, позволяющим снизить размер таблицы страниц, является модель использования т.н. инвертированных таблиц страниц (Рис. 129.). Главной сложностью данного решения является требование к процессору на аппаратном уровне работать с идентификаторами процессов (их PID). Примерами таких процессоров могут служить процессоры из линеек SPARC и PowerPC.

129. Содержание

     • Содержание
     • 1 Введение 5
     • 2 Управление процессами 87
     • 3 Реализация межпроцессного взаимодействия в ос Unix 114
     • 4 Файловые системы 152
     • 4.1 Основные концепции 152
     • 5 Управление оперативной памятью 181
     • 6 Управление внешними устройствами 196
     • Введение
     • Пакетная обработка заданий.
     • Развитие языков и систем программирования.
     • Этапы эволюции.
     • Основы архитектуры вычислительной системы
     • Структура вс
     • Структура вычислительной системы.
     • Аппаратный уровень вс
     • Управление физическими ресурсами вс
     • Пример зависимости от драйвера.
     • Управление логическими/виртуальными ресурсами
     • Системы программирования
     • Этапы проектирования.
     • Кодирование.
     • Тестирование.
     • Каскадная модель.
     • Каскадная итерационная модель.
     • Спиральная модель.
     • Прикладные системы
     • Первый этап развития прикладных систем.
     • Второй этап развития прикладных систем.
     • Третий этап развития прикладных систем.
     • Пакет программ Microsoft Office.
     • Пакет MathCad.
     • Система BaaN.
     • Выводы, литература
     • Структура организации вычислительной системы.
     • Основы компьютерной архитектуры
     • Структура, основные компоненты
     • Структура компьютера фон Неймана.
     • Базовая архитектура современных компьютеров.
     • Оперативное запоминающее устройство
     • Ячейка памяти.
     • Контроль четности.
     • Озу без расслоения памяти — один контроллер на все банки.
     • Озу с расслоением памяти — каждый банк обслуживает отдельный контроллер.
     • Центральный процессор
     • Структура организации центрального процессора.
     • Регистровая память
     • Устройство управления. Арифметико-логическое устройство
     • Общая схема работы кэШа.
     • Аппарат прерываний
     • Использование иерархической модели регистров прерывания.
     • Использование вектора прерываний.
     • Этап программной обработки прерываний.
     • Внешние устройства
     • Внешние устройства.
     • Внешние запоминающие устройства
     • Магнитная лента.
     • Принцип устройства магнитного диска.
     • Принцип устройства магнитного барабана.
     • Принцип устройства памяти на магнитных доменах.
     • Модели синхронизации при обмене с внешними устройствами
     • Синхронная и асинхронная работа с ву.
     • Потоки данных. Организация управления внешними устройствами
     • Непосредственное управление центральным процессором внешнего устройства.
     • Синхронное/асинхронное управление внешними устройствами с использованием контроллеров внешних устройств.
     • Использование контроллера прямого доступа к памяти (dma) или процессора (канала) ввода-вывода при обмене.
     • Иерархия памяти
     • Иерархия памяти.
     • Аппаратная поддержка операционной системы и систем программирования
     • Требования к аппаратуре для поддержки мультипрограммного режима
     • Мультипрограммный режим.
     • Проблемы, возникающие при исполнении программ
     • Вложенные обращения к подпрограммам.
     • Перемещаемость программы по озу.
     • Фрагментация памяти.
     • Регистровые окна
     • Регистровые окна.
     • Регистровые окна. Вход и выход из подпрограммы.
     • Системный стек
     • Системный стек.
     • Виртуальная память
     • Страничная организация памяти.
     • Страничная организация памяти. Преобразование виртуального адреса в физический.
     • Страничная организация памяти. Схема преобразования адресов.
     • Многомашинные, многопроцессорные ассоциации
     • Классификация мкмд.
     • Numa-система.
     • Терминальные комплексы (тк)
     • Терминальные комплексы.
     • Компьютерные сети
     • Компьютерные сети.
     • Организация сетевого взаимодействия. Эталонная модель iso/osi
     • Модель организации взаимодействия в сети iso/osi.
     • Логическое взаимодействие сетевых устройств по I-ому протоколу.
     • Семейство протоколов tcp/ip. Соответствие модели iso/osi
     • Семейство протоколов tcp/ip.
     • Взаимодействие между уровнями протоколов tcp/ip.
     • Система адресации протокола ip.
     • Маршрутизация дейтаграмм.
     • Основы архитектуры операционных систем
     • Структура ос
     • Структурная организация ос.
     • Структура ос с монолитным ядром.
     • Структура ос с микроядерной архитектурой.
     • Логические функции ос
     • Типы операционных систем
     • Структура сетевой ос.
     • Структура распределенной ос.
     • Управление процессами
     • Основные концепции
     • Модели операционных систем
     • Типы процессов
     • Типы процессов: однонитевая (а) и многонитевая (б) организации.
     • Контекст процесса
     • Реализация процессов в ос Unix
     • Процесс ос Unix
     • Разделение сегмента кода.
     • Базовые средства управления процессами в ос Unix
     • Пример использования системного вызова fork().
     • Пример использования системного вызова execl().
     • Пример использования схемы fork-exec.
     • Жизненный цикл процесса. Состояния процесса
     • Жизненный цикл процессов.
     • Формирование процессов 0 и 1
     • Формирование нулевого и первого процессов.
     • Инициализация системы.
     • Планирование
     • Взаимодействие процессов
     • Разделяемые ресурсы и синхронизация доступа к ним
     • Гонка процессов.
     • Пример тупиковой ситуации (deadlock).
     • Способы организации взаимного исключения
     • Пример двоичного семафора.
     • Классические задачи синхронизации процессов
     • Обещающие философы.
     • Реализация межпроцессного взаимодействия в ос Unix
     • Базовые средства реализации взаимодействия процессов в ос Unix
     • Способы организации взаимодействия процессов.
     • Сигналы
     • Неименованные каналы
     • Именованные каналы
     • Модель межпроцессного взаимодействия «главный–подчиненный»
     • Общая схема трассировки процессов.
     • Система межпроцессного взаимодействия ipc (Inter-Process Communication)
     • Очередь сообщений ipc
     • Очередь сообщений ipc.
     • 0666 Определяет права доступа */
     • Разделяемая память ipc
     • Массив семафоров ipc
     • Int val; /* значение одного семафора */
     • Сокеты — унифицированный интерфейс программирования распределенных систем
     • Файловые системы
     • Основные концепции
     • Структурная организация файлов
     • Атрибуты файлов
     • Основные правила работы с файлами. Типовые программные интерфейсы
     • Модель одноуровневой файловой системы.
     • Модель двухуровневой файловой системы.
     • Модель иерархической файловой системы.
     • Подходы в практической реализации файловой системы
     • Структура «системного» диска.
     • Модели реализации файлов
     • Модель непрерывных файлов.
     • Модель файлов, имеющих организацию связанного списка.
     • Модели реализации каталогов
     • Модели организации каталогов.
     • Соответствие имени файла и его содержимого
     • Пример жесткой связи.
     • Пример символической связи.
     • Координация использования пространства внешней памяти
     • Квотирование пространства файловой системы
     • Квотирование пространства файловой системы.
     • Надежность файловой системы
     • Проверка целостности файловой системы
     • Проверка целостности файловой системы. Непротиворечивость файловой системы соблюдена.
     • Проверка целостности файловой системы. Зафиксирована пропажа блока.
     • Проверка целостности файловой системы. Зафиксировано дублирование свободного блока.
     • Проверка целостности файловой системы. Зафиксировано дублирование занятого блока.
     • Проверка целостности файловой системы. Контроль жестких связей.
     • Примеры реализаций файловых систем
     • Организация файловой системы ос Unix. Виды файлов. Права доступа
     • Логическая структура каталогов
     • Логическая структура каталогов.
     • Внутренняя организация файловой системы: модель версии System V
     • Структура файловой системы версии System V.
     • Работа с массивами номеров свободных блоков
     • Работа с массивами номеров свободных блоков.
     • Работа с массивом свободных индексных дескрипторов
     • Индексные дескрипторы. Адресация блоков файла
     • Индексные дескрипторы.
     • Адресация блоков файла.
     • Файл-каталог
     • Файл-каталог.
     • Установление связей.
     • Достоинства и недостатки файловой системы модели System V
     • Внутренняя организация файловой системы: модель версии Fast File System (ffs) bsd
     • Структура файловой системы версии ffs bsd.
     • Стратегии размещения
     • Стратегия размещения последовательных блоков файлов.
     • Внутренняя организация блоков
     • Внутренняя организация блоков (блоки выровнены по кратности).
     • Выделение пространства для файла
     • Выделение пространства для файла.
     • Структура каталога ffs
     • Структура каталога ffs bsd.
     • Блокировка доступа к содержимому файла
     • Управление оперативной памятью
     • Одиночное непрерывное распределение
     • Одиночное непрерывное распределение.
     • Распределение неперемещаемыми разделами
     • Распределение неперемещаемыми разделами.
     • Распределение перемещаемыми разделами
     • Распределение перемещаемыми разделами.
     • Страничное распределение
     • Страничное распределение.
     • Иерархическая организация таблицы страниц.
     • Использование хеш-таблиц.
     • Инвертированные таблицы страниц.
     • Замещение страниц. Алгоритм «Часы».
     • Сегментное распределение
     • Сегментное распределение.
     • Сегментно-страничное распределение
     • Сегментно-страничное распределение. Упрощенная модель Intel.
     • Управление внешними устройствами
     • Общие концепции
     • Архитектура организации управления внешними устройствами
     • Модели управления внешними устройствами: непосредственное (а), синхронное/асинхронное (б), с использованием контроллера прямого доступа или процессора (канала) ввода-вывода.
     • Программное управление внешними устройствами
     • Иерархия архитектуры программного управления внешними устройствами.
     • Планирование дисковых обменов
     • Планирование дисковых обменов. Модель fifo.
     • Планирование дисковых обменов. Модель lifo.
     • Планирование дисковых обменов. Модель sstf.
     • Raid 2. Избыточность с кодами Хэмминга (Hamming, исправляет одинарные и выявляет двойные ошибки).
     • Raid 3. Четность с чередующимися битами.
     • Raid 5. Распределенная четность (циклическое распределение четности).
     • Работа с внешними устройствами в ос Unix
     • Файлы устройств, драйверы
     • Системные таблицы драйверов устройств
     • Ситуации, вызывающие обращение к функциям драйвера
     • Включение, удаление драйверов из системы
     • Организация обмена данными с файлами
     • Организация обмена данными с файлами.
     • Буферизация при блок-ориентированном обмене
     • Борьба со сбоями