操作系统期末复习

1、操作系统期末复习1 操作系统的类型和功能 冯诺曼机又称“存储程序式计算机”，由控制器、运算器、存储器、输入装置、输出装置组成。如图所示。1.1 操作系统的地位 现代计算机系统由硬件和软件两部分组成。硬件由中央处理机、存储器和外部设备组成，又称为裸机。软件由程序、数据和文档资料组成，如下图所示。1.2 操作系统的类型 自世界上第一台计算机ENIAC于1946年问世以来，计算机在运算速度、存储容量、外设功能、元件工艺及系统结构等方面都有了惊人的发展。 通常，人们按照计算机元件工艺的演变过程，将其发展划分为四个时代。操作系统的历史操作系统的历史 操作系统的发展和计算机的组成与体系结构相关，经历了四个

2、发展阶段： 1946年50年代末：第一代，电子管时代，无操作系统。 1950年代末60年代中期：第二代，晶体管时代，批处理系统。 操作系统的历史操作系统的历史1960年代中期-70年代中期：第三代，集成电路时代，多道程序设计。1970年代中期至今：第四代，大规模和超大规模集成电路时代，分时系统。现代计算机正向着并行化、分布式、网络化和智能化几个方面发展。一、手工操作阶段一、手工操作阶段 手工操作过程：手工操作过程： 先把程序纸带（或卡片）装上计算机。 然后启动输入机把程序和数据送入计算机。 接着通过控制台开关启动程序运行。 计算完毕，打印机输出计算结果，用户卸下并取走纸带（或卡片）。 第二个用

3、户上机，重复同样的步骤。 5050年代早期出现了穿孔卡片，程序写年代早期出现了穿孔卡片，程序写在卡片上，然后读入计算机，但计算在卡片上，然后读入计算机，但计算过程则依然如旧过程则依然如旧严重缺点：严重缺点：用户一个个、一道道地串行算题，当一个用户上机时，他独占了全机资源，造成计算机资源利用率不高，计算机系统效率低下。许多操作要求程序员人工干预，如装纸带或卡片、按下开关等等，手工操作多了，不但浪费处理机时间，而且也极易发生差错。由于数据的输入、程序的执行、结果的输出均是联机进行的，因而每个用户从上机到下机的时间拉得非常长。手工操作存在的问题：手工操作存在的问题：手工操作存在的问题：手工操作存在的

4、问题： 这种人工操作方式在低速机器上还能容忍，但随着计算机速度的提高，其缺点就都暴露出来了。譬如下图所示：机器速度作业在机器上所运行的时间人工操作时间手工操作时间占总运行时间百分比1万次/秒1小时3分钟3/(60+3)=4.7%60万次/秒1分钟3分钟3/(1+3)=75% 二、单道批处理系统二、单道批处理系统(simple batch processing)(simple batch processing) 计算机发展的早期，没有任何用于管理功能的软件，所有的运行管理和具体操作都由用户自己承担，任何操作出错都要重做作业，CPU的利用率甚低。 解决的方法有两个：单道批处理系统的解决方案单道批处

5、理系统的解决方案: : 首先配备专门的计算机操作员配备专门的计算机操作员，程序员不再直接操作机器，减少操作机器的错误。 另一个是进行批处理批处理，操作员把用户提交的作业分类，把一批中的作业编排成一个作业执行序列，每一批作业将有专门编制的监督程序（监督程序（monitormonitor）自动依次处理。 批处理中作业的组成批处理中作业的组成 包括用户程序、数据和作业说明书(作业控制语言)。 “批”的含义：供一次加载的磁带或磁盘，通常由若干个作业组装而成，在处理中使用一组相同的系统软件(系统带)。 说明：通常把计算机完成用户算题任务所需进行的各项工作称为一道作业。Simple Batch Syste

6、m早期批处理方式早期批处理分为两种：1.1.联机批处理联机批处理(on line)(on line)2.2.脱机批处理脱机批处理(off line)(off line)1.1.联机批处理联机批处理在这种批处理方式中，低速的输入输出(I/O)处理仍直接由主机来完成。执行过程： u 用户提交作业：对于作业、数据，可用作业控制语言编写作业说明书； u 作业以纸带或卡片为保存介质； u 操作员合成批作业，通过输入设备（纸带输入机或读卡机）存入磁带； u 监督程序根据系统资源情况读入一个作业； u 从磁带读入汇编或编译程序，将用户作业源程序生成目标代码； u 连接装配程序将目标代码变为可执行程序； u

7、启动执行； u 执行完毕，执行结果输出； a. 读入另一个作业，重复过程e-i，直到一批作业完成。联机批处理的优缺点联机批处理的优缺点 联机批处理主要优点：联机批处理主要优点：解决了作业自动转接，减少了作业建立和手工操作时间。 联机批处理存在问题：联机批处理存在问题：CPU与I/O之间的串行操作，导致输入输出时CPU处于等待状态。 2.2.脱机批处理脱机批处理（缓冲技术的一种）脱机批处理技术：脱机批处理技术： 为了解决低速输入设备与CPU速度不匹配的问题，可将用户程序和数据，在一台卫星机(又称外围计算机)的控制下，预先通过低速输入设备输入到磁带上。 当CPU需要这些程序和数据时，再直接通过磁带

8、机高速输入到内存，从而大大加快了程序的输入过程，减少了CPU等待输入的时间。脱机批处理技术脱机批处理技术 当程序运行完毕或告一段落，CPU需要输出时，也无须等待，直接把计算结果送至低速输出设备，然后在外围机的控制下，把磁带上的计算结果由相应的输出设备输出，这样大大加快了程序的输出过程。其示意图如下图所示：Operation of I/O DevicesSpooling(假脱机)Spooling实例 Spooling in modern OSMultiple printing tasks in Windows脱机批处理的优缺点脱机批处理的优缺点脱机批处理主要优点：1.主机摆脱了低速I/O的影响，

9、可以较充分地发挥它的高速计算的能力，提高了CPU的利用率。2.同时，由于主机和卫星机可以并行操作，因此相比早期的联机批处理系统而言，脱机批处理系统大大提高了系统的处理能力。脱机批处理存在问题：磁带需要手工拆装，系统的保护措施不够。批处理系统小结 在批处理系统中，操作人员把作业成批地装入计算机中。由操作系统在计算机中某个特定区域（一般称为输入井）将其组织好，并按一定的算法选择其中的一个或几个作业，将其调入内存中使其运行。运行结束后，把结果放入“输出井”，由计算机统一输出交给用户。 批处理系统的主要优点是系统吞吐量大，资源利用率高，主要缺点就是交互性差，一旦作业提交，其中间过程就很难控制。一道考研

10、题 批处理系统的主要缺点是：(清华大学1996年试题)ACPU利用率低。 B不能并发执行。C缺少交互性。 D以上都不是。 【解答】选择C。三、多道程序系统三、多道程序系统(multiprogramming system)(multiprogramming system)早期的批处理可能出现两种情况：早期的批处理可能出现两种情况： 对于以计算为主的作业，输入输出量少，外围设备空闲外围设备空闲； 对于以输入输出为主的作业，计算量少，主机空闲。问题的提出 中断和通道中断和通道技术出现以后，I/O设备和主机可以并行操作，初步解决了高速处理机和低速外设的矛盾，并提高了计算机的可靠性。 但不久后又发现这种

11、并行是有限的，并不能完全消除中央处理机对外部传输的等待。问题的提出 例：一个作业在运行过程中依次输入N批数据，每批输入1000个字符。输入机每输入1000个字符需用1000ms，而处理机处理这些数据则需300ms。 可见：尽管处理机具有和外部设备并行处理的能力，但是在这种情况下，无法让处理机多做工作，处理机仍然有空闲等待现象！问题的提出 在早期的单道批处理系统中，内存中仅有单个作业在运行，致使系统中仍有许多资源空闲，设备利用率低，系统性能较差。 如下图所示，当CPU工作时，外部设备处于等待；而外部设备工作时，CPU处于等待。 单道程序运行图示 右图所示为单道程序工作情况，在输入操作结束之前，处

12、理机空闲。其原因是本道程序与I/O处理有关，所以就提出了多道程序的概念。t1t2t用户程序计算继续计算结束I/OCPU空闲I/O操作monitorI/O请求启动I/OI/O完成多道程序设计技术（多道程序设计技术（multiprogrammingmultiprogramming） 若当前作业因等待若当前作业因等待I/OI/O而暂停，则而暂停，则CPUCPU只能踏步直至只能踏步直至该该I/OI/O完成。完成。 对于对于CPUCPU操作密集的科学计算问题，操作密集的科学计算问题，CPUCPU浪费时间较浪费时间较少；而对于商业数据处理，少；而对于商业数据处理，I/OI/O等待时间常常占到等待时间常常占

13、到80809090。 解决办法：解决办法： 将内存分为几个部分将内存分为几个部分，每部分存放不同的作业，每部分存放不同的作业， 当一个作业等待当一个作业等待I/OI/O时，另一个作业可以使用时，另一个作业可以使用CPUCPU。 在主存中同时驻留多个作业在主存中同时驻留多个作业需要硬件进行保护需要硬件进行保护， 以避免信息被窃取或攻击以避免信息被窃取或攻击Multiprogramming system three jobs in memory(3rd generation)多道程序设计(Multiprogramming) 多道程序设计(Multiprogramming)是指允许多个程序同时进入一

14、个计算机系统的主存储器，并启动进行计算的方法。 多道程序合理搭配，输入输出为主与计算为主的程序交替地运行，充分利用资源，提高系统效率。多道程序的运行特点多道程序的运行特点多道程序系统的运行特点：多道程序系统的运行特点： 多道：多道：计算机内存中同时存放多道相互独立的程序。 宏观上并行运行：宏观上并行运行：同时进入系统的几道程序都处于运行状态，但都未运行完。 微观上串行运行：微观上串行运行：各作业轮流使用CPU，交替执行。 此处的并行运行只是逻辑上的并行此处的并行运行只是逻辑上的并行，与物理上的并行是有区别的。两道考研题填空题： 1.多道程序的特征之一就是宏观并行，它的含义是（ ）（2000年，

15、华中科技大学） 2.多道程序设计的特点是多道、（ ）和（ ）（2000年西安电子科技大学） 答案：1.计算机内存中同时存放几道相互独立的 程序 2.宏观上并行、微观上串行单、多道程序运行示意图对比单、多道程序运行示意图对比单道处理与多道处理思考作业思考作业例题：有两道程序例题：有两道程序A、B，按下图以多道程序方式运行，按下图以多道程序方式运行，要求在右图画出它们的运行轨迹，并计算在要求在右图画出它们的运行轨迹，并计算在60ms内，内，CPU的利用率的利用率。假设起始时首先运行假设起始时首先运行B，并允许忽略监督并允许忽略监督程序切换程序切换A、B的时间（不考虑的时间（不考虑I/O的冲突）。的

16、冲突）。思考作业思考作业非剥夺式多道程序系统的技术问题多道程序系统的技术问题（1）并行程序的运行需要共享软硬件资源，需要同步和互斥机制。（2）多道程序需要提高内存的使用效率，需要交换技术、虚拟存储等技术。（3）多道程序在内存中要保证系统程序存储区和用户程序存储区的安全可靠，需要内存保护。 说明：在后续节会详细讲到以上技术一道考研题填空题：为了支持多道程序运行，存储管理必须要实现的主要功能有（ ）、（ ）和主存扩充。(华中科技大学1997年试题) 【分析】在多道程序的运行环境下，程序员无法预知存储管理模块将把他们的程序分配到主存的什么地方，而且程序员也希望摆脱存储地址、存储空间大小等细节问题，因

17、此存储管理模块应该提供地址重定位能力。另外，由于主存中可同时存放多道程序，为了防止程序间相互干扰，存储管理模块必须提供存储保护手段。 【解答】存储无关性、存储保护 四、分时系统(time-sharing system) 分时分时(Time Sharing)(Time Sharing)是把计算机的系统资源（尤其是CPU时间）进行时间上的分割，每个时间段称为一个时间片(Time Slice)，每个用户可以依次轮流使用时间片。 分时技术：分时技术：把处理机的运行时间分为很短的时间片，按时间片轮流把处理机分配给各个作业使用。分时系统的定义 分时操作系统（分时操作系统（Time-Sharing Oper

18、ating Time-Sharing Operating SystemSystem）是一种联机的多用户交互式的操作系统。一般采用时间片轮转的方式，使一台计算机为多个终端服务，对每个用户都能够保证足够快的响应时间，并提供交互会话的能力。 如下图所示：分时系统示意图经典案例之一：超市的收银机分时系统的特点分时系统的特点 交互性：交互性：系统能及时对多个用户的操作进行响应，缩短了周转时间。 多用户同时性：多用户同时性：多个用户同时工作，共享系统资源，提高了资源利用率。 独立性：独立性：各用户独立操作，互不干扰。一道考研题 填空题：批处理系统主要解决（ ）问题，分时系统主要解决（ ）问题。(华中科技大

19、学2002) 答案：吞吐量 交互性五、实时系统(real-time system) 产生背景：虽然多道批处理操作系统和分时操作系统获得了较佳的资源利用率和快速的响应时间，从而使计算机的应用范围日益扩大，但它们难以满足实时控制和实时信息处但它们难以满足实时控制和实时信息处理领域的需要理领域的需要。 于是，便产生了实时操作系统，目前有三种典型的实时系统：过程控制系统、信息查询过程控制系统、信息查询系统和事务处理系统系统和事务处理系统。 什么是实时系统？ 实时操作系统（Real-Time Operating System）是指当外界事件或数据产生时，能够接收并以足够快的速度予以处理，其处理的结果又可

20、在规定的时间内控制监控的生产过程或对处理系统作出快速响应的操作系统。 实时系统要求有高可靠性和安全性，系统的效率则放在第二位。实时系统的重要特征 实时操作系统的一个最重要的特征就是必须满足控制对象的截止期限的要求，若不能满足这一时间约束则一般认为系统失败。 实时操作系统的另一个重要特征是可预测性分析，操作系统功能应该具有有限的、已知的执行时间。六、操作系统的进一步发展 从20世纪80年代以来，操作系统得到了进一步的发展。促使其发展的原因有两个：一是微电子技术、计算机技术的迅速发展，二是用户的需求不断提高。 主要包括：个人计算机操作系统，网络操作系统，分布式操作系统，嵌入式操作系统，智能化操作系

21、统。1.3 操作系统的资源管理功能操作系统的核心任务就是系统资源的分配和管理，其目标是要提高系统资源的利用率和方便用户使用。操作系统具有如下几个资源管理功能：l处理机管理l存储管理l设备管理l文件系统（一）处理机管理（即进程管理） 在多道程序或多用户的情况下，需要组织多个作业同时运行，必须要解决对处理机分配调度、分配实施和资源回收等问题。 调度策略：确定多个用户/程序使用处理机的原则，各自占用处理机的时间；给出调度算法，并实施具体的处理机分派。 （二）存储管理存储管理的主要任务是管理存储器资源，为多道程序运行提供有力的支撑。存储管理的主要功能包括： (1)存储分配与回收：存储管理将根据用户程序

22、需要给它分配存储器资源，并在其使用完毕后回收。 (2)存储保护：存储管理要把各个用户程序相互隔离起来互不干扰，更不允许用户程序访问操作系统中的程序和数据，从而保护用户程序存放在存储器中的信息不被破坏。 （二）存储管理(3) 地址映射（变换）：负责进程逻辑地址到内存物理地址的映射。这样程序员无需知道自己的程序被分配到内存的什么具体物理地址，仅要知道自己的逻辑地址即可，体现了存储的无关性。(4) 内存扩充：由于物理内存容量有限，难于满足用户程序的需求，存储管理还应该能从逻辑上来扩充内存储器，为用户提供一个比实际内存容量大得多的空间，方便用户的使用，实现虚拟内存。（三）设备管理设备管理的主要任务是：

23、管理分配各类外围设备，完成用户提出的I/O请求，加快I/O信息的传送速度，发挥I/O设备的并行性，提高I/O设备的利用率； 提供各种设备的驱动程序和中断处理程序，向用户屏蔽硬件使用细节。（四）文件系统 上述三种管理都是针对计算机硬件资源的管理，文件系统则是对计算机软件资源的管理。 在现代计算机中，通常把程序和数据以文件形式存储在外存储器上，供用户使用。这样外存储器上保存了大量文件，对这些文件如不能采取良好的管理方式，就会导致混乱或破坏，造成严重后果。（四）文件系统为此，在操作系统中配置了文件系统，它的主要任务是：u 对用户文件和系统文件进行有效管理，以实现按名存取；u 提供给用户一套能方便使用

24、文件的操作和命令。 实现文件的共享、保护和保密，保证文件的安全性；补充解释几个重要术语1.什么是进程 进程的定义：一个具有一定独立功能的程序在某个数据集合上的一次动态执行过程。进程与程序的区别进程是一个动态的概念，而程序则一个是静态的概念。程序是指令的有序集合，没有任何执行的含义。而进程则强调执行过程，它动态地被创建，并被调度执行后消亡。进程是一个能独立运行的单位，能与其它进程并行活动，具有并行特性，而程序没有。进程是竞争计算机系统资源的基本单位，也是进也是进行处理机调度的单位行处理机调度的单位。同一个程序同时运行于若干不同的数据集合上，它将属于若干个不同的进程。2.什么是线程线程 早期，进程

25、是操作系统中资源分配以及系统调度的独立单位。 由于每个进程拥有自己独立的存储空间和运行环境，进程和进程之间并发性粒度较粗，通信和切换的开销相当大。 要更好地发挥硬件提供的能力（如多CPU），以及实现复杂的各种并发应用，单靠进程是无能为力的，于是近年来开始流行多线程（结构）进程（Multithreaded process），也称多线程。2.什么是线程线程 线程是进程中一条执行路径，每个进程中允许有多个并行执行的路径。 在一个多线程环境中，进程是进行系统保护和资源分配的单位，而线程才是进行系统调度的单位。 在一个进程中包含有多个可并发执行的控制流，而不是把多个控制流一一分散在多个进程中，这是并发多

26、线程程序设计与并发多进程程序设计的主要不同之处。3.什么是原语？ 所谓原语（service primitive），是操作系统内核中，由若干条指令构成、用于完成某一特定功能的一个过程，该过程在执行时是不可中断的。 例如，创建进程原语create(n)，撤销进程原语kill(n)，阻塞进程原语susp(n)，唤醒进程原语wakeup(n)。 4.中断机制 中断(interrupt)(interrupt)是指程序执行过程中，当发生某个事件(例如电源掉电、定点加法溢出或I/O传输结束等)时，中止CPUCPU对现行程序的运行，引出处理该事件的服务程序的执行过程，处理完毕后再返回断点继续执行。中断技术 这

27、种处理突发事件的能力是由硬件和软件协作完成的。 首先，由硬件的中断装置发现产生的中断事件，然后，中断装置中止现行程序的执行，引出处理该事件的程序来处理。中断技术在不同的硬件结构中，通常有不同的中断源和中断装置，但它们都有一个共性： 当中断事件发生后，中断装置能改变处理器内操作执行的顺序。由此可见，中断是现代操作系统实现并发性和自动化的基础之一。整个中断处理流程的软硬件分工图2 处理机管理2.1 进程的概念 在多道程序设计的环境下，为了描述程序在计算机系统内的执行情况，必须引人新的概念进程。 进程的概念来自于麻省理工的MULTICS、IBM的TSS/360，在IBM的OS/360/370系统中也

28、曾称作任务（task)。一、进程的定义 行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。 进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan) 进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C. Shaw) 进程是执行中的程序。（Ken Thompson and Dennis Ritchie ) 进程是指一个具有一定独立功能的程序关于某个数据集合的一次运行活动。进程与程序的区别与联系： 程序是指令的集合，是静态的概念。进程是程序在处理机上的一次执行的过程，是动态的概念。程序可以作为软件资料长期保存

29、，而进程是有生命周期的。 进程是一个能独立运行的单位，且能与其它进程并行（并发）活动，而程序则不是。 进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。 一个程序可以作为多个进程的运行程序，一个进程也可以运行多个程序。二、进程的状态进程在系统中的活动规律是：执行暂停执行进程的三种基本状态：就绪状态运行状态等待状态（又称阻塞、挂起、睡眠）进程的基本状态1、就绪状态（Ready) 存在于处理机调度队列中的那些进程，它们已准备就绪，一旦得到CPU控制权，就可以立即运行，这些进程所处状态为就绪状态。（可有多个进程处于此状态）2、运行状态(Run） 当进程由调度/分派程序分派后，得到

30、CPU控制权，它的程序正在运行，该进程所处的状态为运行状态。（在系统中，某一时刻只有一个进程处于此状态，这也就是所谓的微观上串行。）3、等待状态（Wait) 若一个进程正在等待某个事件的发生（如等待I/O的完成）而暂停执行，这时即使给它CPU运行时间，它也无法执行，则称该进程处于等待状态，又称为阻塞状态。进程状态变迁图 进程状态不是固定不变的，而是在不断变换。如下图所示：A Three-state Process ModelReadyRunningBlockedEventOccursDispatchTime-outEventWait在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种

31、基本状态可以依据一定的条件相互转换：就绪运行（进程调度）运行就绪（时间片到、某高优先级进程处于就绪状态等）运行等待（服务请求，如请求I/O等）等待就绪（服务完成/事件来到）进程状态转换2.2 进程控制块(1)什么是进程控制块？ 描述进程与其他进程、系统资源的关系，以及进程在各个不同时期所处状态的数据结构，称为进程控制块pcb(process control block)或称为进程描述器(process descriptor)。2.2 进程控制块 系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。 进程与PCB是一一对应的。进程控制块 进程控制块PCB集中反映了一个进程的动

32、态特征。 在进程并发执行时，由于资源共享，带来各进程之间的相互制约。 显然，为了反映这些制约关系和资源共享关系，在创建一个进程时，应首先创建其PCB，然后才能根据PCB中的信息对进程实施有效的管理和控制。 当一个进程完成其功能后，系统便释放PCB，进程也随之消亡。PCB的结构PCB的结构说明 进程标识符 name：每个进程都必须有一个唯一的标识符，可以是字符串，也可以是一个数字。（标识信息）UNIX系统中就是一个整型数，在进程创建时由系统赋予。 进程当前状态 status：说明本进程目前处于何种状态（运行、就绪、等待），以作为进程调度/分配时的主要依据。（说明信息）PCB的结构说明 当前队列指

33、针 next： 登记与本进程处于同一队列的下一个进程的PCB的地址。PCB的结构说明 总链指针 all-q-next：登记在系统总链队列中的下一个进程的pcb地址。 执行程序开始地址 start-addr：该进程的程序将从此地址开始执行。 进程优先级 priority： 进程的优先级反映了进程的紧迫程度，通常由用户指定和系统设置。（管理信息） PCB的结构说明 CPU现场保护区 cpustatus：当进程由于某种原因释放处理机时，CPU现场信息被保存在pcb的该区域中，以便该进程重新获得处理机后可继续执行。（现场信息）通常被保护的信息有：工作寄存器、指令计数器以及程序状态字等。2.3 进程的通

34、信控制 在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源。这些资源有些是可共享使用的，如磁盘，有些是以独占方式使用的，如打印机。由此可能会引起一系列的矛盾，产生错综复杂的相互制约关系。 产生这种错综复杂的相互制约关系的原因：资源共享，即由于竞争系统资源而引起的间接相互制约关系；进程合作，即由于进程之间存在共享数据而引起的直接相互制约关系。进程间的关系 进程之间的直接相互制约是通过进程通信来实现的，它们之间需要交换信息以便达到协作的目的。进程通信关系又可细分为：进程互斥、进程同步和进程间的直接通信。 进程的互斥(Mutual Exclusion)是指若干个进程要使用

35、同一共享资源时，任何时刻最多允许一个进程去使用，其它要使用该资源的进程必须等待，直到占有资源的进程释放该资源。进程间的关系 进程的同步(Synchronization)是解决进程间协作关系的手段。指一个进程的执行依赖于另一个进程的消息，当一个进程没有得到来自于另一个进程的消息时需要等待，直到消息到达才被唤醒。 不难看出，进程互斥关系是一种特殊的进程同步关系。一、进程互斥引例：宿舍固定电话的使用打印机的使用1. 内存变量、指针、数组等等也是临界资源临界资源说明例1：现有两个进程A、B共享一台打印机，若不加以控制，两个进程的输出结果可能交织在一起，很难区分。 临界资源说明 例2：现有两个进程共享一

36、个变量x，假设x为某航班机座号，p1和p2为两个售票进程，售票工作是对变量x加1。 这两个进程在一个处理机上并发执行，分别具有内部寄存器r1和r2，两个进程共享一个变量x时，有两种可能的执行次序： 情况B为 x = 10+1 临界资源说明 上述问题称之为与时间有关的错误，其实就是因为共享变量，这个共享的变量就是临界资源。 如果不对临界资源加以控制，那么就可能出现错误，这就是本小节要解决的问题。什么是临界资源 特点：当两个进程共用一个变量时，它们必须顺序地使用，一个进程对公用变量操作完毕后，另一个进程才能去访问和修改这一变量。 一次仅允许一个进程使用的资源称为临界资源。 哪些是临界资源临界资源：

37、物理设备，如输入机、打印机、磁带机等都具有这种性质。 1. 软件资源，如公用变量、数据、表格等也都具有这一特点。什么是临界区 临界区：在每个进程中，访问临界资源的那段程序能够从概念上分离出来，称之为临界区或临界段。 它就是进程中对公共变量(或存储区)进行审查与修改的程序段，称为相对于该公共变量的临界区。什么是临界区什么是临界区什么是互斥 互斥：在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或修改该存储区的内容，否则就会发生无法估计的错误。 进程间的这种相互制约关系称为互斥。 如上图所示，进程A正在执行csa段时，进程B就不能进入csb段执行。进入临界区的准则进入临界区的

38、准则：(1)当有若干个进程欲进入临界区时，应 在有限的时间内使其进入； (2)每次最多有一个进程处于临界区；(3)进程在临界区内仅逗留有限的时间。信号灯 1965年荷兰的计算机科学家Dijkstra提出了新的同步工具信号量和P、V操作。 他将交通管制中利用多种颜色的信号灯管理交通的方法引入操作系统，让两个或多个进程通过信号量(Semaphore)展开交互。 进程在某一特殊点上停止执行直到得到一个对应的信号量。通过信号量这一设施，任何复杂的进程交互要求都可得到满足。信号灯的概念 信号量仅能由同步原语对其进行操作。原语是指操作系统中执行时不可中断的过程，即原子操作(Atomic Action)。

39、Dijkstra发明了两个同步原语：P操作和V操作(荷兰语中“测试Proberen”和“增量Verhogen” 的头字母)。 本书采用Dijkstra最早论文中使用的符号P和V。利用信号量和P、V操作既可以解决并发进程的协作问题，又可以解决并发进程的竞争问题。信号灯的概念信号灯的定义： 信号灯是一个确定的二元组（s,q），s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。 s代表资源的实体，在实际应用中应准确地说明s的意义和初值。而每个信号灯都有相应的一个队列，其初始状态为空。P、V操作信号灯的值仅能由P、V操作来改变， 对信号灯的P操作记为：P(S)，P操作是一个原子操作。 对信号

40、灯的V操作记为：V(S), V操作是一个原子操作。信号量的物理意义 信号灯是整型变量： 变量值0时，表示绿灯，进程继续执行。 变量值0：其数值代表可用的资源数量S=0：代表无资源可用，但也没有等待的进程，即也没有申请资源的进程S0：S代表可用的资源数量S=0：代表无资源可用，但也没有等待的进程，即也没有申请资源的进程S=0，不能为负值P和V的位置放置：对于互斥：P、V操作在同一个进程中对于同步：P、V操作在不同进程中3.生产者消费者问题 问题描述：若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出，且任何时刻只能有一个进程可对共享缓冲区进行操作，假设共

41、享缓冲区共有N个。 即满足如下条件：（1）消费者想接收数据时，有界缓冲区中至少有一个单元是满的。（2）生产者想发送数据时，有界缓冲区中至少有一个单元是空的。生产者消费者例子 例1：计算进程和打印进程 计算进程cp不断产生数据，是生产者；打印进程iop不断打印数据，是消费者。 例2：通信问题 发消息进程send不断产生消息，是生产者； 收消息进程receive不断接收消息，是消费者。 生产者消费者问题图示生产者消费者之间的关系一、同步关系：对于生产者进程：产生一个数据，当要送入缓冲区时，检查缓冲区是否已满，若未满，则可将数据送入缓冲区并通知消费者进程，否则，等待；对于消费者进程：当它取数据时，要

42、看缓冲区中是否有数据可取，若有则取走一个数据，并通知生产者进程，否则，等待；1. 这种相互等待并互通消息就是一种典型的进程同步。生产者消费者之间的关系二、互斥关系：缓冲区同时又是个临界资源。当有多个进程在生产产品时，不允许在缓冲区的某一个单元同时存放产品，也不允许多个进程同时消费缓冲区中的某一个单元产品。因此，两者还有个互斥的问题。生产者消费者问题的一般解答信号灯设置： 两个同步信号灯empty:表示空缓冲区的数目，初值为有界缓冲区的大小n； full:表示满缓冲区的数目，初值为0； 一个互斥信号灯mutex：互斥信号灯，初值为1。生产者消费者问题的一般解答程序描述程序描述思考 在这个问题中，

43、P操作的次序是很重要的。如果我们把生产者进程中的两个P操作次序颠倒，那么会有什么问题吗？参见下图的程序:分析 假设在某个时刻，生产者生产得比较快，把所有的缓冲区用完，则有empty=0，full=n，mutex=1。 接着生产者进程运行到1处，使得mutex=0，运行到2处，empty=-10，生产者进程进入等待。 接着消费者进程运行到3处，使得full=n-1，运行到4处，mutex=-10，表示有S个资源可用 S=0，表示无资源可用 S0，|S|表示S等待队列中的进程个数 P(S)：表示申请一个资源，但可能申请不成功 V(S)：表示释放一个资源，有可能会唤醒等待 进程信号量及P、V操作总结

44、2)P、V操作必须成对出现，有一个P操作就一定有一个V操作：当为互斥操作时，它们处于同一进程中当为同步操作时，则分别在不同进程中出现如果两个P操作在一起，那么P操作的顺序就至关重要，一个同步P操作与一个互斥P操作在一起时，同步P操作须在互斥P操作之前；而两个V操作的顺序则无关紧要信号量及P、V操作总结3)P、V操作的优缺点：优点：简单且表达能力强（用P、V操作可解决任何同步/互斥问题）缺点：不够安全（P、V操作若使用不当会导致死锁）信号量及P、V操作总结2.4 死锁2.4.1 死锁的概念操作系统的基本特征是并发与共享。系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度地利用计算

45、机系统的资源，操作系统应采用动态分配系统各种资源的策略。然而采用这种策略时，若分配不当，可能出现进程之间互相等待资源、又都不能向前推进的情况，即造成进程相互死等的局面。2.4.1 死锁的概念事实上，不同进程对资源的申请可能按某种先后次序得到部分满足，这就可能造成其中的两个或几个进程彼此间相互封锁的情况，即每个进程都抓住一些为其他进程所等待的资源不放，其结果是谁也得不到它所申请的全部资源，这些进程最终也都无法运行。例子：银行家问题银行共有资金10万，客户u1需贷款3万，客户u2需贷款8万，客户u3需贷款9万。某一时刻： u2u3u1 已贷款还需资金1万2万2万6万6万3万银行只剩下银行只剩下一万

46、，造成一万，造成死锁死锁。贷不到款，客户死贷不到款，客户死收不回款，银行家死收不回款，银行家死2.4.1 死锁的概念死锁的定义： 在一组并发进程中，每个进程持有某种资源，同时又都等待着被该组进程中其它进程所占有的资源，最终将无限期地僵持下去。这种现象称为进程死锁，而这一组进程就称为死锁进程。设S1=1，打印机可用；S2=1，读卡机可用。OS中的例子 操作系统中的例子现有二个进程P1、P2，两个设备打印机R1、读卡机R2 。 P(S1)； P(S2)； P(S2)； P(S1)； V(S1)； V(S2)； V(S2)； V(S1)； P1P2 P(S1)； P(S2)； V(S1)； V(S2

47、)； P(S2)； P(S1)； V(S2)； V(S1)； P1P2P1P2P1P2？ 两种写法，谁可能造成死锁？死锁wait 原因：原因：1）系统资源不足系统资源不足 w产生死锁的根本原因是：系统能够提供的资源数目 要求该资源的进程数目结论与问题：死锁一定是由于系统资源不足所引起的，但系统资源不足是否就一定造成死锁呢？2）联合推进路线非法联合推进路线非法w进程推进顺序不当2.4.2 产生死锁的原因和必要条件A2B2C2D2申请r1申请r2释放r2释放r1A1B1C1D1申请r1申请r2释放r1释放r2两进程均占用r1两进程均占用r2xyP2进展P1进展0A 死锁点2.4.2 产生死锁的原因

48、和必要条件产生死锁的原因和必要条件路线1路线2tt2.4.2 产生死锁的原因和必要条件 1971年Coffman总结出了系统产生死锁的四个必要条件必要条件：互斥条件（mutual exclusion）不可剥夺条件（no preemption）占有并等待条件（hold and wait）1.循环等待条件（circular wait）互斥条件（mutual exclusion）：进程应互斥使用资源，即涉及的资源必须是非共享使用的，任一时刻一个资源仅为一个进程独占使用。另一个进程去请求一个已被占用的资源时，将被置为等待状态，直到占用者释放资源。2.4.2 产生死锁的原因和必要条件 不可剥夺条件，或称

49、非抢占条件（no preemption）：任一进程不能从另一个进程那里抢夺已被占用而未使用完毕的资源，只能由占用进程自己来释放。2.4.2 产生死锁的原因和必要条件 w占有并等待条件，或称部分分配条件（hold and wait）：进程每次只申请它当前所需要的那部分资源，且在等待另一新资源的同时继续占用已分配的资源。2.4.2 产生死锁的原因和必要条件 循环等待条件，或称环路条件（circular wait）：存在着一个进程的循环等待链，其中每一个进程都在等待前一个进程所持有的资源，造成无限期等待。2.4.2 产生死锁的原因和必要条件 2.4.3 解决死锁问题的策略一、解决死锁问题的几个策略为

50、了不发生死锁，必须设法破坏产生死锁的四个必要条件之一。条件1（互斥条件）：难以否定，因为这是由某些资源的性质所决定的，即使采用了虚拟设备技术，也不能完全排除非共享使用设备死锁的可能性。条件2（不可剥夺条件）：很容易否定的，只要制定相应的规则即可，例如当一个进程（程序）申请某资源被拒绝时，则必须要释放已占用的资源，如果需要再与其它所需资源一起申请。然而，实现这种策略并不容易，一方面会造成资源被抢占后交叉处理的情况，另一方面为了保护和恢复资源被抢占时的状态将花费很大的开销。一般只将处理机看作可被迫抢占的资源。2.4.3 解决死锁问题的策略条件3（占有并等待条件）：容易否定，也容易实现，只要在分配策

51、略上规定一个进程（程序）必须一次性将所需资源申请到位，系统就不会出现死锁。在具体的资源分配策略上，可以采取静态资源分配的方式，一次性把所需资源全部分配到位，进程在没有获得全部资源之前不能投入运行。2.4.3 解决死锁问题的策略条件4（循环等待条件）：通过有序资源分配法，可以破坏环路条件。静态资源分配方法是一种保守的静态预防死锁的方法，其缺点是被分配的资源可能有的使用时间很短，但在被占用期间其它进程长时间内不能访问它们，使得资源利用率很低。为克服这一缺点，希望仍用动态资源分配的方法，但又要能预防死锁的发生，于是只能从最后一个条件入手。2.4.3 解决死锁问题的策略归纳起来，可以采用以下策略之一来

52、解决死锁问题：采用静态资源分配方法预防死锁采用动态资源分配、有控分配方法来避免死锁允许死锁发生，当死锁发生时能检测出死锁，并设法修复忽略死锁，即鸵鸟算法，这种方法为绝大多数操作系统（如UNIX系统）所采用2.4.3 解决死锁问题的策略为了研究解决死锁的方法，可借助于系统状态分析和资源分配图等工具。系统状态分析可以帮助确定某一时刻系统是否处于一个合理的状态，只有保证系统状态是合理的才能防止死锁的发生。系统状态是根据进程对资源的申请、获得使用和释放而改变的，故必须要说明每个时刻进程对资源的请求和占有情况；系统状态分析在某一给定时刻t，系统状态由资源分配矩阵a(t)和资源请求矩阵d(t)来描述，它们

53、分别表示当前已分配给各进程的各类资源数目以及这些进程在时刻t还需申请各类资源的最大需求量；系统的状态只能通过申请资源、获得使用资源和释放资源这三种操作来改变；系统状态分析在一个系统中，若满足下述条件，则认为系统状态是合理的，可以防止死锁的发生。w一个给定进程，不能申请比系统中所拥有的该类资源数还要多的资源；w在每一时刻，每个进程都不会拥有它未曾申请的资源。w在每一时刻，所有进程所接收到的某类资源总数也不能超过系统所拥有的该类资源总数；系统状态分析资源分配图是一种有关系统资源分配的有向图，它可以更为精确地描述死锁现象。该有向图由一个节点集合和一个边集合组成，其中节点集合又分为系统活动进程集合和系

54、统所有资源类型集合。在系统资源分配的有向图中，以方框代表资源节点、圆圈代表进程节点。由于资源类型可能有多个实例，所在在方框中还可以用圆点表示其实例数。资源分配图从进程节点到资源类型节点的有向边称为资源的请求边，表示进程已申请了资源类型的一个实例，但当前正处于阻塞状态，等待资源变为可用。从资源类型节点到进程节点的有向边称为资源的分配边，表示资源类型的一个实例已分配给进程；资源分配图RASBTDUC(a)进程A分配了一个资源(b)进程B请求了一个资源(c)进程C和进程D形成环路，已处于死锁状态资源分配图根据上述资源分配图的定义，不难理解：如果图没有环，那么系统就不会发生死锁；如果图有环，那么可能会

55、出现死锁，此时需要取决于环中所涉及的每个资源类型包含的实例数目。资源分配图2.4.4 死锁的预防静态分配策略所谓资源的静态分配是指，一个进程必须在执行前就申请所需要的全部资源，并且直到它所需要的资源都得到满足后才开始执行。采用资源的静态分配策略后，进程在执行中不再需要申请资源，因而不会出现进程占有某些资源还等待另一些资源的情况，即破坏了第三个必要条件占有并等待条件。2.4.4 死锁的预防静态分配策略静态分配策略实现简单，被许多操作系统采用。但这种策略严重地降低了资源利用率，其缺点也是明显的：一个用户在进程或作业运行之前很难提出将要使用的全部设备；用户进程或作业必须等待，直到所有资源满足时才能投

56、入运行，而实际上某些设备可能很晚的时候才使用；2.4.4 死锁的预防静态分配策略资源浪费太大，有些资源在进程或作业运行期间可能只有很少的时间才用到，有的甚至不会用到。例如，只有当用户程序出错的时候才会将错误从打印机上输出，此时若采用静态预防策略对系统来说是很浪费的。2.4.5 死锁的避免动态分配+有控分配为了提高资源利用率，应采用动态资源分配的方法。但是，为了避免可能产生的死锁，在进行资源分配时，还应采用某种算法来预测是否有可能发生死锁，若存在可能性，就拒绝该资源请求。2.4.5 死锁的避免动态分配+有控分配静态预防死锁和动态避免死锁的不同处在于：n前者采用的分配策略本身就否定了死锁的必要条件

57、之一，这样就保证死锁不可能发生；n而后者是在动态资源分配策略下，另外采用某种算法来避免死锁的发生，拒绝可能引起死锁的某个资源请求。一、有序资源分配法在这一方法中，系统中所有资源都给定一个唯一的序号，所有分配请求必须以上升的次序进行。系统要求每个进程：n对于它所必须使用的而且属于同一类的所有资源，必须一次申请完毕；n在申请不同类的资源时，必须按各类的编号递增顺序依次申请。2.4.5 死锁的避免动态分配+有控分配为了满足上述系统要求，所以在实施分配时，分配程序必须调用一种算法，以考察本次申请的资源序号是否符合递增规定：若符合，则在资源可用的情况下予以分配，否则，拒绝分配。不难看出，由于通过上述算法

58、对资源申请采取了某种限制，所对应的资源分配有向图不可能形成环路，从而破坏了产生死锁的环路条件，因此不会发生死锁。2.4.5 死锁的避免动态分配+有控分配该方案的优点是，用户不需要预先说明对各类资源的最大需求量，只要在申请时按类按序来申请即可。该方案的缺点是，进程实际需要资源的顺序不一定与资源的序号相一致，因而仍会造成某种程度的资源浪费。2.4.5 死锁的避免动态分配+有控分配例如：进程P1，申请资源的顺序是R1，R2；进程P2，申请资源的顺序是R2，R1；若单采用动态资源分配法，则有可能形成环路条件而造成死锁；但若采用有序资源分配法，则可避免出现循环等待的现象。2.4.5 死锁的避免动态分配+

59、有控分配2.4.5 死锁的避免动态分配+有控分配二、银行家算法死锁的避免算法中最有代表性的是Dijkstra E.W于1968年提出的银行家算法，其模型基于一个小城镇的银行系统。现将该算法描述如下：假定一个银行系统拥有资金的数量为，共被N个客户分享。银行家对客户提出下列约束条件：n每个客户必须预先说明自己所要求的最大资金量，这个数量不能超过现存资金量；n每个客户每次提出部分资金量申请，然后获得分配；n如果银行满足了某客户对资金的最大需求量，那么客户在资金运作后，应在有限时间内全部归还银行。2.4.5 死锁的避免动态分配+有控分配在银行家算法中，客户可看作进程，资金可看作资源，银行家则可看作操作

60、系统，这里叙述的是单资源银行家算法。2.4.5 死锁的避免动态分配+有控分配单资源银行家算法单资源银行家算法在上图a中列出了4个客户，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留了10个单位的资金来为客户服务，而不是22个单位。图b所示的状态是客户各自经营，在某些时刻需要贷款，则客户已获得的贷款和当前可用的最大数额贷款称为与资源分配相关的系统状态。单资源银行家算法一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所有的贷款，即所有进程都能得到所需的全部资源并终止。单资源银行家算法图b所示的状态是安全的，因为在尚有2个单位资金可用的情