計(jì)算機(jī)專業(yè)操作系統(tǒng)先來先服務(wù)算法詳解

1、1、 設(shè)計(jì)一個按先來先服務(wù)調(diào)度的算法提示：（1）假設(shè)系統(tǒng)中有 5 個進(jìn)程，每個進(jìn)程由一個進(jìn)程控制塊（PCB）來標(biāo)識。進(jìn)程控制塊內(nèi)容如圖 1-1 所示。進(jìn)程名即進(jìn)程標(biāo)識。指針：按照進(jìn)程到達(dá)系統(tǒng)的時間將處于就緒狀態(tài)的進(jìn)程連接成衣個就緒隊(duì)列。指針下一個到達(dá)進(jìn)程的進(jìn)程控制塊首地址。最后一個進(jìn)程的指針為 NULL。估計(jì)運(yùn)行時間：可由設(shè)計(jì)者任意指定一個時間值。到達(dá)時間：進(jìn)程創(chuàng)建時的系統(tǒng)時間或由用戶指定。調(diào)度時，總是選擇到達(dá)時間最早的進(jìn)程。進(jìn)程狀態(tài)：為簡單起見，這里假定進(jìn)程有兩種狀態(tài)：就緒和完成。并假定進(jìn)程一創(chuàng)建就處于就緒狀態(tài)，用 R 表示。當(dāng)一個進(jìn)程運(yùn)行結(jié)束時，就將其設(shè)置成完成態(tài)，用 C 表示。（2）設(shè)置

2、一個隊(duì)首指針 head，用來在一起。最先進(jìn)入系統(tǒng)的進(jìn)程。各就緒進(jìn)程通過指針連（3）處理機(jī)調(diào)度時總是選擇隊(duì)首指針指向的進(jìn)程投入運(yùn)行。由于本實(shí)驗(yàn)是模擬實(shí)驗(yàn)，所以對被選中進(jìn)程并不實(shí)際啟動運(yùn)行，而只是執(zhí)行：估計(jì)運(yùn)行時間減 1。用這個操作來模擬進(jìn)程的一次運(yùn)行，而且省去進(jìn)程的現(xiàn)場保護(hù)和現(xiàn)場恢復(fù)工作。（4）在所設(shè)計(jì)的程序中應(yīng)有顯示或打印語句，能顯示或打印正運(yùn)行進(jìn)程的進(jìn)程名、已運(yùn)行時間、時間、就緒隊(duì)列中的進(jìn)程等。所有進(jìn)程運(yùn)行完成時，給出各進(jìn)程的周轉(zhuǎn)時間和平均周轉(zhuǎn)時間。/*實(shí)驗(yàn)一 先來先服務(wù)算法模擬程序writen by daysky* 2007-11-19*/#include #include #includ

3、e #include using namespatd;/控制塊結(jié)構(gòu)體 struct PCBchar name;/進(jìn)程名PCB *next;/指針reach_time;/到達(dá)時間 left_time;/估計(jì)運(yùn)行時間 begin_time;char sus;/R 就緒 c 完成PCB();PCB(charaname,*anext=NULL);areach_time,aleft_time,abegin_time=-1,charasus=R,PCBPCB(const PCB &from);PCB:CB()next=NULL; reach_time = -1;left_time = -1;begin_t

4、ime = -1; sus = R;PCB:CB(char aname,areach_time,aleft_time,abegin_time,char asus,PCB *anext)name = aname; reach_time = areach_time; left_time = aleft_time; begin_time = abegin_time; sus = asus;next = anext;PCB:CB(const PCB &from)name = ; next = NULL;reach_time = from.reach_time;left_time =

5、from.left_time;begin_time = -1; sus = R;/* 先來先服務(wù)類*/classServeprivate:systime;/系統(tǒng)時間list *ready_list,*all_task;/ 就緒隊(duì)列 所有任務(wù)together_time; ofstream fout; public:Serve();Serve(list *a_all_task,const char *logfile);bool run();void check_task(); void run_ready(); void pr_ready();Serve();Serve:Serve()systim

6、e=0; together_time = 0;ready_list=new list();all_task=new list();Serve:Serve(list *a_all_task,const char *logfile)systime=0; together_time = 0;ready_list = new list();fout.open(logfile,ios:trunc);/服務(wù)執(zhí)行總調(diào)度boolServe:run()num = all_task-size(); while(ready_list-empty()/添加新進(jìn)程,同時從所有隊(duì)列中刪除剛添加的進(jìn)程 check_task

7、();systime+;/運(yùn)行直到有任務(wù)do/打印就緒隊(duì)列pr_ready();/執(zhí)行就緒隊(duì)列run_ready();systime+;check_task();while(!ready_list-empty();/打印平均周轉(zhuǎn)時間fout 平均周轉(zhuǎn)時間為: together_ti return true;m ! endl;/檢查到達(dá)的任務(wù)，添加到就緒隊(duì)列的尾部voidServe:check_task()PCB *current;list:iterator it;it = all_task-begin();/這里用循環(huán)處理，因?yàn)榭赡苡卸鄠€同時到達(dá)的任務(wù) while(it!=all_task-e

8、nd()current=(*it);if(current-reach_time=systime)PCB *a_pcb = new PCB(*current);/ a_pcb-sus = R;進(jìn)程信息ready_list-push_back(a_pcb);/添加在就緒隊(duì)列的尾部 it = all_task-erase(it); /從所有任務(wù)中刪除這個任務(wù)fout 進(jìn)程 name 在時刻: systime 進(jìn)入就緒隊(duì)列! empty() return;/就緒隊(duì)列為空就不執(zhí)行,否則PCB *front = ready_list-front();if(front-begin_time = -1)/進(jìn)程

9、第一次運(yùn)行，設(shè)置運(yùn)行起始時間front-begin_time = systime;front-left_time -;/執(zhí)行一次，估計(jì)時間減一fout 進(jìn)程 name 執(zhí)行在時刻: systime ! endl;fout 進(jìn)程 name 已運(yùn)行時間: begin_time+1) ! endl;fout 進(jìn)程 name left_time = 0)front-sus = C;時間為: left_time ! endl;/打印并計(jì)算周轉(zhuǎn)時間,systime-1 為完成時間fout 進(jìn)程 name 在時刻: systime 結(jié)束! reach_time;together_time += a_time

10、;fout 進(jìn)程 name 的周轉(zhuǎn)時間為: a_time ! pop_front();/刪除第一個元素voidServe:pr_ready()fout 就緒隊(duì)列中的進(jìn)程有：;list:iterator it=ready_list-begin();while(it!=ready_list-end()fout name 、; it+;fout endl;Serve:Serve()folose();main()PCB *a_pcb5;list *all_task=new list();cout 正在初始化 endl;/五個進(jìn)程的到達(dá)時間各不相同 a_pcb0 = new PCB(A,9,10);a_pcb1 = new PCB(B,1,30);a_pcb2 = new PCB(C,3,25)