操作系统课后作业

第 1 章 操作系统概述 11 什么是操作系统？ 答：计算机操作系统使方便用户、管理和控制计算机软硬件资源的系统软件（或程序集 合） ；操作系统目前有五大类型（批处理、分时、实时、网络和分布式）和五大功能（作业 管理、文件管理、存储管理、设备管理和进程管理） 。 12 简述操作系统的发展历史 答： 手工操作阶段，联机批处理系统，脱机批处理系统，执行系统，多道批处理系统， 分时操作系统，实时操作系统，网络操作系统，分布式操作系统，PC 操作系统。 13 多道程序设计技术的概念是什么？ 答：多道程序设计技术是在计算机内存中同时存放几道相互独立的程序，使它们在管理 程序控制之下，相互交替地运行。当某道程序因某种原因不能继续运行下去时（如等待外部 设备传输数据） ，管理程序便将内存中的另一道程序投入运行，这样可以使 CPU 及各外部设 备尽量处于忙碌状态，从而大大提高了计算机的使用效率。 14 多道程序设计技术的硬件基础是什么？ 答：多道程序设计技术的硬件基础是通道和中断技术。通道是一种输入/输出专用处理 机，它能控制一台或多台外设工作，负责外部设备与内存之间的信息传输。它一旦被启动， 就能独立于 CPU 运行，这样就可使 CPU 和通道并行操作，而且 CPU 和各种外部设备也能并 行操作。中断是指当 CPU 接到外部硬件（如 I/O 设备）发来的信号时，马上停止原来的工作， 转去处理这一事件，在处理完了以后，CPU 又回到原来的工作点继续工作。 15 操作系统的主要功能是什么？ 答：操作系统的主要功能相应地就有理机管理（进程管理） 、存储管理、设备管理、文 件管理和用户接口。 1 进程管理主要包括： 进程控制。为多道程序并发执行而创建进程，并为之分配必要的资源。当进程运行 结束时，撤消该进程，回收该进程所占用的资源，同时，控制进程在运行过程中的状态转换。 进程同步。为使系统中的进程有条不紊地运行，系统要设置进程同步机制，为多个 进程的运行进行协调。 进程通信。系统中的各进程之间有时需要合作，需要交换信息，为此需要进行进程 通信。 进程调度。从进程的就绪队列中，按照一定的算法选择一个进程，把处理机分配给 它，并为它设置运行现场，使之投入运行。 2 存储管理主要包括： 内存分配。为每道程序分配内存空间，并使内存得到充分利用，在作业结束时收回 其所占用的内存空间。 内存保护。保证每道程序都在自己的内存空间运行，彼此互不侵犯，尤其是操作系 统的数据和程序，绝不允许用户程序干扰。 地址映射。在多道程序设计环境下，每个作业是动态装入内存的，作业的逻辑地址 必须转换为内存的物理地址，这一转换称为地址映射。 内存扩充。内存的容量是有限的。为满足用户的需要，通过建立虚拟存储系统来实 现内存容量的逻辑上的扩充。 3 设备管理主要包括： 缓冲管理。由于 CPU 和 I/O 设备的速度相差很大，为缓和这一矛盾，通常在设备管 理中建立 I/O 缓冲区，而对缓冲区的有效管理便是设备管理的一项任务。 设备分配。根据用户程序提出的 I/O 请求和系统中设备的使用情况，按照一定的策略， 将所需设备分配给申请者，设备使用完毕后及时收回。 设备处理。设备处理程序又称设备驱动程序，对于未设置通道的计算机系统其基本 任务通常是实现 CPU 和设备控制器之间的通信。即由 CPU 向设备控制器发出 I/O 指令，要 求它完成指定的 I/O 操作，并能接收由设备控制器来的中断请求，给予及时的响应和相应的 处理。对于设置了通道的计算机系统，设备处理程序还应能根据用户的 I/O 请求，自动构造 通道程序。 设备独立性和虚拟设备。设备独立性是指应用程序独立于具体的物理设备，使用户 编程与实际使用的物理设备无关。虚拟设备的功能是将低速的独占设备改造为高速的共享设 备。 4 文件管理和用户接口 文件存储空间的管理。所有的系统文件和用户文件都存放在文件存储器上。文件存 储空间管理的任务是为新建文件分配存储空间，在一个文件被删除后应及时释放所占用的空 间。文件存储空间管理的目标是提高文件存储空间的利用率，并提高文件系统的工作速度。 目录管理。为方便用户在文件存储器中找到所需文件，通常由系统为每一文件建立 一个目录项，包括文件名、属性以及存放位置等，由若干目录项又可构成一个目录文件。目 录管理的任务是为每一文件建立其目录项，并对目录项加以有效的组织，以方便用户按名存 取。 文件读、写管理。文件读、写管理是文件管理的最基本的功能。文件系统根据用户 给出的文件名去查找文件目录，从中得到文件在文件存储器上的位置，然后利用文件读、写 函数，对文件进行读、写操作。 文件存取控制。为了防止系统中的文件被非法窃取或破坏，在文件系统中应建立有效 的保护机制，以保证文件系统的安全性。 16 操作系统的主要特征是什么？ 答：操作系统的主要特征是并发性、共享性、虚拟性和不确定性。 2 1并发性：并发性是指两个或多个事件在同一时间间隔内发生。在多道程序环境下， 并发性是指在一段时间内，宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻 却仅能有一道程序执行，故微观上这些程序只能是分时地交替执行。倘若在计算机系统中有 多个处理机，则这些可以并发执行的程序便可被分配到多个处理机上，实现并行执行，即利 用每个处理机来处理一个可并发执行的程序，这样，多个程序便可同时执行。两个或多个事 件在同一时刻发生称为并行。在操作系统中存在着许多并发或并行的活动。 2共享性：共享是指系统中的资源可供内存中多个并发执行的程序共同使用。由于资 源属性的不同，对资源共享的方式也不同，目前主要有以下两种资源共享方式互斥共享方式 和同时访问方式。并发和共享是操作系统的两个最基本的特征，它们又互为对方存在的条件。 一方面，资源共享是以程序的并发执行为条件的，若系统不允许程序并发执行，自然不存在 资源共享问题；另一方面，若系统不能对资源共享实施有效管理，协调好多个程序对共享资 源的访问，也必然影响到程序并发执行的程度，甚至根本无法并发执行。 3虚拟性：是指将一个物理实体映射为若干个逻辑实体。前者是客观存在的，后者是 虚构的，是一种感觉性的存在，即主观上的一种想象。 4不确定性：在多道程序环境下，允许多个程序并发执行，但只有程序在获得所需的 资源后方能执行。在单处理机环境下，由于系统中只有一个处理机，因而每次只允许一个程 序执行，其余程序只能等待。内存中的每个程序在何时能获得处理机运行，何时又因提出某 种资源请求而暂停，以及程序以怎样的速度向前推进，每道程序总共需多少时间才能完成， 等等，都是不可预知的。因此，在操作系统中，存在着不确定性。 17 简述 Windows 系列操作系统的发展历史。 答：Windows 系列操作系统是由微软公司从 1985 年起开发的一系列视窗操作系统产品， 包括个人（家用） 、商用和嵌入式 3 条产品线（图 1.4 ） 。个人操作系统包括 Windows Me、Windows 95/98，及更早期的版本 Windows 1.x、2.x、3.x 等，主要在 IBM 个人机系列 上运行。商用操作系统是 Windows 2000 和其前身版本 Windows NT，主要在服务器、工作站 等上运行，也可以在 IBM 个人系列机上运行。嵌入式操作系统有 Windows CE 和手机用操作 系统 stinger 等。 Windows XP 将使家用和商用两条产品线合二为一。截止至 20 世纪末，全世 界运行各种 Windows 版本的计算机有两亿台左右。微软公司从 1983 年开始研制 Windows 操 作系统。当时，IBM PC 进入市场已有两年，微软公司开发的磁盘操作系统 DOS 和编程语言 BASIC 随 IBM PC 捆绑销售，取得了很大的成功。 Windows 操作系统最初的研制目标是在 DOS 的基础上提供一个多任务的图形用户界面。不过，第一个取得成功的图形用户界面系统 并不是 Windows，而是 Windows 的模仿对象苹果公司于 1984 年推出的 Mac OS （运行 于苹果公司的 Macintosh 个人计算机上） ，Macintosh 机及其上的操作系统当时已风靡美国多 年，是 IBM PC 和 DOS 操作系统在当时市场上的主要竞争对手。当年苹果公司曾对 PC 机和 Windows 操作系统不屑一顾，并大力抨击微软公司抄袭 Mac OS 的外观和灵感。但苹果机和 Mac OS 是封闭式体系 （硬件接口不公开、系统源代码不公开等） ，而 IBM PC 和 MS-DOS 是开放式体系 （硬件接口公开、允许并支持第三方厂家做兼容机、公开操作系统源代 码等） 。这个关键的区别使得 IBM PC 后来者居上，销量超过了苹果机，并使得在 IBM PC 上 运行的 Windows 操作系统的普及率超过了 Mac OS，成为个人计算机市场占主导地位的操作 系统。 18 简述 UNIX 系列操作系统的发展历史。 答：“UNIX ”这个名字是取“Multics ”的反义，其诞生背景与特点一如其名。Multics 项目 （ MULTiplexed Information and Computing Service） 由贝尔（电话）实验室 （Bell （Telephone） Laboratories，简称 BTL） 、通用电气公司 （General Electric） 和麻省理工学 院联合开发，旨在建立一个能够同时支持数千个用户的分时系统，该项目因目标过于庞大而 失败，于 1969 年撤销。退出 Multics 项目后，1969 年中期，贝尔实验室的雇员 Thompson 开 始在公司的一台闲置的只有 4KB 内存的 PDP-7 计算机上开发一个“太空漫游”游戏程序。 由于 PDP-7 缺少程序开发环境，为了方便这个游戏程序的开发，Thompson 和公司的另一名 雇员 Ritchie 一起用 GE-645 汇编语言 （以前曾用于 Multics 开发） 开发 PDP-7 上的操作环 境。最初是一个简单的文件系统，很快又添加了一个进程子系统、一个命令解释器和一些实 用工具程序。他们将这个系统命名为 UNIX。 此后，随着贝尔实验室的工作环境的需要，他 们将 UNIX 移植到 PDP-11 上，并逐渐增加了新的功能。很快， UNIX 开始在贝尔实验室内 部流行，许多人都投入到它的开发中来。1971 年， UNIX 程序员手册第 1 版出版，这之 后直到 1989 年，贝尔实验室又相继发行了 10 个版本的 UNIX 和相应的手册。1973 年 Ritchie 用 C 语言重写了 UNIX （UNIX 第 4 版） ，这使得 UNIX 的可移植性大大增强，这是 UNIX 迈向成功之路的关键一步。1973 年 10 月，Thompson 和 Ritchie 在 ACM （Association for Computing Machinery，计算机协会） 的 SOSP （Symposium Operating Systems Principles， 操作系统原理讨论会） 会议上发表了首篇 UNIX 论文，这是 UNIX 首次在贝尔实验室以外 亮相。 UNIX 的第一次移植是由 Wollongong 大学于 1976 年将其移植到 Interdata 机上。其它几 次较早的移植包括：1978 年，微软公司与 SCO 公司合作将 UNIX 移植到 Intel 8086 上，即 XENIX 系统 （最早的 UNIX 商业变种之一） ；1978 年，DEC 公司将 UNIX 移植到 VAX 上， 即 UNIX/32V （ 3BSD 的前身） 。 UNIX 的不断发展导致许多计算机公司开始发行自己机器上的 UNIX 增值商业版本。 UNIX 的第一个商业变种是 1977 年 Interactive Systems 公司的 IS/1 （PDP-11） 。20 世纪 80 年代著名的商业变种有 SUN 公司的 Sun OS、微软公司与 SCO 公司的 XENIX 等。 20 世纪 70 年代中期到 80 年代中期，UNIX 的迅速发展，众多大学和公司的参与，使得 UNIX 的变种迅速增多。这些变种主要围绕 3 条主线：由贝尔实验室发布的 UNIX 研究版 （First Edition UNIX 到 Tenth Edition UNIX，或称 V1 到 V10，以后不再发行新版；由加利福 尼亚州大学伯克利分校发布的 BSD（Berkeley Software Distribution） 和由贝尔实验室发布的 UNIX System 和 System V。 3 到 20 世纪 80 年代，UNIX 已在从微型机到巨型机等众多不同机型上运行。作为通用操 作系统，当时 UNIX 的主要竞争对手是各计算机厂商的专有系统，如 IBM 的 OS 360/370 系 列等。 20 世纪 80 年代后期，UNIX 已经出现了很多变种，变种增多导致了程序的不兼容性和 不可移植 （同一应用程序在不同 UNIX 变种上不能直接运行） 。因此，迫切需要对 UNIX 进 行标准化。这就导致了两大阵营的出现。 1987 年，在统一市场的浪潮中，AT&T 宣布与 SUN 公司合作，将 System V 和 Sun OS 统一为一个系统。其余厂商十分关注这项开发，认为他们的市场处于威胁之下，于是联合开 发新的开放系统。他们的新机构 Open Software Foundation （开放软件基金会，简称 OSF） 于 1988 年成立。作为回应，AT&T 和 SUN 公司联盟亦于 1988 年形成了 UNIX International （UNIX 国际，简称 UI） 。这场“UNIX 战争”将系统厂商划分成 UI 和 OSF 两大阵营。UI 推出了 SVR4，而 OSF 则推出了 OSF/1。虽然两者都是 UNIX，但他们在系统构架、命令操 作以及管理方式上都有所不同。两者在市场上展开了激烈的竞争。 两种 UNIX 系统并存，却又不能相互兼容，这对用户非常不利，因而直接影响了 UNIX 对用户的吸引力。随着 Microsoft 公司的迅速崛起，并以惊人的速度由传统的 PC 机市场向工 作站和网络市场扩张，迫使 UI 和 OSF 两大阵营不得不相互让步、握手言和，从而共同制定 了应用程序接口 API （Application Program Interface） 标准技术规范，并联合开发共同开放 软件环境 COSE （Common Open Software Environment） 。 19 简述 Linux 操作系统的发展历史。 答：Linux 最初是由芬兰赫尔辛基大学计算机系大学生 Linus Torvalds，在从 1990 年底 到 1991 年的几个月中，为了自己的操作系统课程学习和后来上网使用而陆续编写的，在他 自己买的 Intel 386 PC 机上，利用 Tanenbaum 教授自行设计的微型 UNIX 操作系统 Minix 作 为开发平台。据 Linus 说刚开始的时候他根本没有想到要编写一个操作系统内核，更没想到 这一举动会在计算机界产生如此重大的影响。最开始是一个进程切换器，然后是为自己上网 需要而自行编写的终端仿真程序，再后来是为他从网上下载文件而自行编写的硬盘驱动程序 和文件系统。这时候他发现自己已经实现了一个几乎完整的操作系统内核，出于对这个内核 的信心和美好的奉献与发展愿望，Linus 希望这个内核能够免费扩散使用，但出于谨慎，他 并没有在 Minix 新闻组中公布它，而只是于 1991 年底在赫尔辛基大学的一台 FTP 服务器上 发了一则消息，说用户可以下载 Linux 的公开版本（基于 Intel 386 体系结构）和源代码。从 此以后，奇迹发生了。 1993 年，Linux 的第一个产品Linux 1.0 版问世的时候，是按完全自由版权进行扩 散的。它要求所有的源代码必须公开，而且任何人均不得从 Linux 交易中获利。然而半年以 后，Linus 开始意识到这种纯粹的自由软件理想对于 Linux 的扩散和发展来说，实际上是一 种障碍而不是一股推动力，因为它限制了 Linux 以磁盘复制或者 CD-ROM 等媒体形式进行扩 散的可能，也限制了一些商业公司参与 Linux 进一步开发并提供技术支持的良好愿望。于是 Linus 决定转向 GPL 版权，这一版权除了规定有自由软件的各项许可权之外，还允许用户出 售自己的程序复制品。这一版权上的转变后来证明对 Linux 的进一步发展确实极为重要。从 此以后，便有多家技术力量雄厚又善于市场运作的商业软件公司加入了原先完全由业余爱好 者和网络黑客所参与的这场自由软件运动，开发出了多种 Linux 的发布版本，增加了更易于 用户使用的图形界面和众多的软件开发工具，极大地拓展了 Linux 的全球用户基础。Linus 本人也认为：“使 Linux 成为 GPL 的一员是我一生中所做过的最漂亮的一件事。 ”一些软件 公司，如 Red Hat、InfoMagic 等也不失时机地推出了自己的以 Linux 为核心的操作系统版本， 这大大推动了 Linux 的商品化。在一些大的计算机公司的支持下，Linux 还被移植到 Alpha、Power PC、MIPS 及 SPARC 等为处理机的系统上。 随着 Linux 用户基础的不断扩大，性能的不断提高、功能的不断增加，各种平台版本的 不断涌现，以及越来越多商业软件公司的加盟，Linux 已经在不断地向高端发展，开始进入 越来越多的公司和企业计算领域。Linux 被许多公司和 Internet 服务提供商用于 Internet 网页 服务器或电子邮件服务器，并已开始在很多企业计算领域中大显身手。1998 年下半年，由于 Linux 本身的优越性，使得它成为传媒关注的焦点，进而出现了当时的 “Linux 热”：首先是 各大数据库厂商（Oracle、Informix、Sybase 等） ；继而是其它各大软硬件厂商 （IBM、 Intel、Netscape、Corel、 Adeptec、SUN 公司等） ，纷纷宣布支持甚至投资 Linux （支持是指该厂商自己的软硬件产品支持 Linux，即可以在 Linux 下运行，最典型的是推出 xxx for Linux 版或推出预装 Linux 的机器等） 。即使像 SUN 和 HP 这样的公司，尽管它们的 操作系统产品与 Linux 会产生利益冲突，也大力支持 Linux，从而达到促进其硬件产品销售 的目的。 110 自由软件的含义是什么？ 答：自由软件的自由（free）有两个含义：第一是免费，第二是自由。免费是指自由软 件可免费提供给任何用户使用，即便是用于商业目的，并且自由软件的所有源程序代码也是 公开的，可免费得到。自由是指它的源代码不仅公开而且可以自由修改，无论修改的目的是 使自由软件更加完善，还是在对自由软件进行修改的基础上开发上层软件。总之，可以对它 做自己喜欢做的任何事情，除了一两件不能做的事之外（如不能宣称这个系统是你自己开发 的） 。自由软件的出现给人们带来很大的好处：首先，免费可给用户节省相当的费用；其次， 公开源码可吸引尽可能多的开发者参与软件的查错与改进；在开发协调人的控制下，自由软 件新版本的公布、反馈、更新等过程是完全开放的。 第 2 章 进程管理 21 现代操作系统中为什么要引入“进程”概念？它与程序有什么区别？ 4 答：正是因为在这些可以并发执行的程序段之间，存在着某种相互制约的关系，所以每 个程序段的运行都与运行环境密切相关，它不仅要受到其它程序段活动的制约，而且还要依 赖当时系统资源的分配情况。因此，每个可以并发执行的程序段，都可能会因外界条件的限 制而不能运行，被迫处于阻塞状态。这样，对于这些可以并发执行的程序段，只用“程序” 这一概念就不能说明问题的本质。使用程序这一概念只能是简单、孤立、静止地研究分析它 们，而不能深刻地揭示它们之间的内在活动、相互联系及状态变化。因此，必须从变化的角 度，动态地分析研究这些可以并发执行的程序段，真实地反映出系统的独立性、并发性、动 态性和相互制约性。为了准确地描述程序的执行过程，设计出高质量的操作系统，就不能再 用静态的观点，而应该用动态的观点来刻画程序。为此，在操作系统中引入了“进程”的概 念。 在多道程序的环境下，程序的并发执行代替了程序的顺序执行，它破坏了程序的封闭性 和可再现性，使得程序和计算不再一一对应，而且由于资源共享和程序的并发执行导致在各 个程序活动之间可能存在相互制约关系。总之，程序活动不再处于一个封闭系统中，而出现 了许多新的特征，即：独立性、并发性、动态性和相互制约性。在这种情况下，程序这个静 态概念已经不能如实地反映程序活动的这些特征。为此，20 世纪 60 年代中期 MULTICS 系 统的设计者和以 E.W.Dijkstra 为首的 T.H.E 系统的设计者开始广泛使用“进程” （process） 这一新概念来描述系统和用户的程序活动。进程是可并发执行的程序在一个数据集合上的运 行过程，是系统进行资源分配和调度的一个独立单位。 22 叙述进程的并发性和制约性。 答：进程具有并发性。多个进程实体同存于内存中，在一段时间内可以同时运行。并发 性是进程的重要特性，也是操作系统的重要特性。引入进程概念的目的，也正是为了描述和 实现并发执行。 系统中各个并发程序活动具有独立性的一面，但在两个并发程序活动之间有时也会有相 互依赖和相互制约关系。程序之间的制约关系有两种：直接制约关系和间接制约关系。直接 制约关系通常是在彼此之间有逻辑关系的两个并发执行的程序之间发生的，一般是由于各个 程序段要求共享信息引起的。间接制约关系是由于两个并发程序段由于竞争使用同一资源引 起的，得到资源的程序段可以继续执行，得不到资源的程序段就只好暂停等待，直至获得可 用资源时再继续运行。 23 进程的含义是什么？试简述进程的组成。 答：迄今为止，对这一概念尚无一个非常确切的、令人满意的、统一的定义，不同的 人，站在不同的角度，对进程进行了不同的描述，下面列举几个操作系统的权威人士对“进 程”所下的定义： 行为的一个规则叫做程序，程序在 CPU 上执行时所发生的活动称为进程（Dijkstra） 。 一个进程是一系列逐一执行的操作，而操作的确切含义则有赖于我们以何种详尽程 度来描述进程（Brinch.Hansen） 。 进程是这样的计算部分，它可以与别的进程并发执行（Madniek and Donovan） 。 顺序进程( 有时称为任务)是一个程序与其数据集一道顺序通过 CPU 的执行所发生的 活动（Alan C.Shaw） 。 一个进程是由伪 CPU 执行的一个程序（J.H.Saltzer） 。 上述这些从不同角度对进程所做的解释或所下的定义，有些是近似的，有些则侧重某 一方面，这说明进程这一概念尚未完全统一，但长期以来却巳广泛而成功地用于许多系统之 中，成为构造操作系统的不可缺少的强有力的工具。为了强调进程的并发性和动态性，我们 给进程作如下定义：进程是可并发执行的程序在一个数据集合上的运行过程，是系统进行资 源分配和调度的一个独立单位。 有了进程的概念，就可以用动态的观点分析进程的状态变化及相互制约关系。由于进程 执行时的间断性，决定了进程可能具有多种状态。运行中的进程具有三种基本状态：运行、 阻塞、就绪，这三种状态构成了最简单的进程生命周期模型，进程在其生命周期内处于这三 种状态之一，其状态将随着自身的推进和外界环境的变化而变化，由一种状态变迁到另一种 状态。 24 什么叫临界资源？什么叫临界区？ 答：系统中同时存在有许多进程，它们共享各种资源，然而有许多资源在某一时刻只 能允许一个进程使用。例如打印机、磁带机等硬件设备和变量、队列等数据结构，如果有多 个进程同时去使用这类资源就会造成混乱。因此必须保护这些资源，避免两个或多个进程同 时访问这类资源。我们把某段时间内只能允许一个进程使用的资源称为临界资源。 几个进程若共享同一临界资源，它们必须以互相排斥的方式使用这个临界资源，即当一 个进程正在使用某个临界资源且尚未使用完毕时，其它进程必须延迟对该资源的操作，当使 用该资源的进程释放该资源时，其它进程才可使用该资源，任何进程不能从中插进去使用这 个临界资源，否则将会造成信息混乱和操作出错。我们把访问临界资源的代码段称为临界区。 25 生产者与消费者问题的算法中，交换两个 V 操作的次序及交换两个 P 操作的次序会 有什么结果？试说明理由。 答： 26 设有三个进程 A、B、C，其中 A 与 B 构成一对生产者与消费者（A 为生产者，B 为 5 消费者） ，共享一个由 n 个缓冲块组成的缓冲池；B 与 C 也构成一对生产者与消费者（此时 B 为生产者，C 为消费者） ，共享另一个由 m 个缓冲块组成的缓冲池。用 P、V 操作描述它们之 间的同步关系。 答： 27 面包师问题 面包师有很多面包和蛋糕，由 n 个销售人员销售。每个顾客进店后先取一个号，并且等 着叫号。当一个销售人员空闲下来，就叫下一个号。请分别编写销售人员和顾客进程的程序。 答： 28 睡眠的理发师问题 理发店里有一位理发师、一把理发椅和 n 把供等候理发的顾客坐的椅子。如果没有顾客， 理发师便在理发椅上睡觉。当一个顾客到来时，他必须先叫醒理发师，如果理发师正在理发 时又有顾客来到，则如果有空椅子可坐，他们就坐下来等；如果没有空椅子，他就离开。这 里的问题是：为理发师和顾客各编写一段程序，来描述他们行为。要求不能带有竞争条件。 答： 29 证明短进程优先调度算法可使进程的平均等待时间最短。 答： 210 多级反馈队列轮转法的特点是什么？ 答：所谓多级反馈队列轮转法就是把就绪进程按优先级排成多个队列，并赋给每个队列 不同的时间片，高优先级进程的时间片比低优先级进程的时间片小。调度时先选择高优先级 队列的第一个进程，使其投入运行，当该进程时间片用完后，若高优先级队列中还有其它进 程，则按照轮转法依次调度执行，否则转入低一级的就绪队列。只有高优先级就绪队列为空 时，才从低一级的就绪队列中调度进程执行。此种方法既照顾了时间紧迫的进程又兼顾了短 进程同时考虑了长进程，是一种比较理想的进程调度方法。 211 根据下信息，分别画图说明使用先来先服务、时间片轮转、短进程优先、不可抢 占式优先级法和可抢占式优先级法时进程调度情况。 进程名 产生时间 要求服务时间 优先级 P1 0 10 3 P2 1 1 1 P3 2 2 3 P4 3 1 4 P5 4 5 2 答： 212 何谓死锁？产生死锁的四个必要条件是什么？ 答：在许多中型和大型计算机系统中，都希望在各级系统和用户程序上具有动态共享资 源、并发程序设计及进程通信这些特征，来改善系统资源的利用率和提高系统的处理能力。 由于资源的使用往往是互斥的，因此当某个进程提出资源申请后，使得有关进程在无外力协 助下，永远分配不到必需的资源而无法继续运行，这就产生了一种特殊的现象死锁。 由以上例子可知产生死锁现象的原因：一是系统提供的资源不能满足每个进程的使用需 求；二是在多道程序运行时，进程推进顺序不合法。产生死锁有四个必要条件： 互斥条件 对于独占资源，每个资源每次只能给一个进程使用，进程一旦申请到了资源后占 为已有，则排斥其它进程共享该资源。 不剥夺条件 正在使用的资源不可剥夺，进程获得的资源尚未使用完毕之前，只能由占有者自 己释放，不能被其它进程强行占用。 请求和保持条件 进程因未分配到新的资源而受阻，但又不放弃已占有的资源。 环路等待条件 存在进程的循环等待链，前一进程占有的资源正是后一进程所需求的资源，结果 就形成了循环等待的僵持局面。 死锁不仅会发生在两个进程之间，也可能发生在多个进程之间，甚至发生在全部进程之 间。此外，死锁不仅会在动态使用外部设备时发生，而且也可能在动态使用存储区、文件、 缓冲区、数据库时发生，甚至在进程通信过程中发生。随着计算机资源的增加，系统出现死 锁现象的可能性也大大增加，死锁一旦发生，会使整个系统瘫痪而无法工作。因此，要想办 法解决死锁问题。 213 系统有 R1、R2、R3、R4 四种资源，在 T0 时刻进程 P0 、P1 、P2、P3、P4 的资 源占用和需求情况如下表所示。 Max Allocation Available 进程 R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4 P0 0 0 4 4 0 0 3 2 1 6 2 2 P1 2 7 5 0 1 0 0 0 6 P2 3 6 10 10 1 3 5 4 P3 0 9 8 4 0 3 3 2 P4 0 6 6 10 0 0 1 4 系统此时是否处于安全状态？ 若此时 P2 进程发出 Request2 1,2,2,2，系统能否将资源分配给它？ 答： 214 何谓并发？何谓并行？ 答：计算机为我们自动地做某事，实际上是 CPU 自动执行存放在内存中的程序，同时 做几件事就是同时执行几道不同的程序。如果这几道程序同时在不同的 CPU 上执行，则称 之为“并行” ，如果它们分时地运行在同一个 CPU 上则称之为“并发” 。在单 CPU 条件下同 时运行几道程序，从宏观上看，这几道程序是同时向前推进，但从微观上观察则是由单 CPU 按照时间段轮流执行每个程序的一小段，使每个程序都运行到程序的开始与结束之间的某一 处。从逻辑上讲，这几道程序都在运行，但从 CPU 的执行轨迹上观察，却是轮流地为每个 程序执行一段时间，循环往复，直到所有程序依次完成。我们目前使用的计算机几乎都是单 CPU 的机器，但是都能为我们同时完成几件不同的工作，就是采用的 CPU 分时原理。因此， 逻辑上的并行称为“并发” 。 215 为何引入线程？线程与进程的关系是什么？ 答：在操作系统中引入进程的目的，是为了使多个程序并发执行，以改善资源利用率及 提高系统的吞吐量；那么，在操作系统中再引入线程则是为了减少程序并发执行时所付出的 时空开销，使操作系统具有更好的并发性。 线程具有许多传统进程所具有的特征，故又称为轻型进程(Light-Weight Process)或进 程元；而把传统的进程称为重型进程(Heavy-Weight Process)，它相当于只有一个线程的任 务。在引入了线程的操作系统中，通常一个进程都有若干个线程，至少需要有一个线程。 216 为何引入管程？管程有几部分构成？ 答：管程的基本思想是：把分散在各进程中的控制和管理临界资源的临界区集中起来统 一管理。这样既便于系统管理共享资源，又能保证互斥访问。 Hansen 给管程的定义是：一个管程定义了一个数据结构和在此数据结构上能为并发程 序所执行的一组操作，这组操作能同步进程和改变管程中的数据。 一个管程主要由三部分组成：局部于该管程的共享数据，这些数据表示了相应资源的 状态；局部于该管程的一组操作过程，每个过程完成对上述数据的某种规定操作；对局 部于该管程的数据的初始化。 217 何谓进程通信？试列举几种进程通信方式。 答：进程之间的信息交换，就是进程通信。前面介绍的进程同步与互斥，就实现了进程 之间交换信息，但由于交换的信息量少，可以看作是低级通信。并发执行的进程，有交换信 息的各种需要，除同步与互斥外，还可采用其它的通信方式。介绍几种常用的通信方式：共 享存储、消息传递、共享文件。 218 消息通信机制中应设置哪些基本通信原语？ 答：大部分同步方案均采用某个物理实体（如锁、信号量等）实现通信，进程通信原语 中关锁（lock）和开锁 (unlock)是最简单的原语。在这两个原语中设置一个公共变量 X 代表某 个临界资源的状态。如： 0 资源可用 X= 1 资源正在使用 3.存储管理 3.1 存储管理的功能及目的是什么？ 答：在多道程序环境中，存储管理的主要目的有两个：一是提高资源的利用率，尽量满 足多个用户对内存的要求；二是能方便用户使用内存，使用户不必考虑作业具体放在内存哪 块区域，是如何实现正确运行等复杂问题。为此，存储管理一般应能实现如下所述的基本功 能： 按作业要求进行内存分配并进行适时回收。 实现程序中的逻辑地址到物理地址的转换。 对操作系统及用户信息提供存储保护。 实现内存的逻辑扩充，提供给用户更大的存储空间。 3.2 什么是物理地址？什么是逻辑地址？ 答：内存是由若干个存储单元组成的，每个存储单元有一个编号，这种编号可惟一标识 一个存储单元，称为内存地址（或物理地址） 。源程序经过汇编或编译后，形成目标程序， 每个目标程序都是以 0 为基址顺序进行编址的，原来用符号名访问的单元用具体的数据 单元号取代。这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻 辑空间。在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址。 3.3 什么是地址重定位？为什么要进行地址重定位？ 答：为了实现静态或动态存储分配策略，必须考虑地址的重定位问题。我们把用户程序 装入内存时，对有关指令的逻辑地址部分的修改称为地址重定位，即地址重定位是建立用户 程序的逻辑地址与物理地址之间的对应关系。按实现地址重定位的时机不同，地址重定位又 7 分为两种：静态地址重定位和动态地址重定位。 3.4 什么是动态地址重定位？试举例说明实现动态地址重定位的过程。 答：动态地址重定位是在程序执行期间进行的。一般说来，这种转换由专门的硬件机构 来完成，通常采用一个重定位寄存器，在每次进行存储访问时，对取出的逻辑地址加上重定 位寄存器的内容，形成正确的物理地址，重定位寄存器的内容是程序装入内存的起始地址。 举例说明？ 3.5 什么是存储保护？举例说明常用的硬件存储保护措施是如何实现的？ 答：在多道程序设计环境中，要保证各道程序只能在自己的存储区中活动，不能对别的 程序产生干扰和破坏，尤其是不能破坏操作系统的内存区。因此，必须对存储信息采取各种 保护措施，这也是存储管理的一个重要功能。存储信息的保护体现在不能越界访问，破坏操 作系统或其他用户的程序。实现这种存储保护，可以采用硬件的方法，也可采用软、硬件结 合的方法。举例说明？ 3.6 实存管理和虚拟存储器管理方案的区别在哪里？常用的实存管理方案有哪些？ 答：虚拟存储技术的基本思想是把有限的内存空间与大容量的外存统一管理起来，构成 一个远大于实际内存的、虚拟的存储器。此时，外存是作为内存的逻辑延伸，用户并不会感 觉到内、外存的区别，即把两级存储器当作一级存储器来看待。一个作业运行时，其全部信 息装入虚存，实际上可能只有当前运行所必需的一部分信息存入内存，其它则存于外存，当 所访问的信息不在内存时，系统自动将其从外存调入内存。当然，内存中暂时不用的信息也 可调至外存，以腾出内存空间供其它作业使用。这些操作都由存储管理系统自动实现，不需 用户干预。对用户而言，只感觉到系统提供了一个大容量的内存，但这样大容量的内存实际 上并不存在，是一种虚拟的存储器，因此把具有这种功能的存储管理技术称为虚拟存储管理。 实现虚拟存储管理的方法有请求页式存储管理和请求段式存储管理。常用的实存管理方案有 连续存储管理、分页式存储管理、分段式存储管理、段页式存储管理。 3.7 可变式分区存储管理常用的分配算法有哪几种？比较它们的优缺点。 答：可变式分区存储管理，可采用最佳适应算法、首次适应算法和最差适应算法。最佳 适应算法，理论上看起来比较完美，但每次分配时总产生极小的空闲分区，经过一段时间运 行，内存中可能有多个这样的小分区，因太小而无法分配给其它作业使用。这些无法使用的 小分区，我们称之为外部碎片，外部碎片的增多会降低空闲区链表的查找速度。为此，人们 又在此算法中设定一个参数 G，当从一个分区中，分配 Xk 给某作业后，剩余部分小于 G 时， 就把整个分区分配给该作业，不再划分成两部分。采用最佳适应法的另一个问题是，回收一 个分区时，为了把它插入到空闲区链表的合适位置，也是比较费时的。最差适应算法的优点 是查询简单，而且每次分配的总是最大的空闲区，除用户使用的外，剩余的空闲区还可能相 当大，还能装入较大的程序，但缺点也在于此，每次总从最大的空闲分区分配，当有大的作 业到来时，其存储分配申请往往得不到满足。首次适应算法的优点是分配和回收算法都比较 简单，查找速度快，因这个算法总是从低地址开始查找，因此留在高地址部分的大空闲区被 划分机会少，在大作业到来时容易满足。这三种算法，各有利弊。到底哪一种好，不能一概 而论，应针对具体的作业序列来分析。如果对于某一作业序列来说，某种算法能将该作业序 列中的所有作业安置完毕，那么我们就认为该算法对这一作业序列而言是合适的。 3.8 假设某系统内存共 256kb，其中操作系统占用低址 20 kb ，有这样一个作业序列： 作业 1（80kb） ，作业 2（16kb） ，作业 3（140kb） ，连续进入系统，经过一段时间运行，作业 1、3 先后完成。此时，作业 4（120kb） ，作业 5（80kb）要求进入系统，分别采用首次适应 算法和最佳适应算法，处理上述作业序列，完成下列要求： 画出作业 1、2、3 进入内存后，内存的分配情况。 画出作业 1、3 完成后，内存分配情况。 画出两种算法中空白区的链接情况。 哪种算法该对作业序列而言是合适的？ 答： 3.9 什么是内部碎片？什么是外部碎片？如何克服外部碎片问题？ 假设某作业为 3.5k 大小，在逻辑地址 1000 号单元处有指令 Mov R1,3000，3000 号单元有 数据 5678。采用分页式存储管理，页面大小为 1k 字节，该作业进入内存后，其页面 0，1，2，3 被分配到内存的 2、4、6、7 块中，完成下列要求： 画出该作业的页表 画出当执行指令 Mov R1,3000时，如何进行地址重定位，将逻辑地址 3000 号单元处数据 5678 送入 R1 寄存器。 答： 3.10 什么是联想存储器？为什么用联想存储器可有效提高动态地址转换速度？ 答：为了提高查表的速度，人们在分页地址变换机构中，加入一组高速缓冲存储器，用 来存放当前作业的最常用的页号和与之相应的物理块号。一般称这样的寄存器组为快表或联 想存储器。当处理机给出逻辑地址（p，w）时，分页机构一方面取出页号 p，并根据 p 从页 表中查找相应的内存块号 b；另一方面自动把页号 p 送入联想存储器，并和联想存储器各单 元进行比 较 ， 如 与 某 单 元 页 号 相 符 ， 则 输 出 对 应 块 号 b， 并 与 页 内 地 址 w 形 成 物 理 地 址 进 行 访 问 ， 同 时 停 止 前 面 查 找 页 表 的 工 作 。 由 于 联 想 存 储 器 采 用 的 是 高 速 缓 存 ， 其 访 问 速 度 比 访 问 页表 要 快 得 多 。 如 果 在 联 想 存 储 器 中 查 不 到 ， 仍 继 续 在 页 表 中 查 找 ， 并 把 查 找 到 的 页 号 p 和 块 号 b 放 到 联 想 存 储 器 的 空 闲 单 元 中 ， 以 备 下 次 使 用 。 如 无 空 闲 单 元 ， 则 通 常 把 最 先 装 入 的 那 个 页 号淘 汰 ， 以 8 腾 出 位 置 。 应 用 联 想 存 储 器 和 页 表 相 结 合 的 方 式 ， 可 有 效 地 提 高 系 统 动 态 地 址 转 换 的速 度 ， 是 一 种 行 之 有 效 的 方 法 。 3.11 什么是虚拟存储器？使用虚拟存储器有什么好处？ 答 ： 虚拟存储技术的基本思想是把有限的内存空间与大容量的外存统一管理起来，构成 一个远大于实际内存的、虚拟的存储器。此时，外存是作为内存的逻辑延伸，用户并不会感 觉到内、外存的区别，即把两级存储器当作一级存储器来看待。一个作业运行时，其全部信 息装入虚存，实际上可能只有当前运行所必需的一部分信息存入内存，其它则存于外存，当 所访问的信息不在内存时，系统自动将其从外存调入内存。当然，内存中暂时不用的信息也 可调至外存，以腾出内存空间供其它作业使用。这些操作都由存储管理系统自动实现，不需 用户干预。对用户而言，只感觉到系统提供了一个大容量的内存，但这样大容量的内存实际 上并不存在，是一种虚拟的存储器，因此把具有这种功能的存储管理技术称为虚拟存储管理。 实现虚拟存储管理的方法有请求页式存储管理和请求段式存储管理。 3.12 画图说明请求页式存储管理系统中动态地址重定位及缺页中断的处理过程。 答 ： 3.13 请求页式存储管理系统中有哪几种常见的页面置换算法？ 答 ： 最优算法（OPT 算法） 、先进先出算法（FIFO 算法） 、最近最久未使用算法（ LRU 算法） 、LRU 近似算法。 3.14 在一个请求页式存储管理系统中，一个程序的页面走向是： 6，5，4，3，2，1，5，4，3，6，5，4，3，2，1，6，5 请分别采用 FIFO 算法和 LRU 算法，求出在作业分得的内存块数分别为 M=4 和 M=5 时，缺页 中断次数和缺页率各为多少？ 答： 3.15 请求页式和请求段式存储管理的地址变换过程有什么区别？ 答：请求页式和请求段式存储管理的动态地址变换过程有许多相似之处，但两者有着本 质上的区别。主要表现在以下几点： 请求分页存储管理的作业地址空间是一个单一的线性地址空间；而分段存储管理的 作业地址空间是二维的地址空间。 请求分页存储管理中，页的大小是固定的，对于分页活动，用户是不可见的；分段 存储管理中，段的大小是不定的，是信息的逻辑单位，用户是可见的。 请求分页存储管理中，把程序地址分成页号 p 和页内位移量 w 是硬件完成的功能； 分段存储管理中，把程序地址分成段号 s 和段内偏移量 d 是软件的功能。 3.16 请求段式存储管理有哪些优点？ 答：请求段式存储管理有如下优点： 可提供大容量的虚存：这与请求页式存储管理类似。一个作业运行时，内存只存放 较少的段。在作业执行过程中，需要使用某段时再从外存调入；若此时内存无空间，则需进 行段的紧凑或是移出某些段。 允许动态增加段的长度：对于一个较大的段，开始可以装入其中的一部分。当程序 员企图向段中增加新的内容或扩大段的长度时，可以动态增加段的长度。因为段表中有一个 增补位，当访问的地址大于段长时便产生越界中断，此时检查增补位，若为 1，则可增加段 长度，可通过紧凑或移去一些段的办法来实现。 利用允许动态增长段的特性，容易处理变化的数据结构，比如表格和数据段等。 便于段的动态链接：一个作业可能由若干个程序段组成，在采用单一线性地址空间 时，这些程序段要在执行之前完成链接和装配工作，产生出一个完整的连续空间。 这称之 为静态链接。这种工