操作系统实验(一) 进程调度算法设计(动态优先数+时间片轮转法)

模拟进程调度算法，用动态优先数及时间片轮转法实现进程调度

一、实验要求

1．内容：设计一个简单的进程调度算法，模拟OS中的进程调度过程

2．要求：

① 进程数不少于5个；
② 进程调度算法任选；最好选用动态优先数法，每运行一个时间片优先数减3；
③ 用C++（或C）语言编程；
④ 程序运行时显示进程调度过程。

3．步骤：

① 设计PCB及其数据结构：

进程标识数：ID

进程优先数：PRIORITY（优先数越大，优先级越高）

进程已占用时间片：CPUTIME

进程尚需时间片：ALLTIME（一旦运行完毕，ALLTIME为0）

进程队列指针：NEXT，用来将PCB排成队列

进程状态：STATE（一般为就绪，不用）

② 设计进程就绪队列及数据结构；

③ 设计进程调度算法，并画出程序流程图；

④ 设计输入数据和输出格式；

结构格式：当前正运行的进程：0

当前就绪队列：2，1，3，4

⑤ 编程上机，验证结果。

4．提示：

假设调度前，系统中有5个进程，其初始状态如下：

ID	0	1	2	3	4
PRIORITY	9	38	30	29	0
CPUTIME	0	0	0	0	0
ALLTIME	3	3	6	3	4
STATE	ready	ready	ready	ready	read

① 以时间片为单位调度运行；

② 每次总是从ALLTIME中不为0，且PRIORITY最大的进程调度运行一个时间片；

③ 上述进程运行后其优先数减3，再修改其CPUTIME和ALLTIME，重复②，③;

④ 直到所有进程的ALLTIME均变为0。

5.书写实验报告

① 实验题目；

② 程序中所用数据结构及说明；

③ 程序清单及描述；

④ 执行结果。

二、算法实现：

1.具体代码：

#include <iostream> 
#include <algorithm>

using namespace std;
//进程PCB结构体
typedef struct
{	
  	int id, priority, cputime, alltime, state;	//state,结束-1，就绪0，运行1 
}pcb;

pcb a[110];	//定义进程队列 
void show(int n, pcb a[])
{
	printf("----------------------------------------------\n");
  	printf("id  priority  cputime  alltime  state\n");	//alltime,进程所需时间片 
  	for(int i = 0; i < n; i ++)
    	printf("%d\t %d\t %d\t %d\t %d\n", a[i].id, a[i].priority, a[i].cputime, a[i].alltime, a[i].state);
    cout << endl;
	for(int i = 0; i < n; i ++)	
    {
    	if(a[i].state == 1)
    		cout << "当前运行的进程id号：" << a[i].id << endl;
    }
    cout << "当前的就绪进程id号：";
    for(int i = 0; i < n; i ++)	
    {
    	if(a[i].state == 0)
    		cout << a[i].id << " ";  	
	}
  	printf("\n----------------------------------------------\n\n");
} 

void prior_sort(int n, pcb a[])
{
 	for(int i = 0; i < n - 1; i ++)
    {
        for(int j = 0; j < n - 1 - i; j ++)
        {
            if( (a[j].priority <= a[j + 1].priority))
            	swap(a[j], a[j + 1]); 
        }
    }
	if(a[0].state != -1) a[0].state = 1;//设为运行态 
}

void process_scheduling(int n, int m)
{
	do{
    	if(a[0].state == 1)	//运行态1，完成一次调度
        {
        	a[0].priority -= 3;
            a[0].cputime += 1;
            a[0].alltime -= 1;
            if(a[0].alltime == 0) 
            {
				a[0].state= -1;//该进程结束(-1)
				m ++;
				swap(a[0], a[n - m]);
			}
            else a[0].state= 0;
        }
        prior_sort(n - m,a);
        show(n,a);
    }    
    while(a[0].alltime != 0);
}

int main()
{
	int n; 
	int m = 0;
	cout << "请输入进程个数：" << endl;
	cin >> n;
	cout << "请依次输入这" << n << "个进程的ID号、进程优先数、已占用时间片、需要的时间片："<< endl;//初始化进程队列 
	for(int i = 0; i < n; i ++)
	{
		cin >> a[i].id >> a[i].priority >> a[i].cputime >> a[i].alltime;
		a[i].state = 0; //进程状态（默认就绪态0）
	}
	cout << "进程队列初始状态如下：" << endl;
	show(n,a);
	prior_sort(n,a); 
	show(n,a); //进程第一次调度状况
	process_scheduling(n, m);
    return 0; 
}