靜態(tài)優(yōu)先級(jí)調(diào)度算法

1、_ 成績(jī)（五級(jí)制）：_武漢科技大學(xué)城市學(xué)院操作系統(tǒng)實(shí)驗(yàn)報(bào)告院 系 武漢科技的大學(xué)城市學(xué)院學(xué)生專業(yè) 信科年級(jí) 班 大三課程名稱 操作系統(tǒng)實(shí)驗(yàn)題目 進(jìn)程調(diào)度學(xué)生姓名 宋騁指導(dǎo)教師 郭冀生2013年 11 月 4 日實(shí)驗(yàn)二 進(jìn)程調(diào)度一、實(shí)驗(yàn)?zāi)康倪M(jìn)程是操作系統(tǒng)最重要的概念之一，進(jìn)程調(diào)度又是操作系統(tǒng)核心的重要內(nèi)容。通過(guò)該實(shí)驗(yàn)，要求同學(xué)們了解各進(jìn)程在執(zhí)行過(guò)程中的狀態(tài)和參數(shù)的變化情況，以便于觀察諸進(jìn)程的調(diào)度過(guò)程。二、實(shí)驗(yàn)內(nèi)容及要求 按剝奪式優(yōu)先數(shù)法對(duì)三個(gè)進(jìn)程P1,p2,p3進(jìn)行模擬調(diào)度，各進(jìn)程的優(yōu)先數(shù)靜態(tài)設(shè)置，其中P1的優(yōu)先數(shù)最高，P3的優(yōu)先數(shù)最低。每個(gè)進(jìn)程都處于執(zhí)行E(execute),就緒R(ready

2、)和等待W(wait)三種狀態(tài)之一，并假定初始狀態(tài)均為R.。三個(gè)進(jìn)程有如下同步關(guān)系：P1因等待事件1被阻塞后由P2發(fā)現(xiàn)并喚醒之，P2因等待事件2被阻塞后由P3發(fā)現(xiàn)并喚醒之。當(dāng)系統(tǒng)進(jìn)入運(yùn)行，在完成必要的初始化工作以后便進(jìn)入進(jìn)程調(diào)度，首先選擇優(yōu)先數(shù)最高的進(jìn)程使其進(jìn)入執(zhí)行（分配CPU）。當(dāng)執(zhí)行進(jìn)程因等待某個(gè)事件被阻塞或喚醒某個(gè)等待進(jìn)程時(shí)，轉(zhuǎn)入進(jìn)程調(diào)度。如果被喚醒的進(jìn)程的優(yōu)先數(shù)大于現(xiàn)行的執(zhí)行進(jìn)程，則剝奪現(xiàn)行進(jìn)程的執(zhí)行權(quán)，而將CPU分配給被喚醒的進(jìn)程。當(dāng)系統(tǒng)處于死鎖或三個(gè)進(jìn)程都執(zhí)行完畢時(shí)系統(tǒng)退出運(yùn)行。系統(tǒng)中應(yīng)用到如下數(shù)據(jù)結(jié)構(gòu)：*進(jìn)程控制塊PCB；*信號(hào)量sem；*其它需要的數(shù)據(jù)結(jié)構(gòu)。由自己設(shè)計(jì)。三、實(shí)驗(yàn)

3、原理及步驟 根據(jù)現(xiàn)代操作系統(tǒng)的特征1并發(fā)性（concurrence)；2共享性(sharing)；3虛擬性(virtual)；4異步性(asynchronism) 。模擬出進(jìn)程在執(zhí)行中的狀態(tài)變化過(guò)程；體會(huì)進(jìn)程申請(qǐng)資源、使用資源、歸還資源；體會(huì)死鎖。步驟（參考框圖）4、算法和流程圖可強(qiáng)占優(yōu)先調(diào)度算法實(shí)現(xiàn)過(guò)程流程圖（如下圖）： 四、程序運(yùn)行1 選擇輸入執(zhí)行程序（如下圖）2 可強(qiáng)占優(yōu)先調(diào)度算法圖（如下圖）五.設(shè)計(jì)總結(jié)：通過(guò)該課程設(shè)計(jì)，加深了對(duì)系統(tǒng)進(jìn)程調(diào)度機(jī)制的理解。在搶占方式中實(shí)踐了“搶占” 必須遵循的原則：優(yōu)先權(quán)原則。認(rèn)識(shí)了幾種進(jìn)程調(diào)度算法的優(yōu)缺點(diǎn)以及應(yīng)用范圍。加強(qiáng)C+的編程能力，實(shí)現(xiàn)類的封裝。附

4、錄：程序及注釋（用紅色黑體標(biāo)注自己設(shè)計(jì)的函數(shù)）/進(jìn)程PCB類和模擬cpu的進(jìn)程類的聲明#include <stdio.h>#include <stdlib.h>#include <windows.h>#include <conio.h>#include <stdlib.h>#include <stdio.h>#include <time.h>#include <io.h>#include <string.h>#define MAX_PHILOSOPHERS 3 /待測(cè)試的哲學(xué)家數(shù)#def

5、ine ZERO 48 /數(shù)字0的ASCII碼#define DELAY rand()%25struct PCB char p_name20; int p_priority; int p_needTime; int p_runTime; char p_state;char deadlock(); struct PCB* next;void HighPriority();void deadlock();void Information();/形參的改變映射給實(shí)參 說(shuō)白了就是實(shí)參傳過(guò)去不用return 返回就可以把實(shí)參改變char Choice();struct PCB* SortList(PCB

6、* HL);int main(int argc,char *argv) Information(); char choice = Choice(); switch(choice) case '1': system("cls"); HighPriority(); break; case '2': system("cls"); void deadlock(); break; default: break; system("pause"); return 0;void Information() printf

7、("nn"); printf(" * n"); printf(" 模擬進(jìn)程調(diào)度算法n"); printf(" * nnn"); printf("靜態(tài)優(yōu)先級(jí)調(diào)度算法"); printf("死鎖問題"); printf("按回車鍵進(jìn)入演示程序"); getchar(); system("cls");system("cls");char Choice() printf("nn"); printf(&qu

8、ot; * n"); printf(" 進(jìn)程調(diào)度演示n"); printf(" * nnn"); printf(" 1.演示最高優(yōu)先數(shù)優(yōu)先算法。n"); printf(" 2.演示死鎖問題。n"); printf(" 3.退出程序。nnnn"); printf(" 選擇進(jìn)程調(diào)度方法:"); printf("select a function(13):"); char ch = getchar(); return ch; system("

9、cls");void HighPriority() struct PCB *processes, *pt; /pt作為臨時(shí)節(jié)點(diǎn)來(lái)創(chuàng)建鏈表 processes = pt = (struct PCB*)malloc(sizeof(struct PCB); for (int i = 1; i != 4; +i) struct PCB *p = (struct PCB*)malloc(sizeof(struct PCB); printf("進(jìn)程號(hào)No.%d：n", i); printf("輸入進(jìn)程名："); scanf("%s",

10、p->p_name); printf("輸入進(jìn)程優(yōu)先數(shù)："); scanf("%d", &p->p_priority); printf("輸入進(jìn)程運(yùn)行時(shí)間："); scanf("%d", &p->p_needTime); p->p_runTime = 0; p->p_state = 'W' p->next = NULL; pt->next = p; pt = p; printf("nn"); getchar(); /接受回

11、車 /processes作為頭結(jié)點(diǎn)來(lái)存儲(chǔ)鏈表 processes = processes->next; int cases = 0; struct PCB *psorted = processes; while (1) +cases; pt = processes; /對(duì)鏈表按照優(yōu)先數(shù)排序 /psorted用來(lái)存放排序后的鏈表 psorted = SortList(psorted); printf("The execute number: %dnn", cases); printf("* 當(dāng)前正在運(yùn)行的進(jìn)程是：%sn", psorted->p

12、_name); psorted->p_state = 'R' printf("qname state super ndtime runtimen"); printf("%st%ct%dt%dt%dtnn", psorted->p_name, psorted->p_state, psorted->p_priority, psorted->p_needTime, psorted->p_runTime); pt->p_state = 'W' psorted->p_runTime+;

13、 psorted->p_priority-; printf("* 當(dāng)前就緒狀態(tài)的隊(duì)列為：nn"); /pt指向已經(jīng)排序的隊(duì)列 pt = psorted->next; while (pt != NULL) printf("qname state super ndtime runtimen"); printf("%st%ct%dt%dt%dtnn", pt->p_name, pt->p_state, pt->p_priority, pt->p_needTime, pt->p_runTime); p

14、t = pt->next; /pt指向已經(jīng)排序的鏈表，判斷鏈表是否有已用時(shí)間啊等于需要時(shí)間的 pt = psorted; struct PCB *ap; ap = NULL; /ap指向pt的前一個(gè)節(jié)點(diǎn) while (pt != NULL) if (pt->p_needTime = pt->p_runTime) if (ap = NULL) pt = psorted->next; psorted = pt; else ap->next = pt->next; ap = pt; pt = pt->next; if (psorted->next =

15、NULL) break; getchar(); struct PCB* SortList(PCB* HL) struct PCB* SL; SL = (struct PCB*)malloc(sizeof(struct PCB); SL = NULL; struct PCB* r = HL; while (r != NULL) struct PCB* t = r->next; struct PCB* cp = SL; struct PCB* ap = NULL; while (cp != NULL) if (r->p_priority > cp->p_priority)

16、break; else ap = cp; cp = cp->next; if (ap = NULL) r->next = SL; SL = r; else r->next = cp; ap->next = r; r = t; return SL;/HANDLE h_mutex_chopsticksMAX_PHILOSOPHERS; /互斥體數(shù)組，每根筷子需要一個(gè)互斥體int thread_numberMAX_PHILOSOPHERS=1,2,3;/定義死鎖的個(gè)數(shù)/會(huì)產(chǎn)生死鎖的哲學(xué)家線程int deadlock_philosopher(LPVOID data)int ph

17、ilosopher_number=*(int *)(data); /哲學(xué)家編號(hào)for(;)srand( (unsigned)time( NULL ) * ( philosopher_number+ 1) ); Sleep(DELAY); printf("%s%c%s%cn","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",(ZERO+philosopher_number); WaitForSingleObject(h_mutex_chopsticksphi

18、losopher_number, INFINITE); printf("%s%c%s%cn","Philosopher ",ZERO+philosopher_number," got chopstick ",(ZERO+philosopher_number);Sleep(DELAY/4);printf("%s%c%s%cn","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",(ZERO+(1+phi

19、losopher_number)%MAX_PHILOSOPHERS); WaitForSingleObject(h_mutex_chopsticks(1+philosopher_number)%MAX_PHILOSOPHERS), INFINITE); printf("%s%c%s%cn","Philosopher ",ZERO+philosopher_number," got chopstick ",(ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS); printf("%s%c%s

20、n","Philosopher ",ZERO+philosopher_number," is eating."); Sleep(DELAY); ReleaseMutex(h_mutex_chopsticksphilosopher_number);printf("%s%c%s%cn","Philosopher ",ZERO+philosopher_number," released chopstick ",ZERO+philosopher_number); ReleaseMutex(h_

21、mutex_chopsticks(1+philosopher_number)%MAX_PHILOSOPHERS);printf("%s%c%s%cn","Philosopher ",ZERO+philosopher_number," released chopstick ",(ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS); Sleep(DELAY); / end forreturn 0;/死鎖時(shí)的初始化程序void deadlock()char choice;int i=0;HANDLE

22、h_threadMAX_PHILOSOPHERS;printf("可能出現(xiàn)死鎖的哲學(xué)家就餐問題n");for(i=0;i<MAX_PHILOSOPHERS;i+)h_mutex_chopsticksi=CreateMutex(NULL,FALSE,NULL);for(i=0;i<MAX_PHILOSOPHERS;i+)h_threadi=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(deadlock_philosopher),&thread_numberi,0,NULL);WaitForMultipleObje

23、cts(MAX_PHILOSOPHERS,h_thread,TRUE,-1);dochoice=(char)getch();while( choice!='2');system("cls");deadlock();printf("nPress any key to return to main menu.");getch();system("cls");/通過(guò)按序分配資源預(yù)防死鎖的哲學(xué)家線程int ordered_allocation_philosopher(LPVOID data)int philosopher_nu

24、mber=*(int *)(data);for(;)srand( (unsigned)time( NULL ) * ( philosopher_number+ 1) ); Sleep(DELAY);if(philosopher_number=MAX_PHILOSOPHERS-1) printf("%s%c%s%cn","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",(ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS)

25、; WaitForSingleObject(h_mutex_chopsticks(1+philosopher_number)%MAX_PHILOSOPHERS, INFINITE); Sleep(DELAY/4); printf("%s%c%s%cn","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+philosopher_number); WaitForSingleObject(h_mutex_chopsticksphilosopher_num

26、ber, INFINITE);else printf("%s%c%s%cn","Philosopher ",ZERO+philosopher_number," is waiting chopstick ",ZERO+philosopher_number); WaitForSingleObject(h_mutex_chopsticksphilosopher_number, INFINITE); Sleep(DELAY/4); printf("%s%c%s%cn","Philosopher ",ZE

27、RO+philosopher_number," is waiting chopstick ",ZERO+(1+philosopher_number)%MAX_PHILOSOPHERS); WaitForSingleObject(h_mutex_chopsticks(1+philosopher_number)%MAX_PHILOSOPHERS, INFINITE); printf("%s%c%sn","Philosopher ",ZERO+philosopher_number," is eating."); Sleep(DELAY); printf("%s%c%s%cn","Philosopher ",ZERO+philosopher_number," is releasing chopstick ",ZERO+philosopher_number);