华中科技大学 操作系统课件全集

第六章多处理器系统(xìtǒng)和处理器管理精品资料掌握多处理器分类调度的层次调度算法的性能(xìngnéng)评价各种调度算法的基本思想了解多处理器硬件组织结构Windows2000/XP的调度思想精品资料 无论是在操作系统控制下执行的程序，还是操作系统程序自己(zìjǐ)，都最终是要在处理器上执行，以便实现其功能。计算机系统的核心是中央处理器。如果一个计算机系统只包括一个中央处理器，称之为单处理器系统。如果有多个中央处理器，则称之为多处理器系统。精品资料6.1多处理器系统(xìtǒng) 随着信息和网络技术的发展，进入信息时代，带给计算机领域的一个重要(zhòngyào)的趋势是越来越普遍的使用多重处理，即配置一个有几个甚至几百个处理器的计算机系统。主要原因是由于人们要求处理的信息越来越庞大，要求具有更高性能更高处理速度的计算机系统。精品资料多处理器系统(xìtǒng)的优点可靠性；高度并行性；多处理(chǔlǐ)器可增强单处理(chǔlǐ)器计算机系统的能力，而又不比显著增加费用、价格；建立多重处理(chǔlǐ)，既增强了系统的处理(chǔlǐ)能力，又不必增强完整的额外系统；多处理(chǔlǐ)器系统提供了重要的灵活性。精品资料多处理器的硬件(yìnɡjiàn)组织总线(zǒnɡxiàn)式结构单总线(zǒnɡxiàn)结构多总线(zǒnɡxiàn)结构交叉开关结构多端口存储器结构精品资料单总线结构(jiégòu)MI/OI/OCPUCPU精品资料多总线结构SBCSBCSBCSBCM1MmI/OC1I/OC2P1Pn精品资料交叉开关式结构(jiégòu)M1M2MmP1PnI/OI/O精品资料多端口存储器结构(jiégòu)核心(héxīn)：多端口存储器模块M1M2MmP1PnI/OI/O精品资料6.2多处理器系统(xìtǒng)的分类多处理器簇（Cluster，又称分布式系统）多处理器簇是指每个处理器都有自己专用的存储器，每个单元都有自包含的计算机，计算机之间的通信或者经由(jīngyóu)专用的线路，或者通过网络。共享存储器的多处理器系统多个处理器共享公用存储器，每个处理器共享对公用存储器中的程序和数据的访问。 这种多处理器系统常分为： 主从式多处理器结构和对称式多处理器结构精品资料主/从式处理器系统(xìtǒng)在主从式处理器系统中，指定一个处理器作为主处理器，其他处理器皆为从处理器，由于(yóuyú)处理器地位是不平等的，所以又称为非对称。只有主处理器可运行操作系统，从处理器仅可执行用户程序。精品资料主/从处理器系统(xìtǒng)的缺点主处理负载过重；主处理器故障(gùzhàng)将引起整个系统故障(gùzhàng)，可靠性差；若主处理器不能充分有效地满足从处理器的服务请求，从处理器的利用率会降低。精品资料对称(duìchèn)式多处理器系统系统中有多个处理器，所有的处理器处于同等地位每个处理器都可以运行操作系统和内核程序处理中断、调度进程等；每个处理器都同样(tóngyàng)可以控制I/O设备和系统中其他资源；系统中所有处理器共享主存储器，没有自己私用的存储器精品资料SMP的组织(zǔzhī)处理器缓存处理器缓存处理器缓存存储器I/OI/O精品资料6.3调度(diàodù)的层次 从处理机调度(diàodù)的对象、时间、功能等不同角度，我们可把处理机调度(diàodù)分成不同类型。按照调度(diàodù)的层次，调度(diàodù)可分为三级：长期调度(diàodù)按照某种原则从磁盘某些盘区的作业队列和交互作业中选取作业进入主存，并为作业做好运行前的准备工作和作业完成后的善后工作。中期调度(diàodù)决定哪些进程被允许参与竞争处理资源。将进程的部分或全部换出到外存上，将当前所需部分换入到内存。短期调度(diàodù)按照某种原则将处理器分配给就绪进程或线程精品资料处理机调度(diàodù)的层次精品资料1.作业(zuòyè)调度作业的状态：提交状态作业被提交给机房后或用户(yònghù)通过终端键盘向计算机中键入其作业时所处的状态。后备状态作业的全部信息都已通过输入设备输入，并由操作系统将其存放在磁盘的某些盘区中等待运行。运行状态作业调度程序选中而被送入主存，并建立进程投入运行。完成状态作业完成其全部运行，释放其所占用的全部资源。精品资料作业(zuòyè)调度作业调度由作业调度程序来完成作业调度时的两个决定接纳多少个作业：作业调度每次要接纳多少个作业进入内存(nèicún)，取决于多道程序度。应根据系统的规模和运行速度等因素。接纳哪些作业：即应将哪些作业从外存调入内存(nèicún)，这取决于所采用的调度算法。精品资料作业(zuòyè)调度程序的功能按照某种调度算法从后备作业(zuòyè)队列中挑选作业(zuòyè)为选中的作业(zuòyè)分配主存和外设资源为选中的作业(zuòyè)建立相应的进程为选中的作业(zuòyè)运行时所需的有关表格，如作业(zuòyè)表等作业(zuòyè)结束时完成该作业(zuòyè)的善后处理作业(zuòyè)精品资料选择(xuǎnzé)调度算法时考虑的问题设计目标资源利用率均衡地处理系统和用户地要求在使用优先级地系统中，每个进程都有一个(yīɡè)优先级，调度算法应优先运行高优先级进程在使用优先数的系统中，调度策略还可分为“可抢占”和“不可抢占”两种方式精品资料调度的性能(xìngnéng)准则我们可从不同的角度来判断(pànduàn)处理机调度算法的性能，如用户的角度、处理机的角度和算法实现的角度。实际的处理机调度算法选择是一个综合的判断(pànduàn)结果。面向用户的调度性能准则面向系统的调度性能准则调度算法本身的调度性能准则精品资料周转时间：作业从提交到完成（得到结果）所经历的时间。包括：在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待－－批处理系统平均周转时间t平均带权周转时间（带权周转时间W是t(周转)/t(CPU执行)〕响应时间：用户输入(shūrù)一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间－－分时系统截止时间：开始截止时间和完成截止时间－－实时系统，与周转时间有些相似。公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。优先级：可以使关键任务达到更好的指标。面向用户的调度(diàodù)性能准则精品资料面向用户的调度性能(xìngnéng)准则平均(píngjūn)周转时间t:

为作业I的周转时间为作业I的提交时间为作业I的完成时间ti=tci-tsi精品资料面向用户的调度性能(xìngnéng)准则平均带权周转时间w为： tri为作业(zuòyè)i的实际执行时间 一般来说，系统应选择使作业(zuòyè)的平均周转时间（或带权周转时间）短的某种算法。因为，作业(zuòyè)的平均周转时间越短，意味着这些作业(zuòyè)在系统内停留的时间越短，因而系统资源的利用率也就越高。精品资料2.面向(miànxiànɡ)系统的调度性能准则吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系－－批处理系统平均周转时间不是吞吐量的倒数，因为并发执行的作业在时间上可以重叠。如：在2小时内完成4个作业，而每个周转时间是1小时，则吞吐量是2个作业/小时处理机利用率：－－大中型主机各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配－－大中型主机3.调度算法本身的调度性能(xìngnéng)准则易于实现执行开销比精品资料处理器调度(diàodù)的两种方式非抢占方式：采用(cǎiyòng)该方式，一旦将处理器分配给某进程后，便让进程一直执行，直到该进程完成和其因等待某事件而阻塞时，才将处理器分配给其他进程。优点：实现简单，系统开销小缺点：难以满足紧急任务的要求精品资料处理器调度(diàodù)的两种方式抢占方式采用这种方式，允许调度程序根据某种原则停止正在处理器上运行的进程，将处理器重新分配给其他进程。优点：能满足及时响应紧急任务缺点：增加(zēngjiā)了系统开销精品资料6.4单处理(chǔlǐ)调度算法先进先出调度算法(suànfǎ)优先级调度算法(suànfǎ)时间片轮转算法(suànfǎ)最短进程优先调度算法(suànfǎ)最短剩余时间优先调度算法(suànfǎ)最高响应比优先调度算法(suànfǎ)多级反馈队列调度算法(suànfǎ)调度实质就是一种资源分配，调度算法是指根据系统的资源分配策略分配资源的算法。有的算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。精品资料先进先出调度(diàodù)算法基本原则：按照作业提交或进程进入就绪队列的先后次序来选择。调度方式：不可抢占。缺点：比较有利于长作业，而不利于短作业。有利于CPU繁忙的作业，而不利于I/O繁忙的作业。应用：不作为主要的调度策略(cèlüè)，尤其不能用于分时和实时系统。常结合其他调度策略(cèlüè)使用。可用于作业调度和进程调度精品资料先进先出调度(diàodù)算法作业提交时间执行时间开始时间完成时间周转时间带权周转时间18.002.008.0010.002.00128.500.5010.0010.502.00439.000.1010.5010.601.601649.500.2010.6010.801.306.5平均周转时间t＝1.725平均带权周转时间w＝6.875精品资料优先级调度(diàodù)算法原则： 按照进程的优先级大小来调度(diàodù)，高优先级进程得到优先处理。应用：可用于作业调度(diàodù)和进程调度(diàodù)（主要）用于进程调度(diàodù)时，可分为：“非抢占”的优先级调度(diàodù)法“可抢占”的优先级调度(diàodù)法：UNIX系统进程调度(diàodù)算法。精品资料优先级调度(diàodù)算法优先级的确定方式：静态优先级：优先级在进程创建时确定，且在进程整个运行(yùnxíng)期间保持不变。动态优先级：在创建进程时赋予优先级，在进程运行(yùnxíng)过程中可以自动改变，以便获得更好的调度性能。在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行；进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让CPU。精品资料时间(shíjiān)片轮转算法原则：将系统中所有的就绪进程按照FIFO原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间(shíjiān)片。时间(shíjiān)片的长度从几个ms到几百ms。在一个时间(shíjiān)片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。进程可以未使用完一个时间(shíjiān)片，就出让CPU（如阻塞）。调度方式：可抢占策略应用：用于进程调度，特别适用于分时系统精品资料时间片长度(chángdù)的确定时间片长度变化(biànhuà)的影响过长－>退化为FIFO算法，进程在一个时间片内都执行完，响应时间长。过短－>用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。对响应时间的要求：T(响应时间)=N(进程数目)*q(时间片)时间片长度的影响因素：就绪进程的数目：数目越多，时间片越小（当响应时间一定时）系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。精品资料最短进程优先调度(diàodù)算法原则：从就绪队列中挑选所需运行时间最短的进程进入主存运行。调度方式：“非抢占”策略。 应用：不适用于分时系统优点：比FCFS改善平均周转时间和平均带权周转时间，缺点：对长作业非常不利，可能(kěnéng)长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业的执行时间，从而影响调度性能。精品资料最短进程优先(yōuxiān)调度算法作业提交时间执行时间开始时间完成时间周转时间带权周转时间18.002.008.0010.002.00128.500.5010.3010.802.304.639.000.1010.0010.10.1.101149.500.2010.1010.300.804平均周转时间t＝1.55平均带权周转时间t＝5.15精品资料最短剩余时间优先(yōuxiān)算法短作业优先调度算法的变型。原则：让运行到作业完成时所需运行时间最短的进程优先得到(dédào)处理，包括新进入系统的进程。调度方式：“可抢占”策略（新进入系统的进程有可能抢占处理机）。优点：降低作业的平均等待时间； 缺点：估计运行时间；系统开销大。应用：可用于分时系统。精品资料最高响应比优先(yōuxiān)调度算法原则：引入动态优先级机制，响应比高者得到优先调度。动态优先数为： 等待时间+要求(yāoqiú)的服务时间 要求(yāoqiú)的服务时间调度方式：“非抢占”策略。缺点：调度前，需计算优先数，开销大。精品资料最高响应比优先(yōuxiān)调度算法优点：是一种较好的折中算法。如果(rúguǒ)作业的等待时间相同，则要求的服务时间越短，其优先数越高，因此，有利于短作业。当要求的服务时间相同时，作业的优先数取决于等待时间，因而实现了FIFO。对长作业，当其等待时间越长，其优先数会越高。精品资料最高响应比优先调度(diàodù)算法作业提交时间执行时间开始时间完成时间周转时间带权周转时间18.002.008.0010.002.00128.500.5010.110.62.104.239.000.1010.010.11.101149.500.2010.610.81.306.5平均周转时间t＝1.625平均带权周转时间t＝5.675精品资料最高响应(xiǎngyìng)比优先调度算法开始时只有作业1，作业1被选中，执行时间(shíjiān)2.0作业1完成后，响应比依次为(1.5+0.5)/0.5,(1+0.1)/0.1,(0.5+0.2)/0.2;因此作业3响应比最高，作业3被选中，执行时间(shíjiān)0.1；作业3完成后，响应比依次为：(1.6+0.5)/0.5,(0.6+0.2)/0.2;作业2响应比最高。作业2被选中，执行时间(shíjiān)0.5;作业2完成，作业4执行0.2.精品资料多级反馈(fǎnkuì)队列算法多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。优点：为提高系统吞吐量和缩短(suōduǎn)平均周转时间而照顾短进程为获得较好的I/O设备利用率和缩短(suōduǎn)响应时间而照顾I/O型进程不必估计进程的执行时间，动态调节精品资料基本(jīběn)实现设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。优先级和时间片相结合：每个队列执行时间片的长度不同，规定优先级越低则时间片越长。按FIFO原则调度；新进程进入(jìnrù)内存后，先投入队列1的末尾。动态优先级：若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FIFO算法调度；如此下去，降低到最后的队列，则按"时间片轮转"算法调度直到完成。仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入(jìnrù)较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。精品资料多级反馈(fǎnkuì)队列精品资料几点说明(shuōmíng)I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。I/O次数不多，而主要是CPU处理的进程：在I/O完成后，放回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。为适应(shìyìng)一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级；精