(二)可变分区存储管理方案中的内存分配

Bertha 。 2021-12-22 09:53 286阅读 0赞

可变分区调度算法有:最先适应分配算法,最优适应分配算法,最坏适应算法用户提出内存空间的申请；系统根据申请者的要求，按照一定的分配策略分析内存空间的使用情况，找出能满足请求的空闲区，分给申请者；当程序执行完毕或主动归还内存资源时，系统要收回它所占用的内存空间或它归还的部分内存空间。  
1．程序运行时首先接收输入：空闲区数据文件，包括若干行，每行有两个数据项：起始地址、长度（均为整数），各数据项以逗号隔开。  
2．建立空闲区表并在屏幕上显示输出空闲区表内容，空闲区表中记录了内存中可供分配的空闲区的始址和长度，用标志位指出该分区是否是未分配的空闲区。  
3．从用户界面根据用户提示接收一个内存申请，格式为：作业名、申请空间的大小。  
4．按照最差（最坏）适配算法选择一个空闲区，分割并分配，修改相应的数据结构（空闲区表），填写内存已分配区表（起始地址、长度、标志位），其中标志位的一个作用是指出该区域分配给哪个作业。  
5．重复3、4，直到输入为特殊字符（0）。  
6．在屏幕上显示输出新的空闲区表和已分配区表的内容。  
本程序包括:FIFO,最优适应分配算法,最坏适应算法

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 可变分区存储管理

\#include < stdio.h >   
\#include < iostream.h >   
\#include < string .h >   
\#include < iomanip.h >   
  
 const  int  MAXJOB = 100 ; // 定义表最大记录数    
   
typedef  struct  node\{  
 int  start;  
 int  length;  
 char  tag\[ 20 \];  
\}job;  
  
job frees\[MAXJOB\]; // 定义空闲区表    
 int  free\_quantity;  
  
job occupys\[MAXJOB\]; // 定义已分配区表    
 int  occupy\_quantity;  
  
 // 初始化函数    
 void  initial()  
\{  
 int  i;  
  
 for (i = 0 ;i < MAXJOB;i \++ )\{  
frees\[i\].start =- 1 ;  
frees\[i\].length = 0 ;  
strcpy(frees\[i\].tag, " free " );  
  
occupys\[i\].start =- 1 ;  
occupys\[i\].length = 0 ;  
strcpy(occupys\[i\].tag, "" );  
\}  
free\_quantity = 0 ;  
occupy\_quantity = 0 ;  
\}  
  
 // 读数据函数    
 int  readData()  
\{  
FILE  \* fp;  
 char  fname\[ 20 \];  
  
cout << " 请输入初始空闲表文件名: " ;  
cin >> fname;  
  
 if ((fp = fopen(fname, " r " )) == NULL)\{  
cout << " 错误,文件打不开,请检查文件名 " << endl;  
\}  
 else \{  
 while ( ! feof(fp))\{  
fscanf(fp, " %d,%d " , & frees\[free\_quantity\].start, & frees\[free\_quantity\].length);  
free\_quantity \++ ;  
\}  
 return  1 ;  
\}  
 return  0 ;  
\}  
  
 // sort    
 void  sort()  
\{  
 int  i,j,p;  
  
 for (i = 0 ;i < free\_quantity \- 1 ;i \++ )\{  
p = i;  
 for (j = i \+ 1 ;j < free\_quantity;j \++ )\{  
 if (frees\[j\].start < frees\[p\].start)\{  
p = j;  
\}  
\}  
 if (p != i)\{  
frees\[free\_quantity\] = frees\[i\];  
frees\[i\] = frees\[p\];  
frees\[p\] = frees\[free\_quantity\];  
\}  
\}  
\}  
  
  
 // 显示函数    
 void  view()  
\{  
 int  i;  
  
cout << endl << " \---------------------------------------------------------- " << endl;  
cout << " 当前空闲表: " << endl;  
cout << " 起始地址 长度 状态 " << endl;  
 for (i = 0 ;i < free\_quantity;i \++ )\{  
cout.setf( 2 );  
cout.width( 12 );  
cout << frees\[i\].start;  
cout.width( 10 );  
cout << frees\[i\].length;  
cout.width( 8 );  
cout << frees\[i\].tag << endl;  
\}  
  
cout << endl << " \---------------------------------------------------------- " << endl;  
cout << " 当前已分配表: " << endl;  
cout << " 起始地址 长度 占用作业名 " << endl;  
 for (i = 0 ;i < occupy\_quantity;i \++ )\{  
cout.setf( 2 );  
cout.width( 12 );  
cout << occupys\[i\].start;  
cout.width( 10 );  
cout << occupys\[i\].length;  
cout.width( 8 );  
cout << occupys\[i\].tag << endl;  
\}  
\}  
  
 // 最先适应分配算法    
 void  earliest()  
\{  
 char  job\_name\[ 20 \];  
 int  job\_length;  
 int  i,j,flag,t;  
  
cout << " 请输入新申请内存空间的作业名和空间大小: " ;  
cin >> job\_name;  
cin >> job\_length;  
  
flag = 0 ;  
 for (i = 0 ;i < free\_quantity;i \++ )\{  
 if (frees\[i\].length >= job\_length)\{  
flag = 1 ;  
\}  
\}  
 if (flag == 0 )\{  
cout << endl << " Sorry,当前没有能满足你申请长度的空闲内存,请稍候再试 " << endl;  
\}  
 else \{  
t = 0 ;  
i = 0 ;  
 while (t == 0 )\{  
 if (frees\[i\].length >= job\_length)\{  
t = 1 ;  
\}  
i \++ ;  
\}  
i \-- ;  
occupys\[occupy\_quantity\].start = frees\[i\].start;  
strcpy(occupys\[occupy\_quantity\].tag,job\_name);  
occupys\[occupy\_quantity\].length = job\_length;  
occupy\_quantity \++ ;  
  
 if (frees\[i\].length > job\_length)\{  
frees\[i\].start \+= job\_length;  
frees\[i\].length \-= job\_length;  
\}  
 else \{  
 for (j = i;j < free\_quantity \- 1 ;j \++ )\{  
frees\[j\] = frees\[j \+ 1 \];  
\}  
free\_quantity \-- ;  
cout << " 内存空间成功:\} " << endl;  
\}  
\}  
\}  
 // 最优适应分配算法    
 void  excellent()  
\{  
 char  job\_name\[ 20 \];  
 int  job\_length;  
 int  i,j,flag,t;  
  
cout << " 请输入新申请内存空间的作业名和空间大小: " ;  
cin >> job\_name;  
cin >> job\_length;  
  
flag = 0 ;  
 for (i = 0 ;i < free\_quantity;i \++ )\{  
 if (frees\[i\].length >= job\_length)\{  
flag = 1 ;  
\}  
\}  
 if (flag == 0 )\{  
cout << endl << " Sorry,当前没有能满足你申请长度的空闲内存,请稍候再试 " << endl;  
\}  
 else \{  
t = 0 ;  
i = 0 ;  
 while (t == 0 )\{  
 if (frees\[i\].length >= job\_length)\{  
t = 1 ;  
\}  
i \++ ;  
\}  
i \-- ;  
 for (j = 0 ;j < free\_quantity;j \++ )\{  
 if ((frees\[j\].length >= job\_length) && (frees\[j\].length < frees\[i\].length))\{  
i = j;  
\}  
\}  
  
occupys\[occupy\_quantity\].start = frees\[i\].start;  
strcpy(occupys\[occupy\_quantity\].tag,job\_name);  
occupys\[occupy\_quantity\].length = job\_length;  
occupy\_quantity \++ ;  
  
 if (frees\[i\].length > job\_length)\{  
frees\[i\].start \+= job\_length;  
frees\[i\].length \-= job\_length;  
\}  
 else \{  
 for (j = i;j < free\_quantity \- 1 ;j \++ )\{  
frees\[j\] = frees\[j \+ 1 \];  
\}  
free\_quantity \-- ;  
cout << " 内存空间成功:) " << endl;  
\}  
\}  
\}  
  
 // 最坏适应算法    
 void  worst()  
\{  
 char  job\_name\[ 20 \];  
 int  job\_length;  
 int  i,j,flag,t;  
  
cout << " 请输入新申请内存空间的作业名和空间大小: " ;  
cin >> job\_name;  
cin >> job\_length;  
  
flag = 0 ;  
 for (i = 0 ;i < free\_quantity;i \++ )\{  
 if (frees\[i\].length >= job\_length)\{  
flag = 1 ;  
\}  
\}  
 if (flag == 0 )\{  
cout << endl << " Sorry,当前没有能满足你申请长度的空闲内存,请稍候再试 " << endl;  
\}  
 else \{  
t = 0 ;  
i = 0 ;  
 while (t == 0 )\{  
 if (frees\[i\].length >= job\_length)\{  
t = 1 ;  
\}  
i \++ ;  
\}  
i \-- ;  
 for (j = 0 ;j < free\_quantity;j \++ )\{  
 if ((frees\[j\].length >= job\_length) && (frees\[j\].length > frees\[i\].length))\{  
i = j;  
\}  
\}  
  
occupys\[occupy\_quantity\].start = frees\[i\].start;  
strcpy(occupys\[occupy\_quantity\].tag,job\_name);  
occupys\[occupy\_quantity\].length = job\_length;  
occupy\_quantity \++ ;  
  
 if (frees\[i\].length > job\_length)\{  
frees\[i\].start \+= job\_length;  
frees\[i\].length \-= job\_length;  
\}  
 else \{  
 for (j = i;j < free\_quantity \- 1 ;j \++ )\{  
frees\[j\] = frees\[j \+ 1 \];  
\}  
free\_quantity \-- ;  
cout << " 内存空间成功:) " << endl;  
\}  
\}  
\}  
  
 // 撤消作业    
 void  finished()  
\{  
 char  job\_name\[ 20 \];  
 int  i,j,flag,p = 0 ;  
 int  start;  
 int  length;  
  
cout << " 请输入要撤消的作业名: " ;  
cin >> job\_name;  
  
flag =- 1 ;  
 for (i = 0 ;i < occupy\_quantity;i \++ )\{  
 if ( ! strcmp(occupys\[i\].tag,job\_name))\{  
flag = i;  
start = occupys\[i\].start;  
length = occupys\[i\].length;  
\}  
\}  
 if (flag ==- 1 )\{  
cout << " 没有这个作业名 " << endl;  
\}  
 else \{  
 // 加入空闲表    
 for (i = 0 ;i < free\_quantity;i \++ )\{  
 if ((frees\[i\].start \+ frees\[i\].length) == start)\{  
 if (((i \+ 1 ) < free\_quantity) && (frees\[i \+ 1 \].start == start \+ length))\{  
frees\[i\].length = frees\[i\].length \+ frees\[i \+ 1 \].length \+ length;  
 for (j = i \+ 1 ;j < free\_quantity;j \++ )\{  
frees\[j\] = frees\[j \+ 1 \];  
\}  
free\_quantity \-- ;  
p = 1 ;  
\}  
 else \{  
frees\[i\].length \+= length;  
p = 1 ;  
\}  
\}  
 if (frees\[i\].start == (start \+ length))\{  
frees\[i\].start = start;  
frees\[i\].length \+= length;  
p = 1 ;  
\}  
\}  
  
 if (p == 0 )\{  
frees\[free\_quantity\].start = start;  
frees\[free\_quantity\].length = length;  
free\_quantity \++ ;  
\}  
  
  
  
 // 删除分配表中的该作业    
   
 for (i = flag;i < occupy\_quantity;i \++ )\{  
occupys\[i\] = occupys\[i \+ 1 \];  
\}  
occupy\_quantity \-- ;  
\}  
\}  
  
  
 // 显示版权信息函数    
 void  version()  
\{  
cout << endl << endl;  
  
cout << "  ┏━━━━━━━━━━━━━━━━━━━━━━━┓ " << endl;  
cout << "  ┃　　　 　可变分区存储管理模拟系统　 　　　　 ┃ " << endl;  
cout << "  ┠───────────────────────┨ " << endl;  
cout << "  ┃　 　(c)All Right Reserved Neo　　　 　　　┃ " << endl;  
cout << "  ┃　　　　　　sony006@163.com　　 　　　　　　　┃ " << endl;  
cout << "  ┃　　　　　version 2004 build 1122　　　　　　┃ " << endl;  
cout << "  ┗━━━━━━━━━━━━━━━━━━━━━━━┛ " << endl;  
cout << endl << endl;  
\}  
  
  
 void  main()  
\{  
  
 int  flag = 0 ;  
 int  t = 1 ;  
 int  chioce = 0 ;  
  
version();  
initial();  
  
flag = readData();  
  
 while (flag == 1 )\{  
  
sort();  
cout << endl << endl << " ========================================================= " << endl;  
cout << "  可变分区存储管理模拟系统 " << endl;  
cout << " ========================================================= " << endl;  
cout << "  1.申请空间 2.撤消作业 3.显示空闲表和分配表 0.退出 " << endl;  
cout << " 请选择: " ;  
cin >> chioce;  
  
 switch (chioce)\{  
 case  1 :  
 // 换算法请换下一句调用    
 earliest();  
 break ;  
 case  2 :  
finished();  
 break ;  
 case  3 :  
view();  
 break ;  
 case  0 :  
flag = 0 ;  
 break ;  
 default :  
cout << " 选择错误! " << endl;  
\}  
\}  
\}

转载于:https://www.cnblogs.com/FCWORLD/archive/2010/12/04/1896345.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/3ab6dd9fe9ac4a78bc39a0d11ed7d977.png