操作系统基本原理

软件设计师需要有扎实的理论知识，而操作系统作为计算机科学最为基本的理论基础和分支领域之一，是软件设计师必须重点掌握的知识。本章将介绍操作系统相关的考点，并辅以练习题，以便考生切实掌握相关内容。
根据考试大纲，本章要求考生掌握以下几个方面的知识点。
（1）操作系统的内核。
（2）操作系统的五大管理功能：进程管理、存储管理、设备管理、文件管理、作业管理。
（3）网络操作系统和嵌入式操作系统基础知识。
（4）操作系统的配置。
从历年的考试情况来看，本章主要考查进程状态转换图、信号量与PV操作、死锁问题、银行家算法、段页式存储、页面置换算法、磁盘调度、树形文件系统。

进程管理

进程管理也称为处理机管理，该部分内容是整个操作系统部分的考查重点，主要知识点有：进程状态转换图、信号量与PV操作、死锁问题、银行家算法。

1．进程状态转换图

进程状态转换图用于展现进程的状态，以及各种状态之间的转换。最为常见的有：三态模型和五态模型，其后又提出了七态模型。在考试中，要求考生掌握五态模型。五态模型是对三态模型的扩展（即五态模型已经包含了三态模型）。标准的五态模型如图2-1所示。

从该图可以看出，五态模型中的五态为：执行状态（运行状态）、活跃就绪状态、活跃阻塞状态、挂起就绪状态、挂起阻塞状态。其中前三种状态组成了三态模型。
执行状态：指进程占有处理机正在CPU上执行的状态。在单CPU系统中，每一时刻只有一个进程处于执行状态。
活跃就绪状态：指进程分配到除处理机以外的必需的资源（已经具备了执行的条件）的状态。进程被创建后处于就绪状态，处于就绪状态的进程可以有多个。
活跃阻塞状态：指进程因等待某个事件的发生而放弃处理机进入等待状态。系统中处于这种状态的进程可以有多个。
挂起就绪状态：指进程被移至磁盘镜像区中，此时进程只缺处理机资源。
挂起阻塞状态：指进程被移至磁盘镜像区中，此时进程除了缺处理机资源，还缺其它资源。

2.信号量与PV操作

在操作系统中，进程之间经常会存在互斥和同步两种关系。为了有效地处理这两种情况，W.Dijkstra在 1965年提出信号量和PV操作。
信号量是一种特殊的变量，表现形式是一个整型S和一个队列。
P操作：也称为down()、wait()操作，使S=S-1，若S<0，进程暂停执行，放入信号量的等待队列。
V操作：也称为up()、signal()操作，使S=S+1，若S≤0，唤醒等待队列中的一个进程。

（1）完成互斥控制

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

由于只允许一个进程进入，因此信号量中整型值的初始应该为1。该值表示可以允许多少个进程进入，当该值<0时，其绝对值就是等待使用的进程数，也就是等待队列中的进程数。而当一个进程从临界区出来时，就会将整型值加1，如果等待队列中还有进程，则调入一个新的进程进入（唤醒）。

（2）完成同步控制

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

因此要确保进程B执行V操作之前，不让进程A的运行超过L1，因此信号量的初值就应该为0。这样，如果进程A先执行到L1，那么执行P操作后，信号量的整型值就会小于1，也就停止执行。直到进程B执行到L2时，将信号量的整型值加1，并唤醒它以继续执行。

在考试中，该知识点出题形式主要是给出一系列操作，让考生在适当位置填充P操作或V操作。

3.死锁问题

死锁是指各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想得到资源而又都得不到资源，各并发进程不能继续向前推进的状态。

产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。
产生死锁有四个必要条件：

（1）互斥条件：即一个资源每次只能被一个进程使用，在操作系统中这是真实存在的情况。
（2）保持和等待条件：有一个进程已获得了一些资源，但因请求其他资源被阻塞时，对已获得的资源保持不放。
（3）不剥夺条件：有些系统资源是不可剥夺的，当某个进程已获得这种资源后，系统不能强行收回，只能由进程使用完时自己释放。
（4）环路等待条件：若干个进程形成环形链，每个都占用对方要申请的下一个资源。

对待死锁的策略主要有：

（1）死锁的预防。不让任一产生死锁的必要条件发生就可以预防死锁。
（2）死锁的避免。这种策略不对用户进程的推进顺序加以限制，在进程申请资源时先判断这次分配安全否，只有安全才实施分配，典型的算法是银行家算法。
（3）死锁的检测。这种策略采用资源请求分配图的化简方法来判断是否发生了不安全状态。资源请求分配图是一种有向图，表示进程与资源之间的关系。死锁的检测是在需要的时刻执行的，当发现系统处于不安全状态时，即执行死锁的解除策略。
（4）死锁的解除。解除死锁的基本方法是剥夺。一种方法是把资源从一些进程处剥夺分给别的进程，被剥夺资源的进程则需回退到请求资源处重新等待执行；另一种方法是终止一个进程，剥夺其全部资源，以后再重新运行被终止的进程。

4.银行家算法

银行家算法是一种经典的死锁避免方法。银行家算法的基本思想是：当某个进程提出申请时，必须判断将资源分配给该进程后，会不会引起死锁。若不会，则进行分配；否则就不分配。这样做能保证在任何时刻至少有一个进程可以得到所需的全部资源而执行结束，并将归还资源加入到系统的剩余资源中，这些资源又至少可以满足一个进程的最大需求，于是保证所有进程都能在有限的时间内得到需求的全部资源。

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

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

练习

试题1
某系统的进程状态转换如图2-2所示，图中1、2、3和4分别表示引起状态转换的不同原因，原因4表示__(1)；一个进程状态转换会引起另一个进程状态转换的是(2)__。
（1）A．就绪进程被调度 B．运行进程执行了P操作
C．发生了阻塞进程等待的事件 D．运行进程的时间片到了
（2）A．1→ 2 B．2→ 1 C．3→ 2 D．2→ 4

试题2
系统中有R类资源m个，现有n个进程互斥使用。若每个进程对R资源的最大需求为w，那么当m、n、w分别取下表中的值时，对于表中的①～⑥种情况，(3)可能会发生死锁。若将这些情况的m分别加上(4)，则系统不会发生死锁。

（3）A．①②⑤ B．③④⑤ C．②④⑤ D．②④⑥
（4）A．1、1和1 B．1、1和2 C．1、1和3 D．1、2和1

试题3
若某企业拥有的总资金数为15，投资4个项目P1、P2、P3、P4，各项目需要的最大资金数分别是6、8、8、10，企业资金情况如图2-4所示。Pl新申请2个资金，P2新申请1个资金，若企业资金管理处为项目P1和P2分配新申请的资金，则P1、P2、P3、P4尚需的资金数分别为__(5)；假设P1已经还清所有投资款，企业资金使用情况如图2-5所示，那么企业的可用资金数为(6)。若在图2-5所示的情况下，企业资金管理处为P2、P3、P4各分配资金数2、2、3，则分配后P2、P3、P4已用资金数分别为(7)__。


（5）A．1、3、6、7，可用资金数为0，故资金周转状态是不安全的
B．2、5、6、7，可用资金数为1，故资金周转状态是不安全的
C．2、4、6、7，可用资金数为2，故资金周转状态是安全的
D．3、3、6、7，可用资金数为2，故资金周转状态是安全的
（6）A．4 B．5 C．6 D．7
（7）A．3、2、3．尚需资金数分别为5、6、7，故资金周转状态是安全的
B．5、4、6，尚需资金数分别为3、4、4，故资金周转状态是安全的
C．3、2、3，尚需资金数分别为5、6、7，故资金周转状态是不安全的
D．5、4、6，尚需资金数分别为3、4、4，故资金周转状态是不安全的

试题4
某企业生产流水线M共有两位生产者，生产者甲不断地将其工序上加工的半成品放入半成品箱，生产者乙从半成品箱取出继续加工。假设半成品箱可存放n件半成品，采用PV操作实现生产者甲和生产者乙的同步可以设置三个信号量S、Sl和S2，其同步模型如图2-6所示。

信号量S是一个互斥信号量，初值为__(8)；Sl、S2的初值分别为(9)__。
（8）A．0 B．1 C．n D．任意正整数
（9）A．n、0 B．0、n C．1、n D．n、1

试题5
进程P1、P2、P3、P4和P5的前趋图如图2-7所示。

若用PV操作控制进程P1～P5并发执行的过程，则需要设置6个信号S1、S2、S3、S4、S5和S6，且信号量S1-S6的初值都等于零。图2-8中a和b处应分别填写__(10)；c和d处应分别填写(11)，e和f处应分别填写(12)__。

（10）A．P（S1）P（S2）和P（S3）P（S4）
B．P（S1）V（S2）和P（S2）V（S1）
C．V（S1）V（S2）和V（S3）V（S4）
D．P（S1）P（S2）和V（S1）V（S2）
（11）A．P（S1）P（S2）和V（S3）V（S4）
B．P（S1）P（S3）和V（S5）V（S6）
C．V（S1）V（S2）和P（S3）P（S4）
D．P（S1）V（S3）和P（S2）V（S4）
（12）A．P（S3）P（S4）和V（S5）V（S6）
B．V（S5）V（S6）和P（S5）P（S6）
C．P（S2）P（S5）和P（S4）P（S6）
D．P（S4）V（S5）和P（S5）V（S6）

答案
试题1分析
本题的配图是一个标准的“进程三态图”，其中1表示就绪进程被调度；2表示运行进程的时间片到了；3表示运行进程执行了P操作，进程进入了阻塞状态；4表示被阻塞进程等待的事件发生了。其中的1与2有着一定的关联，因为当一个正在运行的进程时间片到了以后，该进程将从运行态转换为就绪态，同时，需要调入另外一个处于就绪态的进程，使之转换为运行态。
试题1答案
（1）C （2）B
试题2分析
在本题中，第①种情况的系统资源数为3，而有2个进程互斥使用这3个资源，每个进程需要的资源最大值为2，那么无论怎么分配资源，都不会发生死锁。第②种情况的系统资源数为3，有3个进程互斥使用这3个资源，每个进程需要的资源最大值为2，如果每个进程都分配一个该类资源而又互相等待，这时就有可能产生死锁。第③种情况的系统资源数为5，而有2个进程互斥使用这5个资源，每个进程需要的资源最大值为3，那么无论怎么分配资源，都不会发生死锁。第④种情况的系统资源数为5，有3个进程互斥使用这3个资源，每个进程需要的资源最大值为3，如果有两个进程分配了两个资源，而剩余的一个该类资源分配给了第3个进程，这时就有可能产生死锁。对于第⑤种情况，如果
三个进程都分配了2个资源而互相等待则会产生死锁。
经过上面的分析我们可以知道，②④⑤可能会产生死锁，对于第②种情况，由于每个进程都分配一个该类资源，如果系统再多一个该类资源，系统将不会产生死锁。对于第④种情况，由于有两个进程分配了两个资源，而第3个进程只分配了1个资源，如果系统只增加一个资源的话，那么将增加的这个资源分配给第3个进程，这个时候系统仍然会发生死锁，只有增加两个资源系统才不会死锁。第⑤中情况与第②种情况一样，只需要增加一个资源就不会发生死锁。
试题2答案
（3）C（4）D
试题3分析
从图2-4我们可以看出，P1、P2、P3、P4尚需的资金数分别4、5、6、7，而目前再给P1分配2个资金、给P2分配1个资金，那么P1、P2、P3、P4尚需的资金数分别4-2=2,5-1=4,6,7。如果P1已经还清所有投资款，再结合图2-5，已用资金和为：3+2+3=8，那么剩余的可用资金
为15-8=7。从图2-5不难看出，P2、P3、P4目前已经分别分配了3、2、3个资金，再给他们分别分配2、2、3个资金后，他们的已用资金数应分别为5、4、6，尚需资金数分别为8-5=3，8-4=4，10-6=4。
试题3答案
（5）C（6）D（7）D
试题4分析
本题主要考查PV操作实现同步与互斥。在本题中，题目告诉我们甲乙俩人互斥使用半成品箱这个共有资源，且只有一个半成品箱，那么互斥信号量的初值就应该为1。而从题目给出的同步模型图，我们可以看出，信号量S1是生产者甲的私有信号量，而S2是生产者乙的私有信号量，题目告诉我们半成品箱可存放n件半成品，那么初始状态时，S1的值应该为n，表示生产者甲最多只能生产n个半成品放入半成品箱，就需要生产者乙来协调工作。而S2的值为0，表示开始时半成品箱中没有半成品。
试题4答案
（8）B（9）A
试题5分析
本题主要考查用PV操作控制进程的并发执行。首先我们需要弄清楚前驱图中给出的各进制的执行顺序。从图中我们不难看出进程P1和P2没有前驱，也就是可以首先并发执行，而进程P3的前驱是P1和P2，P4的前驱是P1和P3，P5的前驱是P2和P3。那么怎么理解前驱呢？其实前驱就是指只有在前驱进程完成后，该进程才能开始执行。在本题的前驱图中我们不难看出，有6条路径，分别是P1->P3，P1->P4，P2->P3，P2->P5，P3->P4，P3->P5。而且题目也告诉我们分别有6初值为0个信号量（S1-S6），要我们用PV操作来控制进程P1～P5的并发执行。这里我们就需要清楚P与V这两种操作。
P原语的主要操作是：
（1）信号量（sem）减1；
（2）若相减结果大于等于零，则进程继续执行；
（3）若相减结果小于零，则阻塞一个在该信号量上的进程，然后再返回原进程继续执行或转进程调度。
V原语的主要操作是：
（1）信号量（sem）加1；
（2）若相加结果大于零，则进程继续执行；
（3）若相加结果小于或等于零，则唤醒一阻塞在该信号量上的进程，然后再返回原进程继续执行或转进程调度。
总而言之，进行P操作的主要目的是阻塞某信号量上的进程，而进行V操作的主要目的是唤醒某信号量上的进程。
下面我们具体来求解这个题目。a空处，是在进程P1执行完成以后，那么根据题目的前驱图我们可以知道，这个时候它应该唤醒它的后继进程P3和P4，因此需要执行两个V操作，同样的道路，b空处也需要执行两个V操作，因此可以知道此空答案选C。至于C空处，它是在进程P3执行前进行的处理。根据前驱的意义，我们可以知道执行P3要在P1和P2完成后，因此这个时候，它首先需要判断P1和P2进程是否完成，如果它们完成的话，会分别执行唤醒P3的V操作（换句话说就是会给相应的信号量进行加1操作），那么这个时候我们也可以通过同样的信号量来判断，即对相应的信号量进行减1操作，判断它是否大于0，如果大于等于0，则执行P3。从题目给出的答案来看，这两个信号量应该分别是S1和S3。那么执行完P3后，它也需要唤醒它的后继进程P4和P5，因此需要执行两个V操作，因此D空处应该是两个V操作。综上所述，我们可以知道24题的答案选B。
分析到这里后，答案应该就很明显了，P4和P5进程在执行前，都需要做与P3进程执行前一样的判断，因此都需要进行两个P操作。所以本题答案选C。
其实做这类题也不难，首先需要我们对PV操作要有一个透彻的理解，另外就是能分析出题目执行的逻辑关系。
试题5答案
（10）C（11）B（12）C

---

存储管理

存储管理是操作系统的重要职能之一，在计算机中，存储是分层次的体系结构。层次从高到低包括：寄存器（CPU中）、Cache、内存、外存（硬盘，U盘，光盘等）。在本节，主要论述虚拟存储管理技术中的页式存储、段式存储、段页式存储，以及磁盘的基本工作原理。

1. 页式存储组织

页式存储组织的基本原理是将各进程的虚拟空间划分为若干个长度相等的页，把内存空间以与页相等的大小划分为大小相等的片或页面，采用请求调页或预调页技术实现内外存的统一管理。页式存储组织的主要优点是利用率高，产生的内存碎片小，内存空间分配及管理简单。主要缺点是要有相应的硬件支持，增加了系统开销；请求调页的算法如选择不当，有可能产生“抖动”现象。

2. 段式存储组织

一个作业是由若干个具有逻辑意义的段（如主程序、子程序、数据段等）组成。在分段系统中，允许程序（作业）占据内存中若干分离的分区。分段系统中的虚地址是一个有序对（段号，段内位移）。系统为每一个作业建立一个段表，其内容包括段号与内存起始地址的对应关系、段长和状态等。状态指出这个段是否已调入内存，若已调入内存，则指出这个段的起始地址位置，状态同时也指出这个段的访问权限。如果该段尚未调入内存，则产生缺段中断，以便装入所需要的段。段式存储组织的主要优点有：便于多道程序共享内存，便于对存储器的保护，各段程序修改互不影响。其缺点是内存利用率低，内存碎片浪费大。

3. 段页式存储组织

段页式存储组织是分段式和分页式结合的存储组织方法，这样可充分利用分段管理和分页管理的优点。在段页式管理的存储器中，程序按逻辑单位分成基本独立的段，再把每段分成固定大小的页。内存则等分成与上述页大小相等的页。程序对内存的调入或调出是按页进行的。但它又可按段实现共享和保护。
在多道程序环境中，每道程序都有一张段表和一个作为用户标志的基号。一个逻辑地址中，除了基号x、段号s和页号p外，还有一个页内地址d。每个逻辑地址变换成实地址的过程如下：根据基号找到相应的基址寄存器，由该基址寄存器内容找到该程序对应的段表始地址，再由段号找到该段表中相应行地址，该行地址中的内容为页表起始地址，再由页号找到物理页号的地址（已是内存中的某页）它与页内地址拼接后即得物理地址。可见段页式管理中需要多次查表才能最终获得物理地址。该过程可简单地用一个式子来示意，即

其中，（x）表示基寄存器中地址为x的单元的内容，n为页内地址的位数。段页式管理将段式存储管理和页式存储管理两种方式相结合，互相取长补短，充分发挥了它们的优点。使段页式虚拟存储器管理方案具有空间浪费小、存储共享容易、存储保护容易、能动态连接的特点。但由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内存也有所增加，使得执行速度大大下降。

4. 页面置换算法

由于实际主存是小于虚存的，因此可能会发生内存中已满，但需要使用的页不在主存中这一情况。这时就需要进行置换，即将一些主存中的页淘汰到外存，腾出空间给要使用的页，这个过程也称为Swapping。其工作原理与Cache调入相类似。
最优算法（OPT）：淘汰不用的或最远的将来才用的页。这是一种理想算法，不可能实现，只是用来作为衡量算法效率的参照物。
随机算法（RAND）：随机淘汰。这种算法开销小，但性能不稳定。
先进先出算法（FIFO）：选择最早调入（也是驻留时间最长）的页。
最近最少使用算法（LRU）：选择离当前时刻最近的一段时间内使用得最少的页。

5.局部性原理

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

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

工作集的大小依赖于工作集窗口（进程在定长时间间隔中涉及到的页面的集合）的大小，在进程执行时，工作集会发生变化。有时，当进程进入另一具完全不同的执行阶段时，工作集会出现显著的变化。不过在一个进程的执行过程中，工作集的大小处于稳定状态的时间基本上占绝大多数。

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

6.磁盘工作原理

磁盘是最常见的一种外部存储器，它是由1至多个圆形磁盘组成的，其结构如图所示。

（1）概念

磁道：磁道是一组记录密度不同的同心圆。在一个磁盘中，从外到内，磁盘记录密度不断增加。同时，值得注意的是，0磁道是磁盘最外圈的磁道。
扇区：磁盘上的每个磁道被等分为若干个弧段，这些弧段便是磁盘的扇区。
柱面：一个磁盘中，多个记录面相同磁道组成柱面。如磁盘有9个记录面，则这9个记录面的0磁道可组成一个柱面。
注意：硬盘就是磁盘的一种。硬盘工作时，无论是否在进行数据的读取，其盘片都是不断旋转的状态。

（2）公式

平均数据传输速率 = 每道扇区数 X 扇区容量 X 盘片转数。
存取时间 = 寻道时间 x 等待时间，寻道时间是指磁头移动到磁道所需的时间;等待时间为等待读写的扇区转到磁头下方所用的时间。

（3）数据存取过程

根据硬盘存放数据的规则，在向磁盘记录一个文件时，应将文件尽可能记录在同一柱面上，当一个柱面记录不下时，再记录到相邻柱面上。因此，当一个文件超出一个磁道容量时，剩下的部分应存于其他盘面的同一编号的磁道上，即同一柱面的其他磁道上。为存取磁盘上的一个物理记录，必须给出3个参数：柱面号，磁头号（盘面号），扇区号。磁盘机根据柱面号控制移动臂作径向运动，带动读写头到达所需的柱面；从磁头号可确定哪一个磁头来读写数据，然后便等待访问的信息块旋转到读写头下时进行存取。磁盘机实现这些功能的操作是：查找（将读写头定位到指定柱面并选择指定磁头）、搜索（指定磁头寻找访问的记录块）、读、写和控制等。

**平均存取时间（AverageAccessTime）**是反映磁盘数据操作速度的指标，单位是毫秒（ms）。它包括三个时间段，分别是平均寻道时间（SeekTime），平均定位时间（Setting Time）和转动延迟（RotationalLatency），其中后两个又统称为等待时间。

寻道时间也称为查找时间，为磁头移动到目标磁道所需的时间。对于固定磁头磁盘而言，无需移动磁头，只需选择目标磁道对应的磁头即可。等待时间为等待读写的扇区旋转到磁头下方所用的时间。一般选用磁道旋转一周所用时间的一半作为平均等待时间。寻道时间由磁盘机的性能决定，目前主流硬盘典型的平均寻道时间（AverageSeekTime，AST）一般在4ms左右，而转速则有5400rpm、7200rpm、15000rpm等。在考试当中，这些参数通常是由试题指定。

（4）磁盘调度算法

先来先服务（FCFS）：该算法根据进程请求访问磁盘的先后次序进行调度。其优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。

最短寻道时间优先（SSTF）：该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。

扫描算法（SCAN）：SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。

循环扫描（CSCAN）算法：该算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。

磁盘调度算法参考

试题1
假设一台按字节编址的16位计算机系统，采用虚拟页式存储管理方案，页面的大小为2K，且系统中没有使用快表（或联想存储器）。某用户程序如图2-10（左）所示，该程序的页面变换表如图2-10（右）所示，表中状态位等于1和0分别表示页面在内存或不在内存。

图2-10（左）中MOVEData1，Data2是一个4字节的指令，Data1和Data2表示该指令的两个32位操作数。假设MOVE指令存放在2047地址开始的内存单元中，Data1存放在6143地址开始的内存单元中，Data2存放在10239地址开始的内存单元中，那么执行MOVE指令将产生__(1)次缺页中断，其中：取指令产生(2)次缺页中断，取Data1和Data2操作数分别产生(3)__次缺页中断。
（1）A．3 B．4 C．5 D．6
（2）A．0 B．1 C．2 D．3
（3）A．1、1 B．1、2 C．2、2 D．2、3

试题2
某系统采用请求页式存储管理方案，假设某进程有6个页面，系统给该进程分配了4个存储块，其页面变换表如表2-1所示，表中的状态位等于1/0分别表示页面在内存/不在内存。当该进程访问的页面2不在内存时，应该淘汰表中页号为__(4)的页面。假定页面大小为4K，逻辑地址为十六进制3C18H，该地址经过变换后的页帧号为(5)__。

（4）A．0 B．3 C．4 D．5
（5）A．2 B．5 C．8 D．12

试题3
某磁盘磁头从一个磁道移至另一个磁道需要10ms。文件在磁盘上非连续存放，逻辑上相邻数据块的平均移动距离为10个磁道，每块的旋转延迟时间及传输时间分别为100ms和2ms，则读取一个 100块的文件需要__(6)__ms时间。
（6）A．10200 B．11000 C．11200 D．20200

答案
试题1分析
这个题目从其描述来看，非常复杂，但结合图来看，其实非常简单，从图a我们可以看出，MOVE执行属于页面0和1，而Data1属于页面2和3，Data2属于页面4和5，另外，结合图b可以看出，编号为1、2、3、4、5的页面都不在内存中，如果要取这几个页面的数据，必须先将其置换进内存，因此总共是5次缺页中断，其中取指令产生1次缺页中断，取Data1和Data2操作数分别产生2次缺页中断。
试题1答案
（1）C（2）B（3）C
试题2分析
本题主要考查页式存储管理。
在分页存储管理时，将内存划分为大小相等的页面，每一页物理内存叫页帧，以页为单位对内存进行编号，该编号可作为页数组的索引，又称为页帧号。在淘汰页面时，应选择页帧号最大的进行淘汰，因此当该进程访问的页面2不在内存时，应该淘汰页号为5的页面。
另外，题目高位我们页面大小为4K，即需要12位来表示其存储空间，而逻辑地址3C18H转换为二进制为0011110000011000，其低12位为页内地址，而高4位为页号，即0011,，转换为十进制后结果为3，查表可知，页号为3的页面对应的页帧号为2。
试题2答案
（4）D （5）A
试题3分析
本题主要考查读取磁盘数据的相关知识。
在本题中读取磁盘数据的时间应包括：
（1）找磁道的时间。逻辑上相邻数据块的平均移动距离为10个磁道，那么平均读取一块数据所需要的找磁道时间=1010=100ms。
（2）找块（扇区）的时间，即旋转延迟时间
（3）传输时间按照上面的描述计算，我们可以找到平均读取一块数据需要的时间为：100+100+2=202ms，那么读取100块数据需要的时间为100202=20200ms。
试题3答案
（6）D

设备管理

在计算机系统中，除了处理器和内存之外，其他的大部分硬设备称为外部设备。它包括输入/输出设备，辅存设备及终端设备等。

1．数据传输控制方式

输入输出系统主要有五种方式与主机交换数据：程序控制方式、程序中断方式、DMA方式、通道方式、I/O处理机。

（1）程序控制方式：

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

（2）程序中断方式：

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

（3）DMA方式：

使用DMA控制器（DMAC）来控制和管理数据传输。DMAC和CPU共享系统总线，并且具有独立访问存储器的能力。在进行DMA时，CPU放弃对系统总线的控制而由DMAC控制总线；由DMAC提供存储器地址及必须的读写控制信号，实现外设与存储器之间进行数据交换。
DMAC获取总线方式主要有三种，分别是暂停方式、周期窃取方式和共享方式。

（4）通道：

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

（5）输入输出处理机（IOP）：

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

2．虚设备与SPOOLING技术

SPOOLING（SimultaneousPeripheralOperationOnLine）的意思是外部设备同时联机操作，又称为假脱机输入输出操作，采用一组程序或进程模拟一台I/O处理器。SPOOLING系统的组成如图2-11所示。

该技术利用了专门的外围控制机将低速I/O设备上的数据传送到高速设备上，或者相反。但是当引入多道程序后，完全可以利用其中的一道程序来模拟脱机输入时的外围控制机的功能，把低速的I/O设备上的数据传送到高速磁盘上；再利用另一道程序来模拟脱机输出时的外围控制机的功能，把高速磁盘上的数据传送到低速的I/O设备上。这样便可以在主机的控制下实现脱机输入、输出的功能。此时的外围操作与CPU对数据的处理同时进行，我们将这种在联机情况下实现的同时外围操作称为SPOOLING，或称为假脱机操作。

采用假脱机技术，可以将低速的独占设备改造成一种可共享的设备，而且一台物理设备可以对应若干台虚拟的同类设备。SPOOLING系统必须有高速、大容量并且可随机存取的外存(如磁盘或磁鼓)支持。

---

练习

试题1
在输入输出控制方法中，采用__(1)__可以使得设备与主存间的数据块传送无需CPU干预。
（1）A．程序控制输入输出 B．中断 C．DMA D．总线控制

试题2
在操作系统中，虚拟设备通常采用__(2)__设备来提供虚拟设备。
（2）A．Spooling技术，利用磁带 B．Spooling技术，利用磁盘
C．脱机批处理技术，利用磁盘 D．通道技术，利用磁带

试题3
设备驱动程序是直接与__(3)打交道的软件模块。一般而言，设备驱动程序的任务是接收来自与设备(4)__。
（3）A．硬件 B．办公软件 C．编译程序 D．连接程序
（4）A．有关的上层软件的抽象请求，进行与设备相关的处理
B．无关的上层软件的抽象请求，进行与设备相关的处理
C．有关的上层软件的抽象请求，进行与设备无关的处理
D．无关的上层软件的抽象请求，进行与设备无关的处理

答案
试题1分析
本题主要考查I/O控制的各种方法。其中可以使得设备与主存间的数据块传送不需要CPU干预的是DMA方式。DMA方式正是为了将CPU从输入输出控制中解放出来而产生的。在数据的传送过程中由DMA进行管理。
实现DMA传送的基本操作如下：
（1）外设可通过DMA控制器向CPU发出DMA请求：
（2）CPU响应DMA请求，系统转变为DMA工作方式，并把总线控制权交给DMA控制器；
（3）由DMA控制器发送存储器地址，并决定传送数据块的长度；
（4）执行DMA传送；
（5）DMA操作结束，并把总线控制权交还CPU。
试题1答案
（1）C
试题2分析
Spooling是SimultaneousPeripheralOperationOn-Line（即外部设备联机并行操作）的缩写，它是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。实际上是一种外围设备同时联机操作技术，又称为排队转储技术。
它在输入和输出之间增加了“输入井”和“输出井”的排队转储环节。
Spooling系统主要包括以下3部分：
（1）输入井和输出井：这是在磁盘上开辟出来的两个存储区域。输入井模拟脱机输入时的磁盘，用于收容I/O设备输入的数据。输出井模拟脱机输入时的磁盘，用于收容用户程序的输出数据。
（2）输入缓冲区和输出缓冲区：这是在内存中开辟的两个缓冲区。输入缓冲区用于暂存由输入设备送来的数据，以后再传送到输出井。输出缓冲区用于暂存从输出井送来的数据，以后再传送到输出设备。
（3）输入进程和输出进程：输入进程模拟脱机输入时的外围控制机，将用户要求的数据由输入设备送到输入缓冲区，再送到输入井。当CPU需要输入设备时，直接从输入井读入内存。输出进程模拟脱机输出时的外围控制机，把用户要求输入的数据，先从内存送到输出井，待输出设备空闲时，再将输出井中的数据，经过输出缓冲区送到输出设备上。
从以上的分析可以看出，Spooling技术是利用磁盘提供虚拟设备。
试题2答案
（2）B
试题3分析
设备驱动程序是一种可以使计算机和设备通信的特殊程序，相当于硬件的接口，操作系统只有通过这个接口，才能控制硬件设备的工作，假如某设备的驱动程序未能正确安装，便不能正常工作。正因为这个原因，驱动程序在系统中所占的地位十分重要，一般当操作系统安装完毕后，首要的便是安装硬件设备的驱动程序。
第二问是考查驱动程序的任务：首先其作用是将硬件本身的功能告诉操作系统，接下来的主要功能就是完成硬件设备电子信号与操作系统及软件的高级编程语言之间的互相翻译。当操作系统需要使用某个硬件时，比如：让声卡播放音乐，它会先发送相应指令到声卡驱动程序，声卡驱动程序接收到后，马上将其翻译成声卡才能听懂的电子信号命令，从而让声卡播放音乐。要求播放音乐的上层软件→操作系统→驱动程序→硬件，所以相对于驱动程序来说，上层软件与它是无关的，因为它们之间有操作系统。
试题3答案
（3）A（4）B

---

文件管理

文件管理部分考查主要集中于树型目录结构、位示图以及索引文件结构。

1. 树型目录结构

在计算机的文件系统中，一般采用树型目录结构。在树型目录结构中，树的根结点为根目录，数据文件作为树叶，其他所有目录均作为树的结点。

根目录隐含于一个硬盘的一个分区中，根目录在最顶层。它包含的子目录是一级子目录。每一个一级子目录又可以包含若干二级子目录，…，这样的组织结构就叫做目录树。

当前盘和当前目录是系统默认的操作对象。如果用户没有指明操作对象，系统就将用户命令指向当前盘和当前目录。

路径是指从根目录或者当前目录开始到访问对象（目录或者文件），在目录树中路经过的所有目录的序列。例如“c:\dos\lmouse\mouse”就是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字。

位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，如图2-12所示。当其值为“0”时，表示对应的盘块空闲；为“1”时表示已分配。由所有盘块对应的位构成一个集合，称为位示图。位示图也可描述为一个二维数组map：Varmap:array[1…m,1…n]ofbit;

3. 索引文件

索引文件是一种对文件存储不连续分配的方法。为每个文件建立一张索引表，索引表中的每一表项指出文件信息所在的逻辑块号和与之对应的物理块号。

索引文件既可以满足文件动态增长的要求，又可以方便而迅速地实现随机存取。对一些大的文件，当索引表的大小超过一个物理块时，会发生索引表的分配问题。一般采用多级（间接索引）技术，这时在由索引表指出的物理块中存放的不是文件存放处而是存放文件信息的物理块地址。这样，如果一个物理块能存储n个地址，则一级间接索引将使可寻址的文件长度变成n2块，对于更大的文件可以采用二级甚至三级间接索引（例如，Unix操作系统采用三级索引结构，如图2-13所示）。

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

练习

试题1
若某文件系统的目录结构如图2-14所示，假设用户要访问文件f1．java，且当前工作目录为Program，则该文件的全文件名为__(1)，其相对路径为(2)__。

（1）A．f1．java B．\DocumentUava-prog\f1．java
C．D:\Program\Java-prog\f1．java D．\Program\Java-prog\f1．java
（2）A．Java-prog\ B．\Java-prog
C．Program\Java-prog D．\Program\Java-prog\

试题2
假设磁盘每磁道有18个扇区，系统刚完成了10号柱面的操作，当前移动臂在13号柱面上，进程的请求序列如表2-2所示。若系统采用SCAN（扫描）调度算法，则系统响应序列为__(3)；若系统采用CSCAN（单向扫描）调度算法，则系统响应序列为(4)__。

（3）A．⑦⑩①②④③⑨⑧⑤⑥ B．①⑦⑩②③④⑥⑤⑧⑨
C．⑦⑩①②④③⑥⑤⑧⑨ D．①⑦⑩②③④⑧⑨⑥⑤
（4）A．⑦⑩①②④③⑨⑧⑤⑥ B．①⑦⑩②③④⑥⑤⑧⑨
C．⑦⑩①②④③⑥⑤⑧⑨ D．①⑦⑩②③④⑧⑨⑥⑤

试题3
某文件管理系统在磁盘上建立了位示图（bitmap），记录磁盘的使用情况。若系统的字长为32位，磁盘上的物理块依次编号为：0、1、2、…，那么4096号物理块的使用情况在位示图中的第__(5)个字中描述；若磁盘的容量为200GB，物理块的大小为1MB，那么位示图的大小为(6)__个字。
（5）A．129 B．257 C．513 D．1025
（6）A．600 B．1200 C．3200 D．6400

试题4
某文件系统采用多级索引结构，若磁盘块的大小为512字节，每个块号需占3字节，那么根索引采用一级索引时的文件最大长度为__(7)K字节；采用二级索引时的文件最大长度为(8)__K字节。
（7）A．85 B．170 C．512 D．1024
（8）A．512 B．1024 C．14450 D．28900

答案
试题1分析
绝对路径就是从根目录开始一直到该目录的全程的路径，这样说可能太抽象，就这个题目来说：D:\Program\Java-prog\f1．java就是文件f1．java的绝对路径，即全文件名。相对路径就是相对于当前目录的路径，在本题中当前目录是Program，而你要访问文件f1．java，那么只需在命令行里输入Java-prog\就可以了。
试题1答案
（1）C（2）A
试题2分析
SCAN调度算法也叫“电梯”算法，磁头固定从外向内然后从内向外沿柱面运动。如此往复，遇到所请求的柱面时立即为其服务。
在本题中，题目告诉我们系统刚完成了10号柱面的操作，当前移动臂在13号柱面上，说明目前磁头正由小柱面号向大柱面号方向移动，那么根据SCAN调度的原则，接着应该响应柱面号为15的请求，而在题目中给出了三个柱面号为15的请求，但其中①和⑦是磁头号8，而7的扇区号为1，因此应该先响应进程⑦，而⑩是用磁头号为10，其扇区号为4，因此接着要响应进程⑩，然后再响应进程①，接着就要出来柱面号为20的进程，分别为②和④，它们的扇区号相同，而进程②的磁头号为6，进程④的磁头号为10，因此应该先响应②；再接着应该响应柱面号为30的进程，当磁头在这个方向上移动时，也无进程需要出来，因此只有当磁头由大柱面号向小柱面号方向移动时，再来出来其它进程，处理的次序应该要根据柱面号从大到小，因此是⑨⑧⑤⑥。而采用CSCAN（单向扫描）调度算法，它的磁头是单向移动的，也就是当磁头从内向外移动到最外面时，磁头放到最内，然后再从内向外扫描。因此采用这种方式得到的响应序列应该是⑦⑩①②④③⑥⑤⑧⑨。
试题2答案
（3）A（4）C
试题3分析
位示图法是为管理磁盘空闲存储空间而提出的一种方法，该方法是在外存上建立一张位示图来记录文件存储器的使用情况。每一位仅对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。
在本题中，题目告诉我们字长32位，即一个字可以表示32个物理块得使用情况，而物理块依次编号为：0、1、2、…，那么第4096号物理块的使用情况应该在位示图中的第129个字中描述，因为（4096+1）/32等于128余1，所以这一位应属于第129个字的第一位，其中4096+1的这个1是因为编号是从0开始计数的，所以才加1。
由于磁盘的容量为200GB，每个物理块的大小为1MB，那么总共有200GB/1MB=200×1024个物理块，需要200×1024位来表示，因此位示图中字的个数=200×1024/32=6400个。
试题3答案
（5）A （6）D
试题4分析
设块长为512B，每个块号占3B，一个物理块可放：512/3=170个目录项，也即：
一个一级索引可存放的文件大小为：170×512=87040B。
一个二级索引可存放文件的大小为：170×170×512=148×105B。
一个三级索引可存放文件的大小为：170×170×170×512=251×107B。
这里还要请大家注意，为了方便计算机。在本题给出答案中，都是按500，而不是512来计算的。
试题4答案
（7）A（8）C