操作系统知识点梳理

绪论

操作系统的定义

操作系统是计算机系统中的一个系统软件，他管理和控制计算机系统中的硬件及软件资源，在计算机与其用户之间起到接口的作用。

操作系统的基本类型

1. 批处理操作系统
2. 分时系统
3. 实时系统
4. 通用操作系统
5. 个人计算机操作系统
6. 网络操作系统
7. 分布式操作系统

操作系统功能

1. 处理机管理
2. 存储管理
3. 设备管理
4. 信息管理
5. 用户接口

操作系统的特征

1. 并发性
2. 共享性
3. 随机性
4. 虚拟
5. 异步性

操作系统用户界面

作业的定义

它由程序、数据和作业说明书组成，系统通过作业说明书控制文件形式的程序和数据，使之执行和操作。

一般用户的输入输出方式

1. 联机输入输出方式
2. 脱机输入输出方式
3. 直接耦合方式
4. spooling系统
5. 网络联机方式

进程管理

进程的定义和特征

定义：并发执行的程序在执行过程中分配和管理资源的基本单位。
特征（与程序的区别）：进程是一个动态概念；进程具有并发特征；进程是竞争计算机系统资源的基本单位；不同的进程可以包含同一程序，只要该程序所对应的数据采集不同。

进程状态及其转换

进程的组成

进程组成：程序、数据、PCB

PCB是记录OS所需、用于描述进程当前情况以及控制进程运行的全部信息，是进程存在的唯一标志，常驻内存。

进程的互斥与同步

• 进程互斥：进程在运行中竞争系统资源，对于独占型资源，只能一个进程使用完，另一个进程才能使用。
• 进程同步：异步环境下，互相合作的进程按各自独立的速度向前推进，但在某些确定点上必须协调工作。

互斥、同步机制遵循原则

1. 空闲让进
2. 忙则等待
3. 有限等待
4. 让权等待

前驱图

实现：信号量与P、V原语操作
v就是箭头指向别人，p就是被别人指
经典问题：生产者——消费者、小和尚与老和尚

进程通信

1. 高级通信：会话式、主从式、消息缓冲机制、邮箱通信
2. 低级通信

死锁问题

产生死锁问题的必要条件：

1. 互斥条件
2. 不剥夺条件
3. 部分分配
4. 环路条件

避免死锁的经典问题：银行家算法
设系统中有三种类型的资源（A、B、C）和五个进程（P1、P2、P3、P4、P5），A资源的数量是17，B资源的数量是6，C资源的数量是19。在T0时刻的状态如下：若当前剩余资源（A、B、C）分别为（2，3，3）。请采用银行家算法写出它的安全序列。
若P4在T0时刻提出（1，1，0）时是否存在安全序列。

	资源最大需求	已分配资源量
P1	0 0 6	4 0 5
P2	1 3 4	4 0 2
P3	2 1 1	2 1 4
P4	3 4 7	2 1 2
P5	1 1 1	3 1 3

---

解：

进程	max	allocation	need	available
P1	0 0 6	4 0 5	0 0 1	2 3 3
P2	1 3 4	4 0 2	0 3 2
P3	2 1 1	2 1 4	0 0 0
P4	3 4 7	2 1 2	1 3 5
P5	1 1 1	3 1 3	0 0 0

进程	work	allocation	need	work+allocation
P3	2 3 3	2 1 4	0 0 0	4 4 7
P4	4 4 7	2 1 2	1 3 5	6 5 9
P5	6 5 9	3 1 3	0 0 0	9 6 12
P1	9 6 12	4 0 5	0 0 1	13 6 17
P2	13 6 17	4 0 2	0 3 2	17 6 19

安全序列为P3、P4、P5、P1、P2

---

P4请求（1，1，0）< need（1，3，5） P4请求（1，1，0）< available（2，3，3）

进程	max	allocation	need	available
P1	0 0 6	4 0 5	0 0 1	1 2 3
P2	1 3 4	4 0 2	0 3 2
P3	2 1 1	2 1 4	0 0 0
P4	3 4 7	3 2 2	0 2 5
P5	1 1 1	3 1 3	0 0 0

进程	work	allocation	need	work+allocation
P3	1 2 3	2 1 4	0 0 0	3 3 7
P4	3 3 7	3 2 2	0 2 5	6 5 9
P5	6 5 9	3 1 3	0 0 0	9 6 12
P1	9 6 12	4 0 5	0 0 1	13 6 17
P2	13 6 17	4 0 2	0 3 2	17 6 19

存在安全序列P3、P4、P5、P1、P2

---

线程与进程的区别

线程是进程的一部分；它没有自己的地址空间；它和进程中的其他线程一起共享分配给该进程的所有资源。

线程状态转换图

处理及调度

作业状态

提交、收容、执行和完成四个状态

调度等级

• 高级调度：按一定原则选出一些作业，并分配必要的资源，建立根进程以使该作业的进程获得竞争处理机的权力。
• 中级调度：按给定的原则，把处于就绪状态或等待状态的的进程调入内存，或交换到外存交换区。
• 低级调度：按照某种方法选取一个处于就绪状态的进程占用处理机。

调度算法

1. FCFS（先来先服务）
2. SJF（最短作业优先）
3. HRN（最高响应比）

---

例题：

单道环境下的四个作业，进入系统的时间如下：写出先来先服务算法、最短作业优先算法，并求出平均周转时间和带权平均周转时间（保留两位小数）

作业	进入时间	运行时间(分钟)
job1	8:00	120
job2	8:50	50
job3	9:00	10
job4	9:50	20

解：

先来先服务

作业	进入时间	运行时间(分钟)	开始时间	结束时间	周转时间	带权周转时间
job1	8:00	120	8:00	10:00	2	1
job2	8:50	50	10:00	10:50	2	2.4
job3	9:00	10	10:50	11:00	2	12
job4	9:50	20	11:00	11:20	1.5	4.5

周转时间=结束时间-进入时间
带权周转时间=周转时间/运行时间

平均周转时间：(2+2+2+1.5)/4≈1.88
带权平均周转时间：(1+2.4+12+4.5)/4≈4.98

最短作业优先

作业	进入时间	运行时间(分钟)	开始时间	结束时间	周转时间	带权周转时间
job1	8:00	120	8:00	10:00	2	1
job3	9:00	10	10:00	10:10	7/6	7
job4	9:50	20	10:10	10:30	2/3	2
job2	8:50	50	10:30	11:20	2.5	3

平均周转时间：(2+7/6+2/3+2.5)/4≈1.58
带权平均周转时间：(1+7+2+3)/4≈3.25

最高响应比

作业	进入时间	运行时间(分钟)	开始时间	结束时间	周转时间
job1	8:00	120	8:00	10:00	2
job3	9:00	10	10:00	10:10	7/6
job2	8:50	50	10:10	11:00	13/6
job4	9:50	20	11:00	11:20	1.5

10:00计算响应比
job2：(70+50)/50=2.4
job3：(60+10)/10=7
job4：(10+20)/20=1.5
所以选择job3

10:10计算响应比
job2：(80+50)/50=2.6
job4：(20+20)/20=2
所以选择job2
平均周转时间：(2+7/6+13/6+1.5)/4≈1.71

存储管理

存储管理的基本任务和主要功能

基本任务：主存空间分配、地址变换、存储保护和存储扩充

虚拟存储器和地址重定位

虚拟存储器概念：

为解决内存小而作业大、作业多的矛盾，应该把一个程序当前正在使用的部分放在内存，而其余部分放在磁盘上。

地址重定位概念：

内存地址的集合称为内存空间或物理地址空间。内存中，每一个存储单元都与相应的内存地址的编号相对应，显然，内存空间是一维线性的。

分区、分页、分段三者的区别

区别：

覆盖和交换

覆盖技术概念：

程序划分为若干个功能上相对独立的程序段，按照程序逻辑结构让那些不需要同时执行的程序端共享同一块内存区。

交换技术概念：

对象是进程，等待状态的进程驻留内存会造成存储空间的浪费。因此，有必要把处于等待状态的进程换出内存。交换技术是实现此目标的常用方法之一。

页面置换算法

1. 先进先出置换算法（FIFO）：淘汰存在次数最多的
2. 最佳置换算法（OPT）：淘汰未来最久不会被用到的
3. 最近最久未使用算法（LRU）：淘汰最近最左边的那个

计算缺页率教程

根据逻辑地址求物理地址

页号	块号
0	2
1	4
2	6
3	8

已知每页大小2048字节，求逻辑地址4865对应的物理地址。

解：页号=逻辑地址/页大小=4865/2048=2
页内地址=逻辑地址%页大小=4865%2048=769
第2页对应6块
物理地址=块数*块大小(页大小)+页内地址=6*2048+769=13057

文件系统

文件和文件系统、文件系统功能

文件：

文件是一段程序或数据的集合

文件系统：

操作系统中与管理文件有关的软件和数据称为文件系统

功能：

1. 对文件空间进行统一管理
2. 实现按名存取，有用户可见的文件逻辑结构
3. 文件的物理结构
4. 完成文件的查找
5. 完成文件的共享和保护

磁盘调度算法

1. 顺序的
2. 先排序在找最近的

设备管理

设备管理的目标和任务

目标：

对计算机输入输出系统的管理

任务：

1. 选择和分配输入输出设备
2. 控制输出输出设备和CPU之间交换数据
3. 为用户提供友好的透明接口
4. 提高并行操作度，提高操作系统效率

数据传送控制方式

1. 程序直接控制方式
2. 中断方式
3. DMA方式

中断技术、中断处理过程

使CPU暂时中断当前正在执行的程序，转去执行相应的急需处理的程序，处理完毕后返回中断处继续执行

中断处理过程：

1. 检查响应中断条件是否满足
2. 如果CPU响应中断，则CPU关中断，使CPU进入不可再次响应中断的状态
3. 保存被中断进程现场
4. 分析中断原因，调用中断处理子程序
5. 执行中断处理子程序
6. 退出中断，恢复被中断进程的现场
7. 开中断，CPU继续执行