时间片轮转

时间片轮转调度算法，这种算法是将进程控制块按照进入就绪队列的先后次序排成队列。关于就绪队列的操作就是从队头摘下一个进程控制块和从队尾挂入一个进程控制块。

单处理器系统中进程控制块分成一个正在运行进程的进程控制块、就绪进程的进程控制块组织成的就绪队列和等待进程的进程控制块组成的等待队列。由于实验模拟的是进程调度，没有对等待队列的操作，所以实验中只有一个指向正在运行进程的进程控制块指针和一个就绪进程的进程控制块队列指针。

1.进程控制块PCB
           

包括如下信息：进程标识符，进程状态，进程每次申请的时间片大小，通用寄存器，程序计数器，程序状态字寄存器，下一个进程控制块的位置。

其中通用寄存器与程序状态字寄存器都设为0，程序计数器从0开始计数。

2.就绪队列

包括如下信息：整型进程控制块头位置标志，整型进程控制块尾位置标志

全局变量：就绪队列ready，进程控制块数组PCBarea[n]，空闲进程标识pfree，正在运行的进程标志。

进程创建是一个原语，因此在实验中应该用一个函数实现，进程创建的过程应该包括：

（1）申请进程控制块：进程控制块的数量是有限的，如果没有空闲进程控制块，则进程不能创建，如果申请成功才可以执行第二步；

（2）申请资源：除了进程控制块外，还需要有必要的资源才能创建进程，如果申请资源不成功，则不能创建进程，并且归还已申请的进程控制块；如果申请成功，则执行第三步，实验无法申请资源，所以模拟程序忽略了申请资源这一步；

（3）填写进程控制块：将该进程信息写入进程控制块内，实验中只有进程标识符、进程状态可以填写，每个进程现场信息中的寄存器内容由于没有具体数据而使用进程(模拟进程创建时，需输入进程标识符字，进程标识符本应系统建立，并且是惟一的，输入时注意不要冲突)，刚刚创建的进程应该为就绪态，然后转去执行第四步；

（4）挂入就绪队列：如果原来就绪队列不为空，则将该进程控制块挂入就绪队列尾部，并修改就绪队列尾部指针；如果原来就绪队列为空，则将就绪队列的头指针、尾指针均指向该进程控制块，进程创建完成。

代码

// An highlighted block
#include<iostream>
#include<string>
#include<stdlib.h>
#include<Windows.h>
#include<conio.h>
#define n 10
using namespace std;

//进程控制块
typedef struct PCB
{
	int name;//进程标识
	char zhuangtai;//进程状态
	int time;//进程每次申请的时间片大小
	int AX, BX, CX, DX;//通用寄存器
	int PC;//程序计数器
	int PSW;//程序状态字寄存器
	int next;//下一个进程控制块的位置
};

//就绪队列
struct Ready
{
	int head;//头指针
	int tail;//尾指针
};
Ready ready;
PCB PCBarea[n];
int pfree;
int y;//正在运行的进程标志

//初始化就绪队列
void chushi()
{
	y = ready.head = ready.tail = -1;
	pfree = 0;
	for (int i = 0; i<n - 1; ++i)
		PCBarea[i].next = i + 1;
	PCBarea[n - 1].next = -1;
}


//创建进程
void Create(int name, int time)
{
	//空闲进程控制块队列为空
	if (pfree == -1) {
		cout << "无空闲进程控制块" << endl;
		exit(0);
	}
	int i = pfree;
	pfree = PCBarea[pfree].next;
	PCBarea[i].name = name;
	PCBarea[i].zhuangtai = 'W';
	PCBarea[i].AX = 0;
	PCBarea[i].BX = 0;
	PCBarea[i].CX = 0;
	PCBarea[i].DX = 0;
	PCBarea[i].PC = 0;
	PCBarea[i].PSW = 0;
	PCBarea[i].time = time;
	//就绪队列不空时，置入空闲队列
	if (ready.head != -1) 
	{
		
		PCBarea[ready.tail].next = i;
		ready.tail = i;
		PCBarea[ready.tail].next = -1;
	}
	//就绪队列空时,置入就绪队列
	else {
		ready.head = i;
		ready.tail = i;
		PCBarea[ready.tail].next = -1;
	}
}

//进程调度
void diaodu(int usetime)
{
	//空闲进程控制块队列为空，退出
	if (ready.head == -1) {
		cout << "程序执行结束" << endl;
		exit(0);
	}
	y = ready.head;
	ready.head = PCBarea[ready.head].next;//就绪队列头指针后移
	//就绪队列为空
	if (ready.head == -1)
	{
		ready.tail = -1;
	}
	PCBarea[y].zhuangtai = 'R';
	PCBarea[y].AX++;
	PCBarea[y].BX++;
	PCBarea[y].CX++;
	PCBarea[y].DX++;
	PCBarea[y].PC++;
	PCBarea[y].PSW++;
	cout << "当前运行程序:" << endl;
	cout << "	进程号:"<< PCBarea[y].name << endl;
	cout << "	进程状态:"<< PCBarea[y].zhuangtai << endl;
	cout << "	寄存器AX:"<< PCBarea[y].AX<< endl;
	cout << "	寄存器BX:" << PCBarea[y].BX << endl;
	cout << "	寄存器CX:" << PCBarea[y].CX<< endl;
	cout << "	寄存器DX:" << PCBarea[y].DX<< endl;
	cout << "	PC:"<< PCBarea[y].PC << endl;
	cout << "	PSW:"<< PCBarea[y].PSW << endl;
	cout << "	时间:" << PCBarea[y].time << endl;
	system("pause");
//若进程执行完毕，则回收进程控制块
	if (PCBarea[y].time <= usetime) {
		PCBarea[y].time = 0;
		PCBarea[y].zhuangtai = 'F';
		ready.head = PCBarea[y].next;
		cout << endl<<"进程" << y+1 << "执行完毕"<<endl;
		system("pause");
		//将该进程控制块置入空闲队列
		if (pfree == -1) {
			pfree = y;
			PCBarea[pfree].next = -1;
		}
		else {
			PCBarea[pfree].next = y;
			pfree = y;
			PCBarea[y].next = -1;
		}
	}
//若进程还没执行完毕，放入就绪队列，等下次的时间片
	else {
		getchar();
		PCBarea[y].time = PCBarea[y].time-usetime;
		PCBarea[y].zhuangtai = 'W';
		if (ready.tail != -1)
			PCBarea[ready.tail].next = y;
		else
			ready.head = ready.tail = y;
		PCBarea[y].next = -1;
		ready.tail = y;
	}
	diaodu(usetime);//继续递归调度
}


int main()
{
		int name;
		int usetime;
		int time;
		int i = n;
		chushi();
		cout << "输入时间片大小" << endl;
		cin >> usetime;
		cout << "输入进程编号，输入负数结束创建" << endl;
		cin >> name;
		while (name>0) {
			cout << "输入该进程运行所需的总时间" << endl;
			cin >> time;
			Create(name, time);
			if (i>0)
				--i;
			cout << "输入进程编号，输入负数结束创建" << endl;
			cin >> name;
		}
		system("cls");
		diaodu(usetime);
	return 0;
}



           

[1] 汤小丹，梁红兵，哲凤屏，汤子瀛. 计算机操作系统. 第四版. 西安：西安电子科技大学出版社，2014. 98-111