进程调度——操作系统课程设计报告

  课程设计指导教师评定成绩表

   姓名:黄进 学号:20085670

  指导教师评定成绩:

  指导教师签名:杨瑞龙                         20##年 1月7日

  课程设计指导教师评定成绩表

   姓名:王博君 学号:20085680

  指导教师评定成绩:

  指导教师签名:杨瑞龙                         20##年 1月7日

重庆大学本科学生课程设计任务书

正文目录

摘要及关键词......................................... 5

1 设计目的及内容..................................... 6

 2 设计方案........................................... 6

 3 程序功能模块设计................................... 6

 4 程序总控流程图..................................... 8

 5 数据结构设计....................................... 8

6  程序主要代码及解析.. .. .. .. .. .. .. .. .. .. .... .10

 7 测试数据及测试结果................................. 14

    7.1 主程序界面................................... 14

    7.2 进程生成后界面................................ 15

    7.3 开始模拟进程.................................. 15

8设计过程中遇到的问题及解决方法...................... 17

 9设计总结........................................... 17

 10 参考文献... ......................................... 18

摘要

现代计算机系统中,进程是资源分配和独立运行的基本单位,是操作系统的核心概念。因而,进程就成为理解操作系统如何实现系统管理的最基本,也是最重要的概念。

进程调度是进程管理过程的主要组成部分,是必然要发生的事件。在现代操作系统中,进程的并发机制在绝大多数时候,会产生不断变化的进程就绪队列和阻塞队列。处于执行态的进程无论是正常或非正常终止、或转换为阻塞状态,都会引发从就绪队列中,由进程调度选择一个进程进占CPU。进程调度的核心是进程调度算法.

在本课程设计中,用良好清晰的界面向用户展示了进程调度中的先来先服务算法,优先级(抢占式与非抢占式),时间片轮转法和多级反馈轮转法。在最终实现的成果中,用户可指定需要模拟的进程数,CPU时间片和进程的最大执行时间,并且选择需要演示的算法,界面将会动态的显示进程调度过程及各个队列的变化。同时,为了更加清晰直观的演示各个算法及各关键变量的变化,我们时时更新时间片,算法名称,当前进程信息,全局计时器以及进度条等。通过此进程调度模拟系统,用户可以对上述的四种算法有进一步以及直观的了解。

关键词:进程调度  先来先服务  优先级法 时间片轮转 多级反馈轮转

                    

一.  设计目的及内容

1.1 设计目的

课程设计是学习完“操作系统原理”课程后进行的一次全面的综合训练,通过课程设计,更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解,掌握进程调度的原理和方法,加强学生的动手能力。

1.2 设计内容

通过编程实现操作系统进程调度子系统的基本功能,其中,必须实现的调度算法有:先来先服务、时间片轮转、多级反馈轮转法、优先级等,在程序设计过程中,要求要有良好清晰的界面来观测进程调度的执行过程,在每个调度算法展示时,可以看到所有有关的队列结构和其中的内容,如就绪队列、阻塞队列等结构的动态变化的过程。

二.  设计方案

本次课程设计主要开发平台基于windows,我们使用C++并选择VS2010作为开发工具实现进程调度模拟的可视化,以本学期的四次实验作为可视化编程基础,深入学习VS2010的各种控件,使界面更加完善,实现先来先服务、时间片轮转、多级反馈轮转法、优先级(抢占式与非抢占式)这5个算法的可视化模拟调度,并在应用程序的结果分析中统计出5个算法的模拟时间,以比较各个算法的执行效率。

三.程序功能模块设计

图形界面:采用visual studio 2010软件,实现的界面如下:

     

                            图1 开始界面

应用程序共有四个主菜单:参数设置,调度算法,结果分析,使用说明。

·参数设置:点击弹出供用户设置模拟参数的新窗口

图2 参数设置界面

·调度算法

   先来先服务:在就绪进程的队列中,从第一个开始执行下去,且进程开始执行后会一直执行完毕。

   时间片轮转法:当正在执行的进程一个时间片用完后,按照先来先服务的原则在就绪进程队列中选取进程执行,正在执行的进程进入队尾。

   多级反馈轮转:设置多个轮转队列,当一个进程在该队列时间片用完后,跳到下一个队列,继续执行。每个队列的时间片可以不同。

   优先级算法:

   非抢占式:在就绪进程队列中选取优先级最高的执行,相同优先级按照先来先服务原则进行选取,进程开始后不可被抢占。

抢占式:在就绪进程队列中选取优先级最高的执行,相同优先级按照先来先服务原则进行选取,进程开始后可被抢占。

·结果分析

   根据每个算法的运行情况,统计结果,进行比较分析,便于分析调度算法的效率。

四.程序总控流程图

 

五.数据结构设计

5.1进程信息的数据结构

   class  process

{

protected:

    int name;          // 进程名,标识进程的ID

    int spendtime;     //进程已经执行的时间

    int costtime;      //进程占用时间片的时间

    int needtime;       //进程需要的总时间

    int starttime;       //进程进入的时间

    int priority;        //进程的优先级

};

5.2 各个队列的数据结构

 class myqueue

{

protected:

    queue<process> qp;        //放进程的容器

    int dotime;               //时间片大小

    int flag;                 //队列执行标识

public:

    int getdotime();            // 取出时间片大小

    void setdotime(int dotimeq);//设置时间片大小

    void pop();                  //弹出队列中的进程

    process& gethead();           //得到队首进程

    void push(process mpp);

    void pass(myqueue &mqq);       //队列之间的传递函数

    int getflag();

    void setflag(int fflag);

    int isempty();                 //判断当前队列是否为空

    int getsize();              //得到当前队列的大小,即:包含的进程数

};

5.3主程序数据结构

    主要操作类:

class dojob

{

public:

dojob(int dotime, int max, int big,int maxshow);  //构造函数

void createprocess(int max,int big,int maxshow);     //创建进程进程

    void fun1();                                   //先来先服务算法函数

void fun2();                                   //时间片轮转算法函数

    void fun3()                                  //多级反馈轮转算法函数

void fun4(int nowtime);                       //非抢占式优先级函数

    void fun5(int nowtime);                       ////抢占式优先级函数

    void doprocess3(myqueue &qqnow,myqueue &qqnext,myqueue &qqfinish);

                                              //多级反馈轮转的处理函数

    void doprocess2(myqueue &qqfinish)          //时间片轮转的处理函数

    void FIFO(myqueue &qnow);                   //先来先服务的处理函数                                   

    void priority_do_another(int nowtime);   //非抢占式优先级的处理函数

    void priority_do(int nowtime);           //抢占式优先级的处理函数

};

六.程序主要代码及解析

6.1各种调度算法的实现函数

   (因篇幅有限,更多代码请参见程序源代码,此处不一一列举)

void dojob::FIFO(myqueue & qnow)                         //先来先服务函数

{

    if (qnow.gethead().getneedtime() == 0)

     //如果进程所需时间等于该进程所需总时间,则转入完成队列

    {

       qnow.pass(finishq);

    }

    else

    { qnow.gethead().setneedtime(qnow.gethead().getneedtime()-1); 

qnow.gethead().setspendtime(qnow.gethead().getspendtime()+1);

    }

}

void dojob::doprocess2(myqueue &qqfinish)               //时间片轮转函数

{

    if (!q1.isempty())

    {

       if(q1.gethead().getneedtime() == 0) //判断进程的剩余需要时间为0,

       {

           q1.pass(qqfinish);

           return;

       }

       else

       {

           if (q1.gethead().getcosttime()>= q1.getdotime())

           {        //若进程在队列中的执行时间超过时间片,则进入等待队列

              q1.gethead().setcosttime(0);   

              q1.push(q1.gethead());

              q1.pop();

              return;

           }

           else

           {                                                //进程执行

              q1.gethead().setneedtime(q1.gethead().getneedtime()-1);

              q1.gethead().setspendtime(q1.gethead().getspendtime()+1);

               q1.gethead().setcosttime(q1.gethead().getcosttime()+1);

           }

       }

    }

       return;

}

void dojob::priority_do(int nowtime)                //抢占式优先级函数

{

    int temp=-1;

    if(!IsVEmpty(vp))

    {

       for (int i=0;i<vp.size();i++)            

   //使temp的初值为v容器中第一个还未执行的进程

       {

           if(vp[i].finishornot==false)

           {

              temp=i;

              break;

           }

       }

    }

    if(temp!=-1)                         

       //如果temp不为-1,说明还有未执行完的进程,则选出优先级最高的执行

    { 

       for (int i=0;i<vp.size();i++)                 

//通过此循环找到优先级最高且满足到达时间的进程

       {          if (vp[i].finishornot==false&&vp[i].getpriority()>vp[temp].getpriority()&&vp[i].getstarttime()<=nowtime)

           {

              temp=i;

           }

       }

       if (vp[temp].getneedtime()==0)

       {

           vp[temp].finishornot=true;             //标明该进程已经执行完

           finishq.push(vp[temp]);               //将完成进程放至finishq

       }

       else

       {

           vp[temp].setspendtime(vp[temp].getspendtime()+1);

           vp[temp].setneedtime(vp[temp].getneedtime()-1);

           pNOW=temp;

       }

    }

}

6.2程序可视化实现中的主窗体函数

public ref class Form1 : public System::Windows::Forms::Form  //Form1

{

    public:

       form2 data_form;

       formresult result_form;

       forminfor  information_form

       int flag;

       Form1(void)             //Form1的构造函数

       {

           InitializeComponent();

           nowtime=0;

           timer1->Interval = 1000;

       }

     Protected:              //Form1的析构数

       ~Form1()

       {

           if (components)

           {

              delete components;

           }

       }                                         //添加的主要组件声明

    private: System::Windows::Forms::Button^  start;

    protected:

    private: System::Windows::Forms::Button^  stop;

    private: System::Windows::Forms::Button^  go_on;

    private: System::Windows::Forms::Button^  exit;

    private: System::Windows::Forms::MenuStrip^  menuStrip1;

  private: System::Windows::Forms::ToolStripMenuItem^  参数设置ToolStripMenuItem;

 private: System::Windows::Forms::ToolStripMenuItem^  调度算法ToolStripMenuItem;

  private: System::Windows::Forms::ToolStripMenuItem^  先来先服务ToolStripMenuItem;

  private: System::Windows::Forms::ToolStripMenuItem^  时间片ToolStripMenuItem;

  private: System::Windows::Forms::ToolStripMenuItem^  多级反馈轮转ToolStripMenuItem;

private: System::Windows::Forms::ToolStripMenuItem^  优先级ToolStripMenuItem;

    private: System::Windows::Forms::StatusStrip^  statusStrip1;

    private:System::Windows::Forms::ToolStripStatusLabel^  toolStripStatusLabel1;

    private:System::Windows::Forms::ToolStripStatusLabel^  toolStripStatusLabel2;

    private:System::Windows::Forms::ToolStripStatusLabel^  toolStripStatusLabel3;

    private:System::Windows::Forms::ToolStripProgressBar^  toolStripProgressBar1;

    private:System::Windows::Forms::ToolStripStatusLabel^  toolStripStatusLabel4;

    private: System::Windows::Forms::ToolStripMenuItem^  使用说明ToolStripMenuItem1;

    private: System::Windows::Forms::TextBox^  queue_1;

    private: System::Windows::Forms::TextBox^  queue_2;

    private: System::Windows::Forms::TextBox^  queue_3;

    private: System::Windows::Forms::Label^  label7;

    private: System::Windows::Forms::Label^  label8;

    private: System::Windows::Forms::Timer^  timer1;

七.测试数据及测试结果

7.1 主程序界面

捕获3(介绍主界面).PNG

捕获12.PNG捕获11.PNG 

图3 主界面图

弹出参数设置后的主界面,包括参数设置,调度算法,使用说明,结果分析四个主菜单。

7.2 进程生成后界面

 捕获4.PNG

图4 进程生成后界面(以时间片轮转为例)

   (图中红色标记处为整个程序中时时变化的部分,在此标识使说明更直观)

   可读出的信息如下表:

7.3 开始模拟进程

    由于时间片轮转上面已作为例子进行说明,概不赘述,只贴出其余算法的模拟进程,如下所示。

捕获5(fifo).PNG

图5 先来先服务的模拟截图

捕获6(多级).PNG

图6 多级反馈轮转的模拟截图

捕获8抢占.PNG

图7 优先级(以抢占式为例)的模拟截图

捕获0.PNG

图8 结果分析:各种算法总周转时间比较

八.设计中遇到的问题及解决方法

8.1算法切换时的参数初始化问题

     因为该程序要实现进程调度中几种主要算法的调度演示,并且进行比较。那么就需要在一组进程上,调用不同的算法,并比较结果。但是,当从一个算法转换到另一个算法时,涉及到一些关键变量的初始化问题,由于此次课程设计,是我们两个同学一起完成,在实现不同的代码时,用到一些各自的关键变量,这为程序的统一初始化带来了很大问题。在重新带代码检查多次后,找出这些关键变量,异种求同,并各自根据需要重新设置这些变量,调整算法的实现方法,最终,做到了几种算法的切换而不需要重启程序,也使得最后的结果分析有了其实际的分析价值。

8.2优先级调度算法是用和其他算法不同的数据结构带来的问题

  由于优先级调度需选出优先级最高的进程来执行,而其余算法采用的队列的数据结构,无法遍历各个进程,就无法选出优先级最高的进程。这使得优先级算法要是用和其他三种算法不同的数据结构vector。但这位程序的可视化,统一显示带来的问题。因为传参时,数据类型有了变化。为了解决这一问题,新创建一个数据结构vector<process> vp,用进程容器vp记录下就绪队列,遍历各进程,选出优先级最高的首先运行。同时将vp中的标识变量和队列一一对应,将vector类型中所包含的特俗信息用标识变量传入队列。

九.设计总结

◆所用方法及知识

 此次课程设计我们选择任务三——实现操作系统进程调度的模拟,并且实现动态可视化。在本学期,我们从第一个实验开始,就涉及到了可视化编程,平时的实验为我们这次课程设计打下了坚实的基础。我们采用我们较为熟悉的visual studio 2010进行用C++进行编程。

在这次课程设计的过程中,我们用到了很多以前学过的知识,比如说数据结构中的队列知识,C++里学到的编程方法及理念,主要包括创建新类,类的保护,容器vector等。

◆我们的创新

这次,我们所完成的应用程序能很好的完成所规定的先来先服务、时间片轮转、多级反馈轮转、优先级(抢占式与非抢占式)算法,并且我们的创新之处在于:

·实现了初始化,并且可以保存下第一次随机产生的代码序列,每个算法用同一个进程序列模拟,使模拟结果更加可比性。

·具有结果统计功能,每次模拟完,都将结果写入,点击结果统计菜单,就可查看模拟结果信息。

◆获得的进步

 同时,我们也感受到了好的编程习惯在程序开发中的重要性。合作完成的东西必须具有很好的相容性,采用的数据结构和类等必须相同,所以我们在动手编程前,花了很多时间交流,初步完全构建好界面,商量好要实现的功能,确定完所需数据结构才着手正式编程。这样的步骤,是我们省下了很多将两人代码想结合时出现的错误修改时间,锻炼了我们的小组配合能力,我们的收获很大。

十.参考文献

[1]计算机操作系统教程 张尧学,史美林编著  清华大学出版社2006第3版

[2]Windows操作系统原理(重点大学计算机教材)尤晋元、史美林、陈向群等人编著 清华大学出版社 20##年8月第1版

[3]计算机操作系统实验指导,郁红英,李春强,清华大学出版社,20##年9 月第一版                    

相关推荐