进程

进程的状态

七种状态变迁

PS：图片来源于：小林coding

  • 创建状态（new）：进程正在被创建的状态
  • 结束状态（exit）：进程退出的状态
  • 运行状态（running）：此时进程正在CPU中运行
  • 就绪状态（ready）：可运行状态，但是未运行状态，等待CPU时间
  • 阻塞状态（blocked）：等待事件的状态，需要其他进程唤醒
  • 阻塞挂起状态：其内存资源在交换内存中，等待某个事件出现
  • 就绪挂起状态：其内存在交换内存中，可运行状态

数据结构

内核通常使用进程控制块（Process Control Block, PCB）来描述一个进程，包含标识、控制管理信息、资源清单和CPU信息等。

PCB保存在链表中，一般会有就绪队列和阻塞队列两个链表来存储进程

线程

线程只有栈和寄存器是独享的，线程同样有就绪、阻塞和运行三个状态。

调度算法

  • 先来先到：First Come First Serve, FCFS。先进入就绪队列的先执行

  • 最短作业调度算法：Shortest Job First, SJF。选择运行时间最短的进程运行

  • 高响应比优先调度算法：Highest Response Ratio Next, HRRN

    $p=\frac{T{wait}+T{req}}{T_{req}}$

    其中$T{wait}$是等待时间，$T{req}$要求服务时间，$p$是优先级，按照优先级高的先调度

  • 时间片轮转调度算法：Round Robin, RR。每个进程分配一个时间段，用完就切换

  • 最高优先级调度算法：Highest Priority First, HPF

    在创建进程是定好优先级或者在进程运行中动态调整优先级

    优先级高的是否会打断当前的运行

  • 多级反馈队列调度算法：Multilevel Feedback Queue

    存在若干个队列，每个队列有优先级之分，优先级高的队列时间片轮转短

    新进程放入高优先级队列，按照FCFS运行，时间一到就放入低一级的优先级队列中

    只有当上一级的队列没有任务才会运行下一级

Linux中采用的完全公平调度算法（Completely Fair Scheduler, CFS），使用红黑树存储进程，红黑树键是虚拟运行时间。内核记录每个进程使用的CPU时间，称为虚拟运行时间。CFS定期检查当前进程和红黑树下一个进程的虚拟运行时间，选择较小的那个（通常是最左边那个），CFS动态计算时间片，根据负载和进程优先级，时间片决定一次调度的时间长度。