操作系统操作系统考研辅导讲义操作系统考研辅导讲义（第1,2章）

计算机操作系统 1、 操作系统概述 一、考试大纲 （一）操作系统的概念、特征、功能和提供的服务 （二）操作系统的发展与分类 （三）操作系统的运行环境 二、知识点归纳 （一）操作系统的概念、特征、功能和提供的服务 1．操作系统的概念、目标和作用 一个完整的计算机系统由两大部分组成：计算机硬件和计算机软件。硬件是所有软件运行的物质基础；软件能充分发挥硬件潜能和扩充硬件功能，完成各种系统及应用任务，两者互相促进、相辅相成、缺一不可。计算机硬件是指计算机物理装置本身，由运算器、控制器、存储器、输入设备和输出设备五部分组成。计算机软件是指由计算机硬件执行以完成一定任务的程序及其数据。计算机软件包括系统软件和应用软件。系统软件包括操作系统、编译程序、连接装入程序、数据库管理系统等；应用软件是为各种应用目的而编制的程序。 在计算机上配置操作系统的目的有以下几点： ①方便用户使用。操作系统应该使计算机系统使用起来十分方便。 ②有效性。OS能够有效管理好系统中的各种硬件软件资源，并通过合理地组织计算机的工作流程，进一步改善资源的利用率及提高系统的吞吐量。 ③可扩充性。OS必须具有很好的可扩充性，应采用层次化结构，以便于增加新的功能层次和模块，并修改老的功能层次和模块。 ④构筑开放环境。OS应该构筑出一个开放环境，主要是指：遵循有关国际 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 ；支持体系结构的可伸缩性和可扩展性；支持应用程序在不同平台上的可移植性和可互操作性。 操作系统主要由以下的作用： ①OS作为用户与计算机硬件系统之间的接口：为了使用户能灵活、方便地使用计算机和操作系统，操作系统提供了一组友好的用户接口，包括：1）程序接口；2）命令接口；3）图形接口。 ②OS作为计算机系统资源的管理者：资源包括两大类：硬件资源和软件资源。归纳起来资源分为四类：处理机、存储器、I/O设备以及信息（数据和程序），OS的主要功能是对这四类资源进行管理，即处理机管理、存储器管理、I/O设备管理、文件管理。（资源管理观点） ③OS用作扩充机器：在裸机上覆盖上OS后，便可获得一台功能显著增强、使用极为方便的多层扩充机器或多层虚机器。（虚拟机观点） 操作系统可定义为：操作系统是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。 2．操作系统的特征 虽然不同的操作系统具有各自的特点，但它们都具有以下4个基本特征： （1）并发性 并行性和并发性是既相似又有区别的两个概念，并发性是指两个或多个事件在同一时刻发生；并发性是指两个或多个事件在同一时间间隔内发生。在多道程序环境下，并发性是指宏观上在一段时间内有多道程序在同时运行，但在单处理机系统中，每—时刻仅能执行—道程序，故微观上这些程序是交替执行的。 （2）共享性 资源共享是指系统中的硬件和软件资源不再为某个程序所独占，而是供多个用户程序共同使用。 并发和共享是操作系统的两个最基本的特征，二者之间互为存在条件。一方面，资源的共享是以程序的并发执行为条件的，若系统不允许程序的并发执行，自然不存在资源共享问题；另一方面，若系统不能对资源共享实施有效的管理，也必将影响到程序的并发执行，甚至根本无法并发执行。 （3）虚拟性 在操作系统中，虚拟是指把一个物理上的实体变为若干个逻辑上的对应物，前者是实际存在的，后备是虚的，只是用户的一种感觉。 （4）异步性（不确定性） 在操作系统中，不确定性有两种含义： ①程序执行结果是不确定的，即对同一程序，使用相同的输入，在相同的环境下运行却可能获得完全不同的结果。亦即程序是不可再现的； ②多道程序环境下程序的执行是以异步方式进行的，换言之，每个程序何时执行，多个程序间的执行顺序以及完成每道程序所需要的时间都是不确定的，因而也是不可预知的。 3．操作系统的功能 操作系统的职能是负责系统中软硬件资源的管理，合理地组织计算机系统的工作流程，并为用户提供一个良好的工作环境和友好的使用界面。下面从5个方面来说明操作系统的基本功能。 （1）处理机管理。处理机管理的主要任务是对处理机的分配和运行实施有效的管理。在多道程序环境下，处理机的分配和运行是以进程为基本单位的，因此对处理机的管理可归结为对进程的管理。进程管理应实现下述主要功能： ①进程控制：负责进程的创建、撤消及状态转换。 ②进程同步：对并发执行的进程进行协调。 ③进程通信：负责完成进程间的信息交换。 ④进程调度：按一定算法进行处理机分配。 （2）存储器管理。存储器管理的主要任务是对内行进行分配、保护和扩充。存储器管理应实现下述主要功能： ①内存分配：按一定的策略为每道程序分配内存。 ②内存保护：保证各程序在自己的内存区域内运行而不相互干扰。 ③地址映射：将地址空间的逻辑地址转换为内存空间与之对应的物理地址。 ④内存扩充：为允许大型作业或多作业的运行，必须借助虚拟存储技术去获得增加内存的效果。 （3）设备管理：计算机外部设备的管理是操作系统中最庞杂、琐碎的部分。设备管理的主要任务是对计算机系统内的所有设备实施有效的管理。设备管理应具有下述功能： ①设备分配：根据一定的设备分配原则对设备进行分配。为了使设备与主机并行工作，还需采用缓冲技术和虚拟技术。 ②设备传输控制：实现物理的输入输出操作，即启动设备、中断处现、结束处理等。 ③设备独立性：即用户向系统申请的设备与实际操作的设备无关。 （4）文件管理。文件管理的主要任务是有效地支持文件的存储、检索和修改等操作，解决文件的共享、保密和保护问题。文件管理应实现下述功能： ①文件存储空间的管理：负责对文件存储空间进行管理，包括存储空间的分配与回收等功能。 ②目录管理：目录是用来管理文件的数据结构，它能提供按名存取的功能。 ③文件操作管理：实现文件的操作，负责完成数据的读写。 ④文件保护：提供文件保护功能，防止文件遭到破坏。 （5）用户接口。为方便用户使用操作系统，操作系统提供了用户接口。操作系统通常提供如下几种类型的用户接口。 ①命令接口：提供—组命令供用户直接或间接控制自己的作业。 ②程序接口：提供一组系统调用供用户程序和其他系统程序调用。 ③图形接口：图形用户接口采用了图形化的操作界面，用非常容易识别的各种图标将系统的各项功能、各种应用程序和文件直观、逼真地表示出来，用户可通过鼠标、菜单和对话框来完成各种应用程序和文件的操作。 4．操作系统提供的服务 操作系统为程序和用户提供了一系列的操作系统服务，这些服务可使程序员更容易地完成他的工作。 （1）操作系统的公共服务类型，主要有：程序执行、I/O操作、文件系统操作、通信和差错检测等。 （2）系统调用中的作用，系统调用的类型是根据操作系统所提供服务的功能决定的，系统调用可分为进程管理、设备管理、文件管理、信息维护以及通信等。 （二）操作系统的发展与分类 操作系统的主要发展过程如下： 1．无操作系统时的计算机系统 （１）手工操作阶段 早期的计算机系统上没有配置操作系统，计算机的操作由程序员采用手工操作直接控制和使用计算机硬件。程序员使用机器语言编程，并将事先准备好的程序和数据穿孔在纸带或卡片上，从纸带或卡片输入机将程序和数据输入计算机。然后，启动计算机运行，程序员可以通过控制台上的按钮、开关和氖灯来操纵和控制程序，运行完毕，取走计算的结果，才轮到下一个用户上机。这种手工操作方式具有用户独占计算机资源、资源利用率低及CPU等待人工操作的缺点。 随着CPU速度的大幅度提高，手工操作的慢速与CPU运算的高速之间出现了矛盾，这就是所谓的人机矛盾。另一方面，CPU与I/O设备之间速度不匹配的矛盾也日益突出。 （２）脱机输入/输出技术 为解决CPU与I/O设备之间速度不匹配的问题，将用户程序和数据在一台外围机（又称卫星机）的控制下，预先从低速输入设备输入到磁带上，当CPU需要这些程序和数据时，再直接从磁带机高速输入内存，从而大大加快程序的输入过程，减少CPU等待输入的时间，这就是脱机输入技术；类似地，当CPU需要输出时，无需直接把计算结果送至低速输出设备，而是高速地把结果送到磁带上，然后在外围机的控制下，把磁带上的计算结果由相应的输出设备输出，这就是脱机输出技术。 若输入/输出操作在主机控制下进行则称之为联机输入/输出。 2．单道批处理操作系统 批处理技术是指计算机系统对一批作业自动进行处理的一种技术。早期的计算机系统非常昂贵，为了能充分地利用它，应尽量让系统连续地运行，以减少空闲时间。为此通常把一批作业以脱机输入方式输入到磁带上，并在系统中配置监督程序（是一个常驻内存的程序，它管理作业的运行，负责装入和运行各种系统处理程序来完成作业的自动过渡），在它的控制下，先把磁带上的第一个作业传送到内存，并把运行的控制权交给该作业，当该作业处理完后又把控制权交还给监督程序，由监督程序再把第二个作业装入内存。计算机系统按这种方式对磁带上的作业自动地、一个接一个地进行处理，直至把磁带上的所有作业全部处理完毕，由于系统对作业的处理是成批进行的、且在内存中始终只保持一道作业，故称为单道批处理系统。其主要特征是：①自动性；②顺序性；③单道性。 3．多道批处理技术 多道程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 的基本概念：多道程序设计技术是将多个作业存放在内存中并允许它们交替执行，这些作业共享处理机时间和外围设备以及其他资源。当一道程序因某种原因（如I/O请求）而暂停执行时，CPU立即转去执行另一道程序。在操作系统中引入多道程序设计技术后，会使系统具有多道、宏观上并行、微观上串行的特点。 在单道批处理系统中，内存中仅有一道作业，使得系统中仍有较多的空闲资源，致使系统的性能较差，20世纪60年代引入多道程序设计技术后，形成了多道批处理技术，进一步提高了资源利用率和系统的吞吐量。 在多道批处理系统中，用户所提交的作业都先存放在外存并排成一个队列，该队列称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源，以达到提高资源利用率和系统的吞吐量的目的。其主要特征是：①多道性；②无序性；③调度性。 4．分时操作系统 （1）分时系统的产生 如果说，推动多道批处理系统形成和发展的主要动力是提高资源利用率和系统吞吐率，那么，推动分时系统形成和发展的主要动力，则是用户的需要。体现在人-机交互、共享主机、便于用户上机等方面。 （2）分时系统的特征 分时系统与多道批处理系统相比，具有完全不同的特征： ①多路性。指一台计算机与若干台终端相连接，系统按分时原则为每个用户服务。宏观上，是多个用户同时工作，共享系统资源；微观上，则是每个用户作业轮流运行一个时间片。多路性亦即同时性，它提高了资源利用率，从而促进了计算机更广泛地应用。 ②独立性。每个用户各占一个终端，彼此独立操作、互不干扰。 ③及时性。用户的请求能在很短时间内获得响应。 ④交互性。用户可通过终端与系统进行广泛的人机对话。其广泛性表现在：用户可以请求系统提供各方面的服务，如文件编辑、数据处理和资源共享等。 5．实时操作系统 （1）实时系统的引入 虽然多道批处理系统和分时系统已获得较为令人满意的资源利用率和响应时间，从而使计算机的应用范围日益扩大，但它们仍然不能满足以下两个领域的需要： ①实时控制：实时控制系统通常是指以计算机为中心的生产过程控制系统，又称为计算机控制系统。例如钢铁冶炼和钢板轧制的自动控制，化工、炼油生产过程的自动控制等。 ②实时信息处理：在实时信息处理系统中，计算机能及时接收从远程终端发来的服务请求，根据用户提出的问题对信息进行检索和处理，并在很短时间内对用户做出正确回答，如机票订购系统，情报检索系统等。 （2）实时任务的类型 ①按任务执行时是否呈现周期性来划分：分为周期性实时任务和非周期性实时任务。 ②根据对截止时间的要求来划分：分为硬实时任务和软实时任务。 （3）实时系统与分时系统的比较 ①多路性； ②独立性： ③及时性； ④交互性； ⑤可靠性 实时操作系统的主要特点是响应及时和可靠性高。系统必须保证对实时信息的分析和处理的速度要快，而且系统本身要安全可靠，因为在生产过程的实时控制、航空订票等实时事务系统，信息处理的延误或丢失往往会带来不堪设想的后果。 随着计算机硬件及其应用的不断发展，操作系统的类型也逐渐多样化，如何对这些操作系统进行分类取决于分类的方法，即所依据的标准。下面列出了三种分类方法。 （1）按用户数目分为单用户操作系统和多用户操作系统。其中，单用户操作系统又分为单任务操作系统和多任务操作系统。 （2）按硬件结构分为单CPU操作系统、多CPU操作系统、网络操作系统、分布式操作系统和多媒体操作系统。 （3）按使用环境分为批处理操作系统、分时操作系统和实时操作系统。这是最常用的一种分类方法。 批处理操作系统、分时操作系统和实时操作系统是三种基本的操作系统类型。如果一个操作系统兼有批处理、分时处理和实时处理系统三者或其中两者的功能，那就形成了通用操作系统。 （三）操作系统的运行环境 操作系统的运行环境主要包括计算机系统的硬件环境和由其它系统软件形成的软件环境，以及操作系统和使用它的人之间的关系。 硬件环境主要包括中央处理器（CPU）、存储系统、中断机制、I/O技术和时钟等方面。下面主要说明CPU状态和中断机制。 特权指令：只能由操作系统使用的指令。如：修改程序状态字、开关中断、置中断向量、启动设备执行I/O操作、设置硬件实时钟、停机等 非特权指令：特权指令之外的指令，这些指令的执行不影响其它用户以及系统状态.如算术运算指令、逻辑运算指令、取数存数指令、访管指令等 1．CPU状态—管态和目态 计算机系统中，操作系统程序作为用户程序的管理者和控制者，享有用户程序所不能享有的某些特权，为避免错误地使用特权指令，将CPU的运行状态分为管态和目态。由程序状态(PSW)寄存器内的标志触发器来进行标识。 管态又称为系统态或核心态，操作系统程序在管态下运行，能执行包括特权指令在内的所有指令。 目态又称为用户态或常态，外层用户程序在目态下运行，不可执行特权指令。若出现特权指令、CPU能识别出程序非法使用指令，形成一个程序性中断事件，中止程序的执行。 目态--管态 其转换的唯一途径是通过中断 管态--目态 可用设置PSW(修改程序状态字)可实现 2．中断机制 (1)中断的定义：所谓中断是指系统发生某一事件后，CPU暂停正在执行的程序转去执行处理该事件的程序过程，处理中断事件的程序称为中断处理程序，产生中断信号的那个部件称为中断源。硬件的中断机构与处理这些中断的程序统称为中断系统。 (2)中断的类型 不同的计算机系统．其产生中断的原因及其处理方式均不同，通常将系统内的所有中断分为若干类。 ①根据中断信号的含义和功能分为以下五类； 机器故障中断：因机器发生错误(电源故障，内存读数错误等)而产生的中断，用以反映硬件故障，以便进入诊断程序。 I/O中断：由输入/输出设备引起的中断，用以反映通道或外部设备工作状态。 外中断：由各种外部事件引起的中断，用以反映外部的要求。 程序性中断：因程序中错误使用指令或数据引起的中断，用以反映程序执行过程中发生的例外情况。 访管中断：由于程序执行了“访管”指令（系统调用）而产生的中断，用于反映用户程序所请求操作系统为其完成某项工作。 ②根据中断信号的来源分为两类； 中断，也称外中断，指来自CPU以外事件的中断，是与当前运行程序无关的暂停事件。对它的处理不必完全依赖当前程序的运行现场，具有较低的中断优先级，可被临时屏蔽。 异常，也称内中断或陷入，指源自CPU内部事件的中断，是与当前运行程序相关的暂停事件，对其处理要依赖于当前程序的运行现场，均具有较高的优先级，一旦出现应立即处理。 ③根基是否是当前程序期望的分为两类： 强迫性中断： 正在运行的程序所不期望的，由于某种硬件故障或外部请求引起的 · 输入/输出(I/O)中断：主要来自外部设备通道 · 程序性中断：运行程序中本身的中断 (如溢出,缺页中断,缺段中断,地址越界) · 时钟中断 · 控制台中断 · 硬件故障 自愿性中断（访管中断）： 用户在程序中有意识安排的中断，是由于用户在编制程序时因为要求操作系统提供服务，有意使用“访管”指令（系统调用），使中断发生 · 执行I/O，创建进程，分配内存 · 信号量操作，发送/接收消息 三、经典例题解析 1．操作系统是对（ ）进行管理的软件。 A．软件 B．硬件 C．计算机资源 D．应用程序 分析与解答 操作系统是一个系统软件，不但管理计算机系统的硬件资源，还管理软件资源，是整个计算机系统硬、软件资源的总指挥部。 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 是C 2．批处理操作系统的目的是（）。 A．提高系统与用户的交互性能 B．提高系统资源利用率 C．降低用户作业的周转时间 D．减少用户作业的等待时间 分析与解答 批处理系统的主要优点是系统吞吐量大、资源利用率高，主要缺点是交互能力差、作业周转时间长。答案是B 3．试对分时系统和实时系统进行比较。 分析与解答 我们可以从以下几个方面对这两种操作系统进行比较。 （1）从多路性看，实时信息处理系统与分时系统—样都能为多个用户服务。系统按分时原则为多个终端用户服务；而对实时控制系统，则表现为经常对多路现场信息进行采集以及对多个对象或多个执行机构进行控制。 （2）从独立性看，实时信息处理系统与分时系统—样，每个用户各占一个终端，彼此独立操作，互不干扰。因此用户感觉就像他一人独占计算机；而实时控制系统中信息的采集和对对象的控制都是彼此互不干扰的。 （3）从及时性看，实时信息系统对响应时间的要求与分时系统类似，都是以人们所能接受的等待时间来确定；而实时控制系统的响应时间则是以控制对象所能接受的延时来确定的。 （4）从交互性看，分时系统是一种通用性系统，主要用于运行终端用户程序，因此它具有较强的交互能力；而实时系统虽然也有交互能力，但其交互能力不及前者。 （5）从可靠性看，分时系统也要求系统可靠，相比之下，实时系统则要求系统高度可靠。 4．一个分层结构操作系统由裸机，用户，CPU调度和P、V操作，文件管理，作业管理，内存管理，设备管理，命令管理等部分组成。试按层次结构的原则从内到外将各部分重新排列。 分析与解答 采用分层结构方法可以将操作系统的各种功能分成不同的层次，即将整个操作系统看成是由若干层组成，每一层都提供一组功能，这些功能只依赖于该层以内的各层次，最内层部分是机器硬件本身提供的各种功能。操作系统的这种层次结构如图1.1所示，同机器硬件紧挨着的是操作系统内核，它是操作系统的最里一层。内核包括中断处理、设备驱动、处理机调度以及进程控制和通信等功能，其目的是提供一种进程可以存在和活动的环境。内核以外各层依次是存储管理层、I/O管理层、文件管理层和作业管理层。它们提供各种资源管理功能并为用户提供各种服务。命令管理是操作系统提供给用户的接口层，因而在操作系统的最外层。 从上述分析可知，按层次结构原则从内到外依次为：裸机，CPU调度和P、V操作，内存管理，设备管理，文件管理，作业管理，命令管理，用户。 5．操作系统具有哪些特征?它们之间有何关系? 分析与解答 操作系统的特征有并发、共享、虚拟和异步性（不确定性）。它们的关系如下： （1）并发和共享是操作系统最基本的特征。为了提高计算机资源的利用率，操作系统必然要采用多道程序设计技术，使多个程序共享系统的资源，并发的执行。 （2）并发和共享互为存在的条件。一方面，资源的共享以程序（进程）的并发执行为条件，若系统不允许程序并发执行，自然不存在资源的共享问题；另一方面，若系统不能对资源共享实施有效管理，协调好各个进程对共享资源的访问，也必将影响到程序的并发执行，甚至根本无法并发执行。 （3）虚拟以并发和共享为前提条件。为了使并发进程能更方便、更有效地共享资源，操作系统经常采用多种虚拟技术来在逻辑上增加CPU和设备的数量以及存储器的容量，从而解决众多并发进程对有限系统资源的竞争问题。 （4）异步性（不确定性）是并发和共享的必然结果。操作系统允许多个并发进程共享资源、相互合作，使得每个进程的运行过程受到其他进程的制约，系统中的每个程序何时执行，多个程序间的执行顺序以及完成每道程序所需的时间是不确定的，因而也是不可预知的。 四、题型 练习 飞向蓝天的恐龙练习非连续性文本练习把字句和被字句的转换练习呼风唤雨的世纪练习呼风唤雨的世纪课后练习 (一)单项选择题 1．操作系统的（ ）管理部分负责对进程进行调度。 A．主存储器 B．运算器 C．控制器 D．处理机 2．从用户的观点看，操作系统是（） A．用户与计算机之间的接口 B．控制和管理计算机资源的软件 C．合理地组织计算机工作流程的软件 D．由若干层次的程序按一定的结构组成的有机体 3．操作系统是一种（ ）。 A．通用软件 B．系统软件 C．应用软件 D．软件包 4．一般用户更喜欢使用的系统是（ ）。 A.手工操作 B.单道批处理 C.多道批处理 D.多用户分时系统 5．与计算机硬件关系最密切的软件是（ ）。 A.编译程序 B.数据库管理系统 C.游戏程序 D.OS 6．操作系统的基本类型主要有（ ）。 A.批处理系统、分时系统及多任务系统 B.实时系统、批处理系统及分时操作系统 C.单用户系统、多用户系统及批处理系统 D.实时系统、分时系统和多用户系统 7．多道批处理系统的硬件支持是20世纪60年代初发展起来的（ ）。 A.RISC技术 B.通道和中断机构 C.集成电路 D.高速内存 8．现代OS具有并发性和共享性，是（ ）的引入导致的。 A.单道程序 B. 磁盘 C. 对象 D.多道程序 9．（ ）不是设计实时操作系统主要的追求目标。 A．安全可靠 B．资源利用率 C．及时响应 D．快速处理 10．（ ）不是多道程序系统。 A.单用户单任务 B.多道批处理系统 C.单用户多任务 D.多用户分时系统 11．现代操作系统的两个基本特征是（ ）和资源共享性。 A.多道程序设计 B. 中断处理 C.程序的并发性 D. 实现分时与实时处理 12. 早期的OS主要追求的是（ ）。 A.系统的效率 B.用户的方便性 C.可移植 D.可扩充性 13.在单CPU系统中，多道程序运行除了“多道”的特点以外还有( )。 A.宏观上串行，微观上也串行 B.宏观上并行，微观上串行 C.宏观上并行，微观上也并行 D.宏观上串行，微观上并行 14. （ ）操作系统允许在一台主机上同时连接多台终端,多个用户可以通过自己的终端同时交互地使用计算机. A.网络 B.分布式 C.分时 D.实时 15. 没有了（ ）计算机系统就启动不起来。 A.编译器 B.DBMS C.OS D.浏览器 16．用户可以通过（ ）两种方式使用计算机。 A．命令方式和函数方式 B．命令方式和系统调用方式 C．命令方式和文件管理方式 D．设备管理方式和系统调用方式 17. 操作系统的主要功能有（ ）。 A. 进程管理、存储器管理、设备管理、处理机管理 B. 虚拟存储管理、处理机管理、进程调度、文件系统 C. 处理机管理、存储器管理、设备管理、文件系统 D. 进程管理、中断管理、设备管理、文件系统 18．下面关于操作系统的叙述中正确的是( ) A.批处理作业必须具有作业控制信息 B.分时系统不一定都有人机交互功能 C.从响应时间的角度看，实时系统与分时系统差不多 D.由于采用了分时技术，用户可以独占计算机资源 19. 单处理机计算机系统中，（ ）是并行操作的。 A.处理机的操作与通道的操作是并行的 B.程序与程序 C.主程序与子程序 D.用户程序与操作系统程序 20．（ ）是操作系统最重要的两个目标 A.可扩充性和开放性 B.方便性和开放性 C. 可扩充性和有效性 D. 方便性和有效性 21．处理机的所有指令可以在（ ）执行。 A.目态 B.浏览器中 C.任意的时间 D.系统态 22．（ ）功能不是操作系统直接完成的功能。 A.管理计算机硬盘 B.对程序进行编译 C.实现虚拟存储器 D.删除文件 23.要求在规定的时间内对外界的请求必须给予及时响应的OS是（ ）。 A.多用户分时系统 B.实时系统 C.批处理系统时间 D.网络操作系统 24．在指令系统中只能由操作系统使用的指令称为（ ）。 A.系统指令 B.设备指令 C.非特权指令 D.特权指令 25.（ ）对多用户分时系统最重要。 A.实时性 B.交互性 C.共享性 D.运行效率 26.（ ）对多道批处理系统最重要。 A.实时性 B.交互性 C.共享性 D.运行效率 27. ( )对实时系统最重要。 A.及时性 B.交互性 C.共享性 D.运行效率 28. 如果分时操作系统的时间片一定，那么（ ），则响应时间越长。 A.用户数越少 B.用户数越多 C.内存越小 D.内存越大 29. 下列选项中，操作系统提供的给应程序的接口是（） A、系统调用 B、中断 C、库函数 D、原语 30. 在下面关于并发性的叙述中正确的是（ ）。 A.并发性是指若干事件在同一时刻发生 B.并发性是指若干事件在不同时刻发生 C.并发性是指若干事件在同一时间间隔内发生 D.并发性是指若干事件在不同时间间隔内发生 31. 下面对OS不正确的描述是（ ）。 A.OS是系统资源管理程序 B.OS是为用户提供服务的程序 C.OS是其它软件的支撑软件 D.OS是系统态程序的集合 32. OS的不确定性是指（ ） A.程序的运行结果不确定 B.程序的运行次序不确定 C.程序多次运行的时间不确定 D. A、B和C 33. 下面哪一个不是程序在并发系统内执行的特点（ ）。 A.程序执行的间断性 B.相互通信的可能性 C.产生死锁的必然性 D.资源分配的动态性 34. 在下列操作系统的各个功能组成部分中，（ ）不需要硬件的支持。 A．进程调度 B．时钟管理 C．地址映射 D．中断系统 35. 一般来说，为了实现多道程序设计，计算机最需要（ ） A.更大的内存 B.更多的外设 C.更快的CPU D.更先进的终端 36.用户程序在目态下使用系统调用引起的中断属于( ) A．硬件故障中断 B．程序中断 C．外部中断 D．访管中断 37.操作系统在计算机系统中介于( )之间。 A．CPU和用户之间 B．CPU和程序员之间 C．计算机硬件和用户 D．计算机硬件和软件之间 38.下列哪种管理是与系统的软件资源有关的（ ） A.处理机管理 B.存储管理 C.设备管理 D.文件系统管理 39.推动分时系统形成和发展的主要动力是（ ） A．提高资源利用率 B．用户的需要 C．提高系统吞吐量 D．提高CPU利用率 40．在计算机操作中，最外层的是（）。 A．硬件系统 B．系统软件 C．支援软件 D．应用软件 (二)综合应用题 1．采用多道程序设计的主要优点是什么? 2．操作系统是随着多道程序设计技术的出现逐步发展起来的，要保证多道程序的正确运行、在技术上要解决哪些基本问题? 3．实现多道程序系统的最主要硬件支持是什么？ 4．叙述操作系统在计算机系统中的位置。 5．处理机为什么要区分管态和目态（系统态和用户态）？ 6．网络操作系统与分布式操作系统的区别？ 7. 多用户分时系统如何克服多道批处理系统的缺点 ？ 8.AB两个程序，程序A按顺序使用CPU10s，使用设备甲10s，使用CPU5s，使用设备乙10s ,最后使用CPU10s。程序B按顺序使用设备甲10s，使用CPU10s，使用设备乙10s，使用CPU5s，使用设备乙10s，问： （1）在顺序环境下先执行程序A再执行程序B，CPU的利用率是多少？ （2）在多道程序环境下，CPU的利用率是多少？ 五、参考答案 (一)选择题 1.C 2.A 3.B 4.D 5.D 6.B 7.B 8.D 9.B 10.A 11.C 12.A 13.B 14.C 15.C 16.B 17.C 18.A 19.A 20.D 21.D 22.B 23.B 24.D 25.B 26.D 27.A 28.B 29.A 30.C 31.D 32.D 33.C 34.A 35.A 36.D 37.C 38.D 39.B 40.D （二）综合应用题 1．采用多道程序设计的主要优点是什么? 答：在单道运行方式下，每当程序发出I/O请求时，CPU便处于等待I/O完成的状态，致使CPU空闲。多道程序设计考虑到作业的运行规律是交替使用CPU和I/O，故将多道程序同时保存于系统中，使各作业对CPU和I/O的使用在时间上重叠，提高了CPU和I/O设备的利用率。 2．操作系统是随着多道程序设计技术的出现逐步发展起来的，要保证多道程序的正确运行、在技术上要解决哪些基本问题? 答：多道程序设计技术能有效提高系统的吞吐量和改善资源利用率。实现多道程序系统时，由于主存中总是同时存在几道作业，因而需要妥善解决下述几个问题： （1）处理机管理问题。应如何分配被多道程序共享的处理机，以使处理机既能满足各程序运行的需要又有较高的利用率；当把处理机分配给某程序后，应何时收回处理机。 （2）内存管理问题。如何为每道程序分配必要的内存空间，使它们各得其所又不致因相互重叠而丢失信息；应如何防止因某道程序出现异常情况而破坏其他程序。 （3）设备管理问题。系统中可能有多种类型的I/O设备供多道程序共享，应如何分配这些I/O设备；如何做到既方便用户对设备的使用。又能提高设备的利用率。 （4）文件管理问题。在现代计算机系统中，通常都存放着大量的程序和数据信息，应如何组织信息才能便于用户使用并能保证数据信息的安全性和一致性。 3．实现多道程序系统的最主要硬件支持是什么？ 答：最主要硬件支持是中断系统和通道技术。 （1）很多进程的切换是由时钟中断引起的，尤其是分时系统。用户程序进行系统调用时通过软中断来实现，如TRAP。通道和外设的操作也要向操作系统发送中断。 （2）在多道程序系统中，当CPU要求在主存和外设间传输数据时，通过发出I/O指令命令通道工作，通道独立地在内存和外设间进行数据传输，I/O操作完成后，通道以中断方式通知CPU，从而实现了CPU计算与I/O操作的并行。 4．叙述操作系统在计算机系统中的位置。 答：操作系统是运行在计算机硬件系统上的最基本的软件。它控制和管理着所有的系统硬件(CPU、主存、各种硬件部件和外部设备等)，也控制和管理着所有的软件(系统程序和用户进程等)，操作系统为计算机使用者提供了一种良好的操作环境，也为其他各种应用系统提供了最基本的支撑环境。现代操作系统是一个复杂的软件系统．它与计算机硬件系统有着千丝万缕的联系，也与用户有着密不可分的关系，它在计算机系统中位于计算机硬件和计算机用户之间，如图1.2所示。紧挨着硬件的就是操作系统，它通过系统核心程序对计算机系统中的几类资源进行管理，如处理机、存储器、输入／输出设备、数据与文档资源、用户作业等，并向用户提供若干服务，通过这些服务将所有对硬件的复杂操作隐藏起来，为用户操供一个透明的操作环境。操作系统是最基本的系统软件。操作系统的外层是其他系统软件，用户可以直接通过系统软件层与计算机打交道，也可以建立各类应用软件和应用系统，通过它们来解决用户的问题。 由此可见，操作系统是介于计算机硬件和用户之间的一个接口。 5．处理机为什么要区分管态和目态（系统态和用户态）？ 答：区分管态和目态主要原因如下： 为了防止操作系统及关键数据受到用户程序有意或无意的破坏，通常将处理机的执行状态分成管态和目态（系统态和用户态）两种。处于目态执行的程序的操作要受到限制，不能去执行特权指令，访问操作系统区域和其他程序的区域，这就防止了用户程序对操作系统和其他用户程序的破坏。操作系统的内核通常是运行在管态（系统态）的，目态（用户态）的程序通过系统调用接受管态程序运行的服务。 目态下的进程能存取它们自己的指令与数据，但不能存取内核指令和数据或其他进程的指令和数据。然而，管态下的进程能够使用所有指令、资源，并具有改变CPU状态的能力。在目态下执行的进程没有执行特权指令的能力，在目态下执行特权指令会引起错误。 从目态转换为管态的惟一途径是中断；从管态到目态的转换通过修改程序状态字来实现。 6．网络操作系统与分布式操作系统的区别？ 答：在计算机网络中，可根据网络结构、通信方式和资源管理方法配置网络操作系统和分布式操作系统。在配置了网络操作系统的计算机网络中，各计算机没有主次之分；网络中任意两台计算机可以进行信息交换；网络OS中的用户使用自己的机器可以访问网络上别的机器的资源，通过网络将很多的机器连接起来，共享软硬件资源，但是整个系统对用户来说是分散的、不透明的。而分布式计算机是由多台计算机组成的一种特殊的计算机网络，分布式操作系统能使系统中的若干台计算机相互协作完成一个共同的任务，使一个程序分布在几台计算机上并行执行、互相协作得出最终的计算结果，但是整个系统对用户是透明的，用户面对整个OS就好像使用一个自己的机器一样。 7. 多用户分时系统如何克服多道批处理系统的缺点 ？ 答:尽管多道批处理系统已经大大地提高了计算机系统的资源利用率，但是它的致命缺点是缺少交互性。怎样才能使系统既具有交互性又不使资源的利用率降低？资源利用率与交互性是一对矛盾。如果一台计算机能够连接多个操作台（终端），允许多个用户同时在操作台上操作，每个操作台上的用户执行一个程序，就有多个程序进入系统，导致在计算机的内存中就装入了多个程序，形成多个程序的并发执行,通过并发程序的分时执行，确保每个用户的操作计算机终端就好像单独操作一台计算机一样。这样就避免了只有一个操作台时，大量的计算机的时间被一个用户的大量浪费，同时又克服多道批处理系统非交互性的缺点。 8. AB两个程序，程序A按顺序使用CPU10s，使用设备甲10s，使用CPU5s，使用设备乙10s ,最后使用CPU10s。程序B按顺序使用设备甲10s，使用CPU10s，使用设备乙10s，使用CPU5s，使用设备乙10s，问： （1）在顺序环境下先执行程序A再执行程序B，CPU的利用率是多少？ （2）在多道程序环境下，CPU的利用率是多少？ 答：（1）程序A和程序B顺序执行，程序A执行完毕，程序B才开始执行。两个程序共耗时90s，其中占用CPU的时间为40s，因此顺序执行时CPU的利用率为44.4% （2）在多道程序环境下，两个程序并发执行，执行情况如图1.3所示，两个程序共耗时50s，其中占用CPU的时间为40s，故此时CPU的利用率为40/50=80%。 程序A CPU (10s) 设备甲 (10s) CPU (5s) 空闲 (5s) 设备乙 (10s) CPU (10s) 程序B 设备甲 (10s) CPU (10s) 设备乙 (10s) CPU (5s) 空闲 (5s) 设备乙 (10s) 图1.3 多道环境下A、B执行示意图 二、进程管理 一、考试大纲 （一）进程与线程： 1．进程概念 2．进程的状态与转换 3．进程控制 4．进程组织 5．进程通信 共享存储系统；消息传递系统；管道通信 6．线程概念与多线程模型 （二）处理机调度 1．调度的基本概念 2．调度时机、切换与过程 3．调度的基本准则 4．调度方式 5．典型调度算法 先来先服务调度算法；短作业（短任务、短进程、短线程）优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法。 (三)进程同步 1．进程同步的基本概念 2．实现临界区互斥的基本方法 软件实现方法；硬件实现方法 3．信号量 4．管程 5．经典同步问题 生产者—消费者问题；读者—写者问题；哲学家进餐问题。 （四）死锁 1．死锁的概念 2．死锁处理策略 3．死锁预防 4．死锁避免 系统安全状态；银行家算法 5．死锁的检测和解除 二、知识点归纳 （一）进程与线程 1．进程概念 （1）前趋图 前驱图是一个有向无循环图，图中的每个结点可以表示一条语句、一个程序段或进程，结点间的有向边表示两个之间存在偏序或前趋关系“(”： (={(Pi,Pj)( (Pi必须在Pj开始执行之前完成} 若(Pi,Pj) ((，记为Pi(Pj，则称Pi是Pj的直接前趋，Pj 是Pi的直接后继。若存在一个序列Pi(Pj(…(Pk，则称Pi是Pk的前趋。在前趋图中，没有前趋的结点称为初始结点，没有后继的结点称为终止结点。 （2）程序的顺序执行 —个程序通常由若干个程序段所组成，它们必须按照某种先后次序来执行，仅当前一个操作执行完后，才能执行后继操作，这类计算过程就是程序的顺序执行过程。 程序顺序执行时有如下特征。 1）顺序性：处理机的操作严格按照程序所规定的顺序执行，即每一个操作必须在下一个操作开始之前结束。 2）封闭性：程序一旦开始运行，其执行结果不受外界因素影响，因为程序在运行时独占系统的各种资源，故这些资源的状态(除初始状态外)只有本程序才能改变。 3）可再现性：只要程序执行时的初始条件和执行环境相同，当程序重复执行时，都将获得相同的结果。 （3）程序的并发执行 程序的并发执行是指若干个程序(或程序段)同时在系统中运行，这些程序(或程序段)的执行在时间上是重叠的，即一个程序(或程序段)的执行尚未结束，另一个程序(或程序段)的执行已经开始。 程序并发执行时有如下特征。 1）间断性：“走走停停”，一个程序可能走到中途停下来，失去原有的时序关系； 2）失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。 3）不可再现性：由于失去封闭性，外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。 （4）进程的定义与特征 1）进程的定义 进程是具有独立功能的可并发执行的程序在一个数据集合上的运行过程，是系统进行资源分配和调度的独立单位。或者说，“进程”是进程实体的运行过程。 2）进程的特征 ①动态性。进程是程序的一次执行过程，因此，动态性是进程最基本的特性。动态性还表现为：“它由创建而产生，由调度而执行，由得不到资源而暂停执行，以及由撤销而消亡。 ②并发性。这是指多个进程实体同存于内存中，能在—段时间内同时运行。并发性是进程的重要特征。 ③独立性。这是指进程实体是—个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。 ④异步性。这是指进程按各自独立的、不可预知的速度向前推进。 ⑤结构特征。从结构上看，进程实体是由程序段、数据段及进程控制块三部分组成，有人把这三部分统称为“进程映像”。 2．进程的状态与转换 （1）进程有三种基本状态： 1）就绪状态。当进程已分配到除CPU以外的所有必要资源，只要获得CPU，便可立即执行。 2）执行状态。进程已获得CPU，正在执行，单处理机系统中，只有一个进程处于执行状态。 3）阻塞状态。进程不具备运行的条件，如申请的资源（除CPU外）未满足，等待某个事件等。 （2）进程状态的转换 进程在运行期间不断地从一个状态转换到另一个状态，进程的各种调度状态依据一定的条件而发生变化，它可以多次处于就绪状态和执行状态，也可多次处于阻塞状态，但可能排在不同的阻塞队列。 进程的三种基本状态及其转换如图2.1所示。 （3）进程控制块 为了管理和控制进程的运行，操作系统为每个进程定义了—个数据结构——进程控制块(PCB)，用于记录进程的属性信息。系统根据PCB感知进程的存在，PCB是进程存在的惟一标志。当创建一个进程时，系统为该进程建立一个PCB；当进程执行时，系统通过PCB了解进程的现行状态信息；当进程结束时，系统收回其PCB，该进程随之消亡。 一般来说，不同操作系统中的PCB所包含的内存多少会有些差异，但通常包括下面所列出的内容： l）进程标识符：每个进程都有惟一的进程标识符，以区别于系统内部的其他进程。在进程创建时，由系统为进程分配惟—的进程标识号。 2）进程当前状态：说明进程的当前状态，以作为进程调度程序分配处理机的依据。 3）进程队列指针：用于记录PCB链表中下一个PCB的地址。为了查找方便，系统中的PCB可能组织成多个链表，如就绪队列、阻塞队列等。 4）程序开始地址：进程执行的开始地址。 5）进程优先级：反映进程要求CPU的紧迫程度。优先级高的进程可优先获得处理机。 6）CPU现场保护区：当进程因某种原因释放处理机时，CPU现场信息被保存在PCB的该区域中，以便在进程重新获得处理机后能继续执行。 7）通信信息：记录进程在执行过程中与别的进程所发生的信息交换情况。 8）家族联系：有的系统允许进程创建子进程，从而形成一个进程家族树。在PCB中必须指明本进程与家族的关系，如它的子进程与父进程的标识。 9）占有资源清单：列出进程所需资源及当前已分配资源清单。 3．进程控制 进程控制的职责是对系统中的所有进程实施有效的管理，其功能包括进程的创建、进程的撤消、进程的阻塞与唤醒、进程的挂起与激活等。进程控制一般是由OS的内核来实现，OS提供一组原语来实现。 所谓原语是一种特殊的系统功能调用，原语是由若干条机器指令构成的，它可以完成一个特定的功能，其特点是原语执行时不可被中断，所以原语操作具有原子性。 （1）进程创建 进程创建是由创建原语实现的，当需要时，进程就可以建立一个新进程。被创建的进程称为子进程，建立进程的进程称为父进程，而子进程又可以根据需要创建自己的子进程，从而构成了进程图。 引起创建进程的典型事件有分时系统中的用户登录、批处理系统中的作业调度、系统提供服务、应用进程本身的应用请求等。 一旦操作系统发现了要求创建新进程的事件后，便调用进程创建原语creat()，按下述步骤创建一新进程。 ①申请空白PCB； ②为新进程分配资源； ③初始化进程控制块； ④将新进程插入就绪队列。 （2）进程的终止 当进程完成任务或者遇到异常情况和外界干预需要结束时，应通过调用进程终止原语来终止进程。终止进程的实质是回收PCB。具体回收过程是： ①根据被终止进程的标识符从PCB集合中检索出该进程的PCB，从中读出该进程的状态。 ②若被终止进程正处于执行状态，应立即终止该进程的执行并设置调度标志为真，用于指示该进程被终止后应重新进行调度，选择一新进程，把处理机分配给它。 ③若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防它们成为不可控的。 ④将该进程所拥有的全部资源，或者归还其父进程或者归还给系统。 ⑤将被终止进程的PCB从所在队列中移出，等待其他程序来搜集信息。 （3）进程阻塞与唤醒 当—个进程期待的某一事件尚未出现时，该进样调用阻塞原语block()将自己阻塞起来。阻塞原语的主要操作过程如下：在阻塞一个进程时，由于该进程正处于执行状态，故应中断处理机，保存该进程的CPU现场，停止运行该进程，然后将该进程插入到等待该事件的等待队列中，再从就绪队列中选择一个新的进程投入运行。 对处于阻塞状态的进程，当该进程期待的事件出现时，由发现者进程调用唤醒原语wakeup()将阻塞的进程唤醒，使其进入就绪状态。唤醒原语的主要操作如下：将被唤醒进程从相应的等待队列中移出，将状态改为就绪并插入相应的就绪队列。 （4）进程的挂起与激活 当出现引起进程挂起的事件时，系统利用挂起原语suspend()将指定进程或处于阻塞的进程挂起。挂起原语的执行：检查被挂起进程的状态，若处于活动就绪，则改为静止就绪，若处于活动阻塞，则改为静止阻塞，将该进程PCB复制到内存指定区域，若挂起的进程正在执行，则重新进行进程调度。 当发生激活进程的事件时，系统利用激活原语active()将指定进程激活。激活原语先将进程从外存调入内存，检查该进程的状态，若处于静止就绪，则改为活动就绪，若处于静止阻塞，则改为活动阻塞。若采用抢占调度策略，则新进程进入就绪队列时，检查是否要重新进行进程调度。 4．进程组织 在—个系统中，通常存在着许多进程，它们有的处于就绪状态，有的处于阻塞状态，而且阻塞的原因各不相同，为了调度和管理进程方便起见，需要将各进程的进程控制块用适当的方法组织起来。目前常用的组织方式有链接方式和索引方式两种。 （1）链接方式：链接方式是将具有同一状态的PCB，用其中的链接字链接成一个队列，多个状态对应多个不同的链表，如就绪链表、阻塞链表和空白链表等。对其中的就绪队列常按进程优先级的高低排列，把优先级高的进程的PCB排在队列前面。此外，可根据阻塞原因的不同而把处于阻塞状态的进程的PCB，排成等待I/O操作完成的队列和等待分配内存的队列等。如图2.2所示。 （2）索引方式：索引方式是系统根据所有进程的状态建立几张索引表，将同一状态的进程归入一个索引表，并把各索引表在内存的首地址记录在内存的一些专用单元中，再由索引指向相应的进程控制块，多个状态对应多个不同的索引表，如就绪索引表和阻塞索引表等。如图2.3所示。 5．进程通信 进程通信是指进程之间的信息交换。进程互斥与同步就是一种进程间的通信方式。由于进程互斥与同步交换的信息量较少且效率较低，因此称这两种进程通信方式为低级进程通信方式，相应地也将wait、signal原语（P、V原语）称为两条低级进程通信原语。 下面介绍的进程通信为高级进程通信方式。所谓高级进程通信方式是指进程之间以较高的效率传送大量数据。 （1）进程通信的类型 目前，高级进程通信方式可分为3大类：共享存储器系统、消息传递系统以及管道通信系统。 1）共享存储器系统 为了传输大量数据，在存储器中划出一块共享存储区，诸进程可通过对共享存储区进行读或写来实现通信。进程在通信前，应向系统申请建立一个共享存储区，并指定该共享存储区的关键字；若该共享存储区已经建立，则将该共享存储区的描述符返回给申请者。然后，申请者把获得的共享存储区附接到本进程的地址空间上；这样，进程便可以像读、写普通存储器一样读、写共享存储区。 2）消息传递系统 在消息传递系统中，进程间的数据交换以消息为单位，程序员直接利用系统提供的一组通信命令(原语)来实现通信。操作系统隐藏了通信的实现细节，大大简化了通信程序编制的复杂性，因而获得了广泛的应用。消息传递系统因其实现方式不同可分为以下几种。 ①直接通信方式：发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息。 ②间接通信方式：发送进程把消息发送到某个中间实体中，接收进程从中取得消息。这种中间实体一般称为信箱，故这种通信方式也称为信箱通信方式。这种通信方式被广泛应用于计算机网络中，现在称为电子邮件系统。 3）管道通信 管道是用于连接读进程和写进程以实现它们之间通信的共享文件，向管道提供输入的发送进程（即写进程）以字符流形式将大量的数据送入管道，而接收管道输出的接收进程(即读进程)可以从管道中接收数据。 （2）消息缓冲通信 消息缓冲通信是一种直接通传方式，即发送进程直接发送一个消息给接收进程。所谓消息是指一组信息，通常由消息头和消息正文组成。在通信时，发送进程采用发送原语向接收进程发送一个消息，而接收进程则采用接收原语接收来自发送进程的一个消息。发送原语的主要工作是申请分配一个消息缓冲区，然后将消息正文传送到该缓冲区中，并向缓冲区中填写消息头，再将该消息缓冲区挂到接收进程的消息链上。接收原语的主要工作是把消息链上的消息逐个读入到接收进程的接收区中并进行处理。 （3）信箱通信 信箱通信是一种间接通信方式。信箱是一种数据结构，其中存放信件。当一个进程(发送进程)要与另—个进程(接收进程)通信时，可由发送进程创建—个链接两进程的信箱，通信时发送进程只须把它的信件投入信箱，接收进程就可以在任何时候取走信件而不会丢失。 信箱逻辑上分成信箱头和信箱体两部分。信箱头中存放有关信箱的描述。信箱体由若干格子组成，每格存放一信件，格子的数目和大小在创建信箱时确定。信件的传递可以是单向的，也可以是双向的。 在单向信箱通信方式中，只要信箱中有空格，发送进程便可向信箱中投递信件，若所有格子都已装满，则发送进程或者等待，或者继续执行，待有空格子时再发送。类似地，只要格子中装有信件，接收进程便能取出一信件。若信箱为空，接收进程或者等待，或者继续执行。 在双向通信方式中，信箱中既有发送进程发出的信件，也有接收进程的回答信件。由于发送进程和接收进程均以各自独立的速度向前推进，当发送进程发送信件的速度超过接收进程的接收速度时，会产生上溢(信箱满)。反之，会产生下溢，即接收进程向空信箱索取信件。这就需要在两个进程之间进行同步控制，当信箱满时发送进程应等待，直至信箱有空格子时再发送；对接收进程，当信箱空时，它也应等待，直至信箱中有信件时再接收。 信箱通信方式中也使用原语操作，如创建信箱原语、撤消信箱原语、发送与接收原语等。另外，在许多时候，存在着多个发送进程和多个接收进程共享信箱的情况。 6．线程概念与多线程模型 (1)线程的基本概念 自从20世纪60年代提出进程的概念后，在操作系统中一直都是以进程作为独立运行的基本单位，在操作系统中引入进程的目的是为了使多个程序并发执行，以改善资源利用率及提高系统吞吐量；到80年代中期，人们提出了比进程更小的独立运行的基本单位——线程，在操作系统中引入线程，是为了减少程序并发执行时所付出的时空开销，进一步提高系统内程序并发执行的程度，提高系统吞吐量，使操作系统具有更好的并发性。 线程的定义有以下几种提法，这些提法可以相互补充。 （1）线程是进程内的一个执行单元。 （2）线程是进程内的一个可调度实体。 （3）线程是程序(或进程)中相对独立的—个控制流序列。 （4）线程是执行的上下文，其含义是执行的现场数据和其他调度所需的信息。 （5）线程是进程内一个相对独立的、可调度的执行单元。 线程是进程的一个实体，是被系统独立调度和分派的基本单位，线程自己基本上不拥有资源，只拥有—点在运行时必不可少的资源(如程序计数器、一组寄存器和栈)，但它可以与同属一个进程的其他线程共享进程拥有的全部资源。一个线程可以创建和撤销另一个线程；同一个进程中的多个线程之间可以并发执行。 (2)线程的实现机制 对于通常的进程，不论是系统进程还是用户进程，在进行切换时都要依赖于内核中进程的调度。因此，我们说，不论什么进程都是与内核有关的，是在内核支持下进行切换的，对于线程来说，则可分为两类：一类是内核支持线程，它们是依赖于内核的。即无论是在用户进程中的线程，还是系统进程中的线程，它们的创建、撤销和切换都由内核实现。在内核中保留了一张线程控制块，内核根据该控制块而感知该线程的存在并对线程进行控制。另一类是用户级线程。它仅存在于用户级中，对于这种线程的创建、撤销和切换，都不利用系统调用来实现，由应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制。因而这种线程与内核无关。相应地，内核也并不知道有用户级线程的存在。 这两种线程各有优缺点，因此，如果将两种方法结合起来，则可得到两者的全部优点，将两种方法结合起来的系统称之为多线程的操作系统。内核支持多线程的建立、调度与管理。同时，系统中又提供使用线程库的便利，允许用户应用程序建立、调度和管理用户级的线程。 （二）处理机调度 1．调度的基本概念 在多道程序环境下，进程数目往往多于处理机数目，这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，分配处理机的任务是由处理机调度程序完成的。一个作业从提交开始直至完成，往往经历下述三级调度： (1)高级调度 高级调度又称宏观调度、作业调度或长程调度，其主要任务是按一定的原则从外存上处于后备状态的作业中选择一个或多个作业，给它们分配内存、输入输出设备等必要的资源，并建立相应的进程，再将新创建的进程排在就绪队列上，准备执行。高级调度的运行频率较低，通常为几分钟—次。 （2）低级调度 低级调度又称进程调度、短程调度或微观调度，其主要任务是按照某种策略和方法从就绪队列中选取一个进程，将处理机分配给它。进程调度的运行频率很高，一般几十毫秒要运行一次。 （3）中级调度 中级调度又称中程调度或交换调度，引入中级调度的目的是为了提高内存利用率和系统吞吐量。其主要任务是按照给定的原则和策略，将处于外存对换区中的重又具备运行条件的进程调入内存，或将处于内存的暂时不能运行的进程交换到外存对换区。 2．调度时机、切换与过程 （1）引起进程调度的因素主要有： ①正在执行的进程执行完毕，或因发生某事件而不能再继续执行； ②执行中的进程因提出I/O请求而暂停执行； ③在进程通信或同步过程中执行了某种原语操作，如wait原语、block原语、wakeup原语等； ④当进程执行完系统调用功能从核心态返回用户态时，发现调度标志已设置，即系统中某进程的优先级已高于当前执行进程的优先级，系统会调用优先级高的进程执行。 ⑤各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。 （2）进程切换过程 从进程A切换到进程B的过程为：当系统正在用户态执行进程A的代码，若此时发生进程切换，首先通过时钟中断或系统调用进入OS核心，然后保存进程A的上下文，再恢复进程B的上下文（CPU寄存器和一些表格的当前指针），最后转到用户态执行进程B的代码。 3．调度的基本准则 选择调度方式和算法的准则，有的是面向用户的，有的是面向系统的。 (1)面向用户的准则 ①周转时间短。通常把周转时间的长短作为评价批处理系统的性能。周转时间是指从作业被提交给系统开始，直到作业完成为止的这段时间间隔。 设Ti 是第i作业的周转时间，则平均周转时间描述为： 。作业的周转时间T与系统为它提供服务的时间Ts之比，即W=T/Ts，称为带权周转时间，平均带权周转时间表示为： 。 ②响应时间快。常把响应时间的长短作为评价分时系统的性能。所谓响应时间，是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。 ③截止时间的保证。这是评价实时系统性能的重要指标。所谓截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。 ④优先权准则。在批处理、分时和实时系统中，可遵循优先权准则，以便让某些紧急的作业能得到及时处理，在较严格的场合，还需选择抢占式调度方式。 4．调度方式 所谓进程调度方式是指当某一个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要进行处理，即有优先级更高的进程进入就绪队列，此时如何分配处理机。通常有两种进程调度方式。 （1）抢占方式。抢占方式又称剥夺方式、可剥夺方式。这种调度方式是指当一个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要或紧迫的进程。 （2）非抢占方式。非抢占方式又称非剥夺方式、不剥夺方式、不可抢占力式。这种调度方式是指当一个进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或发生某种事件而进入阻塞状态时，才把处理机分配给更为重要或紧迫的进程。 5．典型调度算法 调度算法是指根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标，通常采用不同的调度算法。典型的调度算法有以下几种： （1）先来先服务调度算法 先来先服务（FCFS）调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度，在作业调度中，每次调度都从后备作业中，选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创建进程；用于进程调度时，是按照进程进入就绪队列的先后次序来分配处理机。先来先服务算法采用非剥夺的调度方式，即一旦—个进程占有处理机，它就一直运行下去，直到该进程完成其工作或因等待某一事件而不能继续执行时才释放处理机。 （2）短作业（进程）优先调度算法 可以分别用于作业调度和进程调度，短作业优先（SJF）调度算法，是从后备对列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先（SPF）调度算法，是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它。 （3）时间片轮转调度算法 在时间片轮转调度算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择队列中的第一个进程执行，并规定执行一定时间，该时间称为时间片。当该进程用完这一时间片时，系统将它送至就绪队列队尾，再把处理机分配给下一个就绪进程。这样，处于就绪队列中的进程，就可以依次轮流地获得一个时间片的处理时间，然后回到队列尾部，如此不断循环，直至完成为止。 （4）优先级调度算法 优先级调度算法是一种常用的进程调度算法，其基本思想是把处理机分配给优先级最高的进程，该算法的核心问题是如何确定进程的优先级。 进程的优先级用于表示进程的重要性及运行的优先性。进程优先级通常分为两种：静态优先级和动态优先级。 静态优先级是在创建进程时确定的，确定之后在整个进程运行期间不再改变。 动态优先级是指在创建进程时，根据进程的特点及相关情况确定—个优先级，在进程运行过程中再根据情况的变化调整优先级。 基于优先级的调度算法还可按调度方式不同分为非剥夺优先级调度算法和可剥夺优先级调度算法。 非剥夺优先级调度算法的实现思想是系统一旦将处理机分配给就绪队列中优先级最高的进程后，该进程便一直运行下去，直到由于其自身的原因(任务完成或等待事件)主动让出处理机时，才将处理机分配给另一个更高优先级的进程。 可剥夺优先级调度算法的实现思想是将处理机分配给优先级最高的进程，使之运行。在进程运行过程中，一旦出现了另一个优先级更高的进程时，进程调度程序就停止原运行进程，而将处理机分配给新出现的高优先级进程。 （5）高响应比优先调度算法 此算法是先来先服务算法和短作业优先算法的折衷，为每个作业引入一个动态优先权（响应比），使作业的优先级随着等待时间的增加而提高，响应比的计算公式为： 响应比=（等待时间+要求服务时间）/要求服务时间 （4）多级反馈队列调度算法 多级反馈队列调度算法可以满足各种类型进程的需要，是目前公认的一种较好的调度算法，实现思想如下： 第一，设置多个就绪队列，并为每个队列赋予不同的优先级。第1个队列优先级最高，第2个队列次之，其余队列的优先级逐个降低。每个队列中进程执行的时间片大小也各不相同，进程所在队列的优先级越高，其相应的时间片就越短。通常，第i+1个队列的时间片是第i个队列时间片的两倍。 第二，当一个新进程进入系统时，首先将它放入第一个队列的末尾，按先来先服务的原则排队等待调度。当轮到该进程执行时，如能在此时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二个队列末尾，再同样地按照先来先服务原则等待调度执行；如果它在第二个队列个运行一个时间片后仍未完成，再以同样方法转入第3个队列。如此下去，最后一个队列中使用时间片轮转调度算法。 第三，仅当第一个队列空闲时，调度程序才调度第二个队列中的进程运行；仅当第1至(i-1)个队列均为空时，才会调度第i个队列中的进程运行。当处理机正在为第i个队列中的某进程服务时，若又有新进程进入优先级较高的队列中，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在执行的进程放回第i个队列末尾，重新将处理机分配给新进程。 (三)进程同步 1．进程同步的基本概念 进程同步的主要任务：使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。 （1）进程间的两种制约关系 ①间接相互制约关系。源于资源共享，同处于一个系统中的进程，必然共享某种系统资源，如共享CPU、共享I/O设备等，如两个进程A和B，若系统已将惟一的打印机分配给B，此时如果A进程提出打印请求时，则进程A只能阻塞；一旦B将打印机释放，才能使A进程由阻塞改为就绪状态。此时进程同步的主要任务是保证诸进程能互斥地访问临界资源，为此，系统中的资源应不允许用户进程直接使用，而应有系统统一分配。 ②直接相互制约关系。源于进程合作，此时进程同步的主要任务是保证相互合作的诸进程在执行次序上的协调，不会出现与时间有关的差错。 （2）临界资源和临界区 在计算机中有许多资源一次只能允许一个进程使用，我们把一次仅允许一个进程使用的资源称为临界资源。如打印机和一些共享变量。 进程中访问临界资源的那段代码称为临界区。 （3）同步机制应遵循的准则 ①空闲让进。当没有进程处于临界区时，可以允许一个请求进入临界区的进程立即进入自己的临界区。 ②忙则等待。当已有进程进入自己的临界区时，意味着相应的临界资源正被访问，因而所有其他试图进入临界区的进程必须等待，以保证诸进程互斥地访问临界资源。 ③有限等待。对要求访问临界资源的进程，应保证该进程能在有效时间内进入自己的临界区，以免陷入“死等”状态。 ④让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。 2．实现临界区互斥的基本方法 临界区互斥的实现既可以用软件的方法，也可以用硬件的方法。下面对这两种方法进行介绍。 （1）软件方法 用软件方法解决互斥和同步问题较复杂，为了说明将介绍的正确算法中某些变量设置的必要性，首先给出两个不正确算法。 1）不正确算法1 两个进程(P0，P1)共享一个公用变量turn，turn=i时进程Pi可进入临界区。进程Pi的结构如下：（turn初值为0或1无关紧要。i和j分别为0或1，i＝1—j。) repeat while turn＜＞i do skip; 临界区； turn：=j; 其他代码； until false; 该算法满足互斥性要求，但它要求执行临界区的进程必须严格地交替进行，若turn=0且P1希望进入临界区，尽管P0已用完并退出临界区，该算法也不能让P1进入其临界区运行。 2）不正确算法2 不正确算法1的问题在于，它只记住了哪个进程允许进入它的临界区，但没有记录每个进程的状态。为了避免这种情况，可以用下面的数组来代替变量turn: var flag: array[0..1] of boolean; 该数组的每个元素的初值均为false。若且flag[i]为turn，则表示进程Pi正在其临界区执行。进程Pi的一般结构为： repeat while flag[j] do skip； flag[i]:＝true； 临界区； flag[i]:＝false； 剩余区； untll false; 这里，首先查看是否有另一进程在其临界区中，若有则等待；否则置本进程的flag为true，并进入临界区。当离开临界区时，又置其flag为false，以允许另一进程进入其临界区。然而该算法并未保证一次只有一个进程在其临界区内执行。例如考虑以下执行序列： T0：P0进入while语句并发现flag[1]＝false； T1：P1进入while语句并发现flag[0]＝false； T2：P1置flag[1]为true并进入临界区； T3：P0置flag[0]为true并进入临界区进入。 于是，P0与P1都进入了临界区，从而违反了互斥的要求。 3）正确算法（只针对双进程) 该算法将上述两种不正确算法中的有利思想结合在一起。进程间共享两个共用变量： var flag：array[0..1] of boolean；turn：0..1； 最初flag[0]＝flag[1]＝false，turn的初值是无关紧要的。进程Pi的一般结构为： repeat flag[i]:=true;turn:=j;； while(flag[j] and turn=j) do skip; 临界区； flag[i]:= false; 剩余区； until false； (2)硬件方法解决互斥问题： 1）中断屏蔽方法 当一个进程正在使用处理器执行它的临界区代码时，要防止其他进程再进入其临界区访问的最简单方法是禁止一切中断发生，或称之为屏蔽中断、关中断。因为CPU只在发生中断时引起进程切换，屏蔽中断就能保证当前运行进程将临界区代码顺利地执行完，从而保证了互斥的正确实现，然后再开中断。下面是用中断屏蔽方法实现互斥的典型模式： … 关中断； 临界区； 开中断； … 并关中断方法来实现过程间互斥，既简单又有效。但它存在一些不足，如该法限制了处理器交替执行程序的能力，其执行的效率将会明显降低；对于核心来说，当它在执行更新变量或列表的几条指令期间将中断关掉是很方便的，但将关中断的权力交给用户进程则很不明智，若—个进程关中断之后不再开中断，则系统可能会因此终止。 2）硬件指令方法 许多计算机中都提供了专门的硬件指令，完成对一个字或字节中的内容进行检查和修改，或交换两个字或字节的内容的功能。用一条指令来完成对共享变量的检查和修改两个功能，这样中断不可能发生，所以不会影响共享变量数据的完整性。 实现这种功能的硬件指令有两种： ①TS(Test-and-set)指令。该指令的功能是读出指定标志后把该标志设置为真。 boolean TS(boolean *lock) { boolean old； old=*lock； *lock=true； return old; } 为了实现多个进程对临界资源的互斥访问，可以为每个临界资源设置一个共享的布尔变量lock，表示资源的两种状态：true表示正被占用，false表示空闲，初值为false。在进程访问临界资源之前，利用TS检查和修改标志lock；若有进程在临界区，则重复检查，直到其他进程退出。利用TS指令实现进程互斥的算法可描述为： While TS(＆lock)； 进程的临界区代码CS； Lock=false； 进程的其他代码； ②swap指令。该指令的功能是交换两个字或字节的内容，描述如下： Swap(boolean *a，boolean *b) { Boolean temp； temp＝*a； a=*b； *b=temp； } 利用swap指令实现进程互斥时，应为每个临界资源设置一个共享布尔变量lock，初值为false；在每个进程中再设置一个局部布尔变量key，用于与lock交换传息。在进入临界区之前利用swap指令交换lock与key的内容，然后检查key的状态；若有进程在临界区时，重复交换和检查过程，直到其他进程退出。利用swap指令实现进程互斥的算法描述为： key＝true； while (key!＝false) swap(＆lock，&key)； 进程的临界区代码CS； lock＝false； 进程的其他代码； 3．信号量 荷兰学者Dijkstral965年提出的信号量机制是一种卓有成效的进程同步工具。在长期且广泛的应用中，信号量机制又得到了很大的发展，它从整型信号量经记录型信号量，进而发展为“信号量集”机制。 （1）整型信号量机制 整型信号是—个整型量，除初始化外，仅能通过两个标准的原子操作wait(s)和signal(s)来访问。这两个操作很长时间以来一直被分别称为P、V操作。Wait和signal操作可描述为： Wait(s)：while (s≤0) no-op; s--; signal(s)： s++； 整型信号量的主要问题是，只要s≤0，wait操作就会不断地测试，因而没有做到“让权等待”。 （2）记录型信号量机制 在记录型信号量中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L．用于链接上述的所有等待进程。 typedef struct { int value； 1ist of proces s *L； }semaphore； 相应的wait和signal操作可描述为： void wait(static semaphore s) { s.value--； if (s.value＜0) block(s.L)； } void signal(static semaphore s) { s.value++； if (s.value＜=0) wakeup(s.L)； } 在记录型信号量机制中，s.value的初值表示系统中某类资源的数目，因而又称为资源信号量，每次的wait操作意味着进程请求一个单位的资源，因此描述为s.value--；当s.value＜0时，表示资源己分配完毕，因而进程调用block原语，进行自我阻塞，放弃处理机并插入到信号量链表s.L上。可见，该机制遵循了让权等待准则。此时s.value的绝对值表示在该信号量链表中已阻塞进程的数目。每次signal操作，表示执行进程释放一个单位资源．故s.value++操作表示资源数目加1。若加l后仍是s.value＜=0，则表示在该信号链表中仍有等待该资源的进程被阻塞，故还应调用wakeup唤醒进程。如果s.value的初值等于l，则此时的信号量转化为互斥信号量。 (3)信号量的应用 1）利用信号量实现互斥 为使多个进程能互斥地访问某个临界资源，只需为该资源设置—个互斥信号量mutex，并将其初值设置为1，然后将访问该资源的临界区置于wait(mutex)和signal(mutex)之间。下面的算法描述了如何利用信号量实现进程P1和P2的互斥，信号量mutex的初值为1。 P1进程 P2进程 … … wait(mutex)； wait(mutex)； critical section； critical section； signal(mutex)； signal(mutex)； … … 2）利用信号量实现前趋关系 若干进程为了完成一个共同任务而并发执行。然而，这些并发进程之间根据逻辑上的需要，有的操作可以没有时间上的先后次序，但有的操作有一定的先后次序。我们可以用前面介绍的前趋图来描述进程在执行次序上的先后关系。 例如：S1、S2、S3、S4为一组合作进程，其前驱图如图2.4所示，试用wait、signal操作完成这4个进程的同步。 图2.4说明任务启动后S1先执行，当S1结束后，S2、S3可以开始执行。S2、S3完成后，S4才能开始执行。为了确保这一执行顺序，设四个同步信号量f1、f2、f3、f4，其初值均为0，这四个进程的同步描述如下： semaphore f1=0 /*表示进程S2是否可以开始执行*/ semaphore f2=0 /*表示进程S3是否可以开始执行*/ semaphore f3=0 /*表示进程S4是否可以开始执行*/ semaphore f4=0 /*表示进程S4是否可以开始执行*/ main() { cobegin S1(); S2(); S3(); S4(); coend } S1() { /*“ ”表示进程中的程序代码，下同*/ Signal(f1); Signal(f2); } S2() { Wait(f1); Signal(f3); } S3() { Wait(f2); Signal(f4); } S4() { Wait(f3); Wait(f4); } 4．管程 虽然信号量机制是一种既方便又有效的进程同步机制，但每个要访问临界资源的进程都必须自备同步操作wait(s)和signal(s)。这就使大量的同步操作分散在各个进程中。这不仅给系统的管理带来麻烦，而且还会因同步操作的使用不当而导致系统死锁。这样，在解决上述问题的过程中，便产生了一种新的同步工具——管程。 (1)管程的基本概念 一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的—组操作，这组操作能同步进程和改变管程中的数据。由定义可知，管程由三部分组成：①局部于管程的共享变量说明；②对该数据结构进行操作的一组过程；③对局部于管程的数据设置初值的语句。此外，过需为该管程赋予一个名字。 管程具有以下特点： 1）局部于管程的数据结构，仅能被局部于管程的过程所访问。 2）一个进程只有通过调用管程内的过程才能进入管程访问共享数据。 3）任一时刻，最多只能有一个进程在管程中执行。即进程互斥地通过调用内部过程进入管程，当某进程在管程内执行时，其他想进入管程的进程必须等待。 (2)条件变量 在利用管程实现进程同步时，必须设置两个同步操作原语wait和signal。当某进程通过管程请求临界资源而未能满足时，管程便调用wait原语使该进程等待，并将它排在等待队列上。仅当另一进程访问完并释放之后，管程又调用signal原语唤醒等待队列中的队首进程。 通常，等待的原因可有多个，为了区别它们，引入了条件变量condition。管程中对每个条件变量都需予以说明，其形式为：condition x，y；。该变量应置于wait和盛signal之前，即可表示为x. wait和x. signal。 x. signal操作的作用是重新启动一个被阻塞的进程，如果没有进程被阻塞，则x.signal操作不产生任何后果，这与信号量机制中的signal操作不同。 (3)利用管程解决生产者。消费者问题 利用管程方式来解决生产者—消费者问题时，首先为它们建立一个管程，命名为Producer-Consumer，描述如下： monitor producer—consume { int in, out, count； item buffer[n]； condition notfull, notempty； entry put(item) { if (count>=n) notfull.wait; buffer(in)=nextp; in=(in+1) mod n; count++; if notempty.queue notempty.signal; } entry get(item) { if (count<=0) notempty.wait; nextc=buffer(out); out:=(out+1) mod n; count--; If notfull.queue notfull.signal; } {in=out=0; count=0; } } 利用管程解决生产者—消费者问题时，生产者—消费者可描述如下： producer() { while(1) { producer an item in nextp; producer—consume.put(item); } } Consumer() { while(1) { producer—consume.get(item); Cinsumer the item in nextc; } } Main() { cobegin{ producer(); consumer(); } } 5．经典进程的同步问题 (1)生产者—消费者问题 生产者一消费者问题常发生在一组协同操作进程中，该问题是许多并行进程间存在的内在关系的一种抽象。通常可描述如下：有一个或多个生产者产生某种类型的产品(数据、记录、字符等)并放置在缓冲区中，生产者消费者共享一个有界缓冲池；有一个或多个消费者从缓冲中取产品，每次取一项，系统保证对缓冲区的重复操作，也就是说，在任何时候只有一个代理(生产者或消费者)可以访问缓冲区。 生产者和消费者的同步关系表现为：一旦缓冲池满时，生产者必须等待消费者提供空缓冲区单元，一旦缓冲池中所有单元全为空时，消费者必须等待生产者向缓冲区单元中放入产品。 对于所有的代理来说，缓冲区又是临界资源：任何一个进程在对某个缓冲区单元进行“存”或“取”操作时和其他进程互斥进行。 为解决生产者一消费者这一类问题，应该设置两个同步信号量，一个说明空缓冲单元的数目，用empty表示，其初值为有界缓冲区的大小n；另一个说明满缓冲单元的数目(即产品数目)，用full表示，其初值为0。因为有界缓冲区是一个临界资源，必须互斥使用，所以，需要设置一个互斥信号量mutex，其初值为l。生产者一消费者问题的同步描述如下： semaphore full=0； ／*满缓冲单元的数目*／ semaphore empty=n； ／*空缓冲单元的数目*／ semaphore mutex＝1；／*对有界缓冲区进行操作的互斥信号量*/ item buffer[n] int in=out=0 main() { Cobegin Producer(); Consumer(); Coend } Producer(0 { While(true) { Produce an item in nextp; … Wait(empty); Wait(mutex); Buffer[in]=nextp; In=(in+1) mod n; Signal(mutex); Signal(full); } } Consumer() { While(true) { wait(full); wait(mutex); nextc:=buffer(out); out:=(out+1) mod n; signal(mutex); signal(empty); … consume the item in nexc; } } 程序中有一点需要读者注意，无论在生产者进程还是在消费者进程中，wait操作的次序都不能颠倒，否则将可能造成死锁。 （2）读者—写者问题 一个数据文件或记录(统称数据对象)，可被多个进程共享。其中，有些进程要求读，而另一些进程对数据对象进行写或修改。我们把只要求读的进程称为“reader进程”，其他进程称为“writer进程”。允许多个reader进程同时读一个共享对象，但决不允许—个writer进程和其他reader进程或writer进程同时访问共享对象。所谓读者—写者问题是只保证一个writer进程必须与其他进程互斥地访问共享对象的同步问题。 为实现肥reader进程与writer进程读或写时的互斥，设置了一个互斥信号量wmutex。再设置一个整型变量readcount以表示正在读的进程数目。由于只要有一个read进程在读，便不允许writer进程去写，因此，仅当readcount==0时，表示尚无reader进程在读时，reader进程才需要执行wait(wmutex)操作。若wait(wmutex)操作成功，reader进程便可去读，相应地readcount++。同理，仅当reader进程在执行了readcount--操作后其值为0时，才需执行signal(wmutex)操作，以便让writer进程写。又因为readcount是一个可被多个reader进程访问的临界资源，因此，应为它设置—互斥信号量rmutex。读者—写者问题可描述如下： semaphore rmutex =1; semaphore wmutex =1; int readcount=0; reader( ) { While(1) { wait(rmutex); if (readcount= =0) wait(wmutex); readcount++; signal(rmutex); … … perform read operation; … … wait(rmutex); readcount--; if (readcount= =0) signal(wmutex); signal(rmutex); } } writer() { while(1) { wait(wmutex); perform write operation; signal(wmutex); } } main() { cobegin { reader(); writer(); } coend } （3）哲学家进餐问题 哲学家进餐问题是典型的同步问题，该问题描述有五个哲学家围坐在一圆桌旁，圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有拿到两只筷子时才能进餐，进餐完毕，放下筷子继续思考。 经分析，桌子上的筷子是临界资源，为实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组，描述如下： Semaphore chopstick[4]； 信号量初值为1，第i位哲学家的活动描述为： While(1) { wait(chopstick[i])； wait(chopstick[(i+1) mod 5])； … eat； … signal(chopstick[i])； signal(chopstick[(i+1) mod 5])； … think； } 上述描述中，哲学家饥饿时，总是先拿他左边的筷子，成功后，再去拿他右边的筷子，成功后进餐，进餐毕，放下他左右两边的筷子，虽然上述方法可保证不会有相邻哲学家同时进餐，但有可能引起死锁，假若五位哲学家同时饥饿而各自拿起左边的筷子时，使五个信号量chopstick均为0；当他们再试图去拿右边的筷子时，都将因五筷子可拿而无限等待。可用下述方法解决： 1）至多允许四个哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐。 2）奇数号哲学家先拿他左边的筷子，再去拿右边的筷子；偶数号哲学家先取他右边的筷子，再取他左边的筷子。 3）仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐，否则，一只筷子也不分给他。 下面给出第2种方法的描述： Semaphore chopstick[4]； 信号量初值为1，第i位哲学家的活动描述为： While(1) { if (odd(i)) {wait(chopstick[i])； wait(chopstick[(i+1) mod 5])；} else { wait(chopstick[(i+1) mod 5])； wait(chopstick[i])； } … eat; … signal(chopstick[i])； signal(chopstick[(i+1) mod 5])； … think； } （四）死锁 1．死锁的概念 （1）死锁的定义：死锁是指多个进程因竞争系统资源或相互通信而处于永久阻塞状态，若无外力作用，这些进程都将无法向前推进。 （2）死锁产生的原因和必要条件 死锁产止的原因是竞争资源和进程的推进顺序不当。如果系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足诸进程的需要时，从而可能导致死锁的产生。虽然资源竞争可能导致死锁，但是资源竞争并不等于死锁，只有在进程运行过程中请求和释放资源的顺序不当时，才会导致死锁。 死锁产生的必要条件有以下4条： （1）互斥条件：进程对所分配的资源进行排它性控制使用，即在一段时间内某资源只由一个进程占用。 （2）请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，在等待分配新资源的同时，进程继续占有已分配到的资源。 （3）不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能在使用完时由进程自己来释放。 （4）环路等待条件：存在—种进程——资源的环形链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求。 2．死锁处理策略 处理死锁的方法主要有以下几种： （1）预防死锁。通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。 （2）避免死锁。在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁。 （3）检测死锁 这种方法并不须事先采取任何限制性措施，允许系统在运行过程中发生死锁，但可通过系统所设置的检测机构，及时地检测出死锁的发生。 （4）解除死锁。当检测到系统中已发生死锁时，须将进程从死锁状态解脱出来。 3．死锁预防 预防死锁的方法是使四个必要条件中的第2、3、4条件之一不能成立，必要条件1是由设备的固有条件所决定的，不能改变，还应加以保证。 （1）摒弃“请求和保持”条件 采用这种方法，可使用预先资源静态分配法。资源静态分配法要求进程在运行之前—次申请它所需的全部资源，若系统有足够资源分配给该进程，便把其需要的所有资源分配给它，这样，进程在整个运行期间，便不会再提出资源要求；若有一种资源不能满足，其它空闲资源也不分配给该进程，而让该进程等待。这样可以保证系统不发生死锁。这种方法既简单又安全，但降低了资源利用率。 （2）摒弃“不剥夺”条件 为了破坏不剥夺条件，可以制定这样的策略：一个己获得了某些资源的进程，若新的资源请求不能立即得到满足，则它必须释放所有已获得的资源，以后需要资源时再重新申请。这意昧着，—个进程已获得的资源在运行过程中可被剥夺，从而破坏了个剥夺条件。该策略实现起来比较复杂且要付出很大代价，释放已获得资源可能造成前一段工作的失效，重复申请和释放资源会增加系统开销，降低系统吞吐量。 （3）摒弃“环路等待”条件 为破坏环路等待条件，可以采用有序资源分配法。有序资源分配法是将系统中的所有资源按类型赋予一个编号，要求每一个进程均严格按照编号递增的次序请求资源，同类资源一次申请完。 4．死锁避免 在预防死锁的几种方法中，总的说来都施加了较强的限制条件，从而使实现较简单，但却严重地损害了系统性能。而在避免死锁的方法中，所施加的限制条件较弱，因而有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可避免死锁的发生。 （1）安全状态与不安全状态 所谓安全状态，是指系统能按某种进程顺序如（P1，P2，…，Pn)(称序列为安全序列)来为每个进程分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利完成。若系统不存在这样一个安全序列，则称系统处于不安全状态。 虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于：如何使系统不进入不安全状态。 （2）利用银行家算法避免死锁 最有代表性的避免死锁算法，是Dijkstra的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名。为实现银行家算法，系统中必须设置若干数据结构。 ①可利用资源向量Available。它是一个具有m个元素的数组，其中的每一个元素代表—类可利用的资源数目，其初始值为系统中所配置的该类全部可用资源数目，其数值随该类资源的分配与回收而动态改变。如果Available[j]=K，表示系统中现有Rj类资源K个。 ②最大需求矩阵Max。它是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i, j]= K，表示进程i需要Rj类资源的最大数目为K。 ③分配矩阵Allocation。它是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每个进程的资源数。如果Allocation[i, j]= K，表示进程i当前己分得Rj类资源的数目为K。 ④需求矩阵Need。它是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数目，如果Need[i, j]= K，表示进程i还需要Rj类资源K个，方能完成其任务。 上述三个矩阵存在下述关系： Need[i, j]＝Max[i, j]- Allocation[i, j] 设Requesti是进程Pi的请求向量。如果Requesti [j]= K，表示进程Pi需要K个Rj类型的资源，当Pi发出资源请求后，系统按银行家算法进行检查： ①如果Requesti≤Needi，则转向步骤②；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。 ②如果Requesti≤Available，则转向步骤③；否则，表示尚无足够资源，Pi须等待。 ③系统试探着把要求的资源分配给进程Pi，并修改下面数据结构中的数值： Available=Available-Requesti ； Allocationi= Allocationi + Requesti； Needi＝Needi - Requesti； ④系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给进程Pi以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 系统所执行的安全性算法可描述如下： ①设置两个向量：工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，执行安全性算法开始时，Work= Available；Finish，它表示系统是否有足够的资源分配给进程使之运行完成，开始时先做Finish[i]=false；当有足够资源分配给进程时，Finish[i]=true。 ②从进程集合中找到一个能满足下述条件的进程： Finish[i]=false并且Needi≤Work 如找到，则执行步骤③，否则执行步骤④。 ③当进程Pi获得资源后，顺利执行，直至完成并释放出分配给它的资源，故应执行： Work = Work + Allocationi； Finish[i]=true； Go to step 2； ④如果所有过程的Finish[i]=true，则表示系统处于安全状态，否则系统处于不安全状态。 5．死锁的检测与解除 当系统为进程分配资源时，若未采取任何限制性措施来保证不进入死锁状态，则系统必须提供检测和解除死锁的手段。 （1）资源分配图 系统死锁可利用资源分配图来描述。该图由表示进程的圆圈和表示一类资源的方框组成，其中方框中的一个小圆圈代表一个该类资源，请求边是由进程Pi指向方框中的Rj，表示进程Pi请求一个单位的Rj资源，而分配边则由方框Rj指向进程Pi，表示把一个单位的Rj资源分配给进程Pi。 (2)死锁定理 我们可以利用资源分配图加以简化的方法，来检测系统处于某状态时是否为死锁状态。简化方法如下： ①在资源分配图中找出一个既不阻塞又非独立的进程结点Pi，在顺利的情况下运行完毕，释放其占有的全部资源，这相当于消去的所有请求边和分配边，使之成为孤立结点。 ②由于释放了资源，这样能使其它被阻塞的进程获得资源继续运行。 ③在经过一系列简化后，若能消去图中的所有的边，使所有进程结点都孤立，则称该图是可完全简化的，反之是不可完全简化的。 可以证明：S状态为死锁状态的充分条件是当且仅当S状态的资源分配图是不可完全简化的。该条件称为死锁定理。 （3）死锁的检测 检测死锁的一个常见算法描述如下(算法中Available、Allocation、Need、Work的含义与银行家算法相同，L为一个初值为空的进程表)： ①将不需要、不占有资源的进程(即Needi= Allocationi =0的进程)记入表L中，并令Work等于Available。 ②从进程集合中找—个未记入L中的，且Needi≤Work的进程，若不存在这样的进程，则转步骤③；否则，将该进程记入表L中，增加工作向量Work = Work + Allocationi，并重复执行步骤②。 ③若不能把所有进程都记入L表中，则表示这些进程将发生死锁。 （4）死锁的解除 当发现有进程死锁后，便应立即把它从死锁状态中解脱出来，常采用的两种方法是： ①剥夺资源。从其他进程剥夺足够数量的资源给死锁进程，以解除死锁状态。 ②撤消进程。最简单的撤消进程方法是使全部死锁进程都夭折掉，稍微温和一点的方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。 三、经典例题解析 1．若信号S的初值为2，当前值为-1，则表示有( )个等待进程？ A．0 B．1 C．2 D．3 分析与解答： 信号量的初始值表示系统中资源的数目，每次的wait操作意味着进程请求一个单位的资源，信号量进行减1的操作，当信号量小于0时，表示资源已分配完毕，进程自我阻塞。因此，如果信号量小于0，那么信号量的绝对值就代表当前阻塞进程的个数，答案为B 2．比较进程与程序的异同 分析与解答 进程和程序是既有联系又有区别的两个概念，它们的主要区别如下： （1）每个进程实体中包含了程序段、数据段这两个部分，因此说进程和程序是紧密相关的。但从结构上看，进程实体中除了程序段和数据段外，还必须包含—个数据第构，即进程控制块PCB。 （2）进程是程序的—次执行过程，因此是动态的；动态性还表现在进程由创建产生、由调度而执行、由撤销而消亡，即它具有一定的生命周期。而程序则只是一组指令的有序集合，并可永久地存放在某种介质上，其本身不具有动态的含义，因此是静态的。 （3）多个进程实体可同时存放在内存中并发执行，其实这正是引入进程的目的。而程序的并发执行具有不可再现性，因此程序不能正确地并发执行。 （4）进程是一个能够独立运行、独立分配资源和独立接受调度的基本单位。而因程序不具有PCB，所以它是不可能在多道程序环境下独立运行的。 （5）进程和程序不一一对应。同一个程序的多次运行，将形成多个不同的进程；同一个程序的一次执行也可以产生多个进程；而一个进程也可以执行多个程序。 3． 为某临界区设置一把锁W，当W=1时表示关锁，W=0时表示锁已打开。试写出开锁原语和关锁原语，并利用它们去实现互斥。 分析与解答 在同步机构中，常用一个变量来代表临界资源的状态，并称它为锁，通常用0表示资源可用，用1表示资源已被占用。 关锁原语和开锁原语分别用lock和unlock表示，描述如下： lock(int *w) { whlie(*w= =1)； *w=1； } unlock(int *w) { *w=0； } 利用关锁原语和开锁原语实现互斥的算法描述如下： … lock(w)； 临界区； unlock(w)； … 4．桌上有一空盘，只允许存放一个水果。爸爸可向盘中放苹果，也可向盘中放桔子。儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘中空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。 分析与解答 在本题中，爸爸、儿子、女儿共用一个盘子，且盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是苹果，则允许女儿吃，儿子必须等待；若放入果盘中的是桔子，则允许儿子吃，女儿必须等待。本题实际上是生产者-消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。 在本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值为1；信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0。同步描述如下： semaphore S=1; semaphore Sa=0; semaphore So=0; main( ) { cobegin father(); son(); daughter(); coend } father() { while(1) { wait(S ); 将水果放入盘中； if （放入的是桔子） signal(So); else signal(Sa); } } son( ) { while(1) { wait(So); 从盘中取出桔子； signal(S); 吃桔子； } } daughter( ) { while(1) { wait(Sa); 从盘中取出苹果； signal(S); 吃苹果； } } 5．有5个任务A，B，C，D，E，它们几乎同时到达，预计它们的运行时间为10，6，2，4，8min。其优先级分别为3，5，2，1和4，这里5为最高优先级。对于下列每一种调度算法，计算其平均进程周转时间（进程切换开销可不考虑）。 （1）先来先服务（按A，B，C，D，E）算法。 （2）优先级调度算法。 （3）时间片轮转算法。 分析与解答 （1）采用先来先服务（FCFS）调度算法时，5个任务在系统中的执行顺序、完成时间及周转时间如下表所示： 执行次序 运行时间 优先数 等待时间 周转时间 A 10 3 0 10 B 6 5 10 16 C 2 2 16 18 D 4 1 18 22 E 8 4 22 30 根据表中的计算结果，5个进程的平均周转时间T为： T=（10+16+18+22+30）/5=19.2min （2）采用最高优先级调度（HPF）算法时，5个任务在系统中的执行顺序、完成时间及周转时间如下表所示： 执行次序 运行时间 优先数 等待时间 周转时间 B 6 5 0 6 E 8 4 6 14 A 10 3 14 24 C 2 2 24 26 D 1 1 26 27 它们的平均周转时间为： T=（6+14+24+26+27）/5= 19.4min （3）如果系统采用时间片轮转（RR）算法，令时间片为2分钟，5个任务轮流执行的情况为： 第1轮：（A，B，C，D，E） 第2轮：（A，B，D，E） 第3轮：（A，B，E） 第4轮：（A，E） 第5轮：（A） 显然，5个进程的周转时间为：T1=30min、 T2=22min、 T3=6min、T4=16min、T5=28min。它们的平均周转时间T为： T=（30+22+6+16+28）/5=20.4min 6．考虑由n个进程共享的具有m个同类资源的系统，每个进程一次一个地申请或释放资源，假设每个进程对该资源的最大需求量都小于m大于0，而且所有最大需求量之和小于m+n，证明该系统是死锁无关的。 分析与解答 设max(i)表示第i个进程的最大资源需求量，need(i)表示第i个进程还需要的资源数，alloc(i)表示第i个进程已分配的资源数。可知： max(1)+…+max(n)=(need(1)+…+need(n))+(alloc(1)+ …+alloc(n)) { While (1) { wait(empty1)； /*判断buff1是否有空间，没有则等待 */ wait(B-mutex1)； /*是否可操作buff1*/ 向buff1中放入一个数据； signal(B-mutex1)； /*设置buff1可操作标志 */ signal(full1)； /*将buff1中数据个数增加一个 */ } } { While (1) wait(full1)； /*判断buff1是否有数据，没有则等待*/ wait(empty2)； /*判断buff2是否有空间，没有则等待*/ wait(B-mutex1)； /*是否可操作buff1 */ wait(B-mutex2)； /*是否可操作buff2 */ 将buff1中的一个数据移到buff2； signal(B-mutex1)； /*设置buff1可操作标志*/ signal(B-mutex2)； /*设置buff2可操作标志*/ signal(empty1)； /*将buff1中的空间增加一个*/ signal(full2)； /*将buff2中的数据增加一个*/ } } { While (1) wait(full2)； /*判断buff2是否有数据，没有则等待 */ wait(B-mutex2)； /*是否可操作buff2*/ 从Buff2中将数据取走一个； signal(B-mutex2)； /*设置buff2可操作标志 */ signal(empty2)； /*将buff2中的空间增加一个*/ } } 8．有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。在下表所示的作业序列中，作业优先数即为进程优先数，优先数越小优先级越高。 作业号 到达时间 运行时间 优先数 A 10：00 40分钟 5 B 10：20 30分钟 3 C 10：30 50分钟 4 D 10：50 20分钟 6 （1）列出所有作业进入内存时间及结束时间。 （2）计算平均周转时间。 分析与解答 在本题中，每个作业的运行将经历两级调度：作业调度和进程调度。作业调度采用短作业优先调度算法，进程调度采用基于优先数的抢占式调度算法，高优先级的进程可以抢占系统处理机。只有当作业调度程序将作业装入内存后，方能参与进程调度。本题中的批处理系统是两道作业系统，因此每次只能有两道作业进入系统内存。 本题中的作业和进程推进顺序如下： 10：00时，A作业到达。因系统的后备作业队列中没有其他作业，进程就绪队列中也没有进程，故作业调度程序将作业A调入内存并将它排在就绪队列上，进程调度程序调度它运行。 10：20时，B作业到达。因系统的后备作业队列中没有其他作业，故作业调度程序将作业B调入内存并将它排在就绪队列上。而作业B的优先级高于作业A的优先级，进程调度程序停止作业A的运行，将作业A放入就绪队列，调度作业B运行。此时，系统中已有两道作业在内存中运行，作业A已运行20分钟，还需运行20分钟才能完成。 l0：30时，C作业到达。因系统中已有两道作业在内存中运行，故作业C只能在后备作业队列中等待作业调度。此时，作业B已运行了10分钟并将继续运行，还需运行20分钟才能完成；作业A已等待l0分钟并将继续等待、还需运行20分钟才能完成。 10：50时，B作业运行30分钟结束运行，D作业到达。因系统中只有作业A在内存中运行，作业后备队列中有C、D两作业，按短作业优先的作业调度策略，作业D被作业调度程序选中，装入内存运行，作业C仍在后备作业队列中等待作业调度。在内存中，作业A的优先级高于作业D，进程调度程序调度作业A运行，作业D在就绪队列中等待进程调度。此时，作业A已运行了20分钟，在就绪队列中等待了30分钟，还需运行20分钟才能完成；作业C已在后备队列中等待了20分钟并将继续等待。 11：10时，A作业运行40分钟结束运行。因系统中只有作业D在内存中运行，作业后备队列中只有作业C在等待，作业调度程序将作业C装入内存运行。因作业C的优先级高于作业D，进程调度程序调度作业C运行，作业D仍在就绪队列中等待进程调度。此时作业D已在就绪队列中等待了20分钟并将继续等待。 12：00时，C作业运行50分钟结束运行。因系统中只有作业D在内存，程序调度作业D运行。 12：20时，D作业运行20分钟结束运行。 （1）由上述分析可得出所有作业的进入内存时间和结束时间，如下表所示： 作业号 进入内存时间 结束时间 A 10：00 11：10 B 10：20 10：50 C 11：10 12：00 D 10：50 12：20 （1）各作业执行时的周转时间为： 作业A：70分钟 作业B：30分钟 作业c：90分钟 作业D：90分钟 作业的平均周转时间为 (70+30+90+90)／4＝70分钟。 9．假设某系统中有4种资源（R1,R2,R3,R4），在某时刻系统中共有5个进程，进程P1、P2、P3、P4、P5的最大资源需求量和此时已分配到的资源数向量如下表 进程 max R1 R2 R3 R4 allocation R1 R2 R3 R4 available R1 R2 R3 R4 P1 0 0 1 2 0 0 1 2 2 1 0 0 P2 2 7 5 0 2 0 0 0 P3 6 6 5 6 0 0 3 4 P4 4 3 5 6 2 3 5 4 P5 0 6 5 2 0 3 3 2 （1）当前系统是否是安全的？ （2）如果进程P3发出资源请求request(0,1,0,0)，为保证系统安全，系统能否将资源分配给它？ 分析与解答 （1）利用安全性算法对当前时刻的资源分配情况进行分析，进程的最大资源需求数减去当前进程已分配的资源数就是进程的还需资源数，可得下表所示的安全分析，从中可知存在一个安全序列{P1,P4,P5,P2,P3}；故系统是安全的。 进程 work R1 R2 R3 R4 need R1 R2 R3 R4 allocation R1 R2 R3 R4 work+allocation R1 R2 R3 R4 finish P1 2 1 0 0 0 0 0 0 0 0 1 2 2 1 1 2 true P4 2 1 1 2 2 0 0 2 2 3 5 4 4 4 6 6 true P5 4 4 6 6 0 3 2 0 0 3 3 2 4 7 9 8 true P2 4 7 9 8 0 7 5 0 2 0 0 0 6 7 9 8 true P3 6 6 2 2 6 6 2 2 0 0 3 4 6 6 5 6 true （2）在进程P3发出资源请求request(0,1,0,0)后，假设系统把资源分配给P3，修改有关数据，资源情况如下表所示： 进程 allocation R1 R2 R3 R4 need R1 R2 R3 R4 available R1 R2 R3 R4 P1 0 0 1 2 0 0 0 0 2 0 0 0 P2 2 0 0 0 0 7 5 0 P3 0 1 3 4 6 5 2 2 P4 2 3 5 4 2 0 0 2 P5 0 3 3 2 0 3 2 0 满足资源需求的进程执行序列为： 进程 可用资源数 P1完成后 （2，0，1，2） P4完成后 （4，3，6，6） P5完成后 （4，6，9，8） 此时可用资源数已不能满足P2或P3的需要，即此时系统状态是不安全的，系统将拒绝资源请求。 四、题型练习 (一)单项选择题 1．当（ ）时，进程从执行状态转变为就绪状态。 A．进程被调度程序选中 B。时间片到 C．等待某一事件 D。等待的事件发生 2．操作系统中，wait、signal操作是一种（ ） A．机器指令 B．系统调用命令 C．作业控制命令 D．低级进程通信原语 3. 在进程状态转换时，下列（ ）转换是不可能发生的。 A.就绪态→运行态 B.运行态→就绪态 C.运行态→阻塞态 D.阻塞态→运行态 4. 下面对进程的描述中，错误的是（ ）。 A.进程是动态的概念 B.进程执行需要处理机 C.进程是有生命期的 D.进程是指令的集合 5. 下列各项工作步骤中，（ ）不是创建进程所必需的步骤。 A.建立一个PCB B.作业调度程序为进程分配CPU C.为进程分配内存等资源 D. 将PCB链入进程就绪队列 6. 下列关于进程的叙述中，正确的是（ ）。 A.进程通过进程调度程序而获得CPU。 B.优先级是进行进程调度的重要依据，一旦确定不能改变。 C.在单CPU系统中，任一时刻都有1个进程处于运行状态。 D.进程申请CPU得不到满足时，其状态变为等待状态。 7. 有m个进程共享同一临界资源，若使用信号量机制实现对一临界资源的互斥访问，则信号量的变化范围是（ ）。 A. 1至 –(m-1) B.1至m-1 C.1至–m D.1至m 8. （ ）就是系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。 A. 进程调度 B. 进程通信 C. 进程同步 D. 进程控制 9. 从资源管理的角度看，进程调度属于（ ）。 A.I/O管理 B.文件管理 C.处理机管理 D.存储器管理 10. 设两个进程共用一个临界资源的互斥信号量mutex，当mutex＝-1时表示（ ）。 A.一个进程进入了临界区，另一个进程等待进入 B.没有一个进程进入临界区 C.两个进程都进入了临界区 D.两个进程都在等待 11. 如果系统中有n个进程，则就绪队列中进程的个数最多为（ ）。 A. n+1 B. n C. n-1 D. 1 12. 下列有可能导致一进程从运行变为就绪的事件是（ ）。 A.一次I/O操作结束 B.运行进程需作I/O操作 C.运行进程结束 D.出现了比现运行进程优先权更高的进程 13. 一个进程释放一种资源将有可能导致一个或几个进程（ ）。 A.由就绪变运行 B.由运行变就绪 C.由阻塞变运行 D.由阻塞变就绪 14. 发生死锁的必要条件有四个，要预防死锁的发生，可以破坏这四个必要条件，但是破坏( )条件是不太实际的。 A.请求和保持 B.互斥 C.不剥夺 D.环路等待 15. 线程被引入的原因（ ）。 A．线程分配的资源少。 B．减少进程切换和创建开销 C．为了更加方便系统管理。 D．提高CPU的执行效率，减少CPU的空转 16. 一次I/O操作的结束，有可能导致（ ）。 A.一个进程由阻塞变就绪 B.几个进程由阻塞变就绪 C.一个进程由阻塞变运行 D.几个进程由阻塞变运行 17. 在下面的叙述中，不正确的是（ ）。 A.一个进程可创建一个或多个线程 B.一个线程可创建一个或多个线程 C.一个线程可创建一个或多个进程 D.一个进程可创建一个或多个进程 18. 下述哪一个选项体现了原语的主要特点（ ）。 A.并发性 B.异步性 C.共享性 D.不可分割性 19. 若系统中只有用户级线程，则处理机调度单位是（ ）。 A.线程 B.进程 C.程序 D.作业 20. 进程是（ ）。 A.运行中的程序 B. 一个独立的程序＋数据集 C.与程序等效的概念 D.在内存中的程序 21. 下面关于线程的叙述中，正确的是（ ）。 A.不论是系统支持线程还是用户级线程，其切换都需要内核的支持。 B.线程是资源的分配单位，进程是调度和分配的单位。 C.不管系统中是否有线程，进程都是拥有资源的独立单位。 D.在引入线程的系统中，进程仍是资源分配和调度分派的基本单位。 22. 下列几种关于进程的叙述，（ ）最不符合操作系统对进程的理解？ A.进程是在多程序并行环境中的完整的程序。 B.进程可以由程序、数据和进程控制块描述。 C.线程是一种轻型的进程。 D.进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。 23. 在下面的叙述中，正确的是（ ）。 A.引入线程后，处理机只在线程间切换。 B.引入线程后，处理机仍在进程间切换。 C.线程的切换，不会引起进程的切换。 D.线程的切换，可能引起进程的切换。 24. 对进程间互斥地使用临界资源，进程可以（ ） A.互斥地进入临界区 B.互斥地进入各自的临界区 C.互斥地进入同一临界区 D.互斥地进入各自的同类资源的临界区 25. 进程的控制信息和描述信息存放在（ ）。 A.JCB B.PCB C.AFT D.SFT 26. 当一进程因在记录型信号量S上执行wait(S)操作而被阻塞后，S的值为（ ）。 A.>0 B.<0 C.≥0 D.≤0 27. 只作用于一个进程一次的原语是（ ）。 A.创建 B.解除挂起 C.阻塞 D.挂起 28. 进程依靠（ ）从阻塞状态过渡到就绪状态。 A.程序员的命令 B.系统服务 C.等待下一个时间片到来 D.“合作”进程的唤醒 29. 用wait、signal操作管理临界区时，信号量的初值一般应定义为（ ）。 A.–1 B.0 C.1 D.任意值 30. 当一进程因在记录型信号量S上执行V(S)操作而导致唤醒另一进程后，S的值为（ ）。 A.>0 B.<0 C.≥0 D.≤0 31. 若有4个进程共享同一程序段，而且每次最多允许3个进程进入该程序段，则信号量的变化范围是（ ）。 A. 3，2，1，0 B. 3，2，1，0，-1 C. 4，3，2，1，0 D. 2，1，0，-1，-2 32. 信箱通信是一种（ ）通信方式。 A.直接 B.间接 C.低级 D.信号量 33. （ ）操作不是wait操作可完成的。 A.为进程分配处理机 B.使信号量的值变小 C.可用于进程的同步 D.使进程进入阻塞状态 34. 下述哪个选项不是管程的组成部分（ ）。 A.局部于管程的共享数据结构 B.对管程内数据结构进行操作的一组过程 C.管程外过程调用管程内数据结构的说明 D.对局部于管程的数据结构设置初始值的语句 35. 如果有三个进程共享同一互斥段，而且每次最多允许两个进程进入该互斥段，则信号量的初值应设置为（ ）。 A. 3 B. 1 C. 2 D. 0 36．某系统采用了银行家算法，则下列叙述正确的是（ ）。 A.系统处于不安全状态时一定会发生死锁 B.系统处于不安全状态时可能会发生死锁 C.系统处于安全状态时可能会发生死锁 D.系统处于安全状态时一定会发生死锁 37. 在下列选项中，属于预防死锁的方法是（ ）。 A.剥夺资源法 B.资源分配图简化法 C.资源随意分配 D.银行家算法 38. 为了照顾紧迫型作业，应采用（ ）。 A.先来服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.优先权调度算法 39. 资源静态分配法可以预防死锁的发生，它们使死锁四个条件中的（ ）不成立。 A.互斥条件 B.请求和保持条件 C.不可剥夺条件 D.环路等待条件 40. 某系统中有3个并发进程，都需要同类资源4个，问该系统不会发生死锁的最少资源数是（ ）。 A. 9 B. 11 C. 10 D. 12 41. 若系统中有五台绘图仪，有多个进程均需要使用两台，规定每个进程一次仅允许申请一台，则至多允许（ ）个进程参于竞争，而不会发生死锁。 A． 5 B． 2 C． 3 D． 4 42. 在下列选项中，属于检测死锁的方法是（ ）。 A.银行家算法 B.消进程法 C.资源静态分配法 D.资源分配图简化法 43. 在下列选项中，属于避免死锁的方法是（ ）。 A．剥夺资源法 B.资源分配图简化法 C．银行家算法 D.资源静态分配法 44. 作业从后备作业到被调度程序选中的时间称为（ ）。 A.周转时间 B.响应时间 C.等待调度时间 D.运行时间 45. 在作业调度算法中，（ ）兼顾了短作业与长作业。 A.先来先服务 B.最高响应比优先 (二)综合应用题 1．进程和线程的主要区别是什么? 2．什么是进程控制块？它有什么作用？ 3．用户级线程和内核支持线程有何区别？ 4． 按序分配是防止死锁的一种策略。什么是按序分配？为什么按序分配可以防止死锁？ 5．何谓临界区？下面给出的两个进程互斥的算法是安全的吗？为什么？ #define true; #define false; int flag[2]; flag[1]=flag[2]=false; enter-crtsec(i) int i; { while (flag[1-i]) flag[i]=true; } leave-crtsec(i) int i; { flag[i]=false; } process i: … enter-crtsec(i); In critical section; Leave-crtsec(i); 6．某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请用P、V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。 7．理发店里有一位理发师、一把理发椅和N把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉。当一个顾客到来时，它必须叫醒理发师。如果理发师正在理发时又有顾客来到，如果有空椅上可坐，顾客就坐下来等待，否则就离开理发店。 8．设公共汽车上，司机和售票员的活动分别为：司机的活动为启动车辆，正常行车，到站停车；售票员的活动为关车门，售票，开车门。用wait、signal操作实现他们间的协调操作。 9．多个进程共享一个文件，其中只读文件的称为读者，只写文件的称为写者，读者可以同时读，但写者只能独立写，并要求对写着优先，即一旦有写者到达，后续的读者必须等待，而不论是否有读者在读文件。 10．一个计算机系统中拥有6台打印机，现有N个进程竞争使用，每个进程要求两台，试问，N的值如何选取时系统中绝对不会出现死锁？ 11．有三个进程P1、P2和P3并发工作。进程P1需要资源S3和S1各一个；进程P2需用资源S1和S2各一个；进程P3需用资源S2和S3各一个，S1、S2、S3的资源个数都是1，回答： （1）若对资源分配不加限制，会发生什么情况？为什么？ （2）为保证进程正确地工作，应采用怎样的资源分配策略？为什么？ 12． 现有两道作业同时执行，一道以计算为主，另一道以输入输出为主，你将怎样赋予作业进程占有处理器的优先级？为什么？ 13．有三个作业A、B、C，到达时间和运行时间如下表。在单道批处理系统按照响应比高者优先算法进行调度，计算平均周转时间和平均带权周转时间。 作业号 到达时间 运行时间 A 8.5 1.5 B 9 0.4 C 9.5 1 14．假定某计算机系统有R1和R2两类可以使用资源(其中Rl有两个单位，R2有一个单位)，它们被进程P1和P2所共享，且已知两个进程均以下列顺序使用两类资源： 申请R1→申请R2→申请R1→释放R1→释放R2→释放Rl 试求出系统运行过程中可能到达的死锁点，并画出死锁的资源分配图(或称进程一资源图)。 15．当前系统中出现下述资源分配情况： Allocation Need Available P0 0 0 3 2 0 0 1 2 1 6 2 2 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 利用银行家算法，试问： （1）该状态是否安全？ （2）如果进程P2提出资源请求Request(1,2,2,2)后，系统能否将资源分配给它？ 五、参考答案 (一)选择题 1.B 2.D 3.D 4.D 5.B 6.A 7.A 8.D 9.C 10.A 11.C 12.D 13.D 14.B 15.B 16.A 17.C 18.D 19.B 20.A 21.C 22.A 23.D 24.D 25.B 26.B 27.A 28.D 29.C 30.D 31.B 32.B 33.A 34.C 35.C 36.B 37.A 38.D 39.B 40.C 41.D 42.D 43.C 44.C 45.B （二）综合应用题 1．答：主要从调度、并发性、系统开销、拥有资源等方面来比较线程和进程： （1）调度。在传统的操作系统中，独立调度、分派的基本单位是进程。引入线程的操作系统中，则把线程作为调度和分派的基本单位。 （2）并发性。在引入线程的操作系统中，不仅进程之间可以并发执行，而且在—个进程中的多个线程之间亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。 （3）拥有资源。不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。一般地说，线程自己不拥有系统资源(只有—点运行时必不可少的资源)，但它可以访问其隶属进程的资源。 （4）系统开销。由于在创建、撤销或切换进程时，系统都要为之分配或回收资源，保存CPU现场。因此，操作系统所付出的开销将显著地大于创建、撤销或切换线程时的开销。在进程切换时，涉及到整个当前进程CPU环境的保存及新调度到的进程CPU环境的设置；而线程切换时，只需保存和设置少量寄存器内容，因此开销很少。另外，由于同一进程内的多个线程共享进程的地址空间，因此，这些线程之间的同步与通信非常容易实现，甚至无需操作系统的干预。 2．答：进程控制块PCB是一个记录进程属性信息的数据结构，是进程实体的一部分，是操作系统最重要的数据结构。 当操作系统要调度某进程执行时，需要从该进程的PCB中查询其现行状态和优先级调度参数；在调度到某进程后，要根据其PCB中保存的处理机状态信息去设置和恢复进程运行的现场，并根据其PCB中的程序和数据的内存地址来找到其程序和数据；进程在执行过程中，当需要与其他进程通信时，也要访问其PCB；当进程因某种原因而暂停执行时，又需要将断点的现场信息保存在其PCB中。系统在建立进程的同时就建立了该进程的PcB，在撤销一个进程时也就撤销其PCB。由此可知，操作系统根据PCB来对并发执行的进程进行控制和管理，PCB是进程存在的惟—标志。 3．答：两者的区别是： （1）内核支持线程是OS内核可感知的，而用户级线程是OS内核不可感知的。 （2）用户级线程的创建、撤消和调度不需要OS内核的支持，是在语言（如Java）这一级处理的；而内核支持线程的创建、撤消和调度都需OS内核提供支持，而且与进程的创建、撤消和调度大体是相同的。 （3）用户级线程执行系统调用指令时将导致其所属进程被中断，而内核支持线程执行系统调用指令时，只导致该线程被中断。 （4）在只有用户级线程的系统内，CPU调度还是以进程为单位，处于运行状态的进程中的多个线程，由用户程序控制线程的轮换运行；在有内核支持线程的系统内，CPU调度则以线程为单位，由OS的线程调度程序负责线程的调度。 （5）用户级线程的程序实体是运行在用户态下的程序，而内核支持线程的程序实体则是可以运行在任何状态下的程序。 4．答：按序分配是适应于动态分配的一种分配方法。为了避免产生死锁，系统将所有资源进行编号，并规定进程请求资源时，严格按照设备编号的大小，比如由小到大的顺序进程申请。如果某进程第n号资源没有获得，则进程不能请求第j（j>n）号资源。（系统也可以规定由大到小的请求次序。） 按序分配可以破坏环路等待条件。因为在进程发生死锁时，必然存在一个“进程-资源”的环形链。要排除循环的产生，让进程Pi先请求较小编号的资源，如果不能满足就不准请求较大编号的。这样一来，较小编号的资源如用于其他进程，Pi进程申请不到，也就不能申请高号资源，因此形成不了循环，也就不会产生死锁。 5．答：一次仅允许一个进程使用的资源称为临界资源，在进程中对临界资源访问的程序段称为临界区。从概念上讲，系统中各进程在逻辑上是独立的，它们可以按各自的速度向前推进。但由于它们共享某些临界资源，因而产生了临界区问题。对于具有临界区问题的并发进程，它们之间必须互斥，以保证不会同时进入临界区。 这种算法不是安全的。因为，在进入临界区的enter-crtsec()不是一个原子操作，如果两个进程同时执行完其循环(此前两个flag均为false)，则这两个进程可同时进入临界区。 6．答：设置一个信号量S，表示售票厅里还可以容纳的人数，初值为20。每个购票者的描述如下： Semaphore S=20; Buyer() { wait(S); 进入售票厅； 购票； 退出售票厅； signal(S); } 7．答：本题使用3个信号量和一个控制变量：控制变量waiting用来记录等候理发的顾客数，初值为0；信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为0；信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为0；信号量mutex用于互斥，初值为1。同步算法描述如下： semaphore customers=0；/*等候理发的顾客数*/ semaphore barberers=0；/*等候顾客的理发师数*/ semaphore mutex=1； int waiting=0； main() { cobegin barbers(); customers(); coend } barber() { while(true) { Wait(customers)； /*是否有等候的顾客*/ Wait(mutex); Waiting=waiting-1； /*顾客数减1*/ Signal(barbers)； /*理发师开始理发*/ Signal(mutex)； 理发； } } Customer() { Wait(mutex)； If(waiting