Розподіл пам&#39;яті

Розподіл пам'яті

Введення
1. Області даних
2. Описувачі
3. Пам'ять для даних елементарних типів
4. Пам'ять для масивів
Вектори
Матриці
Багатовимірні масиви
5. Пам'ять для структур
Записи з Хоору
Структури PL/1
Структури даних по Стендішу
6. Відповідність фактичних і формальних параметрів
Виклик за посиланням
Виклик за значенням
Виклик за результатом
Фіктивні аргументи
Виклик на ім'я
Імена масивів в якості фактичних параметрів
Імена процедур в якості фактичних параметрів
7. Динамічний розподіл пам'яті
Метод позначених меж для розподілу пам'яті
Прибирання сміття
Системи з дворівневим розподілом пам'яті
8. Об'єктно-орієнтовані мови. Нові інформаційні
структури і пам'ять для них
Введення
Завданням розподілу пам'яті є обчислення адрес
для фрагментів програми та інформаційних об'єктів, виходячи з
фіксованої при генерації взаємного їх розташування, причому
для адрес тих об'єктів, розташування яких у пам'яті не можна
визначити статично (при трансляції), генеруються
динамічні обчислення цих адрес.
Інформаційні об'єкти в процесі еволюції мов
програмування також розвивалися - від простих змінних
цілого, символьного типів до субстанцій якими оперують
сучасні об'єктно-орієнтовані мови. Нижче будуть
викладені механізми розподілу пам'яті для самих
різноманітних інформаційних об'єктів.
1. Області даних
Областю даних є ряд послідовних комірок - блок
оперативної пам'яті, - виділений для даних, якимось чином
об'єднаних логічно. Часто (але не завжди) всі комірки
області даних належать одній і тій же області дії в
програмі мовою оригіналу; до них може звертатися один і той
самий набір інструкцій (тобто цією областю дії може бути блок
або тіло процедури).
Під час компіляції осередок для будь-якої змінної часу
рахунку може бути представлена впорядкованою парою чисел (номер
області даних, зсув), де номер області даних - це
деякий єдиний номер, присвоєний області даних, а
зсув - це адреса змінної щодо початку області
даних. Коли ми генеруємо команди звернення до змінної, ця
пара переводиться в дійсну адресу змінної. Це звичайно
виконується установкою адреси бази (машинного адреси першого
комірки) області даних на регістр та обігу до змінної по
адресою, рівному зсуву плюс вміст регістру. Пара (номер
області даних, зсув) таким чином переводиться в пару
(Адреса бази, зсув).
Області даних діляться на два класи - статичний і
динамічний. Статична область даних має постійне число
осередків, виділених їй перед початком рахунку. Ці комірки виділяються
на весь час рахунку. Отже, на змінну в статичної
області даних можлива ссилка на її абсолютному адресою замість
пари (адреса бази, зсув).
Динамічна область даних не завжди присутня під час
рахунку. Вона з'являється і зникає, і кожного разу, коли вона
зникає, втрачаються всі величини, що зберігаються в ній.
2. Описувачі
Якщо компілятор знає всі характеристики змінних під
час компіляції, то він може згенерувати повністю команди
звернення до змінних, грунтуючись на цих характеристиках. Але
в багатьох випадках інформація може задаватися динамічно під
час рахунку. Наприклад, у АЛГОЛ не відомі нижня і верхня
кордону розмірностей масивів, а в деяких мовах тип
фактичних параметрів не відповідає точно типу формальних
параметрів. У таких випадках компілятор не може згенерувати
прості та ефективні команди, так як він повинен враховувати всі
можливі варіанти характеристик.
Щоб вирішити це завдання, компілятор виділяє пам'ять не
тільки для змінних, але і для їх описувачів, які містять
атрибути (характеристики), які визначаються під час рахунку. Цей
описувач заповнюється і змінюється в міру того, як стають
відомими і змінюються характеристики за рахунку.
Візьмемо простий приклад: якщо формальний параметр є
простий змінної і тип відповідного фактичного параметра
може змінюватися, фактичний параметр, який передається процедурою,
може виглядати, наприклад, так:
?????????????????????????????????????????????????? ?????????????? ? Описувач 0 = дійсний, 1 = цілий, 2 = бульових і т.д. ?
?????????????????????????????????????????????????? ?????????????? ? Адреса значення (або саме значення)?
?????????????????????????????????????????????????? ?????????????? Якщо в процедурі є звернення до формального параметру,
процедура повинна запитувати або інтерпретувати цей описувач
і потім виконати будь-яке необхідне перетворення типу. Ці
дії можна, звичайно, виконати, звертаючись до іншої програми.
У багатьох випадках компілятор не може виделіт' пам'ять для
значень змінних, так як невідомі атрибути розмірності.
Так відбувається з масивами в АЛГОЛ. Все, що компілятор може
зробити, - це виділити пам'ять в області даних для описувача
фіксованої довжини, що описує змінну. Під час
виконання програми, коли стануть відомі розмірності, буде
викликана програма GETAREA (яка найчастіше є функцією
операційної системи), яка виділить пам'ять і занесе в
описувач адресу цієї пам'яті. При цьому посилання на значення завжди
виконується за допомогою такого описувача.
Для структур або записів потрібні більш складні Описувачі,
в яких вказується, як пов'язані між собою компоненти й
подкомпоненти. Ці механізми будуть розглянуті нижче.
Чим більше атрибутів можуть змінюватися за рахунку, тим більше
доводиться виконувати роботи під час рахунку.
3. Пам'ять для даних елементарних типів
Типи даних вихідної програми повинні бути відображені на
типи даних машини. Для деяких типів це буде відповідністю
один до одного (цілі, речові і т. д.), для інших можуть
знадобитися кілька машинних слів. Можна відзначити наступне:
1) Цілі змінні звичайно містяться в одному слові або
комірці області даних; значення зберігається у вигляді стандартного
внутрішнього зображення цілого числа в машині.
2) Речові змінні звичайно містяться в одному слові.
Якщо бажана велика точність, ніж можливо представити в
одному слові, то може бути застосований машинний формат подвійного
слова з плаваючою комою. У машинах, де відсутня формат з
плаваючою комою, можуть бути вжиті два слова - одне
для показника ступеня, друга для (нормалізувати) мантиси.
Операції з плаваючою комою в цьому випадку повинні виконуватися з
допомогою підпрограм.
3) Булеві або логічні змінні можуть міститися в
одному слові, причому нуль зображує значення FALSE, а не нуль або
1 - значення TRUE. Конкретне уявлення для TRUE і FALSE
визначається командами машини, що здійснюють логічні
операції. Для кожної булевої змінної можна також використовувати
один біт і розмістити в одному слові кілька бульових змінних
або констант.
4) Покажчик - це адреса іншого значення (або посилання на
нього). У деяких випадках буває необхідно представляти
покажчик у двох послідовних клітинках; один осередок містить
посилання на описувач або є описувачем поточної величини,
на яку посилається вказівник, у той час як інша вказує
власне на значення величини. Це буває необхідно в разі
коли під час компіляції неможливо визначити для кожного
використання покажчика тип величини, на яку він посилається.
4. Пам'ять для масивів
Ми припускаємо, що кожен елемент масиву або вектора
займає в пам'яті одне відділення. Випадок більшого числа клітинок
повністю аналогічний.
Вектори
Елементи векторів (одновимірних масивів) зазвичай містяться
в послідовних клітинках області даних у порядку зростання
або зменшення адрес. Порядок залежить від машини і її системи
команд.
Ми припускаємо, що використовується стандартний зростаючий
порядок, тобто елементи масиву, визначеного описом
ARRAY А [1:10], розміщуються в порядку А [1], А [2], ..., А [10].
Матриці
Існує кілька способів розміщення двовимірних масивів.
Звичайний спосіб полягає в зберіганні їх в області даних по рядках
у порядку зростання, тобто (для масиву, описаного як
ARRAY А [1: M, 1: N], у порядку
А [1, 1], А [1, 2], ..., А [1, N],
А [2, 1], А [2, 2], ..., А [2, N],
...
А [M, 1], А [M, 2], ..., А [M, N].
Вид послідовності показує, що елемент А [i, j] знаходиться
в комірці з адресою ADDRESS (A [1, 1]) + (i-1) * N + (j-1) який
можна записати так: (ADDRESS (A [1, 1]) - N - 1) + (i * N + j)
Перше доданок є константою, і його потрібно обчислити
тільки один раз. Таким чином, для визначення адреси А [i, j]
необхідно виконати одну множення і два складання.
Другий метод полягає в тому, що виділяється окрема галузь
даних для кожного рядка і є вектор вказівників для цих
областей даних. Елементи кожного рядка розміщуються у сусідніх
осередках в порядку зростання. Так, опис ARRAY А [1: M, 1: N]
породжує
?????????????????????????? ??????????????????????? ? Покажчик на рядок 1 ??????????? A [1, 1] ... A [1, N]?
?????????????????????????? ??????????????????????? ? Покажчик на рядок 2 ????????? ??????????????????????? ?????????????????????????? ??? A [2, 1] ... A [2, N]?
? ... ? ??????????????????????? ?????????????????????????? ??????????????????????? ? Покажчик на рядок M ??????????? A [M, 1] ... A [M, N]?
?????????????????????????? ??????????????????????? Вектор покажчиків строк зберігається в тій області даних, з якою
асоціюється масив, у той час як власне масив зберігається
в окремій області даних. Адреса елемента масиву А [i, j] є
CONTENTS (i-1) + (j-1).
Перша перевага цього методу полягає в тому, що при
обчисленні адреси не потрібно виконувати операцію множення. Іншим
є те, що не всі рядки можуть перебувати в оперативній
пам'яті одночасно. Покажчик рядка може містити деякий
значення, яке викличе апаратне або програмне переривання
у випадку, якщо рядок в пам'яті відсутній. Коли виникає
переривання, рядок вводиться в оперативну пам'ять з на місце
іншого рядка.
Якщо всі рядки перебувають в оперативній пам'яті, то масив
вимагає більше місця, оскільки необхідно місце і для вектора
покажчиків.
Коли відомо, що матриці розріджені (більшість
елементів - нулі), використовуються інші методи. Може бути
застосована схема хеш-адресації, яка базується на значеннях i
і j елемента масиву А [i, j] і посилається по хеш-адресою на
щодо коротку таблицю елементів масиву. У таблиці
зберігаються тільки ненульові елементи матриці.
Багатовимірні масиви
Ми розглянемо розміщення в пам'яті і звернення до
багатовимірним масивів, описаним, наступним чином:
ARRAY A [L1: U1, L2: U2, ..., Ln: Un]
Метод полягає в узагальненні першого методу, запропонованого для
двовимірного випадку; він також застосовний і для одновимірного масиву.
Подмассів A [i, *, ..., *] містить послідовність
A [L1, *, ..., *], A [L1 1, *, ..., *], і т.д. до A [U1, *, ..., *].
Всередині подмассіва A [i, *, ..., *] знаходяться подмассіви
A [i, L2, *, ..., *], A [i, L2 1, *, ..., *], ... і A [i, U2, *, ..., *].
Це повторюється для кожного виміру. Так, якщо ми просуваємося
в порядку зростання за елементами масиву, швидше змінюються
останні індекси:
????????????????????????????????????????? ??????????? ????????? ? подмассів A [L1]? ? A [L1 1]? ? A [U1]?
? ?????????? ???????????? ??????????? ? ? ? ?
? ? A [L1, L2]? ? A [L1, L2 1]? ... ? A [L1, U2]?? ? ? ... ? ?
? ?????????? ???????????? ??????????? ? ? ? ?
????????????????????????????????????????? ??????????? ????????? Питання полягає в тому, як звернутися до елементу
A [i, j, k, ..., l, m]. Позначимо
d1 = U1-L1 1, d2 = U2-L2 1, ..., dn = Un-Ln 1.
Тобто d1 є число різних значень індексів в i-том
вимірі. За логікою двовимірного випадку, ми знаходимо початок
подмассіва A [i, *, ..., *]
BASELOC + (i-L1) * d2 * d3 *...* dn
Де BASELOC - адреса першого елемента A [L1, L2 ,..., Ln], а
d2 * d3 *...* dn - розмір кожного подмассіва A [i ,*,...,*]. Початок
подмассіва A [i, j ,*,...,*] знаходиться потім додаванням
(j-L2) * d3 *...* dn до отриманого значення.
Діючи далі таким же чином, ми остаточно отримаємо:
BASELOC + (i-L1) * d2 * d3 *...* dn + (j-L2) * d3 *...* dn
+ (K-L3) * d4 *...* dn + ... + (I - Ln-1) * dn + m - Ln
Виконуючи множення, отримуємо CONST_PART + VAR_PART, де
CONST_PART = BASELOC - ((...( L1 * d2 + L2) * d3 + L3) * d4 +...+ Ln-1) * dn + Ln)
VAR_PART = (...(( i * d2) + j) * d3 +...+ 1) * dn + m
Значення CONST_PART необхідно обчислити тільки 1 раз і
запам'ятати, тому що воно залежить лише від нижніх і верхніх меж
індексів і місця розташування масиву в пам'яті. VAR_PART залежить від
значень індексів i, j ,..., m і від розмірів вимірювань d2, d3 ,..., dn. Обчислення VAR_PART можна представити в більш наочному вигляді:
VAR_PART = перший індекс (i)
VAR_PART = VAR_PART * d2 + другий індекс (j)
VAR_PART = VAR_PART * d3 + третій індекс (k)
..... VAR_PART = VAR_PART * dn + n-й індекс (m)
Інформаційні вектори
У деяких мовах верхня і нижня межі масивів відомі
під час трансляції, тому компілятор може виділити пам'ять для
масивів і сформувати команди, що мають посилання на елементи масиву,
???????????????? ? L1? U1? d1?
???????????????? ? L2? U2? d2?
? . ? . ? . ? Опис масиву
? . ? . ? . ? A [L1: U1 ,..., Ln: Un]
? . ? . ? . ?
? Ln? Un? dn?
???????????????? ? n? CONSTPART?
???????????????? ? BASELOC?
???????????????? Рис. . Інформаційний вектор для масиву
використовуючи верхні та нижні межі і постійні значення d1, d2, ..
., dn. В інших мовах це неможливо тому що кордони можуть
обчислюватися під час рахунку. Тому потрібен описувач для масиву,
що містить необхідну інформацію. Цей описатель для масиву
називається допвектор (dope vector) або інформаційний вектор.
Інформаційний вектор має фіксований розмір, який
відомий при компіляції, отже, пам'ять для нього може
бути відведена під час компіляції в області даних, з якою
асоціюється масив. Пам'ять для самого масиву не може бути
відведена до тих пір, поки під час рахунку не виконається вхід в
блок, і якому описано масив. При вході в блок обчислюються
кордону масиву і здійснюється звернення до програми
розподілу пам'яті для масивів. Тут же вноситься в
інформаційний вектор необхідна інформація.
Яка інформація заноситься в інформаційний вектор? Для
запропонованої вище n-мірної схеми нам як мінімум потрібні d2, ... dn
і CONST_PART. Якщо перед зверненням до масиву потрібно перевіряти
правильність завдання індексів, то слід також занести в
інформаційний вектор значення верхніх і нижніх меж.
5. Пам'ять для структур
Існує декілька альтернатив для визначення нових
типів даних як структур, складених з типів даних,
визначених раніше. Величини такого типу ми називаємо
структурними величинами. Існують різні підходи до
реалізації цих конструкцій. Відмінності звичайно стосуються наступних
питань:
Як пам `ятi для структурних величин?
Як будувати структурні величини?
Як посилатися на компоненту структурної величини?
Як звільняти пам'ять?
Записи з Хоору
Визначення нового типу даних має вигляд
RECORD (,
,. . . ,)
де кожна компонента має вигляд

Причому є одним з основних типів мови -
REAL, INTEGER, POINTER і т.д. Тут під час компіляції відомі
всі характеристики всіх компонент, включаючи тип даних, на які
можуть посилатися покажчики. Під час рахунку не потрібні Описувачі ні
для самої структури, ні для її компонент, причому може бути
сгенерирована ефективна програма.
Будь-яка структурна величина з n компонентами може зберігатися в
пам'яті у вигляді:
?????????????????????????????????????????????????? ?????? ? Компонента 1? Компонента 2? ... ? Компонента n?
?????????????????????????????????????????????????? ?????? Оскільки при компіляції відомі всі характеристики, то
відомий також обсяг пам'яті, необхідний для кожної компоненти,
і, отже, компілятор знає зміщення кожної компоненти
щодо початку структурної величини. Для спрощення збору
сміття найкраще присвоїти номер кожного типу даних (включаючи
типи, визначені програмістом) і мати описувач для кожного
покажчика. Описувач буде містити номер, що описує тип
величини, на яку в даний момент посилається вказівник.
Пам'ять для покажчиків і їх описувачів може бути виділена
компілятором в області даних, з якою вони пов'язані; це не
важко, тому що вони мають фіксовану довжину. Для зберігання
поточних значень структурних величин може бути використана
окрема статічес?? а область даних і спеціальна програма для
виділення пам'яті в цій галузі. У розглянутих мовах немає
явного оператора для звільнення пам'яті, так що, коли пам'ять
вичерпана, система звертається до програми "збирання сміття".
Зауважимо, що для того, щоб мати змогу виявити сміття,
потрібно знати, де розташовані всі покажчики, включаючи ті, які
є компонентами структурних величин.
Структури PL/1
Більш складну конструкцію мають структури, в яких
компоненти можуть самі мати подкомпоненти. Приклад таких
структур - структури мови PL/1. Така структура є дерево,
вузли якого пов'язані з іменами компонент, а кінцеві вузли
мають значення даних.
Якщо б можливість мати подкомпоненти була б
єдиною відмінністю між записами за Хоору і структурами
PL/1 не було б істотної різниці під час виконання
програми; можна було б розмістити всі компоненти і
подкомпоненти так, щоб кожна мала фіксоване зсув
щодо початку структури і це зміщення було б відомо під
час компіляції. Проте в мові PL/1 існує ще два
розширення. З метою економії пам'яті атрибут CELL для компоненти
вимагає, щоб всі її подкомпоненти неодмінно займали одне й
теж місце в пам'яті. У будь-який заданий час тільки одна з
кількох змінних може мати значення. Присвоєння значення
подкомпоненте призводить до того, що подкомпонента, до якої
зверталися раніше втрачає своє значення.
Подібна можливість викличе ускладнення під час компіляції,
але насправді не дуже змінює код готової програми,
якщо тільки об'єктна програма не повинна перевіряти при кожному
зверненні до подкомпоненте, що значення подкомпоненти
дійсно існує.
Для іншого розширення потрібні більш складні
адміністративні функції під час виконання програми. В PL/1
кореневий вузол структурного дерева або будь-яка з подкомпонент можуть
бути забезпечені розмірностями.
Так як вирази, які визначають межі зміни
індексів, повинні бути обчислені при виконанні програми, для
них, як і у випадку масивів, слід употреблят' опітелі, або
інформаційні вектори. Тобто нам необхідні інформаційні
вектори для всіх компонент що мають велику розмірність одиниці.
Структури даних по Стендішу
Наступний крок у розвитку - структури даних, які не
можуть бути реалізовані ефективно, але які багатше і могутніше.
Структури даних запропоновані Стендішом змінюються під час
роботи програми. Динамічно можуть змінюватися не тільки
розмірності компонент, але і число компопонент та їх типи.
Зазвичай під час компіляції нічого не відомо, а все робиться
під час виконання програми на основі описувачів, які
самі будуються в цей же час.
Під час виконання програми необхідно зберігати описувач
для кожної структурної величини. Дійсно, цей описувач
аналогічний набору елементів таблиці символів, що використовується
компілятором при компіляції, скажімо, структур PL/1. Такі
опису структур найкраще реалізуються у формі дерева, де
для кожного вузла повинно бути принаймні відомо:
1) кінцевий чи це вузол чи ні;
2) якщо вузол кінцевий, то який його тип;
3) якщо вузол кінцевий, то покажчик на значення, якщо
таке існує;
4) якщо вузол не кінцевий, то покажчики на вузли для
подкомпонент;
5) розмірності подкомпонент.
Кожного разу при зверненні до значення компоненти повинен бути
проінтерпретувати описувач. Починаючи з кореневого вузла, знаходиться
шлях до вузла, до якого звертаються, перевіряється тип цього вузла й,
нарешті, використовується або змінюється його значення.
6. Відповідність фактичних і формальних параметрів
Розглянемо різні типи формальних параметрів і їх
відповідність фактичним параметрам і покажемо, як кожен з них
може бути реалізований. Під формальним параметром ми розуміємо
ідентифікатор у процедурі, який замінюється іншим
ідентифікатором або виразом при виклику процедури.
При зверненні до процедури, скажімо, встановлюється деяким
чином зв'язок між формальними параметрами і фактичними
параметрами.
Коли в якому-небудь мовою відбувається звертання до процедури,
їй передається список адрес аргументів. Процедура переписує
ці адреси в свою власну область даних і використовує їх для
встановлення відповідності фактичних і формальних параметрів.
Крім фактичних параметрів, часто є декілька неявних
параметрів, про які програміст не знає. Один з них це,
звичайно, адреса повернення. Отже, що викликається процедурі
передається список такого вигляду:
неявний параметр 1
.
.
.
неявниі параметр m
адреса фактичного параметра 1
.
.
.
адреса фактичного параметра n
Які в мене є адреси в списку? Це залежить від мови
і від типу параметра. Ніші перераховані типи параметрів, які
ми будемо розглядати:
1) виклик за посиланням;
2) виклик за значенням;
3) виклик по результату;
4) фіктивні аргументи;
5) виклик по імені;
6) імена масивів в якості фактичних параметрів;
7) імена процедур в якості фактичних параметрів.
Виклик за посиланням (by reference)
Цей тип параметра найпростіший для реалізації.
Фактичний параметр обробляється під час виконання
програми перед викликом, якщо він не є змінною або
константою, він обчислюється і запам'ятовується в тимчасовій комірці.
Потім обчислюється адреса (змінної, константи або тимчасової
комірки), і ця адреса передається викликається процедурою.
Її викликає процедура використовує його для посилання на комірку (комірки),
містить значення.
Виклик за значенням (by value)
При цьому типі відповідності формального і фактичного
параметрів викликається процедура має клітинку, виділену в її
області даних для значення формального параметра цього типу. Як
і при виклику за посиланням, адреса фактичного параметра обчислюється
перед викликом і передається викликається процедурі в списку
параметрів. Однак перед фактичним початком виконання процедура
вибирає значення за адресою та заносить його у свою власну
клітинку. Ця комірка потім використовується як осередок для величини
точно так само, як будь-яка змінна, локалізована у процедурі.
Таким чином, немає ніякого способу змінити в процедурі значення
фактичного параметра.
Виклик за результатом (by result)
У мові АЛГОЛ W для будь-якого формального параметра Х,
оголошеного параметром RESULT, справедливо наступне:
1. Для параметра Х відводиться осередок в області даних
процедури. Ця комірка використовується в процедурі як локалізована
осередок для змінної Х.
2. Як і у випадку параметра VALUE, при ризоре при виклику
процедури обчислюється і передається адреса фактичного параметра.
3. Коли виконання процедури закінчується, отримане
значення Х запам'ятовується за адресою, описаного в п.2.
Іншими словами, параметр RESULT є змінна,
локалізована в процедурі, значення якої при виході
запам'ятовується у відповідному фактичному параметрі (який
повинен бути звичайно, змінної). Поняття RESULT було
призначене для того, щоб доповнити в АЛГОЛ виклик на ім'я
(Який описаний нижче), оскільки останній дуже неефективний і
володіє великими можливостями, ніж це необхідно в
більшості випадків.
Фіктивні аргументи
У розвинених мовах наступні фактичні параметри
обробляються по-різному:
1) константи;
2) вирази, які не є змінними;
З) змінні, чиї характеристики відрізняються від функцій
вказаних для відповідних формальних параметрів.
Для такого фактичного параметра в викликає процедурі
заводиться тимчасова змінна. Фактичний параметр обчислюється
і запам'ятовується в тимчасовій переменпой, і адресу цієї змінної
передається в списку параметрів. Така мінлива називається
фіктивним аргументом.
Виклик на ім'я
Згідно з повідомленням про мову АЛГОЛ, використання виклику
параметра на ім'я означає буквальну заміну імені формального
параметра фактичним параметром.
Отримати ефективну реалізацію за допомогою такої текстової
заміни, звичайно, не можна, і ми повинні розробити відповідний
еквівалентний спосіб.
Звичайний спосіб реалізації виклику параметрів на ім'я
полягає в тому, щоб мати окрему програму або процедуру в
об'єктному коді для кожного такого параметра. Для такої програми
було введено термін "санки" (thunk). Коли відбувається виклик санки,
він обчислює значення фактичного параметра (якщо цей параметр
НЕ мінлива) і передає адресу цього значення. У тілі процедури
при кожному посиланні на формальний параметр відбувається виклик санки,
після чого для звернення до потрібного значення використовується
переданий Санком адресу.
Різниця між викликом за посиланням і викликом на ім'я
полягає в наступному: адреса фактичного параметра,
викликається за посиланням, обчислюється тільки один раз, перед
фактичним входом до процедури, в той час як для виклику по
імені адреса обчислюється кожного разу, коли в тілі процедури є
звернення до формального параметру.
Ім'я масиву в якості фактичного параметра
У цьому випадку і фактичний, і формальний параметр повинні
бути масивами. Процедура передається адреса першого елемента
масиву (для мов, які не вимагають інформаційних
векторів) або адресу інформаційного вектора, і ця адреса
використовується процедурою для посилання на елементи масиву.
Назва процедури в якості фактичного параметра
Надсилаєте адреса - це адреса першої команди процедури,
яка зустрілася в якості фактичного параметра. Якщо це
ім'я саме є формальним параметром, то адреса був переданий
що викликає процедурою, коли вона викликалася.
7. Динамічний розподіл пам'яті
Для деяких мов потрібно схема динамічного
розподілу пам'яті під час виконання програми, коли блоки
внутрішньої пам'яті виділяються, використовуються і потім звільняються
для подальшого використання.
Існують два основні методи загального розподілу пам'яті.
В обох методах викликається певна програма GETAREA (ADDRESS,
SIZE) для того, щоб виділити область з SIZE осередків; програма
записує в клітинку ADDRESS, адресу цієї області. У першому методі
пам'ять повинна звільнятися "явно" за допомогою виклику програми
FREEAREA (ADDRESS, SIZE). У другому методі пам'ять "явно" не
звільняється. Замість цього в тих випадках, коли GETAREA не
може знайти область необхідного розміру, вона викликає програму
FREEGARBAGE для того, щоб знайти ті області у внутрішній
пам'яті, які не використовуються програмою, і повернути їх системі.
Крім того вона може ущільнити використовувані області - зрушити
їх разом, щоб усі вільні осередки були в одному блоці.
Опишемо один зі способів реалізації першого методу.
Метод позначених меж для розподілу пам'яті
Розподіл пам'яті відбувається наступним чином. Коли
починає виконуватися програма, як вільна пам'яті
використовується один великий блок осередків. При виконанні програми
може кілька разів викликатися GETAREA. Кожного разу вона виділяє
необхідні комірки, починаючи від початку вільного блоку пам'яті, і
блок набуває наступний вигляд:
?????????????????????????????????????????????????? ??????????? ? Зайнято? Зайнято? ... ? Зайнято? Вільно?
?????????????????????????????????????????????????? ??????????? Зауважимо, що розміри зайнятих областей можуть бути
різними. У певний момент буде викликана FREEAREA, щоб
звільнити одну з використаних областей, взагалі кажучи, не
останню. Після кількох дзвінків GETAREA і FREEAREA блок
може виглядати так:
?????????????????????????????????????????????????? ?????????? ? Зайнято? Зайнято? Вільно? ... ? Зайнято? Вільно?
?????????????????????????????????????????????????? ?????????? де як і раніше розміри областей різні. Система повинна
пам'ятати розташування всіх вільних областей, з тим щоб вони
могли бути знову використані. Більш того, суміжні вільні
області слід зливати в одну вільну область так, щоб
пам'ять не виявилася розбитою на області, занадто малі для
використання.
, Котрий ми описуємо метод позначених меж належить
Кнута. Метод вимагає резервування для системних потреб 2-х
осередків на кордонах кожної області (одній на початку і одній в
кінці). Це прийнятна плата, тому що у випадках, в яких
застосовується цей метод, потрібні досить великі області,
наприклад області даних процедур і пам'ять для масивів.
Перевага цього методу в тому, що необхідно по суті
фіксований час, щоб звільнити область і об'єднати її
з суміжними вільними областями, якщо це можливо. В інших
методах для цієї мети потрібно перегляд деякого списку.
Нижче приводиться формат кожної використаної та вільної області.
Перше слово містить поле TAG, яке вказує, чи вільна
область чи ні; в полі SIZE міститься кількість слів області.
Вільні області зв'язуються разом в двусвязанний список. Поле
FLINK (посилання вперед) вказує на наступну область списку, в
той час як поле BLINK (посилання тому) вказує на попередню
область.
?????????????????????????????? перший ?????????????????????????????? ? TAG? SIZE? BLINK? FLINK? слово? TAG? SIZE? ?
?????????????????????????????? ?????????????????????????????? ? ? SIZE-2? ?
? ? слів? ?
? ? ? ?
?????????????????????????????? останнім ?????????????????????????????? ? TAG? SIZE? ? неї? TAG? ?
?????????????????????????????? слово ?????????????????????????????? Вільна область резервованих область
Крім того, існує одна змінна FREE наступного виду:
TAG SIZE BLINK FLINK
??????????????????????????????????????????????????
FREE? +? 0? на останню? на першому?
? ? ? область в списку? область в списку?
??????????????????????????????????????????????????
Поле BLINK перший області в списку вказує на комірку FREE, так
само, як і поле FLINK останньої області. Нарешті, ми припустимо,
що блоку, що використовується для розподілу пам'яті, передує
слово, а за блоком слід слово, що містить '+' на полі TAG для
вказівки про те, що "навколишні" області зайняті. Така угода
спрощує процес об'єднання суміжних областей.
Алгоритм роботи програми GETAREA заснований на методі "перший
підходящий "; проглядається список свободпих областей і
вибирається перша з них, яка є досить великою.
Несморя на те, що вибір "найбільш придатною" області здається на
перший погляд краще, насправді це не так, і крім того, на
це витрачається, очевидно, більше часу.
Прибирання сміття
При другому методі розподілу пам'яті, коли GETAREA не
може знайти відповідну область, викликається програма FREEGARBAGE,
мета якої - знайти невживані області і занести їх у
деякий список вільних областей. Для цього FREEGARBAGE повинна
бути в змозі визначити наступне:
1) розташування в пам'яті кожного описаного покажчика;
2) точні відомості про величину, на яку посилається кожен
покажчик, - довжина величини і чи містить вона які-небудь
покажчики;
3) для кожного покажчика, що міститься у величині, на
яку посилається інший покажчик, довжину покажчика та його
розташування в величині.
Як легко бачити, це досить сильне вимогу, і
тому, використовуючи покажчики, потрібно дотримуватися суворих правил
Тому зазвичай "збір сміття" використовується в тих випадках, коли
система має певну впевненість в тому, що покажчики
вживаються правильно, і коли кількість різних форматів для
величин невелика. Гарним прикладом такої системи є LISP.
Інший приклад - це система обробки рядків, перевага якої
состоітв те, що величини, на які посилаються покажчики рядків,
є тільки рядками літер, так що величина, на яку
посилається вказівник, ніколи не містить інших покажчиків.
Інша проблема полягає в труднощі точного визначення
які області на будь-якому етапі вільні.
Зазвичай збір сміття проходить у дві фази. Під час першої
фази деяким чином маркуються всі використовувані величини.
Загальноприйнятий метод полягає в тому, щоб мати в кожній
величиною додатковий біт спеціально для маркування, хоча в
деяких випадках це незручно??. Інший метод полягає в
те, що біти маркування збираються в окрему таблицю з
певним відповідністю між осередками і битами маркування.
Однак при цьому потрібна спеціальна таблиця для бітів
маркування, а мабуть, коли викликається збирач сміття,
обсяг вільної пам'яті дуже малий!
У другій фазі ми переглядаємо послідовно всю пам'ять,
заносячи непомеченние області в список вільних областей і
гасячи біти маркування. Останнє робиться для того, щоб
при наступному виклику збирача сміття можна було б правильно
сформувати біти маркування.
Іноді використовується третя фаза, яка збирає
вільні області разом, так щоб вони утворювали один
великий блок. Для цього потрібно, щоб програма збору
сміття змінювала значення покажчиків під час переміщення даних.
Для розгляду існуючих алгоритмів збору сміття
посилаємо читача до гол. 2 книги Кнута "Мистецтво програмування
на ЕОМ "т.1.
Системи з дворівневим розподілом пам'яті
У деяких системах є два рівні розподілу
пам'яті; великі блоки внутрішньої пам'яті резервуються і
звільняються згідно з одним методом, в той час як
кожен великий блок може бути підрозділи з допомогою
іншого методу.
8. Об'єктно-орієнтовані мови. Нові інформаційні
структури і пам'ять для них
Однією з істотних причин, що приводять до появи
нових мов програмування, є обмеженість
визначених типів даних. Їх обмеженість в складності
адаптації під конкретне завдання.
Для формалізації певної концепції, або, іншими словами,
створення нового абстрактного типу, необхідно визначити як
подання об'єкта цього типу, так і операції над цим
об'єктом.
Зручним апаратом для опису об'єктів нового типу володіють
об'єктно-орієнтовані мови. Базовим поняттям об'єктно -
орієнтованої мови є клас.
Клас є типом, створеним програмістом. Зовні
опис найпростішого класу схоже зі структурою даних. На відміну
від структур розглянутих раніше, в об'єктно-орієнтованому
мовою клас може включати в себе не тільки змінні,
визначають новий тип даних, а й функції, що реалізують операції
над цим типом даних. І дані, і функції, складові
клас, називаються членами класу. Серед функцій-членів класу
можуть пристосовувати спеціальні функції, що управляють
ініціалізацією об'єктів такого типу - конструктори та функції,
керуючі знищенням об'єктів - деструктори. Вони і займаються
розподілом пам'яті для екземплярів класу, крім цього ними
може бути виконана ініціалізація цієї пам'яті заданими
значеннями.
Ми будемо розглядати нові об'єкти в аспекті розподілу
пам'яті під них. Ідеологія і механізми використання класів
вичерпно описані, наприклад, в літературі [3], [4], [5].
Отже, коли в програмі оголошується об'єкт якого