68829

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

Лекция

Информатика, кибернетика и программирование

Етап розподілу пам’яті майже не залежить від мови програмування та машини. Якщо у тексті вхідної програми зустрічається опис ідентифікатору що дозволяє визначити необхідний об’єм пам’яті для його зберігання то компілятор спеціальним чином виділяє потрібну пам’ять.

Украинкский

2014-09-26

79.5 KB

0 чел.

Лекція 17

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

Крім з’ясування структури вхідної програми компілятор повинен виділити місце у  пам’яті  ЕОМ  для  значень змінних та проміжних значень виразів. Цей етап роботи називають розподілом пам’яті. Етап розподілу пам’яті майже не залежить від мови програмування та машини.

Якщо у  тексті  вхідної  програми  зустрічається  опис ідентифікатору, що дозволяє визначити необхідний об’єм пам’яті для його зберігання, то компілятор спеціальним  чином  виділяє  потрібну пам’ять. Наприклад, коли читається опис [1:10] int x, для масиву  х  виділяється пам’ять, у якій може  зберігатися  десять цілих чисел. Аналогічно для зміної  y, що описується як

struct(int a, real b, bool c) y,  компілятор  виділяє  пам’ять  для  зберігання  цілого,  дійсного  та логічного значення.

Однак, якщо зустрічається, наприклад, опис  [1:n] int z, а значення  n визначається тільки при обробці вхідних даних,  то  потрібну пам’ять виділити під час компіляції неможливо,  і  вона  виділяється під  час  прогону.  Пам’ять,  що  виділяється  під  час  компіляції, називається статичною, а під час прогону - динамічною.

Пам’ять потрібна також для зберігання проміжних результатів  та констант. Наприклад, при обчисленні виразу  a + c * b  спочатку обчислюється  c * b, і значення добутку запам’ятовується у машині, а потім обчислюється сума. Пам’ять, що використовується для зберігання проміжних результатів називається робочою. Робоча пам’ять може бути статичною або динамічною.

Механізм  розподілу  пам’яті  залежить  від особливостей мови вхідної програми. Якщо у мові виділена  для  ідентифікатора  пам’ять закріпляється за ним до закінчення прогону, то для розподілу пам’яті можна застосувати масив. Наприклад, в результаті читання опису  integer a, b, x, y  виділяється пам’ять, як це умовно показано на рис.17.1.

       a    b   x   y

           

Рис.17.1. Застосування

масиву для розподілу пам’яті.

У мові з блочною структурою, при виході  з  блоку  пам’ять,  що була виділена для ідентифікаторів даного блоку, звільняється  (тобто стає доступною для інших ідентифікаторів). Тому у таких  мовах  для розподілу пам’яті використовують стек, і називають його стеком часу прогону.

Розподіл пам’яті методом керування кучею

Застосування стеку  для  розподілу  пам’яті  передбачає  певний порядок виділення пам’яті та її звільнення. А саме, остання  зайнята комірка звільняється  першою.  Часто  буває  необхідно  організувати виділення і звільнення пам’яті у довільні моменти часу у  довільному порядку. У такому разі застосовується спеціальна структура даних, що називається кучею. Куча -  це  блок  (сукупність  комірок)  пам’яті, частини  якого  можуть  виділятися  та  звільнюватися  за  будь-яким потрібним порядком.

Необхідність у керуванні кучею  виникає  у  мовах,  що  містять структури  даних  з  покажчиками.  У таких мовах передбачаються процедури  зберігання   пам’яті   для   запам’ятовування   елементів списочних структур та  звільнення  цієї  пам’яті.  У  Паскалі  -  це процедури  new  та  dispose. У кучі відрізняють  вільну  частину  та використану.  Процедура  new   вибирає  елемент  пам’яті  з  вільної частини кучі, а  dispose  повертає  його. Якщо  під  час  прогону елемент використаної частини кучі стає не потрібним, його необхідно повернути у вільну частину. Це дає змогу  знов  використовувати  цей елемент пам’яті для інших цілей.

У процесі розподілу пам’яті компілятор виділяє  пам’ять  як  зі стеку, так  і  з  кучі.  Якщо  уявити  усю  пам’ять,  що  розподіляє компілятор,  у  вигляді  лінійного  масиву,  то  можна  сказати,  що доцільно розташувати стек  та  кучу  у  протилежних  сторонах  цього масиву (рис.17.2).

Рис.17.2. Використання пам’яті..

Це означає, що пам’ять можна виділяти з будь-якої ділянки, доки вони  не  зустрінуться.  Такий  підхід дозволяє краще  використати пам’ять порівняно  з фікссованим  діленням  на  дві частини.

При роботі зі списочними структурами важливо, щоб не виникали такі елементи у використаній частині кучі,  на  які  нема  посилань. Крім того, треба, щоб не було  посилань  на  елементи,  повернені  у вільну   частину   кучі.    У    першому    випадку    нераціонально використовується пам’ять, у другому - виникають так звані висячі посилання, які можуть привести до виникнення аварійних ситуацій  під час прогону. Наприклад, якщо у Паскалі виконується послідовність операторів

                                                         new(p);

                       p^.num := a;

                       p := nil;

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

                       new(p);

                       p^.num := a;

                       q := p;

                       dispose(p);

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

Для того, щоб уникнути  цих  ситуацій  застосовують  спеціальні методи  керування  кучею.  Перший  базується  на  ідеї  використання лічильників посилань,  другий - на ідеї збирання сміття.

Лічильники посилань

При використанні лічильників посилань комірки пам’яті повертаються до вільної частини  кучі одразу, як вони стають не потрібні для програми, що  виконується.  В  цьому   методі   куча розглядається як послідовність комірок, у кожній з яких міститься недоступне для користувача поле (лічильник   посилань), де підраховується кількість посилань на подану  комірку.   Лічильники посилань поновлюють під час прогону, і коли значення лічильника стає нулем, комірка з цим лічильником звільняється. Як показує  наступний приклад, алгоритм поновлення лічильників посилань не є тривіальним.

Нехай застосовується структура, що уявляє собою список записів, кожний з яких складається з трьох полів: count - лічильник посилань, name - ім’я та  ptr -  покажчик  на наступний  елемент  списку. Припустимо початковий стан списку такий,  як  на  рис.17.3,а.  Після виконання операторів   y := x^.ptr;   y := y^.ptr;

x   A 

x

                                                                                                                y

                                а)                                                                 б)

Рис.17.3. Перетворення списку з лічильниками посилань.

ніяких  ускладнень  не  виникає  і  список  приймає  вигляд  як   на рис.17.3,б.

Якщо ж виконується оператор  x := z;  то звільнення першого елемента списку недостатньо,  необхідно  також звільнити і другий.

У загальному випадку ланцюжок звільнених  елементів  може  мати будь-яку довжину. Більш того, якщо елементи списку містять  декілька покажчиків (нелінійна структура), при зменшенні значень  лічильників посилань треба використовувати стек для  запам’ятовування  напрямків проглядання елементів списку. Так, якщо черговий елемент має значення лічильника посилань  1 і  три  покажчики   p,  q,  r,  то  за  одним покажчиком, наприклад, p  проглядається  наступний  елемент,  а  два інші  (q, r) заносяться у стек.

                                                                                                                

Рис.17.4. Циклічний список.

Метод керування кучею з використанням лічильників посилань  має два недоліки. Перший полягає у тому,  що  не  поновлюються  циклічні структури. Наприклад, циклічний список, показаний  на  рис.17.4,  не може бути повернений у  вільну  частину  кучі,  хоч  на  нього  нема зовнішніх посилань.

Другий недолік пов’язаний з необхідністю  виконання  додаткових обчислень навіть у випадках, коли  ці  обчислення  не  потрібні.  Це суперечить принципу  Бауера [2], згідно з яким «прості  програми»  не повинні  «розплачуватися» за дорогі мовні засоби, якими вони не користуються. Позбавитись вказаних недоліків дає змогу  метод  збирання сміття.

Збирання сміття

Цей метод звільняє пам’ять не тоді, коли вона стає непотрібною, а лише тоді, коли виявляється, що вільна частина кучі пуста. Таким чином, для програми з невеликою потребою пам’яті необхідність у звільненні використаних комірок може і не виникати.

Недоступні  для  програми  комірки,  що  належать  використаній частині кучі, називають сміттям, а процес повернення цих  комірок  у вільну частину - збиранням сміття. Збирання сміття виконується у два етапи. На першому виконується маркування усіх доступних програмі елементів, на другому усі  елементи, що не одержали мітку  доступності, повертаються  у  вільну  частину  кучі. Другий етап зводиться до послідовного проглядання усієї кучі. При  цьому  елементи  вільної частини  вважаються  доступними.  Розглянемо  більш  детально  етап маркування.

Основна мета - одержати таку програму для реалізації цього етапу, яка б швидко працювала і вимагала якомога менше пам’яті. Звичайно ці вимоги суперечливі, одночасно їх виконати не можливо, і тому треба вибирати  компромісне  рішення. Спочатку  розглянемо найбільш швидкий алгоритм.

Припустимо, що уся куча являє собою масив  записів,  кожний  з яких має три поля: два покажчики і маркер. Засобами Паскалю цю структуру можна описати так

              type

              node = record

                left, right : integer;

                mark : boolean

              end;

var  h : array [1..N] of node;

Пошук усіх доступних для програми комірок пов’язаний з проходженням за покажчиками, починаючи від безпосередньо доступних комірок,  які  будемо  називати  входами.  Нехай  кількість   входів дорівнює  t. Алгоритм складається з чотирьох кроків.

1. {Початкове присвоєння} Помітити входи і занести покажчики на них у стек – stack[1], stack[2], … , stack[t].  

2. {Стек пустий?} Якщо  t = 0, алгоритм закінчено.

3. {Виштовхнути зі стеку елемент} k := stack[t]; t := t -1.

4. {Дослідження зв’язків} Якщо  h[k] - лист, перейти до  кроку 2. Якщо  h[k].left  0,  і комірка  h[h[k].left]  не має мітки, помітити її і вштовхнути у стек  h[k].left - t := t + 1; stack[t] := h[k].left;. У випадку коли   h[k].right  0, і комірка  h[h[k].right]   не  помічена,  помітити  її, вштовхнути у   стек  h[k].right. Перейти до кроку 2.

Процедура, що реалізує кроки  2 - 4 може мати вигляд

var k : integer;

begin

 while t > 0 do

  begin

    k := stack[t]; t := t-1;

    if h[k].left > 0 and not h[h[k].left].mark then

      begin

        h[h[k].left].mark := true; t := t+1;

        stack[t] := h[k].left

      end;

    if h[k].right > 0 and not h[h[k].right].mark then

      begin

        h[h[k].right].mark := true; t := t+1;

        stack[t] := h[k].right

      end;

  end;

end;

Час виконання поданого алгоритму пропорційний кількості комірок, що маркуються, і це, очевидно, найкращий результат. Однак, цей алгоритм потребує великого (і, головне, заздалегідь невідомого) об’єму пам’яті для стеку.

Інший алгоритм, що  не  потребує  такого  об’єму  пам’яті,  але працює дуже повільно, складається з трьох кроків (М - максимальний номер використаної комірки, М  N)

    1. {Початкове присвоєння} Помітити усі входи;  покласти  k = 1.

    2. {Чи прямує за   h[k]  інша комірка?}  Покласти   k1 :=  k + 1.

Якщо  h[k] - лист або непомічена комірка,  перейти  до  кроку  3. Якщо  h[k].left  0,  та  h[h[k].left]  не  помічена, помітити її і, якщо вона не лист, покласти  k1 := min(k1, h[k].left); якщо h[k].right  0, та  h[h[k].right]  не помічена, помітити її і, якщо вона не лист, покласти  k1 := min(k1, h[k].right). 

    3. {Кінець?} Покласти  k := k1. Якщо  k    M, перейти до кроку 2; у іншому разі алгоритм закінчено.

    Програма, що реалізує поданий алгоритм, має вигляд

procedure mark2

var k, k1 : integer;

begin

 k := 1;

 while k <= M do

 begin

   k1 := k+1;

   if (h[k].left > 0) and not h[h[k].left].mark then

     begin

       h[h[k].left].mark := true;

       if (h[h[k].left].left > 0) or

          (h[h[k].left].right > 0)

       then k1 := min(k1, h[k].left)

     end;

   if (h[k].right > 0) and not h[h[k]].right].mark then

     begin

       h[h[k].right].mark := true;

       if (h[h[k].right].left > 0) or                     h[h[k].right].right > 0)

       then k1 := min(k1, h[k].right)

     end;

   k := k1

 end;

end;

У поданому алгоритмі  виконується  послідовне  проглядання  всієї кучі. Якщо чергова комірка  a, що помічається, має менший номер  ніж поточна  b, відбувається повернення до  комірки   а   і  проглядання кучі продовжується від комірки  a. У найгіршому випадку при  кожному присвоєнні мітки комірці відбувається повернення. Тому  час  роботи цього  алгоритму  є   О(nM),  де   n  -  кількість   комірок,   яким присвоюються мітки.

Компромісним рішенням є сполучення розглянутих двох  алгоритмів на основі застосування стека фіксованого розміру  l: stack[0 .. l-1]. У цьому алгоритмі дія вштовхнути  х  у стек означає

      t := (t+1)mod l;

      stack[t] := x;

      if t = b then

      begin

b := (b+1)mod l; k1 := min(k1, stack[b])

      end;

При цьому  t  вказує на вершину стеку, а  b - на комірку, що передує дну. Алгоритм складається з п’яти кроків.

    1. {Початкове присвоєння} Покласти  t := l - 1;  b := l – 1;  k1 := М + 1. Помітити усі входи і вштовхнути покажчики на них у стек.

    2. {Стек пустий?} Якщо  t = b, перейти до кроку 5.

    3. {Виштовхування елемента зі стеку} Покласти  k := stack[t];  t := (t - 1)mod l.

    4. {Дослідження зв’язків}  Якщо  h[k] - лист, перейти до кроку 2. Якщо  h[k].left    0,  і  комірка   h[h[k1].left]  не помічена,  помітити  її  і  вштовхнути  h[k].left   у  стек;   якщо  h[k].right  0, і комірка h[h[k].right]  не помічена, помітити її і вштовхнути  h[k].right  у стек. Перейти до кроку 2.

    5. {Пошук мінімальної поміченої комірки} Якщо  k1 > M, алгоритм закінчено. У іншому разі, якщо комірка  h[k1]  не помічена, покласти  k1 := k1 + 1 і повторити крок 5. Якщо  h[k1]  помічена, то  покласти  k := k1;  k1 := k1 + 1; і перейти до кроку 4.

Поданий алгоритм уявляє собою багаторазове повторення першого алгоритму.  Оскільки  у  стеку  запам’ятовується   не  більш, ніж  l  покажчиків,  то при першому спустошенні стеку, можливо не  усі доступні комірки одержать мітки. При  переході  від  кроку  2  до  5  змінна  k1  дорівнює мінімальному номеру комірки, що одержала  мітку у інтервалі часу між двома послідовними спустошеннями стеку. При  l = M  цей алгоритм стає  еквівалентним  першому,  а  при   l  =  1  - другому.

Існують і інші алгоритми маркування [4]. Один з них, найбільш витончений, було запропоновано незалежно  П.Дойчем  і двома іншими авторами  Г.Шорром  та  У.Уейтом. Суть методу полягає у тому, що починаючи з будь-якого входу, алгоритм проходить ланцюжок покажчиків до  кінця. При проходженні  кожного  покажчика  досягнута  комірка маркується,  а покажчик замінюється на зворотний. Після досягнення кінця ланцюжка (листа) ці обернені покажчики дозволяють пройти ланцюжок у зворотному напрямку. При поверненні у чергову вершину перевіряється можливість пройти новим ланцюжком, і так  далі.  Алгоритм  два  рази проходить за кожним покажчиком у марковану  вершину:  у  прямому напрямку та у зворотньому.

Для реалізації цього алгоритму дещо змінюється структура даних для уявлення кучі. У кожний запис включається додаткове булеве поле sink. Якщо від комірки відбувається перехід до лівого сину, у поле sink записується значення  true, у іншому разі  -  false.  Алгоритм маркування комірок, що  можна  досягти  зі  входу,  на  який  вказує посилання  р0, складається з шости кроків.

    1. {Початкове присвоєння} Покласти  t := 0; р := р0.

    2. {Присвоїти мітку} Покласти  h[p].mark := true.

    3. {Обох синів вершини  р  проглянуто?} Якщо  h[p].sink = true,

перейти до кроку 6.

    4. {Вниз за  h[p].left} Покласти  q := h[p].left. Якщо  q  0, і  h[q].mark = false, покласти 

                        h[p].sink := true;

                        h[p].left := t;

                        t := p; p := q;

і перейти до кроку 2.

    5. {Вниз за  h[p].right} Покласти  q := h[p].right. Якщо   q  0, і  h[q].mark = false, покласти

h[p].right := t; 

                     t := p; p := q;

і перейти до кроку 2.

    6. {УгоруЇ Якщо  t = 0,  алгоритм  закінчено.  У іншому разі покласти  q := t. Якщо  h[q].sink = true, покласти

h[q].sink := false;

                    t := h[q].left;

                    h[q].left := p;

                    p := q;

і перейти до кроку 5. Якщо  h[q].sink = false, покласти

t := h[q].right;

                     h[q].right := p;

                     p := q;

і повторити крок 6.

У поданому алгоритмі під час руху у прямому напрямку поле sink  використовується для запам’ятовування напрямку виходу з поданої комірки. При цьому, якщо використано лівий покажчик, то батько поданої комірки запам’ятовується у полі left, а якщо  правий  -  у  полі right.

Застосована стратегія пошуку доступних комірок називається стратегією одностороннього гілкування або пошуком у глибину. Така назва виправдовується тим, що при досягненні чергової вершини завжди спочатку робиться спроба продовжити рух у одному і тому  ж  напрямку (за допомогою лівого покажчика).


 

А также другие работы, которые могут Вас заинтересовать

4584. Знайомство з системою комп’ютерної математики - математичною матричною лабораторією MATLAB 232.5 KB
  Знайомство з системою комп’ютерної математики - математичною матричною лабораторією MATLAB. Мета роботи: Ознайомитися з основними елементами і складовими частинами системи комп’ютерної математики MatLab® і її робочим і програмним середовищ...
4585. Планування модельних експериментів. Стратегічне планування модельного експерименту 101 KB
  Планування модельних експериментів. Стратегічне планування модельного експерименту. Мета роботи: Ознайомитися з методами стратегічного планування імітаційних експериментів. Планування модельних експериментів Припустимо, три юні натураліст...
4586. Методи управління модельним часом: моделювання з постійним кроком і по особливих станах 101 KB
  Методи управління модельним часом: моделювання з постійним кроком і по особливих станах. Мета роботи: Вивчити методи управління модельним часом. Ознайомитися і програмно реалізувати алгоритми управління модельним часом з постійним кроком і по особли...
4587. Субтрактивне змішування кольорів. Диск Максвелла 38.52 KB
  Субтрактивне змішування кольорів. Диск Максвелла. Виконання роботи. Визначення координат ахроматичної точки. Підібрали такі розміри зовнішніх секторів з кольорами Cyan, Magenta, Yellow, що їх суміш дала ахроматичний колір. Отримали наступні коорд...
4588. Розрахунок припусків на механічну обробку оптичних деталей 47 KB
  Розрахунок припусків на механічну обробку оптичних деталей Мета роботи: Ознайомити студентів з методикою розрахунків припусків на розміри оптичних поверхонь деталей при їх обробці в оптичному виробництві. Завдання 1. Ознайомитись з видами припусків ...
4589. Інсталювання та налагодження мережевих компонент однорангової мережі Windows 9x. 103 KB
  Інсталювання та налагодження мережевих компонент однорангової мережі Windows 9x, Робота в одноранговій мережі. Керування доступом на рівні ресурсів. Використання спільних каталогів та мережевого принтера. Методичні вказівки з курсу Операційні ...
4590. Повышение эффективности разработки Приобского месторождения за счет оптимального подбора параметров работы электропогружных установок 3.05 MB
  Погруженные центробежные насосы (УЭЦН) в настоящее время являются одним из основных средств механизированной эксплуатации нефтяных скважин. На их долю приходится более 53% добываемой в России нефти и более 63% извлекаемой из скважин жидкости...
4591. Уточнения должностных функций, выполняемых менеджером по обучению персонала на предприятии ООО Техно-регион 183.99 KB
  Введение Развитие персонала является важнейшим условием успешного функционирования любой организации. Это особенно справедливо в современных условиях, когда ускорение научно-технического прогресса значительно убыстряет процесс устаревания профессион...
4592. Диссертация магистранта, аспиранта, докторанта 3.27 MB
  Настоящее пособие дает представление о специфике и месте диссертации магистранта, аспиранта и докторанта в системе научного исследования. В нем выделены этапы исследования, для каждого из которых разработаны ментальные карты, чем пособие выгодно отл...