操作系统知识点整理

🔗cyc2018、huihut

基本概念

🔗https://juejin.im/entry/6844903464678457357

并发/并行

并发：操作系统通过引入进程和线程，使得程序能够并发运行

• 宏观上，能同时运行多个程序
• 微观上，任意时刻，有且仅有一个程序在运行
• 硬件环境：一个CPU

并行：需要硬件支持，如多流水线、多核处理器或者分布式计算系统

• 同一时刻能运行多个程序
• 硬件环境中存在多个CPU

阻塞/非阻塞

阻塞：进程/线程的5个状态之一

• 线程调用某个函数，需要等待IO请求或暂时得不到竞争资源时，操作系统会把该线程阻塞起来
  • 阻塞调用：调用者只有收到结果后才返回，否则一直阻塞，socket的recv/read方法
  • 非阻塞调用：调用的函数不会阻塞当前线程，而会立刻返回，socket的send/write方法
• 避免浪费CPU资源
• 等到得到了资源，再变成就绪状态，等待CPU调度运行

阻塞和挂起：

• 阻塞是被动的，比如抢不到资源
• 挂起是主动的，线程自己调用 suspend() 退出运行态，调用 resume() 恢复运行

线程执行完就会被销毁，如果不想线程被频繁的创建，销毁，怎么办？

• 可以给线程里面写个死循环
• 或者让线程有任务的时候执行，没任务的时候挂起

同步/异步

同步和阻塞都是调用方法之后等待结果返回，但同步调用时线程不一定阻塞

• 同步调用虽然没返回，但线程还是在运行状态，CPU时间片尚未耗尽，很可能还在执行这段代码
• 阻塞调用时，线程已耗尽CPU时间片，失去CPU资源

异步和非阻塞都是不必等待结果，函数直接返回

• 异步调用时，如果还有CPU时间片，则继续执行；否则也会阻塞
• 非阻塞调用时，方法直接返回，并在CPU时间片内继续向下执行

基本特征

并发、异步、共享、虚拟

共享：系统资源被多个并发进程使用，宏观上，“同时”共享；微观上，互斥共享

虚拟：一个物理实体转换为多个逻辑实体

• 时分复用（并发）：一个CPU并发处理多个进程，进程轮流占用CPU
• 空分复用（虚存）：将物理内存抽象，每个进程都有各自的地址空间

进程/线程

• 进程：资源分配的基本单位，使用PCB（进程控制块）描述基本状态信息
  • 同一进程的多个线程共享代码段（代码和常量），数据段（全局变量和静态变量），扩展段（堆空间）
  • 一个进程崩溃时，一般不会造成其他进程崩溃
  • 进程创建/切换时，开销大（创建/撤销时资源处理，切换时保护现场）
  • 进程间通信需要IPC，切换使用进程表维护信息
• 线程：资源调度的基本单位，使用TCB（线程控制块）描述基本状态信息
  • 每个线程拥有自己的栈段，又叫运行时段，用来存放局部变量和临时变量
  • 一个线程的崩溃将会导致整个进程的崩溃
  • 线程创建/切换时，系统开销相对较小
  • 线程间可以直接读写同一进程内部数据通信，切换使用涉及线程表

进程状态

⚠️线程间的状态转换和进程是一样的

• 创建：一般通过系统调用fork创建进程，为进程分配资源后，进入就绪状态
• 就绪：进程已经拿到全部资源，等待CPU分配时间片被调度，进入运行状态
• 运行：
  • 进程正常结束/抛出异常，进入终止状态
  • 进程等待IO操作/事件/资源，主动放弃CPU，进入阻塞状态
  • 进程CPU时间片用完/被抢占，进入就绪状态
• 阻塞：进程等待的事件完成/拿到需要的资源后，进入就绪状态

进程调度

批处理系统：用户操作少，进程调度保证任务吞吐量和从提交到终止的时间

• 先来先服务（FCFS）：非抢占、按进程请求顺序调度
  • 短作业等长作业完成再执行，短作业等待时间长
• 短作业优先：非抢占、按进程预估的运行时间从短到长调度
  • 如果一直有短作业，则长作业永远不能执行
• 最短剩余时间优先：抢占式
  • 系统没新进程，当前进程运行完毕，继续下一个剩余时间最短的进程
  • 新进程还未运行，其总的运行时间比当前进程剩余运行时间少，则抢占CPU；否则新进程等待

交互式系统：大量用户操作，调度保证快速响应

• 时间片轮转：就绪进程按照FCFS排入队列

  • 从队首拿进程运行，时间片用尽后，当前进程放入队尾，继续执行队首进程

  ⚠️效率和CPU时间片大小有关：

  • 取太小，响应快，但进程切换频繁，增加耗时，CPU利用率低
  • 取太大，CPU利用率高，但无法确保及时响应

• 优先级调度：根据进程的优先级进行调度

  • 优先级随着等待时间的增加而变高，避免低优先级无法调度

• 多级反馈队列：多层队列，优先级从高到低，时间片由小到大

  • 上一层队列无进程，再执行当前队列
  • 新进程进入第一层队尾，耗尽时间片后，进程加入下一层队尾
  • 当前已经是最后一层，则接入队尾

进程同步

🔗https://www.ibm.com/developerworks/cn/linux/l-synch/part1/

并发的进程对资源的异步访问顺序不确定，因此需要同步机制使得进程有先后执行次序

• 临界资源：每次只允许一个进程访问的资源
• 临界区：对临界资源进行访问的代码段
• 互斥：多进程同一时刻只允许一个进程进入临界区

原子操作

原子操作绝不会在执行完毕前被任何其他任务或事件打断（最小的执行单位）

• 原子操作通常用于实现资源的引用计数（共享指针shared_ptr）

信号量

🔗https://www.jianshu.com/p/836fe237efbf

对其进行原子操作up/down

整型信号量：只能执行初始化/P/V三种操作

• 不满足让权等待原则，发生忙等
• 临界区外的进程在循环中确认信号量的值，占着CPU不释放，这是一种忙等状态

记录型信号量：避免忙等

• down：信号量-1（P操作）

  • 大于0，则当前进程可继续执行，直到离开临界区后执行up
  • 小于0，进程挂起（调用block原语进入阻塞），加入信号量的等待队列，此时信号量的值表示等待的进程数
  • 等于0，信号量被用完，但没有等待该信号量的进程

• up：信号量+1（V操作）

  • 大于0，表示可用信号量数
  • 小于等于0，调用wakeup原语唤醒等待队列中第一个进程（就绪）

Linux内核的信号量在概念和原理上与用户态的System V的IPC机制信号量是一样的，但是它绝不可能在内核之外使用，因此它与System V的IPC机制信号量毫不相干

互斥量：信号量取值0/1，0表示临界区加锁；1临界区解锁

⚠️信号量实现互斥/同步

• 互斥：针对不同临界资源设置不同的互斥量，初始化为1
  • 进入临界区之前执行P操作，确保其他进程无法进入
  • 离开临界区之后执行V操作，释放锁
• 同步：多个进程根据不同的前后关系，设置不同的同步信号量
  • 前进程执行之后，执行V操作，如果不大于0，唤醒等待队列首个进程
  • 后进程执行之前，执行P操作，如果为负值，则阻塞，等待前操作完成执行V

生产者消费者

一个互斥量 mutex 来控制对缓冲区的互斥访问

一个信号量empty表示空余缓冲区数量

一个信号量full表示非空缓冲区数量

int mutex = 1;//互斥量初始化为1，表示缓冲区可访问
int empty = N;//同步信号量，空缓冲区大小为N
int full = 0;//同步信号量，产品数为0
//生产者
producer()
{
    while(1)
    {
        produce();//生产产品
        P(empty);//获取一块空余的缓冲区，如果为0，则阻塞，等待empty>0
        P(mutex);//访问缓冲区,加锁，如果为0，等待解锁
        insert();//放入产品
        V(mutex);//访问完毕，解锁
        V(full);//产品增加
    }
}
//消费者
consumer()
{
    while(1)
    {
        P(full);//消费一个产品，如果为0，阻塞，等待full>0
        P(mutex);//访问缓冲区,加锁，如果为0，等待解锁
        remove();//拿出产品
        consume();//消费产品
        V(mutex);//访问完毕，解锁
        V(empty);//缓冲区空余数量增加
    }
}

读写信号量

对访问者进行了细分，或者为读者，或者为写者

读者：进程持有信号量期间，只能对临界资源进行读操作

• 同一个读写信号量的读者数不受限制
• 当信号量没有被写者拥有或等待，任何读者均可获得该信号量；否则读者挂起

写者：进程只要有写的需求，必须被归类为写者

• 如果进程不需要写，可以降级为读者
• 当信号量没有被写者拥有或等待，也没有读者拥有，则一个写者才能获得该信号量；否则写者挂起（排他、独占）

自旋锁

与互斥锁类似，任何时刻，最多只能有一个保持者，但不会引起调用者睡眠

• 如果自旋锁已经被占用，调用者自己循环并观察锁是否被释放

  ⚠️自旋锁保持锁时间非常短，因此进程不需要睡眠，也不会出现忙等

• 自旋锁的效率远高于互斥锁

• 自旋锁保持期间无法抢占，而信号量和读写信号量保持期间是可以被抢占的

应用场景：

• 单核CPU-互斥锁，或进程需要长时间持有锁
• 大量进程短时间内持有锁-自旋锁，避免频繁唤醒

此外还有读写锁、大读者锁、大内核锁、顺序锁等，参见Linux 内核的同步机制

进程通信

Inter-Process Communication（IPC）

管道

实际上是在内存中开辟的固定大小的缓冲区

• 各个进程互斥访问管道
• 管道满，才能读，写阻塞；管道空，才能写，读阻塞
• 数据读完后被抛弃，因此不能出现多个读进程

无名管道：半双工通信，只能父子/兄弟进程（亲缘关系）间使用，实现简单方便

• 缺点：单向通信、有亲缘关系的进程之间、缓冲区有限

有名管道（FIFO）：半双工，可在任意关系的进程间通信，缓冲区有限

消息队列

在内核中，存放消息的链表，由消息队列标识符标识

消息：进程间数据交换以格式化的消息为单位

• 格式化消息类似“报文”，消息头包含发送进程ID、接收进程ID、消息类型、长度等

消息传递方式

• 直接通信：发送的消息直接进入接收进程的消息缓冲队列
• 间接通信：消息先发送到一个中间实体（信箱），接收进程从信箱读消息

优缺点：

• 通过操作系统发送消息原语/接收消息原语进行数据交换，保证消息收发同步
• 消息队列独立于读写进程存在，避免管道通信时因为同步而阻塞
• 读进程根据消息类型有选择地接收消息
• 缺点：信息的复制需要额外消耗 CPU 的时间，不适宜于信息量大或操作频繁的场合

信号

信号（Signals）是进程间通信机制中唯一的异步通信机制，异步通知进程一个事件已经发生

• 进程收到信号后，任何非原子操作都将被中断（软中断）

• 进程执行定义的信号处理函数，没有定义则执行默认的

信号量

信号量是一个计数器（数量有限），常作为一种锁机制控制多个进程/线程同步访问临界区

共享内存

进程间将同一文件映射到自身的虚拟地址空间中，实现对同一块内存的共享

• 数据不需要在进程间复制，最快的通信方式
• 需要结合信号量，同步访问共享内存
• 只能在同一个计算机系统中多进程共享，不方便网络通信

套接字

常用于不同主机间进程的网络通信

优点：

1. 传输数据为字节级，传输数据可自定义，数据量小效率高
2. 传输数据时间短，性能高
3. 适合于客户端和服务器端之间信息实时交互
4. 可以加密,数据安全性强

缺点：需对传输的数据进行解析，转化成应用级的数据

线程间的通信

目的主要是用于线程同步，没有数据交换的机制

锁机制：互斥锁、读写锁、自旋锁、条件变量

• 条件变量（condition）：可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用

信号量、信号、屏障，屏障允许每个线程等待，直到所有的合作线程都达到某一点，然后从该点继续执行

多线程/多进程

对比维度	多进程	多线程
数据共享同步	数据共享复杂，需要用 IPC；数据是分开的，同步简单	共享进程数据，数据共享简单，同步复杂
内存、CPU	占用内存多，切换复杂，CPU 利用率低，资源占用大	占用内存少，切换简单，CPU 利用率高,资源占用小
创建销毁切换	创建销毁、切换复杂，速度慢	创建销毁、切换简单，速度很快
编程、调试	编程简单，调试简单	编程复杂，调试复杂
可靠性	进程间不会互相影响	一个线程挂掉将导致整个进程挂掉
分布式	适应于多核、多机分布式	适应于多核分布式

• 频繁创建销毁，用线程
• 大量计算，用线程
• 强相关，用线程，弱相关，用进程
• 多机分布，用进程，多核分布，用线程

死锁

🔗https://zhuanlan.zhihu.com/p/61221667

进程间相互等待对方占用的资源，但都不释放已经持有的资源

必要条件

• 互斥：一个资源只能被一个进程/线程使用
• 占有和等待：一个进程占了一个资源，占其他资源时阻塞，不会释放占的资源
• 不可抢占：一个被占的资源不能再被其他进程抢走，不可抢占资源只能被显示释放
• 环路等待：若干进程/线程之间形成一种头尾相接的循环等待资源关系

处理方法

鸵鸟策略

发生死锁的概率低，解决死锁的代价高，因此选择不做处理

死锁检测/恢复

不阻止死锁，当检测到死锁发生时，进行恢复

检测：

• 进程只申请一个资源：当检测到环时，即发生死锁
• 进程申请多个资源：算法执行时标记进程，运行结束后还存在未标记的进程，即发生死锁
  • 寻找一个没有标记的进程，它所请求的资源小于等于系统剩余资源
  • 如果找到，标记该进程，表示该进程当前可执行，并将其占用的资源释放（加入系统剩余资源）
  • 如果没有找到，算法终止

恢复：

• 抢占恢复：不通知原进程，强行占走资源，用完后送回，方式简单但难实现，不可取
• 回滚恢复：类似数据库对数据回滚操作，将每个检测点写入文件，死锁后将资源回滚到上一个检测点，重新分配资源
• 杀死恢复：不断杀死死锁进程释放资源，直到死锁解除；或杀死环外的进程释放资源，最为简单直接

死锁预防

破坏死锁4个必要条件之一，达到预防效果，但会降低系统并发性，资源利用率低

破坏互斥

使资源可以同时访问，就没有进程会阻塞在资源上，从而不发生死锁

• 只用于只读环境，因此多数情况下不适用

破坏占有和等待

进程在执行之前申请需要的全部资源，资源全部得到满足后才开始执行

• 实现简单，但资源利用率很低
• 有些不常用的资源也被占用，真正需要的进程阻塞

破坏不可抢占

针对可抢占资源：内存、CPU

1. 申请新资源时，进程需主动释放已占资源；之后再重新申请该资源
2. 申请新资源时，如果有则分配；否则剥夺占用的全部资源，进程阻塞，直到资源充足后唤醒进程申请资源

破坏循环等待

按层将资源编号，申请资源的顺序必须按照编号进行

• 一个进程得到某层的一个资源后，只能申请较高一层的资源
• 当进程释放某层的一个资源时，必须先释放所占有的较高层的资源
• 当进程获得某层的一个资源时，如果想申请同层的另一个资源，必须先释放此层中已占有的资源

死锁避免

程序运行过程中避免发生死锁

安全状态：

• 没有死锁发生
• 当所有进程突然最大程度申请资源时，仍存在某种调度次序使每个进程运行完毕

银行家算法

🔗https://blog.csdn.net/qq_33414271/article/details/80245715

当一个进程申请使用资源的时候，银行家算法通过试探分配给该进程资源

然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待

1. 当一个进程发出资源请求后，根据系统剩余资源判断是否足够可以分配
2. 如果不够，直接退回；否则假设分配给申请的进程，从系统剩余资源序列减去申请的资源
3. 此时，从当前进程的Need资源序列减去分配的资源，加入已获得资源序列
4. 接着，判断此时系统剩余资源能否满足其他某个进程的Need资源序列
5. 如果一个都不能满足，则假设失败，不给予分配；否则，回到第二步，再次假设分配资源

内存管理

🔗https://blog.csdn.net/weixin_43314519/article/details/107192971

🔗https://blog.csdn.net/tennysonsky/article/details/45092229

🔗https://blog.csdn.net/qq_37375427/article/details/84206495

物理内存

单片机中没有操作系统，烧入程序直接操作物理内存

• 地址空间不隔离，可随意修改内存数据
• 内存利用率低，程序需要全部载入内存，一旦空间不足就不能运行其他程序

虚拟内存

通过CPU中的MMU（内存管理单元）实现虚拟内存到物理内存的映射

目的：地址隔离，“扩充”物理内存

• 每个程序拥有自己的地址空间，虚拟内存按页划分
• 每一页映射的物理内存不一定连续，也不需要全部映射
• 当引用的页不在物理内存时，由硬件执行必要的映射，将页装入物理内存并重新执行失败的指令

分段

根据程序不同的逻辑段（代码分段、数据分段、栈段、堆段）划分虚拟内存

• 每个段都是从 0 开始的独立逻辑地址空间
• 而且各个段的长度因程序而不同

段表

段号+段长+偏移值，但位数不确定

1. 进程获得某个分段的段号，段号大于段表长度则越界
2. 查询段表，获得段长和该段在物理内存中的起始地址
3. 段起始地址+段长=物理地址

⚠️分段都是连续内存空间，但是易出现内存碎片，内存交换效率低

内存碎片

• 外部碎片：多个不连续的小物理内存，导致新进程无法装载
• 内部碎片：程序所有内存均被分段载入内存，但其中部分分段不会经常访问

内存交换

解决外部碎片问题：调整当前物理内存分配布局，腾出连续空间以加载新程序

⚠️每次交换均需要从磁盘的swap分区进行，磁盘读写速度限制内存交换效率

分页

按固定大小的页进行内存分配，解决外部内存碎片问题

⚠️内部内存碎片依旧存在，页固定大小4k，但4k内存并非全都会利用

页表

虚拟内存（页）<=>物理内存（页框）

• 一般还有一位表示是否存在于内存中（1存在/0不存在）
• 根据情况增加访问权限位（读/写）用以内存保护，如果非法访问linux提示段错误

⚠️进程PCB中描述页表起始地址和长度

虚拟内存地址：页号+偏移量

• 页大小：32位系统一般为2^12=4KB，则32位虚拟内存地址的后12位标识页内偏移量
• 页数量：32-12=20，即为2^20个页，则32位虚拟内存地址的前20位标识页号

因此，转换大致如下：

• 根据虚拟内存地址前几位确定页编号：逻辑地址/页大小=页编号
• 查找页表中对应编号所对应的页表项，表示物理内存页框编号：页编号<=>页框编号
• 如果页表项最后一位为1，则找到对应物理内存为：页大小*页框编号+逻辑地址%页大小（页内偏移）
• 如果为0，此时如果还有闲置的物理内存，则将当前页面装入物理内存，页表增加映射关系
• 如果没有空闲的物理内存，则进行页面置换算法，移除被置换的映射，增加新映射

⚠️程序的局部性原理：

• 每次只有进程的少部分代码会在物理内存中运行，其余代码位于磁盘交换分区

• 页面置换时，从交换区中取出一页大小的数据进行置换

快表TLB

为加快映射速度，在CPU高速缓存中存放快表

• CPU先访问快表，找不到映射再访问内存中的页表

• 找到之后，将对应映射关系加入快表

  🔴如果快表已满，则类似页面置换，通过算法将快表中一个项目置换到内存

一级页表缺陷：页表必须连续存放，常驻物理内存，每个进程一个页表，页表占用空间

二级页表

对页表本身分页，将需要的页表项调入内存，其余项存在磁盘

目的：使得页表离散存储，节省物理内存空间

由于程序局部性原理，并非每个一级页表项都会对应1024个二级页表，只在需要的时候创建

页面置换算法

🔗https://blog.csdn.net/weixin_39731083/article/details/82025029

🔗https://blog.csdn.net/wangsifu2009/article/details/6757352

🔗https://www.jianshu.com/p/d76b873fcce7

目的：降低缺页率，减少缺页中断的次数

理想算法：置换出最长时间不被访问的页面（无法实现）

先进先出

调出最早进入内存的页面

• 将进程调用的页面按次序链接为一个队列，队列满时调出队首页面

  ⚠️缺页率高：经常访问的页面随时间推移也会迟早被调出

第二次机会

每个页设置访问标志位R

• 如果队首的页R=0，表示最早载入内存并且没被访问，直接置换
• 如果队首页R=1，表示访问过，则将其移入队尾，并置R=0（相当于刚载入内存）
• 此时再判断新的队首，直到R=0的队首页置换

⚠️可能需要反复移动页（链表），效率低

时钟

使用环形链表连接页，并通过指针指向最早的页，又称为最近未用(Not Recently Used, NRU)算法

改进：使用M标记是否修改

• 寻找R=0；M=0进行置换，表示没有被访问、修改
• 如果没有，寻找R=0；M=1进行置换；在此期间访问到的页R置为0

最近最久未使用

LRU（Least Recently Used）：按照上次访问时间排，淘汰上次访问时间最大的

• 在内存中维护一个所有页面的链表
• 一个页面被访问后就移到链表表头
• 则链表尾部是最近最久未访问的页面，置换

⚠️每次访问都要更新链表（代价高），另属于堆栈算法莫须有硬件支持

最少使用

LFU（Least Frequently Used）：内存中的每个页都会有一个移位寄存器，用于记录该页面被访问的频率

• 算法会选择最近时间内，用得最少次的页面淘汰

分页分段区别

• 页是物理单位，满足系统空间管理需要；段是逻辑单位，满足用户需要
• 页的大小固定，由系统决定；段的长度不固定，由用户决定
• 分页地址空间是一维的（虚拟地址由一个数表示）
  分段地址空间则是二维的（虚拟地址有两个数（段号和段内地址）表示）

出现的原因：

• 分页主要用于实现虚拟内存，从而获得更大的地址空间
• 分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护

段页式

结合段式和页式两者管理优点，既能节省内存空间，提高内存分配效率；又能兼顾用户程序需要

• 先分段，再将每段分页
• 每段对应一个页表，段表存放每个页表的起始地址和页表长度
• 虚拟内存地址：段号+段内页号+页内偏移

1. 根据段号查段表，得到该段所在页的起始地址
2. 根据段内页号查找页表，得到该页对应的物理页号
3. 物理页号*页大小+页内偏移=物理地址

面试补充

🔗https://blog.csdn.net/qq_35181209/article/details/78026636

🔗https://www.cnblogs.com/zl1991/p/12932173.html

自旋锁设计，CAS

互斥锁底层实现

信号量机制底层硬件实现

字节序

🔗https://www.ruanyifeng.com/blog/2016/11/byte-order.html

内存地址	0x00	0x01	0x02	0x03
大端字节序（网络字节序）	12	34	56	78
小端字节序	78	56	34	12

大端：数据高字节低地址，低字节高地址

为啥出现小端

计算机从低字节开始计算速度更快，效率更高；如果收到大端字节序则需要转换

孤儿进程

父进程退出但子进程还在运行，子进程为孤儿进程

• 会被进程号1收养，不会对系统造成危害

僵尸进程

正常情况：父进程通过wait获取已经退出的子进程信息后，子进程描述符被释放

异常情况：父进程没有调用wait，子进程退出，但描述符还存在，此时为僵尸进程

• 由于系统进程号有限，大量僵尸进程出现后系统无法产生新进程

解决方法：杀死父进程，僵尸进程变为孤儿进程后被收养，但由于子进程已经退出，因此释放资源