實(shí)驗(yàn)二單處理器系統(tǒng)的進(jìn)程調(diào)度

1、實(shí)驗(yàn)二  單處理器系統(tǒng)的進(jìn)程調(diào)度（附實(shí)驗(yàn)報(bào)告） 1實(shí)驗(yàn)?zāi)康募由顚?duì)進(jìn)程概念的理解，明確進(jìn)程和程序的區(qū)別；深入了解系統(tǒng)如何組織進(jìn)程、創(chuàng)建進(jìn)程；進(jìn)一步認(rèn)識(shí)如何實(shí)現(xiàn)處理器調(diào)度。 2實(shí)驗(yàn)預(yù)備知識(shí)進(jìn)程的概念；進(jìn)程的組織方式；進(jìn)程的創(chuàng)建；進(jìn)程的調(diào)度。  3實(shí)驗(yàn)內(nèi)容編寫程序完成單處理機(jī)系統(tǒng)中的進(jìn)程調(diào)度，要求采用時(shí)間片輪轉(zhuǎn)調(diào)度算法。實(shí)驗(yàn)具體包括：首先確定進(jìn)程控制塊的內(nèi)容，進(jìn)程控制塊的組成方式；然后完成進(jìn)程創(chuàng)建原語和進(jìn)程調(diào)度原語；最后編寫主函數(shù)對(duì)所作工作進(jìn)程測(cè)試。 4提示與講解這個(gè)實(shí)驗(yàn)主要要考慮三個(gè)問題：如何組織進(jìn)程、如何創(chuàng)建進(jìn)程和如何實(shí)現(xiàn)處理器調(diào)度?？紤]如何組織

2、進(jìn)程，首先就要設(shè)定進(jìn)程控制塊的內(nèi)容。進(jìn)程控制塊PCB記錄各個(gè)進(jìn)程執(zhí)行時(shí)的情況。不同的操作系統(tǒng)，進(jìn)程控制塊記錄的信息內(nèi)容不一樣。操作系統(tǒng)功能越強(qiáng)，軟件也越龐大，進(jìn)程控制塊記錄的內(nèi)容也就越多。這里的實(shí)驗(yàn)只使用了必不可少的信息。一般操作系統(tǒng)中，無論進(jìn)程控制塊中信息量多少，信息都可以大致分為以下四類：    標(biāo)識(shí)信息每個(gè)進(jìn)程都要有一個(gè)惟一的標(biāo)識(shí)符，用來標(biāo)識(shí)進(jìn)程的存在和區(qū)別于其他進(jìn)程。這個(gè)標(biāo)識(shí)符是必不可少的，可以用符號(hào)或編號(hào)實(shí)現(xiàn)，它必須是操作系統(tǒng)分配的。在后面給出的參考程序中，采用編號(hào)方式，也就是為每個(gè)進(jìn)程依次分配一個(gè)不相同的正整數(shù)。 說明信息用于記錄進(jìn)程的基本情況，例如進(jìn)

3、程的狀態(tài)、等待原因、進(jìn)程程序存放位置、進(jìn)程數(shù)據(jù)存放位置等等。實(shí)驗(yàn)中，因?yàn)檫M(jìn)程沒有數(shù)據(jù)和程序，僅使用進(jìn)程控制塊模擬進(jìn)程，所以這部分內(nèi)容僅包括進(jìn)程狀態(tài)。 現(xiàn)場(chǎng)信息現(xiàn)場(chǎng)信息記錄各個(gè)寄存器的內(nèi)容。當(dāng)進(jìn)程由于某種原因讓出處理器時(shí)，需要將現(xiàn)場(chǎng)信息記錄在進(jìn)程控制塊中，當(dāng)進(jìn)行進(jìn)程調(diào)度時(shí)，從選中進(jìn)程的進(jìn)程控制塊中讀取現(xiàn)場(chǎng)信息進(jìn)行現(xiàn)場(chǎng)恢復(fù)。現(xiàn)場(chǎng)信息就是處理器的相關(guān)寄存器內(nèi)容，包括通用寄存器、程序計(jì)數(shù)器和程序狀態(tài)字寄存器等。在實(shí)驗(yàn)中，可選取幾個(gè)寄存器作為代表。用大寫的全局變量AX、BX、CX、DX模擬通用寄存器、大寫的全局變量PC模擬程序計(jì)數(shù)器、大寫的全局變量PSW模擬程序狀態(tài)字寄存器。 管理信息管理信息記錄進(jìn)程管

4、理和調(diào)度的信息。例如進(jìn)程優(yōu)先數(shù)、進(jìn)程隊(duì)列指針等。實(shí)驗(yàn)中，僅包括隊(duì)列指針。因此可將進(jìn)程控制塊結(jié)構(gòu)定義如下：struct pcbint name;                   int status;                  int ax

5、, bx, cx,dx;               int pc;                 int psw;                int n

6、ext;               確定進(jìn)程控制塊內(nèi)容后，要考慮的就是如何將進(jìn)程控制塊組織在一起。多道程序設(shè)計(jì)系統(tǒng)中，往往同時(shí)創(chuàng)建多個(gè)進(jìn)程。在單處理器的情況下，每次只能有一個(gè)進(jìn)程處于運(yùn)行態(tài)，其他的進(jìn)程處于就緒狀態(tài)或等待狀態(tài)。為了便于管理，通常把處于相同狀態(tài)的進(jìn)程的進(jìn)程控制塊鏈接在一起。單處理器系統(tǒng)中，正在運(yùn)行的進(jìn)程只有一個(gè)。因此，單處理器系統(tǒng)中進(jìn)程控制塊分成一個(gè)正在運(yùn)行進(jìn)程的進(jìn)程控制塊、就緒進(jìn)程的進(jìn)程控制塊組織成的就緒隊(duì)列和等待進(jìn)程的進(jìn)程控制塊組成的等待

7、隊(duì)列。由于實(shí)驗(yàn)?zāi)M的是進(jìn)程調(diào)度，沒有對(duì)等待隊(duì)列的操作，所以實(shí)驗(yàn)中只有一個(gè)指向正在運(yùn)行進(jìn)程的進(jìn)程控制塊指針和一個(gè)就緒進(jìn)程的進(jìn)程控制塊隊(duì)列指針。操作系統(tǒng)的實(shí)現(xiàn)中，系統(tǒng)往往在主存中劃分出一個(gè)連續(xù)的專門區(qū)域存放系統(tǒng)的進(jìn)程控制塊，實(shí)驗(yàn)中應(yīng)該用數(shù)組模擬這個(gè)專門的進(jìn)程控制塊區(qū)域，定義如下：#define  n   10           struct pcb  pcbarean;         這

8、樣，進(jìn)程控制塊的鏈表實(shí)際上是數(shù)據(jù)結(jié)構(gòu)中使用的靜態(tài)鏈表。進(jìn)程控制塊的鏈接方式可以采用單向和雙向鏈表，實(shí)驗(yàn)中，進(jìn)程控制塊隊(duì)列采用單向不循環(huán)靜態(tài)鏈表。為了管理空閑進(jìn)程控制塊，還應(yīng)該將空閑控制塊鏈接成一個(gè)隊(duì)列。實(shí)驗(yàn)中采用時(shí)間片輪轉(zhuǎn)調(diào)度算法，這種算法是將進(jìn)程控制塊按照進(jìn)入就緒隊(duì)列的先后次序排成隊(duì)列。關(guān)于就緒隊(duì)列的操作就是從隊(duì)頭摘下一個(gè)進(jìn)程控制塊和從隊(duì)尾掛入一個(gè)進(jìn)程控制塊。因此為就緒隊(duì)列定義兩個(gè)指針，一個(gè)頭指針，指向就緒隊(duì)列的第一個(gè)進(jìn)程控制塊；一個(gè)尾指針，指向就緒隊(duì)列的最后一個(gè)進(jìn)程控制塊。實(shí)驗(yàn)中指向運(yùn)行進(jìn)程的進(jìn)程控制塊指針、就緒隊(duì)列指針和空閑進(jìn)程控制塊隊(duì)列指針定義如下：int  run;

9、60;         structint  head; int  tail;ready;             int  pfree;         以上是如何組織進(jìn)程，下面考慮如何創(chuàng)建進(jìn)程。進(jìn)程創(chuàng)建是一個(gè)原語，因此在實(shí)驗(yàn)中應(yīng)該用一個(gè)函數(shù)實(shí)現(xiàn)，進(jìn)程創(chuàng)建的過程應(yīng)該包

10、括：申請(qǐng)進(jìn)程控制塊：進(jìn)程控制塊的數(shù)量是有限的，如果沒有空閑進(jìn)程控制塊，則進(jìn)程不能創(chuàng)建，如果申請(qǐng)成功才可以執(zhí)行第步；申請(qǐng)資源：除了進(jìn)程控制塊外，還需要有必要的資源才能創(chuàng)建進(jìn)程，如果申請(qǐng)資源不成功，則不能創(chuàng)建進(jìn)程，并且歸還已申請(qǐng)的進(jìn)程控制塊；如果申請(qǐng)成功，則執(zhí)行第三步，實(shí)驗(yàn)無法申請(qǐng)資源，所以模擬程序忽略了申請(qǐng)資源這一步；填寫進(jìn)程控制塊：將該進(jìn)程信息寫入進(jìn)程控制塊內(nèi)，實(shí)驗(yàn)中只有進(jìn)程標(biāo)識(shí)符、進(jìn)程狀態(tài)可以填寫，每個(gè)進(jìn)程現(xiàn)場(chǎng)信息中的寄存器內(nèi)容由于沒有具體數(shù)據(jù)而使用進(jìn)程（模擬進(jìn)程創(chuàng)建時(shí)，需輸入進(jìn)程標(biāo)識(shí)符字，進(jìn)程標(biāo)識(shí)符本應(yīng)系統(tǒng)建立，并且是惟一的，輸入時(shí)注意不要沖突），剛剛創(chuàng)建的進(jìn)程應(yīng)該為就緒態(tài)，然后轉(zhuǎn)去執(zhí)行第

11、四步；掛入就緒隊(duì)列：如果原來就緒隊(duì)列不為空，則將該進(jìn)程控制塊掛入就緒隊(duì)列尾部，并修改就緒隊(duì)列尾部指針；如果原來就緒隊(duì)列為空，則將就緒隊(duì)列的頭指針、尾指針均指向該進(jìn)程控制塊，進(jìn)程創(chuàng)建完成。進(jìn)程創(chuàng)建流程圖如圖2.2所示。多道程序設(shè)計(jì)的系統(tǒng)中，處于就緒態(tài)的進(jìn)程往往是多個(gè)，它們都要求占用處理器，可是單處理器系統(tǒng)的處理器只有一個(gè)，進(jìn)程調(diào)度就是解決這個(gè)處理器競(jìng)爭(zhēng)問題的。進(jìn)程調(diào)度的任務(wù)就是按照某種算法從就緒進(jìn)程隊(duì)列中選擇一個(gè)進(jìn)程，讓它占有處理器。因此進(jìn)程調(diào)度程序就應(yīng)該包括兩部分，一部分是在進(jìn)程就緒隊(duì)列中選擇一個(gè)進(jìn)程，并將其進(jìn)程控制塊從進(jìn)程就緒隊(duì)列中摘下來，另一部分工作就是分配處理器給選中的進(jìn)程，也就是將指向

12、正在運(yùn)行進(jìn)程的進(jìn)程控制塊指針指向該進(jìn)程的進(jìn)程控制塊，并將該進(jìn)程的進(jìn)程控制塊信息寫入處理器的各個(gè)寄存器中。  圖2.2  進(jìn)程創(chuàng)建流程圖  實(shí)驗(yàn)中采用時(shí)間片輪轉(zhuǎn)調(diào)度算法。時(shí)間片輪轉(zhuǎn)調(diào)度算法讓就緒進(jìn)程按就緒的先后次序排成隊(duì)列，每次總是選擇就緒隊(duì)列中的第一個(gè)進(jìn)程占有處理器，但是規(guī)定只能使用一個(gè)“時(shí)間片”。時(shí)間片就是規(guī)定進(jìn)程一次使用處理器的最長(zhǎng)時(shí)間。實(shí)驗(yàn)中采用每個(gè)進(jìn)程都使用相同的不變的時(shí)間片。采用時(shí)間片輪轉(zhuǎn)調(diào)度算法的進(jìn)程調(diào)度流程圖如圖2.3所示。完成上述功能后，編寫主函數(shù)進(jìn)行測(cè)試：首先建立一個(gè)就緒隊(duì)列，手工輸入信息建立幾個(gè)進(jìn)程；然后進(jìn)行進(jìn)程調(diào)度；最后將

13、指向正在運(yùn)行進(jìn)程的指針指向的進(jìn)程控制塊的內(nèi)容輸出，察看結(jié)果。  圖2.3  進(jìn)程調(diào)度流程圖 5課外題編程實(shí)現(xiàn)采用優(yōu)先數(shù)調(diào)度算法的進(jìn)程調(diào)度。  我的實(shí)現(xiàn)代碼（C語言）：#include <stdio.h>#define N 10     /系統(tǒng)中所允許的最大進(jìn)程數(shù)量#define SLOT 5   /時(shí)間片大小/進(jìn)程狀態(tài)枚舉typedef enum Running,     /運(yùn)行狀態(tài) Aready,

14、60;     /就緒狀態(tài) Blocking     /阻塞狀態(tài) ProStatus;/進(jìn)程控制塊typedef struct int name;                  /進(jìn)程標(biāo)識(shí)符 ProStatus status;       

15、60;  /進(jìn)程狀態(tài) int ax,bx,cx,dx;           /通用寄存器 int pc;                    /程序計(jì)數(shù)器寄存器 int psw;       

16、60;           /程序狀態(tài)字寄存器 int next;                  /指向下一個(gè)進(jìn)程的指針 PCB;/就緒隊(duì)列指針typedef struct           int he

17、ad;            /頭指針 int tail;            /尾指針 Ready;/模擬寄存器int PSW,AX,BX,CX,DX,PC,TIME;/PCB的靜態(tài)鏈表PCB pcbAreaN;          /模擬PCB區(qū)域的數(shù)組int run;

18、60;                /運(yùn)行狀態(tài)程序的指針Ready ready;             /就緒隊(duì)列指針              int pfree; 

19、0;             /空閑隊(duì)列的指針 /初始化運(yùn)行狀態(tài)進(jìn)程指針void InitRun() run=-1;  /初始化就緒狀態(tài)隊(duì)列void InitReady() ready.head=ready.tail=-1; /初始化空閑隊(duì)列void InitFree() int temp; for(temp=0;temp<N-1;temp+)   pcbAre

20、atemp.next=temp+1;  pcbAreatemp.next=-1; pfree=0; /就緒隊(duì)列出隊(duì)int PopReady()          /返回結(jié)點(diǎn)在PCB區(qū)域數(shù)組的編號(hào) int temp; if(ready.head=-1)   printf("就緒隊(duì)列為空，不能出隊(duì)。n");  return -1;  temp=ready.hea

21、d; ready.head=pcbAreatemp.next; if(ready.head=-1)  ready.tail=-1; pcbAreatemp.next=-1; return temp; /空閑隊(duì)列出隊(duì)int PopFree()          /返回結(jié)點(diǎn)在PCB區(qū)域數(shù)組的編號(hào) int temp;     if(pfree=-1)   

22、;  printf("空閑隊(duì)列為空，不能出隊(duì)。n");  return -1;   temp=pfree; pfree=pcbAreatemp.next; pcbAreatemp.next=-1; return temp; /就緒隊(duì)列入隊(duì)void PushReady(int x)          /x為入隊(duì)結(jié)點(diǎn)的編號(hào) int temp; if(ready.

23、head=-1)   ready.head=x;  ready.tail=x;  else   temp=ready.tail;  ready.tail=x;  pcbAreaready.tail.next=-1;/創(chuàng)建PCBvoid CreatePCB(int x,PCB pcb)         /x為要?jiǎng)?chuàng)建PCB在PCB區(qū)域數(shù)組的編號(hào) pcbAreax.ax=p

24、cb.ax; pcbAreax.bx=pcb.bx; pcbAreax.cx=pcb.cx; pcbAreax.dx=pcb.dx; pcbA=; pcbAreax.next=-1; pcbAreax.pc=pcb.pc; pcbAreax.psw=pcb.psw; pcbAreax.status=pcb.status;/創(chuàng)建進(jìn)程函數(shù)void Create(PCB pcb) int temp; if(pfree=-1)   prin

25、tf("空閑隊(duì)列為空，不能創(chuàng)建進(jìn)程。n");  return;  temp=PopFree(); pcb.status=Aready; CreatePCB(temp,pcb); PushReady(temp);/進(jìn)程調(diào)度函數(shù)void Schedule() int temp; if(ready.head=-1)   printf("系統(tǒng)內(nèi)沒有進(jìn)程可以調(diào)度。");  return;  temp=Pop

26、Ready(); pcbAreatemp.status=Running; TIME=SLOT;                            /恢復(fù)CPU現(xiàn)場(chǎng) AX=pcbAreatemp.ax; BX=pcbAreatemp.bx; CX=pcbAreatemp.cx;

27、 DX=pcbAreatemp.dx; PC=pcbAreatemp.pc; PSW=pcbAreatemp.psw;  run=temp;             /將選中的進(jìn)程賦給運(yùn)行指針 printf("當(dāng)前運(yùn)行的程序：n");          /輸出調(diào)度結(jié)果 printf("進(jìn)程號(hào)：%dn"