Title 9 - Статическое распределение памяти.pdf ✅

Статическое распределение памяти для данных Блочная структура программ и область видимости переменных В большинстве алгоритмических языков принята блочная структура программ, при которой область видимости переменных, описанных в каком- либо блоке, распространяется только на этот блок и блоки, вложенные в него. Пример программы с блочной структурой на языке C представлен на рисунке 9.1. void main(){ int a,b; m1: ...; { int a1,b1; m2: ...; { int d; m3: ...; } { int d1; m5: ...; }. m6: ...; } m7: ...; { int e,f; m8: ...; } m9: ...; } Рисунок 9.1 – Пример программы с блочной структурой Допустим, память для данных распределяется с адреса k, и длина переменных типа int – 4 байта. Тогда состояние памяти при выполнении программы меняется в зависимости от видимости переменных, как это представлено в таблице 9.1. Таблица 9.1 – Состояние памяти программы адрес метка m1 m2 m3 m4 m5 m6 m7 m8 m9 k+0 a a a a a a a a a k+4 b b b b b b b b b k+8 a1 a1 a1 a1 a1 f k+12 b1 b1 B1 b1 b1 e k+16 d d1 Таким образом, одни и те же области памяти при работе программы могут быть использованы для размещения различных переменных. BL1 BL2 BL5 BL3 BL4
BL1 a, b BL2 a1, b1 BL3 d BL4 d1 BL5 f, e Блочная структура программы может быть представлена в виде дерева, как это показано на рисунке 9.2. уровень 1 уровень 2 уровень 3 Рисунок 9.2 – Дерево блоков программы Узлы дерева соответствуют блокам и расположены на разных уровнях. Внешнему блоку приписан уровень 1. Блоку, содержащемуся в блоке уровня r, приписывается уровень r+1. Распределение памяти для блоков программы Статическое распределение памяти для данных проводится в два этапа. На первом этапе выделяется секция памяти каждому блоку, на втором – назначаются адреса переменным внутри блока. На первом этапе распределения памяти каждому блоку программы присваивается номер i в соответствии с последовательностью их описания в программе. Определяются величины n[i] – размер секции памяти i-го блока (n[1] = n[2] = n[5] = 8 байт, n[3] = n[4] = 4 байта) и строится таблица блоков. Для приведенного примера программы таблица блоков имеет вид, представленный в таблица 9.2. Таблица 9.2. – Таблица блоков программы Затем по таблице блоков определяются адреса начала секций памяти для блоков (A[i]). Для первого блока принимается A[1] = k – адрес начала области данных программы. Для каждого последующего блока i величина A[i] определяется как A[i] = A[m] + n[m], гдеm= max(j| УБ[j]<УБ[i], jТо есть, для определения m последовательно просматриваются строки таблицы блоков j = i-1,i-2,...,1 и ищется первая строка, для которой УБ[j] < УБ[i]. Результат реализации этого алгоритма представлен в таблице 9.3. Таблица 9.3 – Адреса начала секций блоков Адрес начала секции блока (A[i]) k k + 8 k + 16 k + 16 k + 8 Распределение памяти для переменных и массивов На втором этапе секция данных каждого блока распределяется по отдельным переменным и массивам. Для каждого блока выделяются счетчики T[i], указывающие текущий адрес в секции. Первоначально T[i] = A[i]. Просматривается таблица идентификаторов и для каждой переменной или массива извлекается номер блока – i и длина переменной – d. Величина T[i] принимается в качестве адреса переменной и корректируется T[i] = T[i] + d. Результат распределения памяти для переменных приведен в таблице 9.4. Таблица 9.4 – Распределение памяти для переменных программы Пере менн ая Номе р блок а Дли на Адре с T[1] T[2] T[3] T[4] T[5] k k+8 k+16 k+16 k+8 a 1 4 k k+4 b 1 4 k+4 k+8 a1 2 4 k+8 k+12 b1 2 4 k+12 k+16 d 3 4 k+16 k+20 d1 4 4 k+16 k+20 f 5 4 k+8 k+12 e 4 k+12 k+16 Приведенное распределение памяти соответствует распределению, представленному в таблице 9.1 и.полученному в результате анализа хода выполнения программы.