49304 (Управление оперативной памятью), страница 3

Отметим, что случай ЛАП<ФАП возможен, если устройство управления памятью обеспечивает размер слова, больший чем 18 бит. На ЭВМ серии PDP-11/70 ЛАП каждого пользователя ограничено 64К байт, в то время как УУП поддерживает 128К слов. В ЭВМ серии VAX-11/780 фирмы DEC адресное пространство каждого пользователя составляет 2³², а максимальный физический размер основной памяти может достигать 16М байт. В ЭВМ серии VAX-11/780 используется 32-бит слово, имеющее следующую конструкцию:

где биты 31 и 30 имеют специальное назначение для;VAX/VMS;биты 29 - 9 адресуются к одной из 2²⁰страниц;биты 7 - 0 выбирают один из 512 байт в странице.

На ЭВМ, имеющей 16-бит размер слова, большой виртуальный адрес может быть составлен из двух слов. Он может иметь, например, такой вид:

Роль таблицы страниц. Одним из достоинств страничной организации является динамическое распределение страниц пользователя в любом месте памяти. Так, страница Р процесса

Рис. 3.Отображение страницы на основную память.

Виртуальный адрес = (р,i). Физический адрес - x = размер страницы + i. Отрицательное значение идентификатора рамки страницы указывает на то, что страница в данный момент отсутствует в памяти

пользователя может в некоторый момент занимать страничную рамку р в физической памяти. Поскольку у каждого из пользователей имеется свой набор страниц, каждой программе необходима карта, отображающая взаимосвязь между страницами и рамками страниц. На рис. 1 виртуальный адрес (p, i) преобразовывается в физический, поиском в таблице страниц идентификатора х для рамки страницы. Реальный адрес образуется умножением х на размер страницы и прибавлением к полученному результату индекса i.

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

Рис. 3. Обобщенная процедура страничного обмена. Блок # - это адрес рамки страницы в основной памяти (поэтому умножения на размер страницы не требуется).

Например, предположим, что УУП располагает пространством для 16 карт памяти, а каждая карта памяти содержит поля (элементы) для 64 страниц по 512 слов в каждой. Карта с номером 0 всегда принадлежит ядру операционной системы. Такой подход не может быть реализован для систем с большим объемом виртуальной памяти, так как стоимость УУП будет чрезмерно большой. В этом случае карта остается в основной памяти, а УУП управляет текущей картой пользователя с помощью указателей. На рис.2 приведена структура, соответствующая такой схеме.

По этой схеме УУП поддерживает список адресов таблиц для n пользователей. Аппаратно реализованный регистр служит для указания текущего пользователя, т.е. пользователя, чья таблица страниц является в настоящий момент активной. Элемент таблицы, содержащий карту пользователя (в УУП), загружается в аппаратный регистр базы таблицы страниц. Каждый адрес памяти содержит идентификатор страницы и индекс. Идентификатор страницы в комбинации с содержимым базового регистра таблицы страниц указывает на элемент таблицы страниц. Содержимым этого элемента является адрес рамки страницы в памяти. Добавляя индекс к адресу рамки страницы, мы получаем физический адрес.

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

Контрольные биты страниц. С каждым элементом таблицы связывается набор контрольных битов. Эти биты служат для указания стратегии управления страницами. Количество и тип этих битов определяются примененным УУП. Биты, приведенные ниже, характерны для аппаратной части большинства систем.

1. БИТ-ПРИСУТСТВИЯ указывает, находится ли страница в данный момент в основной памяти.

2. БИТ(Ы)-АКТИВНОСТИ указывает на использование за последнее время данной страницы процедурами страничного обмена.

3. БИТ-ИЗМЕНЕНИЯ указывает на то, что содержимое страницы памяти изменялось (или не изменялось) с момента ее загрузки в память.

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

2. Разработка алгоритма управления оперативной памятью

Ниже приведён алгоритм управления оперативной памятью в системе Linux. В основе всего лежат страницы памяти. В ядре они описываются структурой mem_map_t.

typedef struct page {

/* these must be first (free area handling) */

struct page *next;

struct page *prev;

struct inode *inode;

unsigned long offset;

struct page *next_hash;

atomic_t count;

unsigned long flags; /* atomic flags, some possibly updated asynchronously */

struct wait_queue *wait;

struct page **pprev_hash;

struct buffer_head * buffers;

} mem_map_t;

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

Все страницы адресуются глобальным указателем mem_map

mem_map_t * mem_map

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

static inline unsigned long page_address(struct page * page)

{

return PAGE_OFFSET + PAGE_SIZE * (page - mem_map);

}

Свободные страницы хранятся в особой структуре free_area

static struct free_area_struct free_area[NR_MEM_TYPES][NR_MEM_LISTS];

где первое поле отвечает за тип области: Ядра, Пользователя, DMA и т.д. И обрабатываются по очень интересному алгоритму.

Страницы делятся на свободные непрерывные области размера 2 в степени x умноженной на размер страницы ((2^x)*PAGE_SIZE). Области одного размера лежат в одной области массива.

Таблица 1.

Выделение стараницы выполняется функцией get_free_pages(order). Она выделяет страницы составляющие область размера PAGE_SIZE*(2^order). Делается это следующим образом: ищется область соответствующего размера или больше. Если есть только область большего размера, то она делится на несколько маленьких и берется нужный кусок. Если свободных страниц недостаточно, то некоторые будут сброшены в область подкачки и процесс выделения начнется снова. Возвращает страницу функция free_pages(struct page, order). Высвобождает страницы, начинающиеся с page размера PAGE_SIZE*(2^order). Область возвращается в массив свободных областей в соответствующую позицию и после этого происходит попытка объединить несколько областей для создания одной большего размера.

Отсутствие страницы в памяти обрабатываются ядром особо. Страница может или вообще отсутствовать или находиться в области подкачки.

Весь процесс работает с виртуальными адресами, а не с физическими. Преобразование происходит посредством вычислений, используя таблицы дескрипторов, и каталоги таблиц. Linux поддерживает 3 уровня таблиц: каталог таблиц первого уровня (PGD - Page Table Directory),каталог таблиц второго уровня (PMD - Medium Page Table Diractory), и, таблица дескрипторов (PTE - Page Table Entry). Конкретным процессором могут поддерживаться не все уровни, но запас позволяет поддерживать больше возможных архитектур (Intel имеет 2 уровня таблиц, а Alpha - целых 3). Преобразование виртуального адреса в физический происходит соответственно в 3 этапа. Берется указатель PGD, имеющийся в структуре описывающий каждый процесс, преобразуется в указатель записи PMD, а последний преобразуется в указатель в таблице дескрипторов PTE. И, наконец, к реальному адресу, указывающему на начало страницы прибавляют смещение от ее начала. Хороший пример подобной процедуры можно посмотреть в функции ядра partial_clear:

page_dir = pgd_offset(vma->vm_mm, address);

if (pgd_none(*page_dir))

return;

if (pgd_bad(*page_dir)) {

printk("bad page table directory entry %p:[%lx]\n", page_dir, pgd_val(*page_dir));

pgd_clear(page_dir);

return;

}

page_middle = pmd_offset(page_dir, address);

if (pmd_none(*page_middle))

return;

if (pmd_bad(*page_middle)) {

printk("bad page table directory entry %p:[%lx]\n", page_dir, pgd_val(*page_dir));

pmd_clear(page_middle);

return;

}

page_table = pte_offset(page_middle, address);

Все данные об используемой процессом памяти помещаются в структуре: mm_struct

struct mm_struct {

struct vm_area_struct *mmap; /* Список отображенных областей */

struct vm_area_struct *mmap_avl; /* Те же области но уже в виде дерева

для более быстрого поиска */

struct vm_area_struct *mmap_cache; /* Последняя найденная область */

pgd_t * pgd; /*Каталог таблиц*/

atomic_t count;

int map_count; /* Количество областей*/

struct semaphore mmap_sem;

unsigned long context;

unsigned long start_code, end_code, start_data, end_data;

unsigned long start_brk, brk, start_stack;

unsigned long arg_start, arg_end, env_start, env_end;

unsigned long rss, total_vm, locked_vm;

unsigned long def_flags;

unsigned long cpu_vm_mask;

unsigned long swap_cnt; /* количество страниц для свопинга при следующем проходе */

unsigned long swap_address;

/*

* Это архитектурно-зависимый указатель. Переносимая часть Linux

ничего не знает о сегментах. */

void * segments;

};

Замечаем, что помимо вполне понятных указателей на начало данных (start_code, end_code...) кода и стека есть указатели на данные отображенных файлов (mmap).

На уровне процесса работа может вестись как со страницами напрямую, так и через абстрактную структуру vm_area_struct

struct vm_area_struct {

struct mm_struct * vm_mm; /* параметры области виртуальной памяти */

unsigned long vm_start;

unsigned long vm_end;

/* Связянный список областей задачи отсортированный по адресам */

struct vm_area_struct *vm_next;

pgprot_t vm_page_prot;

unsigned short vm_flags;

/* AVL-дерево областей, для ускоренного поиска, сортировка по адресам */

short vm_avl_height;

struct vm_area_struct * vm_avl_left;

struct vm_area_struct * vm_avl_right;

/* Для областей используемых при отображении файлов или при работе

с разделяемой памяти, иначе эта часть структуры не используется */

struct vm_area_struct *vm_next_share;

struct vm_area_struct **vm_pprev_share;

struct vm_operations_struct * vm_ops; /*операции над областью */

unsigned long vm_offset;

struct file * vm_file;

unsigned long vm_pte; /* разделяемая память */

};

struct vm_operations_struct {

void (*open)(struct vm_area_struct * area);

void (*close)(struct vm_area_struct * area);

void (*unmap)(struct vm_area_struct *area, unsigned long, size_t);

void (*protect)(struct vm_area_struct *area, unsigned long, size_t, unsigned int newprot);

int (*sync)(struct vm_area_struct *area, unsigned long, size_t, unsigned int flags);

void (*advise)(struct vm_area_struct *area, unsigned long, size_t, unsigned int advise);

unsigned long (*nopage)(struct vm_area_struct * area, unsigned long address, int write_access);

unsigned long (*wppage)(struct vm_area_struct * area, unsigned long address,

unsigned long page);

int (*swapout)(struct vm_area_struct *, struct page *);

pte_t (*swapin)(struct vm_area_struct *, unsigned long, unsigned long);

};

Данная структура возникла из идеи виртуальной файловой системы, поэтому все операции над виртуальными областями абстрактны и могут быть специфичными для разных типов памяти, например при отображении файлов операции чтения одни, а при отображении памяти (через файл /dev/mem) совершенно другие. Первоначально vm_area_struct появилась для обеспечения нужд отображения, но постепенно распространяется и для других целей.