计算机操作系统第三版全部课件.ppt

《计算机操作系统第三版全部课件.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统第三版全部课件.ppt（313页珍藏版）》请在三一办公上搜索。

1、操 作 系 统 原 理Operating System,第1章 操作系统绪论,操作系统的概念操作系统的历史操作系统的特性操作系统的基本类型操作系统的功能计算机硬件简介算法的描述研究操作系统的观点,1.1 操作系统概念,操作系统的地位引入操作系统的目的操作系统定义,What is operating system?,1.1.1 操作系统地位,硬件抽象层（HAL）之上所有其它软件层之下,硬件（HAL）,OS,其它系统软件层（如编译软件）,应用软件层,1.1.2 引入操作系统的目的,从用户的观点：为用户（应用程序）提供良好的服务界面。API、GUI从系统管理员的观点：为管理和分配系统资源，提高系统工

2、作效率。从发展的观点：为系统提供功能扩展平台。,1.1.3 操作系统定义,操作系统是位于硬件层(HAL)之上，所有其它软件层之下的一个系统软件，是管理和控制系统中各种软硬件资源，方便用户使用计算机系统的程序集合。,Operating supervisormonitoring program,1.2 操作系统的历史,操作系统的产生手工操作阶段成批处理阶段执行系统阶段操作系统的完善多道批处理系统分时系统实时处理系统通用操作系统,操作系统的发展网络操作系统分布式操作系统多处理机操作系统单用户操作系统面向对象操作系统嵌入式操作系统智能卡操作系统,Evolution,1.3 操作系统特性,程序并发性多个

3、程序在宏观上同时向前推进、微观上串行推进并发(concurrent)vs.并行(parallel)资源共享性多个程序共用系统中的各种软硬件资源在操作系统的协调和控制下虚拟性 物理上的一台设备变成逻辑上的多台设备不确定性,1.4 操作系统的基本类型,多道批处理操作系统(batch processing system)分时操作系统(time-sharing system)实时操作系统(real time system)通用操作系统(multi-purpose system)单用户操作系统(single user system)网络操作系统(network operating system)分布式操

4、作系统(distributed operating system)多处理机操作系统(multi-processor system),1.4.1 多道批处理系统（Off-line）,1.4.1 多道批处理系统,特点多道：系统中同时容纳多个作业成批：作业分批进入系统宏观上并行，微观上串行 多道批处理系统是以脱机为标志的操作系统，适用于处理运行时间比较长的程序。主机中作业合理搭配目标1：提高资源利用率目标2：提高吞吐量(throughput),分时处理终端请求,界面1：交互式命令语言(eg.shell,command)界面2：图形用户界面(GUI),1.4.2 分时操作系统（On-line）,Tim

5、e Sharing OS,HAL,终端,终端,终端,.,1.4.2 分时操作系统,特点：多路性：一个主机与多个终端相连；交互性：以对话的方式为用户服务；独占性：每个终端用户仿佛拥有一台虚拟机。分时操作系统是以联机为标志的操作系统，特别适用于程序的动态调试与修改。,1.4.3 实时操作系统,实时控制工业控制，军事控制，医疗控制，.实时信息处理航班定票，联机情报检索，.,实时控制,HAL,Real Time OS,被控对象,A/D,D/A,t1,t2,t2-t1:response time,实时信息处理,HAL,Real Time OS,.,终端,终端,终端,通常为远程终端,特点：（1）响应及时（

6、prompt response）（2）可靠性高（high reliability）,1.4.4 通用操作系统(multi-purpose OS),同时具有：分时、实时、批处理功能。目标：提高处理能力;扩展应用领域。常见模式:分时(前台)+批处理(后台)实时(前台)+批处理(后台),Foreground/BackgroundSystem,1.4.5 单用户操作系统,同一时刻仅有一个用户使用的系统应用领域：台式机，笔记本，.特点：单用户，多进程，多线程,不同的程序，不同的进程；相同的程序,不同的线程,1.4.6 网络操作系统,DOS3,host3,NOS2,host2,Printer,建立在宿主操

7、作系统之上，提供网络通讯、网络资源共享、网络服务的软件包。,NOS1,host1,网络操作系统的目标,相互通讯资源共享（信息，设备）提供网络服务database serverftp servere-mail servertelnet serveretc.,No Transparent view,1.4.7 分布式操作系统,紧耦合：(tightly coupled)由多机系统发展而来（多CPU）有公共内存多处理机操作系统,1.4.7 分布式操作系统,松散耦合：(loosely coupled)由计算机网络发展而来（多Host)无公共内存，无公共时钟,DOS,host3,DOS,host2,DOS

8、,host1,1.4.7 分布式操作系统,分布式操作系统特征:统一的操作系统 资源的进一步共享可靠性 透明性,1.4.8 多处理机操作系统,多处理机系统具有公共内存的多CPU系统对称多处理机系统(SMP)没有主从关系的多处理机系统多处理机操作系统有效管理和使用多个CPU的操作系统复杂性：多个主动体（CPUs)例子：UNIX,Linux,Windows,1.5 操作系统的功能,处理机管理存储管理设备管理信息管理（文件系统管理）用户接口,1.6 计算机硬件简介1.6.1 计算机的基本硬件元素,构成计算机基本硬件元素包含以下4种：处理器、存储器、输入输出控制与总线、外部设备。,计算机的基本硬件元素,

9、1.6.2 与操作系统相关的几种主要寄存器,1.数据寄存器2.地址寄存器3.条件码寄存器4.程序计数器PC5.指令寄存器IR6.程序状态字PSW7.中断现场保护寄存器8.过程调用用堆栈,1.6.3 存储器的访问速度,存储介质的访问速度,一般来说，速度高的存储介质，成本高，容量小；容量大的存储介质，速度慢，成本低。,1.6.4 指令的执行与中断,指令的执行周期,中断执行过程f,1.6.4 指令的执行与中断,中断处理时的指令执行周期,1.7 算法的描述,算法描述的方式：自然语言 流程图方式 类Pascal语言 本书：begin Repeat While 条件 If 条件 end 操作 do the

10、n 操作 操作 Until od else 操作,1.8 研究操作系统的几种观点,操作系统是计算机资源的管理者用户界面的观点进程管理的观点,第2章 操作系统用户界面,用户界面简介一般用户的输入输出界面命令控制界面Linux与Windows的命令控制界面系统调用,2.1用户界面简介,用户界面的功能 用户界面负责用户与操作系统之间的交互。用户分类 使用和管理计算机的应用程序的用户 程序开发人员 用户界面分类 命令控制界面 系统调用,2.2 一般用户的输入输出界面,2.2.1 作业的定义 2.2.2 作业组织 2.2.3 一般用户的输入输出方式,作业的定义,在一次应用业务处理过程中，从输入开始到输出

11、结束，用户要求计算机所做的有关该次业务处理的全部工作称为一个作业。作业由不同的顺序相连的作业步组成。,图2.1 一般编程过程,2.2.2 作业组织,图2.2 作业说明书的主要内容,一般用户的输入输出方式,1.联机输入输出方式 外围设备直接和主机相连，速度慢。2.脱机输入输出方式 外围机进行联机输入输出处理，通过外围机的后援存储来实现和主机的连接。速度快。3.直接耦合方式 主机和外围机通过一个公共外存直接连接。速度快，人工不用干预,一般用户的输入输出方式,图2.3 直接耦合方式,4.SPOOLING系统5.网络联机方式,2.2.3 一般用户的输入输出方式,外围设备通过通道或DMA器件与主机和外存

12、相连。,2.3 命令控制界面,用户使用命令控制界面的方式：1、脱机方式 填写作业说明书，用户不能干预作业执行。2、联机方式 不用填写作业说明书，用户能够干预作业执行。,2.4Linux与Windows的命令控制界面,Redhat Linux 9.0的窗口界面,的命令控制界面,的命令控制界面,Linux的命令一般包含9类：1 系统维护与管理命令文件操作与管理命令进程管理命令磁盘及设备管理命令用户管理命令文档操作命令网络通信命令程序开发命令X Windows管理命令,2.4.2 Windows的命令控制界面,Windows的命令控制界面分为两个部分：窗口交互：通过键盘和鼠标在图形上操作。命令解释器

13、：通过cmd.exe为用户服务。,2.4.2 Windows的命令控制界面,图2.6相互调用批处理示例,2.5 系统调用,系统调用分为6类：1 设备管理2 文件管理3 进程控制4 进程通信5 存储管理6 线程管理,2.5 系统调用,系统调用的处理过程,第3章 进程管理,进程的概念进程的描述进程状态及其转换进程控制进程互斥进程同步进程的通信死锁问题线程的概念、分类与执行,3.1 进程的概念,3.1.1 程序的并发执行3.1.2 进程的定义,程序的并发执行,程序(program)用来描述计算机所要完成的独立功能，并在时间上严格地按前后次序相继地进行计算机操作序列集合，是一个静态的概念。2.程序的顺

14、序执行（sequence)程序顺序执行的概念 一个具有独立功能的程序独占处理机直至最终结束的过程称为程序的顺序执行。程序顺序执行的特征 顺序性 封闭性 可再现性,程序的并发执行,3.程序的并发(concurrent)执行 程序的并发执行：宏观上同时向前推进，微观上同一时刻只有一个程序运行。程序并发执行分为两种：一种是程序间的并发。另一种是同一程序内部多条指令的并发。程序并发执行的特性：交叉性、非封闭性、不可再现性,程序的并发执行,4.程序的顺序性与并发性举例：顺序性内部顺序性：P1:a1,a2,a3;P2:b1,b2,b3外部顺序性：a1,a2,a3,b1,b2,b3;b1,b2,b3,a1,

15、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 进程的定义,进程与程序的区别与联系：进程是一个动态概念，程序是一个静态概念。进程具有并发特征，而程序没有。进程是竞争计算机系统资源的基本

16、单位。不同的进程可以包含同一程序，只要该程序所对应的数据集不同。,3.2 进程的描述,进程控制块进程组成与进程上下文进程上下文的切换进程空间与大小进程的类型进程的相互联系与相互作用,3.2.1 进程控制块PCB,定义：标志进程存在的数据结构，其中保存系统管理进程所需的全部信息。PCB的内容：(不同系统不尽相同)1.描述信息2.控制信息3.资源管理信息4.CPU现场保护结构,Process Control Block,3.2.2 进程的组成与上下文,进程的组成进程控制块(process control block)建立进程建立PCB撤销PCB撤销进程程序代码(code)数据(data)堆栈(st

17、ack+heap),3.2.2 进程的组成与上下文,进程的表记,PCB,程序,PCB,代码,数据+堆栈,表记1,表记2,系统空间,用户空间,3.2.2 进程的组成与上下文,进程上下文（process context)进程的物理实体与支持进程运行的物理环境统称为进程上下文。PCB+程序系统环境：地址空间，系统栈，打开文件表，,3.2.2 进程的组成与上下文,进程上下文结构,3.2.3 进程上下文切换,上下文切换（context switch)由一个进程的上下文转到另外一个进程的上下文系统开销（system overhead)运行操作系统程序完成系统管理工作所花费的时间和空间,3.2.3 进程上下

18、文切换,进程上下文的切换过程,3.2.4 进程空间与大小,进程在内存中自己拥有的一个地址空间称为进程空间。进程空间的大小只与处理机的位数有关。一般，进程空间可以分为：用户空间与系统空间。用户程序在用户空间中运行。操作系统内核程序在系统空间中运行。,3.2.5 进程的类型,进程类型系统进程运行操作系统程序，完成系统管理(服务)功能.用户进程运行用户(应用)程序，为用户服务。,3.2.6 进程间相互联系与相互作用,相互联系相关进程同一家族的进程可以共享文件，需要相互通讯，协调推进速度父进程可以监视子进程，子进程完成父进程交给的任务。无关进程没有逻辑关系、同时执行的进程。有资源竞争关系，互斥、死锁、

19、饿死。,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 进程状态转换,状态

20、转换就绪运行：获得处理机运行就绪：剥夺处理机运行等待：申请资源未得到，启动IO等待就绪：得到资源，IO中断,3.3.2 进程状态转换图,Keep in Mind,3.3.2 进程状态转换图,初创,终止,创建,结束,3.3.3 进程队列,1.就绪队列：系统一个或若干个（根据调度算法确定）2.等待队列：每个等待事件一个3.运行队列：每个处理机一个,PCB构成的队列：（不一定FIFO),3.4 进程控制,进程控制：系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。原语：系统态下执行的某些具有特定功能的程序段。原语的分类

21、：机器指令级：不许中断 功能级：不许并发,3.4.1 进程创建与撤销,进程创建方式：系统创建 父进程创建,3.4.1 进程创建与撤销,进程撤销的方式：正常终止非正常终止祖先进程撤销,3.4.2 进程的阻塞与唤醒,阻塞原语图,阻塞原语实现了进程由执行状态到等待状态的转变。阻塞原语是由进程自己调用的。,3.4.2 进程的阻塞与唤醒,唤醒原语,唤醒原语实现了进程由等待状态到就绪状态的转变。唤醒的方式:系统进程唤醒 事件发生进程唤醒,3.5 进程互斥,与时间有关的错误共享变量与临界区域进程互斥进程互斥的实现信号灯与P，V原语,3.5.1 与时间有关的错误,例：图书借阅系统（x:某种书册数，设当前x=1

22、.）终端1：终端2：CYCLE CYCLE 等待借书者；等待借书者；IF x=1 Then IF x=1 Then Begin Begin x:=x-1;x:=x-1;借书 借书 End End Else 无书 Else 无书 End End,3.5.1 与时间有关的错误,错误原因之1：进程执行交叉(interleave);错误原因之2：涉及公共变量(x)。注意:某些交叉结果不正确;必须去掉导致不正确结果的交叉。,3.5.2 共享变量与临界区域,共享变量（shared variable）多个进程都需要访问的变量。临界区域（critical region）访问共享变量的程序段。,一组公共变量,C

23、R1,CR2,CRn,.,临界区的表示,共享变量:shared 临界区域:region do 语句例子：shared B:array0,.,n-1of integer;region B do region B do begin begin(访问B）.（访问B）.end;end;,3.5.3 进程互斥,定义：多个进程不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象称为进程互斥。二层涵义：（1）任何时刻最多只能有一个进程处于同一组共享变量的相同的临界区域；（2）任何时刻最多只能有一个进程处于同一组共享变量的不同的临界区域。注意:互斥是相对于公共变量而言的。,并发进程

24、互斥执行必须满足4条准则：不能假设并发进程的相对执行速度。某进程不在临界区，不能阻止其他进程进入临界区。若干进程申请进入临界区，只能允许一个进程进入。某进程申请进入临界区，应该在有限的时间内得以进入临界区。,3.5.3 进程互斥,3.5.4 进程互斥的实现,进程互斥的实现有两种方法：软件方法实现：完全用程序实现，不需特殊硬件指令支持。可用于单CPU和多CPU环境中。有忙式等待问题,Busy waiting“运行”或“就绪”,3.5.4 进程互斥的实现,硬件方法实现：硬件提供“测试并建立”指令、“交换”指令 硬件提供“关中断”和“开中断”指令 关中断 Critical Region 开中断Rem

25、arks:(1)开关中断只在单CPU系统中效;(why?)(2)影响并发性。,3.5.4 进程互斥的实现,例：对临界区加锁实现互斥:当某个进程进入临界区之后，它将锁上临界区，直到它退出临界区时为止。lock(key s)临界区 unlock(key s),3.5.5 信号灯与P，V原语,1965.信号灯与PV操作的定义 TYPE semaphore=RECORD value:integer;queue:PCB pointer;END;VAR s:semaphore;备注:(1)semaphore 是一个提前定义好的数据类型.(2)s 是一个信号灯变量,使用前必须先声明.例如:var s1,s2

26、:semaphore;,信号灯变量,S.valueS.queue,Var S:semaphore;,FIFO,P操作原语,P操作原语：Procedure P(var s:semaphore)s.value:=s.value-1;If s.value0 Then asleep(s.queue)Endasleep(s.queue):(1)执行此操作进程的PCB入s.queue尾（状态改为等待）；(2)转处理机调度程序。,Primitive:a piece of code un-interruptible,V操作原语,V操作原语：Procedure V(var s:semaphore)s.value

27、:=s.value+1;If s.value=0 Then wakeup(s.queue)Endwakeup(s.queue)s.queue链头PCB出等待队列，进入就绪队列（状态改为就绪）。,Primitive:a piece of code un-interruptible,规定和结论,对于信号灯变量的规定：必须置一次初值，只能置一次初值，初值=0;只能执行P操作和V操作，所有其它操作非法。几个有用的结论：当s.value=0时，s.queue为空；当s.value0时，|s.value|为队列s.queue的长度；当s.value初=1时，可以实现进程互斥；当s.value初=0时，可以

28、实现进程同步。,用信号灯实现进程互斥,Var mutex:semaphore;(初值=1）shared x,y,z:integer;CR1 CR2 CRn,用信号灯实现进程互斥,Var mutex:semaphore;(初值=1）shared x,y,z:integer;P(mutex)P(mutex)P(mutex)CR1 CR2 CRnV(mutex)V(mutex)V(mutex),互斥例子：借书系统(revisited),Var mutex:semaphore;(initial value is 1)终端1：终端2：CYCLE CYCLE 等待借书者；等待借书者；P(mutex)P(m

29、utex)IF x=1 Then IF x=1 Then Begin Begin x:=x-1;x:=x-1;V(mutex)V(mutex)借书 借书 End End Else V(mutex);无书;Else V(mutex);无书;End End,3.6 进程同步,3.6.1 进程同步的概念例：司机-乘客问题 司机活动：(P1)乘客活动：(P2)do do 启动车辆 上 车 正常行驶 投 币 到站停车 下 车 while(1)while(1),3.6.1 进程同步的概念,定义：一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间这种相互制约的关系称为进程同步。,P1

30、:,P2:,synchronize,后,先,3.6.2 进程同步机制,定义：用于实现进程同步的工具称为同步机制（synchronization mechanism）同步机制要求：描述能力够用;可实现;高效;使用方便.,3.6.3 用信号灯实现进程同步,General Case:VAR S:semaphore;(initial value 0),P(S)后动作,先动作 V(S),P1:,P2:,用信号灯实现进程同步,例子：司机-乘客问题：VAR s1,s2:semaphore;(initial value 0)司机活动：售票员活动：Repeat Repeat P(S1)上 车 启动车辆 V(S1

31、)正常行驶 投 币 到站停车 P(S2)V(S2)下 车 Until false Until false,典型的进程同步问题,生产者消费者问题,生产者/消费者问题,预备知识：组合资源：若干相对独立的资源构成的资源集合，其中每个相对独立的资源称为子资源。同种组合资源：相同类型子资源构成的组合资源。管理：Var S:semaphore;(初值=子资源个数）例子：2台打印机 Var S: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

32、.value=空闲资源数 S.queue=空,|S.value|=等待进程数 空闲资源数=0,.,生产者/消费者问题,0 1 k-1,箱子，容量k B:Array0.k-1Of item,生产者,消费者,生产物品放入B中,从B中取物品消费之,环形缓冲区,1,0,K-1,in,(in+1)mod k,out,(out+1)mod k,问题分析,生产者活动：消费者活动：do do 加工一件物品 箱中取一物品 物品放入箱中 消耗这件物品 while(1)while(1),资源：箱子（同种组合）资源：物品（同种组合）Var S1:semaphore;Var S2:semaphore;S1.value=

33、k;S2.value=0;放前：P（S1）取前：P（S2）放后：V（S2）取后：V（S1）,同 步,生产者活动：消费者活动：Repeat Repeat 加工一件物品 P(S2)P(S1)箱中取一物品 物品放入箱中 V(S1)V(S2)消耗这件物品 Until false Until false对B和in,out的互斥：Var mutex:semaphore;(mutex.value=1),互 斥,生产者活动：消费者活动：Repeat Repeat 加工一件物品 P(S2)P(S1)P(mutex)P(mutex)箱中取一物品 物品放入箱中 V(mutex)V(mutex)V(S1)V(S2)消

34、耗这件物品 Until false Until false,程序,Program producers_consumers;Var B:Array0,k-1Of item;S1,S2,mutex:semaphore;in,out:0.k-1;,Procedure producer cycle produce a product P(S1);P(mutex);Bin:=product;in:=(in+1)mod k;V(mutex);V(S2)end,Procedure consumer cycle P(s2);P(mutex);x:=Bout;out:=(out+1)mod k;V(mutex)

35、;V(S1);consume x;end;,程 序,Begin S1.value:=k;S2.value:=0;mutex.value:=1;in:=0;out:=0;Cobegin P1:producer;,Pm:producer;C1:consumer;,Cn:consumer;Coend;End.,并发性提高策略,生产者和消费者：不操作B的相同分量,生产者的共享变量：Bin，in,消费者的共享变量：Bout，out,in=out:满或空,Var mutex1,mutex2:semaphore;(init 1),并发性提高策略,生产者活动：消费者活动：Repeat Repeat 加工一件物

36、品 P(S2)P(S1)P(mutex2)P(mutex1)箱中取一物品 物品放入箱中 V(mutex2)V(mutex1)V(S1)V(S2)消耗这件物品 Until false Until false,3.7 进程通信,进程通信：进程之间的数据传送。低级通讯（简单信号）进程互斥进程同步高级通讯（大宗信息）,3.7.1 进程通信的概念,3.7 进程通信,单机系统中进程通信可以分为4种形式：1、主从式 2、会话式 3、消息或邮箱机制 4、共享存储方式,3.8 死锁问题,死锁的概念死锁类型死锁的条件死锁的处理资源分配图死锁预防死锁避免死锁的检测死锁的恢复,3.8.1 死锁的概念,死锁概念,有并发

37、进程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,M

38、1);P2:receive(P3,M2);P3:receive(P1,M3);其它原因引起的死锁After you/after you,3.8.3 死锁的条件,Coffman条件（必要条件）资源独占（mutual exclusion）不可抢占（non preemption）保持申请（hold-while-applying）循环等待（circular wait）当每类资源只有一个实例时，充要条件。破坏上述任意一个条件可以消除死锁。,3.8.4 死锁的处理,死锁预防（deadlock prevention）-静态死锁避免（deadlock avoidance）-动态死锁检测（deadlock de

39、tection）死锁恢复（deadlock recovery）,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

40、 死锁预防,对进程有关资源的活动加限制，所有进程遵循这种限制，即可保证没有死锁发生。优点：简单，系统不需要做什么。缺点：对进程的约束，违反约束仍可能死锁。预防方法：预先分配法；有序分配法。,3.8.6.1 预先分配法,进程：运行前申请所需全部资源；系统：能够满足，全部分配，否则，一个也不分配。破坏“hold-and-wait”条件缺点：资源利用效率低；一次提出申请困难。,3.8.6.2 有序分配法,资源集：R=r1,r2,rn 函数：F：RN 例如：R=scanner,tape,printer F(scanner)=1;F(tape)=2;F(printer)=3;,进程pi可以申请资源rj中

41、的实例rl,pi占有rl,F(rl)F(rj),3.8.6.2 有序分配法,证明无死锁（deadlock free)：反证，假定死锁 时刻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.),Bankers algorithm,E.W.Dijkstra.进程：事先申明所需资源最大量（并不分配）

42、系统：对每个可满足的资源申请命令进行安全性检查。P=p1,p2,pn;R=r1,r2,rm;,银行家算法(Cont.),数据结构：Available:array1.mof integer;/系统可用资源Claim:array1.n,1.mof integer;/进程最大需求Allocation:array1.n,1.mof integer;/当前分配Need:array1.n,1.mof integer;/尚需资源Request:array1.n,1.mof integer;/当前请求临时变量：Work:array1.mof integer;Finish:array1.nof boolean;

43、,银行家算法(Cont.),设X,Y为下标1.l的一维数组：XY j(1jl),XjYj X:=Y j(1jl),Xj:=Yj X:=c j(1jl),Xj:=c XY j(1jl),XjYj,资源分配,Pi请求资源,RequestINeedI,请求超量，错返,RequestIAvailable,不满足，等待,Available:=Available-RequestIAllocationI:=AllocationI+RequestINeedI:=NeedI-RequestI,安全,确认，pi继续,Available:=Available+RequestIAllocationI:=Allocat

44、ionI-RequestINeedI:=NeedI+RequestIpi等待,F,T,F,T,T,F,安全性检测算法,F,银行家算法例子,R=A(10),B(5),C(7)P=p0,p1,p2,p3,p4,Claim Allocation Need Available Work FinishA B C A B C A B C A B C A B C 7 5 3 0 1 0 7 4 3 3 3 23 2 2 2 0 0 1 2 29 0 2 3 0 2 6 0 02 2 2 2 1 1 0 1 14 3 3 0 0 2 4 3 1,P0:p1:p2:p3:p4:,安全进程序列：p1请求：Requ

45、est1=(1,0,2),银行家算法例子,Claim Allocation Need Available Work FinishA B C A B C A B C A B C A B C 7 5 3 0 1 0 7 4 3 2 3 03 2 2 3 0 2 0 2 09 0 2 3 0 2 6 0 02 2 2 2 1 1 0 1 14 3 3 0 0 2 4 3 1,P0:p1:p2:p3:p4:,假定分配：,安全进程序列：p4请求：Request4=(3,3,0),不能满足，等待；p0请求：Request0=(0,2,0),不安全，等待。,3.8.8 死锁的检测,数据结构：Availabl

46、e:array1.mof integer;Allocation:array1.n,1.mof integer;Request:array1.n,1.mof integer;临时变量：Work:array1.mof integer;Finish:array1.nof boolean;,3.8.8.1 死锁检测算法,FinishI=truefor allocationI=0,Remarks,1.上述算法可以检测到参与死锁的全部进程，包括占有资 源和不占有资源的进程。2.如果希望只检测占有资源的进程，初始化时：Finishi=true,for AllocationI=0,死锁例子,例子：R=A(7)

47、,B(2),C(6);P=p0,p1,p2,p3,p4,Allocation Request Available Work Finish A B C A B C A B C A B C p0:0 1 0 0 0 0 0 0 0p1:2 0 0 2 0 2 p2:3 0 3 0 0 0p3:2 1 1 1 0 0p4:0 0 2 0 0 2,未死锁。此时，Request2=(0,0,1),死锁，参与死锁进程p1,p2,p3,p4,3.8.8.2 死锁检测时刻,考虑因素：死锁发生频度；死锁影响进程。1.等待时检测：发现早，恢复代价小，开销大（overhead)。2.定时检测：3.资源（eg.CPU

48、）利用率下降时检测。,3.8.9 死锁的恢复,1.重新启动 简单，代价大，涉及未参与死锁的进程。2.终止进程(process termination)环路上占有资源的进程。(1)一次性全部终止；(2)逐步终止（优先级，代价函数）3.剥夺资源(resource preemption)+进程回退(rollback)(1)select a victim；(2)rollback.问题:(1)保存snapshot代价大；(2)消除影响困难;(3)starvation.,3.9 线程的概念,3.9.1 线程的引入3.9.2 线程的概念3.9.3 线程的结构3.9.4 线程的实现,Thread and Pr

49、ocess,3.9.1 线程的引入,进程切换上下文涉及内容多，开销大，“笨重”相关进程之间耦合关系差解决方案Multi-threading同一进程中包含多个线程上下文只涉及寄存器和用户栈，切换速度快相关线程之间通讯方便、快捷,3.9.2 线程的概念,进程中一个相对独立的执行流。进程 vs.线程进程是资源分配单位线程是执行单位多线程优点切换速度快（地址空间不变）(light weighted)系统开销小通讯容易（共享数据空间）,线程控制块,TCB（Thread control block)标志线程存在的数据结构，其中包含对线程管理需要的全部信息内容线程标识线程状态调度参数现场(通用寄存器,PC,

50、SP)存放位置用户级线程：目态空间（运行系统）核心级线程：系统空间,3.9.3 线程结构,寄存器,多进程结构（用户视图）,3.9.3 线程结构,静态数据,程序代码,栈,栈,寄存器,寄存器,线程1：,线程2：,进程,动 态 堆,内存,多线程结构（用户视图）,3.9.3 线程结构（另一种表示）,Task:,3.9.4 线程的实现,3.9.4.1 用户级别线程User-level thread3.9.4.2 核心级别线程Kernel-level thread,3.9.4.1 用户级别线程,实现方法：基于library函数，系统不可见线程创建、撤销、状态转换在目态完成TCB在用户空间，每个进程一个系统