Министерство образования и науки Российской Федерации ГОУ ВПО Тамбовский государственный технический университет
Кафедра «Информационные системы и защита информации»
О Т Ч Е Т
о лабораторной работе № 2 на тему
«ПЕРЕРАСПРЕДЕЛЕНИЕ ПОСЛЕДОВАТЕЛЬНЫХ ТАБЛИЦ»
Выполнил: студент гр. СИБ-21 Уринов А.В.
Проверил: доцент Кулаков Ю.В.
«___» 2010 г.
(Подпись)
Тамбов 2010
Цель работы: Научиться программировать алгоритм распределения последовательных таблиц
Вариант № 16
Задание: Пусть состояние памяти по окончании последней переупаковки будет следующим:
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
1 |
1 |
|
|
|
|
|
|
3 |
3 |
4 |
|
|
|
|
|
|
|
|
|
base[1]=-1 base[2]=4 base[3]=7 base[4]=9
top[1]=1 top[2]=4 top[3]=9 top[4]=10
В результате выполнения операций I2I1I2I2I3 возникает ПЕРЕПОЛНЕНИЕ и начинает свою работу алгоритм G. Определить состояние памяти и значения указателей base[j] и top[j] (j=1,2,3,4) после переупаковки памяти.
Теоретическая часть
Алгоритм G (Перераспределение последовательных таблиц). Предположим, что переполнение произошло в стеке i согласно условиям. После выполнения алгоритма G либо будет исчерпана емкость памяти, либо память будет переупорядочена таким образом, что сможет быть выполнена операция NODE (ТОР[i]) <— У (значение ТОР[i] увеличено еще до применения алгоритма G.)
G1. [Инициализация.] Пусть SUM <- L∞ - Lo, INC <- 0. Выполним шаг G2 для 1 < j < п. (В результате SUM будет равно общему размеру доступного пространства в памяти, a INC — общему количеству последовательных увеличений размеров стеков по завершении последнего распределения памяти.) Выполнив эти действия, перейдем к шагу G3.
G2. [Сбор статистических данных.] Пусть SUM <- SUM - (T0P[j] - BASE[j]). Если T0P[j] > 0LDT0P[j], то D[j] <- T0P[j] – OLDTOP[j] и INC <- INC + D[j]; в противном случае D [j] <—0.
G3. [Ресурсы памяти исчерпаны?] Если SUM < 0 работа не может быть продолжена.
G4. [Вычисление показателей перераспределения памяти.] Пусть α <- 0.1 * SUM/n, β <- 0.9 * SUM/INC. (Здесь α и β — дробные, а не целые числа, которые необходимо вычислить с заданной точностью. На следующем этапе доступное пространство будет распределено среди отдельных списков следующим образом: приблизительно 10% доступной памяти будет распределено поровну среди n стеков, а оставшиеся 90% будут разделены пропорционально увеличению размера стеков со времени предыдущего распределения памяти.)
G5. [Вычисление новых базовых адресов.] Пусть NEWBASE[1] <- BASE[1] и δ <- 0; тогда для j = 2,3, ...,n установим такие значения: τ <— δ + α + D[j — 1]β, NEWBASE[j] <- NEWBASE[j - 1] + T0P[j - 1] - BASE[j - 1] + [τ] – [δ] и δ <- τ.
G6. [Переупаковка.] Пусть TOP [j] <-Т0Р[j]-1. (Таким образом задается истинный размер j-гo стека для того, чтобы не предпринимались попытки переместить информацию за его пределами.) Выполните приведенный ниже алгоритм R, а затем установите ТОР [j] <- ТОР [j] + 1. Наконец, установите 0LDT0P[j] <-ТОР [ j] для 1 < j < п. |
Вероятно, наиболее интересной частью всего этого алгоритма является сам процесс перераспределения, который описывается ниже. Он не совсем тривиален, поскольку одни фрагменты памяти смещаются вниз, а другие — вверх. Очевидно, что очень важно не наложить перемещаемый фрагмент памяти на другую полезную информацию, после чего она может быть полностью утрачена.
Алгоритм R (Перемещение последовательных таблиц). Для 1 < j < n информация, заданная с помощью адресов BASE [ j] и ТОР [ j] в соответствии с указанными выше соглашениями, перемещается на новое место, задаваемое с адресами NEWBASE[j], а сами величины BASE [j] и ТОР [j] после этого принимают новые значения. Данный алгоритм основан на легко проверяемом условии, что перемещаемые вниз данные не должны пересекаться с любыми другими перемещаемыми вверх данными, а также с любыми неперемещаемыми данными.
R1. [Инициализация.] Установить j <- 1.
R2. [Поиск начала перемещения.] (Теперь все перемещаемые вниз стеки с 1- до j-ro перемещены в новое место.) Будем последовательно увеличивать значение j с шагом 1 до тех пор, пока не выполнится одно из перечисленных ниже условий:
-
NEWBASE[j] < BASE[j]: перейти к шагу R3;
-
j > n: перейти к шагу R4.
R3. [Перемещение списка вниз.] Установить δ <- BASE[j] –NEWBASE[j]. Установить CONTENTS(L -δ)<- CONTENTS(L) для L = BASE[j] + 1, BASE[j] + 2, ..., TOP[j]. (Возможен вариант, когда значение BASE [j] равно TOP [j]; тогда никаких действий предпринимать не следует.) Установить BASE[j] <- NEWBASE[j], TOP [j] <- TOP [j] - δ. Вернуться к шагу R2.
R4. [Поиск начала перемещения.] (Теперь все перемещаемые вниз стеки с j-ro по n-й перемещены в нужное место.) Будем последовательно уменьшать значение j с шагом 1 до тех пор, пока не выполнится одно из перечисленных ниже условий:
-
NEWBASE[j] > BASE[j]: перейти к шагу R5;
-
j = 1: прервать выполнение алгоритма.
R5. [Перемещение списка вверх.] Установить δ <- NEWBASE[j] - BASE[j]. Установить CONTENTS(L + δ) <- CONTENTS(L) для L = T0P[j], T0P[j] - 1, ..., BASE[j] + 1. (Как и во время выполнения шага R3, здесь возможен такой вариант, когда никаких действий предпринимать не потребуется.) Установить BASE[j] <- NEWBASE[j], TOP [j] <- TOP [j] + δ. Вернуться к шагу R4. |
Обратите внимание, что стек 1 никогда не придется перемещать. Следовательно, если известно, какой стек обладает наибольшим размером, для повышения эффективности работы программы его можно расположить первым.
Практическая часть
Текст программы на языке Си
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int base[5];
int top[5];
int contents[20];
int oldtop[5];
int newbase[5];
void R() {
//R1 - начальная установка
int j = 0;
//R2 - поиск начала сдвига
for (j++; j < 4; j++) {
if (newbase[j] < base[j]) {
// R3 - сдвиг вниз
int delta = base[j] - newbase[j];
for (int L = base[j] + 1; L <= top[j]; L++) {
contents[L - delta] = contents[L];
}
base[j] = newbase[j];
top[j] = top[j] - delta;
continue;
}
if (newbase[j] > base[j]) {
// R4 - поиск верхней границы сдвига
for (int k=j;k<=4;k++) {
if(newbase[k+1]<=base[k+1]) {
//R5 Сдвиг вверх
for (int T=k;T>=j;T--) {
int delta = newbase[T] - base[T];
for (int L=top[T];L>base[T]+1;L--) {
contents[L+delta]=contents[L];
}
base[T] = newbase[T];
top[T] = top[T] + delta;
}
}
j=k;
}
}
}
}
void G(int i) {
// G1 Начальная установка
int sum = 20;
int inc = 0;
int d[4];
// G2 Сбор статистики
for (int j = 0; j < 4; j++) {
sum = sum - (top[j] - base[j]);
if (top[j] > oldtop[j]) {
d[j] = top[j] - oldtop[j];
inc = inc + d[j];
} else {
d[j] = 0;
}
}
// G3 Проверка на заполненость памяти
if (sum == 0) return; //Память полна и дальше работать нельзя
// G4 Вычисление коэффициентов распределения
double alpha = 0.1 * sum / 4;
double beta = 0.9 * sum / inc;
// G5 Вычисление новых базовых адресов
newbase[0] = base[0];
double sigma = 0;
double tau;
for (int j = 1; j < 4; j++) {
tau = sigma + alpha + d[j - 1] * beta;
int itau = tau;
int isigma = sigma;
newbase[j] = newbase[j - 1] + top[j - 1] - base[j - 1] + itau - isigma;
sigma = tau;
}
//G6 Переупаковка
top[i] = top[i] - 1;
R(); // Запускается алгоритм R
}
void include(int number) { // Функция по добавлению элементов в стек
number--;
top[number]++;
if (top[number] > base[number + 1]) { // Место в нужном стеке закончилось
G(number); // Запускаем алгоритм G
} else {
contents[top[number]] = number + 1; // Место есть, записываем значение
}
}
int main(int argc, char** argv) {
//Присваивание стандартных значений base[i] и top[i]
base[0] = -1;
top[0] = 1;
base[1] = 4;
top[1] = 4;
base[2] = 7;
top[2] = 9;
base[3] = 9;
top[3] = 10;
base[4] = 19;
top[4] = 19;
for (int i = 0; i < 4; i++) {
oldtop[i] = top[i];
}
newbase[4] = base[4];
//Помещение данных в массив contents
for (int i = 0; i < 4; i++) {
for (int j = base[i] + 1; j <= top[i]; j++) {
contents[j] = i + 1;
}
}
//Добавление элементов в стек
include(2);
include(1);
include(2);
include(2);
include(3); // Здесь возникает переполнение
// Вывод значений после переупаковки
for (int i=0;i<4;i++) {
printf("base[%i] = %i, top[%i] = %i\n",i+1,base[i],i+1,top[i]);
}
return 0;
}
Результаты работы программы
base[1] = -1, top[1] = 2
base[2] = 4, top[2] = 7
base[3] = 12, top[3] = 14
base[4] = 17, top[4] = 18
Заключение
В ходе выполнения лабораторной работы я научился программировать алгоритм распределения последовательных таблиц.