可重定向动态分区分配算法

组号 成绩

计算机操作系统

课程设计报告

题目内存的连续分配算法 基于动态分区分配的内存管理的模拟设计与实现

专业：

班级：

学号+姓名：

指导教师：

2016年12月 22 日

一.设计目的

掌握内存的连续分配方式的各种分配算法。

二.设计内容

本系统模拟操作系统内存分配算法的实现，实现动态分区分配，算法，采用PCB定义结构体来表示一个进程，定义了进程的名称和大小，进程内存起始地址和进程状态。内存分区表采用单链表来模拟实现。定义与算法相关的数据结构，如PCB，空闲分区；在使用动态分区分配算法时必须实现紧凑功能。

三．设计原理

1.首次适应算法分配内存：空闲分区链以地址递增的次序链接。进行内存分配时，从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已没有足够大的内存分配给该进程，内存分配结束，返回。

2.回收内存：当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链中找到相应的插入点：

（1）回收区与插入点的前一个空闲分区F1相邻接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需要修改前一分区F1的大小。

（2）回收区与插入点的后一个空闲分区F2相邻接，此时将两分区合并形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。

（3）回收区与插入点的前后两个空闲分区相邻接，此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。

（4）回收区与插入点的前后两个空闲分区均不相邻接，此时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。

3.紧凑：将内存中的所有作业移动，使他们全都相邻接。可以把原来分散的多个空闲小分区拼接成一个大分区，可将一个作业装入该区。这种技术称为“紧凑”。

四．详细设计及编码

1.模块分析

①paixu()：排序算法。按分区的起始位置以递增的次序排序。

②compact()：紧凑算法。记录每个忙碌分区的首址及大小，改变其首址。计算所有空闲分区的大小为新空闲分区的大小，首址为所有忙碌分区的大小总和。

③show(FENQU *p)：输出函数。输出分区信息（首址，大小，状态，进程号）。

④input()：输入函数。输入分区信息（分区个数，各分区首址，大小，状态，进程号）。调用show(FENQU *p)函数。

⑤FENQU *scsf()：（递归算法）首次适应算法。进行内存分配时，从链首开始顺序查找，

直到找到一个大小能满足要求的空闲分区为止。调用compact()函数。

⑥FENQU * huishou()：回收算法。当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链中找到相应的插入点，判断相应情况进行后续动作。

⑦void function()：逻辑函数。从键盘输入选择，实现相应操作。调用scsf()，huishou()，show(p)函数。

⑧int main()：主函数。调用input()，function()函数。

2.流程图

3.代码实现

#include

#include

#include

typedef struct memory{

int startaddress;//首址

int size;//大小

char state[10];//状态

int number;//进程号

struct memory *next;

}FENQU;

FENQU *ready=NULL, *p;

void paixu();

int len();

void compact();

void show(FENQU *p){

printf("%d\t",p->startaddress);

printf("%d\t",p->size);

printf("%s\t",p->state);

printf("%d\t\n\n",p->number);

}

//输入分区信息

void input(){

int i,address,size1,n,number1;

printf("请输入分区个数：");

scanf("%d",&n);

for(i=1;i

p=(FENQU*)malloc(sizeof(FENQU));

printf("请输入第%d个分区的起始地址：",i);

scanf("%d",&address);

p->startaddress=address;

printf("请输入第%d个分区的大小：",i);

scanf("%d",&size1);

p->size=size1;

printf("请输入第%d个分区的状态:",i);

scanf("%s",p->state);

if(strcmp(p->state,"1")==0){//判断分区状态是否闲

printf("请输入第%i个分区的进程号：",i);

scanf("%d",&number1);

p->number=number1;

}

else p->number=-1;//若空闲则定进程号为-1

printf("\n");

p->next=NULL;

paixu(); //按进程起始地址递增排序

}

p = ready;

printf("\n始址\t大小\t状态\t进程号 \n");

while (p != NULL){

show(p);

p = p->next;//继续遍历

}

}

//按分区的起始位置排序

void paixu()

{

FENQU *first,*second;

int insert=0;

if((ready == NULL) || ((p->startaddress) startaddress))) { p->next = ready;

ready = p;

}

else{

first = ready;

second = first->next;

while (second != NULL){

if (p->startaddress startaddress) {

p->next = second;

first->next = p;

insert = 1;

break;

}

else{

first = first->next;

second = second->next;

}

}

if (insert == 0) {

first->next = p;

p->next = NULL;

}

}

}

//首次适应算法

FENQU *scsf()

{

int asize;

int pcbnumber;

printf("请输入进程号，进程大小:");

scanf("%d %d",&pcbnumber,&asize);

printf("\n");

FENQU *pretail,*tail,*q;

p=ready;

pretail=tail=p;

while(tail!=NULL){

//符合条件，分配内存

if(strcmp(tail->state,"0")==0 && tail->size>asize){//分区空闲且长度大于进程长度

if(tail->size>asize){

q=(FENQU *)malloc(sizeof(FENQU));

q->startaddress=tail->startaddress;//进程分区首址为空闲分区首址 q->size=asize;// 进程分区长度为进程长度

strcpy(q->state,"1");//修改进程分区状态为忙碌

q->number=pcbnumber;//进程分区号为进程号

q->next=tail;//进程分区指向空闲分区

pretail->next=q;//令pretail指向当前进程分区

tail->startaddress+=asize;//空闲分区首址+=进程长度

tail->size = tail->size-asize;//空闲分区长度-=进程长度 break;

}

if(tail->size==asize){

tail->number=pcbnumber;

strcpy(tail->state,"1");

break;

}

}

else{

pretail=tail;

tail=tail->next;//后移

}

first = ready;

second = first->next;

while (second != NULL){

if (p->startaddress startaddress) {

p->next = second;

first->next = p;

insert = 1;

break;

}

else{

first = first->next;

second = second->next;

}

}

if (insert == 0) {

first->next = p;

p->next = NULL;

}

}

}

//首次适应算法

FENQU *scsf()

{

int asize;

int pcbnumber;

printf("请输入进程号，进程大小:");

scanf("%d %d",&pcbnumber,&asize);

printf("\n");

FENQU *pretail,*tail,*q;

p=ready;

pretail=tail=p;

while(tail!=NULL){

//符合条件，分配内存

if(strcmp(tail->state,"0")==0 && tail->size>asize){//分区空闲且长度大于进程长度

if(tail->size>asize){

q=(FENQU *)malloc(sizeof(FENQU));

q->startaddress=tail->startaddress;//进程分区首址为空闲分区首址 q->size=asize;// 进程分区长度为进程长度

strcpy(q->state,"1");//修改进程分区状态为忙碌

q->number=pcbnumber;//进程分区号为进程号

q->next=tail;//进程分区指向空闲分区

pretail->next=q;//令pretail指向当前进程分区

tail->startaddress+=asize;//空闲分区首址+=进程长度

tail->size = tail->size-asize;//空闲分区长度-=进程长度 break;

}

if(tail->size==asize){

tail->number=pcbnumber;

strcpy(tail->state,"1");

break;

}

}

else{

pretail=tail;

tail=tail->next;//后移

}

}

//不符合条件，进行紧凑

if(tail==NULL){

compact();//紧凑

scsf();//递归，首次适应

}

return p;

}

//紧凑

void compact(){

FENQU *front=NULL;

FENQU *temp=NULL;

int tempAddress=0;//临时地址变量，存放紧凑后的进程分区首址

//初始为内存首址 ,本程序中为0

int sumAddress=0;//存放空闲分区长度总和

while(p!=NULL){

if(strcmp(p->state,"1")==0){//当前分区状态为忙碌

p->startaddress=tempAddress;//当前分区首址置为临时地址变量 tempAddress+=p->size;//临时地址变量+=当前分区长度

front=p;

p=p->next;//后移

}

else{//当前分区为空闲分区

sumAddress+=p->size;//计算空闲分区长度总和

if(front!=NULL){

front->next=p->next;

}

else{

ready=p->next;

}

temp=p;

p=p->next;

free(temp);

}

}

temp=(FENQU *)malloc(sizeof(FENQU));//初始化temp指针存放空闲分区情况 temp->startaddress=tempAddress;//新空闲分区首址=临时地址变量=

temp->size=sumAddress;//新空闲分区长度=空闲分区长度总和

strcpy(temp->state,"0");//新空闲分区状态置为空闲

temp->number=-1;//新空闲分区进程号置为-1

front->next=temp;

temp->next=NULL;//新空闲分区在分区底部

p=ready;

}

//回收

FENQU * huishou(){

int pcbnumber1;

printf("请输入被回收空间的进程号:");

scanf("%d",&pcbnumber1);

printf("\n");

FENQU *pretail,*tail;

p=ready;

pretail=tail=p;

while(tail!=NULL){

if(tail->number==pcbnumber1){//找到该分区号

if(tail->next!=NULL){//回收区不是最后分区

if(strcmp(pretail->state,"1")==0 && strcmp(tail->next->state,"1")==0){ //上下均不邻接

strcpy(tail->state,"0");//仅回收回收区，回收区状态置为空闲 tail->number=-1;//改进程号为-1

break;

}

if(strcmp(pretail->state,"0")==0 && strcmp(tail->next->state,"1")==0){//上邻接

pretail->next=tail->next;//插入点的前一分区与回收区合并 pretail->size=tail->size+pretail->size;//分区长度=前一分区长度+回收区长度

free(tail);//删除回收区指针

break;

}

if(strcmp(pretail->state,"1")==0 && strcmp(tail->next->state,"0")==0){//下邻接

if(pretail!=tail){

pretail->next=tail->next;//插入点的后一分区与回收区合并

tail->next->size=tail->next->size+tail->size;//分区长度=后一分区长度+回收区长度

tail->next->startaddress=tail->startaddress;

free(tail);//删除回收区指针

break;

}

else{

p=tail->next;

tail->next->startaddress=0;

tail->next->size+=tail->size;

break;

}

}

if(strcmp(pretail->state,"0")==0 && strcmp(tail->next->state,"0")==0){

//上下均邻接

pretail->next=tail->next->next;//插入点的前后两个分区与回收区合并

pretail->size=pretail->size+tail->size+tail->next->size;//分区长度=三区长度总和

free(tail->next);//删除插入点的后一分区指针

free(tail);//删除回收区指针

break;

}

}

else{//回收区是最后分区

if(strcmp(pretail->state,"1")==0){//插入点的前一分区状态为忙碌 strcpy(tail->state,"0");//回收区状态置为空闲

break;

}

else{

pretail->next=NULL;//合并两个分区

pretail->size=pretail->size+tail->size;//分区长度=前一分区长度+回收区长度

free(tail);//删除回收区指针

break;

}

}

}

pretail=tail;

tail=tail->next;//后移

}

return p;

}

void function(){

int x;

while(1){

printf("**1:分配空间 2:回收空间 3:结束** 请选择: "); scanf("%d",&x);

if(x==3) break;//选择3结束

switch(x){

case 1: //选择1

p=scsf();//调用首次适应算法

printf("\n\n始址\t大小\t状态\t进程号 \n"); while (p != NULL){

show(p);//输出分区信息

p = p->next;//后移

}

break;

case 2://选择2

p=huishou();//调用内存回收 算法

printf("\n\n始址\t大小\t状态\t进程号 \n"); while (p != NULL){

show(p);//输出分区信息

p = p->next;//后移

}

break;

default:

printf("输入错误\n\n");

break;

}

}

}

int main(){

input();

function();

return 0;

}

4.结果及其相关分析（结果必须是图示）