教学课件第5章操作系统

《教学课件第5章操作系统》由会员分享，可在线阅读，更多相关《教学课件第5章操作系统（362页珍藏版）》请在金锄头文库上搜索。

1、第第5 5章章 操作系统操作系统第第5章章 操操 作作 系系 统统5.1 概概 述述 5.1.1 操作系统的作用与地位操作系统的作用与地位 5.1.2 操作系统的功能操作系统的功能 5.1.3 操作系统的类型操作系统的类型 5.1.4 操作系统的基本特征操作系统的基本特征5.2 进程管理进程管理 5.2.1 多道程序设计多道程序设计 5.2.2 进程进程 5.2.3 进程间的通信进程间的通信 5.2.4 进程控制进程控制 5.2.5 进程高度调度进程高度调度 5.2.6 进程死锁进程死锁5.3 存储管理存储管理 5.3.1 存储管理的功能存储管理的功能 5.3.2 分区存储管理分区存储管理 5

2、.3.3 页式存储管理页式存储管理 5.3.4 段式存储管理段式存储管理 5.3.5 段页式存储管理段页式存储管理 5.3.6 虚拟存储管理虚拟存储管理 5.3.7 请求页式存储管理请求页式存储管理5.4 设备管理设备管理 5.4.1 设备管理概述设备管理概述 5.4.2 I/O控制方式控制方式 5.4.3 设备分配设备分配 5.4.4 I/O传输控制传输控制 5.4.5 磁盘调度磁盘调度5.5 文件管理文件管理 5.5.1 文件与文件系统文件与文件系统 5.5.2 文件结构和存取方法文件结构和存取方法 5.5.3 文件目录文件目录 5.5.4 文件存储空间的管理文件存储空间的管理 5.5.5

3、 文件存取控制文件存取控制5.6 作业管理作业管理 5.6.1 操作系统与用户的接口操作系统与用户的接口 5.6.2 作业的基本概念作业的基本概念 5.6.3 作业控制块和后备队列作业控制块和后备队列 5.6.4 作业调度与作业控制作业调度与作业控制 5.6.5 UNIX/XENIX操作系统操作系统 简介简介习题习题 第第5 5章章 操作系统操作系统5.1 概概 述述 5.1.1 操作系统的作用与地位 众所周知，计算机系统由硬件和软件组成。在众多的计算机软件中，操作系统占有特殊重要的地位。图5-1简明地显示了计算机系统的基本构成。这一简图表明：第第5 5章章 操作系统操作系统 (1) 操作系统

4、是最基本的系统软件，因为所有其它的系统软件(例如编译程序、数据库管理系统等语言处理器)和软件开发工具都是建立在操作系统的基础之上，它们的运行全都需要操作系统的支持。在计算机启动后，通常先把操作系统装入内存，然后才启动其它的程序。第第5 5章章 操作系统操作系统 (2) 操作系统是用户与计算机硬件之间的接口。用户及其应用程序是通过操作系统与计算机的硬件相联系的。如果没有操作系统作为中介，用户对计算机的操作和使用将变得非常低效和困难。 (3) 按照虚拟机(Virtual machine)的观点，操作系统+裸机=虚拟计算机，如图5-2所示。换句话说，一台纯粹由硬件组成的裸机在配置操作系统后，将变成一

5、台与原机器大相径庭的“虚拟”的计算机，无论在机器的功能或操作方面都将面目一新。第第5 5章章 操作系统操作系统 图5-1 计算机系统的基本构成 第第5 5章章 操作系统操作系统图5-2 裸机+操作系统=虚拟计算机 第第5 5章章 操作系统操作系统 由此可见，硬件仅为人们提供了“原始的处理能力”。有了操作系统，才能使这一能力更有效、更方便地为人们使用。鉴于操作系统在计算机系统及软件开发环境中所处的重要地位，任何用户从系统程序员到一般的最终用户(end user)都需要不同程度地了解它。 所谓操作系统(OS，Operating System)，它是由一些程序模块组成，用来控制和管理计算机系统内的所

6、有资源，并且合理地组织计算机的工作流程，以便有效地利用这些资源，并为用户提供一个功能强、使用方便的工作环境。第第5 5章章 操作系统操作系统 操作系统有两个重要的作用： (1) 管理计算机系统中的各种资源。 我们知道，任何一个计算机系统，不论是大型机、小型机，还是微机，都具有两种资源：硬件资源和软件资源。硬件资源是指计算机系统的物理设备，包括中央处理机、存储器和I/O设备；软件资源是指由计算机硬件执行的、用以完成一定任务的所有程序及数据的集合，它包括系统软件和应用软件。操作系统就是最基本的系统软件，它既是计算机系统的一部分，又反过来组织和管理整个计算机系统，充分利用这些软、硬件资源，使计算机协

7、调一致并高效地完成各种复杂的任务。第第5 5章章 操作系统操作系统 (2) 为用户提供良好的界面。 从用户的角度看，操作系统不仅要对系统资源进行合理的管理，还应为用户提供良好的操作界面，便于用户简便、高效地使用系统资源。这里的用户包括计算机系统管理员、应用软件的设计人员等。 “管家婆”兼“服务员”，就是操作系统所扮演的一身二任的角色。第第5 5章章 操作系统操作系统 5.1.2 操作系统的功能 操作系统的基本功能就是合理地、高效地管理计算机系统的各种软硬件资源。在单用户系统中，资源管理相对简单一些，而在多用户共用的系统中，资源管理的任务就比较复杂。由于多用户要共享系统资源，就带来了一些新的问题

8、。如多个用户如何抢占CPU时间，有限的存储空间特别是宝贵的内存空间如何分配，如何竞争输入输出设备及软件资源等。第第5 5章章 操作系统操作系统 这就要求操作系统必须有相应的功能，来决定资源共享的策略和有效地解决问题的方法，最大限度地发挥计算机的效率，提高计算机在单位时间内处理工作的能力(称为“吞吐量”，through out)。因此，操作系统应具有的基本功能有：中央处理器管理、存储管理、设备管理、文件管理及作业管理。第第5 5章章 操作系统操作系统 1中央处理器管理 中央处理器即CPU，是计算机系统中最宝贵的硬件资源。CPU管理指操作系统根据一定的调度算法对处理器进行分配，并对其运行进行有效的

9、控制和管理。为了提高CPU的利用率，采用了多道程序技术。如果一个程序因等待某一条件而不能继续运行时，就把处理器占用权转交给另一个可运行程序；或者，当出现了一个比当前运行的程序更重要的可运行的程序时，后者应能抢占CPU。为了描述多道程序的并发执行，就要引入进程的概念，通过进程管理协调多道程序之间的关系，解决对处理器分配调度策略、分配实施和回收等问题，以使CPU资源得到最充分的利用。第第5 5章章 操作系统操作系统 正是由于操作系统对处理器管理策略的不同，其提供的作业处理方式也就不同。例如批处理方式、分时处理方式和实时处理方式，从而呈现在用户面前的就是具有不同性质的操作系统。第第5 5章章 操作系

10、统操作系统 2存储管理 存储管理指分配、回收与保护存储单元。其目的是为多个程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率，以及能从逻辑上来扩充内存。第第5 5章章 操作系统操作系统 存储管理主要是指内存管理，虽然RAM芯片的集成度不断地提高，但受CPU寻址能力的限制，内存的容量仍有限。因此，当多个程序共享有限的内存资源时，要解决的问题是如何为它们分配内存空间，同时，既使用户存放在内存中的程序和数据彼此隔离、互不侵扰，又能保证在一定条件下共享，尤其是当内存不够用时，解决内存扩充问题(即将内存和外存结合起来管理)，为用户提供一个容量比实际内存大得多的虚拟存储器。操作系统的这一部分

11、功能与硬件存储器的组织结构密切相关。第第5 5章章 操作系统操作系统 3设备管理 设备管理主要是对设备进行分配、回收与控制。这里所说的设备是指计算机系统中除了CPU和内存以外的所有输入、输出设备，除了完成实际I/O操作的设备外，还包括诸如控制器、通道等支持设备。外部设备的种类繁多、功能差异很大。设备管理负责外部设备的分配、启动和故障处理，用户不必详细了解设备及接口的技术细节，就可以方便地对设备进行操作。 第第5 5章章 操作系统操作系统 为了提高设备的利用效率和整个系统的运行速度，可采用中断技术、通道技术、虚拟设备技术和缓冲技术，尽可能发挥设备和主机的并行工作能力。此外，设备管理应为用户提供一

12、个良好的界面，使用户不必涉及具体设备的物理特性即可方便灵活地使用这些设备。第第5 5章章 操作系统操作系统 4文件管理 计算机系统中的软件资源(如程序和数据)是以文件的形式存放在外存储器(如磁盘、磁带)上的，需要时再把它们装入内存。文件管理的任务是有效地支持文件的存储、检索和修改等操作，解决文件的共享、保密和保护问题，以使用户方便、安全地访问文件。操作系统一般都提供功能很强的文件系统。第第5 5章章 操作系统操作系统 5作业管理 除了上述4项功能之外，操作系统还应该向用户提供使用它自己的手段，这就是操作系统的作业管理功能，作业管理是操作系统提供给用户的最直接的服务。按照用户观点，操作系统是用户

13、与计算机系统之间的接口，因此，作业管理的任务是为用户提供一个使用系统的良好环境，使用户能有效的组织自己的工作流程，并使整个系统能高效地运行。 操作系统的各功能之间并非是完全独立的，它们之间存在着相互依赖的关系。 第第5 5章章 操作系统操作系统 5.1.3 操作系统的类型 操作系统有多种。翻开操作系统的发展史，操作系统经历了手工操作阶段、单道(程序)批处理阶段、多道(程序)批处理阶段、分时系统、实时系统。随着硬件技术的飞速发展，微处理机的出现和发展，操作系统又向个人计算机、计算机网络、分布式处理和智能化方向发展，随着计算机技术和软件技术的发展，目前已经形成了各种类型的操作系统，以满足不同的应用

14、要求。 在以下的描述中用到作业的概念，所谓作业就是用户要求计算机处理的一项工作，是用户程序及所需数据和命令的集合。第第5 5章章 操作系统操作系统 1批处理操作系统 所谓批处理操作系统，就是用户将要机器做的工作有序地排在一起，成批地交给计算机系统，计算机系统就能自动地、顺序地完成这些作业，用户与作业之间没有交互作用，不能直接控制作业的运行。有时也称批处理为“脱机操作”。第第5 5章章 操作系统操作系统 在批处理系统中，用户一般不直接操纵计算机，而是将作业提交给系统操作员。操作人员将作业成批地装入计算机，由操作系统将作业按规定的格式组织好存入磁盘的某个区域，然后按照某种调度策略依次将作业调入内存

15、加以处理，处理的步骤事先由用户设定，输出的作业处理结果通常也由操作系统组织存入磁盘某个区域，然后统一加以输出，最后，由操作员将作业运行结果交给用户。第第5 5章章 操作系统操作系统 在批处理系统中，又有单道批处理和多道批处理两种。在单道批处理的情况下，一次只调一个作业进入内存，CPU只为一道作业服务。但是在这个作业运行期间，输入和输出操作是难免的，而实际中I/O的速度要比CPU慢得多，这样就造成了CPU大部分时间在空闲等待。为了解决这一问题，又产生了多道批处理系统。它一次将几个作业放入内存，宏观上看，同时有多个作业在系统中运行，而实际上这些作业是分时串行地在一台计算机上运行。第第5 5章章 操

16、作系统操作系统 也就是说，CPU先处理第一个作业，如果这个作业由于I/O或其它原因而不能继续进行，就从可运行的作业中挑选另一个作业去运行，从表面上看，好象两个作业同时运行。这样做，显然提高了CPU的利用率，改善了主机和I/O设备的使用情况。 多道批处理系统追求的目标是提高系统资源的利用率和大的作业吞吐量以及作业流程的自动化。这类操作系统一般用于计算中心等较大的计算机系统中，要求系统对资源的分配及作业的调度策略有精心的设计，管理功能要求既全又强。第第5 5章章 操作系统操作系统 2分时操作系统 多道批处理系统虽然能提高机器的资源利用率，但却存在一个重要的缺点。由于一次要处理一批作业，在作业的处理

17、过程中，任何用户都不能和计算机进行交互。即使发现了某个作业有程序错误，也要等一批作业全部结束后脱机进行纠错。这对于软件开发人员来说，是严重的缺陷。正是这一矛盾，导致了分时操作系统应运而生。第第5 5章章 操作系统操作系统 分时操作系统允许多个用户同时联机与系统进行交互通信，一台分时计算机系统连有若干台终端，多个用户可以在各自的终端上向系统发出服务请求，等待计算机的处理结果并决定下一步的处理。操作系统接收每个用户的命令，采用时间片轮转的方式处理用户的服务请求，即按照某个轮转次序给每个用户分配一段CPU时间，进行各自的处理。这样，对每个用户而言，都仿佛“独占”了整个计算机系统。具有这种特点的计算机

18、系统称为分时系统。第第5 5章章 操作系统操作系统 例如一个带20个终端的分时系统，若每个用户分配一个50 ms的时间片，每隔1 s(50 ms20)即可为所有用户服务一遍。如此周而复始，循环不已。因此，尽管各个终端上的作业是断续地运行，但由于操作系统每次都能对用户程序作出及时的响应(例如上述的1 s)，在用户的感觉上，似乎整个系统归他一人占有。分时系统的这一特性称为“独占性”。第第5 5章章 操作系统操作系统 由上所述，分时操作系统具有以下几个方面的特点。 (1) 多路性。允许在一台主机上同时联接多台联机终端，系统按分时原则为每个用户服务。在微观上，是每个用户作业轮流运行一个时间片；而在宏观

19、上，则是多个用户同时工作，共享系统资源。多路性亦称同时性，它提高了资源利用率。第第5 5章章 操作系统操作系统 (2) 独立性。又称独占性。每个用户各占一个终端，彼此独立操作，互不干扰。因此，用户会感觉到就像他一人独占主机。 (3) 及时性。系统对用户的输入能及时地做出响应，此时间间隔是以人们所能接受的等待时间来确定的，通常为12 s。分时操作系统性能的主要指标之一是响应时间，即从终端发出命令到系统予以应答所需的时间。 (4) 交互性。用户可通过终端与系统进行广泛的人机对话。分时系统的主要目标是对用户响应的及时性，即不使用户等待每一条命令的处理时间过长。 第第5 5章章 操作系统操作系统 3实

20、时操作系统 实时操作系统是随着计算机应用领域的日益广泛而出现的，具体含义是指系统能够及时响应随机发生的外部事件，并在严格的时间范围内完成对该事件的处理。实时系统可分为两类： (1) 实时控制系统。实时控制系统实质上是过程控制系统，通过模-数转换装置，将描述物理设备状态的某些物理量转换成数字信号传送给计算机，计算机分析接收来的数据、记录结果，并通过数-模转换装置向物理设备发送控制信号，来调整物理设备的状态。 第第5 5章章 操作系统操作系统 例如把计算机用于飞机飞行、导弹发射等自动控制时，要求计算机能尽快处理测量系统测得的数据，及时地对飞机或导弹进行控制，或将有关信息通过显示终端提供给决策人员。

21、同样，把计算机用于轧钢、石化、机械加工等工业生产过程控制时，也要求计算机能及时处理由各类传感器送来的数据，然后控制相应的执行机构。第第5 5章章 操作系统操作系统 (2) 实时信息处理系统。实时信息处理系统主要是指对信息进行及时地处理。例如利用计算机预订飞机票、火车票或轮船票，查询有关航班、票价等事宜时，或把计算机用于银行系统、情报检索系统时，都要求计算机能对终端设备发来的服务请求及时予以正确的回答。这个过程中，实时的重要性在于防止数据的丢失。第第5 5章章 操作系统操作系统 实时操作系统的一个主要特点是及时响应，即每一个信息接收、分析处理和发送的过程必须在严格的时间限制内完成；其另一个主要特

22、点是要有高可靠性，因为实时系统控制、处理的对象往往是重要的军事、经济目标，任何故障都会导致巨大的损失，所以重要的实时系统往往采用双机系统以保证绝对可靠。第第5 5章章 操作系统操作系统 实时操作系统有别于批处理系统，因为它认为保证可靠操作远比让所有资源经常处于“忙碌”状态更重要；它也不同于分时操作系统，因为它要求的实时响应时间随系统而变化，例如定票和检索系统一般要求在数秒内响应，而导弹系统的响应时间可能短达微秒量级，不像分时操作系统的响应时间总是保持在一定的范围内(例如12 s)。正是由于这些特点，许多实时操作系统都属于专用操作系统，以便按照实际的需要来设计。第第5 5章章 操作系统操作系统

23、4个人计算机操作系统 个人计算机上的操作系统是一种联机交互的单用户操作系统，它提供的联机交互功能与通用分时系统所提供的功能很相似。由于是个人专用，因此一些功能将会简单的多。然而，由于个人计算机的应用普及，要求个人计算机操作系统提供更方便友好的用户接口和功能丰富的文件系统。 单用户单任务的操作系统MS-DOS和单用户多任务的操作系统OS/2及Windows等都是个人计算机上的操作系统。第第5 5章章 操作系统操作系统 5网络操作系统 网络操作系统是为计算机网络而配置的。计算机网络是把不同地点上分布的计算机通过通信机构连接起来，实现资源共享。网络操作系统就是网络用户与计算机网络之间的接口，它除了具

24、有通常操作系统的各种功能外，还应具有网络管理的功能，例如，网络通信、网络服务等。第第5 5章章 操作系统操作系统 6分布式操作系统 分布式操作系统是为分布式计算机系统配置的，它将物理上分布的具有自治功能的数据处理系统或计算机系统互连起来，实现信息交换和资源共享，协作完成任务。分布式操作系统管理分布式系统中的所有资源，它负责全系统的资源分配和调度、任务划分、信息传输控制协调工作，并为用户提供一个统一的界面，用户通过这一界面实现所需要的操作并使用系统资源，至于操作定在哪一台计算机上执行或使用哪台计算机的资源则是操作系统完成的，用户不必知道。第第5 5章章 操作系统操作系统 此外，由于分布式系统更强

25、调分布式计算和处理，因此对于多机合作和系统重构、健壮性和容错能力有更高的要求。第第5 5章章 操作系统操作系统 5.1.4 操作系统的基本特征 操作系统是一个十分复杂的系统软件，考察操作系统的基本特征，能帮助人们从更深的层次上认识操作系统。前面介绍的各种类型的操作系统，虽然它们各有自己的特征，但它们都具有以下四个基本特征。第第5 5章章 操作系统操作系统 1并发(Concurrence) 并发性是指在计算机系统中同时存在着若干个正在运行的程序，这些程序同时或交替地运行。从宏观上看，这些程序是同时向前推进的，但在单处理机的环境下，每一时刻仅能执行一道程序，故在微观上，这些并发执行的程序是交替地在

26、CPU上运行。程序的并发性具体体现在如下两个方面：用户程序与用户程序之间并发执行；用户程序与操作系统程序之间并发执行。第第5 5章章 操作系统操作系统 2共享(Sharing) 并发性必然要求系统资源共享。所谓共享是指系统中的资源可供内存中多个并发执行的进程共同使用，即操作系统程序与多个用户程序共享系统中的各种软、硬件资源。例如，多道程序共占内存，若干个任务分享CPU，多个用户共享一个程序副本，共享同一数据库等，都是共享的表现。共享的好处是可以减少资源浪费，避免软件的重复开发，但随之而来的问题有： 如何处理资源竞争问题，进行合理的资源分配； 当程序同时执行，数据共同存取时，如何保护它们不因受到

27、破坏而引起混乱。第第5 5章章 操作系统操作系统 3虚拟(Virtual) 在操作系统中的所谓“虚拟”，是指通过某种技术把一个物理实体变成逻辑上的多个。物理实体(前者)是实的，即实际存在的，而后者是虚的，是用户感觉上的东西。例如，在多道分时系统中，虽然只有一个CPU，但每个终端用户却都认为是有一个CPU在专门为他服务，亦即，利用多道程序技术可以把一台物理上的CPU虚拟为多台逻辑上的CPU，也称为虚处理机。类似地，也可以把一台物理I/O设备虚拟为多台逻辑上的I/O设备。 第第5 5章章 操作系统操作系统 此外，也可以把一条物理信道虚拟为多条逻辑信道(虚信道)。在操作系统中虚拟的实现，主要是通过分

28、时使用的方法。显然，如果n是某一物理设备所对应的虚拟的逻辑设备数，则虚拟设备的速度必然是物理设备速度的1/n。第第5 5章章 操作系统操作系统 4异步性(Asynchronism) 也称为不确定性。不是说操作系统本身的功能不确定，也不是说在操作系统控制下运行的用户程序的结果不确定(即同一程序对相同的输入数据在两次或两次以上运行中有不同的结果)，而是说在操作系统控制下的多个作业的运行顺序和每个作业的运行时间是不确定的。在多道程序环境下，允许多个程序同时执行，但由于资源等因素的限制，通常程序的执行并非“一气呵成”，而是以“走走停停”的方式运行。内存中的每个进程在何时执行，何时暂停，以怎样的速度向前

29、推进，每道程序总共需多少时间才能完成，都是不可预知的。 第第5 5章章 操作系统操作系统 很可能是先进入内存的作业后完成，而后进入内存的作业先完成。或者说，进程是以异步的方式运行。例如，有三个作业J1、J2、J3，两次或多次运行的顺序可能是不相同的，而且同一个作业(如J1)这次运行需要1 s，下次运行却需要4 s等。尽管如此，但只要运行环境相同，作业经多次运行，都会获得完全相同的结果，因此，异步运行方式是允许的。第第5 5章章 操作系统操作系统5.2 进进 程程 管管 理理 5.2.1 多道程序设计 1程序的顺序执行 自从计算机问世以来，人们广泛地使用“程序”这一概念。程序是一个在时间上按严格

30、次序前后相继执行的操作序列。在多道程序设计出现以前，程序的最大特征是“顺序性”，即顺序执行。下面用一个简单的例子来说明程序顺序执行的特点。第第5 5章章 操作系统操作系统图5-3 程序的顺序执行 第第5 5章章 操作系统操作系统 假设有n个作业，而每个作业Ji由三个程序段Ii，Ci，Pi组成。其中，Ii表示从输入机上读入第i个作业的信息；Ci表示执行第i个作业的计算；Pi表示在打印机上打印出第i个作业的计算结果。在早期的计算机中，每一作业的这三个程序只能是一个接一个地顺序执行。也就是输入，计算和打印三者串行工作，并且前一个作业结束后，才能执行下一个作业，如图5-3所示。 显然，程序的顺序执行具

31、有如下特点。第第5 5章章 操作系统操作系统 (1) 顺序性。程序所规定的动作在机器上严格地按顺序执行，每个动作的执行都以前一个动作的结束为前提条件，即程序和机器执行它的活动严格一一对应。 (2) 封闭性。程序一旦开始运行，其计算结果只取决于程序本身，不受外界因素的影响，即只有程序本身的动作才能改变程序的运行环境。 (3) 可再现性。程序的执行结果与其执行速度无关。只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果，且处理机在执行程序的两个动作之间如有停顿也不会影响程序的执行结果。第第5 5章章 操作系统操作系统 2. 程序的并发执行 为增强计算机系统的处理能力和提高各种资源的

32、利用率，往往要求计算机系统能够同时处理多个具有独立功能的程序。通常采用并行操作技术，使系统中的各种硬件资源尽量做到并行工作。第第5 5章章 操作系统操作系统 所谓程序的并发执行是指两个或两个以上的程序在执行时间上是重叠的。系统中各个部分不再以单纯的串行方式工作。换句话说，在任一时刻，系统中不再只有一个活动，而存在着许多并行的活动。从硬件方面看，处理机，各种外设，存储部件常常并行地工作着；从程序活动方面看，则可能有若干程序同时或者相互穿插地在系统中被执行。程序的并发执行已成为现代操作系统的一个基本特征。第第5 5章章 操作系统操作系统 程序的并发执行虽然卓有成效地增加了系统的处理能力和提高了系统

33、资源的利用率，但它带来了一些新的问题，也就是产生了与顺序程序不同的新特性，这些新特性是： (1) 失去了程序的封闭性。如前所述，程序的顺序执行具有程序的封闭性和由之而来的可再现性，而并发执行是否还保持这种封闭性呢？先来看一个例子。第第5 5章章 操作系统操作系统 设有观察者和报告者并行工作。在一条单向行驶的公路上经常有卡车通过。观察者不断对通过的卡车计数。报告者定时地将观察者的计数值打印出来，然后将计数器重新清“0”。此时可以写出如下程序，其中Cobegin和Coend表示它们之间的程序可以并发执行。第第5 5章章 操作系统操作系统BeginCount:integer;Count:=0Cobe

34、gin Observer Begin L1: Observe next car; Count:=Count +1; Goto L1 End;第第5 5章章 操作系统操作系统Reporter Begin L2: Print Count; Count:=0; Goto L2 End CoendEnd第第5 5章章 操作系统操作系统 由于观察者和报告者各自独立地并行工作，其中，Count:=Count+1的操作，既可以在报告者的Print Count和Count:=0操作之前，也可以在其后，还可以在Print Count和Count:=0之间。既可能出现以下三种执行序列： Count :=Count

35、+1; Print Count; Count:=0; Print Count; Count:=0; Count:=Count+1; Print Count; Count:=Count+1; Count:=0。 假设在开始某个循环之前，Count的值为n，则在完成一个循环后，对上述三个执行序列打印机打印的Count值和执行后的Count值如下表所示：第第5 5章章 操作系统操作系统执行序列打印的值n+1nn执行后的值010第第5 5章章 操作系统操作系统 由上表可见，由于观察者和报告者的程序执行速度不同，导致了计算结果的不同。这就是说，程序并发执行已丧失了顺序执行所保持的封闭性和可再现性。 (2

36、) 程序与计算不再一一对应。程序和机器执行程序的活动是两个概念。程序是指令的有序集合，是静态的概念；而机器执行程序的活动是指处理机按照程序执行指令序列的过程。通常把机器执行程序的活动，称为“计算”。显然，“计算”是一个动态的概念。第第5 5章章 操作系统操作系统 在并发执行中，允许多个用户作业调用一个共享程序段，从而形成了多个“计算”。例如，在分时系统中，一个编译程序往往同时为几个用户服务，该编译程序便对应了几个“计算”。第第5 5章章 操作系统操作系统 (3) 间断性。即并发程序在执行期间具有相互制约关系。程序在并发执行时，总是伴随着资源的共享和竞争，从而制约了各个程序的执行速度，使本来并无

37、逻辑关系的程序之间产生了相互制约的关系，各个程序活动的工作状态与它所处的环境有密切关系。它随着外界变化而不停地变化，并且它不像单道程序系统中顺序执行那样，而是走走停停，具有执行暂停执行的活动规律。第第5 5章章 操作系统操作系统 3多道程序设计 所谓多道程序设计，就是允许多个程序同时进入内存并运行。多道程序设计是操作系统所采用的最基本、最重要的技术，其根本目的是提高整个系统的效率。 衡量系统效率的尺度是系统吞吐量。所谓吞吐量是指单位时间内系统所处理作业(程序)的道数(数量)。如果系统的资源利用率高，则单位时间内所完成的有效工作多，吞吐量大。引入多道程序设计后，提高了设备资源利用率，使系统中各种

38、设备经常处于忙碌状态，最终提高系统吞吐量。第第5 5章章 操作系统操作系统 多道程序设计改善了各种资源的使用情况，从而增加了吞吐量，提高了系统效率，但也带来了资源竞争。因此，在实现多道程序设计时，必须协调好资源使用者与被使用资源之间的关系，即对处理机资源加以管理，以实现处理机在各个可运行程序之间的分配与调度；对内存资源加以管理，将内存分配给各个运行程序，还要解决程序在内存中的定位问题，并防止内存中各个程序之间互相干扰或对操作系统的干扰；对设备资源进行管理，使各个程序在使用设备时不发生冲突。第第5 5章章 操作系统操作系统 5.2.2 进程 1进程的概念 在多道程序的环境下，程序的并发执行代替了

39、程序的顺序执行。程序活动不再处于一个封闭系统中，而出现了许多新的特征，即独立性，并发性，动态性以及它们之间的相互制约性。在这种情况下，程序这个静态概念已经不能如实地反映程序活动的这些特征。为了能更好地描述程序的并发执行，引入“进程”的概念来描述系统和用户的程序活动。第第5 5章章 操作系统操作系统 进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源分配和调度的一个独立单位。 从操作系统角度来看，可将进程分为系统进程和用户进程两类。系统进程执行操作系统程序，完成操作系统的某些功能。用户进程运行用户程序，直接为用户服务。系统进程的优先级通常高于一般用户进程的优先级。第

40、第5 5章章 操作系统操作系统 2进程的特性 (1) 进程与程序的联系和区别。 进程与程序既有联系又有区别。 联系：程序是构成进程的组成部分之一，一个进程的运行目标是执行它所对应的程序，如果没有程序，进程就失去了其存在的意义。从静态的角度看，进程是由程序、数据和进程控制块(PCB)三部分组成的。第第5 5章章 操作系统操作系统 区别：程序是静态的，而进程是动态的。 进程是程序的执行过程，因而进程是有生命周期的，有诞生，也有消亡。因此，程序的存在是永久的，而进程的存在是暂时的，它动态地产生和消亡。一个进程可以执行一个或几个程序，一个程序亦可以构成多个进程。例如，一个编译进程在运行时，要执行词法分

41、析、语法分析、代码生成和优化等几个程序，或者一个编译程序可以同时生成几个编译进程，为几个用户服务。进程具有创建其它进程的功能，被创建的进程称为子进程，创建者称为父进程，从而构成进程家族。第第5 5章章 操作系统操作系统 2) 进程的特性。 进程的概念能很好地描述程序的并发执行，并且能够揭示操作系统的内部特性。事实上，操作系统的并发性和共享性正是通过进程的活动体现出来的。 进程具有以下特性： 动态性。进程是程序的执行过程，“执行”本身就是动态的。因此进程由“创建”而产生，由“撤消”而消亡，因拥有处理机而得到运行。第第5 5章章 操作系统操作系统 并发性。进程是为了实现系统内并发执行而引入的概念，

42、所以并发性是进程与生俱来的特性。 独立性。一个进程是一个相对完整的调度单位，它可以获得处理机并参与并发执行。 异步性。每个进程按照各自独立的、不可预知的速度向前推进。第第5 5章章 操作系统操作系统 3进程的状态及其状态转换 根据进程在执行过程中的不同情况，通常可以将进程分成三种不同的状态。 (1) 运行状态。是指进程已获得CPU，并且在CPU上执行的状态。显然，这种状态的进程数目不能大于CPU的数目，在单CPU情况下，处于运行状态的进程只能有一个。 (2) 就绪状态。这种状态是指进程原则上是可以运行的，只是因为缺少CPU而不能运行，一旦把CPU 分配给它，它就可以立即投入运行。处于就绪状态的

43、进程可以有多个。第第5 5章章 操作系统操作系统图5-4 进程状态转换图第第5 5章章 操作系统操作系统 (3) 等待状态。也称阻塞状态或睡眠状态。进程在前进的过程中，由于等待某种条件(例如当前外设资源不够，等待其它进程来的信息等)而不能运行时所处的状态。在这种情况下，既使CPU空闲，这种进程也不能占据CPU而运行。引起等待的原因一旦消失，进程便转为就绪状态，以便在适当的时候投入运行。处于等待状态的进程可以有多个。第第5 5章章 操作系统操作系统 在任何时刻，任何进程都处于且仅处于以上3种状态之一。进程在运行过程中，由于它自身的进展情况和外界环境条件的变化，3种基本状态可以互相转换。这种转换由

44、操作系统完成，对用户是透明的，它也体现了进程的动态性。图5-4表示了3种基本状态之间的转换及其典型的转换原因。第第5 5章章 操作系统操作系统 4进程控制块 为了便于系统控制和描述进程的基本情况以及进程的活动过程，在操作系统中为进程定义了一个专门的数据结构，称为进程控制块(PCB，Process Control Block)。系统为每一个进程设置一个PCB，PCB是进程存在与否的惟一标志。当系统创建一个进程时，系统为其建立一个PCB；然后利用PCB对进程进行控制和管理；当进程被撤消时，系统收回它的PCB，随之该进程也就消亡了。第第5 5章章 操作系统操作系统 进程由程序、数据和进程控制块三部分

45、组成。PCB是进程的“灵魂”，程序和数据是进程的“躯体”，由于现代操作系统提供程序共享的功能，这就要求程序是可再入程序，且与数据分离。所谓可再入程序是指“纯”代码的程序，即在运行过程中不修改自身。 在通常的操作系统中，PCB应包含如下一些信息：第第5 5章章 操作系统操作系统 (1) 进程标识名或标识数。为了标识系统中的各个进程，每个进程必须有一个而且是惟一的标识名或标识数。进程标识名通常用字母或数字组成的串表示，进程标识数则是在一定数值范围内的进程编号。有的系统用进程标识名作为进程的外部标识，它通常由创建者给出；用进程标识数作为进程的内部标识，通常由系统给出。第第5 5章章 操作系统操作系统

46、 (2) 位置信息。它指出进程的程序和数据在内存或外存中的物理位置。 (3) 状态信息。它指出进程当前所处的状态，作为进程调度，分配处理机的依据。 (4) 进程的优先级。一般根据进程的轻重缓急程度为进程指定一个优先级，优先级用优先数表示。进程调度程序根据优先数的大小，确定优先级的高低，并把CPU控制交给优先级最高的进程。第第5 5章章 操作系统操作系统 (5) 进程现场保护区。当进程状态变化时，例如一个进程放弃使用处理机，它需要将当时的CPU 现场保护到内存中，以便再次占用处理机时恢复正常运行，有的系统把要保护的CPU现场放在进程的工作区中，而PCB中仅给出CPU现场保护区起始地位。 (6)

47、资源清单。每个进程在运行时，除了需要内存外，还需要其它资源，如I/O设备、外存、数据区等。这一部分指出资源需求、分配和控制信息。 (7) 队列指针或链接字。它用于将处于同一状态的进程链接成一个队列，在该单元中存放下一进程PCB首址。第第5 5章章 操作系统操作系统 (8) 其它。 由于在内存中同时存在多个进程，为了实现对进程的管理，系统将所有进程的PCB排成若干个队列。通常，系统中进程队列分成如下3类： (1) 就绪队列。整个系统一个，所有处于就绪状态的进程的PCB都按照某种原则排在该队列中。进程入队和出队的次序与处理机调度算法有关。在有些系统中，就绪队列可能有多个。第第5 5章章 操作系统操

48、作系统 (2) 等待队列。每一个等待事件一个队列，当进程等待某一事件时，其PCB就进入与该事件相应的等待队列。当某事件发生时，与该事件相关的一个或多个进程的PCB离开相应的等待队列，进入就绪队列。 (3) 运行队列。在单机系统中整个系统一个队列。实际上，一个运行队列中只有一个进程，可用一个指针指向该进程的PCB。 三种不同进程队列的PCB链接方式如图5-5所示。 第第5 5章章 操作系统操作系统图5-5 三种不同进程队列的PCB链接方式第第5 5章章 操作系统操作系统 5进程间的相互作用 (1) 相关进程和无关进程。 多道程序系统中同时运行的并发进程通常有多个。在逻辑上具有某种联系的进程称为相

49、关进程，在逻辑上没有任何联系的进程称为无关进程。第第5 5章章 操作系统操作系统 (2) 进程间的相互作用。 多道程序系统中并发运行的进程之间存在着相互制约关系，这种相互制约的关系称做进程间的相互作用。进程之间相互作用有两种方式：直接相互作用和间接相互作用。直接相互作用只发生在相关进程之间；间接相互作用可发生在相关进程之间，也可发生在无关进程之间。第第5 5章章 操作系统操作系统 5.2.3 进程间的通信 进程是操作系统中可以独立运行的单位，但是由于处于同一个系统之中，进程之间不可避免地会产生某种联系，例如，竞争使用共享资源，而且有些进程本来就是为了完成同一个作业而运行的。因此，进程之间必须互

50、相协调，彼此之间交换信息，这就是进程之间的通信。第第5 5章章 操作系统操作系统 1进程的同步与互斥 1) 进程的同步 系统中的各进程可以并发共享资源，从而使系统资源得到充分利用，但是共享资源往往使并发进程产生某种与时间有关的错误，或者说与速度有关的错误。例如，有A、B两个进程，A进程负责从键盘读数据到缓冲区，B进程负责从缓冲区读数据进行计算。要完成取数据并计算的工作，A进程和B进程要协同工作，即B进程只有等待A进程把数据送到缓冲区后才能进行计算，第第5 5章章 操作系统操作系统 A进程只有等待B进程发出已把缓冲区数据取走的信号之后才能从键盘向缓冲区中送数据，否则就会出现错误。这是一个进程同步

51、的问题，如图5-6所示。 进程同步是指进程之间一种直接的协同工作关系，这些进程相互合作，共同完成一项任务。进程间的直接相互作用构成进程的同步。 第第5 5章章 操作系统操作系统图5-6 进程同步示意图 第第5 5章章 操作系统操作系统 2) 进程的互斥 进程互斥。在系统中，许多进程常常需要共享资源，而这些资源往往要求排它地使用，即一次只能为一个进程服务。因此，各进程间互斥使用这些资源，进程间的这种关系是进程的互斥。进程间的间接相互作用构成进程互斥，例如，多个进程在竞争使用打印机、一些变量、表格等资源时，表现为互斥关系。第第5 5章章 操作系统操作系统 临界区。系统中一些资源一次只允许一个进程使

52、用，这类资源称为临界资源。而在进程中访问临界资源的那一段程序称为临界区，要求进入临界区的进程之间就构成了互斥关系。为了保证系统中各并发进程顺利运行，对两个以上欲进入临界区的进程，必须实行互斥，为此，系统采取了一些调度协调措施。 系统对临界区的调度原则归纳为当没有进程在临界区时，允许一进程立即进入临界区；若有一个进程已在临界区时，其它要求进入临界区的进程必须等待；进程进入临界区的要求必须在有限的时间内得到满足。第第5 5章章 操作系统操作系统 3) 信号量和P、V操作 用常规的程序来实现进程之间同步、互斥关系需要复杂的算法，而且会造成“忙等待”，浪费CPU资源，为此引入信号量的概念。信号量是一种

53、特殊的变量，它的表面形式是一个整型变量附加一个队列，而且，它只能被特殊的操作(即P操作和V操作)使用。 P操作和V操作都是原语。所谓原语是由若干条机器指令构成的一段程序，用以完成特定功能。原语在执行期间是不可分割的，即原语一旦开始执行，直到执行完毕之前，不允许中断。第第5 5章章 操作系统操作系统 设信号量为S，S可以取不同的整数值，可以利用信号量S的取值表示共享资源的使用情况，或用它来指示协作进程之间交换的信息。在具体使用时，把信号量S放在进程运行的环境中，赋予其不同的初值，并在其上实施P操作和V操作，以实现进程间的同步与互斥。 P操作和V操作定义如下： P(S)： (1) S := S -

54、 1； (2) 若S0，则该进程进入S信号量的队列等待。 V(S)： (1) S := S + 1；第第5 5章章 操作系统操作系统 (2) 若S0，则释放S信号量队列上的一个等待进程，使之进入就绪队列。 通常，信号量的取值可以解释为S值的大小表示某类资源的数量。当S0时，表示还有资源可以分配；当S0时，其绝对值表示S信号量等待队列中进程的数目。每执行一次P操作，意味着要求分配一个资源；每执行一次V操作，意味着释放一个资源。第第5 5章章 操作系统操作系统 4) 用P、V操作实现进程间的互斥 令S初值为1，进程A、B竞争进入临界区的程序可以写成：进程A进程BP(S)；P(S)；临界区临界区V(

55、S)；V(S)；第第5 5章章 操作系统操作系统 5) 用P、V操作实现进程间的同步 如图5-6所示同步关系，设两个信号量S1和S2，且赋予它们的初值S1为1，S2为0，S1表示缓冲区中是否装满信息，S2表示缓冲区中的信息是否取走，程序可写成：进程A进程BP(S2)；P(S1)；把信息送入缓冲区；把信息从缓冲区取走；V(S1)；V(S2)；第第5 5章章 操作系统操作系统 2进程的通信 并发进程在运行过程中，需要进行信息交换。交换的信息量可多可少，少的只是交换一些已定义的状态值或数值，例如利用信号量和P、V操作；多的则可交换大量信息，而P、V操作只是低级通信原语，因此要引入高级通信原语，解决大

56、量信息交换问题。 高级通信原语不仅保证相互制约的进程之间的正确关系，还同时实现了进程之间的信息交换。目前常用的高级通信机制有消息缓冲通信、管道通信和信箱通信。第第5 5章章 操作系统操作系统 1) 消息缓冲通信 基本思想是系统管理若干消息缓冲区，用以存放消息。每当一个进程(发送进程)向另一个进程(接收进程)发送消息时，便申请一个消息缓冲区，并把已准备好的消息送到缓冲区，然后把该消息缓冲区插入到接收进程的消息队列中，最后通知接收进程。接收进程收到发送进程发来的通知后，从本进程消息队列中的一个消息缓冲区，取出所需的信息，然后把消息缓冲区还给系统。第第5 5章章 操作系统操作系统 2) 管道通信 管

57、道通信是由UNIX首创，已成为一种重要的通信方式。管道通信以文件系统为基础。所谓管道，就是连接两个进程之间的一个打开的共享文件，专用于进程之间进行数据通信。发送进程可以源源不断地从管道一端写入数据流，接收进程在需要时可以从管道的另一端读出数据。 在对管道文件进行读写操作过程中，发送进程和接收进程要实施正确的同步和互斥。以确保通信的正确性。管道通信的实质是利用外存来进行数据通信，故具有传送数据量大的优点，但通信速度较慢。第第5 5章章 操作系统操作系统 3) 信箱通信 为了实现进程间的通信，需设立一个通信机制信箱，以传送、接收信件。当一个进程希望与另一进程通信时，就创建一个链接两个进程的信箱，通

58、信时发送进程只要把信件投入信箱，而接收进程可以在任何时刻取走信件。第第5 5章章 操作系统操作系统 5.2.4 进程控制 进程有一个从创建到消亡的生命周期，进程控制的作用就是对进程在整个生命周期中各种状态之间的转换进行有效的控制。进程控制是通过原语来实现的，用于进程控制的原语一般有创建原语、撤消原语、挂起原语、激活原语、阻塞原语以及唤醒原语等。第第5 5章章 操作系统操作系统 1创建原语 一个进程可以使用创建原语创建一个新的进程，前者称为父进程，后者称为子进程，子进程又可以创建新的子进程，从而使整个系统形成一个树型结构的进程家族。 创建一个进程的主要任务是建立进程控制块PCB。具体操作过程是：

59、先申请一空闲PCB区域，将有关信息填入PCB，置该进程为就绪状态，最后把它插入就绪队列中。第第5 5章章 操作系统操作系统 2撤消原语 当一个进程完成任务后，应当撤消它，以便及时释放它所占用的资源。撤消进程的实质是撤消PCB，一旦PCB撤消，进程就消亡了。 具体操作过程是：找到要被撤消进程的PCB，将它从所在队列中销去，撤消属于该进程的一切“子孙进程”，释放被撤消进程所占用的全部资源，并销去被撤消进程的PCB。第第5 5章章 操作系统操作系统 3阻塞原语 某进程执行过程中，需要执行I/O操作，则由该进程调用阻塞原语把进程从运行状态转换为阻塞状态。 具体操作过程是：由于进程正处于运行状态，因此首

60、先应中断CPU执行，把CPU的当前状态保存在PCB的现场信息中，把进程的当前状态置为等待状态，并把它插入到该事件的等待队列中去。第第5 5章章 操作系统操作系统 4唤醒原语 一个进程因为等待事件的发生而处于等待状态，当等待事件完成后，就用唤醒原语将其转换为就绪状态。 具体操作过程是：在等待队列中找到该进程，置进程的当前状态为就绪状态，然后将它从等待队列中撤出并插入到就绪队列中排队，等待调度执行。 第第5 5章章 操作系统操作系统 5.2.5 进程调度 进程调度即处理机调度。在多道程序设计环境中，进程数往往多于处理机数，这将导致多个进程互相争夺处理机。进程调度的任务是控制、协调进程对CPU的竞争

61、，按照一定的调度算法，使某一就绪进程获得CPU的控制权，转换成运行状态。实际上，进程调度完成把一台物理的CPU转变为多台虚拟的(或逻辑的)CPU的工作。第第5 5章章 操作系统操作系统 1进程调度的时机 引起进程调度的原因与操作系统的类型有关，大体可归结为以下几种： (1) 正在执行的进程运行完毕； (2) 正在执行的进程提出I/O请求； (3) 正在执行的进程执行某种原语操作(如P操作)导致进程阻塞； (4) 在分时系统中时间片用完；第第5 5章章 操作系统操作系统 以上都是在CPU为不可剥夺方式下引起进程调度的原因。在CPU是可剥夺方式时，还有下面的原因： (5) 就绪队列中的某个进程的优

62、先级变得高于当前运行进程的优先级时。 所谓可剥夺方式，即指就绪队列中一旦有优先级高于当前运行进程的优先级的进程出现时，便立即进行进程调度，把CPU分配给高优先级的进程。所谓不可剥夺方式，即一旦把CPU分配给一个进程，它就一直占用CPU，直到该进程自己因调用原语操作或等待I/O而进入阻塞状态，或时间片用完时才让出CPU，引起进程调度程序的执行。第第5 5章章 操作系统操作系统 2进程调度算法 进程调度程序的一项重要工作是根据一定的调度算法从就绪队列中选出一个进程，把CPU分配给它。因此，调度算法的好坏直接影响到系统的设计目标和工作效率。通常，考虑调度算法的因素主要是有利于充分利用系统的资源，发挥

63、最大的处理能力；有利于公平地响应每个用户的服务请求；有利于操作系统的工作效率。下面介绍几种常用的调度算法。第第5 5章章 操作系统操作系统 1) 先来先服务 如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在就绪队列的后面，那么先来先服务(FCFS，First Come First Service)总是把当前处于就绪队列之首的那个进程调度到运行状态。也就是说，它只考虑进程进入就绪队列的先后，而不考虑其它因素。FCFS算法简单易行，但性能却不太好。第第5 5章章 操作系统操作系统 2) 最短进程优先 最短进程优先(SPF，Shortest Process First)的基本思想是：进程调度程序

64、总是调度当前就绪队列中的下一个要求CPU时间最短的那个进程运行。和先来先服务算法相比，SPF调度算法能有效地降低平均等待时间和提高系统的吞吐量。第第5 5章章 操作系统操作系统 3) 时间片轮转法 这种算法常用于分时系统中，将CPU的处理时间划分成一个个时间片，轮流地调度就绪队列中的诸进程运行一个时间片。当时间片结束时，就强迫运行进程让出CPU，该进程进入就绪队列，等待下一次调度。同时，进程调度程序又去选择就绪队列中的一个进程，分配给它一个时间片，以投入运行。第第5 5章章 操作系统操作系统 在这个算法中，时间片长度的选择是一个重要问题，它将直接影响系统开销和响应时间。如果时间片长度很小，则调

65、度程序剥夺处理机的次数频繁，加重系统开销；反之，如果时间片长度选择过长，用户进程将不能及时得到响应，比方说一个时间片就能保证就绪队列中所有进程都执行完毕，轮转法就退化成先来先服务算法。设置时间片大小通常要考虑到系统的响应时间，用户的数目以及CPU的运算速度等因素。第第5 5章章 操作系统操作系统 4) 优先级法 进程调度程序总是调度当前处于就绪队列中优先级最高的进程，使其投入运行。进程的优先级通常由进程优先数(整数)表示，数大优先级高还是数小优先级高取决于规定。例如UNIX系统规定优先数越大优先级越低，优先数越小优先级越高。 进程优先数的设置可以是静态的，也可以是动态的。静态优先数是在进程创建

66、时根据进程初始特性或用户要求而确定的，而且该优先数在进程的整个生命周期内一直不变。动态优先数则是指在进程创建时先确定一个初始优先数，以后在进程运行中随着进程特性的改变，不断修改优先数。第第5 5章章 操作系统操作系统 静态优先数方法虽然简单，但有可能导致某些低优先级的进程无限期地等待，尤其在高优先级的进程不断进入就绪队列的情况下，使等待CPU的低优先级进程更多，等待时间更长。动态优先数方法是按照某种原则使各进程的优先级随着时间而改变，例如随等待时间增长优先级也跟着提高、随着使用CPU时间的增长优先级跟着下降，就是一种较好的策略，等待了较长时间的进程，总会因其优先级不断地提高而被调度运行。 优先

67、级算法又可与不同的CPU方式结合起来，形成可剥夺式优先级算法和不可剥夺式优先级算法。第第5 5章章 操作系统操作系统 5.2.6 进程死锁 1死锁概念 在多道程序系统中，虽可通过多个进程的并发执行来改善系统的资源利用率和提高系统的处理能力，但可能发生一种危险死锁。所谓死锁(Deadlock)，是指多个进程因竞争资源而形成的一种僵持局面，若无外力作用，这些进程都将永远不能再向前推进。例如，设有1台打印机和1台磁带机，有两个进程P1和P2，它们分别占用打印机和磁带机，当P1申请已被P2占用的磁带机，而P2申请已被P1占用的打印机这种情况出现时，P1和P2僵持不下，称为进程死锁。 第第5 5章章 操

68、作系统操作系统 此时操作系统中虽然有死锁进程出现，但系统中其它进程仍然正常工作。如果系统中所有进程都进入死锁，即没有一个进程能前进的话，称为系统死锁，这种情况是很少见的。人们平常说的“死锁”，一般指进程死锁，它至少涉及两个进程。 产生死锁的根本原因有两个。原因之一是系统内的资源数量不足。因为倘若资源数量无限的话，进程之间就不会发生资源竞争，当然不会形成互不相让的僵持局面。原因之二是进程推进的顺序不当。假如上述进程P2在P1已释放了打印机后才开始运行的话，则不会有竞争出现，P2便能安全地运行完毕。第第5 5章章 操作系统操作系统 显然，任何一个计算机系统的资源都是有限的，资源竞争是不可避免的，换

69、句话说，死锁的根本原因之一是固有的。进程的特性之一就是异步性，因此无法预知各进程的推进速度，也就无法控制进程之间的推进顺序，所以，死锁的根本原因之二也是固有的。第第5 5章章 操作系统操作系统 进程的死锁问题可以用有向图更加准确而形象地描述，这种有向图称为资源分配图。有向图中，用圆圈表示进程，用方框表示每类资源，方框中的圆点表示该类资源的数量。申请边为从进程到资源的有向边，表示进程申请一个资源单位；分配边为从资源到进程的有向边，表示有一个资源单位分配给进程。申请边仅能指向方框，表示申请时不具体指定该类资源的哪一个，而分配边必须由方框中的圆点引出，表明哪一个资源已被占有。第第5 5章章 操作系统

70、操作系统图5-7 资源分配图(含环路) 第第5 5章章 操作系统操作系统 例如，对于P=P1,P2,P3，R=R1,R2,R3,R4，E=，它的资源分配图如图5-7所示。 可以证明，如果资源分配图中没有环路，则系统中没有死锁；如果图中存在环路，则系统中可能存在死锁。如果每个资源类中均只包含一个资源，则环路的存在即意味着死锁的存在，此时，环路是死锁的充分必要条件。在图5-7中，有两个环：第第5 5章章 操作系统操作系统 P1R1P2R3P3R2P1 P2R3P3R2P2 环中资源类不全为1(R2有2个)，P1、P2、P3均处于死锁状态。如果删除边，就不会发生死锁。 进一步研究表明，在一个计算机系

71、统中，死锁的产生有如下4个必要条件： (1) 互斥使用。在一段时间内，1个资源只能由1个进程独占使用，若别的进程也要求使用该资源，则必须等待直至其占用者释放。 第第5 5章章 操作系统操作系统 (2) 不剥夺性(不可抢占)。进程所占用的资源在未使用完之前，不能被其它进程强行剥夺，而只能由占用进程自身释放。 (3) 保持和请求。允许进程在不释放其已占用资源的情况下继续请求并等待分配新的资源。 (4) 循环等待。在进程资源图中存在环路，环路中的进程形成等待链。当且仅当每类资源只有1个时，环路才是进程死锁的充分必要条件。第第5 5章章 操作系统操作系统 2死锁排除 1) 死锁预防 死锁预防是通过破坏

72、4个必要条件中的1个或多个以确保系统不会发生死锁。为此，可以采取下列3种预防措施：采用资源的静态预分配策略，破坏“保持和请求”条件；允许进程剥夺使用其它进程占有的资源，从而破坏“不剥夺性”条件；采用资源有序分配法，破坏“环路”条件。第第5 5章章 操作系统操作系统 2) 死锁避免 死锁预防是设法至少破坏产生死锁的必要条件之一，严格地防止死锁的出现。而死锁的避免则不那么严格地限制产生死锁必要条件的存在(因为即使死锁必要条件成立，也未必一定会发生死锁)，只是在系统运行过程中小心地避免死锁的最终发生。最著名的死锁避免算法是Dijkstra提出的银行家算法。第第5 5章章 操作系统操作系统 (1) 安

73、全状态。在T0时刻系统是安全的或系统处于安全状态，仅当存在一个由系统中所有进程构成的进程序列，对于每一个进程Pi(i=1,2, ,n)满足：它以后尚需要的资源数量不超过系统中当前剩余资源与所有进程Pj(ji)当前占有资源数量之和。如果不存在这样的序列，则说系统处于一种不安全状态。第第5 5章章 操作系统操作系统 例如，考虑一个系统，它有1类设备12台磁带机和3个进程P0，P1，P2。进程P0需10台磁带机，P1需4台而P2需9台。在T0时刻，P0已占用5台，P1占2台，P2占2台，有3台闲置。可以找到安全序列，因此T0时刻系统是安全的。假如在T0时刻P0占5台，P1占2台，P2占3台，将不存在

74、任何安全序列，系统处于不安全状态。 安全状态是没有死锁的状态。不安全状态不一定是死锁状态，但是，随着系统的推进，不安全状态一定会转变为死锁状态。因此死锁避免的实质在于：如何使系统不进入不安全状态。第第5 5章章 操作系统操作系统 (2) 银行家算法。该算法对于进程发出的每一个系统能够满足的资源申请命令加以动态检查。如果发现分配资源后，系统进入不安全状态，则不予分配；若分配资源后，系统仍处于安全状态，则分配资源。所以，死锁避免策略主要是根据系统是否处于安全状态，来决定分配资源与否。 与死锁预防策略相比，死锁避免策略提高了资源利用率，但增加了系统开销。第第5 5章章 操作系统操作系统 3) 死锁检

75、测 死锁检测方法是对资源的分配不加限制，即允许死锁发生。但系统定时地运行一个“死锁检测”程序，判断系统是否已发生死锁，若检测到死锁发生，则设法加以解除。 何时进行死锁检测主要取决于死锁发生的频率和死锁所涉及的进程个数。如果死锁发生的频率高，则死锁检测的频率也应很高，否则影响系统资源的利用率，也可能使更多的进程陷入死锁。当然，死锁检测会增加系统开销。 通常，可在如下时刻进行死锁检测：进程等待时检测，定时检测或系统利用率降低时检测。第第5 5章章 操作系统操作系统 4) 死锁解除 死锁解除与死锁检测配套使用，通常有以下做法： (1) 撤消处于死锁状态的进程并收回它们的资源。具体地说，选择占用资源多

76、的进程作为撤消对象或者选择撤消代价最小的那个进程。如果撤消一个进程不足以解除死锁，则继续再选另一个撤消对象，直到解除死锁。 (2) 资源剥夺方法。即从死锁进程中选一个进程，剥夺它的资源(一个或多个资源)但不撤消它，把这些资源分配给别的死锁进程，反复做这一工作直到死锁解除。由于进程未被撤消，解除死锁的代价比较小。第第5 5章章 操作系统操作系统 (3) 进程回退。即让一个或多个进程回退到足以解除死锁的地步。它比资源剥夺法温和，因为进程回退时是自愿释放资源而不是被剥夺资源。回退方法要求系统保持更多的有关进程运行的历史信息。 应当指出，死锁解除的代价是不小的。例如，进程回退时要收回它已发出的消息，但

77、消除该消息产生的影响几乎是不可能的。第第5 5章章 操作系统操作系统5.3 存存 储储 管管 理理 存储管理是操作系统的重要组成部分，它负责存储器的管理。存储管理主要是指对内存空间的管理(外存管理见文件系统)。内存空间一般分为两部分：系统区和用户区。系统区存放操作系统、一些标准子程序、例行程序和系统数据等；用户区存放用户的程序和数据等。存储管理主要是对内存中用户区进行管理。第第5 5章章 操作系统操作系统 5.3.1 存储管理的功能 存储管理的主要目的是既要有利于内存的充分利用，又要方便用户的使用。从这个目标出发，存储管理程序应有如下一些功能。 1存储空间的分配和回收 任何进程要在CPU上执行

78、，都必须首先装入内存，需要一定数量的存储单元用以存放程序和数据。因此，存储管理程序应采用一定的方法，把内存划分为若干部分，在收到请求后，为进程分配内存空间。进程运行结束时，存储管理程序应将其所占用的内存空间收回。第第5 5章章 操作系统操作系统 存储管理设置一张表格记录内存的使用情况，即哪些区域尚未分配，哪些区域已经分配以及分配给哪些进程等。系统根据申请者的要求并按一定策略分析内存空间的使用情况，找出足够的空间分配给申请者，并修改表格的有关项。若不能满足申请要求，则让申请者处于等待内存资源的状态，直到有足够的内存空间时再实施分配。当内存中某进程撤离或主动归还内存时，存储管理要进行一系列操作回收

79、内存空间，使之成为可供分配的空闲区域(也叫自由区)，然后修改表格的有关项。第第5 5章章 操作系统操作系统 2存储保护与共享 存储共享是指两个或多个进程共用内存中相同的区域，其目的是节省内存空间，实现进程间通信，提高内存空间的利用效率。存储共享的内容可以是程序的代码，也可以是数据，如果是代码共享，则共享的代码必须是纯代码，或称“可再入代码”，即它在运行过程中不修改自身。 由于各个用户程序和操作系统同在内存，因而一方面要求各用户程序之间不能互相干扰，另一方面用户程序也不能破坏操作系统的信息。因此，为使系统正常运行，必须对内存中的程序和数据进行保护。第第5 5章章 操作系统操作系统 1) 防止地址

80、越界 每个进程都具有其相对独立的进程空间，如果进程在运行时所产生的地址超出其地址空间，则发生地址越界。地址越界可能侵犯其它进程的空间，影响其它进程的正常运行；也可能侵犯操作系统空间，导致系统混乱。因此，对进程所产生的地址必须加以检查，发生越界时产生中断，由操作系统进行相应处理。第第5 5章章 操作系统操作系统 2) 防止操作越权 对于允许多个进程共享的公共区域，每个进程都有自己的访问权限。例如，有些进程可以执行写操作，而其它进程只能执行读操作等。因此，必须对公共区域的访问加以限制和检查。 存储保护一般以硬件保护机制为主，软件为辅，因为完全用软件实现系统开销太大，速度成倍降低。当发生越界或非法操

81、作时，硬件保护机制产生中断，进入操作系统处理。第第5 5章章 操作系统操作系统 3地址重定位(地址映射) 由于用户在编写程序时并不知道自己的程序会在内存的什么位置，因此在实际运行用户程序时，必须要将用户程序中的有效地址实际映射到内存的某个存储区的某个单元，这件工作虽然主要由装配程序或硬件映射机构来实现，但作为系统中的存储管理程序也要提供相应的软件支持。第第5 5章章 操作系统操作系统 1) 实存储器和虚存储器 实存储器是计算机系统中配置的实际物理存储器，通常有3类： (1) 内存储器，又称主存储器。它接收数据和保存数据，而且能根据命令直接存取数据。 (2) 外存储器，也称辅助存储器。它是为了弥

82、补内存容量不足而使用的存储空间，通常采用大容量的磁盘。第第5 5章章 操作系统操作系统 (3) 高速缓存。它是处于内存和CPU之间的高速小容量存储器。 虚存储器有两层含义，一是指用户程序的逻辑地址构成的地址空间；二是指当内存容量不满足用户要求时，采用一种将内存空间与外存空间有机地结合在一起，利用内外存自动调度的方法构成的一个大的存储器，从而给用户程序提供更大的访问空间。第第5 5章章 操作系统操作系统 2) 逻辑地址和物理地址 用户程序经过编译或汇编形成的目标代码，通常采用相对地址形式，其首地址为零，其余指令中的地址都是相对首地址而定的。这个相对地址就称为逻辑地址或虚拟地址。逻辑地址不是内存中

83、的物理地址，不能根据逻辑地址到内存中存取信息。 物理地址是内存中各存储单元的编号，即存储单元的真实地址，它是可识别、可寻址并实际存在的。第第5 5章章 操作系统操作系统 3) 地址映射 为了保证CPU执行程序指令时能正确访问存储单元，需要将用户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址，这一过程称为地址映射或地址重定位。 地址映射又可分成两类： (1) 静态地址映射。在用户程序被装入到内存的过程中实现逻辑地址到物理地址的转换，以后在程序运行时不再改变，又称静态重定位。第第5 5章章 操作系统操作系统 (2) 动态地址映射。当执行程序过程中要访问指令或数据时，才进行地址变换，又称动态

84、重定位。动态重定位需要依靠硬件地址映射机制完成。第第5 5章章 操作系统操作系统 4存储器的扩充 由于多道程序的引入，使内存资源更为紧张，为了使用户在编制程序时不受内存容量的限制，可以在硬件支持下，将外存作为主存的扩充部分供用户程序使用，这就是内存扩充。内存扩充可以使用户程序得到比实际内存容量大得多的“内存”空间，从而极大地方便了用户。第第5 5章章 操作系统操作系统 采用内存扩充技术，由操作系统处理内存与外存的关系，统一管理内外存，向用户提供一个容量相当大的虚拟存储空间，这就是虚拟存储技术。 为了实现以上这些存储管理的功能，有很多存储管理的方式，本节主要讨论几种常用的管理方式。第第5 5章章

85、 操作系统操作系统 5.3.2 分区存储管理 分区存储管理是满足多道程序运行的最简单的存储管理方案，这种管理方法特别适用于小型机、微型机上的多道程序系统。其基本思想是将内存划分成若干个连续区域，称为分区，在每个分区中装入一个运行作业，用硬件措施保证各个作业互不干扰。分区的划分方式有固定分区方式，可变分区方式以及可重定位分区方式。第第5 5章章 操作系统操作系统 1固定分区方式 也称静态分区，是事先将可分配的内存空间划分成若干个固定大小的连续区域，每个区域大小可以相同，也可以不同。当某一作业要调入内存时，存储管理程序根据它的大小，找出一个适当的分区分配给它。如果当时没有足够大的分区能容纳该作业时

86、，则通知作业调度程序挑选另一作业。为了说明各分区的分配和使用情况，在内存中设置了一张分区说明表，如图5-8所示。第第5 5章章 操作系统操作系统图5-8 固定分区与分区说明表(a) 固定分区；(b) 分区说明表第第5 5章章 操作系统操作系统 固定分区方式虽然简单，但由于一个作业的大小，不可能刚好等于某个分区的大小，故内存利用率不高。每个分区剩余的空白空间，称为“碎片”。 2可变分区方式 也称动态分区，这种方式是在作业将要装入内存时，按作业的大小来划分分区。即根据作业需要的内存量查看内存是否有足够大的内存空闲区；若有，则按需要建立一个分区分配给该作业；若无，则令该作业等待。由于分区的大小是按装

87、入作业的实际需要量来定的，所以克服了固定分区的缺点，提高了内存的利用率。第第5 5章章 操作系统操作系统 随着作业的装入和撤离，内存中分区的数目和大小将不断地发生变化。为了方便内存的分配和回收，可以设置两张分区说明表，一张用于记录已分配的区域情况，另一张用于记录空闲区域的情况(称为空闲区表)，如图5-9所示。进行内存分配时，系统首先查找空闲区表，找到一个空闲区，并根据用户进程对内存申请长度，将该空闲区分割成两部分：一部分的长度与所申请长度相同，将其分配给申请进程；另一部分的长度为原长度与分配长度之差，仍记入空闲区表中，同时调整表中相应的起始地址等信息。第第5 5章章 操作系统操作系统 图5-9

88、 可变分区及其分配表(a) 可变分区；(b) 已分配区域说明表；(c) 空闲区表第第5 5章章 操作系统操作系统 系统在寻找空闲区时可采用以下3种分配算法： (1) 最先适应算法。根据申请，在空闲区表中选取第一个满足申请长度的空闲区。此算法简单，可以快速做出分配决定。 (2) 最佳适应算法。根据申请，在空闲区表中选择能满足申请长度的最小空闲区。此算法最节约空间，因为它尽量不分割大的空闲区。其缺点是可能会形成很多很小的空闲区域。第第5 5章章 操作系统操作系统 (3) 最坏适应算法。根据申请，在空闲区表中选取能满足申请要求的最大的空闲区。此算法的出发点是：在大的空闲区中装入信息后，分割剩下的空闲

89、区相对也大，还能用于装入新的信息。该算法的优点是可以避免形成碎片；缺点是分割大的空闲区后，再遇到较大的申请时，无法满足的可能性较大。第第5 5章章 操作系统操作系统 为实现地址映射和存储保护，系统为当前正在运行的用户程序提供一对硬件寄存器：基址寄存器和限长寄存器。基址寄存器用来存放用户程序在内存的起始地址，限长寄存器用来存放用户程序的长度。用户程序运行时，系统根据用户程序提供的相对地址和基址寄存器内容，形成一个访问内存的物理地址，如图5-10所示。同时，将形成的地址与限长寄存器进行比较，检查是否发生地址越界。第第5 5章章 操作系统操作系统图5-10 动态地址映射与存储保护第第5 5章章 操作

90、系统操作系统 3可重定位分区方式 正如前面所讲到的，可变分区与固定分区方式相比，内存空间利用率要高些。但是，总会存在着一些分散的较小的空闲区，即内存碎片，它们存在于已分配区之间，不能充分利用。解决这些“碎片”问题的最简单方法就是在适当时候，移动内存中的某些已分配区，从而把所有的空闲区合并为一个较大的连续区域，这种技术称为“拼接”。拼接后，作业在内存中已移动了位置，为保证作业在新的位置上仍能正确地执行，可采用动态重定位技术，故把这种方式称为可重定位分区方式。这种方式的内存利用率虽然比前两种方式高，但拼接要消耗较多的CPU时间。第第5 5章章 操作系统操作系统 4 覆盖技术 当用户作业大于主存空间

91、时，该作业无法运行，尤其是在多道作业系统中，大程序的研制受到限制。为了在小空间中运行大的作业，许多操作系统采用了覆盖技术。覆盖技术是解决内存不足的一种方法，但它要求用户提供覆盖结构，给用户使用机器带来很多不便。第第5 5章章 操作系统操作系统 要进行覆盖技术的作业按树形结构分成几层，根部为常驻内存部分，其余部分均为可覆盖部分，同一层上的模块在逻辑上是互相独立的，即在同一时间只有其中一个模块被调用，其它模块可以覆盖。覆盖技术常和单用户连续分配、固定和可变分区分配等存储管理技术配合使用，广泛用于小型、微型机系统中。 将内存划分为若干个分区是为了满足多道程序设计的需求。如果是单道系统，则对内存的用户

92、区不必再划分，这就是单一连续区存储管理方案。一些单用户单任务的微型计算机系统，就是采用了单一连续区存储管理方案。第第5 5章章 操作系统操作系统 5.3.3 页式存储管理 在分区管理时，一道作业要占用内存的一个或几个连续的分区。因此当内存的连续空闲区域不够存放一道作业时，就得大量移动已在内存中的信息。这不仅不方便，而且大大增加了系统的开销。为了克服上述管理的不足，1961年曼彻斯特大学的Arlas研究小组在Atlas计算机上首先采用了分页存储管理技术。第第5 5章章 操作系统操作系统 1基本原理 分页存储管理的基本原理是把内存划分成若干相同大小的存储区域，每个区域称为一个“块”；把用户作业地址

93、空间也按同样大小分成若干“页”；系统以块为单位把内存分配给各作业的各个页，每个作业占有的内存块无需连续。第第5 5章章 操作系统操作系统 内存块有时也称为物理页面，所有的内存块从0开始编号，称做内存块号，每个内存块内亦从0开始依次编址，称为块内地址或块内位移量。每个用户作业的各个逻辑页面也从0开始编号，称做逻辑页号或页号；每个逻辑页面内也从0开始依次编址，称为页内地址或页内位移量。用户作业的逻辑地址由页号和页内地址两部分组成：页号P页内地址D第第5 5章章 操作系统操作系统 页面大小的选择直接影响地址转换和页式存储管理的性能。如果页面太大，以至于和作业地址空间相差无几，这种方法就变成了可重定位

94、分区方法的翻版；反之，如果页面太小，则增加了系统的开销。页面大小一般取2的整数次幂，这样系统就可将地址的高位部分定义成页号，低位部分定义成页内地址。对用户作业地址空间的分页是系统自动进行的，即对用户是透明的。第第5 5章章 操作系统操作系统 2实现方法 在分页系统中，为了保证在连续的逻辑地址空间中的作业能在不连续的物理地址下正确运行，系统为每个程序作业建立一个地址变换表，简称页表。页表中的每一个表项由两部分组成：页号和该页所对应的物理块号。程序作业的地址空间有多少页，它的页表中就登记多少行，且按逻辑页的顺序排列。页表存放在内存系统区内。 页式存储管理的地址映射如图5-11所示。当CPU访问某一

95、逻辑地址时，硬件自动把页号与页表长度进行比较，如果合法才进行地址转换，否则产生越界中断。 第第5 5章章 操作系统操作系统图5-11 页式存储管理的地址映射第第5 5章章 操作系统操作系统 例如，设程序的逻辑地址空间划分为1024字节大小的若干页，一个程序作业占用3页，由管理程序将其分别分配给主存空间的第2、第3和第8块。程序作业的具体任务是从逻辑地址为2500处取得一个数据。图5-12给出了该例逻辑空间与主存空间的对应关系。第第5 5章章 操作系统操作系统图5-12 逻辑地址、主存空间及页表关系 第第5 5章章 操作系统操作系统 图中各部分的具体关系是这样的：当主存管理程序调度到用户作业时，

96、首先为它建立一个页表，并把页表的起始地址和长度装入一个控制寄存器中。假设用户的作业中包含一条从主存读取数据的指令LOAD L，2500，系统自动把地址码2500转换成两部分，即2500=21024+452，其中2为页号，1024是页的大小，452是页内偏移量。产生物理地址时，系统通过控制寄存器确定页表的起始位置，然后找到页表中页号为2的表项，由此知对应的主存块号为8。系统把块号8与页内偏移量拼接在一起，就得到了8644这一物理地址，也就是12345这一数据在主存中的实际存放位置。第第5 5章章 操作系统操作系统 3快表 从地址映射过程中可以看出，共需两次访问内存。第一次访问页表，得到数据的物理

97、地址，第二次才是存取数据，显然增加了访问时间。为了提高存取速度，通常在CPU和主存之间增设高速小型的联想寄存器组，称之为“快表”。快表中存放现行进程页表中最近常用的部分表项，随着进程的推进，快表内容动态更新。第第5 5章章 操作系统操作系统 当某一用户程序需要存取数据时，根据该数据所在页号在快表中找出对应的物理块号，然后拼接页内地址，以形成物理地址；如果在快表中没有相应的页号，则地址映射仍然通过内存中的页表进行，得到物理块号后须将该物理块号填到快表的空闲单元中，若无空闲单元，则根据淘汰算法淘汰一行后填入。实际上查找快表和查找内存页表是并行进行的，一旦发现快表中有与所查页号一致的页号就停止查找内

98、存页表。第第5 5章章 操作系统操作系统 页表管理也给信息共享提供了条件。通过为多个用户作业设置不同页表的方式，可以使它们共用主存中的同一批信息。但实现共享必须提供对信息的安全保护，为此，可在页表中增加一些控制信息，如增加标明读写权限的特征位，或为每个作业设置保护字，通过保护字的动态比较，判断操作的合法性。第第5 5章章 操作系统操作系统 5.3.4 段式存储管理 在页式存储管理方案中，为作业分配的主存空间地址可以是不连续的，但作业的逻辑空间地址仍然要求是连续的。而在实际中，一个用户的程序往往是由若干功能相对独立的模块组成的，如主程序模块、子程序模块、数据块等。我们把各种相对独立的程序和数据模

99、块称为段。每个段都具有完整的逻辑意义。段式存储管理就是以段作为基本单位的主存管理方法。第第5 5章章 操作系统操作系统 1基本原理 在段式存储管理下，每个用户程序可由若干段组成，每段可以对应于一个过程、一个程序模块或一个数据集合，段间的地址可以是不连续的，但每一段内的地址是连续的。将一个用户程序的所有逻辑段从0开始编号，称为段号，每一段内的所有单元从0开始编址，称为段内地址。用户程序地址空间的每一个单元都用二维地址表示，即逻辑地址由段号和段内地址两部分组成：段号S段内地址D第第5 5章章 操作系统操作系统 系统以段为单位进行内存分配，为每一个逻辑段分配一块连续的内存区域，逻辑上连续的段在内存中

100、不一定连续存放。第第5 5章章 操作系统操作系统 2实现方法 为了实现逻辑地址到物理地址的变换，系统为每个用户程序建立一张段表，记录各段的段号、段长以及内存起始地址等内容。用户程序有多少逻辑段，该段表里就登记多少行，且按逻辑段的顺序排列。段表存放在内存系统区里。 段式存储管理的地址映射如图5-13所示。当CPU访问某一逻辑地址时，硬件自动把段号与段表长度进行比较，还要将段内地址与段表内该段长度进行比较，如果合法才进行地址转换，否则产生越界中断。为了加快地址映射速度，亦可以采用快表技术。 第第5 5章章 操作系统操作系统图5-13 段式存储管理的地址映射 第第5 5章章 操作系统操作系统 从实现

101、技术上看，段式管理与页式管理很相似，但在概念上二者有本质上的不同。段是用户可知的逻辑单位，它由用户在程序设计时确定，而页是用户不可知的物理单位，页的大小由操作系统事先确定。第第5 5章章 操作系统操作系统 3段的动态链接和装配 用户设计的一个大型程序可能包含若干段，在实际运行时，需要把这些段装配链接形成一个整体。一种方法是在每次运行前，一次性的将所有段链接好，这种方法称为段的静态链接。采用静态链接要求把所有的程序段，无论在运行中是否被调用，统统装入主存中，这将消耗大量机时和空间，显然是不合理的，因此，为了提高主存利用率，引进动态链接。所谓动态链接，是指在一个程序开始运行时，只将主程序装配好并调

102、入内存，在程序运行过程中若要访问一个新的模块时，再装配此模块，并与主程序链接起来。第第5 5章章 操作系统操作系统 4段的共享与保护 段式存储管理可以方便地实现内存信息的共享并进行有效的内存保护。这是因为段是按逻辑意义来划分的，可以按段名访问的缘故。 1) 段的共享 如果多个用户进程或作业需要共享某段程序或数据，可以使用不同的段名，在各自的段表中填入已在内存中的共享段的起始地址，并设置适当的读写控制权，就可以做到共享一个内存段的信息。第第5 5章章 操作系统操作系统 另外，也存在多次重复执行某段程序的情况，即某个进程在未执行完该段程序前，其它并发进程又开始执行该程序，这就要求该段程序在执行中，

103、其指令和数据不能被修改。另外，段表中还应设有相应的共享位用来判别该段程序是否正被某个进程调用。显然一个正在被某个进程使用或即将被某个进程使用的共享段是不应该被调出内存的。 第第5 5章章 操作系统操作系统 2) 段的保护 在多道程序的情况下，为了保证段的共享并使程序顺利执行，必须实行对段的保护，一般有以下措施： (1) 利用段表及段长来实现段的保护，防止程序执行时地址越界。 (2) 存取权限保护法。在段表中设有“存取权限”一项，可对程序的访问权限进行各种必要的限制。 (3) 存储保护键保护。由于I/O通道对存储器访问是不经过段表的，因此有的机器还采用存储保护键保护。第第5 5章章 操作系统操作

104、系统 5.3.5 段页式存储管理 前面所介绍的页式和段式存储管理方式都各有其优缺点。页式系统能有效地提高内存利用率，而段式系统则能很好地满足用户需求。如果对两种存储管理方式“各取所长”后，则可以形成一种新的存储管理方式。这种新系统既具有分段系统便于实现、分段可共享、易于保护、可动态链接等一系列优点，又能像分页系统那样很好地解决内存的外部碎片问题，以及为各个分段可离散地分配内存等问题。这种结合段式管理及页式管理优点的存储管理方式称为段页式存储管理。第第5 5章章 操作系统操作系统 1基本原理 段页式系统的基本原理是段式和页式原理的结合，即先将用户程序分为若干个段，再把每个段划分成若干页；内存空间

105、采用页式方法来分配和管理，即把内存空间划分为若干个与页大小相等的块。内存空间是以页为基本单位分配给每个用户程序的，在逻辑上相邻的页面，在内存中不一定相邻。图5-14是段页式系统中的一个作业地址空间示意图。在段页式系统中，其有效地址结构由段号、段内页号及页内地址三部分组成，如图5-15所示。第第5 5章章 操作系统操作系统图5-14 段页式系统的作业地址空间 第第5 5章章 操作系统操作系统图5-15 段页式系统的有效地址结构 第第5 5章章 操作系统操作系统 2实现方法 在段页式系统中，为了实现逻辑地址到物理地址的变换，系统为每个用户程序建立一张段表，用于记录各段的段号、页表起始地址和页表长度

106、；为用户程序中的每一段各建立一张页表，用于记录该段中各页与物理块号之间的对应关系。 段页式存储管理的地址映射如图5-16所示。为了加快地址映射速度，亦可以采用快表技术，快表中保存正在运行进程的段表和页表的部分表项。第第5 5章章 操作系统操作系统 图5-16 段页式存储管理的地址映射 第第5 5章章 操作系统操作系统 段页式系统综合了段式和页式各自的优点。其缺点是增加了硬件成本，并且软件也变得复杂，占用了不少处理机时间。此外，段表、页表和页内零头仍占用了不少存储空间。第第5 5章章 操作系统操作系统 5.3.6 虚拟存储管理 前几节介绍的各种存储管理方案有一个共同的问题，即当一个参与并发执行的

107、进程运行时，其整个程序必须都在内存，因而存在如下缺点：若一个进程的程序比内存可用空间还大，则该程序无法运行；由于程序运行的局部特性，一个进程在运行的任一阶段只需使用所占存储空间的一部分，因此，未用到的内存区域就被浪费。其实，没有必要把进程空间的全部信息装入内存，在装入部分信息的情况下，只要安排得法，不仅可以运行，而且能够提高主存利用率。第第5 5章章 操作系统操作系统 所谓“扩充”主存是指在较小的主存条件下运行大于主存的作业，给用户造成主存很大的假象。有两种方法能扩充主存：覆盖技术和虚拟存储技术。覆盖技术要求给出不同时段上运行部分程序模块的详细说明(覆盖说明)，操作系统根据覆盖说明，把后继时段

108、中的程序模块覆盖在前一时段中已运行过且不再使用的模块所占用的主存区域。因为提供覆盖说明的难度不亚于编程，所以眼下少见这种方法。第第5 5章章 操作系统操作系统 引进虚拟存储技术，其基本思想是利用大容量的外存来扩充内存，产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间，以便能够有效地支持多道程序系统的实现和满足大型作业运行的需要，从而增强系统的处理能力。第第5 5章章 操作系统操作系统 1虚拟存储器 1) 局部性原理 虚拟存储管理的效率与程序局部性程度有很大关系。早在1968年P.Denning就指出，程序在执行时将呈现出局部性规律，据统计，在一段时间内，其程序执行往往呈现高度的局部性，

109、包括时间局部性和空间局部性。 时间局部性是指若一条指令被执行，则在不久的将来，它可能再被执行。空间局部性是指一旦一个存储单元被访问，那么它附近的单元也将很快被访问。第第5 5章章 操作系统操作系统 众所周知，进程的某些程序段在进程整个运行期间，可能根本不使用(如出错处理等)，因而没有必要调入内存；互斥执行的程序段在进程运行时，系统只执行其中一段，因而没必要同时驻留内存；在进程的一次运行中，有些程序段执行完毕，从某一时刻起不再使用，因而没必要再占用内存区域。根据以上分析可以看出，程序局部性原理是虚拟存储技术引入的前提。第第5 5章章 操作系统操作系统 2) 虚拟存储器的定义 基于局部性原理，一个

110、作业在运行之前，没有必要全部装入内存，而仅将当前要运行的那部分页面或段装入内存，其余部分暂时留在磁盘上，作业便可运行。程序在运行时如果所访问的页(段)已调入内存，便可继续运行下去；但如果所访问的页(段)尚未调入内存(称为缺页或缺段)，此时应利用OS所提供的请求调页(段)功能，将它们调入内存，以使进程能继续执行下去。 第第5 5章章 操作系统操作系统 如果此时内存已满，无法再装入新的页(段)，则还须再利用页(段)的置换功能，将内存中暂时不用的页(段)调出至磁盘上，腾出足够的内存空间后，再将所要访问的页(段)调入内存，使程序继续执行下去。这样，便可使一个大的用户程序在较小的内存空间中运行；也可使内

111、存中同时装入更多的进程并发执行。从用户角度看，该系统所具有的内存容量，将比实际内存容量大得多，这样的存储器称为虚拟存储器。第第5 5章章 操作系统操作系统 所谓虚拟存储器，是指仅把作业的一部分装入内存就可运行作业的存储器系统。该存储器系统是指具有请求调入功能和置换功能，并能从逻辑上对内存容量进行扩充。实际上，用户所看到的大容量只是一种感觉，是虚的，故而得名虚拟存储器。其逻辑容量由内存和外存容量之和所决定，其运行速度接近于内存速度。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型计算机系统和超级微型机中。第第5 5章章 操作系统操作系统 2虚拟存储器的实现 虚拟

112、存储器的实现，毫无例外地都是建立在离散分配存储管理方式的基础上的。目前，所有的虚拟存储器都是采用下述方式之一实现的。 1) 请求页式系统 请求页式系统是在页式管理系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统。它允许只装入若干页(而非全部程序)的用户程序和数据，便可启动运行。 第第5 5章章 操作系统操作系统 以后再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上，置换时以页面为单位。 为了能实现请求调页和置换功能，系统必须提供必要的硬件支持。其中，最重要的是： 请求分页的页表机制。它是在纯分页的页表机制上增加若干项而形成的

113、。 缺页中断机构。每当用户程序要访问的页面尚未调入内存时，便产生一缺页中断，以请求OS将所缺的页面调入内存。 地址变换机构。它同样是在纯分页的地址变换机构的基础上发展形成的。第第5 5章章 操作系统操作系统 2) 请求段式系统 请求段式系统是在段式管理系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。它允许只装入若干段(而非所有段)的用户程序和数据，即可启动运行。以后再通过调段功能及段的置换功能，将暂不运行的段调出，同时调入即将运行的段，置换时以段为单位。为了实现请求分段，系统同样需要必要的硬件支持。第第5 5章章 操作系统操作系统 3) 请求段页式系统 请求段页式系统是

114、在段页式管理系统的基础上，通过增加请求调页和页面置换功能，而形成的段页式虚拟存储系统。请求段页式系统的硬件、软件开销都比较大，由于现今硬件、软件技术都有了很大提高，承受较大的开销越来越不成为问题。 本章仅讨论请求页式存储管理系统。第第5 5章章 操作系统操作系统 3交换技术 交换技术又称对换技术，它也是为了解决内存不够的问题提出来的，用于分时、实时及批处理系统中。在分时系统中，当某一作业运行时间到或因其它事件不能继续运行时，它不但要让出CPU，而且还要释放其占用的内存空间，移到外存储器上，直到调度程序再次调用它时，才重新进入主存运行。在实时和批处理系统中，当高优先级的作业要求处理而没有足够的内

115、存空间时，则强迫从主存中移出一个或多个低优先级作业到外存去，当高优先级作业完成后，再将移出的作业重新装入内存。第第5 5章章 操作系统操作系统 必须指出，实现虚拟存储技术需要有一定的硬件条件，其一要有相当量的外存；其二要有一定量的主存；其三要有地址变换机构，力求能快速进行地址转换。虚拟内存管理技术是当前操作系统采用的一种内存管理的实用技术，Microsoft公司的Windows操作系统充分地使用了这一技术。第第5 5章章 操作系统操作系统 5.3.7 请求页式存储管理 请求页式存储管理是对页式管理的改进。首先，在进程开始执行前，不是装入其全部页面，而是只装入几个页面，然后，根据进程执行时的需要

116、，动态地装入其它页面。当主存已被占满而新的页面需要装入时，则依据某种算法置换1个页面。按实际需要装入页面的做法可避免装入那些在进程执行中用不着的页面，比起纯粹的页式管理，无疑节省了主存空间。第第5 5章章 操作系统操作系统 1请求页式的实现 请求页式的全部工作即空闲块分配与回收、页面的换进与换出等都是在指令执行过程中完成的，更准确地说，是在CPU访问主存的过程中完成的。图5-17是请求页式管理下指令的执行过程。第第5 5章章 操作系统操作系统 下面对图5-17做一些说明。CPU给出的逻辑地址(虚地址)可能是指令本身的地址，也可能是指令中操作数的地址，按规定虚地址被分成页号和页内位移两部分。所有

117、访问主存的指令都必须经过地址变换形成物理地址。请求页式的地址变换比页式多了一个“该页在主存吗？”的判别动作。没有这个判别，不能产生对页面的“请求”信号，更不能进入缺页中断处理的软件过程，为了说明该页在不在主存，在页表中增设一个标记位。图5-18是Windows 95的页表格式。第第5 5章章 操作系统操作系统图5-17 请求页式管理下指令的执行过程第第5 5章章 操作系统操作系统图5-18 Windows 95的页表格式 第第5 5章章 操作系统操作系统 P标记位，该页在主存为1，否则为0； A引用标记位，任何一次对该页的引用，包括读、写、执行，都置1。若某个页的A位持续保持清除状态10 s，

118、那么表明该页在最近的10 s内从未被访问过，因此在决定淘汰主存中的某个页面时，它作为首选淘汰页面； D修改标记位，对该页内容修改时置1，否则置0； R/W权限标记位，为0表示该页可“只读”，拒绝写入，为1则允许写入； U/S“用户/系统”标记位，若为0，表示该页驻留的块是操作系统自身，任何用户进程都不能访问它。违例则引起“系统受攻击”的中断。它是整个系统安全的一部分。 第第5 5章章 操作系统操作系统 2页面置换算法 在图5-17中，淘汰主存中的1个页面。目的是腾出1个空闲块以便存放新调入的页面。淘汰哪个页面的首要问题是决定在整个主存空间范围内还是在本进程空间范围内选择，在实际系统中这两种选择

119、都是可行的。但为了对置换算法性能作比较准确的评估，以下限定“在本进程空间内选择”，并假定系统限定每个进程占有的最大页面数为M。到目前为止，关于页面置换算法已经提出了很多方案，下面介绍几种常用的算法。第第5 5章章 操作系统操作系统 (1) 先进先出算法(FIFO，First In First Out)。该算法的基本思想是，总是淘汰那些驻留在主存时间最长的页面，即先进入主存的页面先被淘汰。设某进程空间分得的最大主存块数M=3，该进程的页面访问序列如图5-19所示，其页面失效次数为15，页面失效率=15/20=75%。当M增加时，直观上似乎能下降，但FIFO有异常现象，即M增加时反而上升。例如，读

120、者不妨试算这样一个页面访问序列： 1，2，3，4，1，2，5，1，2，3，4，5第第5 5章章 操作系统操作系统 当M=3时， =9/12，当M=4时， =10/12。产生这种异常现象的原因，固然跟页面访问序列有关，但也与FIFO置换算法本身完全不考虑程序的动态性有关。 页面访问序列：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 页面失效()： 第第5 5章章 操作系统操作系统图5-19 当M=3时，FIFO算法示例 页面访问序列：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1页面失效()： 第第5 5章章 操作系统操作系统 该

121、算法只是在按线性顺序访问地址空间的情况下才是理想的，否则，效率不高。因为那些常常被访问的页，在主存中也停留得最久，这些常用的页由于变“老”不得不被淘汰出去，也许刚淘汰出去不久又要访问到。第第5 5章章 操作系统操作系统 (2) 最近最久未使用算法(LRU，Least Recently Used)。这是一种有效的算法，该算法被UNIX系统V、Windows 95、Windows NT、OS/2所采用。它的基本思想是当需要淘汰一页时，选择最近一段时间内最久未被使用过的页面。这是根据程序执行时所具有的局部性来考虑的，即那些刚被使用过的页面，可能马上还要被使用，而那些在较长时间里未被使用的页面，一般可

122、能不会马上用到。对于图5-19的页面访问序列，LRU算法的页面失效率=12/20=60%。第第5 5章章 操作系统操作系统 (3) 最近未使用算法(NUR，Not Used Recently)。该算法每次淘汰最近一段时间内未引用过的页面。当某页被访问时，引用位置1，系统周期性地对页表表目中的引用位清零。当需要淘汰时，从那些引用位为0的页面中任选一页淘汰。该算法实现起来比较简单。第第5 5章章 操作系统操作系统 3性能分析 引入虚拟存储管理，把内存和外存统一管理的目的，是把那些访问频率非常高的页放入内存，减少内外存交换的次数。如果页面在内存和外存之间频繁地调度，以至于系统用于调度页面所需要的时间

123、比进程实际运行所占用的时间还多，此时系统效率急剧下降，这种情况称发生了颠簸，又称抖动。第第5 5章章 操作系统操作系统 颠簸是由于缺页率高而引起的，影响缺页率的因素有： (1) 分配给进程的物理页面数。一般情况下，分配给进程的物理页面数多，则缺页率就低，反之，缺页率就高。 (2) 页面大小。页面尺寸大，则页表中只需较少的表目，这样页表占用空间少且查表速度快，缺页次数也相应少些，但在页面调度时，换页时间较长，且空间浪费也可能大些(一般页内碎片平均占1/2页面)。若页面尺寸小，则正好相反，所以页面大小要根据计算机性能及用户要求等具体情况确定。第第5 5章章 操作系统操作系统 对于给定的进程页面访问

124、序列，从时刻(t?)到时刻之间所访问页面的集合，称为该进程的工作集。其中，称为工作集窗口。工作集是随时间而变化的，如图5-20所示。工作集大小与窗口尺寸密切相关。第第5 5章章 操作系统操作系统图5-20 工作集随时间而变化第第5 5章章 操作系统操作系统 由模拟实验知道，任何程序对内存都有一个临界值要求，当分配给进程的物理页面数小于这个临界值时，缺页率上升；当分配给进程的物理页面数大于该临界值时，再增加物理页面数也不能显著减少缺页次数。因此，希望分配给进程的物理页面数与当前工作集大小一致。 在实现时，操作系统为每一个进程保持一个工作集，并为该进程提供与工作集大小相等的物理页面数，这一过程可动

125、态调整。统计工作集大小一般由硬件完成，系统开销较大。第第5 5章章 操作系统操作系统 系统也可规定缺页率的上界和下界。当运行进程缺页率高于上界时，表明分给它的物理页面数过少，应当增加；反之，当运行进程缺页率低于下界时，表明分给它的物理页面数过多, 可以减少。这样，根据缺页率反馈可动态调整物理页面的分配，以防止颠簸的发生。第第5 5章章 操作系统操作系统5.4 设设 备备 管管 理理 本节讨论操作系统的设备管理。这里所说的“设备”是指计算机系统中除中央处理机和主存储器以外的所有设备，这些设备通常称为外部设备或I/O设备。现代计算机系统的外部设备种类繁多，一台计算机可以配置多类外设，每类设备可能不

126、止一台，而各类设备的物理特性、使用特点和运行速度相差极大，与主机的速度也不匹配，这就为设备管理带来了不少困难。 第第5 5章章 操作系统操作系统 现代操作系统充分考虑了上述特点，从用户的角度出发，在设备管理中引入了一些新技术，如Windows 95中的“即插即用”(Plug and play)是一项很重要的技术，一旦系统加电运行，即插即用子系统可自动管理所有硬件设备的更改。第第5 5章章 操作系统操作系统 5.4.1 设备管理概述 1设备管理的任务和功能 (1) 设备管理的基本任务是： 向用户提供使用外部设备的统一的接口，按照用户的要求和设备的类型，控制设备进行工作，完成用户的I/O请求。 在

127、多道程序环境下，当多个进程竞争使用设备时，按照一定的策略分配和管理设备，以使系统能有条不紊地工作。第第5 5章章 操作系统操作系统 充分利用中断技术、通道技术和缓冲技术，提高CPU与设备、设备与设备之间的并行工作能力，以充分利用设备资源，提高外部设备的使用效率。 (2) 设备管理的功能。 为实现上述任务，设备管理应具有如下功能：设备的分配与回收；管理I/O缓冲区；设备驱动，实现I/O操作；外部设备中断处理，虚拟设备及其实现。第第5 5章章 操作系统操作系统 2设备的分类 外部设备按其用途可分为输入型设备(如光电输入机、卡片输入机等)、输出型设备(如各种类型打印机、绘图仪等)以及输入输出型设备(

128、如磁盘、磁带、可读写光盘等)。 外部设备按其所属关系可分为两类。 (1) 系统设备。即在系统生成时已登记在系统中的标准设备。如输入机、打印机、终端、磁盘等。第第5 5章章 操作系统操作系统 (2) 用户设备。即在系统生成时未登记在系统中的非标准设备。通常这类设备是由用户提供的，因此该类设备的处理程序也应由用户提供，并通过适当的手段把这些设备介绍给系统，以便系统能对它们实施统一的管理。如扫描仪、绘图仪等。 从资源分配角度来看，外部设备又可分为三类。 第第5 5章章 操作系统操作系统 (1) 独占设备。对这类设备来说，在一段时间内最多只能有一个进程占有并使用它。该类设备一经分配给某一进程，就在该进

129、程的运行过程中为其独占，而其它进程只有等该设备被释放后才能使用。例如当某一进程正在使用某打印机时，其它进程就不能使用该打印机，否则将会得到混乱的输出结果。低速I/O设备一般是独占设备，如打印机、终端等。第第5 5章章 操作系统操作系统 (2) 共享设备。允许多个进程同时共享的设备，即多个进程的I/O传输可以交叉。例如，多个进程可以交替地从磁盘上读取信息，所以磁盘是共享设备。应当指出，磁带机是不适于共享的。 (3) 虚拟设备。通过Spooling假脱机技术把原独占设备改造成能为若干用户共享的设备，即把一台设备变成多台虚拟设备，从而提高设备的利用率。第第5 5章章 操作系统操作系统 3通道技术 所

130、谓通道，实际上是可以控制一台或多台外设与主机并行工作的一种硬件。当主机要启动外围设备时，只要将启动信号以及一些必要的参数信息(例如传输的字节数、需要传输的数据起始地址等)送给通道就可以独立地完成输入输出任务，而主机就不再干预了，实现了主机和通道的并行操作。 在具有通道结构的计算机系统中，内存、通道、控制器和设备之间的连接关系有多种，常用的一种如图5-21所示。第第5 5章章 操作系统操作系统图5-21 内存、通道、控制器、设备之间的连接第第5 5章章 操作系统操作系统 通常，一个CPU可以连接若干个通道，一个通道可以连接若干个控制器，一个控制器可以连接若干个设备。CPU执行I/O指令对通道实施

131、控制，通道执行通道命令对控制器实施控制，控制器发出动作序列对设备实施控制，设备执行相应的输入输出操作。第第5 5章章 操作系统操作系统 采用输入输出通道技术后，输入输出操作过程如下：CPU在执行用户程序时如遇到输入输出请求，由它用I/O指令启动指定通道上选定的外围设备，一旦启动成功，通道开始控制外围设备进行操作。这时CPU就可执行其它任务与通道并行工作，直到输入输出操作完成。通道发出操作结束中断时，CPU才停止当前工作，转向处理输入输出操作结束事件。CPU与通道并行工作的结果，提高了系统的利用率。第第5 5章章 操作系统操作系统 4缓冲技术 提高CPU与外设的并行程度的另一项技术措施是缓冲技术

132、。由于CPU与外设运行速度不匹配，在外设中，也存在通道的个数与设备个数不匹配的问题。于是当CPU与I/O设备之间进行数据通信时，就会产生“瓶颈”现象，使并行处理受到限制。为此，人们提出了缓冲技术来匹配CPU与设备的速度差异和系统负荷的不均匀，从而提高CPU与外设的并行程度。 缓冲技术就是在内存中开辟一个或多个缓冲区，缓冲区的大小可以按实际应用的需要来确定，常用的缓冲技术有三种：双缓冲技术、环形缓冲技术和缓冲池。第第5 5章章 操作系统操作系统 (1) 双缓冲技术。双缓冲技术是最简单的一种缓冲技术，对低频度活动的I/O系统较为合适。在这种方案下，分别为输入和输出设置两个缓冲区buf1和buf2。

133、读入数据时，输入设备向buf1填数据，进程从buf1提取数据的同时，输入设备向buf2中填数据。当buf1取空时，进程又从buf2中提取数据，与此同时输入设备向buf1中填数据。如此交替使用两个缓冲区，使CPU和设备的并行操作的程度进一步提高。第第5 5章章 操作系统操作系统 (2) 环形缓冲技术。环形缓冲技术是在主存中分配一组大小相等的存储区作为缓冲区，并将这些缓冲区链接起来，形成一个循环队列。当CPU将数据写入缓冲区时，相当于在循环队列中加入了一个元素；当CPU从缓冲区取走一个数据时，相当于在循环队列中删除了一个元素。第第5 5章章 操作系统操作系统 (3) 缓冲池。缓冲池由内存中一组大小

134、相等的缓冲区组成，池中各缓冲区的大小与I/O设备的基本信息单位相似，缓冲池属系统资源，由系统进行管理。缓冲池中各缓冲区可用于输出信息，也可用于输入信息，并可根据需要组成各种缓冲区队列。缓冲池中有3种类型的缓冲区： 输入缓冲区； 输出缓冲区； 空白缓冲区。第第5 5章章 操作系统操作系统 它们都通过链接指针分别链成三个队列，即输入队列、输出队列和空白队列。 当输入设备通过通道要求输入数据时，系统从空白队列中取出一缓冲区，收容输入数据，并将它挂在输入队列末尾。 当进程要求输出数据时，系统从空白队列中取出一缓冲区，收容输出数据，并将它挂在输出队列末尾。 当进程取完输入数据，或外设处理完输出数据时，就

135、将这部分数据缓冲区挂到空白队列末尾。 第第5 5章章 操作系统操作系统 5.4.2 I/O控制方式 处理机与外部设备之间的通信，即输入输出。按照不同的硬件条件，可以采取如下一些不同的控制方式。 1循环测试I/O方式 循环测试I/O方式是一种利用程序直接控制I/O操作的方式。这种方式的实现最为简单，可以不要任何附加的硬件支持，只要求设置一个设备的忙闲状态位。处理机利用I/O测试指令测试设备的忙闲，若设备不忙，则执行输入或输出指令；若设备忙，则I/O测试指令不断对该设备进行测试，直到设备空闲为止。这种方式使CPU花费大量时间循环测试I/O，造成极大的浪费。第第5 5章章 操作系统操作系统 2中断方

136、式 计算机中断技术及中断处理机构的引入，使得CPU与外围设备的工作有了相对独立性。当一个设备处于工作状态时，CPU可以继续处理其它的任务，而无须等待。每当设备完成I/O操作，便以中断请求方式通知CPU，CPU接收到中断信号后，暂停正在处理的任务，进行相应的处理，完后又可返回继续处理被暂停的任务。在这种方式下，仅当I/O操作正常或异常结束时才中断CPU，从而实现了一定程度的并行操作，但由于CPU直接控制I/O操作，每传送一个单位的信息，都要发生一次中断，因而仍然消耗大量CPU时间。第第5 5章章 操作系统操作系统 3直接内存存取(DMA)方式 DMA(Direct Memory Access)方

137、式用于高速外部设备与内存之间批量数据的传输。它是在硬件的支持下，使用一个专门的DMA控制器，通过占用总线控制权，由DMA控制器发送控制信号来完成内存与设备之间的直接数据传送，而不用CPU干预。当本次DMA传送的数据全部完成后，才产生中断，请求CPU进行结束处理。磁盘设备与主机交换信息主要采用这种方法。第第5 5章章 操作系统操作系统 4通道方式 前面已经介绍了通道技术。通道的出现是现代计算机系统功能不断完善，性能不断提高的结果，是计算机技术的一个重要进步。 通道是指具有独立输入输出功能的处理装置，或者说是专门负责输入输出任务的专用机，功能更强更为完整的通道本身就是一台计算机。按照信息交换方式和

138、所连接的设备种类不同，通道可以分为以下三种类型。第第5 5章章 操作系统操作系统 (1) 字节多路通道。它适用于连接打印机、终端等低速或中速的I/O设备。它以字节为单位传送信息，但可以分时执行多个通道程序。 (2) 选择通道。它适用于连接磁盘、磁带等高速设备。它以成组方式工作，每次传送一批数据，传送速率很高，但在一段时间内只能为一台设备服务。每当一个I/O操作请求完成后，再选择另一台设备为其服务。第第5 5章章 操作系统操作系统 (3) 数组多路通道。这种通道综合了字节多路通道分时工作和选择通道传输速率高的特点，适用于连接高速I/O设备，如磁盘。它首先为一台设备执行一条通道命令，传送一批数据，

139、然后再选择另一台设备执行一条通道命令，即几台设备的通道程序都在同时执行中，但任何时刻，通道只能为一台设备服务。第第5 5章章 操作系统操作系统 5.4.3 设备分配 1设备分配的原则 设备管理程序的主要功能之一是为进入系统的作业或进程分配所需的设备。设备分配的原则、方式和方法是根据设备的特性、用户的要求和系统配置情况决定的，但总的原则是充分发挥设备的使用效率，尽可能地避免出现死锁。第第5 5章章 操作系统操作系统 1) 设备分配方式 设备分配方式有两种：静态分配和动态分配。静态分配是在作业运行之前由系统一次分配满足需要的全部设备，这些设备一直为该作业占用，直到作业撤消。这种分配不会出现死锁，但

140、设备利用率较低。动态分配是在进程运行过程中需要使用设备时，通过系统调用命令向系统提出设备请求，系统按一定的分配策略给进程分配所需设备，一旦使用完毕立即释放。显然动态分配方式有利于提高设备的使用效率，但会出现死锁。第第5 5章章 操作系统操作系统 2) 设备分配的原则 设备分配的原则就是选择用户的算法，即把设备分给谁。常用的有先请求先服务和按请求I/O进程的优先级决定，优先级高的优先服务。 用户程序要使用设备时必须提供进行I/O操作的有关信息，指出执行I/O的逻辑设备名、操作类型、传送数据的数目、信息的源或目的地址等。存放进程I/O操作的信息结构称为I/O请求块(IORB，下同)。第第5 5章章

141、 操作系统操作系统 (1) 先请求先服务。当有多个进程对某一设备提出I/O请求时，系统按请求先后次序组成IORB队列。当一个IORB生成后，系统就把它挂在相应设备的I/O请求队列的队尾，当设备空闲时，从这个设备I/O请求队列的队首取一个IORB，并按这个IORB的要求进行I/O操作。 (2) 优先级高的优先服务。这种算法的设备I/O请求队列按请求I/O操作的进程优先级高低组织，在一个新的IORB生成后，不是插入到I/O队列的队尾，而是按请求I/O的优先级插入适当的位置，从而保证队首的IORB总是当时请求该设备的最高优先级的进程。当设备空闲时，就从IORB队列的队首取得IORB，并按IORB的要

142、求进行I/O操作。第第5 5章章 操作系统操作系统 3) 设备分配技术 根据设备的特性把设备分成独占设备、共享设备和虚拟设备三种，针对这三种设备采用三种不同的分配技术：独享分配、共享分配和虚拟分配。第第5 5章章 操作系统操作系统 2独享分配 独占设备有打印机、键盘、显示器等。磁带机可作为独占设备，也可作为共享设备。若对这些设备不采用独享分配就会造成混乱，如打印机交叉地分配给系统中多个进程使用，就会使多个进程的输出信息交叉在一起无法分开，因此对独占设备一般采用独享分配。独占设备的分配方式通常采用静态分配的方式，但由于单个作业往往不是连续地、自始至终地使用某台设备，所以设备利用率较低。为了提高设

143、备利用率，也可以采用动态分配方式。第第5 5章章 操作系统操作系统 3共享分配 共享设备包括磁盘、磁带和磁鼓，对这些设备的共享有两层涵义：一方面是对这些设备存储介质的共享，如多个用户可以把信息存放在同一磁盘设备的不同扇区上，这种共享一般是存放文件；另一方面是对磁盘、磁带驱动器的共享，多个用户(或进程)要访问这些设备上的信息是通过驱动器来实现的，这些驱动器为共享设备。由于这些设备进行I/O操作的速度较高，并且是直接存取信息，因此必须采用共享分配，即可交叉地分配给多个用户或多个进程使用，这样有利于提高设备的利用率。第第5 5章章 操作系统操作系统 4虚拟分配 系统中设备的数量总是有限的，并且还有一

144、定数量的独占设备。这些独占设备一旦分配给某个作业往往只有很少时间在工作，许多时间一直处于空闲状态。而别的作业又因得不到相应的设备而不能投入运行，因此严重地影响整个计算机系统的效率。从另一个角度来说，独占设备一般是低速设备，若采用联机操作，也会增加作业的运行时间，影响计算机系统的效率。为提高计算机系统的效率，提出了在高速共享设备上模拟低速设备功能的技术，称为虚拟设备技术。第第5 5章章 操作系统操作系统 虚拟分配是针对虚拟设备而言的，其实现的过程是当用户(或进程)申请独占设备时，系统给它分配共享设备的一部分存储空间，当程序要与设备交换信息时，系统就把要交换的信息存放在这部分存储空间。例如，一般是

145、通过磁盘设备(共享设备)将进程的输入输出信息暂存在磁盘上，在适当的时候再将信息传输到相应的设备上去处理。从用户的角度，他已占有了所申请的设备，并完成了所需的输入输出任务，但实际上，信息是在设备可用时才真正输入输出的。因此，对用户作业来说，相当于存在着一个虚拟设备。第第5 5章章 操作系统操作系统 通常人们把共享设备中代替独占设备的那部分存储空间和相应的控制结构称为虚拟设备，并把对这类设备的分配称为虚拟分配。操作系统中完成这种功能所用的技术常称为SPOOLing技术，SPOOLing是Simultaneous Peripheral Operations On-Line(外围设备同时联机操作)的缩

146、写。第第5 5章章 操作系统操作系统 5.4.4 I/O传输控制 设备管理的功能除了监视系统设备状态，进行设备分配外，还有一个重要的功能是控制设备的I/O操作，实现用户的传输请求。 1用户进程的I/O请求 用户通过设备传输系统调用命令请求传输服务。这一命令形式既要使用户使用方便，又能确切地描述这次I/O传输所需的信息。它应包含的内容有：执行I/O操作的逻辑设备名，比如指出设备类、设备号，设备类指明这个设备属于哪一大类(如打印机类)， 第第5 5章章 操作系统操作系统 设备号是同类设备中的编号；指出要求何种操作，如读、写等；还要指出传送数据的数目和数据地址，该地址为传送的目的地。 当用户发出请求

147、I/O传输的系统调用命令时，设备管理模块中有一个接口程序处理这一命令。接口程序的功能是把逻辑设备映射为相应的物理设备，检查命令的合法性，然后转入所需要的服务。 设备管理中的控制程序接收了用户进程的关于I/O的服务请求后，负责启动设备的工作和进行中断处理，完成I/O传输任务。第第5 5章章 操作系统操作系统 2设备驱动 设备驱动工作是由设备驱动程序来完成的。设备驱动程序是能直接控制设备进行运转的程序。这类程序应根据每个设备的特点和性能来设计，一般每一类设备有一个相应的驱动程序，能控制同一类中多台设备的工作。它需要随时检测，有无一个I/O请求来到。若设备请求队列不空，即有IORB时，它就取队列中第

148、一个 IORB来处理，设置相应设备的有关寄存器，启动设备的I/O操作。第第5 5章章 操作系统操作系统 3中断处理 当设备开始工作后，在设备传输信息的过程中或传输结束时要求CPU的帮助和干预，这种要求是通过进行I/O操作的设备向CPU发中断信号实现的。当设备传输数据结束或出错时向CPU发出传输完成或出错的中断请求。CPU接收到中断信号后会转入到相应的中断处理程序。这里分为结束中断处理和出错中断处理。第第5 5章章 操作系统操作系统 (1) 结束中断处理。它的主要工作是做传输完成后的善后工作，如把相应设备、控制器、通道置为空闲状态；唤醒正等待此操作完成的进程；再检查设备请求队列(IORB队列)空

149、否，若未空，则启动下一个I/O请求。 (2) 错误中断处理。发现错误信息后，判断错误性质，或者忽略这个错误继续运行，或者征询用户意见(在交互式系统中)，或向用户返回出错信息，结束I/O传输。第第5 5章章 操作系统操作系统 5.4.5 磁盘调度 对于用来保存文件的磁盘等设备来说，同一时刻可能会有许多访问请求，每个请求读或写一块。按照什么次序为这些访问请求服务是I/O调度所应解决的问题。 例如，对于磁盘的存取访问一般要有三部分时间，首先要将磁头移动到相应的磁道或柱面上，这个时间叫做寻道时间；一旦磁头到达指定磁道，必须等待所需要的扇区旋转到读/写磁头下，这个时间叫旋转延迟时间；最后，信息在磁盘和内

150、存之间的实际传送时间叫传送时间。一次磁盘服务的总时间就是以上三者之和。要使磁盘服务尽可能地快，就需要操作系统提供合适的磁盘调度算法，以改善磁盘服务的平均时间。第第5 5章章 操作系统操作系统 设计磁盘调度算法应当考虑两个基本因素： (1) 公平性。一个磁盘访问请求应当在有限时间内得到满足。 (2) 高效性。减少设备机械运动所带来的时间开销。 下面讨论几种常用的磁盘调度算法。第第5 5章章 操作系统操作系统 1先来先服务(FCFS) 按照访问请求的次序为各个进程服务，这是最公平而又最简单的算法，但是效率不高。因为磁头引臂的移动速度很慢，如果按照访问请求发出的次序依次读写各个磁盘块，则磁头引臂将可

151、能频繁大幅度移动，容易产生机械振动，亦造成较大的时间开销，影响效率。第第5 5章章 操作系统操作系统 例如，有12个磁盘访问请求，它们请求的柱面(磁道)号如下： 请求次序： 1 2 3 4 5 6 7 8 9 10 11 12 磁盘柱面：19 376 205 134 18 56 192 396 29 3 19 40 设当前磁头位于100号柱面，按FCFS调度，即按1，2，3，4，5，6，7，8，9，10，11，12的次序调度，磁头移动的总距离为1604柱面。 第第5 5章章 操作系统操作系统 可以看出，如果把4号请求和7号请求作为第1、第2服务考虑，磁头移动总距离显然小于1604，花费的时间就

152、少，平均服务性能有所提高。 2最短寻道时间优先(SSTF，Shortest Seek Time First) 这种调度算法的基本思想是在选择下一个服务对象时，总是优先为距离磁头当前所在位置最近磁道(柱面)的访问请求服务。仍以上例为例，调度次序改为：4，7，3，6，12，9，1，11，5，10，2，8，磁头移动的总距离为700柱面，比FCFS调度的1604小得多。第第5 5章章 操作系统操作系统 在多个请求已经明确的情况下，SSTF不会比FCFS差。但是，在实际系统中，I/O请求是随机到达的，即IORB队列是或长或短动态变化的。例如在2号请求(376柱面)轮到服务之前的某段时间内，系统又接收一个

153、请求流，流中所有请求所要求移动磁头的距离都小于到达柱面376所移动的距离，那么，原2号请求、原8号请求将长时间得不到服务，对应的两个进程受到“歧视”。因此，SSTF算法缺乏公平性。第第5 5章章 操作系统操作系统 3扫描算法(SCAN) 这种算法因其基本思想与电梯的工作原理相似，故又称电梯算法。 SCAN算法也是一种寻道优化的算法，它克服了SSTF算法的缺点。SSTF算法只考虑访问磁道与磁头当前位置的距离，而未考虑磁臂的移动方向，而SCAN算法既考虑距离，也考虑方向，且以方向优先。即当无访问请求时，磁头臂停止不动；当有访问请求时，磁头臂按照一定方向扫描。假设初始时，磁头处于最外磁道，并向内磁道

154、移动。在移动的过程中，如果经过的磁道有访问请求，则为其服务，然后判断内磁道是否还有访问请求， 第第5 5章章 操作系统操作系统 如果有，则继续向内磁道移动并服务。否则改变磁头移动方向，即开始向外磁道移动，同时为经过的请求服务，如此反复。仍以上例为例，根据SCAN算法，当磁头初始于100时，假设首先向柱面0的方向(向外)移动，依次为序号6，12，9，1，11，5，10提供存取服务，然后，调转磁头移动方向(向内)，依次为序号4，7，3，2，8提供存取服务。磁头移动的总距离为490柱面，比SSTF的总距离少210。 可以看出，SCAN算法比较公平，可以避免柱面歧视。另外效率较高，在大多数情况下比SS

155、TF要好，少数情况下性能不如SSTF。第第5 5章章 操作系统操作系统5.5 文文 件件 管管 理理 5.5.1 文件与文件系统 1文件的概念 文件管理的功能是通过把它管理的信息(程序和数据)组织成一个一个文件的形式来实现的。那么，什么是文件呢？ 文件(File)是具有符号名的，在逻辑上具有完整意义的一组相关信息项的有序序列。第第5 5章章 操作系统操作系统 文件可以包含范围非常广泛的内容。系统和用户都可以将具有一定独立功能的程序模块、一组数据或一组文字命名为一个文件。例如用户的一个Pascal源程序、一个目标代码程序、系统中的库程序和各种系统程序、一批待加工处理的数据、一篇文章等等，都可以构

156、成一个文件。第第5 5章章 操作系统操作系统 文件的符号名称作文件名，它是用户在创建文件时确定的，并在以后访问文件时使用。信息项是构成文件内容的基本单位，各信息项之间具有顺序关系。信息项可以是一个字符，也可以是一个记录。通常，记录是一个有意义的信息集合，它是作为对文件进行存取操作的基本单位。一个文件的各个记录长度可以相等也可以不等。一般情况下，一个逻辑记录可以包含若干个数据项，例如，在学生某门课程成绩文件中，记录有如下数据项：作业、实习、期中、期末。本节只讨论基本文件系统，也就是说，只涉及文件记录的简单逻辑组织，在操作系统级上处理为无结构、无解释的信息集合。第第5 5章章 操作系统操作系统 2

157、文件的分类 为便于文件的控制和管理，通常把文件分成若干类型。 文件按其性质和用途可分为： (1) 系统文件有关操作系统及其它系统程序的信息所组成的文件。这类文件对用户不直接开放，只能通过系统调用为用户服务。 (2) 库文件由标准子程序及常用的应用程序组成的文件。这类文件允许用户调用，但不允许用户修改。第第5 5章章 操作系统操作系统 (3) 用户文件由用户建立的的文件，如源程序、目标程序、以及由原始数据、计算结果等组成的文件。这类文件根据使用情况又可以分为三种类型： 临时文件即用户在一次算题过程中建立的“中间文件”。它只保存在磁盘、磁鼓上，在作为“档案”的磁带上没有副本。当用户撤离系统时，其文

158、件也随之被撤消。第第5 5章章 操作系统操作系统 档案文件只保存在作为档案的磁带上，以备查证和恢复时使用，如日志文件。 永久文件其信息需要长期保存的文件。它不仅在磁盘或磁鼓上有文件副本，而且在“档案”的磁带上也有一个可靠的副本。第第5 5章章 操作系统操作系统 根据文件的保护方式，文件可分为三类：(1) 只读文件允许文件主及核准的用户读，但不允许写。(2) 读写文件允许文件主及核准的用户读、写，但禁止未核准的用户读、写。(3) 不保护文件所有用户都可以存取。 按文件的存取方式，可把文件分为：(1) 顺序文件只能按顺序依次访问其中内容的数据文件。(2) 随机文件可随时访问其内容的数据文件。第第5

159、 5章章 操作系统操作系统 按信息的流向，又可把文件分为三类： (1) 输入文件只能读的文件，如读卡机或纸带输入机文件。 (2) 输出文件只能写的文件，如打印机或穿卡机文件。 (3) 输入输出文件既可读，又可写的文件。如在磁盘，磁鼓，磁带上的文件。 第第5 5章章 操作系统操作系统 在UNIX操作系统中，文件按组织和处理方式分为三类： (1) 普通文件内部无结构的一串平滑的字符。这种文件既可以是系统文件，也可以是库文件或用户文件。 (2) 目录文件由文件目录项构成的文件。对它的处理(读、写、执行)在形式上与普通文件相同。第第5 5章章 操作系统操作系统 (3) 特殊文件由一切输入输出慢速字符设

160、备构成的文件。这类文件对于查找目录、存取权限验证等的处理与普通文件相似，而其它部分的处理针对设备特性要求做相应的特殊处理。 根据文件的存取方法或文件的物理结构，还可以划分为不同类型。与操作系统分类一样，文件分类也无公认标准，上面的分类仅是为了帮助理解文件的概念，了解实际工作中常常提到的这些用语的含义。第第5 5章章 操作系统操作系统 3文件系统 操作系统中负责管理和存取文件信息的软件机构称为文件管理系统，简称文件系统。文件系统由三部分组成：与文件管理有关的软件、被管理的文件以及实施文件管理所需的数据结构。从系统角度看，文件系统是对文件存储器的存储空间进行组织和分配，负责文件的存储并对存入的文件

161、进行保护和检索的系统。具体地说，它负责为用户建立文件；存入、读出、修改、转储文件；控制文件的存取；当用户不再使用时撤销文件。第第5 5章章 操作系统操作系统 在操作系统中增设了文件管理部分后，为用户带来如下好处： (1) 使用的方便性。由于文件系统实现了按名存取，用户不再需要为他的文件考虑存储空间的分配，因而无需关心他的文件所存放的物理位置。特别是，假如由于某种原因，文件的位置发生了改变，甚至连文件的存储装置也换了，在具有按名存取能力的系统中，对用户不会产生任何影响，因而也用不着修改他们的程序。第第5 5章章 操作系统操作系统 (2) 数据的安全性。文件系统可以提供各种保护措施，防止无意或有意

162、地破坏文件。例如有的文件可以规定为“只读文件”，如果某一用户企图对其修改，那么文件系统可以在存取控制验证后拒绝执行，因而这个文件就不会遭到破坏。另外，用户可以规定他的文件除本人使用外，只允许核准的几个用户共同使用。若发现事先未核准的用户要使用该文件，则文件系统将认为其操作非法并予以拒绝执行。第第5 5章章 操作系统操作系统 (3) 信息的共享性。对于重要的信息或系统文件，在文件系统的管理下可以避免重复占用存储空间。尤其是在多用户环境下，文件系统提供的文件并发控制能力，使多个用户可同时访问同一个文件。第第5 5章章 操作系统操作系统 5.5.2 文件结构和存取方法 1文件的逻辑结构 文件的逻辑结

163、构是指文件的外部组织形式，即从用户角度看到的文件组织形式，用户以这种形式存取、检索和加工有关信息。文件的逻辑结构可分为两类。 1) 流式文件 第第5 5章章 操作系统操作系统图5-22 记录式文件 第第5 5章章 操作系统操作系统 构成文件的基本单位是字符，流式文件是有序字符的集合，其长度为该文件所包含的字符个数，所以又称为字符流文件。流式文件无结构，且管理简单，用户可以方便地对其进行操作。源程序、目标代码等文件属于流式文件。UNIX系统采用的是流式文件结构。第第5 5章章 操作系统操作系统 2) 记录式文件 构成文件的基本单位是记录，记录式文件是一组有序记录的集合。记录式文件可把记录按各种不

164、同的方式排列，以便用户对文件中的记录进行修改、追加、查找和管理。记录式文件可分为定长记录文件和变长记录文件两种，如图5-22所示。第第5 5章章 操作系统操作系统 在定长记录文件中，每个记录的长度是固定的，因此，具有k个记录的文件长度为kL，其中L是每个记录的字节数。有时，对于定长记录文件就直接用它的记录个数来表示其长度。在变长记录文件中，每个记录的长度不等，因此通常在每个记录前用一个字节来存放该记录的长度，具有k+1个记录的变长记录文件的长度为 ，其中Li表示第i个记录的字节数。第第5 5章章 操作系统操作系统 2文件的存取方法 文件的存取方法按照存取的顺序关系，通常分为顺序存取和随机存取。

165、对于记录式文件的存取，顺序存取是严格按照记录排列的顺序依次进行存取。如果当前读取了记录Ri，则下次要读取的记录就自动地定为Ri+1，若以r表示读写指针，则对于定长记录有 r i+1 = ri + L 对于变长记录有 r i+1 = ri + L + 1第第5 5章章 操作系统操作系统 随机存取方法允许随机存取文件中的记录，而不管上次存取了哪一个记录。对于定长记录的文件，这种存取是方便的，只要将读写指针r指向第i个记录的首址就可以了，即 ri = offset + i * L(i = 0，1，k) 其中offset是第0个记录的首址。而对于变长记录的文件来说，随机存取时需要从前面所有记录的长度中

166、，通过一个个计算才能确定所需记录的首址，即 ri = offset + (i = 0，1，k)第第5 5章章 操作系统操作系统 3文件的物理结构 文件的物理结构是指文件的内部组织形式，亦即文件在物理存储设备上的存放方法。它和文件的存取方法密切相关。文件的物理结构好坏，直接影响到文件系统的性能。因此，只有针对文件或系统的适用范围建立起合适的物理结构，才能既有效地利用存储空间，又便于系统对文件的处理。第第5 5章章 操作系统操作系统 为了有效地分配文件存储器的空间，通常把它们分成若干块，并以块为单位进行分配和传送。每个块称为物理块，而块中的信息称为物理记录。物理块长通常是固定的，在软盘上常以128

167、字节为一块，在磁带或硬盘上常以512字节或1024字节为一块。在记录式文件中，允许一个逻辑记录占用几块，也可以在一块中存放几个逻辑记录。 文件在逻辑上是连续的，而在文件空间中的存放位置可以有各种形式。根据文件空间中的存放形式，文件可分为连续文件、串连文件和索引文件。第第5 5章章 操作系统操作系统 连续文件是一种最简单的文件物理结构，它把逻辑上连续的文件信息依次存放在连续编号的物理块中，只要知道文件在存储设备上的起始地址(首块号)和文件长度(总块数)，就能很快地进行存取。如图5-23所示。这种结构的优点是访问速度快，缺点是文件长度增加困难。第第5 5章章 操作系统操作系统图5-23 连续文件的

168、结构第第5 5章章 操作系统操作系统 串连文件是将逻辑上连续的文件分散存放在若干不连续的物理块中，每个物理块设有一个指针，指向其后续的物理块。只要指明文件的第一个块号，就可以按链指针检索整个文件。如图5-24所示。这种结构的优点是文件长度容易动态变化，其缺点是不适合随机存取访问。第第5 5章章 操作系统操作系统图5-24 串连文件的结构 第第5 5章章 操作系统操作系统 索引文件的组织方式要求为每个文件建立一张索引表，表中的每个项目指出了文件的逻辑块号和与之对应的物理块号。索引表也以文件的形式存在磁盘上，只要给出索引表的地址，通过索引表就可以查找到文件信息的存放位置，如图5-25所示。这种结构

169、有利于进行随机存取，并具备串连文件的所有优点。缺点是存储开销大，因为每个文件有一个索引表，而索引表也要占用存储空间。第第5 5章章 操作系统操作系统图5-25 索引文件的结构 第第5 5章章 操作系统操作系统 4UNIX文件的多重索引结构 在索引结构的文件中，如果一个文件很大，那么相应的索引表也很大，一个物理块可能放不下一个索引表。而如果系统中各个文件的大小很不均匀，则会导致索引表的大小也很不相同，这对于管理是很不方便的。下面介绍一种UNIX系统中文件的多重索引结构。这种结构如图5-26所示。第第5 5章章 操作系统操作系统 在图5-26中，I-addr索引区共有13项，其中前10项直接登记了

170、存放文件信息的物理块号(即I-addr(0)到I-addr(9)，这称为直接寻址。0到9可以看成是逻辑块号。如果一个文件大于10块，则利用I-addr(10)作一次间接寻址，即I-addr(10)指向一个物理块，其中最多可存放128个存放文件信息的物理块号。如果文件更大，还可以分别用I-addr(11)和I-addr(12)作两次甚至三次间接寻址。第第5 5章章 操作系统操作系统图5-26 UNIX系统中文件的多重索引结构 第第5 5章章 操作系统操作系统 根据统计，文件容量不超过10块(5120 B)的文件占文件总数的80%，而这10块通过直接寻址就能得到文件的物理块号，只是对于大于10块的

171、约占总数20%的文件才采用间接寻址。这种结构的优点与一般索引文件结构一样，只是对于约20%的文件由于多次取索引而影响速度。第第5 5章章 操作系统操作系统 5.5.3 文件目录 在一个计算机系统中保存有许多文件，用户在创建和使用文件时只给出文件的名字，由文件系统根据文件名找到指定文件。为了便于对文件进行管理，设置了文件目录，用于检索系统中的所有文件。文件系统的基本功能之一就是负责目录的编排、维护和目录的检索，因此，要求目录的编排便于寻址，并且要防止冲突，目录的检索要迅速方便。第第5 5章章 操作系统操作系统 1文件控制块FCB 文件控制块FCB是系统为管理文件而设置的一个数据结构。FCB是文件

172、存在的标志，它记录了系统管理文件所需要的全部信息。FCB通常应包括以下内容：文件名、文件号、用户名、文件的物理位置、文件长度、记录大小、文件类型、文件属性、共享说明、文件逻辑结构、文件物理结构、建立文件的日期和时间、最后访问日期和时间、最后修改日期和时间、口令、保存期限等。第第5 5章章 操作系统操作系统 2文件目录与目录文件 1) 文件目录 文件与文件控制块是一一对应的。文件控制块的有序集合构成文件目录，每个目录项即是一个文件控制块。给定一个文件名，通过查找文件目录便可找到该文件对应的目录项(即FCB)。 2) 目录文件 文件目录是需要长期保存的。为了实现文件目录的管理，通常将文件目录以文件

173、的形式保存在外存空间，这个文件就被称为目录文件。目录文件是长度固定的记录式文件。第第5 5章章 操作系统操作系统 3文件目录结构 文件目录的组织与管理是文件管理中的一个重要方面，目前大多数操作系统如UNIX等都采用多级目录结构，又称树型目录结构，如图5-27所示。第第5 5章章 操作系统操作系统 图5-27 多级目录结构 第第5 5章章 操作系统操作系统 其中，树叶结点表示普通文件(用圆圈表示)，非叶结点表示目录文件(用矩形表示)。树根结点称为根目录，根目录是惟一的，由它开始可以查找到所有其它目录文件和普通文件，根目录一般可放在内存。从根结点出发到任一非叶结点或树叶结点都有且仅有一条路径，该路

174、径上的全部分支组成了一个全路径名。采用多级目录结构时，文件名为一个路径名。 多级目录结构的优点是便于文件分类，可为每类文件建立一个子目录；查找速度快，因为每个目录下的文件数目较少；可以实现文件共享。缺点是比较复杂。第第5 5章章 操作系统操作系统 4当前目录 在一个多层次的树型文件目录结构中，如果每次都从根结点开始检索，很不方便，通常各目录文件放在外存，故影响访问速度，尤其是当层次较多时检索要耗费很多时间。 为克服这一缺点，引入“当前目录”或称“工作目录”的概念。系统为用户提供一个目前正在使用的工作目录，称为当前目录。查找文件时既可以从根目录开始，也可以从当前目录开始向下检索。若从当前目录开始

175、，路径名只要给出从当前目录开始到所要访问文件的相对路径名即可。这样检索路径缩短，检索速度提高。如果需要，用户可随意更改当前目录。第第5 5章章 操作系统操作系统 5文件目录的改进 一个文件控制块一般要占很多空间，这样一个目录文件往往很大。在检索目录时，为了找到所需要的目录项，常常要将存放目录文件的多个物理块逐块读入内存进行查找，这就降低了检索速度。可以利用目录项分解法解决这一问题，即把目录项(文件控制块)分为两部分：名号目录项，包含文件名以及相应的文件内部号；基本目录项，包含除文件名外文件控制块的其它全部信息。第第5 5章章 操作系统操作系统 目录文件也分为名号目录文件和基本目录文件。查找一个

176、目录项就分成两步：首先访问名号目录文件，根据文件名查到相应的文件内部号；然后访问基本目录文件，根据文件内部号，可直接计算出相应基本目录项所在基本目录文件中的相对位置和物理位置，并将它 直接读入内存。 目录项分解法的优点是提高了文件目录检索速度。 第第5 5章章 操作系统操作系统 5.5.4 文件存储空间的管理 1位示图(Bit Map) 这种方法是利用一串二进制位(Bit)的值来反映磁盘空间的分配情况。每一个磁盘物理块对应1个二进制位，如果物理块为空闲，则相应的二进制位为0；如果物理块已分配，则相应的二进制位为1，如图5-28所示。第第5 5章章 操作系统操作系统 申请磁盘物理块时，可在位示图

177、中从头开始查找为0的字位，将其改为1，返回对应的物理块号；归还物理块时，在位示图中将该块所对应的字位改为0。位示图描述能力强。一个二进制位就描述一个物理块的状态，因而位示图较小，可以复制到内存，使查找既方便又快速。位示图适用于各种文件物理结构的文件系统。第第5 5章章 操作系统操作系统图5-28 位示图 第第5 5章章 操作系统操作系统图5-29 空闲块表 第第5 5章章 操作系统操作系统 2空闲块表 文件系统建立一张空闲块表，该表记录了全部空闲的物理块：包括首空闲块号和空闲块个数，如图5-29所示。空闲块表方式特别适合于文件物理结构为顺序结构的文件系统。 建立新文件时，系统查找空闲块表，寻找

178、合适的表项，分配一组连续的空闲块。如果对应表项所拥有的空闲块个数恰好等于所申请值，就将该表项从空闲块表中删去。当删除文件时，系统收回它所占用的物理块，考虑是否可以与原有空闲块相邻接，合并成更大的空闲区域，最后修改有关表项。第第5 5章章 操作系统操作系统 3空闲块链 系统将所有的空闲物理块连成一个链，用一个指针指向第一个空闲块，然后每个空闲块含有指向下一个空闲块的指针，最后一块的指针为空，表示链尾。外存空间的申请和释放以块为单位，申请时从链首取一块，释放时将其链入链尾。空闲块链节省内存，但申请释放速度较慢，实现效率较低。第第5 5章章 操作系统操作系统 5.5.5 文件存取控制 文件存取控制可

179、以通过文件的共享、保护和保密三个方面体现。 1文件的共享 文件的共享是指一个文件可以允许多个用户共同使用。文件共享不仅是为完成共同的任务所必需的，而且还带来许多好处，如：节省大量的存储空间；减少用户大量重复性劳动；减少实际I/O文件的个数。第第5 5章章 操作系统操作系统 在多级目录结构中，连接法是常用的文件共享技术。对文件共享可以通过两种连接方式实现，一种是允许目录项连接到任一表示文件目录的结点上；另一种是只允许连接到表示普通文件的叶结点上，如图5-30所示。第第5 5章章 操作系统操作系统图5-30 文件的共享第第5 5章章 操作系统操作系统 第一种方式表示可共享目录所连接的目录及其各个子

180、目录所包含的全部文件，例如，dist连接spell的子目录words，则words目录下的3个文件(list1、rac和w7)都为dist所共享。采用这种方式，则可以把所有要共享的文件放在一个公共目录中，所有要共享这些文件的用户可以建立自己的子目录，并且与共享目录连接。这样做便于共享，但对控制和维护造成困难，甚至因使用不当而造成环路连接，产生目录管理混乱。第第5 5章章 操作系统操作系统 第二种连接方式只允许对单个普通文件连接，从而可以通过不同路径访问同一个文件，即一个文件可以有几个“别名”，在图5-30中，/spell/count和/dict/count是表示同一个文件的两个不同的路径名，这

181、种方式更可靠，且易于管理。UNIX采用的是这种连接方式。第第5 5章章 操作系统操作系统 2文件保护与保密 文件保护是指防止由于误操作对文件造成的破坏；文件保密则是防止未经授权的用户对文件进行访问。文件的保护与保密实际上是用户对文件的存取权限的问题，一般为文件的存取设置两级控制：第一级是访问者的识别，即规定哪些用户可以对文件进行操作；第二级是存取权限的识别，即可对文件执行何种操作。实际上，每一个用户对每一个文件的使用权限有三种：R(只读)、W(可写)、E(可执行)。第第5 5章章 操作系统操作系统 对文件加以权限的方法有很多。其中可以利用存取控制矩阵的方法。由于某一文件往往只与特定的少数几个用

182、户有关，所以这是一个稀疏矩阵，如图5-31所示。另外一种是存取控制表，在这个表中，对于某一个文件，只列出与之有关的用户，如图5-32所示。还可以利用口令或加密的方法，在此就不详述了。第第5 5章章 操作系统操作系统图5-31 存取控制矩阵 第第5 5章章 操作系统操作系统图5-32 存取控制表第第5 5章章 操作系统操作系统5.6 作作 业业 管管 理理 5.6.1 操作系统与用户的接口 用户利用计算机解决问题，大致可分成两个步骤：首先是编制程序，其次是使程序在计算机上运行，这两步都离不开操作系统的支持。操作系统是用户与计算机之间的接口，用户是通过操作系统来使用计算机的，操作系统向用户提供有以

183、下一些接口。 第第5 5章章 操作系统操作系统 1程序级接口 程序级接口是由一组系统调用命令(又称广义指令)组成。每条系统调用命令都对应一个由操作系统设计者事先编制好的、能完成某些特定功能的例行程序。在编制程序时，用户像使用其它过程调用语句一样使用系统调用命令，以便得到操作系统的服务。系统调用在程序一级上为用户提供支持，所以称为程序级接口。第第5 5章章 操作系统操作系统 系统调用命令通常分为以下几类： (1) 与文件相关的命令。如创建文件、打开文件、读写文件、关闭文件等。 (2) 与进程相关的命令。如进程创建、撤消、唤醒以及进程间通信等。 (3) 与系统状态有关的命令。如取日历时间、取或设置

184、终端信息等。 (4) 与资源相关的命令(在UNIX系统中设备归入文件类)。如请求或释放指定大小的主存空间等。 显然，系统提供的系统调用命令越多，系统的功能越强，用户使用起来也就越方便。第第5 5章章 操作系统操作系统 2联机用户接口 联机用户接口是用户以交互方式请求操作系统服务的手段，它由键盘命令和屏幕图形命令组成。键盘命令是由联机用户在交互式终端上通过键盘键入的命令，其特点是键入一条便即可执行并把执行结果反馈到屏幕上，充分体现人机之间的交互性。键盘命令的格式随不同的操作系统而有差异，但功能基本上是相同的。第第5 5章章 操作系统操作系统 屏幕图形命令作为一种交互式手段在近年广为流行。它的出现

185、使用户接口更加友好和开放。屏幕图形命令包括多窗口命令、按钮命令、菜单命令、图标命令、滚动条命令等。屏幕图形命令的输入主要是靠鼠标器的点击、拖拽和移动。若点击选中特定菜单项，则系统即刻执行该菜单项所对应的实用程序而完成相应的功能。这种用法十分方便，因为它不要求用户记住任何命令。如Windows操作系统已在图形用户界面上做得相当成功。第第5 5章章 操作系统操作系统 3脱机用户接口 该接口由一组作业控制命令(或称作业控制语言)组成，供脱机用户使用。脱机用户的作业是批处理的，需要有一份用作业控制语言编制的作业说明书，连同作业的程序和数据一起提交给系统。当系统调度该作业执行时，由操作系统对作业说明书上

186、的命令逐条解释执行，直至遇到“撤离”命令而停止该作业为止。第第5 5章章 操作系统操作系统 5.6.2 作业的基本概念 前面已多次用到作业的概念，在此明确它的含义。 作业：是指用户要求计算机处理的一个相对独立的任务。 作业步：是指一个作业分解成几个必须顺序处理的工作步骤。例如，一个用高级语言编写的程序要提交给计算机执行，计算机要完成这项作业一般可分以下几个作业步：编辑、编译、连接装入、运行。这些作业步是顺序进行的，一个作业步运行的结果产生下一个作业步要用的文件。第第5 5章章 操作系统操作系统 作业一般由程序、数据、作业说明书三部分组成。程序是问题求解的算法描述；数据是程序加工的对象，但有些程

187、序未必使用数据；作业说明书是告诉操作系统本作业的程序和数据按什么样的控制要求执行。作业说明书主要包括三方面内容：一是作业基本情况描述，如作业名、用户名、所使用的编程语言等；二是作业的控制描述，如C语言程序先装入哪些模块、后再装入哪些模块等各作业步的操作顺序以及某步不能正常执行时的出错处理方法等；三是作业的资源要求描述，包括估计的主存需要量、计算时间、外设类型及数量、作业优先级等。 在多道程序中，一个作业从提交给计算机，到最后产生结果，其间有多个作业状态的转换，它们可以分为：第第5 5章章 操作系统操作系统 (1) 提交。用户向计算机提交作业，此时称作业处于进入状态。 (2) 收容。计算机通过设

188、备管理程序，将用户作业送入后援存储器中，其后的状态称为后备状态。处于后备状态的作业，实际上是一种随时等待调度的状态。 (3) 执行。作业调度程序从处于后备状态的作业中选出若干作业，分配一定的资源，使之投入运行，该状态也称为运行状态。 (4) 完成。作业执行完毕后的状态，也称为完成状态，此时系统收回资源，并令该作业退出系统。第第5 5章章 操作系统操作系统 作业状态的转换过程如图5-33所示。从后备状态到运行状态，以及从运行状态到完成状态的转换，都是由处理机管理中的作业调度程序完成的。至于作业划分成进程，并按进程的几种状态具体运行，这是由进程调度程序完成的。第第5 5章章 操作系统操作系统图5-

189、33 作业的状态及其转换 第第5 5章章 操作系统操作系统 5.6.3 作业控制块和后备队列 用户怎样把他的作业提交给操作系统，操作系统又是怎样组织、调度、运行作业，这些都属于作业管理范畴。作业管理的主要任务是作业调度和作业控制。 为了便于对作业进行管理和调度，必须随时掌握并记录作业在各运行阶段的状况，包括资源分配及其使用情况，以及作业所处的状态等信息。为此，对每一个进入系统的作业都要建立一个作业控制块JCB(Job Control Block)，以便记录与该作业调度有关的信息。通常每个JCB用一个一维数组表示，不同的操作系统JCB所包含的内容有所不同，图5-34是一种可能的作业控制块的结构形

190、式。第第5 5章章 操作系统操作系统图5-34 作业控制块及由它组成的后备队列第第5 5章章 操作系统操作系统 作业控制块可以看作是对作业的静态和动态情况的说明表。每个作业控制块，自建立后，即与该作业同时存在，直到该作业被系统撤消并从后援存储器中删除，它才随之撤消。 为了便于调度和管理，系统将处于后备状态的所有作业的JCB按照一定的规则排成一个队列，称为作业后备队列。作业调度程序总是把处于后备队列列首的那一个作业作为选中的作业，因此，按什么原则确定作业的排列顺序，以及排成几个队列都与作业调度有关。第第5 5章章 操作系统操作系统 5.6.4 作业调度与作业控制 1作业调度 作业调度就是按照某种

191、调度算法，从后备作业队列中选择一道作业装入主存参与多道作业运行，即进入运行状态。同时，为选中的作业分配内存和外部设备等资源，为其建立有关的进程，当作业执行结束进入完成状态时，作好释放资源等善后处理工作。完成这种功能的程序称为作业调度程序。 第第5 5章章 操作系统操作系统 作业调度的关键在于确定好的调度算法，这要考虑到各种因素。就系统而言，作业类别(主要是多CPU与多I/O作业)之间的良好搭配，使得系统资源的利用率提高；就用户而言，希望尽早获得作业的运行结果。通常对调度算法的性能有如下评估公式： (1) CPU利用率UP=CPU有效工作时间/CPU总的运行时间； (2) 吞吐量=完成的作业道数

192、/完成的时间(h)； (3) 作业平均周转时间T和带权平均周转时间W第第5 5章章 操作系统操作系统 T = ， 其中Ti = 作业i的完成时间?作业i的提交时间， n为进入运行状态的作业道数。 W = W i ，其中Wi = Ti / 作业i实际运行时间。 好的调度算法力求UP高、吞吐量大、T和W小，但实用的算法往往是上述要求之间的折衷。常见的作业调度算法有下面几种。第第5 5章章 操作系统操作系统 (1) 先来先服务(FCFS)。即依作业进入后备队列的自然顺序，先进入的作业先被选中。这种算法简单，容易实现。若一个长作业在先，那么后来的短作业等待时间将很长，显然该算法不利于短作业。长(短)作

193、业不是指作业的物理长度，而是指它运行的时间长(短)。 (2) 最短作业优先(SJF)。即优先选中短作业。由于系统不断地接受新作业，而作业调度程序总是挑选执行时间短的作业，因而使得进入系统早但执行时间长的作业等候时间过长。第第5 5章章 操作系统操作系统 (3) 响应比高者优先。即定义作业的响应比，每次选中响应比高的作业投入运行。响应比等于作业等待时间除以作业运行时间(用户估计值)，作业等待时间越长，则响应比越高，被选中的可能性越大。每当调度时，要对后备队列中各作业的响应比进行计算，取其中最高者。该算法是先来先服务和最短作业优先之间的一种折衷算法，它既照顾到短作业又不使长作业等候时间过长，但以计

194、算响应比的时间开销为代价。第第5 5章章 操作系统操作系统 (4) 优先级法。即每次总是选取优先级高的作业。确定作业优先级的方法是多种多样的，通常根据作业的缓急程度、用户指定的优先级(在JCB中)、作业的长短、等待时间的多少、资源申请情况等确定一个优先级计算公式。由此看来，优先级法可覆盖前面三种算法。例如，只要加大短作业的权值，短作业的优先级就变得高起来，得到优先调度。 例：设多道程序设计系统有供用户使用的主存空间100 KB，磁带机2台，打印机1台，系统采用可变分区方式管理主存，对磁带机和打印机采用静态分配，并假设各作业的输入输出操作时间忽略不计。现有一作业序列如下： 第第5 5章章 操作系

195、统操作系统作业号进入后备队列时间要求计算时间要求主存大小申请磁带机数量申请打印机数量18:0025 min15 KB1台1台28:2010 min30 KB01台38:2020 min60 KB1台048:3020 min20 KB1台058:3515 min10 KB1台1台第第5 5章章 操作系统操作系统 假设作业调度采用先来先服务算法，优先分配主存的低地址区域且不准移动已在主存中的作业。在主存中参与多道运行的作业平分CPU时间。问作业调度选中作业的次序是什么？如果把一个作业从进入后备队列到得出计算结果的时间定义为周转时间，在忽略系统切换作业所耗时间的情况下，最大的作业周转时间是多少？最小

196、的作业周转时间是多少？作业的平均周转时间是多少？何时作业全部执行结束？第第5 5章章 操作系统操作系统 此例的调度情况如图5-35所示。由图可知，作业的调度次序是1，3，4，2，5；最大的作业周转时间为55 min；最小的作业周转时间为30 min；平均周转时间为(30+55+40+40+55)/ 5 = 44 min；9:30全部作业执行结束。第第5 5章章 操作系统操作系统图5-35 作业调度的例子第第5 5章章 操作系统操作系统 从本例可以看出，作业流情况、资源申请情况对作业调度次序和周转时间的影响是显著的。作业调度程序选中某道作业投入运行的含义是：为作业申请所需资源，并把作业装入主存，

197、改作业状态为“运行”；启动作业控制程序，由作业控制程序具体负责作业运行期间的控制。第第5 5章章 操作系统操作系统 2作业控制 在批处理系统中，系统向用户提供作业控制语言(JCL，Job Control Language)，使用户将自己对作业的控制意图写成作业说明书。当作业从后备状态变为运行状态时，作业调度程序为其建立一个作业控制进程，再由该进程具体控制作业的运行。作业控制进程解释执行作业说明书的每一条作业控制语句，按照要求逐个处理作业步，为其建立子进程，完成用户要求。第第5 5章章 操作系统操作系统 5.6.5 UNIX/XENIX操作系统简介 UNIX是一个多用户、多任务的分时操作系统。最

198、早由美国电话与电报公司(AT&T)贝尔实验室(Bell Lab)的Ken Thompson和Dennis Ritchie两人在DEC的PDP-7机上设计的。从1969年至今，它不断地发展、演变并被广泛应用于小型机、超小型机、大型机甚至超大型机。20世纪80年代以来又凭其性能的完善和可移植性，在微型机上也日益流行起来。由于UNIX的巨大成功和它对计算机科学所做的贡献，两位主设计人曾获得国际计算机界的“诺贝尔奖”ACM图灵奖。第第5 5章章 操作系统操作系统 1UNIX系统的层次结构 UNIX系统在结构上可以分为核心和外层两部分，如图5-36所示。核心部分包含了操作系统的主要功能：存储管理、进程管

199、理、设备管理、文件管理等。核心的最外层是系统调用，它是UNIX系统核心部分与外层部分的接口，是用户程序与核心之间仅有的接口。 核心外的Shell是UNIX操作系统的命令程序设计语言和命令解释语言的统称，是用户与UNIX操作系统之间的接口。UNIX系统可同时接纳多个计算机系统的多个用户，Shell是根据用户输入的命令，找到相应模块中的程序，为它建立进程并执行。第第5 5章章 操作系统操作系统图5-36 UNIX系统的层次结构关系 第第5 5章章 操作系统操作系统 2UNIX系统主要特点 由于UNIX系统集中了许多大型机操作系统的特点，适用面很广，特别适用于内存容量大且存储管理能力强的机器，因而成

200、为目前国际上最为流行、应用最广泛的多用户交互式操作系统。 归纳起来，UNIX的主要特点为： (1) UNIX系统吸取了许多操作系统的成功经验，做了合理的取舍，使整个系统短小精悍；第第5 5章章 操作系统操作系统 (2) 采用了进程映像技术。为了最大限度地利用内存空间，内存只存常驻少量数据，大部分进程在内存紧张时调到磁盘上，作为映像文件存放，等到内存空余时再调入内存； (3) 提供了完善的进程控制功能，可以动态建立和消灭进程，提供进程间通信功能和进程跟踪功能； (4) 文件系统为分级树型结构，可动态装卸文件卷； (5) 文件、目录表、外部设备都作为文件统一处理，为用户提供了简单统一的接口； (6

201、) 系统为用户提供功能完备、使用方便的命令程序语言Shell； 第第5 5章章 操作系统操作系统 (7) UNIX绝大部分程序都是用C语言编写。由于C语言具有汇编语言的大部分功能，又不依赖硬件，易阅读，易修改，因此，便于UNIX系统移植到各种不同的机器上。第第5 5章章 操作系统操作系统 3UNIX系统的发展 随着UNIX系统的普及与流行，形成了多种版本及其变种的UNIX系统。从1970年至1978年，不断改进而推出的是V1V7版本。从1981年AT&T发表UNIX System (S3)开始，UNIX不再采用版本(Version)号排列，而改为按系统(System)号排列。另外一个系统是美国

202、加利福尼亚大学伯克利分校开发的带有虚拟存储功能的UNIX系统，它们是1.0BSD，2.0BSD，直到1983年的4.2BSD系统等。第第5 5章章 操作系统操作系统 进入20世纪80年代以来，UNIX开始进入微机市场。1980年Nierosopt公司在UNIX V7基础上，根据微型机的特点对UNIX进行了修改和扩充，这就是XENIX系统。随后，几经修改，microsoft公司发表了不同版本的XENIX。 XENIX与UNIX虽有一些差别，但核内差别大而核外差别小。从用户使用的角度看，Shell命令解释程序、基本命令和主要实用程序的用法几乎完全一样。XENIX只是在微型机上运行的UNIX，两者本

203、质上没有什么不同。第第5 5章章 操作系统操作系统习习 题题 1什么是操作系统？它的作用是什么？2操作系统的资源管理功能包括哪些方面？3什么是批处理、实时、分时操作系统？它们各有什么特征？分别适用哪些场合？4试述现代操作系统的基本特征。5进程有哪些基本特征？它与程序有什么不同？第第5 5章章 操作系统操作系统6一个进程至少有几种状态？它们在什么情况下转换？7什么叫临界资源？什么叫临界区？8用PV操作描述同步互斥的程序其典型结构如何？9进程调度程序的任务是什么？为什么说它把一台物理处理器变成了多台逻辑处理器？10什么情况下可引发进程调度程序的执行？常用的进程调度算法有哪几种？11什么是进程死锁？

204、死锁的产生有哪4个必要条件？第第5 5章章 操作系统操作系统 12设系统中有A、B、C三类资源为10，5，7个，有P0 P1 P2 P3 P4进程，在T0时刻的系统状态如下： 最大需求 已分配 还需要 目前可用资源A B C A B CA B C A B CP07 5 3 0 1 07 4 3 3 3 2P13 2 2 2 0 01 2 2P29 0 2 3 0 26 0 0P32 2 2 2 1 10 1 1 P44 3 3 0 0 24 3 1第第5 5章章 操作系统操作系统 问：(1) T0时刻系统安全吗？如果安全则给出安全序列。 (2) 若此时P1请求A类1个，C类2个，能否分配？为什

205、么？ (3) 在(2)之后有一个新状态，若此时P0请求B类2个，能否分配？为什么？ 13存储管理的主要功能是什么？ 14什么叫地址重定位？在什么情况下采用地址重定位？怎样区分静态地址重定位和动态地址重定位？各有什么优缺点？ 15什么是虚拟存储器？虚拟存储管理的方案有哪些？第第5 5章章 操作系统操作系统 16考虑下面的段表：段号始址段长 0 219600 1230014 29010031345590 4195795 对下面的逻辑地址，求出其物理地址(段式管理)，如越界请指出。 a；b；c；d；e；f。第第5 5章章 操作系统操作系统 17考虑一个进程的主存地址访问序列：10，11，104，70

206、，73，309，185，245，246，434，485，367，问： (1) 如果页面大小为100，给出其页面访问序列。 (2) 进程空间分得的主存块M=2，采用FIFO置换算法，求页面失效率。 18什么叫系统颠簸？产生颠簸的原因是什么？如何检测颠簸？如何消除颠簸？ 19设备管理的任务和功能是什么？ 20简述通道技术和缓冲技术。第第5 5章章 操作系统操作系统 21处理机和外部设备的通信有哪几种基本方式，各有什么特点？ 22设某活动磁盘有200个磁道，编号为0199，磁头当前在143道服务。对于请求序列86，147，91，177，94，150，102，175，130，求在下列调度策略下的磁头移动顺序及移动量(以道数计)： a FCFS； bSSTF； cSCAN 23什么是文件和文件系统？ 24文件的存取方法主要有哪几种？各自的特点是什么？第第5 5章章 操作系统操作系统 25文件系统中磁盘空间管理技术主要有哪几种？比较它们的优缺点。 26文件的物理组织形式主要有哪几种？比较它们的优缺点。 27操作系统与用户的接口由哪几个部分组成？ 28作业有哪几种基本状态？ 29常用的作业调度算法有哪些？ 30在作业调度的例子中，若减少1台磁带机，增加1台打印机，其它条件不变，那么调度情况如何？