实验五内存管理实验

一、实验目的

1、了解操作系统动态分区存储管理过程和方法。

2、掌握动态分区存储管理的主要数据结构--空闲表区。

3、加深理解动态分区存储管理中内存的分配和回收。

4、掌握空闲区表中空闲区3种不同放置策略的基本思想和实现过程。

5、通过模拟程序实现动态分区存储管理。

6、了解请求分页虚拟存储管理技术的方法和特点。

7、通过模拟实现请求页式存储管理的几种基本页面置换算法。

8、掌握页面置换算法种缺页率、置换率和命中率的计算方法。

二、实验内容

1、编程模拟实现动态分区管理中内存的分配和回收及空闲区表的管理。（2分）

首次适应算法（First Fit）参考程序：

#include<unistd.h>

#include<stdio.h>

#include<stdlib.h>

#define N 5

struct freearea

{

int startaddr; //空闲区起始地址

int size; //空闲区大小

int state; //1表示空闲，0表示占用

}freeblock[N]={{20,20,1},{80,50,1},{150,100,1},{300,30,1},{600,100,1}};

int alloc(int size)

{

int i,tag=0,allocaddr;

for(i=0;i<N;i++)

{

if(freeblock[i].state==1 && freeblock[i].size>size) //申请空间小于空闲空间

{

allocaddr=freeblock[i].startaddr; //作业地址

freeblock[i].startaddr+=size; //新空闲区起始地址

freeblock[i].size-=size; //新空闲区大小

tag=1; //分配标记

break;

}

else if(freeblock[i].state==1 && freeblock[i].size==size)//申请空间正好等于空闲空间

{

allocaddr=freeblock[i].startaddr;

freeblock[i].state=0;tag=1;

break;

}

if(tag==0) //表示没找到合适的空闲区，未分配内存

allocaddr=-1;

return allocaddr; //返回作业地址

}

void setfree(int addr,int size) //传过来的参数是要释放内存的起始地址和大小

{

int i,tag1=0,tag2=0,n1=0,n2=0;

for(i=0;i<N;i++)

{

if(freeblock[i].startaddr+freeblock[i].size==addr && freeblock[i].state==1)

{

tag1=1; //有上邻标记

n1=i; //记录上邻数组位置（分区号）

break;

}

for(i=0;i<N;i++)

{

if(freeblock[i].startaddr==addr+size && freeblock[i].state==1)

{

tag2=1; //有下邻标记

n2=i; //记录下邻数组位置（分区号）

break;

}

if(tag1==1 && tag2==0) //有上邻无下邻

{

freeblock[n1].size+=size;

}

else if(tag1==1 && tag2==1) //有上邻有下邻

{

freeblock[n1].size+=freeblock[n2].size+size;

freeblock[n2].state=0;//？？？

}

else if(tag1==0 && tag2==1) //无上邻有下邻

{

freeblock[n2].startaddr=addr;

freeblock[n2].size+=size;

}

else //无上邻无下邻（表明空间正好全部分配出去，空间的状态为0）

{

for(i=0;i<N;i++)

{

if(freeblock[i].state==0) //通过空间状态值找到这块空间

{

freeblock[i].startaddr=addr;

freeblock[i].size=size;

freeblock[i].state=1;

break;

}

void adjust()

{

int i,j;

struct freearea temp;

for(i=1;i<N;i++) //依据首次适应算法将空闲区按起始地址由低到高冒泡排序

{

for(j=0;j<N-i;j++)

{

if(freeblock[j].startaddr>freeblock[j+1].startaddr)

{

temp=freeblock[j];

freeblock[j]=freeblock[j+1];

freeblock[j+1]=temp;

}

for(i=1;i<N;i++) //把状态为0的排到后面

{

for(j=0;j<N-i;j++)

{

if(freeblock[j].state==0 && freeblock[j+1].state==1)

{

temp=freeblock[j];

freeblock[j]=freeblock[j+1];

freeblock[j+1]=temp;

}

void print()

{

int i;

printf("\t|-------------------------------|\n");

printf("\t|startaddr size state |\n");

for(i=0;i<N;i++)

printf("\t|%4d %4d %4d |\n",freeblock[i].startaddr,freeblock[i].size,freeblock[i].state);

}

int main()

{

int size,addr;

char c1,c2,c;

printf("At first the free memory is this:\n");//首先，空闲区是这样的

adjust();

print();

printf("Is there any job request memory?(y or n):");//有作业需要申请内存么？

while((c1=getchar())=='y')

{

printf("Input request memory size:"); //输入所需内存大小

scanf("%d",&size);

addr=alloc(size); //调用内存分配函数，返回的是作业的起始地址

if(addr==-1)

printf("There is no fit memory.Please wait!!!\n");

else

{

printf("Job's memory start address is:%d\n",addr); //输出作业的起始地址

printf("Job's size is:%d\n",size); //输出作业大小

printf("After allocation the free memory is this:\n"); //分配后可用内存如下： adjust();

print();

printf("Job is running.\n");

}

getchar();

printf("Is there any memory for free?(y or n):");//有需要释放的内存么？

while((c2=getchar())=='y')

{

printf("Input free area startaddress:");

scanf("%d",&addr); //输入要释放内存的起始地址

printf("Input free area size:");

scanf("%d",&size); //输入要释放内存的大小

setfree(addr,size); //调用释放内存函数

adjust();

print();

getchar();

printf("Is there any memory for free?(y or n):");

}

getchar();

printf("Is there any job request memory?(y or n):");

}

return 0;

}

运行结果截屏（包含分配和回收两部分）:

分析该程序，列出各模块实现的功能：

1）alloc()

alloc()函数的功能是根据作业大小，在空闲区中分配合适大小的内存空间，并返回分配的作业的起始地址

2）setfree()

setfree()函数的功能是将释放的内存空间标记为空闲状态，并根据释放空间的位置和大小，进行合并操作。

3) adjust()

adjust()函数的功能是对空闲区进行排序和调整，按照首次适应算法将空闲区按照起始地址由低到高进行冒泡排序，并将状态为0的空闲区排到后面。

修改上题，用最佳适应算法和最坏适应算法模拟内存空间的分配和回收。（4分）

注：只需列出程序不同部分，无需将整个程序列出。

最佳适应算法

int best_fit_alloc(int size) {

int i, allocaddr = -1, min_size = INT_MAX;

for (i = 0; i < N; i++) {

if (freeblock[i].state == 1 && freeblock[i].size >= size && freeblock[i].size < min_size) {

allocaddr = freeblock[i].startaddr;

min_size = freeblock[i].size;

}

if (allocaddr != -1) {

for (i = 0; i < N; i++) {

if (freeblock[i].startaddr == allocaddr) {

if (freeblock[i].size > size) {

freeblock[i].startaddr += size;

freeblock[i].size -= size;

} else {

freeblock[i].state = 0;

}

break;

}

return allocaddr;

}

(2)最坏适应算法

int worst_fit_alloc(int size) {

int i, allocaddr = -1, max_size = -1;

for (i = 0; i < N; i++) {

if (freeblock[i].state == 1 && freeblock[i].size >= size && freeblock[i].size > max_size) {

allocaddr = freeblock[i].startaddr;

max_size = freeblock[i].size;

}

if (allocaddr != -1) {

for (i = 0; i < N; i++) {

if (freeblock[i].startaddr == allocaddr) {

if (freeblock[i].size > size) {

freeblock[i].startaddr += size;

freeblock[i].size -= size;

} else {

freeblock[i].state = 0;

}

break;

}

return allocaddr;

}

编写程序实现先进先出页面置换算法，并计算缺页次数，缺页率，置换次数和命中率。（2分）

参考程序：

#include <stdio.h>

//初始化内存队列

void initializeList(int list[],int number){

int i;

for (i = 0; i < number; i ++) {

list[i] = -1;

}

//展示要访问页面号数组

void showList(int list[], int number){

int i;

for (i = 0; i < number; i ++) {

printf("%2d",list[i]);

}

printf("\n");

}

//展示当前内存状态

void showMemoryList(int list[],int phyBlockNum){

int i;

for (i = 0; i < phyBlockNum; i ++) {

if (list[i] == -1) {

break;

}

printf(" |%d|",list[i]);

}

printf("\n");

}

//计算各项指标

void informationCount(int missingCount,int replaceCount,int pageNum){

printf("缺页次数:%d 缺页率:%d/%d\n",missingCount,missingCount,pageNum);

double result = (double)(pageNum - missingCount)/(double)pageNum;

printf("置换次数:%d 命中率:%.2f\n",replaceCount,result);

}

//先进先出置换算法

void replacePageByFIFO(int memoryList[],int phyNum,int strList[],int pageNum){

//置换次数

int replaceCount = 0;

//缺页次数

int missingCount = 0;

//记录当前最早进入内存的下标

int pointer = 0;

//记录当前页面的访问情况: 0 未访问

int i,j,isVisited = 0;

for (i = 0; i < pageNum; i ++) {

isVisited = 0;

//判断是否需要置换->内存已满且需要访问的页面不在内存中

for (j = 0; j < phyNum; j ++) {

if (memoryList[j] == strList[i]) {

//该页面已经存在内存中

//修改访问情况

isVisited = 1;

//展示

printf("%d\n",strList[i]);

break;

}

if (memoryList[j] == -1) {

//页面不在内存中且内存未满->直接存入

memoryList[j] = strList[i];

//修改访问情况

isVisited = 1;

missingCount ++;

//展示

printf("%d\n",strList[i]);

showMemoryList(memoryList, phyNum);

break;

}

if (!isVisited) {

//当前页面还未被访问过->需要进行页面置换

//直接把这个页面存到所记录的下标中

memoryList[pointer] = strList[i];

//下标指向下一个

pointer ++;

//如果到了最后一个，将下标归零

if (pointer > phyNum-1) {

pointer = 0;

}

missingCount ++;

replaceCount ++;

//展示

printf("%d\n",strList[i]);

showMemoryList(memoryList, phyNum);

}

informationCount(missingCount, replaceCount, pageNum);//计算各项指标

}

int main(int argc, const char * argv[]) {

//物理块的数量

int phyBlockNum;

printf("请输入物理块数量:\n");

scanf("%d",&phyBlockNum);

//生成内存队列数组

int memoryList[phyBlockNum];

//初始化内存状态

initializeList(memoryList, phyBlockNum);

//showMemoryList(memoryList,phyBlockNum);

//页面数量

int pageNum;

printf("请输入要访问的页面总数:\n");

scanf("%d",&pageNum);

//保存页面号数组

int pageNumStrList[pageNum];

int i;

//将要访问的页面号存入数组中

printf("请输入要访问的页面号:\n");

for (i = 0; i < pageNum; i ++) {

scanf("%d",&pageNumStrList[i]);

}

//显示要访问页面号数组中内容

showList(pageNumStrList, pageNum);

int chose;

while (1) {

printf("请选择所需的置换算法:\n");

printf("1.FIFO 2.退出\n");

scanf("%d",&chose);

switch (chose) {

case 1:

//显示要访问页面号数组中内容

showList(pageNumStrList, pageNum);

//调用先进先出置换算法

replacePageByFIFO(memoryList, phyBlockNum, pageNumStrList, pageNum);

//重新初始化内存

initializeList(memoryList , phyBlockNum);

break;

default:

return 0;

break;

}

return 0;

}

编译及执行过程以及结果截屏：

分析程序功能：

主要功能包括：

初始化内存队列：将内存队列中的每个元素初始化为-1。
展示要访问页面号数组：打印输出要访问的页面号数组。
展示当前内存状态：打印输出当前内存中存储的页面号。
计算各项指标：根据缺页次数和页面总数计算缺页率，根据置换次数和页面总数计算命中率，并打印输出。
先进先出置换算法：根据页面号数组和内存队列，实现FIFO算法进行页面置换。根据内存是否已满以及页面是否已存在内存中来判断是否需要进行页面置换，并更新内存队列和各项指标。
主函数中，根据用户的选择调用不同的置换算法函数，实现页面置换。

编程实现其它页面置换算法（如最近最久未使用算法或最佳置换算法等），计算缺页次数，缺页率，置换次数和命中率。（1分）

#include <stdio.h>

#define MAX_PAGES 100

#define MAX_FRAMES 10

// 初始化页面访问序列

void initializePages(int pages[], int numPages) {

printf("请输入页面访问序列（以-1结束）：\n");

int i = 0;

do {

scanf("%d", &pages[i]);

i++;

} while (pages[i-1] != -1 && i < numPages);

}

// LRU算法

int lru(int pages[], int numPages, int numFrames) {

int frames[MAX_FRAMES] = {-1}; // 帧表

int lruCount[MAX_FRAMES] = {0}; // 记录每个帧最后一次使用的时间

int numFaults = 0; // 缺页次数

int numReplacements = 0; // 置换次数

int numHits = 0; // 命中次数

int time = 0; // 记录时间

for (int i = 0; i < numPages; i++) {

int page = pages[i];

int j;

for (j = 0; j < numFrames; j++) {

if (frames[j] == page) {

numHits++;

lruCount[j] = time;

break;

}

if (j == numFrames) {

int lruIndex = 0;

for (int k = 1; k < numFrames; k++) {

if (lruCount[k] < lruCount[lruIndex]) {

lruIndex = k;

}

frames[lruIndex] = page;

lruCount[lruIndex] = time;

numFaults++;

numReplacements++;

}

time++;

}

printf("\nLRU算法结果：\n");

printf("缺页次数：%d\n", numFaults);

printf("缺页率：%f\n", (float)numFaults/numPages);

printf("置换次数：%d\n", numReplacements);

printf("命中率：%f\n\n", (float)numHits/numPages);

return numFaults;

}

// 最佳置换算法

int optimal(int pages[], int numPages, int numFrames) {

int frames[MAX_FRAMES] = {-1}; // 帧表

int numFaults = 0; // 缺页次数

int numReplacements = 0; // 置换次数

int numHits = 0; // 命中次数

for (int i = 0; i < numPages; i++) {

int page = pages[i];

int j;

for (j = 0; j < numFrames; j++) {

if (frames[j] == page) {

numHits++;

break;

}

if (j == numFrames) {

int replaceIndex = -1;

int found = 0;

for (int k = 0; k < numFrames; k++) {

int m;

for (m = i+1; m < numPages; m++) {

if (frames[k] == pages[m]) {

found = 1;

if (m > replaceIndex) {

replaceIndex = m;

}

break;

}

if (!found) {

replaceIndex = k;

break;

}

frames[replaceIndex] = page;

numFaults++;

numReplacements++;

}

printf("最佳置换算法结果：\n");

printf("缺页次数：%d\n", numFaults);

printf("缺页率：%f\n", (float)numFaults/numPages);

printf("置换次数：%d\n", numReplacements);

printf("命中率：%f\n\n", (float)numHits/numPages);

return numFaults;

}

int main() {

int pages[MAX_PAGES];

int numPages;

int numFrames;

printf("请输入页面数：");

scanf("%d", &numPages);

printf("请输入帧数：");

scanf("%d", &numFrames);

initializePages(pages, numPages);

lru(pages, numPages, numFrames);

optimal(pages, numPages, numFrames);

return 0;

}

编程用动态分区链形式模拟动态分区管理中内存的分配和回收，采用3种算法（首次适应算法，最佳适应算法，最坏适应算法）实现。（附加题）

#include <stdio.h>

#include <stdlib.h>

#define MAX_SIZE 100

typedef struct Node {

int start;

int end;

int size;

int status; // 0表示未分配，1表示已分配

struct Node* next;

} Node;

Node* head = NULL;

// 初始化内存

void initMemory() {

head = (Node*)malloc(sizeof(Node));

head->start = 0;

head->end = MAX_SIZE;

head->size = MAX_SIZE;

head->status = 0;

head->next = NULL;

}

// 打印内存分配情况

void printMemory() {

Node* current = head;

while (current != NULL) {

printf("[%d-%d] Size: %d ", current->start, current->end, current->size);

if (current->status == 0) {

printf("Status: Free\n");

} else {

printf("Status: Allocated\n");

}

current = current->next;

}

printf("\n");

}

// 首次适应算法分配内存

void* allocateFirstFit(int size) {

Node* current = head;

while (current != NULL) {

if (current->status == 0 && current->size >= size) {

int remainingSize = current->size - size;

if (remainingSize > 0) {

Node* newNode = (Node*)malloc(sizeof(Node));

newNode->start = current->start;

newNode->end = current->start + size;

newNode->size = size;

newNode->status = 1;

newNode->next = current->next;

current->start = newNode->end;

current->size = remainingSize;

current->next = newNode;

} else {

current->status = 1;

}

return (void*)current->start;

}

current = current->next;

}

return NULL;

}

// 最佳适应算法分配内存

void* allocateBestFit(int size) {

Node* current = head;

Node* bestFitBlock = NULL;

int bestFitSize = MAX_SIZE + 1;

while (current != NULL) {

if (current->status == 0 && current->size >= size && current->size < bestFitSize) {

bestFitBlock = current;

bestFitSize = current->size;

}

current = current->next;

}

if (bestFitBlock != NULL) {

int remainingSize = bestFitBlock->size - size;

if (remainingSize > 0) {

Node* newNode = (Node*)malloc(sizeof(Node));

newNode->start = bestFitBlock->start;

newNode->end = bestFitBlock->start + size;

newNode->size = size;

newNode->status = 1;

newNode->next = bestFitBlock->next;

bestFitBlock->start = newNode->end;

bestFitBlock->size = remainingSize;

bestFitBlock->next = newNode;

} else {

bestFitBlock->status = 1;

}

return (void*)bestFitBlock->start;

}

return NULL;

}

// 最坏适应算法分配内存

void* allocateWorstFit(int size) {

Node* current = head;

Node* worstFitBlock = NULL;

int worstFitSize = -1;

while (current != NULL) {

if (current->status == 0 && current->size >= size && current->size > worstFitSize) {

worstFitBlock = current;

worstFitSize = current->size;

}

current = current->next;

}

if (worstFitBlock != NULL) {

int remainingSize = worstFitBlock->size - size;

if (remainingSize > 0) {

Node* newNode = (Node*)malloc(sizeof(Node));

newNode->start = worstFitBlock->start;

newNode->end = worstFitBlock->start + size;

newNode->size = size;

newNode->status = 1;

newNode->next = worstFitBlock->next;

worstFitBlock->start = newNode->end;

worstFitBlock->size = remainingSize;

worstFitBlock->next = newNode;

} else {

worstFitBlock->status = 1;

}

return (void*)worstFitBlock->start;

}

return NULL;

}

// 回收内存

void deallocate(void* addr) {

Node* current = head;

Node* prev = NULL;

while (current != NULL) {

if (current->start == (int)addr) {

current->status = 0;

// 合并相邻的空闲块

if (prev != NULL && prev->status == 0) {

prev->end = current->end;

prev->size += current->size;

prev->next = current->next;

free(current);

current = prev;

}

if (current->next != NULL && current->next->status == 0) {

current->end = current->next->end;

current->size += current->next->size;

Node* temp = current->next->next;

free(current->next);

current->next = temp;

}

return;

}

prev = current;

current = current->next;

}

int main() {

initMemory();

printMemory();

void* addr1 = allocateFirstFit(20);

printf("Allocated block: [0-20]\n");

printMemory();

void* addr2 = allocateBestFit(30);

printf("Allocated block: [20-50]\n");

printMemory();

void* addr3 = allocateWorstFit(40);

printf("Allocated block: [50-90]\n");

printMemory();

deallocate(addr2);

printf("Deallocated block: [20-50]\n");

printMemory();

deallocate(addr1);

printf("Deallocated block: [0-20]\n");

printMemory();

void* addr4 = allocateBestFit(70);

printf("Allocated block: [0-70]\n");

printMemory();

return 0;

}

三、实验总结和体会（1分）

通过操作系统内存管理实验，我深入了解了内存管理的重要性和各种页面置换算法的实现原理。在实验中，我学会了使用C语言编写代码来模拟内存管理过程，并计算缺页次数、缺页率、置换次数和命中率等指标。

在实验中，我发现不同的页面置换算法对于不同的页面访问序列会产生不同的结果。LRU算法能够较好地预测未来的页面访问情况，因此在某些情况下能够得到较好的性能。而最佳置换算法则会选择最长时间内不会被访问到的页面进行置换，从而最小化缺页次数。

通过实验，我还学会了如何计算缺页次数、缺页率、置换次数和命中率等指标，这些指标能够帮助我们评估不同的内存管理算法的性能。此外，我还学会了使用数组来表示页面和帧表，并使用循环来模拟页面访问过程。

实验五内存管理实验

相关资讯

热文排行

最新新闻

推荐新闻

热搜词

实验五 内存管理实验

相关资讯

热文排行

最新新闻

推荐新闻

热搜词

实验五内存管理实验