Лабораторная работа №21 / ОС2
.docСанкт-Петербургский Государственный Электротехнический
Университет «ЛЭТИ»
Кафедра МОЭВМ
Лабораторная работа по ОС №2
«Управление памятью в ОС»
О Т Ч Е Т
Факультет КТИ
группа 3382
студент Марьяскин Е.
Худяков Я.
Санкт-Петербург
2006 г.
Постановка задачи.
Реализовать менеджер памяти на основе списка свободных ячеек. Изначально выделяется 1мб памяти. Необходимо разработать функции, позволяющие выделять память и очищать.
Описание алгоритма.
Создается линейный список свободных ячеек. Каждый элемент списка содержит указатель на начало свободного блока и размер этого блока. Список поддерживается отсортированным по адресам.
На этапе начальной инициализации выделяется 1мб памяти и весь этот блок заносится в список как свободный.
При выделении памяти под объект ведется поиск наиболее подходящего свободного блока. Наиболее подходящим считается первый же блок с таким же размером, как надо выделить. Если такого блока не существует – выбирается самый большой блок. Под объект выделяется первая часть такого блока (с младшими адресами). Если нет ни одного блока с размером, не уступающим размеру объекта, возвращается пустой указатель, память не выделяется.
При освобождении памяти происходит проверка, действительно ли освобождаемая память относится к рабочей области и считается выделенной (не имеет пересечений с блоками списка). Затем в соответствующей (по возрастанию адресов) позиции в список добавляется новый блок. После чего список проверяется на возможность соединить соседние блоки.
Структура данных.
/*описания свободного блока*/
typedef struct
{
void* pBlockStart;
unsigned int nBlockSize;
} FreeBlock;
/**элемент списка свободных блоков/
typedef struct
{
FreeBlock Data;
void* pNext;
} ListElement;
/*полный максимальный объем памяти*/
const unsigned short USED_MEMORY=1024;
/*указатель на начало выделяемой памяти*/
void *pFreeMemoryStart;
/*список свободных блоков*/
ListElement *pFreeMemory;
Описание функций.
extern void INIT(); - Инициализирует все необходимое для работы
extern int newFREE(void *from, int Size); - освобождает блок памяти размера Size, начиная с позиции from. Возвращает 0, если освобождение прошло успешно, 1 если входные параметры не соответствуют рабочей области памяти. Если в качестве второго параметра подавать NULL, будет освобождаться 1 байт.
extern void newFREEALL(); - полностью освобождает всю рабочую память.
extern void* newALLOC(int nSize); - выделяет блок памяти размера nSize. Возвращает указатель на начало блока. Если выделить память невозможно – возвращает NULL
void concatenateBlocks() – соединяет все свободные соседние блоки памяти в один.
void printList() - выводит на экран информацию о содержимом списка в следующем формате: в каждой строке содержится описание одного блока, сначала значения указателя(в десятичной системе счисления для удобства счета при отладке), а через пробел – размер блока.
Текст программы.
-
заголовочный файл “H.h”
#ifndef MEMORY_HEADER
#define MEMORY_HEADER
extern void INIT();
extern int newFREE(void *from, int Size);
extern void newFREEALL();
extern void* newALLOC(int nSize);
void concatenateBlocks();
void printList();
#endif
-
файл реализации “H.c”
#include <stdio.h>
#include <stdlib.h>
#include "H.H"
typedef struct
{
void* pBlockStart;
unsigned int nBlockSize;
} FreeBlock;
typedef struct
{
FreeBlock Data;
void* pNext;
} ListElement;
unsigned long USED_MEMORY = 1024;
void *pFreeMemoryStart;
ListElement *pFreeMemory;
extern void INIT()
{
pFreeMemoryStart = malloc(USED_MEMORY);
pFreeMemory = malloc(sizeof(ListElement));
(pFreeMemory->Data.pBlockStart) = pFreeMemoryStart;
pFreeMemory->Data.nBlockSize = USED_MEMORY;
pFreeMemory->pNext = NULL;
};
void concatenateBlocks()
{
ListElement *ptr2,*ptr=pFreeMemory;
while ((ptr!=NULL)&&(ptr->pNext!=NULL))
{
if ((int) (ptr->Data.pBlockStart) + (ptr->Data.nBlockSize) ==
(int)((ListElement*)(ptr->pNext))->Data.pBlockStart)
{
ptr->Data.nBlockSize+=((ListElement*)(ptr->pNext))->Data.nBlockSize;
ptr2=(ListElement*) ptr->pNext;
ptr->pNext = ptr2->pNext;
free(ptr2);
}
else
ptr=(ListElement*)ptr->pNext;
}
}
extern int newFREE(void *from, int Size)
{
int nSize=Size;
ListElement *ptr=pFreeMemory,
*ptr2;
if (Size == NULL) nSize=1;
if ((ptr == NULL)&&
(from>=pFreeMemoryStart)&&
((int)from+nSize<=(int)pFreeMemoryStart+USED_MEMORY))
{
pFreeMemory = malloc(sizeof(ListElement));
pFreeMemory->pNext = NULL;
pFreeMemory->Data.pBlockStart = from;
pFreeMemory->Data.nBlockSize = nSize;
return 0;
};
if ((from>=pFreeMemoryStart) &&
((int)from+nSize-1 < (int)ptr->Data.pBlockStart))
{
ptr2 = malloc(sizeof(ListElement));
ptr2->pNext = pFreeMemory;
ptr2->Data.pBlockStart = from;
ptr2->Data.nBlockSize = nSize;
pFreeMemory=ptr2;
concatenateBlocks();
return 0;
};
while ((ptr!=NULL)&&(ptr->pNext!=NULL))
{
if ((((int)from >= (int)(ptr->Data.pBlockStart)+(ptr->Data.nBlockSize)))&&
(((int)from + nSize-1 < ((ListElement*)(ptr->pNext))->Data.pBlockStart)))
{
ptr2 = malloc(sizeof(ListElement));
ptr2->pNext = ptr->pNext;
ptr2->Data.pBlockStart = from;
ptr2->Data.nBlockSize = nSize;
ptr->pNext=ptr2;
concatenateBlocks();
return 0;
};
ptr = ptr->pNext;
};
if (((int)from >= (int)(ptr->Data.pBlockStart) + (ptr->Data.nBlockSize)) &&
((int)from+nSize<=(int)pFreeMemoryStart+USED_MEMORY))
{
ptr2 = malloc(sizeof(ListElement));
ptr2->pNext = NULL;
ptr2->Data.pBlockStart = from;
ptr2->Data.nBlockSize = nSize;
ptr->pNext=ptr2;
concatenateBlocks();
return 0;
};
return 1;
}
extern void newFREEALL()
{
free(pFreeMemory->pNext);
(pFreeMemory->Data.pBlockStart) = pFreeMemoryStart;
pFreeMemory->Data.nBlockSize = USED_MEMORY;
pFreeMemory->pNext = NULL;
}
extern void* newALLOC(int nSize)
{
ListElement *ptr=pFreeMemory,
*max=ptr,
*oldptr;
void *ret;
concatenateBlocks();
if (pFreeMemory == NULL)
return NULL;
if (ptr->Data.nBlockSize == nSize)
{
ret=ptr->Data.pBlockStart;
pFreeMemory=(ListElement*) ptr->pNext;
free(ptr);
return ret;
};
oldptr = ptr;
ptr = (ListElement*) ptr->pNext;
while (ptr!=NULL)
{
if (ptr->Data.nBlockSize == nSize)
{
ret=ptr->Data.pBlockStart;
oldptr->pNext = ptr->pNext;
free(ptr);
return ret;
}
else if ((ptr->Data.nBlockSize > nSize)&&
(ptr->Data.nBlockSize > max->Data.nBlockSize))
{
max = ptr;
};
oldptr=ptr;
ptr = ptr->pNext;
};
if (max->Data.nBlockSize < nSize)
return NULL;
ret = max->Data.pBlockStart;
max->Data.pBlockStart=(int)(max->Data.pBlockStart) + nSize;
max->Data.nBlockSize-=nSize;
return ret;
};
void printList()
{
ListElement *ptr=pFreeMemory;
printf("\r\n");
while (ptr!=NULL)
{
printf("%d", ptr->Data.pBlockStart);
printf(" ");
printf("%u", ptr->Data.nBlockSize);
printf("\r\n");
ptr=(ListElement*) ptr->pNext;
}
}
-
тестировочный модуль. “Test.c”
#include "H.C"
#include <conio.h>
void main()
{
ListElement *p1,*p2;
int i,*pi,j;
long l,*pl;
short s,*ps;
char c,*pc;
double d,*pd;
for (j=0;j<25;j++)
printf("\r\n");
printf("addr bytes\r\n");
printf("\r\n**Initializing memory list**");
getch();
INIT();
printList();
printf("\r\n**take memory for int i**");
getch();
pi=newALLOC(sizeof(i));
printList();
printf("\r\n**take memory for long l**");
getch();
pl=newALLOC(sizeof(l));
printList();
printf("\r\n**take memory for short s**");
getch();
ps=newALLOC(sizeof(s));
printList();
printf("\r\n**take memory for double d**");
getch();
pd=newALLOC(sizeof(d));
printList();
printf("\r\n**free memory from long l**");
getch();
newFREE(pl,sizeof(l));
printList();
printf("\r\n**free memory from short s**");
getch();
newFREE(ps,sizeof(s));
printList();
printf("\r\n**free memory from double d**");
getch();
newFREE(pd,sizeof(d));
printList();
printf("\r\n**free memory from int i**");
getch();
newFREE(pi,sizeof(i));
printList();
getch();
free(pFreeMemory);
}
Тестирование.
В тестировочном модуле проверяется основная функциональность разработанных функций на соответствие заданию. Кроме того, на этапе отладки проводилось более полное тестирование, не включенное в итоговый тестировочный модуль. Программа успешно прошла все тесты.
Выводы.
Разработана программа, отвечающая заданию.