Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Архив1 / docx58 / лабораторная №2 (6)

.docx
Скачиваний:
25
Добавлен:
01.08.2013
Размер:
29.95 Кб
Скачать

Министерство образования и науки Российской Федерации ГОУ ВПО Тамбовский государственный технический университет

Кафедра «Информационные системы и защита информации»

О Т Ч Е Т

о лабораторной работе № 2 на тему

«ПЕРЕРАСПРЕДЕЛЕНИЕ ПОСЛЕДОВАТЕЛЬНЫХ ТАБЛИЦ»

Выполнил: студент гр. СИБ-21 Ивлиев П.В.

Проверил: доцент Кулаков Ю.В.

«___» 2010 г.

(Подпись)

Тамбов 2010

Цель работы: Научиться программировать алгоритм распределения последовательных таблиц

Вариант № 9

Задание: Пусть состояние памяти по окончании последней переупаковки будет следующим:

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

1

1

2

2

2

3

3

4

base[1]=-1 base[2]=4 base[3]=9 base[4]=13

top[1]=1 top[2]=7 top[3]=11 top[4]=14

В результате выполнения операций I1I3I2I1I4I4I2I4I2 возникает ПЕРЕПОЛНЕНИЕ и начинает свою работу алгоритм 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 до тех пор, пока не выполнится одно из перечисленных ниже условий:

  1. NEWBASE[j] < BASE[j]: перейти к шагу R3;

  2. 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 до тех пор, пока не выполнится одно из перечисленных ниже условий:

  1. NEWBASE[j] > BASE[j]: перейти к шагу R5;

  2. 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] = 7;

base[2] = 9;

top[2] = 11;

base[3] = 13;

top[3] = 14;

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(1);

include(3);

include(2);

include(1);

include(4);

include(4);

include(2);

include(4);

include(2); // Здесь возникает переполнение

// Вывод значений после переупаковки

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] = 3

base[2] = 3, top[2] = 8

base[3] = 10, top[3] = 13

base[4] = 14, top[4] = 18

Заключение

В ходе выполнения лабораторной работы я научился программировать алгоритм распределения последовательных таблиц.