调度算法.cpp

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

					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 ) ;
	}
}
//-----------------------------------------------------------------
// 先来先服务算法
/*
 * 从就绪队列中取出最先到达的进程送到运行队列
 *
 * 如果运行结束或要执行IO再重新调度
 *
 */
void fcfs(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;			
			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 ) ;
	}
}
//------------------------------------------------------------
// 短作业(进程)优先调度算法
/*
 * 从就绪队列中取出最短的进程送到运行队列
 *
 * 如果运行结束或要执行IO再重新调度
 *
 */
void sjf(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 minneed = p->pcb->pneedtime;
				while( p )
				{
					if( p->pcb->pneedtime < minneed )
					{
						minneed = p->pcb->pneedtime;
						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 ;
	char x='1';
	remove("result.txt");
	pcblist = new pcbs[proc]; // 为进程表分配空间
	for( i = 0 ; i < proc ; i ++ )
		newpcb(pcblist+i, i);//产生进程
	pprint(pcblist, proc);
	while(x!='0')
	{
		cout<<"时间片轮转法输入1 非强占输入2 可强占输入3 FCFS输入4 SJF输入5  输入0退出："<<endl;

		cin>>x;
		switch(x)
		{
			case '1':poll(pcblist, proc);break;//时间片轮转法
			case '2':generalpriority(pcblist,proc);break;//非抢占式优先权算法
			case '3':priority(pcblist, proc);break;//抢占式优先权算法
			case '4':fcfs(pcblist, proc);break;//先来先服务算法
			case '5':sjf(pcblist, proc);break;//短作业(进程)优先调度算法
		}
	}
	delete pcblist;//释放进程空间
}