糖果派对官方网站_可以赌钱的糖果游戏_手机版
【bb电子糖果派对】操作系统高响应比优先进范例拟算法

【bb电子糖果派对】操作系统高响应比优先进范例拟算法

作者:操作系统    来源:未知    发布时间:2019-12-30 05:40    浏览量:

  这学期刚开始学习操作系统,收到一个作业,百度关于高响应比优先(HRRN,Highest Response Ratio Next)的CPU进程调度模拟算法,基本思想:短作业优先调度算法 + 动态优先权机制;既考虑作业的执行时间也考虑作业的等待时间,综合了先来先服务(FCFS,First Come First Served)和最短作业优先(SJF,Shortest Job First)两种算法的特点。

 1、什么是进程调度

  之后经过多番揣摩... ...决定界面用命令行算了,反正啥也不会...

  无论是在批处理系统还是分时系统中,用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外,系统进程也同样需要使用处理机。bb电子糖果派对,这就要求进程调度程序按一定的策略,动态地把处理机分配给处于就绪队列中的某一个进程,以使之执行。   

  关于响应比:

 

    RR =  (预计运行时间 + 等待时间) / 预计运行时间 = 1 + 等待时间/预计运行时间;

2、处理机调度分类

  响应比高者优先进行调度;

高级、中级和低级调度作业从提交开始直到完成,往往要经历下述三级调度:

 

  • 高级调度:(High-Level Scheduling)又称为作业调度,它决定把后备进程调入内存运行; 
  • 低级调度:(Low-Level Scheduling)又称为进程调度,它决定把就绪队列的某进程获得CPU; 
  • 中级调度:(Intermediate-Level Scheduling)又称为在虚拟存储器中引入,在内、外存对换区进行进程对换

  关于要求中的周转时间、带权周转时间、平均周转时间和平均带权周转时间:

3、短进程优先

最短CPU运行期优先调度算法(SCBF--Shortest CPU Burst First)

该算法从就绪队列中选出下一个“CPU执行期最短”的进程,为之分配处理机

例如,在就绪队列中有四个进程P1、P2、P3和P4,它们的下一个执行

期分别是16、12、4和3个单位时间,执行情况如下图:

P1、P2、P3和P4的周转时间分别为35、19、7、3,平均周转时间为16。

该算法虽可获得较好的调度性能,但难以准确地知道下一个CPU执行期,而只能根据每一个进程的执行历史来预测。

【bb电子糖果派对】操作系统高响应比优先进范例拟算法。 

4、C语言模式实现

  1》、常量声明和数据结构定义

#include "stdio.h"
#include <stdlib.h>
#include "string.h"
#define NULL 0

typedef struct pcb
{
    char name[10]; //进程名称
    int ArrivalTime; //到达时间 
    int StartTime;   //开始运行时间
    int FinishTime;  //结束运行时间
    int WholeTime;   //运行所需时间

    struct pcb *link; //下一个指针 
}pcb; 
int N;  //运行的进程数量 
void input();
pcb *ready=NULL,*p=NULL,*finish = NULL;  
//ready 是初始时的状态,finish 是结束时状态 
int M; 

 

  2》、输入进程信息函数

void input()
{
    printf("请输入进程数量:");
    scanf("%d",&N);   //N为全局变量
    M = N;
    struct pcb *q = ready;
    int  i = 0;
    for( i=0 ;i<N;i++)
    {
        printf("请输入第 %d 个进程信息-----------n",i+1);
        p = (pcb *)malloc(sizeof(pcb));
        printf("请输入进程名:")    ;
        scanf("%s",p->name);
        printf("请输入进程到达时间:");
        scanf("%d",&p->ArrivalTime);
        printf("请输入进程运行时间:");
        scanf("%d",&p->WholeTime);
        p->link = NULL;
        if(NULL == ready)
        {
            ready = p;    
            q = ready;        
        }
        else
        {
            q = ready;
            while(NULL != q->link)  //将q移动到就绪队列最后一个进程 
            {
                q = q->link;
            }
            p->link = NULL;
            q->link = p;    
            q=p;
        }
        printf("n");
    }
    q= NULL;
    free(q);    
} 

 

  3》、短进程优先算法【核心代码】

//先输入的肯定是先到达的 
//nowTime 是现在执行的时间 
pcb* sjf(int nowTime,int *after)
{
    int i = 0 ;
    pcb *nowProgress=NULL, *p = ready;
    int ProgressNum = 0; // 当前最短的是第几个线程 
    int minTime =0; // 最短运行时间

    if(NULL != ready)
    {
        while(NULL != p) //遍历整个链表,查找出最短的进程,即运行时间最短 
        {
        //    printf("n%d  %d  %d  n",p->ArrivalTime,nowTime >= p->ArrivalTime,nowTime) ;
            if(nowTime >= p->ArrivalTime)
            { 
                if(0 == minTime)  //首次赋值 
                {
                    nowProgress = p;
                    minTime = p->WholeTime;                    
                }
                else
                {
                    if(p->WholeTime < minTime)
                    {
                        nowProgress = p;
                        minTime = p->WholeTime;
                    }
                }

                *after = minTime+nowTime;
            }    
            p = p->link;
        }
    } 

    return nowProgress;    
}

 

  4》、输出每个时刻的进程信息函数

void output(pcb *p,int now_time)
{
    if(NULL == p)
    {
        printf("当前时刻:%d,暂无进程在运行!n",now_time);
    }
    else
    {
            printf("进程名:%s,运行时间:%d,到达时间:%dn",p->name,p->WholeTime,p->ArrivalTime);        
    }    
}

 

  5》、输出进程运行总体情况统计

void outputAll()
{
    pcb *p = finish;
    printf("n-----------------------统计结果:-------------------n");
    float avgRevolve = 0;
    float avgSuperRevolve = 0;

    while(NULL != p)
    {
        avgRevolve += p->StartTime+p->WholeTime-p->ArrivalTime;
        avgSuperRevolve += 1.0*(p->StartTime+p->WholeTime-p->ArrivalTime)/p->WholeTime;
        printf("n进程名:%s,开始时间%d,结束时间:%d,运行时间:%d,到达时间:%dn",p->name,p->StartTime,p->FinishTime,p->WholeTime,p->ArrivalTime);
        p = p->link;    
    }    
        printf("n----这组进程平均周转时间:%f,平均带权平均周转时间:%fn",avgRevolve/M,avgSuperRevolve/M);
} 

   

  6》、删除准备队列(ready)已经运行的进程p ,添加到完成队列(finish)队列中 

// 删除准备队列(ready)已经运行的进程p ,添加到完成队列(finish)队列中 
void destory(pcb *p,int now_time)
{

    pcb *q = ready;
    pcb *f = NULL;
    if(strcmp(p->name,ready->name) == 0)  //第一个进程 
    {
        ready = ready ->link;
    }
    else  //中间进程 
    {
        q = ready;

        while(  (strcmp(q->link->name,p->name) != 0) && NULL != q->link)  //找到p要删除的位置 
        {

            q= q->link;

        }

        q->link = p->link;    



    } 




        //将已经运行的进程添加到finish队列 
        p->StartTime = now_time-p->WholeTime;   
        p->FinishTime = now_time;

        if(NULL == finish)  //第一个完成的进程 
        {
            finish = p;
            p->link = NULL;
        }    
        else  //中间完成的进程 
        {
            f = finish;
            while(NULL != f->link )    
            {
                f = f->link;
            }
            f->link = p;
            p->link = NULL;
        }




    N--;  //等待进程减1 
}

 

  7》、主函数

int main()
{

    input();

    struct pcb *s = ready;  
    int now_time = 0 ;
    struct pcb *nowProgress = NULL;  //当前运行的进程 
    int *after = 0; //执行完一个进程之后的时间 
    int i = 0 ;   

    pcb *m = ready;

    while(N > 0)//一次运行一个进程 
    {
        nowProgress = sjf(now_time,&after);

        if(NULL != nowProgress)  //当前有进程在运行 
        {

        for(;now_time < after;now_time++)  //输出每个时刻运行的进程情况 
        {
            printf("#################################################n");
            printf("当前时刻:%dn",now_time);
             printf("n-------------当前执行进程:----------n"); 
                 output(nowProgress,now_time);
                 printf("n-------------等待执行进程:----------n");
            m=ready;
            while(NULL != m)
            {
                if(m != nowProgress)
                {
                    if(m->ArrivalTime <= now_time)
                    output(m,now_time);
                }
                m= m->link;
            }
            printf("#################################################nn");
        }

            printf("n");

            destory(nowProgress,now_time); 

        }
        else   //没有进程在运行 
        {
            output(nowProgress,now_time);
            now_time ++; 
        }

    }            
    outputAll();
    return 0;
}

 

  8》、测试

输入数据:

bb电子糖果派对 1

 

运行结果:

bb电子糖果派对 2

 

省略中途的截图,这里只给出最后的总计情况的截图

 

bb电子糖果派对 3

 

  实际上,进程调度有很多种进程调度的方式,不同的进程调度方式,他们的优缺点各有不同,而且他们的适用场景也不尽相同,这里只给出了短进程优先的调度方式。下面我们来比较一下,一些调度方式【只是部分】的优缺点:

1.先来先服务(FCFS, First Come First Serve),按先后顺序进行调度。 
(1)、适用场景:
比较有利于长进程,而不利于短进程。因为长进程会长时间占据处理机。
有利于CPU繁忙的进程,而不利于I/O繁忙的进程。 

(2)、优点:

有利于长进程,有利于等待时间久的进程,不会有进程长期等待而得不到响应。有利于CPU频繁的进程。

(3)、缺点:

不利于短进程,忽视了进程的运行时间。不利于I/O频繁的进程。

 

 

2. 响应比高者优先(HRN):FCFS和SJF的的折中,动态生成昨夜的优先级。

(1)、优点:

既考虑了进程的等待时间,又考虑了进程的运行时间,是FCFS和SJF的的折中,会考虑让进程短的先进行,随着长进程等待时间的增加,优先级相应的增加,使得通过一定时间的等待,必然有机会获得处理机。

(2)、缺点:

在每次进行调度之前,都需要先做响应比的计算,会增加系统的开销

3. 优先级法(Priority Scheduling):按照进程的优先级,对进程进程调度。

(1)、分类:
静态优先级:
  进程调度中的静态优先级大多按以下原则确定: 
  由用户自己根据进程的紧急程度输入一个适当的优先级。 
  由系统或操作员根据进程类型指定优先级。 
  系统根据进程要求资源情况确定优先级。 
  进程的静态优先级的确定原则: 
  按进程的类型给予不同的优先级。 
  将进程的情态优先级作为它所属进程的优先级。 
动态优先级:
  进程的动态优先级一般根据以下原则确定: 
  根据进程占用有CPU时间的长短来决定。 
  根据就绪进程等待CPU的时间长短来决定。 

(2)、优点:

可以通过优先级反映进程的紧迫程序,使比较紧迫的进程优先运行

(3)、缺点:

需要计算进程的优先级,会产生一定的开销。
4.短进程优先法(SJF, Shortest Job First):短进程优先运行,其目标是减少平均周转时间。 

(1) 优点: 
  比FCFS改善平均周转时间和平均带权周转时间,缩短进程的等待时间; 
  提高系统的吞吐量; 
(2) 缺点: 
  对长进程非常不利,可能长时间得不到执行; 
  未能依据进程的紧迫程度来划分执行的优先级; 
  难以准确估计进程(进程)的执行时间,从而影响调度性能。 

采用SJF算法时,人—机交互无法实现

 完全未考虑进程的紧迫程度,故不能保证紧迫性进程得到及时处理

 

 

 

 

 

 

    周转时间 =(作业完成的时间 - 作业提交时间);

    带权周转时间 = 作业周转时间 / 作业运行时间;

    平均周转时间 = (周转时间1+周转时间2+...+周转时间n)/ n;

    平均带权周转时间 = (带权周转时间1+带权周转时间2+...+带权周转时间n)/ n;

 

上一篇:没有了
下一篇:没有了
友情链接: 网站地图
Copyright © 2015-2019 http://www.tk-web.com. bb电子糖果派对有限公司 版权所有