首页 > 代码库 > 最短作业优先(SJF)

最短作业优先(SJF)

1. 最短作业优先:

    最短作业优先(SJF)是一种调度任务请求的调度策略。每个任务请求包含有请求时间(即向系统提交的请求的时间)和持续时间(即完成任务所需时间)。

    当前任务完成后,SJF策略会选择最短持续时间执行任务,若最短持续时间相同,则选择最早请求时间的任务。任务等待时间为请求时间和实际开始时间之差。

   “短作业优先”=“最短剩余时间优先”

 

 

2. 实例:

    假设系统一直执行任务,从未空闲。设计程序,输入请求时间表和对应的持续时间表,以及任务数量,计算平均等待时间。

    输入例子:

    [0,1,3,9],[2,1,7,5],4

   输出例子:

   0.5

 

解题思路:

按照持续时间长短排序,只要请求时刻<=当前时刻就执行,否则找满足请求时刻<=当前时刻,持续时间次短的执行。

 

#include <iostream>  

#include <vector>  

using namespace std;



void sortDuration(int *arr1, int *arr2, int n){      //arr1为排序数列,arr2为跟随变化数列,第一行不参加排序  

    for (int i = 0; i < n; i++)

        for (int j = 1; j<n - 1 - i; j++)

            if (arr1[j]>arr1[j + 1]){

                int temp1 = arr1[j];

                int temp2 = arr2[j];

                arr1[j] = arr1[j + 1];

                arr2[j] = arr2[j + 1];

                arr1[j + 1] = temp1;

                arr2[j + 1] = temp2;

            }

}



int main(){

    int request[4] = { 0, 1, 3, 9 };

    int duration[4] = { 2, 1, 7, 5 };

    int n = 4;

    int time = duration[0];

    double wait = 0;

    vector<bool> book;



    for (int i = 0; i < n; i++)

        book.push_back(0);

    sortDuration(duration, request, n);

    for (int i = 0; i < n; i++)

        for (int j = 1; j < n; j++)

            if (book[j] == 0 && request[j] <= time){

                book[j] = 1;

                wait += time - request[j];

                time += duration[j];

                break;

            }

    wait = wait / n;

    cout << wait << endl;

    //getchar();  

}

 

 

 

 

 

 

最短作业优先(SJF)