教学课件：《操作系统原理与实训教程》(第2版).ppt

1、操作系统课程任务和要求 任务任务 通过本课程的学习通过本课程的学习,掌握操作系统的基本掌握操作系统的基本概念、设计原理及实施技术概念、设计原理及实施技术,具有初步分析操具有初步分析操作系统和设计、实现、开发实际操作系统的作系统和设计、实现、开发实际操作系统的能。能。基本要求基本要求 通过理论学习和上机操作通过理论学习和上机操作,使学生能掌握使学生能掌握操作系统的基本概念、基本原理、及基本功操作系统的基本概念、基本原理、及基本功能能.了解了解UNIXUNIX操作系统、操作系统、WINDOWS NTWINDOWS NT操作操作系统的基本轮廓系统的基本轮廓,具有初步分析实际操作系统、具有初步分析实际

2、操作系统、设计、构造和开发现代操作系统的基本能力。设计、构造和开发现代操作系统的基本能力。操作系统课程的特点：操作系统课程的特点：实践性强实践性强涉及面广（并行程序，性能问题，结构涉及面广（并行程序，性能问题，结构问题，程序方法论，软件工程，等等）问题，程序方法论，软件工程，等等）错综复杂错综复杂如何学好操作系统？如何学好操作系统？理论抽象理论抽象多看多看（课本和参考书）、多练、多练（习题和上机）、多想多想（包括预习、听课和复习），当然还要端正态度。第第1 1章章 引言引言 OS的地位的地位OS的作用的作用：用用 户户应用软应用软件件其他系统软其他系统软件件 裸机裸机操作系操作系统统1.1 O

3、S(Operating System)的概念的概念计算机系统的层次结构：人机接口人机接口系统资源管理者系统资源管理者虚拟机器虚拟机器1.1 OS的概念（续）的概念（续）OS的设计目标：的设计目标：方便性、有效性、可扩充性、开放性。方便性、有效性、可扩充性、开放性。OS主要功能：主要功能：四大类系统资源的管理和与用户的接口。另有中断处四大类系统资源的管理和与用户的接口。另有中断处理、时钟管理和出错处理等。在批处理系统中还有作业管理、时钟管理和出错处理等。在批处理系统中还有作业管理功能。理功能。OS定义定义(P5)：OS是合理组织计算机的工作流程，有效控制和管理计是合理组织计算机的工作流程，有效控

4、制和管理计算机系统的各类资源，并方便用户使用计算机的一组程序算机系统的各类资源，并方便用户使用计算机的一组程序的集合。它是最基本、最重要的系统软件。的集合。它是最基本、最重要的系统软件。从无到有雏形从无到有雏形 批处理批处理分时分时实时实时PC网络网络分布分布式式OS 19451955 真空管和插件板，无真空管和插件板，无OS时代时代 19551965 晶体管和批处理系统，晶体管和批处理系统，OS诞生、成长时诞生、成长时期期 196519701980 IC芯片和多道程序，芯片和多道程序，OS成熟成熟 1980 VLSIC，PC网络网络分布式分布式OS以上各阶段用户的用机方式：全人工以上各阶段用

5、户的用机方式：全人工脱机脱机I/O联机联机I/O1.2 OS发展过程发展过程n 上个世纪上个世纪6060年代末至年代末至7070年代初年代初 杨芙清杨芙清院士主持我国第一台百万次集成电路计算机院士主持我国第一台百万次集成电路计算机（150150）操作系统，支持多道程序运行，在石油勘探领域成）操作系统，支持多道程序运行，在石油勘探领域成功应用。功应用。n 上个世纪上个世纪7070年代中后期年代中后期 杨芙清杨芙清院士主持我国第一个全部用高级语言书写的院士主持我国第一个全部用高级语言书写的DJS240DJS240机操作系统，机操作系统，DJS200/XT2DJS200/XT2层次管程结构模型，层次

6、管程结构模型，PCMPCM设设计方法，活跃管程结构模式。计方法，活跃管程结构模式。国内操作系统的研制状况国内操作系统的研制状况国内操作系统的研制状况国内操作系统的研制状况（续）（续）n GX73GX73多机实时操作系统（多机实时操作系统（19781978年）年）国防科技大学，国防科技大学，19801980年装在年装在“远望远望”-I-I 号航天测量船上，完成了向太平洋发射运号航天测量船上，完成了向太平洋发射运载火箭、潜水艇水下发射的测控任务；完成了我国第一颗同步地球卫星的测控、定轨、载火箭、潜水艇水下发射的测控任务；完成了我国第一颗同步地球卫星的测控、定轨、控制任务控制任务。n “银河银河”-

7、1 YHOS-1 YHOS巨型操作系统（巨型操作系统（19831983年）国防科技大学年）国防科技大学，用，用于于YH-1YH-1、YH-2YH-2超级计算机，用于我国的石油勘探、天气预报和核物理研究超级计算机，用于我国的石油勘探、天气预报和核物理研究。nCOSIX v 1.X/2.0 COSIX v 1.X/2.0 国产国产UNIXUNIX类操作系统类操作系统（国家八五、九五重点科技攻关成果，（国家八五、九五重点科技攻关成果，以中软为首，联合国内以中软为首，联合国内1818个单位共同完成）个单位共同完成）微内核结构，安全级别超过微内核结构，安全级别超过B1B1，中文界面，中文界面。n嵌入式操

8、作系统嵌入式操作系统HopenHopen（女娲计划）。（女娲计划）。nLinuxLinux类操作系统。类操作系统。可从多角度进行多种分类：可从多角度进行多种分类：比如，按机器硬件结构、规模可分为：大、中、小型机比如，按机器硬件结构、规模可分为：大、中、小型机OS，PC OS，网络，网络OS和嵌入式和嵌入式OS等；等；而按系统处理任务的方式可分为：而按系统处理任务的方式可分为：三种基本类型的三种基本类型的OS（即批（即批 处理系统、处理系统、分时系统分时系统和实时系统）和分布式和实时系统）和分布式OS。若按系统能同时响应的用户及任务数则可分为以下三种类若按系统能同时响应的用户及任务数则可分为以下

9、三种类型：型：单用户单任务单用户单任务OS（如（如DOS）、单用户多任务）、单用户多任务OS（如（如 Windows 9X）和多用户多任务）和多用户多任务OS（如（如UNIX）。）。1.3 OS分类分类早期的批处理系统示意图早期的批处理系统示意图脱机输入脱机输入/输出输出过程：(a)程序员将卡片拿到1401机处(b)1401机将批处理作业读到磁带上(c)操作员将输入磁带送入7094机(d)7094机进行计算(e)操作员将输出磁带送到1401机(f)1401机打印输出分时系统示意图分时系统示意图 分时系统基于分时系统基于主从主从式多终端的计算机式多终端的计算机体系结构体系结构：一台主：一台主机连

10、接着多个带有机连接着多个带有显示器、键盘及控显示器、键盘及控制器的本地或远程制器的本地或远程终端，多用户在自终端，多用户在自己的终端上以交互己的终端上以交互方式使用主机，共方式使用主机，共享系统资源享系统资源 主机主机(分时分时 OS）终端 终端 终端多道操作系统的基本特性多道操作系统的基本特性:1.4 OS的特征的特征P13 图1-3 并发性并发性 共享性共享性(两含义两含义)虚拟性虚拟性 异步性异步性 一、命令界面一、命令界面 1 1、脱机命令界面、脱机命令界面(如如JCLJCL语言语言)2 2、联机命令界面、联机命令界面(如键盘命令如键盘命令)二、程序界面二、程序界面（用户只能在其程序中

11、使用的一组操作（用户只能在其程序中使用的一组操作系统函数，如系统函数，如MS DOSMS DOS的的INTINT函数、函数、UNIXUNIX的的System callSystem call函数、函数、Windows Windows 的的 APIAPI函数等）函数等）三、图形用户界面三、图形用户界面(GUI)1.5 OS的用户界面的用户界面OS的结构设计的结构设计 不同时期的软件开发方法使不同时期的软件开发方法使OS结构从整体式无结构结构从整体式无结构系统系统模块化结构模块化结构 层次式结构层次式结构C/S模式的微内核结构。模式的微内核结构。同时系统本身具有不同的结构。同时系统本身具有不同的结构

12、。一、整体式结构一、整体式结构 二、层次式结构二、层次式结构 三、虚拟机系统三、虚拟机系统 四、客户四、客户-服务器系统服务器系统 1.6 OS的结构的结构OS结构示意图(1)整体式（单块）系统的简单结构模型OS结构示意图(2)Structure of the THE（1968）operating systemMS-DOS LAYERED STRUCTUREUser(L3)Command Processor(L2)DOS Kernel(L1)BIOSHardwareOS结构示意图(3)Structure of VM/370（1979）with CMS（Conversational Monito

13、r System)OS结构示意图(4)The client-server modelOS结构示意图(5)The client-server model in a distributed systemMICROKERNEL Ritche and Thompson 1973,UNIX;1983,Turing AwardBill Gates&Paul Allen 1975 MS Co.，1981 DOS1.0,1990 Windows3.1,1995 Windows 95；1993 Windows NT,2000 Windows 2000,2003 Windows server 2003对对OSOS

14、贡献大的人：贡献大的人：Andrew S.Tanenbaum 1987,MINIXLinus Torvalds 1991,LinuxSteve Jobs，Steve Wozniak 1977 Apple Computer,Inc.,Apple DOS;1984 Macintosh OS;1991,1997 Mac OS;2001 Mac OS x当前几个著名的开源当前几个著名的开源OSOS：MINIXLinuxFreeBSD(UNIX)Solaris 10(SUNs OpenSolaris Project,descendant of BSD and System V)OS定义定义（P5）处理机

15、两种执行状态处理机两种执行状态（核心态（核心态=管态，用户态管态，用户态=目态）目态）Kernel（OS运行于核心态的代码）运行于核心态的代码）系统从用户态进入核心态执行的途径系统从用户态进入核心态执行的途径:中断中断(含系统调用和陷含系统调用和陷阱阱)分时分时(Time Sharing)1959,MIT提出提出,1961实现。实现。时间片大小？时间片大小？特权指令特权指令(启动启动I/O等影响系统安全的指令等影响系统安全的指令,只能只能OS执行执行)并行并行与与并发并发(P12)OS与用户的接口与用户的接口小结：小结：本章几个重要概念本章几个重要概念P19-21 综合练习题一综合练习题一补充

16、题补充题1：当没有用户程序要运行时，：当没有用户程序要运行时，CPU做什么？做什么？补充题补充题2：下述指令中哪些应是：下述指令中哪些应是特权指令特权指令？1）修改内存管理寄存器）修改内存管理寄存器 2）写程序计数器写程序计数器 3）读时钟的时间值读时钟的时间值 4）置时钟的时间值）置时钟的时间值 5）改变进程的优先级）改变进程的优先级 6）置运行模式为核心态）置运行模式为核心态 7）重启动）重启动 8）关中断）关中断 9）读程序状态字读程序状态字作作 业业第第2 2章章 处理机管理处理机管理(重重难难点之一点之一)2.1 2.1 多道程序设计多道程序设计 程序并发执行时的特征：n间断性间断性

17、 程序在并发执行时，由于共享资源，或者需要相互合作，致使相程序在并发执行时，由于共享资源，或者需要相互合作，致使相互间产生了制约关系，呈互间产生了制约关系，呈“走走停停走走停停”的间断执行特征。的间断执行特征。n失去封闭性失去封闭性 程序并发执行时的系统环境（主要指各程序所共享的系统资源的状程序并发执行时的系统环境（主要指各程序所共享的系统资源的状态）是由多个程序来改变的，因而失去了封闭性。态）是由多个程序来改变的，因而失去了封闭性。n不可再现性不可再现性 程序在并发执行时的结果与其执行速度等有关，从而不可再现。程序在并发执行时的结果与其执行速度等有关，从而不可再现。I1I2I3I4C1C2C

18、4C3P1P2P3P4程序并发执行的条件(Bernstein,1966)定理定理：如果两个程序P1和P2满足下述条件，它们便能并发执行，否则不能 R(P1)W(P2)R(P2)W(P1)W(P1)W(P2)=v即当两个程序的即当两个程序的读集读集与与写集写集的交集以及写集与写集的交集都为空集时，它们可的交集以及写集与写集的交集都为空集时，它们可以并发执行，否则不行。该定理也称以并发执行，否则不行。该定理也称Bernstein条件条件。v操作系统中许多任务不满足操作系统中许多任务不满足Bernstein条件，它们不能并发执行吗？怎么办？这条件，它们不能并发执行吗？怎么办？这涉及后面重点讲的进程同

19、步问题涉及后面重点讲的进程同步问题。2.2 2.2 进程的进程的描述描述2.1 2.1 进程的进程的基本基本概念概念 1.1.进程（进程（P26P26）及进程实体（及进程实体（P27P27）的概念的概念 进程是对正在运行的程序的抽象，是进程是对正在运行的程序的抽象，是OSOS最核心的最核心的概念。计算机上所有可运行的软件，包括概念。计算机上所有可运行的软件，包括OSOS，被组被组织成若干顺序进程，简称进程。织成若干顺序进程，简称进程。进程进程是一个具有一定是一个具有一定独立功能的程序关于某个数据集合的一次运行活动，独立功能的程序关于某个数据集合的一次运行活动，是系统进行资源分配和调度的一个独立

20、单位。是系统进行资源分配和调度的一个独立单位。生活例生活例子：一人按菜谱做菜。子：一人按菜谱做菜。进程实体进程实体由程序段、相关数据段和进程控制块构成。由程序段、相关数据段和进程控制块构成。进程的其他定义进程的其他定义 “进程进程”这一术语，在这一术语，在60年代初期，首先在美国年代初期，首先在美国MIT的的MULTICS系统和系统和IBM公司的公司的CTSS/360系统中引入。其中能反映系统中引入。其中能反映进程实质的定义有：进程实质的定义有：（1）进程是程序的一次执行。）进程是程序的一次执行。（2）进程是可以和其他计算并发执行的计算。）进程是可以和其他计算并发执行的计算。（3）进程是一个程

21、序及其数据在处理机上顺序执行时发生）进程是一个程序及其数据在处理机上顺序执行时发生的活动。的活动。（4）进程是程序在一个数据集合上的运行过程，是系统进）进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。行资源分配和调度的一个独立单位。（5）进程是进程实体的一次活动。）进程是进程实体的一次活动。程序任意并发执行具有一些新的特征（间断性、无程序任意并发执行具有一些新的特征（间断性、无封闭性、不可再现性），旧的程序的概念已不足以刻画封闭性、不可再现性），旧的程序的概念已不足以刻画这种并发执行的程序及其执行所产生的新特征。为使程这种并发执行的程序及其执行所产生的新特征。为使

22、程序能并发执行，且为了能对并发执行的程序加以描述和序能并发执行，且为了能对并发执行的程序加以描述和控制而引入进程。控制而引入进程。简言之简言之，为了实现程序的并发执行，为了实现程序的并发执行。前趋图（前趋图（P23P23）在此是一种可用于描述进程间执行在此是一种可用于描述进程间执行的时序关系（前趋后继关系）的的时序关系（前趋后继关系）的DAGDAG。DAGDAG在编译原在编译原理、数据结构和人工智能等课程理、数据结构和人工智能等课程/学科中都有用。学科中都有用。2.2.进程的引入（进程的引入（P26P26）进程的特性：进程的特性：动态性动态性：指进程是程序或进程实体的一次执行过程，：指进程是程

23、序或进程实体的一次执行过程，生命周期短暂。生命周期短暂。并发性并发性：指多个进程实体同存于内存中，且能在一段：指多个进程实体同存于内存中，且能在一段 时间内同时运行。时间内同时运行。独立性独立性：指进程是系统分配资源和调度运行的一个基：指进程是系统分配资源和调度运行的一个基本单位。本单位。异步性异步性：指进程的推进速度是各自独立、不可预知的。：指进程的推进速度是各自独立、不可预知的。结构特性结构特性：从结构上看，进程由程序段、相关数据段：从结构上看，进程由程序段、相关数据段 和进程控制块三部分组成。此即进程实体。和进程控制块三部分组成。此即进程实体。3.3.进程的特性及其与程序的区别进程的特性

24、及其与程序的区别（P26P27P26P27）提示提示：可从二者的定义：可从二者的定义上、进程的特征上上、进程的特征上（结构特征单列）和（结构特征单列）和二者对应数目关系上二者对应数目关系上等几方面分析。另外，等几方面分析。另外，进程可真实地描述并进程可真实地描述并发，而程序不能。发，而程序不能。注意：注意：在在OS中，作业、中，作业、进程、程序和线进程、程序和线程是几个相似但程是几个相似但又不同的概念！又不同的概念！进程与程序的区别与联系进程与程序的区别与联系n从定义上看，进程是程序处理数据的从定义上看，进程是程序处理数据的过程，而程序是一组指令的有序集合；过程，而程序是一组指令的有序集合；n

25、进程具有动态性、并发性、独立性和进程具有动态性、并发性、独立性和异步性等，而程序不具有这些特性；异步性等，而程序不具有这些特性；n从进程结构特性上看，它包含程序从进程结构特性上看，它包含程序（以及数据和（以及数据和PCB）；）；n进程和程序并非一一对应。进程和程序并非一一对应。执行态阻塞态就绪态调度I/O请求时间片完I/O完成 为了更好地描述进程的动态存在，设计者常常给进程定义三种基本状为了更好地描述进程的动态存在，设计者常常给进程定义三种基本状态：就绪态态：就绪态(Ready)、执行态执行态(Running)和阻塞和阻塞(Blocked)状态。其转换方向状态。其转换方向和常见的转换原因如下图

26、所示：和常见的转换原因如下图所示：4.4.进程的三种基本状态及其转换图进程的三种基本状态及其转换图说明：说明：1)在引入挂起功能的系统中，进程状态可至在引入挂起功能的系统中，进程状态可至5个。个。2)在实际的在实际的OS中，进程的状态会更多。比如中，进程的状态会更多。比如UNIX SV中中有有9种，种，Linux中有中有6种，种，Windows2000中有中有7种。种。另外，另外，系统引入挂起功能的原因系统引入挂起功能的原因要了解要了解（P29，为满足系统和为满足系统和用户两方面的需求，如：换入换出、调整负荷、解救死锁、用户两方面的需求，如：换入换出、调整负荷、解救死锁、父进程请求等）。父进程

27、请求等）。5.PCB（Process Control Block）及其组织方式及其组织方式 PCB：系统中用于存放进程的描述和控制信息的数系统中用于存放进程的描述和控制信息的数据结构。它是进程存在于系统的唯一标志据结构。它是进程存在于系统的唯一标志。PCB作用作用(P29)：（1）标识进程的存在；（标识进程的存在；（2）为系统提供可并发执）为系统提供可并发执行的独立单位；（行的独立单位；（3）为系统控制和管理进程提供所）为系统控制和管理进程提供所需的一切信息。需的一切信息。PCB中的主要内容中的主要内容(见见P30)：进程的标识信息、处理机的状态信息、进程调度信进程的标识信息、处理机的状态信息

28、、进程调度信息、进程的控制信息等。息、进程的控制信息等。PCB的组织方式：的组织方式：一般线性表、一般线性表、链接表链接表(多队列多队列)、索引表。、索引表。空闲空闲PCB队列头指针队列头指针阻塞进程队列头指针阻塞进程队列头指针就绪进程队列头指针就绪进程队列头指针执行进程指针执行进程指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9430879015.PCB链接队列示意图：链接队列示意图：进程控制进程控制的主要任务的主要任务是对进程生命周期进程控制，即是对进程生命周期进程控制，即要负责进程的创建、撤消以及实现进程的状态转换要负责进程的创建、撤消以及实现进程的状态转换和

29、进程通信等功能。这是系统的基本功能，由和进程通信等功能。这是系统的基本功能，由内核内核中相应的中相应的原语原语完成。完成。要求要求了解各个进程控制原语的了解各个进程控制原语的算法思想和引起这些控制原语执行的常见原因。算法思想和引起这些控制原语执行的常见原因。原语原语(primitive primitive oror atomic action)atomic action)：是是OSOS内核中由内核中由若干多机器指令构成的完成某种特定功能的一段程若干多机器指令构成的完成某种特定功能的一段程序，其执行具有序，其执行具有不可分割性不可分割性，即，即原子特征原子特征。亦即原。亦即原语的执行必须是连续的

30、，不能是并发或被中断的。语的执行必须是连续的，不能是并发或被中断的。单机系统中的实现方式之一：屏蔽中断。单机系统中的实现方式之一：屏蔽中断。2.3 2.3 进程控制进程控制1.进程创建原语Creat()引起创建进程的事件：引起创建进程的事件：用户登录用户登录 作业调度作业调度 提供服务提供服务 应用请求应用请求 进程创建的主要步骤：进程创建的主要步骤：申请空白申请空白PCB 为新进程分配资源为新进程分配资源 初始化初始化PCB的内容的内容 将新进程插入就绪队列将新进程插入就绪队列2.进程阻塞原语Block()引起进程阻塞的事件：引起进程阻塞的事件：请求系统服务请求系统服务 启动某种操作启动某种

31、操作 新数据尚未到达新数据尚未到达 无新工作可作无新工作可作 进程阻塞的过程：进程阻塞的过程：发现阻塞事件，调用阻塞发现阻塞事件，调用阻塞原语把自己阻塞，原语把自己阻塞，停止进停止进程的执行程的执行，修改修改PCB的的，将其插入到相应将其插入到相应的阻塞队列的阻塞队列。最后。最后转调度转调度程序程序，将处理机分配给另，将处理机分配给另一个就绪进程一个就绪进程。v注意：注意：进程的阻塞是进程的阻塞是进程自身的一种主动行进程自身的一种主动行为为2.4 2.4 进程的互斥进程的互斥 你需要，我也需要 多道程序设计带来的问题多道程序设计带来的问题 ：并发执行的多个进程可能产生互斥或同步的相互制约关并发

32、执行的多个进程可能产生互斥或同步的相互制约关系，不采取措施，可能导致结果的不可再现性。影响系统系，不采取措施，可能导致结果的不可再现性。影响系统效率，而且还可以导致系统崩溃。效率，而且还可以导致系统崩溃。为此，现代操作系统都在内核中设有进程的互斥同步机为此，现代操作系统都在内核中设有进程的互斥同步机制，即制，即同步机构同步机构（硬件指令（硬件指令/信号量机制信号量机制/管程机制等）管程机制等），使并发执行的诸进程之间能有效地共享资源和相互合作，使并发执行的诸进程之间能有效地共享资源和相互合作，并使程序的执行具有可再现性。并使程序的执行具有可再现性。一、一、互斥的定义互斥的定义 所谓所谓，指的是

33、对某个系统资源，一个进，指的是对某个系统资源，一个进程正在使用它，另外一个想用它的进程就必须等程正在使用它，另外一个想用它的进程就必须等待，而不能同时使用待，而不能同时使用。即排他性地用即排他性地用。进程互斥是多道程序系统中进程间存在的一种源进程互斥是多道程序系统中进程间存在的一种源于资源共享的制约关系，也称于资源共享的制约关系，也称间接制约关系间接制约关系，主，主要是由被共享资源的使用性质所决定的。要是由被共享资源的使用性质所决定的。限定进程只能互斥地访问它的资源叫限定进程只能互斥地访问它的资源叫临界资源临界资源（指一次仅允许一个进程使用的资源）。临界资源也是临界资源也是不可剥夺性资源不可剥

34、夺性资源。例：打印机、共例：打印机、共享变量或表格等。类似享变量或表格等。类似生活中的试衣室、电话间等。生活中的试衣室、电话间等。计算机系统中计算机系统中可剥夺性可剥夺性使用的资源主要有使用的资源主要有CPU、内内存存和和磁盘磁盘等。类似等。类似生活中的点歌簿、电话本等。生活中的点歌簿、电话本等。：进程中访问临界资源的那段程序代码：进程中访问临界资源的那段程序代码称为临界区或临界段。称为临界区或临界段。使用同一临界资源的不同进程中的临界区称为使用同一临界资源的不同进程中的临界区称为区区或或。临界区的使用原则临界区的使用原则，即，即“空则让进，忙则等空则让进，忙则等待，等则有限，等则让权待，等则

35、有限，等则让权”。二、上锁和开锁原语二、上锁和开锁原语 现代操作系统用来实现进程的互斥、同步的工现代操作系统用来实现进程的互斥、同步的工具有多种，如上锁与开锁原语、信号灯机制、具有多种，如上锁与开锁原语、信号灯机制、管程机制等。管程机制等。上锁与开锁是一种最简单的进程互斥方法，它上锁与开锁是一种最简单的进程互斥方法，它使用一个锁变量使用一个锁变量W来表示某种临界资源的状态来表示某种临界资源的状态，1 1上锁原语：上锁原语：LOCKLOCK（W W）L1L1：如果如果 W=1W=1那那 么转向么转向L1;L1;否则否则W=1 返回返回 void lock(void lock(锁变量锁变量w)w)

36、test:if(w test:if(w 为为1 1)goto testgoto test else else w=1;/w=1;/*上锁上锁*/*lock(w)lock(w)*/1.考察锁位的值；考察锁位的值；2.如果原来的值为如果原来的值为0，将锁位，将锁位置置1；3.如果为如果为1，则返回第一步再，则返回第一步再次考察次考察2 2开锁原语：开锁原语：UNLOCKUNLOCK（W W）W=0;W=0;返回返回 void unlock(锁变量锁变量w)w=0;/*开锁开锁 */*unlock(w)*/v当进程使用完资源后，当进程使用完资源后，它必须将锁位置成它必须将锁位置成“0”，称为开锁操作

37、称为开锁操作。三、用开关锁原语实现进程互斥三、用开关锁原语实现进程互斥 任何欲进入临界区的进程，必须先执行上锁原语。若任何欲进入临界区的进程，必须先执行上锁原语。若上上锁原语锁原语顺利通过，则进程可顺利通过，则进程可进入临界区进入临界区；当完成对临界；当完成对临界区资源的访问后再执行区资源的访问后再执行开锁原语开锁原语，以释放该临界资源。，以释放该临界资源。即即，就能保证这些进程互斥地进入各自的临界区。就能保证这些进程互斥地进入各自的临界区。例如，甲、乙两进程要访问同一类临界资源例如，甲、乙两进程要访问同一类临界资源 甲进程：甲进程：其他代码；其他代码；LOCKLOCK（W W）；）；甲进程的

38、临界区；甲进程的临界区；UNLOCKUNLOCK（W W）；）；其他代码；其他代码；乙进程：乙进程：其他代码；其他代码；LOCKLOCK（W W）；）；乙进程的临界区；乙进程的临界区；UNLOCKUNLOCK（W W）；）；其他代码；其他代码；v用上锁用上锁用上锁原语和开锁原语来实现进程的互斥的确很简单，但处理用上锁原语和开锁原语来实现进程的互斥的确很简单，但处理机效率不高，因为上锁原语中的条件测试操作可能引起机效率不高，因为上锁原语中的条件测试操作可能引起CPU“忙等忙等”。2.5 2.5 信号量机制信号量机制荷兰著名科学家，荷兰著名科学家，19721972年计算机图灵奖获得者，年计算机图灵

39、奖获得者，E.W.Dijkstra于于1965年利用火车控制系统中信号灯的概年利用火车控制系统中信号灯的概念，提出了用作进程同步工具的念，提出了用作进程同步工具的信号量信号量（semaphore）机制机制，它最初由一个表示资源可用数目或状态的整型，它最初由一个表示资源可用数目或状态的整型量（信号量）和唯一能改变这个信号量值的量（信号量）和唯一能改变这个信号量值的P P、V V原子原子操作组成，是一种简单成效的进程互斥同步工具，已操作组成，是一种简单成效的进程互斥同步工具，已广泛用于现代计算机系统中。广泛用于现代计算机系统中。信号量机制的基本原理是：信号量机制的基本原理是：v两个或多个进程可以利

40、用彼此间收发的简单的信两个或多个进程可以利用彼此间收发的简单的信号来实现号来实现“正确的正确的”并发执行，一个进程在收到并发执行，一个进程在收到一个指定信号前，会被迫在一个确定的或者需要一个指定信号前，会被迫在一个确定的或者需要的地方停下来，从而保持同步或互斥。的地方停下来，从而保持同步或互斥。v经典的整型信号量记录型信号量信号量集机制经典的整型信号量记录型信号量信号量集机制CPU忙等忙等无忙等，若使无忙等，若使用不当，可能用不当，可能造成死锁造成死锁不易死锁，可不易死锁，可能导致资源利能导致资源利用率低用率低一、记录型信号量的概念一、记录型信号量的概念 v记录型信号量是个复合类型的量，其一个

41、分量是记录型信号量是个复合类型的量，其一个分量是个整型分量个整型分量S S，另一个分量是个进程的等待队列指另一个分量是个进程的等待队列指针针Q。PascalPascal的记录相当于的记录相当于C C的结构体的结构体。v记录型信号量机制无进程的记录型信号量机制无进程的“忙等忙等”现象，其现象，其整整型分量相当于最早的整型信号量，其值只能由型分量相当于最早的整型信号量，其值只能由P、V操作改变。操作改变。记录型信号量的整型分量记录型信号量的整型分量S S的值的物理含义的值的物理含义v当当S0时，表示某类可用资源的数目，或者说表示可以时，表示某类可用资源的数目，或者说表示可以执行执行P操作而不会被阻

42、塞的进程的数目；操作而不会被阻塞的进程的数目；v当当S S0时，其绝对值表示信号量时，其绝对值表示信号量S的阻塞队列的阻塞队列L L中的进程中的进程数，即系统中因请求该类资源而被阻塞的进程的数目，数，即系统中因请求该类资源而被阻塞的进程的数目，亦即被信号灯挡住的进程数目，这些进程需要别的进程亦即被信号灯挡住的进程数目，这些进程需要别的进程发出相应的信号灯来唤醒。发出相应的信号灯来唤醒。v记录型信号量机制的另一构件记录型信号量机制的另一构件P、V操作的定义如下：操作的定义如下：二、二、P P、V V操作原语操作原语 P代表荷兰语的代表荷兰语的proberen，意为意为“测试测试”；V代表荷兰语的

43、代表荷兰语的verhogen，意为意为“增加增加”。国外文献现在流行使用国外文献现在流行使用wait操作和操作和signal操作操作(或或down操作和操作和up操作操作)代替代替P操作和操作和V操作。操作。P(S)P(S)、V(S)V(S)原语操作的算法描述：原语操作的算法描述：P(S):（1）S.S 减减 1；（2）若若S.S0，则则Block(S.Q)。V(S):（1）S.S 加加 1；（2）若若S.S 0，则则Wakeup(S.Q)。P（S）和和V（S）操作的物理含义：操作的物理含义：P（S）操作表示操作表示“等信号等信号”，即测试一个要等的信号是否到达；，即测试一个要等的信号是否到达

44、；V（S）操作表示操作表示“发信号发信号”。这个信号在实现同步时就是。这个信号在实现同步时就是“合合作者的伙伴进程已完成前趋任务作者的伙伴进程已完成前趋任务”，在实现互斥时就是，在实现互斥时就是“临界临界资源可用资源可用”。另外，在互斥问题中，每执行一次另外，在互斥问题中，每执行一次P（S）操作的含义，也可理操作的含义，也可理解为进程请求一个单位的解为进程请求一个单位的S类资源；每执行一次类资源；每执行一次 V（S）操作的含义，也可理解为进程释放一个单位的操作的含义，也可理解为进程释放一个单位的S类资源。类资源。三、三、用用P P、V V操作原语实现进程的互斥操作原语实现进程的互斥 用用P、V

45、操作原语实现进程的互斥也一样简单，只需在相关操作原语实现进程的互斥也一样简单，只需在相关进程的临界区的前后分别施以进程的临界区的前后分别施以P操作和操作和V操作即可，即在相操作即可，即在相关进程的程序里由关进程的程序里由P操作和操作和V操作原语紧夹着临界区，就能操作原语紧夹着临界区，就能保证这些进程互斥地进入各自的临界区。保证这些进程互斥地进入各自的临界区。这里所用信号量的初值一般为这里所用信号量的初值一般为1，表示临界资源未被占用，表示临界资源未被占用，且其可用数目为且其可用数目为1。用用P、V操作原语实现进程互斥的效率更高一些，因为操作原语实现进程互斥的效率更高一些，因为P操操作中引入了阻

46、塞机制，所以消除了作中引入了阻塞机制，所以消除了CPU忙等现象。忙等现象。P(S)V(S)P(S)V(S)P(S)V(S)P1P2P3互斥区互斥区一个简化的异地售票程序，假设几乎同时两地一个简化的异地售票程序，假设几乎同时两地有两个乘客要购买同一班次的车票各一张有两个乘客要购买同一班次的车票各一张 两个终端售票程序都要访问存放该次车票的数据单元两个终端售票程序都要访问存放该次车票的数据单元Pk 假设它们都要对假设它们都要对Pk做如下的访问操作做如下的访问操作“若若Pk1，则将则将Pk的值减的值减1，卖出一张票，返回，卖出一张票，返回 否则打印否则打印无票无票信息，返回信息，返回”如果不加任何限

47、制让这两个程序并发执行的话如果不加任何限制让这两个程序并发执行的话，结果可，结果可能会导致错误，甚至两地各卖出一张重票的现象能会导致错误，甚至两地各卖出一张重票的现象 例例2.1 2.1 试用试用P P、V V操作实现火车联网订票系统中北京、天津操作实现火车联网订票系统中北京、天津两地的两个终端售票进程发售同一班次车票的过程。两地的两个终端售票进程发售同一班次车票的过程。v主要步骤是：主要步骤是：v（1）分析清楚题目涉及的进程间的制约关系。）分析清楚题目涉及的进程间的制约关系。v（2）设置信号量（包括信号量的个数和初值，）设置信号量（包括信号量的个数和初值，对于同步问题还要写出信号量的物理含义

48、）。对于同步问题还要写出信号量的物理含义）。v（3）给出进程相应程序的算法描述或流程控）给出进程相应程序的算法描述或流程控 制，并把制，并把P、V操作加到程序的适当处。操作加到程序的适当处。北京售票终端进程：根据顾客订票要求找到公共数据单元根据顾客订票要求找到公共数据单元PK；P（S）；）；把把PK的值读到工作寄存器的值读到工作寄存器R1中；中；根据顾客订票数修改根据顾客订票数修改R1；将将R1的值回写到的值回写到PK中；中；V（S）；）；售出顾客所订的票，返回；售出顾客所订的票，返回；天津售票终端进程：根据顾客订票要求找到公共数据单元根据顾客订票要求找到公共数据单元PK；P（S）；把把PK的

49、值读到工作寄存器的值读到工作寄存器R2中；中；根据顾客订票数修改根据顾客订票数修改R2；将将R1的值回写到的值回写到PK中；中；V（S）；）；售出顾客所订的票，返回售出顾客所订的票，返回；关于此算法的2个问题：如何解决如何解决“票已售完票已售完”？用类用类Pascal语言怎样描述？语言怎样描述？留作课后思考练习！留作课后思考练习！2.6 进程的同步进程的同步 你等我，我也等你你等我，我也等你 相关的并发进程间可能有互斥制约关系，也可能有同相关的并发进程间可能有互斥制约关系，也可能有同步制约关系步制约关系 所谓所谓进程同步进程同步，指的是，指的是合作完成同一个任务的两个或合作完成同一个任务的两个

50、或多个进程，在执行速度或某些多个进程，在执行速度或某些时序时序点上必须相互协调，点上必须相互协调，以同步推进的合作关系。以同步推进的合作关系。这是一种源于相互合作的直这是一种源于相互合作的直接制约关系。接制约关系。即一个进程的执行依赖于另一个进程的即一个进程的执行依赖于另一个进程的消息，当它到达某一确定点而没有得到合作者发来的消息，当它到达某一确定点而没有得到合作者发来的“已完成前驱操作已完成前驱操作”的消息时必须等待。的消息时必须等待。生活中对弈双方、医生与化验员之间都有同步关系生活中对弈双方、医生与化验员之间都有同步关系 系统中父子进程之间通常属于合作（同步）关系系统中父子进程之间通常属于