第一篇：處理機調(diào)度與死鎖小結(jié)

第三章 處理機調(diào)度與死鎖

重點與難點小結(jié)

1.高優(yōu)先權調(diào)度和基于時間片的輪轉(zhuǎn)調(diào)度算法

1)高優(yōu)先權優(yōu)先調(diào)度

2)高響應比優(yōu)先調(diào)度

3)時間片輪轉(zhuǎn)調(diào)度

4)多級反饋隊列調(diào)度

2.常用的幾種實時調(diào)度算法

1)最早截止時間優(yōu)先(EDF)算法

2)最低松弛度優(yōu)先(LLF)算法

3.多處理機環(huán)境下的進程（線程）調(diào)度方式

1)自調(diào)度方式

2)成組調(diào)度方式

3)專用處理器分配方式

4.死鎖的基本概念

1)產(chǎn)生死鎖的原因

2)產(chǎn)生死鎖的必要條件

5.預防死鎖的方法

1)摒棄互斥條件

2)摒棄請求保持條件

3)摒棄不剝奪條件

4)摒棄環(huán)路等待條件

5)各種方式的比較

6.死鎖的避免

熟練掌握銀行家算法和安全性檢測算法，并能利用這兩個算法求解具體問題

第二篇：第三章 處理機調(diào)度與死鎖小結(jié)

第三章 處理機調(diào)度與死鎖

重點與難點小結(jié)

1.高優(yōu)先權調(diào)度和基于時間片的輪轉(zhuǎn)調(diào)度算法

1)

2)

3)時間片輪轉(zhuǎn)調(diào)度

4)多級反饋隊列調(diào)度

2.常用的幾種實時調(diào)度算法

1)最早截止時間優(yōu)先(EDF)算法

2)最低松弛度優(yōu)先(LLF)算法

3.死鎖的基本概念

1)2)4.預防死鎖的方法

1)摒棄互斥條件

2)摒棄請求保持條件

3)摒棄不剝奪條件

4)摒棄環(huán)路等待條件

5)各種方式的比較

5.死鎖的避免 熟練掌握銀行家算法和安全性檢測算法，并能利用這兩個算法求解具體問題

6．死鎖定理

第三篇：操作系統(tǒng)-課程設計報告-處理機調(diào)度程序

操作系統(tǒng)

課程設計報告

學校：廣州大學

學院：計算機科學與教育軟件學院 班級：計算機127班 課題：處理機調(diào)度程序

任課老師：陶文正、陳文彬

姓名：黃俊鵬

學號：1200002111 班內(nèi)序號：27 成績：

日期：2015年1月6日

一、設計目的

在多道程序和多任務系統(tǒng)中，系統(tǒng)內(nèi)同時處于就緒狀態(tài)的進程可能有若干個。也就是說能運行的進程數(shù)大于處理機個數(shù)。為了使系統(tǒng)中的進程能有條不紊地工作，必須選用某種調(diào)度策略，選擇一進程占用處理機。要求學生設計一個模擬處理機調(diào)度算法，以鞏固和加深處理機調(diào)度的概念。

二、設計要求

1）進程調(diào)度算法包括：時間片輪轉(zhuǎn)法，短作業(yè)優(yōu)先算法，動態(tài)優(yōu)先級算法。2）可選擇進程數(shù)量

3）本程序包括三種算法，用C語言實現(xiàn)，執(zhí)行時在主界面選擇算法（可用函數(shù)實現(xiàn)）（進程數(shù)，運行時間，優(yōu)先數(shù)由隨機函數(shù)產(chǎn)生）執(zhí)行，顯示結(jié)果。

三、設計思路及算法思想

1.界面菜單選項

一級菜單提供2個選項： ① 自動生成進程數(shù)量 ② 手動輸入所需進程數(shù)量

一級菜單選擇完畢后進入二級菜單： ① 重新生成進程 ② 時間片輪轉(zhuǎn)法 ③ 短作業(yè)優(yōu)先算法 ④ 動態(tài)優(yōu)先級算法 ⑤ 退出程序

2.調(diào)度算法

程序所用PCB結(jié)構體

需要用到的進程結(jié)構體如上圖所示

1)時間片輪轉(zhuǎn)法

主要是設置一個當前時間變量，curTime和時間片roundTime。

遍歷進程組的時候，每運行一個進程，就把curTime += roundTime。進程已運行時間加roundTime

2)短作業(yè)優(yōu)先算法

遍歷進程組，找到未運行完成并且運行時間最短的進程，讓它一次運行完成，如此往復，直到所有進程都運行完成為止。

3)動態(tài)優(yōu)先級算法

做法跟短作業(yè)優(yōu)先算法類似，此處主要是比較進程的優(yōu)先數(shù)，優(yōu)先級高者，先執(zhí)行。直到全部執(zhí)行完畢。當一個進程運行完畢后，適當增減其余進程的優(yōu)先數(shù)，以達到動態(tài)調(diào)成優(yōu)先級的效果。

3.程序流程圖

四、運行截圖

1）啟動后輸入5，生成5個進程

2）輸入1，選擇時間片輪轉(zhuǎn)法。

自動輸出結(jié)果，分別是時間片為1和4的結(jié)果

3）輸入2，選擇短作業(yè)優(yōu)先算法

4）輸入3，選擇動態(tài)優(yōu)先級算法

5）輸入0，重新生成進程，再輸入3，生成3個進程，選擇2.短作業(yè)優(yōu)先算法

6）輸入q，退出

五、心得體會

通過這次實驗，讓我對操作系統(tǒng)的進程調(diào)度有了更進一步的了解。這個實驗的模擬程度跟真實系統(tǒng)相比只是冰山一角，由此可見操作系統(tǒng)是何其復雜的軟件產(chǎn)品，僅進程調(diào)度就有那么豐富和內(nèi)涵的知識需要掌握。

但是再復雜的系統(tǒng)，都是由小部件構成的。古語云：不積跬步,無以至千里。不積小流,無以成江海。掌握這些基礎的知識，可以為以后打下扎實的基礎。

六、附錄（源代碼）

//

// main.c

// ProcessDispatch //

// Created by Jeans on 1/5/15.// Copyright(c)2015 Jeans.All rights reserved.//

#include #include

//最小進程數(shù)

#define MIN_PROCESS //最大進程數(shù)

#define MAX_PROCESS

//最小優(yōu)先數(shù)

#define MIN_PRIORITY

0 //最大優(yōu)先數(shù)

#define MAX_PRIORITY

//最小運行時間

#define MIN_RUNNING_TIME

//最大運行時間

#define MAX_RUNNING_TIME

typedef struct PCB{

char name;

//進程名

int priority;

//優(yōu)先數(shù)

int runningTime;

//運行時間

int arriveTime;

//到達時間

int beginTime;

//開始時間

int finishTime;

//完成時間

int cyclingTime;

//周轉(zhuǎn)時間

double weigthCyclingTime;//帶權周轉(zhuǎn)時間

int hadRunTime;

//已經(jīng)運行時間

int finish;

//是否完成 }PCB;//獲取隨機數(shù)

int GetRandomNumber(int min,int max){

return arc4random()%(max-min)+ min;}

//初始化PCB組

void InitPCBGroup(PCB p[],int num){

char name = 'A';

for(int i = 0;i < num;i++){

p[i].name = name;

p[i].priority = GetRandomNumber(MIN_PRIORITY, MAX_PRIORITY);

p[i].runningTime = GetRandomNumber(MIN_RUNNING_TIME,MAX_RUNNING_TIME);

name++;

} }

void PrintResult(PCB p[],int num){

double avgCycTime = 0,avgWeiCycTime = 0;

printf(“|進程名

到達時間

運行時間

開始時間

完成時間

周轉(zhuǎn)時間

帶權周轉(zhuǎn)時間

優(yōu)先數(shù)

|n”);

for(int i = 0;i < num;i++){

printf(“|%3c

%-4d

%-4d

%-4d

%-4d

%-4d

%-6.2f

%-4d|n”,p[i].name,p[i].arriveTime,p[i].runningTime,p[i].beginTime,p[i].finishTime,p[i].cyclingTime,p[i].weigthCyclingTime,p[i].priority);

avgCycTime += p[i].cyclingTime;

avgWeiCycTime += p[i].weigthCyclingTime;

//還原

p[i].arriveTime = 0;

p[i].beginTime = 0;

p[i].finishTime = 0;

p[i].cyclingTime = 0;

p[i].weigthCyclingTime = 0;

p[i].hadRunTime = 0;

p[i].finish = 0;

}

avgWeiCycTime /= num;

avgCycTime /= num;

printf(“平均周轉(zhuǎn)時間：%.2f

平均帶權周轉(zhuǎn)時間:%.2fn”,avgCycTime,avgWeiCycTime);} //時間片輪轉(zhuǎn)法

void RealRoundRobin(PCB p[],int num,int roundTime){

printf(“nn-----------------------------時間片：%d------n”,roundTime);

int finishNum = 0;

int curTime = 0;

while(finishNum!= num){

for(int i = 0;i < num;i++){

if(p[i].finish)continue;

//開始時間

if(p[i].beginTime == 0 && i!= 0){

p[i].beginTime = curTime;

}

//已經(jīng)完成

if(p[i].hadRunTime + roundTime >= p[i].runningTime){

p[i].finishTime = curTime + p[i].runningTimep[i].arriveTime;

p[i].weigthCyclingTime = p[i].cyclingTime/(double)p[i].runningTime;

p[i].finish = 1;

finishNum ++;

curTime += p[i].runningTimep[min].arriveTime;

p[min].weigthCyclingTime = p[min].cyclingTime/(double)p[min].runningTime;

p[min].finish = 1;

finishNum++;

curTime = p[min].finishTime;

}

PrintResult(p, num);}

//動態(tài)優(yōu)先級算法

void DynamicPriorityFirst(PCB p[],int num){

printf(“nn-----------------------------動態(tài)優(yōu)先級算法--n”);

int finishNum = 0;

int curTime = 0;

while(finishNum!= num){

int min = 0;

//查找優(yōu)先級最高下標

for(int i = 1;i < num;i++){

if(p[i].finish == 0 && p[min].priority >= p[i].priority)

min = i;

else if(p[i].finish == 0 && p[min].finish == 1)

min = i;

}

p[min].beginTime = curTime;

p[min].hadRunTime = p[min].runningTime;

p[min].finishTime = p[min].beginTime + p[min].runningTime;

p[min].cyclingTime = p[min].finishTime-p[min].arriveTime;

p[min].weigthCyclingTime = p[min].cyclingTime/(double)p[min].runningTime;

p[min].finish = 1;

finishNum++;

curTime = p[min].finishTime;

}

PrintResult(p, num);}

int main(int argc, const char * argv[]){

PCB pcbGroup[30];

//pcb數(shù)組

int processNum = 0;//進程數(shù)

while(1){

//選擇進程數(shù)量

while(1){

if(processNum!= 0)

break;

printf(“n----------n”);

printf(“當前默認進程數(shù)范圍%d--%dn”,MIN_PROCESS,MAX_PROCESS);

printf(“1)輸入0可隨機生成進程數(shù)目n2)輸入%d-%d范圍內(nèi)數(shù)字，回車，可生成指定數(shù)目進程n>>>>>>”,MIN_PROCESS,MAX_PROCESS);

int num = 0;

scanf(“%d”,&num);

if(num == 0){

processNum = GetRandomNumber(MIN_PROCESS, MAX_PROCESS);

break;

}else{

if((num >= MIN_PROCESS)&&(num <= MAX_PROCESS)){

processNum = num;

InitPCBGroup(pcbGroup,processNum);

break;

}else

printf(“n輸入有誤，請重新輸入.n”);

}

}

//選擇算法

printf(“n-----------------------------請輸入對應選項序號-----------------------------n”);

printf(“0.重新生成進程 | 1.時間片輪轉(zhuǎn)法 | 2.短作業(yè)優(yōu)先算法 | 3.動態(tài)優(yōu)先級算法 | q.退出n>>>>>>”);

char ch;

while((ch = getchar())== 'n');

switch(ch){

case '0'://0 重新生成進程

processNum = 0;break;

case '1'://1 時間片輪轉(zhuǎn)法

RoundRobin(pcbGroup, processNum);break;

case '2'://2 短作業(yè)優(yōu)先算法

ShortestJobFirst(pcbGroup, processNum);break;

case '3'://3 動態(tài)優(yōu)先級算法

DynamicPriorityFirst(pcbGroup,processNum);break;

case 'q'://q 退出

exit(0);

default:

break;

}

}

return 0;}

第四篇：操作系統(tǒng) 單處理機系統(tǒng)的進程調(diào)度

一.實驗內(nèi)容描述

1.目的

（1）了解Windows內(nèi)存管理器（2）理解Windows的地址過程 2.內(nèi)容

任意給出一個虛擬地址，通過WinDbg觀察相關數(shù)據(jù)并找到其物理地址

二.理論分析

Windows采用頁式虛擬存儲管理技術管理內(nèi)存，頁面是硬件級別上的最小保護單位 1.Windows內(nèi)存管理器

Windows的內(nèi)存管理主要由Windows執(zhí)行體中的虛存管理程序負責，并由環(huán)境子系統(tǒng)負責，并由環(huán)境子系統(tǒng)負責與具體API相關的一些用戶態(tài)特性的實現(xiàn)。虛存管理程序是Windows中負責內(nèi)存管理的那些子程序和數(shù)據(jù)結(jié)構的集合 內(nèi)存管理器的主要任務是：

地址變換：將一個進程的虛擬地址空間轉(zhuǎn)譯為物理內(nèi)存地址

交換：當內(nèi)存不足時，將內(nèi)存中的有些內(nèi)容轉(zhuǎn)移到磁盤上，并且以后還要再次將這些內(nèi)容讀回

2.Windows內(nèi)存管理策略

Windows采用頁式虛擬存儲管理技術管理內(nèi)存，頁面是硬件級別上最小的保護單位。根據(jù)硬件的體系結(jié)構不同，頁面尺寸被分為兩種，大頁面和小頁面。X86系統(tǒng)下小頁面為4KB，大頁面為4MB。大頁面的優(yōu)點是：當引用同一頁面內(nèi)其他數(shù)據(jù)時，地址轉(zhuǎn)移的速度會很快。不過使用大頁面通常要較大的內(nèi)存空間，而且必須用一個單獨的保護項來映射，因此可能會造成出現(xiàn)錯誤而不引發(fā)內(nèi)存訪問違例的情況。通常PC機都為小頁面 3.Windows虛擬地址空間布局 x86結(jié)構下的布局方式：

默認情況下，32位Windows系統(tǒng)中每個用戶進程可以占有2GB的私有地址空間。操作系統(tǒng)占有另外的2GB 2GB用戶的進程地址空間布局如表：

2GB的系統(tǒng)地址空間布局如同：

3.虛擬地址轉(zhuǎn)譯

地址轉(zhuǎn)譯是指將進程的虛擬地址空間映射到實際物理頁面的過程。x86系統(tǒng)中地址轉(zhuǎn)譯過程如圖：

關鍵數(shù)據(jù)結(jié)構如下： 頁目錄：每個進程都有一個頁目錄，它是內(nèi)存管理器為了映射進程中所有的頁表位置而創(chuàng)建的一個頁面。進程也目錄的地址被保存在內(nèi)核進程快KPROCESS中，在x86系統(tǒng)上，它被映射到虛擬地址0xC0300000，當一個進程正在執(zhí)行時，CPU可以通過寄存器CR3知道該進程頁目錄的位置。頁目錄由目錄項（PDE）構成，每個PDE長4字節(jié)，描述了該進程中所有可能的頁表的狀態(tài)和位置。其格式和PTE類似。x86系統(tǒng)上，要描述完整的4GB虛擬地址空間，需要1024個頁表。因此映射這些頁表的進程頁目錄需包含1024個PDE，恰好占用一個頁面。

頁表：進程的頁目錄項指向頁表。每個頁表占用一個頁面，由1024項PTE組成。一個有效的PTE大小為4字節(jié)，包含兩個主域：數(shù)據(jù)所在的物理頁面的頁面幀編號（PNF）或者內(nèi)存中一個頁面的物理地址的PFN；一些描述該頁面狀態(tài)和保護屬性的標志。

虛擬地質(zhì)結(jié)構：x86系統(tǒng)上，一個32位虛擬地址被解釋為三個單獨的部分，頁目錄索引、頁表索引和字節(jié)索引。由于頁目錄項有1024個，因此頁目錄索引為10位；一個也表中含有1024個PTE。因此頁表索引也為10位，字節(jié)索引為12位，正好表示一頁（4KB）內(nèi)容

三.實驗步驟及結(jié)果

1.查找頁目錄首地址

以程序WG.exe作為觀測對象。

啟動WinDbg到內(nèi)核調(diào)試模式，運行程序WG.exe。終斷目標機運行，輸入命令：kd>!process

發(fā)現(xiàn)WG.exe進程正處于運行狀態(tài) 輸入命令：

在KPROCESS中名為DirectoryTableBase的域，對應值為0x9fa6000，即WG.exe進程頁目錄的物理地址 查看CR3寄存其中的內(nèi)容，輸入命令：

CR3寄存其中的值和KPROCESS中記錄的頁目錄基址相同。這是因為在CPU切換執(zhí)行任務時，其內(nèi)容要更新為當前進程的頁目錄基址。2.地址轉(zhuǎn)譯過程

假設給定的虛擬地址為0x401001 輸入命令：

可以看到：

PDE的虛擬地址為C0300004.PTE的虛擬地址為C0001004 最后一行信息“pfn 9e4a---DA--UWEV”表示PDE中的具體內(nèi)容，9e4a是給定虛擬地址所在頁表在內(nèi)存中對應的物理頁號，“---DA—UWEV”是標志信息，“pfn a173----A--UREV”表示PTE中的具體內(nèi)容，a173是數(shù)據(jù)頁裝入內(nèi)存的物理頁號。

將數(shù)據(jù)頁對應的物理頁號a173加上業(yè)內(nèi)索引（0x1）即可得到虛擬地址0x401001的物理地址

3.觀察系統(tǒng)頁表

給定觀測虛擬地址為0x80001001 輸入命令：

當前正在執(zhí)行的進程是：WG.exe 輸入命令：

得到PDE為C0300800，其對應的物理頁號為3b 繼續(xù)讓目標機運行，啟動A.exe，然后中斷目標機運行。輸入命令：

當前正在執(zhí)行的進程為A.exe 輸入命令：

PDE信息和對應的物理頁號與前面觀測到的相同

四.結(jié)論

1.數(shù)據(jù)頁對應的物理頁號加上相應業(yè)內(nèi)索引即可得到虛擬地址的物理地址 2.不同的進程頁目錄都指向了相同的系統(tǒng)表頁

五.心得體會

在這次上機實驗，通過對WinDbg和VPc的調(diào)試運用，我熟悉了Windows內(nèi)存管理器的結(jié)構，也認知到Windows如何進行地址轉(zhuǎn)譯和轉(zhuǎn)換。對相關的知識也進行了溫習，更牢的掌握了相關知識。當然這些還遠遠不夠，我以后還要繼續(xù)不斷努力，去學習了解掌握操作系統(tǒng)的各方面知識。

附錄：

1.A.exe代碼

#include #include

#define N 1

HANDLE mutexSemaphore;HANDLE synchSemaphore_1;HANDLE synchSemaphore_2;

HANDLE mutexDisplay;

void Display(char*str,int delayTime){ if(WaitForSingleObject(mutexDisplay,INFINITE)==WAIT_OBJECT_0){ printf(“%snn”,str);ReleaseMutex(mutexDisplay);Sleep(delayTime);} }

void useTime(double limit){ for(double i=0;i<=limit;i+=0.001);}

void CreateProduct(){ Display(“Creating a production...”,0);useTime(200000);Display(“Creating finished.”,100);}

void PutProduct(){ Display(“Putting a production...”,0);useTime(150000);Display(“Putting finished”,100);}

void GetProduct(){ Display(“Getting a production...”,0);useTime(100000);Display(“Getting finished.”,100);}

void ConsumeProduct(){ Display(“Cosuming a production...”,0);useTime(100000);Display(“Cosuming finished.”,100);}

void Producer(){ while(true){ CreateProduct();

if(WaitForSingleObject(synchSemaphore_1,INFINITE)==WAIT_OBJECT_0){

if(WaitForSingleObject(mutexSemaphore,INFINITE)==WAIT_OBJECT_0){ PutProduct();ReleaseSemaphore(mutexSemaphore,1,NULL);} ReleaseSemaphore(synchSemaphore_2,1,NULL);} } }

void Consumer(){ while(true){

if(WaitForSingleObject(synchSemaphore_2,INFINITE)==WAIT_OBJECT_0){

if(WaitForSingleObject(mutexSemaphore,INFINITE)==WAIT_OBJECT_0){ GetProduct();ReleaseSemaphore(mutexSemaphore,1,NULL);} ReleaseSemaphore(synchSemaphore_1,1,NULL);} ConsumeProduct();} }

int main(){ HANDLE thread[2];DWORD threadID[2];

synchSemaphore_1=CreateSemaphore(NULL,N,N,NULL);synchSemaphore_2=CreateSemaphore(NULL,0,N,NULL);mutexSemaphore=CreateSemaphore(NULL,1,1,NULL);

mutexDisplay=CreateMutex(NULL,FALSE,NULL);

printf(“Program start.Please use WinDbg to observe main thread.nPress any key to continue...n”);getchar();

thread[0]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(Producer),NULL,CREATE_SUSPENDED,&threadID[0]);printf(“A producer was created.Please use WinDbg to observe producer thread.nPress any key to continue...n”);getchar();

thread[1]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(Consumer),NULL,CREATE_SUSPENDED,&threadID[1]);printf(“A Consumer was created.Please use WinDbg to observe Consumer thread.nPress any key to continue...n”);getchar();

printf(“Please select:n[1]Make producer thread runn[2]Make Consumer thread runn”);bool flag=true;bool flag_1=true,flag_2=true;int count=0;while(flag){ if(getchar()=='1'&&flag_1){ ResumeThread(thread[0]);count++;flag_1=false;} else if(getchar()=='2'&&flag_2){ ResumeThread(thread[1]);count++;flag_2=false;} if(count==2)flag=false;} WaitForMultipleObjects(1,thread,TRUE,INFINITE);

return 0;}

2.WG.exe代碼： #include

int main(){ int a=0;printf(“I'm Wangn”);while(true){a++;} }

第五篇：生產(chǎn)調(diào)度小結(jié)

作為計劃調(diào)度，時刻都要按計劃要求注意產(chǎn)品的流動狀態(tài)。鑄造作為產(chǎn)品的始端，是否能夠按計劃完成客戶訂單起著極其重要的地位。因此每天要到鑄造車間巡視3—4次，監(jiān)督重力和低壓是否按計劃進行生產(chǎn)，對于即將發(fā)貨的型號要及時督促完成，以免影響發(fā)貨。在查看鑄造型號時，有的鑄件型號刻于零件的外圈，有的位于內(nèi)邊緣。還可以從輪轂的輻條上得到型號（模具號+規(guī)格）。

機加作為對毛坯的處理階段，要關注每天所加工的型號是否按計劃正常進行，對于發(fā)現(xiàn)的問題要及時告知，若有不改者及時通知其部門負責人。在機加車間巡視時不僅要關注即將發(fā)貨的型號，還要注意已加工完成還未及時轉(zhuǎn)入下個工序的產(chǎn)品。若出現(xiàn)這類情況告知有關人員并及時清理。一旦出現(xiàn)問題機加責任重大，自身疏忽監(jiān)督也難辭其咎，所以，要全面的，認真對待自己的工作，不得有半點馬虎。在機加巡視時，留心學習各個車輪型號，要達到當看見輪子時就能知道它屬于什么模具類型和尺寸大小

做事要有主次，有輕重，有責任，每天要有一個清醒的任務，今天要完成什么，或者什么該加緊完成，對于即將出貨的訂單型號要及時去鑄造、機加、涂裝巡視產(chǎn)品歸于何處并告知相關人員及時將此類型號的產(chǎn)品抓緊完成。