先來先服務fcfs調度演算法

⑴ 操作系統，為什麼先來先服務演算法適用於cpu繁忙型，啥意思

因為CPU繁忙型進程即長時間佔用cpu很少有I/O操作，一旦獲得cpu，就會運行很長時間，就是會長時間佔用cpu，而I/O繁忙型由於要頻繁訪問IO埠，每次訪問都要放棄cpu，等I/O訪問完後要重新等待下一次調度（此時排到了就緒隊列的隊尾），所以要等待很久才能重新被調度。因此先來先服務有利於cpu繁忙型而不利於I/O繁忙型。
純手打，望採納

⑵ 先來先服務調度演算法。 優先順序調度演算法。 短作業優先調度演算法 輪轉調度演算法 響應比高優先調度演算法

你試一下

#include<stdio.h>
//using namespace std;
#define MAX 10
struct task_struct
{
char name[10]; /*進程名稱*/
int number; /*進程編號*/
float come_time; /*到達時間*/
float run_begin_time; /*開始運行時間*/
float run_time; /*運行時間*/
float run_end_time; /*運行結束時間*/
int priority; /*優先順序*/
int order; /*運行次序*/
int run_flag; /*調度標志*/
}tasks[MAX];
int counter; /*實際進程個數*/
int fcfs(); /*先來先服務*/
int ps(); /*優先順序調度*/
int sjf(); /*短作業優先*/
int hrrn(); /*響應比高優先*/
int pinput(); /*進程參數輸入*/
int poutput(); /*調度結果輸出*/

void main()
{ int option;
pinput();
printf("請選擇調度演算法（0~4）:\n");
printf("1.先來先服務\n");
printf("2.優先順序調度\n");
printf(" 3.短作業優先\n");
printf(" 4.響應比高優先\n");
printf(" 0.退出\n");
scanf("%d",&option);
switch (option)
{case 0:
printf("運行結束。\n");
break;
case 1:
printf("對進程按先來先服務調度。\n\n");
fcfs();
poutput();
break;
case 2:
printf("對進程按優先順序調度。\n\n");
ps();
poutput();
break;
case 3:
printf("對進程按短作業優先調度。\n\n");
sjf();
poutput();
break;
case 4:
printf("對進程按響應比高優先調度。\n\n");
hrrn();
poutput();
break;
}
}
int fcfs() /*先來先服務*/
{
float time_temp=0;
inti;
intnumber_schel;
time_temp=tasks[0].come_time;
for(i=0;i<counter;i++)
{
tasks[i].run_begin_time=time_temp;
tasks[i].run_end_time=tasks[i].run_begin_time+tasks[i].run_time;
tasks[i].run_flag=1;
time_temp=tasks[i].run_end_time;
number_schel=i;
tasks[number_schel].order=i+1;
}
return 0;
}

int ps() /*優先順序調度*/
{
float temp_time=0;
inti=0,j;
intnumber_schel,temp_counter;
intmax_priority;
max_priority=tasks[i].priority;
j=1;
while((j<counter)&&(tasks[i].come_time==tasks[j].come_time))
{
if (tasks[j].priority>tasks[i].priority)
{
max_priority=tasks[j].priority;
i=j;
}
j++;
} /*查找第一個被調度的進程*/
/*對第一個被調度的進程求相應的參數*/
number_schel=i;
tasks[number_schel].run_begin_time=tasks[number_schel].come_time;
tasks[number_schel].run_end_time=tasks[number_schel].run_begin_time+tasks[number_schel].run_time;
tasks[number_schel].run_flag=1;
temp_time=tasks[number_schel].run_end_time;
tasks[number_schel].order=1;
temp_counter=1;
while (temp_counter<counter)
{
max_priority=0;
for(j=0;j<counter;j++)
{if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
if (tasks[j].priority>max_priority)
{
max_priority=tasks[j].priority;
number_schel=j;
}
} /*查找下一個被調度的進程*/
/*對找到的下一個被調度的進程求相應的參數*/
tasks[number_schel].run_begin_time=temp_time;
tasks[number_schel].run_end_time=tasks[number_schel].run_begin_time+tasks[number_schel].run_time;
tasks[number_schel].run_flag=1;
temp_time=tasks[number_schel].run_end_time;
temp_counter++;
tasks[number_schel].order=temp_counter;

}return 0;
}

int sjf() /*短作業優先*/
{
float temp_time=0;
inti=0,j;
intnumber_schel,temp_counter;
float run_time;
run_time=tasks[i].run_time;
j=1;
while((j<counter)&&(tasks[i].come_time==tasks[j].come_time))
{
if (tasks[j].run_time<tasks[i].run_time)
{
run_time=tasks[j].run_time;
i=j;
}
j++;
} /*查找第一個被調度的進程*/
/*對第一個被調度的進程求相應的參數*/
number_schel=i;
tasks[number_schel].run_begin_time=tasks[number_schel].come_time;
tasks[number_schel].run_end_time=tasks[number_schel].run_begin_time+tasks[number_schel].run_time;
tasks[number_schel].run_flag=1;
temp_time=tasks[number_schel].run_end_time;
tasks[number_schel].order=1;
temp_counter=1;
while (temp_counter<counter)
{
for(j=0;j<counter;j++)
{
if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
{run_time=tasks[j].run_time;number_schel=j;break;}
}

for(j=0;j<counter;j++)
{if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
if(tasks[j].run_time<run_time)
{run_time=tasks[j].run_time;
number_schel=j;
}
}
/*查找下一個被調度的進程*/
/*對找到的下一個被調度的進程求相應的參數*/
tasks[number_schel].run_begin_time=temp_time;
tasks[number_schel].run_end_time=tasks[number_schel].run_begin_time+tasks[number_schel].run_time;
tasks[number_schel].run_flag=1;
temp_time=tasks[number_schel].run_end_time;
temp_counter++;
tasks[number_schel].order=temp_counter;
}return 0;
}

int hrrn() /*響應比高優先*/
{ int j,number_schel,temp_counter;
float temp_time,respond_rate,max_respond_rate;
/*第一個進程被調度*/
tasks[0].run_begin_time=tasks[0].come_time;
tasks[0].run_end_time=tasks[0].run_begin_time+tasks[0].run_time;
temp_time=tasks[0].run_end_time;
tasks[0].run_flag=1;
tasks[0].order=1;
temp_counter=1;
/*調度其他進程*/
while(temp_counter<counter)
{
max_respond_rate=0;
for(j=1;j<counter;j++)
{
if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
{respond_rate=(temp_time-tasks[j].come_time)/tasks[j].run_time;
if (respond_rate>max_respond_rate)
{
max_respond_rate=respond_rate;
number_schel=j;
}
}
} /*找響應比高的進程*/
tasks[number_schel].run_begin_time=temp_time;
tasks[number_schel].run_end_time=tasks[number_schel].run_begin_time+tasks[number_schel].run_time;
temp_time=tasks[number_schel].run_end_time;
tasks[number_schel].run_flag=1;
temp_counter+=1;
tasks[number_schel].order=temp_counter;
}
return 0;
}
int pinput() /*進程參數輸入*/
{ int i;
printf("please input the processcounter:\n");
scanf("%d",&counter);

for(i=0;i<counter;i++)
{printf("******************************************\n");
printf("please input the process of %d th :\n",i+1);
printf("please input the name:\n");
scanf("%s",tasks[i].name);
printf("please input the number:\n");
scanf("%d",&tasks[i].number);
printf("please input the come_time:\n");
scanf("%f",&tasks[i].come_time);
printf("please input the run_time:\n");
scanf("%f",&tasks[i].run_time);
printf("please input the priority:\n");
scanf("%d",&tasks[i].priority);
tasks[i].run_begin_time=0;
tasks[i].run_end_time=0;
tasks[i].order=0;
tasks[i].run_flag=0;
}
return 0;
}
int poutput() /*調度結果輸出*/
{
int i;
float turn_round_time=0,f1,w=0;
printf("name number come_time run_timerun_begin_time run_end_time priority order turn_round_time\n");
for(i=0;i<counter;i++)
{
f1=tasks[i].run_end_time-tasks[i].come_time;
turn_round_time+=f1;
w+=(f1/tasks[i].run_time);
printf(" %s, %d, %5.3f, %5.3f, %5.3f, %5.3f, %d, %d,%5.3f\n",tasks[i].name,tasks[i].number,tasks[i].come_time,tasks[i].run_time,tasks[i].run_begin_time,tasks[i].run_end_time,tasks[i].priority,tasks[i].order,f1);
}
printf("average_turn_round_timer=%5.2f\n",turn_round_time/counter);
printf("weight_average_turn_round_timer=%5.2f\n",w/counter);
return 0;
}

⑶ 調度演算法詳細資料大全

作業系統管理了系統的有限資源，當有多個進程（或多個進程發出的請求）要使用這些資源時，因為資源的有限性，必須按照一定的原則選擇進程（請求）來佔用資源。這就是調度。目的是控制資源使用者的數量,選取資源使用者許可佔用資源或佔用資源。

基本介紹

• 中文名 ：調度演算法
• 所屬領域 ：作業系統

調度演算法,評價因素,吞吐量,CPU利用率,周轉時間,確定進程調度原則,調度演算法分類,先來先服務(FCFS),輪轉法(Round Robin),多級反饋佇列演算法,linux進程調度演算法,

調度演算法

在作業系統中調度是指一種資源分配，因而調度演算法是指：根據系統的資源分配策略所規定的資源分配演算法。對於不同的的系統和系統目標，通常採用不同的調度演算法，例如，在批處理系統中，為了照顧為數眾多的段作業，應採用短作業優先的調度演算法；又如在分時系統中，為了保證系統具有合理的回響時間，應當採用輪轉法進行調度。目前存在的多種調度演算法中，有的演算法適用於作業調度，有的演算法適用於進程調度；但也有些調度演算法既可以用於作業調度，也可以用於進程調度。 通常將作業或進程歸入各種就緒或阻塞佇列。 調度演算法要求：高資源利用率、高吞吐量、用戶滿意等原則。 進程調度所採用的演算法是與整個系統的設計目標相一致的： 1.批處理系統：增加系統吞吐量和提高系統資源的利用率; 2.分時系統：保證每個分時用戶能容忍的回響時間。 3.實時系統：保證對隨機發生的外部事件做出實時回響。

評價因素

吞吐量

單位時間內CPU完成作業的數量。

CPU利用率

從0%～100%。

周轉時間

評價批處理系統的性能指標。 Ti = 作業完成時刻 － 作業提交時刻

確定進程調度原則

在系統角度來說，公平性：每個進程（不論優先權）都有機會被運行；較大的吞吐量。 用戶角度：及時性：回響速度要快；較短的周轉時間：不應當讓用戶等待時間過長。

調度演算法分類

先來先服務(FCFS)

先來先服務（FCFS, First Come First Serve）是最簡單的調度演算法，按先後順序進行調度。 1. FCFS演算法 按照作業提交或進程變為就緒狀態的先後次序，分派CPU； 當前作業或進程佔用CPU，直到執行完或阻塞，才出讓CPU（非搶占方式）。 在作業或進程喚醒後（如I/O完成），並不立即恢復執行，通常等到當前作業或梁兆進程出讓CPU。最簡單的演算法。 2. FCFS的特點 比較有利於長作業，而不利於短作業。 有利於CPU繁忙的作業，而不利於I/O繁忙的作業。

輪轉法(Round Robin)

輪轉法(Round Robin)是讓每個進程在就緒佇列中的等待時間與享受服務的時間成正比例。 1. 輪轉法 將系統中所有的就緒進程按照FCFS原則，排成一個佇列。 每次調度時將CPU分派給隊碧渣戚首進程，讓其執行一個時間片。時間片的長度從幾個ms到幾百ms。 在一個時間片結束時，發生時鍾中斷。 調度程式據此暫停當前進程的執行，將其送到就緒佇列的末尾，並通過上下文切換執行當前的隊首進程。? 進程可以未使用完一個時間片，就出讓CPU（如阻塞）。 2. 時間片長度的確定 時間片長度變化的影響2 過長－>退化為FCFS演算法，進程在一個時間片內都執行完，回響時間長。2 過短－>用戶的一次請求需要多個時間片才能處理完，上下文切換次數增加，回響時間長。 對回響時間的要求：T(回響悔陵時間)=N(進程數目)*q(時間片) 就緒進程的數目：數目越多，時間片越小 系統的處理能力：應當使用戶輸入通常在一個時間片內能處理完，否則使回響時間，平均周轉時間和平均帶權周轉時間延長。

多級反饋佇列演算法

多級反饋佇列演算法時間片輪轉演算法和優先權演算法的綜合和發展。優點：2 為提高系統吞吐量和縮短平均周轉時間而照顧短進程。2 為獲得較好的I/O設備利用率和縮短回響時間而照顧I/O型進程。2 不必估計進程的執行時間，動態調節。 1. 多級反饋佇列演算法2 設定多個就緒佇列，分別賦予不同的優先權，如逐級降低，佇列1的優先權最高。每個佇列執行時間片的長度也不同，規定優先權越低則時間片越長，如逐級加倍。2 新進程進入記憶體後，先投入佇列1的末尾，按FCFS演算法調度；若按佇列1一個時間片未能執行完，則降低投入到佇列2的末尾，同樣按FCFS演算法調度；如此下去，降低到最後的佇列，則按「時間片輪轉」演算法調度直到完成。2 僅當較高優先權的佇列為空，才調度較低優先權的佇列中的進程執行。如果進程執行時有新進程進入較高優先權的佇列，則搶先執行新進程，並把被搶先的進程投入原佇列的末尾。 2. 幾點說明 I/O型進程：讓其進入最高優先權佇列，以及時回響I/O互動。通常執行一個小時間片，要求可處理完一次I/O請求的數據，然後轉入到阻塞佇列。 計算型進程：每次都執行完時間片，進入更低級佇列。最終採用最大時間片來執行，減少調度次數。 I/O次數不多，而主要是CPU處理的進程。在I/O完成後，放回優先I/O請求時離開的佇列，以免每次都回到最高優先權佇列後再逐次下降。2為適應一個進程在不同時間段的運行特點，I/O完成時，提高優先權；時間片用完時，降低優先權。 3.shortest job next 系統計算程式調用的時間，時間最短的先執行。

linux進程調度演算法

linux核心的三種調度方法： 1. SCHED_OTHER 分時調度策略， 2. SCHED_FIFO實時調度策略，先到先服務 3. SCHED_RR實時調度策略，時間片輪轉 實時進程將得到優先調用，實時進程根據實時優先權決定調度權值，分時進程則通過nice和counter值決 定權值，nice越小，counter越大，被調度的機率越大，也就是曾經使用了cpu最少的進程將會得到優先調 度。 SHCED_RR和SCHED_FIFO的不同： 當採用SHCED_RR策略的進程的時間片用完，系統將重新分配時間片，並置於就緒佇列尾。放在佇列 尾保證了所有具有相同優先權的RR任務的調度公平。 SCHED_FIFO一旦佔用cpu則一直運行。一直運行直到有更高優先權任務到達或自己放棄。 如果有相同優先權的實時進程（根據優先權計算的調度權值是一樣的）已經准備好，FIFO時必須等待該 進程主動放棄後才可以運行這個優先權相同的任務。而RR可以讓每個任務都執行一段時間。 SHCED_RR和SCHED_FIFO的相同點： SHCED_RR和SHCED_FIFO都只用於實時任務。 創建時優先權大於0(1-99)。 按照可搶占優先權調度演算法進行。 就緒態的實時任務立即搶占非實時任務。 所有任務都採用linux分時調度策略時。 1. 創建任務指定採用分時調度策略，並指定優先權nice值(-20~19)。 2. 將根據每個任務的nice值確定在cpu上的執行時間(counter)。 3. 如果沒有等待資源，則將該任務加入到就緒佇列中。 4. 調度程式遍歷就緒佇列中的任務，通過對每個任務動態優先權的計算(counter+20-nice)結果，選擇 計算結果最大的一個去運行，當這 個時間片用完後(counter減至0)或者主動放棄cpu時，該任務將被放在 就緒佇列末尾(時間片用完)或等待佇列(因等待資源而放棄cpu)中。 5. 此時調度程式重復上面計算過程，轉到第4步。 6. 當調度程式發現所有就緒任務計算所得的權值都為不大於0時，重復第2步。 所有任務都採用FIFO時: 1. 創建進程時指定採用FIFO，並設定實時優先權rt_priority(1-99)。 2. 如果沒有等待資源，則將該任務加入到就緒佇列中。 3. 調度程式遍歷就緒佇列，根據實時優先權計算調度權值(1000+rt_priority),選擇權值最高的任務使用 cpu，該FIFO任務將一直佔有cpu直到有優先權更高的任務就緒(即使優先權相同也不行)或者主動放棄(等 待資源)。 4. 調度程式發現有優先權更高的任務到達(高優先權任務可能被中斷或定時器任務喚醒，再或被當前運行 的任務喚醒，等等)，則調度程式立即在當前任務 堆疊中保存當前cpu暫存器的所有數據，重新從高優先權 任務的堆疊中載入暫存器數據到cpu，此時高優先權的任務開始運行。重復第3步。 5. 如果當前任務因等待資源而主動放棄cpu使用權，則該任務將從就緒佇列中刪除，加入等待佇列，此時 重復第3步。 所有任務都採用RR調度策略時 1. 創建任務時指定調度參數為RR，並設定任務的實時優先權和nice值(nice值將會轉換為該任務的時間片 的長度)。 2. 如果沒有等待資源，則將該任務加入到就緒佇列中。 3. 調度程式遍歷就緒佇列，根據實時優先權計算調度權值(1000+rt_priority),選擇權值最高的任務使用 cpu。 4. 如果就緒佇列中的RR任務時間片為0，則會根據nice值設定該任務的時間片，同時將該任務放入就緒隊 列的末尾。重復步驟3。 5. 當前任務由於等待資源而主動退出cpu，則其加入等待佇列中。重復步驟3。 系統中既有分時調度，又有時間片輪轉調度和先進先出調度 1. RR調度和FIFO調度的進程屬於實時進程，以分時調度的進程是非實時進程。 2. 當實時進程准備就緒後，如果當前cpu正在運行非實時進程，則實時進程立即搶占非實時進程。 3. RR進程和FIFO進程都採用實時優先權做為調度的權值標准，RR是FIFO的一個延伸。FIFO時，如果兩 個進程的優先權一樣，則這兩個優先 級一樣的進程具體執行哪一個是由其在佇列中的未知決定的，這樣導 致一些不公正性(優先權是一樣的，為什麼要讓你一直運行?),如果將兩個優先權一樣的任務 的調度策略都 設為RR,則保證了這兩個任務可以循環執行，保證了公平。

⑷ 操作系統先進先出(FIFO)和先來先服務(FCFS)有什麼區別

1.先來先服務調度演算法（FCFS）:就是按照各個作業進入系統的自然次序來調度作業。這種調度演算法的優點是實現簡單，公平。其缺點是沒有考慮到系統中各種資源的綜合使用情況，往往使短作業的用戶不滿意，因為短作業等待處理的時間可能比實際運行時間長得多。

2.先進先出演算法(FIFO)：按照進程進入就緒隊列的先後次序來選擇。即每當進入進程調度，總是把就緒隊列的隊首進程投入運行。

⑸ 進程調度演算法1——FCFS、SJF、HNNR

  進程的調度方式有兩種： 非剝奪調度方式（非搶占式）和剝奪調度方式（搶占方式）。
  非搶占式：只允許進程主動放棄處理機。如進程運行結束、異常結束或主動請求I/O阻塞。在運行的過程中即使有更緊迫的任務到達，當前進程依然會繼續使用處理機，直到該進程終止或主動要求進入阻塞態。
  搶占式：當一個進程正在處理機上執行時，如果有一個更重要更緊迫的進程需要處理機，則立即暫停正在執行的進程，將處理機分配給更重要更緊迫的那個進程。
  下面介紹適用於早期操作系統幾種進程調度的演算法

  先來先服務（FCFS）：按照到達的先後順序調度，事實上就是等待時間越久的越優先得到服務。
  下面表示按照先來先服務演算法的執行順序

  計算進程的幾個衡量指標：

  短作業優先演算法是非搶占式的演算法，但是也有搶占式的版本—— 最短剩餘時間優先演算法（STRN,Shortest Remaining Time Next） 。
  用於進程的調度演算法稱為短進程優先調度演算法（SPF,Shortest Process First）。

  短作業/進程優先調度演算法：每次調度時選擇當前已到達且運行時間最短的作業/進程.。

  因為進程1最先達到，此時沒有其他線程，所以進程1先被服務。當進程1運行完後，進程2和3已經到達，此時進程3需要的運行時間比進程2少，所以進程3先被服務…
  計算進程的幾個衡量指標：

  最短剩餘時間優先演算法：每當有進程 加入就緒隊列改變時就需要調度 ，如果新到達的進程的所需的運行時間比當前運行的進程剩餘時間更短，則由新進程搶占處理機，當前運行進程重新回到就緒隊列。此外，當一個 進程完成時也需要調度 。

通過比較上面三組的平均周轉時間、平均帶權周轉時間和平均等待時間可以看出，短作業優先演算法可以減少進程的等待時間，對短作業有利。

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

   響應比 = （等待時間 + 運行時間）/ 運行時間

  上面的三種調度演算法一般適用於 早期的批處理系統 ，沒有考慮響應時間也不區分任務的緊急程度。因此對用戶來說交互性差。

  如發現錯誤，請指正！！！

⑹ 實時操作系統常用任務調度演算法有哪些

實時操作系統常用任務調度演算法有哪些
操作系統常用的批處理作業調度演算法
1．先來先服務調度演算法
先來先服務(FCFS)調度演算法是一種最簡單的調度演算法，該演算法既可用於作業調度，也可用於進程調度。當在作業調度中採用該演算法時，每次調度都是從後備作業隊列中選擇一個或多個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然後放入就緒隊列。在進程調度中採用FCFS演算法時，則每次調度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞後才放棄處理機。
2．短作業(進程)優先調度演算法