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

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

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

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

4、錄：程序及注釋（用紅色黑體標(biāo)注自己設(shè)計的函數(shù)）/進程PCB類和模擬cpu的進程類的聲明#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 /待測試的哲學(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();/形參的改變映射給實參 說白了就是實參傳過去不用return 返回就可以把實參改變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(" 模擬進程調(diào)度算法n"); printf(" * nnn"); printf("靜態(tài)優(yōu)先級調(diào)度算法"); printf("死鎖問題"); printf("按回車鍵進入演示程序"); getchar(); system("cls");system("cls");char Choice() printf("nn"); printf(&qu

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

9、cls");void HighPriority() struct PCB *processes, *pt; /pt作為臨時節(jié)點來創(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("進程號No.%d：n", i); printf("輸入進程名："); scanf("%s",

10、p->p_name); printf("輸入進程優(yōu)先數(shù)："); scanf("%d", &p->p_priority); printf("輸入進程運行時間："); 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é)點來存儲鏈表 processes = processes->next; int cases = 0; struct PCB *psorted = processes; while (1) +cases; pt = processes; /對鏈表按照優(yōu)先數(shù)排序 /psorted用來存放排序后的鏈表 psorted = SortList(psorted); printf("The execute number: %dnn", cases); printf("* 當(dāng)前正在運行的進程是：%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)的隊列為：nn"); /pt指向已經(jīng)排序的隊列 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)排序的鏈表，判斷鏈表是否有已用時間啊等于需要時間的 pt = psorted; struct PCB *ap; ap = NULL; /ap指向pt的前一個節(jié)點 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ù)組，每根筷子需要一個互斥體int thread_numberMAX_PHILOSOPHERS=1,2,3;/定義死鎖的個數(shù)/會產(chǎn)生死鎖的哲學(xué)家線程int deadlock_philosopher(LPVOID data)int ph

17、ilosopher_number=*(int *)(data); /哲學(xué)家編號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;/死鎖時的初始化程序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");/通過按序分配資源預(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);