进程调度算法之先到先服务

偏执的太偏执、 2022-12-23 00:40 125阅读 0赞

## 进程调度算法进程调度算法之先到先服务 ##

先到先服务（First-Come First-Served）

*  优点：  
    编码简单且容易理解；
 *  缺点：  
    平均等待时间往往很长；

## 代码 ##

> 根据个人思路模拟的FCFS,仅供参考

#include <iostream>
    #include <queue>
    
    using namespace std;
    typedef  double TimeType;
    const int MAXN =  1e6+5;
    
    int task_num;
    TimeType now_time; //从第一个到达的作业时间开始
    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_time
        TimeType weight_time; //带权周转时间spend_time/service_time
    
        bool operator< (const StruTask &task)const
        {
        
            if(arrive_time == task.arrive_time)
                return id > task.id;
            return arrive_time > task.arrive_time;
        }
    }arrayTask[MAXN];
    
    priority_queue<StruTask>que;
    
    void get_task()
    {
        
        cout<<"请输入任务数:"<<endl;
        cin>>task_num;
        if(task_num <= 0) return;
        cout<<"----------请输入任务相关信息-------"<<endl;
        for(int i = 1; i <= task_num; ++i)
        {
        
            cout<<"请输入第"<<i<<"个任务的 到达时间 和 服务时间:";
            arrayTask[i].id = i;
            cin>>arrayTask[i].arrive_time;
            cin>>arrayTask[i].service_time;
        }
    }
    
    int get_next_task()
    {
        
        if(!que.empty())
        {
        
            StruTask task = que.top();
            que.pop();
            return task.id;
        }
        return 0;
    
    }
    
    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;
    }
    
    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;
    }
    
    /*
    FCFS:
    First-Come First-Served
    */
    void FCFS()
    {
        
        for(int i = 1; i <= task_num; ++i)
        {
        
            que.push(arrayTask[i]);
        }
        now_time = 0;
        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()
    {
        
        get_task();
        FCFS();
        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;
    }

### 运行示例 ###

3
    0 24
    0 3
    0 3

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70_pic_center]

4
    3 2
    1 5
    6 7
    4 3

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/d8c39a701af44e3fb5f578daa8000022.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201121001958396.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo,size_16,color_FFFFFF,t_70#pic_center