時間片輪轉

時間片輪轉排程算法，這種算法是将程序控制塊按照進入就緒隊列的先後次序排成隊列。關于就緒隊列的操作就是從隊頭摘下一個程序控制塊和從隊尾挂入一個程序控制塊。

單處理器系統中程序控制塊分成一個正在運作程序的程序控制塊、就緒程序的程序控制塊組織成的就緒隊列和等待程序的程序控制塊組成的等待隊列。由于實驗模拟的是程序排程，沒有對等待隊列的操作，是以實驗中隻有一個指向正在運作程序的程序控制塊指針和一個就緒程序的程序控制塊隊列指針。

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