进程调度 存储器管理 银行家算法 磁盘调度 操作系统实验报告

江苏科技大学操作系统实验报告（2015/2016学年第2学期）课程名称：操作系统指导教师：实验地点：西校区图书馆计算机机房学生姓名：学生学号：院系：计算机科学与工程学院专业：计算机科学与技术2016年5月15日实验一进程调度一、实验目的多道程序设计中，经常是若干个进程同时处于就绪状态，必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。本实验模拟在单处理机情况下的处理机调度问题，加深对进程调度的理解。二、实验内容1．优先权法、轮转法简化假设1）进程为计算型的（无I/O）2）进程状态：ready、running、finish3）进程需要的CPU时间以时间片为单位确定2．算法描述1）优先权法——动态优先权当前运行进程用完时间片后，其优先权减去一个常数。2）轮转法三、实验要求1．产生的各种随机数的取值范围加以限制，如所需的CPU时间限制在1~20之间。2．进程数n不要太大通常取4~8个3．使用动态数据结构4．独立编程5．二种调度算法四、实验过程//秦魏编写要拷贝使用无（fa）偿(ge)使(hong)用(bao)#ifndefMaxpriority_H#defineMaxpriority_H#definearrayLenth100;templateclassTclassMaxheap{T*heap;intheapsize,lenth;public:Maxheap(intn){lenth=0;heapsize=n;heap=newT[heapsize];}Maxheap(T*maxheap,intn){if(n0)return;lenth=n;heapsize=n;heap=newT[heapsize];inti;for(i=0;iheapsize;i++)heap[i]=maxheap[i];create();}~Maxheap(){delete[]heap;}intParent(inti){return(i+1)/2-1;//注意地址的转换，最后还要减去1}intLchild(inti){return2*(i+1)-1;}intRchild(inti){return2*i+2;}voidMaxheapify(inti){intl,r;l=Lchild(i);r=Rchild(i);intlargest;if(llenth&&heap[l].priorityheap[i].priority)//第一个条件，起到一个判断是否为叶子节点的作用largest=l;elselargest=i;if(rlenth&&heap[r].priorityheap[largest].priority)largest=r;if(largest!=i)swap(heap[largest],heap[i]),Maxheapify(largest);}voidswap(T&a,T&b){Tstore;store=a;a=b;b=store;}voidcreate(){inti;for(i=lenth/2-1;i=0;i--)Maxheapify(i);}voidinsert(T&element){lenth++;heap[lenth-1]=element;create();}voidprint(){inti;for(i=0;ilenth;i++)coutheap[i].priority;}intheapextractmax(){if(lenth==0)return-1;Tmax;max=heap[0];heap[0]=heap[lenth-1];lenth--;Maxheapify(0);returnmax.task;}intempty(){if(lenth==0)return1;return0;}};#endif#ifndefQuene_H#defineQuene_H#definesize1000//队列先进先出，从队尾进，从对头出templateclassTclassCirquene{Ta[size];intfront,rear;public:Cirquene(){front=rear=size-1;}~Cirquene(){}voidEnquene(T&e){if((rear+1)%size==front)throw上溢;rear=(rear+1)%size;a[rear]=e;}intDequene(){if(rear==size)throw下溢;if(Empty())return-1;else{front=(front+1)%size;returna[front].task;}}intGetfront(){returnfront;}intEmpty(){if(front==rear)return1;return0;}voidprint(){datatypee=a[rear];inti;do{i=e.pre;coute.x'\t'e.yendl;e=a[i];}while(i!=-1);//注意这边i的取值}};#endif#includeiostream#includeMaxheap.h#includeQuene.husingnamespacestd;enumState{//enum变量后用逗号隔开！！！！！ready,exe,blo,fin,};//任务状态structPCB//优先级队列通过堆排序实现{inttask;//任务intpriority;//优先级intAexeTime;//已经运行时间intSexeTime;//剩余运行时间intblocktime;//阻塞时间Statestate;//任务状态};intcheckstate(PCB*program){inti;//检查是否所有程序都已运行结束for(i=0;i5;i++)if(program[i].state!=fin)return0;return1;}voidPSA(MaxheapPCBTest,PCB*program,intArrtime[],intquantum){//1个单位时间检查一次用堆排序实现优先级队列intm=0,alltime=0,num=0,k,time=0;while(!checkstate(program)){if(num5)for(m=0;m5;m++)if(alltime==Arrtime[m])Test.insert(program[m]),cout进程m+1到达endl,num++,program[m].state=ready;//到达到达时间进入就绪队列if(alltime==0||k==-1)k=Test.heapextractmax();//在无进程运行后序有进程进入时应该抛出！！！！alltime++,time++;if(k==-1)cout从alltime-1到alltime单位时间无进程运行endl;if(k!=-1){program[k].state=exe,program[k].AexeTime++,program[k].SexeTime--,program[k].priority-=3,//优先级减3cout从alltime-1到alltime单位时间k+1进程运行endl;if(program[k].SexeTime==0)program[k].state=fin,time=0,cout进程k+1在alltime单位时间运行结束endl,k=Test.heapextractmax();if(program[k].SexeTime!=0&&time==quantum)program[k].state=ready,Test.insert(program[k]),time=0,k=Test.heapextractmax();}}}voidRR(PCB*program,inti,intArrtime[],intquantum){//优先级列表用队列实现intm,k,num=0,alltime=0,time=0;CirquenePCBpriority;while(!checkstate(program)){if(alltime==0)for(m=0;mi;m++)if(alltime==Arrtime[m])priority.Enquene(program[m]),cout进程m+1到达endl,num++,program[m].state=ready;//找到第一个到达的进程if(alltime==0||k==-1)k=priority.Dequene();//开始调度alltime++,time++;if(alltime!=0&&numi)for(m=0;mi;m++)//先判断下一个时刻是否有进程到达原因是在一个进程运行结束同时另外一个进程到达到达的那个进程应该首先进入就绪队列if(alltime==Arrtime[m])priority.Enquene(program[m]),cout进程m+1到达endl,num++,program[m].state=ready;if(k==-1)cout从alltime-1到alltime单位时间无进程运行endl;else{program[k].state=exe,program[k].AexeTime++,program[k].SexeTime--;cout从alltime-1到alltime单位时间k+1进程运行endl;if(program[k].SexeTime==0)program[k].state=fin,time=0,cout进程k+1在alltime单位时间运行结束endl,k=priority.Dequene();if(time==quantum)if(program[k].SexeTime!=0)program[k].state=ready,priority.Enquene(program[k]),k=priority.Dequene(),time=0;}}}intmain(){inttask[5]={0,1,2,3,4};//任务intExeTime[5]={5,5,3,1,3};//运行时间intpriority[5]={2,5,2,4,3};//优先级intArrTime[5]={4,3,2,0,4};//到达时间PCBprogram[5],program2[5];inti;for(i=0;i5;i++){program[i].task=task[i],program2[i].task=task[i];program[i].priority=priority[i],program2[i].priority=priority[i];program[i].AexeTime=0,program2[i].AexeTime=0;program[i].SexeTime=ExeTime[i],program2[i].SexeTime=ExeTime[i];program[i].blocktime=0,program2[i].blocktime=0;program[i].state=blo,program2[i].state=blo;}//初始化pcb*/MaxheapPCBTest(5);intquantum=2;//时间片为2cout优先权法:endl;PSA(Test,program,ArrTime,quantum);cout轮转调度法:endl;RR(program2,5,ArrTime,quantum);system(pause);return0;}五、实验分析与实现1.轮转法调度，具有先进先出的特点，所以利用队列实现2.优先级调度算法具有优先级动态变