操作系统读书工程报告

黑龙江大学操作系统读书工程报告操作系统课程设计读书工程报告学期 学院 学号 姓名 基本理论阐述在操作系统中调度实质上是一种资源的分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。对于不同的操作系统和系统目标，通常采用不同的调度算法，例如，在批处理系统中，为了照顾为数众多的短作业，应采用短作业优先的调度算法；又如在分时系统中，为了保证系统具有合理的相应时间，应采用轮转法进行调度。目前存在的多种调度算法中，有的使用于作业调度，也有的适用于进程调度；但也有些算法既可适用于作业调度又适用于进程调度。1.先来先服务(FCFS)先来先服务（FCFS,FirstComeFirstServe）是最简单的调度算法，按先后顺序进行调度。1.1FCFS算法按照作业提交或进程变为就绪状态的先后次序，分派CPU；当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。最简单的算法。1.2FCFS的特点比较有利于长作业，而不利于短作业。有利于CPU繁忙的作业，而不利于I/O繁忙的作业。2.短作业优先短作业优先（SJF,ShortestJobFirst）又称为“短进程优先”SPN(ShortestProcessNext)；这是对FCFS算法的改进，其目标是减少平均周转时间。对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。2.1SJF的特点(1)优点：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量；(2)缺点：对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。2.2SJF的变型“最短剩余时间优先”SRT(ShortestRemainingTime)（允许比当前进程剩余时间更短的进程来抢占）“最高响应比优先”HRRN(HighestResponseRatioNext)（响应比R=(等待时间+要求执行时间)/要求执行时间，是FCFS和SJF的折衷）3优先级法优先级算法（PriorityScheduling）是多级队列算法的改进，平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成抢先式和非抢先式。3.1静态优先级作业调度中的静态优先级大多按以下原则确定：由用户自己根据作业的紧急程度输入一个适当的优先级。由系统或操作员根据作业类型指定优先级。系统根据作业要求资源情况确定优先级。进程的静态优先级的确定原则：按进程的类型给予不同的优先级。将作业的情态优先级作为它所属进程的优先级。3.2动态优先级进程的动态优先级一般根据以下原则确定：根据进程占用有CPU时间的长短来决定。根据就绪进程等待CPU的时间长短来决定。4高响应比优先最高响应比优先法(HRN，HighestResponse_ratioNext)是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。响应比R定义如下：R=(W+T)/T=1+W/T其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W/T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRN方式时其吞吐量将小于采用SJF法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。5时间片轮转轮转法(RoundRobin)是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。进程可以未使用完一个时间片，就出让CPU（如阻塞）。长度的确定时间片长度变化的影响：过长－>退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。过短－>用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。对响应时间的要求：T(响应时间)=N(进程数目)*q(时间片)。就绪进程的数目：数目越多，时间片越小系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。6多级反馈队列6.1多级反馈队列的原理：1、设有N个队列（Q1,Q2....QN），其中各个队列对于处理机的优先级是不一样的，也就是说位于各个队列中的作业(进程)的优先级也是不一样的。一般来说，优先级Priority(Q1)>Priority(Q2)>...>Priority(QN)。怎么讲，位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高（也就是说，Q1中的作业一定要比Q2中的作业先被处理机调度），依次类推其它的队列。2、对于某个特定的队列来说，里面是遵循时间片轮转法。也就是说，位于队列Q2中有N个作业，它们的运行时间是通过Q2这个队列所设定的时间片来确定的（为了便于理解，我们也可以认为特定队列中的作业的优先级是按照FCFS来调度的）。3、各个队列的时间片是一样的吗？不一样，这就是该算法设计的精妙之处。各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。同时，为了便于那些超大作业的完成，最后一个队列QN(优先级最低的队列)的时间片一般很大(不需要考虑这个问题)。6.2多级反馈队列调度算法描述：1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。3、对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。当前应用现状linux内核的三种调度方法：1，SCHED_OTHER分时调度策略，2，SCHED_FIFO实时调度策略，先到先服务3，SCHED_RR实时调度策略，时间片轮转实时进程将得到优先调用，实时进程根据实时优先级决定调度权值，分时进程则通过nice和counter值决定权值，nice越小，counter越大，被调度的概率越大，也就是曾经使用了cpu最少的进程将会得到优先调度。SHCED_RR和SCHED_FIFO的不同：当采用SHCED_RR策略的进程的时间片用完，系统将重新分配时间片，并置于就绪队列尾。放在队列尾保证了所有具有相同优先级的RR任务的调度公平。SCHED_FIFO一旦占用cpu则一直运行。一直运行直到有更高优先级任务到达或自己放弃。如果有相同优先级的实时进程（根据优先级计算的调度权值是一样的）已经准备好，FIFO时必须等待该进程主动放弃后才可以运行这个优先级相同的任务。而RR可以让每个任务都执行一段时间。相同点：RR和FIFO都只用于实时任务。创建时优先级大于0(1-99)。按照可抢占优先级调度算法进行。就绪态的实时任务立即抢占非实时任务。所有任务都采用linux分时调度策略时。1，创建任务指定采用分时调度策略，并指定优先级nice值(-20~19)。2，将根据每个任务的nice值确定在cpu上的执行时间(counter)。3，如果没有等待资源，则将该任务加入到就绪队列中。4，调度程序遍历就绪队列中的任务，通过对每个任务动态优先级的计算(counter+20-nice)结果，选择计算结果最大的一个去运行，当这个时间片用完后(counter减至0)或者主动放弃cpu时，该任务将被放在就绪队列末尾(时间片用完)或等待队列(因等待资源而放弃cpu)中。5，此时调度程序重复上面计算过程，转到第4步。6，当调度程序发现所有就绪任务计算所得的权值都为不大于0时，重复第2步。个人对相关内容的体会通过读书学习学到了很多的东西，对于进程和作业的调度并没有最好的算法，只有更适合，例如短作业优先，它虽然能在一定程度上照顾短进程和短作业但是如果有较多的短作业时长作业就会较长时间地等待，从而有可能造成“饥饿”等待的现象。而如果“饥饿”的进程等待到一定的程度后即使进程所赋予的任务完成也不再具有实际的意义，即为该进程已经被“饿死”。高响应比调度算法解决了短作业的缺点，既照顾了短作业又考虑到了作业到达的先后次序，但是每次进行调度前都要进行计算响应比，因此也会造成一定的时间开销，尤其对于较多的进程时时间的开销还是很大的。所有的处理机调度里面可能比较好的就是多级反馈队列。我在该部分时也遇到了不少的困难，一个好的程序不仅要有较高的效率对容错处理上也要考虑，尤其是在用户输入数据上，如果用户输入的是的是非法的数据该怎么处理，如果输入的文件不存在又该怎么做。最终经过不停的实验调试后成功了，而且对于多级反馈队列来说，它不仅柔和了先来先服务，优先权调度还有时间片轮转，例如只有一个队列时它便是时间片轮转，当时间片调整到很大时又退化到先来先服务等等。设计与实现思路进程调度各个数据结构首先是对于进程或者说作业的结构体PCB设计，要考虑以后的各个算法中可能会用到的需要保存的数据，例如进程名称name，进程的到达时间arrive，进程需要服务的时间等等，如下即为PCB结构体：typedefstructPCB{stringname;intarrive; intneed; intserver; intstart; intpriority; intfinish; intcycletime; floatweight_cyltime;};其中name为进程或作业名称；arrive为进程或作业到达时间；need为需要服务的时间；server为进程或作业已经服务的时间；start为进程或作业开始时间，priority为优先权从小到大，finish为进程或作业完成时间；cycletime为进程或作业的周转时间，weight_cycletime为进程或作业带权周转时间。基类process类：是其它各个调度算法的基类，其他各调度算法类均由process类派生出来，应该有私有成员aver_cycle为平均周转时间，aver_wct为平均带权周转时间；另外由于FCFS和SJF的调度上相差并不大，一个是要获取进程到达早未服务的一个是获取进程到达而未服务的因此用get_nextNum（inttime）为提供FCFS和SJF使用获取下一个要调度的作业。对于process类基本结构定义如下：classprocess{private: floataver_cycle; floataver_wct;protected: vector<PCB>vproc; voidcalculate_all(); voidresetData();public: process(void); ~process(void); voidadd_process(stringn,inta,intse,intst); PCBget_process_at(intnum); intget_vector_num(vector<PCB>v,stringname); intget_nextNum(inttime); voidshow();};用UML中的类图表示如下图所示：图1process类图以下为实现调度算法的各个类：先来先服务FCFS先来先服务(FirstComeFirstServer)，继承自process类，除了父类中的函数和变量外还有使用文件载入数据的函数init_data(file[])；其次便是实现先来先服务的调度算schedul()；FCFS类的定义：classFCFS:publicprocess{public: voidinit_data(charfile[]); voidschedul();};图2FCFS类图短作业优先SJF短作业优先(ShortJobFirst)，包含resetPriority()重新设置优先级，init_data(file)载入数据函数，schedul_grab()抢占调度，schedul_ngrab()抢占调度(即最短剩余作业优先调度算法)；SJF类的定义：classSJF:publicprocess{protected: voidresetPriority();public: voidinit_data(charfile[]); voidschedul_grab();//抢占 voidschedul_ngrab();//非抢占 voidschedul();//调度算法 };图3SJF类图高响应比优先HRN高响应比优先(HighestResponse_ratioNext)，vector<float>ratio为与各个进程相对应的相应比，除了与FCFS，SJF类似的载入数据init_data(file[])外还有calculate_ratio(inttime)即根据时间计算各个作业的响应比；get_nextNum(inttime,intt)为根据时间获取下一个要调度的作业；shedul_grab()为抢占，shedul_ngrab()为非抢占；HRN类的定义：classHRN:publicprocess{private: vector<float>ratio;//响应比protected: voidcalculate_ratio(inttime); intget_nextNum(inttime,intt);public: voidinit_data(charfile[]); voidschedul_grab();//抢占 voidschedul_ngrab();//非抢占 voidschedul();//调度算法};图2HRN类图时间片轮转RR时间片轮转调度算法(RoundRobin)，vector<PCB>ready为已到达的就绪进程；timeslice为轮转的时间片；tradition()为传统高响应比的调度算法，而feed_back()为反馈的调度算法，这两种调度算法分别在schedule()中调用；RR类的定义：classRR:publicprocess{private: vector<PCB>ready; vector<string>line; inttimeslice;//时间片protected: voidcheck_arrive(inttime);public: voidinit_data(charfile[]); voidtraditon();//传统 voidfeed_back();//反馈 voidschedule();};图2RR类图多级反馈队列MFQ多级反馈队列(Multi-levelFeedbackQueues)，私有成员queNum为队列的数量；timeslice为第一个队列的时间片，其余队列的时间片依次成倍增长；bool*record为记录对应存储在vector<PCB>vproc中的进程是否已经进入队列当中。Release()为释放链表当中的各个结点及record；queue_empty()用来检测所有的队列里是否已经为空；check_arrive(inttime)为检查在time时刻到达的进程若已经到达则返回true，并将到达的进程放入第一个队列当中。MFQ类的定义：structqueue{ vector<PCB>v; intnum; structqueue*next;};classMFQ:publicprocess{private: intqueNum; inttimeslice;//第一个队列的时间片 structqueue*execute;//所有的队列，以链表的形式存放 bool*record;//用于记录对应的进程是否调度过被protected: boolqueue_empty();//检查队列是否全部为空 voidrelease();//防止内存泄露 voidpush_to_next(queue*&p,vector<PCB>::iterator&q);//将q放入p的下一队列里public: voidinit_data(charfile[]); boolcheck_arrive(inttime); voidschedule(); voidinit_queue();//初始化队列 voidshow_queue(); };图2MFQ类图总体设计的类图如下所示：类图调度算法FCFS：先来先服务调度算法，每次只需找到已经到达的而未服务进程中到达时间最早的一个即可，令p->server=p->need，time+=p->need再进入下一次循环，直到所有的进程执行完毕再显示数据即可。SJF：短作业优先算法，是对短作业或短进程优先调度的算法。先从后备队列选出一个估计运行时间最短的作业。如果是非抢占的则一直等到进程运行完毕再进行选择下一个进程，如果是抢占的即最短剩余作业优先则当一个作业正在运行中若检测到有更短作业则需要暂停现在的作业改换更短的作业运行；HRN：高响应比优先调度，当需要选择进程时需要选择相应比高的进程，其优先权变化为优先权=（等待时间+要求服务的时间）/要求服务的时间对于非抢占的调度算法类似短作业优先中的调度，而抢占的则需要时间每加一就检查一遍是否有进程的优先权大于当前进程，对于抢占的调度算法其流程图如下所示：RR：时间片轮转调度算法，将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时把CPU分配给队首进程，令其执行一个时间片，当时间片用完时