时间片轮转与高响应比优先算法

轮转调度算法

轮转法的基本原理

在轮转(RR)法中，系统根据FCFS策略，将所有的就绪队列排成一个就绪队列，并可设置一定时间间隔（如30ms）产生一次终断，激活系统中的进程调度程序，完成一次调度，将CPU分配给队首进程，另其执行。当该进程的时间片耗尽或运行完毕时，系统再次将CPU分配给新的队首进程（或新到达的紧迫进程），由此，可保证就绪队列中的所有进程在一个确定的时间片内，都能获得一次CPU执行。

进程切换时机

在RR调度算法中，应在何事进行进程的切换，可分为两种情况：

若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将他从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。
在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序就把他送往就绪队列的尾部。

时间片大小确定

如果选择的时间片小，将有利于短作业，因为它能在该时间片内完成。但时间片小，意味着会进行频繁的进程调度和进程上下文的切换，无疑会增加系统的开销。反之，若时间片选择得太长，且为使每个进程都能在一个时间片内完成。RR算法便会退化成FCFS算法，无法满足短作业和交互式用户的需求。 一个较为可取的时间片大小是略大于一次典型的交互所需要的时间，使大多数交互式进程能在一个时间片内完成

高响应比优先调度算法

高响应比优先调度算法为每一个作业引入一个动态优先级，即优先级是可以改变的，令他随等待时间延长而增加，这将使长作业的优先级在等待期间不断的增加，等到足够的时间后，必然会有机会获得处理机。该优先级变化规律为：

优先级 = (等待时间+要求服务时间)/要求服务时间

由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先级又相当于响应比R_p。优先级又可表示为：

优先级 = (等待时间+要求服务时间)/要求服务时间 = 响应时间/要求服务时间

由上式可以看出

如果作业的等待时间相同，则要求服务的时间愈短，其优先级愈高，因而类似于SJF算法，有利于短作业。
当要求服务的的时间相同时，作业的优先级又取决于其等待时间，因而又类似于FCFS算法。
对于长作业的优先级，可以随等待时间的增加而增大，当其等待时间足够长时，也可获得处理机。
在每次进行调度前，都需要进行响应比的计算，显然会增加系统开销。

两种算法代码实现如下：

//进程类
function Process(){
}
Process.list = []; //进程列表
Process.task_num = 5;//进程数
Process.regetRatioAndGetProcess = function(list){ //获得响应比
    list.forEach(function(item){
        item.ratio = ((Date.parse(new Date()) - item.arriveTime) / item.runTime) +1; //一个进程结束后，重新计算响应比
    });
    var maxRatio = 0,NO = -1;
    list.forEach(function(item,index){ //挑选出响应比最大的进程
        if(item.ratio>maxRatio){
            maxRatio = item.ratio;
            NO = index;
        }
    });
    return list.splice(NO,1)[0];
}
//进程初始化
Process.init = function(){
    Process.list.splice(0,Process.list.length);
    for(var i = 0;i<Process.task_num;i++){
        Process.list.push({
            id: i,//进程号
            arriveTime: 0, //进程到达时间
            ratio: 0, //响应比
            runTime: (Math.floor(Math.random()*4)+2)*1000, //运行时间间隔为[2,6]s
        });
    }
}
//-----------------------------------------------------------
//高响应比优先调度算法
var HRRN = {
    list:[], //记录进程响应时间
    init_task: function(list,num){
        list.forEach(function(item){
            item.arriveTime = Date.parse(new Date()); //获得进程到达时间
        });
    },
    //进程运行
    run: function(list,num){
        for(var i = 0;i<num;i++){
            var runItem = Process.regetRatioAndGetProcess(list); //得到响应比最大的进程
            console.log(`第${runItem.id}号进程开始运行：${new Date()}`);
            var t = Date.parse(new Date());
            var exit = t + runItem.runTime;
            while(true){ //模拟进程运行
                if(Date.parse(new Date()) >=exit){
                    break;
                }
            }
            console.log(`第${runItem.id}号进程结束运行：${new Date()}`);
            //记录进程的响应时间 ：现在时间-到达时间
            HRRN.list.push({
                id: runItem.id,
                responseTime: Date.parse(new Date()) - runItem.arriveTime
            });
        }
    },
    //打印进程响应时间，计算平均响应周期
    show:function(){
        var total = 0;
        HRRN.list.forEach(function(item){
            console.log(`${item.id}的响应时间为${Math.floor(item.responseTime)}`);
            total+=Math.floor(item.responseTime);
        });
        console.log(`平均周转周期为${Math.floor(total/HRRN.list.length)/1000}s`);
    }
}
Process.init();
HRRN.init_task(Process.list,Process.task_num);
HRRN.run(Process.list,Process.task_num);
HRRN.show();
//---------------------------------------------------------------
//时间片轮转算法
var RR = {
    circle_size:4000,//时间片大小
    list:[], //记录进程执行时间
    init_task:function(list){ //初始化进程
        list.forEach(function(item){
            item.arriveTime = Date.parse(new Date());
        });
    },
    run:function(list){
        while(true){
            if(list.length===0) break; //进程全部运行完成后，退出死循环
            var item = list.splice(0,1)[0]; //选出队首进程
            var runTime = item.runTime;
            var id = item.id;
            console.log(`第${id}号进程开始运行 :${new Date()}`);
            if(runTime<RR.circle_size){ //如果能够在本时间片内运行完
                var exit = Date.parse(new Date()) + runTime;
                while((Date.parse(new Date()))< exit);
                console.log(`第${id}号进程结束运行,运行时间为${runTime/1000}s :${new Date()}`);
                RR.list.push({
                    id: item.id,
                    responseTime: Date.parse(new Date()) - item.arriveTime
                });
            }else{ //计算下一次需要的运行时间
                item.runTime -= RR.circle_size;
                list.push(item);
                var exit = Date.parse(new Date()) + RR.circle_size;
                while((Date.parse(new Date()))< exit);
                console.log(`${new Date()}:第${id}号进程时间片用完，处于等待状态`);
            }
        }
    },
    //打印每个进程的响应时间与平均周转周期
    show:function(){
        var total = 0;
        RR.list.forEach(function(item){
            console.log(`${item.id}的响应时间为${Math.floor(item.responseTime)}`);
            total+=Math.floor(item.responseTime);
        });
        console.log(`平均周转周期为${Math.floor(total/RR.list.length)/1000}s`);
    }
}
Process.init();
RR.init_task(Process.list);
RR.run(Process.list);
RR.show();