трусики женские украина

На головну

Розподіл пам'яті - Інформатика

┌│

Введення

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 (А[1, 1]) + (i-1)*N + (j-1) який

можна записати так: (ADDRESS (А[1, 1]) - N - 1) + (i*N + j)

Перший доданок є константою, і його потрібно обчислити

тільки один раз. Таким чином, для визначення адреси А[i, j]

необхідно виконати одне множення і два складання.

Другий метод складається в тому, що виділяється окрема область

даних для кожного рядка і є вектор покажчиків для цих

областей даних. Елементи кожного рядка розміщуються в сусідніх

осередках в порядку зростання. Так, опис ARRAY А [1:][M, 1:][N]

породжує

┌────────────────────────┐ ┌─────────────────────┐

│ Покажчик на рядок 1 ├─────────┤ А[1, 1]. .. А[1, N] │

├────────────────────────┤ └─────────────────────┘

│ Покажчик на рядок 2 ├───────┐ ┌─────────────────────┐

├────────────────────────┤ └─┤ А[2, 1]. .. А[2, N] │

│ ... │ └─────────────────────┘

├────────────────────────┤ ┌─────────────────────┐

│ Покажчик на рядок M ├─────────┤ А[M, 1]. .. А[M, N] │

└────────────────────────┘ └─────────────────────┘

Вектор покажчиків рядків зберігається в тій області даних, з якою

асоціюється масив, в той час як власне масив зберігається

в окремій області даних. Адреса елемента масиву А[i, j] є

CONTENTS(i-1) + (j-1).

Перша перевага цього методу складається в тому, що при

обчисленні адреси не треба виконувати операцію множення. Іншим

є те, що не всі рядки можуть знаходитися в оперативній

пам'яті одночасно. Покажчик рядка може містити деяке

значення, яке викличе апаратне або програмне переривання

у випадку, якщо рядок в пам'яті відсутній. Коли виникає

переривання, рядок вводиться в оперативну пам'ять з на місце

іншого рядка.

Якщо всі рядки знаходяться в оперативній пам'яті, то масив

вимагає більше місця, оскільки необхідне місце і для вектора

покажчиків.

Коли відомо, що матриці розріджені (ольшинство

елементів - нулі), використовуються інші методи. Може бути

застосована схема хеш-адресації, яка базується на значеннях i

і j елемента масиву А[i, j] і посилається по хеш-адресі на

відносно коротку таблицю елементів масиву. У таблиці

зберігаються тільки ненульові елементи матриці.

Багатомірні масиви

Ми розглянемо розміщення в пам'яті і звернення до

багатомірних масивів, описаних, таким чином:

ARRAY А[L1:U1, L2:U2,. .., Ln:Un]

Метод полягає в узагальненні першого методу, запропонованого для

двумерного випадку; він також застосуємо і для одномірного масиву.

Подмассив А[i,*,. .., *] містить послідовність

А[L1,*,. .., *], А[L1+1,*,. .., *], і т.д. до А[U1,*,. .., *].

Всередині подмассива А[i,*,. .., *] знаходяться подмассивы

А[i, L2,*,. .., *], А[i, L2+1,*,. .., *],. .. і А[i, U2,*,. .., *].

Це повторюється для кожного вимірювання. Так, якщо ми просуваємося

в порядку зростання по елементах масиву, швидше змінюються

останні індекси:

┌───────────────────────────────────────┐ ┌─────────┐ ┌───────┐

│ подмассив А[L1] │ │ А[L1+1] │ │ А[U1] │

│ ┌────────┐ ┌──────────┐ ┌────────┐│ │ │ │ │

│ │А[L1, L2]│ │А[L1, L2+1]│ ... │А[L1, U2]││ │ │ ... │ │

│ └────────┘ └──────────┘ └────────┘│ │ │ │ │

└───────────────────────────────────────┘ └─────────┘ └───────┘

Питання полягає в тому, як звернутися до елемента

А[i, j, k,. .., l, m]. Визначимо

d1 = U1-L1+1, d2 = U2-L2+1,. .., dn = Un-Ln+1.

Тобто d1 є число різних значень індексів в i-тому

вимірюванні. Слідуючи логіці двумерного випадку, ми знаходимо початок

подмассива А[i,*,. .., *]

BASELOC + (i-L1)*d2*d3*...*dn

Де BASELOC - адреса першого елемента А[L1, L2,...,Ln], а

d2*d3*...*dn - розмір кожного подмассива А[i,*,...,*]. Початок

подмассива А[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 │

│. │. │. │ Опис масиву

│. │. │. │ А[L1:U1,...,Ln:Un]

│. │. │. │

│ Ln │ Un │ dn │

├────┼────┴────┤

│ n │CONSTPART│

├────┴─────────┤

│ BASELOC │

└──────────────┘

Рис.. Інформаційний вектор для масиву

використовуючи верхні і нижні межі і постійні значення d1, d2,...,

dn. У інших мовах це неможливо так як межі можуть

обчислюватися під час рахунку. Тому потрібен описувач для масиву,

вмісний необхідну інформацію. Цей описувач для масиву

називається допвектор (dope vector) або інформаційний вектор.

Інформаційний вектор має фіксований розмір, який

відомий при компіляції, отже, пам'ять для нього може

бути відведена під час компіляції в області даних, з якою

асоціюється масив. Пам'ять для самого масиву не може бути

відведена доти, поки під час рахунку не виконається вхід в

блок, і якому описаний масив. При вході в блок обчислюються

межі масиву і проводиться звернення  до програми

розподілу пам'яті для масивів. Тут же вноситься в

інформаційний вектор необхідна інформація.

Яка інформація заноситься в інформаційний вектор? Для

запропонованої вище n-мірної схеми нам як мінімум потрібні d2,...dn

і CONST_PART. Якщо перед зверненням до масиву треба перевіряти

правильність завдання індексів, то потрібно також занести в

інформаційний вектор значення верхніх і нижніх меж.

5. Пам'ять для структур

Існує декілька альтернатив для визначення нових

типів даних як структур, складених з типів даних,

визначених раніше. Величини такого типу ми називаємо

структурними величинами. Існують різні підходи до

реалізації цих конструкцій. Відмінності звичайно торкаються наступних

питань:

Як виділяти пам'ять для структурних величин?

Як будувати структурні величини?

Як посилатися на компоненту структурної величини?

Як звільняти пам'ять?

Записи по Хоору

Визначення нового типу даних має вигляд

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(DDRESS,

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].

Отже, коли в програмі появляється об'єкт якого-небудь

класу, або ініціалізувався покажчик на об'єкт цього типу,

викликається конструктор класу. Його задачею є

розподілити необхідну пам'ять. Пам'ять виділяється під

дані-члени класу. Коди функцій-членів зберігаються окремо від

даних, а саме, в сегменті коду програми, і безпосередньо

не присутні в реальному об'єкті; при цьому зберігається тільки

одна копія кожної функції, хоч об'єктів в програмі може бути

декілька. Але, з іншого боку, оскільки ці функції

є членами класу, вони можуть викликатися тільки після

того, як в програмі створені об'єкти абстрактного типу; більш

того вони викликаються тільки для даного конкретного об'єкта, і

дії, що виконуються ними ніяк не можуть впливати на стан

інших об'єктів цього типу.

Пам'ять для даних-членів розподіляється аналогічно

методам, котрые описані вище для структур (м.)( Структури PL/1

і Структури даних по Стендішу).

Після того, як об'єкт виконав свою місію в програмі

він знищується деструктором класу: пам'ять  займана

даними-членами цього примірника класу звільняється. Причому

важливо помітити, що якщо об'єкт містив які-небудь покажчики на

зайнятий спомин - ця пам'ять не звільняється. Тому

відповідальність за можливим таким чином виникнення

втраченої для системи пам'яті несе програміст, а не компілятор.

СПИСОК ЛІТЕРАТУРИ

1. ГРИС Д. Конструїрованіє компіляторів для цифрових

обчислювальних машин. -М.: МИР, 1975.

2. КАСЬЯНОВ В.Н., ПОТТОСИН И.В. Методи побудови

трансляторів. -Н.: НАУКА, 1986.

3. РОМАНІВ В.Ю. Программірованіє на мові З++. -М.:

КОМП'ЮТЕР, 1993.

4. ЦИМБАЛІВ А.А., МАЙОРІВ А.Г., КОЗОДАЕВ М.А. Turbo З++: мова

і його застосування. -М.: Джен Ой Лтд., 1993.

5. ЭЛЛИС М., СТРОУСТРУП Б. Справочноє керівництво по мові

програмування З++ з коментарями. -М.: МИР, 1992.

Авіація і космонавтика
Автоматизація та управління
Архітектура
Астрологія
Астрономія
Банківська справа
Безпека життєдіяльності
Біографії
Біологія
Біологія і хімія
Біржова справа
Ботаніка та сільське господарство
Валютні відносини
Ветеринарія
Військова кафедра
Географія
Геодезія
Геологія
Діловодство
Гроші та кредит
Природознавство
Журналістика
Зарубіжна література
Зоологія
Видавнича справа та поліграфія
Інвестиції
Інформатика
Історія
Історія техніки
Комунікації і зв'язок
Косметологія
Короткий зміст творів
Криміналістика
Кримінологія
Криптологія
Кулінарія
Культура і мистецтво
Культурологія
Логіка
Логістика
Маркетинг
Математика
Медицина, здоров'я
Медичні науки
Менеджмент
Металургія
Музика
Наука і техніка
Нарисна геометрія
Фільми онлайн
Педагогіка
Підприємництво
Промисловість, виробництво
Психологія
Психологія, педагогіка
Радіоелектроніка
Реклама
Релігія і міфологія
Риторика
Різне
Сексологія
Соціологія
Статистика
Страхування
Будівельні науки
Будівництво
Схемотехніка
Теорія організації
Теплотехніка
Технологія
Товарознавство
Транспорт
Туризм
Управління
Керуючі науки
Фізика
Фізкультура і спорт
Філософія
Фінансові науки
Фінанси
Фотографія
Хімія
Цифрові пристрої
Екологія
Економіка
Економіко-математичне моделювання
Економічна географія
Економічна теорія
Етика

8ref.com

© 8ref.com - українські реферати


енциклопедія  бефстроганов  рагу  оселедець  солянка