系统架构设计师考试考点突破、案例分析、试题实战一本通.docx

系统架构设计师 http:/www.educity.cn/jiaocheng/zg3.html系统架构设计师考试考点突破、案例分析、试题实战一本通第1章操作系统根据考试大纲，本章要求考生掌握以下几个方面的知识点：操作系统的类型和结构。操作系统基本原理。网络操作系统及网络管理。1.1考点突破从历年的考试情况来看，本章主要考查操作系统的概念及特点、进程管理、存储管理、文件管理。1.1.1历年考试情况分析在历年的考试试题中，有关操作系统知识的试题如表1-1所示。表1-1 操作系统知识试题分布表按照知识点进行总结和归类的试题分布情况如表1-2所示。表1-2 操作系统知识归类表从表1-2中可以看出，操作系统知识方面的内容在历年的考试中分值非常稳定，一直稳定维持在4分。所占分数比例的趋势如图1-1所示。图1-1 操作系统知识历年试题比例趋势图1.1.2操作系统概论操作系统的定义、功能、类型和层次结构是理解操作系统的工作机制的基础，需要深入理解和掌握。1操作系统的定义任何一个计算机系统都是由两个部分组成的：计算机硬件系统和计算机软件系统。操作系统（Operating System，OS）是计算机系统中的核心系统软件，负责管理和控制计算机系统中硬件和软件资源，合理地组织计算机工作流程和有效利用资源，在计算机与用户之间起接口的作用，如图1-2所示。图1-2 操作系统与硬件/软件的关系其中，其他系统软件包含但不仅限于：语言处理程序、中间件。在计算机系统中引入操作系统的目的可以从4个方面来理解。（1）用户观点操作系统是用户与计算机之间的接口。一方面，用户可以透明地使用计算机软/硬件资源；另一方面，操作系统提供了一些功能强大的系统调用，用户软件可以使用这些系统调用请求操作系统服务。（2）资源管理观点操作系统是计算机资源的管理者，它管理和分配计算机系统硬件和软件资源，合理地组织计算机的工作流程，使资源能为多个用户共享，当用户程序和其他程序争用这些资源时，提供有序的和可控的分配。（3）进程观点操作系统由一个系统核心和若干并发运行的程序组成。这些运行的程序称为“进程”，进程可以分为用户进程和系统进程两大类。每个进程完成特定的任务，系统核心则控制和协调这些进程的运行。（4）分层观点操作系统通常采用分层结构实现，各层次的程序按照一定的结构组织并协调工作。2操作系统的分类操作系统的基本类型有：批处理操作系统、分时操作系统、实时操作系统、网络操作系统、分布式操作系统、嵌入式操作系统、微内核操作系统。（1）批处理操作系统（Batch Processing Operating System）批处理操作系统也称为作业处理系统。在批处理操作系统中，作业成批地装入计算机中，由操作系统在计算机的输入并将其组织好，按一定的算法选择其中的一个或多个作业，将其调入内存使其运行。运行结束后，把结果放入磁盘输出井，由计算机统一输出后交给用户。批处理操作系统中配置了一个监督程序，在该监督程序控制下，系统能够对一批作业自动进行处理。其基本特征是“批量”，把作业的吞吐量作为主要目标，同时兼顾作业的周转时间。批处理操作系统又分为单道批处理和多道批处理系统。单道批处理系统在内存中只能存放一道作业，大大减少了人工操作的时间，提高了机器的利用率。但是，对于某些作业来说，当它发出I/O请求后，CPU（Central Processing Unit，中央处理单元）必须等待I/O的完成，而由于I/O设备的低速性，从而使CPU的利用率很低。为了改善CPU的利用率，引入了多道程序设计技术，就形成了多道批处理操作系统。在多道批处理操作系统中，不仅在内存中可同时有多道作业在运行，而且作业可随时被调入系统，并存放在外存中形成作业队列。然后，由操作系统按一定的原则，从作业队列中调入一个或多个作业进入内存运行。多道批处理系统具有资源利用率高和系统吞吐量大的优点，但它将用户和计算机操作员分开，使用户无法直接与自己的作业进行交互。另外，作业要进行排队，依次处理，因此，作业的平均周转时间较长。（2）分时操作系统（Time Share Operating System）为了解决批处理系统无法进行人机交互的问题，并使多个用户能同时通过自己的终端以交互方式使用计算机，共享主机中的资源，为此，系统中采用了分时技术，即把CPU的时间划分成很短的时间片，轮流地分配给各个终端作业使用。这种操作系统称为分时操作系统，简称分时系统。对于某个作业而言，若在分配给它的时间片内，作业没有执行完毕，也必须将CPU交给下一个作业使用，并等下一轮得到CPU时再继续执行。这样，系统便能及时地响应每个用户的请求，从而使每个用户都能及时地与自己的作业交互。分时系统具有多路性、独立性、及时性、交互性和同时性等特征。（3）实时操作系统（Real Time Operating System）实时操作系统是指当外界事件或数据产生时，能够接收并以足够快的速度予以处理，其处理的结果又能在规定的时间内来控制生产过程或对处理系统作出快速响应，并控制所有实时任务协调一致运行的操作系统。因而，提供及时响应和高可靠性是其主要特点。实时操作系统有硬实时和软实时之分，硬实时要求在规定的时间内必须完成操作，这是在操作系统设计时保证的；软实时则只要按照任务的优先级，尽可能快地完成操作即可。我们通常使用的操作系统在经过一定改变之后就可以变成实时操作系统。（4）网络操作系统（Network Operating System）网络操作系统是指在计算机网络环境下，具有网络功能的操作系统。计算机网络是一个数据通信系统，它把地理上分散的计算机和终端设备连接起来，达到数据通信和资源共享的目的。网络操作系统最主要的特点是网络中各种资源的共享，以及各台计算机之间的通信。有关数据通信与计算机网络方面的详细知识，将在第4章中介绍。（5）分布式操作系统（Distributed Operating System）分布式系统是由多台计算机组成的系统，系统中若干台计算机可以相互合作，共同完成同一个任务。在分布式系统中，任意两台计算机之间都可以利用通信来交换信息，系统中的资源为所有用户共享。分布式系统的优点是各节点的自治性好、资源共享的透明性强、各节点具有协同性，其主要缺点是系统状态不精确、控制机构复杂、通信开销会引起性能的下降。分布式操作系统是网络操作系统的更高级形式，它保持了网络操作系统所拥有的全部功能，与网络操作系统的主要区别在于任务的分布性，即把一个大任务分为若干个子任务，分派到不同的CPU上执行。（6）嵌入式操作系统（Embedded Operation System）嵌入式操作系统运行在嵌入式智能芯片环境中，对整个智能芯片和它所操作、控制的各种部件装置等资源进行统一协调、处理、指挥和控制。嵌入式操作系统具有微型化、可定制、实时性、可靠性、易移植性等特点。嵌入式实时操作系统是指系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。嵌入式实时操作系统的特点是及时性、支持多道程序设计、高可靠性和较强的过载防护能力。（7）微内核操作系统（Microkernel Operating System）微内核操作系统结构是20世纪80年代后期发展起来的，其基本思想是将操作系统中最基本的部分放入内核中，而把操作系统的绝大部分功能都放在微内核外面的一组服务器中实现。这样使得操作系统内核变得非常小，自然提高了系统的可扩展性，增强了系统的可靠性和可移植性，同时微内核操作系统提供了对分布式系统的支持，融入了面向对象技术。虽然微内操作系统具有诸多优点，但它非常完美无缺，在运行效率方面它就不如以前传统的操作系统。当前比较流行的、能支持多处理机运行的操作系统，几乎全部都采用了微内核结构，如卡耐基梅隆大学研制的Mach OS，便属于微内核结构操作系统；又如当前广泛使用的Windows操作系统，也采用了微内核结构。3操作系统的功能从资源管理的观点看，操作系统的功能分成五大部分，即进程管理（处理机管理）、存储管理、文件管理、作业管理和设备管理。这五大部分相互配合，协调工作，实现对计算机系统的资源管理和控制程序的执行，为用户提供方便的使用接口和良好的运行环境。4操作系统的结构设计模式（1）模块化结构操作系统由许多标准的、可兼容的基本单位构成（称为模块），各模块相对独立，模块之间通过规定的接口相互调用。模块化设计方法的优点是缩短了系统的开发周期，缺点是模块之间调用关系复杂、相互依赖，从而使分析、移植和维护系统较易出错。（2）层次化结构层次化结构是指操作系统由若干模块按照某种逻辑关系进行分层组合而成，各层之间只能单向依赖。优点是大大地简化了接口的设计，整个系统的正确性由各层次的正确性来保证，易于保证可靠性，也便于维护和移植。（3）客户/服务器结构操作系统中只包括一个最小的核心，操作系统的其他功能（如文件服务、进程服务等）由用户进程来实现。优点是服务器以用户进程的形式运行而不是运行于核心态，它们不直接访问硬件，单个服务器的崩溃不会导致整个系统的崩溃，它适用于分布式系统。（4）对象模式面向对象的操作系统是按照面向对象思想设计的，具有数据隐藏及消息激活对象等特征。其中，对象是对操作系统管理的信息和资源的抽象，可以被视为受保护的信息或资源的总称。优点是适用于网络操作系统和分布式操作系统中，如Windows NT、Windows Server 2003、Windows Server 2008都被称为对象操作系统。（5）对称多处理模式如果一个操作系统在系统中的所有处理机运行且共享同一内存，这样的系统就是一个对称多处理系统。优点是适合共享存储器结构的多处理机系统，即紧耦合的多处理机系统。1.1.3进程管理进程管理也称为处理机管理，该部分功能是操作系统最为重要的部分，所以也是整个操作系统部分的考查重点，其主要知识点有：进程状态转换图、信号量与PV操作、死锁问题、银行家算法。1进程状态转换图进程状态转换图用于展现进程的状态，以及各种状态之间的转换。最为常见的有：三态模型和五态模型，其后又提出了七态模型。在考试中，要求考生掌握三态模型与五态模型。五态模型是对三态模型的扩展（即五态模型已经包含了三态模型）。标准的五态模型如图1-3所示。图1-3 进程状态转换五态模型从图1-3中可以看出，五态模型中的五态为：执行状态（运行状态）、活跃就绪状态、活跃阻塞状态、挂起就绪状态、挂起阻塞状态。其中，前三种状态组成了三态模型。 执行状态：指进程占有处理机正在CPU上执行的状态。在单CPU系统中，每一时刻只有一个进程处于执行状态。 活跃就绪状态：指进程分配到除处理机以外的必需的资源（已经具备了执行的条件）的状态。进程被创建后处于就绪状态，处于就绪状态的进程可以有多个。 活跃阻塞状态：指进程因等待某个事件的发生而放弃处理机进入等待状态。系统中处于这种状态的进程可以有多个。在三态模型中，总是假设所有的进程都在内存中。事实上，可能出现这样一些情况，例如，由于进程的不断创建，系统的资源已经不能满足进程运行的要求，这个时候就必须把某些进程挂起，对换到磁盘镜像区中，暂时不参与进程调度，起到平滑系统操作负荷的目的。这就形成了挂起就绪状态和挂起阻塞状态。 挂起就绪状态：指进程被移至磁盘镜像区中，此时进程只缺处理机资源。 挂起阻塞状态：指进程被移至磁盘镜像区中，此时进程除了缺处理机资源，还缺其他资源。2信号量与PV操作在操作系统中，进程之间经常会存在互斥（都需要共享独占性资源时）和同步（完成异步的两个进程的协作）两种关系。为了有效地处理这两种情况，W. Dijkstra在 1965年提出信号量和PV操作。信号量是一种特殊的变量，表现形式是一个整型S和一个队列。 P操作：也称为down()、wait()操作，使S=S-1，若S0，进程暂停执行，放入信号量的等待队列。 V操作：也称为up()、signal()操作，使S=S+1，若S0，唤醒等待队列中的一个进程。（1）完成互斥控制为了保护共享资源，不让多个进程同时访问这个共享资源，换句话说，就是阻止多个进程同时进入访问这些资源的代码段，这个代码段称为临界区（也称为管程），这种一次只允许一个进程访问的资源称为临界资源。为了实现进程互斥地进入自己的临界区，代码可以如下所示：P（信号量）临界区V（信号量）由于只允许一个进程进入，因此信号量中整型值的初始应该为1。该值表示可以允许多少个进程进入，当该值0时，其绝对值就是等待使用的进程数，也就是等待队列中的进程数。而当一个进程从临界区出来时，就会将整型值加1，如果等待队列中还有进程，则调入一个新的进程进入（唤醒）。（2）完成同步控制最简单的同步形式是：进程A在另一个进程B到达L2以前，不应前进到超过L1，这样就可以使用程序，如下所示：进程A 进程B L1：P（信号量） L2：V（信号量） 因此，要确保进程B执行V操作之前，不让进程A的运行超过L1，因此信号量的初值就应该为0。这样，如果进程A先执行到L1，那么执行P操作后，信号量的整型值就会小于1，也就停止执行。直到进程B执行到L2时，将信号量的整型值加1，并唤醒它以继续执行。在考试中，该知识点出题形式主要是给出一系列操作，让考生在适当位置填充P操作或V操作。例如，某工厂仓库有一名保管员，该仓库可存放n箱零件。该工厂生产车间有m名工人，只要仓库空闲，工人将生产好的整箱零件放入仓库，并由保管员登记入库数量；该工厂销售部有k名销售员，只要仓库库存数能满足客户要求，便可提货，并由保管员登记出库数量。规定工人和销售员不能同时进入仓库，但是工人和工人，销售员和销售员可以同时进入仓库，其工作流程如图1-4所示。图1-4 仓库管理系统流程为了利用PV操作正确地协调工人和销售员进程之间的工作，设置了信号量S1、S2和S3，它们的初值分别为n、0和1。则图1-4中的ah应分别填写什么操作呢？根据问题给出的条件，我们可以判断出，信号量S1表示仓库空闲位置个数，初值为n；S2表示仓库中零件箱数，初值为0；S3用于实现对保管员的互斥访问，初值为1。对于工人进程，首先应执行P(S1)，看仓库中是否有空闲位置，若有，则将零件送入仓库，然后执行V(S2)，表明仓库中已有一箱零件，通知销售员可以提货。然后执行P(S3)，看保管员是否空闲，若空闲，则登记入库数，然后执行V(S3)，使保管员处于空闲状态。对于销售员进程，首先执行P(S2)，看仓库中是否有货物，若有，则可以提货，然后执行V(S1)，表明已经提走一箱零件，空闲出一个位置，工人进程可以放置货物；然后执行P(S3)，看保管员是否空闲，若空闲，则登记出库数，然后执行V(S3），使保管员处于空闲状态。3前趋图前趋图是一个由节点和有向边构成的有向无循环图。该图通常用于表现事务之间先后顺序的制约关系。图中的每个节点可以表示一个语句、一个程序段或是一个进程，节点间的有向边表示两个节点之间存在的前趋关系。例：在计算机中，经常采用流水线方式执行指令，若每一条指令都可以分解为取指、分析和执行3步。取指操作为Ai，分析操作为Bi和执行操作为Ci (i=1,2,3)。如图1-5所示为3个任务各程序段并发执行的前驱图。图中A1没有前趋节点，称为开始节点，它不受任何制约，可以直接执行；而B1与A2只能在A1执行完成之后才能开始，而B2必须在B1与A2完成之后才能开始；C3没有后继节点，称为终止节点。图1-5 前趋图在前趋图中，执行优后顺序的制约关系可分为两种：直接制约和间接制约。直接制约通常是指一个操作中，多个步骤之间的制约关系，也可以说是“同步的进程之间的制约关系”。例如，在图1-5中，A1、B1、C1是一条指令的取指、分析、执行3个步骤，所以它们之间的关系是直接制约。间接制约通常是指多个操作之间相同步骤的制约关系，也可以说是“互斥的进程之间的制约关系”。例如，在图1-5中，A1、A2、A3之间就存在间接制约的关系。前趋图的应用广泛，在项目开发中，可用前趋图来分析哪些活动可以并行完成。同时，项目管理工具：Pert图、单（双）代号网络图等都融入了前趋图的思想。4死锁问题死锁是指各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想得到资源而又都得不到资源，各并发进程不能继续向前推进的状态。产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。产生死锁有4个必要条件。互斥条件：即一个资源每次只能被一个进程使用，在操作系统中这是真实存在的情况。保持和等待条件：有一个进程已获得了一些资源，但因请求其他资源被阻塞时，对已获得的资源保持不放。不剥夺条件：有些系统资源是不可剥夺的，当某个进程已获得这种资源后，系统不能强行收回，只能由进程使用完时自己释放。环路等待条件：若干个进程形成环形链，每个进程都占用对方要申请的下一个资源。对待死锁的策略主要有以下4种。死锁的预防。不让任一产生死锁的必要条件发生就可以预防死锁。死锁的避免。这种策略不对用户进程的推进顺序加以限制，在进程申请资源时先判断这次分配安全否，只有安全才实施分配，典型的算法是银行家算法。死锁的检测。这种策略采用资源请求分配图的化简方法来判断是否发生了不安全状态。资源请求分配图是一种有向图，表示进程与资源之间的关系。死锁的检测是在需要的时刻执行的，当发现系统处于不安全状态时，即执行死锁的解除策略。死锁的解除。解除死锁的基本方法是剥夺。一种方法是把资源从一些进程处剥夺分给别的进程，被剥夺资源的进程则需回退到请求资源处重新等待执行；另一种方法是终止一个进程，剥夺其全部资源，以后再重新运行被终止的进程。5银行家算法银行家算法是一种经典的死锁避免方法。银行家算法的基本思想是：当某个进程提出申请时，必须判断将资源分配给该进程后，会不会引起死锁。若不会，则进行分配；否则就不分配。这样做能保证在任何时刻至少有一个进程可以得到所需的全部资源而执行结束，并将归还资源加入到系统的剩余资源中，这些资源又至少可以满足一个进程的最大需求，于是保证所有进程都能在有限的时间内得到需求的全部资源。按照银行家算法的思想，当进程请求资源时，系统将按如下原则分配资源：当一个进程对资源的最大需求量不超过系统中的资源数时，可以接纳该进程。进程可以分期请求资源，但请求的总数不能超过最大需求量。当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源。当系统现有的资源能满足进程尚需资源数时，必须测试系统现存的资源能否满足该进程尚需的最大资源数，若能满足，则按当前的申请量分配资源，否则，推迟分配。1.1.4存储管理存储管理是操作系统的重要职能之一，它的主要任务是对内存空间进行分配与回收。由于计算机内存容量有限，故在此基础之上发展产生了虚拟存储系统。虚拟存储系统的基本思想是用外存来换取内存。它通过将运行进程访问的地址（逻辑地址、虚拟地址）与主存的物理地址（实地址）分开，从而使得提供大于物理地址的逻辑地址空间成为可能。建立虚拟地址和实地址之间的对应关系、实现转换的工作就称为“虚存管理”。在本节中，主要介绍虚存的组织结构及管理。1页式存储组织页式存储组织的基本原理是将各进程的虚拟空间划分为若干个长度相等的页，把内存空间以与页相等的大小划分为大小相等的片或页面，采用请求调页或预调页技术实现内、外存的统一管理。页式存储组织的主要优点是利用率高，产生的内存碎片小，内存空间分配及管理简单。主要缺点是要有相应的硬件支持，增加了系统开销；请求调页的算法如选择不当，有可能产生“抖动”（又称Belady）现象。2段式存储组织一个作业是由若干个具有逻辑意义的段（如主程序、子程序、数据段等）组成的。在分段系统中，允许程序（作业）占据内存中若干分离的分区。分段系统中的虚地址是一个有序对（段号，段内位移）。系统为每一个作业建立一个段表，其内容包括段号与内存起始地址的对应关系、段长和状态等。状态指出这个段是否已调入内存，若已调入内存，则指出这个段的起始地址位置，状态同时也指出这个段的访问权限。如果该段尚未调入内存，则产生缺段中断，以便装入所需要的段。段式存储组织的主要优点有：便于多道程序共享内存、便于对存储器的保护、各段程序修改互不影响。其缺点是内存利用率低、内存碎片浪费大。3段页式存储组织段页式存储组织是分段式和分页式结合的存储组织方法，这样可充分利用分段管理和分页管理的优点。在段页式管理的存储器中，程序按逻辑单位分成基本独立的段，再把每段分成固定大小的页。内存则等分成与上述页大小相等的页。程序对内存的调入或调出是按页进行的。但它又可按段实现共享和保护。在多道程序环境中，每道程序都有一张段表和一个作为用户标志的基号。一个逻辑地址中，除了基号x、段号s和页号p外，还有一个页内地址d。每个逻辑地址变换成实地址的过程如下：根据基号找到相应的基址寄存器，由该基址寄存器内容找到该程序对应的段表始地址，再由段号找到该段表中相应行地址，该行地址中的内容为页表起始地址，再由页号找到物理页号的地址（已是内存中的某页），它与页内地址拼接后即得物理地址。可见段页式管理中需要多次查表才能最终获得物理地址。该过程可简单地用一个式子来示意，即其中，(x)表示基寄存器中地址为x的单元内容，n为页内地址的位数。段页式管理将段式存储管理和页式存储管理两种方式相结合，互相取长补短，充分发挥了它们的优点。使段页式虚拟存储器管理方案具有空间浪费小、存储共享容易、存储保护容易、能动态连接的特点。但由于管理软件的增加，复杂性和开销也随之增加，需要的硬件及占用的内存也有所增加，使得执行速度大大下降。4页面置换算法由于实际主存是小于虚存的，因此可能会发生内存中已满，但需要使用的页不在主存中这一情况。这时就需要进行置换，即将一些主存中的页淘汰到外存，腾出空间给要使用的页，这个过程也称为Swapping。其工作原理与Cache调入相类似。常见的页面置换算法有以下几种。（1）最优算法（OPT）淘汰不用的或最远的、将来才用的页。这是一种理想算法，不可能实现，只是用来作为衡量算法效率的参照物。（2）随机算法（RAND）随机淘汰,这种算法开销小，但性能不稳定。（3）先进先出算法（FIFO）淘汰最早调入（也是驻留时间最长）的页。实现FIFO算法需要把各个已分配页面按页面分配时间顺序链接起来，组成FIFO队列，并设置一个置换指针，指向FIFO队列的队首页面。FIFO算法忽略了一种现象的存在，那就是在内存中停留时间最长的页往往也是经常要访问的页。将这些页淘汰，很可能刚置换出去，又请求调用该页，致使缺页中断太频繁，严重降低内存的利用率。FIFO的另一个缺点是它可能会产生一种异常现象。一般来说，对于任一作业或进程，如果给它分配的内存页面数越接近于它所要求的页面数，则发生缺页的次数会越少。但使用FIFO算法时，有时会出现分配的页面数增多，缺页次数反而增加的现象，称为“抖动”（又称Belady）现象。（4）最近最久未使用算法（LRU）淘汰离当前时刻最近的一段时间内使用得最少的页。例如，考虑一个仅460个字节的程序的内存访问序列（10，11，104，170，73，309，185，245，246，434，458，364），页面的大小为100个字节，则460个字节应占5页，编号为04，第0页字节为099，第1页为100199，依此类推。得到页面的访问序列是（0，0，1，1，0，3，1，2，2，4，4，3），可简化为（0，1，0，3，1，2，4，3）。如果内存中有200个字节可供程序使用，则内存提供2个页帧供程序使用。按照FIFO算法，共产生6次缺页中断，如表1-3所示。表1-3 FIFO算法缺页中断按照LRU算法，共产生7次缺页中断，如表1-4所示。表1-4 LRU算法缺页中断（5）最近没有使用页面置换算法（NUR）在需要置换某一页时，从那些最近的一个时期内未被访问的页任选一页置换。只要在页表中增设一个访问位即可实现。当某页被访问时，访问位置为1，否则访问位置为0。系统周期性地对所有引用位清0。当需淘汰一页时，从那些访问位为零的页中选一页进行淘汰。（6）时钟页面替换算法（Clock）使用页表中的引用位，将作业已调入内存的页面连成循环队列，用一个指针指向循环队列中的下一个将被替换的页面。其实现方法如下：一个页面首次装入内存时，其引用位置1；在内存中的任何一个页面被访问时，其引用位置1；淘汰页面时，存储管理从指针当前指向的页面开始扫描循环队列，把所遇到的引用位是1的页面的引用位清0，并跳过这个页面；把所遇到的引用位是0的页面淘汰掉，指针推进一步；扫描循环队列时，如果遇到的所有页面的引用位均为1，则指针就会绕整个循环队列一圈，将碰到的所有页面的引用位清0；指针停在起始位置，并淘汰掉这一页，然后指针推进一步。5局部性原理存储管理策略的基础是局部性原理，即进程往往会不均匀地、高度局部化地访问内存。局部性分为时间局部性和空间局部性。时间局部性是指最近访问存储位置，很可能在不久的将来还要访问；空间局部性是指存储访问有聚集的倾向，当访问了某个位置后，很可能也要访问其附近的位置。根据局部性原理的特征性，Denning阐述了程序性能的工作集理论。工作集是进程频繁访问的页面的集合。工作集理论指出，为使进程有效地运行，它的页面工作集应驻留内存中。否则，由于进程频繁地从外存请求页面，而出现称为“抖动”（又称Belady）的过度的页面调度活动。此时，处理页面调度的时间超过了程序的执行时间。显然，此时CPU的有效利用率会急速下降。工作集的大小依赖于工作集窗口（进程在定长时间间隔中涉及的页面的集合）的大小，在进程执行时，工作集会发生变化。有时，当进程进入另一个完全不同的执行阶段时，工作集会出现显著的变化。不过在一个进程的执行过程中，工作集的大小处于稳定状态的时间基本上占绝大多数。另一种控制“抖动”的技术是控制缺页率。操作系统规定缺页率的上下限，当一个进程的缺页率高于上限时，表明该进程需要更大的内存空间，则分配较多的内存页面给它。当进程的缺页率低于下限时，表明该进程占用的内存空间过大，可以适当地收回若干内存页面。1.1.5文件管理对文件管理部分的考查主要集中于位示图、树形目录结构及索引文件结构。1树形目录结构在计算机的文件系统中，一般采用树形目录结构。在树形目录结构中，树的根节点为根目录，数据文件作为树叶，其他所有目录均作为树的节点。根目录隐含于一个硬盘的一个分区中，根目录在最顶层。它包含的子目录是一级子目录。每一个一级子目录又可以包含若干二级子目录，这样的组织结构就叫做目录树。当前盘和当前目录是系统默认的操作对象。如果用户没有指明操作对象，系统就将用户命令指向当前盘和当前目录。路径是指从根目录或者当前目录开始到访问对象（目录或者文件），在目录树中经过的所有目录的序列。例如，“c:doslmousemouse”就是Windows系统中的一条路径。在树形目录结构中，从根目录到任何数据文件之间，只有一条唯一的通路，从树根开始，把全部目录文件名与数据文件名，依次用“/”（UNIX/Linux系统）或“”（Windows系统）连接起来，构成该数据文件的路径名，且每个数据文件的路径名是唯一的。这样，可以解决文件重名问题。从树根开始的路径为绝对路径，如果文件系统有很多级时，使用不是很方便，所以引入相对路径，即是从当前目录开始，再逐级通过中间的目录文件，最后到达所要访问的数据文件。绝对路径给出文件或目录位置的完全的描述，通常由层次结构的顶端开始（根目录），通常第一个字符是“/”（UNIX/Linux系统）或者是盘符（Windows系统）。相对路径通常由目录结构中的当前的位置开始，一般都比绝对路径要短。父目录是指当前路径的上一层目录。每个目录下都有代表当前目录的“.”文件和代表当前目录父目录的“.”文件，相对路径名一般就是从“.”开始的。2位示图位示图法是为管理磁盘空闲存储空间而提出的一种方法。该方法是在外存上建立一张位示图（Bitmap），记录文件存储器的使用情况。每一位仅对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。文件存储器上的物理块依次编号为：0、1、2、。假如系统中字长为32位，有4096个物理块，那么在位示图中的第1个字对应文件存储器上的0、1、2、31号物理块；第2个字对应文件存储器上的32、33、34、63号物理块；第32字对应文件存储器上的4064、4065、4095号物理块。这样位示图的大小为32字。位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，如图1-6所示。当其值为“0”时，表示对应的盘块空闲；为“1”时表示已分配。由所有盘块对应的位构成一个集合，称为位示图。位示图也可描述为一个二维数组map：Var map:array1.m,1.nof bit;图1-6 位示图3索引文件索引文件是一种对文件存储不连续分配的方法。为每个文件建立一张索引表，索引表中的每一表项指出文件信息所在的逻辑块号和与之对应的物理块号。索引文件既可以满足文件动态增长的要求，又可以方便而迅速地实现随机存取。对一些大的文件，当索引表的大小超过一个物理块时，会发生索引表的分配问题。一般采用多级（间接索引）技术，这时，在由索引表指出的物理块中存放的不是文件存放处而是存放文件信息的物理块地址。这样，如果一个物理块能存储n个地址，则一级间接索引将使可寻址的文件长度变成n2块，对于更大的文件可以采用二级甚至三级间接索引（例如，UNIX操作系统采用三级索引结构，如图1-7所示）。图1-7 索引结构图索引文件的优点是既适用于顺序存取，又适用于随机存取；缺点是索引表增加了存储空间的开销。另外，在存取文件时需要访问两次磁盘，一次是访问索引表，另一次是根据索引表提供的物理块号访问文件信息。为了提高效率，一种改进的方法是，在对某个文件进行操作之前，预先把索引表调入内存。这样，文件的存取就能直接从在内存的索引表中确定相应的物理块号，从而只需要访问一次磁盘。1.2典型试题分析1.2.1试题1（1） 不是操作系统关心的主要问题。（1） A管理计算机裸机 B设计、提供用户程序与计算机硬件系统的界面 C管理计算机系统资源 D高级程序设计语言的编译器试题分析操作系统有2个重要的功能，一是通过资源管理，提高计算机系统的效率；二是改善人机界面，向用户提供友好的工作环境。因此，在所给的选项中，显然只有D不是操作系统关心的主要问题。试题答案（1）D1.2.2试题2某书店有一个收银员，该书店最多允许n个购书者进入。将收银员和购书者看做不同的进程，其工作流程如图1-8所示。利用PV操作实现该过程，设置信号量S1、S2和Sn，初值分别为0、0、n。则图1-8中a1和a2应填入（2） ， b1和b2应填入（3） 。图1-8 购书工作流程（2）AV(S1)、P(S2) BV(Sn)、P(Sn) CP(S1)、V(S2) DP(S2)、V(S1)（3）AP(Sn)、V(S2) BV(Sn)、P(S2) CP(S1)、V(S2) DP(S2)、V(S1)试题分析根据试题描述，在本题中，Sn显然是代表允许进入书店的购书者的人数，初值为n，表示可以进入n个购书者。S2用于实现对收银员的互斥访问，初值为0，表示收银员空闲，可以付款。S1代表有多少顾客等待付款，初值为0，表示没有顾客付款。整个工作流程描述如下：首先是收银员上班，执行P(S1)，看是否有顾客付款，如果没有，则阻塞。否则，开始收费，收费完毕后，再执行V(S2)，表示收银员空闲。购书者进入书店后，执行P(Sn)，然后购书，当要付款时，执行V(S1)，表示多了一个顾客在等待付款，然后执行P(S2)，看收银员是否忙，如果忙，则阻塞。否则，开始付款。顾客离开书店时，执行V(Sn)。试题答案（2）A（3）C1.2.3试题3影响文件系统可靠性因素之一是文件系统的一致性问题，如果读取（4） 的某磁盘块，修改后在写回磁盘前系统崩溃，则对系统的影响相对较大。通常的解决方案是采用文件系统的一致性检查，一致性检查包括块的一致性检查和文件的一致性检查。在块的一致性检查时，检测程序构造一张表，表中为每个块设立两个计数器，一个跟踪该块在文件中出现的次数，一个跟踪该块在空闲表中出现的次数。若系统有16个块，检测程序通过检测发现表（5） 状态下的文件系统是一致的。（4）A用户文件的某磁盘块 B空闲表磁盘块 C用户目录文件 D系统目录文件（5）试题分析影响文件系统可靠性因素之一是文件系统的一致性问题，如果读取系统目录文件的某磁盘块，修改后在写回磁盘前系统崩溃，则对系统的影响相对较大。因为很多文件系统是先读取磁盘块到主存，在主存进行修改，然后写回磁盘。但如果读取某磁盘块，修改后再将信息写回磁盘前系统崩溃，则文件系统就可能会出现不一致性状态。如果这些未被写回的磁盘块是系统目录文件，如索引节点块、目录块或空闲管理块等，那么后果是很严重的。通常的解决方案是采用文件系统的一致性检查，一致性检查包括块的一致性检查和文件的一致性检查。在块的一致性检查时，检测程序构造一张表，表中为每个块设立两个计数器，一个跟踪该块在文件中出现的次数，一个跟踪该块在空闲表中出现的次数。若系统有16个块，当进行文件的一致性检查时发现，选项A的第3块在计数器1中为0，这意味着没有文件使用这个块，但在计数器2中也为0，这意味着这个块不空闲。因此，文件系统进行一致性检查时发现出了问题。选项C的第6块在计数器1中为3，说明这个块被重复分配了3次，因此文件系统进行一致性检查时发现出了问题。选项D的第8块在计数器2中为2，说明这个块被重复释放了2次，因此文件系统进行一致性检查时发现出了问题。选项B的某个块在计数器1中为1，在计数器2为0；而某个块在计数器1中为0，在计数器2中为1。这说明文件系统的一致性检查是正确的。试题答案（4）D （5）B1.2.4试题4如图1-9（a）所示是某一个时刻J1、J2、J3、J4四个作业在内存中的分配情况，若此时操作系统先为J5分配5KB空间，接着又为J6分配10KB空间，那么操作系统采用分区管理中的（6） 算法，使得分配内存后的情况如图1-9（b）所示。图1-9 作业在内存中的分配情况（6）A最先适应 B最佳适应 C最后适应 D最差适应试题分析根据图1-9（a），为J1、J2、J3、J4分配了内存后，内存剩余空间为J1与J2之间的15KB、J2和J3之间的10KB、J3和J4之间的30KB。当为任务J5分配5KB空间时，系统选择了分配在J2和J3之间的10KB，然后为任务J6分配10KB空间时，系统选择了分配在J1和J2之间的15KB，因此采用的是最佳适应算法。试题答案（6）B1.2.5试题5系统中有R类资源m个，现有n个进程互斥使用。若每个进程对R资源的最大需求为w，那么当m、n、w取如表1-5所示的值时，对于表1-5中的ae这5种情况， （7） 可能会发生死锁。表1-5 进程和资源表（7）Aa和b Bb和c Cc和d Dc和e试题分析本题考查死锁的基本知识，给出系统资源情况，判断死锁是否可能发生是一种典型的出题方式。当给定资源情况，如何进行死锁判断呢？在此给出一个简单的公式：进程数（每个进程所需资源数-1）+1得到当前条件下，保证不产生死锁所需要的最少资源数。这个公式的原理为：最坏的情况下，系统的资源是平均分配，这种情况下，若每个进程分到了（所需资源数-1）个资源，则再来一个资源，即可完成进程操作。在这种情况下若系统还有1个资源，则无论这个资源分配给谁，都能保障其顺序执行完。当一个进程执行完以后，将释放其占用的所有资源，所以就不会产生死锁。利用该方法可以计算出c与e两种情况都有可能产生死锁。试题答案（7）D1.2.6试题6在一个单CPU的计算机系统中，有3台不同的外部设备R1、R2、R3 和3个进程P1、P2、P3。系统CPU调度采用可剥夺式优先级的进程调度方案，3个进程的优先级、使用设备的先后顺序和占用设备时间如表1-6所示。表1-6 进程占用设备情况假设操作系统的开销忽略不计，从3个进程同时投入运行到全部完成，CPU 的利用率约为（8） %；R3 的利用率约为（9） %（设备的利用率指该设备的使用时间与进程组全部完成所占用时间的比率）。（8）A.66.7 B.75 C.83.3D.91.7（9）A.66 B.50 C.33D.17试题分析根据表1-6画出系统的时空图，如图1-10所示。从图1-10中可以看出，P1从投入运行到完成需要60ms，P2运行时间为90ms，P3由于等待资源，运行时间延长为120ms。CPU在80ms100ms共20ms时间内没有利用，所以利用率为100/120=83.3%，同样计算得R3的利用率为60/120=50%。试题答案（8）C （9）B1.2.7试题7在如图1-11所示的树形文件系统中，方框表示目录，圆圈表示文件，“/”表示路径中的分隔符，“/”在路径之首时表示根目录。图1-10 系统时空图 图1-11 树形文件系统假设当前目录是D2，进程A以如下两种方式打开文件f2：方式 fd1=open( （10） /f2 ,O_RDONLY);方式 fd1=open( /D2/W2/f2 , O_RDONLY);其中，方式的工作效率比方式的工作效率高，因为采用方式，文件系统是从（11） 。（10）A/D2/W2 BD2/W2 CW2 D/W2（11）A根目录开始查找文件f2，系统查找时间少，读取f2文件次数不变 B当前路径开始查找文件f2，系统查找时间少，读取f2文件次数少 C根目录开始查找文件f2，系统查找时间少，读取f2文件次数少 D当前路径开始查找文件f2，系统查找时间少，读取f2文件次数不变试题分析在树形目录结构中，树的根节点为根目录，数据文件作为树叶，其他所有目录均作为树的节点。在树形目录结构中，从根目录到任何数据文件之间，只有一条唯一的通路。从树根开始，把全部目录文件名与数据文件名依次用“/”连接起来，构成该数据文件的路径名，且每个数据文件的路径名是唯一的。这样可以解决文件重名问题，所以，对于第（10）空，虽然数据文件名均为f2，但不一定是相同的文件。从树根开始的路径名为绝对路径名，如果文件系统没有很多级时，使用不是很方便，所以引入相对路径名，即从当前目录开始，逐级通过中间的目录文件，最后到达所要访问的数据文件。同样，从当前目录开始，采用相对路径名，较之采用绝对路径名，可以减少系统访问目录文件的次数，但是访问文件f2的次数是不变的。试题答案（10）C（11）D1.2.8试题8虚拟内存是基于程序的局部性原理而设计的。下面关于局部性原理的描述正确的是（12） 。（12）A程序代码顺序执行 B程序按照非一致性方式访问内存 C程序连续地访问许多变量 D程序在一段时间内访问相对小的一段地址空间试题分析程序的局部性原理，即程序的地址访问流很强的时序相关性，未来的访问模式与最近已发生的访问模式相似。虚拟内存操作是基于程序执行的局部性原理，程序的局部性包括时间局部性和空间局部性，其中空间局部性是指程序在一段时间内访问相对小的一段地址空间。试题答案（12）D1.2.9试题9（13） 操作需要特权指令执行。（13）A读取当前时钟 B清除一块内存 C关闭中断 D从用户态切换到管态试题分析多任务的计算机系统中，特权指令主要用于系统资源的分配和管理，包括改变系统的工作方式、修改虚拟存储器管理的段表和页表、I/O指令、设置时钟、设置控制寄存器和关闭中断等。简言之，不允许用用户程序中直接使用的指令称为“特权指令”。这里，A、B、D选项可以由用户程序直接使用，而C是不可以直接使用的。试题答案（13）C1.2.10试题10关于分页式虚拟存储器的论述，正确的是（14）。（14）A根据程序的模块性，确定页面大小 B可以将程序放置在页面内的任意位置 C可以从逻辑上极大地扩充内存容量，并且使内存分配方便、利用率高 D将正在运行的程序全部装入内存试题分析由于内存的大小总是有限的，如果都采用“实存管理”，那么大于总物理内存的作业就无法运行。为了解决这一问题，可行的方法就是用外存来换取内存，这也就是虚拟存储系统。它通过将运行进程访问的地址（逻辑地址、虚拟地址）与主存的物理地址（实地址）分开，从而就使得提供大于物理地址的逻辑地址空间成为可能。而建立虚拟地址和实地址之间的对应关系、实现转换的工作就称为“虚存管理”。设置虚拟存储器的目的就是要从逻辑上极大地扩充内存容量，并且使内存分配方便、利用率高。虚拟存储可以分为分区式、分页式、分段式、段页式等方法。分页的基本思想是把程序的逻辑空间和内存的物理空间按照同样的大小划分成若干页面，以页面为单位进行分配。在页式存储管理中，系统中虚地址是一个有序对（页号，位移）。系统为每一个进程建立一个页表，其内容包括进程的逻辑页号与物理页号的对应关系、状态等。试题答案（14）C1.2.11试题11通常将“C:Windowsmyprogram.exe”文件设置成只读和隐藏属性，以便控制用户对该文件的访问，这一级安全管理称为（15） 安全管理。（15）A文件级 B目录级 C用户级 D系统级试题分析系统级安全管理的主要任务是不允许未经核准的用户进入系统。用户级安全管理是为了给用户分配文件访问权而设计的，包括对所有用户进行分类、为指定用户分配文件访问权。目录级安全管理是为保护系统中的各种目录而设计的，它与用户权限无关。为保证目录的安全，规定只有系统核心才具有写目录的权利。通常，系统是分别为用户和目录独立地指定权限的。文件级安全管理是通过系统管理员或文件主对文件属性的设置，来控制用户对文件访问。试题答案（15）A1.2.12试题12某文件管理系统在磁盘上建立了位示图（Bitmap），记录磁盘的使用情况。若磁盘上的物理块依次编号为0、1、2、，系统中字长为32位，每一位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用，如下所示。假设将4195号物理块分配给某文件，那么该物理块的使用情况在位示图中的第（16） 个字中描述；系统应该将（17）。（16）A.128 B.129 C.130 D.131（17）A该字的第3位置“0” B该字的第3位置“1” C该字的第4位置“0” D该字的第4位置“1” 试题分析因为物理块编号是从0开始的，所以4195号物理块其实就是第4196块。因为字长为32位，也就是说，每个字可以记录32个物理块的使用情况。4196/32=131.125，所以，4195号物理块应该在第131个字中（字的编号也是从0开始计数）。那么，具体在第131个字的哪一位呢？到第130个字为止，共保存了13132=4192个物理块（04191），所以，第4195块应该在第131个字的第3位记录（要注意：0是最开始的位）。因为系统已经将4195号物理块分配给某文件，所以其对应的位要置1。试题答案（16）D（17）B1.2.13试题13某系统进程的状态包括运行状态、活跃就绪状态、静止就绪状态、活跃阻塞状态和静止阻塞状态。针对图1-12所示的进程状态模型，为了确保进程调度的正常工作，（a）、（b）和（c）的状态分别为（18） 。图1-12 进程状态模型（18）A静止就绪、静止阻塞和活跃阻塞 B静止就绪、活跃阻塞和静止阻塞 C活跃阻塞、静止就绪和静止阻塞 D活跃阻塞、静止阻塞和静止就绪试题分析请参看“1.1.3 进程管理”的图1-3。试题答案（18）D1.2.14试题14如果一个索引式文件的索引节点有10个直接块，1个一级间接块，1个二级间接块，1个三级间接块。假设每个数据块的大小是512B，一个索引指针占用4B。假设索引节点已经在内存中，那么访问该文件偏移地址在6000B的数据需要再访问（19）次磁盘。（19）A.1 B.2 C.3 D.4试题分析因为每个数据块的大小是512B，且前10块可以直接寻址，得出15120B范围内可以直接寻址。对于间接索引块，一个索引指针占4B，则一个索引块可以映射512/4=128个数据块，因为每个数据块的大小是512B，合计64KB。6000B-5120B =880B64KB，所以只需一次映射就够了。因此，第1次取索引指针，第2次读数据，一共需要两次访问。试题答案（19）B1.2.15试题15在操作系统的虚拟内存管理中，内存地址由页目录号、页号和页内偏移3个部分组成。如果页目录号占10位、页号占10位、页内偏移占12位，那么（20） 。（20）A页大小是1K，一个页目录最多4K页 B页大小是2K，一个页目录最多2K页 C页大小是2K，一个页目录最多1K页 D页大小是4K，一个页目录最多1K页试题分析已知内存地址由页目录号、页号和页内偏移3个部分组成，页目录号占10位，所以一个页目录最多 =1K页。因为页内偏移占12位，即页的大小为 =4K。试题答案（20）D1.3实战练习题 计算机系统中硬件层之上的软件通常按照3层来划分，如图1-13所示，图中分别表示（1） 。