一、实习内容
选择一个调度算法，实现处理器调度。

二、实习目的
本实习模拟在单处理器环境下的处理器调度，加深了解处理器调度的工作。

三、实习题目
设计一个按时间片轮转法实现处理器调度的程序

四、设计思想
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）通过本实验，我进一步加深了对时间片轮转法处理器调度的理解，同时也得到了将系统理论实践的机会，熟练了编程能力。