一、實習內容
選擇一個調度算法，實現處理器調度。

二、實習目的
本實習模擬在單處理器環境下的處理器調度，加深了解處理器調度的工作。

三、實習題目
設計一個按時間片輪轉法實現處理器調度的程序

四、設計思想
1.設計思路
（1）假定系統有5個進程，每個進程用一個PCB來代表。PCB的結構為：
進程名——如Q1~Q5。
指針——把5個進程連成隊列，用指針指出下一個進程PCB的首地址。
要求運行時間——假設進程需要運行的單位時間數。
已運行時間——進程已運行的單位時間數，初始值為0。
狀態——假設兩種狀態，就緒和結束，用R表示就緒，用E表示結束。初始狀態都為就緒狀態。
（2）每次運行之前，為每個進程任意確定它的“要求運行時間”。
（3）把5個進程按順序排成循環隊列，用指針指出隊列連接情況。用一個標誌單元記錄輪到運行的進程。處理器調度總是選擇標誌單元指示的進程運行，對所指的進程，將其“已運行時間”加1。
（4）進程運行一次後，若“要求運行時間”等於“已運行時間”，則將狀態改為“結束”，退出隊列，否則將繼續輪轉。
（5）若就緒隊列為空，結束，否則轉到（3）重複。


2.主要數據結構

1
2
3
4
5
6
7
8
9

typedef struct program
{
	char name[10];            //進程名
	struct program *next;    //進程雙鏈表後繼指針
	struct program *front;    //進程雙鏈表前驅指針
	int needtime;            //要求運行時間
	int donetime;            //已運行時間
	char state;                //進程狀態，R表示就緒，E表示結束
};

3.主要代碼結構及代碼段分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

//創建進程鏈表
int CreatProg()
{
	int i;
	struct program prog[5];
input:	for(i=0;i<5;i++)
	{
		printf("第%d個進程的進程名(不多於10字符)：",i);
		scanf("%10s",&prog[i].name);
		printf("第%d個進程所需要運行的時間：",i);
		scanf("%d",&prog[i].needtime);
		if(i != 4)
			prog[i].next = &prog[i+1];
		else
			prog[4].next = &prog[0];
		if(i != 0)
			prog[i].front = &prog[i-1];
		else
			prog[0].front = &prog[4];
		prog[i].donetime = 0;
		prog[i].state = 'R';
	}
	printf("\n有如下進程等待處理機調度：\n");
	printf("	進程名	需時	已運行	狀態\n");
	for(i=0;i<5;i++)
		printf("%10s	%d	%d	%c\n",prog[i].name,prog[i].needtime,prog[i].donetime,prog[i].state);
	printf("\n確定嗎？確定將開始執行進程調度，否則重新輸入：(Y/N)");
	char c;
	do
	{
		scanf("%c",&c);
		if(c=='y' || c=='Y' || c=='N' || c=='n')
			break;
	}while(1);
	if(c=='N' || c=='n')
		goto input;
	else if(c=='Y'||c=='y')
		execute(prog);
}
 
//開始處理器調度
int execute(struct program prog[])
{
	struct program *Runit;
	int i = 0,k = 0;
	Runit = &prog[0];
	while(Runit->next != Runit)
	{
		{
			Runit->donetime++;
			if(Runit->donetime == Runit->needtime)
			{//將狀態標誌改為E結束，並將該進程從鏈表中刪除
				Runit->state = 'E';
				Runit->front->next = Runit->next;
				Runit->next->front = Runit->front;
			}
			printf("第%d個時間片：%s在運行\n",i,Runit->name);
		       	printf("	進程名	需時	已運行	狀態\n");
			for(k=0;k<5;k++)
				printf("%10s	%d	%d	%c\n",prog[k].name,prog[k].needtime,prog[k].donetime,prog[k].state);
			printf("-------------------------------------------------\n");
			Runit = Runit->next;
		}
		i++;
	}
	//只剩下一個進程了
	int t = Runit->needtime - Runit->donetime;
	for(;t!=0;t--)
	{
		Runit->donetime++;
		if(Runit->donetime == Runit->needtime)
			Runit->state = 'E';
		printf("第%d個時間片：%s在運行\n",i,Runit->name);
		printf("        進程名  需時    已運行  狀態\n");
		for(k=0;k<5;k++)
			printf("%10s    %d      %d      %c\n",prog[k].name,prog[k].needtime,prog[k].donetime,prog[k].state);
		printf("-------------------------------------------------\n");
		i++;
	}
}

五、上機實習所用平台及相關軟件
本程序在Linux平台（Ubuntu8.04.1）下，使用vi編輯器編寫，g++編譯通過。

六、總結
（1）在處理器調度的過程中，最後一個未運行結束的進程需要特殊處理。因為在只剩下一個進程時，鏈表中也只有一個節點了，就不能再進入後繼節點循環。所以在判斷只剩下一個節點時設置了一個單獨的循環體。
（2）我使用了雙鏈表的數據結構，因為這樣可以很方便地訪問到前驅節點，更容易進行鏈表節點的刪除操作，節省了很多時間。
（3）通過本實驗，我進一步加深了對時間片輪轉法處理器調度的理解，同時也得到了將系統理論實踐的機會，熟練了編程能力。