8-1-1

1. Архитектура операционных систем Лекция 1.8

АРХИТЕКТУРА
ОПЕРАЦИОННЫХ
СИСТЕМ
ЛЕКЦИЯ 1.8

2.

Схема
с динамическими разделами
ОС
0
P1
P5
время 10
P1
время 5
200 270
P3
время 16
P3
время 20
P3
время 11
P4P2
время
время
85
P4
время 4
400
650 700
950 1000
Очередь заданий
№
1
2
3
4
5
память
200
300
250
250
70
время
10
5
20
8
15
2

3.

Схема
с динамическими разделами
Стратегии размещения нового процесса
в памяти
Первый подходящий (first-fit). Процесс размещается в
первое подходящее по размеру пустое место
Наиболее подходящий (best-fit). Процесс размещается
в наименьшее подходящее по размеру пустое место
Наименее подходящий (worst-fit). Процесс размещается
в наибольшее пустое место
3

4.

Схема
с динамическими разделами
P1
время 5
ОС
0
200
P4
время 8
400
P3
время 16
650 700
950 1000
Очередь заданий
№
5
память
70
время
15
4

5.

Схема
с динамическими разделами
P1
время 5
ОС
0
200
P4
время 8
400
P3
время 15
650 700
950 1000
Внешняя фрагментация – невозможность
использования памяти, неиспользуемой
процессами, из-за ее раздробленности
Возможна и внутренняя фрагментация при
почти полном заполнении процессом пустого
фрагмента
5

6.

Схема
с динамическими разделами
Сборка мусора
ОС
0
P5
P4
200 270
400
MMU – БУП
CPU
Логический
адрес
520
P3
650 700 770
950 1000
Сегментный
регистр
+
Физический
адрес
Память
6

7.

Линейное
непрерывное отображение
0
100
Логическое
адресное
пространство
Физическое
адресное
пространство
N
N+100
7

8.

Линейное
кусочно-непрерывное отображение
Страничная организация памяти
Логическое
адресное
пространство
Page 0 Page 1 Page 2 Page 3 Page 4
Логический адрес =
Npage*size + offset
(Npage, offset)
Серый цвет – занятое место
Физическое
адресное
пространство
Таблица
страниц
Кадр 0 Кадр 1
Кадр 2 Кадр 3 Кадр 4
0
1
2
3
4
3
4
6
7
1
Кадр 5 Кадр 6 Кадр 7
Кадр 8
Физический адрес =
Nframe*size + offset
(Nfrаme, offset)
Npage -> Nframe
Свойственна внутренняя фрагментация
8

9.

Линейное
кусочно-непрерывное отображение
Страничная организация памяти
Логический адрес
page
CPU
offset
MMU
Таблица
страниц
атрибуты
кадр
Память
кадр
offset
9
Физический адрес

10.

Линейное
кусочно-непрерывное отображение
Сегментная организация памяти
Сегмент 1
Логическое
адресное
пространство
0
0
Серый цвет – занятое место
Сегмент 2
Сегмент 3
0
Логический адрес –
двумерный =
(Nseg, offset)
Физическое
адресное
пространство
Физический адрес линейный = физический адрес начала сегмента + offset
Свойственна внешняя фрагментация
10

11.

Линейное
кусочно-непрерывное отображение
Сегментная организация памяти
Максимальный размер сегмента
Логический
адрес
Nseg
CPU
Таблица
сегментов
Память
offset
адрес начала
размер
+
Физический адрес
11

12.

Линейное
кусочно-непрерывное отображение
Сегментная организация памяти
Максимальный размер сегмента
Логический
адрес
Nseg
CPU
offset
ошибка
нет
Таблица
сегментов
адрес начала
размер
Offset <=
размер
да
Память
Физический
адрес
+
12

13.

Линейное
кусочно-непрерывное отображение
Сегментно-страничная организация памяти
Максимальный размер сегмента
Логический
адрес
Offset
Page внутриOffset
сегмента
Nseg
CPU
Размер страницы
адрес
размер
Offset у сегмента
<= размер
да
нет
Таблица сегментов
кадр
ошибка
Физический адрес
Память
Кадр
Таблица страниц
Offset
13

14.

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

15.

Архитектурные средства поддержки виртуальной памяти
Очевидно, что невозможно создать полностью машинно-независимый компонент
управления виртуальной памятью.
Одним из достижений современных ОС является грамотное и эффективное
разделение средств управления виртуальной памятью на аппаратно-независимую и
аппаратно-зависимую части.
Страничная виртуальная память
Сегментно-страничная организации виртуальной памяти
Структура таблицы страниц
Ассоциативная память
Инвертированная таблица страниц
Размер страницы
15

16.

Пример
двухуровневой
таблицы
страниц
16

17.

Исключительные ситуации при работе с памятью
обслуживания исключительной ситуации (page fault);
• чтения (подкачки) страницы из вторичной памяти (иногда, при
недостатке места в основной памяти, необходимо вытолкнуть
одну из страниц из основной памяти во вторичную, то есть
осуществить замещение страницы);
• возобновления выполнения процесса, вызвавшего данный page
fault.
17

18.

Стратегии управления страничной памятью
Программное обеспечение подсистемы управления памятью
связано с реализацией следующих стратегий:
Стратегия выборки (fetch policy)
Существует два основных варианта выборки - по запросу и с
упреждением.
Стратегия размещения (placement policy)
Стратегия замещения (replacement policy)
18

19.

Алгоритмы замещения страниц
переместить в случае надобности ее содержимое во внешнюю
память;
• переписать в этот страничный кадр содержимое нужной виртуальной
страницы из внешней памяти;
• должным образом модифицировать необходимый элемент
соответствующей таблицы страниц;
• продолжить выполнение процесса, которому эта виртуальная
страница понадобилась.
19

20.

Алгоритм FIFO. Выталкивание первой пришедшей страницы
Аномалия Билэди (Belady)
Оптимальный алгоритм (OPT)
Выталкивание дольше всего не использовавшейся страницы.
Алгоритм LRU
Выталкивание редко используемой страницы. Алгоритм NFU
Другие алгоритмы
20

21.

Аномалия Билэди: (a) - FIFO с тремя страничными кадрами;
(b) - FIFO с четырьмя страничными кадрами
21

22.

Пример работы алгоритма LRU
22

23.

Управление количеством страниц, выделенным процессу.
Модель рабочего множества
Трешинг (Thrashing)
23

24.

Модель рабочего множества
Пример рабочего множества процесса
24

25.

Программная поддержка сегментной модели памяти
процесса
25

26.

Файлы с точки зрения пользователя
основные функции файловой системы.
1. Идентификация файлов.
2. Распределение внешней памяти между файлами.
3. Обеспечение надежности и отказоустойчивости.
4. Обеспечение защиты от несанкционированного доступа.
5. Обеспечение совместного доступа к файлам.
6. Обеспечение высокой производительности.
26

27.

Общие сведения о файлах
Имена файлов
Типы файлов
Атрибуты файлов
Организация файлов и доступ к ним
Последовательный файл
Файл прямого доступа
Другие формы организации файлов
27

28.

Файл как последовательность записей переменной длинны
28

29.

Пример организации индекса для последовательного файла
29

30.

Операции над файлами
Создание файла, не содержащего данных.
Удаление файла и освобождение занимаемого им дискового
пространства.
Открытие файла.
Закрытие файла.
Позиционирование.
Чтение данных из файла.
Запись данных в файл с текущей позиции.
30

31.

Директории. Логическая структура файлового архива
Директории
31

32.

Древовидная структура файловой системы
32

33.

Защита файлов
Информация в компьютерной системе должна быть защищена как от физического
разрушения (reliability), так и от несанкционированного доступа (protection).
Контроль доступа к файлам
Наличие в системе многих пользователей предполагает организацию
контролируемого доступа к файлам.
Списки прав доступа
список прав доступа (access control list).
Основная проблема реализации данного способа - список может быть длинным.
• Конструирование подобного списка может оказаться сложной задачей, особенно
если мы не знаем заранее пользователей системы.
• Запись в директории должна иметь переменный размер (включать список
потенциальных пользователей).
• Владелец (Owner).
• Группа (Group). Hабор пользователей, разделяющих файл и нуждающихся в
типовом способе доступа к нему.
33
• Остальные (Univers)

34.

Блок-схема файловой системы
34

35.

Хранение файла в виде связного списка дисковых
блоков
35

36.

Метод связного списка
с использованием таблицы в
оперативной памяти
36

37.

Структура индексного узла
37

38.

Примерная структура файловой
системы на диске
38

39.

В начале раздела находится суперблок, содержащий общее
описание файловой системы, например:
• тип файловой системы;
• размер файловой системы в блоках;
• размер массива индексных узлов;
• размер логического блока.
39

40.

Реализация директорий
40

41.

Вариант записи в директории MS-DOS
Вариант записи в директории Unix
41

42.

Две файловые системы до монтирования
42

43.

Общая файловая система после монтирования
43

44.

Примеры разрешения коллизий и тупиковых ситуаций
Логика работы системы в сложных ситуациях может проиллюстрировать особенности
организации мультидоступа.
Рассмотрим в качестве примера образование потенциального тупика при создании
связи (link), когда
разрешен совместный доступ к файлу [Bach].
Два процесса, выполняющие одновременно следующие функции:
процесс A: link("a/b/c/d","e/f/g");
процесс B: link("e/f","a/b/c/d/ee");
44

45.

Hадёжность файловой системы
Целостность файловой системы
Порядок выполнения операций
Журнализация
Управление "плохими" блоками
Производительность файловой системы
Кэширование
45

46.

Структура блочного кэша
46

47.

Системные вызовы, работающие с символическим
именем файла
Системные вызовы, связывающие pathname с дескриптором файла
Это функции создания и открытия файла. Например, в ОС Unix
fd = creat(pathname,modes);
fd = open(pathname,flags,modes);
47

48.

Структуры данных после открытия файлов
48

49.

Архитектура современной файловой системы
49

50.

50