【计算机考研复试】操作系统

操作系统

---

第一章 OS概述

*1.1 概念和功能

概念：操作系统是指控制和管理整个计算机系统硬件和软件资源的最基本的系统软件。
功能：（计算机系统自下而上分为：硬件、操作系统、应用程序、用户）
    向上提供接口（用户：命令接口，编程员：程序接口）；
    对下层功能的拓展；
    对系统资源的管理（处理机、存储器、文件、设备）。

*1.2 特征

并发性：指两个或多个事件在同一时间间隔内发生；（并行性：在同一时刻…）
共享性：系统中的资源可供内存中多个并发执行的进程共同使用；
虚拟性：把一个物理上的实体变成若干个逻辑上的对应物；
异步性：进程的执行并不是一气呵成的，而是以不可预知的速度向前推进.

1.3 运行机制

CPU的两种状态
用户态（目态）：不可以执行特权指令
内核态（管态）
CPU“变态”的唯一条件： 中断/异常
实现“变态”的机制：通过硬件实现

1.4 中断和异常

中断（外中断）：指来自CPU执行指令以外的事件发生；（如设备发出的I/O结束中断）
异常（内中断、trap）：指源自CPU执行指令内部的事件.（如地址越界，算术溢出）

1.5系统调用

概念：指用户在程序中调用OS所提供的一些功能。
目的：用户必须通过调用系统调用才能操作系统资源（OS代为完成），以保证系统稳定性和安全性。

1.6处理器为什么要区分核心态和用户态？在什么情况下进行两种方式的切换？

区分执行态的主要目的时保护系统程序。用户态到核心态的转换发生在中断产生时，而核心态到用户态的转换则发生在中断返回用户程序时。

---

---

第2章 进程管理

2.1 进程的概述

概念：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
组成：
    PCB：进程存在的唯一标志
    程序段
    相关数据段
引入进程的目的：
为了更好地使多道程序并发执行，提高资源利用率和系统吞吐量。
特征：
    动态性：进程是程序的一次执行过程。进程是动态的，程序是静态的；
    并发性：多个进程同时存在于内存中，能在一段时间内同时运行。引入进程的目的就是为了使程序能够并发运行；
    独立性：进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。而程序不能作为一个独立的单位参与运行
    异步性：异步性导致执行结果的不可再现性，因此OS中必须配置进程同步机制；
    结构性：每一个进程都配置一个PCB对其进行描述。

2.2 进程的通信

方式：
低级通信方式：PV操作
高级通信方式：共享存储、消息传递、管道通信

2.3 线程

概念：线程时进程中的一个实体，是被系统独立调度和分派的基本单位。 
引入线程的目的：
为了减小程序在并发执行的过程中所付出的时空开销，提高操作系统的并发性能。

2.4 线程与进程的比较

比较	进程	线程
调度	仅是资源分配的基本单位	独立调度、分派的基本单位
并发性	仅进程间并发	进程间、线程间并发
拥有资源	资源拥有的基本单位	基本上不拥有资源
系统开销	创建、撤销、切换开销大	仅保存少量寄存器内容，开销小

线程的实现方式：
    用户级线程：线程的管理工作都由应用程序完成，应用程序通过使用线程库实现多线程程序；
    内核级线程：线程的所有工作由内核完成。

2.5 处理及调度？

处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法选择一个进程，并将处理机分配给它运行。
调度方式：非抢占式、抢占式
调度的性能准则：
    CPU利用率：应该尽量使CPU处于“忙”状态；
    系统吞吐量：表示单位时间内系统完成作业的数量；
    周转时间：作业从提交到完成的时间；
    等待时间：处于等处理机状态的时间；
    响应时间：从用户提交到系统首次响应。
调度算法：
    FCFS、SJF、优先级、高响应比、时间片轮转、多级反馈队列

2.6 进程同步与互斥

同步（直接制约关系）：指为完成某种任务而简历的两个或多个进程，这些进程因需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。
互斥（间接制约关系）：当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许去访问此临界资源。
临界资源：一次仅允许一个进程使用的资源，必须互斥访问；
临界区：每个进程中，访问临界资源的那段代码。（进入区、临界区、退出区、剩余区）
实现进程互斥的方法
软件实现方法：在进入区设置并检查一些标志来标明是否有进程在临界区中，若有，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。
硬件实现方法：
中断屏蔽法：使用“开/关中断”指令，禁止一切中断的发生，只适合单CPU、OS内核进程；
硬件指令法（TSL/Swap）：原子操作，适合多处理机。

*2.7 举例解释一下同步和互斥

同步表现为直接制约，如管道通信，一个进程写，一个进程读，它们是相互制约的。
互斥表现为间接制约，比如多个进程同时请求打印机（无SPOOLing技术时）

2.8 原语？

原语是指完成某种功能且不被分割、不被中断执行的操作序列。

*2.9 管程？

管程是由一组局部变量、对局部变量进行操作的一组过程和对局部变量进行初始化的语句序列组成。引入的原因是因为P/V操作太过分散，对它的维护很麻烦且容易造成死锁。
组成：
    局部于管程的数据结构；
    对数据结构进行操作的函数过程；
    数据结构的初始化。
基本特性：
局部于管程的数据只能被局部于管程的过程所访问；
一个进程只能通过调用管程内的过程才能进入管程访问共享数据；
每次仅允许一个进程在管程内执行某个内部过程。

*2.10 死锁？

定义：
    多个进程因竞争资源而造成的一种互相等待的局面，若无外力作用，这些进程将无法向前推进。
产生的原因：
    系统资源的竞争、进程推进顺序不当。
产生的必要条件：
    互斥条件、不可剥夺条件、请求并保持条件、循环等待条件
死锁的处理策略：
    死锁预防：设置某些限制条件，破坏死锁的4个必要条件中的一个或几个，以防止死锁的发生；
    死锁避免：在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁；
    死锁的检测与解除：通过系统的检测机构及时地检测出死锁的发生，然后采取某些措施解除死锁。
死锁预防：
    破坏互斥条件：使系统资源都能共享；
    （这种方法不太可行）
    破坏不剥夺条件：当进程已保持了一些不可剥夺资源且又申请新的资源而得不到满足时，它必须释放已经保持的所有资源，待需要时重新申请；
    （这种方法实现复杂，会增加系统开销，降低系统吞吐量）
    破坏请求并保持状态：进程在运行前一次性申请完他所需要的全部资源；
    （这种方法实现简单，但是会严重浪费系统资源，还会导致饥饿现象）
    破坏循环等待状态：给系统中的资源编号，规定每个进程必须按照编号递增的顺序请求资源，同类资源一次申请完；
    （这种方法限制了新类型设备的增加，给用户编程带来麻烦）
避免死锁
概念：进程可以动态地申请资源，但系统在进行资源分配前，需要先计算此资源分配的安全性，若此次分配不会导致系统进入不安全状态则分配，否则让进程等待。

安全序列：
    指系统能按照某种顺序为每个进程分配其所需的资源，直到满足每个进程对资源的最大需求，使得每个进程都可以顺利完成。
（并非所有的不安全状态都是死锁状态，反之，只要系统处于安全状态，就不会进入死锁状态）
死锁的检测与解除
资源分配图
死锁定理：死锁的条件是当且仅当资源分配图是不可完全简化的。
死锁解除

*2.11 什么是安全状态？当系统不安全时就是系统进入了死锁状态吗？

安全状态是指系统按照某种进程顺序，为进程分配资源，使得每个进程都能获取所需的最大资源，并顺利完成。
不是，但是死锁状态一定是不安全状态。

2.12 简述银行家算法？

银行家算法是最著名的死锁避免算法，其思想是：避免系统进入不安全状态。在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，若有则先进行分配，并对分配后的新状态进行安全性检查。若新状态安全，则正式分配上述资源，否则拒绝分配上述资源。这样，它保证系统始终处于安全状态，从而避免了死锁现象的发生。

*2.13 简述进程和程序的区别。

进程和程序是既有联系又有区别。
主要区别：
1.程序是指令的有序集合，其本身没有任何运行的含义，它是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态概念。
2.程序的存在是永久的，而进程则是有生命的，它因创建而产生，因调度而执行，因得不到资源而暂停，因撤销而消亡。
3.程序仅是指令的有序集合。而进程则是由程序、数据和进程控制块组成。

---

---

第三章 内存管理

3.1 内存管理的功能

内存的分配与回收
地址转换
内存空间的扩充
存储保护

3.2 进程运行的基本原理

从写程序到程序运行
生成源代码文件
    编译：编译程序将源代码编译成若干的目标模块；
    链接：由链接程序将目标模块与所需库函数链接成一个完整的装入模块；
    装入：由装入程序将装入模块装入内存运行。
三种链接方式（生成逻辑地址）：
    静态链接：在 程序运行之前链接成一个可执行程序；
    装入时动态链接：在装入内存时，采用 边装入边链接的方法；
    运行时动态链接：在程序 运行时需要该目标模块再链接。便于修改和更新，有利于目标模块的共享。
三种装入方式（生成物理地址）：
    绝对装入：在单道程序环境下，编译时知道程序的实际存储位置，则编译时产生绝对地址的目标代码，即 逻辑地址与物理地址相同；
    可重定位装入（静态重定位）：在多道程序环境下，目标模块的起始地址通常是从0开始，装入时，将目标程序的逻辑地址 一次性换为物理地址；
    动态运行时装入（动态重定位）：程序可以可以在内存中发生移动，需要设置一个重定位寄存器，装入时，目标程序的逻辑地址 不需要立即转换为物理地址，可以需要的时候再换。

3.3 内存扩充：覆盖与交换

覆盖技术：
    基本思想：将用户空间分为一个固定区和若干个覆盖区。
    固定区：存放最活跃的程序段，程序运行时不会调入调出；
    覆盖区：不会被同时访问的程序段共享一个覆盖区，根据需要进行调入调出；
    特点：打破了必须将一个进程的全部信息装入内存后才能运行的限制。
交换技术：
    基本思想：（中级调度时采用）
    换出：内存紧张时，将处于等待状态的进程从内存调到辅存；
    换入：把准备好竞争CPU的进程从辅存移到内存中。
    特点：把磁盘空间分为文件区和交换区
二者区别：
覆盖技术常用于 同一个程序或进程中，而交换技术则在 不同进程或程序之间进行；
覆盖技术必须由程序员声明覆盖结构，使得对用户和程序员 不透明。

3.4 连续内存分配

概念：为一个用户程序分配一个连续的内存空间。
三种方式：单一连续分配、固定分区分配、动态分区分配
单一连续分配：
    只支持单道程序，内存分为系统区和用户区；
    无外部碎片，有内部碎片；
    可以采用 覆盖交换技术。
固定分区分配：
    支持多道程序，内存分为若干固定分区；
    无外部碎片，有内部碎片；
    为分区建立一张 分区说明表，分区大小可以相等或不等。
动态分区分配：
    特点：
    支持多道程序，根据进程大小动态分区；
    无内部碎片，有外部碎片；
    外部碎片采用 “紧凑”技术得以解决：操作系统不时的对进程进行移动和整理，需要采用 动态重定位寄存器。

3.5 4种动态分区分配算法：

首次适应：地址递增，顺序查找；
最佳适应：容量递增，依次查找；
最坏适应：容量递减，依次查找；
邻近适应：在首次适应的基础上，按照从上次结束的位置进行依次查找。

3.6 非连续分配管理

概念：
为一个用户程序分配不连续的内存空间。
基本方法：分页存储管理、分段存储管理
分页存储管理
    分页的原理：把主存空间划分为大小相等且固定的块，作为主存的基本单位；每个进程也以块为单位划分，进程执行时，以块为单位申请内存空间。
基本地址变换机构
    具有快表的地址变换机构：先到高速缓冲寄存器中找，再去内存中的页表里找，减少了访存次数；
    两级页表：页表存放在内存中，若大量无用的页表存放在主存中会造成内存浪费，因此建立多级页表，其目的在于建立索引，以便不浪费主存空间去存储无用的页表项，也不用盲目的顺序式查找页表项。
分段存储管理
    分段的特点：将地址空间按程序自身逻辑分段；每个段在内存中占连续空间，各段可不相邻。

*3.7 分段和分页的主要区别：

目的：分页的为了满足系统管理的需要，分段是为了满足用户的需要；
大小：页的大小是固定的，段的大小是不固定的；
维度：页的地址是一维的，段的地址是二维的；
碎片：分页有内部碎片无外部碎片，分段有外部碎片无内部碎片。

3.8 虚拟内存、虚拟存储器？

局部性原理：
    时间局部性：当前所访问的数据，很可能再次被访问；
    空间局部性：当前所访问的存储单元，其周围的存储单元很可能下次被访问。
虚拟存储器的定义和主要特性：
    定义：基于局部性原理，系统利用部分调用、请求调入、置换功能，好像为用户提供了一个比实际内存大得多的存储器；
    主要特性：
        多次性：作业无须一次调入，允许分多次调入内存；
        对换性：作业在运行过程中无须常驻内存，可以根据需要进行换入换出；
        虚拟性：从逻辑上扩充内存容量。
虚拟内存技术的实现：
    三种方式：请求分页存储管理、请求分段存储管理、请求段页式存储管理
    硬件支持：页表机制、缺页中断机构、地址变换机构

3.9 请求分页管理方式

请求分页系统建立在基本分页系统的基础上，为了实现虚拟存储功能而增加了请求调页功能和页面置换功能。
页表机制：
    在基本分页系统的基础上增加了4个字段：
    状态位：用于指示该页是否已经调入内存；
    访问字段：用于记录本页在一段时间内被访问的次数，供置换算法参考；
    修改位：标记在调入内存后该页是否被修改过；
    外存地址：用于指出该页在外存上的地址，供调入页面时参考。
缺页中断机构：
    在请求分页系统中，当所要访问的页面不在内存中时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。
地址变换机构：
    找到页表项要检查页面是否在内存中；若在，则修改页表项中的访问位，得出物理地址，若不在，请求调页，调入时，若内存不够，进行页面置换。

*3.11 试述缺页中断与一般中断有何区别？

缺页中断的处理过程与一般中断相似。
主要区别：
1.在指令执行期间产生和处理中断信号。
2.一条指令在执行期间可能产生多次缺页中断。

3.12 页面置换算法

最佳置换算法：淘汰的页面时未来最长时间不会被使用的；
先进先出算法：优先淘汰最先被调入的页面；
最近最久未使用算法：优先淘汰最近最长时间为被访问的页面；
时钟置换算法（最近未用算法）：循环扫描缓冲区，优先淘汰未使用过的页面。
改进的时钟算法：循环扫描缓冲区，若有未使用过的页面，则当然首先把它换出，若全部页面使用过，则当然优先把未修改过的页面换出。

3.13 简述一下Clock置换算法

该算法为每个页面设置一位访问位，将内存中的所有页面通过指针链成一个循环队列。由于该算法只有一位访问位，只能用它表示该页是否已经使用过，而置换时是将最近未使用过的页面换出去，所以把该算法称为最近未用算法。
选择页置换的过程：
1.当某页被访问时，其访问位置“1”；
2.在选择一页淘汰时，就检查其访问位，如果是“0”，就选择该页换出；若为“1”，则重新置为“0”，暂不换出该页；
3.在循环队列中检查下一个页面，直到访问到访问位为“0”的页面为止。

3.14 页面分配策略

驻留集：请求分页存储管理中，给一个进程分配的物理页框的集合就是这个进程的驻留集。
页面分配策略：固定分区局部置换、可变分配全局置换、可变分区局部置换
抖动：刚换出的页面马上又要换入主存，或者反之。
    主要原因：某个进程频繁访问的页面数目高于可用的物理页框数目
工作集：在某段时间间隔内，进程要访问的页面集合。

---

---

第4章 文件管理

4.1 文件管理的概述

文件的定义：
一组有意义的信息集合，可以是文档、图片、程序等。在用户进行输入、输出时，以文件为基本单位。
文件的基本操作：
操作系统提供 系统调用对文件进行创建、读、写、重定位、删除和截断等操作。

4.2 文件的逻辑结构

文件的逻辑结构是从用户观点出发看到的文件的组织形式。
文件的物理结构是从实现观点出发看到的文件在外存上的存储组织形式。
无结构文件（流式文件）
有结构文件（有记录文件）：
    顺序文件
    索引文件
    索引顺序文件
    直接（散列）文件

4.4 文件物理结构

连续分配：
    支持顺序访问和直接访问
    优点是实现简单、存取速度快
    缺点是文件长度不宜动态增加
链接分配：
    隐式链接：每个文件对应一个磁盘块的链表；磁盘块分布在磁盘的任何地方，除最后一个盘块外，每个盘块都有指向下一个盘块的指针。
    显示连接：把用于链接文件各物理块的指针，从每个物理块的块末尾中提取出来，显式的存放在内存的一张链表中，成为文件分配表。
索引分配

4.5 文件共享

基于索引节点的共享方式（硬链接）
利用符号链实现文件共享（软链接）（类似于快捷方式）

4.6 文件保护

概念：
为了防止文件共享可能会导致文件被破坏或未经批准的用户修改文件，文件系统必须控制用户对文件的存取，为此必须建立保护机制。
方式：
口令保护、加密保护、访问控制

4.7 文件存储空间管理

存储空间的划分与初始化：
文件存储设备分成许多大小相同的物理块，并以块为单位交换信息，因此，文件存储设备的管理实质上是对空闲块的组织和管理，它包括空闲块的组织、分配与回收
    空闲表法：
    空闲链表法：
    位示图法：
    成组链接法：

4.8 文件目录和目录文件的区别？目前广泛采用的目录结构形式是哪种？有何优点？

文件目录，又称文件控制块，存储的是文件的管理信息，控制对象是单个文件；
目录文件，存储的是若干个文件目录，控制对象是整个文件系统；
目前广泛采用的树形目录结构，优点是：允许文件重命名，实现了文件分类。

4.9 磁盘调度算法

4种算法：
先来先服务算法
最短寻找时间优先算法
扫描算法（电梯调度算法）
循环扫描算法

第五章 输入/输出管理

5.1 I/O控制方式

程序直接控制方式:
    工作原理：外设与内存进行数据传输时，每传输一个字，CPU都需要进行循环检查，判断是否已经传输完成。
    传输单位：字
    数据流向：设备与CPU之间、CPU与内存之间
    CPU干预频率：极高
    特点：造成了CPU的极大浪费，使其一直处于“忙等”。
中断驱动方式:
    工作原理：外设要和内存进行数据传输时，允许外设打断CPU运行并请求服务，使得CPU需要在每个指令周期末检查是否有中断，若有中断，则要处理中断，，然后CPU又返回做原来的工作。
    传输单位：字
    数据流向：设备与CPU之间、CPU与内存之间
    CPU干预频率：高
DMA方式:
    工作原理：允许主存和外设在DMA控制器下进行直接交互，在数据传输的整个过程中不需要CPU的参与。
    传输单位：块
    数据流向：设备和内存之间
    CPU干预频率：中等
通道控制方式
    工作原理：是专门负责输入输出的处理机。对DMA方式的改进，可以把对一个数据块的干预减少到对一组数据块的干预。
    传输单位：一组块
    数据流向：设备和内存之间
    CPU干预频率：低

#5.2 什么是 DMA 方式？它与中断方式的主要区别是什麽？

DMA方式是指内存与外设只需要在DMA控制器的控制下进行数据传输，而不需要进行CPU的干预。
与中断方式的主要区别是：
1.中断方式在每个数据需要传输时都需要中断CPU，而DMA方式是在所要求传送的一批数据全部传送完毕时才中断CPU；
2.中断方式中数据传输是在中断处理时由CPU控制完成的，而DMA方式中数据传输是在DMA控制器控制下完成的。

5.3 I/O子系统的层次结构

层次组成:
    用户层I/O软件：实现与用户交互的接口，用户可直接调用在用户层提供的、与I/O操作有关的库函数，对设备进行操作。
    设备独立性软件：用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护及设备分配与释放等，同时为设备管理和数据传送提供必要的存储空间。
    设备驱动程序：与硬件直接线管，负责具体实现系统对设备发出的操作指令，驱动I/O设备工作的驱动程序
    中断处理程序：用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完并恢复被终端进程的现场后，返回到被中断进程。
    硬件设备

*5.4 缓冲区管理

缓冲技术是一种 以空间换时间的资源换取技术。一般利用内存作为缓冲区。
引入的目的：
1.可以协调CPU与I/O设备之间速度不匹配的矛盾；
2.可以减少对CPU的中断频率；
3.提高设备的利用率。
(总的来说，提高CPU利用率，提高并行度)。
缓冲区类型：
单缓冲、双缓冲、循环缓冲、缓冲池

5.5 设备的分配与回收

设备分配是指根据用户的I/O请求分配所需的设备。
合理的分配原则主要考虑的因素：
    I/O设备的固有属性、T/O设备的分配算法、I/O设备分配的安全性以及I/O设备的独立性。
设备分配策略：
    (1)设备分配原则：既要充分发挥设备的使用效率，又要避免造成进程死锁，还要将用户程序和具体设备隔离开。
    (2)设备分配方式：静态分配和动态分配
    (3)设备分配算法：先请求先分配、优先级高者优先
设备分配安全性：
    设备分配中应防止发生进程死锁。

#5.6 在设备管理中，何谓设备独立性？如何实现设备独立性？

设备独立性是指用户程序独立于所使用的具体设备。
实现方式是系统为每个用户进程配置一张用于联系逻辑设备名和物理设备名的映射表，以实现使用逻辑设备名来请求物理设备。

5.7 SPOOLing技术

假脱机技术
作用：为了缓和CPU的高速性与I/O设备低速性之间的矛盾，引入了脱机输入/输出技术。
实现设备组成：
    输入井和输出井
    输入缓冲区和输出缓冲区
    输入进程和输出进程