操作系统讲义-第三章处理机调度与死锁

2020年1月19日操作系统讲义1第三章处理机调度与死锁2020年1月19日第二章进程管理2主要内容3.1处理机调度的层次3.2调度队列模型和调度准则3.3几种调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除2020年1月19日第二章进程管理33.1处理机调度的层次作业的基本概念1.高级调度（HighLevelScheduling）主要功能：根据某种算法，把外存中把处于后备队列中的那些作业调入内存，当作业完成时做善后处理。作业（Job）：包含通常的程序和数据，并且配有作业说明书；作业步（JobStep）：“编译”-“连接装配”-“运行”；作业流：若干个作业在系统外存形成的输入流。作业控制块JCB（JobControlBlock）通常包含：作业标识、用户名称、用户账户、作业类型（CPU繁忙，I/O繁忙，批量型，终端型）、作业状态、调度信息（优先级，作业运行时间）、资源需求（运行时间，内存，I/O类型数量）、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况。2020年1月19日第二章进程管理43.1处理机调度的层次1.高级调度（HighLevelScheduling）作业调度：是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存后备队列中选取某些作业调入内存，为他们创建进程、分配必要的资源，然后将进程插入就绪队列，准备执行。目的：提高内存利用率和系统吞吐量，使那些暂时不能运行的进程不再占用内存，把它们调至外存（存储管理中的对换功能）。1）接收多少个作业到内存取决于多道程序度2）接收哪些作业取决于调度算法最简单：先来先服务调度算法最常用：短作业优先调度算法较常用：优先级调度算法比较好：响应比高者优先调度算法2.中级调度（IntermediateLevelScheduling）2020年1月19日第二章进程管理53.1处理机调度的层次3.低级调度（LowLevelScheduling）它所调度的对象是进程（或内核级线程），当CPU需要重新分配时，利用一定的算法把它分配给进程，它是最基本的调度。进程调度的功能（1）保存处理机的现场信息；（2）按照某种算法选择进程（如优先数算法，轮转算法）（3）把处理器分配给进程。进程调度的三个基本机制（1）排队器：事先将系统所有就绪进程排成一个队列，方便调度程序最快找到它；（2）分派器（分派程序）：把进程调度程序选定的进程从就绪队列移出，切换上下文，然后把CPU分配给它；（3）上下文切换机制：保存当前程序的上下文，装入分配程序的上下文；移出分派程序，装入新选进程的CPU信息；2020年1月19日第二章进程管理63.1处理机调度的层次进程调度方式3.低级调度（LowLevelScheduling）非抢占方式：一旦处理机分配给某个进程，不管它要运行多长时间，都让它一直运行下去，决不会因为其他原因而抢占正在运行进程的处理机。这种方式下引起进程调度的因素包括：•执行完毕或者发生某事件不能再执行•执行进程提出I/O请求而暂停执行•在进程通信或者同步过程中执行了某种原语操作，如P，Block等优点：实现简单，系统开销小，适用于大多数批处理系统；缺点：难以满足紧急任务要求，可能造成难以预料的后果。2020年1月19日第二章进程管理73.1处理机调度的层次进程调度方式3.低级调度（LowLevelScheduling）抢占方式：允许调度程序根据某种原则去暂停某个正在执行的进程，这些原则主要包括：•优先权原则•短作业优先原则•时间片原则优点：防止一个长进程长时间占用处理机，公平服务，适合实时任务的需求；缺点：需要付出较大的开销。2020年1月19日第二章进程管理83.2调度队列模型和调度准则仅有进程调度的调度队列模型通常在分时系统中只设置进程调度，每个用户建立一个进程，系统利用堆栈，树或者链表来管理就绪进程队列。1.调度队列模型进程执行时可能出现的三种情况：•在给定时间片完成，释放处理机进入完成状态；•本次时间片内未完成，放入就绪队列尾部；•因为某事件被阻塞，放入阻塞队列。就绪队列CPU阻塞队列交互用户时间片完进程调度等待事件进程完成事件出现2020年1月19日第二章进程管理93.2调度队列模型和调度准则具有高级和低级调度的调度队列模型作业调度按照一定的算法从外存的后备队列选择一批作业调入内存，建立进程，送入就绪队列，然后按照一定的进程调度算法选择进程，分配CPU。1.调度队列模型就绪队列CPU阻塞队列作业调度时间片完进程调度等待事件1进程完成事件1出现队列后备阻塞队列阻塞队列等待事件2等待事件n事件2出现事件n出现……队……2020年1月19日第二章进程管理103.2调度队列模型和调度准则同时具有三级调度的调度队列模型可把进程的就绪状态分成内存就绪和外存就绪，类似地，阻塞状态也可进一步分成内存阻塞和外存阻塞，调出操作可使进程状态由内存就绪转为外存就绪，内存阻塞转为外存阻塞；中级调度可是外存就绪转为内存就绪。1.调度队列模型就绪队列CPU绪挂起队列就作业调度时间片完进程调度进程完成事件出现队列后备塞挂队队列阻阻塞队列等待事件起批量作业挂起事件出现中级调度2020年1月19日第二章进程管理113.2调度队列模型和调度准则面向用户的准则（1）周转时间短平均周转时间T的计算如下：平均带权周转时间W的计算如下：（2）响应时间快：从用户通过键盘提交一个请求开始，直到系统首次响应未知的时间尽量快；（3）截止时间的保证：是指某任务必须开始执行的最迟时间，或必须完成的最迟时间必须有保证，这是评价实时系统性能的重要指标；（4）优先权准则：遵循优先权准则让某些紧急的作业得到及时处理。2.选择调度方式和算法的若干准则niiTnT11nisiTTnW112020年1月19日第二章进程管理123.2调度队列模型和调度准则面向系统的准则2.选择调度方式和算法的若干准则（1）系统吞吐量高：这个是评价批处理系统性能的另一个重要指标，因此是选择批处理作业调度的重要准则。对于大型作业，一般吞吐量为每小时一道作业，对于中、小型作业，其吞吐量可能达到数十道。（2）处理机利用率好：CPU价格昂贵，利用率成为衡量系统性能的重要指标，一般CPU的利用率在40%到90%之间比较合理。（3）各类资源的平衡利用：不仅要使处理机利用率高，还要有效地利用其他各类资源，如内存、外存和I/O设备，适当的调度方式和算法可以使系统中的各类资源处于忙碌状态。2020年1月19日第二章进程管理133.3调度算法是一种最简单的调度算法，适用于作业调度和进程调度，每次调度都是从后备队列中选择一个或者多个最先进入该队列的作业，将它们调入内存，分配资源，创建进程，然后放入就绪队列。1.先来先服务调度算法FCFS（FirstComeFirstService）FCFS算法比较有利于长作业（进程），不利于短作业（进程）进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.992020年1月19日第二章进程管理143.3调度算法是指对短作业或者短进程优先调度的算法，适用于作业调度和进程调度，SJF算法就是从后备队列中选择一个运行时间最短的作业，然后把它们调入内存运行。2.短作业优先调度算法SJF（ShortJobFirst）SJF的优点：能有效地降低作业的平均等待时间，提高系统吞吐量；进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A030331B145982C223531.5D35914112.2SJF的缺点：1）对长作业不利；2）未考虑作业的紧迫度；3）用户估计执行时间的不准确性。2020年1月19日第二章进程管理153.3调度算法3.FCFS和SJF的性能比较算法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.12020年1月19日第二章进程管理163.3调度算法是为了照顾紧迫型作业，使之在进入系统后便获得优先处理，该算法会把处理机分配给优先级最高的作业（或者进程）。1）非抢占式优先权调度算法，适用于批处理系统或实时性要求不高的系统；2）抢占式优先权调度算法，能更好地满足紧迫作业，适合于严格的实时系统或者对性能要求较高的批处理和分时系统中。4.高优先权优先调度算法（PriorityJobFirst）2020年1月19日第二章进程管理173.3调度算法4.高优先权优先调度算法（PriorityJobFirst）优先权的类型•静态优先权：创建进程时确定，在整个运行期间保持不变；•进程类型，系统进程要比用户进程优先级高；•进程对资源的要求，要求少的优先级高；•用户要求，用户进程的紧迫程度。优点：简单易行，系统开销小缺点：不够精确，优先权低的作业（进程）长期得不到调度•动态优先权：创建时赋予，可以随着进程的而推进或随其等待事件的增加而改变，以便获得更好的调度性能。优点：使调度更加公平，调度性能高缺点：系统开销稍大2020年1月19日第二章进程管理183.3调度算法高响应比优先调度算法每个作业的优先级动态计算，作业的优先级随等待时间的增加而不断提高。4.高优先权优先调度算法（PriorityJobFirst）结论：•如果作业等待事件相同，要求服务时间越短，优先级越高，该算法利于短作业；•如果要求服务时间相同，那么等待时间越长，优先权越高，它实现的是先来先服务；•对于长作业，作业的优先级随着等待时间的增加而提高，如果等待时间足够长也可以获得处理机。优点：既照顾了短作业，又考虑了作业的先后顺序，使长作业也可以得到服务；缺点：但优先级的计算增加了系统的开销。响应比RP=等待时间+要求服务时间要求服务时间=响应时间要求服务时间2020年1月19日第二章进程管理193.3调度算法基本原理系统将所有就绪进程按照先来先服务的原则排成一个队列，每次调度把CPU分配给队首进程，并令其执行一个时间片，当执行时间片用完，调度程序停止其执行，并把它送到队列尾部。5.基于时间片的轮转调度算法（RoundRobin）时间片大小•如果太小利于短作业，但是会频繁中断，进程上下文切换，增加系统开销；•如果太大则每个进程都能在时间片内完成，则退化为FCFS算法，无法满足交互式用户的需求。2020年1月19日第二章进程管理203.3调度算法5.基于时间片的轮转调度算法（RoundRobin）(a)q=1(b)q=4123456789101112131415161718ABACBDAECBDAECABCDEECECC2020年1月19日第二章进程管理213.3调度算法5.时间片轮转法RR算法进程名ABCDE平均到达时间01234服务时间43524RRq=1完成时间1210181117周转时间1291681311.6带权周转时间333.243.253.29RRq=4完成时间47181317周转时间461610139.8带权周转时间123.253.252.892020年1月19日第二章进程管理223.3调度算法调度算法的实施过程•设置多个就绪队列，赋予不同的优先级，各个队列优先级递减，时间片递增；•新进程放入第一个队列尾部，FCFS原则排队调度，时间片内完成则撤离系统，如果没完则转入下个队列尾部，以此类推，在第n个队列采取时间片轮转调度；•第一队列空闲，调度第二队列，以此类推，新进程如果优先级高，可抢占处理机。6.多级反馈队列调度算法（RoundRobinWithMultipleFeedback）2020年1月19日第二章进程管理233.3调度算法6.多级反馈队列调度算法（RoundRobinWithMultipleFee