操作系统实验常见算法实现集合
操作系统实验算法实现集合
（以下代码均在C-Free5 mingw5环境下编译通过）磁盘移臂调度
#include "iostream.h"
#include "math.h"
voidfcfs(int f[],int);
voidsstf(int m[],int);
voidcscan(int d[],int);
voideleattemper(int e[],int,int);
int main()
{ cout<<"模拟磁盘移臂调度程序"< cout<<"***********************************************"< constintbefor=128; constint now=143; int a[]={86,145,93,179,95,150,103,176,132}; fcfs(a,now); intaa[]={86,145,93,179,95,150,103,176,132}; sstf(aa,now); intaaa[]={86,145,93,179,95,150,103,176,132}; cscan(aaa,now); intaaaa[]={86,145,93,179,95,150,103,176,132}; eleattemper(aaaa,now,befor); return 0; } voidfcfs(int f[],intbnow) { cout<<"先来先服务调度算法(fcfs):"< int s=bnow-f[0]; double t=fabs(s); for(int i=0;i<8;i++) { t=t+fabs(f[i]-f[i+1]);} cout<<"移动顺序:"; for(int i=0;i<9;i++) {cout< cout< cout<<"取臂移动总量:"< } voidsstf(int m[],intmnow) { cout<<"最短查找时间优先算法(sstf):"< int mm[9]; int tm=mnow; for(int i=0;i<=8;i++) { double temp=fabs(tm-9999); for(int j=0;j<=8;j++) { te=fabs(tm-m[j]); if (temp>te&&te!=0) {temp=te; c=m[j]; y=j; } } tm=c; mm[i]=c; m[y]=9999999; } s=mnow-mm[0]; double t=fabs(s); for(int i=0;i<8;i++) { t=t+fabs(mm[i]-mm[i+1]);} cout<<"移动顺序:"; for(int i=0;i<9;i++) {cout< cout< cout<<"取臂移动总量:"< cout< } voidcscan(int d[],intdnow) { cout<<"循环扫描法(cscan):"< int t, big; for(int i=0;i<8;i++) { for(int j=0;j<8-i;j++) { if (d[j]>d[j+1]) {t=d[j];d[j]=d[j+1];d[j+1]=t;} } } big = d[8]; for(int z=8;z>=0;z--) {if (d[z]>dnow) { m=z; l++;} } int mm=0; int q; q = 5; if(q > l) {for(int k=m;k<9;k++) { int i=d[k];d[k]=d[mm];d[mm]=i;mm=mm+1;} mm=m-1; for(int k = 8;k > m-1;k--) { int i=d[k];d[k]=d[mm];d[mm]=i;} } double e=fabs(dnow-d[0]); int flag=0; for(int i=0;i<8;i++) {if(d[i] == big) {e += fabs(199 - d[i]); flag = 1; } else if(flag == 1) {e += fabs(0 - d[i]); i--; flag = 0; } else {e=e+fabs(d[i]-d[i+1]); } } cout<<"移动顺序:"; for(int i=0;i<9;i++) {cout< cout< cout<<"取臂移动总量:"< cout< } voideleattemper(int e[],intenow,intebefor) { cout<<"电梯调度算法:"< int t; for(int i=0;i<7;i++) for(int j=0;j<8-i;j++) { if (e[j]>e[j+1]) { t=e[j]; e[j]=e[j+1]; e[j+1]=t; } } } int x; double temp=fabs(enow-e[0]); for(int j=0;j<=8;j++) { double f=fabs(enow-e[j]); if (temp>f) { temp=f; x=j; } } cout<<"移动顺序:"; if (ebefor>enow) { double s=fabs(enow-e[x-1]); for(int i=x-1;i>=0;i--) { cout< if (i!=x&&i!=0){s=s+fabs(e[i]-e[i-1]);} } s=s+fabs(e[0]-e[x]); for(int i=x;i<=8;i++) { cout< if (i!=8){s=s+fabs(e[i]-e[i+1]);} } cout< cout<<"取臂移动总量:"< } else { doubless=fabs(enow-e[x]); for(int i=x;i<=8;i++) { cout< if (i!=x&&i!=8){ ss=ss+fabs(e[i]-e[i+1]);} } ss=ss+5+fabs(e[8]-e[x-1]); for(int i=x-1;i>=0;i--) { cout< if (i!=0) {ss=ss+fabs(e[i]-e[i-1]);} } cout< cout<<"取臂移动总量:"< } } 运行结果： 处理机调度（进程调度）： #include #include #define N 20 typedefstructpcb { char pname[N]; /*进程名*/ int priority; /*进程优先级，用整数表示，值越小，优先级越高*/ intarrivetime; /*进程到达时间*/ int runtime; /*运行进程所需时间*/ char state; /*进程状态*/ structpcb *next; /*链表指针*/ }PCB; static char R = 'r' , E = 'e' , B = 'b' , F = 'f'; /*进程状态：就绪、执行、阻塞、完成*/ PCB ready_head; /*就绪进程队列*/ PCB execute_head; /*执行进程队列*/ PCB block_head; /*阻塞进程队列*/ PCB finish_head; /*完成进程队列*/ intcurrenttime; /*记录系统当前时间*/ void createProcess(); /*建立进程队列，所有进程初始状态为就绪态*/ void showProcess(); /*显示所有队列中的进程情况*/ intisProcessReady(); /*就绪队列中的进程进入执行队列*/ void executeProcess1(); /*按先来先服务调度算法执行进程*/ int runProcess1(); /*运行执行队列中的进程*/ void executeProcess2(); /*按优先级调度算法执行进程*/ int runProcess2(); /*运行执行队列中的进程*/ void executeProcess3(); /*按时间片轮转调度算法执行进程*/ int runProcess3(); /*运行执行队列中的进程*/ void sortByArrivetime(); /*将就绪队列中的进程按到达时间排序*/ void sortByPriority(); /*将就绪队列中的进程按优先级排序*/ /*建立进程队列，所有进程初始状态为就绪态*/ voidcreateProcess() { PCB *p = &ready_head; intnum; /*进程数*/ printf("请输入需要运行的进程数："); scanf("%d",&num); for(int i = 0;i { printf("\n"); p->next = new PCB; p = p->next; printf("No.%3d process input pname: ",i + 1); scanf("%s",p->pname); printf(" priority: "); scanf("%d",&p->priority); printf(" arrivetime: "); scanf("%d",&p->arrivetime); printf(" runtime: "); scanf("%d",&p->runtime); p->state = R; } p->next = NULL; } /*显示所有队列中的进程情况*/ voidshowProcess() { PCB *p; p = &ready_head; p = p->next; printf("\n就绪队列中的进程：\n"); while(p != NULL) { printf("pname:%s\t\tpriority:%d\tarrivetime:%d\truntime:%d\tState:%c\n",p->pname, p->priority,p->arrivetime,p->runtime,p->state); p = p->next; } p = &execute_head; p = p->next; printf("\n执行队列中的进程：\n"); while(p != NULL) { printf("pname:%s\t\tpriority:%d\tarrivetime:%d\truntime:%d\tState:%c\n",p->pname, p->priority,p->arrivetime,p->runtime,p->state); p = p->next; } p = &block_head; p = p->next; printf("\n阻塞队列中的进程：\n"); while(p != NULL) { printf("pname:%s\t\tpriority:%d\tarrivetime:%d\truntime:%d\tState:%c\n",p->pname, p->priority,p->arrivetime,p->runtime,p->state); p = p->next; } p = &finish_head; p = p->next; printf("\n完成队列中的进程：\n"); while(p != NULL) { printf("pname:%s\t\tpriority:%d\tarrivetime:%d\truntime:%d\tState:%c\n",p->pname, p->priority,p->arrivetime,p->runtime,p->state); p = p->next; } } /*就绪队列中的进程进入执行队列*/ intisProcessReady() { if(ready_head.next == NULL) { if(execute_head.next == NULL) return 0; else return 1; } PCB *p1 , *p2 , *p3; p3 = &execute_head; while(p3->next != NULL) { p3 = p3->next; } p2 = &ready_head; p1 = p2->next; while(p1 != NULL) { if((p1->arrivetime<= currenttime)&&(p1->state == R)) { printf("Time slice is %2d ; Process %s start.\n",currenttime,p1->pname); p1->state = E; p2->next = p1->next; p1->next = p3->next; p3->next = p1; p3 = p3->next; p1 = p2; } p2 = p1; p1 = p2->next; } return 1; } /*按先来先服务调度算法执行进程*/ void executeProcess1() { sortByArrivetime(); while(1) { if(isProcessReady() == 0) return; else runProcess1(); } } /*运行执行队列中的进程*/ int runProcess1() { PCB *p1 , *p2 , *p3; if(execute_head.next == NULL) { currenttime ++; return 1; } else { p2 = &execute_head; p1 = p2->next; p3 = &finish_head; while(p3->next != NULL) { p3 = p3->next; } while(p1 != NULL) { while( p1->runtime > 0) { p1->runtime --; currenttime ++; } if(p1->runtime == 0) { printf("Time slice is %2d ; Process %s end.\n",currenttime,p1->pname); p1->state = F; p2->next = p1->next; p1->next = p3->next; p3->next = p1; p3 = p3->next; p1 = p2; } p2 = p1; p1 = p2->next; } return 1; } } /*按优先级调度算法执行进程*/ void executeProcess2() { while(1) { if(isProcessReady() == 0) return; else runProcess2(); } } /*运行执行队列中的进程*/ int runProcess2() { PCB *p1 , *p2 , *p3; sortByPriority(); if(execute_head.next == NULL) { currenttime ++; return 1; } else { p2 = &execute_head; p1 = p2->next; p3 = &finish_head; while(p3->next != NULL) { p3 = p3->next; } p1->runtime --; currenttime ++; if(p1->runtime == 0) { printf("Time slice is %2d ; Process %s end.\n",currenttime,p1->pname); p1->state = F; p2->next = p1->next; p1->next = p3->next; p3->next = p1; } return 1; } } /*按时间片轮转调度算法执行进程*/ void executeProcess3() { while(1) { if(isProcessReady() == 0) return; else runProcess3(); } } /*运行执行队列中的进程*/ int runProcess3() { PCB *p1 , *p2 , *p3; if(execute_head.next == NULL) { currenttime ++; return 1; } else { p2 = &execute_head; p1 = p2->next; p3 = &finish_head; while(p3->next != NULL) { p3 = p3->next; } while(p1 != NULL) { p1->runtime --; currenttime ++; if(p1->runtime <= 0) { printf("Time slice is %2d ; Process %s end.\n",currenttime,p1->pname); p2->next = p1->next; p1->state = F; p2->next = p1->next; p1->next = p3->next; p3->next = p1; p3 = p3->next; p1 = p2->next; } else { p2 = p1; p1 = p2->next; } } return 1; } } /*将就绪队列中的进程按到达时间排序*/ voidsortByArrivetime() { PCB temp; PCB *p1 , *p2 , *p3 , *p4; p2 = &ready_head; p1 = p2->next; temp.next = NULL; while(p1 != NULL) { p4 = &temp; p3 = p4->next; while((p3 != NULL)&&(p3->arrivetime<= p1->arrivetime)) { p4 = p3; p3 = p3->next; } p2->next = p1->next; p1->next = p3; p4->next = p1; p1 = p2->next; } ready_head = temp; } /*将就绪队列中的进程按优先级排序*/ voidsortByPriority() { PCB temp; PCB *p1 , *p2 , *p3 , *p4; p2 = &execute_head; p1 = p2->next; temp.next = NULL; while(p1 != NULL) { p4 = &temp; p3 = p4->next; while((p3 != NULL)&&(p3->priority >= p1->priority)) { p4 = p3; p3 = p3->next; } p2->next = p1->next; p1->next = p3; p4->next = p1; p1 = p2->next; } execute_head = temp; } int main() { int select; currenttime = 0; createProcess(); printf("\n\n"); printf("选择调度算法（1表示先来先服务调度算法，2表示优先级调度算法（数字大优先级高），3表示时间片轮转算法。默认选择为先来先服务调度算法）："); scanf("%d",&select); printf("\n\n"); switch(select) { case 1: executeProcess1(); break; case 2: executeProcess2(); break; case 3: executeProcess3(); break; default: executeProcess1(); } printf("\n\n\n\n\n\n\n\n\n"); return 1; } 银行家算法 #include #include #include #define FALSE 0 #define TRUE 1 #define W 10 #define R 10 int M ; //总进程数 int N ; //资源种类 int ALL_RESOURCE[W];//各种资源的数目总和 int MAX[W][R]; //M个进程对N类资源最大资源需求量 int AVAILABLE[R]; //系统可用资源数 int ALLOCATION[W][R]; //M个进程已经得到N类资源的资源量 int NEED[W][R]; //M个进程还需要N类资源的资源量 int Request[R]; //请求资源个数 void output() { inti,j; cout< for (j=0;j cout<<" 资源"< cout< cout<<"━━━━━━━━━━━━━━━━━━"< cout<<"目前各种资源可利用的数量为:"< for (j=0;j cout<<" 资源"< cout< cout<<"━━━━━━━━━━━━━━━━━━"< cout<<"各进程还需要的资源数量:"< for(i=0;i { cout<<" 资源"< } //cout<<" 资源0"<<" 资源1"<<" 资源2"< for (i=0;i { cout<<"进程"< for (j=0;j cout< cout< } cout< cout<<"━━━━━━━━━━━━━━━━━━"< cout<<"各进程已经得到的资源量: "< //cout<<" 资源0"<<" 资源1"<<" 资源2"< { cout<<" 资源"< } cout< for (i=0;i { cout<<"进程"< for (j=0;j cout< cout< } cout< } void distribute(int k) { int j; for (j=0;j { AVAILABLE[j]=AVAILABLE[j]-Request[j]; ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j]; NEED[k][j]=NEED[k][j]-Request[j]; } } void restore(int k) { int j; for (j=0;j { AVAILABLE[j]=AVAILABLE[j]+Request[j]; ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j]; NEED[k][j]=NEED[k][j]+Request[j]; } } int check() { int WORK[R],FINISH[W]; inti,j; for(j=0;j for(i=0;i for(i=0;i { for(j=0;j { if(FINISH[i]==FALSE&&NEED[i][j]<=WORK[j]) { WORK[j]=WORK[i]+ALLOCATION[i][j]; } } FINISH[i]=TRUE; } for(i=0;i { if(FINISH[i]==FALSE) { cout< cout<<" 系统不安全!!! 本次资源申请不成功!!!"< cout< return 1; } else { cout< cout<<" 经安全性检查，系统安全，本次分配成功。"< cout< return 0; } } } void bank() //银行家算法 { int i=0,j=0; char flag='Y'; while(flag=='Y'||flag=='y') { i=-1; while(i<0||i>=M) { cout<<"━━━━━━━━━━━━━━━━━━"< cout< cin>>i; if(i<0||i>=M) cout<<" 输入的进程号不存在，重新输入!"< } cout<<" 请输入进程"< for (j=0;j { cout<<" 资源"< cin>>Request[j]; if(Request[j]>NEED[i][j]) //若请求的资源数大于进程还需要i类资源的资源量j { cout< flag='N'; break; } else { if(Request[j]>AVAILABLE[j]) //若请求的资源数大于可用资源数{ cout< cout<<" 若继续执行系统将处于不安全状态!"< flag='N'; break; } } } if(flag=='Y'||flag=='y') { distribute(i); //调用change(i)函数，改变资源数 if(check()) //若系统安全 { restore(i); //调用restore(i)函数，恢复资源数 output(); //输出资源分配情况 } else //若系统不安全 output(); //输出资源分配情况 } else //若flag=N||flag=n cout< cout<<"是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示: "; cin>>flag; } } int main() //主函数 { int i=0,j=0,p; getchar(); cout< cin>>M; cout< cin>>N; cout< for(i=0;i { cout<<"资源"< cin>>ALL_RESOURCE[i]; } cout< for (i=0;i { for (j=0;j { do { cout<<"进程"< cin>>MAX[i][j]; if (MAX[i][j]>ALL_RESOURCE[j]) cout< } } cout< for (i=0;i { for (j=0;j { do { cout<<"进程"< cin>>ALLOCATION[i][j]; if (ALLOCATION[i][j]>MAX[i][j]) cout< } } for (j=0;j { p=ALL_RESOURCE[j]; for (i=0;i { p=p-ALLOCATION[i][j];//减去已经被占据的资源 AVAILABLE[j]=p; if(AVAILABLE[j]<0) AVAILABLE[j]=0; } } for (i=0;i for(j=0;j NEED[i][j]=MAX[i][j]-ALLOCATION[i][j]; output(); bank(); return 1; } 运行结果： 内存管理： // 内存管理 #include #include