Управление оперативной памятью

Волжский Университет имени В. Н. Татищева
Факультет «Информатики и телекоммуникаций»
Кафедра «Информатика и системы управления»
Курсовая работа
по дисциплине:
“Основы программного обеспечения”
на тему:
“Управление оперативной памятью”

Содержание
Введение
1.Аналитический раздел
1.1  Определение
1.2  Принципы управления ираспределения оперативной памяти
2.   Разработкаалгоритма управления оперативной памятью
Вывод
Списокиспользуемой литературы

Введение
В настоящее время существуют множество операционных программ,которые в достаточной степени эффективности и надежности, управляют оперативнойпамятью. К таким системам можно отнести Windows, Unix и т.д. Прогрессэлектроники привел к значительному улучшению элементов памяти. А именно такихпараметров, модулей памяти, как объем, надежность, оперативность икомпактность. Память применяется везде, где есть элемент, обрабатывающийинформацию (процессор, контроллер). В следствии этого, появились новые, болеемощные системы управления способные использовать ресурсы оперативной памяти.Это привело к увеличению скорости обработки информации и к увеличению мощности программныхсредств и следовательно самой мощи, всего компьютера в целом. Например,подсистема управления оперативной памятью MS-DOS базировалась на использованииблоков управления памятью MCB. Такое «управление» памятью полностьюосновано на джентльменском соглашении между программами о сохранениицелостности операционной системы, так как любая программа может выполнитьзапись данных по любому адресу. Программа может легко разрушить системныеобласти MS-DOS или векторную таблицу прерываний. На сегодняшний день существуетприложение Windows, которое выполняется в защищенном режиме, поэтому оно неможет адресоваться к любым областям памяти. Это сильно повышает надежностьоперационной системы.
Цель курсовой работы состоит в изучении функционирования ивзаимодействие операционной системы с оперативной памятью. Так же будетвыполнен анализ основных типов, параметров оперативной памяти применяемых всистемных платах персонального компьютера. Далее будет представлена программнаячасть с обработкой и ходом выполнение команд и размещение в оперативной памяти.

1. Аналитический раздел
 
1.1 Определение
Оперативная (или рабочая) память компьютера — ОЗУ(Оперативное Запоминающее Устройство) — собрана на полупроводниковых кристаллах(чипах — chip) и хранит информацию, только пока компьютер включен. Привыключении питания ее содержимое теряется. Иногда, эту память называют ещепамятью с произвольным доступом.(Random Access Memory – RAM).
Всю память с произвольнымдоступом (RAM) можно разделить на два типа:
1.    DRAM (динамическая RAM)
2.    SRAM (статическая RAM).Памятьтипа DRAM
Динамическая оперативная память(Dynamic RAM – DRAM) используется в большинстве систем оперативной памятиперсональных компьютеров. Основное преимущество этого типа памяти состоит втом, что ее ячейки интегрированы плотно, т.е. в небольшую микросхему можнопоместить множество битов, а значит, на их основе можно построить памятьбольшей емкости.
Ячейки памяти вмикросхеме DRAM – это крошечные конденсаторы, которые удерживают заряды.Проблемы, связанные с памятью этого типа, вызваны тем, что она динамическая,т.е. должна постоянно регенерироваться, так как в противном случаеэлектрические заряды в конденсаторах памяти будут “стекать”, и данные будутпотеряны. Регенерация происходит, когда контроллер памяти системы береткрошечный перерыв и обращается ко всем строкам данных в микросхемах памяти.Большинство систем имеет контроллер памяти (обычно встраиваемый в набормикросхем системной платы), который настроен на соответствующую промышленнымстандартам частоту регенерации, равную 15 мкс.
Регенерация памяти, ксожалению, “отнимает время” у процессора: каждый цикл регенерации подлительности занимает несколько циклов центрального процессора. Некоторыесистемы позволяют изменить параметры регенерации с помощью программы установкипараметров CMOS, но увеличение времени между циклами регенерации может привестик тому, что в некоторых ячейках памяти заряд “стечет”, а это вызовет сбойпамяти.
В устройствах DRAM дляхранения одного бита используется только один транзистор и пара конденсаторов,поэтому они более вместительны, чем микросхемы других типов памяти. Транзистордля каждого однозарядного регистра DRAM использует для чтения состояниясмежного конденсатора. Если конденсатор заряжен, в ячейке записана-1; еслизаряда нет – записан 0. Разработчики DRAM нашли возможность осуществленияпередачи данных с помощью асинхронного интерфейса.
С асинхронным интерфейсомпроцессор должен ожидать, пока DRAM закончит выполнение своих внутренних операций,которые обычно занимают около 60 нс. С синхронным управлением DRAM происходитзащелкивание информации от процессора под управлением системных часов. Триггерызапоминают адреса, сигналы управления и данных, что позволяет процессорувыполнять другие задачи. После определенного количества циклов данныестановятся доступны, и процессор может считывать их с выходных линий.
Другое преимуществосинхронного интерфейса заключается в том, что системные часы задают тольковременные границы, необходимые DRAM. Это исключает необходимость наличиямножества стробирующих импульсов. В результате упрощается ввод, т. к.контрольные сигналы адреса данных могут быть сохранены без участия процессора ивременных задержек. Подобные преимущества также реализованы и в операцияхвывода.
К первому поколениювысокоскоростных DRAM главным образом относят EDO DRAM, SDRAM и RDRAM, а кследующему — DDR SDRAM, Direct RDRAM, SLDRAM и т. д. SDRAM
SDRAM (Synchronous DRAM)– это тип динамической оперативной памяти DRAM, работа которой синхронизируетсяс шиной памяти. SDRAM передает информацию в высокоскоростных пакетах,Использующих высокоскоростной синхронизированный интерфейс. SDRAM позволяетизбежать использования большинства циклов ожидания, необходимых при работеасинхронной DRAM, поскольку сигналы, по которым работает память такого типа,синхронизированы с тактовым генератором системной платы.DDR SDRAM (SDRAM II)
DDR SDRAM (Double DataRate SDRAM) является синхронной памятью, реализующей удвоенную скоростьпередачи данных по сравнению с обычной SDRAM.
DDR SDRAM не имеет полнойсовместимости с SDRAM, хотя использует метод управления, как у SDRAM, истандартный 168-контактный разъем DIMM. DDR SDRAM достигает удвоеннойпропускной способности за счет работы на обеих границах тактового сигнала (наподъеме и спаде), а SDRAM работает только на одной.
Direct Rambus DRAM — этовысокоскоростная динамическая память с произвольным доступом, разработаннаяRambus, Inc. Она обеспечивает высокую пропускную способность по сравнению сбольшинством других DRAM. Direct Rambus DRAMs представляет интегрированную насистемном уровне технологию. Памятьтипа SRAM
Существует тип памяти,совершенно отличный от других, — статическая оперативная память (Static RAM –SRAM). Она названа так потому, что, в отличии от динамической оперативнойпамяти, для сохранения ее содержимого не требуется периодической регенерации.Но это не единственное ее преимущество. SRAM имеет более высокое быстродействиечем динамическая оперативная память, и может работать на той же частоте, что исовременные процессоры.
Время доступа SRAM неболее 2 нс, это означает, что такая память может работать синхронно спроцессорами на частоте 500 МГц или выше. Однако для хранения каждого бита вконструкции SRAM используется кластер из 6 транзисторов. Использованиетранзисторов без каких либо конденсаторов означает, что нет необходимости врегенерации. Пока подается питание, SRAM будет помнить то, что сохранено.
Микросхемы SRAM неиспользуются для всей системной памяти потому, что по сравнению с динамическойоперативной памятью быстродействие SRAM намного выше, но плотность ее намногониже, а цена довольно высокая. Более низкая плотность означает, что микросхемыSRAM имеют большие габариты, хотя их информационная емкость намного меньше.Большое число транзисторов и кластиризованное их размещение не толькоувеличивает габариты SRAM, но и значительно повышает стоимость технологическогопроцесса по сравнению с аналогичными параметрами для микросхем DRAM.
Все выше перечисленные модулипамяти размещаются в компьютере на главной системной плате или на отдельныхплатах памяти. Перед обработкой и выводом на экран данные сначала помещаются впамять. Например, файлы прикладных программ обычно располагаются на жёсткомдиске. Когда Вы запускаете программу, её файлы загружаются в память длядальнейшей обработки. Также память обеспечивает временное хранение данных иприкладных программ. В общем случае, чем больше памяти установлено вкомпьютере, тем более сложные прикладные программы могут выполняться Вашимкомпьютером. Память служит для хранения данных (документов), обрабатываемых втекущий момент компьютером. Выполняемая программа, как и значительная частьоперационной системы DOS, хранится в оперативной памяти. С точки зрениявнутренних механизмов оболочки оперативная память делится на две части:основную и расширенную. Оперативная память Вашей системы может быть следующихвидов:
— обычная или базовая память;
— дополнительная память;
— расширенная память;
— верхняя память. Базовая память
Операционнаясистема MS DOS, а, следовательно, и уподобляющее большинство работающих под ееуправлением программ могут использовать лишь первый мегабайт памяти, которыйчасто называют базовой памятью. Эта память в рамках ДОС поделена на двенеравные части: первые 640 К (1К = 1024 байт) отводятся для программпользователя и отдельных частей самой ДОС и называются стандартной памятью(conventional memory). Для использования стандартной памяти не нужны никакиедополнительные драйверы, поскольку операционная система MS-DOS изначальносоздана для работы в адресах 0-640 Кбайт. Оставшиеся 384 К зарезерервированыдля памяти видеоадаптеров и ПЗУ и называются верхним блоком памяти (UMB — UperMemory Block). В то же время в компьютерах IBM AT имеется возможность адресоватьпамять объемом до 16 Mb, если в них используется микропроцессор 80286, или до 4Gb, если используется микропроцессор 80386 или 80486. Объем непосредственноадресуемой оперативной памяти определяется разрядностью адресной шинымикропроцессора. Микропроцессоры 8088 и 8086 имеют 20-разрядную шину, поэтомуадресуют 2 в степени 20 = 1048576 байт = 1 Мb. Микропроцессор 80286 оснащен24-разрядной шиной и адресует 2 в степени 24 = 16 777 216 байт = 16 Mb.32-разрядная шина 80386 и 80486 микропроцессоров адресует 2 в степени 32 =4294967296 байт = 4Gb.
Дополнительнаяпамять
ПамятьПК, остающаяся за вычетом первого мегабайта (т.е. за вычетом базовой памяти),называется дополнительной (Extended Memory). Дополнительная память являетсяестественным дополнением к обычной (базовой) памяти компьютера, на что иуказывает само её название. Однако единственный (но, к сожалению, определяющий)факт, в котором нет никакой естественности, заключается в том, что подавляющемубольшинству программ MS DOS она не доступна! Чтобы использовать дополнительнуюпамять, процессор компьютера должен работать в специальном режиме, называемомзащищённым. А операционнная система MS DOS не поддерживает этого режимапроцессора. Таким образом, владелец современного компьютера IBM AT, оснащенногопамятью, скажем, в 8 Mb, часто либо вообще не использует дополнительные 7 Mb,либо размещает в них электронный диск или буферную кэш-память для дисков. Вверсии Турбо Паскаля 7.0 (точнее, в пакете Borland Pascal with Objects 7.0)введена поддержка защищенного режима микропроцессоров 80286/ 80386/80486, вкотором используется дополнительная память. Однако эта поддержка не касаетсястандартных средств работы с дополнительной памятью. Тем не менее отдельныепрограммы MS DOS применяют технологию «расширения MS DOS», котораяпозволяет им воспользоваться преимуществами дополнительной памяти. Примеромтаких программ служат Lotus 1-2-3 (Lotus Development Corporation) и Paradox 386(Borland International). Компьютеры же на базе микропроцессоров Intel 8086 и 8088не могут иметь дополнительную память, т.к. не имеют защищённого режима. Этимикропроцессоры функционируют исключительно в реальном режиме и поэтому негодятся для работы с программами, использующими дополнительную память.Дополнительную память иногда называют XMS-памятью; XMS — сокращение от eXtendedMemory Specification (спецификация дополнительной памяти). Не путайте этуаббревиатуру с другой — EMS (Expanded Memory
Расширенная память
РанниеIBM-совместимые ПК типа IBM PC/XT оснащались микропроцессорами 8088 или 8086,способными работать с оперативной памятью емкостью не более 1 Мбайт. Несмотряна значительные размеры этой памяти, в ряде прикладных программ ее оказываетсянедостаточио. Такие программы вынуждены интенсивно использовать диск дляразмезщения больших объемов данных, что сильно снижает их производительность.Поэтому почти одновременно с появлением компьютеров IBM PC/XT начались поискипутей повышения производительности крупных прикладных пропоим (табличныхпроцессоров, систем управления базами данных и т.п.) за счет использованияоперативной памяти большего чем 1 Мбайт размера. Эти поиски привели к выработкесоглашения между ведущими фирмами-разработчиками программно-аппаратных средств,которое известно как EMS LIM (от Expanded Memory Specification — спецификациярасширенной памяти, удовлетворяющая стандарту фирм Lotus-Intel-Microsoft). Всоответствии с этим стандартом ПК оснащаются специальными EMS-платами,содержащими собственно расширенную память микросхемы, обеспечивающие доступ кней. Память, организованная по принципам спецификации EMS, называетсярасширенной памятью. На компьютерах с микропроцессорами 80386 и 80486расширенная память может эмулироваться программно. Начиная с версии 4.0операционная система MS DOS поставляется с драйверами расширенной памятиXMAEM.SYS и XMA2EMS.SYS. В DOS 5.0 их функции выполняет драйвер EMM386.SYS.Последний на ПК с микропроцессорами 80386/80486 обеспечивает эмуляциюрасширенной памяти, т.е. программно реализует функции EMS-платы и преобразуетдополнительную память в расширенную. Кроме того, драйвер EMM386.SYS создаетблоки верхней памяти (UMB).
Дляфункционирования драйвера EMM386.SYS требуется обеспечить поддержку расширеннойпамяти, которую осуществляет драйвер HIMEM.SYS. При этом драйвер HIMEM.SYSдолжен быть загружен до драйвера EMM386.SYS, поэтому строка DEVICE=HIMEM.SYS вфайле CONFIG.SYS должна предшествовать строке DEVICE=EMM386.SYS. Таким образом,дополнительная память — это просто добавочная память. Расширенная память — этоспециальная добавочная память, удовлетворяющая требованиям спецификации EMS.Следует отметить, что термины «дополнительная» и«расширенная» память применяются только в операционной системе DOS. Вдругих операционных системах, например, в OS/2, Unix или Windows NT можноиспользовать всю память компьютера. В этих операционных системах памятьназывается просто «памятью».
Верхняя память
Помимобазовой, расширенной и дополнительной памяти, в ПК существует еще такназываемая верхняя память (не путайте с верхним блоком памяти!). Как известно,20-разрядный адрес при работе ПК в реальном режиме образуется путем сложениядвух 16-разрядных слов — сегмента и смещения. Перед сложением сегмент смещаетсяна 4 разряда влево (умножается на 16), что и обеспечивает 20-разрядныйрезультат сложения — адрес конкретного байта. Формальное сложение сегмента исмещения может привести к переполнению 20-разрядной адресной сетки.Действительно, если, например, сегмент S=$FFFF, а смещение O=$0010, то сложение$FFFF*16 + $0010 дает значение $100000, для представления которого требуетсяуже 21 разряд. Поскольку в ПК применяется 20-разрядная шина, переполнениерезультата не может использоваться, и «лишний» 21-й разряд простотеряется, т.е, адресация с сегментом S= $FFFF и смещением O> $000Fэквивалентна адресации с сегментом S= $0000 и смещением O= O — $0010. Вадресной шине IBM AT имеется 21-й разряд, но его использование обычнозапрещено. Однако в таких компьютерах предусмотрена возможность программногоуправления 21-м разрядом. Если этот разряд разблокировать, программе,работающей в реальном режиме процессора, станут доступны еще почти 64 К (без 16байт). Эта часть памяти и называется верхней (High Memory Area). MS DOS версии5.0 и некоторые совместимые с ней операционные системы других фирм (например,DR-DOS фирмы Digital Research версии 4.0 и выше) могут размещать в верхнейпамяти свои резидентные части, тем самым освобождая драгоценную стандартнуюпамять для программ пользователя. Таким образом, существуют 4 вида оперативнойпамяти: • базовая — с адресами от $00000 до $FFFFF; • верхняя — с адресами от$100000 до $10FFEF; • дополнипельная — с адресами от $100000 до $FFFFFFFF; •расширенная — организуется специальными аппаратными средствами на компьютерах смикропроцессорами 8088, 8086, 80286 и может программно эмулироваться напроцессорах 80386 и 80486.
1.2Принципы управления и распределения оперативной памяти
Основнойресурс системы, распределением которого занимается ОС — это оперативная память(ОП). Поэтому организация памяти оказывает большое влияние на структуру ивозможности ОС.
Используемыев операционных системах алгоритмы распределения ОП многообразны. Причинамиэтого многообразия являются:
·          многоуровневаяструктура памяти (регистровая, оперативная, внешняя)
·          стремлениеобеспечить пользователя характеристиками, отличными от реальных (виртуальнаяпамять)
·          необходимостьсогласования распределения ОП с распределением центрального процессора
Самыйпростой случай управления памятью — ситуация, когда диспетчер памятиотсутствует, и в системе может быть загружена только одна программа. Именно втаком режиме работают CP/M и RT-11 SJ (Single-Job, однозадачная).
Вэтих системах программы загружаются с фиксированного адреса PROG_START.В CP/M это 0x100;в RT-11 — 01000.В адресах от 0 до начала программы находятся вектора прерываний, а в RT-11 — также и стек программы. В этом случае управление памятью со стороны системысостоит в том, что загрузчик проверяет, поместится ли загружаемый модуль впространство от PROG_STARTдо SYS_START.Если объем памяти, который использует программа, не будет меняться во время ееисполнения, то на этом все управление и заканчивается.
Однакопрограмма может использовать динамическое управление памятью, например функцию malloc().В этом случае уже код malloc()должен следить за тем, чтобы не залезть в системные адреса. Как правило,динамическая память начинает размещаться с адреса PROG_END = PROG_START + PROG_SIZE.PROG_SIZEв данном случае обозначает полный размер программы, то есть размер ее кода,статических данных и области, выделенной под стек.
Функцияmalloc()поддерживает некоторую структуру данных, следящую за тем, какие блоки памяти изуже выделенных были освобождены. При каждом новом запросе она сначала ищет блокподходящего размера в своей структуре данных и, только когда этот поискзавершится неудачей, откусывает новый блок памяти у системы. Для этогоиспользуется переменная, которая в библиотеке языка C называется brklevel.Изначально эта переменная равна PROG_END, ее значение увеличиваетсяпри выделении новых блоков, но в некоторых случаях может и уменьшаться. Этопроисходит, когда программа освобождает блок, который заканчивается на текущемзначении brklevel.
Потребностиотдельных программ в ресурсе памяти в процессе обработки могут меняться, чтозаранее, до запуска программы, не может быть учтено. В связи с этим необходимораспределять память динамически непосредственно в ходе вычислительногопроцесса, т.е. осуществлять динамическое распределение памяти.Алгоритмы динамического упpавления памятью
Динамическоераспределение памяти (его еще иногда называют управлением кучей (poolили heap)) представляет собой нетривиальную проблему. Действительно,активное использование функций malloc/free может привести к тому, чтовся доступная память будет разбита на блоки маленького размера, и попыткавыделения большого блока завершится неудачей, даже если сумма длин маленькихблоков намного больше требуемой. Это явление называется фрагментацией памяти.Кроме того, большое количество блоков требует длительного поиска.
Взависимости от решаемой задачи используются различные алгоритмы поискасвободных блоков памяти. Действительно, программа может требовать множествоблоков одинакового размера, или нескольких фиксированных размеров. Это сильнооблегчает решение проблемы фрагментации и поиска. Возможны ситуации, когдаблоки освобождаются в порядке, обратном тому, в котором они выделялись. Этопозволяет свести выделение памяти к стековой структуре. Возможны ситуации,когда некоторые из занятых блоков можно переместить по памяти. Так, например, функциюrealloc()в ранних реализациях системы UNIX можно было использовать именно дляэтой цели.
Встандартных библиотеках языков высокого уровня, таких как malloc/free/reallocв C, new/disposeв Pascal и т.д., как правило, используются алгоритмы, рассчитанные на худшийслучай: программа требует блоки случайного размера в случайном порядке иосвобождает их также случайным образом.
Возможныалгоритмы распределения памяти двух типов: когда размер блока являетсяхарактеристикой самого блока, и когда его сообщают отдельно при освобождении. Кпервому типу относится malloc/free,ко второму — GetMem/FreeMemв Turbo Pascal. В первом случае с каждым блоком ассоциируется некоторыйдескриптор, который содержит длину этого блока и еще информацию. Этотдескриптор может храниться отдельно от блока, или быть его заголовком. Иногдадескриптор состоит из двух меток — в начале блока и в его конце. Для чего этоможет быть полезно, будет рассказано ниже.
Обычновсе свободные блоки памяти объединяются в двунаправленный связанный список.Список должен быть двунаправленным для того, чтобы из него в любой момент можнобыло извлечь любой блок. Впрочем, если все действия по извлечению блокапроизводятся после поиска, то можно слегка усложнить пpоцедуpу поиска и всегдасохранять указатель на пpедыдущий блок. Это pешает пpоблему извлечения и можноогpаничиться однонапpавленным списком. Беда только в том, что многие алгоpитмыпpи объединении свободных блоков извлекают их из списка в соответствии садpесом, поэтому для таких алгоpитмов двунапpавленный список необходим.
Поискв списке может вестись двумя способами: до нахождения первого подходящего(first fit) блока или до блока, размер которого ближе всего к заданному- наиболее подходящего (best fit). Для нахождения наиболееподходящего мы обязаны просматривать весь список, в то время как первыйподходящий может оказаться в любом месте, и среднее время поиска будет меньше.
Крометого, в общем случае best fit увеличивает фрагментацию памяти. Действительно,если мы нашли блок с размером больше заданного, мы должны отделить «хвост» ипометить его как новый свободный блок. Понятно, что в случае best fit среднийразмер этого хвоста будет маленьким, и мы в итоге получим большое количествомелких блоков, которые невозможно объединить, так как пространство между нимизанято.
Прииспользовании first fit с линейным двунаправленным списком возникаетспецифическая проблема. Если каждый раз просматривать список с одного и того жеместа, то большие блоки, расположенные ближе к началу, будут чаще удаляться.Соответственно, мелкие блоки будут иметь тенденцию скапливаться в началесписка, что увеличит среднее время поиска. Простой способ борьбы с этимявлением состоит в том, чтобы просматривать список то в одном направлении, то вдругом. Более радикальный и еще более простой метод состоит в том, что списокделается кольцевым, и поиск каждый начинается с того места, где мы остановилисьв прошлый раз. В это же место добавляются освободившиеся блоки.
Вситуациях, когда размещаются блоки нескольких фиксированных размеров, алгоритмыbest fit оказываются лучше. Однако библиотеки распределения памяти рассчитываютна худший случай, и в них обычно используются алгоритмы first fit.
Вслучае работы с блоками нескольких фиксированных размеров напрашивается такоерешение: создать для каждого типоразмера свой список.
Интересныйвариант этого подхода для случая, когда различные размеры являются степенямичисла 2, как 512 байт, 1Кбайт, 2Кбайта и т.д., называется алгоритмомблизнецов. Он состоит в том, что мы ищем блок требуемого размера всоответствующем списке. Если этот список пуст, мы берем список блоков вдвоебольшего размера. Получив блок большего размера, мы делим его пополам. Ненужнуюполовину мы помещаем в соответствующий список свободных блоков. Одно изпреимуществ этого метода состоит в простоте объединения блоков при ихосвобождении. Действительно, адрес блока-близнеца получается простыминвертированием соответствующего бита в адресе нашего блока. Нужно толькопроверить, свободен ли этот близнец. Если он свободен, то мы объединяем братьевв блок вдвое большего размера, и т.д.
Алгоритмблизнецов значительно снижает фрагментацию памяти и резко ускоряет поискблоков. Наиболее важным преимуществом этого подхода является то, что даже внаихудшем случае время поиска не превышает. Это делает алгоритм близнецовтруднозаменимым для ситуаций, когда необходимо гарантированное время реакции — например, для задач реального времени. Часто этот алгоритм или его вариантыиспользуются для выделения памяти внутри ядра ОС. Например, функция kmalloc,используемая в ядре ОС Linux, основана именно на алгоритме близнецов.
Разработчикпрограммы динамического распределения памяти обязан решить еще одну важнуюпроблему, а именно — объединение свободных блоков. Наилучшим из известныхуниверсальных алгоритмов динамического распределения памяти является алгоритмпарных меток с объединением свободных блоков в двунаправленный кольцевой списоки поиском по принципу first fit. Этот алгоритм обеспечивает приемлемуюпроизводительность почти для всех стратегий распределения памяти, используемыхв прикладных программах. Такой алгоритм используется практически во всехреализациях стандартной библиотеки языка C и во многих других ситуациях. Другиеизвестные алгоритмы либо просто хуже, чем этот, либо проявляют своипреимущества только в специальных случаях.
Косновным недостаткам этого алгоритма относится отсутствие верхней границывремени поиска подходящего блока, что делает его неприемлемым для задачреального времени.
Некоторыесистемы программирования используют специальный метод освобождения динамическойпамяти, называемый сборкой мусора. Этот метод состоит в том, чтоненужные блоки памяти не освобождаются явным образом. Вместо этого используетсянекоторый более или менее изощренный алгоритм, следящий за тем, какие блоки ещенужны, а какие — уже нет.
Самыйпростой метод- отличать используемые блоки от ненужных — считать, что блок, накоторый есть ссылка, нужен, а блок, на который ни одной ссылки не осталось — ненужен. Для этого к каждому блоку присоединяют дескриптор, в которомподсчитывают количество ссылок на него. Каждая передача указателя на этот блокприводит к увеличению счетчика ссылок на 1, а каждое уничтожение объекта,содержавшего указатель — к уменьшению.
Всеостальные методы сборки мусора так или иначе сводятся к поддержанию базы данныхо том, какие объекты на кого ссылаются. Использование такой техники возможнопрактически только в интерпретируемых языках типа Lisp или Prolog,где с каждой операцией можно ассоциировать неограниченно большое количестводействий.
Многозадачнаяили многопрограммная ОС также должны использовать тот или иной алгоритмразмещения памяти. Такие алгоритмы могут быть похожи на работу malloc. Однакорежим работы ОС может вносить существенные упрощения в алгоритм.
Так,например, пpоцедуpа управления памятью MS DOS рассчитана на случай,когда программы выгружаются из памяти только в порядке, обратном тому, в какомони туда загружались. Это позволяет свести управление памятью к стековойдисциплине.
Каждойпрограмме в MS DOS отводится блок памяти. С каждым таким блокомассоциирован дескриптор, называемый MCB — Memory ControlBlock. Этот дескриптор содержит размер блока, идентификатор программы, которойпринадлежит этот блок и признак того, является ли данный блок последним вцепочке. Нужно отметить, что программе всегда принадлежит несколькоблоков, но это уже несущественные детали. Другая малосущественная деталь та,что размер сегментов и их адреса отсчитываются в параграфах размером 16 байт.После запуска.com-файлполучает сегмент размером 64К, а.exe — всю доступнуюпамять. Обычно.exe-модулисразу после запуска освобождают ненужную им память и устанавливают brklevelна конец своего сегмента, а потом увеличивают brklevel и наращиваютсегмент по мере необходимости. Естественно, что наращивать сегмент можно толькоза счет следующего за ним в цепочке MCB, и MS DOSразрешит делать это только в случае, если этот сегмент не принадлежит никакойпрограмме.
Призапуске программы DOS берет последний сегмент в цепочке, изагружает туда программу, если этот сегмент достаточно велик. Если оннедостаточно велик, DOS «говорит» Not enough memory иотказывается загружать программу.
Призавершении программы DOS освобождает все блоки, принадлежавшиепрограмме. При этом соседние блоки объединяются. Пока программы, действительно,завершаются в порядке, обратном тому, в котором они запускались, — все вполненормально. Другое дело, что в реальной жизни возможны отклонения от этой схемы.
Например,неявно предполагается, что TSR-программы (Terminate, but StayResident) никогда не пытаются завершиться. Другой пример — отладчики обычнозагружают программу в обход обычной 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-размер страницы).
Предположим,что машина имеет 16-бит слово, позволяющее ей адресоваться к 64К слов. Еслиразмер страницы составит 512 слов, то логическое адресное пространство будетсостоять из 128 страниц. Для идентификатора р необходимо 7 бит, а дляиндекса 9 бит. Полное 16-бит слово будет иметь видИдентификатор — страницы Индекс — слова
Отметим,что случай ЛАП31 30
Вид виртуальной
Страницы
Байт в
странице
гдебиты 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 updatedasynchronously */
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_structfree_area[NR_MEM_TYPES][NR_MEM_LISTS];
где первое поле отвечает за тип области: Ядра, Пользователя,DMA и т.д. И обрабатываются по очень интересному алгоритму.
Страницы делятся на свободные непрерывные области размера 2 встепени x умноженной на размер страницы ((2^x)*PAGE_SIZE). Области одногоразмера лежат в одной области массива.
Таблица 1.Свободные Страницы размера PAGE_SIZE*4 ---> список свободных областей Свободные Страницы размера PAGE_SIZE*2 ---> список свободных областей Свободные Страницы размера PAGE_SIZE ---> список свободных областей
Выделение стараницы выполняется функцией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 — PageTable 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, unsignedlong address, int write_access);
unsigned long (*wppage)(struct vm_area_struct * area, unsignedlong address,
unsigned long page);
int (*swapout)(struct vm_area_struct *, struct page *);
pte_t (*swapin)(struct vm_area_struct *, unsigned long, unsignedlong);
};
Данная структура возникла из идеи виртуальной файловойсистемы, поэтому все операции над виртуальными областями абстрактны и могутбыть специфичными для разных типов памяти, например при отображении файловоперации чтения одни, а при отображении памяти (через файл /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