银行家算法

实验一、进程管理与进程同步实验目的：了解进程管理的实现方法，理解和掌握处理进程同步问题的方法。实验内容：实现银行家算法、进程调度过程的模拟、读者-写者问题的写者优先算 法。实验步骤： 理解安全性算法和银行家算法的核心机制：针对 3 类资源、5个进程的情况，设计相应的数据结构，分别表示 每个进程占用各类资源的情况；编程实现安全性算法函数，编制主函数，动态输入资源的占用情况， 进程的资源申请，调用安全性函数，实现银行家算法；测试：输入可分配和不可分配的请求，测试系统的正确性。 理解进程的三状态调度过程，及各状态间的转换关系； 模拟若干个进程的运行过程，将其存入进程文件中。如：进程 1： 运行 5 秒后有 3 秒的 I/O 操作，之后有 10 秒的运行，结束。可以写 成：”pl:r5,io3,r3 e;” ；编程实现调度算法函数，定义时间片大小和并发进程个数，不断从 进程文件中读出进程信息，模拟进程的运行及调度过程；测试：针对进程文件里面的数据为正常、缺项、格式不正确等各种 情况，检测程序的执行结果。试验程序银行家算法：#include#includestruct typeint a;int b;int c;struct allocationstruct type value;struct allocation *next; ;struct maxstruct type value;struct max *next; ;struct availablestruct type value;struct available *next; ;struct needstruct type value;struct need *next; ;struct pathint value;struct path *next;struct finishint value;struct finish *next; ;void main()int p,status=0,i,j,temp,flag=0;struct allocation *allochead,*alloc1,*alloc2,*alloctemp;struct max *maxhead,*max1,*max2,*maxtemp;struct available *availablehead,*workhead,*worktemp;struct need *needhead,*need1,*need2,*needtemp;struct path *pathhead,*path1,*path2,*pathtemp; struct finish *finishhead,*finish1,*finish2,*finishtemp;pri ntf（请输入进程的数目n）; scanf(%d,&p); for(i=0;ivalue.a);printf(t 当前资源类型是 %ct,b);scanf(%d,&alloc1-value.b);printf(t 当前资源类型是 %ct,c);scanf(%d,&alloc1-value.c);flag+;allochead=alloc1;elsealloc2=(struct allocation*)malloc(sizeof(struct allocation);printf(t 当前资源类型是 %ct,a);scanf(%d,&alloc2-value.a);printf(t 当前资源类型是 %ct,b);scanf(%d,&alloc2-value.b);printf(t 当前资源类型是 %ct,c);scanf(%d,&alloc2-value.c);alloc1-next=alloc2;alloc1=alloc2;flag+; alloc2-next=NULL;flag=0;for(i=0;ivalue.a);printf(t 当前资源类型是 %ct,b); scanf(%d,&max1-value.b);printf(t 当前资源类型是 %ct,c); scanf(%d,&max1-value.c);maxhead=max1;flag+;elsemax2=(struct max*)malloc(sizeof(struct max);printf(t 当前资源类型是 %ct,a); scanf(%d,&max2-value.a);printf(t 当前资源类型是 %ct,b); scanf(%d,&max2-value.b);printf(t 当前资源类型是 s %ct,c);scanf(%d,&max2-value.c); max1-next=max2;max1=max2;flag+; max2-next=NULL;flag=0;printf(n请输入可以利用是资源数目n);availablehead=workhead=(struct available*)malloc(sizeof(struct available); printf(n);printf(t当前资源类型是%ct,a);scanf(%d,&availablehead-value.a);printf(t当前资源类型是%ct,b); scanf(%d,&availablehead-value.b);printf(t当前资源类型是%ct,c);scanf(%d,&availablehead-value.c);workhead=availablehead; workhead-value=availablehead-value;flag=0;alloctemp=allochead; maxtemp=maxhead;for(i=0;inext=need2-next=NULL;need1-value.a=(maxtemp-value.a)-(alloctemp-value.a);need1-value.b=(maxtemp-value.b)-(alloctemp-value.b);need1-value.c=(maxtemp-value.c)-(alloctemp-value.c);needhead=need1;flag+;elseneed2=(struct need*)malloc(sizeof(struct need);need2-value.a=(maxtemp-value.a)-(alloctemp-value.a); need2-value.b=(maxtemp-value.b)-(alloctemp-value.b); need2-value.c=(maxtemp-value.c)-(alloctemp-value.c);need1-next=need2;need1=need2;flag+;maxtemp=maxtemp-next; alloctemp=alloctemp-next;need2-next=NULL;flag=0;for(i=0;inext=finish2-next=NULL;finish1-value=0;finishhead=finish1;flag+;elsefinish2=(struct finish*)malloc(sizeof(struct finish);finish2-value=0;finish1-next=finish2; finish1=finish2;flag+;finish2-next=NULL;flag=0;for(temp=0;tempp;temp+)alloctemp=allochead;needtemp=needhead; finishtemp=finishhead;worktemp=workhead;for(j=0;jvalue=0)if(needtemp-value.avalue.a)&(needtemp-value.bvalue.b)&(needtemp-value.cvalue.c)worktemp-value.a+=alloctemp-value.a; worktemp-value.b+=alloctemp-value.b; worktemp-value.c+=alloctemp-value.c;finishtemp-value=1;if(flag=0)pathhead=path1=path2=(struct path*)malloc(sizeof(struct path); path1-next=path2-next=NULL;path1-value=j+1;pathhead=path1;flag+;elsepath2=(struct path*)malloc(sizeof(struct path);path2-value=j+1;path1-next=path2;path1=path2;flag+;finishtemp=finishtemp-next;alloctemp=alloctemp-next; needtemp=needtemp-next;elsefinishtemp=finishtemp-next; alloctemp=alloctemp-next; needtemp=needtemp-next;elsefinishtemp=finishtemp-next; alloctemp=alloctemp-next; needtemp=needtemp-next;path2-next=NULL;finishtemp=finishhead; pathtemp=pathhead;for(temp=0;tempvalue=0)printf(n警告!当前系统是不安全的n);exit(0);finishtemp=finishtemp-next;printf(n当前系统是安全的!n);printf(n 安全序列为: n); for(i=0;ivalue);pathhead=pathhead-next;试验结果：进程调度程序：#include #include #include #define P_NUM 3 /进程数 #define P_TIME 1/时间片长度 #define MIN -9999 enum state /进程状态ready, /就绪 run, /执行 wait,/阻塞finish /完成;class Pcbpublic:static void print();Pcb(); protected:char* name;/进程名int allTime;/需要运行时间int cpuTime;/已用 cpu 时间state process; /进程状态;class HPcb:public Pcbpublic:static void print();static void highS(); static int getFirst();private:int firstNum;HPcb hpcbP_NUM;class FPcb:public Pcbpublic:static void print();static void fcfs();private:int comeTime;FPcb fpcbP_NUM;int HPcb:getFirst() /得到优先级最高的进程int k=0;for(int i=1;iP_NUM;i+) if(hpcbk.firstNumhpcbi.firstNum) k=i;return k;void HPcb:highS() /最高优先数优先的调度算法int ii,f,i=0;for(;iP_NUM;i+)char* ch;ch=new char1;cout请输入第vvi+1vv个进程的“进程名”、“优先数”、“需要运行的时间”: ch;hpcbi.name=new charstrlen(ch)+1; strcpy(hpcbi.name,ch);cinhpcbi.firstNumhpcbi.allTime;hpcbi.cpuTime=0; hpcbi.process=ready;dof=getFirst(); hpcbf.cpuTime+=P_TIME;hpcbf.firstNum-;hpcbf.process=run;if(hpcbf.cpuTime=hpcbf.allTime) 该进程执行完成hpcbf.firstNum=MIN;hpcbf.process=finish;hpcbf.cpuTime=hpcbf.allTime;防止所用时间超过总的时间 system(cls);print();Sleep(1000);elsehpcbf.firstNum+;为了输出改变前的相关信息system(cls);print();Sleep(1000);hpcbf.firstNum-;hpcbf.process=ready;for(ii=0;iivP_NUM;ii+)用于判断是否还有进程未完成if(hpcbii.firstNum!=MIN)break;while(iivP_NUM);还有进程未完成coutvv所有进程已运行完成！ ”vvendl;Pcb:Pcb()delete name;void FPcb:fcfs()/先来先服务算法int i=0;for(;ivP_NUM;i+)char* ch;ch=new char1;coutvv请输入第”vvi+1vv”个进程的进程名”、需要运行的时间”：”vvendl;cinch;fpcbi.name=new charstrlen(ch)+1;strcpy(fpcbi.name,ch);cinfpcbi.allTime; fpcbi.comeTime=i+1;fpcbi.cpuTime=0;fpcbi.process=ready; for(i=0;iP_NUM;i+) /P_NUM 个进程for(int j=0;j=fpcbi.allTime)if(i+1)!=P_NUM)/如果第i+1个进程不是最后一个进程 fpcbi+1.cpuTime=fpcbi.cpuTime-fpcbi.allTime;fpcbi.cpuTime=fpcbi.allTime; fpcbi.process=finish;fpcbi+1.process=run;elsefpcbi.process=finish; fpcbi.cpuTime=fpcbi.allTime; system(cls);print(); Sleep(1000);coutvv”所有进程已运行完成！ ”vvendl;void HPcb:print()cout*endl;coutvv进程名vvtvv还需运行时间tvv已用CPU时间vvtvv优先级 vvtvv状态vve ndl;for(int i=0;ivP_NUM;i+)coutvvhpcbi.namevvttvvhpcbi.allTime-hpcbi.cpuTimevvttvvhpcbi.cpuTimevvtvvhpcbi.firstNumvvt;switch(hpcbi.process)case wait:coutv v阻塞态”vven dl;break;case ready:coutv v就绪态”vven dl;break;case run: coutv v运行态”vven dl;break;case fin ish:coutvv完成态vve ndl;break;coutvvvvendl;coutvvendl;void FPcb:print()coutvv*vvendl;coutvv进程名vvtvv还需运行时间tvv已用CPU时间vvtvv状态 vvendl;for(int i=0;ivP_NUM;i+)coutvvfpcbi.namevvttvvfpcbi.allTime-fpcbi.cpuTimevvttvvfpcbi.cp uTimevvt;switch(fpcbi.process)case wait:coutv v阻塞态vven dl;break;case ready:coutv v就绪态vven dl;break;case run: coutv v运行态vven dl;break;case fin ish:coutvv完成态vve ndl;break;coutvvvvendl;coutch; if(ch=1)FPcb:fcfs();else if(ch=2) HPcb:highS();return 0; #includevwindows.h #includeviostream.h #includevstring.h#define P_NUM 3 /进程数 #define P_TIME 1/时间片长度#define MIN -9999 enum state /进程状态ready,/就绪run, /执行 wait,/阻塞finish/完成;class Pcbpublic:static void print();Pcb();protected:char* name;/进程名int allTime;/需要运行时间int cpuTime;/已用 cpu 时间state process; /进程状态;class HPcb:public Pcbpublic:static void print();static void highS();static int getFirst(); private:int firstNum;HPcb hpcbP_NUM;class FPcb:public Pcbpublic:static void print();static void fcfs(); private:int comeTime;FPcb fpcbP_NUM;int HPcb:getFirst() /得到优先级最高的进程int k=0;for(int i=1;iP_NUM;i+)if(hpcbk.firstNumhpcbi.firstNum)k=i;return k;void HPcb:highS() /最高优先数优先的调度算法int ii,f,i=0;for(;iP_NUM;i+)char* ch;ch=new char1;cout请输入第vvi+1vv个进程的“进程名”、“优先数”、“需要运行的时间”:ch;hpcbi.name=new charstrlen(ch)+1;strcpy(hpcbi.name,ch);cinhpcbi.firstNumhpcbi.allTime;hpcbi.cpuTime=0;hpcbi.process=ready;dof=getFirst();hpcbf.cpuTime+=P_TIME;hpcbf.firstNum-;hpcbf.process=run;if(hpcbf.cpuTime=hpcbf.allTime) 该进程执行完成hpcbf.firstNum=MIN;hpcbf.process=finish;hpcbf.cpuTime=hpcbf.allTime;防止所用时间超过总的时间 system(cls);print();Sleep(1000);elsehpcbf.firstNum+;为了输出改变前的相关信息 system(cls);print();Sleep(1000);hpcbf.firstNum-;hpcbf.process=ready;for(ii=0;iivP_NUM;ii+)用于判断是否还有进程未完成if(hpcbii.firstNum!=MIN)break;while(iivP_NUM);还有进程未完成coutvv所有进程已运行完成！ ”vvendl;Pcb:Pcb()delete name;int i=0;for(;ich;fpcbi.name=new charstrlen(ch)+1;strcpy(fpcbi.name,ch);cinfpcbi.allTime;fpcbi.comeTime=i+1;fpcbi.cpuTime=0;fpcbi.process=ready;for(i=0;ivP_NUM;i+) P_NUM 个进程for(int j=0;jvfpcbi.allTime;j+=P_TIME) /每个进程所用时间fpcbi.cpuTime+=P_TIME;/第 i 个进程所用时间加 1 个时间片if(fpcbi.cpuTimevfpcbi.allTime) /第 i 个进程还未完成fpcbi.process=run;/将其状态设为就绪态elsefpcbi.cpuTime=fpcbi.allTime; /防止所用时间超过总时间，因为时间片 不定fpcbi.process=finish;/将状态设为完成态if(j+P_TIME=fpcbi.allTime)if(i+1)!=P_NUM)/如果第i+1个进程不是最后一个进程fpcbi+1.cpuTime=fpcbi.cpuTime-fpcbi.allTime; fpcbi.cpuTime=fpcbi.allTime;fpcbi.process=finish; fpcbi+1.process=run;elsefpcbi.process=finish;fpcbi.cpuTime=fpcbi.allTime;system(cls);print();Sleep(1000);coutvv”所有进程已运行完成！ ”vvendl;void HPcb:print()coutvv*vvendl;coutvv进程名vvtvv还需运行时间tvv已用CPU时间vvtvv优先级 vvtvv状态vve ndl;for(int i=0;ivP_NUM;i+)coutvvhpcbi.namevvttvvhpcbi.allTime-hpcbi.cpuTimevvttvvhpcbi.cpuTimevvtvvhpcbi.firstNumvvt;switch(hpcbi.process)case wait:coutv v阻塞态”vven dl;break;case ready:coutv v就绪态”vven dl;break;case run: coutv v运行态”vven dl;break;case fin ish:coutvv完成态vve ndl;break;coutvvvvendl;coutvvendl;void FPcb:print()coutvv*vvendl;coutvv进程名vvtvv还需运行时间tvv已用CPU时间vvtvv状态 vvendl;for(int i=0;ivP_NUM;i+)coutfpcbi.namettfpcbi.allTime-fpcbi.cpuTimettfpcbi.cp uTimech;if(ch=1)FPcb:fcfs();else if(ch=2)HPcb:highS();return 0;读者写者问题写着优先写者优先:readerRepeatP(writerpending) ;P(s);P(mutex);RC:=RC+1;if RC=1 then P(w);V(mutex);V(s);V(writerpending); reading;P(mutex);RC:=RC-1; if RC=0 then V(w); V(mutex);Util false;writerRepeatP(k);WC:=WC+1; if WC=1 then P(s); V(k);P(w); writing;V(w);P(k);WC:=WC-1; if WC=0 then V(s); V(k);Util false;