OS Notes

进程和线程

  • 进程是拥有资源和执行任务的单元体。资源包括内存空间中的代码、数据、IO资源、文件、处理机等
  • 线程是一个执行任务的单元体。线程只拥有处理机，线程之间共享进程的资源，如内存、IO等
进程 线程
资源 进程是一个拥有资源和执行任务的单元体 线程是一个执行任务的单元体，共享地址空间
切换开销 大 小
通信 IPC 共享内存
健壮性 多个进程不会相互干扰 一个线程出错会终止整个进程

进程切换开销

  • 处理器上下文切换（保存和恢复寄存器的内容）
  • 存储信息表（页表）、文件管理数据（文件描述符）、PCB中的阻塞队列、就绪队列、通信队列等的更改

把一个进程分为多个执行任务的线程，只为其分配处理机，就能减少开销。
每次切换时不需要加载页表，只需要切换处理机上下文

Thread

共享资源 独享资源
内存空间（代码、全局变量、堆） 栈
文件描述符 上下文
进程ID和进程组ID 线程ID

  • 线程切换开销小、通信方便、共享内存，但是会有并发问题
  • 对 linux 内核来说，线程和进程都是用 task_struct 结构体表示，只是线程的 mm 和 files是共享的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

struct task_struct {
	// 进程状态
	long			  state;
	// 虚拟内存结构体
	struct mm_struct  *mm;
	// 进程号
	pid_t			  pid;
	// 指向父进程的指针
	struct task_struct __rcu  *parent;
	// 子进程列表
	struct list_head		children;
	// 存放文件系统信息的指针
	struct fs_struct		*fs;
	// 一个数组，包含该进程打开的文件指针
	struct files_struct		*files;
};

Process

进程状态

调度算法

  • CPU分配：抢占式和非抢占式
  • 系统分时：批处理系统/交互系统
  • 饥饿问题：某个process长时间等待，无法调度

批处理调度

指标：吞吐量、周转时间、CPU利用率

  1. First Come First Serve
    • 按先来后到顺序使用CPU，非抢占式
    • 只需要就绪队列实现
    • 对短作业不公平，等待时间长
  2. Shortest Job First / Shortest Remaining Time Next
    • 存在饥饿问题
  3. Highest Response Ratio Next
    • 优先考虑短作业，也避免长作业长时间等待

交互系统调度

指标：快速响应交互、CPU运行分成切片

  1. Round Robin
    • 时间片轮转的就绪队列，无饥饿问题
  2. Priority
    • 优先级调度，但是会饿死低优先级的进程
  3. Multilevel Feedback Queue
    • 多级反馈队列，动态设定优先级，优先级越高，时间片越短

僵尸进程：终止但还未回收的进程，会占用进程号和内存

  • 父进程调用 wait 或者 waitpid 回收子进程
  • 杀死父进程，僵尸进程->孤儿进程，由Init进程接管

孤儿进程：Init调用wait等待结束

daemon：守护进程，后台执行系统服务

进程IPC

IPC 传输信息量 场景 keywords
Signal 少 硬件异常信号 / 信号队列
Pipe 多 父子进程 半双工，单向流动 / 无格式字节流 / 循环队列 / 由内核管理的缓冲区 / OS负责同步
FIFO 多 创建磁盘索引节点 / 索引节点设置访问权限，无数据块 / 内核缓冲区实现数据传输 / OS负责同步
Semaphore N 底层原子操作 / Psignal()增Vwait()减 / Counting Semaphore && Binary Semaphore
Shared Memory 多 多进程 内存映射 / 简单 / 并发问题
Message Queue 比Signal多 k-v消息链表 / 按消息类型过滤 / 轮询式 / OS负责同步
Socket 多 不同计算机进程 内容包括主机地址和端口号 / 收发缓冲区 / OS负责同步
  1. Pipe
    • ps -ef | grep java | xargs echo操作符|表示命令间的管道通信
    • pipe()创建匿名管道
    • pipe是特殊的文件，同一时刻只有一个进程访问
    • 管道为空时，下游进程读阻塞；管道满时，上游进程写阻塞；管道不再被使用时自动消失
  2. FIFO
    • 命名管道，mknode()或mkfifo创建
    • FIFO会创建磁盘索引，有权限的进程可以通过索引节点来读写这块缓冲区。FIFO释放时，磁盘节点仍然存在
  3. Semaphore
    • Linux 中 Binary Semaphore又称Mutex，用于实现进程或线程的互斥同步
  4. Shared Memory
    • 不同进程将共享的物理内存映射到自己的地址空间，然后像正常内存一样访问
    • Linux 中有mmap()，Posix，shm共享内存
  5. Socket
    • 不同的计算机的进程之间通过 socket 通信，也可用于同一台计算机的不同进程
    • socket 内容包括主机地址与端口号，port声明接收来自端口地址的数据
    • 进程通过 socket 把消息发送到网络层中，网络层通过主机地址将其发到目的主机，目的主机通过端口号发给对应进程

内核态与用户态

  • 内核态只能由 os 执行，可以执行特权操作
  • 用户态必须通过系统调用来执行特权操作，而且进程必须有权限
  • 区分两者的机制为：Limited Direct Execution
  • 当系统调用（trap）、异常（exception）、中断（interrupt）时 os 会陷入内核态

锁

  • Mutex：互斥锁，同一时间只有一个线程持有锁
  • RWLock：读写不共存；允许同时多个读，一个写
  • 重入锁：同一线程可在持有锁时再次获取同一个锁，但不会被持有的锁阻塞（避免死锁）
  • SpinLock：自旋锁，锁定机制，不让线程休眠，反复检查锁是否可用
  • 乐观锁 / 悲观锁
    • 悲观锁认为数据处理阶段都要加锁
    • 乐观锁认为线程没有修改数据时不会加锁，而是采用版本号/Compare ans Swap算法判断数据是否修改
  • 公平锁 / 非公平锁

sync.Mutex

1
2
3
4
type Mutex struct{
   state int32
   sema uint32 // 控制锁状态的信号量
}

State

  1. mutexLocked 锁定状态
  2. mutexWoken 从正常模式被唤醒
  3. mutexStarving 饥饿状态
  4. waitersCount 互斥锁上等待的 Goroutine 数
  • 正常模式：FIFO
  • 饥饿模式：防止Goroutine被饿死，保证公平性
  • 加锁
    • 初始状态，置位 mutexLocked 加锁
    • 互斥锁处于 mutexLocked 状态和普通模式，会进入自旋，执行 30 次 PAUSE 等待锁的释放
    • Goroutine 等待时间超过 1ms，切换饥饿模式
    • sync_runtime_SemacquireMutex让等待的 Goroutine 休眠，直至被锁的持有者唤醒
    • Goroutine 是最后等待的协程 / 等待时间 < 1ms，切换正常模式
  • 解锁
    • 已经解锁时，调用 Mutex.Lock 抛出异常
    • 饥饿模式时，将锁的所有权交给队列中的下一个等待者
    • 普通模式时，没有 Goroutine 等待锁的释放 / 被唤醒的 Goroutine 获得了锁，直接返回
    • 其他情况，sync.runtime_Semrelease 唤醒 Goroutine

协程

实现

  1. 在堆上模拟栈，实现用户态的协程（Goroutine协程）
  2. 调度器（GMP），负责调度协程和上下文切换，不必切换到内核态

互斥与同步

  • 经典并发问题：生产者与消费者，哲学家问题
  • 死锁条件（参考：银行家算法）
    1. 互斥
    2. 占有资源且等待其他资源
    3. 不可被抢占资源
    4. 环路等待资源

TODO:

cover
画师: LAM
id: 122857414