Организация памяти компьютера

 

Введение

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

На рис. 1 все алгоритмы распределения памяти разделены на два класса: алгоритмы, в которых используется перемещение сегментов процессов между оперативной памятью и диском, и алгоритмы, в которых внешняя память не привлекается.

Рис. 1. Классификация методов распределения памяти

Мы подробно рассмотрим алгоритмы работы с памятью без использования внешней памяти, а алгоритмы с использованием внешней памяти опустим.

1.1 Распределение памяти фиксированными разделами

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

Рис. 2. Распределение памяти фиксированными разделами:

а - с общей очередью; б - с отдельными очередями

Подсистема управления памятью в этом случае выполняет следующие задачи:

)Сравнивая размер программы, поступившей на выполнение, и свободных разделов, выбирает подходящий раздел.

)Осуществляет загрузку программы и настройку адресов.

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

1.2 Распределение памяти динамическими разделами

память virtualalloc windows зарезервированный

В этом случае память машины не делится заранее на разделы. Сначала вся память свободна. Каждой вновь поступающей задаче выделяется необходимая ей память. Если достаточный объем памяти отсутствует, то задача не принимается на выполнение и стоит в очереди. После завершения задачи память освобождается, и на это место может быть загружена другая задача. Таким образом, в произвольный момент времени оперативная память представляет собой случайную последовательность занятых и свободных участков (разделов) произвольного размера. На рисунке 3 показано состояние памяти в различные моменты времени при использовании динамического распределения. Так в момент t0 в памяти находится только ОС, а к моменту t1 память разделена между 5 задачами, причем задача П4, завершаясь, покидает память. На освободившееся после задачи П4 место загружается задача П6, поступившая в момент t3.

Рис. 3. Распределение памяти динамическими разделами

Задачами операционной системы при реализации данного метода управления памятью является:

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

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

)Загрузка задачи в выделенный ей раздел и корректировка таблиц свободных и занятых областей.

)После завершения задачи корректировка таблиц свободных и занятых областей.

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

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

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

1.3Распределение памяти перемещаемыми разделами

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

Рис. 4. Распределение памяти перемещаемыми разделами

Хотя процедура сжатия и приводит к более эффективному использованию памяти, она может потребовать значительного времени, что часто перевешивает преимущества данного метода.

1.4Распределение памяти в Windows

Как устроена виртуальная память

Процессу выделяется свое частное 4-гигабайтное виртуальное адресное пространство. Программа может обращаться к любому байту в этом адресном пространстве, используя единственный 32-битный линейный адрес. Программы и элементы данных разбросаны по адресному пространству блоками по 4 Кб, выровненных по границам, кратным 4 Кб. Каждый такой блок называется страницей (page) и может содержать либо код, либо данные. Когда страница действительно используется, она занимает физическую память, но программист никогда не встретится с физическими адресами. Микропроцессорный чип фирмы Intel эффективно преобразует 32-битный виртуальный адрес в номер физической страницы и смещение внутри нее, пользуясь двумя уровнями таблиц 4-килобайтных страниц. Отдельные страницы могут быть помечены либо как «только для чтения», либо как «для чтения и записи». Кроме того, у каждого процесса свой набор таблиц страниц. Регистр чипа CR3 содержит указатель на страницу каталога - переключаясь с одного процесса на другой, Windows просто обновляет этот регистр. Страница памяти может быть отмечена в таблице страниц как «присутствующая», что говорит о том, что данная 4-килобайтная страница находится ли сейчас в памяти. При попытке обращения к странице, отсутствующей в памяти, генерируется прерывание, и Windows приступает к анализу ситуации, просматривая свои внутренние таблицы. Если обращение к памяти было неверным, выдается сообщение об ошибке страницы (page fault), и программа завершается. В ином случае Windows считает в оперативную память нужную страницу из дискового файла и обновит таблицу страниц, записав в нее физический адрес и установив бит присутствия. Момент чтения и записи страницы (чтобы достичь максимальной производительности) определяет диспетчер виртуальной памяти Windows. Если какой-то процесс не использовал страницу в течение определенного периода и эта память нужна другому процессу, данная страница выгружается из памяти, а вместо нее загружается страница нового процесса. Все процессы совместно используют один большой общесистемный файл подкачки (swap file), в который помещаются (при необходимости) все виды данных «для чтения и записи» и некоторые виды данных «только для чтения». (Windows NT поддерживает одновременную работу с несколькими файлами подкачки). Windows определяет размер файла подкачки в зависимости от размера ОЗУ и свободного дискового пространства, но существуют способы тонкой настройки размера и физического расположения этого файла. Однако файл подкачки - не единственный файл, используемый диспетчером виртуальной памяти. Нет особого смысла в том, чтобы записывать в этот файл страницы кода. Вместо этого Windows проецирует ЕХЕ- и DLL-модули непосредственно на их дисковые файлы. Поскольку страницы кода помечены как «только для чтения», то необходимости в их записи обратно на диск не возникает. Если два процесса используют один и тот же ЕХЕ-файл, то данный файл отображается на адресные пространства обоих процессов. Файлы, проецируемые в память, о которых мы поговорим позже, также отображаются напрямую. Они доступны «для чтения и записи» и разделяются несколькими процессами.

Функция VirtualAlloc: переданная и зарезервированная память

Если программе нужна динамически распределяемая память, то рано или поздно ей придется вызвать функцию VirtualAlloc. Вызовет ее не программист, а функции Windows или библиотеки С периода выполнения, выделяющие память из кучи. Зная, как работает VirtuаlAlloc, можно лучше понять функции, которые обращаются к ней. Сначала разберемся с понятиями зарезервированной (reserved) и переданной (committed) памяти. При резервировании памяти выделяется непрерывный диапазон виртуальных адресов. Если, допустим, известно, что программа будет оперировать с одним 5-мегабайтным блоком памяти (блоки памяти называют также регионами (regions)), но весь он сейчас не нужен, тогда следует вызвать VirtualAlloc и в параметре, определяющем тип выделения памяти, указать MEM_RESERVE, а в параметре, задающем размер выделяемой памяти, - 5 Мб. Windows округляет начальный и конечный адреса региона до значений, кратных 64 Кб, и уже не даст процессу повторно зарезервировать память из этого региона. Когда программе всерьез понадобится эта память, она снова вызовет VirtualAlloc, чтобы передать память из этого региона. Теперь начальный и конечный адреса региона округляются до значений, кратных 4 Кб, и в файле подкачки выделяются соответствующие страницы, а также создается нужная таблица страниц. Блок помечается либо как «только для чтения», либо как «для чтения и записи». Однако оперативная память по-прежнему не выделяется; это произойдет, лишь когда программа попытается что-то записать в этот блок памяти. Если передаваемая память не была ранее зарезервирована, ошибки все равно не возникает. А если память уже была передана, то и в этом случае - никаких проблем. Главное в том, что перед использованием память должна быть передана. Чтобы вернуть (decommit) переданную память (по сути, вернуть соответствующим страницам статус зарезервированных), применяется функция VirtualFree. Она может также освободить и зарезервированный регион памяти, но для этого ей надо передать базовый адрес, возвращенный VirtualAlloc в момент резервирования памяти.

Кучи

Windows поддерживает пулы памяти, называемые кучами (heaps). Процесс может иметь несколько куч, которые используются для распределения памяти. Во многих случаях одной кучи вполне достаточно, но в силу ряда причин, о которых будет сказано ниже, иногда целесообразно иметь в своем распоряжении несколько куч. Если одной кучи вам хватает, можно обойтись использованием функций управления памятью, предоставляемых библиотекой С (malloc, free, calloc, realloc).

Кучи являются объектами Windows и, следовательно, имеют дескрипторы. Дескриптор кучи используется при распределении памяти. У каждого процесса имеется куча, заданная по умолчанию, которую использует функция malloc и для получения дескриптора которой используется следующая функция:GetProcessHeap(VOID)

Возвращаемое значение: дескриптор кучи процесса, в случае неуспешного завершения - NULL. Для создания и уничтожения куч применяются две функции, описания которых приводятся ниже.

Начальный размер кучи, устанавливаемый параметром dwInitialSize (который может быть нулевым), всегда округляется до величины, кратной размеру страницы, и определяет объем физической памяти (в файле подкачки), который передается (commit) в распоряжение кучи (для последующего распределения памяти по запросам) первоначально, а не в ответ на запросы распределения (allocation) памяти из кучи. Когда программа исчерпывает первоначальный размер кучи, куче автоматически передаются дополнительные страницы памяти вплоть до пор, пока она не достигнет установленного для нее максимального размера. Поскольку файл подкачки является ограниченным ресурсом, рекомендуется откладывать передачу памяти куче на более поздний срок, если только заранее не известно, какой размер кучи потребуется. Максимально допустимый размер кучи при ее увеличении в результате динамического расширения определяется значением параметра dwMaximumSize (если оно ненулевое). Рост куч процессов, заданных по умолчанию, также осуществляется динамическим путем.

HANDLE HeapCreate (DWORD flOptions, SIZE_T dwInitialSize, SIZE_T dwMaximumSize)

Возвращаемое значение: дескриптор кучи; в случае неудачного завершения - NULL. Типом данных обоих упомянутых полей, связанных с размерами кучи, является не DWORD, a SIZE_T. Тип данных SIZE_T определяется как 32-битовое целое число без знака.- этот параметр может объединять следующие два флага:

. HEAP_GENERATE_EXCEPTIONS: в случае ошибки при распределении памяти вместо возврата значения NULL генерируется исключение, которое должно быть обработано средствами SEH. Если установлен этот флаг, то такие исключения при сбоях будет возбуждаться не самой функцией HeapCreate, а такими функциями, как HeapAlloc.

. HEAP_NO SERIALIZE: при определенных обстоятельствах, о которых сказано ниже, установка этого флага может привести к незначительному повышению производительности.

Для уничтожения объекта кучи используется функция HeapDestroy. Она также может служить примером исключения из общих правил, в данном случае - правила, согласно которому для удаления ненужных дескрипторов любого типа используется функция CloseHandle.

BOOL HeapDestroy (HANDLE hHeap)

Параметр hHeap должен указывать на кучу, созданную посредством вызова функции HeapCreate. Необходимо следить за тем, чтобы случайно не уничтожить кучу процесса, заданную по умолчанию (дескриптор которой получают с помощью функции GetProcessHeap). В результате уничтожения кучи освобождается область виртуального адресного пространства и физическая область сохранения файла подкачки. Разумеется, правильно спроектированная программа должна уничтожать кучи, необходимости в которых больше нет. Уничтожение кучи позволяет быстро освободить память, занимаемую структурами данных, избавляя вас от необходимости отдельного уничтожения каждой из структур, однако экземпляры объектов C++ уничтожены не будут, поскольку их деструкторы при этом не вызываются. Применение операции уничтожения кучи имеет следующие положительные стороны:

. Отпадает необходимость в написании программного кода, обеспечивающего обход структур данных.

. Отпадает необходимость в освобождении памяти, занимаемой каждым из элементов, по отдельности.

. Система не затрачивает время на обслуживание кучи, поскольку отмена распределения памяти для всех элементов структуры данных осуществляется посредством единственного вызова функции.

2. Выделение памяти функцией malloc

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

Постановка задачи:

Выделить память для входной строки используя функцию malloc. Получить выходную строку необходимой длины начиная с указанной позиции входной строки.

Листинг кода на языке С++ с применением ассемблерной вставки.

#include <stdio.h>

#include <iostream>

#include <stdlib.h>

main ()

{(LC_ALL, «rus»);len;pos;hello[] = «Введите строку!\n»;

char position[] = «Введите позицию:\n»;lengt[] = «Введите длину для подстроки:\n»;

const char fstring[] = «%s»;char fint[] = «%d»;

const int N = 256;string[N]; // Строка, с которой мы будем работатьstring1 [N];

__asm {

// Предложение ввести строкуeax, hello // загружаем адрес строки в eaxeax // кладем в стек адрес строкиdword ptr printf // выводим строку по данному адресуesp, 4 // чистим стек

// Выделение памяти под входную строкуeax, N // загружаем в eax размер строкиeax // кладем в стекdword ptr malloc // выделяем память под строкуesp, 4 // чистим стек

// Ввод строкиeax, string // загружаем адрес строки в eaxeax // кладем в стек адрес строкиdword ptr gets // считываем введенную строкуesp, 4 // чистим стек

// Ввод длины нужной подстроки и позиции, с которой она начинается

// выводим сообщение «введите позицию»eax, position // загружаем адрес строки в eaxeax // кладем в стек адрес строкиdword ptr printf // выводим строку по данному адресуesp, 4 // чистим стек

// ввод позицииeax, pos // загружаем адрес переменной в eaxeax // кладем в стекeax, fint // загружаем адрес в eaxeax // кладем в стекdword ptr scanf // считываем введенный символ как числоesp, 8 // чистим стек

// выводим сообщение «Введите длину для подстроки»eax, lengt // загружаем адрес строки в eaxeax // кладем в стек адрес строкиdword ptr printf // выводим строку по данному адресуesp, 4 // чистим стек

// ввод длины подстрокиeax, len // загружаем адрес переменной в eaxeax // кладем в стекeax, fint // загружаем адрес в eaxeax // кладем в стекdword ptr scanf // считываем введенный символ как числоesp, 8 // чистим стек

// Выделение памяти под подстрокуebx, N // загружаем в eax размер строкиebx // кладем в стекdword ptr malloc // выделяем память под строкуesp, 4 // чистим стек

eax, string // загружаем адрес входной строки в eaxebx, string1 // загружаем адрес выходной строки в ebxesi, pos // загружаем переменную в esiecx, len // загружаем переменную в ecx

CYCLE: // Начиная с заданной позиции переписываем len элементов string в string1

mov dh, [eax] [esi] // загружаем в dh адрес позиции нужного символа

mov [ebx], dhesi // увеличиваем значение регистраebx // увеличиваем значение регистра

loop CYCLE

mov [ebx], 0 // конец строки

lea eax, string1 // загружаем в eax адрес выходной строки

push eax // кладем в стек

lea eax, fstring

push eaxdword ptr printf // выводим строкуesp, 8 // чистим стек

}

system («pause»); // ожидание нажатия клавиши

};

Полученный exe-файл запустим в отладчике OllyDbg.

Рис. 5 Интерфейс ПО.

Заполняем входную строку, для которой мы выделили память, некоторыми символами. Перезаписываем 100 символов входной строки в выходную начиная с пятой позиции (Рис. 5). Открыв дамп памяти, мы можем убедиться в том, что память под строку выделилась, и все символы выходной строки записались (Рис. 6).

Рис. 6 dump-памяти

Заключение

Наиболее эффективным способом управления памятью является виртуальная память, вытеснившая в современных ОС методы распределения памяти фиксированными или перемещаемыми разделами.

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

Список литературы

память virtualalloc windows зарезервированный

1. Сетевые операционные системы / В.Г. Олифер, Н.А. Олифер-СПб.: Питер, 2002.

. Операционные системы / А.В. Гордеев

. Ассемблер. Учимся программировать/ Калашников О.А.-СПб.: БХВ-Питербург, 2006.

. Assembler. Учебник для вузов. 2-е изд. / В.И. Юров - СПб.: Питер, 2003.

. Системное программирование в среде Windows, 3-е издание / Харт, Джонсон, М.: Издательский дом «Вильямс», 2005.

Введение В данной работе мы рассмотрим алгоритмы работы с памятью характерные для операционных систем. Некоторые из них сохранили актуальность и широко и

Больше работ по теме: