操作系统第六章处理机调度

1、第六章 处理机调度 为了提高处理机的效率，处理机采用多级调度。 用户作业从进入系统成为后备作业开始，直到运行结束退出系统为止，需要经过不同级别的调度。 批处理OS可能经历作业调度、进程调度、线程调度 分时OS 可能经历进程调度、线程调度6.2作业调度作业调度作业可以是一次计算，一个控制过程。作业的状态：1. 后备状态：作业在辅存上，并建立JCB，等待调度；2. 执行状态：作业进入主存，到作业计算完成为止；3. 完成状态：从作业计算完成开始，到善后处理完毕并退出系统为止。例如：1. 后备状态：在家拿到大学录取通知书2. 执行状态：到大学报道注册3. 完成状态：完成答辩后，归还资源到毕业离校6.2

2、作业调度作业调度作业调度的功能主要是完成作业从后备执行和执行完成状态的转变。其中主要的是按一定的调度算法，从后备作业队列中选出一个作业投入运行。执行就绪等待后备完成作业调度作业调度执行状态当作业处于执行状态时，其对应的进程不一定处于执行状态。进程调度6.2.4调度算法性能的衡量 调度目标主要有一下四点：1. 对所有作业应该是公平合理的；2. 应使设备有高的利用率；3. 系统吞吐量大；4. 有较快的响应时间； 但这些目标本身有些是相互冲突的。6.2.4调度算法性能的衡量 通常用平均周转时间和平均带权周转时间衡量作业调度算法的好坏。1、平均周转时间t= 其中：ti=tcitsiti是作业的周转时间

3、;tci是作业i的完成时间(closure);tsi是作业i进入系统的时间;i=1nti 1 n6.2.4调度算法性能的衡量 通常用平均周转时间和平均带权周转时间衡量作业调度算法的好坏。2、平均带权周转时间w= 其中：wi=ti/triti是作业i的周转时间tri是作业i的执行时间i=1nwi 1 n6.2.5作业调度算法1.先来先服务调度算法（FCFS算法）思想：作业按来到的先后次序进行调度例如：下列作业序列采用FCFS算法（为方便计算采用十进制），分别计算平均周转时间和平均带权周转时间。作业作业进入系统时间进入系统时间tsi执行时间执行时间tri开始时间开始时间完成时间完成时间 tci周转

4、时间周转时间 ti=tci-tsi带权周转时间带权周转时间Wi=ti/tri18.002.008.0010.002.001.0028.500.5010.0010.502.004.0039.000.1010.5010.601.601649.500.2010.6010.801.306.6调度次序1234 t=1.725 w=6.875特点：对短作业不利6.2.5作业调度算法2.短作业优先调度算法（SJF算法）思想：从后备作业中选择执行时间最短的作业作为下一次服务的对象。例如：下列作业序列采用SJF算法（为方便计算采用十进制），分别计算平均周转时间和平均带权周转时间。作业作业进入系统时间进入系统时间

5、tsi执行时间执行时间tri开始时间开始时间完成时间完成时间 tci周转时间周转时间 ti=tci-tsi带权周转时间带权周转时间Wi=ti/tri18.002.008.0010.002.001.0028.500.5010.3010.802.34.6039.000.1010.0010.101.101149.500.2010.1010.300.84调度次序1342 t=1.55 w=5.15缺点：只照顾短作业的利益，而不考虑长作业的利益。6.2.5作业调度算法作业调度算法3、响应比高者优先调度算法（介于二者之间的一种折中算法）响应比rp=响应时间/执行时间响应时间=等待时间+执行时间rp=1+等

6、待时间/执行时间 或rp=等待时间/执行时间当调度时，需计算后备作业的响应比，然后选择响应比最高者投入运行。作业作业进入系统时间进入系统时间tsi执行时间执行时间tri开始时间开始时间完成时间完成时间 tci周转时间周转时间 ti=tci-tsi带权周转时间带权周转时间Wi=ti/tri18.002.008.0010.002.001.0028.500.5039.000.1049.500.20开始时，调度作业1投入运行。当作业1结束时，需要计算后备队列作业的响应比。当作业1结束时：rp2=(10.00-8.50)/0.5=3rp3=(10.00-9.00)/0.1=10rp4=(10.00-9.

7、50)/0.2=2.5作业3投入运行作业作业进入系统时间进入系统时间tsi执行时间执行时间tri开始时间开始时间完成时间完成时间 tci周转时间周转时间 ti=tci-tsi带权周转时间带权周转时间Wi=ti/tri18.002.008.0010.002.001.0028.500.5039.000.1010.0010.101.11149.500.20当作业3结束时：rp2=(10.10-8.50)/0.5=3.2rp4=(10.10-9.50)/0.2=3作业2投入运行，最后作业4运行作业作业进入系统时间进入系统时间tsi执行时间执行时间tri开始时间开始时间完成时间完成时间 tci周转时间周

8、转时间 ti=tci-tsi带权周转时间带权周转时间Wi=ti/tri18.002.008.0010.002.001.0028.500.5010.1010.602.14.239.000.1010.0010.101.11149.500.2010.6010.801.36.5调度次序1324t=1.625 w=5.675缺点：每次需要调度时都要计算响应比，较复杂。2、在一个多道程序设计系统中，有3个作业A,B,C，到达输入井的时间如下：进程到达时间运行时间（小时）开始执行时间完成时间周转时间（分）A7：501.5（(90分)B8：000.4（24分）C8：301（60分）系统在9:00开始按响应比高

9、者优先算法对它们进行调度，请计算该作业序列的平均响应时间。3、有j1,j2,j3三个作业同时到达，执行时间分别为a,b,c且abc,试证明SJF算法能够获得最小的平均周转时间。课堂练习课堂练习1、P 157 6.6 FCFS算法：t=2.025 w=4.225 SJF算法： t=1.8375 w=3.28752.在一个多道程序设计系统中，有3个作业A,B,C，到达输入井的时间如下：进程到 达 时间运行时间（小时）开始执行时间完成时间周 转 时 间（分）A7：501.5（(90分)9:2410:543:04（184分)B8：000.4（24分）9:009:241:24（84分）C8：301（60

10、分）10:5411:543:24（204分）系统在9:00开始按响应比高者优先算法对它们进程调度，请计算该作业序列的平均响应时间。分析：响应比=等待时间/执行时间9:00时，rpA=70/90=7/9，rpB=60/24=5/2，rpC=30/60=1/2，作业B执行9:24时，rpA=94/90=47/45， rpC=54/60=9/10，作业A执行周转时间=完成时间到达时间，t=（184+84+204）/3=157分。6.3进程调度一：进程调度的功能将进程按一定的策略从就绪队列中移出并建立它执行的机器状态。二、进程调度的时机可能有以下几种情况1.正在执行的进程执行完毕；2.执行的进程因中断

11、调用、自陷、请求I/O服务等而阻塞；3.在分时系统中，进程分配的时间片用完；4.在可剥夺方式中，有优先级更高的进程要求处理；6.3进程调度三：进程调度方式当有优先级更高的进程进入就绪队列时，如何分配处理机？1、非剥夺方式：让正在执行的进程继续执行，直到该进程完成或因某事件而进入“等待”时，才把处理机分配给优先级更高的进程。2、可剥夺方式：当优先级更高的进程一到，便暂停正在执行的进程，立即把处理机分配给它。3、选择可抢占策略：每个进程不仅有优先级，而且还有一对标志（U、V）U=1，表示该进程可以抢占另一进程U=0，表示该进程不可抢占另一进程V=1，表示该进程可以被另一进程抢占V=0，表示该进程不

12、可被另一进程抢占U、V的值可根据进程的动态特征由系统临时提交，这样，就使抢占方式具有一定的灵活性。例如： :表示该进程可以抢占另一进程，但不 能被其它的进程抢占。UV106.3.4进程优先数调度算法思想：把处理机分配给就绪队列中优先权最高的进程。1.不可抢占优先权算法2.可抢占优先权算法优先权的处理较为关键一静态优先权在进程建立时确定，且规定它在进程的整个运行期间保持不变。确定优先权的依据有： 进程所需资源的要求。如进程的执行时间及内存需要量少的应赋予较高的优先权。 进程类型。如系统进程的优先权应高于用户进程。 根据用户类型。如按用户付费用的多少来确定优先权。6.3.4进程优先数调度算法二 .

13、 动态优先权在进程创建时所赋予的优先权，可以随着进程的推进而改变，以便获得更好的调度性能。P155 UNIX系统中优先数的计算优先数P_pri=min127,P_cpu/16-P_nice+PUSER优先数P_pri越大，则优先级越小。PUSER是固定偏置常数，定为100P_nice的值默认为20，可以用命令nice设置P_cpu的值可变，当时钟信号到来时，当前进程的P_cpu+1,直到255，而每过1S，内核中计算优先数的程序又将所有进程的P_cpu-10，当P_cpu10时，P_cpu置0。这样的负反馈过程使系统中在用户态下运行的各个进程都能比较均衡地享用处理机。P_cpu P_pri 进

14、程优先级 进程被调度的机会进程被调度的机会 进程优先级 P_pri P_cpu6.3.5循环轮转调度 在分时系统中，系统规定1个时间片，每个进程被调度时分得1个时间片，当这一时间片用完时，该进程就转为就绪态并进入就绪队列的末端。6.3.5循环轮转调度1. 简单循环轮转调度 时间片q固定，q=t/n t为用户可接受的响应时间 n为进入系统的最大进程数 如t=3s,n=100,则q=30ms如果q太大，则退化为FIFO算法如果q太小，则会导致系统开销的增加。切换占时间片10%。q的值通常为几百ms6.3.5循环轮转调度循环轮转调度2、可变时间片轮转调度例如：t=3s,n=6如图所示此时q1=3s/

15、6=500ms在轮转过程中，如果有新的进程到达，都暂时不进入就绪队列。如果此时到达24个进程，经过一轮后，n=24+6=30此时q2=3/30=100ms。可以减少系统开销。CPUPCB1PCB2PCB6就绪队列6.3.6多级反馈队列调度多级反馈队列调度1.当上一个队列空时，才调度下一个队列；2.当1个进程的时间片用完时，进入下一个就绪队列；3.当进程由等待变成就绪时，进入第1个队列；这种算法可以先用较小的时间片处理完那些需时间较短的进程，而给那些需时间较长的进程分配较大的时间片，以免较长的进程频繁中断而影响处理机的效率。CPU就绪队列1就绪队列2就绪队列n时间片 q 2q: 2nq优先权高低

16、:假设一个计算机系统具有如下特征：处理一次中断，平均耗用1ms;一次进程调度，平均需要2ms;将CPU分配给选中的进程，又需要平均1ms;再假设其定时器芯片每秒产生100次中断，请回答：操作系统将百分之几的CPU数据用于时钟中断处理？如果操作系统采用轮转法调度，10个时钟中断为1个时间片。那么，操作系统将百分之几的CPU时间用于进程调度（包括调度，分配CPU和引起调度时的时钟中断处理时间）？解：1001ms/1s10%时间片的大小10（1S/100）=100ms /每10ms产生1个时钟中断信号1个时间片要处理10个时钟中断，需要101ms=10ms时间片到后再进行一次进程调度，需要2ms再将

17、CPU分配给选中的进程，又需要平均1ms系统将CPU时间的（1012）/10013%用于进程调度。4.2.5线程概念及特点（threads） 自60年代提出进程的概念后，在OS中一直都是以进程作为能独立运行的基本单位。直到80年代中期，人们又提出了一个比进程更小的能独立运行的基本单位线程，用来提高系统的并发执行程度，从而提高系统的吞吐量。4.2.5线程概念及特点（threads）一什么是线程进程的两个基本属性1. 进程是一个可拥有资源的独立单位。2. 进程又是一个可以独立调度和分配CPU的基本单位。 由于进程是一个资源拥有者，因而在进程的创建、撤销和切换中，涉及资源的释放，系统必须付出较大的时

18、空开销。正因如此，在系统中所设置的进程数目不宜过多，进程切换的频率也不宜过高，但这也限制了并发程度的进一步提高。4.2.5线程概念及特点（threads） 如何使多个程序更好的并发执行，同时又尽量减少系统的开销，成为设计操作系统所追求的重要目标。 进程作为资源分配的基本单位 线程是在进程内用于调度和占有CPU的基本单位。 每个线程可以用一个现场（context）表示，现场由PC,GR,PSW组成，这样线程切换时，就不涉及资源的分配和释放。二、二、线程的描述线程的描述 系统为每个线程都配置一张线程控制块（TCB）。TCB包括：Tid ,Context,栈，用于调度的信息（优先级、状态）和有关I/

19、O活动的信息。指针指针1指针2指针3 pid TCB1TCB2TCBnPCB代码段数据段堆栈段 PTDB段(Per Threads Data Area)IBM OS/2系统中允许每个进程最多可创建255个线程。二、二、线程的描述线程的描述1. 当1个进程执行时，它只有一个线程，如果需要进程可以继续创建新的线程，也就是一个进程可以包含多个控制线程，每个线程运行进程中的一个程序段，这样，进程就有多个执行路径，增强了并行处理能力。2. 线程完全继承父进程占有的资源，当它活动时具有自己的运行现场。指针指针1指针2指针3 pid TCB1TCB2TCBnPCB代码段数据段堆栈段 PTDB段(Per Th

20、reads Data Area)IBM OS/2系统中允许每个进程最多可创建255个线程。三、线程与进程的比较1. 调度： 线程作为CPU调度的基本单位，进程作为资源调度的基本单位。 在同一进程中，线程的切换不会引起进程的切换；由一个进程的线程切换到另一个进程的线程时，将会引起进程的切换。三、线程与进程的比较2. 并发性： 在引入线程的OS 中，不仅进程之间可以并发执行，而且一个进程中的多个线程之间也可并发，因而使OS具有更好的并发性，从而能更有效地使用系统资源和提高系统的吞吐量。三、线程与进程的比较3. 拥有资源： 进程是拥有资源的一个独立单位；线程自己不拥有系统资源（也有一点必不可少的资源

21、），但可访问其隶属进程的资源。即一个进程的代码段、数据段及系统资源可供同一进程的所有线程共享。三、线程与进程的比较4. 系统开销： 线程切换只需保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。进程切换的开销远大于线程切换的开销。四、四、线程的状态及变迁线程的状态及变迁1. 创建：建立的新生线程处于新建状态，已完成初始化。2. 就绪：进入线程就绪队列，一旦分到CPU时间，就可立即运行。3. 运行：一个线程正占用CPU，执行它的程序。4. 等待：让出CPU，暂时终止自己的执行，进入等待状态。5. 终止：一个线程已经退出，但该信息还未被其他线程所收集。创建就绪执行等待终止线程调度6.4线程

22、调度线程调度采用优先数调度算法1. 当优先级不同时，采用可抢占式线程调度2. 当优先级相同时，采用轮转调度。例题1.期末试题作业调度（响应比）+进程调度例题2.期末试题作业调度（SJF）+进程调度习题课：1、在一个两道批处理系统中，有一作业序列，其到达时刻/估计运行时间列表及优先数如下。 作业 到达时刻（时） 估计运行时间（分钟） 优先数 JA 10:00 40 5 JB 10:20 30 3 JC 10:30 50 4 JD 10:50 20 6 JE 11:00 30 2假设作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法（表中所列优先数即为进程优先数，数值越小优先级越高）。 列出各作