proc.cpp

关于操作系统课程设计进程调度问题

/*
 * 
 * 
 *　进程调度实验
 *　本程序提供了以下几种进程调度方法
 *　1、时间片轮询法
 *  2、可强占优先法
 *  3、非抢占算法
 *
 */

#include <iostream.h>
#include <string.h>
#include <fstream.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

int proc;
int piece;
//时间片
//#define TIMESLICE 1

//完成状态
#define FINISH 0

//运行状态
#define RUNNING 1

//就绪状态
#define READY 2

//io状态
#define IO 3

//等待IO
#define WAIT 4

//进程个数
//#define PCBNUM 5

//定义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 ;

					running.addnode( q ) ;

					ready.deletenode( q, front ) ;

					q->pcb->pstate = RUNNING ;
				}
			}
			else
			{
				running.addnode( q ) ;

				ready.deletenode( q, front ) ;

				q->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;
			}
		}

		/*
		 * 运行进程
		 */
		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() ;

		//动态计算就绪队列优先级
		p = ready.link;

		while( p )
		{
			(p->pcb->priority) ++ ;

			p = p->link;
		}

		//print proc state
		pprint(pcb, pcbsnum);
	}
}


//普通的优先调度
/*

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

 * 如果运行结束或要执行IO再重新调度

 */

void generalpriority(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;
			}
		}

		if( !running.link )
		{
			//当运行队列为空

			//寻找最大的一个优先级

			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;
				}
			}

			p = running.link;

			if( q )
			{
				running.addnode(q) ;

				ready.deletenode(q, front);

				q->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 ;
			}
		}

		/*
		 * 运行进程
		 */
		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 ) ;
	}
}

void main()
{
	pcbs *pcblist;//进程表
cout<<"请输入数据个数："<<endl;
cin>>proc;

	int i ;

	remove("result.txt");

	pcblist = new pcbs[proc]; // 为进程表分配空间

	for( i = 0 ; i < proc ; i ++ )
		newpcb(pcblist+i, i);//产生进程

	pprint(pcblist, proc);

	poll(pcblist, proc);//轮循法调度

	generalpriority(pcblist,proc);//非抢占

	priority(pcblist, proc);//可抢占优先法

	delete pcblist;//释放进程空间
}