操作系统: 进程管理

Posted on Edited on In , Word count in article: 3.3k Reading time ≈ 12 mins.

进程组成

  • 进程(Process)是程序的执行过程，也即运行中的程序；一个进程即某个程序在给定输入下的一次执行

    • 在其它OS中，可称为作业(Job)、任务(Task)
    • 在宏观上，进程支持多任务，看起来进程在“同时”执行，是并发的 不同进程是串行执行的(通过调度分时执行)

  • 多任务环境下，进程是OS分配资源的基本单位

    • 多任务(Multitasking)是现代操作系统的基本属性
    • 最早为批处理系统(Batch System)，通过将一系列任务打包送给操作系统队列运行而非人工提交单个任务，来提高CPU利用率 由单道(内存中只载入一个任务)到多道(前方任务进行I/O读写等操作时使CPU处理后方任务)，均为批处理系统 现代提供特定的交互功能(用户可干预进程的优先级、状态等)并进行优化，成为专用的多任务系统

  • 进程的结构：

    • PCB(Process Control Block，进程控制块)：管理进程的唯一数据结构
      • PID：唯一标识一个进程的标识符
    • 进程映像：独立的存储进程地址的内存空间，包含指向各种数据的地址指针
    • 数据段

  • 进程的控制功能：

    • 创建/撤销
    • 阻塞：进程提出系统请求，但内核未响应时，将调用阻塞命令
    • 唤醒：阻塞进程所等待的事件完成/发生，将调用唤醒命令

  • 进程状态：

    $$\begin{align}&\rm new\stackrel{admitted}\rightarrow ready\stackrel{interrupt}\leftrightarrows running\stackrel{exit}\rightarrow terminated\\&\ \ \ \rm \ \ \ \ \ \ \ \ \ {\small事件发生}\uparrow\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \downarrow{\small等待事件}\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \rm waiting\end{align}$$ 有时因内存空间不足，OS会将一些进程主动移出内存(放入交换空间)，称为挂起 被挂起的进程可能处于就绪或等待状态，因此挂起队列有两种 挂起等待进程在等待事件发生后，变为挂起就绪 取消挂起状态需要由OS主动将其载入内存

进程调度

  • 调度(分配CPU资源)：管理处于不同状态的多个进程 将所有进程根据状态归入阻塞队列、就绪队列、部分OS含挂起队列

  • 通过支持CPU调度，可实现并发，即宏观上同时执行多个进程 与并行的区别：并发强调调度提高CPU利用率，并行需要多核实现真正的同时执行

    频繁调度将导致频繁进行系统调用(切换执行态)，降低执行效率

  • 切换进程时，需保护上下文，上下文可分为：

    • 用户级上下文：代码段、数据段、用户堆栈、共享内存区
    • 寄存器上下文：所有寄存器的数据
    • 系统级上下文：进程控制块、内存管理信息、内核栈

  • 调度层次：

    • 短程调度：从就绪队列中选择合适进程被CPU执行
    • 中程调度：交换进程，即将进程从内存移出/从交换空间中取出
    • 长程调度：将用户提交的批作业载入内存

IPC(进程间通信)

  • IPC用于支持不同进程间的相互协作、共享/交换信息
  • IPC的底层实现有：
    • 低级通信：用于传递控制信息，通过信号量、互斥锁实现
    • 高级通信：用于进程间大量信息的交换/共享，通过共享内存区/消息传递实现
      • 消息传递：进程通过调用内核的发送/接收函数，和其它进程通信 由于使用隐式同步(阻塞式通信/协议通信)且传递的消息为副本，过程清晰可查，编程简单易于调试而不易出错；但效率较低
        • 阻塞式通信：即进程调用函数后进入阻塞队列
        • 由于消息为副本，进程修改消息不会对其它进程产生影响
      • 共享内存：所有进程可直接读写共享内存区内的数据 由于使用同一份数据，为保证进程安全，需进行显式的同步控制(低级通信) 使一份数据同时仅能被一个进程访问 编程较复杂，调试难度高，但效率高
  • 根据用户的需求不同，有不同的通信模型(上述方法的接口)：
    • LPC(Local Produce Call，本地过程调用)：同一进程内/同一主机的不同进程调用IPC的接口
    • RPC(Remote Produce Call，远程过程调用)：不同主机的进程调用IPC的接口，涉及网络通信
  • 管道(Pipe)：是Linux中消息传递机制的具体实现，由内核为两个进程开创管道
  • 套接字(Socket)：套接字即一组信息组成的唯一标识，是计网模型里低层协议为高层协议提供的接口，在RPC中通过IP地址、协议、端口地址组成套接字来唯一标识一个进程(因为远程IPC中pid无法唯一标识进程)

线程

  • 线程(Thread)是更细粒度的计算单位，一个线程是进程中一个单一顺序的控制流(独立于其它线程的代码流)

    • 线程的引入支持充分利用多核资源，实现多个线程的并行执行，加快一个进程的执行速度
    • 线程独有TCB(线程控制块)、堆栈、 和其它在同一进程下的不同线程共享代码段、共享内存区，同一进程下不同线程间通信较IPC简单

  • 分为用户级线程(用户在高级语言中使用线程库)、内核级线程(由内核直接管理)

    • 用户级线程由线程库实现，不需要内核线程的支持；但也意味着它们并非真正的并行执行

      在用户眼中，用户级线程可随意调度，可由用户编写专用的调度算法 在内核眼中，用户级线程不可见因此不可调度，当一个用户级线程进入阻塞态，其所属的进程也进入阻塞态

    • 内核级线程由内核支持，创建线程时需要进行系统调用，并真正更新在线程表中，由内核调度 实现并行执行，但消耗内核资源多

    • ~协程

  • 线程模型：用户级线程需要通过内核级线程运行

    • M:1模型：多个用户级线程绑定到一个内核级线程，会导致某个用户级线程阻塞后，其它M-1个用户级线程也被阻塞
    • 1:1模型
    • M:N模型
    • 混合模型

进程调度算法

  • 调度过程：
    • CPU调度：进行一次短程调度(处于内核态)
    • 派遣：切换上下文→切换回用户态→执行从就绪队列推出的任务
  • 调度时机：
    • 进程阻塞/结束：进程主动放弃CPU，属于非抢占点
    • 进程被唤醒/被中断：因中断等事件发生，该进程从阻塞状态/运行状态进入就绪队列，属于可抢占点，两种原因造成的可抢占的资源分别是非CPU资源、CPU资源
  • 调度算法评价指标：
    • CPU利用率：倾向使CPU不含空余时间
    • 进程吞吐率：倾向选择短进程执行
    • 周转时间：进程从第一次到达就绪队列到全部运行结束的时间
    • 带权周转时间：进程的周转时间除以运行的总时间
    • 平均周转时间/平均带权周转时间：多个进程的平均周转时间/平均带权周转时间，可表示进程的总体执行效率
    • 等待时间：进程就绪后等待执行所花费的全部时间
    • 响应时间：进程提交后到第一次获得CPU的时间
  • 抢占式/非抢占式调度：进程进入就绪队列后，是否会影响运行中的进程，如果是抢占式调度，在新进程根据调度算法比运行中进程更优时，新进程将和运行中进程交换
  • 优先级调度算法：任务队列为优先数的最小堆(分为非抢占式/抢占式)
    • FCFS(First Come First Serve，先进先服务)算法：就绪队列为一般的先进先出队列，等待前方进程结束后执行下一进程
      • 各指标不稳定，且为非抢占式调度
    • SJF(Shortest Job First，短作业优先)算法：就绪队列为剩余时间(所需时间-已执行时间)的最小堆
      • 追求更低的平均周转时间，但响应时间长
      • 为非抢占式调度，先到的任务一定比后到的任务先完成(尽管执行中进程的剩余时间比后到任务多)
      • 存在饥饿问题：剩余时间长的进程可能永远得不到调度
    • SRTF(Shortest Remaining Time First，最短剩余时间优先)算法：就绪队列及运行中进程组成剩余时间的最小堆
      • 为抢占式调度，就绪队列每次更新时都需要对比，使执行中任务始终为剩余时间最短的
      • 存在饥饿问题
    • HRRN(Highest Response Ratio Next，最高响应比优先)算法：就绪队列为响应比$\begin{align}\left(R=\frac{周转时间}{执行时间}=\frac{等待时间+执行时间}{执行时间}\right)\end{align}$的最大堆
    • 饥饿现象：优先级调度算法中，无论是非抢占式还是抢占式调度，均会发生饥饿现象，即某进程因优先级过低而等待时间过长，导致即使其最终完成也失去其实际意义(饿死) 可使用老化机制，即优先级同时需考虑其等待时间，HRRN即一种采用老化机制的优先级调度算法
  • RR(Round Robin，轮转)调度：轮转调度考虑进程的公平性(使它们的平均值最短)，将时间分为多个时间片，每个进程执行一个时间片后必须返回就绪队列，使资源被轮转使用
    • 平均等待时间与时间片长度成正比，最坏等待时间为(就绪进程数-1)*时间片长度，使时间片较短，可提升交互体验
    • 吞吐率较低，批处理速度慢
    • 通过计时器中断实现
    • 一个进程可以通过产生多个子进程，增大本身的占有CPU的时间
  • MLQ(Multi-Level Queue，多级队列)调度：全体就绪进程采用优先级调度算法，但处于同一优先级的进程采用轮转调度(或其他调度算法)
  • MLFQ(Multi-Level Feedback Queue，多级反馈队列)调度：在MLQ调度基础上，支持动态优先级；即任务执行一个时间片释放资源后，增加考虑是否降低其优先级的步骤(允许进程在不同优先级队列间移动)

进程同步

  • 进程协作以异步为主(保证效率)，同步为辅(保证进程间通信的数据安全)

  • 进程同步根据IPC方式有所区别：

    • 进程直接协作：采用消息传递，属于隐式同步，进程间有特定的执行顺序，此方发送/接收消息时需进入阻塞态、直到对方接收/发送消息时被唤醒
    • 进程间接协作：采用共享内存，进程间不互锁，因此需要显式同步以保证数据一致性
      • 一个进程的临界区(连续的访问共享内存的代码)执行过程中不能被其它进程的临界区影响 在并发执行中，起因为抢占式调度/RR调度算法等的分时执行

  • 针对间接协作的同步控制(互斥)，有以下解法：

    • Peterson解法(互斥的软件解法)：
    • 互斥锁(互斥的硬件解法，也称互斥量Mutex)：
    • 信号量(Semaphore)：
      • P-V问题：
      • 读者写者问题：
    • 互斥信号量必须紧贴临界区

  • 管程：

  • 同步控制造成死锁：

    • 特点/必要条件：
      • 进程在运行结束前不释放资源
      • b
      • c
      • d
    • 死锁预防：在程序未执行时，进程的申请阶段
      • 要求进程执行前先申请整个进程所需的所有资源，仅当全部所需资源均满足时分配(破坏)
      • 要求进程按资源的编号顺序申请资源(破坏循环等待)
    • 死锁避免：程序的执行阶段(未发生死锁)
      • 对进程的动态申请资源进行审查
      • 银行家算法：
    • 死锁检测：
      • 检测算法：构建进程等待图，求拓扑排序检测是否有环
      • 鸵鸟机制：由于死锁检测代价高昂且死锁概率十分小，一般不进行处理
    • 死锁恢复：直接终止相关进程，让它们释放资源