【实验名称】进程调度模拟实验                     

 

【实验目的】

1. 掌握进程控制块的作用和实现技术；

2. 熟悉操作系统的进程调度算法及实现方法。

 

【实验原理】

进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法。每个进程有一个进程控制块（PCB）表示。进程控制块可以包含：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程、状态等等。

进程的优先数及需要的运行时间可以事先人为地指定。进程的到达时间为进程输入的时间。进程的运行时间以时间片为单位进行计算。每个进程的状态可以是就绪 W（Wait ）、运行R（Run）、或完成F（Finish ）三种状态之一。

 

【实验内容】

实验内容：用高级语言编写和调试一个 N个进程共行的进程调度程序。 进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法。

 

代码：

#include <iostream>
using namespace std;

//进程类
class pcb
{
public:
	//构造函数
	pcb(char Name[20], int Rank, int Needtime)
	{
		strcpy(name, Name);
		state = 'W';
		rank = Rank;
		needtime = Needtime;
		runtime = 0;
		next = NULL;
	}
	char name[20];
	char state;
	int rank;
	int needtime;
	int runtime;
	pcb* next;
};
pcb *ready = NULL, *now = NULL;

//输出进程
void output(pcb *point)
{
	cout << ".................................................";
	cout << "\n name \t state \t rank \t needtime \t runtime" << endl;
	cout << "|" << point->name << "\t";
	cout << "|" << point->state << "\t";
	cout << "|" << point->rank << "\t";
	cout << "|" << point->needtime << "\t\t";
	cout << "|" << point->runtime << "\t" << endl;
	cout << "................................................." << endl;
}

//进程依次排序
void sort(pcb *point)
{
	if (ready == NULL)//若链表为空
	{
		ready = point;
	}
	else
	{
		pcb *point1 = ready, *point2 = ready->next;
		if (point->rank > point1->rank)//若为优先等级最高，放在队首
		{
			point->next = ready;
			ready = point;
		}
		else
		{
			while (point2 != NULL)//遍历链表，直到找到合适位置
			{
				if (point->rank > point2->rank)
				{
					point1->next = point;
					point->next = point2;
					break;
				}
				point1 = point2;
				point2 = point2->next;
			}
			if (point2 == NULL)//若为优先等级最低，放在队尾
			{
				point1->next = point;
			}
		}
	}
}

//进程结束函数，打印已完成进程，释放内存
void finish(pcb *point)
{
	point->state = 'F';
	cout << "################################################" << endl;
	cout << "**************** 进程" << point->name << "已经完成 *****************" << endl;
	cout << "\n name \t state \t rank \t needtime \t runtime" << endl;
	cout << "|" << point->name << "\t";
	cout << "|" << point->state << "\t";
	cout << "|" << point->rank << "\t";
	cout << "|" << point->needtime << "\t\t";
	cout << "|" << point->runtime << "\t" << endl;
	cout << "################################################" << endl;
	delete(point);
	point = NULL;
}

//运行一个单位时间
void running()
{
	now = ready;
	ready = ready->next;
	now->next = NULL;
	now->state = 'R';
	now->rank--;
	now->runtime++;
	
	if (now->needtime == now->runtime)
	{
		//若当前进程执行完毕
		finish(now);
		now = NULL;
	}
	else
	{
		//若当前进程没有执行完毕
		cout << "************* 当前正在运行的进程是 **************" << endl;
		output(now);
	}
	//打印就绪队列
	cout << "************* 当前就绪队列状态为 ***************" << endl;
	pcb *point = ready;
	while (point != NULL)
	{
		output(point);
		point = point->next;
	}
	//把没执行完的进程重新放入队列
	if (now != NULL)
	{
		now->state = 'W';
		sort(now);
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	int t;
	cout<<"**** 输入进程数目：";
	cin >> t;
	cout << endl;
	//进程信息输入
	for (int i = 1; i <= t; i++)
	{
		pcb *temp;
		char name[20];int rank;int needtime;
		cout << "**** 请输入第" << i << "个进程的信息 ****" << endl;
		cout << "请输入该进程的名字：";
		cin >> name;
		cout << "请输入该进程的优先等级:";
		cin >> rank;
		cout << "请输入该进程需要的运行时间:";
		cin >> needtime;
		temp = new pcb(name, rank, needtime);
		sort(temp);
		temp = NULL;
		cout << endl;
	}

	//打印执行前的就绪队列
	cout << "************* 执行前就绪队列排序 ***************" << endl;
	pcb *point = ready;
	while (point != NULL)
	{
		output(point);
		point = point->next;
	}
	cout << "************ 程序准备正式开始执行 **************" << endl;

	//程序开始执行
	char ch;
	while (now != NULL || ready != NULL)
	{
		//一次运行一个单位时间
		cout << "\n\n 按任一键继续......" << endl;
		ch = getchar();
		running();
		cout << endl;
	}
	//所有进程完成
	cout << "\n************************************************" << endl;
	cout << "************* 所有进程均已执行完成 *************" << endl;
	cout << "************************************************\n" << endl;
	return 0;
}

 

运行结果：

 

 

 

 

 

 

从实验结果可以看出，实验成功。

 

【小结或讨论】

这里我想总结一下在C++实现时遇到的一些困难。比如在给指针开辟内存时，原先C语言结构体需要使用malloc函数给指针分配内存空间，而在C++中不能这样做。我一开始使用pcb temp(name, rank, needtime)直接对每个对象进行初始化，但是因为需要循环输入，发现这一语句会导致循环输入时异常。我仔细调试了一下，发现temp分配的地址并不会随着循环重新分配，所以新的输入数据会将旧的输入数据覆盖，我在网上找了找解决方法，最后使用pcb *temp; temp = new pcb(name, rank, needtime); 在堆内存中动态开辟空间创建对象，修改过后实验成功。

这次实验的主要难点我觉得是在调度排序算法上。这个调度排序实际上是链表排序，首先按优先级排序，若优先级相同则先来的排在前面。这里的逻辑判断顺序问题是需要着重注意的，特别要留意对队首和队尾的特殊处理上，在遍历队列时也要注意使用两个指针记录插入点的前后两个节点，毕竟这是一个单向链表。我的逻辑判断顺序是：链表是否为空；若为优先等级最高，放在队首；遍历链表，直到找到合适位置；若为优先等级最低，放在队尾。