操作系统处理机管理

会计学1操作系统处理机管理处理机管理处理机管理主要介绍操作系统对于CPU的管理，分为作业管理和进程管理两部分。第1页/共76页作业步完成整个作业的执行，往往要分为若干个步骤，每个步骤称之为一个“作业步”。作业步的划分通常以数据依赖关系来确定，即上一步骤的输出结果是下一步骤执行所需要的输入数据。例如：一个C语言程序的执行可分为编译—>连接—>运行三个步骤。编译步骤将源程序编译成.obj的中间代码；连接步骤将中间代码转化为可执行代码，执行步骤运行可执行代码。第2页/共76页作业管理操作系统将用户提交的作业输入到辅助存储器，并按照一定的调度策略，选择合适的作业进入内存执行，直至完成的管理过程。作业管理贯穿整个作业的生命周期。第3页/共76页作业状态（P31）

提交状态——作业及说明书提交给系统管理员，等待输入辅助存储器；后备状态——作业被输入到辅助存储器中，等待调度程序挑选进入内存；运行状态——作业被调度程序选中，加载进入内存执行；完成状态——作业执行完毕，系统回收所有资源。第4页/共76页作业状态转化图作业辅存主机结束用户把作业提交给系统操作人员操作人员把作业输入到辅助存储器操作系统把作业加载进入内存作业执行完毕，系统回收资源提交后备运行完成作业状态：第5页/共76页后备作业和作业控制块被接纳到辅助存储器的作业，在没有投入运行之前，被称为后备作业。系统在接纳后备作业的时候，会为其建立一个作业控制块（JobControlBlock）。所有后备作业的JBC形成一个后备作业队列。作业控制块（JCB）包括了作业说明书的主要内容，也包括一些作业状态等信息。（P31图2-18）第6页/共76页作业执行的两种调度系统执行作业通常分为两个阶段：1、系统从辅存中选择合适的作业进入内存，属于作业调度。2、系统对已经在内存中的作业分配处理机，属于进程调度。第7页/共76页作业调度

操作系统按照一定的策略，将“后备状态”的作业调入内存中准备执行的行为，称之为作业调度。从作业位置变化角度看，作业调度是把要执行的作业从辅助存储器调入内存的行为。第8页/共76页作业调度的原则公平对待后备队列中的每一个作业进入内存的作业能均衡地使用资源力争在单位时间内为更多的作业服务，提高吞吐能力第9页/共76页作业平均周转时间

假设第i个作业进入后备状态的时刻为Si,执行完毕的时刻为Wi，则该作业周转的时间为：Ti=Wi-Si

在系统中如果有n个作业，则平均周转时间为：T=∑(Ti)/n

平均周转时间值越小，表示作业平均等待的时间越短。第10页/共76页经典的作业调度算法FCFS——先来先服务（FirstComeFirstServed

）SJF——短作业优先(SortestJobFirst)HRRF——最高相应比优先(HighestResponseRatioFirst)第11页/共76页FCFS按照作业进入后备队列的先后次序作为运行的先后次序。这与我们排队处理各种事情的理念是一样的。在一般情况下，在后备队列等待时间最长的将被调度进入内存运行。但是如果此时该作业所需的资源无法获得满足，将会被推迟选中。

第12页/共76页例题1有三个作业，分别于第0秒、第1.5秒、第2.5秒分别进入后备队列，他们所需CPU时间分别为：2秒、6秒、30秒，按照FCFS调度算法，计算这三个作业的平均周转时间。第13页/共76页例题1平均周转时间T1=2秒T2=0.5+6=6.5秒（从1.5—2秒等待作业A完成)T3=5.5+30=35.5秒(从2.5—8秒等待作业B完成)则：T=(T1+T2+T3)/3=(2+6.5+35.5)/3=15(秒)第14页/共76页例题2有三个作业，分别于第0秒、第1.5秒、第2.5秒分别进入后备队列，他们所需CPU时间分别为：30秒、6秒、2秒，按照FCFS调度算法，计算这三个作业的平均周转时间。第15页/共76页例题2平均周转时间T1=30秒T2=28.5+6=34.5秒（从1.5—30秒等待作业A完成)T3=33.5+2=35.5秒(从2.5—36秒等待作业A和B完成)则：T=(T1+T2+T3)/3=(30+34.5+35.5)/3=33.33(秒)第16页/共76页结果比较比较上面两个例子可以得出：在大作业先行到达后备时，使用FCFS调度策略，可能导致系统作业的平均周转时间较长，也就是说如果小作业到达略微迟一点点，就可能要等待很长时间。如果只要执行一分钟的作业需要等待10小时，是一件令人痛苦的事。第17页/共76页SJF——短作业优先

将CPU占用时间短的作业放在优先运行的位置上，可以提高系统的周转率，这就是SJF调度策略。SJF调度策略不考率作业进入后备的时间顺序，只考虑作业对CPU的时间需求。第18页/共76页SJF调度策略的例子有A、B、C三个作业分别在第0、7、10秒进入后备，申请CPU时间为20秒、40秒、10秒，假如系统在第10秒后开始作业调度，按照SJF调度策略，不考虑进入后备的顺序，只考虑后备作业对CPU时间的需求量，调入运行顺序为C->A->B。第19页/共76页SJF算法的缺点但如果在系统运行过程中，仍不断有短作业进入后备，则长作业前面就不断有“插队”的，在极端情况下造成长作业永远得不到运行，这对长作业是不公平的。因此希望有一种算法能兼顾作业申请CPU时间和在辅存中已等待时间这两方面的因素。第20页/共76页HRRF——最高相应比优先

最高相应比优先

(HighestResponse_ratioFirst)将作业在后备区已经等待的时间与该作业申请需要的处理器时间相除，得出一个称之为“响应比”系数：

响应比=已等待时间／申请CPU时间如果一个作业的响应比大，要么该作业需要的时间短，要么该作业已经在后备区等待了足够长的时间。第21页/共76页例题（P33例2-5）有5个作业到达后备时间如下表：作业到达时间所需CPU时间110.1(0)0.7210.3(0.2)0.5310.5(0.4)0.4410.6(0.5)0.4510.7(0.6)0.2第22页/共76页FCFS调入顺序1、2、3、4、55432100.20.40.60.71.21.622.20.5t1=0.7t2=0.7+0.5-0.2=1t3=0.7+0.5+0.4-0.4=1.2t4=0.7+0.5+0.4+0.4-0.5=1.5t5=0.7+0.5+0.4+0.4+0.2-0.6=1.6T=(0.7+1+1.2+1.5+1.6)/5=1.2第23页/共76页SJF调入顺序1、5、3、4、20.50.70.91.31.72.2t1=0.7t5=0.7+0.2-0.6=0.3t3=0.7+0.2+0.4-0.4=0.9t4=0.7+0.2+0.4+0.4-0.5=1.2t2=0.7+0.2+0.4+0.4+0.5-0.2=20243510.20.40.6T=(0.7+0.3+0.9+1.2+2)/5=1.02第24页/共76页HRRF调入顺序1、2、5、3、40.50.71.21.41.82.2t1=0.7R2=1t2=0.7+0.5-0.2=1R5=3t5=0.7+0.5+0.2-0.6=0.8R3=2t3=0.7+0.5+0.2+0.4-0.4=1.4R4=3.25t4=0.7+0.5+0.2+0.4+0.4-0.5=1.70435210.20.40.6T=(0.7+1+0.8+1.4+1.7)/5=1.12第25页/共76页环境对调度的影响P33例2-6，只要内存许可就调入作业，并采用FCFS调度算法：作业到达时间所需CPU时间所需内存量110.10.715K210.30.570K310.50.450K410.60.420K510.70.210k调入顺序为：1、2、5、4、3第26页/共76页前台后台你排队去买火车票，假如买一张票，需要花费10秒钟，如果在你前面的某个人要买500张票，你以及在后面排队的人将会感觉很糟糕。售票员把这个单子接下来，并请他明天来取，然后继续为后面买零票的顾客服务。只在窗口没有人排队的空闲时间里，售票员才来处理500张票的单子。第27页/共76页人们为解决各种不同的问题，编写各种不同的程序，有的计算量大，有的计算量小；有的需要经常性信息交互，有的不需要信息交互。在分时操作系统中把那些运行时间短、交互频繁的作业，赋予较高的运行级别，优先保证其CPU时间片，称为前台作业。把计算量大而且基本没有交互会话的作业，放在较低的运行级别上，只是在没有前台作业运行或没有交互请求时，才去运行它们，称之为后台作业。

前台作业和后台作业

第28页/共76页课后练习讨论：有时貌似公平的解决方案，也有不合理的地方，因此没有绝对的公平合理。今天所学的三个调度算法就是一个例证。结合自己在平时生活中见到或亲身经历的情况，谈谈想法。复习：教材P32—P37的内容。作业：有A、B、C、D四个作业，分别于0秒、2秒、2.5秒、6秒进入系统后备队列，他们分别申请CPU时间8秒、4秒、20秒、5秒。请参照教材的做法，分别给出在FCFS、SJF、HRRF调度算法下的作业周转时间表和平均周转时间。第29页/共76页程序的概念

程序是人们为了让计算机完成某项任务，按照执行时间顺序而编写的指令序列。

第30页/共76页程序的特点连续执行——人们在编写时都假设，自己的程序将一次执行完毕。独占资源——人们在编写时都假设，自己的程序将无条件享有所需要的各种资源。过程再现——人们在编写时都假设，当程序重复运行时，每一时刻的状态和结果都能够重复再现。第31页/共76页单道程序执行执行的连续性——程序一次执行完毕，不被打断。资源的独占性——程序独自享有所需要的各种资源。结果的再现性——程序重复运行时，每一时刻的状态和结果都将能够再现。第32页/共76页多道程序执行在多道程序并发执行的情况下，程序的上述三个特点都不存在了，相反呈现出下面的特征：程序执行是断断续续的；程序与其它程序共享资源；程序的执行过程不可再现。第33页/共76页１、程序执行的不连续性输入输出执行等待CPU321单道程序执行：321多道程序执行（以分时系统为例）：第34页/共76页2、与其它程序共享资源从上例可以看出，多道程序在执行时，一个程序要与其它程序共享CPU资源，实际上，在多道程序运行时，包括内存、外部设备在内的各种资源都需要共享（竞争），在后面的内存管理和设备管理章节中会有更详细的阐述。第35页/共76页3、程序执行过程不可再现例如一辆汽车从事从A地到B地货物运输，虽然每次运输时车型、运输的物品、行驶的线路都相同，但由于各种交通因素的影响（其它车辆干扰、交通信号控制），每次行驶过程都与以前不同，是独一无二的、不可再现的。同样，一个程序的执行过程受到在内存中的其他程序的影响和制约。如果把该程序再次投入运行，尽管自身的代码、数据、需求都没有变化，但由于内存中其它程序数量及状态的变化，影响该程序的执行过程，相对应的每个时刻的状态而言，本次执行过程有别于过去任何一次执行过程，而且是不可再现的。第36页/共76页多道程序运行的特点执行的并发性——从宏观上看，内存中有多个程序同时执行。相互的制约性——一个程序占用的资源，会影响到其他程序的运行。状态的多变性——程序时而运行，时而停止等待，走走停停。第37页/共76页进程概念的引入为了更准确地表述在多道程序环境中程序运行的特点，就引入了进程（Process）的概念。通俗地讲，进程就是进行中的程序。第38页/共76页进程的定义（P15)“进程”是指一个程序在给定数据集上的一次执行过程，是操作系统进行资源分配和运行调度的独立单位第39页/共76页进程和程序的关系（1）相对于程序而言，“进程”是对程序运行的动态描述。教材中把程序比喻成电影拷贝，把进程比作一次放映过程（P15），从一个方面说明了程序和进程之间的关系：即进程是计算机程序的实际执行过程。第40页/共76页进程和程序的关系（2）我们还可以这样理解：从事从A地到B地货物运输，我们要制定一个运输计划，如用什么车辆、什么时候装货、什么时候出发、行驶线路、行驶速度等等，这个计划就是程序，而每一次的实际运输过程就是一个进程。当一次运输结束时，这个进程的生命周期就结束了。第41页/共76页进程和程序的区别（1）程序是静态的——程序是命令代码的集合，存在于纸上或辅助存储器中（没进入内存）。进程是动态的——进程存在于内存中，并且正在某个特定的数据集合上运行。第42页/共76页进程和程序的区别（2）程序不会实际获得资源——虽然程序中表明了对资源的需求，但由于尚未被加载执行，操作系统不会为程序分配资源。进程能实际获得资源——操作系统向每个进程分配资源，包括需要的CPU时间、内存、外部设备等。如果多个用户同时执行同一个程序，则该程序将会发起多个独立的进程，操作系统将为每个进程分别分配所需资源。第43页/共76页进程的特征进程是动态的（在执行中）进程有生命周期（程序没有）进程具有并发性（同时进行）进程会相互制约（互相影响）多个进程可以由同一个程序发起举例：在任务管理器的进程列表中查看不同用户同时执行PowerPoint程的进程。第44页/共76页进程的分类用户进程——由用户的应用程序发起的进程系统进程——由操作系统发起的进程（如调度、资源分配和回收）Windows中，由操作系统发起的系统进程，用户名为System，由用户发起的进程则使用该用户的名称。第45页/共76页进程的基本状态运行状态——进程获得CPU时间，正在运行着。阻塞状态——如果运行状态的进程因某种事件（如等待I/O操作完成）而暂时停止运行，进程就变成阻塞状态，也称“等待状态”。就绪状态——进程已经具备运行条件（如I/O操作已经完成，可以进一步往下执行），但此时CPU正被别的进程占用，此时的进程就处于就绪状态。第46页/共76页进程状态转换运行→阻塞：处于运行中的进程，由于某种原因（等待I/O操作结束或等待某些信号），导致该进程无法继续运行，则变为阻塞状态，并根据阻塞原因安排到相应的队列中。运行→就绪：运行中的进程，由于此次分配给它的时间片用完，则被转变成就绪状态，安排在就绪队列中。阻塞→就绪：当引起一个进程阻塞的原因被解决，该进程满足可以继续运行的条件，则被转变成就绪状态，安排在就绪队列中。第47页/共76页运行就绪阻塞获得CPU时间时间片用完等待的事件已发生，可以继续运行需要等待某个事件发生进程状态转换示例图第48页/共76页课后作业进程是什么，进程和程序有哪些不同？阐述进程基本状态及其相互转化条件，画出进程状态转化图。处于阻塞状态的进程能不能转化成运行状态，为什么？处于就绪状态的进程能不能转化成阻塞状态，为什么？第49页/共76页寄存器寄存器是中央处理器的组成部分,拥有非常高的读写速度，是CPU内部高速存贮部件，用来暂存指令、数据、地址。常用的寄存器包含有程序计数器(PC)、指令寄存器(IR)，地址寄存器、通用寄存器等。第50页/共76页高速缓存—Cache高速缓存（cache）是集成在CPU中的特殊的存储器子系统，其中复制了频繁使用的数据，以利于CPU快速访问。当处理器引用内存中的某地址时，高速缓冲存储器首先检查是否存有该地址。如果存有该地址，则将相应保存的数据放入处理器；如果没有保存该地址，则进行常规的存储器访问。因为访问高速缓存比访问内存速度快，所以当访问高速缓存“命中率”高，可以提高系统处理速度。

第51页/共76页队列在操作系统中所讲的队列，一般是队列链表，通常有单链和双链形式。

第52页/共76页堆栈

堆栈具有先进后出的处理特点，在程序调用、中断处理过程的开始和结束，经常会使用堆栈来保存和恢复返回地址。第53页/共76页中断技术进程在执行过程中，如果时间片用完就应立即停止下来。但用户进程并没有配备计时功能，如何就能知道到时间片到了，如何就能停下来呢？这里用到的就是“中断”技术。中断技术是硬件和软件配合，用来打断当前正在执行的进程，转而处理特定事务的技术。是计算机中非常重要的技术。第54页/共76页“中断”在生活中的事例你正在做数学作业，忽然听到敲门声，有人给你送快件，于是你放下手头的作业，转去处理接收事宜，然后回来继续从被打断的地方做下去。第55页/共76页中断的概念系统暂时停止正在运行的进程，强制转去处理发生的事件，处理完毕后，再返回原进程执行的过程。处理发生事件的程序是事先设计好的，一般称为“中断服务程序”中断服务进程与被中断的进程是相互独立的，不需要相互传递数据。第56页/共76页中断处理过程

中断请求——由中断发起方（中断源）向系统发出请求中断信号（IRQ）；断点保护——将被中断进程的指令计数器、状态字寄存器等放入系统堆栈；中断服务——确定中断源，并转向执行相应的中断服务程序；恢复现场——将被中断进程的指令计数器、状态字寄存器等内容恢复；继续执行——从断点处开始继续执行原来的程序。第57页/共76页中断的优先级根据中断服务的重要性，将各种中断赋予不同的级别，在同时有两个或两个以上中断请求时，只响应级别最高的，而其它低级别的中断请求或等待或撤销。第58页/共76页中断嵌套在处理一个中断服务的过程中，如果发生了级别更高的中断请求，当前中断服务进程也被中断，CPU去执行更高级别的中断服务，这就是中断嵌套。第59页/共76页中断屏蔽对于不允许中断的进程（或进程片段），可以通过屏蔽指令对相关设备进行相应的设置，阻断中断请求链路，阻塞中断请求信号，以达到不响应中断的目的。例如下面介绍的“原语”，就是利用屏蔽的手段，以达到不被中断的目的。第60页/共76页原语原语一般指最基本的不可分割的程序，这个程序一旦被启动，就必须执行完，不能够被中断。通常在这个程序的开始处设置中断屏蔽指令（关中断），在末尾处设置撤销屏蔽指令（开中断）。第61页/共76页进程控制块PCB（ProcessControlBlock）进程的执行是断断续续的，状态也在不断地发生变化，系统为了随时掌握情况进程的变化，设置了一个随时记载其状态的信息载体——进程控制块。每个程序从加载进入内存时，系统就为它创建了一个进程控制块。

第62页/共76页进程控制块的内容（P18）标识信息——记载进程名称等；状态信息——记载进程的状态（运行/就绪/阻塞）、程序及数据在内存中的位置等；现场信息——记载进程被迫放弃CPU时，各种寄存器内容等，以便在重新获得CPU时能恢复现场，继续运行。管理信息——进程的优先级、队列指针等。第63页/共76页进程控制块队列（P20图2-6）

运行队列——每个时刻只可能有一个进程处于运行状态，故运行队列中最多只有一个PCB

。就绪队列——符合运行条件进程，将其PCB按一定的策略排列,等待获得CPU。阻塞队列——进程根据被阻塞的原因的不同，分别排在不同的队列中，因此阻塞队列有多个。第64页/共76页进程调度算法所谓进程调度算法，就是在就绪队列中选择相应的进程投入运行的调度策略。第65页/共76页先来先服务方法——

谁最先到达就绪队列，谁先得到CPU。优点——

算法简单，调度效率高缺点——平均等待时间可能较长，不利于对CPU时间要求短和I/O工作频繁的进程。第66页/共76页时间片轮转方法——每个运行的进程轮流获得一个固定长短的CPU时间片。优点——调度算法