分配与回收

// 文件名: osmd.cpp// 作者: 宋梦国// 功能描述: 操作系统内存分区分配算法演示// 开发日志: Creat on 02-06-29 15:24// Modefy on 02-07-24 19:39// Modefy on 05-02-10 实现在DEV-C++下编译;bf算法有bug! // Modefy on 06-11-10 1.修正bf算法bug// 2.增加测试数据// 3.拟增加从文件输入测试数据功能// 测用数据:// 1.测试最佳适应算法// 作业 begint keept size// A 0 4 200// B 1 6 300// C 4 1 70// D 5 4 250// 2.测试适应算法// 作业 begint keept size// A 0 4 100// B 1 6 100// C 2 2 150// D 3 5 120// E 3 2 40// F 4 2 40// G 5 3 30// H 5 2 30///////////////////////////////////////////////////using namespace std;// HDR FIELS //////////////////////////////////////#include <iostream>#include <stdlib.h>#include <stdio.h>#include <conio.h>#include <windows.h>// CONST //////////////////////////////////////////#define MMAX 600// TYPE ///////////////////////////////////////////typedef struct jobstr //作业信息{ int begint;//作业开始时间int keept;//作业持续时间int endt;//作业结束时间int size;//作业申请空间大小}jobstr;typedef struct lnode //内存映像链表结点{ int h; //内存块起始地址int t; //内存块结束地址int tag;//内存块标记struct lnode *next;//下一结点地址}lnode;// GLOBAL /////////////////////////////////////////int st=-1;//当前时间int latest=-1;//最近的int latestime=latest;int latestid=-1;jobstr job[30]; //作业信息映像int jobcount;//作业个数lnode *ml=NULL,*bfp=NULL,*rffp=NULL;//内存映象链表头指针,// 屏幕输出定位 /////////////////////////////////////////void gotoxy(int x, int y)// DEV-C++库函数无该函数{COORD c;c.X = x - 1;c.Y = y - 1;SetConsoleCursorPosition (GetStdHandle(STD_OUTPUT_HANDLE), c);}// 屏幕输出着色 /////////////////////////////////////////void textcolor (int color)// DEV-C++库函数无该函数{SetConsoleTextAttribute (GetStdHandle (STD_OUTPUT_HANDLE), color ); }// 整数输入(只接受数字) /////////////////////////////////////////int inputnum(int x, int y){char w=' ';int flag=0,p=0;do{cout << " ";gotoxy(x,y); w=cin.get(); //从屏幕坐标为(x,y)位置输入字符if('\n' != w ){if(1==flag) continue;else if(w <'0' || w > '9')flag=1;else{p=p*10+int(w)-48;continue;}}else{ if(1==flag) {flag=0;p=0;continue;}else break;}}while(1);return (p);}// 作业信息输入 /////////////////////////////////////////void inputjob(){int i,k;jobcount=0;//重新输入一批作业时,作业总数清零system("CLS");textcolor(12);while(0 == jobcount ||15 < jobcount)//输入0到15之间的整数{gotoxy(3,3);cout << "请输入作业个数(15>=jobcount>0): ";jobcount = inputnum(34,3);//cin.get();}for(i=0;i<jobcount;i++){system("CLS");gotoxy(5,4);textcolor(10);cout <<"输入第"<<i+1<<"个作业"<<char(i+65)<<"的相关信息:";textcolor(15);job[15+i].begint=-1;while(0 > job[15+i].begint ||15 < job[15+i].begint){gotoxy(7,5);cout <<char(i+65) <<"作业开始时间(25>=t>0): "; job[15+i].begint = inputnum(32,5);//cin.get();}job[15+i].keept=-1;while(0 > job[15+i].keept ||15 < job[15+i].keept){gotoxy(7,6);cout <<char(i+65) <<"作业持续时间(25>=t>0): ";job[15+i].keept = inputnum(32,6);//cin.get();}job[15+i].size=-1;while(0 > job[15+i].size ||600 < job[15+i].size){gotoxy(7,7);cout <<char(i+65) <<"作业申请内存空间大小(600>size>0): ";job[15+i].size = inputnum(42,7);//cin.get();}job[15+i].endt=job[15+i].begint+job[15+i].keept;if(latest<job[15+i].endt){//cout<< job[15+i]latest=job[15+i].endt;latestime=latest;/////////////////////////////latestid=i;}job[i].begint=job[15+i].begint;job[i].keept=job[15+i].keept;job[i].size=job[15+i].size;job[i].endt=job[15+i].endt;}}// 作业信息输出 //////////////////////////////////////void outputjob(){int i;for(i=0;i<jobcount;i++){textcolor(i+1==8 ? 14:i+1);gotoxy(1,i+6);printf(" %c%5d%5d%5d\n",i+65,job[i].begint,job[i].endt,job[i].size);}textcolor(15);}// 屏幕输出格式 /////////////////////////////////////////void fm(){int i;system("CLS");;textcolor(15);gotoxy(21,1);cout <<"内存动态分区分配方法演示";gotoxy(1,2);for(i=1;i<=80;i++)cout <<"=";gotoxy(1,3);cout <<" JOB INFO PARTITION TABLE MEMORY STATE"; gotoxy(1,4);cout <<" ID START END SIZE HEAD TAIL TAG";gotoxy(1,5);for(i=1;i<=80;i++)cout <<"-";for(i=3;i<=20;i++){gotoxy(20,i);cout <<"|";gotoxy(38,i);cout <<"|";}gotoxy(1,i);for(i=1;i<=80;i++)cout <<"=";}// 内存映像链表初始化 /////////////////////////////////////////void initml(){ml=new lnode;ml->next=NULL;ml->h=1;//内存块起始地址ml->t=MMAX;//内存块结束地址ml->tag='*';//内存块标记}// 内存不足处理 /////////////////////////////////////////void mnoenough(int i){int j;job[i].begint++;job[i].endt++;if(i==latestid)latest++;for(j=0;j<jobcount;j++){if(latest<=job[i].endt){latest=job[i].endt;latestid=i;}}gotoxy(1,24);textcolor(12);cout <<"内存不足!!!作业";gotoxy(16+i,24);textcolor(12);cout<<char(i+65)<<"被迫延迟1秒响应!!!";textcolor(15); }#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 a){occupys[0].start=20;occupys[0].length=32;strcpy(occupys[0].tag,"A");occupys[1].start=52;occupys[1].length=20;strcpy(occupys[1].tag,"B");occupys[2].start=98;occupys[2].length=40;strcpy(occupys[2].tag,"C");occupys[3].start=148;occupys[3].length=22;strcpy(occupys[3].tag,"D");if(a==1){frees[0].start=72;frees[0].length=26; strcpy(frees[0].tag,"free"); frees[1].start=138;frees[1].length=10; strcpy(frees[1].tag,"free"); frees[2].start=170;frees[2].length=86; strcpy(frees[2].tag,"free"); free_quantity=3;occupy_quantity=4;}if(a==2){frees[0].start=138;frees[0].length=10; strcpy(frees[0].tag,"free"); frees[1].start=72;frees[1].length=20; strcpy(frees[1].tag,"free"); frees[2].start=170;frees[2].length=86; strcpy(frees[2].tag,"free"); free_quantity=3;occupy_quantity=4;}if(a==3){frees[0].start=170;frees[0].length=86; strcpy(frees[0].tag,"free"); frees[1].start=72;frees[1].length=26; strcpy(frees[1].tag,"free"); frees[2].start=138;frees[2].length=10; strcpy(frees[2].tag,"free"); free_quantity=3;occupy_quantity=4;}}//显示函数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 main(){int t=1;int chioce=0;int flag=1;int a;state:cout<<"1.最先适应算法，2.最优适应算法3.最差适应算法"; cin>>a;initial(a);while(flag==1){cout<<endl<<endl<<"================================= ========================"<<endl;cout<<" 可变分区存储管理模拟系统"<<endl;cout<<"=========================================== =============="<<endl;cout<<" 1.申请空间2.撤消作业3.显示空闲表和分配表0.退出"<<endl;cout<<"请选择:";cin>>chioce;switch(chioce){case 1:switch(a){case 1: earliest(); break;case 2: excellent();break;case 3: worst();break;}break;case 2:finished();break;case 3:view();break;case 0:goto state;break;default:cout<<"选择错误!"<<endl;}}}。