Тема 13. Стратегии замещения виртуальной памяти
Стратегии замещения
Оптимальная
Случайная
FIFO
LRU
LFU
NRU
«Второй шанс»
«Часы»
Оптимальная стратегия
Замена страницы, которая не понадобится дольше других
Оптимальность
Практическая нереализуемость
Случайное замещение
Каждая страница может быть замещена с равной вероятностью
Высокая скорость выбора
Непредсказуемость
FirstInFirstOut
Замена страницы, дольше всего находившейся в памяти
Простота
Очень вероятен неудачный выбор
LeastRecentlyUsed
Замена страницы, к которой дольше всего не было обращений
Повышение скорости работы процессов с временной локальностью
Требуется хранить очередь обращений
LeastFrequentlyUsed
Замена страницы, которая реже всего использовалась
Логичность
Требуется хранить количество обращений
NotRecentlyUsed
К PTE добавляются бит обращения и бит изменения
Все страницы делятся на 4 группы
Заменяется страница из наименее приоритетной группы
Более оптимальный, чем LFU
Хорошее приближение LRU
Малые накладные расходы
Уязвимость после сброса бита обращения
Второй шанс
FIFO с зацикливанием
При переходе в конец очереди снимается бит обращения
Если бит обращения == 0, то страница замещается
Оставление периодически используемых страниц в памяти
Экономия времени на оставлении изменённых страниц в памяти
Часы
Использование циклического буфера для FIFO
Если бит обращения == 0, то страница замещается
Снижение накладных расходов на поддержание очереди страниц
Замена дальней страницы
Построение графа использования страницами друг друга
Замещение страницы, к которой не было обращений, наиболее удалённой от страниц, к которым были обращения
Хорошее приближение оптимального алгоритма
Высокие накладные расходы
Задачи ядра
Обработка прерываний
Управление процессами и потоками
Обеспечение межпроцессного взаимодействия
Управление памятью
Управление вводом-выводом
Обеспечение защиты
Тема 13.Файловые системы
Определение
Оперативная (первичная) память не предназначена для:
постоянного хранения данных
хранения больших объёмов данных
Файл — структурированная именованная область вторичного устройства памяти
Файловая система — часть ОС, отвечающая за постоянное хранение больших объёмов данных на вторичных устройствах памяти
Задачи файловой системы
Управление файлами
Управление свободным пространством
Обеспечение совместного доступа к файлам
Защита
Способы доступа к файлу
Последовательный
Произвольный
Атрибуты файла
Основные атрибуты:
Имя
Размер
Флаги типа
Атрибуты безопасности:
Создатель
Владелец
Права доступа
Адресные атрибуты:
Том
Путь
Начальный адрес
Список выделенных блоков
Временные атрибуты:
Время создания
Время последнего изменения
Время последнего доступа
Работа с файлом
open(path, mode) ->fd # дескрипторфайла
read(fd, &data)
write(fd, &data)
append(fd, &data)
unlink(fd)
...
Файлы, отображаемые в память
Memory-mappedfiles (mmap)
Файл дополняет адресное пространство процесса
Не требуется использовать read()/write()
Проблема определения длины файла
Проблема синхронизации данных про совместном использовании файла
Проблема с отображением файлов большого размера
Каталоги
Каталог — средство организации файлов в группы
Виды каталожных систем:
Одноуровневые
Двухуровневые
Многоуровневые (иерархические)
Путь к файлу
Путь — последовательное перечисление имён каталогов через разделитель, позволяющее найти файл
Виды пути:
Абсолютный
Относительный
Вопросы реализации файловой системы
Структура ФС
Реализация файлов
Реализация каталогов
Совместное использование
Организация дискового пространства
Устойчивость к сбоям
Вариант структуры ФС – MBR
Master Boot Record (PC BIOS)
Вариант структуры ФС – GPT
GUID PartitionTable (EFI)
Вариант структуры ФС – LVM
LogicalVolumeManager
Реализация файлов
Непрерывное размещение
Связные списки
Таблица размещения файлов
i-узлы
Реализация каталогов
Проблема размещения атрибутов файлов
В самом каталоге
В i-узлах
Проблема хранения длинных имён
Фиксированный размер поля под имя
Символ-разделитель (заполнитель)
Выделение пространства в самом каталоге
Выделение пространства в «куче»
Совместное использование файлов
Жёсткие ссылки
Символические ссылки
Организация свободного пространства
Связный список блоков
Блок фиксированного размера
Блок произвольного размера
Битовая карта
i-узлы
Дисковые квоты
Механизм ограничения доступного пользователю дискового пространства
Мягкая квота
Жёсткая квота
Надёжность файловой системы
Обеспечение непротиворечивости служебных структур ФС
Обеспечение надёжного хранения данных пользователя
Причины потери данных
Отключение питания
Отказ аппаратного обеспечения
Программная ошибка
Аварийное завершение работы
Повреждение носителя
Невнимательность пользователя
Виды нарушения целостности структур ФС’
Неверный формат каталога
Конфликт свободных и занятых блоков
Несоответствие значения атрибута «размер» количеству выделенных блоков
Пересечение файлов
Потерянные блоки
Неправильное значение счётчика ссылок на i-узел
Повышение отказоустойчивости ФС
Журналирование
Резервирование носителя
Резервное копирование
Журналирование файловой системы
Журнал — структура, в которой регистрируются выполняемые операции
По завершении операции запись помечается как отработанная
При сбое операция откатывается
Резервирование носителя
RAID = Redundand Array of Independent (Inexpensive) Disks
RAID0 = Stripe
RAID1 = Mirroring
RAID5
RAID 1+0 (RAID10)
Резервное копирование
Полная копия
Дифференциальная копия
Инкрементная копия
Повышение производительности ФС
Кеширование данных
Упреждающее чтение (prefetch/readahead)
Дефрагментация
Оптимизация положения данных
Оптимизация дисциплины планирования запросов
Программная оптимизация
Аппаратная оптимизация