操作系统复习笔记

基本上就是各种考点的概念集合，简短无力但是有用。

引论

定义

介于计算机硬件和应用软件中间的软件系统

主要功能

1. 处理器管理
2. 存储管理
3. 设备管理
4. 文件管理
5. 用户接口
6. 网络和通信管理

基本特征

1. 并发性
2. 共享性
3. 虚拟性
4. 不确定性

逻辑结构

1. 单内核结构，灵活快，调用复杂，难以维护
2. 分层式结构，解耦，易于维护和验证，速度慢
3. 微内核结构，一致性结构，易于拓展和修改，可以执行好，良好的分布式支持，效率高于分层

运行模型

1. 独立运行
2. 嵌入到用户进程
3. 作为独立进程运行

分类

1. 单道批处理
2. 多道批处理
3. 分时
4. 实时
5. 网络
6. 分布式

处理器管理

进程

一个独立的可以调度的活动，aka 运行的程序

进程与程序区别

1. 程序是指令的静态有序集合，进程是一次CPU上的执行过程
2. 进程有生命周期
3. 进程是独立运行的基本单位
4. 一个程序的执行可以包含多个进程，不同的进程也可以包含同一个程序
5. 进程由程序段、数据段、PCB构成

进程结构

程序段 + 数据段 + PCB（Process Control Block）

进程模型

三态模型

三状态模型

1. 运行：获得了资源且正在执行
2. 阻塞：发生了等待事件例如IO等
3. 就绪：获得除CPU以外的所有资源

五态模型

五状态模型

CPU调度策略

三级调度是一种层次化的CPU调度策略，包括高级调度（作业调度）、低级调度（进程调度）和中级调度（内存调度）。高级调度选择作业调入内存，低级调度选择下一个执行的进程，中级调度优化内存利用。它们分别控制系统的长期资源分配、进程的执行顺序和内存中进程的调整，以提高系统性能和资源利用。

周转时间、带权周转时间、响应时间

周转时间 = 完成时间 - 到达时间

带权周转 = 周转时间 / 运行时间

响应时间：发起请求到首次响应的时间间隔

调度算法

FCFS（先来先服务）

维护一个队列，先来先服务

SPF （短作业优先）

从后备队列中选择运行时间最短的

RR （时间片轮转）

CPU时间分片的FCFS

HRRF（高响应比优先）

\[ R_p = \frac{响应时间}{运行时间} = \frac{运行时间+等待时间}{运行时间} = 1 + \frac{等待时间}{运行时间} \]

每次计算后选择最高的执行

优先级调度

1. 静态优先级

2. 动态优先级

3. 抢占式：允许更高优先级的进程/线程抢占CPU

4. 非抢占式：直到阻塞才会放弃使用权

进程同步与通信

同步机制的准则

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

信号量

含义

P （Proberen） acquire

V （Verhogen） release

1. \(value > 0\) 资源可用数量
2. \(value = 0\) 资源为空
3. \(value < 0\) 则 \(|value|\) 为等待该资源的阻塞的进程数

伪代码

typedef struct 
{
    int value;
    struct PCB* L;
} Semaphore;

P

void P(Semaphore S) {
    lock interrupts;
    s.value = s.value - 1;

    if(s.value < 0) {
        i.status = 'block';
        Insert(BlockQueue, i)
        unlock interrupts;
        Scheduler(); //执行调度程序调度另一就绪进程运行
    } else {
        unlock interrupts;
    }
}

V

void V(Semaphore S) {
    lock interrupts;
    s.value = s.value + 1;

    if(s.value <= 0) {
        Remove(BlockQueue, i);
        i.status = 'ready';
        Insert(ReadyQueue, i); 
    } 
    
    unlock interrupts;
}

临界区保护（语言模型生成内容）

在临界区保护中，存在几条必须遵守的原则，其中最有可能的原则包括：

1. 互斥性（Mutual Exclusion）：在任何时刻，只允许一个进程进入临界区访问共享资源。这是最基本的原则，确保共享资源不会同时被多个进程访问，避免数据的不一致性和竞态条件的发生。

2. 公平性（Fairness）：每个进程有公平的机会进入临界区。确保各个进程按照一定的顺序和优先级获得临界区的访问权，避免某个进程长时间占用临界区而导致其他进程饥饿。

3. 有限等待（Bounded Waiting）：任何进程在获取临界区访问权限前都有一个有限的等待时间。确保没有进程永远被其他进程拒绝访问临界区，避免产生死锁等问题。

这些原则的遵守可以提高临界区保护的有效性和可靠性。

互斥性是最重要的原则，因为它保证了共享资源在同一时间只能被一个进程访问，避免了数据不一致性和竞态条件。如果没有互斥性，多个进程同时修改共享资源可能导致数据错乱或无效的结果。

公平性是为了确保每个进程都有公平的机会访问临界区，避免某个进程长时间占用临界区导致其他进程无法获得资源。公平性原则可以提高系统的公正性和可靠性。

有限等待原则是为了防止某个进程永远等待临界区访问的情况发生，保证所有进程都能够在有限的时间内获得临界区的访问权限。这样可以避免系统陷入死锁状态，提高系统的稳定性和可用性。

死锁

原因

1. 系统资源不足
2. 进程推进顺序不当

必要条件

1. 互斥条件，进程对所获得的资源进行排他性使用。
2. 请求和保持条件，一个进程请求资源得不到满足而阻塞自己时，并不释放已分配给它的资源
3. 不可抢占条件，在该进程的资源未使用完毕时，其他进程不可抢占
4. 循环等待条件，至少两个进程构成了循环等待链

银行家算法

进程通信的方式

低级通信

信号量等，一般用于互斥与同步的工具。

高级通信

共享内存

划出一块内存区作为共享数据区，待通信的进程双方将虚拟地址空间映射到共享分区上

消息缓冲

1. 发送者设置发送区并填入待发送的消息
2. 发送者申请缓冲区并将消息从发送区送到缓冲区，并附加发送进程和消息的元信息至缓冲区，最后将缓冲区挂载到接收方的消息链上
3. 接收者设置接受区
4. 从消息链上取下第一条消息复制到接受区并释放该消息缓冲区

信箱

1. 若接收方信箱已满则发送方阻塞
2. 若接收方接收信息时信箱为空则阻塞

// 有点像是 golang 的 channel ？

管道通信

1. 管道是一种单向通信方式，可以在一个进程中创建管道，然后将其连接到另一个相关进程。
2. 管道可以分为匿名管道（Anonymous Pipe）和命名管道（Named Pipe）两种类型。
3. 匿名管道是一种临时的、单向的管道，通常用于有亲缘关系（如父子进程）的相关进程之间通信。
4. 命名管道是一种具有持久性的、命名的管道，可以在无亲缘关系的进程之间进行通信。
5. 管道的操作方式是基于文件描述符（File Descriptor）进行的，进程通过文件描述符来读取和写入管道中的数据。
6. 管道可以实现进程间的单向通信，其中一个进程负责写入数据到管道，另一个进程负责从管道中读取数据。
7. 管道通信是一种同步阻塞的通信方式，当管道为空时，读取进程会被阻塞，直到有数据可读取；当管道满时，写入进程会被阻塞，直到有空间可写入。

存储管理

地址相关的名词

1. 逻辑地址：程序中的地址
2. 逻辑地址空间：一个程序的所有逻辑地址的集合
3. 物理地址：实际内存中的地址
4. 物理地址空间：全部存储单元的物理地址的集合
5. 虚拟地址空间：程序能用到的整个地址的范围

地址转换算法

\[ 物理地址=逻辑地址+分区起始地址=页号 \times 页长+页内地址=段起始地址+段内地址 \]

分区分配算法

1. 首次适应法：按内存地址递增找到第一个满足的
2. 最佳适应法：从最小空闲分区开始递增查找到第一个满足的
3. 最差适应法：从最大空闲分区开始分配

段页式存储管理

\[ 逻辑地址=段号+段内地址+页内地址 \]

页置换算法

OPT（最佳置换）

页访问序列已知，每次置换时找最长时间后才被访问的页面

FIFO (First in First out)

维护循环队列

LRU (最近最久未使用)

两种方式

1. 维护一个链表，表顺序按照最近的访问排序，表头为上一次的访问
2. 每个块维护一个计数器，当有页面访问时置零，否则自增1，置换时找计数器最大的块

设备管理

IO设备控制方式

// 此节为语言模型生成内容

程序直接IO控制（忙查询）

特点

1. IO操作由程序直接控制，程序通过查询IO设备的状态来判断是否准备好进行IO操作。
2. 需要程序主动轮询IO设备状态，属于主动方式，占用CPU资源较多。
3. 简单实现，适用于设备处理速度较快，对实时性要求不高的情况。

区别

1. 相对于其他控制方式，程序直接IO控制实现简单，无需额外硬件支持。
2. 但是程序需要主动查询IO设备状态，占用大量CPU资源，效率较低。
3. 对于设备处理速度较慢、实时性要求高的情况，程序直接IO控制可能无法满足要求。

程序中断IO控制（中断处理）

特点

1. 通过中断机制实现IO控制，设备在完成IO操作后触发中断信号，通知CPU进行处理。
2. CPU在收到中断信号后会暂停当前任务，转而处理中断服务程序，然后恢复原任务继续执行。
3. 减少了程序主动查询设备状态的开销，提高了CPU利用率和系统响应性。

区别

1. 相对于程序直接IO控制，程序中断IO控制通过中断机制实现，减少了程序主动查询设备状态的开销。
2. CPU在收到中断信号后会暂停当前任务，转而处理中断服务程序，提高了CPU利用率和系统响应性。
3. 需要中断控制器的支持，对硬件要求较高。

DMA控制方式

特点

1. DMA（Direct Memory Access）是一种无需CPU干预的IO数据传输方式。
2. DMA控制器直接将数据从IO设备读取到内存或从内存写入到IO设备，减少了CPU的参与。
3. 提高了数据传输速率和系统性能，释放了CPU的负担。

区别

1. 相对于程序直接IO控制和程序中断IO控制，DMA控制方式无需CPU的干预，通过DMA控制器直接进行数据传输。
2. DMA控制方式可以提高数据传输速率和系统性能，减少了CPU的参与，释放了CPU的负担。
3. 需要硬件支持，包括DMA控制器和能与之配合的IO设备。

IO通道控制方式

特点

1. IO通道是一种专用的硬件设备，用于处理IO操作。
2. IO通道独立于CPU，具有自己的控制逻辑和寄存器，能够执行IO操作。
3. 通过命令和参数设置，CPU可以委托IO通道执行特定的IO任务，然后继续执行其他任务。

区别

1. 相对于其他控制方式，IO通道控制方式使用专用的硬件设备进行IO操作，独立于CPU。
2. IO通道可以独立执行IO任务，减少了CPU的负担，提高了系统的并发性能。
3. 需要特定的硬件支持，对于复杂IO操作和高性能要求的场景，IO通道控制方式是一种有效的选择。

虚拟设备技术 - Spooling

Spooling （Simultaneous Peripheral Operations On-Line）

外部设备联机并行操作 aka 假脱机

实现原理

输入输出井

特点

1. 提高了IO速度
2. 将独占设备改造成共享设备
3. 实现了虚拟设备功能

缓冲技术

硬件缓冲器或者内存缓冲区

单双缓冲

单缓冲缓冲区为临界资源，无法并行IO操作。

双缓冲（缓冲对换）

设置双缓冲后，设备输入时先将数据送入第一个缓冲区，第个缓冲区装满数据后再转向第二个缓冲区输入数据，此时操作系统可以从第一个缓冲区中取出数据传给用户进程：当第一个缓冲区的数据被操作系统全部取走后，设备又可以重新转向第二个缓冲区输入数 据，而此时，操作系统又可以从第二个缓冲区中取走数据：依此重复进行直至输入结束。

循环缓冲

多个缓冲区组成队列，标记三种状态，空E、满G、当前C

缓冲池

同种类型的缓冲区链接成队列

1. 空缓冲区队列EmQ
2. 输入缓冲区队列InQ
3. 输出缓冲区队列OutQ

四个工作缓冲区

1. 收容输入Hin
2. 提取输入Sin
3. 收容输出Hout
4. 提取输出Sout

Cache

可以保存数据副本的高速存储器

磁盘

相关名词

1. 寻道时间：磁头移动到磁道位置的平均时间
2. 旋转延迟时间：磁头到达位置后扇区旋转到磁头下方的平均时间，旋转延迟通常约为旋转时间的一半，\(平均访问时间 = 寻道时间+旋转延迟时间\)
   
3. 数据传输时间：实际读写磁盘数据的时间

磁盘调度算法

FCFS

先来先服务

SSTF (最短寻道时间优先)

每次找离当前磁头位置最近的下一个位置

SCAN (扫描)

磁头朝一个方向扫描，到头后返回扫描

Elevator (电梯算法)

没有访问请求时磁头不动，有访问时磁头来回扫描，每次选择离当前磁头最近的位置方向开始扫描

CSCAN (循环扫描)

磁头处理请求时只往一个方向移动，没有请求时不运动

文件系统

文件属性和特点

属性

1. 本身的数据信息
2. 附加的组织与管理信息（元信息）

特点

1. 保存性
2. 按名存取
3. 一组信息集合

虚拟文件系统的设计思路

虚拟层定义用户一致性接口，实现层通过开关表等进行文件系统转换

逻辑结构

无结构和有结构文件

1. 流式文件：有序字符的集合，按照字符组的长度读写信息
2. 记录式文件：由如果逻辑记录构成的序列 //看成数据库就行