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.

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


 

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

22435. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ КООПЕРАЦИИ 117 KB
  ТЕОРЕТИЧЕСКИЕ ОСНОВЫ КООПЕРАЦИИ 1. Сущность кооперации. Формы и виды кооперации. Понятие межхозяйственной кооперации и направления ее развития.
22436. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ АГРОПРОМЫШЛЕННОЙ ИНТЕГРАЦИИ 86 KB
  ТЕОРЕТИЧЕСКИЕ ОСНОВЫ АГРОПРОМЫШЛЕННОЙ ИНТЕГРАЦИИ 1. Теоретические основы агропромышленной интеграции. Типы и виды агропромышленной интеграции. Факторы агропромышленной интеграции.
22437. ИСТОРИЯ УЧЕНИЙ О КООПЕРАЦИИ 1.88 MB
  ИСТОРИЯ УЧЕНИЙ О КООПЕРАЦИИ 1. Развитие кооперации во второй половине XIX века 3. Чаянова о кооперации 7. Колыбелью и родиной кооперации является Западная Европа.
22438. АПК как объект межотраслевых связей 107.5 KB
  АПК как объект межотраслевых связей Сущность АПК его место и роль в народном хозяйстве Республики Беларусь 2. Предпосылки и объективная необходимость формирования АПК сущность его взаимосвязей 3. Современное состояние и перспективы развития АПК 1. Сущность АПК его место и роль в народном хозяйстве Республики Беларусь В ходе исторического развития сельское хозяйство все больше теряет свою былую изолированность и неуклонно интегрируется со многими отраслями экономики.
22439. ОРГАНИЗАЦИЯ ИСПОЛЬЗОВАНИЯ РАБОЧЕЙ СИЛЫ 66 KB
  Содержание принципы задачи и основные направления организации труда в сельском хозяйстве. Основные формы организации труда. Внутрибригадная организация труда. Содержание принципы задачи и основные направления организации труда в сельском хозяйстве Одним из важнейших условий обеспечивающих высокие темпы развития сельского хозяйства является широкое применение прогрессивных форм организации труда сокращение потерь рабочего времени всемерная активизация человеческого фактора.
22440. СИСТЕМА ВЕДЕНИЯ ХОЗЯЙСТВА 49 KB
  Система растениеводства. Система животноводства. Экономическая сущность и основные принципы построения системы ведения хозяйства Система – это множество взаимосвязанных элементов образующих определённую целостность единство. Система ведения сельского хозяйства – это совокупность социальноэкономических организационных технических и технологических принципов построения и ведения производства для конкретных условий с целью удовлетворения потребностей общества в сельскохозяйственных продуктах.
22441. ПЛАНИРОВАНИЕ (ПРОГНОЗИРОВАНИЕ) ПРОИЗВОДСТВА 66.5 KB
  Задачи и основные принципы планирования экономического и социального развития. Методы планирования. Система внутрихозяйственного планирования. Задачи и основные принципы планирования экономического и социального развития В системе экономических законов действует закон планомерного и пропорционального развития народного хозяйства.
22442. СПЕЦИАЛИЗАЦИЯ И СОЧЕТАНИЕ ОТРАСЛЕЙ 50 KB
  Сущность значение и формы специализации. Сущность значение и формы специализации Все колхозы с момента их создания функционировали как многоотраслевые сельхозпредприятия. С середины 60х годов с укрупнением их размеров начался процесс специализации. Иначе говоря сущность специализации ее экономическое содержание заключается в общественном разделении труда которое происходит постоянно и в разных формах.
22443. ОРГАНИЗАЦИЯ МАТЕРИАЛЬНОГО СТИМУЛИРОВАНИЯ ТРУДА 90.5 KB
  Сущность материального стимулирования и принципы оплаты труда в сельскохозяйственных предприятиях. Основные формы виды и системы оплаты труда. Сущность материального стимулирования и принципы оплаты труда в сельскохозяйственных предприятиях Оплата труда в сельхозпредприятиях производится на основе экономического закона распределения по труду который выражает объективную необходимость распределения предметов потребления в соответствии с количеством и качеством труда вложенного каждым работником в общественное хозяйство.