操作系统：C++实现RR（时间片轮转算法）

算法描述：

1.在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列， 每次调度时，把 CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几 ms 到 几百 ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号 来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新 的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定 的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用 户的请求。
2.当时间片没结束但此时进程结束，立即重新调度新进程，不等时间片用完

二

代码：

#include <iostream>
#include<iomanip>
#include<queue>
#include<list>
#include<algorithm>

using namespace std;

class PCB
{
public:
    int pid;
    int arrivalTime;
    int initialServeTime;
    int needTime;
    int leaveTime;

    PCB() //不会默认生成
    {
    }
    PCB(int pid,int arriveTime,int initialServeTime)
    {
        this->pid=pid;
        this->arrivalTime=arriveTime;
        this->needTime=initialServeTime;
        this->initialServeTime=initialServeTime;
        leaveTime=0;
    }
    bool operator == (const PCB &a)const
    {
        return pid==a.pid?true:false;//erase函数需要
    }
    bool operator <(const PCB &a)const
    {
        return pid<a.pid;     //list正常排序从小到大
    }
};

class RR
{
public:
    queue<PCB> processQue;
    list<PCB> allNeedList;
    list<PCB> allFinishList;
    static int TIME_SLICE;

    void prepareProcess(int pid,int arriveTime,int needTime);
    void schedule();
    void printFinishList();
    void printQueue();
};

int RR::TIME_SLICE=1;
void RR::schedule()
{
    int currentTime=0;
    bool isBusy=false;
    PCB currentProcess;
    allNeedList.sort();
    while (true)
    {

        for (list<PCB>::iterator i=allNeedList.begin(); i!=allNeedList.end();)
        {

            if(currentTime>=(*i).arrivalTime)//错误，这里用>=而不是==,进程在中间可能进不来
            {
                processQue.push(*i);   //若进程到达，加入队列
                i=allNeedList.erase(i);
            }
            else
            {
                i++;
            }
        }

        //特殊情况处理：当TIME_SLICE不为1时，处理机空闲时，进程要在时间片中间进入
        if(!isBusy&&processQue.empty()&&!allNeedList.empty()&&currentTime<allNeedList.front().arrivalTime)
        {
            currentTime=allNeedList.front().arrivalTime;
            for (list<PCB>::iterator i=allNeedList.begin(); i!=allNeedList.end();)
            {

                if(currentTime>=(*i).arrivalTime)
                {
                    processQue.push(*i);   //若进程到达，加入队列
                    i=allNeedList.erase(i);
                }
                else
                {
                    i++;
                }
            }
        }

        //进程完成或者时间片结束，更新服务时间，解除占用
        if(isBusy)
        {
            if(currentProcess.needTime>TIME_SLICE)
            {
                currentProcess.needTime-=TIME_SLICE;
                processQue.push(currentProcess);
            }
            else
            {
                currentProcess.needTime=0;//直接出列
                currentProcess.leaveTime=currentTime;
                cout<<"   进程"<<currentProcess.pid<<"已结束 ";
                cout<<"周转时间："<<currentTime-currentProcess.arrivalTime;
                cout<<"带权周转时间："<<(currentTime-currentProcess.arrivalTime)/(double)currentProcess.initialServeTime<<endl;
                allFinishList.push_back(currentProcess);
            }
            isBusy=false;
        }
        //给队首元素分配处理机

        if(!isBusy&&!processQue.empty())
        {
            currentProcess=processQue.front();
            processQue.pop();
            cout<<"进程"<<currentProcess.pid<<"在时刻"<<currentTime<<"开始占用处理机\n";
            isBusy=true;

        }
        //如果所需服务时间大于时间片，中断程序
        if(currentProcess.needTime>=TIME_SLICE)
            currentTime+=TIME_SLICE;
        //错误，如果所需服务时间小于时间片，当前进程结束，调度队列里的进程
        else{
            currentTime+=currentProcess.needTime;
        }

        //最后所有进程结束，退出
        if(allNeedList.empty()&&processQue.empty()&&!isBusy)
            break;

    }

}

void RR::prepareProcess(int pid,int arriveTime,int needTime)
{
    PCB newProcess(pid,arriveTime,needTime);
    allNeedList.push_back(newProcess);
}

void RR::printFinishList()
{
    allFinishList.sort();
    setiosflags(ios::left);
    cout<<setw(15)<<"进程"<<setw(15)<<"到达时间"<<setw(15)<<"服务时间"<<setw(15)<<"周转时间"<<setw(15)<<"带权周转时间\n";
    for (list<PCB>::iterator i=allFinishList.begin(); i!=allFinishList.end(); i++)
    {
        cout<<setw(15)<<(*i).pid<<setw(15)<<(*i).arrivalTime<<setw(15)<<(*i).initialServeTime<<setw(15)<<(*i).leaveTime-(*i).arrivalTime<<setw(15)<<((*i).leaveTime-(*i).arrivalTime)/(double)(*i).initialServeTime<<"\n";
    }
}
void RR::printQueue()
{
    while (!processQue.empty())
    {
        cout<<processQue.front().needTime<<" ";
        processQue.pop();
    }
}


int main()
{
    RR one;
    one.prepareProcess(1,1,4);
    one.prepareProcess(2,2,3);
    one.prepareProcess(3,3,4);
    one.prepareProcess(4,4,2);
    one.prepareProcess(5,5,4);
    one.prepareProcess(6,6,4);
    one.prepareProcess(7,7,2);
    one.prepareProcess(8,8,4);
    one.TIME_SLICE=6;
    one.schedule();
    one.printFinishList();
    return 0;
}

注意事项

1.程序在时间片为1的时候非常顺利
2.当时间片变为3的时候，各种错误就出来了。原因在于进程按时间片递增，当时间从0开始，但是此时最早的进程在2秒才能进，于是等到时间片用完3秒的时候才能进进程， 这是由于currentTime+=TIME_SLICE的原因。所以当第一次处理机空闲时，要立即扫描链表，找出时间最早的一个进程加入等待队列调入处理机，把时间变为到达时间。
3.逻辑理顺了就好写程序，关键在写的时候没有把特殊情况考虑进去，故后来不知道哪里错了，一直在调试程序寻找哪里错了耽误了好多时间。关键是特殊情况和执行顺序问题。
4.list在删除erase的时候，迭代器会失效，故要利用i后置++或者返回值i=
5.c++里声明一个变量即是创建一个变量在堆，new是在栈中。这与Java不太一样。