// post
OS: Process & its management
操作系统进程管理
Updated
进程
一个进程的实体由 PCB，程序段，数据段组成， 是系统进行资源分配和调度的一个独立单位，是资源分配的基本单位。
PCB: Process Control Block
用于存储每个进程的资源占用情况、运行情况、进行现场保护， CPU 切换当前执行的进程时，其上下文全部由 PCB 存储、导出。
- process state
- program counter
- CPU registers
- CPU-scheduling information
- memory-management information
- accounting information
- I/O status information
PCB 是进程存在的唯一标志。
进程的状态
- 创建态
- 就绪态
- 运行态
- 阻塞态
- 终止态
进程的控制
状态转换：原子性地将 PCB 的 state 变更，同时将进程从一个队列移动到另一个队列。 原子性由原语提供，通过关中断、开中断实现。
进程间通信
- 共享内存，如 Linux 中的
shm申请一片共享内存，再通过mmap将共享内存区 映射到进程自己的地址空间。不同进程访问共享内存的操作应该是互斥的。 - 消息传递
- 消息机制：PCB 中保存着一个消息队列，操作系统提供的 发送原语将消息挂到目标进程的消息队列中。
- 管道：在内存中分配一个大小固定的内存缓冲区，缓冲区是先入先出的。 当管道写满时，写进程将被阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。 当管道空时，读进程将被阻塞，直到写进程向管道中写入数据，即可唤醒读进程。
线程
线程是程序执行流的最小单位，进程中的各个线程共享一部分内存， 因此线程切换不需要切换运行环境，开销更小。 同一个进程的不同线程共享这个进程的资源，由于共享内存地址空间， 线程间的通信不需要额外的系统调用等机制。
线程的实现方式
- 用户级线程（多对一），也就是说只有一个内核线程，是早期实现的“假”的多线程， 实际上就是用户态的多个线程轮流执行。
- 内核级线程
- 一对一：不影响并行速度，但是占用的存储空间大
- 多对多：理论最优，实现最复杂。内核中的线程数等于硬件可同时并行执行的线程数量。
调度
- Long-term scheduler: Job scheduler 决定将哪个进程放进 Ready queue，协调 CPU 为主（CPU-bound）和 I/O 为主（I/O-bound）的程序在 PSQ 中的比例。调度操作频率较低。
- Medium-term scheduler: 长期调度程序的一种替代在 PSQ 过大的时候从其中选择一些进程移出 PSQ。
- Short-term scheduler: CPU scheduler 决定 CPU 接下来执行队列中的那个进程，加载进程运行环境并分配 CPU 资源。
PSQ: Process Scheduling Queues
用于存储 PCB 的队列，对生命周期的描述被抽象为 PCB 在多个 PSQ 之间迁徙的过程。
- Job queue: set of all processes in the system
- Ready queue: set of all processes residing in main memory, ready to be execute
- Device queues: set of processes waiting for an I/O device
进程调度的时机
在操作系统内核的临界区中不能进行调度与切换，注意*必须是内核态的临界区， 用户态的临界区访问会被进程调度切换。
- 抢占式，适合批处理系统
- 非抢占式，适合分时与实时操作系统
调度算法
评价指标
- 利用率：忙碌的时间 / 总时间
- 系统吞吐量：共完成作业数量 / 所用时间
- 周转时间：从作业被提交给系统，到作业完成为止的时间
- 带权周转时间：作业周转时间 / 作业实际运行时间
- 等待时间：作业处于等待处理机状态时间之和
- 响应时间：从作业提交到首次开始执行的时间
FCFS 先来先服务
非抢占式，对长作业有利，对频繁出现的短作业不利。
SJF 最短作业优先
非抢占式，其抢占式版本是 SRTN，会导致饥饿， 对短作业有利，对长作业有利。
SRTN 最短剩余时间优先
抢占式
HRRN 高响应比优先
响应比 = (等待时间 + 运行时间) / 运行时间
非抢占式，不会导致饥饿。
RR 时间片轮转
抢占式，优点是响应快，且不会导致饥饿，缺点是进程切换频率高，且不区分任务的紧急程度。
优先级调度
可抢占也可不抢占，可动态优先级也可静态优先级，会导致饥饿。
多级别反馈队列
不同级别的队列时间片不一样，队列级别从高到低，时间片从小到大。 更高级队列时间片到时，将更低级的任务放入其所在级别的队尾， 相当于每个级别内部是 RR。