//os1.cpp--采用響應比高者優先的作業調度算法，進行批處理系統中的作業調度，
//編譯IDE:C++ Builder 命令行下編譯
//注：本實驗中用了三個隊列
//外存就緒隊列(后備隊列)head；內存就緒隊列read；運行隊列run
//處理機處理每一個作業的時間統一為3秒

#include <iostream.h>
#include <time.h>
#include <dos.h>

//#define N 10;					//假定系統中可容納的作業數量為n

typedef  struct  jcb
{char  name[4];				    //作業名
 int  length;					    //作業長度，所需主存大小
 int  printer;					    //作業執行所需打印機的數量
 int  tape;					    //作業執行所需磁帶機的數量
 int  runtime;					    //作業估計執行時間
 int  waittime;						//作業在系統中的等待時間
 int  next;						//指向下一個作業控制塊的指針，用游標實現·
}JCB;          				//作業控制塊類型定義

//存放作業控制塊的區域
JCB jobtable[10];			//作業表

//三個隊列的首指針
int  head;	//指向后備隊列的首指針，即外存就緒就緒首指針
struct 
{
	int head;
	int tail;
}ready;		//指向內存就緒隊列的頭指針和尾指針
int run;	//指向CPU正在運行的作業

int  jobcount=0;	//系統內現有作業數量
int  runcount=0;	//已運行的作業數量

int s, p, kp;	//p指向當前正在操作計算的作業，s標識p的前一位置
int t, q, kq;	//q指向滿足條件的作業，t標識q的前一位置

//設置系統所擁有的資源
int sysmemory=64*1024, sysprinter=4, systape=2;

void initialize(int);	//初始化某個時刻系統中各個作業的情況
void selectHRjob();
void loadin();	//裝入程序
void batrun();	//批處理運行程序

int main()
{
		
	initialize(10);	//手工初始化10個作業，且全部作業進入外存就緒隊列中

	system("PAUSE");

	for(;runcount<=9;){	//一共要處理10個作業
		ready.head=ready.tail=-1;	//
		bool tag=1;	//tag為真時表示還有作業可以調入內存
		while(tag){	//在運行前將外存中所有符合兩個條件的所有作業調入內存
			selectHRjob();	//從后備隊列中選擇滿足資源滿足且響應比最高的作業
			if(q!=-1)	//找到了q滿足兩個條件：系統資源滿足且響應比最高
				loadin();	//裝入內存，并修改系統資源
			else
				tag=0;	//沒有作業可以調入內存了，跳出
		}

		cout<<"將所有滿足條件的作業調入內存之后的系統信息："<<endl;
		cout<<"jobcount="<<jobcount<<endl;
		cout<<"sysmemory="<<sysmemory<<endl;
		cout<<" sysprinter="<<sysprinter<<endl;
		cout<<"systape="<<systape<<endl;

		system("PAUSE");

		//批處理內存中所有的作業
		batrun();
		cout<<"批處理完內存中的所有作業后的系統信息："<<endl;
		cout<<"runcount="<<runcount<<endl;
		cout<<"jobcount="<<jobcount<<endl;
		cout<<"sysmemory="<<sysmemory<<endl;
		cout<<"sysprinter="<<sysprinter<<endl;
		cout<<"systape="<<systape<<endl;

		system("PAUSE");

	}//for

	cout<<"Congratulations! "<<runcount<<" jobs haved run off"<<endl;
	system("PAUSE");

	return 0;
}

//手工初始化10個作業
void initialize(int n)
{
	void entercontent(int);	

	cout<<"注意：若提示輸入的是數字，而輸入的是字母或其它字符，則可能會導致死循環"<<endl;
	cout<<"請按提示輸入10個要處理的作業的信息:"<<endl;
	for(int i=0; i<=n-1; i++){	//系統中的n個作業組成一個靜態鏈表
		entercontent(i);	//輸入作業i的各項內容
		jobtable[i].next=i+1;	//作業指針指向下一個作業
	}
	jobtable[n-1].next=-1;	//表尾的指針域為空，即不指向任單元

	head=0;	//head指針指向第一個作業
}

void entercontent(int i)
{
	//輸入作業名
	cout<<"enter the JOBNAME of NO."<<i<<endl;
	cin>>jobtable[i].name;
	
	//輸入作業長度，所需主存大小
	cout<<"enter the job's LENGTH(1~65536)"<<endl;
	cin>>jobtable[i].length;
	while(jobtable[i].length<=0||jobtable[i].length>sysmemory){	//輸入正確性判斷
		cout<<"Enter error!"<<"\n請重新輸入作業大小(1～65536)：";
		cin>>jobtable[i].length;
	}
	
	//輸入作業執行行所需打印機的數量
	cout<<"enter how many PRINTERS the job need(<=4)"<<endl;
	cin>>jobtable[i].printer;
	while(jobtable[i].printer>4){	//輸入正確性判斷
		cout<<"Enter error!"<<"\n請重新輸入作業需要的打印機數量(0～4臺)：";
		cin>>jobtable[i].printer;
	}

	//輸入作業執行所需磁帶機的數量
	cout<<"enter how many TAPES the job need(<=2)"<<endl;
	cin>>jobtable[i].tape;
	while(jobtable[i].tape>2){		//輸入正確性判斷
		cout<<"Enter error!"<<"\n請重新輸入作業需要的磁盤帶數量(0～2臺)：";
		cin>>jobtable[i].tape;
	}

	//輸入作業估計執行時間
	cout<<"enter the RUNTIME of the job"<<endl;
	cin>>jobtable[i].runtime;

	//輸入作業在系統中的等待時間
	cout<<"enter the WAITIME of the job during systems"<<endl;
	cin>>jobtable[i].waittime;
}

//選擇外存就緒隊列中響應比最高的作業調入內存
void selectHRjob()
{

	p=head;
	q=s=-1;
	//循環一輪：從隊列頭找到隊列尾
	while(p!=-1){	
			bool condition=jobtable[p].length<=sysmemory&&jobtable[p].printer<=sysprinter&&
							jobtable[p].tape<=systape;
			if(condition){	//系統可用資源滿足作業要求
				kp=jobtable[p].waittime/jobtable[p].runtime;
				if(0==p||kp>kq){	//p是第一個滿足條件的作業或作業p的響應比比作業q的響應比高
					q=p; t=s; kq=kp;
				}
			}
			
			//指針p后移(1,condition為假; 2condition為真&&0==p||kp>kq)
			s=p;
			p=jobtable[p].next;	
	}

	cout<<"一輪循環之后選擇的是作業"<<jobtable[q].name<<" 此時q="<<q<<endl;

}

//裝入，并修改系統資源
void loadin()
{
			//從作業隊列中摘取q
			if(q==head)	//q是作業隊列中的第一個
				head=jobtable[head].next;
			else	//一般情況
				jobtable[t].next=jobtable[q].next;

			//為作業q分配資源
			sysprinter-=jobtable[q].printer;
			systape-=jobtable[q].tape;
			
			//輸出作業名
			cout<<"輸出作業的作業名 \""<<jobtable[q].name<<"\" 代替裝入主存儲器"<<endl;
			sysmemory-=jobtable[q].length;
			//裝入內存的作業掛入內存就緒隊列中
			if((ready.head==ready.tail)&&-1==ready.head&&-1==ready.tail)//內存就緒隊列為空，則插入隊列頭
				ready.head=ready.tail=q; 					
			else{	//一般情況
				jobtable[ready.tail].next=q;
				ready.tail=q;
			}

			++jobcount;	//內存中作業數增加1			
}

//批處理內存就緒隊列中的作業
void batrun()
{
	
	while(jobcount!=0){	//內存中還有作業	
		//摘取內存就緒隊列中的第一個作業
		if(1==jobcount){	//內存中只有一個作業
			run=ready.head;
			ready.head=ready.tail=-1;	//內存就緒隊列清空
		}
		else{	//一般情況
				run=ready.head;
				ready.head=jobtable[ready.head].next;
		}

		//運行，批處理的作業統一運行3秒
		cout<<"現在批處理作業"<<jobtable[run].name<<" please wait 3 seconds……"<<endl;
		for(int tmp=1; tmp<=3; ++tmp){
			cout<<"1 second"<<endl;
			sleep(1);
		}

		++runcount;	//運行作業數加1
		--jobcount;	//內存就緒隊列中的作業數減1
		cout<<"The job "<<jobtable[run].name<<"run OVER!"<<endl;
		cout<<"Now, you haved batrun "<<runcount<<" jobs"<<endl;

		//修改系統資源
		sysmemory+=jobtable[run].length;
		sysprinter+=jobtable[run].printer;
		systape+=jobtable[run].tape;
	}

}