单道批处理系统：把一批作业以脱机方式输入到磁带上，并在系统中配上监督程序，在它的控制下，使这批作业能够一个接一个地连续处理。单道批处理系统是为了解决人机矛盾和CPU与IO设备速度不匹配的过程中形成的。
多道批处理系统：将用户提交的作业先存放在外存，形成一个队列（后备队列）。然后作业调度程序按照一定的算法，从后备队列中选择若干作业调入内存，使他们共享CPU和系统中的各种资源。多道批处理系统是为了进一步提高资源的利用率和系统吞吐量

单道批处理系统优点是实现作业连续处理，缺点是系统资源得不到充分利用。多道批处理的优点是资源利用率高，系统吞吐量大。缺点是平均周转时间长，无交互能力。

5.操作系统的基本特征有哪些？请解释每个特征

并发：使得两个或者多个事件在同一时间间隔发生，提高系统资源利用率，增加系统吞吐量
共享：系统中资源可供内存中多个并发执行的进程共同使用
虚拟：通过某种技术将一个物理实体变为若干个逻辑上的对应物
异步：进程不是一次性执行完，而是以停停走走的方式运行，以不可预知的速度向前推进

6.简述操作系统的主要功能

处理机管理：创建和撤销进程，对诸进程的运行进程协调，实现进程之间的信息交换，以及按照一定的算法把处理机分配给进程
存储器管理：为多道程序的运行提供良好的环境，提高存储器的利用率，方便用户使用，并能从逻辑上扩充内存
设备管理功能：1、完成用户提出的I/O请求，为用户进程分配所需的I/O设备，并完成指定的I/O操作。2、提高CPU和I/O设备的利用率，提高I/O速度，方便用户使用I/O设备
文件管理功能：对用户文件和系统文件进行管理以方便用户的使用，并保证文件的安全性

第二章、进程的描述与控制

7.什么是前驱图，什么是资源分配图

前驱图：所谓前驱图，是指一个有向无循环图，可记为DAG(Directed Acyclic Graph)，它用于描述进程之间执行的先后顺序。使用->表示前驱关系
资源分配图：用于检测系统中是否发生死锁，传统的图是由节点集N和边集E构成，在资源分配图中N定义为N=PUR，P为所有进程的集合，R为所有资源的集合。边集E定义为E={（Pi，Ri）}U{（Ri，Pi）}，边集中（Pi，Ri）表示进程Pi申请资源Ri，（Ri，Pi）表示资源的分配

8.什么是程序顺序执行？什么是程序并发执行？二者的特征有哪些？

顺序执行：一个程序往往由若干程序段组成，程序在执行时，都需要按照某种先后次序执行，仅当前一段程序段执行完毕后，才运行后一程序段。特征有3点，分别是顺序性、封闭性、可再现性
并发执行：一组在逻辑上相互独立的进程或程序段在执行过程中，其执行时间在客观上相互重叠，即一个程序段执行尚未执行结束，另一个程序段的执行已经开始。特征也是3点，分别是间断性、失去封闭性、不可再现性

9.什么是进程？什么是线程？什么是管程？什么是进程实体？进程的特征有哪些？

进程：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
线程：做为调度和分派的基本单位，包含在进程中，是进程中的实际运作单位，具有许多进程所具有的特征，被称为轻量级进程
管程：代表共享资源的数据结构以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序共同构成了一个操作系统的资源管理模块(理解为一个对象，里面有属性和方法即可)
进程实体：由程序段、相关的数据段、PCB(Process Control Block)组成，一般情况下，进程实体简称为进程

进程的特征如下：

动态性：由创建而产生，由调度而执行，由撤销而消亡。进程实体具有一定的生命周期
并发性：多个进程实体同存于内存中，且能在一段时间内同时运行
独立性：进程实体是一个能够独立运行、独立获得资源和独立接受调度的基本单位
异步性：进程以异步方式运行，即按照各自独立、不可预知的速度向前推进

10.进程有哪五个基本状态

就绪状态：指进程已处于准备好运行的状态，获得CPU即可运行
执行状态：进程已获得CPU，正在运行
阻塞状态：进程由于某种原因无法继续执行，程序执行受到阻塞
创建状态：未获得进程运行所需的资源，或者PCB初始化工作尚未完成
终止状态：进程自然结束或者因某种原因结束，操作系统进行善后处理，最后将PCB空间归还系统

11.进程控制块的作用是什么？进程控制块中包含哪些信息？

进程控制块(PCB)的作用是使一个在多道程序环境下不能独立运行的程序(含数据)成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。

进程控制块中包含信息如下：

进程标识符：用于唯一标识一个进程
处理机状态：主要由处理机的各种寄存器中的内容组成
进程调度信息：进程的状态及有关的进程调度信息
进程控制信息：用于进程控制所必须的信息

12.简述程序和进程的异同

进程是动态的，具有一定的生命周期。程序是静态的，只是一组有序指令的集合
进程可以并发执行，程序由于没有PCB不能参与并发执行
进程可以独立运行，独立获得资源，独立接受调度。而程序不能作为独立单位参与运行
进程和程序都具有异步性，但是进程执行结果结果是可再现的，而程序是不可再现的

13.什么是进程控制？什么是进程同步？什么是进程通信？

进程控制：进程控制是进程管理中最基本的功能，主要包括创建新进程、终止已完成的进程、将因发生异常情况而无法继续运行的进程置于阻塞状态、负责进行运行过程中的状态转换等功能
进程同步：对多个相关的进程在执行次序上进行协调，使并发执行的诸进程之间能够按照一定的规则(或时序)共享系统资源，并能很好的相互合作，从而使进程的执行具有可再现性
进程通信：进程通信是指进程之间的信息交换

14.进程同步应遵循哪些准则？请逐一进行解释

空闲让进：当无进程处于临界区时，表明该临界资源处于空闲状态，应当允许一个请求进入临界区的进程立即进入自己的临界区，以有效的利用资源
忙则等待：当已有进程进入临界区时，表明临界资源正在被访问，因而其他进入临界区的进程必须等待，以保证对临界资源的互斥访问
有限等待：对要求访问临界资源的进程，应保证在有限的时间内进入自己的临界区，以免陷入”死等“状态
让权等待：当进程不能进入自己临界区时，应当立即释放处理机，以免陷入”忙等“状态

15.什么是P操作？什么是V操作？

P操作和V操作都是原子操作，执行过程不可中断。P操作表示wait操作，而V操作则是表示signal操作。

P操作可以描述为：

    wait(S){
        while(S<=0);
        S--;
    }

V操作可描述为：

    signal(S){
        S++;
    }

上述描述基于整形型号量，记录型信号量有所不同，是通过自我阻塞的方式来进行的

16.什么是进程？什么是线程？进程和线程之间的关系是什么？为什么要在有进程的操作系统中引入线程？试比较线程和进程之间的异同

进程：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
线程：线程是调度和分派的基本单位

线程包含在进程中，是进程中的实际运作单位，具有许多进程所具有的特征，被称为轻量级进程。相应的，传统进程被称为重型线程，相当于只有一个线程的任务

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

线程与进程之间的异同主要有以下几个方面：

- 调度的基本单位：传统OS中，进程是独立运行的基本单位。在引入线程的OS中，线程是能独立运行的基本单位
- 并发性：在引入线程的OS中，不仅进程之间可以并发执行，而且进程中的线程也能够并发执行
- 拥有资源：进程拥有系统资源，作为拥有资源的基本单位，而线程仅有一点必不可少、能保证独立运行的资源
- 独立性：同一进程中的不同线程之间的独立性要比不同进程之间的独立性低很多
- 系统开销：线程创建、切换、撤销等操作的开销明显小于进程
- 支持多处理机系统：进程只能运行在一个处理机上，而线程可以运行在多个处理机上

17.线程包含哪些状态？

执行状态：表示进程已获得处理机正在运行
就绪状态：指线程已具备了各种执行条件，只需再获得CPU便可立即执行
阻塞状态：指线程在执行过程中因某事件受阻而处于暂停状态

第三章、处理机调度与死锁

18.什么是高级调度？什么是中级调度？什么是低级调度？

高级调度：高级调度又称为长程调度或作业调度，调度对象为作业。主要功能是根据某种算法，将外存上处于后备队列中的哪几个作业调入内存，为他们创建进程、分配必要资源，并将他们放入就绪队列。高级调度主要用于多道批处理系统中，分时和实时系统中不进行设置
中级调度：中级调度又称为内存调度。主要目的是提高内存利用率和系统吞吐量。负责进程的换入和换出
低级调度：低级调度又称为进程调度或短程调度，调度的对象为进程(或内核级线程)。主要功能是决定就绪队列中的哪个进程获得处理机。多道批处理、分时和实时的三种OS中都必须配置这级调度

19.什么是作业的周转时间？什么是作业平均周转时间？作业周转时间包含哪几部分？什么是作业的带权周转时间？什么是作业平均带权周转时间？

周转时间：作业从提交给系统开始，到作业完成的这段时间间隔
平均周转时间：平均周转时间就是所有作业周转时间的平均值
带权周转时间：作业周转时间T与系统为它提供服务的时间Ts之比，即为T
平均带权周转时间：对所有作业的带权周转时间取平均值

周转时间包含四个部分：

作业在外村后备队列上等待(作业)的时间
进程在就绪队列上等待进程调度的时间
进程在CPU上执行的时间
进程等待I/O操作完成的时间

20.什么是作业控制块？作业控制块包含哪些内容？作业运行时有哪些状态？

作业控制块：作业存在的标志，保存了系统对作业进行管理和调度所需的全部信息
作业控制块内容：作业表示、用户名称、用户账号、作业类型、作业状态、调度信息、资源需求、资源使用情况等

作业运行包含以下三个状态：

后备状态：作业已经建立JCB(作业控制块)，并且放入了后备队列中
运行状态：一个作业从第一次进入就绪状态开始，一直到运行结束前
完成状态：作业正常或异常终止，作业进入该阶段

21.进程调度的任务是什么？

保存处理机的现场信息：在进程调度时首先需要保存当前进程的处理机的现场信息
按某种算法选取进程：调度程序按某种算法从就绪队列中选取一个进程，将其状态改为运行状态，并准备把处理机分给它
把处理机分配给进程：由分配程序把处理机分配给该进程，装入该进程信息，将处理机控制权交予该进程

22.什么是死锁？死锁产生的原因有哪些？死锁产生的必要条件有哪些？

死锁：一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件
死锁产生的原因：1、竞争不可抢占性的资源。2、竞争可消耗资源。3、进程推进顺序不当
死锁产生的必要条件：1、互斥条件(资源只能被一个资源占用)。2、请求和保持条件(不能运行时依然保持自己拥有的资源，不进行释放)。3、不可抢占条件(未使用完不能被抢占)。4、循环等待条件(存在进程-资源的循环链)

23.简述银行家算法

为实现银行家算法，每一个新进程在进入系统时，它必须明确声明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应当超过系统所拥有的资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算将这些资源分配给进程后，是否会使系统处于不安全状态，如果不会，才将资源分配给它，否则让进程等待

第四章、存储器管理

24.什么是程序的装入？程序的装入方式有哪些？

装入：由装入程序将装入模块装入内存，包含三种装入模式，如下：

- 绝对装入方式：程序中的相对地址(逻辑地址)与实际内存地址相同，适用于单道程序环境
- 可重定位装入方式：在装入时对目标程序中的指令和数据地址进行修改，模块中的逻辑地址和装入内存后的实际物理地址不同，适用于多道程序环境
- 动态运行时的装入方式：装入程序把装入模块装入内存后，并不立即把装入模块中的逻辑地址转换为物理地址，而是把这种地址推迟到程序真正要执行时才进行

25.什么是程序的链接？程序的链接方式有哪些？

链接：将目标模块以及他们所需要的库函数装配成一个完整的装入模块，根据链接时间的不同，分为以下三种模式：

- 静态链接：在程序运行前，把目标模块和所需函数链接成一个完整的装配模块，以后不再拆开
- 装入时动态链接：在目标模块装入内存时，采用边装入边链接的方式
- 运行时动态链接：将某些模块的链接推迟到运行时才进行

26.什么是作业的连续内存分配？什么是作业的离散内存分配？什么是虚拟存储器？常见的连续内存分配方式有哪些？常见的离散分配方式有哪些？常见的虚拟存储器实现方式有哪些？

连续内存分配为用户程序分配一个连续的内存空间，即程序中的代码或数据的逻辑地址相邻，体现在内存空间分配时物理地址的相邻。

连续内存分配可分为以下四类：

单一连续分配：用户内存区仅装有一道用户程序，程序独占内存
固定分区分配：用户空间划分为若干固定大小的区域，每个区域只装入一道作业，互不干扰
动态分区分配：又称为可变分区分配，根据进程的实际需要，动态分配内存空间
动态可重定位分区分配：在动态分区分配的方式上增加了紧凑的功能，即系统中没有足够大的空闲分区时，如果小的空闲分区的总和满足要求，那么就对这些空间进行合并

离散内存分配方式将一个进程分散的装入到许多不相邻的分区中，充分利用内存空间。

离散内存分配根据所分配地址空间的基本单位不同，主要分为以下三种：

分页存储管理方式：将用户程序和内存空间都分为若干个大小固定的页面
分段存储管理方式：将用户程序分为若干段，这些程序段可以存储在内存中不相邻的位置
段页式存储管理方式：结合上述两种的优点，简单来说就是程序先分段，再分页

虚拟存储器都是建立在离散分配存储管理方式上的，实现采用分页请求系统或者请求分段系统。

27.什么是内存碎片？什么是外存碎片？

内部碎片就是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间；
外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。

28.什么是固定分区分配？什么是动态分区分配？

固定分区分配：用户空间划分为若干固定大小的区域，每个区域只装入一道作业，互不干扰
动态分区分配：又称为可变分区分配，根据进程的实际需要，动态分配内存空间

29.什么是伙伴系统

一种基于索引搜索的动态分区分配算法，该算法规定，无论已分配分区或空闲分区，其大小均为2的k次幂（1<=k<=m），通常情况下2的m次方为可分配内存的大小。

算法执行的具体流程就是当进程需要长度为n的内存空间时，寻找满足 2^i-1 < n <= 2^i，相当于要找到最小的大于n的那个空闲分区，如果存在，直接分配，不存在，那么就寻找2^i+1这个块，然后分为两个2^i块，一个用于分配，一个加入空闲分区链表，如果2^i+1块也不存在，那么继续往上找，然后往下分。以此类推即可。回收和分配类似，只是把分配时的分割变为了回收时的合并

30.什么是紧凑？紧凑能解决什么问题？紧凑的优缺点是什么？

把通过移动内存中作业的位置，把原来多个分散的小分区拼接为一个大分区的方法，称为紧凑(或拼接)。紧凑可以获得大的空闲空间，解决用户程序过大不能装入内存的问题。紧凑的优点是可以获得很大的空闲空间，缺点是需要对移动的程序和数据的地址进行修改，影响了系统效率。

31.什么是对换？对换的类型有哪些？

所谓对换，是指把内存中暂时不能运行的进程或暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据换入内存。

进程的对换类型根据对换的数量进行分类，主要有以下两种：

- 整体对换：以进程为单位进行换入换出，又被称为进程对换
- 页面(分段)对换：以进程的一个页面或以分段为单位进行的对换。

32.什么是页表？什么是页表寄存器？什么是快表(联想寄存器)？什么是段表？什么是段表寄存器？什么是请求页表？什么是请求段表？页表、段表、请求页表、请求段表的结构是怎样的？什么是页面？什么是物理块？什么是逻辑段？

ps：吐槽一下，这tm是什么问题，真是见鬼了…….

页表：实现从页面到物理块号的地址映射
页表寄存器：存放页表在内存的起始地址和页表的长度
快表(联想寄存器)：存放当前访问的那些页表项，就是为了减少对页表寄存器的访问次数，提高效率
段表：用于实现逻辑段到物理内存区的映射
段表寄存器：用于存放段表起始地址和段表长度
请求页表：将用户地址空间中的逻辑地址映射为内存空间中的物理地址
请求段表：将用户程序段中的段地址映射为内存空间中的物理地址
页表的结构：就是页号到块号对应关系的一张二维表格
段表的结构：段号到基址对应关系的二维表格
请求页表结构：包含页号、物理块号、状态位P、访问字段A、修改位M、外存地址
请求段表结构：包含段名、段长、段基址、存取方式、访问字段A、修改位M、存在位P、增补位、外存地址
页面：把作业划分为若干大小相等的块，称为页面
物理块：把内存划分为若干大小相等的块，称为物理块
逻辑段：逻辑段就是程序设计中的数据分段，一个程序往往分为几个段

33.试画出分页存储管理方式的地址变换机构

34.试画出分段存储管理方式的地址变换机构

35.试画出段页式存储管理方式的地址变换机构

第五章、虚拟存储器

36.什么是程序的局部性原理？什么是虚拟存储器？虚拟存储器的特征有哪些？

局部性原理就是在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域

虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存加以扩充的一种存储器系统。

虚拟存储器具有的功能如下：

多次性：一个作业的程序和数据无需一次装入内存，分多次装入，只需要将当前运行所需的那部分程序和数据装入即可
对换性：作业的程序和数据不是常驻内存，允许程序和数据进行换入和换出
虚拟性：从逻辑上扩充内存容量，使用户看到的内存容量远大于实际容量

37.什么是抖动？什么是工作集？

抖动：指刚被换出的页面很快又要被访问，需要重新调入，此时又需要选择一页调出，而刚被选择调出的页面很快又要访问，有需要进行调入，页面频繁的调入调出，我们就称之未发生了抖动
工作集：指在某段实际间隔里，进程实际所要访问页面的集合

第六章、输入输出系统

38.I/O的基本功能有哪些？

隐藏物理设备的细节：对设备进行抽象，屏蔽底层细节，向上层进程提供接口
与设备的无关性：基于隐藏设备的细节，对于不同的设备，提供相同的接口
提供处理机和I/O设备的利用率：尽可能让处理机和CPU并行操作，提高它们的利用率，同时也减少I/O设备对处理机的干预时间
对I/O设备进行控制：方便高层软件和用户使用
确保设备的正确共享：一段时间内，允许多个进程同时访问设备
错误处理：将可以解决的错误进行处理，不进行上传

39.I/O软件的层次结构是怎样的？

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

上述结构依次是从少到下的，越往下，越贴近于硬件

40.I/O系统的层次结构是怎样的？

中断处理程序：I/O设备最底层，直接与硬件进行交互
设备驱动程序：I/O设备的ci底层，是进程和设备控制器之间的通信程序
设备独立性软件：I/O软件独立于具体使用的物理设备

I/O系统与I/O软件组织的层次结构相对应

41.设备控制器的基本功能

接收和识别命令：设备控制器能接收并识别处理机发来的多种命令
数据交换：设备控制器可以实现CPU与控制器之间、控制器与设备之间的数据交换
标识与报告设备的状态：控制器应记下设备的状态供CPU了解
地址识别：设备控制器必须能够识别其所控制的每个设备的地址
数据缓冲区：由于I/O设备和CPU速率差距大，必须设置缓冲区
差错控制：对应I/O设备传来的数据，设备控制器必须进行差错检测

42.什么是DMA？什么是I/O通道？设备驱动程序的作用是什么？

DMA：中文叫直接存储器，为了进一步减少CPU对I/O的干预。由主机与DMA控制器接口、DMA控制器与块设备的接口、I/O控制逻辑三部分组成
I/O通道：I/O通道是一种特殊的处理机。他具有执行I/O指令的能力，并通过执行通道(I/O)程序来控制I/O操作。主要目的就是原来由CPU处理的I/O任务转由通道来承担，使CPU从繁忙的I/O任务中解脱出来

设备驱动程序的作用如下：