时间片轮转问题

先上代码



#include <iostream>
#include <string>
#include <iomanip>
using namespace std;
 
struct PCBNode
 {
         string name; 
    float runTime;      //总的需要运行时间 
    float remainTime;   //剩下需要运行时间 
    float arriveTime;   //进入就绪队列时间 
    float startTime;    //开始运行时间 
    float finishTime;   //结束运行时间 
    float totalTime;    //周转时间 
    float weightTotalTime;  //带权周转时间
         PCBNode * next;
 };
 
struct LinkQueue  //队列定义
 {
         PCBNode * front; //队头指针
         PCBNode * rear;  //队尾指针
 };
 
//队列初始化
 void InitialQueue(LinkQueue& q);
 //输入PCBNode
 void Input(PCBNode* p);
 //队列构造
 void CreateQueue(LinkQueue& q, int n);


 //时间片轮转算法
 void RoundRobin(LinkQueue& q, int n);
//打印队列
 void PrintQueue(LinkQueue& q);
 
int main()
 {
int i = 1;
         while (i)
         {
                 
                         LinkQueue queue;
                         InitialQueue(queue);
                         
                        int num = 0;
                         cout << "输入进程个数" << endl;
                         cin >>num;
                         CreateQueue(queue, num);
                         RoundRobin(queue, num);
                         PrintQueue(queue);
                
                
                 cout << endl;
                 cout << "继续请输入1,退出请输入0" <<endl;
                 cin >>i;
         }
         



        return 0;
         
 }
 
//队列初始化
 void InitialQueue(LinkQueue& q)
 {
         q.front = NULL;
         q.rear = NULL;
 }
 //输入PCB进程控制块的信息
 void Input(PCBNode*p)
 {
         //需要用户输入的信息
         cout << "输入进程名称" <<endl;
         cin >> p->name;
         cout << "输入到达时间" << endl;
         cin >> p->arriveTime;
     cout << "输入运行时间" << endl;
         cin >> p->runTime;
         //自动初始化的信息
         p->startTime = 0;  //开始时间
         p->finishTime = 0;  //完成时间
         p->remainTime = p->runTime;  //还需要时间
         p->totalTime = 0;   //周转时间
         p->weightTotalTime = 0;   //带权周转时间
         p->next = NULL;
 
}
 //创建队列
 void CreateQueue(LinkQueue& q, int n)
 {
         for (int i=0; i<n; i++)
         {
                 PCBNode *pcb=new PCBNode;
                 Input(pcb);
                 if (q.front == NULL)
                 {
                         PCBNode * temp = new PCBNode;
                         temp = pcb;
                         q.front = q.rear = temp;
                    
                 }
                 else
                 {
                         //此处必须新建一个PCBNode，否则连不上队列
                         PCBNode * temp = new PCBNode;
                         temp = pcb;
                         q.rear->next = temp;
                         q.rear = temp;
                         
                 }
         }
 q.rear->next = NULL;
 }

 //时间片轮转法，时间片为1
 void RoundRobin(LinkQueue& q, int n)
 {      
         
         LinkQueue p;
 PCBNode*temp1=q.front;

 int flag=1;
 int time=q.front->arriveTime;
 p.front=p.rear=temp1;
 PCBNode*temp2=p.front;
 p.rear->next=NULL;
while(temp2){
     cout<<temp2->name;
   temp2=temp2->next;
}
temp1=q.front;
while(temp1){
     cout<<temp1->name;
 temp1=temp1->next;
}
 /* while (flag)
         {
                 PCBNode * current = p.front;
                 //如果当前进程还需要时间运行
                 if (current->arriveTime <= time && current->remainTime != 0)
                 { 
                         //第一次占有CPU
                         if (current->remainTime == current->runTime)
                         {
                                 //执行1次修改进程相应信息
                                 current->startTime = time;
                                 if (current->remainTime <= 1)
                                 {
                                         time += current->remainTime;
                                         current->remainTime = 0;
                                         current->finishTime = time;
                                 }
                                 else
                                 {
                                         time++;
                                         current->remainTime--;
                                 }
                                 //将执行过的进程插到队尾
                                 PCBNode * temp = p.front;


 if(temp->next==NULL){
 cout << current->name<<"************"<<endl;
 cout<<temp1->name<<"&&&&"<<endl;
       p.front=temp1;  
   current=p.front;
   current->next=temp;
   temp->next=NULL;PrintQueue(p);
   p.rear=temp;

  
   temp1=temp1->next;
                                      
   
 }
 
                                 else{
 while (temp->next != NULL)
 {
                                         temp = temp->next;
 }
 
                                cout << current->name;
                                cout<<"****************";
                                p.front = current->next;
                                 temp->next = current;
                                 current->next = NULL;
                                 p.rear = current;
 PrintQueue(p);
                                 


 temp->next=temp1;
 temp1->next=current;
 temp1=temp1->next;
 }

                                 
                         }
                         //第N次占有CPU
                         else
                         {
                                 if (current->remainTime <= 1)
                                 {
                                         time += current->remainTime;
                                         current->remainTime = 0;
                                         current->finishTime = time;
                                 }
                                 else
                                 {
                                         time++;
                                         current->remainTime--;
                                 }
                                 //将执行过的进程插到队尾
                                 
                                 PCBNode * temp = p.front; 
 
                                 while (temp->next != NULL)
                                 {
                                         temp = temp->next;
                                 }
 
                                cout << current->name;
                                p.front = current->next;
                                 temp->next = current;
                                 current->next = NULL;
                                p.rear=current;
 
                         }
                 }
            
else
                 {
                         //将执行过的进程插到队尾
                         PCBNode * temp = p.front;
                         while (temp->next != NULL)
                         {
                                 temp = temp->next;
                         }
 
                        p.front = current->next;
                         temp->next = current;
                         current->next = NULL;
                         p.rear = current;
 
                }
 
PCBNode * m = p.front;
cout<<"%%"<<m->next->name<<endl;;
                 while (m != NULL)
                 {       
                         if(m->remainTime != 0)
                         {
                                 flag = 1;
                                 break;
                         }
                         else
                         {
                                 flag = 0;
                         }
                         m = m->next;
                 }
         //while循环结束
 
         }
 
        //周转时间，带权周转时间
/* q=p;
         PCBNode * current = q.front;
         while (current != NULL)
         {
                 current->totalTime = current->finishTime - current->arriveTime;
                 current->weightTotalTime = (current->finishTime - current->arriveTime) / current->runTime;
                 current = current->next;
         }*/
      
 }
         
 
 
      

         
void PrintQueue(LinkQueue& q)
 {
         PCBNode * current = q.front;
         double total = 0;
         double weightTotal = 0;
         int i = 0;
         cout << endl;
         cout << "运行结果如下：" <<endl;
         while (current != NULL)
         {
                 cout << "进程名称  " << "到达时间  " << "开始时间  " << "运行时间  " 
                        <<"结束时间  " << "周转时间  " << "带权周转时间" <<endl;
                 cout << setiosflags(ios::left);
                 cout << setw(13) << current->name << setw(10) << current->arriveTime << setw(10) 
                        << current->startTime << setw(10) << current->runTime << setw(10) << current->finishTime
                         << setw(10) << current->totalTime << setw(14) << current->weightTotalTime << endl;
                 total += current->totalTime;
                 weightTotal += current->weightTotalTime;
                 i++;
                 current = current->next;
         }
         cout << "平均周转时间：" << total/i <<endl;
         cout << "平均带权周转时间：" << weightTotal/i <<endl;
 }
 

5 个解决方案

#1

我想达到的效果是
进程名 a b c d e
到达时间 0 1 2 4 5
服务时间 4 3 5 2 4
完成时间 12 10 18 11 17
周转时间 12 9 16 8 13
带权周转 3 3 3.2 4 3.25

#2

而不是出现下面链接出现的结果http://imgsrc.baidu.com/forum/pic/item/4b5e4bfbfbedab649e941131f736afc378311e2a.jpg

#3

我实验的原理是
就比如说有5个作业等待完成a，b,c,d,e,按先来先服务的顺序。首先将a，b，c，d，e依次加入到队伍，因此队列变化为 
1. a
2、b，a
3、a,c,b
4、c,b,d,a
5、b,d,a,e,c
之后按照5的顺序循环作业，直至完成

#4

自己调试，衣食无忧。
#include <iostream>
#include <string>
#include <iomanip>
using namespace std;
 
struct PCBNode
 {
         string name;
     
    float runTime;      //总的需要运行时间 
    float remainTime;   //剩下需要运行时间 
    float arriveTime;   //进入就绪队列时间 
    float startTime;    //开始运行时间 
    float finishTime;   //结束运行时间 
    float totalTime;    //周转时间 
    float weightTotalTime;  //带权周转时间
         PCBNode * next;
 };
 
struct LinkQueue  //队列定义
 {
         PCBNode * front; //队头指针
         PCBNode * rear;  //队尾指针
 };
 
//
 void InitialQueue(LinkQueue& q);
 //输入PCBNode
 void Input(PCBNode*p);
 //队列构造
 void CreateQueue(LinkQueue& q, int n);
 PCBNode*DeQueue(LinkQueue&p);
//队列出队
void insertTail(LinkQueue&p,PCBNode*item);

 bool Empty(LinkQueue &q);

 
 //时间片轮转算法
 void RoundRobin(LinkQueue& q, int n,int rr);
 
//打印队列
 void PrintQueue(LinkQueue& q);
 
int main()
 {
                   
         int flag = 1;
 

         while (flag)

 {      
 LinkQueue queue;
         InitialQueue(queue);
 
         int num = 0;
 int rr;
         cout << "输入进程个数" << endl;
         cin >>num;
         CreateQueue(queue, num);
 
       
  cout<<"请输入时间片rr=  ";
cin>>rr;
 
                       
                        
                         RoundRobin(queue, num,rr);
                         PrintQueue(queue);
            
                 cout << endl;
                 cout << "继续请输入1,退出请输入0" <<endl;
                 cin >>flag;
         }
         



        return 0;
 }
 //队列初始化
 void InitialQueue(LinkQueue& q)
 {
         q.front = NULL;
         q.rear = NULL;
 }
 //输入PCB进程控制块的信息
 void Input(PCBNode* p)
 {
         //需要用户输入的信息
         cout << "输入进程名称" <<endl;
         cin >> p->name;
         cout << "输入到达时间" << endl;
         cin >> p->arriveTime;
     cout << "输入运行时间" << endl;
         cin >> p->runTime;
     
         //自动初始化的信息
         p->startTime = 0;  //开始时间
         p->finishTime = 0;  //完成时间
         p->remainTime = p->runTime;  //还需要时间
         p->totalTime = 0;   //周转时间
         p->weightTotalTime = 0;   //带权周转时间
         p->next = NULL;
 
}
 //创建队列
 void CreateQueue(LinkQueue& q, int n)
 {     
         for (int i=0; i<n; i++)
         {
                 PCBNode *pcb=new PCBNode;
                 Input(pcb);
                 if (q.front == NULL)
                 {
                         PCBNode * temp = new PCBNode;
                         temp = pcb;
                         q.front = q.rear = temp;
                        
                 }
                 else
                 {
                         //此处必须新建一个PCBNode，否则连不上队列
                         PCBNode * temp = new PCBNode;
                         temp =pcb;
                         q.rear->next = temp;
                         q.rear =temp;
                         
                 }
         }
 q.rear->next = NULL;
 }
 

#5

PCBNode*DeQueue(LinkQueue&p){
    PCBNode*temp=p.front;
        p.front=p.front->next;
return temp;
 }
 void insertTail(LinkQueue&p,PCBNode*item){
        PCBNode*temp=p.front;
while(temp->next!=NULL){
     temp=temp->next;
}
temp->next=item;
item->next=NULL;

p.rear=temp;
 }
 bool Empty(LinkQueue &q){
        if(q.front==NULL)   return 0;
return 1;
 }

 //时间片轮转法
 void RoundRobin(LinkQueue& p, int n,int rr)
 {       LinkQueue q;
         PCBNode*DeTemp=DeQueue(p);
 DeTemp->next=NULL;
 q.front=q.rear=DeTemp;
 //insertTail(q,DeQueue(p));
     //PrintQueue( q);
     //PrintQueue( p);
         float time = q.front->arriveTime;  //时间，初值为第一个节点到达时间
         int flag = 1;  //循环标志，为1则循环
 int RemainRR=0;//上一个时间片所残留的时间
         cout << "运行顺序：";
         while (flag)
         {
                 PCBNode * current = q.front;
                 //如果当前进程还需要时间运行
                 if (current->arriveTime <= time && current->remainTime != 0)
                 {
                         //第一次占有CPU
                         if (current->remainTime == current->runTime)
                         {
                                 //执行1次修改进程相应信息
                                 current->startTime = time;
                                if(RemainRR)
{
if (current->remainTime <= rr+RemainRR)
{
                                        RemainRR=rr-current->remainTime;
                                         time += current->remainTime;
                                         current->remainTime = 0;
                                         current->finishTime = time;
 
}
                                   else
   {      
 
 
                                         time=time+1+RemainRR;
                                         current->remainTime=current->remainTime-rr-RemainRR;
 
 
 }
                                 }
else
{
       if (current->remainTime <= rr)
{
                                        RemainRR=rr-current->remainTime;
                                         time += current->remainTime;
                                         current->remainTime = 0;
                                         current->finishTime = time;
 
}
                                   else
   {      
 
 
                                         time=time+rr;
                                         current->remainTime=current->remainTime-rr;
 
 
 }
}
                                 //将执行过的进程插到队尾
                                 //将执行过的进程插到队尾
 cout << current->name;
                                 PCBNode * temp = q.front;
                                 
 if(Empty(p)){
      PCBNode*DeTemp=DeQueue(p);
  insertTail(q,DeTemp);
 }
                                q.front=q.front->next;                                
                                insertTail(q,temp);
// PrintQueue( q);
                                
                         }
                         //第N次占有CPU
                         else
                         {       if(RemainRR)
{
if (current->remainTime <= rr+RemainRR)
{
                                        RemainRR=rr-current->remainTime;
                                         time += current->remainTime;
                                         current->remainTime = 0;
                                         current->finishTime = time;
 
}
                                   else
   {      
 
 
                                         time=time+rr+RemainRR;
                                         current->remainTime=current->remainTime-rr-RemainRR;
 
 
 }
                                 }
else
{
       if (current->remainTime <= rr)
{
                                        RemainRR=rr-current->remainTime;
                                         time += current->remainTime;
                                         current->remainTime = 0;
                                         current->finishTime = time;
 
}
                                   else
   {      
 
 
                                         time=time+rr;
                                         current->remainTime=current->remainTime-rr;
 
 
 }
}
                                  cout<<current->name;
  PCBNode * temp = q.front;
                                 q.front=q.front->next;
                                 
                                if(Empty(p)){
      PCBNode*DeTemp=DeQueue(p);
  insertTail(q,DeTemp);
 }
                                insertTail(q,temp);
//PrintQueue( q);
                         }
                 }
                 //执行一次，时间至少加1
                 else
                 {
                         //将执行过的进程插到队尾
                         PCBNode * temp = q.front;
                          
                                 q.front=q.front->next;
 
                                
                                insertTail(q,temp);
//PrintQueue( q);
 
                }
 
                //检查是否全部运行完了
                 PCBNode * m = q.front;
                 while (m != NULL)
                 {
                         if(m->remainTime != 0)
                         {
                                 flag = 1;
                                 break;
                         }
                         else
                         {
                                 flag = 0;
                         }
                         m = m->next;
                 }
         //while循环结束
         }
 
        //周转时间，带权周转时间
         PCBNode * current = q.front;
         while (current != NULL)
         {
                 current->totalTime = current->finishTime - current->arriveTime;
                 current->weightTotalTime = (current->finishTime - current->arriveTime) / current->runTime;
                 current = current->next;
         }
                 
        p=q;
}
 
void PrintQueue(LinkQueue& q)
 {
         PCBNode * current = q.front;
         double total = 0;
         double weightTotal = 0;
         int i = 0;
         cout << endl;
         cout << "运行结果如下：" <<endl;
         while (current != NULL)
         {
                 cout << "进程名称  " << "到达时间  " << "开始时间  " << "运行时间  " <<"剩余时间  "
                        <<"结束时间  " << "周转时间  " << "带权周转时间" <<endl;
                 cout << setiosflags(ios::left);
                 cout << setw(13) << current->name << setw(10) << current->arriveTime << setw(10) 
                        << current->startTime << setw(10)<<current->remainTime<<setw(10) << current->runTime << setw(10) << current->finishTime
                         << setw(10) << current->totalTime << setw(14) << current->weightTotalTime << endl;
                 total += current->totalTime;
                 weightTotal += current->weightTotalTime;
                 i++;
                 current = current->next;
         }
         cout << "平均周转时间：" << total/i <<endl;
         cout << "平均带权周转时间：" << weightTotal/i <<endl;
 }