操作系统期末速成-阿南达文事网

操作系统期末速成

参考书籍：郁红英第四版计算机操作系统、王道操作系统。内容以老师提供重点为主，参考价值有限。

文章目录

操作系统期末速成
- 第1章 OS引论
- - 1.1 产生和发展（p15）
  - 1.2 主要功能（p20，细节）
  - 1.3 操作系统的类型（p25）
  - 1.4 分时系统的特点（p28）
- 第2章进程与线程
- - 2.1 单道程序执行的特点（p49）
  - 2.2 进程的状态（p52）
  - 2.3 进程的静态描述（p56）
  - 2.4 PCB的作用和基本内容（p56）
  - 2.5 线程的作用、进程和线程的比较（p72）
- 第3章进程同步和通信
- - 3.1 进程的关系（p75）
  - 3.2 临界资源和临界区（p77）
  - 3.3 信号量的使用方法（p82）
  - 3.4 PV原语
  - 3.5 进程同步和互斥问题
  - 3.6 经典问题（哲学家进餐问题）（p87）
  - 3.7 进程通信的方式（p98）
- 第4章调度和死锁
- - 4.1 调度类型（p105）
  - 4.2 先来先服务调度算法和最短作业优先调度算法的应用（p108-109）
  - 4.3 死锁的概念（p113）
  - 4.4 死锁的解决方法（p118-125）
  - 4.5 系统的安全状态、银行家算法、系统资源分配图
- 第5章存储管理
- - 5.1 重定位的方法（p127）
  - 5.2 连续分配存储管理，可变分区分配算法（p133）
  - 5.3 页表结构，页式存储管理的地址转换（p134）
  - 5.4 分页和分段的区别（p141）
- 第6章虚拟存储管理
- - 6.1 虚拟存储器的特点（p150）
  - 6.2 请求页式管理页表结构（p150）
  - 6.3 请求页式存储管理的页面调入策略、FIFO算法进行页面置换（p154）
- 第7章设备管理
- - 7.1 DMA控制方式的特点（p173）
  - 7.2 通道的作用（p174）
  - 7.3 设备固有属性（p176）
  - 7.4 设备独立性（p178）
  - 7.5 SPOOLing技术的特点和作用（p182）
  - 7.6 硬盘的结构（p186）
  - 7.7 磁盘调度（p189）
- 第8章文件系统
- - 8.1 文件类型（p210）
  - 8.2 文件逻辑结构的组织（p214）
  - 8.3 文件目录的概念和包含的信息（p217）
  - 8.4 树形目录的作用（p221）
  - 8.5 文件物理结构（p228）
- 第九章课后习题模拟
- - 9.1 进程同步与通信问题：
  - 9.2 调度与判断死锁问题：
  - 9.3 页式存储管理问题：
  - 9.4 磁盘调度问题

第1章 OS引论

1.1 产生和发展（p15）

操作系统的特征：

1.2 主要功能（p20，细节）

1.3 操作系统的类型（p25）

批处理、分时、实时为主：

1.4 分时系统的特点（p28）

第2章进程与线程

2.1 单道程序执行的特点（p49）

2.2 进程的状态（p52）

主要状态为 就绪态运行态阻塞态（书本中终止态又为退出态）

2.3 进程的静态描述（p56）

PCB是给操作系统识别的，程序段和数据段是进程自己所使用

2.4 PCB的作用和基本内容（p56）

PCB的作用：为了描述和控制程序的并发执行；让操作系统对每个并发执行单独的程序（含数据）来控制管理
PCB的基本内容：

2.5 线程的作用、进程和线程的比较（p72）

第3章进程同步和通信

常见英文：semaphore==>信号量；mutex==>互斥；philosopher==>哲学家；block==>阻塞

3.1 进程的关系（p75）

3.2 临界资源和临界区（p77）

临界资源： 某段时间内只允许一个进程使用的资源
临界区： 每个进程中访问临界资源的那段程序

3.3 信号量的使用方法（p82）

信号量操作通常有两种基本操作：

P操作（等待操作或减操作）：尝试获取信号量，如果计数器不为0，则计数器减一，继续执行；如果计数器为0，则进程或线程将被阻塞等待，直到资源可用为止。
V操作（发信号操作或增操作）：释放信号量，如果有其他进程或线程在等待该信号量，则唤醒其中一个或多个等待的进程或线程，使其有机会继续执行。

PV操作的名称来自荷兰语单词：

P（Probeer）代表尝试或等待。
V（Verhoog）代表增加或释放。

3.4 PV原语

//信号量包括一个整型 、等待队列queue
struct semaphore{int value;struct PCB *queue;
}
//wait函数为 p操作
void wait(semaphore s)
{	s.value=s.value-1;if(s.value<0)block(s.queue);/*进程堵塞，放入等待队列s.queue*/
}
//signal函数为 v操作
void signal(semaphore s)
{	s.value=s.value+1;if(s.value<=0)wakeup(s.queue);/*进程唤醒，从等待队列s.queue中取出，放入等待队列*/
}

3.5 进程同步和互斥问题

互斥问题：参照课本，基础的互斥问题在临界区的前后增加 p、v操作即可

同步问题：参照课本 v操作放在先执行的进程的临界区代码后； p操作在后执行的进程的临界区代码前

同步问题示例1：（小疑惑：为什么p3，p4执行完成后不v。估计是影响不大）

同步问题示例2:

3.6 经典问题（哲学家进餐问题）（p87）

哲学家：0～4 并用信号数组设置筷子信号量。每个哲学家身边的筷子为：i 、（i+1）%5
如果采用课本算法：

semaphore chopstick[5]={1,1,1,1,1};
void philosopher(int i)
{
while(true)
{P(chopstick[i]);P(chopstick[i+1]%5);...;eat;...;V(chopstick[i]);V(chopstick[i+1]%5);...;think;...;
}
}

五个人同时拿起左边的筷子，会都阻塞并且拿不到右边的筷子。发生死锁。

解决方案1：设置最多只可以四个哲学家同时进餐；就会至少有一个完成进餐释放左右筷子资源
解决方案2：要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子；偶数号哲学家相反。这样
如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。
解决方案3：“同时拿起两个筷子才可以进餐”，也就是书本所说的再写一个信号量。（速成可以。虽然不会死锁，但也会出现因为mutex死锁，下一个人拥有左右资源但不可以进餐的情况。）
参照代码：

semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex = 1;
void philosopher(int i)
{
while(true)
{	p(mutex);P(chopstick[i]);P(chopstick[i+1]%5);v(mutex);...;eat;...;V(chopstick[i]);V(chopstick[i+1]%5);...;think;...;
}
}

3.7 进程通信的方式（p98）

第4章调度和死锁

4.1 调度类型（p105）

4.2 先来先服务调度算法和最短作业优先调度算法的应用（p108-109）

周转时间 = 完成时间 - 到达时间
带权周转时间 = 周转时间 / 运行时间
等待时间 = 周转时间 - 运行时间
平均时间： ➗进程数
如果是有计算又有I/O操作的进程，等待时间是周转时间-运行时间-I/O操作时间
先来先服务（FCFS ，first come first serve）：

最短作业优先调度（SJF，shortest job first）：

例题展示：

4.3 死锁的概念（p113）

死锁通常发生在两个或多个不同程序对应的进程或线程使用的时候。
死锁涉及两个或者多个进程对资源的需求引起的冲突

4.4 死锁的解决方法（p118-125）

4.5 系统的安全状态、银行家算法、系统资源分配图

安全序列：如果系统按照此顺序分配资源，每个进程都能顺利完成。
安全状态：只要能找到一个安全序列，系统就是安全状态
不安全状态：找不到安全序列，之后的进程可能无法顺利执行。如果有进程提前归还，也可能重新回到安全状态。不过正常考虑最坏情况

如果系统处于安全状态；一定不会死锁。
如果系统处于不安全状态；可能发生死锁。
（发生死锁时一定是不安全状态）

银行家算法：

系统资源分配图： 方框为资源中间的点为个数圆形为进程箭头方向代表申请资源和分配资源

第5章存储管理

5.1 重定位的方法（p127）

5.2 连续分配存储管理，可变分区分配算法（p133）

5.3 页表结构，页式存储管理的地址转换（p134）

假设一个页表结构如下：

页号	块号
0	3
1	7
2	2
3	9
4	5

进行地址转换，将逻辑地址转换为物理地址。
假设逻辑地址为0x214，页大小为4KB（即2^12字节），物理块大小也为4KB。

物理地址 = (块号 × 物理块大小) + 页内偏移

对于逻辑地址0x214 二进制0000 0010 0001 0100其中前4位的0000代表页号0；后12位是页面偏移

现在我们可以使用基本公式进行地址转换：

物理地址 = (3 × 4KB) + 0x214

5.4 分页和分段的区别（p141）

方面	分页	分段
物理单位	页	段
存储原因	减少碎片，提高内存利用率	满足用户需求
大小	固定大小的页	可变长度的段
地址结构	页号 + 页内位移	段号 + 段内地址
逻辑地址空间	一维	二维

第6章虚拟存储管理

6.1 虚拟存储器的特点（p150）

6.2 请求页式管理页表结构（p150）

状态位：指示该页是否调入内存
访问字段：记录本页多长时间没被访问
修改位：表示该页调入内存后是否被修改
外存地址：指出该页的外存地址，供调入该页时使用

6.3 请求页式存储管理的页面调入策略、FIFO算法进行页面置换（p154）

FIFO算法： 先入先出置换算法

第7章设备管理

7.1 DMA控制方式的特点（p173）

DMA：Direct Memory Access 直接存储器存取。

基本单位是数据块
所传的数据是从设备直接送入内存的，或者相反
只在传送一个或多个数据时，才需要CPU干预。整块数据的传送是在DMA控制器的控制下完成

7.2 通道的作用（p174）

通道的作用	对比DMA
提高数据传输效率	以字节为单位的中断方式减少了CPU的干预，而通道以数据块为单位进行传输，提高效率和速度
减少CPU的干预	CPU每次发送一条I/O指令，只能读写一个连续的数据块。通道可以对一组数据块进行读写操作，减轻CPU负担
并行工作	CPU和通道之间的并行工作，提高整个系统的资源利用率
简化操作	通道处理程序执行I/O任务，简化CPU操作步骤

7.3 设备固有属性（p176）

7.4 设备独立性（p178）

也称为设备无关性；用户独立于具体使用的物理设别。操作系统把逻辑设备名转换为物理设备名

7.5 SPOOLing技术的特点和作用（p182）

假脱机技术；

作用： 把独占设备改造成共享设备

下图参照理解SPOOLing原理

7.6 硬盘的结构（p186）

7.7 磁盘调度（p189）

先来先服务
最短寻道
扫描算法
循环扫描

第8章文件系统

考的少，不过多展开

8.1 文件类型（p210）

8.2 文件逻辑结构的组织（p214）

8.3 文件目录的概念和包含的信息（p217）

文件控制块： File Control Block （FCB）

8.4 树形目录的作用（p221）

树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。
树形结构不便于实现文件的共享。为此，提出了 “无环图目录结构”。

绝对路径：从根目录出发
相对路径：每次从根目录出发，太过低效。就从当前路径出发

8.5 文件物理结构（p228）

第九章课后习题模拟

参见课本第四章、第五章、第七章课后习题

9.1 进程同步与通信问题：

9.2 调度与判断死锁问题：

9.3 页式存储管理问题：

9.4 磁盘调度问题