操作系统课件-孟庆昌.ppt

《操作系统课件-孟庆昌.ppt》由会员分享，可在线阅读，更多相关《操作系统课件-孟庆昌.ppt（477页珍藏版）》请在三一办公上搜索。

1、第1章操作系统引论,参考书：操作系统精髓与设计原理第五版 William Stalling 著 操作系统原理与设计 曹先彬 陈兰香 编操作系统第二版 孟庆昌 牛欣源 编,本章内容提要,计算机硬件结构 什么是操作系统操作系统概念 操作系统的主要功能 操作系统的地位 操作系统的发展历程操作系统的类型操作系统的特征操作系统结构设计,1.1计算机硬件结构,计算机系统是由硬件和软件组成的 硬件是软件建立与活动的基础 软件是对硬件进行管理和功能扩充 计算机硬件结构 由五大功能部件组成，即：运算器、控制器、存储器、输入设备和输出设备。它们经由系统总线连接在一起，实现彼此通信。,现代计算机硬件结构,1.1.1

2、 处理器,CPU工作的基本周期是：提取指令，译码分析，执行指令 每个CPU可以执行的指令集是专用的所有CPU都包含某些寄存器通用寄存器 专用寄存器 程序计数器栈指针 PSW（程序状态字）两种处理机执行状态 核心态 用户态,1.1.2 存储器,寄存器高速缓存 内存磁盘磁带,1.1.3 I/O设备,通常由控制器和设备本身两部分组成控制器设备 设备驱动程序,1.1.4 总线,总线分类数据总线地址总线控制总线,1.2 什么是操作系统,1.2.1 操作系统概念1操作系统作为扩展机器 把硬件细节与程序员隔离开，隐藏了底层硬件的特性 功能更强、使用更方便 2操作系统作为资源管理器监视各种资源，随时记录它们的

3、状态；实施某种策略以决定谁获得资源，何时获得，获得多少；分配资源供需求者使用；回收资源，以便再分配。3.操作系统的用户观点和系统观点,定义：操作系统是控制和管理计算机系统内各种硬件和软件资源，有效地组织多道程序运行的系统软件（或程序集合），是用户与计算机之间的接口。,操作系统是系统软件 基本职能是控制和管理系统内各种资源，有效地组织多道程序的运行提供众多服务，方便用户使用，扩充硬件功能,1.2.2 操作系统的主要功能,1存储管理 内存分配 地址映射 内存保护 内存扩充,1.2.2 操作系统的主要功能,2作业和进程管理 作业和进程调度 进程控制 进程通信,1.2.2 操作系统的主要功能,3设备管

4、理 缓冲区管理 设备分配 设备驱动 设备无关性,1.2.2 操作系统的主要功能,4文件管理功能 文件存储空间的管理 文件操作的一般管理 目录管理 文件的读/写管理和存取控制,1.2.2 操作系统的主要功能,5用户接口程序接口命令行接口图形用户接口（GUI）,1.2.3 操作系统的地位,计算机系统的层次关系,简言之，软件是计算机执行的程序软件通常可分为三大类 应用软件 支撑软件 系统软件操作系统是裸机之上的第1层软件，它只在核心态模式下运行。通常把经过软件扩充功能后的机器称为“虚拟机”,1.3 操作系统的发展历程,1.3.1 操作系统的形成 1手工操作阶段 2早期批处理阶段 早期联机批处理 早期

5、脱机批处理 3多道批处理系统,多道批处理系统,多道程序设计：在内存中同时存放多道程序，在管理程序的控制下交替地执行。这些作业共享CPU和系统中的其他资源。并发：多道程序在CPU上交替运行 系统吞吐量：在一段给定的时间内，计算机所能完成的总工作量。,1.3.2 操作系统的发展,1.3.3 推动操作系统发展的动力,硬件技术更新 应用需求扩大,1.4 操作系统的类型,5大基本类型 批处理系统 分时系统 实时系统 网络系统 分布式系统,1.4.1 批处理系统,1作业是用户定义的、由计算机完成的工作单位。它通常包括一组计算机程序、文件和对操作系统的控制语句。作业步 由作业控制语句明确标识的计算机程序的执

6、行过程,2工作流程,多道批处理系统中的作业流程,批处理系统,3.特点 多道：系统在内存中存放多个作业，并且在外存上还保存大量的后备作业。成批：系统按批次调度作业，而在系统运行过程中不允许用户和机器之间发生交互作用。批处理系统的主要优点：系统资源利用率高 系统吞吐量大明显缺点：用户作业的等待时间长 没有交互能力,1.4.2 分时系统,1分时概念和分时系统的实现方法分时：广义上，是指对时间的共享。在分时系统中，分时主要是指若干并发程序对CPU时间的共享并行：是指在同一时刻有两个或两个以上的活动发生。时间片,分时系统,2分时系统的特征和优点 基本特征 同时性 交互性 独立性 及时性主要优点 人机交互

7、友好 应用方便 资源共享,1.4.3 实时系统,1实时系统的引入实时系统 具有实时特性，能够支持实时控制系统工作的操作系统。重要特征：对时间有严格限制和要求 三种典型应用形式 过程控制系统 信息查询系统 事务处理系统,2实时系统与分时系统的差别 交互性 实时性 可靠性,实时系统,3实现方式 硬式实时系统 对时间严格约束 软式实时系统 对时间限制稍弱一些,1.4.4 网络操作系统,1计算机网络的特征 分布性 自治性 互连性 可见性,2网络操作系统 服务器 客户机 网络操作系统实现网络通信、资源共享和保护，以及提供网络服务和网络接口等 本地操作系统完成本地资源的管理和服务功能 客户-服务器模式 S

8、un公司的NFSNovell公司的Netware 5.0Microsoft公司的Windows NT Server 4.0IBM公司的LAN Server 4.0SCO公司的UNIX Ware 7.1自由软件Linux,3网络操作系统的特性接口一致性 资源透明性 操作可靠性 处理自主性 执行并行性,1.4.5 分布式操作系统,分布式系统特点 透明性 灵活性 可靠性 高性能 可扩充性,1.4.6 其他操作系统,1.个人机系统 Windows XP、Windows Vista、UNIX、Linux 2.多处理器系统 对称多处理（SMP）系统 增加吞吐量 提高性能/价格比 提高可靠性 3嵌入式系统,

9、1.5 操作系统的特征,（1）并发 两个或多个活动在同一给定的时间间隔中进行。（2）共享 计算机系统中的资源被多个进程所共用。（3）不确定性 系统中各种事件发生顺序的不可预测性。,1.6 操作系统结构设计,1.6.1 整体系统 任意调用，耦合紧密，实现的效率高 结构关系不清晰，系统的可靠性降低,模块调用示意图,1.6.2 层次式系统,THE操作系统的层次结构具有整体系统的长处新优点结构关系清晰，提高系统的可靠性、可移植性和可维护性。,1.6.3 虚拟机结构,带CMS的VM/370结构,通过共享物理机器资源来实现主要优点 同时运行多个操作系统 系统安全,有效地保护系统资源 提供良好的工作环境 组

10、建虚拟网络,1.6.4 客户-服务器系统,客户-服务器系统模型 微内核,客户-服务器系统,适于在分布式系统中应用,分布式系统中的客户-服务器模型,第2章 进程和线程,本章内容提要,进程概念 进程的状态和组成进程管理 线程 进程的同步和通信 经典进程同步问题 管程 进程通信,2.1 进程概念,2.1.1 多道程序设计 1顺序程序活动的特点 顺序性 封闭性 可再现性 2多道程序设计 程序并发执行 提高系统资源利用率 增加作业吞吐量,多道程序设计,3程序并发执行的特征 失去封闭性 程序与计算不再一一对应 并发程序在执行期间相互制约,2.1.2 进程概念,1进程概念的引入 多道程序并发执行所引发的一系

11、列新情况,2进程概念,进程最根本的属性是动态性和并发性进程定义：程序在并发环境中的执行过程进程和程序的区别（1）动态性（2）并发性（3）非对应性（4）异步性,进程概念,3进程的基本特征（1）动态性（2）并发性（3）调度性,2.2 进程的状态和组成,2.2.1 进程的状态及其转换 1进程的基本状态 运行状态（Running）就绪状态（Ready）阻塞状态（Blocked）,进程的5种基本状态及其转换,2进程状态的转换,（1）新建就绪（2）就绪运行（3）运行阻塞（4）阻塞就绪（5）运行就绪（6）运行终止,2.2.2 进程描述,1进程映像 进程映像通常就由程序、数据集合、栈和PCB等4部分组成,进程

12、映像模型,进程描述,2进程控制块的组成进程控制块（PCB）也称进程描述块（Process Descriptor），它是进程组成中最关键的部分，其中含有进程的描述信息和控制信息，是进程动态特性的集中反映，是系统对进程施行识别和控制的依据。,进程描述,进程控制块应包含的主要内容：进程名特征信息进程状态信息调度优先权通信信息现场保护区资源需求进程实体信息族系关系其他信息,进程描述,3进程控制块的作用每个进程有惟一的进程控制块操作系统根据PCB对进程实施控制和管理进程的动态、并发等特征是利用PCB表现出来的PCB是进程存在的唯一标识,2.2.3 进程队列,1线性方式,PCB线性队列示意图,进程队列,2

13、链接方式,PCB链接队列示意图,PCB索引结构示意图,3索引方式,进程队列,2.3 进 程 管 理,2.3.1 进程图 进程图（Process Graph）是描述进程族系关系的有向树,进程创建的层次关系,2.3.2 进程创建,引发创建进程的事件：调度新作业用户登录 操作系统提供特定服务 派生新进程,进程创建,创建新进程时要执行创建进程的系统调用（如UNIX/Linux系统中的fork）其主要操作过程有如下四步：（1）申请一个空闲的PCB（2）为新进程分配资源（3）将新进程的PCB初始化（4）将新进程加到就绪队列中,#include#include#include int main(int ar

14、gc,char*argv)int pid;pid=fork();/*创建一个子进程*/if(pid 0)/*出现错误。进程ID号不可能小于0*/fprintf(stderr,Fork Failed);/*输出出错消息Fork Failed*/exit(-1);/*程序终止，返回码-1*/else if(pid=0)/*下面是子进程执行*/execlp(/bin/ls,ls,NULL);/*执行目录/bin下面的ls命令*/else/*下面是父进程执行*/wait(NULL);/*父进程等待子进程完成*/printf(Child Complete);/*输出子进程完成的信息*/exit(0);/

15、*终止*/,2.3.3 进程终止,导致进程终止的三种情况：正常终止异常终止外部干扰,进程终止,终止进程的主要操作过程如下：找到指定进程的PCB终止该进程的运行回收该进程所占用的全部资源终止其所有子孙进程，回收它们所占用的全部资源。将被终止进程的PCB从原来队列中摘走,进程阻塞,进程阻塞的过程如下：立即停止当前进程的执行现行进程的CPU现场保存现行状态由“运行”改为“阻塞”转到进程调度程序,2.3.5 进程唤醒,唤醒原语执行过程如下：把阻塞进程从相应的阻塞队列中摘下将现行状态改为就绪状态，然后把该进程插入就绪队列中如果被唤醒的进程比当前运行进程的优先级更高，则设置重新调度标志,2.4 线程,2.

16、4.1 线程概念现代操作系统中，进程只作为资源拥有者，而调度和运行的属性赋予新的实体线程。线程（Thread）是进程中实施调度和分派的基本单位,线程概念,1线程的组成每个线程有一个thread结构，即线程控制块，用于保存自己私有的信息，主要由以下4个基本部分组成：一个唯一的线程标识符 一组寄存器 两个栈指针 一个私有存储区,thread结构示意图,线程的组成,线程必须在某个进程内执行一个进程可以包含一个线程或多个线程,单线程和多线程的进程模型,2线程的状态运行状态就绪状态 阻塞状态终止状态,3线程的管理 线程创建 线程终止 线程等待 线程让权,4线程和进程的关系 一个进程可以有多个线程，但至少

17、要有一个线程；而一个线程只能在一个进程的地址空间内活动。资源分配给进程，同一进程的所有线程共享该进程的所有资源。处理机分配给线程，即真正在处理机上运行的是线程。线程在执行过程中需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。,5引入线程的好处 易于调度 提高并发性 开销少 利于充分发挥多处理器的功能,线程的实现,在用户空间实现 优点：切换速度快；调度算法可专用；可运行在任何操作系统上 缺点：阻塞问题；多处理器利用问题 在核心空间实现 优点：克服了用户级线程方式的两个主要缺陷；本身也可以是多线程的 缺点：控制转移开销大 组合方式,2.5 进程的同步和通信,进程间的相互关系主要分为如下

18、三种形式：互斥竞争同一资源而发生相互制约 同步协同完成一项任务 通信交换信息,2.5.1 进程的同步与互斥,1同步 同步进程通过共享资源来协调活动，在执行时间的次序上有一定约束。虽然彼此不直接知道对方的名字，但知道对方的存在和作用。在协调动作的情况下，多个进程可以共同完成一项任务。,2互斥在逻辑上这两个进程本来完全独立，毫无关系，只是由于竞争同一个物理资源而相互制约。它们的运行不具有时间次序的特征,互斥示例 假定进程Pa负责为用户作业分配打印机，进程Pb负责释放打印机。系统中设立一个打印机分配表，由各个进程共用。打印机分配表（初始情况）打印机分配表（出错情况）,竞争条件（Race Condit

19、ion）两个或多个进程同时访问和操纵相同的数据时，最后的执行结果取决于进程运行的精确时序。,2.5.2 临界资源和临界区,1临界资源和临界区临界资源（Critical Resource）一次仅允许一个进程使用的共享资源临界区（Critical Section），简称CS区 在每个进程中访问临界资源的那段程序,2进程的一般结构,典型进程的一般结构,3临界区进入准则 单独进入 独占该区 限时退出 主动让权,进程A和进程B互斥使用临界区的过程,2.5.3 互斥实现方式,1利用硬件方法解决进程互斥问题 禁止中断 进入临界区之后立即关闭所有的中断 专用机器指令 TSL（Test and Set Lock

20、，即测试并上锁）的指令：TSL RX，LOCK 汇编代码示例 enter_region:TSL REGISTER,LOCK CMP REGISTER,#0 JNE enter_region RET leave_region:MOVE LOCK,#0 RET,2原语是机器指令的延伸，往往是为完成某些特定的功能而编制的一段系统程序。原语操作也称做“原子操作”（atomic action），即一个操作中的所有动作要么全做，要么全不做。执行原语操作时，要屏蔽中断，以保证其操作的不可分割性。,3利用软件方法解决进程互斥问题 可为每类临界区设置一把锁，该锁有打开和关闭两种状态。关锁原语lock(W):wh

21、ile(W=1);W=1;开锁原语unlock(W):w=0;,进程A lock(W);打印信息S;CS区 unlock(W);,进程B lock(W);打印信息S;CS区 unlock(W);,用锁实现进程互斥设系统中有一台打印机，有两个进程A和B都要使用它，以变量W表示锁，预先把它的值置为0。,2.5.4 信号量,1整型信号量P操作最初源于荷兰语proberen，表示测试；V操作源于荷兰语verhogen，表示增加。在有些书上将P操作称做wait或者DOWN操作，将V操作称做signal或者UP操作。对信号量的操作有以下限制：信号量可以初始化为一个非负值。只能由P和V两个操作来访问信号量。

22、,整型信号量,P和V操作都是原语伪代码形式 P(S)V(S)while(S0);S+;S-;实现互斥的伪代码形式 do P(mutex);临界区 V(mutex);其他代码区 while(1);,信号量,2结构型信号量结构型信号量又称计数信号量，简称信号量 一般是由两个成员组成的数据结构。其中一个成员是整型变量，表示该信号量的值；另一个是指向PCB的指针。typedef struct int value;struct PCB*list;semaphore;,结构型信号量,信号量的值与相应资源的使用情况有关信号量的一般结构及PCB队列,对信号量的操作有如下严格限制：信号量可以赋初值，且初值为非负

23、数。在使用过程中，信号量的值可以修改，但只能由P和V操作来访问，不允许通过其他方式来查看或操纵信号量。,结构型信号量,P、V操作的定义 void P(semaphore S)void V(semaphore S)S.value-;S.value+；if(S.value0)if(S.value=0)把这个进程加到S.list队列；从S.list队列中移走进程Q；block()；wakeup(Q)；在具体实现时应注意，P,V操作都应作为一个整体实施，不允许分割或相互穿插执行,结构型信号量,结构型 信号量3二值信号量 一种特例，它的值只能在0和1之间选择,typedef struct enumfal

24、se,truevalue;/*枚举量*/struct PCB*list;B_semaphore;void P_B(B_semaphore S)if(S.value=true)S.value=false;else 把该进程放入S.list队列;block();,void V_B(B_semaphore S)if(S.list=NULL)S.value=true;else 从S.list队列中移走进程Q;wakeup(Q);,2.5.5 信号量的一般应用,1用信号量实现进程互斥 打印机分配表的互斥使用 Pa:Pb:P(mutex)P(mutex)分配打印机 释放打印机（读写分配表）（读写分配表）V

25、(mutex)V(mutex),用信号量实现进程互斥,利用信号量实现互斥的一般模型是：进程P1 进程P2 进程Pn P(mutex);P(mutex);P(mutex);临界区 临界区 临界区 V(mutex);V(mutex);V(mutex);,用信号量实现进程互斥,注意点：在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对出现，即先做P，进入临界区；后做V，退出临界区。互斥信号量mutex的初值一般为1。,2用信号量实现进程简单同步 对缓冲区的同步使用问题,简单供者和用者对缓冲区的使用关系,用信号量实现进程简单同步,供者和用者间要交换两个消息：缓冲区空 缓冲区满设置两个

26、信号量：S1表示缓冲区是否空（0表示不空，1表示空）。S2表示缓冲区是否满（0表示不满，1表示满）。规定S1和S2的初值分别为1和0,用信号量实现进程简单同步,供者进程 用者进程 L1:P(S1)L2:启动读卡机 P(S2);从缓冲区取出信息 收到输入结束中断 V(S1);V(S2);加工并且存盘 goto L1;goto L2;,用信号量实现进程简单同步,用P和V操作实现同步时应注意如下三点：分析进程间的制约关系，确定信号量种类。信号量的初值与相应资源的数量有关，也与P,V操作在程序代码中出现的位置有关。同一信号量的P,V操作要“成对”出现，但是，它们分别出现在不同的进程代码中。,2.6 经

27、典进程同步问题,1生产者-消费者问题生产者:能产生并释放资源的进程消费者:单纯使用（消耗）资源的进程问题表述 一组生产者进程和一组消费者进程（设每组有多个进程）通过缓冲区发生联系。生产者进程将生产的产品（数据、消息等统称为产品）送入缓冲区，消费者进程从中取出产品。假定缓冲区共有N个，不妨把它们设想成一个环形缓冲池。,生产者-消费者问题,生产者-消费者问题环形缓冲池,它们应满足如下同步条件：任一时刻所有生产者存放产品的单元数不能超过缓冲区的总容量（N）。所有消费者取出产品的总量不能超过所有生产者当前生产产品的总量。,生产者-消费者问题,设缓冲区的编号为0N-1，in和out分别是生产者进程和消费

28、者进程使用的指针，指向下面可用的缓冲区，初值都是0。设置三个信号量：full：表示放有产品的缓冲区数，其初值为0。empty：表示可供使用的缓冲区数，其初值为N。mutex：互斥信号量，初值为1，表示各进程互斥进入临界区，保证任何时候只有一个进程使用缓冲区。,生产者-消费者问题,生产者进程Producer：消费者进程Consumer：while(TRUE)while(TRUE)P(empty);P(full);P(mutex);P(mutex);产品送往buffer(in);从buffer(out)中取出产品；in=(in+1)mod N;out=(out+1)mod N;/*以N为模*/*以

29、N为模*/V(mutex);V(mutex);V(full);V(empty);,2读者-写者问题 读者-写者问题也是一个著名的进程互斥访问有限资源的同步问题。例如，一个航班预订系统有一个大型数据库，很多竞争进程要对它进行读、写。允许多个进程同时读该数据库，但是在任何时候如果有一个进程写（即修改）数据库，那么就不允许其他进程访问它 既不允许写，也不允许读。,读者-写者问题,信号量设置：读互斥信号量rmutex 初值为1 写互斥信号量wmutex 初值为1 rmutex：读者互斥地访问readcount wmutex：保证一个写者与其他读者/写者互斥地访问共享资源,读计数器readcount，整

30、型变量，初值为0。,读者-写者问题,读者Readers while(TRUE)P(rmutex);readcount=readcount+1;if(readcount=1)P(wmutex);V(rmutex);执行读操作 P(rmutex);readcount=readcount-1;if(readcount=0)V(wmutex);V(rmutex);使用读取的数据,写者Writers while(TRUE)P(wmutex);执行写操作 V(wmutex);,这个算法隐含读者的优先级高于写者,3哲学家进餐问题五位哲学家围坐在一张圆桌旁进餐，每人面前有一只碗，各碗之间分别有一根筷子。每位哲

31、学家在用两根筷子夹面条吃饭前独自进行思考，感到饥饿时便试图占用其左、右最靠近他的筷子，但他可能一根也拿不到。他不能强行从邻座手中拿过筷子，而且必须用两根筷子进餐；餐毕，要把筷子放回原处并继续思考问题。,哲学家进餐问题,哲学家进餐问题,=#define N 5#define LEFT(i-1)%N#define RIGHT(i+1)%N#define THINKING 0#define HUNGRY 1#define EATING 2 typedef struct/*定义结构型信号量*/int value;struct PCB*list;semaphore;int stateN;semaphor

32、e mutex=1;/*互斥进入临界区*/semaphore sN;/*每位哲学家一个信号量*/,哲学家进餐问题,void philosopher(int i)while(TRUE)think();/*哲学家在思考问题*/take_chopstick(i);/*拿到两根筷子或者等待*/eat();/*进餐*/put_chopstick(i);/*把筷子放回原处*/void take_chopstick(int i)P(mutex);statei=HUNGRY;test(i);/*试图拿两根筷子*/V(mutex);P(si);,哲学家进餐问题,void put_chopstick(int i)

33、P(mutex);statei=THINKING;test(LEFT);/*查看左邻，现在能否进餐*/test(RIGHT);/*查看右邻，现在能否进餐*/V(mutex);void test(int i)if(statei=HUNGRY=,打瞌睡的理发师,4打瞌睡的理发师问题理发店有一名理发师，一把理发椅和几把座椅，等待理发者可坐在上面。如果没有顾客到来，理发师就坐在理发椅上打盹。当顾客到来时，就唤醒理发师。如果顾客到来时理发师正在理发，该顾客就坐在椅子上排队；如果满座了，他就离开这个理发店，到别处去理发。,打瞌睡的理发师问题,理发师和每位顾客都分别是一个进程=#define CHAIRS

34、5typedef struct int value;struct PCB*list;semaphore;semaphore customers=0;semaphore barbers=0;semaphore mutex=1;int waiting=0;,void barber(void)while(TRUE)P(customers);/*如果没有顾客，则理发师打瞌睡*/P(mutex);/*互斥进入临界区*/waiting-;V(barbers);/*一个理发师准备理发*/V(mutex);/*退出临界区*/cut_hair();/*理发（在临界区之外）*/,打瞌睡的理发师问题,打瞌睡的理发师

35、问题,void customer(void)P(mutex);/*互斥进入临界区*/if(waitingCHAIRS)waiting+;V(customers);/*若有必要，唤醒理发师*/V(mutex);/*退出临界区*/P(barbers);/*如果理发师正忙着，则顾客打瞌睡*/get_haircut();else V(mutex);/*店里人满了，不等了*/,2.7 管 程,管程：一个管程定义一个数据结构和能为并发进程在其上执行的一组操作，这组操作能使进程同步和改变管程中的数据。由管程名称、局部于管程的共享数据的说明、对数据进行操作的一组过程和对该共享数据赋初值的语句四部分组成。,管程

36、的结构,管 程,管程具有以下三个特性：管程内部的局部数据变量只能被管程内定义的过程所访问，不能被管程外面声明的过程直接访问。进程要想进入管程，必须调用管程内的某个过程。一次只能有一个进程在管程内执行，而其余调用该管程的进程都被挂起，等待该管程成为可用的。即管程能有效地实现互斥。,管 程,实现互斥是由编译程序完成为解决同步问题，引入两个条件变量x和y：condition x,y;操作原语wait(x)：挂起等待条件x的调用进程，释放相应的管程，以便供其他进程使用。操作原语signal(x)：恢复执行先前因在条件x上执行wait而挂起的那个进程。管程的职责与信号量的职责不同。,带条件变量的管程结构

37、,2.8 进 程 通 信,进程通信进程间的信息交换低级进程通信高级进程通信 共享存储器方式：在内存中分配一片空间作为共享存储区 消息传递方式：以消息（Message）为单位在进程间进行数据交换 直接通信方式 间接通信方式 管道文件方式：写者向管道文件中写入数据；读者从该文件中读出数据,2.8.1 消息传递系统允许进程彼此进行通信，而不必借助于共享数据提供两个原语（系统调用）send和receive：send(destination,message)receive(source,message),消息传递系统,消息传送系统设计 涉及同步、寻址、格式和排队规则等多项问题 同步 寻址 直接通信方式

38、对称寻址；非对称寻址 间接通信方式 信箱 公用信箱 共享信箱 私有信箱,消息传送系统设计,消息格式 取决于消息机制的目标和 在什么系统上运行 排队规则 先进先出 优先权法 接收方挑选,一般消息格式,消息传递系统,用消息传递方式解决生产者-消费者问题#define N 100/*缓冲区个数*/void producer(void)int item;message m;/*消息缓冲区*/while(TRUE)item=produce_item()；/*生成一些数据放入缓冲区*/receive(consumer,/*使用数据项进行操作*/,2.8.2 客户-服务器系统中的通信,1socket好像一条

39、通信线两端的接插口一对进程通过网络进行通信要用一对socket，每个进程一个。三个要素：网络地址表明一个socket用于哪种网络 连接类型表明网络通信所遵循的模式，主要分为“有连接”和“无连接”模式。网络规程表明具体网络的规程。一般来说，网络地址和连接类型结合在一起就基本上确定了适用的规程。,socket通信流程,2远程过程调用远程过程调用（Remote Procedure Call,RPC）是远程服务的一种最常见的形式。远程过程调用的思想：允许程序调用另外机器上的过程远程过程调用的具体步骤,第3章 死 锁,本章内容提要资源死锁概念死锁的预防死锁的避免死锁的检测和恢复处理死锁的综合方式,3.1

40、 资源,3.1.1 资源使用模式 申请 使用 释放,3.1.2 可剥夺资源与不可剥夺资源,按占有方式划分：可剥夺资源 当该资源被某进程拥有后，其它进程仍可以把它剥夺过去为己所用，并且不会产生任何不良影响。例如，内存就是可剥夺资源。不可剥夺资源 该资源一旦被某进程占有，则其它进程不能强行抢占，必须由拥有者自动释放，否则会引起相关计算的失效。如光盘刻录机。死锁和不可剥夺资源有关 按其它方式划分,3.2 死锁概念,3.2.1 什么是死锁 1死锁示例,汽车过窄桥时的冲突,在计算机系统中，涉及软件、硬件资源的进程都可能发生死锁,2死锁定义死锁 是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进

41、程才能引发的事件而无限期地僵持下去的局面。计算机系统产生死锁的根本原因就是资源有限且操作不当死锁的危害 系统瘫痪 资源浪费,什么是死锁,有两个进程A和B，竞争两个资源R和S，这两个资源都是不可剥夺资源。进程A 进程B 申请并占用R 申请并占用S 申请并占用S 申请并占用R 释放R 释放S 释放S 释放R,什么是死锁,进程推进顺序对引发死锁的影响,3.2.2 死锁的条件,产生死锁的4个必要条件 1互斥条件 2占有且等待条件 3不可抢占条件 4循环等待条件只要有一个必要条件不满足，则死锁就可以排除。,3.2.3 资源分配图,1资源分配图的构成由结对组成：G=(V,E)V是顶点的集合，E是边的集合。

42、顶点集合可分为两部分：P=p1,p2,pn 由系统中所有活动进程组成 R=r1,r2,rm 由系统中全部资源类型组成有向边pi rj称为申请边 有向边rj pi 称为赋给边在资源分配图中，通常用圆圈表示每个进程，用方框表示每种资源类型。,2资源分配图示例（1）集合P,R和E如下：P=p1,p2,p3 R=r1,r2,r3,r4 E=p1r1,p2r3,r1p2,r2p2,r2p1,r3p3（2）资源数量 分别为1，2，1，3（3）进程状态 该图不含环路，没有死锁,资源分配图示例,3环路与死锁 如果每类资源的实体都只有一个，那么图中出现环路就说明死锁了。,环路与死锁,有死锁的资源分配图,有环路但

43、无死锁的资源分配图,如果每类资源的实体不止一个，那么资源分配图中出现环路并不表明一定出现死锁。,资源分配图中存在环路是死锁产生的必要条件，但不是充分条件。,3.2.4 处理死锁的方法,利用某些协议预防或避免死锁，保证系统不会进入死锁状态。允许系统进入死锁状态，然后设法发现并克服它。完全忽略这个问题，好像系统中从来也不会出现死锁。,3.3 死锁的预防,3.3.1 破坏互斥条件3.3.2 破坏占有且等待条件 预分资源策略静态分配“空手”申请资源策略不占有资源时才可以申请资源 存在以下4个主要缺点 不可预测 利用率低 降低并发性“饥饿”现象,3.3.3 破坏非抢占条件,隐式抢占方式 抢占等待者资源,

44、3.3.4 破坏循环等待条件,资源有序分配策略 资源编号 设R=r1,r2,rm，表示一组资源 定义一对一的函数F：RN，N是一组自然数。如：F（磁带机）=1，F（磁盘机）=5，F（打印机）=12 依序分配 约定：所有进程对资源的申请严格按照序号递增的次序进行。,破坏循环等待条件,先弃大，再取小 一个进程申请资源rj，它应释放所有满足F(ri)F(rj)关系的资源ri,这两种办法都是可行的，都可排除环路等待条件,优点：资源利用率和系统吞吐量都有很大提高缺点：资源请求受限，合理编号困难，增加系统开销。暂不使用的资源也需提前申请，增加资源占用时间。,3.4 死锁的避免,排除死锁的动态策略。关键是确

45、定资源分配的安全性 3.4.1 安全状态在当前分配状态下，进程的安全序列P1,P2,Pn是：若对于每一个进程Pi（1in），它需要的附加资源可被系统中当前可用资源与所有进程Pj（ji）当前占有资源之和所满足，则P1,P2,Pn为一个安全序列。这时系统处于安全状态。存在安全序列时一定不会有死锁发生 死锁是不安全状态中的特例,安全状态,安全状态示意设系统中共有10台磁带机，有三个进程p1,p2和p3，分别拥有3台、2台和2台磁带机，而它们各自的最大需求分别是9台、4台和7台磁带机。此时，系统已分配了7台磁带机，还有3台空闲。下表给出三个进程在不同时刻占有资源及向前推进的情况。,不安全状态示意,若不

46、按照安全序列分配资源，则系统可能会由安全状态转换为不安全状态,死锁的避免,死锁状态是不安全状态。如果系统处于不安全状态，并不意味着它就在死锁状态，而是表示存在导致死锁的危机。如果一个进程申请的资源当前是可用的，但为了避免死锁，该进程也可能必须等待。此时资源利用率会下降。,3.4.2 资源分配图算法,资源类 单体资源类 多体资源类单体资源类的资源分配图 除申请边和赋给边之外，还要有一种称为“要求边”的新边。要求边 pi rj表示进程pi能够申请资源rj，有时用虚线表示。,资源分配图示例,处于不安全状态的资源分配图,3.4.3 银行家算法,“银行家算法”（Bankers Algorithm）针对多

47、体资源类 设计思想：当用户申请一组资源时，系统必须做出判断：如果把这些资源分出去，系统是否还处于安全状态。若是，就可以分出这些资源；否则，该申请暂不予满足。,银行家算法数据结构令n表示系统中进程的数目，m表示资源分类数。Available是一个长度为m的向量，它表示每类资源可用的数量。Available j=k，表示rj类资源可用的数量是k。Max是一个nm矩阵，它表示每个进程对资源的最大需求。Maxi,j=k，表示进程pi至多可申请k个rj类资源单位。Allocation是一个nm矩阵，它表示当前分给每个进程的资源数目。Allocation i,j=k，表示进程pi当前分到k个rj类资源。N

48、eed是一个nm矩阵，它表示每个进程还缺少多少资源。Need i,j=k，表示进程pi尚需k个rj类资源才能完成其任务。记号：令X和Y表示长度为n的向量 可以把矩阵Allocation和Need中的每一行当做一个向量，并分别写成Allocationi和Needi。Allocationi表示当前分给进程pi的资源。,1资源分配算法令Requesti表示进程pi的申请向量。Requestij=k，表示进程pi需要申请k个rj类资源。当进程pi申请资源时，就执行下列动作：若RequestiNeedi，表示出错，如果RequestiAvailable，则pi等待。假设系统把申请的资源分给进程pi，则应

49、对有关数据结构进行修改：Available：=Available Requesti Allocationi：=Allocationi+Requesti Needi：=Needi Requesti 系统执行安全性算法，查看此时系统状态是否安全。如果是安全的，就实际分配资源，满足进程pi 的此次申请；否则，若新状态是不安全的，则pi等待，对所申请资源暂不予分配，并且把资源分配状态恢复成之前的情况。,2安全性算法 令Work和Finish分别表示长度为m和n的向量，最初，置Work：=Available，Finishi：=false，i=1,2,n。搜寻满足下列条件的i值：Finishi=false

50、，且NeediWork。若没有找到，则转向。修改数据值：Work：=Work+Allocationi（pi释放所占的全部资源）Finishi=true 转向。若Finishi=true对所有i都成立（任一进程都可能是pi），则系统处于安全状态；否则，系统处于不安全状态。,3算法应用示例假定系统中有4个进程A,B,C,D和三类资源R1,R2和R3，各自的数量分别为9,3和6个单位。,T0时刻资源分配表（安全）,资源情况,（1）T0时刻是安全的 存在一个安全序列B,A,C,D,进程,T0时刻的安全序列,（2）进程A请求资源 进程A发出请求Request（1,0,1）,系统进入不安全的状态 不能为进