计算机科学技术学院

操作系统原理

课程设计报告

题    目：进程管理系统

专    业：

班    级：

姓    名：

学    号：

指导老师：

年   月   日

《操作系统原理》课程设计任务书

一、课程设计题目（任选一个题目）

1.模拟进程管理

2.模拟处理机调度

3.模拟存储器管理

4.模拟文件系统

5.模拟磁盘调度

二、设计目的和要求

1.设计目的

《操作系统原理》课程设计是网络工程专业实践性环节之一，是学习完《操作系统原理》课程后进行的一次较全面的综合练习。其目的在于加深对操作系统的理论、方法和基础知识的理解，掌握操作系统结构、实现机理和各种典型算法，系统地了解操作系统的设计和实现思路，培养学生的系统设计能力，并了解操作系统的发展动向和趋势。

2.基本要求：

(1)选择课程设计题目中的一个课题，独立完成。

(2)良好的沟通和合作能力

(3)充分运用前序课所学的软件工程、程序设计、数据结构等相关知识

(4)充分运用调试和排错技术

(5)简单测试驱动模块和桩模块的编写

(6)查阅相关资料，自学具体课题中涉及到的新知识。

(7)课题完成后必须按要求提交课程设计报告，格式规范，内容详实。

三、设计内容及步骤

1.根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么。

2.根据实现的功能，划分出合理的模块，明确模块间的关系。

3.编程实现所设计的模块。

4.程序调试与测试。采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；

5.结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。

6.编写课程设计报告；

设计报告要求：A4纸，详细设计部分主要叙述本人的工作内容

设计报告的格式：

(1)封面（题目、指导教师、专业、班级、姓名、学号）

(2)设计任务书
(3)目录

(4)需求分析

(5)概要设计

(6)详细设计（含主要代码）

(7)调试分析、测试结果

(8)用户使用说明

(9)附录或参考资料

四、进度安排

设计在学期的第15、16周进行，时间安排如下：

五、成绩评定办法

成绩分为优（A）、良（B）、中（C）、及格（D）、不及格（E）五个等级。其中设计表现占30%，验收40%，设计报告占30%。

1.设计表现：教师可依据学生使用实验环境的能力、观察和分析实验现象的能力、实验结果和数据的正确性以及学生的课堂纪律、实验态度、保持实验室卫生等方面的表现进行综合考核。

2.验收：要求学生演示设计的程序，讲解设计思路、方法、解决的主要问题，教师根据具体情况向每个学生提问2至3个问题。

3.设计报告：学生设计后应按时完成设计报告。要求：内容充实、写作规范、项目填写正确完整、书面整洁等。

目录

一、   需求分析………………………………………………6

1.进一步理解进程的基本概念 …………………………6

2.加强进程管理的设计及算法 …………………………6                   

3.观察和管理进程 ………………………………………6

二、   概要设计………………………………………………6

1．实验原理………………………………………………6

2．数据结构………………………………………………6

3. 算法描述………………………………………………6

4. 算法流程图……………………………………………7

三、   详细设计………………………………………………8

1．源程序代码……………………………………………8

四、  调试分析及测试结果 ………………………………15

五、  用户及用说明 ………………………………………17

六、  附录或参考资料 ……………………………………17

一、需求分析

1.进一步理解进程的基本概念。

2.加强进程管理中主要数据结构的设计及进程调度算法。                    

3.观察和管理进程——系统在运行过程中可显示或打印各进程的状态及有关参数的变化情况。

二、概要设计

1．实验原理

定义PCB的数据结构，用链表的形式管理进程，采用多级反馈队列调度的算法模拟进程的控制，最终完成有创建、撤销、调度、阻塞、唤醒进程等功能。

2．数据结构

类：

class queuenode

class queue

函数：

void enqueue( char &item);

char dequeue();

void del(char item);

void display();

int find(char item);

int isempty()

3.算法描述

1-1、创建进程，根据进程的顺序依次放入就绪队列。

2-1、执行进程——管理系统将就绪队列中的第一个进程调入运行队列；

2-2、将阻塞队列中进程调入就绪队列；

2-3、封锁进程——管理系统将就绪队列中的第一个进程调入阻塞队列；

2-4、结束进程——管理系统撤销所选进程；

2-5、结束程序。

4. 算法流程图

三、详细设计

1．源程序代码

#include<iostream.h>

class queuenode

{

    friend class queue;

private:

    char data;

    queuenode * link;

    queuenode (char d=0,queuenode * l=NULL): data(d),link(l){}

};

class queue

{

public:

    queue():rear(NULL),front(NULL){};

    ~queue();

    void enqueue( char &item);

    char dequeue();

    void del(char item);

    void display();

    int find(char item);

    int isempty(){return front==NULL;}

private:

    queuenode *front,*rear;

};

queue::~queue()

{

    queuenode * p;

    while(front!=NULL)

    {

       p=front;front=front->link;delete p;

    }

}

void queue::enqueue(char &item)

{

    if(front==NULL)front=rear=new queuenode(item,NULL);

    else rear=rear->link=new queuenode(item,NULL);

}

char queue::dequeue()

{

    queuenode *p=front;

    char f=p->data;front=front->link;

    delete p;

    return f;

}

void queue::display()

{

    queuenode *p;

    p=front;

    while(p!=NULL)

    {   cout<<p->data<<"->";

         p=p->link;

    }

    cout<<"NULL";

}

queue::find(char item)

{   queuenode *w;

    w=front;

    M:while(w!=NULL)

    {

     if(item==w->data)

     {  return 1;break;

     }

    else

    {   w=w->link;

       goto M;

    }

    }

    if(w==NULL) return 0;

}

void queue::del( char item)

{   queuenode *q,*b;

     q=front;

     while(q->data!=item)

        {b=q;

       q=q->link;

        }

     if(q==front)  {front=front->link; delete q;}

     else if(q==rear) {rear=b;rear->link=NULL;delete q;}

        else {b->link=q->link;  delete q;}

}

void main()

{

    int n;

    char a;

   cout<<"\n[-----------操作系统之进程管理模拟系统（先来先服务算法）------------]\n"<<endl;

    queue execute,ready,clog;    //执行，就绪，阻塞

    cout<<"\n[-------请用户输入进程名及其到达cpu的顺序（结束进程数请输入x）------]\n"<<endl;

    char r;

    r='x';

    for(int i=0;;i++)

    {  

       char e[100];

       cout<<"输入进程名:"<<" ";

       cin>>e[i];

       if(e[i]!=r)

           ready.enqueue(e[i]);

       else

           break;

    }

A: cout<<"\n  [------------请（学号）用户（姓名）选择操作------------]\n";

   cout<<"\n [1、执行进程……2、将阻塞队列中进程调入就绪队列………]\n";

   cout<<"\n [3、封锁进程…………………4、结束进程 …………………]\n";

   cout<<"\n [5、退出程序………………………………………………… ]\n选项： ";

   cin>>n;

   if(n==1)

   {

       if(!execute.isempty ())

       {

          cout<<"已经有进程在执行！,此操作不能执行\n";

          char w;

          cout<<endl;

          cout<<"如果要继续请输入#；如果要退出按其它任意键"<<endl;

          cout<<"要选择的操作:";

          cin>>w;

          if(w=='#')goto L;

          else goto E;

       }

       else

       {

          if(!ready.isempty())

          {

              a=ready.dequeue();

              if(a!=r)

                 execute.enqueue(a);

              goto L;

          }

          else goto L;

       }

   }

   else if(n==2)

   {

       if(!clog.isempty())

       {

          a=clog.dequeue ();

           if(a!=r)

              ready.enqueue(a);

          goto L;

       }

       else goto L;

   }

   else if(n==3)

   {

       if(!execute.isempty())

       {

          a=execute.dequeue ();

          if(a!=r)

              clog.enqueue(a);

              goto L;

       }

   else goto L;

   }

   else if(n==4)

   {

       cout<<"\n请输入要结束的进程名： ";

       cin>>a;

       if(execute.find (a)||ready.find (a)||clog.find (a))

       {

          if(execute.find(a))

          {execute.del(a);}

          else if(ready.find(a))

          {ready.del(a);}

          if(clog.find(a))

          {clog.del(a);}

          cout<<"\n结束进程成功！\n"<<endl;

          goto L;

       }

       else

          cout<<"没有此进程"<<endl;

       goto L;

  L:

       if(n==1||n==2||n==3||n==4)

       {

          cout<<"执行队列"<<endl;

          execute.display();

          cout<<endl;

          cout<<"就绪队列"<<endl;

          ready.display();cout<<endl;

           cout<<"阻塞队列"<<endl;

          clog.display();cout<<endl;

          goto A;

       }

       else

          if(n==5);

          else

          {

              cout<<"\n你的输入错误！\n";

              goto A;

          }

   }

   E:;} 

四、调试分析及测试结果

五、用户使用说明

用户通过VC++ 即可运行改程序。需说明的是主函数是实现进程管理的入口，在入口处需输入进程名称，然后输入进程的状态选项，如果完毕后，则通过相应的调度算法进行进程机的调度，同时也将结果显示在屏幕上。   

     本次实验通过模拟多个进程的同步运行，实现了进程就绪，运行，阻塞三个状态的转换，并可以根据用户要求改变进程的状态。

六、附录及参考资料

[1]王红 ，《操作系统实训》，中国水利水电出版社，2005

[2]张红光，《UNIX操作系统试验教程》，机械工程出版社，2006

[3]史美林，《操作系统教程》，清华大学，2006

[4]殷兆麟，《计算机操作系统》，北京大学，2007

[5]严蔚敏，《数据结构（C语言版）》，清华大学，2007

 

第二篇：操作系统课程设计报告操作系统课程设计报告操作系统课程设计报告

一、课程设计题目：进程/作业调度

二、实现要求：

1. 建立作业的数据结构描述

2. 使用两种方式产生作业/进程: (a)自动产生 (b)手工输入

3. 在屏幕上显示每个作业/进程的执行情况。

4. 时间的流逝可用下面几种方法模拟：(a)按键盘，每按一次可以认为过一个时间单位 (b)响应WM_TIMER (本实验采用b方法)

5. 计算并显示一批作业/进程的周转时间，平均周转时间，带权周转时间，平均带权周转时间。

6. 将一批作业/进程的执行情况存入磁盘文件，以后可以读出并重放。

7. 支持的调度算法：先来先服务，短作业/进程优先，时间片轮转调度算法，优先权调度算法，高响应比优先调度算法，多级反馈队列调度算法。

三、实验设备及环境：

IBM PC及其兼容机一台、WindwosXP操作系统、Microsoft Visual C++6.0集成开发环境。

四 实验目的：

通过本次课程设计进一步加深对进程控制块、进程调度的理解，能够实现各种不同的进程调度算法。深入理解操作系统设计中有关进程方面的应该注意的相关事项。

五 实验总体设计思路：

1、程序结构框架

<1> 程序中自定义了一个进程控制块PCB结构体，所有对进程的调度、进程切换等操作全都建立在PCB的基础之上。PCB中保存了进程标识符、进程到达时间、等待时间、进程调度状态、需要运行的时间等重要信息。PCB的定义如下： struct PCB{ //PCB结构

int pid; //ID号

int status; //进程状态

int priority; //进程优先级数值越小，优先级越高.

int start_time; //进程开始时间

int need_time; //进程执行所需时间

int wait_time; //进程已等待时间

int end_time; //运行结束时间

struct PCB *next; //PCB指针，指向下一PCB

};

<2> 程序中还定义了一个正在PCB类型的指针指向正在运行的进程的进程控制块，3个就绪队列。除了多级反馈队列调度算法需要用到3个就绪队列外其他5种调度算法均只需要一个就绪队列。

<3> 本程序实现中采取产生PCB代替真实进程的方法来模拟进程。

<4> 本程序采用MFC框架构建，菜单栏主要包括了进程选项与调度算法。以task

单文档视图为主题结构，mainframe实现菜单栏功能。

2、程序初始化阶段

<1> 程序开始运行后首先要产生若干个进程，可以采取自动产生也可以采取手工输入进程控制块参数的方法产生进程。

当用户每点击“自动产生”菜单一次，函数void CMainFrame::OnAuto()便自动产生一个进程并将其挂到就绪队列末尾，当用户点击“手工输入”菜单，便由函数void CMainFrame::OnManual()弹出输入对话框引导用户输入进程参数，之后把新产生的进程控制块挂到就绪队列末尾。以上两个函数均对进程编号pid做检查，以保证每个进程的唯一性，不允许有相同的进程。

<2> 在“调度算法”菜单中，用户选择了调度算法后，由相应的消息响应函数对调度算法标志dispatch进行赋值，然后根据dispatch值调用相关函数执行作业(进程)调度运算。

////////////////////调度算法的响应函数///////////////////

void CMainFrame::OnFcfs(){dispatch=1;}

void CMainFrame::OnSpf(){dispatch=2;}

void CMainFrame::OnTimeroll(){dispatch=3;}

void CMainFrame::OnPriority(){dispatch=4;}

void CMainFrame::OnHrespond(){dispatch=5;}

void CMainFrame::OnMultifeedback(){dispatch=6;}

/////////////////////////////////////////////////////////

void CMainFrame::dispatch_entry() //算法入口

{

switch(dispatch)

{

case 1:fcfs();break;

case 2:spf();break;

case 3:timeRoll();break;

case 4:priority();break;

case 5:hirespond();break;

case 6:multiFeedback();

}

}

如果未选择进程调度算法，系统默认使用先来先服务的调度算法(dispatch赋值为1)。

3、运行阶段

<1> 用户点击“运行”菜单后消息响应函数void CMainFrame::OnRun()设置计时器开始计时，置程序状态为运行状态，开始对各进程进行模拟调度、运行。在模拟进程调度运行的过程中由消息响应函数void CMainFrame::OnTimer(UINT nIDEvent)每秒被调用一次，在该函数中对各进程的状态进行刷新（包括进程调度）并输出到屏幕供用户观察进程的调度运行情况。

<2> 程序中还有一个free队列，该队列中保存所有运行完的进程的进程控制块，因为这些进程控制块信息要用来计算进程的周转时间，平均周转时间，带权周转时间，平均带权周转时间。

<3> 进程运行完后点击“打印运行结果”菜单，由void CMainFrame::OnPrintresult()函数计算并打印进程的周转时间，平均周转时间，带权周转时间，平均带权周转时间。

<4> 重放功能的实现较简单，在调度开始前每产生一个进程便调用void CMainFrame::store_PCB(const PCB* p)函数把该进程的PCB保存到文件pcb.txt中。当运行完后只需把文件pcb.txt中保存的PCB按系统时间先后顺序依次读出并挂到就绪队列后按之前的调度算法再开始调度运行便可。

六、主要代码分析

1、进程代码

<1>

/*

void CMainFrame::OnAuto()函数，自动产生进程控制块(PCB)状态。产生的 PCB挂接到以存在PCB的后面，其中，为了演示程序，优先级和所需时间都限

定在1-10之内。

*/

void CMainFrame::OnAuto()

{

//随机数产生

srand((unsigned)time(NULL));

//产生新的PCB指针

ready_end->next=new PCB();

ready_end=ready_end->next;

ready_end->next=NULL;

//产生新的PCB

ready_end->pid=getnewpid();

ready_end->status=0;

ready_end->priority=(rand()%9+1);

ready_end->start_time=task_timer;

ready_end->need_time=(rand()%9+1);

ready_end->wait_time=0;

ready_end->end_time=0;

//存储状态到pcb.txt

store_PCB(ready_end);

//进行刷新显示操作

status_print();

}

<2>

/*

void CMainFrame::OnManual()函数，点击菜单栏“手动输入”后手动创建 PCB。

*/

void CMainFrame::OnManual()

{

CInputDlg input;

if(input.DoModal()==IDOK){

if(!exist_pid(input.m_pid)){

ready_end->next=new PCB();

ready_end=ready_end->next;

ready_end->next=NULL;

ready_end->pid=input.m_pid;

ready_end->status=0;

ready_end->priority=input.m_priority;

ready_end->start_time=task_timer;

ready_end->need_time=input.m_needtime;

ready_end->wait_time=0;

ready_end->end_time=0;

store_PCB(ready_end);

status_print();

}

else MessageBox("ID号重复,请重新输入.");

}

}

<3>

/*

调用SetTimer函数，以一秒钟为单位，以定时器TASK_TIMER为标志，使用OnTimer()函数做事件响应。

*/

void CMainFrame::OnRun()

{

if(app_status==false)

{

SetTimer(TASK_TIMER,1000,NULL);

app_status=true;

}

}

其中，void CMainFrame::OnTimer(UINT nIDEvent)为关键函数。在此函数中，确定了

(1) 函数判断replay赋值情况，为真调用get_PCB_FromFile()函数，从pcb.txt文件中调用数据。

(2) 调用status_print()函数进行显示操作。【void CMainFrame::status_print()函数，在创建的矩形框内每隔单位时间(此时间为1秒)进行刷新显示所有可用PCB操作。】

(3) 在第一次运行OnTimer时，系统调用dispatch_entry()进行算法选择，只要用

户选择过算法，dispatch值会做响应改变，dispatch_entry()根据dispatch值进入相应算法。

void CMainFrame::OnTimer(UINT nIDEvent)

{

if(TASK_TIMER && app_status==true)

{

task_timer++;

if(replay==true)get_PCB_FromFile();

add_wait_time();

status_print();

dispatch_entry();

}

else task_timer=0;

CFrameWnd::OnTimer(nIDEvent);

}

【UINT SetTimer( UINT nIDEvent, UINT nElapse, void (CALLBACK EXPORT* lpfnTimer)(HWND, UINT, UINT, DWORD) );

参数含义：

nIDEvent:是指设置这个定时器的iD，即身份标志，这样在OnTimer（）事件中，才能根据不同的定时器，来做不同的事件响应。这个ID是一个无符号的整型。

nElapse:是指时间延迟。单位是毫秒。这意味着，每隔nElapse毫秒系统调用一次Ontimer（）。 】

<4>

周转时间：是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。 平均周转时间T=1/n[∑T].

带权周转时间W是指作业的周转时间T与系统为它提供服务的时间之比。 平均带权周转时间W=1/n[∑W].

void CMainFrame::OnPrintresult()

{

CRect rect;

CFont font;

HideCaret();

CDC *pDC;

pDC=GetDC();

CBrush brush;

CPen pen(PS_SOLID,2,RGB(84,141,226));

brush.CreateSolidBrush(RGB(84,141,226));

pDC->SelectObject(pen);

pDC->SelectObject(brush);

CFont* pOldFont=(CFont*)pDC->SelectObject(&font);

pDC->Rectangle(100,40,700,600);

pDC->TextOut(200,80,"PID 到达时间 服务时间 完成时间 周转时间 带权周转时间");

PCB *p=free->next; int i=0,s=100; int turnover,server_time; float sum_turn=0,sum_right=0,right=0; char buffer[100]; while(p!=NULL) //输出显示一个队列. {

//周转时间

turnover=p->end_time - p->start_time;

// 带权周转时间

right=turnover/ (float)(p->end_time - p->start_time - p->wait_time); server_time=p->end_time - p->start_time - p->wait_time; sprintf(buffer,"%3d%10d%16d%18d%17d%25.3f",

p->pid,p->start_time,server_time,p->end_time,turnover,right); sum_turn+=turnover;

sum_right+=right;

i++;

pDC->TextOut(200,s,buffer);

p=p->next;

s=s+20;

}

// sum_turn/i计算平均周转时间，sum_right/i计算平均带权周转时间 sprintf(buffer,"平均周转时间: %0.3f",sum_turn/i);

pDC->TextOut(200,s,buffer);

sprintf(buffer,"平均带权周转时间: %0.3f",sum_right/i); pDC->TextOut(200,s+20,buffer);

ReleaseDC(pDC);

ShowCaret();

}

<4>

//释放所有PCB占用空间

void CMainFrame::OnRelease() .

{

PCB *p;

while(free->next!=NULL){

p=free->next;

free->next=p->next;

delete p;

}

free_end=free;

MessageBox("释放成功");

}

<4>

赋值replay为true，调用OnRun()函数，进行进程显示操作。具体在OnTimer()

函数中已经说明

void CMainFrame::OnPlayback()

{

if(replay==false){

replay=true;

OnRun();

}

}

2、具体算法函数

<1> 每个具体算法函数对应一个dispatch值。

void CMainFrame::OnFcfs(){dispatch=1;}

void CMainFrame::OnSpf(){dispatch=2;}

void CMainFrame::OnTimeroll(){dispatch=3;}

void CMainFrame::OnPriority(){dispatch=4;}

void CMainFrame::OnHrespond(){dispatch=5;}

void CMainFrame::OnMultifeedback(){dispatch=6;}

<2> 先来先服务调度算法(FCFS)。按照先来先服务调度算法定义，依次执行队列中PCB。通过task_run()函数是从PCB队列中取出一个最靠前的PCB指针，处理完成后使用pcb_recycle()函数释放run指针空间；再继续使用task_run()函数??依次反复直到队列结束。

void CMainFrame::fcfs()

{

if(run!=NULL || ready->next!=NULL || blocked->next!=NULL){

task_run();

if(run!=NULL){

run->need_time--;

if(run->need_time==0){

pcb_recycle();

task_run();

if(run!=NULL)run->wait_time++;

}

}

}

else app_status=false;

}

void CMainFrame::task_run()

{

if(run==NULL && ready->next!=NULL)

{

run=ready->next;

ready->next=run->next;

run->next=NULL;

run->status=1;

if(run==ready_end)ready_end=ready;

}

}

void CMainFrame::pcb_recycle() //PCB回收机制.

{

free_end->next=run;

free_end=run;

free_end->status=0;

free_end->end_time=task_timer;

run=NULL;

}

<3> 短作业进程优先调度算法(SPF)。根据短作业进程优先调度算法定义，调用task_run_spf()函数以“need_time”为比较找出需要时间最短的PCB，进行显示后调用pcb_recycle()释放run空间；而后继续调用task_run_spf()函数??直到PCB队列结束。

void CMainFrame::spf()

{

if(run!=NULL || ready->next!=NULL || blocked->next!=NULL){

task_run_spf();

if(run!=NULL){

run->need_time--;

if(run->need_time==0){

pcb_recycle();

task_run_spf();

if(run!=NULL)run->wait_time++;

}

}

}

else app_status=false;

}

void CMainFrame::task_run_spf()

{

if(run==NULL && ready->next!=NULL)

{

PCB *p,*q,*r; //r指向p前一个PCB,q为搜索指针

r=ready;

p=q=ready->next;

while(q!=NULL){

if(p->need_time > q->need_time)p=q;

while(r->next!=p)r=r->next;

q=q->next;

}

r->next=p->next;

run=p;

run->next=NULL;

run->status=1;

if(run==ready_end)ready_end=ready;

}

}

<3> 时间片轮转调度算法。根据时间片轮转调度算法定义，设定时间片为TIME_CHIP=3,调用task_run()函数，从PCB队列中取出一个PCB，判断此PCB能否在一个时间片内执行完毕，如果不可以，在执行完毕后调用task_exchange_timeRoll()函数切换进程，并使用task_block()函数将此进程置于PCB队列最后；如果可以，释放此PCB所占空间后，调用task_run()函数继续调入后面PCB。反复直到PCB进行完毕。

void CMainFrame::timeRoll()

{

if(run!=NULL || ready->next!=NULL || blocked->next!=NULL){

task_run();

if(run!=NULL){

if((time_chip--)==0){ //进程切换.

task_exchange_timeRoll();

time_chip=TIME_CHIP;

}

else run->need_time--;

if(run->need_time==0){

time_chip=TIME_CHIP;

pcb_recycle();

task_run();

if(run!=NULL)run->wait_time++;

}

}

if(rand()%5==0){

task_block();

task_run();

}

if(rand()%5==4)task_wake();

}

else app_status=false;

}

void CMainFrame::task_exchange_timeRoll()

{

if(ready->next!=NULL)

{

ready_end->next=run;

ready_end=run;

ready_end->status=0;

run=NULL;

task_run();

}

}

void CMainFrame::task_block()

{

if(run!=NULL){

blocked_end->next=run;

blocked_end=run;

blocked_end->status=2;

run=NULL;

}

}

void CMainFrame::task_wake()

{

if(blocked->next!=NULL){

if(blocked->next==blocked_end)blocked_end=blocked;

ready_end->next=blocked->next;

ready_end=ready_end->next;

blocked->next=ready_end->next;

ready_end->next=NULL;

ready_end->status=0;

}

}

<4> 优先权调度算法。根据优先权调度算法定义，此算法将最初处于最高优先权的PCB完成之后再进行第二优先权PCB，即使用非抢占式优先权算法。它使用task_run_priority()函数找出优先权最高的PCB进程，然后进行，完成后释放空间；并继续调用task_run_priority()函数，直到PCB队列结束。

void CMainFrame::priority()

{

if(run!=NULL || ready->next!=NULL || blocked->next!=NULL){

task_run_priority();

if(run!=NULL){

run->need_time--;

if(run->need_time==0){

pcb_recycle();

task_run_priority();

if(run!=NULL)run->wait_time++;

}

}

}

else app_status=false;

}

void CMainFrame::task_run_priority()

{

if(run==NULL && ready->next!=NULL)

{

PCB *p,*q,*r;

r=ready;

p=q=ready->next;

while(q!=NULL){

if(p->priority > q->priority)p=q;

while(r->next!=p)r=r->next;

q=q->next;

}

r->next=p->next;

run=p;

run->next=NULL;

run->status=1;

if(run==ready_end)ready_end=ready;

}

}

<4> 高响应比优先算法。根据计算公式：R=(所需时间+已等待时间)/所需时间，调用task_run_hirespond()函数取出首个PCB进行，之后反复调用task_run_hirespond()函数直到结束。

void CMainFrame::hirespond()

{

if(run!=NULL || ready->next!=NULL || blocked->next!=NULL){

task_run_hirespond();

if(run!=NULL){

run->need_time--;

if(run->need_time==0){

pcb_recycle();

task_run_hirespond();

if(run!=NULL)run->wait_time++;

}

}

}

else app_status=false;

}

void CMainFrame::task_run_hirespond()

{

if(run==NULL && ready->next!=NULL)

{

PCB *p,*q,*r;

r=ready;

p=q=ready->next;

while(q!=NULL){

if(((p->wait_time+p->need_time)/p->need_time) <

((q->wait_time+q->need_time)/q->need_time)) p=q;

while(r->next!=p)r=r->next;

q=q->next;

}

r->next=p->next;

run=p;

run->next=NULL;

run->status=1;

if(run==ready_end)ready_end=ready;

}

}

<5> 多级反馈队列调度算法。设置多个就绪队列(ready,ready1,ready2)并初始化，调用task_run_multiFeedback(r,r_end)函数从PCB队列中读取第一个PCB，分入第一反馈队列，执行它后判断time_chip值，当值为0时调用task_exchange_multiFeedback(i)函数进行队列切换到第二队列，调用task_run_multiFeedback(r,r_end)函数从PCB队列中读取PCB，反复进行判断；当值不为0时，继续向第一队列添加PCB并判断run->need_time值，为0调用pcb_recycle()函数进行PCB空间释放操作，并继续余下进程。

void CMainFrame::multiFeedback()

{

if(run!=NULL || ready->next!=NULL || ready2->next!=NULL || ready3->next!=NULL || blocked->next!=NULL){

int i;

PCB *r,*r_end;

if(ready->next!=NULL){ i=1; r=ready; r_end=ready_end; }

else if(ready2->next!=NULL ){ i=2; r=ready2; r_end=ready2_end; } else { i=3; r=ready3; r_end=ready3_end; }

task_run_multiFeedback(r,r_end);

if((time_chip--)==0){ //进程切换.

task_exchange_multiFeedback(i);

time_chip=TIME_CHIP*i;

}

else run->need_time--;

if(run->need_time==0){

time_chip=TIME_CHIP*i;

pcb_recycle();

if( ready->next!=NULL) task_run_multiFeedback(ready,ready_end); else if(ready2->next!=NULL ) task_run_multiFeedback(ready2,ready2_end);

else if(ready3->next!=NULL ) task_run_multiFeedback(ready3,ready3_end);

if(run!=NULL) run->wait_time++;

}

}

else app_status=false;

}

///////////////////////////////////////////////////////////////////////

void CMainFrame::task_run_multiFeedback(PCB *r, PCB *r_end) //产生新进程

{

if(run==NULL && r->next!=NULL)

{

run=r->next;

r->next=run->next;

run->next=NULL;

run->status=1;

if(run==r_end){

if(r==ready)ready_end=ready;

else if(r==ready2)ready2_end=ready2;

else ready3_end=ready3;

}

}

}

void CMainFrame::task_exchange_multiFeedback(int i) //进程切换.

{

if(i==1)

{

ready2_end->next=run;

ready2_end=run;

ready2_end->status=0;

run=NULL;

if( ready->next!=NULL) task_run_multiFeedback(ready,ready_end);

else if(ready2->next!=NULL ) task_run_multiFeedback(ready2,ready2_end); else if(ready3->next!=NULL ) task_run_multiFeedback(ready3,ready3_end);

}

else if(i==2 || i==3)

{

ready3_end->next=run;

ready3_end=run;

ready3_end->status=0;

run=NULL;

if( ready->next!=NULL) task_run_multiFeedback(ready,ready_end);

else if(ready2->next!=NULL ) task_run_multiFeedback(ready2,ready2_end); else if(ready3->next!=NULL ) task_run_multiFeedback(ready3,ready3_end);

}

}

七、课程设计心得体会

通过本次操作系统课程设计让我对操作系统课程中所讲授的进程调度部分的认识有了一个质的进步。通过自己动手实现了进程相关的描述信息、进程调度算法、进程切换等功能更进一步了解了如何对进程操作同时也锻炼了自己编程的的能力。

八、程序中有几个不足之处：

1、使用了背景图后，在移动窗口覆盖时会调用OnDraw()函数进行重绘，有可能覆盖了输出显示。

2、时间片轮转调度算法中，有stack溢出错误，查询资料无法解决，不过不影响程序编译与执行。

3、多级反馈队列设计时有点混乱。

4、进程运行之后不能打断。

九、程序运行测试的部分截图

进程调度过程中的截图

调度运行完成后打印的结果

文件pcb.txt中保存的PCB

十、程序实现的主要代码

// MainFrm.h : interface of the CMainFrame class

//

/////////////////////////////////////////////////////////////////////////////

#if !defined(AFX_MAINFRM_H__4FD998F9_FB1D_409E_B6A1_A6CD8A6DDCC5__INCLUDED_)

#define

AFX_MAINFRM_H__4FD998F9_FB1D_409E_B6A1_A6CD8A6DDCC5__INCLUDED_

#if _MSC_VER > 1000

#pragma once

#endif // _MSC_VER > 1000

#define MAX_NUM 50

#define TIME_CHIP 3

#define PCB_FILENAME "pcb.txt"

#include <stdio.h>

//////////////////////////////////////////////////////////////////////////////

struct PCB{ //PCB结构

int pid; //ID号

int status; //进程状态

int priority; //进程优先级数值越小，优先级越高.

int start_time; //进程开始时间

int need_time; //进程执行所需时间

int wait_time; //进程已等待时间

int end_time; //运行结束时间

struct PCB *next; //PCB指针，指向下一PCB

};

//////////////////////////////////////////////////////////////////////////////

class CMainFrame : public CFrameWnd

{

protected: // create from serialization only

CMainFrame();

DECLARE_DYNCREATE(CMainFrame)

// Attributes

public:

// Operations

public:

// Overrides

// ClassWizard generated virtual function overrides //{{AFX_VIRTUAL(CMainFrame)

virtual BOOL PreCreateWindow(CREATESTRUCT& cs); //}}AFX_VIRTUAL

// Implementation

public:

bool replay;

void get_PCB_FromFile();

void linkchar(char * s,char c);

void store_PCB(const PCB* p);

void task_run_multiFeedback(PCB* r,PCB* r_end); void task_exchange_multiFeedback(int i);

void task_wake();

void task_block();

void pcb_recycle();

bool exist_pid(int id);

void task_run_priority();

void task_run_hirespond();

void task_exchange_timeRoll();

void task_run_spf();

void dispatch_entry();

void multiFeedback();

void hirespond();

void priority();

void timeRoll();

void spf();

void fcfs();

int getnewpid();

void status_print();

void task_run();

virtual ~CMainFrame();

#ifdef _DEBUG

virtual void AssertValid() const;

virtual void Dump(CDumpContext& dc) const;

#endif

protected: // control bar embedded members

CStatusBar m_wndStatusBar;

// Generated message map functions

protected:

//{{AFX_MSG(CMainFrame)

afx_msg int OnCreate(LPCREATESTRUCT lpCreateStruct); afx_msg void OnTimer(UINT nIDEvent);

afx_msg void OnDestroy();

afx_msg void OnManual();

afx_msg void OnRun();

afx_msg void OnAuto();

afx_msg void OnFcfs();

afx_msg void OnHrespond();

afx_msg void OnMultifeedback();

afx_msg void OnPriority();

afx_msg void OnSpf();

afx_msg void OnTimeroll();

afx_msg void OnPrintresult();

afx_msg void OnRelease();

afx_msg void OnPlayback();

//}}AFX_MSG

DECLARE_MESSAGE_MAP()

private:

int ready_num;

FILE* m_filein;

FILE* m_fileout;

void add_wait_time();

bool app_status; //标志有无进程运行

int dispatch; //调度算法标志

int task_timer; //时间

int time_chip; //时间片

PCB *run,*blocked,*blocked_end,*free,*free_end;

PCB *ready,*ready_end,*ready2,*ready2_end,*ready3,*ready3_end; };

/////////////////////////////////////////////////////////////////////////////

//{{AFX_INSERT_LOCATION}}

// Microsoft Visual C++ will insert additional declarations immediately before the previous line.

#endif

// !defined(AFX_MAINFRM_H__4FD998F9_FB1D_409E_B6A1_A6CD8A6DDCC5__INCLUDED_)

// MainFrm.h : interface of the CMainFrame class

//

/////////////////////////////////////////////////////////////////////////////

#if !defined(AFX_MAINFRM_H__4FD998F9_FB1D_409E_B6A1_A6CD8A6DDCC5__INCLUDED_)

#define

AFX_MAINFRM_H__4FD998F9_FB1D_409E_B6A1_A6CD8A6DDCC5__INCLUDED_

#if _MSC_VER > 1000

#pragma once

#endif // _MSC_VER > 1000

#define MAX_NUM 50

#define TIME_CHIP 3

#define PCB_FILENAME "pcb.txt"

#include <stdio.h>

//////////////////////////////////////////////////////////////////////////////

struct PCB{ //PCB结构

int pid; //ID号

int status; //进程状态

int priority; //进程优先级数值越小，优先级越高.

int start_time; //进程开始时间

int need_time; //进程执行所需时间

int wait_time; //进程已等待时间

int end_time; //运行结束时间

struct PCB *next; //PCB指针，指向下一PCB

};

//////////////////////////////////////////////////////////////////////////////

class CMainFrame : public CFrameWnd

{

protected: // create from serialization only

CMainFrame();

DECLARE_DYNCREATE(CMainFrame)

// Attributes

public:

// Operations

public:

// Overrides

// ClassWizard generated virtual function overrides //{{AFX_VIRTUAL(CMainFrame)

virtual BOOL PreCreateWindow(CREATESTRUCT& cs); //}}AFX_VIRTUAL

// Implementation

public:

bool replay;

void get_PCB_FromFile();

void linkchar(char * s,char c);

void store_PCB(const PCB* p);

void task_run_multiFeedback(PCB* r,PCB* r_end); void task_exchange_multiFeedback(int i);

void task_wake();

void task_block();

void pcb_recycle();

bool exist_pid(int id);

void task_run_priority();

void task_run_hirespond();

void task_exchange_timeRoll();

void task_run_spf();

void dispatch_entry();

void multiFeedback();

void hirespond();

void priority();

void timeRoll();

void spf();

void fcfs();

int getnewpid();

void status_print();

void task_run();

virtual ~CMainFrame();

#ifdef _DEBUG

virtual void AssertValid() const;

virtual void Dump(CDumpContext& dc) const;

#endif

protected: // control bar embedded members

CStatusBar m_wndStatusBar;

// Generated message map functions

protected:

//{{AFX_MSG(CMainFrame)

afx_msg int OnCreate(LPCREATESTRUCT lpCreateStruct);

afx_msg void OnTimer(UINT nIDEvent);

afx_msg void OnDestroy();

afx_msg void OnManual();

afx_msg void OnRun();

afx_msg void OnAuto();

afx_msg void OnFcfs();

afx_msg void OnHrespond();

afx_msg void OnMultifeedback();

afx_msg void OnPriority();

afx_msg void OnSpf();

afx_msg void OnTimeroll();

afx_msg void OnPrintresult();

afx_msg void OnRelease();

afx_msg void OnPlayback();

//}}AFX_MSG

DECLARE_MESSAGE_MAP()

private:

int ready_num;

FILE* m_filein;

FILE* m_fileout;

void add_wait_time();

bool app_status; //标志有无进程运行

int dispatch; //调度算法标志

int task_timer; //时间

int time_chip; //时间片

PCB *run,*blocked,*blocked_end,*free,*free_end;

PCB *ready,*ready_end,*ready2,*ready2_end,*ready3,*ready3_end;

};

/////////////////////////////////////////////////////////////////////////////

//{{AFX_INSERT_LOCATION}}

// Microsoft Visual C++ will insert additional declarations immediately before the previous line.

#endif

// !defined(AFX_MAINFRM_H__4FD998F9_FB1D_409E_B6A1_A6CD8A6DDCC5__INCLUDED_)

// MainFrm.cpp : implementation of the CMainFrame class

//

#include "stdafx.h"

#include "Task.h"

#include "MainFrm.h"

#include "InputDlg.h"

#include <stdlib.h>

#include <time.h>

#ifdef _DEBUG

#define new DEBUG_NEW

#undef THIS_FILE

static char THIS_FILE[] = __FILE__;

#endif

#define TASK_TIMER 1

/////////////////////////////////////////////////////////////////////////////

// CMainFrame

IMPLEMENT_DYNCREATE(CMainFrame, CFrameWnd)

BEGIN_MESSAGE_MAP(CMainFrame, CFrameWnd)

//{{AFX_MSG_MAP(CMainFrame)

ON_WM_CREATE()

ON_WM_TIMER()

ON_WM_DESTROY()

ON_COMMAND(ID_MANUAL, OnManual)

ON_COMMAND(ID_RUN, OnRun)

ON_COMMAND(ID_AUTO, OnAuto)

ON_COMMAND(ID_FCFS, OnFcfs)

ON_COMMAND(ID_HRESPOND, OnHrespond)

ON_COMMAND(ID_MULTIFEEDBACK, OnMultifeedback)

ON_COMMAND(ID_PRIORITY, OnPriority)

ON_COMMAND(ID_SPF, OnSpf)

ON_COMMAND(ID_TIMEROLL, OnTimeroll)

ON_COMMAND(ID_PRINTRESULT, OnPrintresult)

ON_COMMAND(ID_RELEASE, OnRelease)

ON_COMMAND(IDM_PLAYBACK, OnPlayback)

//}}AFX_MSG_MAP

END_MESSAGE_MAP()

static UINT indicators[] =

{

ID_SEPARATOR, // status line indicator ID_INDICATOR_CAPS,

ID_INDICATOR_NUM,

ID_INDICATOR_SCRL,

};

///////////////////////////////////////////////////////////////////////////// // CMainFrame construction/destruction

CMainFrame::CMainFrame()

{

task_timer=0;

run=NULL;

blocked=new PCB();

blocked->next=NULL;

blocked_end=blocked;

ready=new PCB();

ready->next=NULL;

ready_end=ready;

free=new PCB();

free->next=NULL;

free_end=free;

ready2=new PCB();

ready2->next=NULL;

ready2_end=ready2;

ready3=new PCB();

ready3->next=NULL;

ready3_end=ready3;

replay=false;

app_status=false;

ready_num=1;

dispatch=1; //默认调度算法：FCFS. time_chip=TIME_CHIP; //设置时间片大小 srand((unsigned)time(NULL));

//初始化文件操作成员变量。

m_fileout=fopen(PCB_FILENAME,"w");

fclose(m_fileout);

}

CMainFrame::~CMainFrame()

{

delete ready;

delete ready2;

delete ready3;

delete blocked;

delete free;

}

int CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct) {

if (CFrameWnd::OnCreate(lpCreateStruct) == -1)

return -1;

if (!m_wndStatusBar.Create(this) ||

!m_wndStatusBar.SetIndicators(indicators,

sizeof(indicators)/sizeof(UINT)))

{

TRACE0("Failed to create status bar\n");

return -1; // fail to create

}

CRect rect(100,100,900,800);

this->MoveWindow(rect,true);

return 0;

}

BOOL CMainFrame::PreCreateWindow(CREATESTRUCT& cs) {

if( !CFrameWnd::PreCreateWindow(cs) )

return FALSE;

// TODO: Modify the Window class or styles here by modifying // the CREATESTRUCT cs

cs.lpszName = "进程/作业调度"; cs.style &= ~FWS_ADDTOTITLE; //必须要加 return TRUE;

}

/////////////////////////////////////////////////////////////////////////////

// CMainFrame diagnostics //标题名

#ifdef _DEBUG

void CMainFrame::AssertValid() const

{

CFrameWnd::AssertValid();

}

void CMainFrame::Dump(CDumpContext& dc) const

{

CFrameWnd::Dump(dc);

}

#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////

// CMainFrame message handlers

/*

SetTimer表示的是定义个定时器。根据定义指定的窗口，在指定的窗口（CWnd）中实现OnTimer事件，这样，就可以相应事件了。

SetTimer有两个函数。一个是全局的函数::SetTimer()

UINT SetTimer(

HWND hWnd, // handle of window for timer messages

UINT nIDEvent, // timer identifier

UINT uElapse, // time-out value

TIMERPROC lpTimerFunc // address of timer procedure

);

其中hWnd 是指向CWnd的指针，即处理Timer事件的窗口类。说道窗口类（CWnd），我们有必要来看一下CWnd的继承情况：CWnd有以下子类：CFrameWnd,CDialog,CView,CControlBar等类。这也意味这些类中都可以定义SetTimer事件。

同时，SetTimer（）在CWnd中也有定义，即SetTimer（）是CWnd的一个成员函数。CWnd的子类可以调用该函数，来设置触发器。

UINT SetTimer( UINT nIDEvent, UINT nElapse, void (CALLBACK EXPORT* lpfnTimer)(HWND, UINT, UINT, DWORD) );

参数含义：

nIDEvent:是指设置这个定时器的iD，即身份标志，这样在OnTimer（）事件中，才能根据不同的定时器，来做不同的事件响应。这个ID是一个无符号的整型。

nElapse:是指时间延迟。单位是毫秒。这意味着，每隔nElapse毫秒系统调用一次Ontimer（）。

*/

/*

调用SetTimer函数，以一秒钟为单位，以定时器TASK_TIMER为标志，做事件响应。

*/

void CMainFrame::OnRun()

{

if(app_status==false)

{

SetTimer(TASK_TIMER,1000,NULL);

app_status=true;

}

}

void CMainFrame::OnTimer(UINT nIDEvent)

{

if(TASK_TIMER && app_status==true)

{

task_timer++;

if(replay==true)get_PCB_FromFile();

add_wait_time();

status_print();

dispatch_entry();

}

else task_timer=0;

CFrameWnd::OnTimer(nIDEvent);

}

void CMainFrame::OnDestroy()

{

CFrameWnd::OnDestroy();

KillTimer(TASK_TIMER);

}

/*

void CMainFrame::OnManual()函数，点击菜单栏“手动输入”后手动创建 PCB。

*/

void CMainFrame::OnManual()

{

CInputDlg input;

if(input.DoModal()==IDOK){

if(!exist_pid(input.m_pid)){

ready_end->next=new PCB();

ready_end=ready_end->next;

ready_end->next=NULL;

ready_end->pid=input.m_pid;

ready_end->status=0;

ready_end->priority=input.m_priority;

ready_end->start_time=task_timer;

ready_end->need_time=input.m_needtime;

ready_end->wait_time=0;

ready_end->end_time=0;

store_PCB(ready_end);

status_print();

}

else MessageBox("ID号重复,请重新输入.");

}

}

/*

void CMainFrame::OnAuto()函数，自动产生进程控制块(PCB)状态。产生的 PCB挂接到以存在PCB的后面，其中，为了演示程序，优先级和所需时间都限

定在1-10之内。

*/

void CMainFrame::OnAuto()

{

//随机数产生

srand((unsigned)time(NULL));

//产生新的PCB指针

ready_end->next=new PCB();

ready_end=ready_end->next;

ready_end->next=NULL;

//产生新的PCB

ready_end->pid=getnewpid();

ready_end->status=0;

ready_end->priority=(rand()%9+1);

ready_end->start_time=task_timer;

ready_end->need_time=(rand()%9+1);

ready_end->wait_time=0;

ready_end->end_time=0;

//存储状态到pcb.txt

store_PCB(ready_end);

//进行刷新显示操作

status_print();

}

void CMainFrame::OnPrintresult()

{

CRect rect;

CFont font;

HideCaret();

CDC *pDC;

pDC=GetDC();

CBrush brush;

CPen pen(PS_SOLID,2,RGB(84,141,226));

brush.CreateSolidBrush(RGB(84,141,226));

pDC->SelectObject(pen);

pDC->SelectObject(brush);

CFont* pOldFont=(CFont*)pDC->SelectObject(&font);

pDC->SetBkMode(TRANSPARENT);

//pDC->SelectStockObject(NULL_BRUSH);

//pDC->Rectangle(&rect);

pDC->Rectangle(100,40,700,600);

pDC->TextOut(200,80,"PID 到达时间 服务时间 完成时间 周转时间 带权周转时间");

PCB *p=free->next;

int i=0,s=100;

int turnover,server_time;

float sum_turn=0,sum_right=0,right=0;

char buffer[100];

while(p!=NULL) //输出显示一个队列.

{

//周转时间

turnover=p->end_time - p->start_time;

// 带权周转时间

right=turnover / (float)(p->end_time - p->start_time - p->wait_time); server_time=p->end_time - p->start_time - p->wait_time;

sprintf(buffer,"%3d%10d%16d%18d%17d%25.3f",

p->pid,p->start_time,server_time,p->end_time,turnover,right); sum_turn+=turnover;

sum_right+=right;

i++;

pDC->TextOut(200,s,buffer);

p=p->next;

s=s+20;

}

// sum_turn/i计算平均周转时间，sum_right/i计算平均带权周转时间 sprintf(buffer,"平均周转时间: %0.3f",sum_turn/i);

pDC->TextOut(200,s,buffer);

sprintf(buffer,"平均带权周转时间: %0.3f",sum_right/i);

pDC->TextOut(200,s+20,buffer);

ReleaseDC(pDC);

ShowCaret();

}

void CMainFrame::OnRelease() //释放所有PCB.

{

PCB *p;

while(free->next!=NULL){

p=free->next;

free->next=p->next;

delete p;

}

free_end=free;

MessageBox("释放成功");

}

void CMainFrame::OnPlayback()

{

if(replay==false){

replay=true;

OnRun();

}

}

/*

void CMainFrame::status_print()函数，再创建的矩形框内每隔单位时间(此时间

受时间随机函数控制)进行刷新显示进程进展操作。

*/

void CMainFrame::status_print() //刷新输出显示所有可用PCB.

{

//图形化参数

CRect rect;

CFont font;

HideCaret();

CDC *pDC;

pDC=GetDC();

//////////////////////////////////刷新设置

CBrush brush;

CPen pen(PS_SOLID,2,RGB(84,141,226));

brush.CreateSolidBrush(RGB(84,141,226));

pDC->SelectObject(pen);

pDC->SelectObject(brush);

//////////////////////////////////////////

//创建矩形框体

pDC->Rectangle(100,40,700,600);

//透明背景设置

CFont* pOldFont=(CFont*)pDC->SelectObject(&font);

pDC->SetBkMode(TRANSPARENT);

//文本输出设置

pDC->TextOut(200,40,"PID 状态 优先级 开始时间 所需时间 已等待时间");

//pDC->SelectStockObject(NULL_BRUSH);

//pDC->Rectangle(&rect);

//主体输出函数，判定有几个就绪队列后进行输出。

PCB *p;

int i=0,s=60;

char buffer[100];

do{

if(i==0)p=run;

else if(i==1)p=ready;

else if(i==2)p=ready2;

else if(i==3)p=ready3;

else p=blocked;

if((p==ready || p==blocked || p==ready2 || p==ready3) && p!=NULL) p=p->next;

while(p!=NULL) //输出显示一个队列.

{

sprintf(buffer,"%3d%8d%10d%14d%16d%18d",p->pid,p->status,p->priority,p->start_time,p->need_time,p->wait_time);

pDC->TextOut(200,s,buffer);

p=p->next;

s=s+20;

}

i++;

}while(i!=5);

ReleaseDC(pDC);

ShowCaret();

}

void CMainFrame::add_wait_time()

{

if(run!=NULL || blocked->next!=NULL){ int i=0;

PCB *p;

do{

if(i==0)p=ready;

else if(i==1) p=ready2;

else if(i==2) p=ready3;

else p=blocked;

p=p->next;

while(p!=NULL)

{

p->wait_time++;

p=p->next;

}

i++;

}while(i!=4);

}

}

////////////////////调度算法的响应函数/////////////////// void CMainFrame::OnFcfs(){dispatch=1;} void CMainFrame::OnSpf(){dispatch=2;}

void CMainFrame::OnTimeroll(){dispatch=3;} void CMainFrame::OnPriority(){dispatch=4;} void CMainFrame::OnHrespond(){dispatch=5;} void CMainFrame::OnMultifeedback(){dispatch=6;} /////////////////////////////////////////////////////////

int CMainFrame::getnewpid()

{

int id;

id=rand()%999+1;

while(exist_pid(id))id=rand()%999+1; return id;

}

bool CMainFrame::exist_pid(int id)

{

PCB *p;

int i=0;

do{

if(i==0)p=run;

else if(i==1)p=ready;

else p=blocked;

if((p==ready || p==blocked) && p!=NULL)p=p->next;

while(p!=NULL)

{

if(id==p->pid)return true;

p=p->next;

}

i++;

}while(i!=3);

return false;

}

void CMainFrame::pcb_recycle() //PCB回收机制.

{

free_end->next=run;

free_end=run;

free_end->status=0;

free_end->end_time=task_timer;

run=NULL;

}

void CMainFrame::dispatch_entry() //算法入口

{

switch(dispatch)

{

case 1:fcfs();break;

case 2:spf();break;

case 3:timeRoll();break;

case 4:priority();break;

case 5:hirespond();break;

case 6:multiFeedback();

}

}

////////////////////////////////////////调度算法///////////////////////////////

void CMainFrame::fcfs()

{

if(run!=NULL || ready->next!=NULL || blocked->next!=NULL){ task_run();

if(run!=NULL){

run->need_time--;

if(run->need_time==0){

pcb_recycle();

task_run();

if(run!=NULL)run->wait_time++;

}

}

/* if(rand()%5==0){ //进程阻塞和唤醒可能同时发生. task_block();

task_run();

}

if(rand()%5==4)task_wake();*/

}

else app_status=false;

}

void CMainFrame::spf()

{

if(run!=NULL || ready->next!=NULL || blocked->next!=NULL){ task_run_spf();

if(run!=NULL){

run->need_time--;

if(run->need_time==0){

pcb_recycle();

task_run_spf();

if(run!=NULL)run->wait_time++;

}

}

/* if(rand()%5==0){

task_block();

task_run();

}

if(rand()%5==4)task_wake();*/

}

else app_status=false;

}

void CMainFrame::timeRoll()

{

if(run!=NULL || ready->next!=NULL || blocked->next!=NULL){ task_run();

if(run!=NULL){

if((time_chip--)==0){ //进程切换.

task_exchange_timeRoll();

time_chip=TIME_CHIP;

}

else run->need_time--;

if(run->need_time==0){

time_chip=TIME_CHIP;

pcb_recycle();

task_run();

if(run!=NULL)run->wait_time++;

}

}

if(rand()%5==0){

task_block();

task_run();

}

if(rand()%5==4)task_wake();

}

else app_status=false;

}

void CMainFrame::priority()

{

if(run!=NULL || ready->next!=NULL || blocked->next!=NULL){ task_run_priority();

if(run!=NULL){

run->need_time--;

if(run->need_time==0){

pcb_recycle();

task_run_priority();

if(run!=NULL)run->wait_time++;

}

}

/* if(rand()%5==0){

task_block();

task_run();

}

if(rand()%5==4)task_wake();*/

}

else app_status=false;

}

void CMainFrame::hirespond()

{

if(run!=NULL || ready->next!=NULL || blocked->next!=NULL){ task_run_hirespond();

if(run!=NULL){

run->need_time--;

if(run->need_time==0){

pcb_recycle();

task_run_hirespond();

if(run!=NULL)run->wait_time++;

}

}

/* if(rand()%5==0){

task_block();

task_run();

}

if(rand()%5==4)task_wake();*/

}

else app_status=false;

}

void CMainFrame::multiFeedback()

{

if(run!=NULL || ready->next!=NULL || ready2->next!=NULL || ready3->next!=NULL || blocked->next!=NULL){

int i;

PCB *r,*r_end;

if(ready->next!=NULL){ i=1; r=ready; r_end=ready_end; }

else if(ready2->next!=NULL ){ i=2; r=ready2; r_end=ready2_end; } else { i=3; r=ready3; r_end=ready3_end; }

task_run_multiFeedback(r,r_end);

if((time_chip--)==0){ //进程切换.

//if(run!=NULL && ready->next==NULL && ready2->next==NULL && ready3->next==NULL && blocked->next==NULL) // if(ready_num!=3)ready_num++;

task_exchange_multiFeedback(i);

time_chip=TIME_CHIP*i;

}

else run->need_time--;

if(run->need_time==0){

time_chip=TIME_CHIP*i;

pcb_recycle();

if( ready->next!=NULL) task_run_multiFeedback(ready,ready_end); else if(ready2->next!=NULL ) task_run_multiFeedback(ready2,ready2_end);

else if(ready3->next!=NULL ) task_run_multiFeedback(ready3,ready3_end);

if(run!=NULL) run->wait_time++;

}

}

/* if(rand()%5==0){

task_block();

if( ready->next!=NULL) task_run_multiFeedback(ready,ready_end);

else if(ready1->next!=NULL task_run_multiFeedback(ready1,ready1_end);

else if(ready2->next!=NULL task_run_multiFeedback(ready2,ready2_end);

}

if(rand()%5==4)task_wake();*/

else app_status=false;

}

///////////////////////////////////////////////////////////////////////

void CMainFrame::task_block()

{

if(run!=NULL){

blocked_end->next=run;

blocked_end=run;

blocked_end->status=2;

run=NULL;

}

}

void CMainFrame::task_wake()

{

if(blocked->next!=NULL){

if(blocked->next==blocked_end)blocked_end=blocked; ready_end->next=blocked->next;

ready_end=ready_end->next;

blocked->next=ready_end->next;

ready_end->next=NULL;

ready_end->status=0;

}

}

void CMainFrame::task_run()

{

if(run==NULL && ready->next!=NULL)

{

run=ready->next;

ready->next=run->next;

run->next=NULL;

run->status=1;

if(run==ready_end)ready_end=ready;

}

}

) )

void CMainFrame::task_run_spf()

{

if(run==NULL && ready->next!=NULL)

{

PCB *p,*q,*r; //r指向p前一个PCB,q为搜索指针 r=ready;

p=q=ready->next;

while(q!=NULL){

if(p->need_time > q->need_time)p=q;

while(r->next!=p)r=r->next;

q=q->next;

}

r->next=p->next;

run=p;

run->next=NULL;

run->status=1;

if(run==ready_end)ready_end=ready;

}

}

void CMainFrame::task_exchange_timeRoll()

{

if(ready->next!=NULL)

{

ready_end->next=run;

ready_end=run;

ready_end->status=0;

run=NULL;

task_run();

}

}

void CMainFrame::task_run_priority()

{

if(run==NULL && ready->next!=NULL)

{

PCB *p,*q,*r;

r=ready;

p=q=ready->next;

while(q!=NULL){

if(p->priority > q->priority)p=q;

while(r->next!=p)r=r->next;

q=q->next;

}

r->next=p->next;

run=p;

run->next=NULL;

run->status=1;

if(run==ready_end)ready_end=ready;

}

}

void CMainFrame::task_run_hirespond()

{

if(run==NULL && ready->next!=NULL)

{

PCB *p,*q,*r;

r=ready;

p=q=ready->next;

while(q!=NULL){

if(((p->wait_time+p->need_time)/p->need_time) ((q->wait_time+q->need_time)/q->need_time)) p=q;

while(r->next!=p)r=r->next;

q=q->next;

}

r->next=p->next;

run=p;

run->next=NULL;

run->status=1;

if(run==ready_end)ready_end=ready;

}

}

void CMainFrame::task_run_multiFeedback(PCB *r, PCB *r_end) 程

{

if(run==NULL && r->next!=NULL)

{

run=r->next;

r->next=run->next;

run->next=NULL;

run->status=1;

if(run==r_end){

if(r==ready)ready_end=ready;

else if(r==ready2)ready2_end=ready2;

else ready3_end=ready3;

} < //产生新进

}

}

void CMainFrame::task_exchange_multiFeedback(int i) //进程切换.

{

if(i==1)

{

ready2_end->next=run;

ready2_end=run;

ready2_end->status=0;

run=NULL;

if( ready->next!=NULL) task_run_multiFeedback(ready,ready_end);

else if(ready2->next!=NULL ) task_run_multiFeedback(ready2,ready2_end); else if(ready3->next!=NULL ) task_run_multiFeedback(ready3,ready3_end);

}

else if(i==2 || i==3)

{

ready3_end->next=run;

ready3_end=run;

ready3_end->status=0;

run=NULL;

if( ready->next!=NULL) task_run_multiFeedback(ready,ready_end);

else if(ready2->next!=NULL ) task_run_multiFeedback(ready2,ready2_end); else if(ready3->next!=NULL ) task_run_multiFeedback(ready3,ready3_end);

}

}

void CMainFrame::store_PCB( const PCB* p)

{

m_fileout=fopen(PCB_FILENAME,"a+");

charbuf[20];

//save end_time;

sprintf(buf,"%d%s",p->end_time,"\t");

fputs(buf,m_fileout);

//save need_time

memset(buf,0,20);

sprintf(buf,"%d%s",p->need_time,"\t");

fputs(buf,m_fileout);

//save next

memset(buf,0,20);

sprintf(buf,"%d%s",(int)p->next,"\t");

fputs(buf,m_fileout);

//save pid

memset(buf,0,20);

sprintf(buf,"%d%s",p->pid,"\t"); fputs(buf,m_fileout);

//save priority

memset(buf,0,20);

sprintf(buf,"%d%s",p->priority,"\t"); fputs(buf,m_fileout);

//save start_time

memset(buf,0,20);

sprintf(buf,"%d%s",p->start_time,"\t"); fputs(buf,m_fileout);

//save status

memset(buf,0,20);

sprintf(buf,"%d%s",p->status,"\t"); fputs(buf,m_fileout);

//save wait_time

memset(buf,0,20);

sprintf(buf,"%d%s",p->wait_time,"\t"); fputs(buf,m_fileout);

fclose(m_fileout);

}

void CMainFrame::linkchar(char* s,char {

int i=0;

while(s[i]!='\0')

{

i++;

}

s[i]=c;

s[i+1]='\0';

}

void CMainFrame::get_PCB_FromFile() {

PCB *p=new PCB();

m_filein=fopen(PCB_FILENAME,"r"); charbufin[1024];

charbuf[20],ch;

int j=0;

memset(bufin,'\0',1024);

/* memset c)

用法: void *memset(void *s, char ch, unsigned n);

功 能: 将s所指向的某一块内存中的每个字节的内容全部设置为ch指定的ASCII值,

// 块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作

*/

fread(bufin,sizeof(char),1024,m_filein);

fclose(m_filein);

//read end_time

memset(buf,0,20);

while(true)

{

if('\t'!=(ch=bufin[j++]))

{

if(ch=='\0') return;

linkchar(buf,ch);

}

else break;

}

p->end_time=atoi(buf);

//read need_time

memset(buf,0,20);

while(true)

{

if('\t'!=(ch=bufin[j++]))

{

linkchar(buf,ch);

}

else break;

}

p->need_time=atoi(buf);

//read next

memset(buf,0,20);

while(true)

{

if('\t'!=(ch=bufin[j++]))

{

linkchar(buf,ch);

}

else break;

}

p->next=(PCB*)atoi(buf);

//read pid

memset(buf,0,20); while(true) { if('\t'!=(ch=bufin[j++])) { linkchar(buf,ch); } else break; } p->pid=atoi(buf); //read priority memset(buf,0,20); while(true) { if('\t'!=(ch=bufin[j++])) { linkchar(buf,ch); } else break; } p->priority=atoi(buf); //read start_time memset(buf,0,20); while(true) { if('\t'!=(ch=bufin[j++])) { linkchar(buf,ch); } else break; } p->start_time=atoi(buf); //read status memset(buf,0,20); while(true) { if('\t'!=(ch=bufin[j++])) { linkchar(buf,ch); } else break; } p->status=atoi(buf); //read wait_time

memset(buf,0,20);

while(true)

{

if('\t'!=(ch=bufin[j++]))

{

linkchar(buf,ch);

}

else break;

}

p->wait_time=atoi(buf);

if(p->start_time==task_timer-1)

{

for(int k=0;(bufin[j]!='\0');k++,j++)

{

bufin[k]=bufin[j];

}

bufin[k]='\0';

//保存修改后的PCB文件。

m_fileout=fopen(PCB_FILENAME,"w"); fputs(bufin,m_fileout);

fclose(m_fileout);

//将新产生的PCB放入就绪队列里.

ready_end->next=p;

ready_end=ready_end->next;

get_PCB_FromFile();

}

else delete p;

}

// Task.cpp : Defines the class behaviors for the application. //

#include "stdafx.h"

#include "Task.h"

#include "MainFrm.h"

#include "TaskDoc.h"

#include "TaskView.h"

#ifdef _DEBUG

#define new DEBUG_NEW

#undef THIS_FILE

static char THIS_FILE[] = __FILE__;

#endif

/////////////////////////////////////////////////////////////////////////////

// CTaskApp

BEGIN_MESSAGE_MAP(CTaskApp, CWinApp)

//{{AFX_MSG_MAP(CTaskApp)

ON_COMMAND(ID_APP_ABOUT, OnAppAbout)

// NOTE - the ClassWizard will add and remove mapping macros here. // DO NOT EDIT what you see in these blocks of generated code! //}}AFX_MSG_MAP

// Standard file based document commands

ON_COMMAND(ID_FILE_NEW, CWinApp::OnFileNew)

ON_COMMAND(ID_FILE_OPEN, CWinApp::OnFileOpen)

// Standard print setup command

ON_COMMAND(ID_FILE_PRINT_SETUP, CWinApp::OnFilePrintSetup) END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////

// CTaskApp construction

CTaskApp::CTaskApp()

{

// TODO: add construction code here,

// Place all significant initialization in InitInstance

}

/////////////////////////////////////////////////////////////////////////////

// The one and only CTaskApp object

CTaskApp theApp;

/////////////////////////////////////////////////////////////////////////////

// CTaskApp initialization

BOOL CTaskApp::InitInstance()

{

SetDialogBkColor(RGB(84, 141, 226), RGB(0, 0, 255));

AfxEnableControlContainer();

// Standard initialization

// If you are not using these features and wish to reduce the size

// of your final executable, you should remove from the following // the specific initialization routines you do not need.

#ifdef _AFXDLL

Enable3dControls(); // Call this when using MFC in a shared DLL #else

Enable3dControlsStatic(); // Call this when linking to MFC statically #endif

// Change the registry key under which our settings are stored.

// TODO: You should modify this string to be something appropriate // such as the name of your company or organization.

SetRegistryKey(_T("Local AppWizard-Generated Applications"));

LoadStdProfileSettings(); // Load standard INI file options (including MRU)

// Register the application's document templates. Document templates // serve as the connection between documents, frame windows and views.

CSingleDocTemplate* pDocTemplate;

pDocTemplate = new CSingleDocTemplate(

IDR_MAINFRAME,

RUNTIME_CLASS(CTaskDoc),

RUNTIME_CLASS(CMainFrame), // main SDI frame window RUNTIME_CLASS(CTaskView));

AddDocTemplate(pDocTemplate);

// Parse command line for standard shell commands, DDE, file open CCommandLineInfo cmdInfo;

ParseCommandLine(cmdInfo);

// Dispatch commands specified on the command line

if (!ProcessShellCommand(cmdInfo))

return FALSE;

// The one and only window has been initialized, so show and update it. m_pMainWnd->ShowWindow(SW_SHOW);

m_pMainWnd->UpdateWindow();

return TRUE;

}

/////////////////////////////////////////////////////////////////////////////

// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog

{

public:

CAboutDlg();

// Dialog Data

//{{AFX_DATA(CAboutDlg)

enum { IDD = IDD_ABOUTBOX };

//}}AFX_DATA

// ClassWizard generated virtual function overrides //{{AFX_VIRTUAL(CAboutDlg)

protected:

virtual void DoDataExchange(CDataExchange* pDX); //}}AFX_VIRTUAL

// Implementation

protected:

//{{AFX_MSG(CAboutDlg)

// No message handlers

//}}AFX_MSG

DECLARE_MESSAGE_MAP()

};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD) {

//{{AFX_DATA_INIT(CAboutDlg)

//}}AFX_DATA_INIT

}

void CAboutDlg::DoDataExchange(CDataExchange* pDX) {

CDialog::DoDataExchange(pDX);

//{{AFX_DATA_MAP(CAboutDlg)

//}}AFX_DATA_MAP

}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog) //{{AFX_MSG_MAP(CAboutDlg)

// No message handlers

//}}AFX_MSG_MAP

END_MESSAGE_MAP()

// App command to run the dialog // DDX/DDV support

void CTaskApp::OnAppAbout()

{

CAboutDlg aboutDlg;

aboutDlg.DoModal();

}

///////////////////////////////////////////////////////////////////////////// // CTaskApp message handlers