精华内容
参与话题
问答
  • 操作系统 时间片轮转调度算法

    万次阅读 2015-08-17 21:34:00
    时间片轮转法(RR) 算法描述:用于分时系统中的进程调度。每次调度时,总是选择就绪队列的队首进程,让其在CPU上运行一个系统预先设置好的时间片。一个时间片内没有完成运行的进程,返回到绪队列末尾重新排队,等待...

     时间片轮转法(RR)

    算法描述:用于分时系统中的进程调度。每次调度时,总是选择就绪队列的队首进程,让其在CPU上运行一个系统预先设置好的时间片。一个时间片内没有完成运行的进程,返回到绪队列末尾重新排队,等待下一次调度。

    【例】进程A、B、C、D需要运行的时间分别为20ms、10 ms、15 ms、5 ms,均在0时刻到达。到达的先后次序为A、B、C、D。如果时间片分别为1 ms和5ms,计算各个进程的带权周转时间和平均带权周转时间。

     

    分析 在掌握了时间片轮转法概念的基础上,我们可以用一个执行时间图来形象地表示作进程的执行情况,帮助我们理解此题。具体如下:


    根据执行时间图就可以计算各个进程的带权周转时间和平均带权周转时间了。这里要注意的是,要记住带权周转时间和平均带权周转时间的算术公式:

    带权周转时间W,即:

     W = T/R

    其中T为周转时间,R为实际运行时间。

    平均带权周转时间为:


    解:采用时间片轮转法进行调度,算法的性能指标如下:

    到达时间

    到达时间

    运行时间

    开始时间

    完成时间

    周转时间

    带权

    周转时间

    时间片=1

    A

    0

    20

    0

    50

    50

    2.5

    B

    0

    10

    1

    34

    34

    3.4

    C

    0

    15

    2

    45

    45

    3.0

    D

    0

    5

    3

    20

    20

    4.0

    平均周转时间=37.25      平均带权周转时间=3.225

    时间片=5

    A

    0

    20

    0

    50

    50

    2.5

    B

    0

    10

    5

    30

    30

    3.0

    C

    0

    15

    10

    45

    45

    3.0

    D

    0

    5

    15

    20

    20

    4.0

    平均周转时间=36.25      平均带权周转时间=3.125

     

     

    感兴趣的同学还可以根据时间片从1~10的变化,多计算几次,并分析每次计算得到的平均周转时间,做一条平均周转时间随时间片变化的曲线,来体会时间片的变化对平均周转时间的影响,并分析原因。

    展开全文
  • 时间片轮转调度算法的C语言模拟实现

    万次阅读 多人点赞 2016-04-17 12:23:36
    时间片轮转调度是一种最古老,最简单,最公平且使用最广的算法。每个进程被分配一个时间段,称作它的时间片,即该进程允许运行的时间。如果在时间片结束时进程还在运行,则CPU将被剥夺并分配给另一个进程。如果进程...

           时间片轮转调度是一种最古老,最简单,最公平且使用最广的算法。每个进程被分配一个时间段,称作它的时间片,即该进程允许运行的时间。如果在时间片结束时进程还在运行,则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束,则CPU当即进行切换。

          以下是C算法的模拟实现:

    #include<stdio.h>
    #define MAX 10
    struct task_struct
    {
        char name[10];           /*进程名称*/
        int number;              /*进程编号*/
        float come_time;         /*到达时间*/
        float run_begin_time;     /*开始运行时间*/
        float run_time;          /*运行时间*/
        float run_end_time;      /*运行结束时间*/
        int priority;           /*优先级*/
        int run_flag;          /*调度标志*/
        int start_flag;     //是否为第一次开始调度
    } tasks[MAX];
    int counter; /*实际进程个数*/
    int time_counter=0;
    int poutput(); /*调度结果输出*/
    int time();
    int charge();//判断是否所有的进程都被执行过
    
    void main()
    {
    
        pinput();
        printf("时间片轮转算法。\n\n");
        time();
        poutput();
    }
    
    int time()
    {
        float time_temp=0;
        int i;
        int j=0;
        int k=0;
    
        struct task_struct  copy_task[MAX];//备份
        for(i=0; i<counter; i++)
        {
            copy_task[j++]=tasks[i];//对进程的初始化信息备份
        }
    
        time_temp=tasks[0].come_time;
        while(charge())
        {
            for(i=0; i<counter; i++)
            {
                if(tasks[i].come_time>time_temp)
                {
                    time_temp=tasks[i].come_time;
                }
                if(tasks[i].run_flag==0)//该进程还未结束
                {
                    if(tasks[i].start_flag==0)  //该条件成立则说明,该进程是第一次执行,记录开始执行时间
                    {
                        tasks[i].run_begin_time=time_temp;
                        tasks[i].start_flag=1;
                    }
                    if(tasks[i].run_time/time_counter>1)//至少有两倍的时间片未执行
                    {
                        tasks[i].run_time=tasks[i].run_time-time_counter;
                        time_temp=time_temp+time_counter;
                    }
                    else if(tasks[i].run_time-time_counter==0)
                    {
                        time_temp=time_temp+time_counter;
                        tasks[i].run_end_time=time_temp;
                        tasks[i].run_flag=1;
                        tasks[i].run_time=copy_task[i].run_time;
                    }
                    else//仅剩下不足一倍的时间片
                    {
                        time_temp=time_temp+tasks[i].run_time;
                        tasks[i].run_end_time=time_temp;
                        tasks[i].run_flag=1;
                        tasks[i].run_time=copy_task[i].run_time;
                    }
                }
            }
        }
    }
    
    int charge()//判断是否全部进程都执行完毕
    {
        int k;
        int super_flag=0;//判断是否全部的进程都执行完毕
        for(k=0; k<counter; k++)
        {
            if(tasks[k].run_flag==0)
            {
                super_flag=1;
                return super_flag;
                break;
            }
            else
            {
                super_flag=0;
            }
        }
        return super_flag;
    }
    
    int pinput() /*进程参数输入*/
    {
        int i;
        printf("please input the process counter:\n");
        scanf("%d",&counter);
        printf("please input the length of time:\n");
        scanf("%d",&time_counter);
        for(i=0; i<counter; i++)
        {
            printf("******************************************\n");
            printf("please input the process of %d th :\n",i+1);
            printf("please input the name:\n");
            scanf("%s",tasks[i].name);
            printf("please input the number:\n");
            scanf("%d",&tasks[i].number);
            printf("please input the come_time:\n");
            scanf("%f",&tasks[i].come_time);
            printf("please input the run_time:\n");
            scanf("%f",&tasks[i].run_time);
            printf("please input the priority:\n");
            scanf("%d",&tasks[i].priority);
            tasks[i].run_begin_time=0;
            tasks[i].run_end_time=0;
            tasks[i].run_flag=0;  //运行是否结束
            tasks[i].start_flag=0;//是否首次被执行
        }
        return 0;
    }
    
    int poutput() /*调度结果输出*/
    {
        int i;
        float turn_round_time=0,f1,w=0;
        printf("进程名 进程号 到达时间 运行时间 开始时间 结束时间 优先级 周转时间\n");
        for(i=0; i<counter; i++)
        {
            f1=tasks[i].run_end_time-tasks[i].come_time;
            turn_round_time+=f1;
            printf("%s\t%d\t%5.3f\t%5.3f\t%5.3f\t %5.3f\t   %d\t  %5.3f\n",tasks[i].name,tasks[i].number,tasks[i].come_time,tasks[i].run_time,tasks[i].run_begin_time,tasks[i].run_end_time,tasks[i].priority,f1);
        }
        printf("average_turn_round_timer=%5.2f\n",turn_round_time/counter);
        return 0;
    }
    展开全文
  • 调度算法:时间片轮转

    千次阅读 2018-01-28 21:29:34
    时间片轮转法:每个进程被分配一时间段,称作它的时间片,即该进程允许运行的时间。  如果在时间片结束时进程还在运行,则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束,则CPU当即进行切换...
    

    
    
    时间片轮转法:每个进程被分配一时间段,称作它的时间片,即该进程允许运行的时间。

     如果在时间片结束时进程还在运行,则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束,则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表,当进程用完它的时间片后,它被移到队列的末尾。

     时间片设得太短会导致过多的进程切换,降低了CPU效率;而设得太长又可能引起对短的交互请求的响应变差。将时间片设为100毫秒通常是一个比较合理的折中。

    展开全文
  • 按照时间片轮转调度进程| 动态地输入进程(key,run_time,message),按照输入次序建立就绪队列l 输入CPU运行的单位时间片(cpu_base_time)l 按照时间片轮转方式模拟进程逐个被调度并执行单位时间片(运行结束进程结束,...

    按照时间片轮转调度进程

    | 动态地输入进程(key,run_time,message),按照输入次序建立就绪队列

    l 输入CPU运行的单位时间片(cpu_base_time)

    l 按照时间片轮转方式模拟进程逐个被调度并执行单位时间片(运行结束进程结束,否则修改进程运行时间run_time,将该进程放置在就绪队列尾巴)。
    (1)假设系统有5个进程,每个进程用一个进程控制块PCB来代表,PCB的格式如右图所示。其中:
    进程名:即进程标识。
    链接指针:指出下一个到达进程的进程控制块首地址。按照进程到达的顺序排队。系统设置一个队头和队尾指针分别指向第一个和最后一个进程。新生成的进程放队尾。
    估计运行时间:可由设计者任意指定一个时间值。
    到达时间:进程创建时的系统时间或由用户指定。调度时,总是选择到达时间最早的进程。
    进程状态:为简单起见,这里假定进程有两种状态:就绪和完成。并假定进程一创建就处于就绪状态,用R表示。当一个进程运行结束时,就将其置成完成态,用C表示。
    (2)为每个进程任意确定一个要求运行时间和到达时间。
    (3)按照进程到达的先后顺序排成一个循环队列。再设一个队首指针指向第一个到达进程的首址。
    (4)执行处理机调度时,开始选择队首的第一个进程运行。另外再设一个当前运行进程指针,指向当前正运行的进程。
    (5)由于本实验是模拟实验,所以对被选中进程并不实际启动运行,而只是执行:
    ①估计运行时间减1个时间片;
    ②输出当前运行进程的名字。
    用这两个操作来模拟进程的一次运行。

    #include <malloc.h>
    #include <stdio.h>
    #include <string.h>
    #define NULL 0
    typedef struct table
     {
       int key;               /*进程ID号*/
       int run_time;         /*进程运行时间*/
       char message[10];     /*进程说明信息*/
       struct table *next;
     }node;
    node *creat(void)      /*定义函数,输入ID号和顺序号,按照输入次序建立进程链表*/
    {
       node *head,*p1,*p2;
       int n=0;
       p1=p2=(node *)malloc(sizeof(node));
       scanf("%d %d %s",&p1->key,&p1->run_time,&p1->message);
       head=NULL;
       while (p1->run_time>0)
        {
         n=n+1;
             if (n==1) head=p1;
         else p2->next=p1;
         p2=p1;
         p1=(node *) malloc (sizeof(node));
       scanf("%d %d %s",&p1->key,&p1->run_time,&p1->message);
        }
       p2->next=NULL;
       return(head);
    }
    void print (node *head)  /*输出链表*/
      {
        node *p;
        p=head;
       if(!p)
       {
           printf("该链表为空!");
       }
       else
       {
           while(p)
           {
               printf("%d , ",p->key);
               printf("%d , ",p->run_time);
               printf("%s",p->message);
               p=p->next;
               printf("\n");
           }
       }
     }
    
    node *insert(node *head,node *news)   /*将进程news插入到队列尾部*/
      {
        node *t;
        t=head;
        while(t->next)
        {
            t=t->next;
        }
        t->next=news;
        news->next=NULL;
         return head;
     }
    node *timeslice(node *head,int cpu_base_time)
              /*模拟时间片轮转调度过程:队列首进程使用一个时间片的CPU*/
    {
        node *r,*q;
        r=head;
        q=(node *)malloc(sizeof(node));
        if(r->run_time>cpu_base_time)
        {
           q->run_time=r->run_time-cpu_base_time;
           q->key=r->key;
           strcpy(q->message,r->message);
           insert(r,q);
        }
        return head;
    }
    void main()
      {
           int count=0,cpu_base_time;
           node *p;
           printf("新建的进程控制表为:\nkey run_time message\n");
           p=creat();     /*输入进程控制表*/
           printf("所建的进程控制表为:\n");
           print(p);      /*输出原始进程控制表*/
           printf("CPU运行的单位时间片cpu_base_time为:\n");
           scanf("%d",&cpu_base_time);
           while(p)      /*模拟按单位时间片进程逐个被调度并进入CPU运行的过程*/
           {  
               p=timeslice(p,cpu_base_time);
               printf("第%d次被调度的就绪进程:\n",count+1);
               printf("key=%d,run_time=%d,message=%s\n",p->key,p->run_time,p->message);
               printf("recent table is:\n");
               print(p->next);
               printf("\n");
               count++;
               p=p->next;
           }
       printf("distribute is over!\n");
      }
    
    展开全文
  • 时间片轮转调度算法

    千次阅读 2018-05-28 23:22:31
    #include<stdio.h> #define MAX 10 struct task_struct { char name[10]; /*进程名称*/ int number; /*进程编号*/ float arrivetime; /*到达时间*/ float starttime; ...
  • 时间片轮转调度算法的计算

    万次阅读 多人点赞 2018-04-25 14:39:23
    在分时系统中,最简单最常用的就是基于时间片轮转调度算法,时间片轮转调度算法是非常公平的处理机分配方式,让就绪队列的每个进程每次仅运行一个时间片。1.时间片轮转调度算法的基本原理 在时间片轮转调度算法中,...
  • 调度算法之时间片轮转算法

    千次阅读 多人点赞 2018-04-16 16:36:00
    根据先来先服务的原则,将需要执行的所有进程按照到达时间的大小排成一个升序的序列,每次都给一个进程同样大小的时间片,在这个时间片内如果进程执行结束了,那么把进程从进程队列中删去,如果进程没有结束,那么把...
  • 实验1 进程调度 一、实验目的 通过实验加强对进程调度算法的理解和掌握。 二、实验内容 编写程序实现基于优先级的时间片轮转调度算法
  • 求一个基于优先级的时间片轮转调度算法。实在是不太会做了,没思路。要求java 要求: (1)设系统中有n个进程,每个进程PCB格式如下: 进程ID; 进程名称:p1,..., pn; 进程状态:1-运行,2-就绪,3-等待,0-完成;...
  • 进程调度:时间片轮转调度算法

    万次阅读 2016-11-24 14:43:19
    (4) 掌握时间片轮转法进程调度算法 二、实验原理 (1)建立进程控制块 (2)设计两个链队列,分别表示就绪队列和完成队列 (3)用户输入进程标识符,进程到达时间,进程所需的时间,申请空间存放进程,PCB...
  • 时间片轮转调度算法 a.在时间片轮转调度算法中,系统根据先来先服务的原则,将所有的就绪进程排成一个就绪队列,并且每隔一段时间产生一次中断,激活系统中的进程调度程序,完成一次处理机调度,把处理机分配给就绪...
  • 时间片轮转调度算法(C++实现)

    万次阅读 多人点赞 2019-06-05 20:29:19
    时间片轮转调度算法: (1)假设系统中有5个进程,每个进程有一个进程控制块(PCB)来标识。进程控制块内容包括:进程名,链接指针,到达时间,估计运行时间,进程状态。 进程名即进程标识。 链接指针:按照...
  • 在分时系统中,最简单最常用的就是基于时间片轮转调度算法时间片轮转调度算法是非常公平的处理机分配方式,让就绪队列的每个进程每次仅运行一个时间片。 1.时间片轮转调度算法的基本原理  在时间片轮转调度算法中...
  • 操作系统课程设计_时间片轮转调度算法_Java版
  • 时间片轮转调度算法模拟C语言

    千次阅读 2020-01-02 14:37:25
    时间片轮转调度算法模拟C语言 本来要做这么一个作业,准备用C语言写,然后参考网上的一些代码,发现很多都有错误,用课本的例子代入都不对,后来我发现是错在对时间片调度算法的理解。所以在别人的基础上写了以下...
  • 实现短进程优先调度算法(SPF)和时间片轮转调度算法(RR)。
  • (C语言实现)进程调度—时间片轮转调度算法

    万次阅读 多人点赞 2018-07-08 12:02:43
    一、设计目的: 本设计模拟在单处理器情况下的时间片轮转进程调度,目的是加深对进程调度工作的理解,掌握不同调度算法的优缺点。二、设计内容 设计程序模拟单处理机系统中时间片轮转进程调度算法,每个进程由一个...
  • 1、合理设计PCB结构,设计模拟指令格式,并以文件形式存储,程序能够读取文件并自动生成指令序列。2、根据文件内容,建立模拟进程队列,并能采用时间片轮转调度算法对模拟进程进行调度。
  • 1、设计一个程序实现基于优先数的时间片轮转调度算法调度处理器。 2、假定系统有5个进程,每个进程用一个进程控制块PCB开代表 3、每次运行所设计的处理器调度程序调度进程之前,为每个进程任意确定它的要求运行时间...
  • #include #include #include #define time 2 typedef int datatype; typedef struct link_node { char name[20]; int arrive; int sta
  • #include #define N 4 /*源进程大小 可以自己重新规定*/ #define M 6 /*最多只能输入六组数据*/ typedef struct{ char name; int arriver_time; int need_time; }prosse; typedef struct{ prosse *low;...
  • 时间片轮转调度算法(C++代码)

    万次阅读 2007-11-01 09:10:00
    #include #include #include #include typedef struct node{ char name[10]; int prio; int round; int cputime; int needtime; int count; char state; s
  • #include&lt;stdio.h&gt; #define MAX 10 struct task_struct { char name[10]; /*进程名称*/ int number; /*进程编号*/ float come_time; /*到达时间*/ float run_begin_time;...
  • 操作系统|时间片轮转调度算法(RR)

    千次阅读 2019-12-02 22:26:18
    将进程信息表的信息根据进入时间排序,判断当前时间线下有哪些进程到达,将其插入到等待队列中,等待分配一个时间片,若进程未全部执行结束,将其插入队尾,等待下次分配。 在进行插入队尾前判断当前时间下哪些进程...

空空如也

1 2 3 4 5 ... 20
收藏数 16,615
精华内容 6,646
关键字:

时间片轮转调度