操作系统复习资料

本文格式为Word版，下载可任意编辑——操作系统复习资料

第一章操作系统概论

操作系统的目标:便利性，有效性，可扩展性，开放性。操作系统的作用有：作为用户与计算机硬件系统之间的接口，作为计算机系统资源的管理者，用作扩展机器。

用户使用计算机的三种方式：命令方式，系统调用方式，图形、窗口方式。资源分为四种：处理器，存储器，I/O设备，信息（数据和程序）。

推动操作系统发展的主要动力有：不断提高计算机资源利用率，便利用户，器件的不断更新换代，计算机体系结构的不断发展。

操作系统同计算机系统发展的几个阶段：无操作系统的计算机系统，单道批处理系统，多道批处理系统，分时系统，实时系统。

操作系统:一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及便利用户使用的程序的集合。

分时系统是指:在一台主机上连接了多个带有显示器和键盘的终端，同时允大量个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。

实时系统是指，系统能及时（或即时）响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。

实时任务可分为:周期性实时任务和非周期性实时任务，也可分为硬实时任务和软实时任务。操作系统都具有四个基本特征：（程序）并发，（资源）共享，虚拟和异步。

并行性指:两个或多个事件在同一时间发生，并发性指两个或多个事件在同一时间间隔内发生。

共享指:系统中地资源可供内存中多个并发执行的进程（线程）共同使用，可分为互斥共享方式和同时访问方式。

虚拟指:通过某种技术把一个物理实体变为若干个规律上的对应物。假使n是某物理设备所对应的虚拟的规律设备数，则虚拟设备的平均速度必然是物理设备速度的1/n。

操作系统的功能：处理机管理，存储器管理，设备管理和文件管理。处理器管理包括：进程控制，进程同步，进程通信，调度。存储器管理包括：内存分派，内存保护，地址映射，内存扩展。设备管理包括：缓冲管理，设备分派，设备处理。

文件管理包括：文件存储空间管理，目录管理，文件的读写管理和保护。操作系统向用户提供的接口有：命令接口，程序接口，图形接口。

操作系统的结构发展：无结构，模块式结构，层次式结构，微内核OS结构。软件:指当计算机运行时，能提供所要求的功能和性能的指令和程序的集合。

微内核技术是:精心设计的、能实现现代OS核心功能的小型内核，它与一般的OS（程序）不同，它更小更精炼，它不仅运行在核心态，而且在开机后常驻内存，它不会因内存紧张而换出内存来。

微内核提供的寻常都是一些最基本的功能：进程管理，存储器管理，进程通信管理，低级I/O功能。

其次章进程管理

程序顺序执行的特征：顺序性，封闭性，可再现性。

前趋图:是一个有向无循环图，DAG，用于描述进程之间执行的前后关系。进程的实体:由程序段、相关的数据段和进程控制块PCB构成。创立和撤消进程都是指:创立或撤消进程中的PCB。进程具有:动态性、并发性、独立性和异步性的特征。

进程是:进程实体的运行过程，是系统进行资源分派和调度的一个独立单位。进程的三种基本状态是:就绪状态、执行状态和阻塞状态（等待状态）。（见P31图2-5）系统根据PCB控制进程，PCB:是进程存在的唯一标志。PCB常驻内存，系统将所有PCB组织成若干链表（或队列），存放在操作系统专门开拓的PCB区内。

进程控制块PCB主要包括四方面的信息:进程标识符（内部标识符和外部标识符），处理机状态（一些寄放器中断时的信息），进程调度信息，进程控制信息。

进程控制块的组织方式寻常有:链接方式（指针链接）和索引方式（索引表）两种。PCB中都设置了:家族关系表项，以标明自己的父进程及所有的子进程。

进程创立进程的典型事件可分为四类：用户登录，作业调度，提供服务，应用请求。进程创立步骤：1申请空白PCB，2分派资源，3初始化PCB，4插入就绪队列。初始化进程控制块包括：初始化标识信息；初始化处理机状态信息；初始化处理机控制信息。引起进程终止的事件有：正常终止，异常终止，外界干预。

进程终止步骤：1根据被终止进程的标识符，在PCB集合中检索出该进程的PCB，读取其状态，2若处于执行状态，马上终止，置调度标志为真，用于指示该进程被终止后应重新进行调度，3假使有的话，终止所有子进程，4将被终止进程拥有的全部资源归还其父进程或系统，5将被终止进程PCB从所在队列（或链表）中移出，等待其他程序来搜集信息。引起进程阻塞或唤醒的条件：请求系统服务，启动某种操作，新数据未到，无新工作做。进程阻塞过程：调用阻塞原语block把自己阻塞，如在执行状态，马上中止执行，修改PCB中状态为“阻塞〞，PCB插入阻塞队列。转调度程序将CPU重新调度给另一就绪进程。进程唤醒过程：调用唤醒原语wakeup，将被阻塞的进程从等待该事件的阻塞队列中移出，将PCB中状态改为“就绪〞，将PCB插入到就绪队列中去。

进程挂起过程：调用挂起原语suspend，如进程为活动就绪状态就改为静止就绪，如活动阻塞状态就改为静止阻塞，如进程正在执行就转向调度程序重新调度。

进程激活过程：调用激活原语active，先将进程从外存调入内存，如进程为静止就绪就改为活动就绪，如静止阻塞就改为活动阻塞，判定新就绪的进程的优先级是否能抢夺CPU。进程之间包括:互斥和同步两种关系。

进程同步的主要任务:是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

临界区CS（criticalsection）是指:每个进程中访问临界资源的那段代码。临界区前面用于检查是否能访问临界资源的代码叫进入区，后面加上一段代码退出区用于恢复标志，其余的代码部分叫做剩余区。

进程同步可以采用:信号量机制和管程机制。

同步机制遵循的原则：空闲让进，忙则等待，有限等待，让权等待。

记录型信号量:采用wait(S)和signal(S)来防止类似整型信号量会导致的忙等。AND型信号量采用:Swait(S1,S2,?Sn)和Ssignal(S1,S2,?Sn)来防止死锁。信号量集用:Swait（S,t,d）表示，S为信号量，t为下限值，d为需求值。例子：利用信号量实现前趋关系。（P45，图2-10）例子：利用记录型信号量解决生产者－消费者等问题。（P46）

一个管程定义了:一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。

管程由三部分组成：局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对局部于管程的设置初始值的语句。

例子：利用管程解决生产者－消费者问题。（P52）

进程通信包括:低级通信（进程之间的互斥和同步）和高级通信（共享存储器系统，消息传

递系统以及管道通信系统），又可分为直接通信（通信原语）和间接通信（信箱）。

高级进程通信:是指用户可直接利用操作系统所提供的一组通信命令，高效的传送大量数据的一种通信方式。可归结为三大类：共享存储系统、消息传递系统以及管道通信系统。管道通信具有三方面的协调能力：互斥，同步，确定对方是否存在。进程通信可分为直接通信方式和间接通信方式。

直接通信方式指:利用OS提供的发送命令，直接把消息发送给目标进程。寻常系统提供两条通信命令（原语）：Send（Receive,Message）和Receive（Sender,Message）。

间接通信方式指:进程之间的通信需要通过作为共享数据结构的实体，寻常称之为信箱。信箱可分为:私用信箱（单向通信链路的信箱），公用信箱（双向通信链路的信箱）和共享信箱。拥有私用信箱的进程终止时，信箱随之消失。公用信箱在系统运行期间始终存在。公用信箱和共享信箱的区别在于:公用信箱是由操作系统创立，并提供给系统中的所有核准进程使用的。而共享信箱是由某进程创立给它和其他指定共享进程使用的。

两种方式建立一条通信链路：用显式的“建立连接〞命令原语请求系统为之建立（常用于计算机网络中）；利用发送命令原语，系统自动为之建立（常用于单机系统中）。

通信链路可分为：点对点连接通信链路和多点连接链路；单向通信链路和双向链路；无容量通信链路（无缓冲区）和有容量通信链路（有缓冲区）。

消息分为消息头（控制信息）和消息正文（实际上发送的数据）。

进程同步方式有：1发送进程阻塞，接收进程阻塞（又称为会集）2发送进程不阻塞，接收进程阻塞3发送进程接收进程都不阻塞。

消息缓冲队列通信机制及其中的发送原语和接收原语。（P59）

在操作系统中引入线程:是为了减少程序在并发执行所付出的时控开销，使操作系统具有更好的并发性。

在多线程OS中，寻常是:在一个进程中包含多个线程，每个线程都是作为利用CPU的基本单位，是花费最小开销的实体。

线程具有以下属性：轻型实体，独立调度和分派的基本单位，可并发执行，共享进程资源。线程的状态：状态参数和运行状态（也有执行状态，就绪状态，阻塞状态）

线程被中止后并不马上释放它所占有的资源，只有当进程中的其它线程执行了分开函数后，被终止的线程才与资源分开，此时的资源才能被其他线程利用。

多线程OS中的进程：进程仍是系统分派资源的基本单位，每个进程都含有多个相对独立的线程，进程不是一个可执行的实体，而是把线程作为独立运行的基本单位。所谓进程处于“执行〞状态，实际上是指该进程中的某线程正在执行。把某个进程挂起或激活，该进程的所有线程也都被挂起或激活。

线程同步和通信机制有：互斥锁，条件变量，信号量机制。

互斥锁适合于:高频度使用的关键共享数据和程序段，关锁lock和开锁unlock操作mutex每个条件变量寻常都和一个互斥锁一起使用,线程首先对mutex执行关锁操作，若成功便进入临界区，然后查找用于描述该资源状态的数据结构，以了解资源的状况。只要发现所需资源R正处于繁忙状态，线程便转为等待状态，并对mutex执行开锁操作后，等待资源被释放；若资源处于空闲状态，说明线程可以使用该资源，于是将该资源设置为繁忙状态，再对mutex执行开锁操作。

线程的实现方式有:用户级线程和内核支持线程。

内核支持线程是:无论是用户进程中的线程还是系统进程中的线程，他们的创立、撤消和切换等，都是依靠内核实现的。此外，内核空间中还每个线程设置了一个线程控制块。

用户级线程仅存在于用户空间中。这种线程的创立、撤消、同步等都无须利用系统调用来实现。所以线程的切换速度特别快。内核完全不知道用户级线程的存在。

用户级线程的调度以:进程为单位，而内核支持线程的调度以线程为单位。用户级线程的实现可分为:运行时系统和内核控制线程。第三章处理机调度和死锁

高级调度又称为:作业调度或长程调度，用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创立进程，分派必要的资源，然后，再将新创立的进程排在就绪队列上。低级调度称为:进程调度或短程调度，用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分派给该进程的具体操作。

进程调度可分为非抢占方式和抢占方式（优先权原则/短作业优先原则/时间片原则）。中级调度又称:中程调度。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量，实际上就是存储器管理中的对换功能。

三种调度队列模型：仅有进程调度的调度队列模型，具有高级和低级调度的调度队列模型，同时具有三级调度的调度队列模型。

调度算法是指：根据系统的资源分派策略所规定的资源分派算法。先来先服务调度算法（FCFS），短作业（进程）优先调度算法（SJF），高优先权优先调度算法，基于时间片的轮转调度算法。（P76）

高优先权优先调度算法分为:非抢占式优先权算法和抢占式优先权调度算法。优先权分为:静态优先权和动态优先权。

基于时间片的轮转调度算法可分为:时间片轮转法和多级反馈队列调度算法。

实现实时调度的条件：提供必要的信息，系统处理能力强，采用抢占式调度机制，具有快速切换机制。

抢占调度的时机可在时钟中断发生的时候或者马上抢占。实时调度算法：最早截止时间优先算法（EDF），最低松弛度优先算法（LLF）。（P84）多处理器系统可分为:紧凑耦合MPS（通过高速总线或高速交织开关）和松弛耦合MPS（通过通道或通信线路）。

多处理器系统可分为:对称MPS（所有处理器都一样）和非对称MPS（一主多从）。

多处理器的进（线）程调度方式有：自调度方式、成组调度方式和专用处理器分派方式。产生死锁的原因有：竞争资源、进程间推进顺序非法。

死锁的发生必需具备四个必要条件：1互斥条件，2请求和保持条件，3不剥夺条件，4环路等待条件。

处理死锁的基本方法有：预防死锁，避免死锁，检测死锁，解除死锁。

预防死锁的方法是使以上四个必要条件中的2，3，4不成立，如静态分派，有序分派。安全序列是指:系统能按某种进程顺序来为每个进程Pi分派其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利完成。避免死锁：例子：银行家算法避免死锁。（P95）

检测死锁：死锁定理：当且仅当S状态的资源分派图使不可完全简化的。（P99）解除死锁：死锁解除可以通过剥夺资源和撤消进程（最小代价进程撤消法）。第四章存储器管理

创立进程的第一件事便是:将程序和数据装入内存。

将一个用户源程序变为一个可在内存中执行的程序:首先要编译，由编译程序将用户源代码编译成若干目标模块；其次是链接，由链接程序将目标模块和需要的库函数链接在一起形成一个完整的装入模块；最终是装入，由装入程序将装入模块装入内存。

将装入模块装入内存的方式有：绝对装入方式，可重定位装入方式和动态运行时装入方式。采用可重定位装入程序将装入模块装入内存后，会使装入模块中的所有规律地址与实际装入内存的物理地址不同。在装入时对目标程序中的指令和数据的修改过程成为重定位。

动态运行时装入，在把装入模块装入内存后，并不马上把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真刚要执行时才进行，该方式需要一个重定位寄放器的支持。

链接的方式有：静态链接，装入时动态链接和运行时动态链接。连续分派方式是指为:一个用户程序分派一个连续的内存空间，进一步可分为单一连续分派，固定分区分派，动态分区分派以及动态重定位分区分派四种方式。单一连续分派是:把内存分为系统区和用户区两部分。

固定分区分派是:将内存用户空间划分为若干固定大小（分区大小可等可不等）的区域，每个分区只装一道作业。

寻常按分区大小排队:建立一张分区使用表，给程序一个能满足要求又尚未分派的分区。动态分区分派中的数据结构可采用:空闲分区表和空闲分区链两种。分区分派算法有:首次适应算法，循环首次适应算法和最正确适应算法。

最正确适应算法是:将空闲分区大小从小到大形成一个链，最先适应的必然是最正确的。但是这种分派算法寻常会导致切割下来的剩余空间最小，而产生大量难以利用的小空闲区。

分派内存时看:是否剩下的空间大于事先规定的不再切割的剩余分区的大小，而回收内存时根据前后是否是空闲分区决定是否需要合并。

动态重定位分区分派是:指将空闲分区紧凑成连续空闲区分派给需要的程序，同时修改有关数据结构使已经被分派空间的程序能继续正常运行。“对换〞，是指:把内存中暂时不能运行的进程或暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程需要的程序和数据调入内存。以整个进程为单位的对换称为:“整体对换〞或“进程对换〞。以“页〞或“段〞为单位的对换分别称为“页面对换〞或“分段对换〞。

为实现进程对换，系统必需具有以下功能：对换空间的管理，进程的换出，进程的换入。将一个进程直接分散装入到大量不相邻接的分区中，则无须再进行“紧凑〞，此谓离散分派方式，离散分派的基本单位是“页〞或“段〞，对应于分页/段存储管理方式。

分页存储管理是:将一个进程的规律地址空间分为若干大小相等的片，称为页面或页。分页大小应适中，太小会使进程的页表过长，占用大量内存；太大会使页内碎片增大。分页地址中的地址分为两部分:前一部分为页号P，后一部分为位移量W（页内地址）。系统为每个进程建立了一张页面映象表，简称页表，其作用是实现页号到物理块号的映射。即使在最简单的页表系统中，也设置一存取控制字段，用于保护该存储块中的内容。

地址变换机构的任务:只是将规律地址中的页号，转换为内存中的物理块号。地址变换的任务就可以借助于页表来完成。

页表寻常驻留在内存中，而系统中只设置一个页表寄放器PTR来实现页表功能。“快表〞又称:“联想寄放器〞，是为了:提高地址变换速度而增设的一个具有并行查寻能力的特别高速缓冲寄放器。此时，在CPU给出有效地址后，首先将页号与联想寄放器中的页号对比，假使有，就直接读出对应物理块号送物理地址寄放器，若无再访问内存中的页表。两级页表和多级页表是为了:防止页表占有太大内存空间而对页表结构再进行分级。

分段存储管理方式的引入主要是为了满足以下需要：便利编程，信息共享，信息保护，动态增长，动态链接。

分段存储管理方式中，作业的地址空间被划分为:若干个段，每个段定义了一组规律信息。例如，有主程序段MAIN，子程序段X，数据段D及栈段S等。段的长度由:相应的规律信息组的长度决定，因而各段长度不等。

段的数据结构可分为两部分:段号和段内地址。一般状况下，段比页大。系统为每个进程建立了一张段表，用于实现从规律段到物理内存区的映射。

分段系统和分页系统有好多相像之处，但在概念上完全不同，主要表现在以下三个方面：1页是信息的物理单位，是为了满足系统管理的需要，而段是信息的规律单位，是为了满足用户的需要；2页的大小固定且由系统决定，而段的长度不确定，取决于用户编写的程序；3分页的作业地址空间是一维的，程序员只需利用一个记忆符即可表示一个地址；而分段的作业地址则是二维的，程序在标识一个地址时，既需给出段名，又需给出段内地址。

分段系统的一个突出优点是:易于实现段的共享，对段的保护也十分简单易行。可重入代码又称“纯代码〞，是:一种允大量个进程同时访问的代码，是一种不允许任何进行对它进行修改的代码。

段页式存储管理方式，是:将用户程序分为段，段再分为页，并为每个段赋予一个段名。

段页式系统中，地址结构由:段号，段内页号及页内地址三部分组成。虚拟存储器，是指具有请求调入功能和置换功能，能从规律上对内存容量加以扩展的一种存储器系统。

虚拟存储器系统可分为:分页请求系统和分段请求系统。虚拟存储器有几大特征：屡屡性（最重要和特别的特征），对换性，虚拟性。其中，虚拟性是以屡屡性和对换性为基础的，而屡屡性和对换性又必需建立在离散分派的基础上。

请求分页系统需要:页表机制，缺页中断机构以及地址变换机构。

页表的基本作用仍是:将用户地址空间中的规律地址变换为内存空间中的物理地址，页表项中包括：页号，物理块号，状态位P，访问字段A，修改位M，外存地址。

缺页中断与一般中断的区别：在指令执行期间产生和处理中断信号；一条指令在执行期间，可能产生屡屡缺页中断。

请求分页系统中的地址变换机构及其运行流程。（P130）

内存中的物理块分派策略包括:固定分派局部置换，可变分派全局置换，可变分派局部置换。固定分派指固定为某进程分派n个物理块，缺页就要对换；可变分派指可以动态地增加分派给某进程的物理块数。局部置换指只能换出本进程的其他物理块，全局置换指可以先将需要的信息换到系统的空闲物理块中，仅当空闲物理块快用完时换出系统中任一物理块。物理块分派算法包括：平均分派算法，按比例分派算法，考虑优先权的分派算法。页面调入时机的确定可分为:预调页策略和请求调页策略。

从何处调入页面的确定可分为:1全部从对换区调入所需页面；2凡是不会修改的文件，都直接从文件区调入，可能修改的部分，便须调到对换区；3Unix方式，未运行过的页面，从文件区调入，运行过但又被换出的页面，由于放在对换区，因此下次从对换区调入。

页面置换算法包括:最正确置换算法（理想化算法Optimal），先进先出置换算法（FIFO），最近最久未使用置换算法（LRU），Clock置换算法（简单型NRU和改进型），最少使用置换算法（LFU），页面缓冲算法（PBA）。（P137）

请求分段管理所需的硬件支持:有段表机制，缺段中断机构，以及地址变换机构。请求分段段表项有：存取方式，访问字段A，修改位M，存在位P，增补位，外存始址。

增补位是:请求分段管理中特有的字段，用于表示本段在运行过程中是否做过动态增长。

请求分段系统中的缺段中断处理流程和地址变换过程。（P139）

共享段表中的共享进程计数count记录有多少个进程需要共享该分段。共享段表中的存取控制字段定义了不同进程的不同的存取权限。共享段表中的段号让不同的进程可以以不同的段号去共享该段。共享段的分派与回收：对第一个请求使用该共享段的进程，由系统为该共享段分派一物理区，再把共享段调入该区，同时将该区的始址填入请求过程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1，之后又有其他进程需要调用该共享段时，只需在调用进程的段表中，增加一表项，填写该共享段的物理地址，在共享段的段表中，填上调用进程的进程名、存取控制等，再将count加1。回收共享段时，将count减1，若结果为0，则由系统回收该共享段的物理内存，取消在共享段表中该段所对应的表项。分段保护的措施：越界检查，存取控制检查，环保护机构。

环保护机构的规则：1一个程序可以访问驻留在一致环或较低特权环中的数据；2一个程序可以调用驻留在一致环或较高特权环中的服务。第五章设备管理

I/O设备重要的性能指标有：数据传输速率，数据的传输单位，设备共享属性等。I/O可分为:低速设备，中速设备，高速设备；可分为块设备，字符设备；可分为独占设备，共享设备，虚拟设备。

I/O设备到设备控制器有一根数据信号线和一根状态信号线，设备控制器到I/O设备有一根数据信号线和一根控制信号线。

设备控制器是:计算机中的一个实体，其主要职责是控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换。设备控制器的基本功能有：接收和识别命令，数据交换，标识和报告设备的状态，地址识别，数据缓冲，过错控制。设备控制器由三部分组成：设备控制器与处理器的接口，设备控制器与设备的接口，I/O规律。I/O规律的作用是对收到的命令进行译码，来对所选设备进行控制。

I/O通道引入的目的是:使一些原来由CPU处理的I/O任务转由通道来承受。I/O通道其实是一种特别的处理机，但也有其不同于处理机之处：指令类型单一，能执行的命令主要局限于与I/O操作有关的指令；通道没有自己的内存，而要与CPU共享内存。

通道三种类型：字节多路通道，数组选择通道，数组多路通道。

解决通道“瓶颈〞问题的最有效的方法是:增加设备到主机间的通路而不增加通道。

总线的性能是:用总线的时钟频率、带宽和相应的总线传输速率等指标来衡量的。由最早的ISA总线发展为EISA总线、VESA总线，进而到现在的PCI总线。PCI在CPU和外设间插入一繁杂的管理层，用于协调数据传输和提供一致的接口。

I/O控制方式由:最早的程序I/O方式，到中断驱动方式，再到DMA控制方式。（P152）

中断驱动方式中，CPU把工作通过中断交给设备控制器，然后转而继续执行原来的任务，而任务完成后，设备控制器通过中断告诉CPU，实现了CPU与I/O设备的并行工作。

DMA方式中，数据传输的基本单位是数据块；所传输的数据是从设备直接送入

内存，或者相反；仅在传送一个或多个数据块的开始和终止时，才需CPU干预。DMA控制器由三部分组成：主机与DMA控制器的接口，DMA控制器与块设备的接口，I/O控制规律。

DMA控制器中设置有如下四类寄放器：命令/状态寄放器CR，内存地址寄放器MAR，数据寄放器DR，数据计数器DC。DMA控制器的工作方式。（P154）

I/O通道方式是:DMA方式的发展。通道通过通道程序，与设备控制器共同实现对I/O设备的控制。

通道程序包含：操作码（读，写，控制等），内存地址，计数（操作的数据的字节数），通道程序终止位P（为1表示本条指令为通道程序的最终一条指令），记录终止标志R（为0表示本指令与下指令处理的数据同属一个记录，为1表示这是处理某记录的最终一条指令）

缓冲可以：1）缓和CPU和I/O设备间速度不匹配的矛盾；2）减少对CPU的中断频率，放宽对CPU中断响应时间的限制；3）提高CPU和I/O设备之间的并行性。

单缓冲，双缓冲，循环缓冲属于专用缓冲，现在多采用的是缓冲池。

缓冲池中三个队列：空缓冲队列emq，输入队列inq，输出队列outq；四种工作缓冲区：收容输入数据的工作缓冲区，提供输入数据的工作缓冲区，收容输出数据的工作缓冲区，提供输出数据的工作缓冲区。Getbuf过程，Putbuf过程，缓冲区工作方式。（P160）

设备分派时需要的数据结构（表格）有:设备控制表DCT，控制器控制表COCT，通道控制表CHCT和系统设备表SDT等。

设备的固有属性可分为:独占性，共享性，可虚拟性。

设备分派算法寻常只采用以下两种：先来先服务算法，优先权服务算法。

设备独立性（无关性）的基本含义是：应用程序独立于具体使用的物理设备。设备独立性软件能执行所有设备的公用操作，向用户层（或文件层）软件提供统一接口。

规律设备表LUT将应用程序中所使用的规律设备名映射为物理设备名。

独占设备的分派程序：根据I/O请求中的物理设备名查找系统设备表SDT，找到该设备的设备控制表DCT；在系统把设备分派给请求I/O的进程后，再到其设备控制表DCT中找出该设备连接的控制器的控制器控制表COCT；在该控制器控制表COCT中又可找到与该控制器连接的通道的通道控制表CHCT。当设备、控制器和通道都分派成功时，分派成功。

在联机状况下实现的同时外围操作称为SPOOLing，或称为假脱机操作。SPOOLing技术是对脱机输入，输出系统的模拟。

SPOOLing系统主要有：输入井和输出井；输入缓冲区和输出缓冲区；输入进程SPi和输出进程SPo。

SPOOLing系统提高了I/O的速度，将独占设备改造为共享设备，实现了虚拟设备功能。

设备处理程序寻常又称为设备驱动程序，是I/O进程和设备控制器之间的通信程序。

设备驱动程序的处理过程：将抽象要求转换为具体要求；检查I/O请求的合法性；读出和检查设备的状态；传送必要的参数；工作方式的设置；启动I/O设备。中断处理程序的处理过程：唤醒被阻塞的驱动（程序）进程；保护被中断进程的

CPU环境；转入相应的设备处理程序；中断处理；恢复被中断进程的现场。（P171）磁盘设备包括:一个或多个盘片，每片两面，每面分为若干磁道，每磁道分为若干扇区。

根据磁头的类型，磁盘可分为固定头磁盘和移动头磁盘。磁盘访问时间＝寻道时间＋旋转延迟时间＋传输时间

磁盘调度算法有：先来先服务，最短寻道时间优先，扫描算法，循环扫描算法，N-Step-SCAN和FSCAN调度算法等。

磁盘高速缓存是一组在规律上属于磁盘，而物理上是驻留在内存中的盘块。UNIX系统中，每隔一定时间，强制性地将所有在高速缓存中已修改的盘块数据写回磁盘，MS-DOS发现某盘块数据修改，就马上写回磁盘（“写穿透，高速缓存〞）。

提高磁盘I/O速度的其他方法还有提前读，延迟写，优化物理块的分布，虚拟盘。RAID的优点有:可靠性高，磁盘I/O速度高，性能/价格比高。第六章文件管理

基于文件系统的概念:可以把数据组成分为数据项，记录和文件三级。其中，数据项是最低级的数据组织形式，包括基本数据项和组合数据项。记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。文件是指由创立者所定义的、具有文件名的一组相关元素的集合，可分为有结构文件（由若干记录组成）和无结构文件（字符流）两种。

文件规律结构，首先是:能提高检索速度，其次是便于修改，第三是降低文件的存储费用。

有结构文件中记录的长度可分为:定长和不定长两种，但是不管哪一种，在处理前，每个记录的长度是可知的。

有结构文件中组织记录的方式有:顺序文件，索引文件和索引顺序文件，直接文件哈希文件。

无结构文件即:流式文件的长度以字节为单位，也可看作是记录式文件的一个特例。

外存的分派方式有:连续分派，链接分派和索引分派三种。连续分派要求:为每一个文件分派一组相邻接的盘块。链接分派可分为:隐式链接和显式链接两种形式。

隐式链接要求:在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最终一个盘块的指针。

显式链接是:把用于链接文件各物理块的指针，显式地放在内存的一张链接表中，该表在整个磁盘上仅设置一张。MS-DOS中，每个文件的第一个盘块号放在自己的FCB中，而其余链接的盘块号放在系统唯一的一张文件分派表FAT中。索引分派是:将分派给文件的所有盘块号记录在索引块中，有单级索引分派，多级索引分派和混合索引分派方式。目录管理要求：1实现“按名存取〞；2提高对目录的检索速度；3文件共享；4允许文件重名。

为了能对一个文件正确的存取，必需为文件设置用于描述和控制文件的数据结构，称之为“文件控制块（FCB）〞。文件与文件控制块一一对应，而人们把文件控制块的有序集合称为文件目录，即一个文件控制块就是一个文件目录项。寻常，一个文件目录也被看作一个文件，称为目录文件。

文件控制块中寻常含有三类信息：基本信息，存取控制信息及使用信息。

索引结点是文件描述信息单独形成的一个数据结构，简称为I结点。在文件目录中的每个目录项，仅有文件名和指向该文件所对应的I结点的指针所构成。常用的目录结构形式有:单级目录，两级目录和多级目录。

单级目录中:文件名在目录中是唯一的，相应的也是一个文件名对应一个文件。两级目录中:每个用户有一个单独的用户文件目录UFD。不同用户目录中文件名可一致，不同用户还可以使用不同的文件名来访问系统中的同一个共享文件。多级目录中:主目录被称为根目录，数据文件称为树叶，其他的目录称为树的结点。

对目录的查询方式可分为:线性检索法和Hash法两种。文件存储空间的基本分派:单位都是磁盘块而非字节。

文件存储空间的管理方式有:空闲表法，空闲链表法，位示图法，成组链接法几种。（P208）

文件的共享方式有:基于索引结点的共享和利用符号链实现文件共享等。

基于索引结点的共享中，目录结构不再是树型结构，而是有向非循环图（可以两个结点指向一个树叶）；文件的属性存放在索引结点中而不是目录项中以便修改；索引结点中还有一个链接计数count表示链接到本索引结点（亦即文件）上的用户目录项的数目。

在利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的指针；而共享该文件的其他用户，则只有该文件的路径名，并不拥有指向其索引结点的指针。

利用符号链实现文件共享的一个缺点是:当程序员将一个目录上的所有文件都转储到磁带上去时，就可能对一个共享文件产生多个拷贝。

为了确保文件系统的安全性，可以采取以下措施：1存取控制机制防人为因素；2磁盘容错技术防磁盘故障；3“后备系统〞防自然因素。

容错技术是通过在系统中设置冗余部件的方法，来提高系统可靠性的一项技术。磁盘容错技术则是通过增加冗余的磁盘驱动器、磁盘控制器来提高磁盘系统可靠性的一项技术。

磁盘容错技术往往也被称为系统容错技术SFT，可分为三个级别：SFT-I，低级磁盘容错技术，防磁盘表面缺陷所引起的数据丢失；SFT-II，中级磁盘容错技术，防磁盘驱动器和磁盘控制器故障导致磁盘无法正常工作；SFT-III，高级磁盘容错技术。

低级磁盘容错技术有：双份目录、双份文件分派表和写后读校验。中级磁盘容错技术有：磁盘镜像和磁盘双工。

事务是:用于访问和修改各种数据项的一个程序单位。事务操作具有“原子性〞。引入检查点后，只需对最终一个检查点之后的事务记录进行处理。

互斥锁:仅允许一个事务对相应对象执行读或写操作，而共享锁则允大量个事务对相应对象执行读操作，而不允许其中任何一个事务对对象进行写操作。读只需共享锁，而写操作则需要互斥锁。

空闲盘块号计数器组和数据盘块号计数器组对同一个盘块号应当一个为1，一个为0。

共享文件的索引结点中的链接计数应和实际的共享文件的用户（进程）数一致，否则可能导致无人访问但不删或有人访问但删除。

第一章操作系统概论

1．（）不是批处理多道程序的性质。A．“多道作业并发工作〞B．“未采用spooling技术〞C．“作业成批输入〞D．“作业调度可合理选择作业投入运行〞2．网络操作系统和分布式操作系统的主要区别是（）A．是否连接多台计算机B．各台计算机有没有主次之分C．计算机之间能否通信D．网上资源能否共享3．用户程序中的I／O操作实际是由（）完成。A．程序设计语言B．标准库程序C．编译系统D．操作系统4.设计分时操作系统的主要目标是（）A．吞吐量和周转时间B．交互性和响应时间C．灵活性和可适应性D．可靠性和完整性5.以下关于多道程序设计系统的说法，不正确的是：()

A.多道程序同时存在于内存中，且并发执行。B.各种不同的设备可并行工作。C.处理机上会同时运行多道程序。D.系统的吞吐量远远大于单道程序设计系统。6.分时OS设计中关系到系统效率的关键问题是：()

A.时间片的长短B.用户的数目C.主机性能D.内存容量

7.使操作系统易于对功能进行增、删、修改，为提高效率对算法进行调整等，这是操作系统结构设计追求的目标中的（）A．便利性B．有效性C．可扩展性D．开放性8.分时操作系统不具有以下哪个特征（）A.多用户同时性B．独立性C．高可靠性D．交互性9.在实时系统中，处理机的分派往往采用（）算法。A.先来先服务B.非抢占式优先权C.时间片轮转D.可抢占式优先权二、多项选择题

1．操作系统的设计方法有（）等。

A．无序模块法B．有序模块法C．层次结构法D．内核扩展法E．管程设计法

2.操作系统是一种系统软件，它的职能是（）

A.只管理软件B.只管理硬件C.既不管理硬件，也不管理软件D.既管理硬件，也管理软件3.设计批处理操作系统时，首先应考虑的是（）

A.交互性和响应时间B.吞吐量和周转时间C.灵活性和可适应性D.可靠性和完整性4.批处理多道系统的性质有（）A．作业成批输入

B．作业调度可合理选择作业投入运行

C．多个作业并行工作D．不采用spool技术E．处理前台的联机作业5.操作系统的基本功能有（）。A．处理机管理B．存储管理C．设备管理D．文件系统管理E．用户接口三、填空题

1软件可以分为__________软件和__________软件两类。2.裸机＋软件＝。

3.操作系统为用户提供的接口有__________、__________

4.操作系统的基本功能包括______、_______、______和__________。5.在__________的基础上覆盖了软件的计算机系统称为虚拟机。

6.所谓__________技术，是指精心设计的、能实现现代OS核心功能的小型内核。

7.操作系统是一种__________软件，其基本的类型有_______________操作系统、分时操作系统、_______________操作系统、个人计算机操作系统、_______________操作系统和网络操作系统六种。

8.计算机系统中引导程序的作用是______________和______________。简答题、

1、操作系统的作用是什么？

2、操作系统的的基本类型有哪些？各有什么特点？部分答案：

一、单项选择1B2B3B4B5C6A7C8C9A二、多项选选择1ACDE2D3BC4ABCE5ABCDE三、填空

1.系统应用2.计算机系统3.命令接口系统调用

4.处理机管理设备管理文件管理存储器管理5.裸机6.微内核

7.系统批处理实时分布8系统初始化把操作系统的核心程序装入主存其次章进程管理一、单项选择题

1．采用多道程序设计后，可能（）A．缩短对用户请求的响应时间B．降低了系统资源的利用率C．缩短了每道程序执行时间D．延长了每道程序执行时间2.操作系统中同时存在着多个进程，它们（）A．不能共享系统资源B．不能调用同一段程序代码C．可以共享所有的系统资源D．可以共享允许共享的系统资源3.．涉及某一资源造成与时间有关的错误的原因，正确的是（）A．一个进程屡屡申请，释放该资源B．若干并发进程互斥使用该资源C．若干并发进程同时使用该资源D．以上说法均不对4.．PV操作是在（）上的操作。A．临界区B．进程C．缓冲区D．信号量

5．有关资源分派图中存在环路和死锁关系正确的说法是（）A．图中无环路则系统可能存在死锁B．图中有环路则系统确定存在死锁

C．图中有环路则系统可能存在死锁，也可能不存在死锁D．以上说法都不对

6.有关抢夺资源预防死锁说法中不正确的是（）

A．若进程P申请资源R被进程Q占用，当进程Q等待另一资源时，可抢夺资源R，否则进程P等待

B．一个等待资源的进程只有得到新申请的资源和所有被抢夺的资源后才能继续运行C．打印机是可抢夺的资源D．主存空间是可抢夺的资源7.采用多道程序设计能（）A．增加平均周转时间B．发挥且提高并行工作能力C．缩短每道程序执行时间D．降低对处理器调度的要求8.为了对紧急进程或重要进程进行调度，调度算法应采用（）A．先来先服务B．轮转法C．优先权调度D．短执行时间优先调度9.有关进程同步机制不正确的提法是（）A．“同步机制能把其它进程需要的消息发送出去〞B．“同步机制能测试调用进程需要的消息是否到达〞C．“PV操作和管程是两种典型的同步机制〞D．“同步信号上的V操作是测试调用进程所需的消息是否到达〞10.依照PV操作的定义正确的说法是（）

A．调用P操作后进程确定能继续运行B．调用P操作后进程确定阻塞C．调用P操作后进程可能继续运行或阻塞D．调用V操作后可能会阻塞11．系统运行银行家算法是为了（）A．检测死锁B．避免死锁C．解除死锁D．防止死锁12．有关死锁检测的提法错误的是（）A．“死锁检测用于对系统资源的分派不加限制的系统〞B．“系统可定时运行死锁检测程序进行死锁的检测〞

C．“死锁检测的结果能知道系统是否能预防死锁〞D．“死锁检测的结果能知道系统当前是否存在死锁〞13.以下哪个是阻塞状态转换为就绪状态的时机：

A.被进程调度程序选中B.时间片到C.发生等待事件D.等待事件发生14.以下关于进程家族的说法，不正确的是：A.子进程可以继承父进程所拥有的资源

B.在撤消父进程时，必需同时撤消其所有的子进程C.父进程可以创立子进程D.子进程可以创立父进程

15.列操作中，哪个是wait原语的操下作：

A.beginS.value:=S.value-1;ifS.value>0thenblock(S.L);end;B.beginS.value:=S.value+1;ifS.value>0thenwakeup(S.L);end;C.beginS.value:=S.value+1;ifS.value0thenblock(S,L)end;B.beginS.value:=S.value+1;ifS.value>0thenwakeup(S,L)end;C.beginS.value:=S.value+1;ifS.value0thenblock(S);end;B.beginS:=S+1;ifS>0thenwakeup(S);end;C.beginS:=S+1;ifS

整数逐个存入缓冲区池，读进程Reader则逐个从缓冲区池中读出并打印输出，要求打印的与输入的完全一样，即个数、次序、数值一样。试问：

（1）写进程与读进程间具体的制约关系如何？

（2）用PV操作写出这两个进程的同步算法程序。

采用“时间片轮转〞的进程调度算法时，时间片取值过大或过小对操作系统的影响是什么？3、假定一个阅览室可供50个人同时阅读。读者进入和离开阅览室时都必需在阅览室入口入的一个登记表上登记，阅览室有50个座位，规定每次只允许一个人登记或注销登记。

要求：

（1）用PV操作描述读者进程的同步算法（可用流程图表示，登记、注销可用自然语言描述）；

（2）指出流程图中所用信号量的名称、作用及初值。

4.假设有32个存储区域，其编号为0，1，?，31，用一个32位的标志字，位号也是0，1，?，31，分别描述32个存储区域使用状态：当某一位为1时，表示对应存储区域已分派，若为0，表示对应存储区域空闲。get进程负责存储区域分派，每次分派一个区域，找出标志字某为0的位置成1。put进程负责存储区域回收，把回收存储区域标志字对应位清成0。要求：

(1)分析get进程与put进程的具体同步关系。

(2)采用PV操作同步工具，写出get进程与put进程的同步算法（可用流程图描述，但信号量名称、作用、初值必需说明。）

5.画出以下五条语句的前趋图，并说明S2和S3语句、S2和S4语句是否可以并发执行？S1：a=5+y；S2：b=8+x；S3：d=a＋b；S4：c=4＊z；S5：e=d＋c；部分参考答案

一、单项选择1A2C3A4A5C6B7B8C9D10C11B12C13D14D15B16B17A18B19D20D21.B22B23D24D25B26D27C28D29B30A31D32A33A34B35B36B37D38D二多项选择1ABCDE2ACE3ABCE4CE5BCE6ACD7ADE三填空题

动态性异步性进程记录执行直接制约作业步作业控制块进程上下文就绪执行等待共享资源同步执行相关临界区时间分派策略执行速度静态动态进程并发执行系统处于安全状态就绪执行

15等信箱等信件16一个唯一的标识符和线程描述表分派给进程的主存地址空间17在有限的时间内得到全部资源死锁18不可抢夺资源环路等待

19生产者消费者问题社学家进餐问题20共享存储器系统消息传递系统管道通信系统21进程调度非剥夺方式剥夺方式22系统资源不足进程推进顺序不当23进程上下文24就绪运行等待25共享对方私有信息进程同步执行

第三章作业管理

一、单项选择题

1．用户可以使用（）编写控制作业执行步骤的作业说明书。A．操作控制命令B．作业控制语言C．作业启动命令D．窗口或菜单2．计算时间短的作业优先的调度算法会使（）A．每个作业等待时间较短B．平均周转时间最短C．系统效率最高D．长作业等待时间较短

3.实现批处理控制方式有作业控制卡和作业说明书，它们使用由系统规定的（）编制。A.系统调用B.原语C.作业控制语言D.机器语言

4.某作业（Job）对应的进程P，因请求I/O处于等待状态，则该作业（Job）处于（）状态。A.等待B.执行C.就绪D.输入

5.用作业控制语言编写作业控制说明书主要用在（）系统。

A．分时B．实时C．批处理D．多CPU

6.选择作业调度算法时，从系统角度，主要希望进入“输入井〞的作业的（）A．响应时间短B．平均周转时间短C．服务费用低D．优先权高的作业能优先得到服务7.．作业由输入状态转变为收容状态，是由（）程序完成的。A．作业调度B．设备调度C．预输入D．进程调度8.进程调度中先来先服务调度算法对以下哪种进程不公允：

A.长进程B.短进程C.繁杂进程D.简单进程9.以下作业输入方式中，需要在外存上开拓输入井和输出井的是：

A.联机输入方式B.脱机输入方式C.直接耦合方式D.SPOOLING方式10以下作业输入方式中，需要在外存上开拓输入井和输出井的是：

A.联机输入方式B.脱机输入方式C.直接耦合方式D.SPOOLING方式

11用户寻常利用键盘命令、系统调用命令请求操作系统服务，有时也会用（）A．宏指令B．汇编语言C．作业控制语言D．计算机高级语言二、多项选择题

1.属于PCB的信息有（）。

A．文件名B．进程名C．存取权限D．优先权E．物理位置

2．操作系统为用户提供的接口有（）。

A．操作控制命令B．系统调用C．作业控制语言D．键盘操作命令E．作业说明书

3.在以下各项中，操作系统提供的操作接口是（）A．窗口技术B．命令语言C．系统调用D．菜单技术E．访管指令4.以下关于线程的说法，正确的有（）。

A.引入线程是为了提高系统的执行效率，减少处理机的空转时间和调度切换时间B．线程是被系统独立调度和分派的基本单位C．线程自己基本上不拥有系统资源，但它可与同属一个进程的其它线程共享进程所拥有的全部资源

D．线程也称作轻权进程

E．同一个进程中的多个线程之间可以并发执行5．处理机调度可以分为（）。

A．作业调度B．交换调度C．进程调度D．线程调度E．设备调度

6．以下调度算法，可用于进程调度的有（）。A．FCFS调度算法B．轮转法C．优先级法D．最高响应比优先法E．LRU调度算法填空

1进程的五大特点是、、、和。2.作业由不同顺序相连的组成，是作业存在的唯一标志。3.PCB是标志。

4.系统将处于阻塞状态的进程依照_________组成不同的阻塞队列。5.PCB的组织方式有和。

6.操作系统为用户提供了两种作业控制方式，它们是___________和___________方式。简答题

1.什么叫“驱动调度〞？比较“最短寻觅时间优先〞算法和“电梯调度〞算法。

2.在单道批处理系统中，有四个作业到达输入井和需要的计算时间如表所示，现采用响应比最高者优先算法，忽略作业调度所化的时间。当第一个作业进入系统后就可开始调度。作业到达输入井时间需计算时间开始时间完成时间周转时间18︰002小时28︰3030分钟

39︰006分钟49︰3012分钟（1）填充表中空白处（2）四个作业的执行次序为__________________。

（3）四个作业的平均周转时间为__________________。

3.在单道批处理系统中，有四个作业进入系统，进入时间及所需计算时间如下表所示。现忽略作业调度所花时间。当第一个作业进入系统后就可开始调度。作业进入时间所需计算时间18∶002小时28∶3030分钟39∶006分钟49∶3012分钟（1）将分别采用“先来先服务〞和“短作业优先〞调度算法时，各个作业的开始时间，完成时间，周转时间分别填入下面的表中。先来先服务短作业优先作业开始时间完成时间周转时间开始时间完成时间周转时间1234（2）采用“先来先服务〞调度算法时，平均周转时间为。采用“短作业优先〞调度算法时，平均周转时间为。

4.设某作业共占有9个页面，假使在主存中只允许装入5个工作页面（即工作集为5），作业运行时，实际访问页面的次序是1，2，3，4，5，6，1，3，2，9，6，3，8，7，1，2，3。试用FIFO与LRU页面调度算法，列出各自的页面淘汰次序和缺页中断次数，以及最终留驻主存5页的次序。（假定开始的5个页面已装入主存）

5.某作业的程序需占用11个页面，若主存只能提供6个工作页面（即工作集为6），作业运行时实际访问页面的次序是1，2，3，4，5，10，3，2，4，6，5，7，4，3，8，11，2，1，9，4，10，9，6，4，9。现采用FIFO和LRU页面调度算法，列出它们的页面调度次序和缺页中断次数。答案：

单项选择1B2B3C4A5C6B7C8B9D10D11C多项选择1BDE2AB3BC4ABDE5ACD6ABCDE填空

1动态性并发性独立性异步性结构特征2作业步作业控制块

3.系统感知进程存在的4.队列5.线性表方式索引表方式链接表方式6.脱机控制联机控制

第四章：存储器管理一、单项选择题

1.存储管理中地址重定位必需在CPU中设置专门寄放器，而（）不是此类寄放器。A．基址寄放器B．界限寄放器C．页表控制寄放器D．程序计数器

2．在段式分派的存储管理中，最坏适应算法要求对空闲区表项按（）进行排列。A．尺寸从小到大B．尺寸从大到小C．地址从小到大D．地址从大到小3．段式存储管理中的地址格式是（）地址。A．线性B．一维C．二维D．三维4.单个分区的存储管理不适用于（）

A．个人计算机B．专用计算机C．单道程序系统D．多道程序系统5.．页式管理中的地址结构分页号和页内地址两部分，它（）

A．仍是线性地址B．是个二维地址C．是个三维地址D．是个四维地址6.在固定分区存储管理中，固定不变的是：

A.作业的长度B.分区的大小和数目C.作业的个数D.分区的状态

7.以下说法，正确的是：

A.每个内存空间对应着一个目标程序B.每个地址空间对应着一个目标程序C.规律地址和物理地址都是“实〞的概念D.内存空间和地址空间都是“实〞的概念8.虚拟存储器的容量取决于：（）

A．内存容量B．外存容量C．地址结构和寻址方式D．硬件的地址9.在固定分区存储管理中，可以改变的是：（）

A.分区的长度B.分区的数目C.分区的个数D.分区的状态10.要求可用表中的空闲区按大小递增的