操作系统实验报告
院别：计算机学院
班级：
学号：
序号：
姓名：
实验：内存管理实验
一、 实验目的
1、 通过本次试验体会操作系统中内存的分配模式；
2、 掌握内存分配的方法（FF,BF,WF）；
3、 学会进程的建立，当一个进程被终止时内存是如何处理被释放块，并当内存不满足进程申请时是如何使用内存紧凑；
4、 掌握内存回收过程及实现方法；
5、 学会进行内存的申请释放和管理；
二、 实验内容
附源代码：
//memory.h
====================================================
#ifndef MEMORY_H
#define MEMORY_H
#include ＜cstdio＞
#include ＜cstdlib＞
#include ＜malloc.h＞
#include ＜cstring＞
using namespace std;
#define PROCESS_NAME_LEN 32 /*进程名长度*/
#define MIN_SLICE 10 /*最小碎片的大小*/
#define DEFAULT_MEM_SIZE 1024 /*内存大小*/
#define DEFAULT_MEM_START 0 /*起始位置*/
/* 内存分配算法 */
#define MA_FF 1 //首次适应算法
#define MA_BF 2 //最佳适应算法
#define MA_WF 3 //最坏适应算法
int mem_size; /*内存大小*/
int ma_algorithm; /*当前分配算法*/
int pid; /*初始pid*/
int flag; /*设置内存大小标志*/
/*描述每一个空闲块的数据结构*/
struct free_block_type{
int size;
int start_addr;
struct free_block_type *next;
};
/*指向内存中空闲块链表的首指针*/
struct free_block_type *free_block_head;
/*每个进程分配到的内存块的描述*/
struct allocated_block{
int pid;
int size;
int start_addr;
char process_name[PROCESS_NAME_LEN];
struct allocated_block *next;
};
/*进程分配内存块链表的首指针*/
struct allocated_block *allocated_block_head;
/*初始化变量*/
void init_parameter(void);
/*初始化空闲块，默认为一块，可以指定大小及起始地址*/
struct free_block_type* init_free_block(int mem_size);
/*显示菜单*/
void display_menu(void);
/*设置内存的大小*/
int set_mem_size(void);
/* 设置当前的分配算法 */
int set_algorithm(void);
void rearrange(int algorithm);
/*按FF算法重新整理内存空闲块链表*/
int rearrange_FF(void);
/*按BF算法重新整理内存空闲块链表*/
int rearrange_BF(void);
/*按WF算法重新整理内存空闲块链表*/
int rearrange_WF(void);
/*创建新的进程，主要是获取内存的申请数量*/
int new_process(void);
/*分配内存模块*/
int allocate_mem(struct allocated_block *ab);
/*紧缩内存*/
int free_memory_rearrage(int memory_size,int size);
/*删除进程，归还分配的存储空间，并删除描述该进程内存分配的节点*/
int kill_process(void);
/*将ab所表示的已分配区归还，并进行可能的合并*/
struct allocated_block* find_process(int pid);
int free_mem(struct allocated_block *ab);
/*释放ab数据结构节点*/
int dispose(struct allocated_block *free_ab);
/* 显示当前内存的使用情况，包括空闲区的情况和已经分配的情况 */
int display_mem_usage(void);
//释放链表并退出
void do_exit(void);
#endif //memory_h
//memory.cpp
====================================================
#include "memory.h"
// 初始化变量
void init_parameter(void)
{
mem_size=DEFAULT_MEM_SIZE;
ma_algorithm = MA_FF;
pid = 0;
flag = 0;
free_block_head =(struct free_block_type *)malloc(sizeof(struct free_block_type));
free_block_head-＞size = 0;
free_block_head-＞start_addr =0;
free_block_head-＞next = NULL;
allocated_block_head = NULL;
}
/*初始化空闲块，默认为一块，可以指定大小及起始地址*/
struct free_block_type* init_free_block(int mem_size)
{
struct free_block_type *fb;
fb=(struct free_block_type *)malloc(sizeof(struct free_block_type));
if(fb==NULL){
fprintf(stderr,"Memory Application is Failed!\n");
exit(EXIT_FAILURE);
}
fb-＞size = mem_size;
fb-＞start_addr = DEFAULT_MEM_START;
fb-＞next = NULL;
return fb;
}
/*显示菜单*/
void display_menu(void)
{
printf("\n");
printf("1 - Set memory size (default=%d)\n", DEFAULT_MEM_SIZE);
printf("2 - Select memory allocation algorithm\n");
printf("3 - New process \n");
printf("4 - Terminate a process \n");
printf("5 - Display memory usage \n");
printf("0 - Exit\n");
}
/*设置内存的大小*/
int set_mem_size(void)
{
int size;
if(flag!=0){ //防止重复设置
fprintf(stderr,"Cannot set memory size again\n");
return 0;
}
printf("Total memory size =");
scanf("%d", &size);
if(size＞0){
mem_size = size;
free_block_head-＞next-＞size = mem_size;
}
flag=1;
return 1;
}
/* 设置当前的分配算法 */
int set_algorithm(void)
{
int algorithm;
printf("\t1 - First Fit\n");
printf("\t2 - Best Fit \n");
printf("\t3 - Worst Fit \n");
scanf("%d", &algorithm);
if(algorithm＞=1 && algorithm ＜=3)
ma_algorithm=algorithm;
else {
printf("you choice is error!\n");
return 0;
}
//按指定算法重新排列空闲区链表
rearrange(ma_algorithm);
return 1;
}
/*按指定的算法整理内存空闲块链表*/
void rearrange(int algorithm){
switch(algorithm){
case MA_FF: rearrange_FF(); break;
case MA_BF: rearrange_BF(); break;
case MA_WF: rearrange_WF(); break;
}
}
/*按FF算法重新整理内存空闲块链表*/
int rearrange_FF(void)
{
struct free_block_type *pointer,*pointer1,*pointer2;
pointer = free_block_head;
pointer1 = pointer2 = pointer-＞next;
/*使用插入法进行排序*/
while(pointer-＞next != NULL){
while(pointer2 != NULL){
if(pointer-＞next-＞start_addr ＜= pointer2-＞start_addr){
pointer1 = pointer2;
pointer2 = pointer2-＞next;
}
else{
pointer1-＞next = pointer2-＞next;
pointer2-＞next = pointer-＞next;
pointer-＞next = pointer2;
break;
}
}
pointer = pointer-＞next;
pointer1 = pointer2 = pointer-＞next;
}
return 1;
}
/*按BF算法重新整理内存空闲块链表*/
int rearrange_BF(void)
{
struct free_block_type *pointer,*pointer1,*pointer2;
pointer = free_block_head;
pointer1 = pointer2 = pointer-＞next;
/*使用冒泡法进行排序*/
while(pointer-＞next !=NULL){
while(pointer2 != NULL){
if(pointer-＞next-＞size ＜= pointer2-＞size){
pointer1 = pointer2;
pointer2 = pointer2-＞next;
}
else{
pointer1-＞next = pointer2-＞next;
pointer2-＞next = pointer-＞next;
pointer-＞next = pointer2;
break;
}
}
pointer = pointer-＞next;
pointer1 = pointer2 = pointer-＞next;
}
return 1;
}
/*按WF算法重新整理内存空闲块链表*/
int rearrange_WF(void)
{
struct free_block_type *pointer,*pointer1,*pointer2;
pointer = free_block_head;
pointer1 = pointer2 = pointer-＞next;
/*使用冒泡法进行排序*/
while(pointer-＞next != NULL){
while(pointer2 != NULL){
if(pointer-＞next-＞size ＞= pointer2-＞size){
pointer1 = pointer2;
pointer2 = pointer2-＞next;
}
else{
pointer1-＞next = pointer2-＞next;
pointer2-＞next = pointer-＞next;
pointer-＞next = pointer2;
break;
}
}
pointer = pointer-＞next;
pointer1 = pointer2 = pointer-＞next;
}
return 1;
}
/*创建新的进程，主要是获取内存的申请数量*/
int new_process(void)
{
struct allocated_block *ab;
int size;
int ret;
ab=(struct allocated_block *)malloc(sizeof(struct allocated_block));
if(!ab)
exit(-5);
ab-＞next = NULL;
pid++;
sprintf(ab-＞process_name, "PROCESS-%02d", pid);
ab-＞pid = pid;
printf("Memory for %s:", ab-＞process_name);
scanf("%d", &size);
if((size ＞ mem_size)|(size ＜ 0)){
fprintf(stderr,"you must input crrocet number!\n");
exit(EXIT_FAILURE);
}
else
ab-＞size=size;
ret = allocate_mem(ab); /* 从空闲区分配内存，ret==1表示分配ok*/
/*如果此时allocated_block_head尚未赋值，则赋值*/
if((ret==1) &&(allocated_block_head == NULL)){
allocated_block_head=ab;
return 1;
}
/*分配成功，将该已分配块的描述插入已分配链表*/
else if (ret==1) {
ab-＞next=allocated_block_head;
allocated_block_head=ab;
return 1;
}
else if(ret==-1){ /*分配不成功*/
printf("Allocation fail\n");
free(ab);
return -1;
}
return 1;
}
/*分配内存模块*/
int allocate_mem(struct allocated_block *ab)
{
struct free_block_type *fbt, *pre;
int request_size;
int memory_count;
memory_count = 0;
request_size=ab-＞size;
fbt = pre = free_block_head;
while((pre != NULL)&&(request_size ＞ pre-＞size)){ //遍历查找匹配空白区
memory_count +=pre-＞size;
fbt = pre;
pre = pre-＞next;
}
if(!pre){
if(memory_count ＞= request_size){
free_memory_rearrage(memory_count - request_size,request_size); /*不可满足，采用紧缩技术*/
return 0;
}
else{
printf("the memory allocated is failed!\n");
return 0;
}
}
else{
if((pre-＞size - request_size) ＞ MIN_SLICE){ //找到可满足空闲分区且分配后剩余空间足够大，则分割
pre-＞size = pre-＞size - request_size;
ab-＞start_addr = pre-＞start_addr + pre-＞size;
}
else {
fbt-＞next = pre-＞next; //找到可满足空闲分区且但分配后剩余空间比较小，则一起分配
ab-＞start_addr = pre-＞start_addr;
ab-＞size = pre-＞size;
}
}
rearrange(ma_algorithm); //分配成功，按照相应算法排序
return 1;
}
/*紧缩内存*/
int free_memory_rearrage(int memory_reduce_size,int size)
{
struct free_block_type *pointer1,*pointer2;
struct allocated_block *x1,*x2;
x1 = (struct allocated_block *)malloc(sizeof(struct allocated_block));
pointer1 = free_block_head-＞next;
pointer2 = pointer1-＞next;
pointer1-＞start_addr =0 ;
pointer1-＞size = memory_reduce_size;
pointer1-＞next = NULL;
while(pointer2 != NULL){
pointer1 = pointer2;
pointer2 = pointer2-＞next;
free(pointer1);
}
x2 = allocated_block_head;
x1-＞pid = pid;
x1-＞size =size;
x1-＞start_addr = memory_reduce_size;
sprintf(x1-＞process_name, "PROCESS-%02d", pid);
//x2-＞process_name ="the process";
//x1-＞next = allocated_block_head-＞next;
x1-＞next = allocated_block_head;
//free(allocated_block_head);
allocated_block_head = x1;
x2 = x1-＞next;
while(x2 != NULL){
x2-＞start_addr = x1-＞start_addr + x1-＞size;
x1 = x2;
x2 = x2-＞next;
}
return 1;
}
/*删除进程，归还分配的存储空间，并删除描述该进程内存分配的节点*/
int kill_process(void)
{
struct allocated_block *ab;
int pid;
printf("Kill Process, pid=");
scanf("%d", &pid);
ab=find_process(pid);
if(ab!=NULL){
free_mem(ab); /*释放ab所表示的分配区*/
dispose(ab); /*释放ab数据结构节点*/
}
return 1;
}
struct allocated_block* find_process(int pid)
{
struct allocated_block *pointer,*pointer1;
pointer=pointer1=allocated_block_head;
while(pointer1-＞next != NULL){
if(pointer1-＞pid == pid)
break;
else{
pointer = pointer1;
pointer1 = pointer1-＞next;
}
}
if(!pointer1){
fprintf(stderr,"your input pid is wrong!\n");
exit(EXIT_FAILURE);
}
return pointer1;
}
/*将ab所表示的已分配区归还，并进行可能的合并*/
int free_mem(struct allocated_block *ab)
{
struct free_block_type *fbt, *pre, *work;
pre = free_block_head;
work = free_block_head-＞next;
fbt=(struct free_block_type*) malloc(sizeof(struct free_block_type));
if(!fbt) return -1;
fbt-＞size = ab-＞size;
fbt-＞start_addr = ab-＞start_addr;
fbt-＞next = NULL;
rearrange(MA_FF); //按地址有序排列
while((work != NULL)&&(fbt-＞start_addr ＞ work-＞start_addr)){
pre = work;
work = work-＞next;
}
if(free_block_head-＞next == NULL){
free_block_head-＞next = fbt;
goto end;
}
//插入当前节点
if(!work){
pre-＞next = fbt;
if(fbt-＞start_addr == pre-＞start_addr+pre-＞size){
pre-＞next = work;
pre-＞size = pre-＞size + fbt-＞size;
}
}
else{
fbt-＞next = work;
pre-＞next = fbt;
// 检查并合并相邻的空闲分区
if((fbt-＞start_addr == pre-＞start_addr+pre-＞size)&&(fbt-＞start_addr+fbt-＞size == work-＞start_addr)){
pre-＞next = work-＞next;
pre-＞size = pre-＞size + fbt-＞size +work-＞size;
}
else
if(fbt-＞start_addr == pre-＞start_addr+pre-＞size){
pre-＞next = work;
pre-＞size = pre-＞size + fbt-＞size;
}
else
if(fbt-＞start_addr+fbt-＞size == work-＞start_addr){
fbt-＞next = work-＞next;
fbt-＞size = fbt-＞size + work-＞size;
}
}
// 将空闲链表重新按照当前算法排序
rearrange(ma_algorithm);
end: return 1;
}
/*释放ab数据结构节点*/
int dispose(struct allocated_block *free_ab)
{
struct allocated_block *pre, *ab;
if(free_ab == allocated_block_head) { /*如果要释放第一个节点*/
allocated_block_head = allocated_block_head-＞next;
free(free_ab);
return 1;
}
pre = allocated_block_head;
ab = allocated_block_head-＞next;
while(ab!=free_ab)
{
pre = ab;
ab = ab-＞next;
}
pre-＞next = ab-＞next;
free(ab);
return 1;
}
/* 显示当前内存的使用情况，包括空闲区的情况和已经分配的情况 */
int display_mem_usage(void)
{
struct free_block_type *fbt=free_block_head-＞next;
struct allocated_block *ab=allocated_block_head;
if(fbt==NULL)
printf("the block is full!\n");
printf("----------------------------------------------------------\n");
/* 显示空闲区 */
printf("Free Memory:\n");
printf("%20s %20s\n", " start_addr", " size");
while(fbt!=NULL){
printf("%20d %20d\n", fbt-＞start_addr, fbt-＞size);
fbt=fbt-＞next;
}
/* 显示已分配区 */
printf("\nUsed Memory:\n");
printf("%10s %20s %10s %10s\n", "PID", "ProcessName", " start_addr", "size");
while(ab!=NULL){
printf("%10d %20s %10d %10d\n", ab-＞pid, ab-＞process_name, ab-＞start_addr, ab-＞size);
ab=ab-＞next;
}
printf("----------------------------------------------------------\n");
return 1;
}
//释放链表并退出
void do_exit(void)
{
struct free_block_type *p1,*p2;
struct allocated_block *a1,*a2;
p1 = free_block_head;
p2 = p1-＞next;
a1 = a2 = allocated_block_head;
while(p2 != NULL){
free(p1);
p1 = p2;
p2 = p2-＞next;
}
if(a1 != NULL){
a2 = a1-＞next;
while(a2 != NULL){
free(a1);
a1 = a2;
a2 = a2-＞next;
}
}
}
====================================================
//main.cpp
====================================================
#include "memory.h"
int main(int argc,char **argv)
{
char choice;
struct free_block_type *free_block;
init_parameter();
free_block = init_free_block(mem_size); //初始化空闲区
free_block_head-＞next = free_block;
while(1){
display_menu(); //显示菜单
fflush(stdin);
printf("Please input your choice:");
choice=getchar(); //获取用户输入
switch(choice){
case '1': set_mem_size();//设置内存大小
break;
case '2': set_algorithm();//设置算法
flag = 1;
break;
case '3': new_process();//创建新进程
flag = 1;
break;
case '4': kill_process();//删除进程
flag = 1;
break;
case '5': display_mem_usage();//显示内存使用
flag = 1;
break;
case '0': do_exit(); //释放链表并退出
exit(0);
default: break;
}
}
return 0;
}
====================================================
三 实验结果
四 实验心得体会
这次试验让我们充分了解了内存管理的机制实现,从而更深一步的对计算机有了长足的了解,这对于我们以后研究或学习计算机系统起到了很重要的作用.