操作系統(tǒng)處理器調(diào)度(董迎順)

1、實(shí)驗(yàn)三 處理器調(diào)度【實(shí)驗(yàn)?zāi)康摹吭诓捎枚嗟莱绦蛟O(shè)計(jì)的系統(tǒng)中，往往有若干個(gè)進(jìn)程同時(shí)處于就緒狀態(tài)。當(dāng)就緒進(jìn)程個(gè)數(shù)大于處理器數(shù)時(shí)，就必須依照某種策略來(lái)決定哪些進(jìn)程優(yōu)先占用處理器。本實(shí)驗(yàn)?zāi)M在單處理器情況下的處理器調(diào)度，幫助學(xué)生加深了解處理器調(diào)度的工作?！緦?shí)驗(yàn)內(nèi)容】選擇一個(gè)調(diào)度算法，實(shí)現(xiàn)處理器調(diào)度?！緦?shí)驗(yàn)指導(dǎo)】本實(shí)驗(yàn)有兩個(gè)題，學(xué)生可選擇其中的一題做實(shí)驗(yàn)。第一題：設(shè)計(jì)一個(gè)按優(yōu)先數(shù)調(diào)度算法實(shí)現(xiàn)處理器調(diào)度的程序。提示：(1) 假定系統(tǒng)有五個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來(lái)代表，進(jìn)程控制塊的格式為：進(jìn)程名指針要求運(yùn)行時(shí)間優(yōu)先數(shù)狀態(tài)其中，進(jìn)程名作為進(jìn)程的標(biāo)識(shí)，假設(shè)五個(gè)進(jìn)程的進(jìn)程名分別為P1，P2，P3，P

2、4，P5。指針按優(yōu)先數(shù)的大小把五個(gè)進(jìn)程連成隊(duì)列，用指針指出下一個(gè)進(jìn)程的進(jìn)程控制塊的首地址，最后一個(gè)進(jìn)程中的指針為“0”。要求運(yùn)行時(shí)間假設(shè)進(jìn)程需要運(yùn)行的單位時(shí)間數(shù)。優(yōu)先數(shù)賦予進(jìn)程的優(yōu)先數(shù)，調(diào)度時(shí)總是選取優(yōu)先數(shù)大的進(jìn)程先執(zhí)行。狀態(tài)可假設(shè)有兩種狀態(tài)，“就緒”狀態(tài)和“結(jié)束”狀態(tài)。五個(gè)進(jìn)程的初始狀態(tài)都為“就緒”，用“R”表示，當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。(2) 在每次運(yùn)行你所設(shè)計(jì)的處理器調(diào)度程序之前，為每個(gè)進(jìn)程任意確定它的“優(yōu)先數(shù)”和“要求運(yùn)行時(shí)間”。(3) 為了調(diào)度方便，把五個(gè)進(jìn)程按給定的優(yōu)先數(shù)從大到小連成隊(duì)列。用一單元指出隊(duì)首進(jìn)程，用指針指出隊(duì)列的連接情況。例： 隊(duì)首標(biāo)志

3、 K2 K1P1 K2P2 K3P3 K4P4 K5P50K4K5K3K12312415342RRRRRPCB1PCB2PCB3PCB4PCB5(4) 處理器調(diào)度總是選隊(duì)首進(jìn)程運(yùn)行。采用動(dòng)態(tài)改變優(yōu)先數(shù)的辦法，進(jìn)程每運(yùn)行一次優(yōu)先數(shù)就減“1”。由于本實(shí)驗(yàn)是模擬處理器調(diào)度，所以，對(duì)被選中的進(jìn)程并不實(shí)際的啟動(dòng)運(yùn)行，而是執(zhí)行：優(yōu)先數(shù)-1要求運(yùn)行時(shí)間-1來(lái)模擬進(jìn)程的一次運(yùn)行。提醒注意的是：在實(shí)際的系統(tǒng)中，當(dāng)一個(gè)進(jìn)程被選中運(yùn)行時(shí)，必須恢復(fù)進(jìn)程的現(xiàn)場(chǎng)，讓它占有處理器運(yùn)行，直到出現(xiàn)等待事件或運(yùn)行結(jié)束。在這里省去了這些工作。(5) 進(jìn)程運(yùn)行一次后，若要求運(yùn)行時(shí)間¹0，則再將它加入隊(duì)列（按優(yōu)先數(shù)大小插入，

4、且置隊(duì)首標(biāo)志）；若要求運(yùn)行時(shí)間=0，則把它的狀態(tài)修改成“結(jié)束”（E），且退出隊(duì)列。(6) 若“就緒”狀態(tài)的進(jìn)程隊(duì)列不為空，則重復(fù)上面（4）和（5）的步驟，直到所有進(jìn)程都成為“結(jié)束”狀態(tài)。(7) 在所設(shè)計(jì)的程序中應(yīng)有顯示或打印語(yǔ)句，能顯示或打印每次被選中進(jìn)程的進(jìn)程名以及運(yùn)行一次后進(jìn)程隊(duì)列的變化。(8) 為五個(gè)進(jìn)程任意確定一組“優(yōu)先數(shù)”和“要求運(yùn)行時(shí)間”，啟動(dòng)所設(shè)計(jì)的處理器調(diào)度程序，顯示或打印逐次被選中進(jìn)程的進(jìn)程名以及進(jìn)程控制塊的動(dòng)態(tài)變化過(guò)程。第二題：設(shè)計(jì)一個(gè)按時(shí)間片輪轉(zhuǎn)法實(shí)現(xiàn)處理器調(diào)度的程序。提示：(1) 假定系統(tǒng)有五個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來(lái)代表。進(jìn)程控制塊的格式為：進(jìn)程名指針

5、要求運(yùn)行時(shí)間已運(yùn)行時(shí)間狀態(tài)其中，進(jìn)程名作為進(jìn)程的標(biāo)識(shí)，假設(shè)五個(gè)進(jìn)程的進(jìn)程名分別為Q1，Q2，Q3，Q4，Q5。指針進(jìn)程按順序排成循環(huán)隊(duì)列，用指針指出下一個(gè)進(jìn)程的進(jìn)程控制塊的首地址，最后一個(gè)進(jìn)程的指針指出第一個(gè)進(jìn)程的進(jìn)程控制塊首地址。要求運(yùn)行時(shí)間假設(shè)進(jìn)程需要運(yùn)行的單位時(shí)間數(shù)。已運(yùn)行時(shí)間假設(shè)進(jìn)程已經(jīng)運(yùn)行的單位時(shí)間數(shù)，初始值為“0”。狀態(tài)有兩種狀態(tài)，“就緒”和“結(jié)束”，初始狀態(tài)都為“就緒”，用“R”表示。當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。(2) 每次運(yùn)行所設(shè)計(jì)的處理器調(diào)度程序前，為每個(gè)進(jìn)程任意確定它的“要求運(yùn)行時(shí)間”。(3) 把五個(gè)進(jìn)程按順序排成循環(huán)隊(duì)列，用指針指出隊(duì)列連接情況

6、。另用一標(biāo)志單元記錄輪到運(yùn)行的進(jìn)程。例如，當(dāng)前輪到P2執(zhí)行，則有：標(biāo)志單元 K2 K1Q1 K2Q2 K3Q3 K4Q4 K5Q5K2K3K4K5K12312410000RRRRRPCB1PCB2PCB3PCB4PCB5(4) 處理器調(diào)度總是選擇標(biāo)志單元指示的進(jìn)程運(yùn)行。由于本實(shí)驗(yàn)是模擬處理器調(diào)度的功能，所以，對(duì)被選中的進(jìn)程并不實(shí)際的啟動(dòng)運(yùn)行，而是執(zhí)行：已運(yùn)行時(shí)間+1來(lái)模擬進(jìn)程的一次運(yùn)行，表示進(jìn)程已經(jīng)運(yùn)行過(guò)一個(gè)單位的時(shí)間。請(qǐng)同學(xué)注意：在實(shí)際的系統(tǒng)中，當(dāng)一個(gè)進(jìn)程被選中運(yùn)行時(shí)，必須置上該進(jìn)程可以運(yùn)行的時(shí)間片值，以及恢復(fù)進(jìn)程的現(xiàn)場(chǎng)，讓它占有處理器運(yùn)行，直到出現(xiàn)等待事件或運(yùn)行滿一個(gè)時(shí)間片。在這時(shí)省去了這

7、些工作，僅用“已運(yùn)行時(shí)間+1”來(lái)表示進(jìn)程已經(jīng)運(yùn)行滿一個(gè)時(shí)間片。(5) 進(jìn)程運(yùn)行一次后，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到標(biāo)志單元，以指示下一個(gè)輪到運(yùn)行的進(jìn)程。同時(shí)，應(yīng)判斷該進(jìn)程的要求運(yùn)行時(shí)間與已運(yùn)行時(shí)間，若該進(jìn)程的要求運(yùn)行時(shí)間¹已運(yùn)行時(shí)間，則表示它尚未執(zhí)行結(jié)束，應(yīng)待到下一輪時(shí)再運(yùn)行。若該進(jìn)程的要求運(yùn)行時(shí)間=已運(yùn)行時(shí)間，則表示它已經(jīng)執(zhí)行結(jié)束，應(yīng)指導(dǎo)它的狀態(tài)修改成“結(jié)束”（E）且退出隊(duì)列。此時(shí)，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到前面一個(gè)進(jìn)程的指針位置。(6) 若“就緒”狀態(tài)的進(jìn)程隊(duì)列不為空，則重復(fù)上面的（4）和（5）的步驟，直到所有的進(jìn)程都成為“結(jié)束”狀態(tài)。(7) 在所設(shè)計(jì)的程序中應(yīng)

8、有顯示或打印語(yǔ)句，能顯示或打印每次選中進(jìn)程的進(jìn)程名以及運(yùn)行一次后進(jìn)程隊(duì)列的變化。(8) 為五個(gè)進(jìn)程任意確定一組“要求運(yùn)行時(shí)間”，啟動(dòng)所設(shè)計(jì)的處理器調(diào)度程序，顯示或打印逐次被選中的進(jìn)程名以及進(jìn)程控制塊的動(dòng)態(tài)變化過(guò)程。長(zhǎng)春大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告日期_ 地點(diǎn)_ 指導(dǎo)教師_ 成績(jī) 實(shí)驗(yàn)三 處理器調(diào)度一、寫(xiě)出程序代碼并分析運(yùn)行結(jié)果#include <stdio.h>#include<stdlib.h>#include<malloc.h>typedef struct DATAchar pname10;/進(jìn)程名float time;/要求運(yùn)行時(shí)間數(shù)int ove;

9、/優(yōu)先級(jí)char flag;/狀態(tài)DATA; typedef struct pcbDATA data;struct pcb *next;pcb;int flag=5;/假設(shè)有五個(gè)進(jìn)程pcb* init(pcb *p)/初始化p=(pcb *)malloc(sizeof(DATA);p->next = NULL;return p;void show(pcb *p)/輸出顯示if(!flag)printf("n沒(méi)有正在運(yùn)行的進(jìn)程，或進(jìn)程已經(jīng)全部執(zhí)行完畢。n");elseprintf("n名稱");printf("");printf(

10、"執(zhí)行時(shí)間");printf("" );printf("優(yōu)先數(shù)");printf("" );printf("狀態(tài)n");while(p->next)p=p->next ;printf("%s",p->data .pname );printf(" ");printf("%1.0f",p->data .time );printf(" " );printf("%d",p->

11、data .ove );printf(" " );printf("%cnn",p->data .flag );void del(pcb *h)/進(jìn)程執(zhí)行完成后的刪除pcb *p;p=h;p=p->next;if(p->data .flag ='E')printf("有一個(gè)進(jìn)程執(zhí)行完成：n");printf("進(jìn)程的名稱為：%sn",p->data .pname);p=p->next;h->next =p;flag-;void in(pcb *h)/從鍵盤(pán)中輸入數(shù)據(jù)

12、int i=0;pcb *pc,*l;pc=h;printf("請(qǐng)依次輸入五個(gè)進(jìn)程的名稱、執(zhí)行時(shí)間、優(yōu)先數(shù)：（輸入時(shí)進(jìn)程與進(jìn)程之間用回車(chē)來(lái)隔開(kāi)?。﹏");for(i;i<flag;i+)l=init(l);scanf("%s%f%d",&l->data .pname ,&l->data .time ,&l->data .ove );rewind(stdin);if(!l->data .time )l->data .flag ='E'elsel->data .flag=

13、9;R'l->next =NULL;pc->next =l;pc=pc->next ;void soar(pcb *p)/對(duì)于這五個(gè)進(jìn)程按其優(yōu)先級(jí)進(jìn)行排序pcb *q;pcb *h;int i=0;int j;q=init(q);h=p->next ;for(i;i<flag;i+)for(j=0;j<(flag-1);j+)if(h->data .time )if(h->data .ove<h->next ->data .ove )q->data =h->data ;h->data =h->ne

14、xt->data ;h->next->data =q->data ;h=h->next ;elseprintf("有一個(gè)進(jìn)程執(zhí)行完成：n");printf("進(jìn)程的名稱為：%sn",h->data .pname);flag-;h=p->next ;if(flag)printf("n目前優(yōu)先級(jí)最高的進(jìn)程的名稱是：%sn所以執(zhí)行此進(jìn)程！",p->next ->data .pname );void run(pcb *h)/執(zhí)行程序h=h->next;h->data .time

15、 -;h->data .ove -;if(!h->data .time )h->data .flag ='E'void main()pcb *p;char c;p=init(p);in(p);soar(p);show(p);del(p);while(flag)run(p);del(p);soar(p);show(p);c=getch();rewind(stdin);程序運(yùn)行時(shí)的初值a 1 2b 3 4 c 5 6d 3 1e 5 5運(yùn)行結(jié)果： 進(jìn)程控制塊的初始狀態(tài)。 RRRRR 按同一順序訪問(wèn)對(duì)象。    如果所有并發(fā)事務(wù)按同一順

16、序訪問(wèn)對(duì)象，則發(fā)生死鎖的可能性會(huì)降低。例如，如果兩個(gè)并發(fā)事務(wù)獲得   Supplier   表上的鎖，然后獲得   Part   表上的鎖，則在其中一個(gè)事務(wù)完成之前，另一個(gè)事務(wù)被阻塞在   Supplier   表上。第一個(gè)事務(wù)提交或回滾后，第二個(gè)事務(wù)繼續(xù)進(jìn)行。不發(fā)生死鎖。將存儲(chǔ)過(guò)程用于所有的數(shù)據(jù)修改可以標(biāo)準(zhǔn)化訪問(wèn)對(duì)象的順序          避免事務(wù)中的用戶交互。    避免編寫(xiě)包含用戶交互的事務(wù)，因?yàn)檫\(yùn)行沒(méi)有用戶交互的批處理的速度要遠(yuǎn)遠(yuǎn)快于用戶手動(dòng)響應(yīng)

17、查詢的速度，例如答復(fù)應(yīng)用程序請(qǐng)求參數(shù)的提示。例如，如果事務(wù)正在等待用戶輸入，而用戶去吃午餐了或者甚至回家過(guò)周末了，則用戶將此事務(wù)掛起使之不能完成。這樣將降低系統(tǒng)的吞吐量，因?yàn)槭聞?wù)持有的任何鎖只有在事務(wù)提交或回滾時(shí)才會(huì)釋放。即使不出現(xiàn)死鎖的情況，訪問(wèn)同一資源的其它事務(wù)也會(huì)被阻塞，等待該事務(wù)完成。       保持事務(wù)簡(jiǎn)短并在一個(gè)批處理中。    在同一數(shù)據(jù)庫(kù)中并發(fā)執(zhí)行多個(gè)需要長(zhǎng)時(shí)間運(yùn)行的事務(wù)時(shí)通常發(fā)生死鎖。事務(wù)運(yùn)行時(shí)間越長(zhǎng)，其持有排它鎖或更新鎖的時(shí)間也就越長(zhǎng)，從而堵塞了其它活動(dòng)并可能導(dǎo)致死鎖。      &

18、#160;保持事務(wù)在一個(gè)批處理中，可以最小化事務(wù)的網(wǎng)絡(luò)通信往返量，減少完成事務(wù)可能的延遲并釋放鎖          使用低隔離級(jí)別。    確定事務(wù)是否能在更低的隔離級(jí)別上運(yùn)行。執(zhí)行提交讀允許事務(wù)讀取另一個(gè)事務(wù)已讀?。ㄎ葱薷模┑臄?shù)據(jù)，而不必等待第一個(gè)事務(wù)完成。使用較低的隔離級(jí)別（例如提交讀）而不使用較高的隔離級(jí)別（例如可串行讀）可以縮短持有共享鎖的時(shí)間，從而降低了鎖定爭(zhēng)奪       使用綁定連接。    使用綁定連接使同一應(yīng)用程序所打開(kāi)的兩個(gè)或多個(gè)連接可

19、以相互合作。次級(jí)連接所獲得的任何鎖可以象由主連接獲得的鎖那樣持有，反之亦然，因此不會(huì)相互阻塞 選中運(yùn)行的進(jìn)程名以及選中進(jìn)程運(yùn)行后的各進(jìn)程控制塊狀態(tài)。EEEEE二、思考題1、試比較FCFS和SPF兩種進(jìn)程調(diào)度算法。答:FCFS每次調(diào)度從進(jìn)程隊(duì)列中選擇最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，運(yùn)行。 SPF是從隊(duì)列中選擇運(yùn)行時(shí)間最短的作業(yè)，優(yōu)先調(diào)入內(nèi)存運(yùn)行。但是SPF必須預(yù)知 作業(yè)的運(yùn)行時(shí)間，一般會(huì)偏長(zhǎng)估計(jì)，而且對(duì)長(zhǎng)作業(yè)不利，容易出現(xiàn)饑餓現(xiàn)象。該調(diào) 度算法完全未考慮作業(yè)的緊迫程度，故不能保證緊迫性作業(yè)得到及時(shí)處理2、 請(qǐng)?jiān)敿?xì)說(shuō)明可通過(guò)哪些途徑預(yù)防死鎖。 答： 死鎖發(fā)生的條件： 1、資源不能共享，需要只

20、能由一個(gè)進(jìn)程或者線程使用 2、請(qǐng)求且保持，已經(jīng)鎖定的資源自給保持著不釋放 3、不剝奪，自給申請(qǐng)到的資源不能被別人剝奪 4、循環(huán)等待 想預(yù)防死鎖，把上面四個(gè)條件破壞一個(gè)就可以了。 可以利用銀行家算法。 按同一順序訪問(wèn)對(duì)象。    如果所有并發(fā)事務(wù)按同一順序訪問(wèn)對(duì)象，則發(fā)生死鎖的可能性會(huì)降低。例如，如果兩個(gè)并發(fā)事務(wù)獲得   Supplier   表上的鎖，然后獲得   Part   表上的鎖，則在其中一個(gè)事務(wù)完成之前，另一個(gè)事務(wù)被阻塞在   Supplier   表上。第一個(gè)事務(wù)提交或回滾后，第二個(gè)事務(wù)繼續(xù)進(jìn)行。不發(fā)生死鎖。將存儲(chǔ)過(guò)程用于所有的數(shù)據(jù)修改可以標(biāo)準(zhǔn)化訪問(wèn)對(duì)象的順序          避免事務(wù)中的用戶交互。    避免編寫(xiě)包含用戶交互