调度算法.cpp

这是操作系统实验的调度算法,包含时间片轮转法,抢占式优先权算法,非抢占式优先权算法,先来先服务算法,短作业(进程)优先调度算法.

// 调度算法.cpp : Defines the entry point for the console application.
//
/*
 * 
 * 
 *　进程调度实验
 *　本程序提供了以下几种进程调度方法
 *　1、时间片轮转法
 *  2、抢占式优先权算法
 *  3、非抢占式优先权算法
 *  4、先来先服务算法
 *  5、短作业(进程)优先调度算法
 */
//-------------------------------------------------------------------------
#include "stdafx.h"
#include <iostream.h>
#include <string.h>
#include <fstream.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

int proc;
int piece;

//完成状态
#define FINISH 0
//运行状态
#define RUNNING 1
//就绪状态
#define READY 2
//io状态
#define IO 3
//等待IO
#define WAIT 4

//定义PCB结构
typedef struct tagPCBS
{
// id
long pid;
// name
char pname[10];
// state
int pstate;
// total time
int pneedtime;
// start time
int piostarttime;
// need time
int pioneedtime;
// current time
int ptime;
// priotiry
int priority;
} pcbs, *ppcbs ;



class pcbnode;
//队列结点
class pcbnode
{
public:
	pcbs *pcb;
	pcbnode *link;
	pcbnode();
	~pcbnode();
	int run();//运行操作
	int runend();//运行结束？
	void runio();//IO操作
	int ioend();//io结束？
	int insertnode(pcbnode *p,pcbnode *q);//在q后插入结点p
	int deletenode(pcbnode *p,pcbnode *q);//删除p结点，q为p的前驱
	int addnode(pcbnode *p);//增加结点
	int pcbnode::isio();//是否开始IO
} ;


pcbnode::pcbnode()
{
	pcb = 0;
	link = 0;
}

pcbnode::~pcbnode()
{
	if( link )
		delete link;
	if( pcb )
		pcb->pstate = FINISH;
}

int pcbnode::run()
{
	pcb->pstate = RUNNING ;
	++ pcb->ptime ;
	//优先级降低	
	pcb->priority -- ;
	return 0;
}

int pcbnode::runend()
{
	return ( pcb->pneedtime <= pcb->ptime ) ;
}

int pcbnode::isio()
{
	return ( (pcb->piostarttime == pcb->ptime) && (pcb->pioneedtime > 0) ) ;
}

int pcbnode::ioend()
{
	return ( (pcb->pioneedtime) <= 0 ) ;
}

void pcbnode::runio()
{
	pcb->pstate = IO;
	--(pcb->pioneedtime);
}

int pcbnode::addnode( pcbnode *p )
{
	pcbnode *q;
	q = this;
	p->pcb->pstate = READY;
	while( q->link )
		q = q->link;
	q->link = p;
	return 0;
}

int pcbnode::insertnode( pcbnode *p,pcbnode *q )
{
	p->link = q->link;
	q->link = p;
	return 0;
}

int pcbnode::deletenode( pcbnode *p, pcbnode *q )
{
	q->link = p->link;
	p->link = 0;
	return 0;
}


int randInt( int seed )
{
	int r;
	r = rand();
	while ( (r > seed) || ( r < 0 ) )
	r = rand();
	return r;
}
//---------------------------------------------------------------------------------------------
void newpcb( pcbs *pcb, int order )
//随机生成进程
{
	char buf[10] ;
	pcb->pid = order ;
	strcpy( pcb->pname, "proc" ) ;
	itoa( order, buf, 10 ) ;
	strcat( pcb->pname, buf ) ;
	pcb->pneedtime = randInt( 10 ) ;
	pcb->piostarttime = randInt( pcb->pneedtime ) ;
	pcb->pioneedtime = randInt( 10 ) ;
	pcb->ptime = 0 ;
	pcb->priority = randInt( 10 ) ;
}

void pprint( pcbs *pcb, int count )
{
	int i ;
	// 打印进程状态
	ofstream ofs( "result.txt", ios::out | ios::app ) ;
	cout<<"id\tname\tstat\tneed\tiostart\tioneed\truntime\tpri"<<endl ;
	ofs<<"id\tname\tstat\tneed\tiostart\tioneed\truntime\tpri"<<endl ;
	for( i = 0 ; i < count ; i ++ )
	{
		cout<<pcb[i].pid<<'\t'<< pcb[i].pname<<'\t' ;
		ofs<< pcb[i].pid<<'\t'<< pcb[i].pname<<'\t' ;
		switch( pcb[i].pstate )
		{
		case IO :
			cout<<"IO" ;
			ofs<<"IO";
			break;
		case RUNNING:
			cout<<"Running";
			ofs<<"Running";
			break;
		case READY:
			cout<<"Ready";
			ofs<<"Ready";
			break;
		case FINISH:
			cout<<"Finish";
			ofs<<"Finish";
			break;
		case WAIT:
			cout<<"Wait";
			ofs<<"Wait";
			break;
		}
		cout<<'\t'<<pcb[i].pneedtime ;
		ofs<<'\t'<<pcb[i].pneedtime ;
		cout<<'\t'<<pcb[i].piostarttime<<'\t'<<pcb[i].pioneedtime<<'\t'<<pcb[i].ptime ;
		ofs<<'\t'<<pcb[i].piostarttime<<'\t'<<pcb[i].pioneedtime<<'\t'<<pcb[i].ptime ;
		cout<<'\t'<<pcb[i].priority ;
		ofs<<'\t'<<pcb[i].priority ;
		cout<< endl ;
		ofs<< endl ;
	}
	ofs<<"---------------------------------------------"<<endl ;
	cout<<"---------------------------------------------"<<endl ;
}
//------------------------------------------------------------------------------------
//时间片轮转法
/*

 * 每执行一次，cpu时间加1， 还需时间减1

 *　每次执行时间片指定次数

 *　时间片执行完毕排到就绪队列尾部

 */
void poll(pcbs * pcb, int pcbsnum)
{
	pcbnode running, ready, blocked ;
	pcbnode *p ;
	pcbnode *q ;
	cout<<"输入时间片长度："<<endl;
	cin>>piece;
	int i ;
	/* 将进程表中的进程加到就绪队列中 */
	for( i = 0 ; i < pcbsnum ; i++ )
	{
		p = new pcbnode ;
		p->pcb = pcb + i ;
		ready.addnode( p ) ;
	}
	//开始调度
	 while( ready.link || running.link || blocked.link )
	{
		/*
		 * 判断正在运行的进程是否要进行IO
		 * 是则将其送到IO队列否则
		 * 将正在运行的进程送到就绪队列中
		 */
		if( running.link )
		{
			//需要IO?
			if( running.link->isio() )
			{
				blocked.addnode(running.link) ;
				running.link->pcb->pstate = WAIT ;
			}
			//运行结束?
			else if ( running.link->runend() ) 
			{
				p = running.link ;
				running.link = 0 ;
				delete p ;
			}
			//调度
			else
			{
				ready.addnode(running.link) ;
				running.link->pcb->pstate = READY ;
			}
			running.link = 0;
		}
		/*
		 * 将就绪队列的首结点送入运行队列
		 */
		q = &ready;
		p = ready.link;
		if( ready.link )
		{
			ready.deletenode( p, q ) ;
			running.addnode( p ) ;
			p->pcb->pstate=RUNNING ;
		}
		/*
		 * 将处理完IO的进程送到就绪队列
		 */

		p = blocked.link;
		q = &blocked;
		if( p )
		{
			int r;
			r = p->ioend();
			if( r )
			{
				blocked.deletenode( p, q ) ;
				ready.addnode( p ) ;
				p = q->link ;
			}
		}
		/*
		 * 运行进程,运行时间为时间片指定长度
		 */
		int j = piece;
		while( j-- )
		{
			p = running.link ;
			q = &running ;
			if( p )
			{
				//is IO start?
				if( !(p->isio()) )
					p->run();//RUN
			}
			/*
			* IO
			*/
			p = blocked.link;
			q = &blocked;
			if (p)
				p->runio();
			//print proc state
			pprint(pcb, pcbsnum);
		}
	}
}
//-----------------------------------------------------------------------------------
//抢占式优先权算法
/*

 * 从就绪队列中取出最优先的进程送到运行队列

 * 每运行一次，正在运行的进程优先数减1，等待的进程优先数加1

 * 如果就绪队列中的最大优先数进程的优先数大于正在运行的优先数，

 * 则运行的进程让出cpu,排到就绪队列的尾部，将最大优先数的进程送进

 * 运行队列。

 */
void priority( pcbs * pcb, int pcbsnum )
{
	pcbnode running, ready, blocked ;
	pcbnode *p, *f, *front ;
	pcbnode *q ;
	int i ;
	/*将进程表中的进程加到就绪队列中*/
	for ( i = 0 ; i < pcbsnum ; i ++ )
	{
		p = new pcbnode ;
		p->pcb = pcb + i ;
		ready.addnode( p ) ;
	}
	while( ready.link || running.link || blocked.link )
	{
		//判断将运行队列中的进程是否要io或结束
		if( running.link )
		{
			//需要IO?
			if( running.link->isio() )
			{
				blocked.addnode( running.link ) ;
				running.link->pcb->pstate = WAIT ;
				running.link = 0 ;
			}
			//运行结束?
			else if( running.link->runend() )
			{
				p = running.link;
				running.link = 0;
				delete p;
			}
		}
		//寻找最大的一个优先级
		p = ready.link;
		q = p ;
		f = &ready ;
		front = f ;
		if( p )
		{
			int maxpri = p->pcb->priority ;
			while( p )
			{
				if( p->pcb->priority > maxpri )
				{
					maxpri = p->pcb->priority ;
					front = f;
					q = p;
				}
				f = p;
				p = p->link;
			}

		}

		//如果最大优先级大于正在运行的优先级则强占cpu
		p = running.link;

		if( q )
		{
			if (p)
			{
				if( p->pcb->priority < q->pcb->priority )
				{
					ready.addnode(p);

					running.deletenode( p, &running ) ;

					p->pcb->pstate = READY ;