操作系统-在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收。

实验六
一、实验题目
在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收。
二、实验内容
(1) 分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时可把作业的信息按页分散存放在主存的空闲块中，为了说明主存中哪些块已经被占用，哪些块是尚未分配的空闲块，可用一张位示图来指出。位示图可由若干存储单元来构成，其中每一位与一个物理块对应，用0/1表示对应块为空闲/已占用。
(2) 假设某系统的主存被分成大小相等的64块，则位示图可用8个字节来构成，另用一单元记录当前空闲块数。如果已有第0，1，4，5，6，9，11，13，24，31，共10个主存块被占用了，那么位示图情况如下：


图4-1 最先适应分配模拟算法

图4-2 主存回收算法
(3) 当要装入一个作业时，根据作业对主存的需要量，先查当前空闲块数是否能满足作业要求，若不能满足则输出分配不成功。若能满足，则查位示图，找出为“0”的一些位，置上占用标志“1”，从“当前空闲块数”中减去本次占用块数。
按找到的计算出对应的块号，其计算公式为： 块号= j8+i
其中，j表示找到的是第n个字节，I表示对应的是第n位。
根据分配给作业的块号，为作业建立一张页表，页表格式：

(4) 当一个作业执行结束，归还主存时，根据该作业的页表可以知道应归还的块号，由块号可计算出在位示图中的对应位置，把对应位的占用标志清成“0”，表示对应的块已成为空闲块。归还的块数加入到当前空闲块数中。由块号计算在位示图中的位置的公式如下：
字节号 j=[块号/8] （[ ]表示取整）
位数 i={块号/8} （{ }表示取余）
(5) 设计实现主存分配和回收的程序。假定位示图的初始状态如（2）所述，现有一信息量为5页的作业要装入，运行你所设计的分配程序，为作业分配主存且建立页表（格式如（3）所述）。然后假定有另一作业执行结束，它占用的块号为第4，5，6和31块，运行你所设计的回收程序，收回作业归还的主存块。
要求能显示和打印分配或回收前后的位示图和当前空闲块数，对完成一次分配后还要显示或打印为作业建立的页表。
三、实验过程
1、实验原理
（1）假定系统的主存被分成大小相等的64个块，用0/1对应空闲/占用。
（2）当要装入一个作业时，根据作业对主存的需求量，先查空闲块数是否能满足作业要求，若能满足，则查位示图，修改位示图和空闲块数。位置与块号的对应关系为：
块号=j*8+i，其中i表示位，j表示字节。
根据分配的块号建立页表。页表包括两项：页号和块号。
（3）回收时，修改位示图和空闲块数。
2、数据结构
struct bitGraph
{
int a[8][8];//位示图
int freebit;//空闲块数
}BG;
//进程的数据结构
struct proc
{
char name[10];//进程名
int *PT;//页表
int size;//进程所需要的空间
struct proc *next;
struct proc *front;
};
3、算法设计
void Initial()
{
int i,j;
table=(int **)malloc(sizeof(int)*8);//使用指针动态建立一个位视图的数组
for(i=0;i<8;i++)
{
table[i]=(int *)malloc(sizeof(int)8);
}
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
table[i][j]=0;
}
}
table[0][0]=1,table[0][1]=1,table[0][4]=1,table[0][5]=1,table[0][6]=1;
table[1][1]=1,table[1][3]=1,table[1][5]=1,table[3][0]=1,table[3][7]=1;
}
四、实验结果




五、体会与收获
这次实验我使用了一个二维数组作为位示图的数据结构，这样简单明了。而进程页表使用一个一维数组，用数组下标即可表示页号，节省了存储空间。通过本实验，我进一步加深了对使用位示图方式表示和实现主存分配回收的理解，同时也得到了将系统理论实践的机会，熟练了编程能力。
六、源代码
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include"stdlib.h"
struct work
{
int size;
char name[10];
int a[64];
};
typedef struct node
{
struct work data;
struct node next;
}Node;
int **table;
int v=0;
int kuaihao[10][64];
void menu()
{
printf(“1.打印位视图\n”);
printf(“2.添加作业\n”);
printf(“3.结束作业\n”);
printf(“4.显示所有作业\n”);
printf(“5.退出\n”);
}
void Initial()
{
int i,j;
table=(int **)malloc(sizeof(int)*8);//使用指针动态建立一个位视图的数组
for(i=0;i<8;i++)
{
table[i]=(int *)malloc(sizeof(int)*8);
}
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
table[i][j]=0;
}
}
table[0][0]=1,table[0][1]=1,table[0][4]=1,table[0][5]=1,table[0][6]=1;
table[1][1]=1,table[1][3]=1,table[1][5]=1,table[3][0]=1,table[3][7]=1;
}
int kongxiankuai()
{
int k;
int i,j;
k=0;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(table[i][j]==0)
{
k++;
}
}
}
return k;
}
int InialWork(Node *h)
{
Node *p,*w;
p=(Node *)malloc(sizeof(Node));
p->data.size=4;
strcpy(p->data.name,“p1”);
p->data.a[0]=4;
p->data.a[1]=5;
p->data.a[2]=6;
p->data.a[3]=31;
w=(Node *)malloc(sizeof(Node));
w->data.size=6;
strcpy(w->data.name,“p2”);
w->data.a[0]=0;
w->data.a[1]=1;
w->data.a[2]=9;
w->data.a[3]=11;
w->data.a[4]=13;
w->data.a[5]=24;
p->next=w;
w->next=NULL;
h->next=p;
return 0;
}
int AddWork(Node *h)
{
int g=0,i,j,w;
Node *p;
Node *q;
q=h;
while(h->next!=NULL)
{
h=h->next;
}
p=(Node )malloc(sizeof(Node)); //分配空间
printf(“请输入进程的所需块数”);
scanf("%d",&p->data.size);
if(p->data.size>kongxiankuai())
{
printf(“内存不足。\n”);
return 0;
}
w=p->data.size;
while(w!=0)
{
printf(“请输入作业名：\n”);
scanf("%10s",p->data.name);
while(q!=NULL)
{
if(strcmp(q->data.name,p->data.name)==0)
{
printf(“该作业存在，重新输入。\n\n”);
return 0;
}
q=q->next;
}
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(table[i][j]==0&&w!=0)//作业分配存储
{
table[i][j]=1;
p->data.a[g]=i8+j; //保存作业块号
g++;
w=w-1;
}
}
}

}
printf("作业添加成功\n\n");
h->next=p;
p->next=NULL;
return 0;

}

void PrintWork(Node *h)//打印页表
{
Node *p;
int i;
printf(“打印作业表\n”);
p=h->next;
while(p!=NULL)
{
printf(“作业名:”);
printf("%s\n",p->data.name);

    for(i=0;i<p->data.size;i++)
    {
        printf("页号:%-3d 块号:%-3d\n",i,p->data.a[i]);
    }
    p=p->next;
}
printf("\n");

}

void PrintPicture()//打印位示图
{
int i,j;
printf(“打印位示图\n”);
printf(" “);
for(i=0;i<8;i++)
{
printf(”%3d",i);
}
printf("\n");
for(i=0;i<8;i++)
{
printf("%3d",i);
for(j=0;j<8;j++)
{
printf("%3d",table[i][j]);
}
printf("\n");
}
printf(“剩余空闲块:%d”,kongxiankuai());
printf("\n");
printf("\n");
}
int EndingWork(Node *h) //按照需要释放内存
{
int i,m,n;
Node *node1 = h;
Node *node2 = NULL;
char name[10];
printf(“请输入归还的作业名：”);
scanf("%10s",name);
if(h->next== NULL)
{
printf(“作业表为空\n\n”);
return 0;
}
else
{
while(node1->next!= NULL)
{
node2 = node1;
node2 = node1 -> next;
if(strcmp(node2->data.name,name)==0)
{
node1 -> next = node2 -> next;
for(i=0;idata.size;i++)
{
printf(“回收的块号:%d\n”,node2->data.a[i]);
m = node2->data.a[i]/8;
n = node2->data.a[i]%8;
table[m][n]=0;
}
printf("\n");
free(node2);
return 0;
}
node1 = node1 -> next;
}
printf(“没有该作业\n\n”);
return 0;
}
}

int main()
{
int q;
Node *h;
h=(Node *)malloc(sizeof(Node));
h->next=NULL;
Initial();
InialWork(h);
while(1)
{
menu();
printf(“请输入选择：\n”);
scanf("%d",&q);
switch(q)
{
case 1:
PrintPicture();
break;
case 2:
AddWork(h);
break;
case 3:
EndingWork(h);
break;
case 4:
PrintWork(h);
break;
case 5:
exit(0);
break;
}
}
return 0;
}