数学模型：操作系统中FCFS、SJF、HRRN算法的平均周转时间比较 c语言

摘  要

研究目的：比较操作系统中进程调度FCFS、SJF、HRRN算法的平均周转时间和带权周转时间的大小关系。

研究方法：在建模分析时，分别举4个进程的例子，1个进程用两个字母分别表示到达时间和执行时间。分两种极端情况，一种是每个进程到达时cpu还在执行之前的进程，这种结果为T(FCFS)>T(HRRN)>T(SJF),W(FCFS)>W(HRRN)>W(SJF)。另一种是每个进程到达时cpu已经处理完之前的进程，这种结果为3种算法的执行都是相同的且T=W=1。而随机数据在两种极端之间。

在进行算法检验时，用c语言随机生成5000个进程，三个函数代表3中不同算法的求解结果。

研究结果与结论：T(FCFS)>=T(HRRN)>=T(SJF),W(FCFS)>=W(HRRN)>=W(SJF)

关键词：初等模型；操作系统进程调度；FCFS；SJF；HRRN

1. 问题重述

    在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。作业调度的主要任务是根据jcb中的信息，检查系统中的资源能否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为他们创建进程、分配必要的资源。

先来先服务调度算法（FCFS），系统按照作业到达后的先后次序来进行调度，后者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所执行的时间长短。在进程调度中，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行，该进程一直运行到完成或发生某事件而阻塞后，进程调度程序才将处理机分配给其他进程。

短作业优先算法(SJF)，以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。所以需要预知作业的运行时间，但却很难准确估计作业的运行时间，如果估计过低，系统可能按估计的时间终止作业的运行，但此时作业并未完成，故一般估计时间都会偏长。

高相应比优先调度算法(HRRN)，该算法即考虑了作业的等待时间，又考虑了作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长。每个作业都有一个动态优先级，优先级是可以改变的，令它随等待时间延长而而增加，这将使长作业在等待期间不断地增加，等到足够的时间后，必然会有机会获得处理机，该优先级的变化规律是

         （1-1）

批处理系统的目标，平均周转时间短，它包括4部分时间：作业从外存后备队列上等待调度的时间，进程在就绪队列上等待进程调度的时间，进程在CPU上执行的时间，以及进程等待I/O操作完成的时间。平均周转时间短，不仅会有效的提高系统资源的利用率，而且还可以使大多数用户感到满意。平均周转时间
                

                                                                             （1-2）                   

为了进一步反应调度的性能，更清晰的描述各进程在其周转时间中，等待和执行的具体分配情况，往往使用带权周转时间，即作业的周转时间T与系统的为它提供服务的时间Ts

之比，即W=T/Ts,平均带权周转时间可表示为:         

 （1-3）             

问题1：3种算法的平均周转时间有什么大小关系

问题2：3种算法的带权周转时间有什么大小关系

2. 问题分析

本题为3种算法的平均周转时间和带权周转时间的比较，可以列出几个进程进行具体的计算，然后再进行比较，在利用程序进行检验。在平均周转时间中分为4种：作业从外存后备队列上等待调度的时间，进程在就绪队列上等待进程调度的时间，进程在CPU上执行的时间，以及进程等待I/O操作完成的时间。在进行计算时只考虑进程在就绪队列上等待进程调度的时间和进程在CPU上执行的时间。在进行分析时，分两种极端情况，一种是每个进程到达时cpu还在执行之前的进程，一种是每个进程到达时cpu已经处理完之前的进程。

3. 模型假设

3.1忽略cpu执行进程时的切换时间。

3.2在计算平均周转时间和带权周转时间时只考虑进程在就绪队列上等待进程调度的时间和进程在CPU上执行的时间。

3.3每个进程的执行时间已经预知且精准。

3.4在分析每个进程到达时cpu还在执行之前的进程这种情况时，认为T1>T2>T3>T4，A<B<C<D。

4.符号说明

A：进程1的到达时间。T1：进程1的执行时间

B：进程2的到达时间。T2：进程2的执行时间

C：进程3的到达时间。T3：进程3的执行时间

D：进程4的到达时间。T4：进程4的执行时间

5.模型建立

模型一

先来先服务调度算法-每个进程到达时cpu还在执行之前的进程

进程

到达时间

执行时间

开始时间

结束时间

等待时间

1

A

T1

A

A+T1

0

2

B

T2

A+T1

A+T1+T2

T1-B

3

C

T3

A+T1+T2

A+T1+T2+T3

T1+T2-C

4

D

T4

A+T1+T2+T3

A+T1+T2+T3+T4

T1+T2+T3-D

表1-1

短作业优先算法-每个进程到达时cpu还在执行之前的进程

进程

到达时间

执行时间

开始时间

结束时间

等待时间

1

A

T1

A

A+T1

0

4

D

T4

A+T1

A+T1+T4

T1-D

3

C

T3

A+T1+T4

A+T1+T4+T3

T1+T4-B

2

B

T2

A+T1+T4+T3

A+T1+T2+T3+T4

T1+T4+T3-C

表1-2

高相应比优先调度算法-每个进程到达时cpu还在执行之前的进程

进程

到达时间

执行时间

开始时间

结束时间

等待时间

1

A

T1

A

A+T1

0

4

D

T4

A+T1

A+T1+T4

T1-D

2

B

T2

A+T1+T4

A+T1+T2+T4

T1+T4-B

3

C

T3

A+T1+T4+T2

A+T1+T4+T3+T2

T1+T4+T2-C

表1-3

高相应比优先调度算法：再执行完进程3时进程2的优先级为(T1-B)/T2+1,

进程3的优先级为(T1-C)/T3+1，进程4的优先级为(T1-D)/T4+1。3个进程优先级比较大小，因为B>C>D,所以T1-B<T1-C<T1-D。又因为T2>T3>T4,所以无法比较，这里假设进程4的优先级最大，即T1T3-T3D>T1T4-T4C.再执行完进程2时，进程3与进程4的等待时间又变了，所以需要重新计算，进程3的优先级为(T1+T4-C)/T3+1,进程2的优先级为(T1+T4-B)/T2+1,T1+T4-C<T1+T3-D且T2>T3.无法比较，这里假设进程2的优先级大，即T2(T1+T4)-T2C<T3(T1+T4)-T3B,与上面假设不冲突

模型二

每个进程到达时cpu已经处理完之前的进程

进程

到达时间

执行时间

开始时间

结束时间

等待时间

1

A

T1

A

A+T1

0

2

B

T2

B

B+T2

0

3

C

T3

C

C+T3

0

4

D

T4

D

D+T4

0

表2-1

6. 模型求解

模型一

先来先服务调度算法:时间总和为4T1+3T2+2T3+T4,即T=(4T1+3T2+2T3+T4-B-C-D)/4。

W=(1+（T1+T2-B）/T2+(T1+T2+T3-C)/T3+(T1+T2+T3+T4-D)/T4)/4。

短作业优先算法：因为T2>T3>T4,并且假设3个进程到达之前T1还没有执行完，所以按照短作业优先算法时，进程4先执行，再执行进程3，最后在执行进程4。时间总和为4T1+3T4+2T3+T2,即

T=(4T1+3T4+2T3+T2-B-C-D)/4。

W=(1+（T1+T4-D）/T4+(T1+T4+T3-C)/T3+(T1+T4+T3+T2-B)/T2)/4

高相应比优先调度算法：T=(4T1+3T4+2T2+T3-B-C-D)/4。

W=(1+（T1+T4-D）/T4+(T1+T4+T2-B)/T2+(T1+T4+T3+T2-C)/T3)/4。

3种进行比较T(FCFS)>T(HRRN)>T(SJF),W(FCFS)>W(HRRN)>W(SJF)

模型二

因为每个进程到达时cpu已经处理完之前的进程，并且A<B<C<D,所以3种算法的执行都是相同的且T=W=1.

综上所述T(FCFS)>=T(HRRN)>=T(SJF),W(FCFS)>=W(HRRN)>=W(SJF)

7. 模型检验

用c语言随机生成5000个进程进行计算结果符合

c语言执行结果

 

图1

 c代码

#include <stdio.h>
#include <stdlib.h>
typedef struct
{
    int arrived;
    int serve;
    int priority;
    long wait;
}Hrrn;
typedef struct
{
    int arrived;
    int serve;
    long wait;
}Fcfs;
typedef struct
{
    int arrived;
    int serve;
    long wait;
}Sjf;

void FCFS(Fcfs *fcfs,int n)     //先来先服务算法
{
    long now = 0;           //cpu从处理到现在所用的时间
    for (int i=0;i<n;i++)
    {

        if(now >= fcfs[i].arrived)      //如果有进程到达 直接加时间
            now+=fcfs[i].serve;
        else                        //如果没有进程到达      需要更新为到达时间
            now = fcfs[i].arrived+fcfs[i].serve;
        for(int j=i+1;j<n;j++)              //更新等待时间
        {
            if(now > fcfs[j].arrived)
            fcfs[j].wait=now-fcfs[j].arrived;
        }
    }
    long total=0;double totalserve=0;
    for (int i=0;i<n;i++)
    {
        total+=(fcfs[i].wait+fcfs[i].serve);      //总的周转时间
        totalserve+=(fcfs[i].wait+fcfs[i].serve)/(double)fcfs[i].serve;          //带权周转时间
    }
    printf("FCFS\nT=%f                   W=%f\n",total/(float)n,(totalserve/(double)n));
}
void SJF(Sjf *sjf,int n)            //短作业优先算法
{Sjf *temp = malloc(sizeof(Sjf));
    for(int p=n/2;p>0;p/=2)    //  希尔排序 按照作业长短排序 一样的按照先后
    {
        for (int i=p;i<n;i++)
        {

            *temp=sjf[i];
            int j;
            for (j=i;j-p>=0 && sjf[j-p].serve >= temp->serve;j-=p)
            {
                if (sjf[j-p].serve > temp->serve)  //第一排序为执行时间
                    sjf[j] = sjf[j-p];
                else
                {
                    if(sjf[j-p].arrived > temp->arrived)    //第二排序为到达时间
                        sjf[j] = sjf[j-p];
                    else
                        break;
                }
            }
            sjf[j] = *temp;
        }

    }

 free(temp);
    int flag[10000]={0};            //标志哪一个没有没有执行 因为排序中短作业可能后来到达
    int now=0,nowloc=0;                 //now记录cpu从处理到现在的时间  nowloc为将要执行的位置
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
        {
            if (now>=sjf[j].arrived && !flag[j])            //找最短的进程且没有执行过的
              {
                  nowloc = j;                                          //找到后记录
                  break;
              }
             if(now<sjf[j].arrived && j==n-1)           //如果没有进程 等1秒
             {
                 j=-1;
                 now+=1;
             }
        }
        now+=sjf[nowloc].serve;                  //执行的总时间
        flag[nowloc] = 1;
        for(int j=0;j<n;j++)                            //修改等待时间
        {
            if(now > sjf[j].arrived && !flag[j])
            sjf[j].wait=now-sjf[j].arrived;
        }
    }
    long total=0;double totalserve=0;              //计算T W
    for (int i=0;i<n;i++)
    {
        total+= (sjf[i].wait+sjf[i].serve);
        totalserve+=(sjf[i].wait+sjf[i].serve)/(double)sjf[i].serve;
    }
    printf("SJF\nT=%f                   W=%f\n",total/(float)n,(totalserve/(double)n));
}
void HRRN(Hrrn *hrrn,int n)
{

    long now = 0,loc=0;Hrrn *temp = malloc(sizeof(Hrrn));       //loc为后面还没有到达进程的位置
    for(int i=0;i<n;i++)
    {
        if(now>hrrn[i].arrived)
            now += hrrn[i].serve;
        else
            now = hrrn[i].arrived+hrrn[i].serve;
        for (int j = i+1;j<n;j++)       //每执行一个进程都要更新优先级 和等待时间
        {
            if (now>=hrrn[j].arrived)
            {
                hrrn[j].wait = now-hrrn[j].arrived;
                hrrn[j].priority = hrrn[j].wait/hrrn[j].serve;
            }
            else                //如果没有后面的进程都没到达 那么记录位置并结束
            {
                loc=j;
                break;
            }
        }
        for(int p=(loc-i)/2;p>0;p/=2)    //  希尔排序 按照优先级排序 一样的按照先后   优先级在变 所以需要每次都排序
        {
            for (int ii=p;ii<loc;ii++)
            {
                *temp=hrrn[ii];
                int j;
                for (j=ii;j-p>=i+1 && hrrn[j-p].priority <= temp->priority;j-=p)        //第一排序为优先级 第二为到达时间
                {
                    if (hrrn[j-p].priority < temp->priority)
                        hrrn[j] = hrrn[j-p];
                    else
                    {
                        if(hrrn[j-p].arrived > temp->arrived)
                            hrrn[j] = hrrn[j-p];
                        else
                            break;
                    }
                }
                hrrn[j] = *temp;
            }
        }

    }
    free(temp);
    long total=0;double totalserve=0;                 //计算T W
    for (int i=0;i<n;i++)
    {
        total+= (hrrn[i].wait+hrrn[i].serve);
        totalserve+=(hrrn[i].wait+hrrn[i].serve)/(double)hrrn[i].serve;
    }
    printf("HRRN\nT=%f                   W=%f\n",total/(float)n,(totalserve/(double)n));
}

int main()
{
    int n=5000;int a;
    Sjf *sjf = malloc(n*sizeof(Sjf));
    Hrrn *hrrn = malloc(n*sizeof(Hrrn));
    Fcfs *fcfs = malloc(n*sizeof(Fcfs));
    for(int i=0;i<n;i++)                    //按照到达时间先后进行存储 再进行fcfs时不需要再排序
    {
        a=rand() %100+1;                    //随机生成1~100的数 为每一个进程的服务时间
        sjf[i].arrived=i;
        sjf[i].wait = 0;
        sjf[i].serve = a;
        fcfs[i].arrived = i;
        fcfs[i].serve = a;
        fcfs[i].wait = 0;
        hrrn[i].serve = a;
        hrrn[i].wait = 0;
        hrrn[i].priority = 0;
        hrrn[i].arrived = i;
    }
    FCFS(fcfs,n);
    SJF(sjf,n);
    HRRN(hrrn,n);
    free(fcfs);free(hrrn);free(sjf);
/* for(int i=0;i<n;i++)
    {
        printf("%d %d %d %d\n",hrrn[i].arrived,hrrn[i].serve,hrrn[i].wait,hrrn[i].priority);
    }*/
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/699328.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

解锁工业数据流：NeuronEX 规则调试功能实操指南

解锁工业数据流：NeuronEX 规则调试功能实操指南

工业企业要实现数据驱动的新质生产力升级&#xff0c;一个重要的环节便是如何准确、可靠地收集并利用生产过程中的数据流。 NeuronEX 工业边缘软件中的规则调试功能&#xff0c;可帮助用户在安全的环境中模拟数据输入&#xff0c;测试和优化数据处理规则&#xff0c;从而提前发…
阅读更多...
低代码是什么，低代码平台可以解决哪些业务问题

低代码是什么，低代码平台可以解决哪些业务问题

低代码&#xff08;Low-Code&#xff09;是一种软件开发方法&#xff0c;它使得开发人员能够通过图形界面、拖放组件和模型驱动的逻辑&#xff0c;快速地构建和部署应用程序&#xff0c;而无需编写大量的代码。 近年来&#xff0c;低代码正在逐步帮助企业解决业务问题&#xff…
阅读更多...
STL——Stacks容器

STL——Stacks容器

一、stack 1.操作 语法: <><>!所有的这些操作可以被用于堆栈. 相等指堆栈有相同的元素并有着相同的顺序。 2.empty 语法: bool empty();如当前堆栈为空&#xff0c;empty() 函数 返回 true 否则返回false. 3.pop 语法: void pop();pop() 函数移除堆栈中最顶层元…
阅读更多...
React 懒加载源码实现

React 懒加载源码实现

懒加载 React 中懒加载是一种按需加载组件的机制&#xff0c;有些组件不需要在页面初始化就进行加载&#xff0c;这些组件可以按需加载&#xff0c;当需要时再进行加载。懒加载是怎么实现的呢&#xff1f;如果要实现一个懒加载功能应该怎么去做呢&#xff1f;可以通过异步动态…
阅读更多...
专业学习|博弈论-课程改革

专业学习|博弈论-课程改革

学习来源&#xff1a;北京大学刘霖《博弈论》MOOC公开课 备注&#xff1a;仅做学习分享&#xff0c;请勿转载&#xff0c;转载必究&#xff01; &#xff08;一&#xff09;博弈论的预备知识 基本的微积分的知识和概率论的知识。简单的说会求导数&#xff0c;会求简单的积分&am…
阅读更多...
BUUCTF---web---[SUCTF 2019]CheckIn

BUUCTF---web---[SUCTF 2019]CheckIn

1、点击题目连接来到页面 2、上传正常的jpg文件&#xff0c;提示内容不能有<?。本来打算上传图片马&#xff0c;但是有过滤 3、可以改成下面的图片马&#xff1a; <script languagephp>eval($_POST[cmd]);</script> 4、将上面的一句话木马先写成txt再修改后缀为…
阅读更多...
01_基于人脸的常见表情识别实战_深度学习基础知识

01_基于人脸的常见表情识别实战_深度学习基础知识

1. 感知机 感知机通常情况下指单层的人工神经网络，其结构与 MP 模型类似（按照生物神经元的结构和工作原理造出来的一个抽象和简化了模型，也称为神经网络的一个处理单元） 假设由一个 n 维的单层感知机，则： x 1 x_1 x1​ 至 x n x_n xn​ 为 n 维输入向量的各个分量w 1 j…
阅读更多...
【C语言】一篇带你高强度解析精通 字符串函数和内存函数 (万字总结大全，含思维导图)（建议收藏！！！）

【C语言】一篇带你高强度解析精通 字符串函数和内存函数 (万字总结大全，含思维导图)（建议收藏！！！）

【 库函数】——字符串函数和内存函数 目录 思维导图&#xff1a; 一&#xff1a;字符串函数 1.1&#xff1a;字符串常规函数 1.1.1&#xff1a;长度不受限制的字符串函数 1.1.1.1&#xff1a;strlen函数 1.1.1.2&#xff1a;strcpy函数 1.1.1.3&#xff1a;strcat函数 …
阅读更多...
芯片级激光器研发取得新进展

芯片级激光器研发取得新进展

欢迎关注GZH《光场视觉》 自 20 世纪 60 年代以来&#xff0c;激光给世界带来了革命性的变化&#xff0c;如今已成为从尖端手术和精密制造到光纤数据传输等现代应用中不可或缺的工具。 但是&#xff0c;随着激光应用需求的增长&#xff0c;挑战也随之而来。例如&#xff0c;光…
阅读更多...
勒索病毒搜索引擎

勒索病毒搜索引擎

360勒索病毒搜索引擎 https://lesuobingdu.360.cn/ 腾讯勒索病毒搜索引擎 https://guanjia.qq.com/pr/ls/ VenusEye勒索病毒搜索引擎 https://lesuo.venuseye.com.cn/ 奇安信勒索病毒搜索引擎 https://lesuobingdu.qianxin.com/index/getFile 深信服勒索病毒搜索引擎…
阅读更多...
idea插件开发之hello idea plugin

idea插件开发之hello idea plugin

写在前面 最近一直想研究下自定义idea插件的内容&#xff0c;这样如果是想要什么插件&#xff0c;但又一时找不到合适的&#xff0c;就可以自己来搞啦&#xff01;这不终于有时间来研究下&#xff0c;但过程可谓是一波三折&#xff0c;再一次切身体验了下万事开头难。那么&…
阅读更多...
如何用Vue3打造一个逼真的3D手机模型

如何用Vue3打造一个逼真的3D手机模型

本文由ScriptEcho平台提供技术支持 项目地址&#xff1a;传送门 手机界面卡片功能实现 应用场景介绍 本代码片段适用于构建移动设备或网页端界面的手机卡片功能。它可以通过简单的HTML、CSS和JavaScript实现一个具有逼真视觉效果和交互功能的手机卡片。 基本功能介绍 该代…
阅读更多...
Project 项目管理软件真的好用吗？

Project 项目管理软件真的好用吗？

作为一个普通的职场人&#xff0c;或许只要掌握office全家桶&#xff0c;即可应对大部分工作。 但对项目经理来说&#xff0c;这是远远不够的。项目经理需要实时掌握项目进度、把关项目质量、应对项目风险、实时分析项目数据&#xff0c;做出正确的决策等等… 而拥有一款高效…
阅读更多...
浅谈DALL-E2

浅谈DALL-E2

目录 1.概述 2.诞生背景 3.作用 4.版本历史 5.模型和技术 6.应用场景 6.1.十个应用场景 6.2.游戏开发 7.接口 8.未来展望 9.总结 1.概述 DALL-E2 是由 OpenAI 开发的一个图像生成模型&#xff0c;可以根据文本描述生成高质量的图像。DALL-E2 是 DALL-E 的升级版&am…
阅读更多...
IBM，开始构建以量子为中心的超级计算机

IBM，开始构建以量子为中心的超级计算机

6月6日&#xff0c;IBM与Pasqal宣布了一项重大合作!IBM和Pasqal打算合作开发一种以量子为中心的超级计算的通用方法并促进化学和材料科学的应用研究。IBM和Pasqal将与高性能计算领域的领先机构合作&#xff0c;为以量子为中心的超级计算奠定基础——将量子计算与先进的经典计算…
阅读更多...
用于每个平台的最佳WordPress LMS主题

用于每个平台的最佳WordPress LMS主题

你已选择在 WordPress 上构建学习管理系统 (LMS)了。恭喜&#xff01; 你甚至可能已经选择了要使用的 LMS 插件&#xff0c;这已经是成功的一半了。 现在是时候弄清楚哪个 WordPress LMS 主题要与你的插件配对。 我将解释 LMS 主题和插件之间的区别&#xff0c;以便你了解要…
阅读更多...
使用lombok帮我们生成 getter、setter、无参构造器、全参构造器、equals、hashcode

使用lombok帮我们生成 getter、setter、无参构造器、全参构造器、equals、hashcode

文章目录 为什么要使用lombok&#xff1f;lombok的使用步骤1.检查 idea 是否安装 lombok 插件2.检查是否勾选了 enable annotation processing3.导入 lombok.jar 并加入到模块中4.在实体类添加注解 测试 为什么要使用lombok&#xff1f; lombok可以帮我们生成 getter、setter、…
阅读更多...
MySQL-数据处理函数（-1）

MySQL-数据处理函数（-1）

033-数据处理函数之获取日期时间 now()&#xff1a;获取的是执行select语句的时刻。sysdate()&#xff1a;获取的是执行sysdate()函数的时刻。 select now(), sleep(2), sysdate();获取当前日期 select curdate(); select current_date(); select current_date;获取当前时间…
阅读更多...
超详解——Python 编程中的类型和对象深入探讨——基础篇

超详解——Python 编程中的类型和对象深入探讨——基础篇

目录 1. 内建类型的布尔值 1.1 布尔值的基本规则 1.2 进阶应用 2. 对象身份的比较 2.1 基本概念 2.2 示例代码 2.3 实际应用 3. 对象类型比较 3.1 基本概念 3.2 示例代码 3.3 实际应用 4. 类型工厂函数 4.1 常见的类型工厂函数 4.2 示例代码 4.3 实际应用 5. P…
阅读更多...
Docker 安装gitLab

Docker 安装gitLab

目录 1. 安装 Docker 2. 拉取 GitLab 镜像 3. 创建并运行 GitLab 容器 4. 登录GitLab 修改下载地址 修改账号密码 前言-与正文无关 生活远不止眼前的苦劳与奔波&#xff0c;它还充满了无数值得我们去体验和珍惜的美好事物。在这个快节奏的世界中&#xff0c;我们往往容易…
阅读更多...
最新文章

Copyright @ 2022~2023