操作系统课件Chapter6.pptx

操作系操作系统课件件-Chapter6n掌握n多处理器分类n调度的层次n调度算法的性能评价n各种调度算法的基本思想n了解n多处理器硬件组织结构nWindows2000/XP的调度思想无论是在操作系统控制下执行的程序，还是操作系统程序自己，都最终是要在处理器上执行，以便实现其功能。计算机系统的核心是中央处理器。n如果一个计算机系统只包括一个中央处理器，称之为单处理器系统。n如果有多个中央处理器，则称之为多处理器系统。6.1 多处理器系统随着信息和网络技术的发展，进入信息时代，带给计算机领域的一个重要的趋势是越来越普遍的使用多重处理，即配置一个有几个甚至几百个处理器的计算机系统。主要原因是由于人们要求处理的信息越来越庞大，要求具有更高性能更高处理速度的计算机系统。多处理器系统的优点n可靠性；n高度并行性；n多处理器可增强单处理器计算机系统的能力，而又不比显著增加费用、价格；n建立多重处理，既增强了系统的处理能力，又不必增强完整的额外系统；n多处理器系统提供了重要的灵活性。多处理器的硬件组织n 总线式结构n单总线结构n多总线结构n交叉开关结构n多端口存储器结构单总线结构MI/OI/OCPUCPU多总线结构SBCSBCSBCSBCM1MmI/O C1I/O C2P1Pn交叉开关式结构M1M2MmP1PnI/OI/O多端口存储器结构n核心：多端口存储器模块M1M2MmP1PnI/OI/O6.2 多处理器系统的分类n多处理器簇（Cluster，又称分布式系统）多处理器簇是指每个处理器都有自己专用的存储器，每个单元都有自包含的计算机，计算机之间的通信或者经由专用的线路，或者通过网络。n共享存储器的多处理器系统 多个处理器共享公用存储器，每个处理器共享对公用存储器中的程序和数据的访问。这种多处理器系统常分为：主从式多处理器结构和对称式多处理器结构主/从式处理器系统 在主从式处理器系统中，指定一个处理器作为主处理器，其他处理器皆为从处理器，由于处理器地位是不平等的，所以又称为非对称。只有主处理器可运行操作系统，从处理器仅可执行用户程序。主/从处理器系统的缺点n 主处理负载过重；n 主处理器故障将引起整个系统故障，可靠性差；n 若主处理器不能充分有效地满足从处理器的服务请求，从处理器的利用率会降低。对称式多处理器系统n系统中有多个处理器，所有的处理器处于同等地位n每个处理器都可以运行操作系统和内核程序处理中断、调度进程等；n每个处理器都同样可以控制I/O设备和系统中其他资源；n系统中所有处理器共享主存储器，没有自己私用的存储器SMP的组织处理器缓存处理器缓存处理器缓存存储器I/OI/O6.3 调度的层次从处理机调度的对象、时间、功能等不同角度，我们可把处理机调度分成不同类型。按照调度的层次，调度可分为三级：n长期调度n按照某种原则从磁盘某些盘区的作业队列和交互作业中选取作业进入主存，并为作业做好运行前的准备工作和作业完成后的善后工作。n中期调度n决定哪些进程被允许参与竞争处理资源。将进程的部分或全部换出到外存上，将当前所需部分换入到内存。n短期调度n按照某种原则将处理器分配给就绪进程或线程处理机调度的层次1.作业调度作业的状态：n提交状态n作业被提交给机房后或用户通过终端键盘向计算机中键入其作业时所处的状态。n 后备状态n作业的全部信息都已通过输入设备输入，并由操作系统将其存放在磁盘的某些盘区中等待运行。n 运行状态n作业调度程序选中而被送入主存，并建立进程投入运行。n 完成状态n作业完成其全部运行，释放其所占用的全部资源。作业调度n作业调度由作业调度程序来完成n作业调度时的两个决定n接纳多少个作业：n作业调度每次要接纳多少个作业进入内存，取决于多道程序度。应根据系统的规模和运行速度等因素。n接纳哪些作业：n即应将哪些作业从外存调入内存，这取决于所采用的调度算法。作业调度程序的功能n按照某种调度算法从后备作业队列中挑选作业n为选中的作业分配主存和外设资源n为选中的作业建立相应的进程n为选中的作业运行时所需的有关表格，如作业表等n作业结束时完成该作业的善后处理作业选择调度算法时考虑的问题n 设计目标n资源利用率n均衡地处理系统和用户地要求n在使用优先级地系统中，每个进程都有一个优先级，调度算法应优先运行高优先级进程n在使用优先数的系统中，调度策略还可分为“可抢占”和“不可抢占”两种方式 调度的性能准则我们可从不同的角度来判断处理机调度算法的性能，如用户的角度、处理机的角度和算法实现的角度。实际的处理机调度算法选择是一个综合的判断结果。面向用户的调度性能准则面向系统的调度性能准则调度算法本身的调度性能准则n周转时间：作业从提交到完成（得到结果）所经历的时间。包括：在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待批处理系统n平均周转时间tn平均带权周转时间（带权周转时间W是 t(周转)/t(CPU执行)n响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间分时系统n截止时间：开始截止时间和完成截止时间实时系统，与周转时间有些相似。n公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。n优先级：可以使关键任务达到更好的指标。面向用户的调度性能准则面向用户的调度性能准则n平均周转时间t:为作业为作业 I 的周转时间的周转时间为作业为作业 I 的提交时间的提交时间为作业为作业 I 的完成时间的完成时间ti=tci-tsi面向用户的调度性能准则平均带权周转时间w为：tri为作业i的实际执行时间一般来说，系统应选择使作业的平均周转时间（或带权周转时间）短的某种算法。因为，作一般来说，系统应选择使作业的平均周转时间（或带权周转时间）短的某种算法。因为，作业的平均周转时间越短，意味着这些作业在系统内停留的时间越短，因而系统资源的利用率业的平均周转时间越短，意味着这些作业在系统内停留的时间越短，因而系统资源的利用率也就越高也就越高。2.面向系统的调度性能准则n吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系批处理系统n平均周转时间不是吞吐量的倒数，因为并发执行的作业在时间上可以重叠。如：在2小时内完成4个作业，而每个周转时间是1小时，则吞吐量是2个作业/小时n处理机利用率：大中型主机n各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配大中型主机3.调度算法本身的调度性能准则n易于实现n执行开销比处理器调度的两种方式n非抢占方式：n采用该方式，一旦将处理器分配给某进程后，便让进程一直执行，直到该进程完成和其因等待某事件而阻塞时，才将处理器分配给其他进程。n优点：实现简单，系统开销小n缺点：难以满足紧急任务的要求处理器调度的两种方式n抢占方式n采用这种方式，允许调度程序根据某种原则停止正在处理器上运行的进程，将处理器重新分配给其他进程。n优点：能满足及时响应紧急任务n缺点：增加了系统开销6.4 单处理调度算法先进先出调度算法优先级调度算法时间片轮转算法最短进程优先调度算法最短剩余时间优先调度算法最高响应比优先调度算法多级反馈队列调度算法调度实质就是一种资源分配，调度算法是指根据系统的资源分配策略分配资源的算法。有的算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。先进先出调度算法n基本原则：按照作业提交或进程进入就绪队列的先后次序来选择。n调度方式：不可抢占。n缺点：n比较有利于长作业，而不利于短作业。n有利于CPU繁忙的作业，而不利于I/O繁忙的作业。n应用：n不作为主要的调度策略，尤其不能用于分时和实时系统。常结合其他调度策略使用。n可用于作业调度和进程调度先进先出调度算法作业提交时间执行时间开始时间完成时间周转时间带权周转时间18.002.008.0010.002.00128.500.5010.0010.502.00439.000.1010.5010.601.601649.500.2010.6010.801.306.5平均周转时间 t1.725平均带权周转时间 w 6.875优先级调度算法n原则：按照进程的优先级大小来调度，高优先级进程得到优先处理。n应用：可用于作业调度和进程调度（主要）n用于进程调度时，可分为：n n“非抢占非抢占”的优先级调度法n n“可抢占可抢占”的优先级调度法：UNIX系统进程调度算法。优先级调度算法n优先级的确定方式：n静态优先级：优先级在进程创建时确定，且在进程整个运行期间保持不变。n动态优先级：在创建进程时赋予优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能。n在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行；n进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让CPU。时间片轮转算法n原则：n将系统中所有的就绪进程按照FIFO原则，排成一个队列。n每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。n在一个时间片结束时，发生时钟中断。n调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。n进程可以未使用完一个时间片，就出让CPU（如阻塞）。n调度方式：可抢占策略n应用：用于进程调度，特别适用于分时系统 时间片长度的确定n时间片长度变化的影响n过长退化为FIFO算法，进程在一个时间片内都执行完，响应时间长。n过短用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。n对响应时间的要求：nT(响应时间)=N(进程数目)*q(时间片)n时间片长度的影响因素：n就绪进程的数目：数目越多，时间片越小（当响应时间一定时）n系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。最短进程优先调度算法n原则：从就绪队列中挑选所需运行时间最短的进程进入主存运行。n调度方式：“非抢占”策略。n应用：不适用于分时系统n优点：n比FCFS改善平均周转时间和平均带权周转时间，n缺点：n对长作业非常不利，可能长时间得不到执行；n未能依据作业的紧迫程度来划分执行的优先级；n难以准确估计作业的执行时间，从而影响调度性能。最短进程优先调度算法作业提交时间执行时间开始时间完成时间周转时间带权周转时间18.002.008.0010.002.00128.500.5010.3010.802.304.639.000.1010.0010.10.1.101149.500.2010.1010.300.804平均周转时间 t1.55平均带权周转时间 t 5.15最短剩余时间优先算法n短作业优先调度算法的变型。n原则：让运行到作业完成时所需运行时间最短的进程优先得到处理，包括新进入系统的进程。n调度方式：“可抢占”策略（新进入系统的进程有可能抢占处理机）。n优点：降低作业的平均等待时间；n缺点：估计运行时间；系统开销大。n应用：可用于分时系统。最高响应比优先调度算法n原则：引入动态优先级机制，响应比高者得到优先调度。n动态优先数为：等待时间+要求的服务时间 要求的服务时间n调度方式：“非抢占”策略。n缺点：调度前，需计算优先数，开销大。最高响应比优先调度算法n优点：是一种较好的折中算法。n如果作业的等待时间相同，则要求的服务时间越短，其优先数越高，因此，有利于短作业。n当要求的服务时间相同时，作业的优先数取决于等待时间，因而实现了FIFO。n对长作业，当其等待时间越长，其优先数会越高。最高响应比优先调度算法作业提交时间执行时间开始时间完成时间周转时间带权周转时间18.002.008.0010.002.00128.500.5010.110.62.104.239.000.1010.010.11.101149.500.2010.610.81.306.5平均周转时间 t1.625平均带权周转时间 t 5.675最高响应比优先调度算法n开始时只有作业1，作业1被选中，执行时间2.0n作业1完成后，响应比依次为(1.5+0.5)/0.5,(1+0.1)/0.1,(0.5+0.2)/0.2;因此作业3响应比最高，作业3被选中，执行时间0.1；n作业3完成后，响应比依次为：(1.6+0.5)/0.5,(0.6+0.2)/0.2;作业2响应比最高。作业2被选中，执行时间0.5;n作业2完成，作业4执行0.2.多级反馈队列算法n多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。n优点：n为提高系统吞吐量和缩短平均周转时间而照顾短进程n为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程n不必估计进程的执行时间，动态调节基本实现n设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。n优先级和时间片相结合：每个队列执行时间片的长度不同，规定优先级越低则时间片越长。n按FIFO原则调度；新进程进入内存后，先投入队列1的末尾。n动态优先级：若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FIFO算法调度；如此下去，降低到最后的队列，则按时间片轮转算法调度直到完成。n仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。多级反馈队列几点说明nI/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。n计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。nI/O次数不多，而主要是CPU处理的进程：在I/O完成后，放回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。n为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级；低级就绪队列高级就绪队列中级就绪队列等待磁盘磁带等待其他外设运行选中,时间片500ms超过时间片启动磁盘磁带启动其他外设选中,时间片200ms选中,时间片100msn多级反馈队列调度算法具有较好的性能，能满足各类用户的需要。n对分时交互型短作业，系统通常可在第一队列规定的时间片内让其完成工作，使终端型用户都感到满意；n对短的批处理作业，通常，只需在第一或第一、第二队列中各执行一个时间片就能完成工作，周转时间仍然很短；n对长的批处理作业，它将依次在第一、第二、队列中获得时间片并运行，决不会出现得不到处理的情况。Windows 2000/XP调度算法 nWindows 2000/XP的调度是基于内核级线程的；n它支持抢占式调度，包括多个优先数层次，在某些层次线程的优先数是固定的，在另一些层次线程的优先数将根据执行的情况动态调整。n它的调度策略是一个多级反馈队列，每一个优先数都对应于一个就绪队列，而每一个进程队列中的进程按照时间片方式调度。nWindows 2000/XP有两个优先级层次 n实时优先级层次（优先数为31-16）：用于通信任务和实时任务。当一个线程被赋予一个实时优先数，在执行过程中这一优先数是不可变的。2000/XP支持优先数驱动的抢占式调度，一旦一个就绪线程的实时优先数比运行线程高，它将抢占处理器运行。n可变优先级层次（优先数为15-0）：用于用户提交的交互式任务。具有这一层次优先数的线程，可以根据执行过程中的具体情况动态地调整优先数，但是15这个优先数是不能被突破的。最高(31)实时优先级层次最低(16)最高(15)最低(0)可变优先级层次作业n6.8n6.11n6.12汇报结束谢谢大家!请各位批评指正