OS: Process & its management
操作系统进程管理
Last updated on
进程
一个进程的实体由 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。