02326自考操作系统2021年考前知识点总结

第一章 操作系统概论⭐

计算机系统是由 硬件系统 和 软件系统 组成的

操作系统的任务：组织和管理计算机系统中的硬件和软件资源、有效、合理、方便

操作系统为用户提供两类使用接口：分别是 编程接口、用户接口。

操作系统的特征：并发性、共享性、随机性

研究操作系统的观点：

1. 软件观点：外在特性--接口、内在特性--与硬件交互

2. 资源管理的观点

3. 进程的观点：把操作系统看作由多个可以同时独立运行的程序和一个对这些程序进行协调的核心所组成。

4. 虚机器观点：操作系统把原来的计算机（裸机）扩充成功能强大、使用方便的计算机系统，这种计算机系统被称为 虚拟计算机。

5. 服务提供者观点：提供了比裸机功能更强、服务质量更好、更方便灵活的虚拟机

操作系统的功能：进程管理、存储管理、文件管理、作业管理、设备管理

windows操作系统的体系结构采用了分层的模块结构，主要层次有：硬件抽象层HAL、内核、执行体、大量子系统集合

unix操作系统的体系结构，从内向外各层分别是 硬件层、操作系统内核层、系统调用层、应用层

Linux操作系统体系结构：Linux内核、Linux Shell、Linux文件系统、Linux应用程序

Android操作系统体系结构，从高到低：应用程序层、应用框架层、系统运行库层、Linux内核层

批处理操作系统：

1. 基本工作方式：用户将作业交给系统操作员，操作员收到一定数量的用户作业后组成一批作业，再输入到计算机中，这批作业在系统中形成一个连续的、自动转接的作业流。操作员然后启动操作系统，系统自动、依次执行每个作业，最后由操作员将执行完毕的作业结果交给用户。

2. 特点：成批处理，用户自己不能干预自己作业的运行。发现作业无法及时改正。

3. 优点：作业流程自动化较高、资源利用率较高、作业吞吐量大，从而提高了整个系统效率。

4. 缺点：用户不能直接与计算机交互，不适合调试程序。

分时系统：用户通过中断交互式向系统提出命令，系统采用时间片轮转方式处理服务请求。

特点：多路性、交互性、独占性、及时性

实时操作系统：需具备实时时钟管理、过载防护、高可靠性

嵌入式操作系统：微型化、实时性

操作系统结构研究的目标：系统模块化、模块标准化、通信规范化

常见的操作系统结构有：整体式结构、层次式结构、微内核（客户/服务器）结构

第二章 操作系统运行环境⭐⭐

处理器一般由 运算器、控制器、一系列的寄存器、高速缓存 构成。

处理器内通常有两类寄存器：

1. 用户可见寄存器：数据寄存器、地址寄存器、条件吗寄存器

2. 控制和状态寄存器：程序计数器PC、指令寄存器IR、程序状态字PSW

指令分为：访问存储器指令、算数逻辑指令、I/O指令、控制转移指令、处理器控制指令

特权指令：只能由操作系统使用的指令，用户不允许使用。

非特权指令：用户使用

处理器的工作状态分为：管态（内核态/系统态/特权态）、目态（用户态/普通态）

当处理器处于管态时，可执行全部命令，可使用所有资源，并具有改变处理器状态的能力

当处理器处于目态时，就只有非特权指令才能执行。

目态到管态的转换唯一途径是通过中断。

管态到目态的转换可通过设置PSW指令（修改程序状态字）

程序状态字PSW：指示处理器状态

包括以下状态代码：CPU的工作状态代码、条件码、中断屏蔽码

存储器的类型：读写型存储器RAM（存储随机存取的程序的数据）、只读存储器ROM

存储的最小单位“二进制”，存储器的最小编址单位是字节，内存空间的最小分配单位是块

存储分区的保护方法：界地址寄存器、保护键

例（1710 ）当每个程序在主存中占一个连续的存储空间时，系统使用那两个寄存器来实现存储保护？当处理器在目态下执行程序时，对每一个访问主存空间的地址都要进行核查，请写出访问地址与着两个寄存器值之间的关系。

答：基址寄存器、限长寄存器。基址寄存器的值<=访问地址<=限长寄存器的值

中断是由外部事件引发的，而异常是由正在执行的指令引发的。

典型的中断：时钟中断、输入输出（I/O）中断、控制台中断、硬件故障中断

典型的异常：程序性中断、访管指令异常

例（1904）中断和异常的区别是什么？请指出“时间片到时”、“算术溢出”、“掉电”和“虚拟存储中的缺页”分别属于中断和异常的哪一种？

答：中断是由外部事件引发的，异常是由正在执行的指令引起的。

中断：时间片到时、掉电。异常：算术溢出、虚拟存储中的缺页

例（1910）中断系统由哪两部分组成？请介绍计算机系统中典型的中断有哪些？

答：硬件中断装置和软件中断处理程序。I/O中断、时钟中断、硬件故障中断、程序性中断、系统服务请求（自愿中断）

典型的中断处理：I/O中断、时钟中断、硬件故障中断、程序性中断、系统服务请求（自愿中断）

I/O中断：一般由I/O设备的控制器或通道发出，可分为：I/O操作正常结束、I/O异常。

时钟中断：维护时钟软件、处理器调度、控制系统定时任务、实时处理

自愿性中断：用户通过访管指令调用系统调用

例（1804 ）什么是程序性中断？程序性中断都必须由操作系统来完成吗？举例说明。

答：程序性中断是指程序指令出错，指令越权或指令寻址越界而引发的系统保护。不一定，也可以由自己完成，如系统调试中断和算术错误等。

例（1810）什么是中断？如果同一中断级中的多个设备接口中同时都有中断请求时，如何处理？

答：中断是指处理器对系统中或系统外发生的异步事件的响应，如果同一中断级中的多个设备接口中同时都有中断请求时，可以采用固定优先数或轮转法

应系统调用的目的：请求系统服务

第三章 进程与线程⭐⭐⭐

程序的顺序执行：一各具有独立功能的程序独占处理器直到得到最终结果。

特点：顺序性、封闭性、程序执行结果的确定性、程序执行结果的可再现性

程序的并发执行：两个或以上程序同时处于已开始且尚未结束的状态。

特点：在执行期间并发程序相互制约、程序与计算不再一一对应、执行结果不可再现、程序的并行执行（宏观上同时）和程序的并发执行（微观上同时）

多道程序设计：

特点：独立性、随机性、资源共享性

缺陷：可能延长程序的执行时间、系统效率的提高有一定限度

进程：具有一定独立功能的程序在某个数据集合上的一次运行活动，是系统进行资源分配和调度的一个独立单位。

进程由 程序、数据、进程控制块 3部分组成

程序是动态的，进程是动态的，二者是多对多的关系。

进程的特性：并发性、动态性、独立性、交往性、异步性、结构性

三状态模型：运行状态、就绪状态、等待状态

五状态模型：运行状态、就绪状态、阻塞状态、创建状态、结束状态

七状态模型：

例（1804）在七状态进程模型中，什么是阻塞状态？什么是阻塞挂起状态？两个状态之间有何转换？

答：进程阻塞：进程在内存并等待某事件出现。阻塞挂起：进程在外存并等待某事件出现。当没有进程处于就绪状态或就绪进程要求更多内存资源时，会把进程从阻塞状态转为阻塞挂起。

进程控制块PCB是描述进程状态和特性的数据结构，PCB是进程存在的唯一标识，一个进程只能有唯一的进程控制块。

操作系统中每创建一个进程就要为该进程建立一个 进程控制块 ，一个刚被创建的进程，它的初始状态为 就绪态

PCB的内容：调度信息（描述进程当前状况）、现场信息（刻画进程的运行情况）

PCB组织方式：线性方式、索引方式、链接方式

进程控制：对进程在整个生命周期中各种状态之间的转换进行有效的控制。通过原语实现。

原语：原语是操作系统核心的一个组成部分，由若干条指令组成，用来实现某个特定的操作功能，执行时具有不可间断性。

进程控制原语：创建原语、撤销原语、阻塞原语、唤醒原语

阻塞原语过程：首先中断处理器的执行，把处理器的当前状态保存在PCB的现场信息中，然后把进程的当前状态置为等待状态，并把它插入到该事件的等待队列中。

唤醒原语过程：在等待队列中找到该进程，将进程的当前状态置为就绪状态，然后将它从等待队列中撤出并插入到就绪队列中排队，等待调度执行。

例（1810）进程控制通过进程控制原语开实现，请分别描述创建原语和撤销原语的操作过程。

答：（1）创建原语：先申请一个空闲PCB区域，将有关信息填入PCB，置该进程为就续状态，最后把它插入就绪队列中。

（2）撤销原语：找到要被撤销进程的PCB，将它匆匆所在队列中消去，撤销属于该进程的一切“子孙进程”，释放被撤销进程所占用的全部资源，并消去被撤销进程的PCB

线程：在引入线程的操作系统中，线程是进程中的一个 实体，是调度和分派的基本单位，进程是资源拥有的基本单位。线程自己基本上不拥有系统资源，只拥有少量在运行中必不可少的资源，但它可与同属一个进程的其他线程共享进程所拥有的全部资源。一个线程可以创建和撤销另一个线程，同一个进程中的多个线程之间可以并发执行。

线程的属性：

（1）每个线程有一个唯一的标识符和一张线程描述表

（2）不同的线程可以执行相同的程序

（3）同一进程中各个线程共享该进程的内存地址空间

（4）线程是处理器的独立调度单位，多个线程可以并发执行

（5）一个线程被创建后便开始它的生命周期，在生命周期内会经历等待状态、就绪态、

运行态等各种状态变化。

引入线程的好处：创建/结束一个新线程花费时间少、线程之间的切换花费时间少

在线程的两种实现方式中：用户级线程只存在于用户态中，与内核无关。内核级线程所有线程的创建、撤销、切换都由内核实现。

例（1710）请分别从资源分配、创建速度、通信、并行执行效率的角度简述多线程技术优势

答：（1）创建线程无需另外分配资源，而创建进程需分配资源

（2）因为创建线程无需分配资源，因此速度比创建进程快

（3）线程间通信在同一地址空间中进行，不需额外的通信机制，所以通信简单，信息传递速度更快。

（4）线程能独立执行，充分利用，发挥处理器与外围设备并行工作的能力。

进程调度：从就绪进程中选取一个进程，让它占用处理器

例（1910）什么是进程调度？在设计调度算法时通常使用吞吐量、周转时间和处理器利用率作为衡量指标，请解释吞吐量和周转时间的含义。

答：进程调度：即处理器调度，是指根据一定的调度算法，系统从就绪队列中选择一个进程，把处理器分配给它。

吞吐量：系统每小时完成的进程数量。

周转时间：指从一个批处理进程提交时刻开始直到该进程完成时刻为止的统计平均时间

处理器的调度方式分为 抢占式、非抢占式

调度算法的设计目标：资源利用率高、公平、平衡、强制执行策略

进程调度算法：

1. 先来先服务算法FCFS：进程按照它们请求处理器的顺序使用处理器。公平、简单

2. 最短进程优先算法SJF

3. 最短剩余时间优先算法SRTN

4. 最高相应比优先算法HRRF：响应比Rp=（等待时间+预计运行时间）/预计运行时间

= 周转时间/预计运行时间

5. 轮转算法RR

6. 最高优先级算法HPF

7. 多级反馈队列算法：综合先进先出、时间片轮转、可抢占式最高优先级算法

例（1904）什么是轮转调度算法？请分析时间片长短对算法性能的影响。

答：（1）轮转调度算法是指将处理器的处理时间划分成一个个时间片，就绪队列中的诸进程轮流运行一个时间片。当时间片结束时，就强迫运行进程让出处理器，该进程进入就绪队列，等待下一次调度。

（2）时间片太短，进程切换频繁，加重系统开销。时间片太长，引起对短的交互请求的响应时间变长。

系统内核：中断处理程序、进程同步与互斥、进程调度、控制与通信、存储管理、时钟管理

对内核的各种功能调用通过执行原语操作实现。

第四章 进程的同步与互斥⭐⭐⭐⭐

在逻辑上具有某种联系的进程称为相关进程，在逻辑上没有任何联系的进程称为无关进程

对于相关进程来说，可能有若干并发进程同时使用共享资源，形成交替使用共享资源，结果就会形成与时间相关的错误。

进程的同步：进程之间一种直接的协同工作关系，一些进程相互合作，共同完成一项任务。

进程的互斥：各进程间互斥的使用资源，是进程间的一种间接制约关系。

临界资源：一次只允许一个进程使用的资源。

临界区：在进程中访问临界资源的程序。

如果有若干进程共享某一临界资源，则该临界区称为相关临界区。

相关临界区的调度使用原则：有空让进、无空等待、多中择一、有限等待、让权等待

信号量：一个用于标识资源数目的整型量S。信号量是个被保护的量，只有P、V操作和信号量初始化操作才能访问和改变它的值。

PV操作是供进程调用，执行时不可中断的过程，操作系统通常称这种过程为 原语

P、V操作：

P(S)

{ S=S-1;

若S<0，将该进程状态置为等待状态，然后将该进程的PCB插入响应的S信号量等待队列末尾，直到有其他进程在S上执行V操作为止；}

V(S)

{ S=S+1;

若S<=0，释放在S信号量队列中等待的一个进程，将其状态改变为就绪态，并将其插入就绪队列；然后，执行本操作的进程继续执行；}

信号量S表示某类可用的临界资源。

当S>0时，S值的大小表示某类可用资源的数量。

当S<0时，S的绝对值表示排在S信号量的等待队列中进程的数目。

每执行一次P操作，意味着请求的进程分配到一个资源

每执行一次V操作，意味着进程释放了一个资源。

P、V操作在使用时必须成对出现；互斥操作时，它们同处于同一进程；同步操作时；不在同一进程；既有同步又有互斥时，同步P操作在互斥P操作前，V操作顺序无关紧要。

例 有m个进程共享一临界资源，若使用信号量机制来实现临界资源的互斥访问，则该信号量的最小取值是 1-m

例 用PV操作正确管理进程互斥使用某共享资源情况下，假定现在有n-1个进程（n>=3）

在等待使用资源，那么调用过p操作的进程数至少是n

一个管程由管程名称、共享数据说明、对数据进行操作的一组过程 和对共享数据赋初值的语句 四个部分组成。

管程能保障共享资源的互斥执行，即一次只能由一个进程可以在管程内活动。

管程定义了一个共享变量的数据结构，以及在该数据结构上所执行的一组操作。

管程的三个特性：模块化、抽象数据类型、信息隐蔽

管程中的共享变量 在管程外部是不可见的，外部只能通过调用管程中所说明的 外部过程（函数） 来间接的对其进行访问。

进程通信是一种高级通信方式，可以实现进程间交换大量信息

目前常用的通信方式有共享内存、消息机制、管道通信。这三种方式可以称为高级通信原语，它们不仅要保证相互制约的进程间的正确关系，还要同时实现进程之间的信息交换。

消息机制：消息缓冲通信、信箱通信、管道通信

第五章 死锁⭐⭐⭐⭐

死锁：是指一组进程中的每一个进程均无限期的等待被该组进程中的另一个进程所占有且永远不会释放的资源的现象。

死锁产生的两个原因：（1）竞争资源，系统资源分配不当，进程内对资源的相互争夺而造成僵局。（2）多道程序运行时，进程推进顺序不合理。

死锁产生的四个必要条件：互斥条件、不可剥夺条件、请求和保持条件、循环等待条件

只要发生死锁，则产生死锁的四个必要条件一定成立。

解决死锁的方法：预防死锁、避免死锁、检测与解除死锁、忽略死锁

1. 预防死锁：破坏产生死锁的四个必要条件之一。

资源的静态分配策略：

（1）若一个进程已占用了某些资源，在申请新的资源时，不能立即得到满足，在变为等待状态之前，该进程必须释放已有的资源。若一个进程申请某些资源，首先检查这些资源是否可用，如果可用，就分配给该进程。否则检查这些资源是否分配给某个等待进程，若是，则系统剥夺所需资源，分配给这个进程。此方法破坏了不可剥夺条件。

（2）每个进程在执行前就申请它所需的全部资源，仅当系统能满足要求且一次性分配资源后，该进程才能执行。此方法破坏了 请求和保持条件。

资源的有序分配法：对系统中所有资源顺序编号，规定任何一个进程申请两个以上资源时，按资源编号顺序申请，只有得到编号小的资源之后，才能申请编号大的资源。破坏了循环等待条件。

2. 避免死锁：系统对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源；如果分配后系统可能发生死锁，则不予分配，否则予以分配

操作系统能保证所有的进程在有限时间内得到需要的全部资源，则称系统处于安全状态

如果不存在任何一个安全序列，则系统处于不安全状态。不安全状态不一定导致死锁

但死锁状态一定是不安全状态。

银行家算法：确保系统处于 安全状态 时才把资源分配给申请的进程，避免发生死锁。

例（1904）简述死锁预防与死锁避免这两种死锁解决方法的含义

答：死锁预防是系统预先确定资源分配策略，这些策略至少能破坏死锁四个必要条件中的一个，进程按规定申请资源，系统按预先规定的策略进行分配，从而防止死锁的发生。

死锁避免是当进程提出资源申请时，系统先测试资源分配后系统的安全状态，仅当能确保系统安全时才把资源分配给进程，使系统一直处于安全状态之中，从而避免死锁。

3. 检测与解除死锁：

死锁检测的实质是通过检测是否存在循环等待条件以此来确定死锁的存在与否，并识别出与死锁有关的 进程和资源。

死锁检测的时机：（1）一次资源分配后、（2）每次调度后、（3）定时器定时运行检测、（4）当系统中某个进程长期位于阻塞状态或阻塞进程过多时。

死锁的解除：剥夺资源、撤销进程

资源分配图：判定死锁的法则，又称为死锁定理。

有向图SRAG=（⚪表示进程，方框表示每类资源，框中的圆点表示资源实例，申请边是从进程到资源的有向边，分配便是从资源到进程的有向边）

（1）如果资源分配途中没有环路，则系统没有死锁。

（2）如果资源分配图中出现了环路，则系统中可能存在死锁

（3）如果处于环路中的每个资源类中均中只包含一个资源实例，则环路的存在即意味着死锁的存在，此时，环路是死锁的充分必要条件。

（4）如果处于环路中的每个资源类中资源实例的个数不全为一，则环路是死锁的必要条件

资源分配图化简：

（1）在资源分配图中，找出一个既非等待又非孤立的进程结点P，运行后释放它所占的全部资源，使之称为孤立结点。

（2）将P所释放的资源分配给申请它们的进程

（3）重复（1）（2），直到找不到符合条件的进程结点。

经过化简后，若能消去资源分配图中的所有边，则该图是可完全化简的。系统的资源分配图是不可完全简化的，是死锁的充分条件。

例（1710）防止死锁发生时可采用什么策略来使循环等待资源的条件不成立？这个策略如何应用到5个哲学家就餐问题中？

答：对资源采用按序分配的策略，修改第5个哲学家的程序，即规定每个哲学家想吃面条时，总是从自己左右两旁的筷子中先取编号小的筷子，再取编号大的筷子，对于第5个哲学家，她必须先拿右边的筷子，再拿左边的。

例（1910）某系统中有10台打印机，有3个进程P1、P2、P3分别需要8台，7台和4台。若P1,P2，P3已申请到4台、2台、2台。试问：（1）系统目前还有几台可申请的打印机？各进程还需要几个打印机？（2）目前系统是否处于安全状态？为什么？

答：（1）目前系统还有2台可申请的打印机。进程P1,P2,P3分别需要4台、5台、2台。

（2）系统处于安全状态。根据目前的各进程资源分配情况，可以先分配2台打印机给进程P3达到它最大需要，然后P3释放其原来占有的打印机，系统就会有4台打印机，然后分配给进程P1达到它最大需求，这时系统有8台打印机，可满足进程P2最大需要，所以系统目前处于安全状态。

第六章 存储管理

存储管理的主要任务：内存的分配与回收、内存扩充、存储共享、存储保护

绝对地址对应的存储空间称为 物理地址空间，逻辑地址对应的存储空间称为逻辑地址空间

把逻辑地址转换成物理地址的过程称为 地址重定位/地址转换/地址映射

重定位的方式：动态重定位、静态重定位

动态重定位：在程序装入时 不进行 地址转换，而是直接将程序装入到分配的内存区域中，程序运行过程中，再将指令中的 逻辑地址 转换为绝对地址

地址动态重定位方式适用于 可变分区存储管理、页式存储管理、页式虚拟存储管理

静态重定位：地址转换工作是在 程序开始执行前 集中完成的

固定分区：把内存划分成若干个大小固定的分区，每个分区只装入一道作业

可变分区：系统不预先划分固定分区，而是在程序装入时划分内存分区，使为程序分配的分区的大小正好等于该程序的需求量，且分区的个数可变。可变分区有较大的灵活性，较之固定分区能获得较好的 内存利用率。

紧缩技术：通过移动内存中的程序，把 所有空闲碎片合并成一个连续的大空闲区且放在内存的一端，把 所有程序占用区 放在内存的另一端。

查找和分配空闲的分配算法：最先适应算法、最优适应算法、最坏适应算法

分区回收：若有相邻空闲区，则合并为一个。

例 在可变分区存储管理中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数-2的情况是，有上邻空闲区，也有下邻空闲区

分区的保护：保护键方法、设置界限寄存器

覆盖技术：把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构使哪些不会同时执行的程序段共享同一块内存区域。

交换技术：将系统中不再运行中的进程或其一部分从内存中调出，让出内存空间以调入其他需要内存空间的进程

采用覆盖技术与交换技术的目的是 节省内存空间以扩充内存。

虚拟存储技术：利用大容量的外存来扩充内存，产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间，简称虚存。

采用页式存储管理的目的是提高内存的利用率，采用虚拟存储技术的目的扩充内存容量

实现虚拟存储器需要以下的硬件支持：系统有容量足够大的外存。系统有一定容量的内存。最主要的是，硬件提供实现虚-实地址映射的机制。

虚拟技术同交换技术在原理上是类似的，其区别在于，交换技术是以进程为单位进行的，而虚拟存储一般以页为单位。

例（1810）虚拟存储器的工作原理是什么？

答：当进程开始运行时，先将程序的一部分装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，系统自动完成将它们从外存调入内存的工作，当没有足够的内存空间时，系统自动选择部分内存空间，将其原有的内容交换到磁盘，并释放这些内存空间，供该进程或其它进程使用。

页式存储器提供编程使用的虚拟地址由两部分组成：虚拟页号、页内地址

例（1804）简述虚拟页式存储的优缺点。

答：优点：由于其不要求进程的程序段和数据在内存中连续存放，从而有效解决碎片问题。既提高内存利用率，又有利于组织多道程序执行。缺点：存在页面空间的浪费问题。

位示图：用于磁盘空间管理

物理页面号（块号）= 字号*字长+位号

字号=块号/字长， 位号=块号mod 字长

例 使用8个字（字长32位）组成的位示图来管理页式主存空间的分配与回收，0表示空闲，1表示占用。假定将 位示图中字号为4，位号为5的空闲块分配储区，则该块的块号是 133

页表：程序虚拟地址中的页号到物理页面号之间的对应关系。

物理地址（页帧/页框号）=物理页面号*块长+页内地址

转换检测缓冲区（TLB/快表）TLB只存储当前进程中最活跃的少数活动页面的页号，随着进程的推进，TLB的内容 动态更新

如果刚被调出的页面又立即要用，因而把它装入，装入不久又被选中调出，调出不久又被装入，如此反复，使调度非常频繁，这种现象称为“抖动”或“颠簸”

页面置换算法：理想页面置换算法OPT、先进先出页面置换算法FIFO、最近最少使用页面置换算法LRU

缺页率：缺页数/访问页面总次数

影响缺页率的因素：分配给程序的物理页面数、页面的大小、程序编制方法、页面调度算法

第七章 文件系统

文件系统的主要目的：是为用户提供 按名存取的功能

文件：一组带标识的、在逻辑上有完整意义的信息项的序列。

文件系统：操作系统中统一管理信息资源的软件。

外存储设备：

磁带：存储容量大，读取速度慢，只能进行顺序存取。

例（1804）假定某系统中，磁带的记录密度为每英寸800个字符，每个逻辑记录长为160个字符，块与块之间的间隙为0.5英寸。现有600个逻辑继续需要存储到磁带上，请问：（1）如果不采用成组操作，磁带空间的利用率是多少？（2）在采用6个逻辑记录为一组的成组操作时，磁带空间的利用率是多少？

答：（1）每个逻辑记录需占用160/800=0.2英寸，利用率：0.2/（0.2+0.5）=28.57%

（2）（6*160）/800=1.2英寸，利用率：1.2/（1.2+0.5）=70.59%

磁盘：存储容量大，成本低，随机存取

光盘：非磁记录介质，容量大，速度快，价格便宜，一般不可写

闪存：电可擦除，可随机存取，可靠性高

文件的存取方式：由文件的性质和用户使用文件的情况而确定。

常用的文件存取方式：顺序存取 和随机存取 两种。

文件的分类：

按文件的用途分类：系统文件、用户文件、库函数文件

按文件的组织形式分类：普通文件、目录文件、特殊文件

按保护方式分类：只读文件、读写文件、可执行文件、无保护文件

按信息的流向分类：输入文件、输出文件、输入输出文件

按案件的存放时限：临时文件、永久文件、档案文件

按文件的组织结构分类：顺序文件、链接文件、索引文件

UNIX系统中文件分类：普通文件、目录文件、特殊文件（UNIX把I/O设备看成是特殊文件）

文件的逻辑结构：用户看到的文件的组织结构。

按逻辑结构把文件划分成三类：无结构的字符流式文件、定长记录文件、不定长记录文件

文件的物理结构：文件在实际的存储空间存储时的结构。

常用的文件物理结构有：顺序结构、链接结构、索引结构

1. 顺序结构：把逻辑上连续的文件信息依次存放在连续编号的物理块中，支持顺序存取和随机存取。优点对于顺序存取存取速度快，缺点文件不能动态增长。

2. 链接结构：将逻辑上连续的文件分散存储在若干不连续的物理块中。在每个物理块中都设有一个指针，指向其后续需的物理块。优点解决碎片问题，有利于文件动态扩充，提高了磁盘空间利用率。缺点存取速度慢，不适于随机存取文件，可靠性差。

3. 索引结构：把每个物理盘块的指针字集中存储在称为索引表的数据结构中的内存索引表

中。优点适用顺序存取和随机存取，满足文件动态增长，满足文件插入、删除的要求。缺点会引起较多的寻道次数和寻道时间，索引表本身增加了存储空间的开销。

每个索引文件都有一个索引表，索引表的条目包含文件的逻辑块号 及所对应的物理块号

文件控制块FCB：为了实现按名存取，操作系统给每个文件都设置了一个描述性数据结构，即文件控制块，它是文件存在的标志。把所有文件的描述性数据结构组织起来，就构成了文件目录。一个FCB就是一个目录项

一级目录结构：简单，容易实现。不能重名，搜索效率较低

二级目录结构：第一级为主文件目录，给出用户名和用户子目录所在物理位置。第二级为用户文件目录，给出该用户所有文件的FCB。解决文件重名问题、实现用户间的文件共享

多级目录结构/树型目录：搜索速度快、同一子目录下文件名不能重复、有利于文件保护

例（1704）简述设置文件目录的主要目的以及目录项中包括的主要内容

答：目的：实现按名存取。包含：有关文件存取控制的信息；有关文件结构的信息和有关文件管理的信息。

磁盘空间的分配回收算法：位示图、空闲块表、空闲块链表、空闲块成组链接法

系统打开文件表：专门用于保存已打开文件的文件控制块，通常放在内存。

典型的文件操作：1.建立文件 2.打开文件 3.读文件 4.写文件 5.关闭文件 6.删除文件

打开文件：是使用文件的第一步，把文件控制块PCB送到内存

记录的成组：把若干个逻辑记录合成一组存储一物理块。每块中的逻辑记录个数称为块因子

记录的分解：从一组逻辑记录中把一个逻辑记录分离出来。

记录的成组和分解技术是磁盘高速缓存的一种应用，具有提高存储空间利用率和减少启动设备次数的优点。

文件共享：一个文件可以允许多个用户共同使用

引起文件破坏丢失的可能原因：灾祸、硬件或软件故障、人为出错

保护文件的方法： 建立副本、定时转储

常用的保护文件内容方法：对用户的存取权限实施控制。当用户数目和文件数目不多时，可以用存取控制矩阵方式，但是当文件和用户较多时，为了减少空间和时间开销，则采用二级存取控制方式。

文件保密的目的：防止不经文件拥有者授权而窃取文件。

常用文件保密措施：隐蔽文件目录、设置口令、使用密码、病毒防范

第八章 I/O设备管理

I/O设备分类：

1. 按设备使用特性分类：输入设备、输出设备、交互式设备、存储设备

2. 按设备信息组织方式分类：字符设备、块设备

3. 按设备可共享性分类：独占设备、共享设备、虚拟设备

虚拟设备：在一类设备上模拟另一设备，被模拟的设备为虚拟设备。目的：提高设备利用率。

I/O硬件组成：物理设备、电子部件

I/O软件组成：中断处理程序、设备驱动程序、设备独立的操作系统软件、用户级软件

设备独立性：设计I/O软件的一个最关键的目标

例（1910）什么是设备独立性？实现设备独立性的好处是什么？

答：设备独立性就是应用程序独立于具体使用的物理设备。好处：提高设备管理软件的设计效率，当I/O设备更新时，不需要重新编写全部软件。

I/O设备控制方式：程序控制方式、中断控制方式、DMA控制方式、通道控制方式。

1. 程序控制方式PIO：由用户进程直接控制处理器与外围设备之间信息传送的方式，也称为忙-等方式、轮询方式、循环测试方式。这种方式的控制着是用户进程。优点：处理器和外设的操作能通过状态信息得到同步，硬件结构简单。缺点：处理器效率低，无实时响应能力

2. 中断控制方式：发生异常事件时调用相应处理程序进行服务的过程。优点：提高计算机效率、可靠性，具有实时响应能力。

3. DMA（直接访问内存）控制方式：完全由硬件执行I/O数据交换，直接在内存和I/O设备之间进行。优点：传输速度快，减少处理器开销，效率高。

4. 通道控制方式：目的：进一步减少数据输入输出对整个系统运行效率的影响。

一个系统中可设立三种类型的通道：选择通道、数组多路通道、字节多路通道。

例 （1704）解释通道命令、通道程序、通道地址字和通道状态字。

答：通道命令：规定的设备一种操作的命令。通道程序：若干条通道命令组成的程序，由通道执行，完成一次I/O操作。通道地址字：用来存放通道程序首地址的主存固定单元。通道状态字：用来记录通道程序执行结果的主存固定单元。

例（1904）请回答通道有哪三种类型？简述三类通道的优缺点。

答：通道的三种类型是：选择通道、数组多路通道、字节多路通道。选择通道优点是以数据块为单位传输，传输效率高，缺点是通道利用率低。数组多路通道优点是以数据块为单位进行传输，传输率高，具有多路并行操作的能力，通道利用率高，缺点是控制复杂。字节多路通道优点是具有多路并行操作能力，缺点是以字节为单位传输，传输效率低。

设备分配算法数据结构包含四张表：系统设备表、设备控制表、控制器控制表、通道控制表

设备的绝对号：系统为每一台设备确定一个编号

设备的相对号：由用户在程序中定义的设备的编号

指定设备的方式：1. 绝对号 2. 设备类、相对号

为了提高设备分配的灵活性，用户用“设备类、相对号”来提出使用设备的要求；用户程序中所指定的设备可与实际能占用的设备无关。

磁盘调度：

执行依次输入输出所花的时间：寻找时间、延迟时间、传送时间

块号b=扇区k+扇区数s*（磁头j+柱面i*磁道数t）

柱面号=第p块/（扇区数*磁道数）

磁头号=（第p块 mod （扇区数*磁道数））/扇区数

扇区号=（第p块 mod （扇区数*磁道数））mod 扇区数

移臂调度：根据访问者指定的柱面位置来决定执行次序的调度

移臂调度的目的：尽可能减少操作中的寻找时间

常用的移臂调度算法：先来先服务调度算法、最短寻找时间调度算法、电梯调度算法、单向扫描算法。

旋转调度：根据延迟时间来就决定执行次序的调度。

缓冲的 引入：为了缓解I/O设备与CPU速度的不匹配问题

缓冲技术分为：单缓冲、双缓冲、多缓冲、缓冲池

SPOOLing技术：同时的外部设备联机操作，也称为假脱机技术。

SPOOLing系统包括：输入程序模块、输出程序模块、作业调度程序三部分。

SPOOLing：把独占设备改造成了共享设备，从而提高了设备的利用率和系统效率。

综合题：

1. P、V操作：

例（1804）在多个生产者-消费者问题中，设置信号量mutex，初值为1，用于实现临界区（唤醒缓冲池）的互斥；信号量empty，初值为k，用于标识缓冲池中空缓冲区的数目；信号量full，初值为0，用于标识缓冲区中产品的数目。另设整形变量i和j，初值均为0，i表示空缓冲区的头指针，j表示有产品缓冲区的头指针。

生产者进程P1,P2,....,Pa；

i=0;

While(true){

生产一个产品；

P(empty)；

P(mutex);

往Buffer[i]中放一个此产品；

i=(i+1) mod k;

V(mutex);

V(full); }

消费者进程Q1,Q2,....,Qm；

j=0;

While(true){

P(full);

P(mutex);

从Buffer[j]中取一个产品；

j=(j+1) mod k;

V(mutex);

V(empty);

消费一个产品；}

例（1704）若有一个文件F，供多进程读。现把进程分成A,B两组，规定同组的进程可以同时读文件F，但不同组的进程不能同时读文件F。现定义两个计数器C1和C2分别记录A组和B组中正在读文件F的进程数。当用PV操作进行管理时设置三个信号量S1、S2、SAB才能保证正确并发执行，程序结构如下：

Begin

Process Bj(j=) //B组读进程

S1,S2,SAB: semaphore; Begin

C1,C2: integer; P(S2);

S1:=1; S2:=1; SAB:=1; C1:=0; C2:=0; C2:C2+1;

Cobegin If C2=1 then P(SAB);

V(S2);

Process Ai(i=1,2,...) //A组读进程

Begin Read file F;

P(S1); P(S2);

C1:=C1+1; C2:=C2-1;

If C1=1 then P(SAB); If C2=0 then V(SAB);

V(S1); V(S2);

Read file F; End;

P(S1); Coend;

C1:=C1-1; End;

If C1=0 then V(SAB);

V(S1);

End;

(1) 说明信号量S1,S2,SAB的作用。

答：S1是对计数器C1的互斥信号量，S2是对C2互斥信号量，SAB是AB两组的互斥信号量

例（1904）桌上有一空盘，只允许存放一个水果，爸爸可向盘中放苹果或橘子，儿子专吃盘中的橘子，女儿转持盘中的苹果。规定当盘空时一次只能放一个水果供吃者取用。程序如下

Semaphore s1=1; semaphore s2=0; semaphore s3=0;

爸爸进程：

While(true){

P(s1);

If(放入的是苹果) V(s2);

Else V(s3); }

女儿进程：

While (true){

P(s2);

从盘中取苹果；

V(s1);}

儿子进程：

While(true){

P(s3);

从盘中取橘子；

V(s1);}

2. 进程算法：

例（1904）某单CPU系统有如下一批处于就绪状态的进程

（1）给出在先来先服务FCFS算法和最短进程优先SJF算法下各进程的各时间填表

（2）计算在 各算法下的平均周转时间。

FCFS SJF

进程进入就运行绪队列的先时间

开始时间 完成时间 周转时间 开始时间 完成时间 周转时间

后顺序

1

2

3

4

5

10

1

2

1

5

0

10

11

13

14

10

11

13

14

19

10

11

13

14

19

9

0

2

1

4

19

1

4

2

9

19

1

4

2

9

(2) FCFS: (10+11+13+14+19)/5=13.4 SJF: (19+1+4+2+9)/5=7

3. 缺页：

例（1904）某程序在内存分配三个页面，初始为空，所需页面的走向为0、1、2、3、0、1、4、0、1、2、3、4，请给出分别采用先进先出页面置换算法 FIFO和最近最少使用页面置换算法LRU时的页面置换过程，并计算相应的缺页次数及缺页率。

FIFO：

页面走向

时间短-页

时间中-页

时间长-页

是否缺页

LRU:

页面走向

时间短-页

时间中-页

时间长-页

是否缺页

0

0

1

1

0

2

2

1

0

3

3

2

1

是

0

0

3

2

是

1

1

0

3

是

4

4

1

0

是

0

0

4

1

1

1

0

4

2

2

1

0

是

3

3

2

1

是

4

4

3

2

是

0

0

1

1

0

2

2

1

0

3

3

2

1

是

0

0

3

2

是

1

1

0

3

是

4

4

1

0

是

0

4

1

0

1

4

1

0

2

2

4

1

是

3

3

2

4

是

4

3

2

4

是 是 是

是 是 是

FIFO：缺页9次，缺页率9/12=75%。LRU：缺页10次，缺页率10/12=83.3%

4. 调度算法

例（1804）假设磁盘有500个柱面，编号从0到499.当前磁头在190柱面上，并刚刚完成121柱面的请求。现有等待访问磁盘的柱面号依次为418、134、331、18、59、211、417、152、313、157.分别给出使用先来先服务调度算法、最短寻找时间优先调度算法、电梯调度算法进行磁盘调度时，磁头移动的顺序和移动的柱面总数。并回答对本题而言，哪个算法移动的柱面数最少。

答：（1）先来先服务：移动顺序190->418->134->331->18->59->211->417->152->313->157

移动的柱面总量：228+284+197+313+41+152+206+265+161+156=2003

(3) 最短时间：移动顺序190->211->157->152->134->59->18->313->331->417->418

移动的柱面总数：21+54+5+18+75+41+295+18+86+1=614

（3）电梯：移动顺序190->313->331->417->418->211->159->152->134->59->18

移动的柱面总数：123+18+86+1+207+54+5+18+75+41=628

最短寻找时间优先调度算法移动的柱面数最少。

5. i结点

例（1910）某UNIX操作系统采用i结点管理文件的存储空间，假设i结点包括13个地址项，其中10个地址用来存直接地址，一个地址项存一重间接地址，一个地址项存二重间接地址，一个地址项存三重间接地址。每个磁盘块地址占64位（8个字），磁盘块大小为2048字节，如果要存取某文件的字节偏移量1260000，请问，需要读取几次硬盘？写出中间过程。

答：12660000/2048=615.234 因此地址在第615个盘块中。

去掉10个直接地址615-10=605

一个一重间接地址，每个盘块大小为2048字节，每个地址项占8个字节，所以每个组中可以存放256个盘块号，605-256=349

一个二重间接地址，能存放256个一重间接地址，第一个一重间接地址，放256个盘块号，所以是放在第二个一重间接地址中。

所以，需要先读取该文件的i结点的盘块，访问一次一重间接地址的盘块，访问一次二重间接地址的盘块，在访问1260000地址的盘块，所以，供需要访问磁盘4次。

例（1904）某UNIX操作系统采用i结点管理文件的存储空间，假设磁盘块大小为2048字节，每个地址占64位（8个字节），i结点包括13个地址项，其中10个地址用来存直接地址，一个地址项存一次间接地址，一个地址项存二次间接地址，一个地址项存三次间接地址。请问，系统能管理的单个文件最大长度是多少？

答：10个直接地址表示的文件大小为：10*2KB=20KB

一个一次间接地址，每个 盘块大小为2KB，每个地址项占8个字节，所以每个硬盘块中可以存放256个盘块号，所以能存放的文件大小为256*2KB=512KB

一个二次间接地址，共能存放256*256个盘块号，能存放的文件大小为256*256*2KB=128MB

一个三次间接地址，共能存放256*256个盘块号，能存放的文件大小为256*256*256*2KB=32GB

所以一个文件的最大长度=20KB+512KB+128MB+32GB