操作系统实验报告

计算机操作系统

实 验 报 告

题 目 进程调度算法 班 级 学 号 学 生

2015 年 5 月

进程调度算法

一、 算法选择

优先级的算法用于多道批量处理系统可以获得满意的调度效果，但是在这种系统中，只能在优先级高的进程全部完成或发生某种事件后，才去执行下一个进程。这样，优先级较低的进程必须等待很长时间才能得到服务，这在分时系统中是绝对不允许的。

为此，在分时系统中通常采用时间片轮转法。

二、 程序代码

#include using namespace std; #include #include #include #include

const int MAXCOMMANDLEN =50;

/////////////////////////////////////////////////////////////////////////////////////

//PROCESS

/////////////////////////////////////////////////////////////////////////////////////

class Process //进程类 { friend class CPU; //声明友元函数类CPU protected: static int init_ID; //随机进程ID int ID; //进程ID char runText[MAXCOMMANDLEN]; //字符型进程指令数组 int IP; //进程指令指针，保存进程指令执行到的具体位置 bool ISuseSource; //此进程是否使用资源，ture:使用中 false : 未使用 bool ISblocked; //此进程是否被阻塞 ture:阻塞 false :未阻塞

int unitTime; //进程单位被cpu执行时间, 默认 1 int blockTime; //进程被阻塞时间 public: static void RandID(); //随机生成进程ID Process(); //构造函数声明 int getID(); int getIP(); void setIP(int); void Runed(); //进程被cpu执行 int getUnittime(); //得到进程单位执行时间 int getBlcoktime(); //得到进程阻塞时间 void setBlocktime(int); //设置进程阻塞时间 void setUnittime(int); //设置进程单位执行时间 char getResult(int); //得到进程执行结果 char* getRuntext(); //得到进程执行的指令 void setBlockstate(bool); //设置阻塞状态 bool getBlockstate(); bool getISusesource(); //得到资源的状态 使用 未使用 void setISusesource(bool); //设置资源的使用状态 };

int Process::init_ID;

void Process::RandID() { srand( (unsigned)time( NULL ) );//利用随机数函数得到ID的值 init_ID=rand(); //将得到的值赋给数据成员带回类中 }

Process::Process() //定义带参数的构造函数 { ID=init_ID++; //以产生的第一个ID为初始值，以后生产的ID顺序加1 int commandLen; //定义命令长度变量 IP=0; cout<<\"Please input the text which process runed by CPU [#command#] : \"; cin>>runText; //输入进程指令数组 if( (commandLen=strlen(runText) ) > MAXCOMMANDLEN )

//如果输入的runText字符数大于宏MAXCOMMANDLEN，正常退出程序 exit(0); runText[commandLen]='#'; // 程序ID结束标志 '#' runText[commandLen+1]='\\0'; //指令字符串结尾符 ISuseSource=false; //默认程序不使用资源

ISblocked=false; //默认程序不阻塞 unitTime=1; //默认程序执行时间为1 blockTime=0; //默认程序阻塞时间为0 }

void Process::Runed() { cout<int Process::getID() { return ID; }

int Process::getIP() { return IP; }

void Process::setIP(int ip) { IP=ip; }

bool Process::getISusesource() { return ISuseSource; }

void Process::setISusesource(bool s) { ISuseSource=s; }

char* Process::getRuntext() { return runText; }

int Process::getUnittime()

{ return unitTime; }

int Process::getBlcoktime() { return blockTime; }

void Process::setBlocktime(int BT) { blockTime=BT; }

void Process::setUnittime(int UT) { unitTime=UT; }

void Process::setBlockstate(bool state) { ISblocked=state;//布尔整型变量 }

bool Process::getBlockstate() { return ISblocked; }

char Process::getResult(int k)//返回进程数 { return runText[k]; }

/////////////////////////////////////////////////////////////////////////////////////

//SOURCE

/////////////////////////////////////////////////////////////////////////////////////

class Source //资源类 {

protected:

int ID; //资源 ID bool state; //资源状态 true : 未被进程占有 false : 已被占有 int pro_ID; //使用资源的进程id

Process *pro; //在资源类中定义进程类的对象，使用资源的进程指针 int time; //进程使用资源的时间 public: Source(int); bool getState(); //得到进程状态 void setState(bool); //设置进程状态 void setTime(int); void setPro(Process *); int getID(); int getPorID(); void setProID(int); void runned(); };

Source::Source(int id) { ID=id; pro=NULL; state=true; }

void Source::setProID(int id) { pro_ID=id; }

void Source::setTime(int t) { time=t; }

void Source::setState(bool s) { state=s; }

bool Source::getState() { return state; }

//设置进程使用资源的时间 //设置使用该资源的进程 //得到资源id //得到使用资源的进程id //设置使用资源的进程id //资源被cpu调用 void Source::setPro(Process *p) { pro=p; }

void Source::runned() { if(time>0) { cout<<\"( Source :\"<setISusesource(false); int ip=pro->getIP(); pro->setIP(++ip); Source::setState(true); cout<getID()<<\" relase the source!\"</////////////////////////////////////////////////////////////////////////////////////

//CPU

/////////////////////////////////////////////////////////////////////////////////////

typedef struct Block //阻塞队列结构 { Process *p_BlockProcess; //被阻塞的进程队列 int index; //被阻塞的进程在就绪队列中的索引（位置） }Block;

class CPU {

protected: Process *p_Process; //进程队列 Process **pp_Process; //进程就绪队列 Block *blockQueue ; //进程阻塞队列 Source *p_Source; //资源指针 int numOfprocess; //进程数量

int numOfblock; //被阻塞的进程数 int PC; //程序计数器 int allTime; //cpu运行的总时间 public : CPU(int); void Run(); //cpu运行进程 bool _IC(Process&); //虚拟IC,进行进程指令翻译 void useSource(Process&); //进程申请资源 void blockProcess(Process&); //阻塞进程 void releaseBlockPro(); //释放阻塞进程 int getAlltime(); //得到进程运行的总时间 void displayPro(); //显示进程的基本信息，id,指令,运行时间等 void blockTimeADD(); //阻塞时间加1 };

CPU::CPU(int num) //构造函数以初始化数据成员的值 { p_Source=new Source(379857); numOfprocess=num; //以输入的值初始化进程数量 numOfblock=0; //初始化被阻塞的进程数为零 allTime=0; //初始化所需的时间值为零 p_Process=new Process[numOfprocess]; //开辟一个新的存放Process类型数据的空间 pp_Process=new Process*[numOfprocess]; //开辟一个新的存放process类型数据指针的空间 blockQueue=new Block[numOfprocess]; //开辟一个存放Block结构体的空间 for(int i=0;ip_BlockProcess=NULL; blockQueue->index=-1; } }

int CPU::getAlltime() //返回完成所有进程所需要的时间值 { return allTime; }

void CPU::displayPro() { for(int i=0;i}

void CPU::Run() { int numPro=numOfprocess; //初始化numPro的值，为进程数num0fprocess的值 do { for(int num=0;num < numOfprocess;num++) // 当num的值大于等于进程数时，循环结束 {

//如果该指针为空，说明该进程不在就绪队列中，则结束本趟循环，执行下一次循环

if(!pp_Process[num]) continue;

//当程序运行时间大于程序执行时间，循环结束

for(int t=0;trunned(); if( p_Source->getState() && numOfblock>0 ) //释放阻塞进程 { releaseBlockPro(); } } } else { if(!p_Process[num].getBlockstate()) { numPro--; pp_Process[num]=NULL; continue; } break; } allTime++;

if(numOfblock>0) blockTimeADD(); }//end for t... if( p_Process[num].getUnittime() ) p_Process[num].setUnittime(1); cout<bool CPU::_IC(Process &p) //对进程中的指令进行翻译 { char resultRunned; resultRunned=p.getResult(PC); if(resultRunned=='#') return false; else { if(resultRunned=='$') //申请资源指令 { PC++; p.setIP(PC); resultRunned=p.getResult(PC); if( resultRunned >='1' && resultRunned <='9' ) { if(p_Source->getState()) { useSource(p); cout<<\"The process \"<//资源未被使用则使用资源

} else { blockProcess(p); cout<<\"The process \"<//资源已被使用则阻塞进程

return false; } } else { cout<<\"The process [\"<} } } return true; }

void CPU::blockTimeADD() { for(int i=0;igetBlcoktime(); blockQueue[i].p_BlockProcess->setBlocktime(++BT); } }

void CPU::useSource(Process& p) { p.setISusesource(true); p_Source->setState(false); p_Source->setProID(p.getID()); p_Source->setTime(p.getResult(PC)-'0'); p_Source->setPro(&p); }

void CPU::blockProcess(Process& p) { int tempIndex=numOfprocess-( Process::init_ID-p.getID() ); blockQueue[numOfblock].p_BlockProcess=&p; blockQueue[numOfblock].index=tempIndex; numOfblock++; int ip=p.getIP(); p.setIP(--ip); p.setBlockstate(true); p.setBlocktime(1); p.setUnittime(0); pp_Process[tempIndex]=NULL; }

void CPU::releaseBlockPro() {

//释放阻塞队列的第一个进程，因为它阻塞时间最长 pp_Process[blockQueue[0].index]=blockQueue[0].p_BlockProcess; blockQueue[0].index=-1; blockQueue[0].p_BlockProcess->setBlockstate(false);

blockQueue[0].p_BlockProcess->setUnittime( blockQueue[0].p_BlockProcess->getBlcoktime() ); blockQueue[0].p_BlockProcess->setBlockstate(0); blockQueue[0].p_BlockProcess=NULL; numOfblock--;

//阻塞队列中的其他进程向前移动一个位置 for(int i=0;i/////////////////////////////////////////////////////////////////////////////////////

//The main progress

/////////////////////////////////////////////////////////////////////////////////////

void main() { int num;//进程的数量 cout<<\"\********************************************************\"<//检查输入数据是否异常 try { cin>>num; //输入进程数量num if(num<=0) throw(num); //抛出异常的数据 } catch(int) //接受抛出的数据 { cout<<\"You input the numbers of process is error !\"<CPU virtualCPU(num); //定义CPU类的对象，同时将num传入CPU的构造函数中 cout<<\"Pocesses runed by CPU \"<virtualCPU.Run(); //通过对象访问CPU类中的Run函数 cout<<\"Processes runned over ! \"<cout<<\"\********************************************************\"<virtualCPU.displayPro();

cout<<\"\********************************************************\"<}

//这里没有任何的API调用 只是模拟，将进程设定了自己的语法，输入一般的字符cpu 调用时只是正常输出，如果遇到'$'表示该进程要调用系统资源后面必须跟一个数字表示占有的时间，如果资源闲置则占有资源否则阻塞，等资源释放在占有资源。进程的调用算法采用的是时间片轮转算法并有所改进，当某个进程从阻塞队列释放后，它将把以前因为等待资源而被浪费的时间补回来。

三、 程序执行结果及解释

1、不调用系统资源；

执行一个程序，程序编号为1，但因为没有输入调用资源符号“$”，故不调用系统资源，直接结束程序，默认程序运行时间为1秒，程序运行总时间1秒。

2、调用系统资源；

执行一个程序，程序编号为1，调用系统资源4秒，调用时显示“take up the source!”,调用完毕后释放资源，显示“relase the source!”，程序默认执行时间为1秒，加上调用系统资源3秒，故程序运行总时间为4秒。

3、程序阻塞；

执行两个程序，程序编号分别为1、2，由于程序1调用系统资源4秒，故程序2阻塞，当程序1执行完释放资源后，程序2才能调用系统资源；程序运行总时间为10秒。

4、程序异常；

i>由于系统调用符后未跟时间或输入不正确导致错误；

ii>由于输入程序的编号大于50位数，超出宏数组界限，程序出错；