進程調度之最短作業(yè)優(yōu)先

最短作業(yè)優(yōu)先

SJF（Shortest-Job-First）:

• 分為搶占式和非搶占式：
  • 非搶占式的SJF 更確切的叫 最短下次CPU執(zhí)行算法(shortest-next-CPU-burst)
  • 搶占式的SJF 叫 最短剩余時間優(yōu)先算法（shortest-remaining-time-first）
• 優(yōu)點：
  它的平均等待時間最小，是最優(yōu)的調度算法。
• 缺點：
  獲取下次CPU執(zhí)行長度比較困難（一般估計）。
• 用途：
  經常用于長期調度。

代碼

根據個人思路模擬的SJF,僅供參考

非搶占式

#include <iostream> #include <queue>using namespace std; typedef double TimeType; const int MAXN = 1e6+5;int task_num; TimeType now_time; //從第一個到達的作業(yè)時間開始 TimeType avg_spend_time; //平均周轉時間 TimeType avg_weight_time; //平均帶權周轉時間struct StruTask {int id; //序號TimeType arrive_time; //到達時間（輸入）TimeType service_time; //服務時間（輸入）TimeType start_time; //開始時間（設置）TimeType end_time; //結束時間（設置）TimeType spend_time; //周轉時間:end_time - arrive_timeTimeType weight_time; //帶權周轉時間spend_time/service_timebool finished;} arrayTask[MAXN];TimeType get_task() {cout<<"請輸入任務數:"<<endl;cin>>task_num;if(task_num <= 0) return -1;cout<<"----------請輸入任務相關信息-------"<<endl;TimeType minx = 1e15;for(int i = 1; i <= task_num; ++i){cout<<"請輸入第"<<i<<"個任務的 到達時間 和 服務時間:";arrayTask[i].id = i;cin>>arrayTask[i].arrive_time;minx = min(minx,arrayTask[i].arrive_time);cin>>arrayTask[i].service_time;}return minx; }int get_next_task() {int minx = 1<<30;int aim = 0;for(int i = 1; i <= task_num; ++i){if(arrayTask[i].arrive_time<=now_time && !arrayTask[i].finished){if(arrayTask[i].service_time < minx){minx = arrayTask[i].service_time;aim = i;}}}return aim;}void run_task(StruTask &task) {now_time = max(now_time,task.arrive_time);task.start_time = now_time;task.end_time = now_time + task.service_time;now_time = task.end_time;task.spend_time = task.end_time - task.arrive_time;avg_spend_time += task.spend_time;task.weight_time = task.spend_time / task.service_time;avg_weight_time += task.weight_time;task.finished = true; }void print_result(StruTask &task) {cout<<" id: "<<task.id<<" arrive_time: "<<task.arrive_time<<" service: "<<task.service_time;cout<<" start: "<<task.start_time<<" end: "<<task.end_time;cout<<" spend: "<<task.spend_time<<" weight: "<<task.weight_time<<endl; }/*SJF 非搶占式 Short Job First */ void SJF() {avg_spend_time = 0;avg_weight_time = 0;for(int i = 1; i <= task_num; ++i){int id = get_next_task();run_task(arrayTask[id]);print_result(arrayTask[id]);} }int main() {now_time = get_task();if(now_time == -1)return 0;SJF();double wait = 0;for(int i = 1; i <= task_num; ++i){wait += arrayTask[i].start_time - arrayTask[i].arrive_time;}avg_spend_time /= task_num;avg_weight_time /= task_num;cout<<" avg_spend: "<<avg_spend_time<<" avg_weight: "<<avg_weight_time<<endl;cout<<" avg_wait: "<<(wait/task_num)<<endl;return 0; }

運行示例

4 0 6 0 8 0 7 0 3

4 0 8 1 4 3 5 2 9

搶占式

#include <iostream> #include <queue> using namespace std; typedef double TimeType; const int MAXN = 1e3+5;int task_num; TimeType now_time; //從第一個到達的作業(yè)時間開始 TimeType avg_spend_time; //平均周轉時間 TimeType avg_weight_time; //平均帶權周轉時間 TimeType avg_wait; TimeType last_run[MAXN];struct StruTask {int id; //序號TimeType arrive_time; //到達時間（輸入）TimeType service_time; //服務時間（輸入）TimeType start_time; //開始時間（設置）TimeType end_time; //結束時間（設置）TimeType spend_time; //周轉時間:end_time - arrive_timeTimeType weight_time; //帶權周轉時間spend_time/service_timeTimeType remain_service_time; //剩余服務時間} arrayTask[MAXN];TimeType get_task() {cout<<"請輸入任務數:"<<endl;cin>>task_num;if(task_num <= 0) return -1;cout<<"----------請輸入任務相關信息-------"<<endl;TimeType minx = 1e15;for(int i = 1; i <= task_num; ++i){cout<<"請輸入第"<<i<<"個任務的 到達時間 和 服務時間:";arrayTask[i].id = i;cin>>arrayTask[i].arrive_time;minx = min(minx,arrayTask[i].arrive_time);cin>>arrayTask[i].service_time;arrayTask[i].remain_service_time = arrayTask[i].service_time;}return minx; }int get_next_task() {TimeType minx = 1e15;int aim = -1;for(int i = 1; i <= task_num; ++i){if(arrayTask[i].arrive_time<=now_time && arrayTask[i].remain_service_time){if(arrayTask[i].remain_service_time < minx){minx = arrayTask[i].remain_service_time;aim = i;}}}return aim;}void run_task(StruTask &task) {now_time = max(now_time,task.arrive_time);avg_wait += now_time - (last_run[task.id]==-1?task.arrive_time:last_run[task.id]);task.start_time = now_time;task.end_time = now_time + 1; // 執(zhí)行一秒后詢問，便于實現task.remain_service_time -= 1;now_time = task.end_time;last_run[task.id] = now_time;if(!task.remain_service_time){task.spend_time = task.end_time - task.arrive_time;avg_spend_time += task.spend_time;task.weight_time = task.spend_time / task.service_time;avg_weight_time += task.weight_time;}}void print_result(StruTask &task) {cout<<" id: "<<task.id<<" arrive_time: "<<task.arrive_time<<" service: "<<task.service_time;cout<<" start: "<<task.start_time<<" end: "<<task.end_time;cout<<" spend: "<<task.spend_time<<" weight: "<<task.weight_time<<endl; }/*SJF 搶占式:又叫最短剩余時間優(yōu)先 Shortest remaining time first */ void SRTF() {avg_spend_time = 0;avg_weight_time = 0;avg_wait = 0;for(int i = 0; i < MAXN; ++i){last_run[i] = -1;}int id;while(1){id = get_next_task();if(id == -1) break;run_task(arrayTask[id]);print_result(arrayTask[id]);} }int main() {now_time = get_task();if(now_time == -1)return 0;SRTF();avg_spend_time /= task_num;avg_weight_time /= task_num;avg_wait /= task_num;cout<<" avg_spend: "<<avg_spend_time<<" avg_weight: "<<avg_weight_time<<endl;cout<<" avg_wait: "<<avg_wait<<endl;return 0; }

運行示例

4 0 8 2 9 3 5 1 4

總結

以上是生活随笔為你收集整理的进程调度之最短作业优先的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。