Распределение памяти в многозадачных системах

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

В первых ОС память размещалась очень просто – каждая программа начиналась с одного и того же адреса т.е. каждая следующая накладывалась на предыдущую. Если часть программы оставалась в памяти, то при следующей загрузке догружалась только недостающая часть. Например:

память	выполнение задачи 1	выполнение задачи 2	выполнение задачи 3	выполнение задачи 2
0 000 - 5 000	Система	Система		Система
10 000	задача 1	задача 2	задача 3	догрузка 2
15 000	задача 2	задача 2
20 000
25 000	свободная память
	свободная память	свободная память	свободная память

В этом примере для загрузки задачи 2 повторно не требуется загружать ее всю (т.к. часть ее уже находится в памяти), а только недостающую часть, которую использовала задача 3 до этого..

Однако такое распределение неэффективно. Например, задачу3 можно было разместить в свободном участке и тогда задачу2 не пришлось бы повторно догружать. Поэтому появились другие системы распределения памяти:

раздел 8М

раздел 8М

раздел 8М

раздел 8М

...

Фиксированное распределение:

вся память делится на одинаковые части – разделы. Каждой программе отводится свой раздел. Однако для маленьких программ, большая часть раздела остается неиспользованной (это называется внутренней фрагментацией), а для больших программ одного раздела недостаточно и приходится программисту использовать «оверлеи» т.е. распределять размещение данных в памяти в нескольких разделах, а затем позаботиться о переключении на использование то одного, то другого раздела, так как в каждый момент работы должен использоваться только один раздел. Т.е. программист сам должен позаботиться о распределении памяти, что сильно усложняет его работу и требует много времени на разработку программ.
Бороться с этим можно путем использования фиксированных разделов разного размера:

2М

4М

8М

8М

16М

...

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

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

1 прогр

2 прогр

4 прогр

6пр

...

система «двойников»: это был компромисс между динамическим и фиксированным распределением, по которому память выделялась блоками размером 2^к. Допустим вся память размером 1 М, тогда для размещения программы 100кБ подбирается блок следующим образом: вся память делится пополам (т.е. на 2 части по 512 кБ), затем снова пополам (по 128Кб) и отводится для программы кусок 128Кб т.к. при следующем делении программа уже не разместится. По такому же принципу размещаются остальные программы в оставшейся части памяти. При образовании двух подряд одинаковых свободных кусков они объединяются в один блок. Например, при запросе на размещение программ А(=100Кб), В (=186 Кб) и С(=52Кб) они будут размещены последовательно так:

А - 128	128 Кб	256 Кб	512 Кб
А - 128	128 Кб	В - 256	512 Кб
А - 128	С-64	64Кб	В - 256	512 Кб

Страничная организация: Вся память разбивается на небольшие блоки одинакового размера – страницы. Для каждой программы отводится необходимое ей количество страниц. При этом страницы могут находиться не подряд, а вразброс. Поэтому для каждой программы создается своя таблица страниц. Реальный адрес памяти формируется из логического адреса, который состоит из номера страницы и смещения внутри страницы. Преобразование адреса выполняет система невидимо для программиста. За счет малых размеров страниц внутренняя фрагментация небольшая, а внешняя отсутствует.

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

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