精华内容
下载资源
问答
  • 调度算法

    2016-08-25 23:16:23
    调度算法

    调度算法

    调度算法是指:根据系统的资源分配策略所规定的资源分配算法。

    调度的基本准则包括CPU利用率、系统吞吐量、周转时间、等待时间、响应时间等。

    系统吞吐量:单位时间内CPU完成作业的数量

    周转时间:作业完成时刻减去作业到达时刻

    带权周转时间:周转时间与系统为它提供服务的时间之比

    等待时间:进程处于等处理器状态的时间之和,等待时间越长,用户满意度越低

    响应时间:从用户提交请求到系统首次产生响应所用的时间

     

    1.     先来先服务和短作业(进程)优先调度算法

    1)     先来先服务调度算法(FCFS)

    比较有利于长作业(进程),不利于短作业(进程)。即利于CPU繁忙型的作业(进程)不利于I/O繁忙型的作业(进程)。

    2)     短作业(进程)优先调度算法(SJF/SPF)

    缺点:①对长作业不利,导致长作业(进程)长期不被调度;②未考虑作业的紧迫程度,不能保证紧迫型作业被及时处理;③作业长短只是根据用户所提供的估计执行时间而定,而用户可能会有意或无意缩短其作业的估计运行时间,致使该算法不一定能真正做到短作业优先调度

    2.     高优先权优先调度算法

    类型:非抢占式和抢占式

           高响应比优先调度算法

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

           该算法既照顾了短作业,又考虑了作业到达的先后次序,不会使长作业长期得不到服务。

    3.     基于时间片的轮转调度算法

    1)     时间片轮转法:系统将所有就绪进程按先来先服务的原则排成一个队列,每次调度时,把CPU分配给队首进程,并令其执行一个时间片。当执行时间片用完,停止该进程的执行并将它送往就绪队列的末尾,然后再把处理机分配给就绪队列中新的队首进程。

    2)     多级反馈队列调度算法

    短进程优先调度算法仅照顾了短进程而忽略了长进程,而且如果未指明进程的长度,则短进程优先和基于进程长度的枪占式调度算法(高响应比优先调度算法)都无法使用。而多级反馈队列调度算法不必事先知道各种进程所需的执行时间,而且还可以满足各种类型进程的需要。

    过程:①设置多个就绪队列,并为各个队列赋予不同的优先级。第一个队列的优先级最高,第二个次之,其余的逐个降低。赋予各个队列中进程执行时间片的大小也不同,优先权越高的队列中,为每个进程所规定的执行时间片就越小,如第二个比第一个队列的时间片长一倍;②当一个新进程进入内存后,首先将它放入第一队列末尾,按FCFS原则排队等待调度。当轮到该进程执行时,如它能在该时间片内完成,便可准备撤离系统,如果在一个时间片结束时为完成,调度程序将该进程放入下一个队列的末尾……仅当第1~(i-1)队列均空时,才会调度第i队列中的进程。

    展开全文
  • 调度算法调度算法调度算法调度算法调度算法调度算法调度算法调度算法
  • SystemOperation:高响应比优先调度算法,作业调度算法,进度调度算法,银行家算法,缓存管理实验
  •  掌握进程调度算法,如先来先服务调度算法(first come first served,FCFS)、短作业优先调度算法(shotjob first,SJF)、时间片轮转调度算法。 二、 实验内容设计模拟实现FCFS、SJF、时间片轮转调度算法的C语言...

    一、  实验目的和要求

    1.  了解进程调度算法的特点

    2.  掌握进程调度算法,如先来先服务调度算法(first come first served,FCFS)、短作业优先调度算法(shotjob first,SJF)、时间片轮转调度算法。

     

    二、    实验内容

    设计模拟实现FCFS、SJF、时间片轮转调度算法的C语言程序

    1.  FCFS算法:按照作业/进程进入队列的先后顺序进行挑选,先进入的将先进行后续步骤的处理。

    2.  SJF算法:以进入系统的作业所要求的CPU运行时间的长短为挑选依据,优先选取预计所需服务时间最短的作业进行调度,可以分别用于高级调度和低级调度。

    3.  时间片轮转算法:将所有的就绪进程按先来先服务的原则排成一个队列,每次调度时,把处理机分配给队首进程,并令其执行一个时间片。

     

    三、  实验步骤

    1.  使用C++语言编译程序。

    2.  完成算法代码。

    3.  运行程序,算出结果。

     

    四、     实验源程序

    代码:

    #include <stdio.h>

    #include <iostream>

    #include <queue>

    #include <stack>

    #include <set>

    #include <string>

    #include <cstring>

    #include <cmath>

    #define MAX 1111

    const double Max = 11111.0;

    using namespace std;

    typedef struct FCFS

    {

        int mark;

        string name;

        doublearrivetime;

        doubleservetime;

        doublestarttime;

        doublefinishtime;

        doubleroundtime;

        doubledaiquantime;

        bool operator< (const FCFS &a)const{

            returnarrivetime > a.arrivetime;

        }

    }FCFS;

     

    typedef struct SJF

    {

        int mark;

        string name;

        doublearrivetime;

        doubleservetime;

        doublestarttime;

        doublefinishtime;

        doubleroundtime;

        doubledaiquantime;

        bool operator< (const SJF &a)const{

            returnservetime > a.servetime;

        }

    }SJF;

     

    typedef struct RDRN

    {

        int mark;

        bool flag =true;

        string name;

        double Count =0.0;

        doublearrivetime;

        doubleservetime;

        doublestarttime;

        doublefinishtime;

        doubleroundtime;

        doubledaiquantime;

        double running= 0.0;

        bool operator< (const RDRN &a)const{

            returnCount > a.Count;

        }

    }RDRN;

     

     

    void FCFS_arithmetic()

    {

        FCFS f[MAX];

        FCFS ff;

        int n;

        doubleaveragedaiquantime = 0.0;

       priority_queue<FCFS> q1;

        printf("请输入作业数(整数)\n");

       scanf("%d",&n);

        printf("请输入n组数据,每组数据包括作业名字(字符串)、作业到达时间(浮点数)、作业服务时间(浮点数)(每组数据的给元素之间用空格隔开!):\n");

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

            f[i].mark =i;

           cin>>f[i].name;

            scanf("%lf%lf",&f[i].arrivetime,&f[i].servetime);

           q1.push(f[i]);

        }

        doublestarttime = 0.0;

        ff = q1.top();

        q1.pop();

       f[ff.mark].starttime = ff.arrivetime;

       f[ff.mark].finishtime = f[ff.mark].starttime + ff.servetime;

       f[ff.mark].roundtime = f[ff.mark].finishtime - f[ff.mark].arrivetime;

       f[ff.mark].daiquantime = f[ff.mark].roundtime / f[ff.mark].servetime;

        starttime =f[ff.mark].finishtime;

        printf("先来先服务调度算法的作用时间表:\n\n");

        printf("作业名字 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间\n");

       cout<<"  "<<f[ff.mark].name;

    printf("%10.2f %8.2f %8.2f %8.2f %8.2f%8.2f\n",f[ff.mark].arrivetime,f[ff.mark].servetime,f[ff.mark].starttime,f[ff.mark].finishtime,f[ff.mark].roundtime,f[ff.mark].daiquantime);

       while(!q1.empty()){

            ff =q1.top();

            q1.pop();

           f[ff.mark].starttime = starttime;

           f[ff.mark].finishtime = f[ff.mark].starttime + ff.servetime;

           f[ff.mark].roundtime = f[ff.mark].finishtime - f[ff.mark].arrivetime;

           f[ff.mark].daiquantime = f[ff.mark].roundtime / f[ff.mark].servetime;

           averagedaiquantime += f[ff.mark].daiquantime;

            starttime =f[ff.mark].finishtime;

           cout<<"  "<<f[ff.mark].name;

    printf("%10.2f %8.2f %8.2f %8.2f %8.2f%8.2f\n",f[ff.mark].arrivetime,f[ff.mark].servetime,f[ff.mark].starttime,f[ff.mark].finishtime,f[ff.mark].roundtime,f[ff.mark].daiquantime);

        }

        printf("\n平均代权周转时间:\n");

       printf("%.2f\n",averagedaiquantime/n);

    }

     

    void SJF_arithmetic()

    {

        SJF f[MAX];

        SJF ff;

        int n;

        doublestarttime = Max;

        doubleaveragedaiquantime = 0.0;

       priority_queue<SJF> q1;

        printf("请输入作业数(整数)\n");

       scanf("%d",&n);

        printf("请输入n组数据,每组数据包括作业名字(字符串)、作业到达时间(浮点数)、作业服务时间(浮点数)(每组数据的给元素之间用空格隔开!):\n");

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

            f[i].mark =i;

           cin>>f[i].name;

           scanf("%lf %lf",&f[i].arrivetime,&f[i].servetime);

           if(f[i].arrivetime < starttime) starttime = f[i].arrivetime;

           q1.push(f[i]);

        }

        printf("短作业优先调度算法的作用时间表:\n\n");

        int cnt = 0;

       while(!q1.empty()){

            SJFtemp[MAX];

            ff =q1.top();

            q1.pop();

           if(f[ff.mark].arrivetime <= starttime){

                for(inti=0; i<cnt; i++) q1.push(temp[i]);

                cnt =0;

               f[ff.mark].starttime = starttime;

               f[ff.mark].finishtime = f[ff.mark].starttime + ff.servetime;

               f[ff.mark].roundtime = f[ff.mark].finishtime - f[ff.mark].arrivetime;

               f[ff.mark].daiquantime = f[ff.mark].roundtime / f[ff.mark].servetime;

               averagedaiquantime += f[ff.mark].daiquantime;

               starttime = f[ff.mark].finishtime;

            }

            elsetemp[cnt++] = ff;

        }

        printf("作业名字 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间\n");

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

           cout<<"  "<<f[i].name;

           printf("%10.2f %8.2f %8.2f %8.2f %8.2f%8.2f\n",f[i].arrivetime,f[i].servetime,f[i].starttime,f[i].finishtime,f[i].roundtime,f[i].daiquantime);

        }

        printf("\n平均代权周转时间:\n");

       printf("%.2f\n",averagedaiquantime/n);

    }

     

    void RDRN_arithmetic()

    {

        doubletimeslice;

        RDRN f[MAX];

        RDRN temp[MAX];

        int cnt = 0;

        RDRN ff;

        int n;

        doubleaveragedaiquantime = 0.0;

       priority_queue<RDRN> q1;

        printf("请输入作业数和时间片长度(作业数为整数,时间片长度可为浮点数,中间用空格隔开!):\n");

        scanf("%d%lf",&n,&timeslice);

        int tot = n;

        printf("请输入n组数据,每组数据包括作业名字(字符串)、作业到达时间(浮点数)、作业服务时间(浮点数)(每组数据的给元素之间用空格隔开!):\n");

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

            f[i].mark =i;

           cin>>f[i].name;

           scanf("%lf %lf",&f[i].arrivetime,&f[i].servetime);

            f[i].Count= f[i].arrivetime;

           q1.push(f[i]);

        }

        double clock =q1.top().arrivetime;

        int t = 0;

        while(t != n){

            ff =q1.top();

           if(f[ff.mark].arrivetime <= clock && tot-- > 0){

               q1.pop();

               if(f[ff.mark].flag){

                   f[ff.mark].starttime = clock;

                   f[ff.mark].flag = false;

                }

     

               if(f[ff.mark].running != f[ff.mark].servetime){

                   double newtime = f[ff.mark].servetime - f[ff.mark].running;

                   if(newtime >= timeslice){

                       clock += timeslice;

                       f[ff.mark].running += timeslice;

                       f[ff.mark].Count += timeslice;

                    }

                   else{

                       clock += newtime;

                       f[ff.mark].running += newtime;

                       f[ff.mark].Count += newtime;

                    }

                   if(f[ff.mark].running != f[ff.mark].servetime) temp[cnt++] = f[ff.mark];

                }

     

               if(f[ff.mark].running == f[ff.mark].servetime){

                   t++;

                   f[ff.mark].finishtime = clock;

                   f[ff.mark].roundtime = f[ff.mark].finishtime - f[ff.mark].arrivetime;

                   f[ff.mark].daiquantime = f[ff.mark].roundtime / f[ff.mark].servetime;

                   averagedaiquantime += f[ff.mark].daiquantime;

                }

            }

     

            else{

                for(inti=0; i<cnt; i++) q1.push(temp[i]);

                cnt =0;

                tot =q1.size();

            }

        }

     

        printf("时间轮转调度算法的作用时间表:\n\n");

        printf("作业名字 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间\n");

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

           cout<<"  "<<f[i].name;

    printf("%10.2f %8.2f %8.2f %8.2f %8.2f %8.2f\n",f[i].arrivetime,f[i].servetime,f[i].starttime,f[i].finishtime,f[i].roundtime,f[i].daiquantime);

        }

        printf("\n平均代权周转时间:\n");

       printf("%.2f\n",averagedaiquantime/n);

    }

     

    int main()

    {

       printf("********************************************************欢迎您!***********************************************************\n");

        int ca = 0;

        do{

           printf("\n请选择调度算法或结束程序:\n");

           printf("0、结束程序\n1、先来先服务\n2、短作业优先\n3、时间片轮转\n");

           scanf("%d",&ca);

            if(ca == 1)FCFS_arithmetic();

            if(ca == 2)SJF_arithmetic();

            if(ca == 3) RDRN_arithmetic();

        }while(ca);

        return 0;

    }

     

    五、  实验结果

    先来先服务调度算法:

    短作业优先调度算法:

     

    时间片轮转调度算法:

     


     

     


    展开全文
  • 自己写的磁盘调度算法,通俗易懂,其中有先来先服务调度算法,最短寻道时间调度算法、电梯调度算法
  • 优先级调度算法3.多级反馈队列调度算法4.三种算法的对比总结 0.思维导图 1.时间片轮转—RR Round-Robin 时间片为2举例 以时间片为5举例 可能出现的问题,比如与FCFS对比 2.优先级调度算法 非抢占式例子 -...


    0.思维导图

    在这里插入图片描述

    1.时间片轮转—RR

    • Round-Robin
      在这里插入图片描述
    • 时间片为2举例
      在这里插入图片描述在这里插入图片描述
    • 以时间片为5举例
      在这里插入图片描述
    • 可能出现的问题,比如与FCFS对比
      在这里插入图片描述
      在这里插入图片描述

    2.优先级调度算法

    在这里插入图片描述

    • 非抢占式例子
      在这里插入图片描述- 抢占式例子

    在这里插入图片描述

    • 补充
      在这里插入图片描述

    3.多级反馈队列调度算法

    在这里插入图片描述
    在这里插入图片描述

    • 举个例子
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述

    4.三种算法的对比总结

    在这里插入图片描述

    展开全文
  • 时间片轮转调度算法、优先级调度算法、多级反馈队列调度算法 1.先了解下算法的评估 cpu 利用率 = 忙碌时间 / 总时间 系统吞吐量 = 总共完成多少道作业 / 总共花了多少时间 周转时间 周转时间:(作业提交到 操作系统...

    本章讲解三种调度算法。时间片轮转调度算法、优先级调度算法、多级反馈队列调度算法

    1.先了解下算法的评估

    cpu 利用率 = 忙碌时间 / 总时间
    系统吞吐量 = 总共完成多少道作业 / 总共花了多少时间

    周转时间

    周转时间:(作业提交到 操作系统开始,到作业完成)包括四个部分

    1. 从外存中后备队列等待作业调度(高级调度)的时间
    2. 进程在就绪队列等待进程调度(低级调度)的时间
    3. 进程在cpu执行的时间
    4. 进程等待IO操作完成的时间
      (作业)周转时间 = 作业完成时间 - 作业提交时间
      平均周转时间 = 各作业周转时间之和 / 作业数

    带权周转时间 = 作业周转时间 / 作业实际运行时间
    平均带权周转时间 = 各作业带权周转时间之和 / 作业数

    等待时间

    进程/作业处于等待处理机状态时间之和

    1. 对于进程:进程建立后等待被服务的时间之和
    2. 对于作业:除了进程建立后的等待还包括作业在外存后备队列中等待的时间

    相应时间

    用户提交请求到首次产生相应所用的时间

    2.时间片轮转调度算法

    1. 算法思想
      公平、轮流为每个进程服务、每个进程在一定时间内得到相应
    2. 算法规则
      按照到达就绪队列的顺序,轮流让各个进程执行一个时间片。若一个进程未在一个时间片中完成任务,剥夺处理机,将进程重新放到就绪队列队尾重新排队
    3. 作业/进程调度
      作业放入内存建立了相应进程后,才能被分配处理机时间片
    4. 是否可抢占
      若进程未在时间片内运行完成,将被强行剥夺时间片使用权(抢占式)。由时钟装置发时钟中断来通知cpu时间片已到
    5. 优缺点
      优点:公平,相应快,适用于分时操作系统
      缺点:高频率的进程切换,需要开销,不区分任务紧急程度
    6. 不会导饥饿现象
    7. 时间片太大=先来先服务算法
    8. 时间片太小,进程调度频繁

    3.优先级调度算法

    1. 算法思想
      根据任务的紧急程度决定处理的顺序
    2. 算法规则
      每个作业/进程都有各自的优先级,调度时选择优先级最高的作业/进程
    3. 作业/进程调度
      作业/进程调度都适用
    4. 是否抢占
      非抢占:进程主动放弃处理机
      抢占式:就绪队列变化,检查是否发生抢占
    5. 优缺点
      优点:适用于实时操作系统、可灵活调整对作业/进程的偏好程度
      缺点:源源不断有高优先级到来,可能导致饥饿

    4.多级反馈队列调度算法

    1. 算法思想
      对之前算法的折中权衡
    2. 算法规则
      多级就绪队列,各级队列优先级从高到低,时间片从小到大
      新进程首先进入1级队列,FCFS原则分配时间片。若时间片用完进程未结束,则进程放入下一级队列的队尾
      若当前进程还未结束时,到达了更高优先级的进程,当前进程插入到当前级别队列的队尾
      只有k级队列未空时候,才为k+1级队列分配处理机
    3. 用于进程调度
    4. 是否可抢占
      抢占式算法,在k级队列运行过程中,新进程会抢占处理机,原来运行的进程放回k级队列队尾
    5. 优缺点
      优点:进程相对公平,新进程会得到相应,短进程只用较短时间完成,灵活调整进程的偏好程度
      缺点:会导致饥饿现象

    算法对比

    在这里插入图片描述

    展开全文
  • 用C语言实现了先来先服务(FCFS)、短作业优先(SJF)、响应比高优先(HRRF)、优先权高优先(HPF)四种作业调度算法,程序同样适用于进程调度算法。以文件形式提交输入,附样例输入文件job.txt。
  • 文章目录一、先来先服务(FCFS)调度算法二、最短作业优先(SJF)算法1. 非抢占式SJF2. 抢占式SJF三、优先级调度算法1. 非抢占式优先级调度算法2. 抢占式优先级调度算法四、时间片轮转(RR)算法五、多级队列调度 一...
  • 1.作业调度与进程调度算法 作业调度算法: 先来先服务调度算法(FCFS) 短作业优先调度算法(SJF) 优先级调度算法 高响应比优先调度算法 进程调度算法: 先来先服务调度算法(FCFS) 短进程优先调度算法(SPF) ...
  • 一 ,先来先服务的调度算法 1.1 优缺点 二,最短作业优先算法SJF 2.1 SJF算法的优缺点: 2.2 SJF调度算法的问题: 三,高优先级调度算法 3.1 优先级调度的含义 3.2 调度算法的两种方式 3.3 优先级的类型 ...
  • cpu调度算法

    2018-12-12 13:24:02
    cpu常见的调度算法,有FCFS调度算法、PS调度算法、SJF调度算法、RR调度算法
  •  掌握磁盘调度算法,如先来先服务(firstcome first served,FCFS)调度算法、最短寻道时间优先(shortest seek timefirst,SSTF)调度算法、扫描(SCAN)调度算法、循环扫描(C-SCAN)调度算法。二、 实验内容设计...
  • 先来先服务FCFS调度算法短作业优先SJF算法优先级调度算法PSA高响应比优先调度算法HRRN轮转调度算法RR多级反馈队列调度算法实现实时调度的基本条件1. 提供必要的信息2. 系统处理能力强3. 采用抢占式调度机制4. 具有...
  • 实时操作系统:优先级调度算法 非抢占式 抢占式优先级调度算法:新进程来的时候判断一下是不是要抢占只有第1级队列所以的运行完了才会把CPU给第2级队列,P2在第二级队列运行到1个时间片后 P3到达第1级队列,此时P2就...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 23,892
精华内容 9,556
关键字:

调度算法