操作系统复习大纲

Posted on |

Chapter 1 操作系统概观

1.批处理与多道程序设计
2.分时系统与实时系统
3.操作系统的基本类型与特征
4.并发与并行的概念
5.操作系统的层次结构与功能模块
6.程序的并发执行与顺序执行

批处理与多道程序设计

单道批处理

1
2
3
4
5
1. 处理过程该系统把一批作业以脱机方式输入到磁带上，并在系统中配上监督程序，在它的控制下使这批作业能一个接一个地连续处理，在内存中始终只保持一道作业。
2. 特征：
	1. 自动性
	2. 顺序性
	3. 单道性

多道批处理

1
2
3
4
5
6
7
8
9
10
11
12
13
1. 在该系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。
2. 优点：
	1. 资源利用率高（CPU、I/O）
	2. 系统吞吐量大（单位时间完成的总工作量）
3. 缺点：
	1. 平均周转时间长
	2. 无交互能力
4. 需要解决的问题：
	1. 处理机管理
	2. 内存管理
	3. I/O设备管理
	4. 文件管理
	5. 作业管理

分时系统与实时系统

分时OS

1. 需求：
    1. 人机交互
    2. 共享主机
    3. 便于用户上机
2. 关键问题：
    1. 及时接收
    2. 及时处理
    3. 
3. 特征：
    1. 多路性
    2. 独立性
    3. 即时性
    4. 交互性

实时OS

1. 需求：
    1. 实时控制
    2. 实时信息处理
2. 分类：
    1. 任务执行时是否呈现周期性
        1. 周期性实时任务：外部设备周期性发出激励信号，计算机按照激励信号循环执行
        2. 非周期性实时任务：外部设备所发出的激励信号并无明显的周期性，但都必须联系着一个截止时间(Deadline)。它又可分为开始截止时间（某任务在某时间以前必须开始执行）和完成截止时间（某任务在某时间以前必须完成）两部分
    2. 对截止时间的要求：
        1. 硬实时：某个动作必须在规定时间完成（导弹、飞控）
        2. 软实时：可以接收偶尔违反时间规定（飞机订票系统、银行管理系统）

分时OS和实时OS的比较

1
2
3
4
5
1. 多路性：实时操作系统也要按照分时原则为多个终端服务
2. 独立性：多个用户彼此互不干扰
3. 及时性：实时OS要求更高
4. 交互性：实时信息处理系统虽然也具有交互性，但这里人与系统的交互仅限于访问系统中某些特定的专用服务程序
5. 可靠性：实时OS要求更高

操作系统的类型和基本特征

操作系统的基本类型：

单道批处理 多道批处理 分时 实时（硬实时/软实时） 网络（客户/服务机） 分布式 个人操作系统
特征 自动性、顺序性、单道性 多道、宏观上并行、微观上串行 同时性、独立性、及时性、交互性 及时性、可靠性 共享 分布性、并行性 windows、Linux、macOS
优点 资源利用率高、系统吞吐量大 人机交互能力 系统内的若干计算机完成同一任务
缺点 资源利用率与系统吞吐量较低 用户响应时间长、没有人机交互能力 不能对外部信息在规定时间内做出处理

**分时操作系统与批处理系统的不同点：追求目标不同、适应作业不同、资源利用率不同、作业控制方式不同。

操作系统的基本特征：

1
2
3
4
5
6
7
8
9
1. 并发性（最重要）：指两个或两个以上的活动或事件在同一个时间间隔内发生。并发性会使操作系统的设计和实现变得复杂化。

2. 共享性：指计算机系统的资源可以被多个并发执行的程序共同使用，而不是被某个程序独占。与共享性有关的问题是资源分配、信息保护、存取控制。
	1. 互斥共享：打印机、磁带机
	2. 同时访问：宏观同时，微观交替访问，例如磁盘
3. 虚拟性
	1. 时分复用
	2. 空分复用：虚拟磁盘、虚拟存储器
4. 异步性：在多道程序环境中，允许多个程序并发执行，并发活动会导致随机事件的发生。异步性会给系统带来潜在的危险，有可能会导致并发程序的执行产生与时间有关的错误。

操作系统的目标和功能

  1. 操作系统作为资源的管理者

    1
    2
    3
    4
    1. 处理机管理（进程控制、进程同步、进程通信、死锁处理、处理机调度）
    2. 存储器管理（内存分配/回收、地址映射、内存保护/共享、内存扩充）
    3. 文件管理（存储空间管理、目录管理、读写管理/保护）
    4. 设备管理（缓冲管理、设备分配、设备处理、虚拟设备）

  2. 操作系统作为用户与硬件系统之间的接口

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    1. 命令接口
        联机控制方式（交互式命令接口）
        脱机控制方式（批处理命令接口）：.bat

    2. 程序接口
        程序接口由一组系统调用（广义指令）组成。

    3. 操作系统实现了对计算机资源的扩充
        裸机：没有软件支持的计算机
        虚拟机：覆盖了软件的机器

并发与并行的概念

并发

1
2
1. 多个进程在同一段时间内运行。
2. OS的并发性是指计算机OS中同时存在多个运行的程序，具备处理和调度多个程序同时执行的能力

并行

1
2
1. 并行性是指OS具有同时进行运算或操作的特性，在同一时刻能完成两种或两种以上的工作
2. 并行性需要硬件的支持，如多流水线或多处理机

计算机层次结构与功能模块

1
2
3
组成：硬件和软件。
层次结构：应用程序->系统程序->操作系统->硬件。
功能模块：

  1. 分层

    1
    2
    3
    4
    5
    6
    优点：
    	1. 便于系统调试和验证
    	2. 易扩充、易维护
    缺点：
    	1. 合理定义各层较难
    	2. 效率较差：完成一个功能都需要穿越多层，每层之间的通讯机制增加了开销（0-copy）

  2. 模块化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    1. 衡量独立性的标准：
    	1. 内聚性：模块内部各部分间联系的紧密程度
    	2. 耦合性：模块间相互联系和影响的程度
    2. 优点：
    	1. 提高设计的正确性、可理解性、和可维护性
    	2. 增强OS的可适应性
    	3. 加速OS的开发过程
    3. 缺点：
    	1. 模块间的接口设计很难匹配实际需求
    	2. 无法找到可靠的决定顺序

  3. 宏内核

    1
    2
    3
    优点：高效
    缺点：随OS设计规模的发展越来越复杂
    目前主流是以宏内核为基础，吸收微内核优点的混合内核架构

  4. 微内核

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    1. 微内核将内核中最基本的功能保留在内核，将不需要在核心态运行的功能移动到用户态执行
    2. 微内核将OS分为两个部分：
    	1. 微内核：
    		1. 与硬件处理联系紧密的部分
    		2. 一些基本的功能
    		3. 客户和服务机之间的通信
    	2. 多个服务器
    3. 微内核结构通常利用“机制和策略分离”的原理构造OS结构：
     	1. 进程管理：
     		1. 内核中实现进程的切换、调度、多处理机简单同步等机制
     		2. 服务器中实现进程的分类、优先级的确认等策略
     	2. 低级存储器管理：
     		1. 内核中实现逻辑地址与物理地址间的变换、页表、地址变换等机制
     		2. 服务器中实现页面置换算法、内存分配及回收等策略
     	3. 中断和陷入处理：
     		1. 内核中只保留与硬件紧密相关的一部分，主要工作是捕获所发生的中断和陷入事件并发送给相应的服务器处理
     		2. 服务器提供中断服务程序，因中断的事件不同而有不同的处理
    3. 优点：
    	1. 扩展性和灵活性
    	2. 可靠性和安全性
    	3. 可移植性
    	4. 分布式计算
    4. 缺点：
    	1. 小内核导致CPU在内核态和用户态之间频繁切换，增大开销
    	2. 提高执行效率的同时会导致内核增大，需要平衡二号取舍
    5. 微内核在实时、工业、航空及军事应用中特别流行

  5. 外核

    1
    2
    3
    4
    5
    1. 虚拟机除了克隆真实机器，另一种策略是对机器进行分区，给每个用户整个资源的一个子集
    2. 外核（进程）运行在内核态，用于为虚拟机分配资源，并检查资源请求是否合法，确保每台虚拟机都只使用自己的资源
    3. 优点：
    	1. 减少了映射层：如果每台虚拟机认为自己拥有整个资源，虚拟机监控程序就需要为每台虚拟机维护一张资源映射表
    	2. 减少负载：外核将多道程序（在外核内）与用户操作系统代码（在用户空间中）加以分离，减轻负载

程序的顺序执行与并发执行

顺序执行：单处理机、没有操作系统

1
2
3
1. 顺序性
2. 封闭性：程序运行时独占全机资源
3. 可再现性

并发执行：与异步执行的定义不同

1
2
3
1. 间断性：多道程序环境允许多个程序并发运行，但程序的执行不是一贯到底的，而是走走停停，以未知的速度推进
2. 失去封闭性：多个程序共享的资源被运行中的程序更改，程序之间相互影响
3. 不可再现性（异步性保证能再现）：失去封闭性导致失去可再现性

Chapter 2 进程管理

1. 进程:进程控制块、进程的几种基本状态与状态转换（进程的创建、进程的终止、进程的阻塞与唤醒、进程的挂起与激活等)
2. 进程的同步与互斥:临界资源、临界区、进程同步与互斥问题、信号量机制以及P、V操作、管程机制
3. 进程间通信:进程通信的类型(直接通信和间接通信方式)、消息传递系统中的几个问题、消息缓冲队列通信机制
4. 线程与进程的调度:线程与进程的基本概念，调度的类型、调度队列模型、调度方式、进程调度算法（先来先服务、短进程优先、时间片轮转、基于优先级的调度算法等)
5. 死锁:死锁的基本概念，死锁定理、死锁预防、死锁避免与处理死锁的基本方法、银行家算法
6. 综合应用:生产者消费者问题、读者和写者问题、哲学家进餐问题等

进程

1
进程 = 程序段 + 数据段 + PCB

进程控制块

1
2
3
4
1. 进程描述信息
2. 进程控制和管理信息
3. 资源分配清单
4. 处理机相关信息（上下文）

进程的几种基本状态与状态转换

进程申请了PCB但资源（如内存）不足时，并不是创建失败，而是处于创建态，等待资源分配。

进程的同步与互斥

临界资源

1
2
1. 临界资源是同一时刻只允许一个进程访问的资源
2. 没有临界资源机制导致程序失去再现性

临界区

1
2
1. 临界区：进程中访问临界资源的代码段
2. 进程互斥的访问临界区 = 互斥访问临界资源

进程同步与互斥问题

实现互斥的方法：

1
2
3
4
5
6
7
8
1. 信号量 软硬都有（关中断/原子操作）
2. 硬件实现 tsl
3. 软件实现：
	1. 单标志 turn
	2. 双标志先检查法：必须交替进行
	4. 双标志后检查法：可能相互谦让导致饥饿
	5. 皮特森
4. 管程

经典同步问题：

1
2
3
1. 生产者、消费者
2. 哲学家进餐
3. 读者、写者问题

信号量机制以及P、V操作

1
2
信号量分为整型信号量与记录型信号量。
记录型信号量可以解决忙等问题。

管程机制(monitor)

1
2
3
4
5
只允许被一个进程调用的类
1. 管程的名称
2. 定义管程内部的共享数据结构（共享数据结构 = 可共享资源）
3. 对管程的操作
4. 对管程的初始化

条件变量(condition)

1
2
3
4
5
6
condition x;//声明一个条件变量x
x.value = 1;//初始化x
x.wait();//排队
x.signal();//唤醒一个阻塞进程

条件变量是没有值的，条件变量是一个数据结构，与信号量相比只是实现了“排队等待”功能。

进程间通信

低级通信：PV操作（信号量），信号

高级通信：高速率、多数据

1
2
3
4
5
6
7
8
9
1. 共享存储
	低级：基于数据结构
	高级：基于存储区
2. 消息传递
	直接通信方式
	间接通信方式
3. 管道通信
	以特殊文件的形式存在（通过FCB操作缓冲区）
	实际是一个固定大小缓冲区

进程通信的类型(直接通信和间接通信方式)

1
2
直接通信：发送进程将消息挂在目标进程的消息缓冲队列上
间接通信：通信双方通过信箱（共享数据结构的实体）交换信息，广泛应用与计算机网络中

消息传递系统中的几个问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1. 通信链路：
	1. 点对点、多点连接
	2. 无容量、有容量通信链路、
2. 消息的格式
3. 进程同步方式：
	1. 发送进程阻塞，接收进程阻塞：
		1. 用于进程之间紧密同步，且无缓冲
		2. 两个进程都处于阻塞状态，直到有消息传递
	2. 发送进程不阻塞，接收进程阻塞：
		1. 用于尽快将一个或多个消息发送给多个目标，应用广泛
		2. 接收进程平时处于阻塞状态，知道接收到消息才被唤醒，例如打印服务
	3. 发送、接收进程均不阻塞：
		1. 发送、接收进程无法继续运行时才阻塞
		2. 例如无法向消息队列发送信息（已满），或者无法从消息队列（已空）取得信息时
		3. 类似生产者消费者模型？

消息缓冲队列通信机制

在这种通信机制中， 发送进程利用send源语将消息直接发给接收进程，接收进程利用receive源语接收消息。使用了信号量互斥机制。

1
2
3
4
5
6
7
8
9
10
11
12
1. 消息缓冲队列通信机制中的数据结构
	1. 消息缓冲区
		1. 发送者进程标识符
		2. 消息长度
		3. 消息正文
		4. 指向下一个消息缓冲区的指针
	2. PCB中有关通信的数据项
		1. 消息队列首指针
		2. 消息队列互斥信号量
		3. 消息队列资源信号量
2. 发送源语
3. 接收源语

线程与进程的调度

线程与进程的基本概念

1
2
3
4
5
进程是资源分配的基本单位
线程是独立调度的基本单位，线程切换的代价远小于进程切换
线程不拥有系统资源（仅有一点保证独立运行的资源）
不同线程可以执行相同的程序，当一个程序被不同用户调用时，OS将其创建成不同的线程
线程没有创建态

多线程模型：

1
2
3
1. 多对一（一旦一个用户线程被阻塞，其他线程也动不了。因为只有一个核心线程）
2. 一对一
3. 多对多（核心线程少于用户线程）

调度的类型

1
2
3
1. 高级调度（作业调度）：外存->创建态->就绪态 内存与外存之间的调度
2. 中级调度（内存调度）：运行态<->挂起态（调入外存） 提高内存利用率和系统吞吐量
3. 低级调度（进程调度）：就绪态->运行态

调度队列模型

1
2
3
4
1. 作业调度为进程活动做准备，进程调度使进程正常活动起来
2. 中级调度将暂时不能运行的进程挂起
3. 作业调度次数最少，中级调度次数略多，进程调度最频繁
4. 进程调度（低级调度）是最基本的，不能或缺

调度方式

1
2
3
剥夺式调度（抢占式）：当进程正在处理器上运行时，系统可根据所规定的原则剥夺分配给此进程的处理器，并将其移入就绪队列，选择其他进程运行。

非剥夺式调度（非抢占式）：一旦某个进程开始运行后便不再让出处理器，除非此进程运行结束，或主动放弃处理器，或因发生某个事件而不能继续执行。

调度的目标

$$
CPU利用率 = \frac{CPU有效工作时间}{CPU有效工作时间 + CPU空闲等待时间}
$$

$$
周转时间 = 作业完成时间 - 作业提交时间
$$

$$
带权周转时间 = \frac{作业周转时间}{作业实际运转时间}
$$

$$
等待时间 = \sum_0^{\infty}{进程处于等待处理机的时间}
$$

$$
相应比R_p = \frac{等待时间 + 要求服务时间}{要求服务时间}
$$

进程调度算法

1
2
3
4
5
6
1. 先来先服务
2. 短进程优先
3. 时间片轮转
4. 基于优先级的调度算法
5. 多级队列
6. 多级反馈队列

多级反馈队列：

1
2
3
4
1. 设置多个就绪队列
2. 时间片随队列优先级增高而减小
3. 每个队列都采用FCFS
4. 按队列优先级调度，优先级高的队列为空时才调度低一级队列。新进入高优先级进程后，立即把处理机分配给高优先队列。

死锁

死锁的基本概念

  1. 系统资源的竞争

  2. 进程推进顺序非法

  3. 死锁产生的必要条件

    1
    2
    3
    4
    5
    6
    7
    1. 互斥条件：系统中存在临界资源，进程应互斥地使用这些资源

    2. 占有和等待条件：进程在请求资源得不到满足而等待时，不释放已占有资源

    3. 不剥夺条件：已被占用的资源只能由属主释放，不允许被其他进程剥夺

    4. 循环等待条件：存在循环等待链，其中，每个进程都在链中等待下一个进程所持有的资源，造成这组进程处于永远等待状态

死锁预防

破坏死锁产生的必要条件之一。

死锁避免与处理死锁的基本方法

银行家算法

死锁定理（死锁检测）

如果能消去资源分配图中所有的边，那么此图是可完全简化的。

S为死锁的条件是，当且仅当S状态的资源分配图是不可完全简化的。

原理和银行家算法差不多，只不过死锁检测发生在进程运行时，而死锁避免发生在进程运行前。

Chapter 3 内存管理

1
2
3
4
5
1. 内存管理的需求：重定位、内存保护、内存共享
2. 程序的装入和链接：静态装入和可重定位装入、静态链接、动态链接、运行时动态链接
3. 分区存储管理：分区方式（单一连续分区、固定分区、可变式分区）、分区分配算法（首次适应算法、循环首次适应算法、最佳适应法、最坏适应法等）
4. 段式管理与页式管理：段、页、碎片等基本概念、段式管理与页式管理机制
5. 虚拟内存：局部性原理、虚拟内存概念、请求分段与请求分页、段页式管理、段页式地址结构与地址转换、页面置换算法（OPT、先进先出、LRU、Clock、改进型 Clock 置换）、抖动

内存管理的需求

1
2
3
重定位：程序->进程，逻辑地址->物理地址
内存保护：各道作业在各自的存储空间内运行，互不干扰
内存共享：允许多个进程访问内存的同一部分

程序的装入和链接

链接

1
2
3
4
5
6
7
8
9
10
1. 静态链接
	1. 所有目标模块都使用同一套逻辑地址
	2. 外部调用符号也变换为逻辑地址：函数名换成逻辑地址
2. 装入时动态链接
	1. 边装入边链接
	2. 便于修改和更新
	3. 此方法是在装入时把每个目标及对应外部调用模块链接在一起装入内存，而实际上程序执行过程中，一些外部调用模块可能是用不上的
3. 运行时动态链接
	1. 目标模块需要时再调入内存和被链接到装入模块上
	2. 加快程序装入过程，节省大量内存空间

装入

1
2
3
4
5
6
7
8
9
10
1. 绝对装入
	1. 单道程序系统
	2. 事先知道程序将驻留在内存中的位置，用户编译程序后，产生绝对地址（与实际物理地址相同）的目标代码
2. 可重定位装入
	1. 多道程序系统
	2. 地址变换在装入时一次完成
	3. 分配要求的所有空间，运行期间不能移动
3. 动态运行时装入
	1. 地址变换在程序执行时进行
	2. 可以将程序分配到不连续的存储区

连续分配：分区存储管理

分区方式

1
2
3
1. 单一连续分区
2. 固定分区 -> 内部碎片
3. 可变式分区 -> 外部碎片

可变式分区：分区分配算法

1
2
3
4
1. 首次适应算法：从空闲链首开始，找到大小能满足要求的第一个空闲分区
2. 循环首次适应法（邻近适应）：从上次查找结束的位置开始继续查找，找到大小能满足要求的第一个空闲分区
3. 最佳适应法：空闲区递增链接，找到最小能满足的空闲分区（最多外部碎片）
4. 最坏适应法等：空闲区递减链接，找到最大能满足的空闲分区

回收内存时：相邻空闲分区将合并成一个大空闲分区

伙伴系统：固定分区和动态分区的折中

伙伴系统规定，无论已分配分区或空闲分区，其大小均为$$2^k，k\geq1$$。

合并时若当前空闲分区大小为$$2^i$$，则应将与伙伴分区合并为大小为$$2^{i+1}$$的分区。

1
2
3
4
1. 性能取决于查找空闲分区的位置和分割、合并空闲分区所花的时间：
	1. 顺序搜索算法 < 时间性能 < 分类搜索算法
	2. 分类搜索算法 << 空间性能 < 顺序算法
2. 分页、分段性能优于伙伴系统，但伙伴系统在多处理机系统中作为亿中有效的内存分配和释放的方法，仍有大量应用

离散分配：基本段式管理与页式管理

快表TLB

1
2
3
4
1. 基于局部性原理
2. 主存中的称为慢表
3. 快表中存储页表项
4. 慢表中的查询结果应该存入快表，若快表已满，则按照特定算法淘汰

页式管理机制

1
2
3
4
1. 提高内存利用率，不会产生外部碎片
2. 由硬件机制负责，对用户透明
3. OS为进程建立页表，页表是由页表项组成
4. 为了压缩页表，可以建立多级页表

地址结构：

页号 页内偏移

多级页表地址结构：

一级页号 二级页号 页内偏移

页表项结构：

页号 块号

物理地址RA ：

块号 页内偏移

段式管理

1
2
3
4
5
6
7
8
1. 按照用户进程中的自然段划分逻辑空间（程序段、栈段、数据段...）
2. 段式系统的段号、段内偏移必须由用户显式提供。高级语言中由编译器负责。
3. 段式系统方便共享
	1. 可共享段：纯代码（可重入代码），不可修改，不属于临界区
	2. 不可共享段：可修改的代码
4. 段式系统方便保护
	1. 存取控制保护
	2. 地址越界保护（产生越界中断）

逻辑地址：

段号 段内偏移

段表项结构：

段号 段长 段首地址

虚拟内存：

局部性原理

高速缓存能够提高OS性能的原理

1
2
1. 时间局部性：当某个数据被访问，不久后这个数据又将被访问（产生原因：循环操作）
2. 空间局部性：当某块存储单元被访问，不久后这块存储单元又将被访问（产生原因：指令顺序存放、顺序执行、数据簇聚存储）

虚拟内存概念

1
2
3
1. 请求分页存储管理
2. 请求分段存储管理
3. 请求段页式存储管理

内存分配策略

1
2
3
4
5
1. 固定分配局部置换：分配的物理块不变
2. 可变分配全局置换：发生缺页 -> 增加物理块 -> 调入页面
3. 可变分配局部置换：
	1. 发生缺页 -> 选一页置换
	2. 频繁发生缺页 -> 增加物理块 -> 调入页面

调入页面时机：

1
2
3
4
5
1. 预调页策略
	1. 用于进程的首次调入
	2. 由程序员指出先调入哪些页
2. 请求调页策略
	1. 运行期间调入

从何处调入页面：

1
2
3
4
5
6
7
请求分页系统中的外存分为两部分：
	1. 文件区：离散分配
	2. 对换区：连续分配
当发生缺页请求时，系统调入内存分为三种情况：
	1. 对换区空间足够：运行前将文件从文件区复制到对换区
	2. 对换区空间不足：文件中可能被修改的部分从文件区复制到对换区，不被修改的直接从文件区读取
	3. UNIX方式：未运行过的页面从文件区调入，运行过被换出的放在对换区

虚拟内存的特征：

1
2
3
1. 多次性：一个作业被分成多次调入内存
2. 对换性：再作业运行的过程中允许换出
3. 虚拟性：能从逻辑上扩充内存容量

请求分段与请求分页

请求分段

在分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。允许只装入少数段的用户程序和数据，即可启动运行。在运行过程中，再通过请求调段及分段置换将暂不运行的段调出，并调入即将运行的段。置换是以段为单位进行的。

请求分段需要硬件支持：

1
2
3
1. 请求分段的段表机制
2. 缺段中断机构
3. 地址变换机构
请求分页

页表项：

页号 物理块号 状态位 访问字段 修改位 外存地址

段页式管理

1
2
3
1. 提高内存利用率，反应程序逻辑结构，便于共享和保护
2. OS为每个进程建立一张段表，每个分段有一张页表（一张段表，多张页表）
3. 有段表寄存器记录作业的段首地址和段表长度（作用是寻址和防止越界）

逻辑地址：

段号 页号 页内偏移

段表项：

段号 段长 页表首地址

页面置换算法

FIFO可能出现belady异常，LRU和OPT不会出现belady

belady：页面异常次数随分配物理块数增加而增加

1
2
3
4
5
6
7
8
9
10
11
1. OPT：向后看
2. FIFO先进先出
3. LRU：向前看
4. Clock（最近未使用）：
	1. 只有一位访问位
	2. 向下找第一个访问位为0的页面换出
	3. 边找边将访问位为1的置0
5. 改进型 Clock 置换）：相比于CLock可以减少IO次数
	1. 找A=0, M=0
	2. 找A=0, M=1，边找边将A置0
	3. 重复第一步

抖动

1
2
3
4
5
1. 定义：对某一页面频繁调度
2. 抖动发生根本原因：系统中运行的今晨管太多，分配给每个进程的物理块少，不能满足正常运行的需求
3. 解决（工作集）：
	1. 工作集窗口 >= 工作集大小（取集合计算的性质）
	2. 驻留集：工作集中的页面调入到内存中

Chapter 4 设备管理

1
2
3
1. I/O系统的：基本概念、I/O控制方式（程序I/0、中断、DMA、通道）、相关数据结构、缓冲管理（单缓冲、双缓冲、循环缓冲、缓冲池）
2. 磁盘管理与磁盘调度算法：SSTF算法，SCAN算法，CSCAN算法，N-STEP-SCAN算法，FSCAN算法
3. 设备分配、设备处理、虚拟设备，Spooling系统

基本概念

I/O设备分类：

1
2
3
4
5
6
7
按信息交换的单位分类：
    1. 块设备（磁盘、硬盘）：有结构设备，速率高、可寻址
    2. 字符设备（打印机、终端）：无结构类型、速率低、不可寻址
按传输速率分类：
	1. 低速设备：键盘、鼠标
	2，中速设备：打印机
	3. 高速设备：磁盘、光盘

I/O设备接口：

1
2
3
4
5
6
7
8
9
10
11
CPU与控制器接口 <-> I/O逻辑 <-> 控制器与设备接口：
    1. CPU与设备控制器的接口
        1. 数据线
        2. 地址线
        3. 控制线
    2. I/O逻辑
        1. 用于实现对设备的控制
        2. 通过控制线与CPU交互，将收到的控制命令进行译码
    3. 设备控制器与设备的接口
        1. 一个设备控制器可以连接多个设备
        2. 每个接口中都存在数据、地址、控制三种类型的信号

设备控制器的功能：

1
2
3
4
5
6
1. 接收和识别CPU发来的命令（读、写、查找）
2. 数据交换，包括设备控制器之间的数据传输，以及控制器和主存之间的数据传输
3. 表示和报告设备的状态
4. 地址识别
5. 数据缓冲
6. 差错控制

I/O软件层次结构：

用户层I/O软件（read、write）
设备独立性软件（统筹管理所有I/O设备（调度与保护），提供系统调用接口、逻辑设备表存于此处）
设备驱动程序（对上对硬件传入的raw数据进行解码，对下命令翻译成对应的指令（机器码））
中断处理程序（对上传递硬件状态，对下直接操作硬件）
硬件

I/O控制方式

程序I/0（程序直接控制）

对外设进行循环检查

中断（中断驱动）

1
2
3
4
1. 允许I/O设备主动打断CPU的运行并请求服务
2. 一次读取两次中断
	1. 发出I/O指令后，需要中断阻塞提出I/O请求的进程
	2. 当传输完成时，需要中断对CPU发出信号

DMA

特点：

1
2
3
4
5
6
7
1. 基本单位是数据块
2. 内存与外存的数据交换不经过CPU
3. 仅在数据传送的开始和结束时才需要CPU干预，传输中由DMA控制器控制：
	1. 命令/状态寄存器(MA)
	2. 内存地址寄存器(MAR)
	3. 数据寄存器(DR)
	4. 数据计数器(DC)，计数的单位是数据总线的位宽，即一个字

工作过程：

1
2
3
1. CPU -> DMA控制器，设置MAR, DC初值
2. DMA控制器与存储器直接交互（请求总线 -> 进行传输）
3. 传送完成发出中断信号给CPU

通道

I/O通道是专门负责输入/输出的处理机，能进一步减少CPU的干预，实现CPU、通道、I/O设备三者并行操作

I/O通道与一般处理机的区别：

1
通道执行的类型单一，没有自己的内存，通道所执行的通道程序是放在主机的内存中，通道与CPU共享内存

I/O通道与DMA方式的区别：

1
2
1. DMA方式需要CPU来控制传输的数据块大小、传输的内存位置，而通道方式中这些信息是由通道控制的
2. 每个DMA控制器对应一台设备与内存传递数据，而一个通道可以控制多台设备与内存的数据交换

相关数据结构

1
2
3
4
5
1. 系统设备表(SDT) system device table
2. 设备控制表(DCT) device control table
3. 控制器控制表(COCT) controller control table 
4. 通道控制表(CHCT) channel control table
5. 逻辑设备表(LUT) logic unit table

逻辑设备表

逻辑设备名 物理设备名 驱动程序入口地址
/dev/tty 3 1024
/dev/printer 5 2046
… … …

配置系统设备表的多用户系统中的逻辑设备表格式：

逻辑设备名 系统设备表
/dev/tty 3
/dev/printer 5
… …

缓冲管理

1
2
3
C, 处理时间
T, 缓冲区（内存）传入工作区（CPU）时间
M, I/O设备传入缓冲区时间

引入缓冲区的目的：

1
2
3
4
1. 缓解CPU和I/O设备速率不匹配
2. 减少对CPU的终端频率，放宽对CPU中断响应时间的限制
3. 解决基本数据单元大小不匹配的问题（字节、比特）
4. 提高CPU和I/O设备之间的并行性

实现方法：

1
2
1. 硬件缓冲器
2. 缓冲区（使用部分内存）

单缓冲

$$
平均用时T = max(C,T) + M
$$

双缓冲

双缓冲提高了处理机和输入设备的并行程度
$$
平均用时T = max(C+M, T)
$$

循环缓冲

循环队列

缓冲池

1
2
3
4
5
6
7
8
9
三个队列：
	1. 空缓冲队列
	2. 装满输入数据的缓冲队列
	3. 装满输出数据的缓冲队列
四个缓冲区：
	1. 收容输入数据
	2. 提取输入数据
	3. 收容输出数据
	4. 提取数据数据

磁盘管理与磁盘调度算法

1
2
3
4
5
6
7
1. SSTF算法（最短寻找时间优先）
2. SCAN算法（电梯）
3. CSCAN算法（循环扫描）
4. N-STEP-SCAN算法：
	把磁盘请求队列分为若干个长度为N的子队列，按照FCFS顺序访问这些子队列，但是每个子队列里面都是按照SCAN算法处理。
5. FSCAN算法：
	将磁盘请求队列分为两个子队列，一个是当前所有请求队列，按照SCAN算法处理，另一个是扫描期间新出现的请求汇合成另一个子队列。

寻找时间 = 跨越n条磁道的时间 + 启动磁臂的时间：
$$
T_s = m * n + s,
$$
旋转延迟时间：磁头定位到某一磁道的扇区所需要的时间
$$
T_r = \frac{1}{2r}，r为磁盘的旋转速度
$$
传输时间：从磁盘读出/写入数据所经历的时间，取决于每次所读/写的字节数b和磁盘的旋转速度
$$
T_t = \frac{b}{rN}，r为磁盘转速，N为一个磁道上的字节数， rN为磁盘读取速率
$$
总平均存取时间：
$$
T_a = T_s + T_r + T_t = T_s + \frac{1}{2r} + \frac{b}{rN}
$$

优点 缺点
SSTF 性能比FCFS好 不能保证平均寻道时间最短，可能出现“饥饿”现象
SCAN 寻道性能较好，避免“饥饿”现象 不利于远离磁头一端的访问请求
C-SCAN 消除了对两端磁道请求的不公平
N-STEP-SCAN
FSCAN

设备管理

设备分配

1
2
3
1. 独占式设备
2. 分时式共享使用设备
3. 以SPOOLing方式使用外部设备：实现了虚拟设备功能，实质上实现了对设备的I/O操作的批处理

数据结构：

1
2
3
4
5
6
7
1. 系统设备表(SDT)
2. 设备控制表(DCT)
3. 控制器控制表(COCT)controller control table 
4. 通道控制表(CHCT) channel control table

   分配设备 -> 分配控制器 -> 分配通道
SDT -> DCT -> COCT -> CHCT

设备分配中应该考虑的问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1. 设备固有属性
	1. 独占性：对于独占设备，应采用独享分配策略（静态分配），即将一个设备分配给某进程后，便由该进程独占，直至该进程完成或释放该设备，然后，系统才能再将该设备分配给其他进程使用。这种分配策略的缺点是，设备得不到充分利用，而且还可能引起死锁。
	2. 共享性：对于共享设备，可同时分配给多个进程使用（动态分配），此时须注意对这些进程访问该设备的先后次序进行合理的调度。
	3. 可虚拟设备：由于可虚拟设备是指一台物理设备在采用虚拟技术后，可变成多台逻辑上的所谓虚拟设备，因而说，一台可虚拟设备是可共享的设备，可以将它同时分配给多个进程使用，并对这些访问该(物理)设备的先后次序进行控制。

2. 设备分配算法
	1. 先请求先分配
	2. 优先级
3. 设备分配的安全性：
    1. 安全分配方式：
        1. 进程发出I/O请求后就被阻塞，I/O完成时被唤醒
        2. CPU和I/O串行工作
        3. 进程被阻塞无法再请求资源，破坏了了造成死锁的四个必要条件之一的“请求和保持”条件
    2. 不安全分配方式
        1. 进程发出I/O请求后继续运行，仅当I/O设备被占用时阻塞
        2. 一个进程可以同时操作多个设备
        3. 进程在运行时可能提出新的请求，可能造成死锁

设备分配程序的改进 ：

1
2
3
4
5
6
7
1. 仔细研究上述基本的设备分配程序后可以发现: 
	1. 进程是以物理设备名来提出I/O请求的
	2. 采用的是单通路的I/O系统结构，容易产生“瓶颈”现象
	
2. 为此，应从以下两方面对基本的设备分配程序加以改进，以使独占设备的分配程序具有更强的灵活性，并提高分配的成功率。 
	1. 增加设备的独立性为了获得设备的独立性，进程应使用逻辑设备名请求I/O。这样，系统首先从SDT中找出第一个该类设备的DCT。若该设备忙，又查找第二个该类设备的DCT，仅当所有该类设备都忙时，才把进程挂在该类设备的等待队列上；而只要有一个该类设备可用，系统便进一步计算分配该设备的安全性。
	2. 考虑多通路情况为了防止在I/O系统中出现“瓶颈”现象，通常都采用多通路的I/O系统结构。此时对控制器和通道的分配同样要经过几次反复，即若设备（控制器）所连接的第一个控制器（通道）忙时，应查看其所连接的第二个控制器（通道），仅当所有的控制器（通道）都忙时，此次的控制器（通道）分配才算失败，才把进程挂在控制器(通道)的等待队列上。而只要有一个控制器（通道）可用，系统便可将它分配给进程。

设备处理（设备驱动程序+CPU发起的中断处理程序）

此处要区别中断处理程序是由设备无关软件发起，还是由驱动程序发起。中断仅仅是进程调度的信号，前者中断处理程序由操作系统负责；后者中断处理程序由设备生产厂家负责，由设备的类型、厂家、型号不同而不同。

当一个进程请求I/O操作时，该进程将被挂起，直到I/O设备完成I/O操作后，设备控制器便向CPU发送一中断请求，CPU响应后便转向中断处理程序：

1
2
3
4
5
1. 唤醒被阻塞的驱动进程
2. 保护被中断进程的CPU环境
3. 分析中断原因，转入相应的设备处理程序（设备驱动）
4. 中断处理，该中断处理过程因设备的不同而不同
5. 恢复被中断进程的现场

设备驱动程序的处理过程：

1
2
3
4
5
6
1. 将抽象要求转换为具体要求（此处开始引入设备特有的指令、机器码）
2. 检查 I/O 请求的合法性
3. 读出和检查设备的状态
4. 传送必要的参数
5. 工作方式的设置
6. 启动 I/O 设备

虚拟设备

1
2
3
1. 提高设备分配的灵活性和设备的利用率
2. 方便实现I/O重定向
3. 引入了设备独立性

逻辑设备表(Logical Unit Table, LUT)

1
2
3
1. 进程利用逻辑设备名请求服务
2. 系统为他分配一台相应的物理设备，并在LUT中建立一个表目
3. 之后进程利用逻辑设备名请求服务时，系统通过查找LUT来寻找对应的物理设备和驱动程序

Spooling系统

1
2
3
4
5
6
7
8
9
10
11
12
1. 输入井和输出井
	1. 磁盘中
	2. 输入井用于收容I/O设备输入的数据
	3. 输出井用于收容用户程序输出的数据
2. 输入缓冲区和输出缓冲区
	1. 内存中
	2. 输入缓冲区用于暂存输入设备送入的数据
	3. 输出缓冲区用于暂存从输出井送来的数据
3. 输入/输出进程
 	1. 用于模拟脱机输入、输出时的外围控制机
 	2. 输入进程：输入设备 -> 输入缓冲区 -> 输入井 -> 用户进程空间（内存）
 	3. 输出进程：用户进程空间 -> 输出井 -> 输出缓冲区 -> 输出设备（打印机）

Chapter 5 文件系统

1
2
3
4
1. 基本概念：文件和文件系统、目录、文件结构的物理结构和逻辑结构（顺序文件、索引顺序文件、索引文件、HASH 文件）、文件共享（基于索引节点、基于符号链接实现文件共享）
2. 外存分配方法：连续分配、链接分配、索引分配
3. 目录管理：单级目录、二级目录、多级目录
4. 文件存储空间的管理技术：位示图、空闲链表、索引

基本概念

文件和文件系统

文件：

1
2
1. 以硬盘为载体的存储字啊计算机上的信息集合
2. 用户在输入、输出中以文件为基本单位

文件的属性：

1
2
3
4
5
6
7
8
1. 名称
2. 类型
3. 创建者
4. 所有者
5. 位置
6. 大小
7. 保护
8. 创建时间

文件控制块(FCB) = 文件目录项:

1
2
3
1. 基本信息：文件名、物理位置、逻辑结构、物理结构
2. 存取控制信息：ugo的存储权现
3. 使用信息：建立时间、上次修改时间

索引节点(inode)：在检索目录时，文件的其他描述信息不会用到，也不需要调入内存。因此，有的系统(UNIX)便采用了文件名和文件描述信息分开的方法，使文件描述信息单独形成一个称为索引结点的数据结构
$$
FCB = 文件目录项
\begin{cases}
文件名\
i结点（文件描述信息）
\end{cases}
$$
磁盘索引结点：存放在磁盘上的索引结点

1
2
3
4
5
6
7
1. 文件主标识符
2. 文件类型：普通文件、目录文件、特殊文件
3. 文件存取权现
4. 文件物理地址
5. 文件长度
6. 文件链接计数
7. 文件存取时间：最近存取、最近修改的时间

内存索引结点：文件被打开时，从硬盘索引结点中复制到内存，增加了以下内容

1
2
3
4
5
1. 索引结点编号
2. 状态：有无被上锁
3. 访问计数：有多少进程正在访问
4. 逻辑设备号：文件所属系统的逻辑设备号
5. 链接指针：指向空闲链表、散列队列的指针

文件操作：

1
2
3
4
5
6
1. 创建文件
2. 写文件
3. 读文件
4. 重新定位文件：将文件位置指针重新定位到新值
5. 删除文件：释放存储空间，删除目录条目
6. 截断文件：保持文件属性不变，删除文件内容

打开文件表：

1
2
3
4
5
6
7
8
9
10
1. 调用open()后，文件属性从硬盘复制到内存的打开文件表中，返回用户文件属性在打开文件表中的编号
2. 内核为每个进程维护一个打开文件表（返回给用户的索引），索引指向的是系统范围的打开文件表，真正保存了文件属性
3. 其他进程调用open()打开此文件，仅在其进程的打开文件表增加一项指向系统范围打开文件表的索引
4. 文件名不必是打开文件表的一部分，一旦完成FCB在磁盘上的定位，系统就不再使用文件名，只要文件未关闭，系统就使用打开文件表来进行（允许多个进程打开同个文件的系统中应该还是要保留文件名，用于在打开文件表中检索）
5. 对于访问打开文件表的索引，UNIX称之为文件描述符，Windows称之为文件句柄
6. 每个打开文件表都关联如下信息：
	1. 文件指针
	2. 文件打开计数
	3. 文件磁盘位置
	4. 访问权现

目录

文件结构的物理结构和逻辑结构（顺序文件、索引顺序文件、索引文件、HASH 文件）

文件共享（基于索引节点、基于符号链接实现文件共享）

符号链接

1
2
3
1. 建立符号链接时，引用计数值直接复制
2. 删除操作对于符号链接是不可见的
3. 访问时发现文件不存在，则删除此符号链接

外存分配方法：

连续分配

1
2
3
4
5
6
优点：
	1. 顺序访问容易
	2. 顺序访问速度快
缺点：
	1. 必须要有连续的存储空间
	2. 必须事先知道文件的长度

链接分配

1
2
3
4
5
6
1. 显式链接：
	1. 在采用隐式链接分配方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。指向下一个盘块的指针存放在每个盘块里
	2. 主要问题：只适合顺序访问
2. 隐式链接：文件分配表(FAT)：
	1. 把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中，该表在整个磁盘仅设置一张
	2. 由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数

索引分配

1
2
3
4
5
6
1. 单级索引分配：直接访问
2. 多级索引分配
3. 混合索引分配;
	1. 直接地址
	2. 一次间接地址
	3. 多次间接地址

目录管理

单级目录

文件名 物理地址 文件说明 状态位
文件名1
文件名2
… 
1
2
3
4
5
6
7
优点：
	1. 简单
	2. 能实现按名存取
缺点：
	1. 查找速度慢
	2. 不允许重名
	3. 不便实现文件共享

二级目录

为了克服单级目录所存在的缺点，可以为每一个用户建立一个单独的用户文件目录UFD(User File Directory)。

用户名 指向子目录指针
Alice
Bob
… 
1
2
3
4
5
优点：
	1. 提高检索目录的速度
	2. 在不同的目录中允许重名文件存在
	3. 不同的用户可以使用不同的文件名访问系统中的同一个文件
缺点：在需要多用户合作时，不同的用户可以使用不同的文件名访问系统中的同一个文件，不利于共享文件

多级目录

文件存储空间的管理技术

位示图

空闲链表

1
2
1. 空闲表
2. 空闲链表

索引（成组链接法）