一、实验内容
主存储器空间的分配和回收。
二、实验目的
一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现虽与主存储器的管理方式有关的，通过本实验帮助学生理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。
三、实验题目
模拟在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收。
[提示]：
(1) 分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时可把作业的信息按页分散存放在主存的空闲块中，为了说明主存中哪些块已经被占用，哪些块是尚未分配的空闲块，可用一张位示图来指出。位示图可由若干存储单元来构成，其中每一位与一个物理块对应，用0/1表示对应块为空闲/已占用。
(2) 假设某系统的主存被分成大小相等的64块，则位示图可用8个字节来构成，另用一单元记录当前空闲块数。如果已有第0，1，4，5，6，9，11，13，24，31，共10个主存块被占用了，那么位示图情况如下：
字 位 节 数 号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
(3) 当要装入一个作业时，根据作业对主存的需要量，先查当前空闲块数是否能满足作业要求，若不能满足则输出分配不成功。若能满足，则查位示图，找出为“0”的一些位，置上占用标志“1”，从“当前空闲块数”中减去本次占用块数。
按找到的计算出对应的块号，其计算公式为：
块号= j´8+i
其中，j表示找到的是第n个字节，I表示对应的是第n位。
根据分配给作业的块号，为作业建立一张页表，页表格式：
页 号 | 块 号 |
0 | |
1 | |
2 | |
M M |
(4) 当一个作业执行结束，归还主存时，根据该作业的页表可以知道应归还的块号，由块号可计算出在位示图中的对应位置，把对应位的占用标志清成“0”，表示对应的块已成为空闲块。归还的块数加入到当前空闲块数中。由块号计算在位示图中的位置的公式如下：
字节号 j=[块号/8] （[ ]表示取整）
位数 i={块号/8} （{ }表示取余）
(5) 设计实现主存分配和回收的程序。假定位示图的初始状态如（2）所述，现有一信息量为5页的作业要装入，运行你所设计的分配程序，为作业分配主存且建立页表（格式如（3）所述）。然后假定有另一作业执行结束，它占用的块号为第4，5，6和31块，运行你所设计的回收程序，收回作业归还的主存块。
要求能显示和打印分配或回收前后的位示图和当前空闲块数，对完成一次分配后还要显示或打印为作业建立的页表。
四、实验报告
(1) 实验题目。
(2) 程序中使用的数据结构及符号说明。
(3) 流程图。
(4) 打印一份源程序并附上注释。
(5) 打印程序运行时的初值和运行结果，要求如下：
打印位示图和当前空闲块数的初值；要求装入的作业对主存的申请量，为作业分配后的位示图、当前空闲块数和页表；作业归还的块号、回收作业所占主存后的位示图和当前空闲块数。
#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]=i*8+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,q,p,j; //p表示数组长度 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;i<node2->data.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; }