Так, например, пpоцедуpа управления памятью MS DOS рассчитана на случай, когда программы выгружаются из памяти только в порядке, обратном тому, в каком они туда загружались. Это позволяет свести управление памятью к стековой дисциплине.

Каждой программе в MS DOS отводится блок памяти. С каждым таким блоком ассоциирован дескриптор, называемый MCB - Memory Control Block. Этот дескриптор содержит размер блока, идентификатор программы, которой принадлежит этот блок и признак того, является ли данный блок последним в цепочке. Нужно отметить, что программе всегда принадлежит несколько блоков, но это уже несущественные детали. Другая малосущественная деталь та, что размер сегментов и их адреса отсчитываются в параграфах размером 16 байт. После запуска.com-файл получает сегмент размером 64К, а.exe - всю доступную память. Обычно.exe-модули сразу после запуска освобождают ненужную им память и устанавливают brklevel на конец своего сегмента, а потом увеличивают brklevel и наращивают сегмент по мере необходимости. Естественно, что наращивать сегмент можно только за счет следующего за ним в цепочке MCB, и MS DOS разрешит делать это только в случае, если этот сегмент не принадлежит никакой программе.

При запуске программы DOS берет последний сегмент в цепочке, и загружает туда программу, если этот сегмент достаточно велик. Если он недостаточно велик, DOS «говорит» Not enough memory и отказывается загружать программу.

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

Например, неявно предполагается, что TSR-программы (Terminate, but Stay Resident) никогда не пытаются завершиться. Другой пример - отладчики обычно загружают программу в обход обычной DOS-овской функции LOAD & EXECUTE, а при завершении отлаживаемой программы сами освобождают память из-под нее.

В системах с динамической сборкой первые две проблемы не так остры, потому что память выделяется и освобождается небольшими кусочками, по блоку на каждый объектный модуль, поэтому код программы обычно не занимает непрерывного пространства. Соответственно, такие системы часто разрешают и данным программы занимать несмежные области памяти.

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

Объем виртуального адресного пространства может даже превосходить всю доступную реальную память на ЭВМ. Содержимое виртуальной памяти, неиспользуемой программой, хранится на некотором внешнем устройстве (внешней памяти). По необходимости части этой виртуальной памяти отображаются в реальную память. Ни о внешней памяти, ни о ее отображении в реальную память программа ничего не знает. Она написана так, как будто бы виртуальная память существует в действительности (рис. 2.).

Рис.2. Основная концепция виртуальной памяти

При страничной организации основная память делится на блоки фиксированного размера, обычно называемые рамка страниц. Каждая программа пользователя делится на блоки сответствующего размера, называемые страницами. Страницы организуются в логическом адресном пространстве, а рамки cтраниц - в физическом. Поскольку страницы и рамки страниц имеют различные идентификаторы, возникают интересные ситуации, касающиеся взаимосвязи между логическим адресным пространством (ЛАП) и физическим адресным пространством ФАП).

1. ЛАП < ФАП. В этом случае основной акцент делается на повышение эффективности использования памяти.

2. ЛАП = ФАП. Страничная организация служит не только для увеличения эффективности использования памяти, но и для расширения возможности разделенного использования процедур (т.е. несколькими пользователями). Возможно использование эффективного оверлейного механизма, реализованного аппаратно.

3. ЛАП > ФАП. Этот случай предполагает виртуальную память и дает наибольшие преимущества.

Мы будем рассматривать управление страницами применительно к последнему случаю. Выбор между случаями 1 и 2 обычно находится в зависимости от структуры Устройства Управления Памятью (УУП) и задач проектировщика операционной системы. Пользователь, располагая ЛАП из m страниц, будет иметь k страниц, отведенных под интерпретатор, и m - k страниц рабочего пространства. Описанный подход эффективен для системы с разделением времени.

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

Пусть p есть размер страницы в словах (например, 512).

Пусть т есть размер основной памяти в словах, такой, что m=n*p по модулю 1024 есть 0; р по модулю 2К есть 0 и i*p=j*1024. Таким образом, основная память состоит из участков по 1К слов в каждом. Кроме этого, размер страницы есть степень числа 2, а 1К памяти содержит четное число страниц. Набор целых чисел 0, 1, 2,...,п-1 соответствует идентификаторам страничных рамок.

Пусть М есть размер программы пользователя в словах. Для размещения этой программы в памяти необходимо N страниц, так что М=N*p. Набор целых чисел от 0 до п-1 соответствует идентификаторам страниц пользователя. Заметим, что требование равенства нулю m по модулю р не является обязательным. Это означает, что программа пользователя не должна заполнять целиком все страницы. Последняя страница может быть заполнена лишь частично.

Используя двоичную арифметику, - представление страницы степенью числа 2 легко реализуемо. Фактически в большинстве машин имеются команды сдвига, делающие генерацию виртуального адреса очень простой операцией. Требование задания М кратным 1К является результатом стандартизации. В последнее время принято считать, что размер 8К, 16К и даже 64К более предпочтителен.

Конструкция виртуального адреса. Виртуальный адрес - это адрес логического пространства процесса пользователя (обычно для случая ЛАП >ФАП). Все ссылки к логическому пространству должны быть преобразованы в физический адрес основной памяти. Для этого системе необходимы идентификатор рамки страницы и смещение внутри нее. Система должна преобразовать виртуальный адрес в физический. Каждый виртуальный адрес есть пара (р, i), где р - номер страницы процесса пользователя, а i-индекс страницы (такой, что i<w, где w-размер страницы).

Предположим, что машина имеет 16-бит слово, позволяющее ей адресоваться к 64К слов. Если размер страницы составит 512 слов, то логическое адресное пространство будет состоять из 128 страниц. Для идентификатора р необходимо 7 бит, а для индекса 9 бит. Полное 16-бит слово будет иметь вид

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

где биты 31 и 30 имеют специальное назначение для;VAX/VMS;биты 29 - 9 адресуются к одной из 220страниц;биты 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 появилась для обеспечения нужд отображения, но постепенно распространяется и для других целей.

Что делать, когда требуется получить новую область памяти. Есть целых 3 способа.

1. get_free_page()

2. kmalloc - Простенькая (по возможностям) процедура с большими ограничениями по выделению новых областей и по их размеру.

3. vmalloc - Мощная процедура, работающая с виртуальной памятью, может выделять большие объемы памяти.

С каждой из двух процедур в ядре связаны еще по списку свободных/занятых областей, что еще больше усложняет понимание работы с памятью. (vmlist для vmalloc, kmem_cash для kmalloc)

Добавлена поддержка новой архитектуры памяти NUMA. В противовес классической UMA память делится на зоны с разным временем доступа к каждой из них. Это очень полезно и для кластерных решений. В связи с этим появились новые обертки на функции, новые структуры и найти суть стало еще сложнее. Появилась также поддержка памяти до 64Гб.

Ранее для всех файловых систем был один generic_file_read и generic_file_mmap в связи с тотальным засасыванием всего подряд в память при чтении (различия делались уже только на уровне inode->readpage).

Вывод.

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

Список используемой литературы

1. Рихтер Джеффри "Linux для профессионалов", С-П. Русская редакция 1998.

2. Хендерсон К. "Руководство разработчика баз данных"

3. Г. Майерс "Надежность ПО" Мир, М., 1980

Страницы: 1, 2, 3