多级调度.cpp

操作系统实验 实验一 进程调度 实验二 作业调度 实验三(综合性) 主存空间的分配与回收 实验四 文件系统

#include <iostream>
#include <conio.h>
#define getpch(type) (type *)malloc(sizeof(type))
#define NULL 0

using namespace std;

const int que_num = 5;		//就绪队列数

struct pcb{		//进程控制块
	char name[10];			
	char state;				//状态：就绪(w)、运行(r)、完成()
//	int super;				//优先级			
	int ntime;				//需要运行时间
	int rtime;				//已运行时间
	struct pcb *link;
}*p;				//ready为就绪队列队首，p为当前运行进程

typedef struct pcb PCB;

struct que{		//就绪队列
	PCB * top, * tail;		//队首指针、队尾指针
	int rtime;				//队列每次运行的时间片
}ready[que_num];

const int tt[que_num] = {1, 2, 4, 8, 16};		//初始化队列时间片用
int allpcb;					//总进程个数

//初始化
void init()	
{
	int k;
	for(k = 0; k < que_num; k++){
		ready[k].top = ready[k].tail = NULL;
		ready[k].rtime = tt[k];
	}
	allpcb = 0;
}


//向第k个队列插入p进程
void insert(int k)
{
	if(ready[k].top == NULL){	
		ready[k].top = p;
		ready[k].tail = p;
	}
	else {
		ready[k].tail->link = p;
		ready[k].tail = p;
	}
}

//将p进程插入到k的下一个队列中，
//如果k队列队列没有下一个队列，则插入到它本身
void insert2(int k)
{
	p->state = 'w';
	if(k == que_num)
		insert(k);
	else
		insert(k+1);
}


//建立进程控制块
void input()						
{
	int i, num;
	system("cls");
	printf("\n 请输入进程数？");
	scanf("%d", &num);
	for(i = 0; i < num; i++){
		printf("\n 进程号 No.%d:\n", ++allpcb);
		p = getpch(PCB);
		printf("\n 输入进程名:");
		scanf("%s", p->name);
//		printf("\n 输入进程优先数:");
//		scanf("%d", &p->super);
		printf("%n 输入进程运行时间:");
		scanf("%d", &p->ntime);
		printf("\n");
		p->rtime = 0;
		p->state = 'w';
		p->link = NULL;
		insert(0);
	}
	char ch = getchar();
	return ;
}


//计算进程数
int space(int k)
{
	int l = 0; 
	PCB * pr = ready[k].top;
	while(pr != NULL){
		l++;
		pr = pr->link;
	}
	return l;
}


//显示传入pr进程
void disp(PCB *pr)
{
	printf("\n qname \t state \t ndtime  runtime \n");
	printf("|%s\t", pr->name);
	printf("|%c\t", pr->state);
//	printf("|%d\t", pr->super);
	printf("|%d\t", pr->ntime);
	printf("|%d\t", pr->rtime);
	printf("\n");
	return ;
}



//进程查看
//并将按算法得到的当前执行进程赋值给p
void look(int k)
{
	PCB * pr;
	int i;
	p = ready[k].top;
	printf("\n **** 当前正在运行第%d个队列的进程是:%s", k+1, p->name);
	for(i = 0; i < que_num; i++){
		pr = ready[i].top;
		printf("\n **** 当前第%d个就绪队列状态为:\n", i+1);
		while(pr != NULL){
			disp(pr);
			pr = pr->link;
		}
	}
	ready[k].top = p->link; 
	if(ready[k].tail == p)
		ready[k].tail = NULL;
	p->link = NULL;
	p->state = 'r';
	return ;
}

//查看当前运行进程
void look2(int k, int rtime)
{
	printf("\n **** 当前正在运行第%d个队列的进程是:%s\n", k+1, p->name);
	printf("已运行了%d个时间片\n", rtime);
	disp(p);
}


//撤销进程
void destroy()
{
	printf("\n 进程 [%s] 已完成。\n", p->name);
	free(p);
	return;
}

//检查由前向后有多少队列为空
int check()
{
	int k = 0;
	while(ready[k].top == NULL){
		k++;
	}
	return k;
}


//运行p进程
//如果进程运行完成，返回1；否则，返回0；
int running()
{
	p->rtime ++;
	if(p->rtime == p->ntime){
		destroy();
		return 1;
	}
	else {
		return  0;
	}
}

//输出被剥夺信息
void grab(int k2)
{
	PCB * pr = ready[k2].top;
	printf("\n 进程 [%s] 被第%d个队列的 [%s] 抢占。\n", p->name, k2+1, pr->name);
}


int main()
{	
	int k, k2;
	int rtime, in_flag;
	char ch;
	PCB *tmp;
	init();
	input();
	k = check();      //检查有多少队列为空
	while(k < que_num){                 //小于反馈队列的数目，即有进程在就绪队列中 
		system("cls");
		look(k);                        //取出按算法得到当前要执行的进程 
		tmp = p;
		//执行ready[k].rtime个时间片
		rtime = 0;
		while(rtime++ < ready[k].rtime){      //运行ready[k].rtime个时间片的时间                           
			in_flag = 1;                      //标记为完成                                                             
			printf("\n 是否插入新进程？(Y/N)");
			scanf("%c%*c", &ch);
			if(ch == 'Y' || ch == 'y'){
				input();
				k2 = check();
				if(k2 < k){			//有新进程进入优先级较高的队列
					grab(k2);
					p = tmp;
					break;
				}
			}
			look2(k, rtime);
			if(running()){
				in_flag = 0;		        //标记进程已完成                      
				break;
			}

		}
		if(in_flag)       //如果未完成 
			insert(k);             //插入下一个队列队尾 
		k = check();			
		printf("按任意键进行下一次调度...");
		ch = getchar();
	}
	printf("\n\n 进程已经完成。\n");
	ch = getchar();

	return 0;
}