Мех-мы упр-я дин-кой пам.

Стек.

стек - это дин-ки распределяемая пам, к-я хар-ся сл св-ми: 1. стек – это обл пам, к-я вкл все эл-ты сосмежными адресами; 2. стек имеет фикс размер; 3. эл-т, к-рый последним помещ-ся в стек, наз его вершиной; 4. указ-ль вершины стека изм-ся при кажд вкл-нии и искл-нии эл-та в/из стек(а); 5. реализ-ся дисц LIFO; 6. При вкл-нии эл-та в сте указ-ль вершины уменьшается, при искл-нии увел-ся;

7. для реал-ции такой модели управления пам-ю треб-ся 2 зн-я – базовый адр и ук-ль вершины; 8. В Intel эта модель поддерж-ся аппар-но (спец сегм стека); 9.Исп-я доп рег-р можно получить доступ к эл-там стека, к-е не явл вершиной. Только их нельзя вытолкнуть до тех пор, пока они не окажутся на верш; 10. Аппар-но поддерж-ся команды, к-е позв моместить или извлечь сзазу неск эл-тов стека. Начальное распред-е пам в стеке сводится к уменьш-ю SP, т о резервируется часть стека. Сущ стеки разл типов. В частн стек выр-ний – для хранения промежут рез-тов выч-ний, для проц-р – МТ.

Куча.

Куча – это обл дин-ки распред-мой пам, вкл эл-ты со смежными адресами. Пам в этой обл может выдел-ся и освоб-ся в произв пор, не сущ какой-л дисц. При нач распред-ии пам размер обл-ти известен, пам можем зарезерв-ть. Нужен указ-ль своб простр-ва. Одного указ-ля недост, т к пам распр-ся как попало, нужны спец мех-мы и ср-ва для дин выд-я и освоб-я пам.

Треб-ся отслеж-ть своб простр-во, вкл-щее эл-ты, доступные для распред-я, треб-ся спец мех-м утилизации – освоб-я использ-ных эл-тов, вкл-е их в своб простр-во. 1 способ реал-ции этих мех-мов – маркировка. Кажд своб эл-т кучи помеч-ся спец конст-той (зарезерв), т е признаком того, что он свободен. Для эл-тов кучи фикс-го размера работа с кучей: придин-ком выд-нии пам сист должна делать еребор в поисках своб эл-та, помеченного маркером. Долгий поиск – неэф-но. С освоб-ем проблем нет – указ-ль известен.

Зарезерв конст может совпасть с данными, исп-мыми в пр-мме. Для блоков перем длины в кажд блоке нужно хранить еще и длину блока – т е сразу за конст – длина своб блока. Резерв-ся часть пам в куче под хран-е служеб инф-ии (F=const 0 or 1 теперь);

2 способ – создание списка своб простр-в: в кажд своб-ый эл-т кучи вкл-ся ссылка на след своб эл-т. Т о строится лин список из своб эл-тов. Ситт для отслеживания всего списка кужно знать ссылк на 1-й своб эл-т. При нач распред-ии эл-ты фикс длины. При освоб-нии эл-ты вкл-ся в начало списка.

Эл-ты освоб-ся в произв пор. Эл-ты кучи перем разм:

Осн проблнмы: когда треб-ся выделить эл-т, т к сист должна подобрать своб эл-т подход разм. Сущ те же стратегии: 1)Пробегаем по списку, нач от1-го, выдел-ет 1-ый эл-т, разм к-го > запрошенного, сист отрезает от него кусочек, перебрасывает ссылки, меняет длину. Т О сист при распред-нии пам прих-ся искл-ть эл-т из списка своб блоков, пренастраивать указ-ль на оставшуюся своб часть и вычислять ее размер. Если размеры мал-кие – возникает проблема фрагментации пам => проблема уплотнения; 2)Выд-е наиб подход-го по размеру блока; 3) Выдел-е наим подход-го по разм блока. Для 2-3: список своб простр-в должен быть упор-н. 2 способ – утилизации своб блоков в куче – метод близнецов (для ПП): допускает распред-е эл-тов размером степени двойки. Создаются неск списков своб простр-в – для блоков кажд размера. Если нет блока опр-го размера – сист берет блок в 2р больше и режет его пополам, перестраивает списки. При освоб-нии пам - если сист видит, что у блока есть близнец – рядом нах-ся блок – она их сливает обратно.