系统架构设计师
http://www.daodoc.com/
系统架构设计师教程（第3版）
第 1 章 操作系统
本章主要介绍操作系统的基本概念及其形成、发展历史和主要类型，并指出操作系统的5大管理功能。掌握操作系统原理的关键在于深入理解\"一个观点、两条线索\".一个观点是以资源管理的观点来定义操作系统；两条线索是操作系统如何管理计算机各类资源和控制程序的执行。操作系统如何实现对这些资源的管理，其内涵、设计和实现是本章的主要内容。
1.1 操作系统的类型与结构
计算机系统由硬件和软件两部分组成。操作系统是计算机系统中最基本的系统软件，它既管理计算机系统的软、硬件资源，又控制程序的执行。操作系统随着计算机研究和应用的发展进步形成并日趋成熟，它为用户使用计算机提供了一个良好的环境，从而使用户能充分利用计算机资源，提高系统的效率。操作系统的基本类型有：批处理操作系统、分时操作系统和实时操作系统。从资源管理的观点看，操作系统主要是对处理器、存储器、文件、设备和作业进行管理。
1.1.1 操作系统的定义
系统中的硬件和软件资源，合理地组织计算机工作流程和有效地利用资源，在计算机与用户之间起接口的作用。操作系统与硬件/软件的关系如图1-1所示。
系统架构设计师
http://www.daodoc.com/
图1-1 操作系统与硬件/软件的关系
1.1.2 操作系统分类
按照操作系统的功能划分，操作系统的基本类型有批处理操作系统、分时操作系统、实时操作系统、网络操作系统、分布式操作系统、嵌入式操作系统等。
1.批处理操作系统
在批处理操作系统（Batch Proceing Operating System,BPOS）中，系统操作员将作业成批地输入计算机，由操作系统选择作业调入内存加以处理，最后由操作员将运行结果交给用户。批处理操作系统有两个特点：一是\"多道\",指系统内可同时容纳多个作业；二是\"成批\",指系统能成批自动运行多个作业，在运行过程中不允许用户与其作业发生交互作用。所以，合理地调度和管理系统资源是操作系统的主要任务。资源使用的有效性和作业的吞吐量是多道批处理操作系统的主要设计目标，同时也要兼顾作业的周转时间。
2.分时操作系统
在计算机架构发展中，引进了中断和通道技术，于是就有了分时的概念。分时操作系统（Time Share Operating System,TSOS）是指一台计算机连接多个终端，系统把CPU（Central Proce Unit,中央处理单元）时间分为若干时间片，采用时间片轮转的方式处理用户的服务请求。对每个用户能保证足够快的响应时间，并提供交互会话能力。在计算机系统中，分时的概念是指两个或两个以上事件按时间划分轮流地使用系统中的某一资源。实际
系统架构设计师
http://www.daodoc.com/
上，在多道程序系统中，内存中的诸作业程序也是分时使用CPU的。分时操作系统具有多用户同时性、交互性、独立性、及时性等特点。
3.实时操作系统
计算机不但广泛应用于科学计算和数据处理方面，也广泛应用于工业生产过程中的通常称之为实时控制的自动控制，实验室中的实验过程控制，导弹发射控制，票证预订管理等应用领域。实时系统是随着计算机应用于实时控制和实时信息处理领域中而发展起来的。\"实时\"是指及时响应随机发生的外部事件的请求，并以足够快的速度完成对外部事件的处理，控制所有实时设备和实时任务协调一致地运行。实时系统包括实时控制系统和实时处理系统。实时控制指生产过程控制等。实时处理指实验数据采集、订票系统等；实时系统的主要特点是及时性和高可靠性。
4.网络操作系统
网络操作系统（Network Operating System,NOS）是建立在各结点计算机的操作系统之上，用于管理网络通信和共享资源，协调各结点计算机上任务的运行，并向用户提供统
一、有效的网络接口的一组系统软件。网络用户只有通过网络操作系统才能为其提供各种网络服务。网络操作系统的主要任务是用统一的方法管理整个网络中共享资源的使用和协调处理任务。它应具有下述4个基本功能：
（1）网络通信。实现源计算机与目标计算机之间的无差错数据传输。它包括为通信双方建立通信链路；对传输过程中的数据差错进行检查和校正，并使发送、接收速度匹配；在传输任务完成后，拆除通信链路。
（2）资源管理。采用统
一、有效的方法协调多个用户对共享资源的使用，使用户能很方便地使用远程资源。对资源的具体管理和控制，仍由其主机的操作系统实现。
系统架构设计师
http://www.daodoc.com/
（3）提供多种网络服务。主要的网络服务有：远程作业录入服务，使用户能将作业传输到远程结点计算机进行批处理，并将结果回送给用户；电子邮件服务，为用户传输实时和非实时的电子邮件；文件传送、访问和管理服务，使用户能方便地访问远程结点的文件。
（4）提供网络接口。向网络用户提供统
一、有效的网络共享资源和得到网络服务的网络接口。
5.分布式操作系统
从计算机发展趋势来看，计算机的架构开始向并行处理技术和多处理机的计算机系统结构的方向发展。分布式操作系统是为分布式计算机系统配置的操作系统。它在多计算机系统环境下，负责控制和管理以协同方式工作的各类系统资源和分布式进程的同步，并执行和处理机间的通信、调度与分配等控制事务，自动实行全系统范围内的任务分配和负载平衡。它是具有高度并行性、故障检测和重构能力的一种高级软件系统。
分布式操作系统（Distributed Operating System,DOS）与网络操作系统都工作在一个由多台计算机组成的系统中，这些计算机之间可以通过一些传输设备来进行通信和共享系统资源。分布式操作系统更倾向于任务的协同执行，并且各系统之间无主次之分，也无须采用标准的通信协议进行通信。它基本上废弃（或改造）了各单机的操作系统，整个网络设有单一的操作系统，由这个操作系统负责整个系统的资源分配和调度，为用户提供统一的界面。用户在使用分布式操作系统时，不需要像使用网络操作系统那样指明资源在哪台计算机上，因此分布式操作系统的透明性、坚强性、统一性及系统效率都比网络操作系统要强，但实现起来难度也大。
6.嵌入式操作系统
嵌入式系统是指将操作系统和功能软件集成于计算机硬件系统之中，简单地说就是系统
系统架构设计师
http://www.daodoc.com/
的软件与系统的硬件一体化，类似于BIOS（Basic Input Output System,基本输入输出系统）的工作方式，具有软件体积小，高度自动化，响应速度快等特点。
根据IEEE（Institute of Electrical and Electronics Engineers,美国电气和电子工程师协会）的定义，嵌入式系统是用于控制、监视或者辅助操作机器和设备的装置。此定义是从应用上考虑的，嵌入式系统是软件和硬件的综合体，还可以涵盖机电等附属装置。
嵌入式系统是以应用为中心、以计算机技术为基础、软硬件可裁减，对功能、可靠性、成本、体积、功耗严格要求的专用计算机系统。广而言之，可以认为凡是带有微处理器的专用软硬件系统都可以称为嵌入式系统。嵌入式系统采用\"量体裁衣\"的方式把所需的功能嵌入到各种应用系统中，它融合了计算机软硬件技术、通信技术和半导体微电子技术，是信息技术的最终产品。
7.微内核操作系统
微内核操作系统结构是20世纪80年代后期发展起来的，其基本思想是将操作系统中最基本的部分放入内核中，而把操作系统的绝大部分功能都放在微内核外面的一组服务器中实现。这样使得操作系统内核变得非常小，自然提高了系统的可扩展性，增强了系统的可靠性和可移植性，同时微内核操作系统提供了对分布式系统的支持，融入了面向对象技术。虽然微内核操作系统具有诸多优点，但它也并非完美无缺，在运行效率方面它就不如以前传统的操作系统。
当前比较流行的、能支持多处理机运行的操作系统，几乎全部都采用了微内核结构，如卡耐基梅隆大学研制的Mach OS,便属于微内核结构操作系统；又如当前广泛使用的Windows操作系统，也采用了微内核结构。
系统架构设计师
http://www.daodoc.com/
1.2 操作系统基本原理
操作系统的主要功能是进行处理机与进程管理、存储管理、设备管理、文件管理和作业管理，本节讨论操作系统是如何完成这些功能的。
1.2.1 进程管理
处理机是计算机系统的核心资源。操作系统的功能之一就是处理机管理。随着计算机的迅速发展，处理机管理显得更为重要，这主要由于：计算机的速度越来越快，处理机的充分利用有利于系统效率的大大提高；处理机管理是整个操作系统的重心所在，其管理的好坏直接影响到整个系统的运行效率；而且操作系统中并发活动的管理和控制是在处理机管理下实现的，它集中了操作系统中最复杂的部分，它设计的好坏关系到整个系统的成败，
进程（proce）是处理机管理中最基本的、最重要的概念。进程是系统并发执行的体现。由于在多道程序系统中，众多的计算机用户都以各种各样的任务，随时随地争夺使用处理机。为了动态地看待操作系统，则以进程作为独立运行的基本单位，以进程作为分配资源的基本单位，从进程的观点来研究操作系统。因此，处理机管理也被称为进程管理。处理机管理的功能就是组织和协调用户对处理机的争夺使用，把处理机分配给进程，对进程进行管理和控制，以最大限度发挥处理机的作用。
1.进程的概念
用静态的观点看，操作系统是一组程序和表格的集合。用动态的观点看，操作系统是进程的动态和并发执行的。而进程的概念实际上是程序这一概念发展的产物。因此，可以从分析程序的基本特征入手，引出\"进程\"的概念。
顺序程序是指程序中若干操作必须按照某种先后次序来执行，并且每次操作前和操作后的数据、状态之间都有一定的关系。在早期的程序设计中，程序一般都是顺序地执行的。
系统架构设计师
http://www.daodoc.com/
在多道程序系统中，程序的运行环境发生了很大的变化。主要体现在：
（1）资源共享。为了提高资源的利用率，计算机系统中的资源不再由一道程序专用，而是由多道程序共同使用。
（2）程序的并发执行或并行执行。逻辑上讲：允许多道不同用户的程序并行运行；允许一个用户程序内部完成不同操作的程序段之间并行运行；允许操作系统内部不同的程序之间并行运行。物理上讲：内存储器中保存多个程序，I/O设备被多个程序交替地共享使用；多处理机系统的情形下，表现为多个程序在各自的处理机上运行，执行时间是重叠的。单处理机系统时，程序的执行表现为多道程序交替地在处理机上相互空插运行。
实际上，在多道程序系统中，程序的并行执行和资源共享之间是相辅相成的。一方面，只有允许程序并行执行，才可能存在资源共享的问题；另一方面，只有有效地实现资源共享，才可能使得程序并行执行。
这样，可增强计算机系统的处理能力和提高机器的利用率。并发操作实际上是这样的事实：大多数程序段只要求操作在时间上是有序的，也就是有些操作必须在其他操作之前。这是有序的，但其中有些操作却可以同时进行。
2.进程的定义与分类
由于多道程序系统环境下并行程序执行的特征：并发性、动态性、开放性和相互制约，这样，使用程序的概念就不能如实地反映程序活动的这些特征，必须引入新的概念--进程。操作系统内在最本质的特征是动态性和并发性，而进程正反映了动态性和并发性等特征。
程序的并行执行具有如下特征：
（1）并发性。即并发程序的若干个程序段同时在系统中运行，这些程序段的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭
系统架构设计师
http://www.daodoc.com/
是很小的一部分，也称这几个程序段是并发执行的。
（2）动态性。指程序与其执行活动不再一一对应。并发程序中的并发活动是动态产生、动态消亡的。如，几道并发执行的C语言程序共享C编译系统，在这种情况下，-个编译程序能同时为多道程序服务，每个程序调用-次就是执行一次，即这个编译程序对应多个执行活动。
（3）开放性。指系统中并发执行的程序共享使用的资源，程序的执行与外部因素（如执行速度）相关，不再具有封闭性。
（4）相互制约性。指程序的动态活动相互依赖、相互制约。其制约关系可分为间接制约关系和直接制约关系两种：间接制约关系是指相互无逻辑关系的用户程序之间竞争使用资源所发生的制约关系；直接制约关系是指存在逻辑关系的程序之间相互等待而发生的制约关系。通过程序活动的这种相互制约关系，才能保证程序的正确运行。
系统中同时存在许多进程，它们依性质不同可分为各种不同的类别：
（1）系统进程和用户进程。一般来讲，在管态下执行的进程称为系统进程；在目态下执行的进程称为用户进程。系统进程起着资源管理和控制的作用；用户进程是为用户任务而建立的进程。
（2）父进程和子进程。系统或用户首先创建的进程称为父进程；在父进程下面的进程称为子进程。父子进程间存在着某些控制结构和控制关系，因此可以定义一个进程图。进程图是一棵有向的、包含一个根节点的树。节点表示进程，记为Pi,从节点Pi到节点Pj的一条边表示进程Pj是由进程Pi创建的。其中，称Pi是Pj的父进程，而Pj则是Pi的子进程。如图1-2所示。
系统架构设计师
http://www.daodoc.com/
图1-2 进程图
进程图反映了进程间的父、子关系，创建与被创建关系，控制与被控制关系，反映了进程间的层次关系。同一个进程下属的所有进程称为一个进程族，即协调完成同一任务的进程集合同属于一个进程族。父、子进程间的关系主要如下：
（1）进程控制。任何一个进程只能由其直接的父进程创建，进程也只能被其父进程删除。而且当删除某一中间进程（即非叶子节点）时，同时隐含地删除其所属的所有各级子进程。父进程能对其下属的各级子孙进程实施控制，如挂起某个子孙进程。而子进程无权对其父进程实施控制。
（2）运行方式。父进程一旦创建了进程后，可以选择父、子进程同时运行的方式；父进程也可以等待子进程的运行，直至全部子进程结束后，才开始重新运行。
（3）资源共享。可以选择两种不同的资源共享方式：一是子进程可共享父进程所拥有的全部资源；二是子进程仅能共享父进程的部分资源。
3.进程的状态转换
由进程运行的间断性，决定了进程至少具有下述三种状态：
（1）就绪状态。当进程已分配了除CPU以外的所有必要的资源后，只要能再获得处理机，便能立即执行，把进程这时的状态称为就绪状态。在一个系统中，可以有多个进程同
系统架构设计师
http://www.daodoc.com/
时处于就绪状态，通常把它们排成一个队列，称为就绪队列。
（2）执行状态指进程已获得处理机，其程序正在执行。在单处理机系统中，只能有一个进程处于执行状态。
（3）阻塞状态进程因发生某事件（如请求I/O、申请缓冲空间等）而暂停执行时的状态，亦即进程的执行受到阻塞，故称这种暂停状态为阻塞状态，有时也称为\"等待\"状态，或\"睡眠\"状态。通常将处于阻塞状态的进程排成一个队列，称为阻塞队列。
进程的状态随着自身的推进和外界的变化而变化。例如，就绪状态的进程被进程调度程序选中进入执行状态；执行状态的进程因等待某一事件的发生转入等待状态；等待状态的进程所等待事件来到便进入就绪状态。进程的状态可以动态地相互转换，但阻塞状态的进程不能直接进入执行状态，就绪状态的进程不能直接进入阻塞状态。在任何时刻，任何进程都处于且只能处于某一状态。进程状态的变化情况如下：
（1）运行态→等待态：一个进程运行中启动了外围设备，它就变成等待外围设备传输信息的状态；进程在运行中申请资源（主存储空间及外围设备因得不到满足）时，变成等待资源状态，进程在运行中出现了故障（程序出错或主存储器读写错等），变成等待干预状态。
（2）等待态→就绪态：外围设备工作结束后等待外围设备传输信息的进程结束等待；等待的资源能得到满足时（另一个进程归还了资源），则等待资源者就结束等待；故障排队后让等待干预的进程结束等待，任何一个结束等待的进程必须先变成就绪状态，待分配到处理器后才能运行。
（3）运行态→就绪态：进程用完了一个使用处理器的时间后强迫该进桂暂时让出处理器，当有更优先权的进程要运行时也迫使正在运行的进程让出处理器。由于自身或外界原因成为等待状态的进程让出处理器时，它的状态就变成就绪状态。
系统架构设计师
http://www.daodoc.com/
（4）就绪态→运行态：等待分配处理器的进程，系统按一种选定的策略从处于就绪状态的进程中选择一个进程，让它占用处理器，那个被选中的进程就变成了运行态。
图1-3表示了进程的三种基本状态及各状态之间的转换。
图1-3 进程三态模型及其状态转换
3.关于挂起状态
在不少系统中，进程只有图1-3所示的三种状态。但在另一些系统中，又增加了一些新状态，其中最重要的是挂起状态。引入挂起状态的原因有：
（1）对换的需要。为了缓和内存紧张的情况，而将内存中处于阻塞状态的进程换至外存上，使进程又处于一种有别于阻塞状态的新状态。因为即使该进程所期待的事件发生，该进程仍不具备执行条件而不能进入就绪队列，称这种状态为挂起状态。
（2）终端用户的请求。当终端用户在自己的程序运行期间，发现有可疑问题时。往往希望使自己的进程暂停下来。也就是说，使正在执行的进程暂停执行，若是就绪进程，则不接受调度以便研究其执行情况或对程序进行修改。把这种静止状态也称为挂起状态。
（3）父进程请求。父进程常希望挂起自己的子进程，以便考查和修改子进程，或者协调各子进程间的活动。
（4）负荷调节的需要。当实时系统中的工作负荷较重，有可能影响到对实时任务的控制时，可由系统把一些不重要的进程挂起，以保证系统能正常运行。
（5）操作系统的需要。操作系统希望挂起某些进程，以便检查运行中资源的使用情况
系统架构设计师
http://www.daodoc.com/
及进行记账。
由上所述，不难了解挂起状态具有下述三个属性：
（1）被挂起的进程，原来可能处于就绪状态，此时进程（被挂起）的状态称为挂起就绪；若被挂起的进程原来可能处于阻塞状态，此时的状态称为挂起阻塞。不论哪种状态。该进程都是不可能被调度而执行的。
（2）处于挂起阻塞状态的进程，其阻塞条件与挂起条件无关；当进程所期待的事件出现后，进程虽不再被阻塞，但仍不能运行，这时，应将该进程从静止阻塞转换为挂起就绪。
（3）进程可以由其自身挂起，也可由用户或操作系统等将之挂起。其目的都在于阻止进程继续运行，被挂起的进程是只能被用显式方式来激活，以便从挂起状态中解脱出来。
图1-4示出了具有挂起操作的进程状态演变情况。
图1-4 进程状态转换
4.进程互斥与同步
进程互斥定义为：一组并发进程中一个或多个程序段，因共享某一共有资源而导致必须以一个不允许交叉执行的单位执行。也就是说互斥是要保证临界资源在某一时刻只被一个进程访问。
进程同步定义为：把异步环境下的一组并发进程因直接制约而互相发送消息而进行互相
系统架构设计师
http://www.daodoc.com/
合作、互相等待，使得各进程按一定的速度执行的过程称为进程同步。也就是说进程之间是异步执行的，同步即是使各进程按一定的制约顺序和速度执行。
系统中有些资源可以供多个进程同时使用，有些资源则一次仅允许一个进程使用，将一次仅允许一个进程使用的资源称为临界资源（Critical Resourse），很多物理设备如打印机、磁带机等都属于临界资源，某些软件的变量、数据、表格也不允许两个进程同时使用，所以也是临界资源。
进程在并发执行中可以共享系统中的资源。但是临界资源的访问则必须互斥进行，即各进程对临界资源进行操作的那段程序的执行也须是互斥的，只有这样才能保证对临界资源的互斥访问。把一个进程访问临界资源的那段程序代码称为临界区（Critical section）有了临界区的概念，进程间的互斥就可以描述为：禁止两个及以上的进程同时进入访问同一临界资源的临界区。为此，必须有专门的同步机构来协调它们，协调准则如下：
（1）空闲让进。无进程处于临界区时，若有进程要求进入临界区则立即允许其进入；
（2）忙则等待。当已有进程进入其临界区时，其他试图进入各自临界区的进程必须等待，以保证诸进程互斥地进入临界区；
（3）有限等待。有若干进程要求进入临界区时，应在有限时间内使一进程进入临界区，即它们不应相互等待而谁也不进入临界区；
（4）让权等待。对于等待进入临界区的进程必须释放其占有的CPU.
信号量可以有效地实现进程的同步和互斥。在操作系统中，信号量是一个整数。当信号量大于等于零时，代表可供并发进程使用的资源实体数，当信号量小于零时则表示正在等待使用临界区的进程数。建立一个信号量必须说明所建信号量所代表的意义和设置初值，以及建立相应的数据结构，以便指向那些等待使用该临界区的进程。
系统架构设计师
http://www.daodoc.com/
对信号量只能施加特殊的操作：P操作和V操作。P操作和V操作都是不可分割的原子操作，也称为原语，因此，P原语和V原语执行期间不允许中断发生。
P（sem）操作的作用是将信号量sem值减l,若sem的值成负数，则调用P操作的进程暂停执行，直到另一个进程对同一信号量做V操作。V（sem）操作的作用是将信号量sem值加1,若sem的值小于等于0,从相应队列（与sem有关的队列）中选一个进程，唤醒它。
一般P操作与V操作的定义如下所述：
P操作：
P（sem）{
sem = sem-1;
if（sem
else 继续进行；}
V操作：
V（sem）{
sem = sem+1;
if（sem≤0） 唤醒队列中的一个等待进程；
else 继续进行；}
为了保护共享资源（如公共变量等），使它们不被多个进程同时访问，就要阻止这些进程同时执行访问这些资源（临界资源）的代码段（临界区）；进程互斥不允许两个以上共享临界资源的并发进程同时进入临界区。利用P、V原语和信号量可以方便地解决并发进程对临界区的进程互斥问题。
设信号量mutex是用于互斥的信号量，初值为1,表示没有并发进程使用该临界区。于
系统架构设计师
http://www.daodoc.com/
是各并发进程的临界区可改写成下列形式的代码段：
P（mutex）；
临界区
V（mutex）；
要用P,V操作实现进程同步，需要引进私用信号量。私用信号量只与制约进程和被制约进程有关，而不是与整组并发进程相关。与此相对，进程互斥使用的信号量为公用信号量。首先为各并发进程设置私用信号量，然后为私用信号量赋初值，最后利用P,V原语和私用信号量规定各进程的执行顺序。
经典同步问题的例子是生产者-消费者问题。这要求存后再取，取后再存，即有两个制约关系，为此，需要两个信号量，表示缓冲区中的空单元数和非空单元数，记为Bufempty和Buffull,它们的初值分别是1和0,相应的程序段形式是：
生产者
loop
生产一产品next;
P（Bufempty）；
next产品存缓冲区；
V（Buffull）；
endloop
消费者
loop
P（Buffulll）；
系统架构设计师
http://www.daodoc.com/
V（Bufempty）；
从缓冲区中取产品；
使用产品
endloop
5.前趋图
前趋图是一个由结点和有向边构成的有向无循环图。该图通常用于表现事务之间先后顺序的制约关系。图中的每个结点可以表示一个语句、一个程序段或是一个进程，结点间的有向边表示两个结点之间存在的前趋关系。
例：在计算机中，经常采用流水线方式执行指令，若每一条指令都可以分解为取指、分析和执行三步。取指操作为：取指操作为Ai,分析操作为Bi和执行操作为Ci （i=1,2,3）。图1-5为三个任务各程序段并发执行的前驱图。
图中A1没有前趋结点，称为开始结点，它不受任何制约，可以直接执行；而B1与A2只能在A1执行完成之后才能开始，而B2必须在B1与A2完成之后才能开始；C3没有后继结点，称为终止结点。
图1-5 前趋图
在前趋图中，执行优后顺序的制约关系可分为两种：直接制约和间接制约。
直接制约通常是指一个操作中，多个步骤之间的制约关系，也可以说是\"同步的进程之
系统架构设计师
http://www.daodoc.com/
间的制约关系\".例如图1-5中，A
1、B
1、C1是一条指令的取指、分析、执行三个步骤，所以他们之间的关系是直接制约。
间接制约通常是指多个操作之间相同步骤的制约关系，也可以说是\"互斥的进程之间的制约关系\".例如图1-5中，A
1、A
2、A3之间就存在间接制约的关系。
前趋图的应用广泛，在项目开发中，可用前趋图来分析哪些活动可以并行完成。同时项目管理工具：Pert图，单（双）代号网络图等都融入了前趋图的思想。
6.进程调度与死锁
进程调度即处理器调度（又称上下文转换），它的主要功能是确定在什么时候分配处理器，并确定分给哪一个进程，即让正在执行的进程改变状态并转入就绪队列的队尾，再由调度原语将就绪队列的队首进程取出，投入执行。
引起进程调度的原因有以下几类：
（1）正在执行的进程执行完毕。
（2）执行中的进程自己调用阻塞原语将自己阻塞起来进入睡眠状态。
（3）执行中的进程调用了P原语操作，从而因资源不足而阻塞；或调用V原语操作激活了等待资源的进程队列。
（4）在分时系统中，当一进程用完一个时间片。
（5）就绪队列中某进程的优先级变得高于当前执行进程的优先级，也将引起进程调度。
进程调度的方式有两类：剥夺方式与非剥夺方式。所谓非剥夺方式是指，一旦某个作业或进程占有了处理器，别的进程就不能把处理器从这个进程手中夺走，直到该进程自己因调用原语操作而进入阻塞状态，或时间片用完而让出处理机；剥夺方式是指，当就绪队列中一旦有进程的优先级高于当前执行进程的优先级时，便立即发生进程调度，转让处理机。
系统架构设计师
http://www.daodoc.com/
进程调度的算法是服务于系统目标的策略，对于不同的系统与系统目标，常采用不同的调度算法：
（1）先来先服务（First Come and First Serverd,FCFS）调度算法，又称先进先出（First In and First Out,FIFO）。就绪队列按先来后到原则排队。
（2）优先数调度。优先数反映了进程优先级，就绪队列按优先数排队。有两种确定优先级的方法，即静态优先级和动态优先级。静态优先级是指进程的优先级在进程开始执行前确定，执行过程中不变，而动态优先级则可以在进程执行过程中改变。
（3）轮转法（Round Robin）。就绪队列按FCFS方式排队。每个进程执行一次占有处理器时间都不超过规定的时间单位（时间片）。若超过，则自行释放自己所占有的CPU而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程。
进程管理是操作系统的核心，在进程管理的实现中，如果设计不当，会出现一种尴尬的局面--死锁。
当若干个进程互相竞争对方已占有的资源，无限期地等待，不能向前推进时会造成\"死锁\".例如，P1进程占有资源R1,P2进程占有资源R2,这时，P1又需要资源R2,P2也需要资源R1,它们在等待对方占有的资源时，又不会释放自己占有的资源，因而使双方都进入了无限等待状态。
死锁是系统的一种出错状态，它不仅浪费大量的系统资源，甚至会导致整个系统的崩溃，所以死锁是应该尽量预防和避免的。
（1）死锁条件。产生死锁的主要原因是供共享的系统资源不足，资源分配策略和进程的推进顺序不当。系统资源既可能是可重复使用的永久性资源，也可能是消耗性的临时资源。
系统架构设计师
http://www.daodoc.com/
产生死锁的必要条件是：互斥条件、保持和等待条件、不剥夺条件和环路等待条件。
（2）解决死锁的策略。处于死锁状态的进程不能继续执行又占有了系统资源，从而会阻碍其他作业的执行。
解决死锁有两种策略：一种是在死锁发生前采用的预防和避免策略；另一种是在死锁发生后采用的检测与恢复策略。
死锁的预防主要是通过打破死锁产生的4个必要条件之一来保证不会产生死锁。采用的死锁预防策略通常有资源的静态分配法或有序分配法，它们分别打破了资源动态分配条件和循环等待条件，因此不会发生死锁。但这样做会大大降低系统资源的利用率和进程之间的并行程度。
死锁避免策略，则是在系统进行资源分配时，先执行一个死锁避免算法（典型的如银行家算法），来保证本次分配不会导致死锁的发生。由于资源分配很频繁，因此死锁避免策略要耗费大量的CPU时间。
希赛教育专家提示：实际上，系统出现死锁的概率很小，故从系统所花的代价上看，采用死锁发生后的检测与恢复策略要比采用死锁发生前的预防与避免策略代价小一些。
7.线程
在支持线程的操作系统中，线程是进程中的-个实体，是系统实施调度的独立单位。线程只拥有-些在运行中必不可少的资源，它与属于同一个进程的其他线程共享该进程所拥有的资源。各线程之间可以并发地运行。线程切换时只需保存和设置少量寄存器的内容，而并不涉及存储器管理方面的操作，所以线程切换的开销远远小于进程的切换（原运行进程状态的切换还要引起资源转移及现场保护等问题）。同一个进程中的多个线程共享同一个地址空间，这使得线程之间同步和通信的实现也比较容易。
系统架构设计师
http://www.daodoc.com/
1.2.2 存储管理
存储器是计算机系统中最重要的资源之一。因为任何程序和数据以及各种控制用的数据结构都必须占有一定的存储空间，因此，存储管理直接影响系统性能。
存储器由内存和外存组成。内存是由系统实际提供的存储单元（常指字节）组成的一个连续地址空间，处理器可直接存取。外存（辅存）是指软盘、硬盘、光盘和磁带等一些外部存储部件，常用来存放暂不执行的程序和数据。处理器不能直接访问外存，需通过启动I/O（Input/Output,输入/输出）设备才能进行内存、外存交换，其访问速度慢，但价格便宜，常用做内存的后援设备。
内存大小由系统硬件决定，存储容量受到实际存储单元的限制。虚拟存储器（简称虚存）不考虑实际内存的大小和数据存取的实际地址，只考虑相互有关的数据之间的相对位置，其容量由计算机地址的位数决定。
系统中内存的使用一般分成两部分，一部分为系统空间，存放操作系统本身及相关的系统程序；另一部分为用户空间，存放用户的程序和数据。
存储管理主要是指对内存储器的管理，负责对内存的分配和回收、内存的保护和内存的扩充。存储管理的目的是尽量提高内存的使用效率。
1.地址重定位
在存储管理中，有一个地址重定位的问题。一般来说，用户的目标程序地址是相对地址，指令中的地址是相对首地址而定的，在程序执行之前首地址通常设为零。这个相对地址称为逻辑地址，它不是内存中的物理地址。物理地址是内存中各存储单元的编号，是存储单元的真实地址，可以寻址并且实际存在。为了保证程序指令执行时能够正确地访问到预定的单元，需要将逻辑地址通过一种地址转换机制变换成物理地址，这一过程就称为\"地址重定位\",也
系统架构设计师
http://www.daodoc.com/
称为地址映射或地址映像。
重定位方法有两种：静态重定位和动态重定位。
静态重定位的地址转换是在程序运行之前完成的，一般由连接装入程序在程序装入主存的过程中实现逻辑地址到物理地址的转换。程序被装入主存后，不能再在主存中移动，因而采用这种重定位方式，不能实现虚拟存储器。
动态重定位是在程序装入主存后，在指令执行阶段完成对该指令中的逻辑地址到物理地址的转换。它的实现由硬件地址变换机构完成，因此系统对硬件要求的支持多，但装入主存中的程序可以根据系统当前的需求在主存中上、下移动或在内、外存中调进、调出，是实现虚拟存储器必须采用的一种重定位方法。目前的计算机系统大部分采用这种重定位方式。
2.存储管理的功能
在多道程序系统中，多个程序同时驻留内存。那么，该如何有效地利用内存，如何让需要较大运行空间的作业运行，如何保护与共享内存呢？为了提高存储资源的利用率，存储管理应具有以下功能：
（1）分配与回收。内存分配方法有两种：静态分配和动态分配。静态分配是指在目标模块装入内存时即取得所需空间，直至完成不再变动：动态分配则允许进程在运行过程中动态申请内存空间。采用动态分配方法的系统中，常配合使用合并自由区的方法，使一个连续的空区尽可能大。
（2）存储扩充。提供虚拟存储器，使计算机系统似乎有一个比实际内存储器容量大的内存空间。需考虑放置策略、调入策略和淘汰策略。
（3）共享与保护。共享指共享系统在内存中的程序和数据。由于多道程序共享内存，每个程序都应有它单独的内存区域，各自运行，互不干扰。
系统架构设计师
http://www.daodoc.com/
3.单一连续区管理
在单道程序系统中，内存区域的用户空间全部为一个作业或进程占用。单一连续分配方法主要用于早期单道批处理系统及20世纪80年代的个人计算机系统。单一连续分配方法主要采用静态分配方法。为降低成本和减小复杂度，常不对内存进行保护，因而会引起冲突，使系统瘫痪。
4.分区存储管理
分区存储管理包括固定分区和可变分区。其基本思想是把内存划分成若干个连续区域，每个分区装入一个作业运行。要求作业一次性装入内存，且分区内部地址必须连续。
（1）固定分区管理。固定分区分配方法是把内存空间固定地划分为若干个大小不等的区域，划分的原则由系统决定。系统使用分区表描述分区情况，如图1-6所示。分区一旦划分结束，在整个执行过程中每个分区的长度和内存的总分区个数保持不变。
图1-6 固定分区表
（2）可变分区管理。可变分区分配方法是把内存空间按用户要求动态地划分成若干个分区，如图1-7所示。这样就解决了固定分区分配方法中的小作业占据大分区后产生碎片的浪费问题。可变分区分配方法初始时只有一个分区，随后，分配程序将这个分区依次分给作业或进程。
系统架构设计师
http://www.daodoc.com/
图1-7 可变分区表
希赛教育专家提示：每种存储组织方案都包含一定程度的浪费。在可变分区分配系统中，内存中的作业在开始装入和归还自由区之前，内存浪费并不明显，但这些自由区可以被其他作业使用。随着进程的执行，剩余的自由区域会变得更小。因此在可变分区分配系统中，也存在着存储器浪费。
在可变分区分配系统中，当一个作业完成时，能够检测到被释放的存储区是否与其他自由存储区域（自由区）相邻接。如果与其他自由存储区邻接，可以在自由存储区表记录上新增加一个自由区，或新的自由区与相邻接的现存自由区合并的单一自由区。
合并相邻接的自由区以形成单个更大的自由区叫做合并。用合并自由区的方法，重新获得最大可能连续的存储块。即使合并了自由区，仍会发现分布在主存各处的破碎的自由区在主存中占据了相当数量的空间。有时，虽然自由区的总和大于新作业所要的存储区，而此时却没有单个的自由区足够装下这个作业。
存储拼接技术也称碎片收集，包括移动存储器的所有被占用区域到主存的某一端。这样留下单独的大的存储自由区，来代替在可变分区多道程序设计中常见的许多小自由区。
当所有可利用的自由存储区连续时，一个正等待着的作业能够调入运行，因为它的存储需求能被拼接形成的单个自由区所满足。
存储分配算法用来决定输入的程序和数据应该放到主存中的什么地方。常使用的3种
系统架构设计师
http://www.daodoc.com/
算法是：
（1）最佳适应算法。选择最小的足够装入的可利用自由区。对许多人来说，最佳适应看起来是最直观且吸引人的算法。
（2）首次适应算法。从主存低地址开始选择第一个足够装入的可利用的自由区。首次适应也具有直观吸引力，此算法可以快速做出分配决定。
（3）最差适应算法。最差适应说的是，把一个程序放入主存中最大的自由区。这种方法吸引人的原因很简单，在大自由区中放入程序后，剩下的自由区经常也很大，于是也能装下一个较大的新程序。
上述3种方法都把用户作业完全地连续存放在一个存储区域中。为了能在较小的内存空间中运行较大的作业，常采用内存交换技术。所谓内存交换技术，是指将作业不需要或暂时不需要的部分移到辅存，让出内存空间以调入需要的部分，交换到辅存的部分也可以再次被调入。实际上这是用辅存作缓冲，让用户程序在较小的存储空间中，通过不断地换出作业而运行较大的作业。
5.页式存储管理
在可变分区分配方案中，内存中放置的程序常采用首次适应、最佳适应、最差适应算法实现，但运行的程序需存放在一个连续的分区中。
分页的基本思想是把程序的逻辑空间和内存的物理空间按照同样的大小划分成若干页面，以页面为单位进行分配。在页式存储管理中，系统中虚地址是一个有序对（页号，位移）。系统为每一个进程建立一个页表，其内容包括进程的逻辑页号与物理页号的对应关系、状态等。
页式系统的动态地址转换是这样进行的：当进程运行时，其页表的首地址已在系统的动
系统架构设计师
http://www.daodoc.com/
态地址转换机构中的基本地址寄存器中。执行的指令访问虚存地址（p,d）时，首先根据页号p查页表，由状态可知，这个页是否已经调入内存。若已调入内存，则得到该页的内存位置p\',然后，与页内相对位移d组合，得到物理地址r.如果该页尚未调入内存，则产生缺页中断，以装入所需的页。如图1-8所示。
图1-8 页式存储管理地址转换示意图
页式虚拟存储管理是在页式存储管理的基础上实现虚拟存储器的。首先把作业信息作为副本存放在磁盘上，作业执行时，把作业信息的部分页面装入内存储器，作业执行时若所访问的页面已在内存中，则按页式存储管理方式进行地址转换，得到欲访问的内存绝对地址，若欲访问的页面不在内存中，则产生一个\"缺页中断\",由操作系统把当前所需的页面装入内存储器中。
为此，在装入作业时，就应在该作业的页表中指出哪些页已在内存储器中，哪些页还没有装入内存。可用一个标志位指示对应页是否在内存储器，可假设标志位为1表示该页在内存，而标志位为0表示该页尚未装入内存。为了能方便地从磁盘上找到作业信息的副本，故在页表中还可指出每一页副本在磁盘上的位置。
当要装入一个当前需要的页面时，如果内存储器中无空闲块，则可选择一个已在内存储
系统架构设计师
http://www.daodoc.com/
器中的页面，把它暂时调出内存。若在执行中该页面被修改过，则把该页信息重新写回到磁盘上，否则不必重新写回磁盘。当一页被暂时调出内存后，让出的内存空间用来存放当前需要使用的页面。以后再要使用被调出的页面时，可用同样的方法调出另一个页面而将其再装入内存。页面被调出或装入之后都要对页表中的相应表目做修改。
当内存中无空闲块时，为了装入一个页面而必须按某种算法从已在内存的页中选择一页，将它暂时调出内存，让出内存空间来存放所需装入的页面，这个工作称为\"页面调度\".如何选择调出的页面是很重要的，如果采用了一个不合适的算法，就会出现这样的现象，刚被调出的页面又立即要用，因而又要把它装入，而装入不久又被选中调出，调出不久又被装入，如此反复，使调度非常频繁。这种现象称为\"抖动\".一个好的调度算法应减少和避免抖动现象。常用的页面调度算法有：
（1）最优（OPT）算法。选择不再使用或最远的将来才被使用的页，这是理想的算法，但是难以实现，常用于淘汰算法的比较。
（2）随机（RAND）算法。随机地选择被淘汰的页，开销小，但是可能选中立即就要访问的页。
（3）先进先出算法。选择在内存驻留时间最长的页，似乎合理，但可能淘汰掉频繁使用的页。另外，使用FIFO算法时，在未给予进程分配足够的页面数时，有时会出现给予进程的页面数增多，缺页次数反而增加的异常现象。FIFO算法简单，易实现。可以把装入内存储器的那些页的页号按进入的先后次序排成队列，每次总是调出队首的页，当装入一个新页后，把新页的页号排到队尾。
（4）最近最少使用（Least Recently Used,LRU）算法。选择离当前时间最近的一段时间内使用得最少的页。这个算法的主要出发点是，如果某个页被访问了，则它可能马上就
系统架构设计师
http://www.daodoc.com/
要被访问；反之，如果某个页长时间未被访问，则它在最近一段时间也不会被访问。
6.段式存储管理
段式存储管理与页式存储管理相似。分段的基本思想是把用户作业按逻辑意义上有完整意义的段来划分，以段为单位作为内、外存交换的空间尺度。
一个作业是由若干个具有逻辑意义的段（如主程序、子程序、数据段等）组成。分段系统中，容许程序（作业）占据内存中许多分离的分区。每个分区存储一个程序分段。这样，每个作业需要几对界限地址寄存器，判定访问地址是否越界也困难了。在分段存储系统中常常利用存储保护键实现存储保护。分段系统中虚地址是一个有序对（段号，位移）。系统为每个作业建立一个段表，其内容包括段号、段长、内存起始地址和状态等。状态指出这个段是否已调入内存，即内存起始地址指出这个段，状态指出这个段的访问权限。
分段系统的动态地址转换是这样进行的：进程执行时，其段表的首地址已在基本地址寄存器中，执行的指令访问虚存（s,d）（取指令或取操作数）时，首先根据段号s查段表，若段已经调入内存，则得到该段的内存起始地址，然后与段内相对地址（段内偏移量d）相加，得到实地址。如果该段尚未调入内存，则产生缺段中断，以装入所需要的段。段式存储与页式存储的地址转换方式类似，参看图1-8.
段式虚似存储管理仍然以段式存储管理为基础，为用户提供比内存实际容量大的虚拟空间。段式虚拟存储管理把作业中的各个分段信息都保留在磁盘上，当作业可以投入执行时，做如下操作：
（1）首先把当前需要的一段或几段装入内存。
（2）作业执行时，如果要访问的段已经在内存，则按照\"段式存储管理\"中的方式进行地址转换；如果要访问的段不在内存中，则产生一个\"缺段中断\",由操作系统把当前需用的
系统架构设计师
http://www.daodoc.com/
段装入内存。
因此，在段表中应增设段是否在内存的标志以及各段在磁盘上的位置，已在内存中的段仍要指出该段在内存中的起始地址和占用内存区长度。
作业执行要访问的段时，由硬件的地址转换机构查段表，若该段在内存中，则立即把逻辑地址转换成绝对地址。若该段不在内存中，则形成\"缺段中断\",由操作系统处理这个中断。
处理的办法是，查内存分配表，找出一个足够大的连续区以容纳该分段，如果找不到足够大的连续区则检查空闲区的总和，若空闲区总和能满足该段要求，那么进行适当移动将分散的空闲区集中：若空闲区总和不能满足该段要求，可把内存中的一段或几段调出，然后把当前要访问的段装入内存中。段被移动、调出和装入后都要对段表中的相应表目做修改。新的段被装入后应让作业重新执行被中断的指令，这时就能找到要访问的段，可以继续执行下去。
7.段页式存储管理
段页式管理是段式和页式两种管理方法结合的产物，综合了段式组织与页式组织的特点，根据程序模块分段，段内再分页，内存被分划成定长的页。段页式系统中虚地址形式是（段号、页号、位移），如图1-9所示。系统为每个进程建立一个段表，为每个段建立一个页表。段页式管理采用段式分配、页式使用的方法，便于动态连接和存储的动态分配。这种存储管理能提高内存空间的利用率。
图1-9 段页式存储管理地址
段式虚拟管理还是以段为单位分配内存空间，整段的调出、装入，有时还要移动，这些
系统架构设计师
http://www.daodoc.com/
都增加了系统的开销。如果按段页式存储管理的方式，把每一段再分成若干页面，那么，每一段不必占用连续的存储空间，甚至，当内存块不够时，可只将一段中的部分页面装入内存，这种管理方式称为\"段页式虚拟存储管理\".
段页式虚拟存储管理为每一个装入内存的作业建立一张段表，还要为每一段建立页表。段表中指出该段的页表存放位置及长度，页表中应指出该段的各页在磁盘上的位置以及页是否在内存，若在内存则填上占用的内存块号。作业执行时按段号查段表，找到相应的页表再根据页号查页表，由标志位判定该页是否已在内存，若是，则进行地址转换；否则进行页面调度。地址转换过程如图1-10所示。
图1-10 段页式存储管理中的动态地址转换示意图
段页式虚拟存储管理结合了段式和页式的优点，但增加了设置表格（段表、页表）和查表等开销，段页式虚拟存储器一般只在大型计算机系统中使用。
8.存储保护
存储保护的基本思想是规定各道程序只能访问属于它的区域，以及存取公共区域中的信息，当然，对公共区域的访问是有限制的。
系统架构设计师
http://www.daodoc.com/
存储保护通常是由计算机软件和硬件的相互配合来实现的。存储保护包括两方面的内容，分别是上下界保护和控制权保护。
（1）上下界保护。上下界保护通常由硬件提供保护机制，软件配合实现。当要访问内存某一单元时，硬件首先进行访址合法性检查，检查经过重定位后的内存地址是否在上下界寄存器所规定的范围之内。若在规定的范围之内，则允许访问，否则产生中断。
在分页和分段环境下，利用给出作业的最大页号（页表长度）和段号（段表长度）来实现。程序运行时，页表长度或段表长度被放入页表或段表地址寄存器的左边部分，当中央处理器访问某虚拟地址时，硬件自动把页号（段号）与页表（段表）长度进行比较；在分段环境下还要将段内地址与段表中的段长度进行比较，如果合法，才进行地址转换，否则产生越界中断信号。
（2）控制权保护。控制权保护是对授权可使用的信息可读可写权限进行控制。常用的存取控制包括读、写、执行和增加（只允许添加不允许修正）4类。各类用户的访问权限是这4类存取控制类型的组合。此外，对共享段的访问还要注意读和写操作之间的互斥。
1.2.3 设备管理
在计算机系统中，除了处理器和内存之外，其他的大部分硬设备称为外部设备。它包括输入/输出设备，辅存设备及终端设备等。这些设备种类繁多，特性各异，操作方式的差异很大，从而使操作系统的设备管理变得十分繁杂。
1.设备管理的任务
设备管理是对计算机输入/输出系统的管理，这是操作系统中最具有多样性和复杂性的部分。其主要任务是：
（1）选择和分配输入/输出设备以便进行数据传输操作。
系统架构设计师
http://www.daodoc.com/
（2）控制输入/输出设备和CPU（或内存）之间交换数据。
（3）为用户提供一个友好的透明接口，把用户和设备硬件特性分开，使得用户在编制应用程序时不必涉及具体设备，系统按用户要求控制设备工作。另外，这个接口还为新增加的用户设备提供一个和系统核心相连接的入口，以便用户开发新的设备管理程序。从而提高设备和设备之间、CPU和设备之间，以及进程和进程之间的并行操作度，以使操作系统获得最佳效率。
为了完成上述主要任务，设备管理程序一般要提供下述功能：
（1）提供和进程管理系统的接口。当进程要求设备资源时，该接口将进程要求转达给设备管理程序。
（2）进行设备分配。按照设备类型和相应的分配算法把设备和其他有关的硬件分配给请求该设备的进程，并把未分配到所请求设备或其他有关硬件的进程放入等待队列。
（3）实现设备和设备、设备和CPU等之间的并行操作。
（4）进行缓冲区管理。一般来说，CPU的执行速度和访问内存速度都比较高，而外部设备的数据流通速度则低得多（例如键盘）。为了减少外部设备和内存与CPU之间的数据速度不匹配的问题，系统中一般设有缓冲区（器）来暂放数据。设备管理程序负责进行缓冲区分配、释放及有关的管理工作。
2.主要设备管理技术
设备管理的主要任务首先是分配和回收设备，控制设备的工作，完成用户的输入/输出请求；其次是提高CPU与设备以及设备与设备之间的并行工作速度，提高设备的使用效率。主要设备管理技术有：
（1）中断技术。当外设向CPU发出中断请求的时候，CPU暂停正在执行的程序，转
系统架构设计师
http://www.daodoc.com/
去执行中断处理程序。处理完成后，再返回到断点处继续执行被中断的程序。中断处理能够对输入/输出是否正常结束或者发现错误等进行相应的处理。使用中断技术后，CPU不必时时去查询外设，减少了CPU询问外设的时间，从而提高了CPU和外设并行工作的能力。
（2）通道技术。指专门建立一套用于控制外设和内存之间进行信息传输的硬件机构，又称I/O处理机。建立通道后，CPU不直接去控制各个I/O设备。而是通过通道去控制，每个通道把一个或多个外部设备与CPU联系起来，使它们能并行工作。通道专门用于数据传输工作。
中断和通道技术为CPU与外设之间的并行操作提供了可能性，但CPU与外设之间速度的不匹配仍会降低CPU的使用效率。因此又发展了缓冲技术。
（3）缓冲技术。缓冲区是在内存中开辟的专门用于数据传输过程中暂存数据的区域，是一种解决高速CPU和低速外设之间速度不匹配的存储装置。引入缓冲不但缓解了速度方面的矛盾，且减少了CPU对I/O设备的访问次数。提高了CPU和外设并行工作的程度。
3.数据传输控制方式
设备管理的主要任务之一是控制设备和内存或CPU之间的数据传送，本节介绍几种设备管理的主要任务之一是控制设备和内存或CPU之间的数据传送常用的数据传送控制方式。
选择和衡量控制方式的原则如下：
（1）数据传送速度足够高，能满足用户的需要但又不丢失数据。
（2）系统开销小，所需的处理控制程序少。
（3）能充分发挥硬件资源的能力，使得I/O设备尽量忙，而CPU等待时间少。
外围设备和内存之间常用的数据传送控制方式主要有以下几种方式：
系统架构设计师
http://www.daodoc.com/
（1）程序控制方式。处理器启动数据传输，然后等设备完成。
（2）中断方式。程序控制方式不能实现并发。中断方式的数据传输过程是这样的，进程启动数据传输（如读）后，该进程放弃处理器，当数据传输完成，设备控制器产生中断请求，中断处理程序对数据传输工作处理以后，让相应进程成为就绪状态。以后，该进程就可以得到所需要的数据。
（3）直接存储访问（Direct Memory Acce,DMA）方式。指外部设备和内存之间开辟直接的数据交换通路。除了控制状态寄存器和数据缓冲寄存器外，DMA控制器中还包括传输字节计数器、内存地址寄存器等。DMA方式采用窃取（或挪用）处理器的工作周期和控制总线而实现辅助存储器和内存之间的数据交换。有的DMA方式也采用总线浮起方式传输大批量数据。
（4）通道方式。通道又称为输入/输出处理器（Input/Output Proceor,IOP），可以独立完成系统交付的输入/输出任务，通过执行自身的输入/输出专用程序（称通道程序）进行内存和外设之间的数据传输。主要有3类通道：字节多路通道、选择通道和成组多路通道。
4.磁盘调度算法
设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。
在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。
访问磁盘的时间因子由三部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇
系统架构设计师
http://www.daodoc.com/
区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。
（1）先来先服务调度。按先来后到次序服务，未做优化。
（2）最短查找时间优先（Shortest Seek Time First,SSTF）调度。FCFS会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿）。
（3）SCAN调度。又称电梯算法，SCAN算法是磁头前进方向L的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。
5.虚设备与SPOOLING技术
采用假脱机技术，可以将低速的独占设备改造成一种可共享的设备，而且一台物理设备可以对应若干台虚拟的同类设备。假脱机（Simultaneous Peripheral Operation On Line,SPOOLING）的意思是外部设备同时联机操作，又称为假脱机输入/输出操作，采用一组程序或进程模拟一台输入/输出处理器。
SPOOLING系统的组成如图1-11所示。该技术利用了专门的外围控制机将低速I/O设备上的数据传送到高速设备上，或者相反。但是当引入多道程序后，完全可以利用其中的一道程序来模拟脱机输入时的外围控制机的功能，把低速的I/O设备上的数据传送到高速磁盘上；再利用另一道程序来模拟脱机输出时的外围控制机的功能，把高速磁盘上的数据传送到低速的I/O设备上。这样便可以在主机的控制下实现脱机输入、输出的功能。此时的外围操作与CPU对数据的处理同时进行。
系统架构设计师
http://www.daodoc.com/
图1-11 SPOOLING系统示意图
采用假脱机技术，可以将低速的独占设备改造成一种可共享的设备，而且一台物理设备可以对应若干台虚拟的同类设备。SPOOLING系统必须有高速、大容量并且可随机存取的外存（例如，磁盘或磁鼓）支持。
希赛教育专家提示：在现代计算机系统中，还可以用一台设备来模拟自身。例如，常见的多窗口技术，即在一个终端上开多个窗口，每个窗口可以独立地进行显示，以监视用户不同任务的执行情况。这是通过缩小显示区域、平铺或重叠显示来模拟多个显示器的。
1.2.4 文件管理
操作系统对计算机的管理包括两个方面：硬件资源和软件资源。硬件资源的管理包括CPU的管理、存储器的管理、设备管理等，主要解决硬件资源的有效和合理利用问题。
软件资源包括各种系统程序、各种应用程序、各种用户程序，也包括大量的文档材料、库函数等。每一种软件资源本身都是具有一定逻辑意义的、相关信息的集合，在操作系统中它们以文件形式存储。
计算机系统的重要作用之一是能快速处理大量信息，因此数据的组织、存取和保护成为一个极重要的内容。文件系统是操作系统中组织、存取和保护数据的一个重要部分。
文件管理的功能包括：建立、修改、删除文件；按文件名访问文件；决定文件信息的存
系统架构设计师
http://www.daodoc.com/
放位置、存放形式及存取权限；管理文件间的联系以及提供对文件的共享、保护和保密等。允许多个用户协同工作又不引起混乱。文件的共享是指一个文件可以让多个用户共同使用，它可以减少用户的重复性劳动，节省文件的存储空间，减少输入/输出文件的次数等。文件的保护主要是为防止由于误操作而对文件造成的破坏。文件的保密是为了防止未经授权的用户对文件进行访问。
文件的保护、保密实际上是用户对文件的存取权限控制问题。一般为文件的存取设置两级控制：第1级是访问者的识别，即规定哪些人可以访问；第2级是存取权限的识别，即有权参与访问者可对文件执行何种操作。
1.文件的逻辑结构
文件的结构是指文件的组织形式，从用户观点所看到的文件组织形式，称为文件的逻辑结构。
文件的逻辑组织是为了方便用户使用。一般文件的逻辑结构可以分为两种：无结构的字符流文件和有结构的记录文件。记录文件由记录组成，即文件内的信息划分成多个记录，以记录为单位组织和使用信息。
记录文件有顺序文件、索引顺序文件、索引文件和直接文件。
（1）顺序文件。大多数文件是顺序文件。顺序文件的记录定长，记录中的数据项的类型长度与次序固定，一般还有一个可以惟一标识记录的数据项，称为键（key），记录是按键值的约定次序组织的。顺序文件常用于批处理应用，对于查询或更新某个记录的处理性能不太好。
（2）索引顺序文件。索引顺序文件是基于键的约定次序组织的，而且维护键的索引和溢出区域。键的索引也可以是多级索引。索引顺序文件既适用于交互方式应用，也适用于批
系统架构设计师
http://www.daodoc.com/
处理方式应用。
（3）索引文件。索引文件是基于记录的一个键数据项组织的。许多应用需按照别的数据项访问文件，为此，常采用索引文件方法，即对主文件中的记录按需要的数据项（一个或几个）建索引，索引文件本身是顺序文件组织。
（4）直接文件。直接文件又称哈希（Hash）文件。记录以它们在直接访问存储设备上的物理地址直接（随机地）访问。直接文件常用于需要高速访问文件而且每次访问一条记录的应用中。
2.文件的物理结构
文件的物理结构是指文件在存储设备上的存放方法。文件的物理结构侧重于提高存储器的利用效率和降低存取时间。文件的存储设备通常划分为大小相同的物理块，物理块是分配和传输信息的基本单位。文件的物理结构涉及文件存储设备的组块策略和文件分配策略，决定文件信息在存储设备上的存储位置。常用的文件分配策略有：
（1）顺序分配（连续分配）。这是最简单的分配方法。在文件建立时预先分配一组连续的物理块，然后，按照逻辑文件中的信息（或记录）顺序，依次把信息（或记录）按顺序存储到物理块中。这样，只需知道文件在文件存储设备上的起始位置和文件长度，就能进行存取，这种分配方法适合于顺序存取，在连续存取相邻信息时，存取速度快。其缺点是在文件建立时必须指定文件的信息长度，以后不能动态增长，一般不宜用于需要经常修改的文件。
（2）链接分配（串联分配）。这是按单个物理块逐个进行的。每个物理块中（一般是最后一个单元）设有一个指针，指向其后续连接的下一个物理块的地址，这样，所有的物理块都被链接起来，形成一个链接队列。在建立链接文件时，不需指定文件的长度，在文件的说明信息中，只需指出该文件的第一个物理块块号，而且链接文件的文件长度可以动态地增
系统架构设计师
http://www.daodoc.com/
长。只调整物理块间的指针就可以插入或删除一个信息块。
链接分配的优点是可以解决存储器的碎片问题，提高存储空间利用率。由于链接文件只能按照队列中的链接指针顺序序查找，因此，搜索效率低，一般只适用于顺序访问，不适用于随机存取。
（3）索引分配。这是另一种对文件存储不连续分配的方法。采用索引分配方法的系统，为每一个文件建立一张索引表，索引表中每一表项指出文件信息所在的逻辑块号和与之对应的物理块号。
索引分配既可以满足文件动态增长的要求，又可以方便而迅速地实现随机存取。对一些大的文件，当索引表的大小超过一个物理块时，会发生索引表的分配问题。一般采用多级（间接索引）技术，这时在由索引表指出的物理块中存放的不是文件存放处而是存放文件信息的物理块地址。这样，如果一个物理块能存储n个地址，则一级间接索引将使可寻址的文件长度变成n2块，对于更大的文件可以采用二级甚至三级间接索引（例如，Unix操作系统采用三级索引结构，如图1-12所示）。
图1-12 索引结构图
系统架构设计师
http://www.daodoc.com/
索引文件的优点是既适用于顺序存取，又适用于随机存取。缺点是索引表增加了存储空间的开销。另外，在存取文件时需要访问两次磁盘，一次是访问索引表，另一次是根据索引表提供的物理块号访问文件信息。为了提高效率，一种改进的方法是，在对某个文件进行操作之前，预先把索引表调入内存。这样，文件的存取就能直接从在内存的索引表中确定相应的物理块号，从而只需要访问一次磁盘。
3.文件存储设备管理
文件存储设备管理，就是操作系统要有效地进行存储空间的管理。由于文件存储设备是分成许多大小相同的物理块，并以块为单位交换信息，因此，文件存储设备的管理实质上是对空闲块的组织和管理问题。它包括空闲块的组织，空闲块的分配与空闲块的回收等问题。有3种不同的空闲块管理方法，它们分别是索引法、链接法和位示图法。
（1）索引法。索引法把空闲块作为文件并采用索引技术。为了有效，索引对应于一个或由几个空闲块构成的空闲区。这样，磁盘上每一个空闲块区都对应于索引表中一个条目，这个方法能有效地支持每一种文件分配方法。
在系统中为某个文件分配空闲块时，首先扫描索引空闲文件目录项，如找到合适的空闲区项，则分配给申请者，并把该项从索引空闲文件中去掉。如果一个空闲区不能满足申请者的要求，则把另一项分配给申请者。如果一个空闲区所含块数超过申请者的要求，则为申请者分配所要的物理块后，再修改该表项。当一个文件被删除释放物理块时，系统则把被释放的块号以及第一块块号置入索引空闲文件的新表项中。
希赛教育专家提示：在内存管理中所用到的有关空闲区的分配和回收算法，只要稍加修改就可以用于索引法。
（2）链接法。链接法使用链表把空闲块组织在一起，当申请者需要空闲块时，分配程
系统架构设计师
http://www.daodoc.com/
序从链首开始摘取所需的空闲块。反之，管理程序把回收的空闲块逐个地挂入队尾，这个方法适用于每一种文件分配方法。空闲块的链接方法可以按释放的先后顺序链接，也可以是按空闲块区（连续/1个空闲块）的大小顺序链接。后者有利于获得连续的空闲块的请求，但在分配请求和回收空闲块时系统开销多一点。
（3）位示图法。该方法是在外存上建立一张位示图（Bitmap），记录文件存储器的使用情况。每一位仅对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。文件存储器上的物理块依次编号为：0、
1、
2、…假如系统中字长为32位，有4096个物理块，那么在位示图中的第1个字对应文件存储器上的0、
1、2…31号物理块；第2个字对应文件存储器上的
32、
33、
34、…、63号物理块；第128字对应文件存储器上的406
4、406
5、…、4095号物理块。这样位示图的大小为32字。
位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，如图1-13所示。当其值为\"0\"时，表示对应的盘块空闲；为\"1\"时表示已分配。由所有盘块对应的位构成一个集合，称为位示图。位示图也可描述为一个二维数组map:Var map:array[1…m,1…n]of bit;
图1-13 位示图
4.树型目录结构
在计算机的文件系统中，一般采用树型目录结构。在树型目录结构中，树的根结点为根
系统架构设计师
http://www.daodoc.com/
目录，数据文件作为树叶，其他所有目录均作为树的结点。
根目录隐含于一个硬盘的一个分区中，根目录在最顶层。它包含的子目录是一级子目录。每一个一级子目录又可以包含若干二级子目录，…，这样的组织结构就叫做目录树。
当前盘和当前目录是系统默认的操作对象。如果用户没有指明操作对象，系统就将用户命令指向当前盘和当前目录。
路径是指从根目录或者当前目录开始到访问对象（目录或者文件），在目录树中路经过的所有目录的序列。例如\"c:\\dos\\lmouse\\mouse\"就是Windows系统中的一条路径。在树型目录结构中，从根目录到任何数据文件之间，只有一条惟一的通路，从树根开始，把全部目录文件名与数据文件名，依次用\"/\"（UNIX/Linux系统）或\"\"（Windows系统）连接起来，构成该数据文件的路径名，且每个数据文件的路径名是惟一的。这样，可以解决文件重名问题。
从树根开始的路径为绝对路径，如果文件系统有很多级时，使用不是很方便，所以引入相对路径，即是从当前目录开始，再逐级通过中间的目录文件，最后到达所要访问的数据文件。
绝对路径给出文件或目录位置的完全的描述，通常由层次结构的顶端开始（根目录），通常第一个字符是\"/\"（UNIX/Linux系统）或者是盘符（Windows系统）。相对路径通常由目录结构中的当前的位置开始，一般都比绝对路径要短。
父目录是指当前路径的上一层目录。每个目录下都有代表当前目录的\".\"文件和代表当前目录父目录的\"\"文件，相对路径名一般就是从\"\"开始的。
1.2.5 作业管理
从用户的角度看，作业（Job）是系统为完成一个用户的计算任务（或一次事务处理）
系统架构设计师
http://www.daodoc.com/
所做的工作总和。例如，对于用户编制的源程序，需经过对源程序的编译、连接编辑或连接装入以及运行产生计算结果。这其中的每一个步骤，常称为作业步，作业步的顺序执行即完成了一个作业。
从系统的角度看，作业则是一个比程序更广的概念。它由程序、数据和作业说明书组成。系统通过作业说明书控制文件形式的程序和数据，使之执行和操作。而且，在批处理系统中，作业是抢占内存的基本单位。
操作系统中用来控制作业的进入、执行和撤销的一组程序称为作业管理程序，这些控制功能也能通过把作业步细化，通过进程的执行来实现。
用户的作业可以通过直接的方式，由用户自己按照作业步顺序操作，也可以通过间接的方式，由用户率先编写的作业步依次执行的说明，一次交给操作系统，由系统按照说明依次处理。前者称为联机方式，后者称为脱机方式。
1.作业控制与作业管理
一般操作系统提供两种作业控制方式：一种为联机方式，另一种为脱机方式。
（1）联机方式。联机方式是通过直接输入作业控制命令，提交用户作业，运行用户作业。用户作业的提交是通过终端依次键入操作命令或可执行程序名提出运行请求，系统做出相应的处理，直至完成一个作业的计算要求。
命令的输入有两种方式。一种是交互式输入，用户每键入一条命令，操作系统接收命令，解释执行然后等待用户键入下一条命令，直到作业完成为止。另一种是连续批处理输入，用户键入一条命令，不等这条命令执行完成（让这条命令在后台运行），用户又可键入下一条命令，而连续键入若干命令形成命令串，由操作系统自动地对这些命令逐个取出并解释执行多行，最后给出计算结果。
系统架构设计师
http://www.daodoc.com/
（2）脱机方式。脱机方式是通过作业控制语言（也称做业控制命令），编写用户作业说明书。这种方式中，用户不直接干预作业的运行，而是把作业与作业说明书一起交给系统，当系统调度到这个程序时，由操作系统根据作业说明书对其中的作业控制语言和命令解释执行。
早期的脱机作业方式是由操作员接收用户的请求再提交给系统的。现代操作系统提供了让用户经终端把作业和作业说明书直接提交给系统的能力。
2.作业状态及其转换
一个作业从交给计算机系统到执行结束退出系统，一般都要经历提交、后备、执行和完成4个状态。其状态转换如图1-14所示。
图1-14 作业的状态及其转换
（1）提交状态。作业由输入设备进入外存储器（也称输入井）的过程称为提交状态。处于提交状态的作业，其信息正在进入系统。
（2）后备状态。当作业的全部信息进入外存后，系统就为该作业建立一个作业控制块（Job Control Block,JCB）。系统通过JCB感知作业的存在。JCB包括的主要内容包括作业名、作业状态、资源要求、作业控制方式、作业类型以及作业优先权等。
系统架构设计师
http://www.daodoc.com/
（3）执行状态。一个后备作业被作业调度程序选中而分配了必要的资源并进入了内存，作业调度程序同时为其建立了相应的进程后，该作业就由后备状态变成了执行状态。
（4）完成状态。当作业正常运行结束，它所占用的资源尚未全部被系统回收时的状态为完成状态。
3.处理机调度
处理机调度通常分为三级调度：高级调度、中级调度和低级调度。
（1）高级调度。高级调度也称为作业调度。高级调度的主要功能是在批处理作业的后备作业队列中选择一个或者一组作业，为它们建立进程，分配必要的资源，使它们能够运行起来。
（2）中级调度。中级调度也称为交换调度。中级调度决定进程在内、外存之间的调入、调出。其主要功能是在内存资源不足时将某些处于等待状态或就绪状态的进程调出内存，腾出空间后，再将外存上的就绪进程调入内存。
（3）低级调度。低级调度也称为进程调度。低级调度的主要功能是确定处理器在就绪进程间的分配。
4.作业调度
作业调度主要完成从后备状态到执行状态的转变及从执行状态到完成状态的转变。
作业调度算法有许多种。与进程调度相似，调度算法有的适宜于单道系统，有的适宜于多道系统。作业调度算法有：
（1）先来先服务。按作业到达的先后次序调度，它不利于短作业。
（2）短作业优先（Short Job First,SJF）。按作业的估计运行时间调度，估计运行时间短的作业优先调度。它不利于长作业，可能会使一个估计运行时间长的作业迟迟得不到服
系统架构设计师
http://www.daodoc.com/
务。
（3）响应比高者优先（Highest Response Ratio Next,HRRN）。综合上述两者，既考虑作业估计运行时间，又考虑作业等待时间，响应比是：
HRRN = （估计运行时间+等待时间）/估计运行时间
（4）优先级调度。根据作业的优先级别，优先级高者先调度。
5.用户接口
用户接口也称为用户界面，其含义有两种，一种是指用户与操作系统交互的途径和通道，即操作系统的接口；另一种是指这种交互环境的控制方式，即操作环境。
（1）操作系统的接口。操作系统的接口又可分成命令接口和程序接口。命令接口包含键盘命令和作业控制命令；程序接口又称为编程接口或系统调用，程序经编程接口请求系统服务，即通过系统调用程序与操作系统通信。系统调用是操作系统提供给编程人员的惟一接口。系统调用对用户屏蔽了操作系统的具体动作而只提供有关功能。系统调用大致分为设备管理、文件管理、进程控制、进程通信和存储管理等。
（2）操作环境。操作环境支持命令接口和程序接口，提供友好的、易用的操作平台。操作系统的交互界面已经从早期的命令驱动方式，发展到菜单驱动方式、图符驱动方式和视窗操作环境。
如需阅读完整版教材请到希赛软考学院，
系统架构设计师教程（第3版）：http://www.daodoc.com/
