什麼是最好優先演算法

❶ A*演算法 和 最佳優先搜索演算法（Best-First-Search）

最佳優先搜索演算法是一種啟發式搜索演算法（Heuristic Algorithm），其基於廣度優先搜索演算法，不同點是其依賴於估價函數對將要遍歷的節點進行估價，選擇代價小的節點進行遍歷，直到找到目標點為止。 BFS演算法不能保證找到的路徑是一條最短路徑，但是其計算過程相對於Dijkstra
演算法會快很多 。

最佳優先搜索是一種啟發式搜索演算法。廣度優先搜索和深度優先搜索都屬於窮舉類型的搜索，需要依次遍歷所有的節點，當空間非常大的時候，這種方式的效率就會非常差。而啟發式的搜索是對狀態控制項中的每個點進行評估，然後選出最好的位置。

啟發估價函數公式為：

n表示當前的點，g(n)為從起始點到點n的實際代價，h(n)為從點n到目標點的估價。

（圖片來源於網路）

A*演算法將BFS演算法和Dijkstra演算法結合在一起，結合兩演算法的優點，既可以查找最短路徑的，有擁有和BFS差不多的效率。

（圖片來源於網路）

A*演算法詳解

模擬尋路的地址

❷ 動態高優先權優先調度演算法

動態高優先權優先調度演算法：

動態優先權是指，在創建進程時所賦予的優先權，是可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調度性能。例如，我們可以規定，在就緒隊列中的進程，隨其等待時間的增長，其優先權以速率a提高。若所有的進程都具有相同的優先權初值，則顯然是最先進入就緒隊列的進程，將因其動態優先權變得最高而優先獲得處理機，此即FCFS演算法。若所有的就緒進程具有各不相同的優先權初值，那麼，對於優先權初值低的進程，在等待了足夠的時間後，其優先權便可能升為最高，從而可以獲得處理機。當採用搶占式優先權調度演算法時，如果再規定當前進程的優先權以速率b下降，則可防止一個長作業長期地壟斷處理機。

演算法代碼模擬實現：

#include<stdio.h>
#include<stdlib.h>
#defineN6

//待插入就緒隊列的進程數據
intid[N]={0,1,
2,3,4,
5};
intpriority[N]={9,38,17,
2,7,18};
intcpuTime[N]={0,
0,0,0,
0,0};
intallTime[N]={3,
2,3,6,
1,3};

//********************************
//
//模擬進程/PCB數據結構
//
//********************************

//
枚舉進程的狀態：就緒、執行、阻塞、完成
enumSTATE{Ready,Run,Block,Finish
};

//建立PCB結構體
structPCB{
intid;//標志數
intpriority;//優先數
intcpuTime;//
已佔CPU時間
intallTime;//
還需佔CPU時間
intblockTime;//已被阻塞的時間
STATEstate;//
進程狀態
PCB*pre;//
PCB的前指針
PCB*nxt;//
PCB的後指針
};

//********************************
//
//模擬進程隊列
//
//********************************

//進程入列
voidqueQush(PCB*process,PCB
*queHead)
{
process->pre=NULL;
process->nxt=
queHead->nxt;
if(queHead->nxt!=NULL){
//非第一個入列
queHead->nxt->pre=
process;
}
queHead->nxt=process;
}

//進程出列
voidquePop(PCB*process,PCB
*queHead)
{
if(process->pre!=NULL){
//不是頭節點
process->pre->nxt=
process->nxt;
}
else{
queHead->nxt=
process->nxt;
}
if(process->nxt!=NULL){
//不是尾節點
process->nxt->pre=
process->pre;
}
//
清空進程指針
process->pre=process->nxt=
NULL;
}

//查看隊列里進程的信息
voidqueWalk(PCB*queHead)
{
PCB*pro=queHead->nxt;
if(pro==NULL){
printf("(無進程)
");
return;
}
while(pro!=NULL)
{
printf("id:%d,
pri:%d,alltime:%d
",
pro->id,
pro->priority,
pro->allTime);
pro=
pro->nxt;
}
}

//********************************
//
//模擬就緒隊列
//
//********************************

intreadyQueNum;//就緒隊列的進程數量
PCBreadyQueHead;//
就緒隊列的頭部
PCB*readyMaxProcess;//就緒隊列中優先順序最高的進程

//進程插入到就緒隊列
voidreadyQueQush(PCB
*process)
{
readyQueNum++;
process->state=Ready;
queQush(process,&readyQueHead);
}

//優先順序最高的進程出列
PCB*readyQuePop()
{
readyQueNum--;
quePop(readyMaxProcess,
&readyQueHead);
returnreadyMaxProcess;
}

//每個時間片，更新就緒隊列里進程的信息
voidreadyQueUpdate()
{
intmaxPriority=-1;
PCB*pro=readyQueHead.nxt;
if(pro==NULL){
//就緒隊列沒有進程
readyMaxProcess=
NULL;
return;
}
while(pro!=NULL)
{
pro->priority
++;
if(pro->priority>maxPriority)
{
maxPriority=
pro->priority;
readyMaxProcess=pro;
}
pro=
pro->nxt;
}
}

//返回就緒隊列最高優先順序的值
intreadyMaxPriority()
{
returnreadyMaxProcess->priority;
}

//查看就緒隊列里進程的信息
voidreadyQueWalk()
{
printf("就緒隊列里的進程信息為：
");
queWalk(&readyQueHead);
}

//********************************
//
//模擬阻塞隊列
//
//********************************

#defineEndBlockTime3
//進程最長被阻塞時間

intblockQueNum;//阻塞隊列的進程數量
PCBblockQueHead;//
阻塞隊列的頭部
PCB*blockMaxProcess;//阻塞隊列中優先順序最高的進程

//進程插入到阻塞隊列
voidblockQueQush(PCB
*process)
{
blockQueNum++;
process->blockTime=0;
process->state=Block;
queQush(process,&blockQueHead);
}

//優先順序最高的進程出列
PCB*blockQuePop()
{
blockQueNum--;
quePop(blockMaxProcess,
&blockQueHead);
returnblockMaxProcess;
}

//每個時間片，更新阻塞隊列里進程的信息
voidblockQueUpdate()
{
intmaxPriority=-1;
PCB*pro=blockQueHead.nxt;
while(pro!=NULL)
{
pro->blockTime
++;
if(pro->blockTime>=EndBlockTime)
{
PCB*process=pro;
pro=pro->nxt;
//阻塞時間到，調入就緒隊列
blockQueNum--;
quePop(process,
&blockQueHead);
readyQueQush(process);
}else
if(pro->priority>maxPriority)
{
//更新阻塞隊列里優先順序最高的進程指針
maxPriority=
pro->priority;
blockMaxProcess=pro;
pro=pro->nxt;
}
}
}

//查看阻塞隊列里進程的信息
voidblockQueWalk()
{
printf("阻塞隊列里的進程信息為：
");
queWalk(&blockQueHead);
}

//********************************
//
//模擬動態優先權的進程調度
//
//********************************

//初始化數據
voidinitData()
{
//
初始化就緒隊列和阻塞隊列
readyQueNum=blockQueNum=0;
readyMaxProcess=blockMaxProcess=NULL;
readyQueHead.pre=readyQueHead.nxt=NULL;
blockQueHead.pre=blockQueHead.nxt=NULL;

//
初始化進程進入就緒隊列
inti,maxPriority=-1;
for(i=0;i<N;i
++)
{
//分配一個PCB的內存空間
PCB*pro=(PCB
*)malloc(sizeof(PCB));
//給當前的PCB賦值
pro->id
=id[i];
pro->priority
=priority[i];
pro->cpuTime
=cpuTime[i];
pro->allTime
=allTime[i];
pro->blockTime
=0;
if(pro->allTime>0){
//插入到就緒隊列中
readyQueQush(pro);
//更新就緒隊列優先順序最高的進程指針
if(pro->priority>
maxPriority){
maxPriority=pro->priority;
readyMaxProcess=pro;
}
}
}
}

//模擬cpu執行1個時間片的操作
voidcpuWord(PCB
*cpuProcess)
{
cpuProcess->priority-=3;
if(cpuProcess->priority<0)
{
cpuProcess->priority=0;
}
cpuProcess->cpuTime++;
cpuProcess->allTime--;
//
顯示正執行進程的信息：
printf("CPU正執行的進程信息為：
");
printf("id:M,pri:M,
alltime:M
",
cpuProcess->id,
cpuProcess->priority,
cpuProcess->allTime);
}

intmain()
{
inttimeSlice=0;//
模擬時間片
intcpuBusy=0;
//模擬cpu狀態
PCB*cpuProcess=NULL;//當前在cpu執行的進程
//
初始化數據
initData();
//
模擬進程調度
while(1)
{
if(readyQueNum==0
&&blockQueNum==0
&&cpuBusy==0){
//就緒隊列、阻塞隊列和cpu無進程，退出
break;
}
//printf("
%d%d",
readyQueNum,blockQueNum);
if(cpuBusy==0)
{
//cpu空閑，選擇一個進程進入cpu
if(readyQueNum>0)
{
//
選擇緒隊列優先順序最高的進程
cpuProcess
=readyQuePop();
}else{
//
就緒隊列沒有進程，改為選擇阻塞隊列優先順序最高的進程
cpuProcess
=blockQuePop();
}
cpuProcess->cpuTime=
0;
cpuProcess->state=
Run;
cpuBusy=1;
}
timeSlice++;
printf("
第%d個時間片後：
",
timeSlice);
//
模擬cpu執行1個時間片的操作
cpuWord(cpuProcess);
if(cpuProcess->allTime==0){
cpuProcess->state=
Finish;
//釋放已完成進程的PCB
free(cpuProcess);
cpuBusy=0;
}
//
更新就緒隊列和阻塞隊列里的進程信息
blockQueUpdate();
readyQueUpdate();
//
查看就緒隊列和阻塞隊列的進程信息
readyQueWalk();
blockQueWalk();
if(cpuBusy==1
&&readyQueNum>0
&&
cpuProcess->priority
<readyMaxPriority()){
//需搶佔cpu，當前執行的進程調入阻塞隊列
blockQueQush(cpuProcess);
cpuProcess=readyQuePop();
}
}
printf("
模擬進程調度演算法結束
");
return0;
}

❸ 優先順序調度演算法

優先順序調度演算法的原理是給每個進程賦予一個優先順序，每次需要進程切換時，找一個優先順序最高的進程進行調度。這樣，如果賦予長進程一個高優先順序，則該進程就不會再「飢餓」。事實上，STCF演算法本身就是一種優先順序調度，只不過它給予短進程高優先順序而已。

優先順序調度的優點是可以賦予重要的進程以高優先順序以確保重要任務能夠得到CPU時間。其缺點則與STCF演算法一樣，低優先順序的進程可能會「飢餓」。不過，這個問題在優先順序調度演算法里比在STCF里好解決：只要動態地調節優先順序即可。例如，在一個進程執行特定CPU時間後將其優先順序降低一個級別，或者將處於等待進程的優先順序提高一個級別。這樣，一個進程如果等待時間很長，其優先順序將因持續提升而超越其他進程的優先順序，從而得到CPU時間。這樣，「飢餓」現象就可以防止。

不過，優先順序調度還有一個缺點，就是響應時間不能保證，除非將一個進程的優先順序設置為最高。即使將優先順序設置為最高，但如果每個人都將自己進程的優先順序設為最高，則響應時間還是無法保證。