В. Столлингс - Операционные системы (1114679), страница 68
Текст из файла (страница 68)
нению с д ческим ра лением Отсутствует внут- ренняя фрагмента- ция Каждый процесс рас- пределен за ряд сег- ментов. Процесс за- гружается путем за- грузки всех своих сегментов а динамиче- ские (ке обязательно смежные) разделы тая сегмев- "чапа 7. управление памятью ица 7.1. Технологии управления памятью Основная память рас- пределена на ряд кад- ров равного размера.
Каждый процесс рас- пределен иа некоторое количество страниц равного размера и той же длины, что и кадры. Процесс загружается путем загрузки всех его страниц в доступные, но не обязательно по- следовательные, кадры Незффект исцользоваийй. памяти иэ.за,:, " внутренней, " ментапии,.ф мальное кй процессов '.'й' Неэффект использо процессо необходит4 уплотненийз противо внешней ф „ ментации,:,~ ' Наличие шой а фрагмент Фиксированное распределение В большинстве схем управления памятью мы будем полагать, что операционная система занимает некоторую фиксированную часть основной памяти и что остальная часть основной памяти доступна для использования многочисленным процессам.
Простейшая схема управления этой доступной памятью — ее распределение на области с фиксированными границами. размеры разделов возмо ы два примера фиксированного распреде жность состоит в использовании разделов одинакового размера В этом случае любой процесс, размер которого не превышает размер раздела, может быть заг загружен в любой доступный раздел. Если все разделы заняты и нет ни одного процесса в состоянии готовности или работы, операционная система может выг узить здела и загрузить друтой проце тем самым процессор работой.
П и Ри использовании разделов с одинаковым размером имеются две трудности. П ог Р Рамма может быть слишком велика для размещения в разделе. В этом случае программист должен разрабатывать программу, использующую оверлеи, с тем чтобы в любой момент времени ей требовался только один раздел основной памяти. Когда требуется модуль, который в настоящий момент отсутствует в основной памяти, пользовательская программа должна сама заг ма загрузить этот модуль в раздел памяти программы (независимо от того, является ли этот модуль кодом или данными). Использов льзование основной памяти при этом крайне неэффективно. Любая пр рамма, независимо от ее размера, занимает раздел целиком.
Так, в напрог амм шем и и римере программа размером менее мегабайта все равно будет зани- Алгоритм размещения Чаеть 3. „:~®ава 7. Управление памятью га „целиком раздел в В Мбайт; при этом остаются неиспользов " Мб йт блока. Этот Феномен появления неиспользованной памяти что загружаемый блок по размеру меньше раздела, называется в ей Фрагментацией (1пьегпа) 1гавпзепьа1зоп). а) Разделы одинакового размера б) Разделы разина размеров Рис.
7.2. Пример фиксированного расаределенил б4.мегадайтовой паггяти Бороться с этими трудностями (хотя и не устранить полностью) м твом использования разделов разных размеров (см. рис. 7.2,б). В зт~( рограмма размером 16 Мбайт может обойтись без оверлеев, а раздел~~, амера позволяют уменьшить внутреннюю Фрагментацию при загруз, е малого размера. Я том случае, когда разделы имеют одинаковый размер, размещение процессов в памяти представляет собой тривиальную задачу.
Не имеет значения, в „-эком из свободных разделов будет размещен процесс. Если все разделы заняты процессами, которые не готовы к немедленной работе, любой из них может быть вьггружен для освобождения памяти для нового процесса. Принятие решения о том, какой именно процесс следует выгрузить — задача планировщика (об этом мы поговорим в части 4, "Планирование*'). Когда разделы имеют разные размеры, есть два возможных подхода к назначению процессов разделам памяти. Простейший путь состоит в том„чтобы каждый процесс размещался в наименьшем разделе, способном полностью вместить данный процесс.1 В таком случае для каждого раздела требуется очередь планировщика, в которой хранятся выгруженные из памяти процессы, предназначенные для данного раздела памяти (см.
рис. 7.3,а). Достоинство такого подхода заключается в том, что процессы могут быть распределены между разделамн памяти так, чтобы минимизировать внутреннюю фрагментацию. а) По одной очереди для каждого раздела б) Общая очередь для воок разделов Рис. 7.3. Распределение памяти при фиксированном распределении 'ьотя этот метод представляется оптимальным с точки зрения отдельного дела. он не оптимален с точки зрения системы в целом. Представим, что в Раздела систем еме изображенной на рис. 7.2,6, в некоторый момент времени нет ни одного П во памя При атом предполагается„что заранее известно.
какое максимальное количестггяти может потребоваться процессу, однако зто далеко не всегда так. Если маньков количество необходимой процессу памяти неизвестно, следует использовать ~ряса или виртуальную память. ео Фр -рагментированной становится память, внешняя по отношению ксг! ,лам (в отличие от рассмотренной ранее внутренней Фрагментации). Один из методов преодоления этого явления состоит в уплотн оас11ои): время от времени операционная система перемещает про1, " тп так, чтобы они занимали смежные области памяти; свободная утом со том собирается в один блок. Например, на рис.
7.4,з после уплотнен :я, мы получим блок свободной памяти размером 16 Мбайт, чего мо я вполне достаточно для загрузки нового процесса. Сложность при гнення состоит в том, что при этом расходуется дополнительное е того, уплотнение требует динамического перемещения процессов .е. должна быть обеспечена возможность перемещения программы и :ти основной памяти в другую без потери корректности ее обращений: (см. приложение к данной главе). Алгоритм размещения Поскольку уплотнение памяти вызывает дополнительные расходы вю)ь ессора, разработчик операционной системы должен принять разумное; > том, каким образом размещать процессы в памяти (образно говоря, вм затыкать дыры).
Когда наступает момент загрузки процесса в о ть н имеется несколько блоков свободной памяти достаточного щионная система должна принять решение о том, какой именно свобо использовать. ~ Можно рассматривать три основных алгоритма — наилучший по , первый подходящий, следующий подходящий.
Все они, само с ется, ограничены выбором среди свободных блоков размера, дост шого для размещения процесса. Метод наилучшего подходящего . блок, размер которого наиболее близок к требуемому; метод одящего проверяет все свободные блоки с начала памяти и в ый достаточный по размеру для размещения процесса. Метод сл ~дходяшего работает так же, как и метод первого подходящего, наст проверку с того места, где был выделен блок в последний 1жении конца памяти он продолжает работу с ее начала). На рис. 7.5,а показан пример конфигурации памяти после ряда 1й и выгрузки процессов из памяти. Последним использованным блок размером 22 Мбайт, в котором был создан раздел в 14 Мб 7.б,б показано различие в технологии наилучшего, первого и еле одходящего при выполнении запроса на выделение блока ра :байт.
Метод наилучшего подходящего просматривает все свободи ., выбирает наиболее близкий по размеру блок в 18 Мбайт, ос . мент размером 2 Мбайт. Метод первого подходящего в данной си:, 'ляет Фрагмент свободной памяти размером 6 Мбайт, а метод след, ~дходящего — 20 Мбайт. дополнительный материал по вопросам динамического распределениЯ тель может найгпи в разделе Я.Б (стр. 48д) книги Кнут Д.Э. Искусство гения.
Том 1. Основные алгоритмы, 3-е изд. — М.: Издательский дом " — Прим. Род. Пер~ый 12М подкодящнй 2М Выделенный блок П П Свободный блок 14М Следующий Годходящнй в) До выделения б) После выделения Рис. 7.Б. Пример конгригурации памяти до и после вы. деления блока размером 16 Мбайт Какой из этих методов окажется наилучшим, будет зависеть от точной после ледовательности загрузки и выгрузки процессов и их размеров, Однако (ВА к'877 можно говорить о некоторых обобщенных выводах (см. 1ВВЕИ891, 1ЯНОВ753, '~8771). Обычно алгоритм первого подходящего не только проще, но и быст е Рее и дает лучшие результаты. Алгоритм следующего подходящего, как правило нло, дает немного худшие результаты.
Это связано с тем, что алгоритм след ув дУвщего подходящего проявляет склонность к более частому выделению памяти „ ~оки сво н из свободных блоков в конце памяти. В результате самые большие быстро свободной памяти (которые обычно располагаются в конце памяти) ван,ц, Ро Разбиваются на меньшие Фрагменты и, следовательно, при использоц(е. С, метода следующего подходящего уплотнение должно выполняться чадругой стороны, алгоритм первого подходящего обычно засоряет начао бачит яти небольшими свободными блоками, что приводит к увеличению Реме ни и поиска подходящего блока в последующем. Метод наилучшего под'' одя„г щего, вопреки своему названию, оказывается, как правило, наихудшим. Часть 3.
: ~а 7. управление памятью 369 (3. == (6+1) ) < Ошибка >; ( ~. ~-Г7ис<эк 1 пу», т > ) де~ )1о1~ ('+1); ~~злелить .~":,"~ру нэ,~в~ияийи < ЙОместить лвойниен в список 1 взять первук лиру нз списке 1 >,. 7. Управление памятью как он ищет блоки, наиболее близкие по размеру к требуемому„': 1яет после себя множество очень маленьких блоков. В результат:. каждом выделении впустую тратится наименьшее возможное код'" ' яти, основная память очень быстро засоряется множеством мелк.
' , неспособных удовлетворить ни один запрос (так что при этом ал отнение памяти должно выполняться значительно чаще). Алгоритм замещения В многозадачной системе с использованием динамического распред ахает момент, когда все процессы в основной памяти находятся в заблок оянии, а памяти для дополнительного процесса недостаточно даже дя. Чтобы избежать потерь процессорного времени на ожидание деблов "" явного процесса, операционная система может выгрузить один из ~ >аной памяти, и, таким образом, освободить место для нового процесса, '""' .а в состоянии готовности. Задача операционной системы — опреде нно процесс должен быть выгружен из памяти, Поскольку тема алго ' " ' ~ия будет детально рассматриваться в связи с различными схемами в яти, пока что мы отложим обсуждение этого вопроса.
СтЕМа ДВОИНИКОВ ,:„'-:~~ъ Как фиксированное, так и динамическое распределение памяти и остатки. Фиксированное распределение ограничивает количество цессов и неэффективно использует память при несоответствии м :и разделов и процессов. Динамическое распределение реализуе жно и включает накладные расходы по уплотнению памяти. Ин ~промиссом в этом плане является система двойников (1КХБТ971, 1Р ., В системе двойников память распределяется блоками размером 2", Ъ.
2 — минимальный размер выделяемого блока памяти; 2 — наибольший распределяемый блок; вообще говоря, 2 предст бой размер всей доступной для распределения памяти. Вначале все доступное для распределения пространство рассма единый блок размера 2~. При запросе размером а, та < ~<2", выделяется весь блок, В противном случае блок разде Р-1 а -2 о-! эквивалентных двойника с размерами 2 . Если 2' сю<2 су выделяется один из двух двойников; в противном случае' '.
йников вновь делится пополам. Этот процесс продолжается до,:. :а не будет сгенерирован наименьший блок, размер которого не :тема двойников постоянно ведет список "дыр" (доступных бло,, одого размера 2'. Дыра может быть удалена из списка (1+1) Раз пополам и внесением двух новых дыр размера 2' в список 1. Ко,, йников в списке 1 оказывается освобожденной, они удаляются бъединяются в единый блок в списке (1+1). Ниже приведен рек оритм (11.1ЯТ931) для удовлетворения запроса размера 2' '(1-~2',. ~ осуществляется поиск дыры размером 2~. с( оеС Ьо1е (1пс 1) Г На рис. ~.6 приведен пример использования блока с начальным разме- 1 Мбайт. Первый запрос А — на 1ОО Кбайт (для него требуется блок азмерам 128 Кбайт). Для этого начальный блок делится на два двойника по 512 Кбайт.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
