os_第3章处理机调度和死锁

《os_第3章处理机调度和死锁》由会员分享，可在线阅读，更多相关《os_第3章处理机调度和死锁（155页珍藏版）》请在金锄头文库上搜索。

1、南昌大学信息管理系 NanChang University,Department of information manager,操作系统 Operating System,第二部分 B 处理机调度与死锁,南昌大学信息管理系 NanChang University,Department of information manager,3.1 处理机调度的基本概念,高级调度 低级调度 中级调度,按OS的类型分：,批处理调度 分时调度和实时调度 多处理机调度等,按调度层次分：,处理机调度的基本类型：,一个作业从提交给计算机系统到执行结束退出系统，一般都要经历4个状态：提交、后备（收容）、执行和完成。,

2、1）提交状态：通过终端设备向计算机的磁盘输入作业信息时所处的状态。,2）后备状态：作业的全部信息已输入到磁盘的一个专用区(输入井)中等待作业调度时所处的状态。,3）执行状态：在后备作业队列中的作业一旦被作业调度程序选中，为它分配了必要的资源，并且建立了进程, 开始处理时所处的状态。,4）完成状态：作业完成其全部任务后，进程撤消, 做善后处理时的作业状态称为完成状态。,作业的状态,一、作业的状态及其转换,作业的状态及其转换,一、高级调度（作业调度） High Level Scheduling,决定允许哪些作业竞争系统资源。也就是说，高级调度用于决定把外存上处于后备状态的作业按照一定的算法，选取出

3、一个作业，当内存空间满足其要求时，为它分配存储空间，调入内存，创建该作业的进程，再分配它所需的I/0设备及其它资源，再将新进程排在就绪队列上，新进程具有了获得处理机的资格。,外存后备状态作业,调入内存，分配资源创建进程,就绪队列,在执行作业调度时，要做以下两步：,接纳多少个作业 接纳哪些作业,二、低级调度（Low Level Scheduling）,就绪队列进程,获得处理机,也称进程调度，它决定在就绪队列中哪一个进程将分配到处理机，并由分派程序把处理机实际分配给这个进程。,进程调度可采用下述两种方式：,非抢占方式 抢占方式 抢占原则： （1）时间片原则 （2）优先权原则 （3）短作业优先原则,

4、三、中级调度（Intermediate Level Scheduling）,目的：是为了提高内存的利用率和系统吞吐量。,四、三级调度的关系,3.1.2 进程调度队列模型,1、仅有进程调度的调度队列模型 2、具有高级和低级调度的调度队列模型 3、同时具有三级调度的调度队列模型,进程完成,CPU,进程调度,时间片完,阻 塞 队 列,就 绪 队 列,事 件 出 现,交互用户,等待事件,仅有进程调度的调度队列模型,CPU,进程 调度,作业调度,超时,就绪队列,等待事件2,事件2出现,后备作业队列,具有高,低两级调度的调度队列模型,事件n出现,事件1出现,等待事件n,等待事件1,完成,中级调度,CPU,

5、进程 调度,作业调度,完成,超时,挂起就绪队列,挂起等待队列,等待队列,就绪队列,等待事件,交互式用户,事件 出现,后备作业队列,中级调度,具有三级调度时的调度队列模型,3.1.3 选择调度方式和调度算法的若干准则,1、面向用户的准则 （1）周转时间短 （2）响应时间快 （3）截止时间的保证 （4）优先权准则,1、平均周转时间,周转时间： 由等待时间、执行时间 等组成 平均周转时间： Ti=1/nTi n=1，n为作业或进程个数。,2、带权周转时间,带权周转时间：Wi=Ti/Tr 周转时间与执行时间之比。 平均带权周转时间：W=1/n Wi n为作业或进程个数。,3、响应时间,响应时间是从用户

6、通过键盘提交一个请求开始，直至系统首次产生响应位置的时间说直到或在屏幕上显示出结果为止的一段时间间隔。包括： （1）从键盘输入的请求信息传送到处理机的时间； （2）处理机对请求信息进行处理的时间； （3）将所形成的响应回送到终端显示器的时间。,2、面向系统的准则 （1）系统吞吐量高。 （2）处理机利用率好。 （3）各类资源的平衡利用。,选择调度方式和调度算法的若干准则（续）,进程调度,进程调度的任务就是按照一定的策略负责把处理机分配给某一就绪进程。由进程调度程序具体实现处理机在进程之间的转换。,进程调度程序的功能,具体功能包括： （1）记录系统中所有进程的执行情况。 （2）进行进程上下文切换,

7、进程上下文实际上是进程执行活动全过程的静态描述，进程上下文包括计算机系统中与执行进程有关的各种寄存器的值，程序段在经过编译之后形成的机器指令代码集（正文段）、数据集及各种堆栈值和PBC结构。,进程调度的时机,进程调度的时机与引起进程调度的原因以及进程调度的方式有关。 一、引起进程调度的原因 （1）正在执行的进程执行完毕。 （2）执行中的进程提出I/O请求后被阻塞。 （3）执行某种原语操作，比如wait(s)，block原语，wakeup原语。,（4）分时系统中，由于分配给该进程的时间片已经用完。 （5）执行中进程自己调用阻塞原语将自己阻塞起来。 （6）执行完系统程序后返回用户进程时，可看作系统

8、进程执行完毕，从而可以调度选择一个新的用户进程执行。 以上是在不可剥夺方式下的引起进程调度的原因，在CPU执行方式是可剥夺时，还有一个原因。,（7）一个比正在运行进程的优先数更高的进程进入就绪队列，从而引起调度。 在以上所列的几种原因之一发生的情况下，OS进行进程调度。,进程上下文切换,进程上下文由正文段、数据段、硬件积存器的内容以及有关数据结构等组成。在发生进程调度时系统要做进程上下文切换。,进程上下文切换包括四个步骤：,（1）决定是否做上下文切换以及是否允许做上下文切换。 在OS中不是每进每刻上下文切换进程都在检查和分析是否可做上下文切换。在可剥夺方式中，是采用优先级高的进程发生信号中断正

9、在执行的优先级低的进程，从而进行上下文切换；在不可剥夺方式中可采用时间片方式，也可采用原语调用，调用上下文切换程序。,（2）保存当前执行进程的上下文 当前执行进程是指调用上下文切换程序之前的执行进程。上下文切换程序不能破坏“老”进程的上下文结构。,（3）采用进程调度算法，从就绪队列中选择一个进程。 （4）恢复或装配所选进程的上下文，把处理机分配给所选进程。,3.2 调度算法,在OS中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。,3.2.1先来先服务和短作业优先调度算法,1、先来先服务调度算法 先来先服务FCFS调度算法是一种最简单的调度算法。 作业调

10、度中采用该算法时，每次调度是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。,既可用于进程调度，也可用于作业调度,在进程调度中，采用FCFS时每次调度是从就绪队列中，选择一个最先进入该队列的进程，把处理机分配给它，使之投入运行，该进程一直运行到完成或发生某事件而阻塞后，才放弃处理机。,可见，FCFS调度算法有利于CPU繁忙型的作业， FCFS调度算法不利于I/0繁忙型作业。,FCFS在一定意义上是公平合理的。 FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。 先来先服务不能保证良好的响应时间，在处理交互用户时很少用这

11、种方法。,2.短作业（进程）优先调度算法（Shortest Job First）SJF,短作业（进程）优先调度算法SJ(P)F，是指对短作业或进程优先调度的算法。它们可分别用于作业调度(SJF)和进程调度(SPF)。,二、实例,FCFS:只考虑等待时间，而不考虑运行时间。 SPJ、SJF：根据作业（进程）占用处理机时间长短而定，注重了作业运行时间。,SJF调度算法能有效地降低作业的平均等待时间和提高系统的吞吐量。,SJ(P)F调度算法的缺点： （1）该算法对长作业非常不利。 （2）该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会得到及时处理；,（3）由于作业（进程）的长短只是根

12、据用户所提供的估计执行时间而定，而用户又可能会有意或无意地缩短其作业的估计执行时间，致使该算法不一定能真正做到短作业优先调度。,FCFS与SJF都属于非剥夺调度，不适用在合理的响应时间应得到保证的分时环境中。,FCFS与SJF属于非剥夺调度，还是可剥夺调度？,3.2.2 优先权（级）调度算法,该算法的核心是确定作业或进程的优先权。,一、优先权调度算法的类型,当用于进程调度时，把处理机分配给就绪队列中优先权最高的进程，这时又可进一步把该算法分成两种方式： 1.非抢占式优先权算法 2.抢占式优先权调度算法,二、优先权类型,设计优先权的主要原则是充分地利用处理机，使用户进程尽可能地并行运行。优先权可

13、分为静态优先权和动态优先权。,确定作业的静态优先权可根据以下原则：,（1）由用户自己根据作业的紧急程度输入一个适当的优先权。 （2）由系统或操作员根据作业类型指定优先权。作业类型可由用户约定，也可以由操作员指定。 （3）作业使用资源。,1).静态优先权,进程的静态优先权确定原则：,（1）进程类型。 （2）进程对资源的要求。 （3）根据用户的要求。 （4）将作业的静态优先权作为它所属进程的优先级。,静态优先权法简单易行，系统开销小，但不够精确，很可能出现优先权低的作业或进程，长期没有被调度的情况，而且静态优先级一旦确定之后，直到执行结束为止始终保持不变，从而系统效率较低，调度性能不高。因此，仅在

14、要求不太高的系统中才使用静态优先权。,2).动态优先权,动态优先权把作业或进程的静态特性和动态特性结合起来确定作业或进程的优先权，随着作业或进程的执行过程，其优先权不断变化。,动态优先权的确定原则：,（1）根据进程占有CPU时间的长短来决定。 （2）根据就绪进程等待CPU的时间长短来决定。,3 高响应比优先调度算法 (High Response-ratio Next),Brich Hansen发展的最高响应比优先调度策略修正了最短作业优先调度的某些弱点，特别是后者忽视长作业，优待新的短作业的弱点。,HRN是一种非剥夺调度,优先权的变化可描述为：,该算法既照顾了短作业，又考虑了作业到达的先后次序

15、，也不会使长作业长期得不到服务，是介于FCFS与SJF之间的一种算法，由于每次调用前，都要先进行响应比的计算，这会增加系统的开销。,3.2.3基于时间片的轮转调度算法 （Round Robin）,一、基本原理 系统将所有的就绪进程按先来先服务原则，排成一个队列，每次调度时把CPU分配给队首进程，并令其执行一个时间片，当执行的时间片用完时，由计时器发出时钟中断，调度程序根据这个信号来停止该进程的执行，把它放到就绪队列的末尾，等待下一次执行；然后再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就保证就绪队列中的所有进程，在一个给定的时间内，均能获得一时间片的处理机执行时间。,

16、轮转法只能调度分配可抢占的资源，而作业调度是对除了CPU之外的所有系统硬件资源的分配，其中包含有不可抢占资源，比如说打印机，所以作业调度不使用轮转法,也就是说轮转法只适用于进程调度。,轮转法能否用于作业调度?,二、时间片大小的确定,1、系统对响应时间的要求 响应时间T与用户进程N和时间片q成正比，T=Nq。 当进程数目一定时，时间片量值与系统响应时间成正比。,轮转法的性能几乎完全 取决于时间片,2、就绪队列中进程的数目 T=Nq 3、系统的处理能力,系统的处理能力是必须保证用户键入的常用命令能在一个时间片内处理完毕，否则将无法保证得到满意的响应时间，而且会使平均周转时间及带权周转时间都很长。,在时间片轮转法中，就绪进程按照先来先服务的原则排队，每个进程轮流地运行大小相等的时间片，对短作业和I/O操作较高的作业是不利的。如果有紧急进程进入就绪队