shd.cpp

自己写的操作系统的实验：处理机调度模拟及内存分配模拟二合一小程序。

#include "stdafx.h"
#include "shd.h"
#include <cstdlib>	//for srand() and rand()
#include <cassert>
#define DEFAULT_RUN_PROCESS 4

Crunqueue::Crunqueue():n_max_run(DEFAULT_RUN_PROCESS),n_process(0),sched_kind(0),usemm(false)
{
	Cmm* mp=new Cmm;
	mp->size=MM_TOTAL_SIZE;
	mm.push_back(mp);
}

Cpcb* Crunqueue::randpcb()
{
	++n_process;
	srand(n_process);
	Cpcb* p=new Cpcb;
	p->pid=n_process;
	p->priority=rand()%MAX_PRIO;
	p->time_slice=(int)rand()%DEFAULT_TIME_SLICE+1;
	p->memory=rand()%MM_MAX_SIZE+8;
	return p;
}

void Crunqueue::deletepcb(Cpcb* p)
{
	--n_process;
	delete p;
}

void Crunqueue::add_to_reserve(Cpcb* p)
{
	if( p->state!=TASK_OVER )
	{
		reserve.push_back(p);
		p->state=TASK_RESERVE;
	}
	if( sched_kind==SCHED_PRIO )
	{
		reserve.sort();
	}
}

void Crunqueue::add_to_reday(Cpcb* p)
{
	if( active.count<n_max_run )
	{
		if( p->state!=TASK_READY )
			p->state=TASK_READY;
		active.push_back(p);
	}
}

void Crunqueue::add_to_hang(Cpcb* p)
{
	if( p->state==TASK_HANG || p->state==TASK_OVER )
		return;
	if( p )
	{
		active.pop(p);	
		hang.push_back(p);
		p->state=TASK_HANG;
	}
	schedule();
}

void Crunqueue::active_hang(Cpcb* p)
{
	if( p->state==TASK_HANG )
	{
		hang.pop(p);
		active.push_back(p);
		in_schedule();
	}
}

void Crunqueue::add_to_over(Cpcb* p)
{
	over.push_back(p);
	p->state=TASK_OVER;
	reclaim(p);
	schedule();
}

void Crunqueue::in_schedule_prio()
{
		active.sort();
		current=active.head;
		if( !current->run() )
		{
			Cpcb* p=active.pop_front();	
			add_to_over(p);
			schedule();
		}
}

void Crunqueue::in_schedule_rr()
{
	current=active.head;
	if( !current->run() )
	{
		Cpcb* p=active.pop_front();	
		add_to_over(p);
		schedule();
	}
	//while( active.head->run() );	//一直运行，直到该进程结束
	//Cpcb* p=active.pop_front();	
	//add_to_over(p);
	//if( !active.count && !hang.count ) return;
	//schedule();	//重新载入进程
}

/*内调度(俗语低级调度或进程调度)：负责就绪队列中进程切换*/
void Crunqueue::in_schedule()
{
	if( active.count==0 ) return;
	if( SCHED_PRIO==sched_kind )
		in_schedule_prio();
	else if( SCHED_RR==sched_kind )
		in_schedule_rr();
}

/*外调度(俗语高级调度或作业调度)：负责就绪队列线程的供给*/
void Crunqueue::schedule()
{
	if( reserve.count>0 )
	{
		int canrun=0;
		//判断后备队列是否超出规定运行线程数，是则按规定道数慢慢来，否则全部上
		if( reserve.count>n_max_run-active.count) canrun=n_max_run;
		else canrun=reserve.count+active.count;
		for(int i=active.count;i<canrun;i++)
		{
			if( usemm && !alloc(reserve.head) ) break;
			add_to_reday(reserve.pop_front());
		}
	}
	/*外调度是为内调度作准备，循环机制*/
	//if( active.count || hang.count )
	//	in_schedule();
	/*当就绪队列和挂起队列中都没有进程时说明调度完成*/
}

bool Crunqueue::alloc(Cpcb* p)
{
	Cmm* mp=mm.head;
	while(mp->size<p->memory)
	{
		mp=mp->nextp;
		if( mp==mm.end ) //无足够多的内存
			return false;
	}
	//分配到内存
	p->mm_begin=mp->begin;
	mp->div(p->memory);
	if( mp->size==0 && mp->begin!=MM_TOTAL_SIZE)
		mm.remove(mp);
	return true;
}

void Crunqueue::reclaim(Cpcb* p)
{
	Cmm* mp=mm.head;
	while( mp!=mm.end && p->mm_begin>mp->begin)
	{
		mp=mp->nextp;
	}

	Cmm* tp=new Cmm;
	tp->size=p->memory;
	tp->begin=p->mm_begin;

	if( mp->begin==tp->begin+tp->size )
	{
		if( mp!=mm.head && tp->begin==mp->prep->begin+mp->prep->size )
		{
			mp->extent_front(tp);
			mp->prep->extent_back(mp);
			mm.remove(mp);
		}
		else
			mp->extent_front(tp);
	}
	else if( mp!=mm.head && tp->begin==mp->prep->begin+mp->prep->size )
		mp->prep->extent_back(tp);
	else
		mm.insert_before(tp,mp);
	p->mm_begin=0;
}

void Crunqueue::clear()
{
	if( n_process )
	{
		reserve.clear();	//清空后备队列
		active.clear();		//清空就绪队列
		hang.clear();		//清空挂起队列
		over.clear();		//清空完成队列
		n_max_run=0;
		n_process=0;
		sched_kind=0;
	}
}