操作系统进程调度算法 先到先服务 短作业 优先级 时间片轮转

时间:2021-12-08 21:13:43

#include <iostream>

#include <stdio.h>

#include <string>

//#include <windows.h>

using namespace std;

//hyugtyftydrtdtrdrrtrdrt

struct Node

{

   string name;//进程(作业)名称

   int arriveTime;//到达时间

   int ServerTime;//服务时间

   int leftTime;//the left time

   Node *link;//指向下一个节点的指针

};

class CProcess

{

 

public:

    CProcess();//构造函数

~CProcess();//析构函数

const CProcess &operator =(const CProcess& p);//重载赋值操作符

    void insertNode(string &na,int& at,int& st);//插入新元素(at由小到大)到链表合适的位置

    void sort();//按照服务时间由大到小排序

bool isEmpty();//判断是否为空

void destroy();//销毁

int length();//求出链表长度

void print();//打印出元素

void FCFS();//先到先服务

void SJF();//短进程(作业)优先

void RR(int& q);//时间片轮转

void priority();//优先权调度

protected:

Node *first;

Node *last;

 

};

const CProcess& CProcess::operator=(const CProcess& p)

{

    Node *newNode;

Node *Current;

if(this!=&p)//避免自己给自己赋值

{

if(first!=NULL)//如果链表不为空

destroy();

if(p.first==NULL)

{//如果要拷贝的对象为空

this->first = NULL;

this->last = NULL;

}

else

{

Current = p.first;

first= new Node;

first->name=Current->name;//

            first->arriveTime=Current->arriveTime;

first->ServerTime=Current->ServerTime;

first->link =NULL;

last =first;

Current = Current->link;

while(Current!=NULL)

{

newNode = new Node;

newNode->name=Current->name;

                newNode->arriveTime=Current->arriveTime;

newNode->ServerTime=Current->ServerTime;

newNode->link=NULL;

last->link=newNode;

last=newNode;

Current = Current->link;

}

}

}

return *this;

}

 

CProcess::CProcess()

{//构造函数

   first=NULL;

   last=NULL;

}

CProcess::~CProcess()

{

Node *temp;

while(first!=NULL)

{

temp=first;

first=first->link;

delete temp;

}

last=NULL;

 

}

 

void CProcess::insertNode(string &na,int& at,int& st)

{//按照到达时间升序排序

Node *Current;

Node *trailCurrent;//指向Current的前一个节点

Node *newNode;

bool found;

newNode = new Node;//建立一个新节点

    newNode->name=na;

newNode->arriveTime=at;

newNode->ServerTime=st;

newNode->link=NULL;//

if(first==NULL)//如果第一个节点为空(如果是第一次插入元素)

first=newNode;//将新节点赋给第一个节点

else

{//如果不是第一次

Current =first;

found = false;

while(Current!=NULL && !found)

{

if(Current->arriveTime >= at)

found = true;

else

{

trailCurrent = Current;

Current = Current->link;

}

}

if(Current==first)

{

newNode->link = first;

first = newNode;

}

else

{

trailCurrent->link = newNode;

newNode->link = Current;

}

}

}

int CProcess::length()

{

int count =0;//声明变量,并初始化为0(用来记录长度)

Node *Current;

Current = first;

while(Current!=NULL)//当前节点不为空,记录值自加,一直向后遍历,

{

count++;

Current = Current->link;

}

return count;//返回长度

}

void CProcess::sort()//按照服务时间,升序排列

{//冒泡排序

string sname;

int at;

int st;

Node *Current;//指向当前节点

Node *trailCurrent;//指向当前节点的前一个节点

   for(trailCurrent=first->link;trailCurrent!=NULL;trailCurrent=trailCurrent->link)//控制条件有问题

{

        for(Current=trailCurrent->link;Current!=NULL;Current=Current->link)//控制条件有问题

{

            if(trailCurrent->ServerTime > Current->ServerTime)

{

 

                 sname=trailCurrent->name;

 at=trailCurrent->arriveTime;

 st=trailCurrent->ServerTime;

 

 trailCurrent->name=Current->name;

 trailCurrent->arriveTime=Current->arriveTime;

 trailCurrent->ServerTime=Current->ServerTime;

 

 Current->name=sname;

 Current->arriveTime=at;

 Current->ServerTime=st;

 

}

}

}

}

 

bool CProcess::isEmpty()//判断是否为空

{

    return (first==NULL);//如果第一个节点为空,返回值

}

void CProcess::print()

{

Node *Current;

Current = first->link;//头节点赋给当前节点

while(Current!=NULL)//当前节点不为空,一直向后遍历打印

{

cout<<Current->name<<" ";

cout<<Current->arriveTime<<" ";

cout<<Current->ServerTime<<"/n";

Current = Current->link;

}

}

void CProcess::destroy()

Node *temp;//定义一个临时指针变量

while(first!=NULL)

{

temp=first;

first=first->link;

delete temp;

}

last=NULL;

}

void CProcess::FCFS()//先到先服务

{

Node *Current;

int T0=0;//完成时间

int T1=0;//周转时间

    Current = first->link;//头节点赋给当前节点

while(Current!=NULL)

{   

if(T0 < Current->arriveTime)

{

            T0=Current->arriveTime+Current->ServerTime;

T1=T0-Current->arriveTime;

cout<<Current->name<<"/t";//打印出进程名

cout<<T0<<"/t";//打印出完成时间

cout<<T1<<"/n";//打印出周转时间

Current = Current->link;

}

else

{

T0=Current->ServerTime+T0;

       T1=T0-Current->arriveTime;//周转时间等于,完成时间 - 到达时间

cout<<Current->name<<"/t";//打印出进程名

cout<<T0<<"/t";//打印出完成时间

cout<<T1<<"/n";//打印出周转时间

Current = Current->link;

}

}

 

}

void CProcess::SJF()//短进程(作业)优先

{

//首先执行第一个到达的作业

    Node *Current;

int T0=0;//完成时间

int T1=0;//周转时间

    T0=first->link->ServerTime+T0;

T1=T0-first->link->arriveTime;

cout<<first->link->name<<"/t";

    cout<<T0<<"/t";//打印出完成时间

cout<<T1<<"/n";//打印出周转时间

first->link=first->link->link;//删除

//执行剩下的

    sort();//对剩下的排序

Current = first->link;//头节点赋给当前节点

while(Current!=NULL)

{   

if(T0 < Current->arriveTime)

{

            T0=Current->arriveTime+Current->ServerTime;

T1=T0-Current->arriveTime;

cout<<Current->name<<"/t";//打印出进程名

cout<<T0<<"/t";//打印出完成时间

cout<<T1<<"/n";//打印出周转时间

Current = Current->link;

}

else

{

T0=Current->ServerTime+T0;

       T1=T0-Current->arriveTime;//周转时间等于,完成时间 - 到达时间

cout<<Current->name<<"/t";//打印出进程名

cout<<T0<<"/t";//打印出完成时间

cout<<T1<<"/n";//打印出周转时间

 

Current = Current->link;

}

}

}

void CProcess::RR(int& q)//时间片轮转

{

    cout<<"时间片轮转操作完成!/n";

}

void CProcess::priority()//优先权调度

{

 

    cout<<"优先权操作完成!/n";

}

void main()

{

CProcess p0,p1,p2,p3,p4;

int at,st;

string na;

int judge=1;//控制退出程序

int choice;//控制选择操作

while(judge)

{

        cout<<"********************************************************/n";

cout<<"******     说明:本程序适用于单道进程(作业)     ******/n";

cout<<"********          请选择您的操作         ***************/n";

        cout<<"*********输入相应的数字,按下(Enter)键!**************/n";

cout<<"*************     5.录入信息                ************/n";

cout<<"*************     1.先到先服务              ************/n";

cout<<"*************     2.短进程(作业)优先      ************/n";

cout<<"*************     3.时间片轮转              ************/n";

cout<<"*************     4.优先权(静态)调度        ************/n";

cout<<"*************     0.退出程序                ************/n";

cout<<"********************************************************/n";

cin>>choice;

switch(choice)

{

case 0:

judge=0;

break;

case 5:

            cout<<"请输入信息以“end”结束输入!/n";

cout<<"进程名 到达时间 服务时间"<<endl;

while(na.compare("end"))//如果相等则会返回0

{   

p0.insertNode(na,at,st);

cin>>na>>at>>st;

}

cout<<"录入成功,目前的信息为:/n";

cout<<"进程名 到达时间 服务时间"<<endl;

p0.print();

break;

case 1://先到先服务

    p1=p0;//拷贝一份

if(p1.isEmpty())

{

     cout<<"请先录入信息/n";

 break;

}

else

{

cout<<"先到先服务/n";

cout<<"进程名 完成时间 周转时间/n";

p1.FCFS();

break;

}

case 2://短作业优先

p2=p0;//拷贝一份

//p2.sort();

    //p2.print();

if(p2.isEmpty())

{

cout<<"请先录入信息/n";

break;

}

else

{

cout<<"短作业优先/n";

cout<<"进程名 完成时间 周转时间/n";

p2.SJF();

break;

}

case 3://时间片轮转

p3=p0;//拷贝一份

int q;

if(p3.isEmpty())

{

cout<<"请先录入信息/n";

break;

}

else

{

cout<<"请输入时间片大小";

     cin>>q;

cout<<"时间片轮转/n";

                cout<<"进程名 完成时间 周转时间/n";

p3.RR(q);

                break;

}

case 4://优先权

p4=p0;//拷贝一份

if(p4.isEmpty())

{

cout<<"请先录入信息/n";

break;

}

else

{

cout<<"时间片轮转/n";

                cout<<"进程名 完成时间 周转时间/n";

p4.priority();

                break;

}

default:

cout<<"请选择目录中的选项!/n";

break;

}

}

return;

}

void CProcess::priority()//优先权调度
{
        int T0=0;//完成时间
        int T1=0;//周转时间
        Node *Current;
    int pr;
        Node *p;
        p=first->link;
        print();
        cout<<"请依次输入各个进程的优先级(按照上面的打印顺序):/n";
        cout<<"        注:数字越小,优先级越高        /n";
        while(p!=NULL)
        {//存储优先级
                cin>>pr;
                p->priority=pr;
                //cout<<p->name<<"  "<<p->priority<<endl;
                p=p->link;
        }
        /////////////////////////////////////////////////////////////////////////////////////////////////
        //首先判断是否是同时到达,如果是,则
        if(equalAll())
        {//同时到达的情况
                sort_bypr();//按照优先级由高到低排序
                Current = first->link;//头节点赋给当前节点
                cout<<"进程名 完成时间 周转时间 优先级/n";
                while(Current!=NULL)
                {   
                        
                        T0=T0+Current->ServerTime;
                        T1=T0-Current->arriveTime;
            cout<<Current->name<<"/t";//打印出进程名
                        cout<<T0<<"/t";//打印出完成时间
                        cout<<T1<<"/t";//打印出周转时间
                        cout<<Current->priority<<"/n";//打印出优先级
                        Current = Current->link;
                        
                }
                return;
        }
        ////////////////////////////////////////////////////////////////////////////////////////////
        //首先执行最早到达的进程
        T0=first->link->ServerTime+T0;
        T1=T0-first->link->arriveTime;
        cout<<"进程名 完成时间 周转时间 优先级/n";
        cout<<first->link->name<<"/t";
    cout<<T0<<"/t";//打印出完成时间
        cout<<T1<<"/t";//打印出周转时间
        cout<<first->link->priority<<"/n";//打印出优先级
        first->link=first->link->link;//删除
    sort_bypr();//按照优先级由高到低排序
        /////////////////////////////////////////////////////////////////////////////////
        //执行剩下的
        Current=first->link;
    while(Current!=NULL)
        {   
                if(T0 < Current->arriveTime)
                {
            T0=Current->arriveTime+Current->ServerTime;
                        T1=T0-Current->arriveTime;
                        cout<<Current->name<<"/t";//打印出进程名
                        cout<<T0<<"/t";//打印出完成时间
                        cout<<T1<<"/t";//打印出周转时间
                        cout<<Current->priority<<"/n";//打印出优先级
                        Current = Current->link;
                }
                else
                {
                        T0=Current->ServerTime+T0;
                        T1=T0-Current->arriveTime;//周转时间等于,完成时间 - 到达时间
                        cout<<Current->name<<"/t";//打印出进程名
                        cout<<T0<<"/t";//打印出完成时间
                        cout<<T1<<"/t";//打印出周转时间
                        cout<<Current->priority<<"/n";//打印出优先级
                        Current = Current->link;
                }
        }
        
        
    
}

只是部分,未写完!

有时间再写啦!

望指正!

帮忙补全一下!感激不尽!