Управление памятью компьютера. Простые схемы управления памятью

1.

Управление памятью
Простые схемы управления
памятью
Лекция 12,13
2020

2.

Управление памятью
Иерархия памяти
Стоимость
одного бита
Регистры
Время доступа
Объем
Кэш
Оперативная память
Управляется менеджером памяти
Вторичная память
Управляется ОС

3.

Управление памятью
Принцип локальности
Большинство реальных программ в течение некоторого
отрезка времени работает с небольшим набором
адресов памяти – это принцип локальности
Принцип локальности связан с особенностями
человеческого мышления

4.

Управление памятью
Проблема разрешения адресов
Человеку свойственно символическое мышление. Адреса
(имена) переменных описываются идентификаторами,
формируя символьное адресное пространство
Как ?
Когда ?
Оперативная физическая память может быть представлена
в виде массива ячеек с линейными адресами
Совокупность всех доступных физических адресов в
вычислительной системе – это ее физическое адресное
пространство

5.

Управление памятью
Связывание адресов
Этап
компиляции
Другие
объектные
модули
Исходная
программа
Компилятор
Объектный
модуль
Редактор
связей
Динамически
загружаемые
библиотеки
Процессор
и БУП
Двоичный
образ
в памяти
Загрузчик
Этап
выполнения
Этап
загрузки
Загрузочный
модуль
Системные
библиотеки

6.

Управление памятью
Логическое адресное пространство
Символьное адресное пространство – совокупность всех
допустимых идентификаторов переменных
Логическое адресное пространство – совокупность всех
допустимых адресов, с которыми работает процессор
Физическое адресное пространство – совокупность всех
доступных физических адресов в вычислительной системе

7.

Управление памятью
Функции ОС и hardware
1. Отображение логического адресного пространства
процесса на физическое адресное пространство
2. Распределение памяти между конкурирующими
процессами
3. Контроль доступа к адресным пространствам процессов
4. Выгрузка процессов (целиком или частично) во внешнюю
память
5. Учет свободной и занятой памяти

8.

Простые схемы управления памятью
Однопрограммная система
0
ОС
Процесс
пользователя
Процесс
пользователя
ОС
max

9.

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

10.

Простые схемы управления памятью
Фиксированные разделы
0
Очереди заданий
ОС
Раздел 1
Раздел 2
1
2
3
Раздел 3
max

11.

Простые схемы управления памятью
Фиксированные разделы
Очередь заданий
0
ОС
Задание 1
Раздел 1
Раздел 2
Раздел 3
max
Процесс 1
Процесс 3
Процесс 2
3адание 2
Задание 3
Задание 4

12.

Простые схемы управления памятью
Фиксированные разделы
0
ОС
Раздел 1
Раздел 2
Раздел 3
max
Процесс 1
Процесс 3
Внутренняя фрагментация –
«потеря» части памяти, выделенной
процессу, но не используемой им
Процесс 2
Задание 4

13.

Простые схемы управления памятью
Динамические разделы
Память
P1
время 10
ОС
0
200
P2
время 5
400
P3
время 20
950 1000
700
Очередь заданий
№
1
2
3
4
5
память
200
300
250
250
70
время
10
5
20
8
15

14.

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

15.

Простые схемы управления памятью
Динамические разделы
Память
ОС
0
200 270
P3
время 11
P4
время 4
P5
400
650 700
950 1000
Очередь заданий
№
5
память
70
время
15

16.

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

17.

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

18.

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

19.

Простые схемы управления памятью
Динамические разделы
Сборка мусора
P1
время 5
ОС
0
200
P3 P3
P5
время
время
16 16
P4
время 8
400
650 700
900 950
970 1000
Очередь заданий
№
5
память
70
время
15

20.

Простые схемы управления памятью
Динамические разделы
Сборка мусора
P1
время 5
ОС
0
200
P3 P3
P5
время
время
16 16
P4
время 8
400
650
900
970 1000
Сегментный
регистр
CPU
Логический
адрес
+
Физический
адрес
БУП (MMU)
Память

21.

Простые схемы управления памятью
Динамические разделы
Память
ОС
0
P1
200
P3
P4
P4
400
698 700
950 1000
Возможна и внутренняя фрагментация при почти
полном заполнении процессом пустого
фрагмента

22.

Простые схемы управления памятью
Линейное непрерывное отображение
Логическое
адресное
пространство
0
100
Физическое
адресное
пространство
N
N+100

23.

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

24.

Кусочно-непрерывное отображение
Страничная организация памяти
Логический адрес
Процессор
Npage
offset
MMU (БУП)
Таблица
страниц
Nframe
Атрибуты (биты
управления
доступом)
Память
Nframe
offset
Физический адрес

25.

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

26.

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

27.

Кусочно-непрерывное отображение
Сегментная организация памяти
Максимальный размер сегмента
Логический адрес
Процессор
MMU (БУП)
Nseg
Таблица
сегментов
Память
Адрес начала
+
Физический адрес
offset
да
Размер
Атрибуты (биты
управления
доступом)
offset <=
Размер?
нет
Ошибка

28.

Кусочно-непрерывное отображение
Сегментно-страничная организация
Сегмент 0
Логическое
адресное
пространство
p1
p0
Сегмент 1
p0
p2
0
Физическое
адресное
пространство
Таблица
сегментов
p2
p3
p4
0
к0
к2
к1
к3
(Nseg, Np, poffset)
к4
к5
к6
к7
к8
к10 к11 к12 к13 к14 к15
к9
0
L1
L0
0
Таблицы
страниц
p1
Логический адрес –
двумерный =
(Nseg, soffset)
soffset = Np*size+poffset
0
1
2
0
1
1
1
6
4
5
8
Сегмент 0
2
3
4
9
10
11
Физический адрес –
линейный =
Nframe*size + offset
Сегмент 1
(Nseg, Np) -> Nframe
(Nframe, offset)

29.

Кусочно-непрерывное отображение
Сегментно-страничная организация
Максимальный размер сегмента
Логический адрес
Процессор
Nseg
Soffset
Npage Soffset
Poffset
Адрес
Размер
Soffset в сегменте
<= размер ?
Размер страницы
да
Таблица страниц
Nframe
Таблица сегментов
нет
Ошибка
Nframe
Nframe
Физический адрес
Память
Nframe
offset

30.

Кусочно-непрерывное отображение
Многоуровневая таблица страниц
Логическое адресное
пространство
процесса
Page 0 Page 1 Page 2 Page 3
0
Таблица страниц
процесса
Физическое
адресное
пространство
1
4
2
5
3
7
1
Кадр 0 Кадр 1 Кадр 2 Кадр 3 Кадр 4 Кадр 5 Кадр 6 Кадр 7
Таблица страниц процесса располагается в физическом адресном
пространстве.
При больших размерах таблицы страниц её размещение в
последовательных кадрах памяти проблематично.

31.

Кусочно-непрерывное отображение
Многоуровневая таблица страниц
Таблица страниц
процесса (page table)
Таблица страниц для
таблицы страниц
процесса
Физическое
адресное
пространство
Page 0 Page 1 Page 2 Page 3
0
1
1
2
4
3
5
2
Кадр 0 Кадр 1 Кадр 2 Кадр 3 Кадр 4 Кадр 5 Кадр 6 Кадр 7
Возникает двухуровневая таблица страниц.

32.

Кусочно-непрерывное отображение
Многоуровневая таблица страниц
p1
Esize
Таблица страниц
процесса (page table)
Лог. адрес процесса = (p, d)
p2
p
p = p1*Esize + p2
p1
Таблица страниц для
таблицы страниц
процесса
Физическое
адресное
пространство
p2
d
При двухуровневой организации таблицы страниц логический адрес
процесса описывается тройкой (p1, p2, d)
p1 p
p2
d

33.

Кусочно-непрерывное отображение
Ассоциативная память (TLB)
Логический адрес
Процессор
page
offset
page
кадр
…
…
Т
а
б
л
и
ц
а
TLB
Память
Кадр
offset
Физический адрес
с
т
р
а
н
и
ц

34.

Кусочно-непрерывное отображение
Ассоциативная память (TLB)
Расчет среднего времени доступа к данному
Обозначения:
t0 – среднее время доступа к оперативной памяти
t1 – среднее время доступа к TLB
h – вероятность наличия информации в TLB (hit ratio)
Среднее время доступа к данному при
двухуровневой страничной схеме – это:
T = t1 + h*t0 + (1-h)*3t0