搶占演算法節點

❶ 搶占的短進程優先調度演算法如果進程時間相同選哪個進程

短進程優先演算法是一種非剝奪式演算法，總是選取預計作業時間最短的作業優先運行；最短剩餘時間優先演算法是非剝奪式的，但可以改造成剝奪式的調度演算法，稱搶占式最短作業優先演算法。

❷ 靜態搶占式優先順序調度演算法是如何進行的

按照優先順序值的大小進行調度，選擇優先順序值大的作業優先調度。搶占式是指如果進入的作業的優先順序數大於當前正在執行的作業的優先順序數，就執行進入的作業，搶佔了當前正在執行的作業的資源。
按照到達時間將作業放入就緒隊列，當前作業執行過程中有作業進入，根據作業的優先順序值進行判斷，如果進入的作業的優先順序值小於或等於當前執行的作業的優先順序值，繼續執行當前作業；如果進入的作業的優先順序值大於當前執行的作業的優先順序值，將資源給進入的作業，當前的作業就放入就緒隊列隊尾，此時還需要的服務時間為原服務時間-進入的作業的到達時間。之後，每到達一個作業就與當前執行的作業進行優先順序值比較，優先順序值大的優先執行。當當前執行的作業執行結束後，比較就緒隊列中的作業的優先順序值，優先順序值大的優先執行。如此執行，直到就緒隊列為空，結束調度。

❸ 高響應比演算法是搶占式演算法嗎

非搶占式的演算法。因此只有當前運行的作業/進程主動放棄處理機時，才需要調度，才需要計算響應比。

優點： 綜合考慮了等待時間和運行時間（要求服務時間）等待時間相同時，要求服務時間短的優先（SJF的優點）。要求服務時間相同時，等待時間長的優先（FCFS的優點）。對於長作業來說，隨著等待時間越來越久，其響應比也會越來越大，從而避免了長作業飢餓的問題。

高響應比優先演算法：非搶占式的調度演算法，只有當前運行的進程主動放棄cpu時（正常/異常完成，或主動阻塞）,才需要進行調度，調度時計算所有就緒進程的響應比，選響應比最高的進程上處理機。響應比=（等待時間+要求服務時間）/ 要求服務時間。

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

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

動態優先權是指，在創建進程時所賦予的優先權，是可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調度性能。例如，我們可以規定，在就緒隊列中的進程，隨其等待時間的增長，其優先權以速率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;
}