OS考试

一、操作系统引论

1.定义

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

2.地位

操作系统是裸机之上的第一层软件，是建立其他所有软件的基础。它是整个系统的控制管理中心，既管硬件，又管软件，它为其他软件提供运行环境。

3.四大特征

• 并发： 是指两个或多个活动在同一给定的时间间隔中进行
• 共享： 是指计算机系统中的资源被多个进程所共用
• 异步： 进程以不可预知的速度向前推进
• 虚拟： 把一个物理上的实体变为若干个逻辑上的对应物

其中并发和共享是两个最基本的特征，两者互为存在条件

4.主要功能

• 处理机管理： 进程控制、进程同步、进程通信、死锁处理、处理机调度
• 存储器管理： 内存分配、地址映射、内存保护与共享、内存扩充
• 文件管理： 存储空间管理、目录管理、文件读写管理和保护
• 设备管理： 缓冲管理、设备分配、设备处理、虚拟设备

5.发展历程

• 手工操作阶段(此阶段无操作系统)

  缺点：人机速度矛盾

• 批处理阶段(操作系统开始出现)

  • 单道批处理阶段
  • 多道批处理阶段(操作系统正式诞生)
    • 优点：多道程序并发执行，资源利用率高
    • 缺点：不提供人机交互(缺少交互性)

  目的：提高系统资源利用率

• 分时操作系统(不可以插队，有了人机交互)

  • 优点：提供人机交互(交互性)
  • 缺点：不能优先处理紧急任务

• 实时操作系统(可以插队)

  • 硬实时操作系统

    必须在被控制对象规定时间内完成(火箭发射)

  • 软实时操作系统

    可以松一些(订票)

  优点：能优先处理紧急任务

从可靠性看实时操作系统更强，从交互性看分时操作系统更强

6.两种指令

• 特权指令：不允许用户程序使用(只允许操作系统使用)。如IO指令、置中断指令
• 非特权指令：普通的运算指令

7.两种程序

• 内核程序： 系统的管理者，可以执行一切指令，运行在内核态
• 应用程序： 普通用户程序只能执行非特权指令，运行在用户态

8.处理机状态

• 用户态(目态)： CPU只能执行非特权指令
• 核心态(管态、内核态)： 可以执行所有指令
• 用户态到核心态： 通过中断(是硬件完成的)
• 核心态到用户态： 特权指令psw的标志位 0用户态1核心态

9.原语

• 处于操作系统的最底层，最接近硬件的部分
• 这些程序的运行具有原子性，其操作只能一气呵成
• 这些程序的运行时间都较短，而且调用频繁

10.中断和异常

• 内中断(异常，信号来自内部)
  • 自愿中断—指令中断
  • 强迫中断，分为硬件中断、软件中断
• 外中断(中断，信号来自外部)
  • 外设请求(打印机缺纸)
  • 人工干预

11.系统调用

系统给程序员(应用程序)提供的唯一接口，可获得OS的服务。在用户态发生，核心态处理。

12.体系结构

• 宏内核： 高性能
• 微内核： 方便维护

二、进程调度

1.引入进程的目的

为了更好地描述和控制程序并发执行，实现操作系统的并发性和共享性而引入进程概念。

(进程是动态的，程序是静态的)

2.进程定义

是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位。

3.进程的组成

• PCB： 保存进程运行期间相关的数据，是进程存在的唯一标志
• 程序段： 被CPU执行的代码
• 数据段： 程序的数据

4.进程的状态

• 创建状态： 进程正在被创建
• 就绪态： 进程已处于准备运行的状态，即进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行
• 运行态： 进程正在占用CPU
• 阻塞态： 进程由于等待某一事件不能享用CPU
• 结束状态： 进程从系统上销毁

5.进程的状态变化

• 就绪态->运行态：处于就绪状态的进程被调度后，获得处理机资源(分派处理机时间片)
• 运行态->就绪态：时间片用完或在可剥夺系统中有更高优先级的进程进入
• 运行态->阻塞态：进程需要的某一资源还没有准备好
• 阻塞态->就绪态：进程等待的事件到来时

6.引入线程的目的

为了更好的使用多道程序并发执行，提高资源利用率和系统吞吐量。

7.线程特点

是程序执行的最小单位，基本不拥有任何系统资源。

8.处理机调度

是处理机进行分配，即从就绪队列中按照定的算法(公平、高效)选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

9.调度分类

• 高级调度(作业调度)
• 中级调度(内存对换)
• 低级调度(进程调度)

10.调度方式

• 剥夺时
• 非剥夺时

11.调度准则

• CPU利用率
• 系统吞吐量
• 周转时间
• 等待时间
• 响应时间

12.调度算法

• 先来先服务
• 短作业优先
• 优先级调度算法
• 高响应比优先调度算法
• 时间片轮转
• 多级反馈队列调度算法

13.引入进程同步的原因

协调进程之间的相互制约关系。

14.进程制约关系

• 同步： 也称为直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。
• 互斥： 也称为间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另进程才允许去访问此临界资源。

15.临界资源

一次仅允许一个进程使用的资源。

16.临界区

在每个进程中访问临界资源的那段程序。

17.临界区互斥原则

• 空闲让进： 如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。
• 忙则等待： 任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。
• 有限等待： 进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。
• 让权等待： 如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。

18.临界区互斥基本方法

信号量，利用PV操作实现互斥。

19.死锁产生的原因

非剥夺资源的竞争和进程的不恰当推进顺序导致的。

20.死锁定义

多个进程因竞争资源而造成的一种僵局，如果没有外力，这些进程将无法推进。

21.死锁的解决方法

• 预防死锁
  • 破坏互斥条件
  • 破坏不剥夺条件
  • 破坏请求和保持条件
  • 破坏循环等待条件
• 避免死锁
  • 安全状态
  • *银行家算法
• 检测死锁
  • 利用死锁定理
• 解除死锁
  • 资源剥夺法
  • 撤销进程法
  • 进程回退法

三、内存管理

1.引入内存管理的目的

更好的支持多道程序的并发执行，提高系统性能

2.内存管理的主要功能

• 内存空间的分配和回收
• 存储的保护和共享：保证各道作业在各自的存储空间内存运行，互不干扰。
• 地址转换：在多道程序环境下，程序中的逻辑地址与内存中的物理地址不可能一致，因此存储管理器必须提供地址变换功能，把逻辑地址转换成相应的物理地址。
• 内存扩充：利用虚拟内存技术或自动覆盖技术，从逻辑上扩充内存。

3.用户程序的主要处理阶段

• 编辑阶段： 创建源文件
• 编译阶段： 由编译程序将用户源代码编译成若干目标模块，生成目标文件
• 链接阶段： 由链接程序将编译后形成的一组目标模块及所需的库函数链接在一起，形成一个完整的装入模块，生成可执行文件
• 装入阶段： 由装入程序将装入模块装入内存运行
• 运行阶段： 得到结果

4.内存管理相关基本概念

• 程序的装入
  • 绝对装入
  • 静态重定位
  • 动态重定位
• 程序的链接
  • 静态链接
  • 装入时链接
  • 运行时链接
• 地址空间
  • 逻辑地址空间
  • 物理地址空间

5.内存的连续分配管理方式

• 单一连续分配：分配到内存固定的区域
• 固定分区分配：分配到内存不同的固定区域，分区可以相等可以不等
• 动态分区分配：可变分区存储管理，按照程序的需要进行动态的划分

动态分区分配的策略算法：

• 首次适应：空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。
• 最佳适应：空闲分区按容量递增的方式形成分区链，找到第一个能满足要求的空闲分区。
• 最坏适应：空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区，即挑出最大的分区。
• 邻近适应：由首次适应算法演变而成。不同之处是：分配内存时从上次查找结束的位置开始继续查找。

6.内存的非连续分配管理方式

• 基本分页式存储管理
• 基本分段式存储管理
• 段页式

7.内存的扩充方法

• 覆盖(同一程序或进程中)
• 交换(不同进程/作业之间进行)
• 虚拟内存

8.引入虚拟内存的原因

物理硬件不变的情况下，在逻辑上扩充内存。

9.虚拟内存的组成部分

• 页表机制
• 中断机制
• 地址变换机制
• 内存与外存

10.虚拟内存的页面淘汰/置换算法

• 先进先出页面淘汰/置换算法(FIFO)：淘汰最先进入内存的页面(三个内存块都为空，3次缺页中断)

  注： 对于FIFO页面淘汰算法，有时增加分配给作业的可用内存块数，它的缺页次数反而上升，通常称为异常现象

• 最近最久未用页面淘汰/置换算法(LRU)：总是把最长时间未被访问过的页面淘汰出去(需要寄存器和栈)

• 最近最少用页面淘汰/置换算法(clock)：总是把当前使用的最少的页面淘汰出去

• 最佳页面淘汰/置换算法(OPT)：把以后不再使用的或最长时间内不会用到的页面淘汰出去(理论上，不会实现)

页面淘汰是由缺页中断引起的，但缺页中断不见得一定引起页面淘汰

四、文件管理

1.文件的定义

文件是以计算机硬盘为载体的存储在计算机上的信息集合

2.文件系统的定义

就是操作系统中负责操纵和管理文件的一整套设施，它实现文件的共享和保护，方便用户“按名存取”。

3.文件系统的功能

• 文件管理
• 目录管理
• 文件空间管理
• 文件共享和保护
• 提供方便的接口

4.文件的逻辑结构

• 无结构文件(即流式文件)
• 有结构文件(记录式文件)
  • 顺序文件
  • 索引文件
  • 索引顺序文件

5.文件控制块

在文件系统内部给每一个文件唯一地设置一个文件控制块，它用于描述和控制文件的数据结构，与文件一一对应。

6.目录结构

• 单级目录
• 二级目录
• 树形目录
• 图形目录

7.文件分配方式

• 连续分配
• 链接分配
• 索引分配

8.文件存储空间管理

• 空闲表法
• 空闲链表法
• 位示图法

9.磁盘地址结构

• 柱面号
• 盘面号
• 扇面号

10.磁盘调度算法

• 先到先服务算法
• 最短查找时间优先算法
• 扫描算法和LOOK算法
• 循环扫描算法和循环LOOK算法

五、设备管理

1.设备管理的目的

使用方便、与设备无关、效率高、管理统一

2.I/O设备分类

• 存储设备或输入输出设备
• 块设备或字符设备
• 低速中速高速设备

3.I/O控制方式

• 程序直接控制方式： 这种方式也称为查询方式，CPU不断地去查询设备控制器是否将数据放到了数据存储器中，或者从数据存储器存到设备中，当完成IO时CPU才能去干别的事。
• 中断方式： 这种方式当CPU发出指令后就可以去干别的事，当设备控制器把数据存在数据存储器后，向CPU发出中断请求，然后CPU再来处理这部分数据。
• DMA方式： 虽然中断方式提高了CPU的利用率，但是数据寄存器有限，中断是以字节单位进行中断，也就是说读取或存储一个字节后需要进行中断，那么其实CPU的利用率还是很低的，所以就诞生了DMA方式，这种方式由DMA控制器直接将设备中的数据以数据块为单位直接传输到内存中，当传输结束后才向CPU发起中断。
• IO通道控制方式： DMA虽然大大提升了CPU的利用率，但是DMA只能传输一个连续的数据块。所以引入了IO通道的控制方式，IO通道控制方式可以传输不连续的数据块，减少了CPU干预。CPU通过对IO通道发出指令，然后让IO容道自己工作，等数据传输完才向CPU发起中断。

4.引入缓冲区的目的

• 缓和CPU与外设间速度不匹配的矛盾
• 提高CPU与外设之间的并行性
• 减少对CPU的中断次数

5.缓冲区的设置方式

• 单缓冲： 当数据到达率与离去率相差很大时，可采用单缓冲方式。
• 双缓冲： 当信息输入和输出率相同(或相差不大)时，可利用双缓冲区，实现两者的并行。
• 多缓冲： 对于阵发性的输入、输出，为了解决速度不匹配问题，可以设立多个缓冲区。

6.常用三种设备

• 独占设备： 不能共享的设备，即：在一段时间内，该设备只允许一个进程独占。如打印机。
• 共享设备： 可由若干个进程同时共享的设备。如磁盘机。
• 虚拟设备： 是利用某种技术把独占设备改造成可由多个进程共享的设备。

7.针对三种设备采用的三种分配技术

• 独占分配技术： 是把独占设备固定地分配给一个进程，直至该进程完成I/O操作并释放它为止。
• 共享分配技术： 通常适用于高速、大容量的直接存取内存设备。由多个设备共享一台设备，每个进程只用其中的一部分。
• 虚拟分配技术： 利用共享设备去模拟独占设备，从而使独占设备成为可共享的、快速I/O设备。实现虚拟分配的最有名的技术是SPOOLing技术，也称为假脱机操作。