计算机操作系统第三版全部

操作系统原理OperatingSystem,第1章操作系统绪论,操作系统的概念操作系统的历史操作系统的特性操作系统的基本类型操作系统的功能计算机硬件简介算法的描述研究操作系统的观点,1.1操作系统概念,操作系统的地位引入操作系统的目的操作系统定义,Whatisoperatingsystem?,1.1.1操作系统地位,硬件抽象层（HAL）之上所有其它软件层之下,硬件（HAL）,OS,其它系统软件层（如编译软件）,应用软件层,1.1.2引入操作系统的目的,从用户的观点：为用户（应用程序）提供良好的服务界面。API、GUI从系统管理员的观点：为管理和分配系统资源，提高系统工作效率。从发展的观点：为系统提供功能扩展平台。,1.1.3操作系统定义,操作系统是位于硬件层(HAL)之上，所有其它软件层之下的一个系统软件，是管理和控制系统中各种软硬件资源，方便用户使用计算机系统的程序集合。,Operatingsupervisormonitoringprogram,1.2操作系统的历史,操作系统的产生手工操作阶段成批处理阶段执行系统阶段操作系统的完善多道批处理系统分时系统实时处理系统通用操作系统,操作系统的发展网络操作系统分布式操作系统多处理机操作系统单用户操作系统面向对象操作系统嵌入式操作系统智能卡操作系统,Evolution,1.3操作系统特性,程序并发性多个程序在宏观上同时向前推进、微观上串行推进并发(concurrent)vs.并行(parallel)资源共享性多个程序共用系统中的各种软硬件资源在操作系统的协调和控制下虚拟性物理上的一台设备变成逻辑上的多台设备不确定性,1.4操作系统的基本类型,多道批处理操作系统(batchprocessingsystem)分时操作系统(time-sharingsystem)实时操作系统(realtimesystem)通用操作系统(multi-purposesystem)单用户操作系统(singleusersystem)网络操作系统(networkoperatingsystem)分布式操作系统(distributedoperatingsystem)多处理机操作系统(multi-processorsystem),1.4.1多道批处理系统（Off-line）,1.4.1多道批处理系统,特点多道：系统中同时容纳多个作业成批：作业分批进入系统宏观上并行，微观上串行多道批处理系统是以脱机为标志的操作系统，适用于处理运行时间比较长的程序。主机中作业合理搭配目标1：提高资源利用率目标2：提高吞吐量(throughput),分时处理终端请求,界面1：交互式命令语言(eg.shell,command)界面2：图形用户界面(GUI),1.4.2分时操作系统（On-line）,TimeSharingOS,HAL,终端,终端,终端,.,1.4.2分时操作系统,特点：多路性：一个主机与多个终端相连；交互性：以对话的方式为用户服务；独占性：每个终端用户仿佛拥有一台虚拟机。分时操作系统是以联机为标志的操作系统，特别适用于程序的动态调试与修改。,1.4.3实时操作系统,实时控制工业控制，军事控制，医疗控制，.实时信息处理航班定票，联机情报检索，.,实时控制,HAL,RealTimeOS,被控对象,A/D,D/A,t1,t2,t2-t1:responsetime,实时信息处理,HAL,RealTimeOS,.,终端,终端,终端,通常为远程终端,特点：（1）响应及时（promptresponse）（2）可靠性高（highreliability）,1.4.4通用操作系统(multi-purposeOS),同时具有：分时、实时、批处理功能。目标：提高处理能力;扩展应用领域。常见模式:分时(前台)+批处理(后台)实时(前台)+批处理(后台),Foreground/BackgroundSystem,1.4.5单用户操作系统,同一时刻仅有一个用户使用的系统应用领域：台式机，笔记本，.特点：单用户，多进程，多线程,不同的程序，不同的进程；相同的程序,不同的线程,1.4.6网络操作系统,DOS3,host3,NOS2,host2,Printer,建立在宿主操作系统之上，提供网络通讯、网络资源共享、网络服务的软件包。,NOS1,host1,网络操作系统的目标,相互通讯资源共享（信息，设备）提供网络服务databaseserverftpservere-mailservertelnetserveretc.,NoTransparentview,1.4.7分布式操作系统,紧耦合：(tightlycoupled)由多机系统发展而来（多CPU）有公共内存多处理机操作系统,1.4.7分布式操作系统,松散耦合：(looselycoupled)由计算机网络发展而来（多Host)无公共内存，无公共时钟,DOS,host3,DOS,host2,DOS,host1,1.4.7分布式操作系统,分布式操作系统特征:统一的操作系统资源的进一步共享可靠性透明性,1.4.8多处理机操作系统,多处理机系统具有公共内存的多CPU系统对称多处理机系统(SMP)没有主从关系的多处理机系统多处理机操作系统有效管理和使用多个CPU的操作系统复杂性：多个主动体（CPUs)例子：UNIX,Linux,Windows,1.5操作系统的功能,处理机管理存储管理设备管理信息管理（文件系统管理）用户接口,1.6计算机硬件简介1.6.1计算机的基本硬件元素,构成计算机基本硬件元素包含以下4种：处理器、存储器、输入输出控制与总线、外部设备。,计算机的基本硬件元素,1.6.2与操作系统相关的几种主要寄存器,1.数据寄存器2.地址寄存器3.条件码寄存器4.程序计数器PC5.指令寄存器IR6.程序状态字PSW7.中断现场保护寄存器8.过程调用用堆栈,1.6.3存储器的访问速度,存储介质的访问速度,一般来说，速度高的存储介质，成本高，容量小；容量大的存储介质，速度慢，成本低。,1.6.4指令的执行与中断,指令的执行周期,中断执行过程f,1.6.4指令的执行与中断,中断处理时的指令执行周期,1.7算法的描述,算法描述的方式：自然语言流程图方式类Pascal语言本书：beginRepeatWhile条件If条件end操作dothen操作操作Untilodelse操作,1.8研究操作系统的几种观点,操作系统是计算机资源的管理者用户界面的观点进程管理的观点,第2章操作系统用户界面,用户界面简介一般用户的输入输出界面命令控制界面Linux与Windows的命令控制界面系统调用,2.1用户界面简介,用户界面的功能用户界面负责用户与操作系统之间的交互。用户分类使用和管理计算机的应用程序的用户程序开发人员用户界面分类命令控制界面系统调用,2.2一般用户的输入输出界面,2.2.1作业的定义2.2.2作业组织2.2.3一般用户的输入输出方式,2.2.1作业的定义,在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作称为一个作业。作业由不同的顺序相连的作业步组成。,图2.1一般编程过程,2.2.2作业组织,图2.2作业说明书的主要内容,2.2.3一般用户的输入输出方式,1.联机输入输出方式外围设备直接和主机相连，速度慢。2.脱机输入输出方式外围机进行联机输入输出处理，通过外围机的后援存储来实现和主机的连接。速度快。3.直接耦合方式主机和外围机通过一个公共外存直接连接。速度快，人工不用干预,2.2.3一般用户的输入输出方式,图2.3直接耦合方式,4.SPOOLING系统5.网络联机方式,2.2.3一般用户的输入输出方式,外围设备通过通道或DMA器件与主机和外存相连。,2.3命令控制界面,用户使用命令控制界面的方式：1、脱机方式填写作业说明书，用户不能干预作业执行。2、联机方式不用填写作业说明书，用户能够干预作业执行。,2.4Linux与Windows的命令控制界面,RedhatLinux9.0的窗口界面,2.4.1Linux的命令控制界面,2.4.1Linux的命令控制界面,Linux的命令一般包含9类：1系统维护与管理命令文件操作与管理命令进程管理命令磁盘及设备管理命令用户管理命令文档操作命令网络通信命令程序开发命令XWindows管理命令,2.4.2Windows的命令控制界面,Windows的命令控制界面分为两个部分：窗口交互：通过键盘和鼠标在图形上操作。命令解释器：通过cmd.exe为用户服务。,2.4.2Windows的命令控制界面,图2.6相互调用批处理示例,2.5系统调用,系统调用分为6类：1设备管理2文件管理3进程控制4进程通信5存储管理6线程管理,2.5系统调用,系统调用的处理过程,第3章进程管理,进程的概念进程的描述进程状态及其转换进程控制进程互斥进程同步进程的通信死锁问题线程的概念、分类与执行,3.1进程的概念,3.1.1程序的并发执行3.1.2进程的定义,3.1.1程序的并发执行,程序(program)用来描述计算机所要完成的独立功能，并在时间上严格地按前后次序相继地进行计算机操作序列集合，是一个静态的概念。2.程序的顺序执行（sequence)程序顺序执行的概念一个具有独立功能的程序独占处理机直至最终结束的过程称为程序的顺序执行。程序顺序执行的特征顺序性封闭性可再现性,3.1.1程序的并发执行,3.程序的并发(concurrent)执行程序的并发执行：宏观上同时向前推进，微观上同一时刻只有一个程序运行。程序并发执行分为两种：一种是程序间的并发。另一种是同一程序内部多条指令的并发。程序并发执行的特性：交叉性、非封闭性、不可再现性,3.1.1程序的并发执行,4.程序的顺序性与并发性举例：顺序性内部顺序性：P1:a1,a2,a3;P2:b1,b2,b3外部顺序性：a1,a2,a3,b1,b2,b3;b1,b2,b3,a1,a2,a3并发性内部并发性：P1:a1,a2,a3;P2:b1,b2,b3外部并发性：a1,b1,b2,a2,a3,b3;b1,b2,a1,b3,a2,a3,3.1.2进程的定义,定义：并发执行的程序在执行过程中分配和管理资源的基本单位。定义强调两个方面：动态：执行中的程序;并发：可与其他进程同时执行。,并发vs.并行,并发：concurrent宏观同时，“交替执行”，不要求多个CPU并行：parallel微观同时，要求多个CPU“并行算法”,3.1.2进程的定义,进程与程序的区别与联系：进程是一个动态概念，程序是一个静态概念。进程具有并发特征，而程序没有。进程是竞争计算机系统资源的基本单位。不同的进程可以包含同一程序，只要该程序所对应的数据集不同。,3.2进程的描述,进程控制块进程组成与进程上下文进程上下文的切换进程空间与大小进程的类型进程的相互联系与相互作用,3.2.1进程控制块PCB,定义：标志进程存在的数据结构，其中保存系统管理进程所需的全部信息。PCB的内容：(不同系统不尽相同)1.描述信息2.控制信息3.资源管理信息4.CPU现场保护结构,ProcessControlBlock,3.2.2进程的组成与上下文,进程的组成进程控制块(processcontrolblock)建立进程建立PCB撤销PCB撤销进程程序代码(code)数据(data)堆栈(stack+heap),3.2.2进程的组成与上下文,进程的表记,PCB,程序,PCB,代码,数据+堆栈,表记1,表记2,系统空间,用户空间,3.2.2进程的组成与上下文,进程上下文（processcontext)进程的物理实体与支持进程运行的物理环境统称为进程上下文。PCB+程序系统环境：地址空间，系统栈，打开文件表，,3.2.2进程的组成与上下文,进程上下文结构,3.2.3进程上下文切换,上下文切换（contextswitch)由一个进程的上下文转到另外一个进程的上下文系统开销（systemoverhead)运行操作系统程序完成系统管理工作所花费的时间和空间,3.2.3进程上下文切换,进程上下文的切换过程,3.2.4进程空间与大小,进程在内存中自己拥有的一个地址空间称为进程空间。进程空间的大小只与处理机的位数有关。一般，进程空间可以分为：用户空间与系统空间。用户程序在用户空间中运行。操作系统内核程序在系统空间中运行。,3.2.5进程的类型,进程类型系统进程运行操作系统程序，完成系统管理(服务)功能.用户进程运行用户(应用)程序，为用户服务。,3.2.6进程间相互联系与相互作用,相互联系相关进程同一家族的进程可以共享文件，需要相互通讯，协调推进速度父进程可以监视子进程，子进程完成父进程交给的任务。无关进程没有逻辑关系、同时执行的进程。有资源竞争关系，互斥、死锁、饿死。,3.2.6进程间相互联系与相互作用,相互作用,1.直接相互作用：发生在相关进程之间,2.间接相互作用：发生在任何进程之间,R,P2,P1,sync,send,receive,P1:,P2:,hold,wait,3.3进程状态及其转换,进程的状态进程状态的转换进程队列,3.3.1进程状态,进程状态：初始态（Initial）：进程刚被创建，其他进程正占据处理器而得不到执行。运行态（Run）：占有CPU正在向前推进。就绪态（Ready）：可以运行，但未得到CPU。等待态（Wait）：等待某一事件发生。终止态（Stop）：进程执行结束，将退出执行而被终止。,3.3.2进程状态转换,状态转换就绪运行：获得处理机运行就绪：剥夺处理机运行等待：申请资源未得到，启动IO等待就绪：得到资源，IO中断,3.3.2进程状态转换图,KeepinMind,3.3.2进程状态转换图,初创,终止,创建,结束,3.3.3进程队列,1.就绪队列：系统一个或若干个（根据调度算法确定）2.等待队列：每个等待事件一个3.运行队列：每个处理机一个,PCB构成的队列：（不一定FIFO),3.4进程控制,进程控制：系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。原语：系统态下执行的某些具有特定功能的程序段。原语的分类：机器指令级：不许中断功能级：不许并发,3.4.1进程创建与撤销,进程创建方式：系统创建父进程创建,3.4.1进程创建与撤销,进程撤销的方式：正常终止非正常终止祖先进程撤销,3.4.2进程的阻塞与唤醒,阻塞原语图,阻塞原语实现了进程由执行状态到等待状态的转变。阻塞原语是由进程自己调用的。,3.4.2进程的阻塞与唤醒,唤醒原语,唤醒原语实现了进程由等待状态到就绪状态的转变。唤醒的方式:系统进程唤醒事件发生进程唤醒,3.5进程互斥,与时间有关的错误共享变量与临界区域进程互斥进程互斥的实现信号灯与P，V原语,3.5.1与时间有关的错误,例：图书借阅系统（x:某种书册数，设当前x=1.）终端1：终端2：CYCLECYCLE等待借书者；等待借书者；IFx=1ThenIFx=1ThenBeginBeginx:=x-1;x:=x-1;借书借书EndEndElse无书Else无书EndEnd,3.5.1与时间有关的错误,错误原因之1：进程执行交叉(interleave);错误原因之2：涉及公共变量(x)。注意:某些交叉结果不正确;必须去掉导致不正确结果的交叉。,3.5.2共享变量与临界区域,共享变量（sharedvariable）多个进程都需要访问的变量。临界区域（criticalregion）访问共享变量的程序段。,一组公共变量,CR1,CR2,CRn,.,临界区的表示,共享变量:shared临界区域:regiondo语句例子：sharedB:array0,.,n-1ofinteger;regionBdoregionBdobeginbegin(访问B）.（访问B）.end;end;,3.5.3进程互斥,定义：多个进程不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象称为进程互斥。二层涵义：（1）任何时刻最多只能有一个进程处于同一组共享变量的相同的临界区域；（2）任何时刻最多只能有一个进程处于同一组共享变量的不同的临界区域。注意:互斥是相对于公共变量而言的。,并发进程互斥执行必须满足4条准则：不能假设并发进程的相对执行速度。某进程不在临界区，不能阻止其他进程进入临界区。若干进程申请进入临界区，只能允许一个进程进入。某进程申请进入临界区，应该在有限的时间内得以进入临界区。,3.5.3进程互斥,3.5.4进程互斥的实现,进程互斥的实现有两种方法：软件方法实现：完全用程序实现，不需特殊硬件指令支持。可用于单CPU和多CPU环境中。有忙式等待问题,Busywaiting“运行”或“就绪”,3.5.4进程互斥的实现,硬件方法实现：硬件提供“测试并建立”指令、“交换”指令硬件提供“关中断”和“开中断”指令关中断CriticalRegion开中断Remarks:(1)开关中断只在单CPU系统中效;(why?)(2)影响并发性。,3.5.4进程互斥的实现,例：对临界区加锁实现互斥:当某个进程进入临界区之后，它将锁上临界区，直到它退出临界区时为止。lock(keys)临界区unlock(keys),3.5.5信号灯与P，V原语,E.W.Dijkstra,1965.信号灯与PV操作的定义TYPEsemaphore=RECORDvalue:integer;queue:PCBpointer;END;VARs:semaphore;备注:(1)semaphore是一个提前定义好的数据类型.(2)s是一个信号灯变量,使用前必须先声明.例如:vars1,s2:semaphore;,信号灯变量,S.valueS.queue,VarS:semaphore;,FIFO,P操作原语,P操作原语：ProcedureP(vars:semaphore)s.value:=s.value-1;Ifs.value=0时，s.queue为空；当s.value=1ThenIFx=1ThenBeginBeginx:=x-1;x:=x-1;V(mutex)V(mutex)借书借书EndEndElseV(mutex);无书;ElseV(mutex);无书;EndEnd,3.6进程同步,3.6.1进程同步的概念例：司机-乘客问题司机活动：(P1)乘客活动：(P2)dodo启动车辆上车正常行驶投币到站停车下车while(1)while(1),3.6.1进程同步的概念,定义：一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间这种相互制约的关系称为进程同步。,P1:,P2:,synchronize,后,先,3.6.2进程同步机制,定义：用于实现进程同步的工具称为同步机制（synchronizationmechanism）同步机制要求：描述能力够用;可实现;高效;使用方便.,3.6.3用信号灯实现进程同步,GeneralCase:VARS:semaphore;(initialvalue0),P(S)后动作,先动作V(S),P1:,P2:,用信号灯实现进程同步,例子：司机-乘客问题：VARs1,s2:semaphore;(initialvalue0)司机活动：售票员活动：RepeatRepeatP(S1)上车启动车辆V(S1)正常行驶投币到站停车P(S2)V(S2)下车UntilfalseUntilfalse,典型的进程同步问题,生产者消费者问题,生产者/消费者问题,预备知识：组合资源：若干相对独立的资源构成的资源集合，其中每个相对独立的资源称为子资源。同种组合资源：相同类型子资源构成的组合资源。管理：VarS:semaphore;(初值=子资源个数）例子：2台打印机VarS:semaphore;S.value=2;申请：P（S）；释放：V（S）；,2,2,自动机描述,1,0,-1,-2,P(S),P(S),P(S),P(S),P(S),V(S),V(S),V(S),V(S),V(S),S.value=空闲资源数S.queue=空,|S.value|=等待进程数空闲资源数=0,.,生产者/消费者问题,01k-1,箱子，容量kB:Array0.k-1Ofitem,生产者,消费者,生产物品放入B中,从B中取物品消费之,环形缓冲区,1,0,K-1,in,(in+1)modk,out,(out+1)modk,问题分析,生产者活动：消费者活动：dodo加工一件物品箱中取一物品物品放入箱中消耗这件物品while(1)while(1),资源：箱子（同种组合）资源：物品（同种组合）VarS1:semaphore;VarS2:semaphore;S1.value=k;S2.value=0;放前：P（S1）取前：P（S2）放后：V（S2）取后：V（S1）,同步,生产者活动：消费者活动：RepeatRepeat加工一件物品P(S2)P(S1)箱中取一物品物品放入箱中V(S1)V(S2)消耗这件物品UntilfalseUntilfalse对B和in,out的互斥：Varmutex:semaphore;(mutex.value=1),互斥,生产者活动：消费者活动：RepeatRepeat加工一件物品P(S2)P(S1)P(mutex)P(mutex)箱中取一物品物品放入箱中V(mutex)V(mutex)V(S1)V(S2)消耗这件物品UntilfalseUntilfalse,程序,Programproducers_consumers;VarB:Array0,k-1Ofitem;S1,S2,mutex:semaphore;in,out:0.k-1;,ProcedureproducercycleproduceaproductP(S1);P(mutex);Bin:=product;in:=(in+1)modk;V(mutex);V(S2)end,ProcedureconsumercycleP(s2);P(mutex);x:=Bout;out:=(out+1)modk;V(mutex);V(S1);consumex;end;,程序,BeginS1.value:=k;S2.value:=0;mutex.value:=1;in:=0;out:=0;CobeginP1:producer;,Pm:producer;C1:consumer;,Cn:consumer;Coend;End.,并发性提高策略,生产者和消费者：不操作B的相同分量,生产者的共享变量：Bin，in,消费者的共享变量：Bout，out,in=out:满或空,Varmutex1,mutex2:semaphore;(init1),并发性提高策略,生产者活动：消费者活动：RepeatRepeat加工一件物品P(S2)P(S1)P(mutex2)P(mutex1)箱中取一物品物品放入箱中V(mutex2)V(mutex1)V(S1)V(S2)消耗这件物品UntilfalseUntilfalse,3.7进程通信,进程通信：进程之间的数据传送。低级通讯（简单信号）进程互斥进程同步高级通讯（大宗信息）,3.7.1进程通信的概念,3.7进程通信,单机系统中进程通信可以分为4种形式：1、主从式2、会话式3、消息或邮箱机制4、共享存储方式,3.8死锁问题,死锁的概念死锁类型死锁的条件死锁的处理资源分配图死锁预防死锁避免死锁的检测死锁的恢复,3.8.1死锁的概念,死锁概念,有并发进程P1,P2,Pn，它们共享资源R1,R2,Rm(n0，m0，nm）。其中，每个Pi（1in）拥有资源Rj(1jm)，直到不再有剩余资源。同时，各Pi又在不释放Rj的前提下要求得到Rk（kj，1km），从而造成资源的互相占有和互相等待。在没有外力驱动的情况下，该组并发进程停止住往前推进，陷入永久等待状态。把这种现象称为死锁。,由概念得到的结论,几个有用的结论：参与死琐的进程至少有二个；每个参与死锁的进程均等待资源；参与死锁的进程中至少有两个进程占有资源；死锁进程是系统中当前进程集合的一个子集。,3.8.2死锁类型,3.8.2死锁类型,2.进程通讯引起的死锁P1：receive(P2,M1);P2:receive(P3,M2);P3:receive(P1,M3);其它原因引起的死锁Afteryou/afteryou,3.8.3死锁的条件,Coffman条件（必要条件）资源独占（mutualexclusion）不可抢占（nonpreemption）保持申请（hold-while-applying）循环等待（circularwait）当每类资源只有一个实例时，充要条件。破坏上述任意一个条件可以消除死锁。,3.8.4死锁的处理,死锁预防（deadlockprevention）-静态死锁避免（deadlockavoidance）-动态死锁检测（deadlockdetection）死锁恢复（deadlockrecovery）,3.8.5资源分配图,定义:G=(V,E),V=PR,P=p1,p2,pn,R=r1,r2,rm,E=(pi,rj)(rj,pi),piP,rjR.申请边(pi,rj):pi申请rj；分配边(rj,pi):rj分配pi;图示：进程：资源：申请边：由进程到资源类；分配边：由资源实例到进程。,3.8.5资源分配图,申请：pi申请rj中的一个资源实例，由pi向rj画一申请边，如可满足，改为分配边。释放：去掉分配边。,例子（无环路，无死锁）,例子（有环路，有死锁）,例子（有环路，无死锁）,p1,p2,p3,p4,r1,r2,3.8.6死锁预防,对进程有关资源的活动加限制，所有进程遵循这种限制，即可保证没有死锁发生。优点：简单，系统不需要做什么。缺点：对进程的约束，违反约束仍可能死锁。预防方法：预先分配法；有序分配法。,预先分配法,进程：运行前申请所需全部资源；系统：能够满足，全部分配，否则，一个也不分配。破坏“hold-and-wait”条件缺点：资源利用效率低；一次提出申请困难。,有序分配法,资源集：R=r1,r2,rn函数：F：RN例如：R=scanner,tape,printerF(scanner)=1;F(tape)=2;F(printer)=3;,进程pi可以申请资源rj中的实例rl,pi占有rl,F(rl)F(rj),有序分配法,证明无死锁（deadlockfree)：反证，假定死锁时刻t1:p1无限等待rk1中的资源实例，被p2占有；时刻t2:p2无限等待rk2中的资源实例，被p3占有；时刻tn:pn无限等待rkn中的资源实例，被p1占有;根据有序申请假设：F(rk1)F(rk2)F(rkn)F(rk1)矛盾。,3.8.7死锁避免,系统处于安全状态：存在安全进程序列进程序列安全，p1,p2,pn可依次进行完。,银行家算法(Cont.),Bankersalgorithm,E.W.Dijkstra.进程：事先申明所需资源最大量（并不分配）系统：对每个可满足的资源申请命令进行安全性检查。P=p1,p2,pn;R=r1,r2,rm;,银行家算法(Cont.),数据结构：Available:array1.mofinteger;/系统可用资源Claim:array1.n,1.mofinteger;/进程最大需求Allocation:array1.n,1.mofinteger;/当前分配Need:array1.n,1.mofinteger;/尚需资源Request:array1.n,1.mofinteger;/当前请求临时变量：Work:array1.mofinteger;Finish:array1.nofboolean;,银行家算法(Cont.),设X,Y为下标1.l的一维数组：XYj(1jl),XjYjX:=Yj(1jl),Xj:=YjX:=cj(1jl),Xj:=cXYj(1jl),XjYj,资源分配,Pi请求资源,RequestINeedI,请求超量，错返,RequestIAvailable,不满足，等待,Available:=Available-RequestIAllocationI:=AllocationI+RequestINeedI:=NeedI-RequestI,安全,确认，pi继续,Available:=Available+RequestIAllocationI:=AllocationI-RequestINeedI:=NeedI+RequestIpi等待,F,T,F,T,T,F,安全性检测算法,F,银行家算法例子,R=A(10),B(5),C(7)P=p0,p1,p2,p3,p4,ClaimAllocationNeedAvailableWorkFinishABCABCABCABCABC753010743332322200122902302600222211011433002431,P0:p1:p2:p3:p4:,安全进程序列：p1请求：Request1=(1,0,2),银行家算法例子,ClaimAllocationNeedAvailableWorkFinishABCABCABCABCABC753010743230322302020902302600222211011433002431,P0:p1:p2:p3:p4:,假定分配：,安全进程序列：p4请求：Request4=(3,3,0),不能满足，等待；p0请求：Request0=(0,2,0),不安全，等待。,3.8.8死锁的检测,数据结构：Available:array1.mofinteger;Allocation:array1.n,1.mofinteger;Request:array1.n,1.mofinteger;临时变量：Work:array1.mofinteger;Finish:array1.nofboolean;,死锁检测算法,FinishI=trueforallocationI=0,Remarks,1.上述算法可以检测到参与死锁的全部进程，包括占有资源和不占有资源的进程。2.如果希望只检测占有资源的进程，初始化时：Finishi=true,forAllocationI=0,死锁例子,例子：R=A(7),B(2),C(6);P=p0,p1,p2,p3,p4,AllocationRequestAvailableWorkFinishABCABCABCABCp0:010000000p1:200202p2:303000p3:211100p4:002002,未死锁。此时，Request2=(0,0,1),死锁，参与死锁进程p1,p2,p3,p4,死锁检测时刻,考虑因素：死锁发生频度；死锁影响进程。1.等待时检测：发现早，恢复代价小，开销大（overhead)。2.定时检测：3.资源（eg.CPU）利用率下降时检测。,3.8.9死锁的恢复,1.重新启动简单，代价大，涉及未参与死锁的进程。2.终止进程(processtermination)环路上占有资源的进程。(1)一次性全部终止；(2)逐步终止（优先级，代价函数）3.剥夺资源(resourcepreemption)+进程回退(rollback)(1)selectavictim；(2)rollback.问题:(1)保存snapshot代价大；(2)消除影响困难;(3)starvation.,3.9线程的概念,3.9.1线程的引入3.9.2线程的概念3.9.3线程的结构3.9.4线程的实现,ThreadandProcess,3.9.1线程的引入,进程切换上下文涉及内容多，开销大，“笨重”相关进程之间耦合关系差解决方案Multi-threading同一进程中包含多个线程上下文只涉及寄存器和用户栈，切换速度快相关线程之间通讯方便、快捷,3.9.2线程的概念,进程中一个相对独立的执行流。进程vs.线程进程是资源分配单位线程是执行单位多线程优点切换速度快（地址空间不变）(lightweighted)系统开销小通讯容易（共享数据空间）,线程控制块,TCB（Threadcontrolblock)标志线程存在的数据结构，其中包含对线程管理需要的全部信息内容线程标识线程状态调度参数现场(通用寄存器,PC,SP)存放位置用户级线程：目态空间（运行系统）核心级线程：系统空间,3.9.3线程结构,寄存器,多进程结构（用户视图）,3.9.3线程结构,静态数据,程序代码,栈,栈,寄存器,寄存器,线程1：,线程2：,进程,动态堆,内存,多线程结构（用户视图）,3.9.3线程结构（另一种表示）,Task:,3.9.4线程的实现,用户级别线程User-levelthread核心级别线程Kernel-levelthread,用户级别线程,实现方法：基于library函数，系统不可见线程创建、撤销、状态转换在目态完成TCB在用户空间，每个进程一个系统栈优点：不依赖于操作系统，调度灵活切换速度快缺点：同一进程中多个线程不能真正并行一个线程进入系统受阻，进程中其它线程不能执行,用户级别线程,用户空间,系统空间,核心级线程,实现方法：基于系统调用创建、撤销、状态转换由操作系统完成优点：同一进程内多线程可以并行执行一线程进入核心等待，其它线程仍可执行缺点：系统开销大，同一进程内多线程切换速度慢调度算法不能灵活控制,核心级线程,进程,线程,核心栈,进程表,用户空间,系统空间,TCB,第4章处理机调度,处理机调度是指处理机在可运行实体上的分配,进程、线程,不同类型的操作系统采用不同的处理机的调度策略,批处理系统、分时系统、实时系统,第4章处理机调度,分级调度作业调度进程调度调度算法实时调度算法,4.1分级调度,4.1.1作业的状态及其转换,一个作业从用户提交开始到占有处理机被执行，要由系统经过多级调度才能实现。,通常指批处理系统,一个作业从提交给计算机系统到执行结束退出系统，一般都要经历提交、收容、执行和完成等四个状态。,4.1.1作业的状态及其转换,作业的状态及其转换,4.1.1作业的状态及其转换,作业的提交状态：从输入设备进入外部存储设备的过程。作业的后备状态：作业的全部信息输入至输入井。作业的执行状态：被作业调度程序选中的作业所处的状态。作业的完成状态：作业运行完毕，所占用的资源尚未全部被系统回收。,4.1.2调度的层次,只有参与竞争处理机所必需的资源都已经得到满足的进程才能有资格竞争处理机。这些必需的资源包括内存、外设及有关数据结构等。,4.1.2调度的层次,处理机调度分为4级：作业调度（高级调度）交换调度（中级调度）进程调度（进程调度）线程调度,对输入井的作业进行选择，为其分配内存、设备；创建根进程；回收系统资源,根据系统并发度，完成进程在内外存的换入和换出。,选取一个处于就绪状态的进程占用处理机,4.1.3作业与进程的关系,作业是用户向计算机提交任务的任务实体进程是为了完成用户任务实体二设置的执行实体。一个作业由一个以上的进程组成。,作业,进程,4.2作业调度,4.2.1作业调度功能,1）记录系统中各作业的状况。2）从后备队列中挑选出一部分作业投入执行。3）为被选中作业做好执行前的准备工作。4）在作业执行结束时善后处理工作。,主要完成作业从后备状态到执行状态的转变，以及从执行状态到完成状态的转变。,4.2作业调度,4.2作业调度,4.2.2作业调度目标与性能衡量,作业调度目标：1）对所有作业应该是公平合理的2）应使设备有高的利用率3）每天执行尽可能多的作业4）有快的响应时间,性能衡量指标：周转时间带权周转时间,4.3进程调度,4.3.1进程调度的功能,1.记录系统中所有进程的执行情况2.选择占有处理机的进程3.进行进程上下文切换,4.3进程调度,4.3.2进程调度的时机,剥夺式调度与非剥夺式调度,剥夺式(preemptive)就绪进程可以从运行进程手中抢占CPU。非剥夺式(non-preemptive)就绪进程不可从运行进程手中抢占CPU。,4.3进程调度,4.3.2进程调度的时机,进程调度的原因：1）运行的进程执行结束2）运行的进程调用阻塞原语（主动等待）3）运行的进程调用了P、V原语4）运行的进程提出I/O请求5）分时系统中时间片已经用完6）系统进程执行完毕时7）就绪队列中的某个进程的优先级别高于当前执行进程的优先级。,进程等待,4.3进程调度,4.3.2进程调度性能评价,进程调度性能的衡量是操作系统设计的一个重要指标。,进程调度性能的衡量方法可分为定性和定量两种：定性衡量方面：可靠性和简洁性定量衡量方面：CPU的利用率评价、就绪进程的等待时机与执行时间之比等。,4.4调度算法,1先到先服务FCFS算法,按作业和进程的提交顺序或申请CPU（就绪）的次序。Gantt图（到达次序：P1，P2，P3）,P1,P2,P3,0273035,平均等待时间：（0+27+30）/3=19（ms)Gantt图（到达次序：P2，P3，P1）平均等待时间（0+3+8）/3=3.67,P1,P2,P3,03835,4.4调度算法,1先到先服务FCFS算法,1先到先服务算法,优缺点：“公平”；短作业等待时间长。,作业的执行时间短,2短作业优先,SJF（ShortestJobFirst)按作业的执行时间长度Gantchart:,P1,P3,P2,P4,0381527,2短作业优先(SJF),平均等待时间：（0+3+8+15）/4=6.5（ms)特点：假定所有任务同时到达，平均等待时间最短。长作业可能被饿死。,3最高优先数算法(HPF),静态优先数(static)优先数在进程创建时分配，生存期内不变。响应速度慢，开销小，系统效率低。适合批处理进程动态优先数(dynamic)进程创建时继承优先数，生存期内可以修改。响应速度快，开销大。,适用于实时系统,作业或进程执行之前就确定,作业进程执行的过程中确定,3最高优先数算法,非剥夺式静态优先数获得处理机的进程运行，直至终止等待剥夺式动(静)态优先数获得处理机的进程运行，直至终止等待出现高优先级的进程,作业调度中静态优先数的确定原则：1）用户确定2）根据作业类型指定3）根据资源情况指定2）和3）都是由系统和操作员确定的,进程调度中静态优先数的确定原则：1）进程类型2）继承作业的优先数,3最高优先数算法(Cont.),3最高优先数算法,进程的动态优先数的确定原则：1）根据进程占有CPU时间的长短。2）根据就绪进程等待CPU的时间长短。,4循环轮转算法(RR),基本思路：让每个进程在等待队列中的等待时间与享受服务的时间成比例。,4循环轮转算法(RR),RoundRobin(RR)基本轮转时间片(quantum,timeslice)长度固定，不变；所有进程等速向前推进。改进轮转时间片长度不定，可变。,适用于分时系统,4循环轮转算法,时间片长度：几十毫秒几百毫秒(eg.50ms)过长：响应速度慢；过短：系统开销(overhead)大。适应系统：分时系统,主机把时间片轮流分配给各个终端,5多级队列算法(MLQ),多级队列多个就绪队列，进程所属的队列固定。例如：通用系统中：队列1：实时进程就绪队列（HPF）队列2：分时进程就绪队列（RR）队列3：批处理进程就绪队列（HPF）,6反馈排队算法(FB),Feed-Back:多个就绪队列，进程所属队列可变。,Q1（RR，HPF）,Q2（RR，HPF）,Qn（RR，HPF）,运行s1时间片,运行s2时间片,.,创建唤醒,优先级时间片,运行sn时间片,6反馈排队算法,调度效果：资源利用率高被唤醒的进程尽早投入运行；响应速度快交互式进程反应及时；系统开销小计算量大的进程落入底层队列。,FeedBack,4.5实时系统调度方法,4.5.1实时系统的特点,1）有限等待时间2）有限响应时间3）用户控制4）可靠性高5）系统出错处理能力强,实时操作系统的能力：1.很快的进程或线程切换速度2.快速的外部中断响应能力3.基于优先级的随时抢先式调度策略,4.5实时调度(real-timescheduling),实时任务：具有明确时间约束的计算任务。Eg.某时刻前必须开始处理某时刻前必须处理完毕实时调度：合理安排就绪实时任务的执行次序，满足每个实时任务时间约束条件的调度。,实时任务分类,硬实时与软实时硬实时:必须满足任务截止期要求.软实时:期望满足截止期要求.周期性与随机性周期性:每隔固定时间发生一次随机性:由随机事件触发，其发生时刻不确定,?,术语解释,Readytime:就绪时间Startingdeadline:开始截止期Processingtime:处理时间Completiondeadline:完成截止期Occurringfrequency:发生频率,4.5实时调度(real-timescheduling),4.5.2实时调度算法的分类,1.静态表格驱动类2.静态优先级驱动抢先式调度算法类3.动态计划调度算法类4.尽力而为调度算法类,4.5实时调度(real-timescheduling),4.5.3时限调度算法与频率单调调度算法,周期性实时事务,令Ci为任务Pi处理时间，Ti为任务Pi的发生周期，则任务P1,Pm可调度的必要条件为：,周期性实时事务,例：P1=100,P2=200,P3=500(ms)C1=50,C2=30,C3=100(ms)C1/P1+C2/P2+C3/P3=0.5+0.15+0.2=0.851Schedulable,周期性实时事务,