1、操操 作作 系系 统统 原原 理理Operating System第第1章章 操作系统绪论操作系统绪论 操作系统的概念操作系统的概念 操作系统的历史操作系统的历史 操作系统的特性操作系统的特性 操作系统的基本类型操作系统的基本类型 操作系统的功能操作系统的功能 计算机硬件简介计算机硬件简介 算法的描述算法的描述 研究操作系统的观点研究操作系统的观点1.1 操作系统概念操作系统概念 操作系统的地位操作系统的地位 引入操作系统的目的引入操作系统的目的 操作系统定义操作系统定义1.1.1 操作系统地位操作系统地位 硬件抽象层（硬件抽象层（HAL）之上）之上 所有其它软件层之下所有其它软件层之下硬件（
2、硬件（HAL）OS其它系统软件层（如编译软件）其它系统软件层（如编译软件）应用软件层应用软件层1.1.2 引入操作系统的目的引入操作系统的目的 从用户的观点：为用户（应用程序）提供从用户的观点：为用户（应用程序）提供良好的服务界面。良好的服务界面。API、GUI 从系统管理员的观点：为管理和分配系统从系统管理员的观点：为管理和分配系统资源，提高系统工作效率。资源，提高系统工作效率。从发展的观点：为系统提供功能扩展平台。从发展的观点：为系统提供功能扩展平台。1.1.3 操作系统定义操作系统定义 操作系统是位于硬件层操作系统是位于硬件层(HAL)之之上，所有其它软件层之下的一个系上，所有其它软件层
3、之下的一个系统软件，是管理和控制系统中各种统软件，是管理和控制系统中各种软硬件资源，方便用户使用计算机软硬件资源，方便用户使用计算机系统的程序集合。系统的程序集合。1.2 操作系统的历史操作系统的历史 操作系统的产生操作系统的产生 手工操作阶段手工操作阶段 成批处理阶段成批处理阶段 执行系统阶段执行系统阶段 操作系统的完善操作系统的完善 多道批处理系统多道批处理系统 分时系统分时系统 实时处理系统实时处理系统 通用操作系统通用操作系统 操作系统的发展操作系统的发展 网络操作系统网络操作系统 分布式操作系统分布式操作系统 多处理机操作系统多处理机操作系统 单用户操作系统单用户操作系统 面向对象操
4、作系统面向对象操作系统 嵌入式操作系统嵌入式操作系统 智能卡操作系统智能卡操作系统1.3 操作系统特性操作系统特性 程序并发性程序并发性 多个程序在宏观上同时向前推进、微观上串行推进多个程序在宏观上同时向前推进、微观上串行推进 并发并发(concurrent)vs.并行并行(parallel)资源共享性资源共享性 多个程序共用系统中的各种软硬件资源多个程序共用系统中的各种软硬件资源 在操作系统的协调和控制下在操作系统的协调和控制下 虚拟性虚拟性 物理上的一台设备变成逻辑上的多台设备物理上的一台设备变成逻辑上的多台设备 不确定性不确定性1.4 操作系统的基本类型操作系统的基本类型 多道批处理操作
5、系统多道批处理操作系统(batch processing system)分时操作系统分时操作系统(time-sharing system)实时操作系统实时操作系统(real time system)通用操作系统通用操作系统(multi-purpose system)单用户操作系统单用户操作系统(single user system)网络操作系统网络操作系统(network operating system)分布式操作系统分布式操作系统(distributed operating system)多处理机操作系统多处理机操作系统(multi-processor system)1.4.1 多道批处理
6、系统（多道批处理系统（Off-line）1.4.1 多道批处理系统多道批处理系统 特点特点 多道：系统中同时容纳多个作业多道：系统中同时容纳多个作业 成批：作业分批进入系统成批：作业分批进入系统 宏观上并行，微观上串行宏观上并行，微观上串行 多道批处理系统是以脱机为标志的操作系统，多道批处理系统是以脱机为标志的操作系统，适用于处理运行时间比较长的程序。适用于处理运行时间比较长的程序。主机中作业合理搭配主机中作业合理搭配 目标目标1：提高资源利用率：提高资源利用率 目标目标2：提高吞吐量：提高吞吐量(throughput)1.4.2 分时操作系统（分时操作系统（On-line）1.4.2 分时操
7、作系统分时操作系统 特点：特点：多路性：一个主机与多个终端相连；多路性：一个主机与多个终端相连；交互性：以对话的方式为用户服务；交互性：以对话的方式为用户服务；独占性：每个终端用户仿佛拥有一台虚拟机。独占性：每个终端用户仿佛拥有一台虚拟机。分时操作系统是以联机为标志的操作分时操作系统是以联机为标志的操作系统，特别适用于程序的动态调试与修系统，特别适用于程序的动态调试与修改。改。1.4.3 实时操作系统实时操作系统 实时控制实时控制 工业控制，军事控制，医疗控制，工业控制，军事控制，医疗控制，.实时信息处理实时信息处理 航班定票，联机情报检索，航班定票，联机情报检索，.实时控制实时信息处理实时信
8、息处理1.4.4 通用操作系统通用操作系统(multi-purpose OS)同时具有：分时、实时、批处理功能。同时具有：分时、实时、批处理功能。目标：目标：提高处理能力提高处理能力;扩展应用领域。扩展应用领域。常见模式常见模式:分时分时(前台前台)+批处理批处理(后台后台)实时实时(前台前台)+批处理批处理(后台后台)1.4.5 单用户操作系统单用户操作系统 同一时刻仅有一个用户使用的系统同一时刻仅有一个用户使用的系统 应用领域：应用领域：台式机，笔记本，台式机，笔记本，.特点：特点：单用户，多进程，多线程单用户，多进程，多线程1.4.6 网络操作系统网络操作系统网络操作系统的目标网络操作系
9、统的目标 相互通讯相互通讯 资源共享（信息，设备）资源共享（信息，设备）提供网络服务提供网络服务 database server ftp server e-mail server telnet server etc.No Transparent view1.4.7 分布式操作系统分布式操作系统 紧耦合：紧耦合：(tightly coupled)由多机系统发展而来（多由多机系统发展而来（多CPU）有公共内存有公共内存 多处理机操作系统多处理机操作系统1.4.7 分布式操作系统分布式操作系统 松散耦合：松散耦合：(loosely coupled)由计算机网络发展而来（多由计算机网络发展而来（多Ho
10、st)无公共内存，无公共时钟无公共内存，无公共时钟1.4.7 分布式操作系统分布式操作系统 分布式操作系统特征分布式操作系统特征:统一的操作系统统一的操作系统 资源的进一步共享资源的进一步共享 可靠性可靠性 透明性透明性 1.4.8 多处理机操作系统多处理机操作系统 多处理机系统多处理机系统 具有公共内存的多具有公共内存的多CPU系统系统 对称多处理机系统对称多处理机系统(SMP)没有主从关系的多处理机系统没有主从关系的多处理机系统 多处理机操作系统多处理机操作系统 有效管理和使用多个有效管理和使用多个CPU的操作系统的操作系统 复杂性：多个主动体（复杂性：多个主动体（CPUs)例子：例子：U
11、NIX,Linux,Windows1.5 操作系统的功能操作系统的功能 处理机管理处理机管理 存储管理存储管理 设备管理设备管理 信息管理（文件系统管理）信息管理（文件系统管理）用户接口用户接口1.6 计算机硬件简介计算机硬件简介1.6.1 计算机的基本硬件元素计算机的基本硬件元素 构成计算机基本硬件元素包含以下构成计算机基本硬件元素包含以下4种：处理器、种：处理器、存储器、输入输出控制与总线、外部设备。存储器、输入输出控制与总线、外部设备。计算机的基本硬件元素计算机的基本硬件元素1.6.2 与操作系统相关的几种与操作系统相关的几种主要寄存器主要寄存器1.数据寄存器数据寄存器2.地址寄存器地址
12、寄存器3.条件码寄存器条件码寄存器4.程序计数器程序计数器PC5.指令寄存器指令寄存器IR6.程序状态字程序状态字PSW7.中断现场保护寄存器中断现场保护寄存器8.过程调用用堆栈过程调用用堆栈1.6.3 存储器的访问速度存储器的访问速度存储介质的访问速度存储介质的访问速度 一般来说，速度高的存储介质，成本高，一般来说，速度高的存储介质，成本高，容量小；容量大的存储介质，速度慢，成本容量小；容量大的存储介质，速度慢，成本低。低。1.6.4 指令的执行与中断指令的执行与中断指令的执行周期指令的执行周期 中断执行过程中断执行过程f1.6.4 指令的执行与中断指令的执行与中断中断处理时的指令执行周期中
13、断处理时的指令执行周期1.7 算法的描述算法的描述 算法描述的方式：算法描述的方式：自然语言自然语言 流程图方式流程图方式 类类Pascal语言语言 本书：本书：begin Repeat While 条件条件 If 条件条件 end 操作操作 do then 操作操作 操作操作 Until od else 操作操作1.8 研究操作系统的几种观点研究操作系统的几种观点 操作系统是计算机资源的管理者操作系统是计算机资源的管理者 用户界面的观点用户界面的观点 进程管理的观点进程管理的观点第第2章章 操作系统用户界面操作系统用户界面 用户界面简介用户界面简介 一般用户的输入输出界面一般用户的输入输出界
14、面 命令控制界面命令控制界面 Linux与与Windows的命令控制界面的命令控制界面 系统调用系统调用2.1用户界面简介用户界面简介 用户界面的功能用户界面的功能 用户界面负责用户与操作系统之间用户界面负责用户与操作系统之间的交互。的交互。用户分类用户分类 使用和管理计算机的应用程序的用户使用和管理计算机的应用程序的用户 程序开发人员程序开发人员 用户界面分类用户界面分类 命令控制界面命令控制界面 系统调用系统调用 2.2 一般用户的输入输出界面一般用户的输入输出界面 2.2.1 作业的定义作业的定义 2.2.2 作业组织作业组织 2.2.3 一般用户的输入输出方式一般用户的输入输出方式2.
15、2.1作业的定义作业的定义 在一次应用业务处理过程中，从输入开始到在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务输出结束，用户要求计算机所做的有关该次业务处理的全部工作称为一个作业。作业由不同的顺处理的全部工作称为一个作业。作业由不同的顺序相连的作业步组成。序相连的作业步组成。图图2.1 一般编程过程一般编程过程2.2.2 作业组织作业组织图图2.2 作业说明书的主要内容作业说明书的主要内容2.2.3一般用户的输入输出方式一般用户的输入输出方式 1.联机输入输出方式联机输入输出方式 外围设备直接和主机相连，速度慢。外围设备直接和主机相连，速度慢。2.脱机输入输
16、出方式脱机输入输出方式 外围机进行联机输入输出处理，通过外外围机进行联机输入输出处理，通过外围机的后援存储来实现和主机的连接。速围机的后援存储来实现和主机的连接。速度快。度快。3.直接耦合方式直接耦合方式 主机和外围机通过一个公共外存直接连主机和外围机通过一个公共外存直接连接。速度快，人工不用干预接。速度快，人工不用干预2.2.3一般用户的输入输出方式一般用户的输入输出方式图图2.3 直接耦合方式直接耦合方式 4.SPOOLING系统系统 5.网络联机方式网络联机方式2.2.3 一般用户的输入输出方式一般用户的输入输出方式外围设备通过通道或外围设备通过通道或DMA器件与主机和外存相连。器件与主
17、机和外存相连。2.3 命令控制界面命令控制界面 用户使用命令控制界面的方式：用户使用命令控制界面的方式：1、脱机方式、脱机方式 填写作业说明书，用户不能干预作业执行。填写作业说明书，用户不能干预作业执行。2、联机方式、联机方式 不用填写作业说明书，用户能够干预作业执不用填写作业说明书，用户能够干预作业执行。行。2.4Linux与与Windows的命令控制界面的命令控制界面Redhat Linux 9.0的窗口界面的窗口界面2.4.1Linux的命令控制界面的命令控制界面2.4.1Linux的命令控制界面的命令控制界面Linux的命令一般包含的命令一般包含9类：类：1 系统维护与管理命令系统维护
18、与管理命令2文件操作与管理命令文件操作与管理命令3进程管理命令进程管理命令4磁盘及设备管理命令磁盘及设备管理命令5用户管理命令用户管理命令6文档操作命令文档操作命令7网络通信命令网络通信命令8程序开发命令程序开发命令9X Windows管理命令管理命令2.4.2 Windows的命令控制界面的命令控制界面 Windows的命令控制界面分为的命令控制界面分为两个部分：两个部分：窗口交互：通过键盘和鼠标在窗口交互：通过键盘和鼠标在图形上操作。图形上操作。命令解释器：通过命令解释器：通过cmd.exe为为用户服务。用户服务。2.4.2 Windows的命令控制界面的命令控制界面图图2.6相互调用批处
19、理示例相互调用批处理示例2.5 系统调用系统调用系统调用分为系统调用分为6类：类：1 设备管理设备管理2 文件管理文件管理3 进程控制进程控制4 进程通信进程通信5 存储管理存储管理6 线程管理线程管理2.5 系统调用系统调用系统调用的处理过程系统调用的处理过程第第3章章 进程管理进程管理 进程的概念进程的概念 进程的描述进程的描述 进程状态及其转换进程状态及其转换 进程控制进程控制 进程互斥进程互斥 进程同步进程同步 进程的通信进程的通信 死锁问题死锁问题 线程的概念、分类与执行线程的概念、分类与执行3.1 进程的概念进程的概念 3.1.1 程序的并发执行程序的并发执行 3.1.2 进程的定
20、义进程的定义3.1.1程序的并发执行程序的并发执行1.程序程序(program)用来描述计算机所要完成的独立功能，并在时间用来描述计算机所要完成的独立功能，并在时间上严格地按前后次序相继地进行计算机操作序列上严格地按前后次序相继地进行计算机操作序列集合，是一个静态的概念。集合，是一个静态的概念。2.程序的顺序执行（程序的顺序执行（sequence)程序顺序执行的概念程序顺序执行的概念 一个具有独立功能的程序独占处理机直至最终一个具有独立功能的程序独占处理机直至最终结束的过程称为程序的顺序执行。结束的过程称为程序的顺序执行。程序顺序执行的特征程序顺序执行的特征 顺序性顺序性 封闭性封闭性 可再现
21、性可再现性 3.1.1程序的并发执行程序的并发执行 3.程序的并发程序的并发(concurrent)执行执行 程序的并发执行：宏观上同时向前程序的并发执行：宏观上同时向前推进，微观上同一时刻只有一个程序运推进，微观上同一时刻只有一个程序运行。行。程序并发执行分为两种：一种是程程序并发执行分为两种：一种是程序间的并发。另一种是同一程序内部多序间的并发。另一种是同一程序内部多条指令的并发。条指令的并发。程序并发执行的特性：程序并发执行的特性：交叉性、非封闭性、不可再现性交叉性、非封闭性、不可再现性3.1.1程序的并发执行程序的并发执行 4.程序的顺序性与并发性举例：程序的顺序性与并发性举例：顺序性
22、顺序性 内部顺序性内部顺序性：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,a33.1.2 进程的定义进程的定义 定义：定义：并发执行的程序在执行过程中分并发执行的程序在执行过程中分配和管理资源的基本单位。配和管理资源的基本单位。定义强调两个方面：定义强调两个方面：动态：执行中的程序动态：执行中的程序;并发：可与其他进程同时执行。
23、并发：可与其他进程同时执行。并发并发 vs.并行并行 并发：并发：concurrent 宏观同时，宏观同时，“交替执行交替执行”，不要求多个，不要求多个CPU 并行：并行：parallel 微观同时，要求多个微观同时，要求多个CPU“并行算法并行算法”3.1.2 进程的定义进程的定义 进程与程序的区别与联系：进程与程序的区别与联系：进程是一个动态概念，程序是一个静态概念进程是一个动态概念，程序是一个静态概念。进程具有并发特征，而程序没有。进程具有并发特征，而程序没有。进程是竞争计算机系统资源的基本单位。进程是竞争计算机系统资源的基本单位。不同的进程可以包含同一程序，只要该程序所不同的进程可以包
24、含同一程序，只要该程序所对应的数据集不同。对应的数据集不同。3.2 进程的描述进程的描述 进程控制块进程控制块 进程组成与进程上下文进程组成与进程上下文 进程上下文的切换进程上下文的切换 进程空间与大小进程空间与大小 进程的类型进程的类型 进程的相互联系与相互作用进程的相互联系与相互作用3.2.1 进程控制块进程控制块PCB 定义：标志进程存在的数据结构，其中保定义：标志进程存在的数据结构，其中保存系统管理进程所需的全部信息。存系统管理进程所需的全部信息。PCB的内容的内容：(不同系统不尽相同不同系统不尽相同)1.描述信息描述信息 2.控制信息控制信息 3.资源管理信息资源管理信息 4.CPU
25、现场保护结构现场保护结构Process Control Block3.2.2 进程的组成与上下文进程的组成与上下文 进程的组成进程的组成 进程控制块进程控制块(process control block)建立进程建立进程建立建立PCB 撤销撤销PCB撤销进程撤销进程 程序程序 代码代码(code)数据数据(data)堆栈堆栈(stack+heap)3.2.2 进程的组成与上下文进程的组成与上下文 进程的表记进程的表记PCB程序程序PCB代码代码数据数据+堆栈堆栈表记表记1表记表记2系统空间系统空间用户空间用户空间l进程上下文（进程上下文（process context)进程的物理实体与支持进程
26、运行的物理环境进程的物理实体与支持进程运行的物理环境统称为进程上下文。统称为进程上下文。lPCB+程序程序l系统环境：地址空间，系统栈，打开文件系统环境：地址空间，系统栈，打开文件表，表，进程上下文结构进程上下文结构3.2.3 进程上下文切换进程上下文切换 上下文切换（上下文切换（context switch)由一个进程的上下文转到另外一个进程的上下由一个进程的上下文转到另外一个进程的上下文文 系统开销（系统开销（system overhead)运行操作系统程序完成系统管理工作所花费的运行操作系统程序完成系统管理工作所花费的时间和空间时间和空间3.2.3 进程上下文切换进程上下文切换进程上下文
27、的切换过程进程上下文的切换过程3.2.4 进程空间与大小进程空间与大小进程在内存中自己拥有的一个地址空间称为进程在内存中自己拥有的一个地址空间称为进程空间。进程空间。进程空间的大小只与处理机的位数有关。进程空间的大小只与处理机的位数有关。一般，进程空间可以分为：用户空间与系统一般，进程空间可以分为：用户空间与系统空间。空间。用户程序在用户空间中运行。用户程序在用户空间中运行。操作系统内核程序在系统空间中运行操作系统内核程序在系统空间中运行。3.2.5 进程的类型进程的类型 进程类型进程类型 系统进程系统进程 运行操作系统程序，完成系统管理运行操作系统程序，完成系统管理(服务服务)功能功能.用户
28、进程用户进程 运行用户运行用户(应用应用)程序，为用户服务。程序，为用户服务。3.2.6 进程间相互联系与相互作用进程间相互联系与相互作用 相互联系相互联系 相关进程相关进程 同一家族的进程同一家族的进程 可以共享文件，需要相互通讯，协调推进速度可以共享文件，需要相互通讯，协调推进速度 父进程可以监视子进程，子进程完成父进程交给的父进程可以监视子进程，子进程完成父进程交给的任务。任务。无关进程无关进程 没有逻辑关系、同时执行的进程。没有逻辑关系、同时执行的进程。有资源竞争关系，互斥、死锁、饿死。有资源竞争关系，互斥、死锁、饿死。3.2.6 进程间相互联系与相互作用进程间相互联系与相互作用 相互
29、作用相互作用RP2P1syncsendreceiveP1:P2:holdwait3.3 进程状态及其转换进程状态及其转换 进程的状态进程的状态 进程状态的转换进程状态的转换 进程队列进程队列3.3.1 进程状态进程状态 进程状态：进程状态：初始态（初始态（Initial）：进程刚被创建，其他进程正）：进程刚被创建，其他进程正占据处理器而得不到执行。占据处理器而得不到执行。运行态（运行态（Run）：占有）：占有CPU正在向前推进。正在向前推进。就绪态（就绪态（Ready）：可以运行，但未得到）：可以运行，但未得到CPU。等待态（等待态（Wait）：等待某一事件发生。）：等待某一事件发生。终止态（
30、终止态（Stop）：进程执行结束，将退出执行而）：进程执行结束，将退出执行而被终止。被终止。3.3.2 进程状态转换进程状态转换 状态转换状态转换就绪就绪运行：获得处理机运行：获得处理机运行运行就绪：剥夺处理机就绪：剥夺处理机运行运行等待：申请资源未得到，启动等待：申请资源未得到，启动IO等待等待就绪：得到资源，就绪：得到资源，IO中断中断就绪就绪等待等待运行运行获得处理机剥夺处理机等待事件事件发生3.3.2 进程状态转换图进程状态转换图3.3.2 进程状态转换图进程状态转换图就绪就绪等待等待运行运行获得处理机剥夺处理机等待事件事件发生初创初创终止终止创建结束3.3.3 进程队列进程队列PCB
31、PCBPCBhead1.就绪队列：系统一个或若干个（根据调度算法确定）就绪队列：系统一个或若干个（根据调度算法确定）2.等待队列：每个等待事件一个等待队列：每个等待事件一个3.运行队列：每个处理机一个运行队列：每个处理机一个PCB构成的队列：（不一定构成的队列：（不一定FIFO)3.4 进程控制进程控制 进程控制：系统使用一些具有特定功能进程控制：系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进的程序段来创建、撤销进程以及完成进程各状态间的转换，从而达到多进程高程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的效率并发执行和协调、实现资源共享的目的。目的。原语：系统
32、态下执行的某些具有特定功原语：系统态下执行的某些具有特定功能的程序段。能的程序段。原语的分类：机器指令级：不许中断原语的分类：机器指令级：不许中断 功能级：不许并发功能级：不许并发3.4.1 进程创建与撤销进程创建与撤销进程创建方式：进程创建方式：系统创建系统创建 父进程创建父进程创建3.4.1 进程创建与撤销进程创建与撤销进程撤销的方式：进程撤销的方式：正常终止正常终止非正常终止非正常终止祖先进程撤销祖先进程撤销3.4.2 进程的阻塞与唤醒进程的阻塞与唤醒阻塞原语图阻塞原语图阻塞原语实现了进程阻塞原语实现了进程由执行状态到等待状由执行状态到等待状态的转变。态的转变。阻塞原语是由进程自阻塞原语
33、是由进程自己调用的。己调用的。3.4.2 进程的阻塞与唤醒进程的阻塞与唤醒唤醒原语唤醒原语唤醒原语实现了进程唤醒原语实现了进程由等待状态到就绪状由等待状态到就绪状态的转变。态的转变。唤醒的方式唤醒的方式:系统进程唤醒系统进程唤醒 事件发生进程唤醒事件发生进程唤醒3.5 进程互斥进程互斥 与时间有关的错误与时间有关的错误 共享变量与临界区域共享变量与临界区域 进程互斥进程互斥 进程互斥的实现进程互斥的实现 信号灯与信号灯与P，V原语原语3.5.1 与时间有关的错误与时间有关的错误例：图书借阅系统例：图书借阅系统 （x:某种书册数，设当前某种书册数，设当前x=1.=1.）终端终端1：终端终端2：C
34、YCLE 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 共享变量与临界区域共享变量与临界区域 共享变
35、量（共享变量（shared variable）多个进程都需要访问的变量。多个进程都需要访问的变量。临界区域（临界区域（critical region）访问共享变量的程序段。访问共享变量的程序段。一组公共变量一组公共变量CR1CR2CRn.临界区的表示临界区的表示共享变量共享变量:shared 临界区域临界区域:region do 语句语句例子：例子：shared B:array0,.,n-1of integer;region B do region B do begin begin (访问访问B）.（访问（访问B）.end;end;3.5.3 进程互斥进程互斥定义：多个进程不能同时进入关于同一
36、组共享变量的临定义：多个进程不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象称界区域，否则可能发生与时间有关的错误，这种现象称为进程互斥为进程互斥二层涵义：二层涵义：（1）任何时刻最多只能有一个进程处于同一组共）任何时刻最多只能有一个进程处于同一组共享变量的相同的临界区域；享变量的相同的临界区域；（2）任何时刻最多只能有一个进程处于同一组共）任何时刻最多只能有一个进程处于同一组共享变量的不同的临界区域。享变量的不同的临界区域。注意注意:互斥是相对于公共变量而言的。互斥是相对于公共变量而言的。并发进程互斥执行必须满足并发进程互斥执行必须满足4条准则：条准则：不能假
37、设并发进程的相对执行速度。不能假设并发进程的相对执行速度。某进程不在临界区，不能阻止其他进某进程不在临界区，不能阻止其他进程进入临界区。程进入临界区。若干进程申请进入临界区，只能允许若干进程申请进入临界区，只能允许一个进程进入。一个进程进入。某进程申请进入临界区，应该在有限某进程申请进入临界区，应该在有限的时间内得以进入临界区。的时间内得以进入临界区。3.5.3 进程互斥进程互斥3.5.4 进程互斥的实现进程互斥的实现进程互斥的实现有两种方法：进程互斥的实现有两种方法：软件方法实现：软件方法实现：完全用程序实现，不需特殊硬件指完全用程序实现，不需特殊硬件指令支持。令支持。可用于单可用于单CPU
38、和多和多CPU环境中。环境中。有忙式等待问题有忙式等待问题Busy waiting“运行运行”或或“就绪就绪”3.5.4 进程互斥的实现进程互斥的实现硬件方法实现：硬件方法实现：硬件提供硬件提供“测试并建立测试并建立”指令、指令、“交换交换”指令指令 硬件提供硬件提供“关中断关中断”和和“开中断开中断”指令指令 关中断关中断 Critical Region 开中断开中断Remarks:(1)开关中断只在单开关中断只在单CPU系统中效系统中效;(why?)(2)影响并发性。影响并发性。3.5.4 进程互斥的实现进程互斥的实现 例：对临界区加锁实现互斥例：对临界区加锁实现互斥:当某个进程进入临界区
39、之后，它将锁上当某个进程进入临界区之后，它将锁上临界区，直到它退出临界区时为止。临界区，直到它退出临界区时为止。lock(key s)临界区临界区 unlock(key s)3.5.5 信号灯与信号灯与P，V原语原语 E.W.Dijkstra,1965.信号灯与信号灯与PV操作的定义操作的定义 TYPE semaphore=RECORD value:integer;queue:PCB pointer;END;VAR s:semaphore;备注备注:(1)semaphore 是一个提前定义好的数据类型是一个提前定义好的数据类型.(2)s 是一个信号灯变量是一个信号灯变量,使用前必须先声明使用前
40、必须先声明.例如例如:var s1,s2:semaphore;信号灯变量信号灯变量S.valueS.queueS.valueS.queuePCBPCBPCBVar S:semaphore;FIFOP操作原语操作原语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
41、piece of code un-interruptibleV操作原语操作原语V操作原语：操作原语：Procedure V(var s:semaphore)s.value:=s.value+1;If s.value=0;只能执行只能执行P操作和操作和V操作，所有其它操作非法。操作，所有其它操作非法。几个有用的结论：几个有用的结论：当当s.value=0时，时，s.queue为空；为空；当当s.value=1 Then IF x=1 Then Begin Begin x:=x-1;x:=x-1;V(mutex)V(mutex)借书借书 借书借书 End End Else V(mutex);无书无
42、书;Else V(mutex);无书无书;End End3.6 进程同步进程同步3.6.1 进程同步的概念进程同步的概念例：司机例：司机-乘客问题乘客问题 司机活动：司机活动：(P1)乘客活动：乘客活动：(P2)do do 启动车辆启动车辆 上上 车车 正常行驶正常行驶 投投 币币 到站停车到站停车 下下 车车 while(1)while(1)3.6.1 进程同步的概念进程同步的概念定义：一组进程，为协调其推进速度，在某些定义：一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间关键点处需要相互等待与相互唤醒，进程之间这种相互制约的关系称为进程同步。这种相互制约的关系称为
43、进程同步。P1:P2:synchronize后先3.6.2 进程同步机制进程同步机制 定义：用于实现进程同步的工具称为同定义：用于实现进程同步的工具称为同步机制步机制（synchronization mechanism）同步机制要求：同步机制要求：描述能力够用描述能力够用;可实现可实现;高效高效;使用方便使用方便.3.6.3 用信号灯实现进程同步用信号灯实现进程同步 P(S)后动作后动作先动作先动作 V(S)P1:P2:用信号灯实现进程同步用信号灯实现进程同步例子：司机例子：司机-乘客问题：乘客问题：VAR s1,s2:semaphore;(initial value 0)司机活动：司机活动：
44、售票员活动：售票员活动：Repeat Repeat P(S1)上上 车车 启动车辆启动车辆 V(S1)正常行驶正常行驶 投投 币币 到站停车到站停车 P(S2)V(S2)下下 车车 Until false Until false典型的进程同步问题典型的进程同步问题 生产者生产者消费者问题消费者问题生产者生产者/消费者问题消费者问题预备知识：预备知识：组合资源组合资源：若干相对独立的资源构成的资源集合，其中：若干相对独立的资源构成的资源集合，其中每个相对独立的资源称为子资源。每个相对独立的资源称为子资源。同种组合资源同种组合资源：相同类型子资源构成的组合资源。：相同类型子资源构成的组合资源。管理
45、：管理：Var S:semaphore;(初值初值=子资源个数）子资源个数）例子：例子：2台打印机台打印机 Var S:semaphore;S.value=2;申请：申请：P（S）；）；释放：释放：V（S）；）；2 2自动机描述自动机描述10-1-2P(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.生产者生产者/消费者问题消费者问题 0 1 k-1箱子，容量箱子，容量k B:Array0.k-1Of item生产者生产者消费者消费者生产物品
46、生产物品放入放入B中中从从B中取物品中取物品消费之消费之环形缓冲区环形缓冲区10K-1in(in+1)mod kout(out+1)mod k问题分析问题分析生产者活动：生产者活动：消费者活动：消费者活动：do do 加工一件物品加工一件物品 箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 消耗这件物品消耗这件物品 while(1)while(1)资源：箱子（同种组合）资源：箱子（同种组合）资源：物品（同种组合）资源：物品（同种组合）Var S1:semaphore;Var S2:semaphore;S1.value=k;S2.value=0;放前：放前：P（S1）取前：取前：P（S2）放
47、后：放后：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)箱中取一物
48、品箱中取一物品 物品放入箱中物品放入箱中 V(mutex)V(mutex)V(S1)V(S2)消耗这件物品消耗这件物品 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)endProcedure consumer cyc
49、le P(s2);P(mutex);x:=Bout;out:=(out+1)mod k;V(mutex);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，ou
50、tin=out:满或空满或空,Var mutex1,mutex2:semaphore;(init 1)并发性提高策略并发性提高策略生产者活动：生产者活动：消费者活动：消费者活动：Repeat Repeat 加工一件物品加工一件物品 P(S2)P(S1)P(mutex2)P(mutex1)箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mutex2)V(mutex1)V(S1)V(S2)消耗这件物品消耗这件物品 Until false Until false3.7 进程通信进程通信 进程通信：进程之间的数据传送。进程通信：进程之间的数据传送。低级通讯（简单信号）低级通讯（简单信号）进程互
