2014年华北电力大学计算机专业考研专业课复习3

处理机调度的基本概念 就绪队列中只要有两个以上的进程存在就会竞争CPU的使用权。如果只有1个CPU可用，那么就必须选择下一个要运行的进程。完成选择工作的这一部分称为调度程序（scheduler），该程序使用的算法称为调度算法（scheduling algorithm）。

调度方式及算法 不可抢占调度方式：一个进程若被选中，就一直运行下去，直到它被阻塞（I/O，或正在等待其他的进程），或主动地交出CPU。可抢占调度方式：当一个进程在运行时，调度程序可以打断它。另外，在其他的一些情形下，如就绪队列中有进程的优先级高于当前运行进程的优先级，也可能立即进行调度。

算法 先来先服务（First Come First Served，FCFS； First In First Out，FIFO）：按照作业到达的先后次序进行调度；不可抢占方式：当前进程占用CPU，直到执行完或被阻塞，才让出CPU给另外一个进程；在进程被唤醒后（如I/O完成），并不立即恢复执行，而是放在就绪队列的末尾；优点：简单，易于理解也易于实现。现实生活中应用广泛：排队。短作业优先（Shortest Job First，SJF），设计目标是改进FCFS算法，减少平均周转时间；SJF算法要求作业在开始执行时预计执行时间，对预计执行时间短的作业优先分派处理器两种实现方案：不可抢占方式：当前作业在运行时不会被打断，只有运行完毕或阻塞时，才让出CPU；可抢占方式：如果一个新的短作业到来，其运行时间小于当前正在运行作业的剩余时间，则抢占CPU运行，称为SRTF（Shortest Remaining Time First）。一种动态优先权算法 最高应比作业优先算法是对FCFS方式和SJF方式的一种综合平衡。响应比R定义为系统对作业的响应时间与作业要求运行时间的比值R＝响应时间 / 要求运行时间＝(作业等待时间＋需运行时间)/ 需运行时间＝1＋已等待时间 / 需运行时间＝1＋W/T优先级调度算法是从就绪队列中选出优先级别最高的进程。让它占用CPU运行静态优先级：静态优先级调度算法是指在创建 进程时就确定下来的，而且在进程的整个运行 期间其优先级是维持不变的动态优先级：动态优先级是随着进程的推进而不断变化的 (例如HRN)在时间片轮转算法（Round-Robin，RR）中，将所有的就绪进程按照FCFS原则，排成一个队列每次调度时将处理器分派给队首进程，让其执行一小段CPU时间（时间片time quantum）在一个时间片结束时，如果进程还没有执行完的话，将发生时钟中断，在时钟中断中，进程调度程序将暂停当前进程的执行，并将其送到就绪队列的末尾，然后执行当前的队首进程如果一个进程在它的时间片用完之前就已结束或被阻塞，那么立即让出CPU多级队列算法（Multilevel Queue）引入多个就绪队列，通过各个队列的区别对待，达到一个综合的调度目标。根据进程的性质或类型的不同，将就绪队列再分为若干个子队列，如系统进程、用户交互进程、批处理进程等；不同的队列可以有不同的优先级；不同的队列可以采用各自不同的调度算法，如前台式进程可采用RR算法，后台的批处理进程可采用FCFS算法。在各个队列之间也必须进行调度：固定优先级调度：按照各种类型的进程的优先级别从高到低地进行，先运行最高优先级的所有进程，再运行次一级所有进程，依此类推。 问题：可能导致“饥饿”；时间片方法：把CPU时间按比例分配给不同的队列，然后再由各个队列的调度算法去调度，如80％给前台的交互式进程队列（RR算法），20％给后台的批处理进程队列FCFS）。多级反馈队列算法 (Multilevel Feedback Queue)即根据一个进程的运行反馈信息，动态地调整它所在的队列。三种优先级别，3最高、1最低，三个就绪队列。时间片长度分别为N、2N和4N；新进程进入内存后，优先级为3，加入队列3的末尾，按FCFS算法调度；若一个时间片内未能执行完，则优先级降为2，加入到队列2的末尾，同样按FCFS算法调度；依此类推。仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执先级的队列，则抢先执行新进程。在实时系统中，对时间的要求是非常严格的。典型的例子是：一个或多个外部的物理设备定期或不定期地生成激励信号，而计算机必须在一定的时间期限内做出恰当的反应。根据任务的开始截止时间确定任务优先级，截止时间越早，优先级越高。可用于抢占和非抢占式。最低松弛度优先算法该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。松弛度＝必须完成时间－本身运行时间－当前时间

死锁的基本概念 在一组进程中，每个进程都占用着若干个资源，同时又在等待得到该组进程中另一进程所占用的资源，因而造成的所有进程都无法进展下去的现象，这种现象称为死锁，这一组进程就称为死锁进程。死锁的4个必要条件：互斥条件：在任何时刻，每一个资源最多只能被一个进程所使用；请求和保持条件：进程在占用若干个资源的同时又可以请求新的资源；不可抢占条件：进程已经占用的资源，不会被强制性拿走，而必须由该进程主动释放；环路等待条件：存在一条由两个或多个进程所组成的环路链，其中每一个进程都在等待环路链中下一个进程所占用的资源。

死锁的处理策略 忽略死锁，无为而治Windows、UNIX检测并恢复动态避免 小心的进行资源分配预防 破坏死锁的4个必要条件之一银行家算法在小镇上，有一位银行家和一些需要贷款服务的客户。银行家根据每一位客户的背景情况，为之设定了相应的最高贷款限额。现在的问题是银行家必须设计出一种算法，以保证借贷过程的顺利进行，也就是说，当某个客户提出了一个贷款申请时，该算法必须判断，如果批准了这个申请，是否会导致一种不安全的状态，如果是的话，就拒绝该申请；如果否的话，就批准该申请。求安全序列。