第四章调度修改版11.doc

一、单项选择题，在四个备选答案中选一个合适的答案1多道程序设计系统中，让多个计算问题同时装入计算机系统的主存储器( A )。 A并发执行 B顺序执行 c.并行执行 D同时执行2引入多道程序设计技术后，处理器的利用率( B )。 A有所改善 B极大地提高 c.降低了 D无变化，仅使程序执行方便3计算机系统采用多道程序设计技术后，（ C )。A缩短了每个程序的执行时间 B系统效率随并行工作道数成比例增长 C提高了系统效率 D使用设备时不会发生冲突4进程是(D )。A一个系统软件 B与程序概念等效 C存放在内存中的程序 D执行中的程序5进程的( A )和并发性是两个很重要的属性。 A动态性 B.静态性 c易用性 D顺序性6( B )是完成操作系统功能的进程。 A，用户进程 B系统进程 C并发进程 D编译进程7已经获得除( c )以外所有运行所需资源的进程处于就绪状态。 A主存储器 B打印机 CCPU D磁盘空间8在一个单处理器单核系统中，处于运行态的进程( C )。 A可以有多个 B不能被打断 c只有一个 D不能请求系统调用9对于一个单处理器系统来说,允许若干进程同时执行，轮流占用处理器称它们为（ D)的。 A.顺序执行 B.同时执行 C.并行执行 D.并发执行10操作系统根据( B )控制和管理进程，它是进程存在的标志。 A程序状态字 B进程控制块 C中断寄存器 D中断装置11若干个等待占有CPU并运行的进程按一定次序链接起来的队列为( D )。A运行队列 B后备队列 C等待队列 D就绪队列12用户从终端上输入一条命令，即产生了( c )。 A程序性中断事件 B外部中断事件 C输入输出中断事件 D自愿性中断事件16当出现中断事件后，必须( a )才能把断点的信息保护起来。 A把当前PSW放到旧Psw B把旧Psw放到当前PSw C把新PSW放到当前PSw D所有PSw保持不变17.中断处理程序占用处理器的执行时，要从( B )取出信息，才能分析中断发生的原因 A当前PSW B旧PSW c新PsW D.当前指令的操作码19中断处理程序在保护现场和分析中断原因后，一般会请求系统创建相应的处理事件进程，排入( D )。 A等待队列 B运行队列 c后备队列 D就绪队列20中断优先级是按照中断事件的重要性和紧迫程度来确定的，是在( A )。 A硬件设计时固定下来的 B作业说明书中申请的 C动态分配的 D由中断装置确定的21采用中断屏蔽技术，会封锁( c)的响应。A比自己级别高的中断事件 B比自己级别低的中断事件C与自己级别相同的中断事件 D与中断屏蔽标志相对应的事件23中断程序可以有选择地设置屏蔽位，但( c)是不能屏蔽的。 .A比自己级别低的中断事件 B和自己级别相同的中断事件 C自愿中断事件 d.输入输出中断事件24为了根据进程的紧迫性做进程调度，应采用( b)。A先来先服务调度算法 B，优先数调度算法 C时间片轮转调度法 D分级调度算法25采用时间片轮转法调度是为了( a)。 A多个终端都能得到系统的及时响应 B先来先服务 C优先数高的进程先使用处理器 D紧急事件优先处理 27当一进程运行时，系统强行将其撤下，让另一个更高优先数的进程占用处理器，这种调度方式是(B )。 A.非抢占方式 B抢占方式 C.中断方式 D查询方式29操作系统使用( D)机制使计算机系统能实现进程并发执行，保证系统正常工作。A中断 B查询 c同步 D互斥30（ b）是按某种算法，从就绪队列中挑选一个进程，并向它移交处理器的控制权。A作业调度 B进程调度 C磁盘调度 D中级调度31实时系统中的进程调度，通常采用 （C） 算法。A先来先服务 B时间片轮转C抢占式的优先级调度 D短作业优先 34某系统中预计有50个用户同时上机，为使每个用户能在2秒内得到响应，时间片最大限度应为（ c ）。A20ms B30 ms C40 ms D50 ms二、填空题 1在多道程序设计的系统中，应采用_并发执行_的方法保证各道程序互不侵犯2在多道程序设计的系统中必须对_进程_按一定的策略进行分配和调度。 3采用多道程序设计技术后可有效地提高系统中资源的_利用率_，增加单位时间的算题量，从而提高了系统的_吞吐量_。4多道程序设计提高了系统的吞吐量但可能会_延长_某些程序的执行时间。 5程序是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合。；进程是程序在并发环境中的执行过程。6完成操作系统的进程称为_系统进程_，完成用户功能的进程称为_用户进程_。 12进程的四个属性为：_动态性_，_并发性_，_非对应性_，_异步性_。14进程的三种基本状态为：就绪态、_阻塞态_和运行态。 15进程状态变化时，运行态和_阻塞态_、都有可能变为_就绪态_。 16同时执行的进程是_互斥_占用处理器的，这些进程可称为并发执行的。 17进程控制块应包括标识信息、_描述信息_、_控制信息_和管理信息。 18每个进程都是有生命期的,即从_生成_到消亡。 19操作系统依据_进程控制块_对进程进行控制和管理。 20进程有三种基本队列方式：_线性_，_链接_和_索引_ 。 27中断响应的三项工作为检查终止当前程序的执行, _保存原程序的断点信息_和_转到相应的处理程序_28中断装置要通过检查_中断源（旧psw）_才能识别是否有中断事件发生。29程序状态字主要包括程序的基本状态、_优先级_和_访问方式_等多个内容。 31中断处理程序占用处理器后，只要从_中断源（旧psw）_中取出中断码。分析后完成中断事件的处理。 32保护_现场 _是中断处理的主要工作之。 34中断优先级是按中断事件的_优先权_来确定的。 37中断处理程序通常只屏蔽比自己级别_低_的中断事件，而_等级高的中断事件_是不能屏蔽的。 38_中断处理_程序按照某种调度算法从就绪队列中选出一个进程，让它占用处理器。38 常用的进程调度算法有先来先服务、_优先级_、_轮转法_等算法。 40采用优先级调度算法时，一个高优先级进程占用处理器后可有_非抢占式优先级_或_抢占式优先级_两种处理方式。 41_时间片_是规定进程一次使用处理器的最长时间。 42进程调度算法的选择准则有_吞吐量_、处理器利用率、_周转时间_、响应时间和_就绪等待时间_。 44处理器的三级调度是指作业调度，中级调度和_低级调度_或称作_进程调度_。45进程调度采用抢占方式时，常用的抢占原则有3种，_rr（时间片轮转）_、_srtf（最短剩余时间优先）_、和_mfq（多级反馈队列）_。 47在动态优先权调度的系统中，如果某个进入就绪队列的进程的优先权高于正在运行的进程时，系统采用抢占方式，将_cpu_分配给优先权高的进程使之执行。48常用的实时调度算法，_优先级随速率单调的调度算法_和_最早截止时间优先调度算法_。三、判断改错题判断下列各题正误，正者打“”，误者打“”，并将具体修改内容写在该题的下面，但有下划线部分不能改。1引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量，因此也可以把它归入到主存管理。（错 ）2在实时要求严格的实时系统中进程调度采用非抢占方式。（错 ）四、简答题1进程调度需要完成哪些功能？P97 （1）保存现场；（2）挑选进程；（3）恢复现场。2实时调度常用哪些调度算法？它们适用什么场合？优先级随速率单调的调度算法最早截至时间优先调度算法3高级调度与低级调度的主要任务是什么?为什么要引入中级调度?高级调度：根据一定算法，分配必要得资源。低级调度：根据一定的算法，将cpu分派给就绪队列中的一个进程。为使内存中同时存放的进程数目不致太多，有时需要把某些进程从内存中移到外存中，以减少多道程序的数目。4在作业调度中需做出哪些决定?接纳多少个作业接纳哪些作业5在可抢占调度方式中,有哪些抢占原则? 时间片轮转法，最短剩余时间优先法，多级反馈队列法6在系统中引起进程调度的主要因素有哪些?设计目标，公平性，均衡性，统筹兼顾，优先级，开销7选择调度方式和调度算法时，应遵循的准则是什么?CPU利用率，吞吐量，周转时间，就绪等待时间，响应时间8为什么说多级反馈队列能较好地满足各种用户的需要?多级反馈队列调度算法即能使高优先级的作业得到响应又能使短作业(进程)迅速完成。多级反馈队列调度算法描述： 1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。 2、首先调度优先级高的队列中的进程。3、对于同一个队列中的各个进程，按照时间片轮转法调度。 4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。9在批处理系统，分时系统和实时系统中，各采用哪几种进程(作业)调度算法? 10在按时间片轮转调度算法中，在确定时间片的大小时，应考虑哪些因素?a. 系统对相应时间的要求； b. 就绪队列中进程的数目； c. 系统的处理能力11为实现实时调度，对实时系统提出了哪些要求?a. 要提供必要的调度信息； b. 在调度方式上要具体情况具体分析； c. 要具有快速响应外部中断的能力； d. 快速任务分派12 在多处理机系统中，比较有代表性的线程调度方式有哪几种?1，负载共享 2，成组调度 3。专用处理器分配 4，动态调度13在解决死锁问题的几个方法中，哪种方法最容易实现?哪种方法使资源的利用率最高? 预防死锁是最容易实现的； 避免死锁使资源的利用率最高14简述处理机三级调度分别完成什么工作？15什么是多道程序设计系统? 多道程序设计是在内存中间时存放多道程序，它们在管理程序的控制下交替地在CPU上运行。16多道程序设计系统中应注意些什么? 多道程序设计系统必须做好存储保护、程序浮动、资源分配及管理工作。17多道程序设计从哪几方面提高系统的效率? 多道程序设计从三个方面提高系统的效率：减少cPU的空闲时间，提高处理器的利用率。合理搭配程序，充分利用外围设备资源。发挥处理器与外围设备，以及外围设备之间的并行工作能力。18什么是进程?为什么要引入进程的概念? 进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。它是操作系统动态执行的基本单元，在传统的操作系统中，进程既是基本的分配单元，也是基本的执行单元。引入进程概念是为了封装和分治、19简述进程的三种基本状态及其变化情况1.等待态：等待某个事件的完成； 2.就绪态：等待系统分配处理器以便运行； 3.运行态：占有处理器正在运行。 运行态等待态 往往是由于等待外设，等待主存等资源分配或等待人工干预而引起的。 等待态就绪态 则是等待的条件已满足，只需分配到处理器后就能运行。 运行态就绪态 不是由于自身原因，而是由外界原因使运行状态的进程让出处理器，这时候就变成就绪态。例如时间片用完，或有更高优先级的进程来抢占处理器等。 就绪态运行态 系统按某种策略选中就绪队列中的一个进程占用处理器，此时就变成了运行态20进程与程序有何区别? 程序是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合，是静态的。进程是程序在并发环境中的执行过程，是动态的。21进程由哪三部分组成? 进程由程序、数据集和进程控制块三部分组成。22操作系统根据什么控制和管理进程?为什么? 操作系统根据进程控制块控制和管理进程。因为进程控制块是进程存在的标志，它记录了进程执行时的变化情况。23简述中断事件的类型。答：1. 中断中断包括非屏蔽中断和可屏蔽中断两类。它们都是在当前指令执行完后才服务的，中断服务完后，程序继续执行紧跟在被中断指令之后的下一条指令。2.异常(内中断，软中断)1) 指令引起的异常2) 处理器检测的异常 25中断事件的处理应做哪几件事? 答：保存被中断程序的现场，分析中断原因，转入相应处理程序进行处理，恢复被中断程序现场（即中断返回）27进程优先数可以固定也可动态变化，说说动态变化的考虑因素。进程优先数可以固定也可动态变化，说说动态变化的考虑因素。优先数随进程执行而动态变化可考虑以下因素：提高经常使用外围设备进程的优先数，有利于利用处理器与外围设备的并行能力；提高在较长时间内未使用处理器的就绪进程的优先数，以缩短等待处理器的平均时间。28中断系统有何作用? （1）实现并行处理； （2）实现实时处理； （3）实现故障处理。1提高主机的利用率，使高速CPU可以和低速的外部设备并行工作2及时进行事故处理。3实现分式操作4实现实时操作5方便程序调试29进程调度有何功能?有哪些常用的调度算法? 1、保存现场2、挑选进程3、恢复现场 31作业调度与进程调度有什么区别？作业调度是宏观调度，它所选择的作业只具有获得cpu的资格，但尚未占用cpu，不能立即投入运行。而进程调度是微观概念，它根据一定算法，动态的把cpu实际的分配给所选择的进程，使之真正活动起来。进程调度必须相当频繁地为CPU选择进程。另一方面，作业调度执行的次数很少，新作业到达系统的间隔可以是几分钟。32系统中的各种进程队列都是由进程的PCB链接而成的。当一个进程的状态从阻塞变为就绪状态时，它的PCB从哪个队列移到哪个队列？它所对应的程序也要跟着移来移去吗？为什么？Pcb也是从阻塞队列移到就绪队列，对应的程序是不移动的。因为（pcb概念）33为什么说响应比高者优先作业调度算法是对先来先服务以及短作业优先这两种调度算法的折中？高响应比优先法是一种非抢占方式。RR响应比：w是进程等待处理机所用的时间，s是进程要求的服务时间。由于w+s就是系统对该进程的响应时间，所以RR 就是进程的响应比。在调度进行时，以个进程的响应比作为其优先级，从中选出级别最高的进程投入运行。在进程等待时间固定的情况下，该算法有利于短进程，因为s越小，W/S的值越大，当要求服务时间s相同时，等代时间w越长的进程其优先级越高，从而实现先来先服务策略。对于长作业，随着其等待时间的延长，相应的优先级可以上升，而避免饥渴。34短作业优先调度算法总能得到最小的平均周转时间吗？为什么？五、应用题1在单道批处理系统中，假设有四道作业，它们的情况描述如下：作业号提交时间运行时间（分）开始执行时间完成时间18:003028:102038:20548:3010约定系统从8：00开始调度，要求：（1） 计算这批作业在（FCFS）先来先服务算法时的作业平均周转时间T、作业平均带权周转时间W。 （2） 计算这批作业在（SJF）短作业优先算法时的作业平均周转时间T、作业平均带权周转时间W。 （1） 计算这批作业在（FCFS）先来先服务算法时的作业平均周转时间T、作业平均带权周转时间W。 T=35 W=3.375（2） 计算这批作业在（SJF）短作业优先算法时的作业平均周转时间T、作业平均带权周转时间W。T=28.75 W =2.06252假设有四道作业，他们的提交时间和执行时间由下表给出。请计算在单道程序环境下，用先来先服务调度算法(FCFS)和最短作业优先调度算法(SJF)时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。（从相对时间0开始调度）作业名提交时刻（时）执行时间（小时）A04B15C22D33E44先来先服务调度算法： 平均周转时间 平均带权周转时间最短作业优先调度算法：平均周转时间 平均带权周转时间解：（1） 先来先服务调度算法： A:4B:6C:9D:8E:14平均周转时间=(4+6+9+8+14)/5=8.2平均带权周转时间=（4/4+6/5+9/2+8/3+14/4）/5=2.57（2）最短作业优先调度算法：A:4B:8C:9D:11E:14平均周转时间=9.2平均带权周转时间=(1+2+2.25+2.75+3.5)/5=2.34在一个两道作业的操作系统中，设在一段时间内先后到达4个作业，它们的提交时刻和运行时间由下表给出。若作业调度采用短作业优先的调度算法，进程调度采用优先权调度算法（数值越小，优先级越高）。（1）完成下列表格（2）计算平均周转时间、平均带权周转时间（小数点后保留两位）进程名到达时间估计运行时间优先数进入内存时间完成时间周转时间带权周转时间A045B233C354D526进程名到达时间估计运行时间优先数进入内存时间完成时间周转时间带权周转时间A0450777/4B2332531C35451077/5D5267942(2)平均周转时间 21/4平均带权周转时间 3+63/205上题中，若作业调度采用短作业优先的调度算法，进程调度采用以优先权为基础的抢占式调度方式（数值越小，优先级越高）。完成下表：进程名到达时间估计运行时间优先数进入内存时间完成时间周转时间带权周转时间A045B233C354D526进程名到达时间估计运行时间优先数进入内存时间完成时间周转时间带权周转时间A0450441B2334751.66C35471291.80D52681052.506单道批处理系统中，一批作业的到达和要求运行时间如下：作业到达时间(时)所需运行时间(小时)18.00.528.20.438.20.248.40.358.50.2（1） 采用SJF算法进行调度（2） 采用HRF算法进行调度分别指出调度顺序，计算平均周转时间T和平均带权周转时间W。（同等条件下，按FCFS原则调度）短作业优先法sjf作业到达时间(时)所需运行时间(小时)开始时间完成时间周转时间带权周转时间18.00.58.038.20.28.28.40.2158.50.28.48.60.10.548.40.38.68.90.55/328.20.48.99.31.12.7518.00.39.39.81.83.6平均周转时间T=0.74h带权平均周转时间W=2.454h作业到达时间(时)所需运行时间(小时)开始时间完成时间周转时间带权周转时间RR18.00.58.08.50.51128.20.48.58.90.71.751.7538.20.28.99.10.94.54.548.40.39.19.41.03.333.3358.50.29.49.61.15.55.5平均周转时间T=0.6h平均带权周转时间W=3.136h 8设有PA,PB，PC,Pd四个进程同时依次进入就绪队列它们所需的处理器时间和优先数如下表所示： 进程 处理器时(秒) 优先数 若不计调度等所消耗的时间。请回答：(1)分别写出采用“先来先服务”和“非抢占式的优先数”调度算法选中的进程执行的次序(2)在上述两种算法下，分别算出每个进程在就绪队列的等待时间和平均等待时间。答：（1）进程执行次序为：先来先服务：PA,PB,PC ,PD;非抢占式的优先数法：PC,PB,PD,PA;(2)先来先服务法：每个进程在就绪队列的等待时间分别为：PA:0秒；PB:0+20=20秒；PC:20+15=35秒；PD：35+10=45秒；平均等待时间为（0+20+35+45）/4=25秒；非抢占式的优先数法：每个进程在就绪队列中的等待时间为：PA：25+12=37秒；PB：0+10=10秒；PC：0秒；PD：10+15=25秒；平均等待时间为（37+10+0+25）/4=18秒9有三个作业：进程名到达时间估计运行时间优先数开始时间完成时间周转时间带权周转时间10.08520.44331.014分别采用先来先服务和短作业优先作业调度算法。试问它们的平均周转时间各是什么？你是否还可以给出一种更好的调度算法，使其平均周转时间优于这两种调度算法？（1）采用先来先服务作业调度算法时的实施过程如下。作 业到达时间所需CPU时间开始时间完成时间周转时间10.080.08.08.020.448.012.011.631.0112.013.012.0这时，作业的调度顺序是123。其平均周转时间为：（8 + 11.6 + 12）/ 3 = 10.53（2）采用短作业优先作业调度算法时的实施过程如下。作 业到达时间所需CPU时间开始时间完成时间周转时间10.080.08.08.031.018.09.08.020.449.013.012.6这里要注意，在作业1运行完毕进行作业调度时，作业2和3都已经到达。由于是实行短作业优先作业调度算法，因此先调度作业3运行，最后调度作业2运行。所以，这时的作业调度顺序是132。其平均周转时间为：（8 + 8 + 12.6）/ 3 = 9.53（3）还可以有更好的作业调度算法，使其平均周转时间优于这两种调度算法。例如，如果知道在作业1后面会来两个短作业，那么作业1到达后，先不投入运行。而是等所有作业到齐后，再按照短作业优先作业调度算法进行调度，具体实施过程如下。作 业到达时间所需CPU时间开始时间完成时间周转时间31.011.02.01.020.442.06.05.610.086.014.014.0这时的作业调度顺序是321。其平均周转时间为：（1 + 5.6 + 14）/ 3 = 6.8710设有一组作业，它们的到达时间和所需CPU时间如下所示。作业号到达时间所需CPU时间19:0070分钟29:4030分钟39:5010分钟410:105分钟分别采用先来先服务和短作业优先作业调度算法。试问它们的调度顺序、作业周转时