系统架构设计师考试全程指导(第2版)

第1章 操作

根据考试大纲要求,在操作系统方面,要求考生掌握以下知识点∶

(1)操作系统的类型和结构∶

(2)操作系统的基本原理;

(3)网络操作系统及网络管理;

(4)嵌入式操作系统与实时操作系统。

本章主要介绍操作系统方面的基本知识,有关网络管理方面的知识,将在第4章中介绍∶有关嵌入式操作系统与实时操作系统方面的知识,将在第3章介绍。

1.1 操作系统的类型与结构

<b>1.1 操作系统的类型与结构</b>

操作系统是计算机系统中的核心系统软件,负责管理和控制计算机系统中硬件和软件资源,合理地组织计算机工作流程和有效地利用资源,在计算机与用户之间起接口的作用。

<b>1.1.1 操作系统的类型</b>

根据使用环境和对作业的处理方式,操作系统可分为批处理操作系统、分时操作系统、实时操作系统、网络操作系统和分布式操作系统。

  • 批处理操作系统把用户提交的作业分类,把一批中的作业编成一个作业执行序列。批处理又可分为联机批处理和脱机批处理。批处理系统的主要特征有:用户脱机使用计算机、成批处理、多道程序运行。
  • 分时操作系统采用分时技术、使多个用户同时以会话方式控制自己程序的运行,每个用户都感到似乎各自有一台独立的、支持自己请求服务的系统。分时技术把处理机的运行时间分成很短的时间片,按时间片轮流把处理机分配给各联机作业使用。若某个作业在分配给它的时间片内不能完成其计算,则该作业暂时中断,把处理机让给另一作业使用,等待下一轮时再继续运行。分时系统的主要特征有:交互性、多用户同时性、独立性。
  • 实时操作系统往往是专用的,系统与应用很难分离,常常紧密结合在一起的。实时系统并不强调资源利用率,而更关心及时性(时间紧迫性)、可靠性和完整性。实时系统又分为实时过程控制与实时信息处理两种。实时系统的主要特征有:提供即时响应、高可靠性。
  • 网络操作系统按照网络架构的各个协议标准进行开发,包括网络管理、通信、资源共享、系统安全和多种网络应用服务等。在网络系统中,各计算机的操作系统可以互不相同,它需要有一个支持异种计算机系统之间进程通信的网络环境,以实现协同工作和应用集成。网络操作系统的主要特征有:互操作性、协作处理。
  • 分布式操作系统要求有一个统一的操作系统,实现系统操作的统一性,负责全系统的资源分配和调度,为用户提供统一的界面。它是一个逻辑上紧密耦合的系统。

不管哪种操作系统,都应该具有5个基本功能,即处理机管理、存储管理、设备管理、文件管理和作业管理。

<b>1.1.2 操作系统的结构</b>

操作系统的结构可以分为无序结构、层次结构、面向对象结构、对称多处理结构和微内核结构。

  • 无序结构,又称整体结构或模块组合结构。它以大型表格和队列为中心,操作系统的各部分程序围绕着表格运行,整个系统是一个程序。这种操作系统常称为面向过程的操作系统。操作系统由许多标准的、可兼容的基本单位构成(称为模块),各模块相对独立,模块之间通过规定的接口相互调用。模块化设计方法的优点是缩短了系统的开发周期,缺点是模块之间调用关系复杂、相互依赖,从而使分析、移植和维护系统较易出错。
  • 层次结构。把一个大型复杂的操作系统分解成若干个单向依赖的层次,由多层的正确性保证操作系统的可靠性。层次结构清晰,大大地简化了接口的设计,且有利于系统功能的增加或删改,易于保证可靠性,也便于维护和移植。
  • 面向对象结构。基于面向对象程序设计的概念,采用了各种不同的对象技术。在计算机系统中对象是操作系统管理的信息和资源的抽象,是一种抽象的数据类型。可以把对象作为系统中的最小单位,由对象、对象操作、对象保护组成的操作系统,就是面向对象的操作系统,如Windows Server中有执行体对象(例如,进程、线程、文件和令牌等)和内核对象(例如,时钟、事件和信号等)。面向对象结构的优点是适用于网络操作系统和分布式操作系统中。
  • 对称多处理结构。如果一个操作系统在系统中的所有处理机运行且共享同一内存(内存储器、主存、实存),这样的系统就是一个对称多处理系统。优点是适合共享存储器结构的多处理机系统,即紧耦合的多处理机系统。
  • 微内核结构。把系统的公共部分抽象出来,形成一个底层核心,提供最基本的服务,其他功能以服务器形式建立在微内核之上。它具有良好的模块化和结构化特征,模块之间和上下层之间通过消息来通信。建立在微内核上的服务器可以根据不同的需要构造,从而形成不同的操作系统。

现代操作系统大多拥有两种工作状态:核心态和用户态。我们使用的一般应用程序工作在用户态,而内核模块和最基本的操作系统核心工作在核心态。

微内核结构由一个非常简单的硬件抽象层和一组比较关键的原语或系统调用组成,这些原语仅仅包括了建立一个系统必需的几个部分,如线程管理、地址空间和进程间通信等。微内核的目标是将系统服务的实现和系统的基本操作规则分离开来。例如,进程的输入/输出锁定服务可以由运行在微内核之外的一个服务组件来提供。这些模块化的用户态服务用于完成操作系统中比较高级的操作,这样的设计使内核中最核心的部分的设计更简单。一个组件的失效并不会导致整个系统的崩溃,内核需要做的,仅仅是重新启动这个组件,而不必影响其他的部分。

微内核技术的主要优点如下:

  • 具有统一的接口,在用户态和核心态之间无需进程识别。
  • 可伸缩性好,能适应硬件更新和应用变化
  • 可移植性好,所有与具体机器特征相关的代码,全部隔离在微内核中,如果操作系统要移植到不同的硬件平台上,只需修改微内核中极少代码即可。
  • 实时性好,微内核可以方便地支持实时处理。
  • 安全可靠性高,微内核将安全性作为系统内部特性来进行设计,对外仅使用少量应用编程接口。
  • 支持分布式系统,支持多处理器的架构和高度并行的应用程序。
  • 真正面向对象的操作系统。

由于操作系统核心常驻内存,而微内核结构精简了操作系统的核心功能,内核规模比较小,一些功能都移到了外存上,所以微内核结构十分适合嵌入式的专用系统,对于通用性较广的系统,将使CPU(Central Processing Unit,中央处理单元)的通信开销增大,从而影响到计算机的运行速度。

<b>1.2 处理器管理</b>

在单用户多任务的操作系统中,或者多用户多任务的操作系统中,系统同时运行多个程序,这些程序的并行运行势必形成对系统资源的竞争使用。因此,操作系统必须能够处理和管理这种并行运行的程序,使之对资源的使用按照良性的顺序进行。

<b>1.2.1 进程的状态</b>

进程是一个程序关于某个数据集的一次运行。进程是程序的一次运行活动,是一个动态的概念,而程序是静态的概念,是指令的集合。进程具有动态性和并发性,程序是进程运行所对应的运行代码,一个进程对应于一个程序,一个程序可以同时对应于多个进程。在操作系统中进程是进行系统资源分配、调度和管理的最小单位(注意,现代操作系统中还引入了线程(thread)这一概念,它是处理器分配资源的最小单位)。从静态的观点看,进程由程序、数据和进程控制块(Process Control Block,PCB)组成;从动态的观点看,进程是计算机状态的一个有序集合。

PCB是进程存在的唯一标志,PCB描述了进程的基本情况。其中的内容可分成为调度信息和执行信息两大部分。调度信息供进程调度使用,包括进程当前的一些基本属性;执行信息即现场,刻画了进程的执行情况。PCB随着进程的建立而产生,随着进程的完成而撤销。

一个进程从创建而产生至撤销而消亡的整个生命周期,可以用一组状态加以刻画,为了便于管理进程,把进程划分为几种状态,分别有三态模型和五态模型。

<b>1、三态模型</b>

按照进程在执行过程中的不同状况,至少可以定义三种不同的进程状态:

  • 运行态:占有处理器正在运行。
  • 就绪态:具备运行条件,等待系统分配处理器以便运行。
  • 等待态(阻塞态):不具备运行条件,正在等待某个事件的完成。

一个进程在创建后将处于就绪状态。每个进程在执行过程中,任一时刻当且仅当处于上述三种状态之一。同时,在一个进程执行过程中,它的状态会发生改变。如图所示为进程的状态转换。

运行状态的进程将由于出现等待事件而进入等待状态,当等待事件结束之后等待状态的进程将进入就绪状态,而处理器的调度策略又会引起运行状态和就绪状态之间的切换。引起进程状态转换的具体原因如下:

  • 运行态 -> 等待态:等待使用资源,如等待外设传输;等待人工干预。
  • 等待态 -> 就绪态:资源得到满足,如外设传输结束;人工干预完成。
  • 运行态 -> 就绪态:运行时间片到;出现有更高优先权进程。
  • 就绪态 -> 运行态:CPU空闲时选择一个就绪进程。
<b>2、五态模型</b>

在三态模型中,总是假设所有的进程都在内存中。事实上,可能出现这样一些情况,例如由于进程的不断创建,系统的资源已经不能满足进程运行的要求,这个时候就必须把某些进程挂起,对换到磁盘镜像区中,暂时不参与进程调度,起到平滑系统操作负荷的目的。引起线程挂起的原因是多样的,主要有如下几种原因。

1、系统中的进程均处于等待状态,处理器空闲,此时需要把一些阻塞进程对换出去,以腾出足够的内存装入就绪进程运行。

2、进程竞争资源,导致系统资源不足,负荷过重,此时需要挂起部分进程以调整系统负荷,保证系统的实时性或让系统正常运行。

3、把一些定期执行的进程(如审计程序、监控程序和记账程序)对换出去,以减轻系统负荷。

4、用户要求挂起自己的进程,以便根据中间执行情况和中间结果进行某些调试、检查和改正。

5、父进程要求挂起自己的后代子进程,以进行某些检查和改正。

6、操作系统需要挂起某些进程,检查运行中资源使用情况,以改善系统性能;或当系统出现故障或某些功能受到破坏时,需要挂起某些进程以排除故障。

图1-2给出了具有挂起进程功能的系统中的进程状态。在此类系统中,进程增加了两个新状态:静止就绪态和静止阻塞态。为了区别,而把三态模型中的等待态改名为活跃阻塞态,就绪态改为活跃就绪态。静止就绪态表明进程具备运行条件,但目前在二级存储器(辅存)中,只有当它被对换到内存中才能被调度执行。静止阻塞态则表明进程正在等待某一个事件,且在二级存储器中。

五态模型说明:

1、进程禁止、活跃、就绪、阻塞四状态转换,必须保证单属性一致,如:

静止阻塞 -> 静止就绪 静止属性一致

静止就绪 -> 活跃就绪 就绪属性一致

2、阻塞-就绪 状态转换为单向

即只能从阻塞转换为就绪,不能反过来。

静止阻塞 —-【等待事件发生】 —- 静止就绪

活跃阻塞 —-【等待事件发生】 —- 活跃就绪

3、静止-活跃 状态转换为双向

静止-活跃 状态可以互相转换

静止阻塞 —-【恢复或激活】 —- 活跃阻塞

活跃阻塞 —-【挂起】 —- 静止阻塞

就绪状态一样。

4、运行状态说明

运行 —-【挂起】 —- 静止就绪

运行 —-【出现等待事件】 —- 活跃阻塞

运行 —-【时间片到】 —- 活跃就绪

活跃就绪 —-【调度】 —- 运行

2、状态转换动作说明

引起进程状态转换的具体原因如下:

1、活跃阻塞态 -> 静止阻塞态:如果当前不存在活跃就绪态进程,那么至少有一个等待态进程将被对换出去成为静止阻塞态;操作系统根据当前资源状况和性能要求,可以决定把活跃阻塞态进程对换出去成为静止阻塞态。

2、静止阻塞态 -> 静止就绪态:引起进程等待的事件发生之后,相应的静止阻塞态将转换为静止就绪态。

3、静止就绪态 -> 活跃就绪态:当内存中没有活跃就绪态进程,或者静止就绪态进程具有比活跃就绪态进程更高的优先级,系统将把静止就绪态进程转换成活跃就绪态。

4、活跃就绪态 -> 静止就绪态:操作系统根据当前资源状况和性能要求,也可以决定把活跃就绪态进程对换出去成为静止就绪态。

5、静止阻塞态 -> 活跃阻塞态:当一个进程等待一个事情时,原则上不需要把它调入内存。当时,但一个进程退出后,内存已经有了一大块自由空间,而某个静态阻塞态进程具有较高的优先级并且操作系统已经得知导致它阻塞的事件即将结束,此时便发生了这一状态变化。

不难看出,一个挂起进程等同于不在内存的进程,因此挂起的进程将不参与进程调度直到它们被对换进内存。一个挂起的进程具有如下特征:

  • 该进程不能立即被执行。
  • 挂起进程可能会等待一个事件,但多等待的事件是独立于挂起条件的,事件结束并不能导致进程具备执行条件。
  • 进程进入挂起状态是由于操作系统、父进程和进程本身阻止它的运行。
  • 结束进程挂起状态的命令只能通过操作系统或父进程发起。
  • 阻塞态。进入阻塞态通常是因为在等待I/O完成或等待分配到需要资源。

<b>1.2.2 信号量与PV操作</b>

对于本知识点的考查,重点在于理解信号量与PV操作的基本概念,能够正确地理解在互斥、同步方面的控制应用,并能够灵活的运行,相对来说是个难点。

在操作系统中,进程之间经常会存在互斥(都需要共享独占性资源时)和同步(完成异步的两个进程的协作)两种关系。为了有效的处理这两种情况,W.Dijkstra在1965年提出信号量和PV操作。

  • 信号量:是一种特殊的变量,表现形式是一个整型S和一个队列。
  • P操作:S = S – 1,若 S<0,进程暂停执行,进入等待队列。
  • V操作:S = S + 1,若 S<=0,唤醒等待队列中的一个进程。
<b>1、互斥控制</b>

互斥控制是为了保护共享资源,不让多个进程同时访问这个共享资源。换句话说,就是阻止多个进程同时进入访问这些资源的代码段,这个代码段称为临界区,而这种一次只允许一个进程访问的资源称为临界资源。为了实现进程互斥的进入自己的临界区,代码可以如下所示:

由于只允许一个进程进入,因此信号量S的初始值应该为1。该值表示可以允许多少个进程进入,当 S<0时,其绝对值就是等待使用临界资源的进程数,也就是等待队列中的进程数。而当一个进程从临界区出来时,执行V操作 (S=S+1),如果等待队列中还有进程(S<=0),则调入一个新的进程(唤醒)。

<b>2、同步控制</b>

最简单的同步形式是进程A在另一个进程B到达L2以前,不应前进到超过点L1,这样就可以使用如下程序:

因此,要确保进程B执行V操作之前,不让进程A的运行超过L1,就要设置信号量S的初值为0。这样,如果进程A先执行到L1,那么执行P操作(S=S-1),则S<0,就停止执行。直到进程B执行到L2时,执行V操作(S=S+1),唤醒A以继续执行。

<b>3、生产者-消费者问题</b>

生产者-消费者是一个经典的问题,它不仅要解决生产者进程与消费者进程的同步关系,还要处理缓冲区的互斥关系,因此通常需要三个信号量来实现,如表1-1所示:

信号量功能类别功能说明
empty同步说明空闲的缓冲区数量,因为程序开始时,缓冲区全部为空,所以,其初始值应为缓冲区的总个数
full同步说明已填充的缓冲区数量、因为程序开始时,所有缓冲区都为空(未填充),所以,其初始值应为0
mutex互斥保证同时只有一个进程在写缓冲区,因此,其初始值应为1

如果对缓冲区的读写无须进行互斥控制的话,那么就可以省去mutex信号量。

<b>4、理解P、V操作</b>

信号量与PV操作的概念比较抽象,在历年的考试中总是难倒许多考生,其实主要还是没有能够正确地理解信号量的含义。

  • (1)信号量与P、V操作是用来解决并发问题的,而在并发问题中最重要的是互斥与同步两个关系,也就是说,只要有这两个关系存在,信号量就有用武之地。因此,在解题时,应该先从寻找互斥与同步关系开始。这个过程可以套用简单互斥、简单同步、生产者-消费者问题。
  • (2)通常来说,一个互斥或一个同步关系可以使用一个信号量来解决,但要注意经常会忽略一些隐藏的同步关系。例如,在生产者-消费者问题中,就有两个同步关系,一个是判断是否还有足够的空间给生产者存放产物,另一个是判断是否有足够的内容让消费者使用。
  • (3)信号量的初值通常就是表示资源的可用数。而且通常对于初始为0的信号量,会先做V操作。
  • (4)在资源使用之前,将会使用P操作;在资源使用之后,将会使用V操作。在互斥关系中,P、V操作是在一个进程中成对出现的;而在同步关系中,P、V操作一定是在两个进程甚至是多个进程中成对出现的。
<b>5、实际应用</b>

在考试时,可能会出现一些需要综合应用的问题,需要考生根据基本的概念,结合实际问题进行解答。

例如,在某并发系统中,有一个发送进程A、一个接受进程B、一个环形缓冲区BUFFER、信号量S1和S2。发送进程不断地产生消息并写入缓冲区BUFFER,接受进程不断地从缓冲区BUFFER取消息。假设发送进程和接受进程可以并发地执行,那么,当缓冲区的容量为N时,如何使用P、V操作才能保证系统的正常工作。发送进程A和接受进程B的工作流程如图1-3所示。请在图1-3中的(1)-(4)处填写正确的操作。

根据题意,很显然,这是一个“生产者-消费者”问题,根据该问题的特性,通常需要三个信号量来实现:两个用来管理缓冲区同步,信号量empty表示空闲缓冲区的数量,初值为缓冲区最大数N,信号量full表示已填充缓冲区数量,初值为0;一个用于管理互斥,由信号量mutex保证只有一个进程在写缓冲区,初值为1。但在本题中,进程A和进程B允许并发地访问缓冲区,因此无须管理互斥,就不需要使用信号量mutex了。因此,因此,只需定义两个信号量:S1和S2,初值为N的S1在此承担的是信号量empty的功能,初值为0的S2在此承担的是信号量full的功能。

通过这样的分析,不难得出:

(1)处应该是P(S1),将空闲缓冲区数量减1;

(2)处应该是V(S2),将已填充的缓冲区数量加1;

(3)处则是P(S2);

(4)处为V(S1)。

在这个例子的基础上,如果系统中有多个发送进程和接受进程,进程间的工作流程如图1-4所示,其中空(1)- (4)的内容与图1-3相同。发送进程产生消息并顺序地写入环形缓冲区BUFFER,接受者进程顺序地从BUFFER中取消息,且每条消息只能读取一次。为了保证进程间的正确通信,增加了信号量Sa和Sb。请说明信息量Sa和Sb的物理意义,在图1-4中的(5)和(6)处填入正确的内容,并从图1-4的(a) – (1)中选择4个位置正确地插入P(Sa)、V(Sa)、P(Sb)、V(Sb)。

图1-4所涉及的问题在普通的“生产者-消费者”问题上增加了一些复杂度:“系统中有多个发送进程和接受进程”,根据题意,可以得知它要完成的控制是发送进程的顺序写入,接受进程顺序读取,而且每条消息都只能够读取一次。这显然是两个互斥的问题,即多个发送进程在写缓冲区时是互斥关系,多个接受进程在读缓冲区时也是互斥关系。因此,信号量Sa和Sb分别实现用来完成两个进程间的互斥控制。

(1)Sa:初值为1,表示允许同时对缓冲区进行写操作的进程数量。

(2)Sb:初值为1,表示允许同时对缓冲区进行读操作进程数量。

当然,两个对调也是可以的。在发送进程和接受进程中分别有一组信号量Sa和Sb的P、V操作。因此,接下来的问题就是找插入点。互斥控制的要点在于判断临界区的范围,也就是哪部分程序必须互斥进入,否则将出现问题。根据这一点,可以进行如下分析:

(1)发送进程:在进程产生消息之后准备写入缓冲区时,需要进行互斥判断,因此在位置(b)应插入P(Sa);而直到完成“i = (i + 1) mod N”操作后,才完成缓冲区操作,因此必须在位置(f)插入V(Sa)。

(2)接收进程:由于接收进程是负责读数据的,如果数据区是空的则应该等待,因此必须先完成P(S2)操作,来决定其是否需要阻塞。如果没有阻塞时,再进入临界区,因此应该在位置(h)处操作P(Sb);而“对读取的消息进行处理”已显然在临界区之外,因此应该在位置(k)插入V(Sb)。

<b>1.2.3 死锁问题</b>

死锁是指多个进程之间互相等待对方的资源,而在得到对方资源之前又不释放自己的资源,这样,造成循环等待的一种现象。如果一个进程在等待一个不可能发生的事件,则进程就死锁了。如果一个或多个进程产生死锁,就会造成系统死锁。

<b>1、死锁发生的必要条件</b>

产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。产生死锁有4个必要条件:互斥条件、不可抢占条件、保持与等待条件(部分分配条件)、循环等待条件。

  • (1)互斥条件:即一个资源每次只能被一个进程使用。
  • (2)保持与等待条件:有一个进程已获得了一些资源,但请求其他资源时被阻塞,因此对已获得的资源保持不放。
  • (3)不可抢占条件:有些系统资源是不可抢占的,当某个进程已获得这种资源后,系统不能强行收回,只能由进程使用完时自己释放。
  • (4)循环等待条件:若干个进程形成环形链,每个都占用对方要申请的下一个资源。
<b>2、银行家算法</b>

所谓银行家算法,是指在分配资源之前先看清楚,资源分配后是否会导致系统死锁。如果会死锁,则不分配,否则就分配。

按照银行家算法的思想,当进程请求资源时,系统将按如下原则分配资源。

  • (1)当一个进程对资源的最大需求量不超过系统中的资源数时,可以接纳该线程。
  • (2)进程可以分期请求资源,但请求的总数不能超过最大需求量。
  • (3)当系统现有的资源不能满足进程尚需资源数时,对进程的请求可以推迟分配,但总能使进程在有限的时间里得到资源。
  • (4)当系统现有的资源能满足进程尚需资源数时,必须测试系统现存的资源能否满足该进程尚需的最大资源数,若能满足则按当前的申请量分配资源,否则也要推迟分配。

对于这些内容,关键在于融会贯通地理解与应用。下面通过一个例子来说明银行家算法的应用。

假设系统中有三类互斥资源R1、R2和R3,可用资源数分别是9、8和5。在T0时刻系统中有P1、P2、P3、P4和P5这5个进程,这些进程对资源的最大需求量和已分配资源数如表1-2所示。进程按照P1-P2-P4-P5-P3序列执行,系统状态安全吗?如果按P2-P4-P5-P1-P3的序列执行呢?

在这个例子中,先看一下未分配的资源还有哪些?根据试题给出的条件,从上表可以看出,很明显,还有2个R1未分配,1个R2未分配,而R3全部分配完毕。

按照P1-P2-P4-P5-P3的顺序执行时,首先执行P1,这时由于其R1、R2和R3的资源数都未分配够,因而开始申请资源,得到还未分配的2个R1、1个R2、。但其资源仍不足(没有R3资源),从而进入阻塞状态,并且这时所有资源都已经分配完毕。因此,后续的进程都无法得到能够完成任务的资源,全部进入阻塞,死锁发生了。

而如果按照P2-P4-P5-P1-P3的序列执行时:

  • (1)首先执行P2,它还差1个R2资源,系统中还有1个未分配的R2,因此满足其要求,能够顺利结束进程,释放出2个R1、2个R2、1个R3。这时,未分配的资源就是4个R1、2个R2、1个R3。
  • (2)然后执行P4,它还差一个R3,而系统中正好有一个未分配的R3,因此满足其要求,也能够顺利结束,并释放出其资源。因此,这时系统就有5个R1、4个R2、1个R3。根据这样的方式推下去。

会发现按这种序列可以顺利地完成所有的进程,而不会出现死锁现象。

从这个例子中可以体会到,死锁的4个条件是如何引起作用的。只要打破任何一个条件,都不会产生死锁。

<b>3、解决死锁的策略</b>

对待死锁的策略主要有如下几种:

  • (1)死锁预防。破坏导致死锁必要条件中的任意一个就可以预防死锁。例如,要求用户申请资源时一次性申请所需要的全部资源,这就破坏了保持和等待条件;将资源分层,得到上一层资源后,才能够申请下一层资源,它破坏了环路等待条件。预防通常会降低系统的效率。
  • (2)死锁避免。避免是指进程在每次申请资源时判断这些操作是否安全,例如,使用银行家算法。死锁避免算法的执行会增加系统的开销。
  • (3)死锁检测。死锁预防和避免都是事前措施,而死锁的检测则是判断系统是否处于死锁状态,如果是,则执行死锁解除策略。
  • (4)死锁解除。这是与死锁检测结合使用的,它使用的方式就是剥夺。即将某进程所拥有的资源强行收回,分配给其他的进程。

<b>1.2.4管程与线程</b>

管程由管程名、局部子管程的变量说明、使用共享资源并在数据集上进行操作的若干过程以及对变量赋初值的语句4个基本部分组成。每一个管程管理一个临界资源。当有几个进程调用某管程时,仅允许一个进程进入管程,其它调用者必须等待,也就是申请进程必须互斥地进入管程。方法是通过调用特定的管程入口进入管程,然后通过管程中的一个过程使用临界资源。当某进程通过调用请求访问某临界资源而未能满足时,管程调用相应同步原语使该进程等待,并将它排在等待队列上。当使用临界资源的进程访问完该临界资源并释放之后,管程又调用相应的同步原语唤醒等待队列中的队首进程。为了表示不同的等待原因,设置条件变量,条件变量是与普通变量不同的变量,条件变量不能取任何值,只是一个排队栈。

线程是进程的活动成分,是处理器分配资源的最小单位,它可以共享进程的资源和地址空间,通过线程的活动,进程可以提供多种服务(对服务器进程而言)或实行子任务并行(对用户进程而言)。每个进程创建时只有一个线程,根据需要在运行过程中创建更多的线程(前者也可以称为“主线程”)。显然,只有主线程的进程才是传统意义下的进程。内核负责线程的调度,线程的优先级可以动态地改变。采用线程机制的最大优点是节省开销,传统的进程创建子进程的办法内存开销大,而且创建时间也长。

在多线程系统中,一个进程可以由一个或多个线程构成,每一线程可以独立运行,一个进程的线程共享这个进程的地址空间。有多种方法可以实现多线程系统,一种方法是核心级线程,另一种方法是用户级线程,也可以把两者组合起来。

多线程实现的并行避免了进程间并行的缺点:创建线程的开销比创建进程要小,同一进程的线程共享进程的地址空间,所以线程切换(处理器调度)比进程切换快。例如,Windows Server内核采用基于优先级的方案选定线程执行的次序。高优先级线程先于低优先级线程执行,内核周期性地改变线程的优先级,以确保所有的线程均能执行。

<b>1.3 文件管理</b>

文件管理是对外部存储设备上的以文件方式存放的信息的管理。文件的结构是指文件的组织形式,从用户角度所看到的文件组织形式,称为文件的逻辑结构。文件的物理结构是指文件在存储设备上的存放方法,侧重于提高存储器的利用效率和降低存取时间。文件的存储设备通常划分为大小相同的物理块,物理块是分配和传输信息的基本单位。用户通过对文件的访问(读写)来完成对文件的查找、修改、删除和添加等操作。常用的访问方法有两种,即顺序访问和随机访问。

<b>1.3.1 文件的逻辑组织</b>

文件的逻辑组织是为了方便用户的使用,逻辑结构是用户可见的结构。文件的逻辑结构可以分为无结构的字符流文件和有结构的记录文件两种,后者也称为有格式文件。记录文件由记录组成,即文件的内容划分成多个记录,以记录为单位组织和使用信息。

常用的记录式结构有连续结构、多重结构、转置结构和顺序结构。

  • (1)连续结构∶连续结构是一种把记录按生成的先后顺序排列的逻辑结构。连续结构的特点是适用性强,可用于所有文件,且记录的排列顺序与记录的内容无关。缺点是搜索性能较差。
  • (2)多重结构∶多重文件把记录按键和记录名排列成行列式结构,一个包含n个记录名、m个键的文件构成一个 m×n 维行列式。

  • (3)转置结构∶转置结构把含有相同键的记录指针全部指向该键,也就是说,把所有与同一键对应的记录的指针连续地置于目录中该键的位置下。转置结构最适合于给定键后的记录搜索。
  • (4)顺序结构∶顺序结构把文件中的键按规定的顺序排列起来。

用户通过对文件的存取来完成对文件的修改、追加和搜索等操作,常用的存取方法有顺序存取法、随机存取法(直接存取法)和按键存取法。

<b>1.3.2 文件的物理组织</b>

在文件系统中,文件的存储设备通常划分为若干个大小相等的物理块。文件的物理结构是指文件在存储设备上的存储方法,常用的文件物理结构有连续文件、串联文件和索引文件。

  • (1)连续文件(顺序文件)∶连续文件是一种最简单的物理文件结构,它把一个在逻辑上连续的文件信息依次存放到物理块中。连续文件的优点是一旦知道文件在文件存储设备上的起始位置和文件长度,就能进行存取。连续文件适合于顺序存取,在连续存取相邻信息时,存取速度快。其缺点是在文件建立时必须指定文件的信息长度,以后不能动态增长,需要经常修改的文件一般不宜采用此方式存储。
  • (2)串联文件(链接文件)∶串联文件用非连续的物理块来存放文件信息,这些物理块之间没有顺序关系,其中每个物理块设有一个指针,指向下一个物理块的地址,这样,所有的物理块都被链接起来,形成一个链接队列。串联文件的优点是可以解决存储器的碎片问题,提高存储空间利用率。由于串联文件只能按照队列中的链接指针顺序查找,因此搜索效率低,一般只适用于顺序访问,不适用于随机存取。
  • (3)索引文件∶索引文件是另一种对文件存储不连续分配的方法。为每个文件建立一张索引表,索引表中的每一表项指出文件信息所在的逻辑块号和与之对应的物理块号。索引文件既可以满足文件动态增长的要求,又可以方便而迅速地实现随机存取。对一些大的文件,当索引表的大小超过一个物理块时,会发生索引表的分配问题。一般采用多级(间接索引)技术,这时在由索引表指出的物理块中存放的是存放文件信息的物理块地址。这样,如果一个物理块能存储n个地址,则一级间接索引,将使可寻址的文件长度变成n²块,对于更大的文件可以采用二级甚至三级间接索引(例如,UNIX操作系统采用三级索引结构)。

索引文件的优点是既适用于顺序存取,又适用于随机存取。缺点是索引表增加了存储空间的开销。另外,在存取文件时至少需要访问两次磁盘,一次是访问索引表,另一次是根据索引表提供的物理块号访问文件信息。为了提高效率,一种改进的方法是,在对某个文件进行操作之前,预先把索引表调入内存。这样,文件的存取就能直接从在内存的索引表中确定相应的物理块号,从而只需要访问一次磁盘。

<b>1.3.3树形目录结构</b>

文件控制块的集合称为文件目录,文件目录也被组织成文件,常称为目录文件。文件管理的一个重要方面是对文件目录进行组织和管理。文件系统一般采用一级目录结构、二级目录结构和多级目录结构。DOS、UNIX、Windows系统都是采用多级树形目录结构。

在多级树形目录结构中,整个文件系统有一个根,然后在根上分枝,任何一个分枝上都可以再分枝,枝上也可以长出树叶。根和枝称为目录或文件夹。而树叶则是一个个的文件。实践证明,这种结构的文件系统效率比较高。例如,图1-5就是一个树形目录结构,其中方框代表目录,圆形代表文件。

在树形目录结构中,树的根结点为根目录,数据文件作为树叶,其他所有目录均作为树的结点。系统在建立每一个目录时,都会自动为它设定两个目录文件,一个是”.”,代表该目录自己,另一个是”.”,,代表该目录的父目录。对于根目录,”.”和”.”都代表其自己。

从逻辑上讲,用户在登录到系统中之后,每时每刻都处在某个目录之中,此目录被称作工作目录或当前目录,工作目录是可以随时改变的。

对文件进行访问时,需要用到路径的概念。路径是指从树形目录中的某个目录层次到某个文件的一条道路。在树形目录结构中,从根目录到任何数据文件之间,只有一条唯一的通路,从树根开始,把全部目录文件名与数据文件名依次用””/“连接起来,构成该数据文件的路径名,且每个数据文件的路径名是唯一的。这样,可以解决文件重名问题,不同路径下的同名文件不一定是相同的文件。例如,在图1-5中,根目录下的文件f1和/DI/W1目录下的文件f可能是相同的文件,也可能是不相同的文件。

用户在对文件进行访问时,要给出文件所在的路径。路径又分相对路径和绝对路径。绝对路径是指从根目录开始的路径,也称为完全路径∶相对路径是从用户工作目录开始的路径。应该注意到,在树形目录结构中到某一确定文件的绝对路径和相对路径均只有一条。绝对路径是确定不变的,而相对路径则随着用户工作目录的变化而不断变化。

用户要访问一个文件时,可以通过路径名来引用。例如,在图1-5中,如果当前目录是DI,则访问文件2的绝对路径是DI/W2/2,相对路径是W2/2。如果当前目录是W1,则访问文件f2的绝对路径仍然是/DI/W2/2,但相对路径变为/W2/2。

在Windows系统中,有两种格式的文件,分别是FAT32(FAT16)文件和NTFS文件。NTFS在使用中产生的磁盘碎片要比 FAT32少,安全性也更高,而且支持单个文件的容量更大,超过了4GB,特别适合现在的大容量存储。NTFS可以支持的分区(如果采用动态磁盘则称为卷)大小可以达到2TB,而Windows 2000中的FAT32支持分区的大小最大为32GB。

<b>1.3.4 存储空间管理</b>

由于文件存储设备是分成许多大小相同的物理块,并以块为单位交换信息,因此,文件存储设备的管理,实质上是对空闲块的组织和管理问题,它包括空闲块的组织、空闲块的分配与空闲块的回收等问题。

<b>1.空闲表法</b>

空闲表法属于连续分配,系统为外存上的所有空闲区建立一张空闲表,每个空闲区对应一个空闲表项,包括序号、第一空闲盘块号和空闲盘块数。

<b>2.空闲链表法</b>

将所有空闲盘区,拉成一条空闲链,根据构成链所用的基本元素的不同,可把链表分成两种形式∶

  • (1)空闲盘块链。将磁盘上所有空闲区空间,以盘块为单位拉成一条链,当用户因创建文件而请求分配存储空间时,系统从链首开始,依次摘下适当数目的空闲盘块链给用户。当用户因删除文件而释放存储空间时,系统将回收的盘块依次插入空闲盘块链的末尾。空闲盘块链分配和回收一个盘块的过程非常简单,但在为一个文件分配盘块时,可能要重复多次操作。
  • (2)空闲盘区链。将磁盘上所有空闲盘区拉成一条链,在每个盘区上包含若干用于指示下一个空闲盘区的指针,指明盘区大小的信息。分配盘块时,通常采用首次适应算法(显式链接法)。在回收时,要将回收区与空闲盘区相合并。
<b>3.位图法</b>

位图(bitmap)用二进制位表示磁盘中的一个盘块的使用情况,0表示空闲,1表示已分配。磁盘上的所有盘块都与一个二进制位相对应,由所有的二进制位构成的集合,称为位图。位图法的优点是很容易找到一个或一组相邻的空闲盘块。位图小,可以把它保存在内存中,从而节省了磁盘的启动操作。

<b>4.成组链接法</b>

成组链接法将空闲表和空闲链表法结合形成的一种空闲盘块管理方法,适用于大型文件系统。

<b>1.4 存储管理</b>

对于本知识点,主要考查虚拟存储器(虚存),特别是页式存储管理。所谓虚拟存储技术,即在内存中保留一部分程序或数据,在外存中放置整个地址空间的副本。程序运行过程中可以随机访问内存中的数据或程序,但需要的程序或数据不在内存时,就将内存中部分内容根据情况写回外存,然后从外存调入所需程序或数据,实现作业内部的局部转换,从而允许程序的地址空间大于实际分配的存储区域。它在内存和外存之间建立了层次关系,使得程序能够像访问内存一样访问外存,主要用于解决内存的容量问题。其逻辑容量由内存和外存容量之和以及CPU可寻址的范围来决定,其运行速度接近于内存速度,成本也不高。可见,虚拟存储技术是一种性能非常优越的存储器管理技术,故被广泛地应用于大、中、小型及微型机中。

<b>1.4.1 地址变换</b>

由进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器,虚拟存储器允许用户用比内存容量大得多的地址空间来编程,以运行比内存实际容量大得多的程序。用户编程所用的地址称为逻辑地址(虚地址),而实际的内存地址则称为物理地址(实地址)。每次访问内存时都要进行逻辑地址到物理地址的转换,这种转换是由硬件完成的,而内存和外存间的信息动态调度是硬件和操作系统两者配合完成的。

  • (1)静态重定位∶静态重定位是在虚空间程序执行之前由装配程序完成地址影射工作。静态重定位的优点是不需要硬件的支持。缺点是无法实现虚拟存储器,必须占用连续的内存空间,且难以做到程序和数据的共享。
  • (2)动态重定位∶动态重定位是在程序执行过程中,在CPU访问内存之前,将要访问的程序或数据地址转换为内存地址。动态重定位依靠硬件地址变换机构完成,其优点主要有∶可以对内存进行非连续分配,提供了虚拟存储器的基础,有利于程序段的共享。

<b>1.4.2 存储组织</b>

虚拟存储器可以分为单一连续分区、固定分区、可变分区、可重定位分区、页式、段式、段页式7种。

  • (1)单一连续分区。把所有用户区都分配给唯一的用户作业,当作业被调度时,进程全部进入内存,一旦完成,所有内存恢复空闲,因此,它不支持多道程序设计。
  • (2)固定分区。这是支持多道程序设计的最简单的存储管理方法,它把内存划分成若干个固定的和大小不同的分区,每个分区能够装入一个作业,分区的大小是固定的,算法简单,但是容易生成较多的存储器碎片。
  • (3)可变分区。引入可变分区后虽然内存分配更灵活,也提高了内存利用率,但是由于系统在不断地分配和回收中,必定会出现一些不连续的小的空闲区,尽管这些小的空闲区的总和超过某一个作业要求的空间,但是由于不连续而无法分配,产生了碎片。解决碎片的方法是拼接(紧凑),即向一个方向(如向低地址端)移动已分配的作业,使那些零散的小空闲区在另一方向连成一片。分区的拼接技术,一方面是要求能够对作业进行重定位,另一方面系统在拼接时要耗费较多的时间。
  • (4)可重定位分区。这是克服固定分区碎片问题的一种存储分配方法,它能够把相邻的空闲存储空间合并成一个完整的空区,还能够整理存储器内各个作业的存储位置,以达到消除存储碎片和紧缩存储空间的目的。紧缩工作需要花费大量的时间和系统资源。
  • (5)页式。页式存储组织的基本原理是将各进程的虚拟空间划分为若干个长度相等的页,把内存空间以与页相等的大小划分为大小相等的片或页面,采用请求调页或预调页技术实现内外存的统一管理。页式存储组织的主要优点是利用率高,产生的内存碎片小,内存空间分配及管理简单。主要缺点是要有相应的硬件支持,增加了系统开销;请求调页的算法如选择不当,有可能产生抖动现象。
  • (6)段式。一个作业是由若干个具有逻辑意义的段(如主程序、子程序、数据段等)组成。段式存储管理中,允许程序(作业)占据内存中若干分离的分区。分段系统中的虚地址是一个有序对(段号,段内位移)。系统为每一个作业建立一个段表,其内容包括段号与内存起始地址的对应关系、段长和状态等。状态指出这个段是否已调入内存,若已调入内存,则指出这个段的起始地址位置,状态同时也指出这个段的访问权限。如果该段尚未调入内存,则产生缺段中断,以便装入所需要的段。段式存储管理的主要优点是便于多道程序共享内存,便于对存储器的保护,各段程序修改互不影响。其缺点是内存利用率低,内存碎片浪费大。
  • (7)段页式。这是分段式和分页式结合的存储管理方法,充分利用了分段管理和分页管理的优点。作业按逻辑结构分段,段内分页,内存分块。作业只需将部分页装入即可运行,所以支持虚拟存储,可实现动态连接和装配。

现在,最常见的虚存组织有分段技术、分页技术、段页式技术3种。下面把这3种存储组织的特点列于表1-3。

表1-3 常见的虚存组织

项目段式管理页式管理段页式管理
划分方式段(不定长) 每个进程一张段表页(定长) 每个进程一张页表先将内存分为等长页,每个作业一张段表(通常有一个基号指向它),每段对应一组页表
虚地址(s,d),即(段号,段内偏移)(p,d),即(页号,页内偏移(s,p,d)即(段号,段内页号,页内偏移)
虚实转换段表内找出起始地址,然后加段内偏移页表内找出起始地址,然后加页内偏移先在段表中找到贝表的起始地址,然后在页表中找到起始地址,最后加页内偏移
主要优点简化了任意增长和收缩的数据段管理,利于进程间共享过程和数据消除了页外碎片结合了段与页的优点便于控制存取访问
主要缺点段外碎片降低了利用率存在页内碎片提高复杂度,增加硬件存在页内碎片

说明∶段内偏移也称为段内地址,页内偏移也称为页内地址。

例如∶某页式存储系统的地址变换过程如图1-6所示。假定页面的大小为8K,图1-6中所示的十进制逻辑地址 9612经过地址变换后,形成的物理地址a应为十进制多少呢?

因为8K=2的13次方,所以页内地址有13位。逻辑地址9612转换成二进制,得到1001011000 1100,这里的低13位为页内偏移量,最高一位则为页号,所以逻辑地址9612的页号为1,根据图1-6的对照表,即物理块号为3(二进制形式为11)。把物理块号和页内偏移地址拼合得到110010110001100,再转换为十进制,得到25996。

希赛教育专家提示∶在现行的虚存组织方面,最常见的就是段页式管理。在进行虚实地址转换时,可以采用的公式如下∶

(((x)+s)+p)×2"+d

其中x为基号,s为段号,p为段内页号,d为页内偏移,n的值为d的总位数,(x)表示x里的内容。

<b>1.4.3 存储管理</b>

在虚拟存储器的管理中,涉及载入(调入)、放置(放入分区)和置换(swping)等问题。

  • (1)调入策略∶即何时将一页或一段从外存中调入内存,通常有两种策略,一种是请求调入法,即需要使用时才调入;另一种是先行调入法,即将预计要使用的页/段先行调入内存。
  • (2)放置策略∶也就是调入后,放在内存的什么位置,这与内存管理基本上是一致的。
  • (3)置换策略∶由于实际内存是小于虚存的,因此可能会发生内存中已满,但需要使用的页不在内存中这一情况(称为缺页中断)。这时就需要进行置换,即将一些内存中的页淘汰到外存,腾出空间给要使用的页,这个过程也称为Swapping。
<b>1.置换算法</b>

常见的置换算法如下∶

(1)最优(Optimized,OPT)算法∶选择淘汰不再使用或将来才使用的页,这是理想的算法,但难以实现,常用于淘汰算法的比较。

(2)随机(Rand)算法∶随机地选择淘汰的页,开销小,但可能选中立即就要访问的页。

(3)先进先出(First In and First Out,FIFO)算法∶选择淘汰在内存驻留时间最长的页,似乎合理,但可能淘汰立即要使用的页。另外,使用FIFO算法时,在未给予进程分配足够的页面时,有时会出现给予进程的页面数越多,缺页次数反而增加的异常现象,这称为 Belady现象。例如,若某个进程访问页面的顺序(称页面访问序列)是432143543215,当进程拥有3个主存页面时,发生缺页率比拥有4个主存页面时要小。

(4)最近最少使用(Least Recently Used,LRU)算法∶选择淘汰离当前点时刻最近的一段内使用得最少的页。例如,若某个进程拥有3个主存页面,已访问页面的顺序是4314,现在如果要访问第2页,则需要淘汰第3页,因为第1、4页刚刚使用了。这个算法的主要出发点是,如果某页被访问了,则它可能马上就要被访问。OPT 算法和 LRU 算法都不会发生 Bclady异常现象。

<b>2. 局部性原理</b>

存储管理策略的基础是局部性原理,即进程往往会不均匀地高度局部化地访问内存。局部性分为时间局部性和空间局部性。时间局部性是指最近访问存储位置,很可能不久的将来还要访问∶空间局部性是指存储访问有成组的倾向∶当访问了某个位置后,很可能也要访问其附近的位置。

根据局部性原理的特征性,Denning阐述了程序性能的工作集理论。工作集是进程频繁访问的页面的集合。工作集理论指出,为使进程有效地运行,它的页面工作集应驻留内存中。否则,由于进程频繁地从外存请求页面,而出现称为”颠簸”(抖动)的过度的页面调度活动。此时,处理页面调度的时间超过了程序的执行时间。显然,此时CPU 的有效利用率会急速下降。

通常用两种等价的方法确定进程的工作集,一种是将工作集确定为在定长的页面访问序列(工作集窗口)中的页面集合,另一种是将工作集确定为在定长时间间隔中涉及页面的集合。工作集的大小依赖于工作集窗口的大小,在进程执行时,工作集会发生变化。有时,当进程进入另一个完全不同的执行阶段时,工作集会出现显著的变化。不过在一个进程的执行过程中,工作集的大小处于稳定状态的时间基本上占绝大多数。

另一种控制颠簸的技术是控制缺页率。操作系统规定缺页率的上下限,当一个进程的缺页率高于上限时,表明该进程需要更大的内存空间,则分配较多的内存页面给它,当进程的缺页率低于下限时,表明该进程占用的内存空间过大,可以适当地收回若干内存页面。

<b>1.5 作业管理</b>

操作系统中用来控制作业的进入、执行和撤销的一组程序称为作业管理程序,这些控制功能也能通过把作业细化,通过进程的执行来实现。

在作业管理中,系统为每一个作业建立一个作业控制块(Job Control Block,JCB)。系统通过JCB感知作业的存在。JCB包括的主要内容有作业名、作业状态、资源要求、作业控制方式、作业类型以及作业优先权等。

<b>1.5.1 作业的状态</b>

一个作业从交给计算机系统到执行结束退出系统,一般都要经历提交、后备、执行和完成四个状态。其状态转换如图1-7所示。

(1)提交状态。作业由输入设备进入外存储器(也称输入井)的过程称为提交状态。处于提交状态的作业,其信息正在进入系统。

(2)后备状态。当作业的全部信息进入外存后,系统就为该作业建立一个作业控制块。

(3)执行状态。一个后备作业被作业调度程序选中分配了必要的资源并进入了内存,作业调度程序同时为其建立了相应的进程后,该作业就由后备状态变成了执行状态。

(4)完成状态。当作业正常运行结束,它所占用的资源尚未全部被系统回收时的状态为完成状态。

<b>1.5.2 作业调度</b>

处理器调度通常分为三级调度,即高级调度、中级调度和低级调度。

1)高级调度。高级调度也称为作业调度。高级调度的主要功能是在批处理作业的后备作业队列中选择一个或者一组作业,为它们建立进程,分配必要的资源,使它们能够运行起来。

2)中级调度。中级调度也称为交换调度,中级调度决定进程在内存、外存之间的调入、调出。其主要功能是在内存资源不足时将某些处于等待状态或就绪状态的进程调出内存,腾出空间后,再将外存上的就绪进程调入内存。

3)低级调度。低级调度也称为进程调度,低级调度的主要功能是确定处理器在就绪进程间的分配。

作业调度主要完成从后备状态到执行状态的转变,以及从执行状态到完成状态的转变。作业调度算法有∶

(1)先来先服务(First Come and First Served,FCFS)。按作业到达的先后次序调度,它不利于短作业。

(2)短作业优先(Short Job First,SJF)。按作业的估计运行时间调度,估计运行时间短的作业优先调度。它不利于长作业,可能会使一个估计运行时间长的作业迟迟得不到服务。

(3)响应比高者优先(Highest Response ratio Next,HRN)。对FCFS方式和SJF方式的一种综合平衡。FCFS 方式只考虑每个作业的等待时间而未考虑执行时间的长短,而SJF方式只考虑执行时间而未考虑等待时间的长短。因此,这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短,从中选出响应比最高的作业投入执行。响应比R的定义如下∶

R=(W+T/T=1+W/T

其中T为该作业估计需要的执行时间,W为作业在后备状态队列中的等待时间。每当要进行作业调度时,系统计算每个作业的响应比,选择其中R最大者投入执行。这样,即使是长作业,随着它等待时间的增加,W/T也就随着增加,也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行,在同一时间内处理的作业数显然要少于SJF 法,从而采用HRN方式时其吞吐量将小于采用SJF 法时的吞吐量。另外,由于每次调度前要计算响应比,系统开销也要相应增加。

(4)优先级调度。根据作业的优先级别,优先级高者先调度。

<b>1.6 设备管理</b>

在计算机系统中,除了处理器和内存之外,其他的大部分硬设备称为外部设备。它包括输入/输出设备,外存设备及终端设备等。为了完成上述主要任务,设备管理程序一般要提供下述功能∶

(1)提供和进程管理系统的接口。当进程要求设备资源时,该接口将进程要求转达给设备管理程序。

(2)进行设备分配。按照设备类型和相应的分配算法把设备和其他有关的硬件分配给请求该设备的进程,并把未分配到所请求设备或其他有关硬件的进程放入等待队列。

(3)实现设备和设备、设备和CPU 等之间的并行操作。

(4)进行缓冲区管理。主要减少外部设备和内存与CPU之间的数据速度不匹配的问题,系统中一般设有缓冲区(器)来暂放数据。设备管理程序负责进行缓冲区分配、释放及有关的管理工作。

<b>1.6.1 数据传输控制方式</b>

在计算机中,输入/输出(Input/Output,IO)系统可以有5种不同的工作方式,分别是程序控制方式、程序中断方式、DMA(Direct Memory Access,直接内存存取)工作方式、通道方式、输入/输出处理机。

(1)程序控制方式。CPU直接利用IVO指令编程,实现数据的输入输出。CPU发出I/O命令,命令中包含了外设的地址信息和所要执行的操作,相应的IO系统执行该命令并设置状态寄存器;CPU不停地(定期地)查询IO系统以确定该操作是否完成。由程序主动查询外设,完成主机与外设间的数据传送,方法简单,硬件开销小。

(2)程序中断方式。CPU利用中断方式完成数据的输入/输出,当IO系统与外设交换数据时,CPU无须等待,也不必去查询I/O的状态,当I/O系统完成了数据传输后则以中断信号通知CPU。CPU然后保存正在执行程序的现场,转入IO中断服务程序完成与I/O系统的数据交换。然后返回原主程序继续执行。与程序控制方式相比,中断方式因为CPU无需等待而提高了效率。在系统中具有多个中断源的情况下,常用的处理方法有∶多中断信号线法、中断软件查询法、雏菊链法、总线仲裁法和中断向量表法。

(3)DMA方式。使用DMA控制器(Direct Memory Access Controler,DMAC)来控制和管理数据传输。DMAC和CPU共享系统总线,并且具有独立访问存储器的能力。在进行DMA时,CPU放弃对系统总线的控制而由DMAC控制总线;由DMAC提供存储器地址及必需的读写控制信号,实现外设与存储器之间的数据交换。DMAC有3种获取总线的方式∶暂停方式、周期窃取方式和共享方式。

(4)通道方式。通道是一种通过执行通道程序管理I/O操作的控制器,它使主机与I/O 操作之间达到更高的并行程度。在具有通道处理机的系统中,当用户进程请求启动外设时,由操作系统根据 I/O 要求构造通道程序和通道状态字,将通道程序保存在内存中,并将通道程序的首地址放到通道地址字中,然后执行启动 IO指令。按照所采取的传送方式,可将通道分为字节多路通道、选择通道和数组多路通道3种。

(5)输入输出处理机。输入输出处理机也称为外围处理机,它是一个专用处理机,也可以是一个通用的处理机,具有丰富的指令系统和完善的中断系统。专用于大型、高效的计算机系统处理外围设备的输入输出,并利用共享存储器或其他共享手段与主机交换信息。从而使大型、高效的计算机系统更加高效地工作。与通道相比,输入输出处理机具有比较丰富的指令系统,结构接近于一般的处理机,有自己的局部存储器。

<b>1.6.2 磁盘调度算法</b>

访问磁盘的时间由3部分构成,它们是寻道(查找数据所在的磁道)时间、等待(旋转等待扇区)时间和数据传输时间,其中寻道时间(查找时间)是决定因素。

(1)FCFS 算法∶有些文献称为FIFO 算法。FCFS是一种最简单的磁盘调度算法,按先来先服务的次序,未作优化。这种算法的优点是公平、简单,且每个进程的请求都能依次得到处理,不会出现某一进程的请求长期得不到满足的情况。此算法未对寻道进行优化,致使平均寻道时间可能较长。

(2)SSTF(Shortest Seck Time First,最短寻道时间优先)算法∶选择这样的进程,其要求访问的磁道距当前磁头所在的磁道距离最近,以使每次寻道的时间最短。FCFS 会引起读写头在盘面上的大范围移动,SSTF 查找距离磁头最短(也就是查找时间最短)的请求作为下一次服务的对象。SSTF 查找模式有高度局部化的倾向,会推迟一些请求的服务,甚至引起无限拖延(这种现象称为”饥饿”)。

(3)SCAN(电梯)算法∶不仅考虑到欲访问的磁道与当前磁道的距离,而且优先考虑的是磁头的当前移动方向,是在磁头前进方向上的最短查找时间优先算法,它排除了磁头在盘面局部位置上的往复移动。SCAN算法在很大程度上消除了SSTF算法的不公平性,但仍有利于对中间磁道的请求。SCAN算法的缺陷是当磁头刚由里向外移动过某一磁道时,恰有一进程请求访问此磁道,这时进程必须等待,待磁头由里向外,然后再从外向里扫描完所有要访问的磁道后,才处理该进程的请求,致使该进程的请求被严重地推迟。

(4)N-SCAN(N步SCAN)算法∶这是对SCAN算法的改良,磁头的移动与SCAN 算法是一样的,不同的是扫描期间只对那些在扫描开始前已等待服务的请求提供服务。在服务期间,新到达的请求即使在磁头前进方向上也得不到服务,直到下一个新扫描周期开始。N-SCAN算法的实质是把FCFS和SCAN的优点结合起来,以便取得较好的性能。如果新到达的请求按优化次序排列,则下一个扫描周期必然花费最少的磁头移动时间。

(5)C-SCAN(循环扫描)算法∶这是对SCAN算法的另一种改良,是单向服务的N步SCAN算法,C-SCAN算法规定磁头单向移动。C-SCAN算法彻底消除了对两端磁道请求的不公平。

<b>1.6.3 虚设备与SPOOLing技术</b>

SPOOLing(Simultaneous Peripheral Operation On Line)的意思是外部设备同时联机操作,又称为假脱机输入输出操作或排队转储技术,采用一组程序或进程模拟一台输入输出处理器。它在输入和输出之间增加了”输入井”和”输出井”的排队转储环节,SPOOLing系统的组成如图1-8所示。

从图1-8可以看出,SPOOLing系统主要包括以下3个部分∶

(1)输入井和输出井∶这是在磁盘上开辟出来的两个存储区域。输入井模拟脱机输入时的磁盘,用于存放I/O设备输入的数据;输出井模拟脱机输出时的磁盘,用于存放用户程序的输出数据。因此,SPOOLing系统必须有高速、大容量、随机存取的外存的支持。

(2)输入缓冲区和输出缓冲区∶这是在内存中开辟的两个缓冲区。输入缓冲区用于暂存有输入设备送来的数据,以后在传送到输出井。输出缓冲区用于暂存从输出井送来的数据,以后再传送到输出设备。

(3)输入进程和输出进程∶输入进程模拟脱机输入时的外围控制机,将用户要求的数据有输入设备到输入缓冲区,再送到输入井。当CPU需要输入设备时,直接从输入井读入内存。输出进程模拟脱机输出时的外围控制机,把用户要求输入的数据,先从内存送到输出井,待输出设备空闲时,再将输出井中的数据,经过输出缓冲区送到输出设备上。

SPOOLing技术的主要特点如下∶

(1)提高了I/O速度。从对低速I/O设备进行的I/O操作变为对输入井或输出井的操作,如同脱机操作一样,提高了I/O速度,缓和了CPU与低速IO设备速度不匹配的矛盾。

(2)设备并没有分配给任何进程。在输入井或输出井中,分配给进程的是一存储区和建立一张 I/O 请求表。

(3)实现了虚拟设备功能。多个进程同时使用一独享设备,而对每一进程而言,都认为自己独占这一设备,不过,该设备是逻辑上的设备。采用SPOOLing技术,可以将低速的独占设备改造成一种可共享的设备,而且一台物理设备可以对应若干台虚拟的同类设备。

<b>1.7 网络操作系统</b>

网络操作系统是指能使网络上个计算机方便而有效的共享网络资源,为用户提供所需的各种服务的操作系统软件。

<b>1.7.1 网络操作系统概述</b>

如果网络操作系统相等地分布在网络上的所有结点,则称之为对等式网络操作系统;如果网络操作系统的主要部分驻留在中心结点,则称为集中式网络操作系统。集中式网络操作系统下的中心结点称为服务器,使用由中心结点所管理资源的应用称为客户。因此,集中式网络操作系统下的运行机制是C/S(Client/Server,客户/服务器)架构。

网络操作系统除了具备单机操作系统所需的功能外,还应具备下列功能∶

(1)提供高效可靠的网络通信能力。

(2)提供多项网络服务功能,例如,远程管理、文件传输、电子邮件、远程打印等。网络操作系统一般具有以下特征∶

  • (1)硬件独立。网络操作系统应当独立于具体的硬件平台,即系统应该可以运行于各种硬件平台之上。为此,Microsoft提出了HAL(Hardware Abstraction Layer,硬件抽象层)的概念。HAL与具体的硬件平台无关,一旦改变具体的硬件平台,只要改变其HAL,系统就可以作平稳转换。
  • (2)网络特性。应当管理计算机资源并提供良好的用户界面。
  • (3)可移植性和可集成性。
  • (4)多用户、多任务。在多进程系统中,为了避免两个进程并行处理所带来的问题,可以采用多线程的处理方式。支持多处理机技术是对现代网络操作系统的基本要求。

<b>1.7.2 网络操作系统的组成</b>

网络操作系统由网络驱动程序、子网协议和应用层协议等3个方面组成。网络操作系统通过网络驱动程序与网络硬件通信,因此它是作为网卡和子网协议间的联系体来工作的。子网协议是经过网络发送应用和系统管理信息所必需的通信协议。应用层协议则与子网协议进行通信,并实现网络操作系统对网络用户的服务。

(1)网络驱动程序。网络驱动程序涉及 OS/RM(Open System Interconnection Reference Model,开放系统互连参考模型)的第2层(数据链路层)和第3层(网络层),是网卡和高层协议间的接口。网络驱动程序把网卡如何对来自和发往高层的包所使用的方法进行了屏蔽,使高层不必了解收发操作的复杂性,而网络驱动程序本身则必须对网卡的操作有详细的了解。由于对标准的具体实现不同,网络驱动程序也就不同。正因为这样,网络集成商对所使用的网卡必须选择配对的驱动程序,并将所用的网络驱动程序同网络操作系统集成到一起。

(2)子网协议。子网协议涉及OSI/RM的第3层、第4层(传输层)和第5层(会话层)。第3层建立在第2层提供的点到点连接上,主要任务是如何对通信量进行路由选择,提供拥塞和流量控制,提供统一的网络寻址方法,以便令牌环和以太网络能理解。第4层可对第3层提供的服务进行提高,能确保可靠的数据交付。第5层提供有序的会话服务,如在会话上可提供会话控制,权标管理和活动管理。

(3)应用层协议。应用层协议最重要的是NCP(Netware Core Proeocol)。NCP作为应用层的协议,提供了下述主要功能∶在不同方式下打开文件,关闭打开的文件,从打开的文件读取数据块,将数据块写入打开的文件,获取目录项表,处理服务器数据库,提供高级连接服务,提供同步操作。

<b>1.8 例题分析</b>

在对操作系统知识的考查中,主要考查操作系统的基本原理。为了帮助考生了解操作系统试题的题型和难度,本节分析5道典型的试题。

<b>例题1</b>

计算机系统中硬件层之上的软件通常按照三层来划分,如图1-9所示,图中①②③分别表示__

  • A.操作系统、应用软件和其他系统软件
  • B.操作系统、其他系统软件和应用软件
  • C. 其他系统软件、操作系统和应用软件
  • D.应用软件、其他系统软件和操作系统

<b>例题1分析</b>

操作系统的目的是为了填补人与机器之间的鸿沟,即建立用户与计算机之间的接口,而为裸机配置的一种系统软件,如图1-10所示。

从图1-10可以看出,操作系统是裸机上的第一层软件,是对硬件系统功能的首次扩充。它在计算机系统中占据重要而特殊的地位,其他系统软件属于第二层,如编辑程序、汇编程序、编译程序和数据库管理系统等系统软件(这些软件工作于操作系统之上,可服务于应用软件,所以有别于应用软件);大量的应用软件属于第三层,例如希赛教育网上辅导平台,常见的一系列MIS系统等。其他系统软件和应用软件都是建立在操作系统基础之上的,并得到它的支持和取得它的服务。从用户角度看,当计算机配置了操作系统后,用户不再直接使用计算机系统硬件,而是利用操作系统所提供的命令和服务去操纵计算机,操作系统已成为现代计算机系统中必不可少的最重要的系统软件,因此把操作系统看作是用户与计算机之间的接口。

<b>例题 1答案</b>

B

<b>例题2</b>

进程P1、P2、P3、P4和P5的前趋图如图1-11所示。

若用PV操作控制进程P1~P5并发执行的过程,则需要设置5个信号量S1、S2、S3、S4和S5,进程间同步所使用的信号量标注在图1-11中的边上,且信号量S1~S5 的初值都等于零,初始状态下进程PI开始执行。图1-12中a、b和c处应分别填写(1);d和e处应分别填写(2),f和g 处应分别填写(3)。

(1)

A.v(SI)V(S2)、P(SI)和 v(S3)V(S4)

B.PISI)V(S2)、P(SI1)和P(S2)V(SI)

C. V(SI)vS2)、P(S1)和P(S3)P(S4)

D.P(S1)P(S2)、V(S1)和P(S3)V(S2)

(2)

A.P(SI)和V(S5) B.V(S1)和P(S5)

C.P(S2)和V(S5) D.V(S2)和P(S5)

(3)

A.P(S3)和V(S4)V(S5) B.P(S3)和P(S4)P(S5)

C. V(S3)和V(S4)V(S5)D.V(S3)和P(S4)P(S5)

<B>例题2分析</B>

本题考查操作系统中的前趋图和PV操作。

从题目的前趋图,可以得知以下约束关系∶

①PI执行完毕,P2与P3才能开始。

②P2执行完毕,P4才能开始。

③P2与P3都执行完,P5才能开始。

分析清楚这种制约关系,解题也就容易了。

①从”PI执行完毕,P2与P3才能开始”可以得知∶P2与P3中的b与d位置,分别应填P(S1)和P(S2),以确保在P1执行完毕以前,P2与P3不能执行。当然当P1执行完毕时,应该要对此解锁,所以P1中的a位置应填V(S1)与V(S2)。

②从”P2执行完毕,P4才能开始”可以得知∶P4的f位置,应填P(S3),而P2 的结束位置 c应有V(S3)。

③从”P2与P3都执行完,P5才能开始”可以得知∶P5的g位置,应填P(S4)与P(S5),而对应的P2的结束位置c应有V(S4),结合前面的结论可知,c应填V(S3)与V(S4)。而e应填V(S5)。

例题2答案

(1)A (2) C (3)B

<b>例题3</b>

采用微内核结构的操作系统提高了系统的灵活性和可扩展性,_

A.并增强了系统的可靠性和可移植性,可运行于分布式系统中

B.并增强了系统的可靠性和可移植性,但不适用于分布式系统

C.但降低了系统的可靠性和可移植性,可运行于分布式系统中

D.但降低了系统的可靠性和可移植性,不适用于分布式系统

<b>例题3分析</b>

微内核操作系统结构是20世纪80年代后期发展起来的,其基本思想是将操作系统中最基本的部分放入内核中,而把操作系统的绝大部分功能都放在微内核外面的一组服务器中实现。这样使得操作系统内核变得非常小,自然提高了系统的可扩展性、增强了系统的可靠性和可移植性,同时微内核操作系统提供了对分布式系统的支持,融入了面向对象技术。虽然微内操作系统具有诸多优点,但它非常完美无缺,在运行效率方面它就不如以前传统的操作系统。

从上述特点来看,本题应选A。

<b>例题3答案</b>

A

<b>例题 4</b>

某磁盘盘组共有10个盘面,每个盘面上有100个磁道,每个磁道有32个扇区,假定物理块的大小为2个扇区,分配以物理块为单位。若使用位图管理磁盘空间,则位图需要占用(1)字节空间。若采用空白文件管理磁盘空间,且空白文件目录的每个表项占用5个字节,则当空白文件数目大于(2)时,空白文件目录占用的字节数大于位图占用的字节数。

(1)A.32000 B.3200 C.2000 D.1600

(2)A.400 B.360 C.320 D.160

<b>例题4分析</b>

已知磁盘盘组共有10个盘面,每个盘面上有100个磁道,每个磁道有32个扇区,则一共有10×100×32=32000个扇区。试题又假定物理块的大小为2个扇区,分配以物理块为单位,即一共有16000个物理块。因此,位图所占的空间为16000/8=2000字节。

若采用空白文件管理磁盘空间,且空白文件目录的每个表项占用5个字节,2000/5=400,因此,则当空白文件数目大于400时,空白文件目录占用的字节数大于位图占用的字节数。

<b>例题 4答案</b>

(1)C (2)A

<b>例题5</b>

若操作系统文件管理程序正在将修改后的【】文件写回磁盘时系统发生崩溃,对系统的影响相对较大。

A.用户数据 B.用户程序 C.系统目录 D.空困块管理

<b>例题5分析</b>

本题考查操作系统基本概念。操作系统为了实现”按名存取”,必须为每个文件设置用于描述和控制文件的数据结构,专门用于文件的检索,因此至少要包括文件名和存放文件的物理地址,该数据结构称为文件控制块(File Control Block,FCB),文件控制块的有序集合称为文件目录,或称系统目录文件。若操作系统正在将修改后的系统目录文件写回磁盘时系统发生崩溃,则对系统的影响相对较大。

<b>例题5答案</b>

c

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇