第二章-处理器管理

1.处理器

（1）特权指令和非特权指令

特权指令：仅在内核态才能使用的指令

非特权指令：在目态（用户态）和管态（内核态）都能工作。（应用程序只能使用非特权指令）

（2）内核态和用户态

内核态：有权管理和分配资源。

如处理器、内存、设备等资源管理程序在内核态运行。否则安全性没有保证；

再如为应用程序执行提供良好运行环境的各种原语（内核中实现的不可中断过程）应在内核态运行，否则会导致系统混乱；

对于文件系统及数据而言，则系统数据及管理必须放在内核态，但用户数据及管理可以放在用户态。

有的操作系统为了提高效率，减少用户态与内核态之间的转换，将原本可以放在用户态的图形等软件放在内核态运行。

用户态：只能向系统申请使用资源。

Intel x86处理器状态有4种，分别支持4个特权级别，0级权限最高，3级权限最低。

• 0级为内核级，处理I/O操作、执行中断处理、存储管理和其他关键操作。
• 1级为系统调用级，可以执行系统调用，获得特定的和受保护的程序的服务。
• 2级为共享库级，可以被多个运行进程共享，允许调用库函数，读取但不修改相关数据。
• 3级为应用程序级，所受到的保护最少。

（3）处理器状态及转换

用户态→内核态（中断或者异常）：

1. 程序请求操作系统服务，执行系统调用
2. 程序运行时产生中断事件（如I/O操作完成），运行程序被中断，转向中断处理程序处理
3. 程序运行时产生异常事件（如发生程序性中断，如用户态执行特权指令），运行程序被中断，转向异常处理程序处理

内核态→用户态：

通常是计算机提供的一条乘坐加载程序状态字的特权指令（如Intel x86的iret指令）。

（4）程序状态字

操作系统将程序运行时的一组动态信息汇集在一起，成为程序状态字（Program Status Word, PSW），并存放在处理器的一组特殊处理器中，以方便系统的控制和管理。1个正在执行的程序都有一个与其执行相关的PSW，而每个处理器都设置一个程序状态字寄存器 。

在Intel x86机器中，PSW由标志寄存器EFLAGS和指针寄存器EIP组成，均为32位。标志划分为三组：状态标志、控制标志和系统标志。

程序状态字寄存器一般包括以下内容：

• 程序基本状态
  • 程序计数器：指明下一条执行的指令地址
  • 条件码：表示指令执行的结果状态
  • 处理器状态位：指明当前的处理器状态，如目态或管态、运行或等待
• 中断码：保存程序执行时当前发生的中断事件
• 中断屏蔽位：指明程序执行中发生中断事件时，是否响应出现的中断事件

2.中断（操作系统是由中断驱动的 ）

（1）定义和目的

中断（interrupt）指在程序执行过程中遇到急需处理的事件时，暂时终止现行程序的在CPU上的运行，转而执行相应的事件处理程序，待处理完成后再返回断点或调度其他程序执行的过程。

中断事件发生后，中断装置能改变处理器内操作的执行顺序。

引入中断的目的：请求系统服务，实现并行工作，处理突发事件，满足实时要求，都需要打断处理器正常的工作。

（2）中断源分类

• 按中断事件的性质和激活方式划分：

  • 自愿性中断

    正在运行的程序所期待的事件（如请求分配外设、执行系统调用）。执行一条访管指令，一旦机器执行到一条访管指令时，便自愿停止现行程序的执行而转入访管中断处理程序处理 。

  • 强迫性中断

    • 机器故障中断事件：如电源故障、主存储器出错等

    • 程序性中断事件（异常）：定点溢出、除数为0、地址越界等

    • 外部中断事件：如时钟的定时中断、控制台发控制信息等

    • 输入输出中断事件：如设备出错、传输结束等

    不是正在运行的程序所期待的，而是由于随机发生的某种事故或外部请求信息所引起的。

• 中断事件的来源和实现手段划分

  • 硬中断（由硬件发出或产生的中断）

    • 外中断（又称中断，或者异步中断，指来自处理器和主存之外的中断 ，与CPU是异步的）

      • 电源故障中断

      • 时钟中断

      • 控制台中断

      • 它机中断

      • I/O中断等

      不同的中断具有不同的中断优先级，处理高一级中断时，往往会屏蔽部分或全部低级中断。

    • 内中断（又称异常，或者同步中断，指来自处理器和主存内部的中断，与CPU是同步的）

      • 访管中断
        • 系统调用
      • 硬件故障中断
        • 协处理器错误
        • 奇偶校验错
        • 总线超时
      • 程序性异常

        • 非法操作码

        • 地址越界

        • 页面失效

        • 调试指令

        • 除数为0

        • 浮点溢出

      通常是由程序执行过程中，发现与当前指令关联的、不正常的或错误的事件，异常（内中断）是不能被屏蔽的，一旦出现应立即响应并加以处理。

  • 软中断（不必由硬件发信号而能引发的中断称软中断，利用硬件中断的概念，用软件方式进行模拟，实现宏观上的异步执行效果）

（3）中断处理

1）硬件故障中断（由硬件故障产生的，排除故障须进行人工干预）

中断处理能做的工作是：

• 保护现场
• 防止故障蔓延
• 报告给操作员并提供故障信息以便维修和校正
• 对程序中所造成的破坏进行估价和恢复

2）程序性中断

• 语法错误，可由编译程序发现并报错
• 逻辑错误，可由测试程序发现并报错
• 程序运行过程中所产生的异常
  • 定点溢出
  • 阶码下溢
  • 除数为零

3）I/O中断

I/O中断处理原则：

• I/O操作正常结束
• I/O操作发生故障
• I/O操作发生异常
• 设备报到或设备结束

4）访管中断（自愿性中断，由程序执行访管指令引起）

访管中断的大致处理原则：

• 程序执行访管指令，并通过适当方式指名系统调用号
• 通过中断机制进入访管中断处理程序，现场保护到核心栈
• 通过系统调用入口表找到相应功能服务程序的入口地址
• 执行相应的服务程序，正常情况下结束后返回系统调用的下一条指令继续执行

5）时钟中断

时钟是操作系统进行调度工作的重要工具。可分为绝对时钟和间隔时钟。

①绝对时钟

系统设置绝对时钟寄存器，定时地把该寄存器的内容加1。如果开始时这个寄存器的内容为0，那么，只要操作员告诉系统开机时的年、月、日、时、分、秒，以后就可推算出当前的年、月、日、时、分、秒，计算当前时间时，只要按时钟中断的次数和绝对时钟寄存器的内容推算就可得到。

②间隔时钟

间隔时钟是定时将一个间隔时钟寄存器的内容减1，当间隔时钟寄存器的内容为0时，产生一个间隔时钟中断，起到闹钟的作用，意味着预定的时间到了。操作系统经常利用间隔时钟作控制调度。

3.进程（操作系统中最基本、重要的概念）

（1）定义

• 进程是程序的执行
• 并行程序称为进程
• 进程是可以和别的计算并发执行的计算
• 进程是一个数据结构及其上进行操作的程序
• 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
• 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位
• 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位（进程实体是由程序段、相关的数据段和进程控制块组成的）

费翔林版本

进程是具有独立功能的程序关于某个数据集合的一次执行过程，也是操作系统进行资源分配和保护的基本单位。

汤小丹版本

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

（2）进程的属性 (进程与程序比较)

①结构性

进程包含了数据集合和运行于其上的程序。每个进程至少包含三个组成要素：程序块、数据块和进程控制块。

②共享性

同一程序运行于不同数据集合上时，构成不同的进程。多个不同的进程可以共享相同的程序，所以进程和程序不是一一对应的。进程之间可以共享某些公用变量，进程的运行环境不再是封闭的。

③动态性

进程由创建而产生，由调度而执行，由撤销而消亡。程序是一组有序指令序列，作为一种系统资源是永久存在的。

④独立性

进程是系统中资源分配和保护的基本单位，也是系统调度的独立单位（单线程进程）。

⑤制约性

并发进程之间存在着制约关系，进程在进行的关键点上需要相互等待或互通消息，以保证程序执行的可再现性和计算结果的唯一性。

⑥并发性

在一个单处理器系统环境下，各个进程轮流占用处理器。

（3）进程的状态及转换

①三态模型

• 运行态（running）：进程占有处理器正在运行。
• 就绪态（ready）：进程具备运行条件，等待系统分配处理器以便运行（进程已经获得了除cpu以外的所有资源后处的状态）。
• 阻塞态（blocked）：又称为等待态（wait）或睡眠态（sleep），进程不具备运行条件，正在等待某个事件的完成。

②五态模型

• 新建态：对应进程刚被创建的状态。为一个新进程创建必要的管理信息，它并没有被提交执行，而是在等待操作系统完成创建进程的必要操作。
• 终止态：进程的终止。首先，等待操作系统进行善后处理，然后，退出主存进入终止态的进程不再执行，但依然临时保留在系统中等待善后，一旦其他进程完成了对终止态进程的信息抽取之后，系统将删除该进程。

③七态模型

为什么要有“挂起”状态？

答：由于进程的不断创建，系统资源已不能满足进程运行的要求，就必须把某些进程挂起（suspend），对换到磁盘镜像区中，暂时不参与进程调度，起到平滑系统操作负荷的目的 。

• 挂起就绪态（ready suspend）：表明进程具备运行条件但目前在辅助存储器中，当它被对换到主存才能被调度执行
• 挂起等待态（blocked suspend）：表明进程正在等待某一个事件且在辅助存储器中。

（4）进程映像

由于进程状态在不断发生变化，某时刻进程的内容及其状态集合称为进程映像。

进程映像包含以下要素：

①进程控制块（Process Control Block，PCB）

是进程存在的唯一标识，是操作系统中最为重要的数据结构，是操作系统用来记录和刻画进程状态及环境信息的数据结构，是进程动态特征的汇集，也是操作系统掌握进程的唯一资料结构和管理的主要依据。

一般来说，PCB应包含以下信息：

• 标识信息（用于唯一地标识一个进程，分为用户使用的外部标识符和系统使用的内部标识号）
• 现场信息（用于保留进程在运行时存放在处理器现场中的各种信息）
• 控制信息（用于管理和调度进程）

②进程程序块

是被进程执行的程序，规定进程一次运行所应完成的功能。

③进程核心栈

每一个进程都将捆绑一个系统/用户堆栈，进程在内核态工作时使用，用来保存中断/异常现场，保存函数调用的参数、局部变量和返回地址等。

④进程数据块

是进程的私有地址空间，存放各种私有数据，用户栈也在数据块中开辟，用于在函数调用是存放栈帧、局部变量和返回地址等参数。

（5）进程上下文

操作系统中把进程物理实体和支持进程运行的环境合称为进程上下文，当系统调度新进程占有处理器时，新老进程随之发生上下文切换，进程的运行被认为是在上下文中执行。

进程上下文的三个组成部分：

• 用户级上下文(user-level-context)：由用户进程的程序块、用户数据块（含共享数据块）和用户堆栈组成的进程地址空间。
• 系统级上下文(system-level-context)：包括进程控制块、内存管理信息、进程环境块，及系统堆栈等组成的进程地址空间。
• 寄存器上下文(register-level-context)：由程序状态字（PSW）寄存器和各类控制寄存器、地址寄存器、通用寄存器、用户栈指针等组成。

（6）进程切换

进程切换定义在内核态，是让处于运行态的进程中断运行，让出处理器，这时要做一次进程上下文切换、即保存老进程状态而装入被保护了的新进程的状态，以便新进程运行。

进程切换的实现步骤：

1. 保存被中断进程的处理器现场信息；
2. 修改被中断进程PCB的有关信息，如进程状态等；
3. 把被中断进程的PCB加入相关队列；
4. 选择占有处理器运行的另一个进程；
5. 修改被选中进程的PCB的有关信息，如改为运行态；
6. 修改被选中进程的地址空间，恢复存储管理信息；
7. 设置被选中进程的上下文信息来恢复处理器现场。

（7）模式切换

从用户态到核心态或从核心态到用户态的转换称为模式切换。

当发生中断或者系统调用时，暂停正在运行的进程，把处理器从用户态切换到核心态，执行系统服务程序，这就是一次模式切换。发生模式切换时，进程仍在自己的上下文中执行。内核在被中断进程的上下文中进行处理。

模式切换的步骤如下：

1. 保存被中断进程的处理器现场信息；
2. 处理器从用户态切换到核心态，以便执行系统服务程序或中断处理程序；
3. 如果处理中断，可根据所规定的中断级别设置中断屏蔽位；
4. 根据系统调用号或中断号，从系统调用表或中断入口地址标中找到系统服务程序或中断处理程序的地址。

（8）进程控制

• 创建
• 阻塞
• 唤醒
• 挂起
• 激活
• 终止
• 撤销

进程的控制和管理功能是由操作系统中的原语来实现的。

原语(Primitive)是在内核态下执行、完成系统特定功能的过程。

• 原语是机器指令的延伸，往往是为完成某些特定的功能而编制的一段系统程序。为保证操作的正确性，在许多机器中规定，执行原语操作时，要屏蔽中断，以保证其操作的不可分割性。
• 原语和机器指令类似，其特点是执行过程中不允许被中断，是一个不可分割的基本单位，原语的执行是顺序的而不可能是并发的。
• 原语的实现方法是以系统调用方式提供原语接口，且采用屏蔽中断的方式来实现原语功能，以保证原语操作不被打断的特性。

原语和系统调用的区别：

• 相同
  • 调用形式相同：都使用访管指令实现
• 不同
  • 实现方式不同：原语由内核实现，系统调用通常由系统进程或系统服务器实现
  • 运行方式不同：原语不可中断，系统调用执行时允许被中断，甚至有些操作系统中系统进程或系统服务器在用户态运行
  • 服务的对象不同：通常情况下，原语提供给系统进程或系统服务器使用，系统进程或系统服务器提供系统调用给系统程序（和用户）使用，系统程序提供高层功能给用户使用

①进程创建

进程的创建过程：

1. 在主进程表中增加一项，并从PCB池中取一个空白PCB；
2. 为新进程的进程映像分配地址空间。传递环境变量，构造共享地址空间；
3. 为新进程分配资源，除内存空间外，还有其他各种资源；
4. 初始化进程控制块（如状态、PSW、栈等），为新进程分配进程标识符；
5. 把进程加入就绪进程队列,或直接将进程投入运行；
6. 通知操作系统的某些模块，如记账程序、性能监控程序。

#include <stdio.h>
#include <unistd.h>

int main ()
{
    pid_t fpid;
    int count = 0;
    fpid = fork();
    if (fpid < 0)
        printf("Error in fork!\n");
    else if (fpid == 0)
    {
        printf("I am the child process, my process id is %d\n", getpid());
        ++count;
    }
    else
    {
        printf("I am the parent process, my process id is %d\n", getpid());
        ++count;
    }
    printf("统计结果是: %d\n", count);
    return 0;
}

②进程撤销

进程的撤销分为：

• 正常撤销
  • 分时系统中的注销
  • 批处理系统中的撤离作业步
• 非正常撤销
  • 程序运行过程中出现错误或异常

③进程阻塞和进程唤醒

进程阻塞是指一个进程让出处理器，去等待一个事件。

通常，进程自己调用阻塞原语阻塞自己，所以，阻塞是自主行为，是一个同步事件。当一个等待事件结束时会产生一个中断，从而激活操作系统，在系统的控制之下将被阻塞的进程唤醒。

进程的阻塞和唤醒是由进程切换来完成的。

引起进程阻塞的事件：

• 等待资源
• 等待I/O操作完成
• 新数据未到达
• 无新工作可做
• 执行P操作没有满足

进程阻塞是主动行为

进程阻塞的步骤：

1. 停止进程执行，保存现场信息到PCB；
2. 修改PCB的有关内容，如进程状态由运行改为等待等；
3. 把修改状态后的PCB加入相应等待进程队列；
4. 转入进程调度程序调度其他进程运行。

进程唤醒是被动行为

当进程期待的事件发生时，有关进程便调用唤醒原语wakeup把等待该事件的进程唤醒——把被阻塞的进程从相应的阻塞队列中移出，把其PCB中的进程状态改为就绪，然后把PCB插入到就绪队列。

进程唤醒的步骤：

1. 从相应等待进程队列中取出PCB；
2. 修改PCB有关信息，如进程状态改为就绪等；
3. 把修改后PCB加入有关就绪进程队列。

④进程挂起和激活

挂起原语执行过程如下：检查要被挂起进程的状态，若处于活动就绪态就修改为挂起就绪，若处于阻塞态，则修改为挂起阻塞。被挂起进程PCB的非常驻部分要交换到磁盘对换区。

激活原语主要工作：把进程PCB非常驻部分调进内存，修改它的状态，挂起等待态改为等待态，挂起就绪态改为就绪态，排入相应队列中。挂起原语既可由进程自己也可由其他进程调用，但激活原语却只能由其他进程调用。

4.线程

（1）概念

运行在同一个进程中的各个并发任务称为该进程的线程。

每个线程分别是进程中的一个执行流。 线程代表从进程划分出来的更小的任务单元。 在多线程进程中，进程是系统进行资源分配的基本单位，线程是处理器调度的基本单位。

（2）线程结构

（3）线程状态

• 运行
• 就绪
• 阻塞

（4）线程控制

①创建

进程创建时系统会缺省创建并启动一个线程，已经启动的线程可以再创建和启动同一进程中的其它线程。

②阻塞

即等待，暂停线程执行。

③恢复

被阻塞线程等待的事件发生时，线程变成就绪态或相应状态。

④结束

线程终止，撤销线程。

（5）线程实现

多线程实现方法：

• 用户级线程
• 内核级线程
• 混合式线程

①用户级线程

实现原理：

用户级线程是在一个进程内部实现了类似进程调度、进程切换功能的一层进程内多任务应用支持软件。 用户级线程不是由操作系统提供的，因而，操作系统不参与用户级线程的调度。

优点：

1. 线程切换不需要内核特权方式；
2. 针对不同进程按需选择不同的线程调度算法；
3. 用户级线程可以运行在任何操作系统上，不需对内核做任何改造。

缺点：

1. 线程执行系统调用时，不仅该线程被阻塞，且进程内的所有线程均被阻塞；
2. 纯用户级线程不能利用多处理器技术。

②内核级线程

实现原理：

内核级线程是在操作系统内核层对进程实现的多线程功能，操作系统以线程作为处理器调度和分派的基本单位。

优点：

1. 内核可以同时把同一进程中的多个线程调度到多个处理器上并行执行；
2. 进程中的一个线程被阻塞了，内核能调度同一进程的其它就绪线程运行；
3. 内核线程数据结构和堆栈小，切换速度快，内核自身也可采用多线程技术实现，提高系统执行速度和效率。

③混合式线程

某些操作系统提供了同时支持用户级线程与内核级线程的混合式线程设施，线程的创建、调度和同步在用户空间进行。 一个应用程序中的多个用户级线程被映射到一些（小于或等于用户级线程的数目）内核级线程上。

原理：

（6）线程与进程

每个线程分别是进程中的一个执行流。

线程代表从进程划分出来的更小的任务单元。

在多线程进程中，进程是系统进行资源分配的基本单位，线程是处理器调度的基本单位。

传统进程的特征：

传统进程中只有一个执行流，属于单线程进程，进程所代表的任务仅由一个执行流承担。

在单线程进程中，进程既是系统进行资源分配的基本单位，也是处理器调度的基本单位，两者合二为一。

多线程环境中的进程：

在多线程环境中，进程被定义为资源分配和保护的单位，多线程进程不再作为处理器调度和分派的基本单位，线程不是资源分配和保护的基本单位，而是处理器调度和分派的单位。

多线程环境中的线程：

线程是进程中能够独立执行的实体（控制流），是处理器调度和分派的基本单位。

5.处理机调度

（1）三级调度

进程调度自外向内分为三层，分别是高级调度（作业调度），中级调度（内存调度）和低级调度（进程调度）。

①高级调度

高级调度发生在新进程的创建中，它决定一个进程能否被创建，或者创建后能否被置成就绪状态。

②中级调度

中级调度反映到进程状态上就是挂起和解除挂起，它根据系统的当前负荷情况决定停留在主存中进程数。

③低级调度

低级调度决定哪一个就绪进程占有CPU。

（2）调度算法

①类型

调度算法类型分为：

• 剥夺式
• 非剥夺式

②原则

原则为：

• 资源利用率

  CPU利用率 = CPU有效工作时间 / CPU总的运行时间

  CPU总的运行时间 = CPU有效工作时间 + CPU空闲等待时间

• 吞吐率

  单位时间内CPU处理作业的个数。

• 公平性

  避免饥饿现象。

• 响应时间

  从交互式进程提交一个请求（命令）直到获得相应之间的时间间隔。

• 周转时间

  批处理用户从向系统提交作业开始到作业完成为止的时间间隔。

③7个算法

1）先来先服务（First Come First Served，FCFS）

算法思想：按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度。

类型：非剥夺式

是否导致饥饿：不会

优点：公平、算法实现简单。

缺点：对长作业有利，对短作业不利。排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。

2）最短作业优先算法（Shortest Job First，SJF）

算法思想：从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。

类型：非剥夺式

是否导致饥饿：会

优点：“最短的”平均时间、平均周转时间。

缺点：不公平。对短作业有利，对长作业不利。作业/进程的运行时间是由用户提供，并不一定真实，不一定能做到真正的短作业优先。

3）最短剩余时间优先算法（Shortest Remaining Time First，SRTF）

算法思想：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度。

类型：剥夺式

是否导致饥饿：不会

优点：对比非抢占式的短作业优先算法，抢占式的短作业优先算法的平均等待时间、平均周转时间、平均带权周转时间都更低。

4）最高响应比优先算法（Highest Response Ratio First，HRRF）

算法思想：HRRF是FCFS和SJF的结合，克服了两种算法的缺点，设置响应比最高的作业优先启动。

等待时间 + 服务时间 = 该作业的响应时间。

类型：非剥夺式

是否导致饥饿：不会

响应比 = 1 + 作业等待时间 / 作业处理时间

优点：既照顾了短作业，又考虑了作业到达的先后次序，又不会使长作业长期得不到服务。

等待时间相同时，要求服务时间短的优先（SJF的优先，对短作业有利）；

要求服务时间相同时，等待时间长的优先（FCFS的优点）；

随着等待时间越来越长，其响应比也会越来越大，从而避免了长作业饥饿的问题（长作业有利）。

缺点：要进行响应比计算，增加了系统开销。

5）优先级调度算法（Priority Scheduling Algorithm，PSA）

算法思想：根据确定的优先级来选取进程/线程，总是选择就绪队列中优先级最高者投入使用。

类型：剥夺式/非剥夺式

是否导致饥饿：会

优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。

缺点：若源源不断地有高优先级进程到来，则可能导致饥饿。

几个例子：

（1）抢占式优先级调度算法

把处理机分配给优先级最高的进程，但在执行期间，只要出现另一个优先级更高的进程，则进程调度程序就立即停止当前进程的执行，并将处理机分配给新到的优先级最高的进程。只要系统中出现一个新的就绪进程，就进行优先级比较

（2）非抢占式优先级调度算法

系统一旦把处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去，直至完成。

（3）静态优先级调度算法

静态优先级在创建进程时确定，且在进程的整个运行期间保持不变。

（4）动态优先级调度算法

优先级随进程的推进或随其等待时间的增加而改变，以获得更好的调度性能。

6）轮转调度算法（Round-Robin，RR）

算法思想：系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便停止该进程的执行，并将其放就绪队列尾；然后，再把处理机分配给就绪队列中新的队首。

类型：剥夺式

是否导致饥饿：不会

优点：公平，响应快，适用于分时操作系统。

缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急性。

7）多级反馈队列（Multi-Level Feedback Queue，MLFQ）

算法思想：设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先级逐个降低。各个队列中时间片的大小也各不相同，队列优先级愈高，时间片就愈小。

类型：剥夺式/非剥夺式

是否导致饥饿：会

优点：对其他调度算法的折中权衡。

对各类进程相对公平（FCFS的优点）；

短进程只用较少的世界就可完成（SPF的优点）；

每个新到达的进程都可以很快得到响应（RR的优点）；

不必实现估计进程的运行时间（避免用户作假）；

可灵活地调整对各类进程的偏好程度，比如：CPU密集型进程、I/O密集型进程（拓展：可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级）。

缺点：可能会导致饥饿

剥夺式例题视频：

非剥夺式例题视频：