Операционные системы

Джон фон Нейман (John Von Neumann)
EDVAC (Electronic Discrete Variable Computer —Электронный Компьютер Дискретных Переменных)
«Предварительный доклад о компьютере EDVAC» (A First Draft Report on the EDVAC)
Джон Мочли (John Mauchly) и Джон Преспер Эккерт (John Presper Eckert)
ENIAC (Electronic Numerical Integrator And Computer)
Компьютер фон Неймана
Историческая справка

Компьютер фон Неймана
Структура, основные компоненты компьютера фон Неймана
Принципы построения компьютера фон Неймана
1. Принцип двоичного кодирования
2. Принцип программного управления
3. Принцип хранимой программы

Оперативное запоминающее устройство
ОЗУ предназначено для хранения программы, выполняющейся в компьютере.
Тег — поле служебной информации.
Машинное слово — поле программно изменяемой информации.

Оперативное запоминающее устройство
Использование содержимого поля служебной информации
1. Контроль за целостностью данных
При записи слова в память контрольная сумма бит = 9 (1001b) ⇒ тег = 1.
Ошибки нет
При чтении машинного слова 16 бит вычисляется сумма бит = 9 (1001b) и сверяется со значением тега.
тег
Ошибка
При чтении машинного слова 16 бит вычисляется сумма бит = 8 (1000b), а тег = 1
Пример контроля за целостностью данных по четности
⇒
Сбой в работе ОЗУ
Ошибка не видна
При чтении машинного слова 16 бит вычисляется сумма бит = 7 (111b), и тег = 1
⇒
Ошибка будет не выявлена

Оперативное запоминающее устройство
Использование содержимого поля служебной информации
2. Контроль доступа к командам/данными
3. Контроль доступа к машинным типам данных

Оперативное запоминающее устройство
Время доступа (access time, taccess) — время между запросом на чтение слова из оперативной памяти и получением содержимого этого слова.
Длительность цикла памяти (cycle time, tcycle) — минимальное время между началом текущего и последующего обращения к памяти.
(tcycle>taccess)
Производительность оперативной памяти — скорость доступа процессора к данным, размещенным в ОЗУ.

Оперативное запоминающее устройство
К независимых банков памяти, где К = 2L.
L-разрядов
номер банка (0...2L-1)
Расслоение памяти

Оперативное запоминающее устройство
Расслоение памяти
. . .
Контроллер доступа к памяти
Последовательность адресов
i, i+1, i+2, ..., i+K–1
Контроллер банка №0
Контроллер банка №1
Контроллер банка №2
Контроллер банка №K–1
Сравнение времени доступа
Схема работы

Центральный процессор
Устройство управления (control unit) — координация выполнения команд.
Арифметико-логическое устройство (arithmetic/logic unit) —выполнение команд, арифметической или логической обработки операндов.
Регистровая память (register memory) — совокупность устройств памяти процессора - регистров.
Кэш-память (cache memory) — буферизация работы процессора с оперативной памятью.

Центральный процессор
Регистры общего назначения (РОН)
Специальные регистры:
счетчик команд (program counter)
указатель стека (stack pointer)
слово состояние процессора (processor status word)
.........................
Регистровая память

Центральный процессор
Рабочий цикл процессора
.…
да
Условие не выполняется
Передача управления
Логическая или арифметическая операция
Выборка команды по значению СчК, формирование адреса следующей команды:
СчК = СчК+1
Анализ кода операции
Вычисление адресов операндов и их значений
АЛУ
Выполнение команды
Анализ условия перехода
Вычисление исполнитель-ного адреса операнда Аперехода,
СчК = Аперехода

Центральный процессор
Кэш-память (cache memory) первого уровня (L1)
Обмен данными между кэшем и оперативной памятью осуществляется блоками фиксированного размера
Адресный тег блока — содержит служебную информацию о блоке (соответствие области ОЗУ, свободен/занят блок, …)
Нахождение данных в кэше – попадание (hit). Если искомых данных нет в кэше, то фиксируется промах (cache miss)
При возникновении промаха происходит обновление содержимого кэша — вытеснение. Стратегии вытеснения:
случайный выбор блока
вытеснение наименее «популярного» блока (LRU — Least-Recently Used)
5. Вытеснение кэша данных:
сквозное кэширование (write-through caching)
кэширование с обратной связью (write-back cache) — тег модификации (dirty bit )

Аппарат прерываний
Прерывание — событие в компьютере, при возникновении которого в процессоре происходит предопределенная последовательность действий.
Внутренние — инициируются схемами контроля работы процессора
Внешние — события, возникающие в компьютере в результате взаимодействия центрального процессора с внешними устройствами
Типы прерываний

Аппарат прерываний
Этап аппаратной обработки прерываний
Завершение текущей команды
Блокировка прерываний. Сохранение актуального состояния процессора
прерывание
Программный этап обработки прерывания

Аппарат прерываний
Программный этап обработки прерываний
…
да
нет
нет
Идентификация типа прерывания
короткое ?
обработка
Выход из прерывания: восстановление состояния процессора в точке прерывания, возврат, снятие блокировки прерываний
«Полное» сохранение регистров
фатальное?
да
Снятие блокировки прерывания
Снятие блокировки прерывания
Завершение обработки прерывания
Завершение прерванной программы

Внешние устройства

Внешние устройства
Внешние запоминающие устройства (ВЗУ)
Обмен данными:
записями фиксированного размера — блоками
записями произвольного размера
Доступ к данным:
операции чтения и записи (жесткий диск, CD-RW)
только операции чтения (CD-ROM, DVD-ROM, …)
Последовательного доступа:
Магнитная лента
Прямого доступа:
Магнитные диски
Магнитный барабан
Магнито-электронные ВЗУ прямого доступа

Устройство последовательного доступа
Магнитная лента
Маркер конца ленты
Маркер конца i-ой записи
Маркер начала i-ой записи
Маркер начала ленты
i-ая запись

Устройство прямого доступа
Магнитные диски
Условный цилиндр
головка
Операции, необходимые для начала чтения (позиционирования)
Установка головки на требуемую дорожку
Поворот для совмещения головки с началом сектора

Устройство прямого доступа
Магнитный барабан
Операции, необходимые для начала чтения (позиционирования)
Поворот для совмещения головки с началом сектора

обращение к внешнему устройству
Модели синхронизации при обмене с внешними устройствами
Синхронная организация обмена
завершение обмена с ВУ
возможность выполнения
процесса1
приостановка выполнения процесса, ожидание завершения обмена
завершение обработки прерывания
обработка прерывания
1 Примечание: процесс выполняется до возникновения следующего прерывания
Асинхронная организация обмена
обращение к внешнему устройству
обращение к внешнему устройству

ЦП:
Иерархия устройств хранения информации
РОН
КЭШ L2
ОЗУ
ВЗУ прямого доступа с внутренней кэш буферизации (оперативный доступ к данным)
ВЗУ прямого доступа без кэш буферизации
(оперативный доступ к данным)
ВЗУ долговременного хранения данных (архивы, резервные копии...)
КЭШ L1
Увеличение ёмкости
Увеличение времени доступа
Уменьшение скорости чтения/записи
Увеличение времени хранения информации

Аппаратная поддержка ОС
и систем программирования
Мультипрограммный режим — режим, при котором возможна организация переключения выполнения с одной программы на другую.
программа 1
t1
t2
t3
время обмена программы 1 (операции ввода/вывода)
программа 2
программа 3
программа 1
t

Аппарат защиты памяти
Специальный режим операционной системы (привилегированный режим или режим супервизора)
Аппарат прерываний (как минимум, прерывание по таймеру)
Базовая аппаратная поддержка мультипрограммного режима

Аппаратная поддержка программных систем и мультипрограммного режима
Проблемы:
Вложенные обращения к подпрограммам
Накладные расходы при смене обрабатываемой программы
Перемещаемость программы по ОЗУ
Фрагментация памяти

Перемещаемость программы по ОЗУ
Соответствие адресов, используемых в программе, области ОЗУ, в которой будет размещена данная программа
Загрузка и начало выполнения
ОЗУ
Буфер программ, ожидающих начала обработки

Фрагментация памяти
V1своб.
V2своб.
V3своб.
V4своб.
VKсвоб.
Буфер программ, ожидающих начала обработки
V1прог.
V2прог.
VLпрог.
Проблема фрагментации: Viпрог. > Vjсвоб. для ∀ i,j (несмотря на то, что ∃{i}:
) => деградация системы
Несмотря на то, что имеется достаточное количество места в памяти, разместить ни одну из программ не удаётся.

Виртуальная память. Базирование
Исходный текст программы
Транслятор
Объектный модуль
Библиотека объектных модулей, редактор внешних связей
Исполняемый модуль
Проблема – установление соответствия между программной адресацией и физической памятью
В исполняемом модуле используется программная (логическая или виртуальная) адресация

Виртуальная память. Базирование
Аппарат виртуальной памяти — аппаратные средства компьютера, обеспечивающие преобразование (установление соответствия) программных адресов, используемых в программе с адресами физической памяти, в которой размещена программа во время выполнения.
Базирование адресов — реализация одной из моделей аппарата виртуальной памяти.

Виртуальная память. Базирование
Аисп.прог.
Базирование адресов — решение проблемы перемещаемости программы по ОЗУ.
Абсолютный адрес
⇒ Аисп.физ. = Аисп.прог.
Относительный (адрес относительно начала программы)
⇒ Аисп.физ. = Аисп.прог. +

Виртуальная память. Базирование
Базирование адресов — отображение виртуального адресного пространства программы в физическую память «один в один».
Программное (виртуальное) адресное пространство
0
L -1
Физическая память

Виртуальная память. Страничная организация памяти
0-я страница
1-я страница
...
...
Страницы - блоки фиксированного размера. Размер страницы — 2k
номер страницы номер в странице
Количество страниц ограничено размером поля «номер страницы»
k k-1 0
Структура адреса

Виртуальная память. Страничная организация памяти
Аисп.вирт.
Таблица страниц
процессора
Аисп.физ.
Преобразование виртуального адреса в физический — замена номера виртуальной страницы на соответствующий номер физической страницы

Виртуальная память. Страничная организация памяти
Модельный пример организации страничной виртуальной памяти
нет
да
Аисп.вирт.
Номер виртуальной
страницы
Номер в странице
α0
α1
αi
αm-1
0:
1:
i:
m-1:
αi ≥ 0
i-ой виртуальной странице соответствует физическая страница с номером αi
Получаем физический адрес,
продолжение работы
Полученный виртуальный адрес не размещен в ОЗУ
Обращение в «чужую» память
Страница откачена в целях оптимизации использования ОЗУ
Прерывание «защита памяти»
Причина?
СТОП
Подкачка нужной страницы,
вычисление физического адреса, продолжение работы программы

Регистровые окна (Register windows)
Окно N–1
Окно 0
Окно 1
Виртуальные регистры
CWP — указатель текущего окна
(current window pointer)
SWP — указатель сохраненного окна
(saved window pointer)
Окно 0
Множество
физических регистров
0
K-1
Окно 1
Окно N–1
. . .
. . .