基础概念

什么是操作系统

操作系统(Operating System)，是介于硬件资源和应用程序之间的一个系统软件 ，能控制和管理整个计算机系统的硬件和软件资源，调度计算机的工作与资源的分配，进而为用户和其他软件提供服务，操作系统是计算机系统中最基本的系统软件。

如果将它理解为“掌控计算机的系统”是否更能精确的描述OS所做的事情呢？

如果要更深入的掌握这个问题，可以问一问：如果没有了操作系统，你使用的PC机还能干什么？或者说，你能够使用你的PC机做什么呢？

操作系统的特征：

  • 并发：并发指的是两个或多个事件在同一时间间隔内发生，计算机系统中同时存在多个运行的程序，因此具有处理和调度多个程序同时执行的能力。

⚠️注意：并行和并发的区别：并发指的是同一时间间隔，并行指的是同一时刻。

  • 共享：系统中的资源可以供内存中多个并发执行的进程共同使用。
    • 互斥共享：一段时间内只允许一个进程访问该资源。一段时间内只允许一个进程访问的资源称为临界资源。
    • 同时访问：一段时间内允许多个进程“同时”访问，“同时”通常是宏观的，实际上是交替的对该资源进行访问。
  • 虚拟：把一个物理上的实体变为若干逻辑上的对应物。
  • 异步：进程的执行并不是一贯到底的，而是以不可预知的速度向前推进。

操作系统的功能

操作系统位于硬件资源之上，管理硬件资源; 应用程序之下，为应用程序提供服务，同时管理应用程序

1、资源分配，资源回收

计算机必要重要的硬件资源无非就是 CPU、内存、硬盘、I/O设备。 而这些资源总是有限的，因此需要有效管理，资源管理最终只有两个问题：资源分配、资源回收。

资源分配： 体现在CPU上，比如进程调度，多个进程同时请求CPU下，应该给哪一个进程呢？再比如内存分配，内存不够了怎么办？A进程非法访问了B进程的内存地址怎么办？内存内、外碎片问题等。

资源回收： 考虑内存回收后的合并等等。

2、为应用程序提供服务

操作系统将硬件资源的操作封装起来，提供相对统一的接口（系统调用）供开发者调用。

如果没有操作系统，应用程序将直接面对硬件，除去给开发者带来的编程困难不说，直接访问硬件，使用不当极有可能直接损坏硬件资源。

3、管理应用程序

即控制进程的生命周期：进程开始时的环境配置和资源分配、进程结束后的资源回收、进程调度等。

4、操作系统内核的功能

（1）进程调度能力： 管理进程、线程，决定哪个进程、线程使用CPU。

（2）内存管理能力： 决定内存的分配和回收。

（3）硬件通信能力： 管理硬件，为进程和硬件之间提供通信。

（4）系统调用能力： 应用程序进行更高限权运行的服务，需要系统调用，用户程序和操作系统之间的接口。

操作系统的角色

1、管理者

主要分为：CPU管理、内存管理、外存管理、IO管理；以及自己的健壮性和安全性管理。

健壮性，又称鲁棒性，即使很粗鲁的对待程序，它还是可以很好的运行。

2、魔术师:

比如操作系统会让每个进程都觉得自己独占CPU、独占整片物理内存，而实际上每个进程都只是在某一时间段内占用CPU，仅仅只是占用实际一点点物理内存。

用户程序与操作系统的关系

用户程序和操作系统之间是相互调用的关系

1、操作系统的角度

计算机启动后启动的第一个软件就是操作系统，随后启动的所有进程都运行在操作系统之上，使用操作系统提供的服务，同时被操作系统监控，进程结束后也由操作系统回收。

2、进程角度

调用操作系统提供的服务，实现自己的功能。

进程与线程

进程和线程的区别？

【简要回答】

进程和线程的概念

  • 进程：进程（Process）是计算机中一个执行的程序实例，每个进程对应一个运行中的程序；进程是操作系统资源分配的最小单位，在未引入线程概念的操作系统中，同样是调度的最小单位。
  • 线程：线程（Threads）是比进程更小的概念，也称“轻量级进程（Light Weight Process, LWP），是将进程进一步细分的单位；在多道程序操作系统中，线程概念的引入可以进一步提高程序的并发执行程度，一个进程可以同时拥有多个线程，借助多个线程实现程序的并发执行（而不必借助进程）。

进程和线程的对比

  • 调度单位：引入内核级线程后，进程不再是调度的最小单位；线程是调度的最小单位。
  • 资源分配：无论是否引入“线程”，进程始终都是资源分配的最小单位；线程只拥有少量资源（来自创建它的进程）。
  • 并发性：多个进程间可以并发执行；一个进程的多个线程也能并发执行。
  • 独立性：进程之间默认不共享全局变量，且拥有独立的地址空间和不同资源；线程之间只有少数资源不能共享（例如线程的栈区）。
  • 系统开销：“进程通信”，“进程切换”开销大；“线程通信”，“线程切换”开销小。
  • 多处理机：单个进程只能运行在一个处理机上；多线程进程可以充分利用多处理机（内核级线程）。
  • 协同工作：进程之间互不影响；用户级线程的阻塞会影响到整个进程的执行。

【详细回答】

  • 进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的独立单位。
  • 进程的主要特点：
    1. 动态性：从创建到消亡，是动态的，具有生命周期。
    2. 并发性：多个进程并发执行时，会有以下3个特性：
      • 间断性：并发的进程有间断运行的特点，当多个进程协同完成同一任务时，需要进行同步等操作，进而导致进程的暂停。
      • 失去封闭性：并发进程会共享系统中的资源，任意进程都可能改变某个资源的状态，从而影响到其他进程。失去封闭性意味着进程的执行结果取决于其执行速度，使得进程的执行有不可再现性（每次执行的结果不一定相同）；失去封闭性导致了不可再现性。
      • 不可再现性：在相同的初始环境和条件下，并发执行的进程可能得到不同的结果。
    3. 独立性：进程能够独立运行，是资源分配的最小单位，各个进程获得的资源独立于其他进程。
    4. 异步性：进程以不可预知的状态向前推进。进程的并发性导致了进程的异步性。但是，通过同步与互斥，可以保证在异步性的前提下得到确定（可再现）的结果。
  • 未引入线程概念时，进程有两个特点：
    ①是资源所有权最小单位，指一个进程拥有对资源的控制和所有权，包括内存、I/O通道、I/O设备等；
    ②是调度/执行的最小单位，指进程是一个可以被操作系统内核调度的独立实体。
  • “线程”可以看作是在调度/执行这一属性上对进程的进一步细分——在引入线程前，进程是操作系统调度的最小单位；在引入线程且是由操作系统内核支持的线程（即内核级线程）后，线程是操作系统调度的最小单位。
  • 引入线程的优势：
    1. 进一步提高并发性：在单处理机系统中，线程模型可以分离同一个进程内的CPU计算和I/O访问，让它们并发执行；在多处理机系统中，引入线程模型后，每个内核级线程都能占用一个处理机，这使得多处理机系统的优势得以发挥。
    2. 共享地址空间与可用数据：线程之间可以直接共享数据而不需要经由操作系统内核，在速度上有很大优势。
    3. 更轻量级：在很多操作系统中，一个线程的创建比一个进程的创建快10~100倍。（线程的切换和撤销也远快于进程）
    4. 更好的交互性：线程可以提高图形界面程序的交互性，避免程序“卡死”，使用户得到更好的体验。

【知识图解】

  1. 进程的基本结构和资源所有权，示意图如下：
    image
  2. 多进程模型 和 多线程模型 的内存布局，示意图如下：
    image

【知识拓展】

  • 线程的实现方式主要分为两类——内核级线程（Kernel Supported Threads，KST）和用户级线程（User-Level Threads，ULT）。
    1. 用户级线程：线程的管理由应用程序实现，在用户空间下完成，操作系统感知不到线程的存在。在这种实现方式下，系统调度的最小单位依然是进程，线程的调度则由其所在进程实现。
    2. 内核级线程：需要操作系统内核的支持，其创建、阻塞、撤销和切换都是在内核空间下实现的，内核通过TCB（线程控制块）来对线程进行感知和控制。在这种实现方式下，线程是系统调度的最小单位。

进程间有哪些通信方式？

简要回答

  1. 信号量机制（Semaphore）：进程通过P / V操作控制信号量，可以有效地解决同步和互斥问题；信号量机制适合需要同步的场景，如避免竞争条件和死锁。
  2. 共享存储机制（Shared Memory）：共享内存是一种高效的进程间通信方式，允许多个进程直接访问同一块内存区域。共享存储机制适合需要高效数据传输的场景。
  3. 消息传递机制（Message Passing）：消息传递机制需要操作系统内核的支持，通过消息队列 或 信箱传递数据，消息以数据块的形式传输。消息传递机制支持不同类型的数据，适用于无关进程之间的通信。
  4. 管道通信机制（Pipeline）：管道通信机制适合进程间的简单数据传输，其又可细分为两类——①匿名管道：半双工通信，适用于父子进程或兄弟进程；②命名管道：具有文件名，适用于无关进程。
  5. 套接字机制（Socket）：Socket（套接字）是一种网络通信机制，可以在不同主机上的进程之间进行通信；Socket机制适合分布式系统和网络通信。

详细回答

  1. 信号量机制（Semaphore）：信号量是一种同步通信机制，用于控制多个进程对共享资源的访问；信号量支持两种原子操作：P()（等待）和V()（信号）。
  2. 共享存储机制（Shared Memory）：共享存储机制又可细分为两种方式——①共享数据结构的通信方式：进程间共享同一个数据结构，编程人员需要考虑进程间的同步互斥问题，传输效率低；②共享存储区的通信方式：操作系统在内存中开辟一块共享存储区，多个进程可以对该内存区域进行读写，传输效率高。当进程希望对共享存储区进行存取时，会将自己的虚地址空间映射到共享存储区，并向操作系统提出申请。
  3. 消息传递机制（Message Passing）：进程之间可以调用由操作系统实现的通信命令来传递消息；实现消息传递即分别实现Send 和 Receive两个原语，用于消息的发送和接收。消息传递机制又可细分为两类——①直接通信方式：发送进程直接将消息发送给接收进程，将信息挂载到接收进程的消息队列上，接收进程从自己的消息队列中获取信息；②间接通信方式：操作系统额外创建一片空间用于存储各种消息，类似一个信箱，发送进程和接收进程依靠这个中间实体实现信息的发送和接收，这种方式也被称为 “信箱通信模式”，在计算机网络中被广泛运用。
  4. 管道通信机制（Pipeline）：管道机制又可细分为两种类型——
    ①匿名管道：即我们平时所说的“管道”通信，它使用一种共享文件来实现进程间通信，这种共享文件被称为“管道” 或 “pipe文件”，可以连接一个读进程和一个写进程。写进程以字节流的形式，将数据送入管道，读进程通过管道将数据读出。匿名管道是一种半双工的通信方式，数据只能单向流动，适用于父子进程或兄弟进程之间的通信；在UNIX/Linux系统中，使用pipe()系统调用创建匿名管道。
    ②命名管道（Named Pipe/FIFO）：一种特殊的管道，具有文件名，可以在无关进程之间使用；在UNIX/Linux系统中，使用mkfifo()系统调用创建命名管道。
  5. 套接字机制（Socket）：Socket是一种网络通信机制，支持不同主机上的进程之间进行通信。Socket支持网络通信，适用于分布式系统，其通信方式可以是面向连接的（如TCP），也可以是无连接的（如UDP）。

知识图解

  1. 消息传递机制的示意图如下所示：
    image
  2. 管道实现全双工通信的示意图，如下所示：
    image

知识拓展

  • 操作系统实现管道机制，需要提供三种机制——①同步机制；②互斥机制；③通信进程间确定对方存在的机制。
  • 管道具有以下特点：
    1. 同步：写进程向管道中写入一定量数据后，会进入阻塞状态，等待读进程将数据读出后将其唤醒；读进程在将管道中数据读完后，也会进入阻塞状态，等待写进程对管道写操作完毕后将其唤醒。
    2. 互斥：当有一个进程在对一个管道读/写时，其他想要读/写该管道的进程必须等待。
    3. 管道需要通信双方确定对方的存在，否则会陷入阻塞。
    4. 管道是一个固定大小的 缓冲区（如4KB），在内核中实现，其大小不受磁盘大小的影响。
    5. 管道的实质是一个共享文件，读进程将管道视为输出文件，写进程将管道视为输入文件，因此管道通信机制可以利用文件系统机制实现。
    6. 读数据操作是一次性的，管道中的数据一旦被读取就会被抛弃。
    7. 管道是半双工通信的，某一时刻，数据只能单向传输，若希望实现双向传输（即全双工通信），可以使用两个管道。
  • 当多个进程读写同一个管道时，可能会出现读写错乱，解决方案——
    1. 一个管道允许多个写进程，一个读进程；
    2. 允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据。

进程调度算法你了解多少

简要回答

  1. 先来先服务（FCFS, First-Come, First-Served）：
    • 工作原理：进程按照到达顺序进入就绪队列，CPU依次执行队列中的进程。FCFS是非抢占式，一旦进程开始执行，直到完成才会释放CPU。
    • 适用情景：批处理系统，任务执行时间差异不大的场景。
    • 优点：实现简单，公平性较高。
    • 缺点：可能导致“饥饿”现象，长作业会阻塞短作业；平均等待时间较长，不适合交互式系统。
  2. 短进程优先调度算法（SPF和SRT）：
    • 工作原理：
      1> SPF（Shortest Process First）：非抢占式，选择当前就绪队列中运行时间最短的进程执行。
      2> SRT（Shortest Remaining Time）：抢占式，选择剩余运行时间最短的进程执行。
    • 适用情景：适合批处理系统，尤其是短作业较多的场景。
    • 优点：
      1> SPF（Shortest Process First）：减少平均等待时间，适合短作业。
      2> SRT（Shortest Remaining Time）：进一步优化平均等待时间。
    • 缺点：
      1> SPF（Shortest Process First）：长作业可能“饥饿”。
      2> SRT（Shortest Remaining Time）：需要频繁计算剩余时间，开销较大。
  3. 优先级调度算法（PSA, Priority Scheduling Algorithm）：
    • 工作原理：每个进程分配一个优先级，CPU选择优先级最高的进程执行；可以是抢占式或非抢占式。
    • 适用情景：适合实时系统或需要区分任务优先级的场景。
    • 优点：灵活，可根据任务重要性调整优先级。
    • 缺点：低优先级进程可能“饥饿”；动态调整优先级会增加开销。
  4. 高响应比优先调度算法（HRRN, Highest Response Ratio Next）：
    • 工作原理：选择响应比最高的进程执行，响应比 = (等待时间 + 运行时间) / 运行时间。
    • 适用情景：适合批处理系统，任务执行时间差异较大的场景，兼顾等待时间和运行时间。
    • 优点：兼顾公平性和效率，减少平均等待时间。
    • 缺点：需要计算响应比，开销较大。
  5. 时间片轮转调度算法（RR, Round Robin）：
    • 工作原理：每个进程分配一个时间片（如10ms），时间片用完后切换到下一个进程。
    • 适用情景：交互式系统，如桌面操作系统。
    • 优点：公平性高，适合交互式系统。
    • 缺点：时间片过大会退化为FCFS。
  6. 多级队列调度算法（Multilevel Queue Scheduling）：
    • 工作原理：将进程按优先级或类型分配到不同的队列，每个队列采用不同的调度算法（如FCFS、RR）；队列之间可以有优先级，高优先级队列的进程优先执行。
    • 适用情景：适合任务类型多样的系统，如混合批处理和交互式任务。
    • 优点：灵活，可根据任务类型定制调度策略。
    • 缺点：可能导致低优先级队列的进程“饥饿”。
  7. 多级反馈队列调度算法（Multilevel Feedback Queue Scheduling）：
    • 工作原理：将就绪队列分为多个子队列，每个队列的时间片大小不同；新进程到达首先进入最高优先级队列，时间片用完后降级到下一队列；低优先级队列的时间片较大，避免频繁切换。
    • 适用情景：通用操作系统，如Linux、Windows。
    • 优点：能较好地满足各类进程对处理器的需求；适合通用操作系统。
    • 缺点：实现复杂，开销较大。

详细回答

  1. 先来先服务（FCFS, First-Come, First-Served）：
    • 工作原理：也称为FIFO（First In First Out），可以适用于作业调度，进程调度；每次进程调度时，系统会从就绪队列中选择一个最先进入该队列的进程，将该进程的状态转为执行态并为其分配处理器资源，直到下一个调度的时机到来。
    • 适用情景：批处理系统，任务执行时间差异不大的场景。
    • 优点：逻辑简单，公平性较高。
    • 缺点：可能导致“饥饿”现象，长作业会阻塞短作业；效率差，平均等待时间较长，不适合交互式系统；无法实现人机交互；未考虑到不同进程间的差异性（例如进程的紧急性）；更加偏向处理器密集型进程 和 长进程。
  2. 短进程优先调度算法（SPF和SRT）：- 工作原理： 可以适用于作业调度、进程调度。 PS：**有些教材将SPF专指非抢占式短进程优先调度算法，而将抢占式短进程优先调度算法称为最短剩余时间优先调度算法，即SRT，此处也这样划分。
    **1> SPF（Shortest Process First）**：**非抢占式**，在进程调度时，根据就绪队列中排队的进程所预估的处理器使用时间，每次调度选择预估剩余处理器使用时间最短的进程；在作业调度时，称为短作业优先调度算法（Shortest Job First, SJF），根据外存队列中作业所要求的执行时间来调度作业，每次调度选择预估剩余处理器使用时间最短的作业。
    **2> SRT（Shortest Remaining Time）**：**抢占式**，选择**剩余运行时间最短**的进程执行；如果在当前进程运行过程中，就绪队列中出现了要求时间更短的进程，则这个要求时间更短的进程会    抢占处理器资源，当前运行的进程状态会由执行态变为就绪态。- 适用情景：适合批处理系统，尤其是短作业较多的场景。- 优点：
    1> SPF（Shortest Process First）：较FCFS性能更好，    如果调度时满足“待调度进程同时可运行” 或者 “待调度进程都几乎同时到达”，那么SPF的平均等待时间和平均周转实际是最优的**。
    2> SRT（Shortest Remaining Time）：进一步优化平均等待时间。- 缺点：
    1> SPF（Shortest Process First）：长作业可能“饥饿”；算法需要进程预估其运行时间，在预估时，可能出现估算时间不准确 或者 进程“谎报”时间等问题；同FCFS一样，未考虑到不同进程间的差异性。
    2> SRT（Shortest Remaining Time）：需要频繁计算剩余时间，开销较大。
  3. 优先级调度算法（PSA, Priority Scheduling Algorithm）：
    • 工作原理：可以适用于作业调度、进程调度；作业（进程）的优先级由外界赋予，系统只需要根据外界赋予的优先级来进行调度即可；根据是否可以抢占，优先级调度算法可以分为“非抢占式优先级调度算法” 和 “抢占式优先级调度算法”；根据在调度程序运行过程中优先级是否可以动态变化，优先级调度算法又可分为“静态优先级” 和 “动态优先级”。对于静态优先级，是指各个进程的优先级在调度程序运行之初就已经确定好，整个运行期间不会改变；对于动态优先级，是指在调度程序运行的过程中，各个进程的优先级是动态变化的。
    • 适用情景：适合实时系统或需要区分任务优先级的场景。
    • 优点：灵活，可根据任务重要性调整优先级。
    • 缺点：低优先级进程可能“饥饿”；动态调整优先级会增加开销。
  4. 高响应比优先调度算法（HRRN, Highest Response Ratio Next）：
    • 工作原理：可以适用于作业调度、进程调度；高响应比优先调度算法综合考虑了进程（作业）的等待时间和运行时间来调度进程，响应比 = (等待时间 + 运行时间) / 运行时间；随着进程的等待时间增加，该进程的优先级就会变高，更容易被调度。。
    • 适用情景：适合批处理系统，任务执行时间差异较大的场景，兼顾等待时间和运行时间。
    • 优点：兼顾公平性和效率，减少平均等待时间。
    • 缺点：需要计算响应比，开销较大。
  5. 时间片轮转调度算法（RR, Round Robin）：
    • 工作原理：适用于进程调度一般不适用于作业调度；RR算法将处理器使用时间分成一个个时间片，公平地分给每一个等待处理器资源的就绪进程，当时钟中断发生时，系统会修改当前进程在时间片内的剩余时间，当一个进程分配的时间片耗尽后，其会重新进入就绪队列等待下一次分配时间片。系统会将所有就绪进程按照FCFS算法来维护就绪队列，每个时间片结束后操作系统都会结束当前进程，将当前进程放回到就绪队列末尾，并调度下一个就绪程序运行；在这种策略下，每个进程都能公平地使用处理器资源，也保证了进程的响应时间。
    • 适用情景：分时操作系统，交互式系统，如桌面操作系统。
    • 优点：公平性高，适合交互式系统。
    • 缺点：时间片过大会退化为FCFS。
  6. 多级队列调度算法（Multilevel Queue Scheduling）：
    • 工作原理：仅适用于进程调度；该算法将就绪队列置为多个，根据就绪进程的特点和类型，将其分配在不同的就绪队列中。针对每个就绪队列，可以采用不同的调度算法；这样不但可以凸显出各种调度算法的优势，也能在一定程度上弥补这些算法的缺点。每个队列都可以是抢占式的，也都可以是非抢占式的，并且也都可能导致“饥饿”现象，具体要取决于各个队列的调度策略和优先级设置。
      尤其是在多处理器系统中，可以利用该调度算法为每个处理器资源指定一个就绪队列，这样既可以根据进程类型和紧急程度等因素为进程分配更合理的就绪队列，还有利于需要多组线程或进程协作完成任务的情况，即将这些线程或进程分配到不同的就绪队列中，使得它们可以同时获得处理器资源。
    • 适用情景：适合任务类型多样的系统，如混合批处理和交互式任务。
    • 优点：灵活，可根据任务类型定制调度策略。
    • 缺点：可能导致低优先级队列的进程“饥饿”。
  7. 多级反馈队列调度算法（Multilevel Feedback Queue Scheduling）：- 工作原理：仅适用于进程调度；将就绪队列分为多个子队列，每个子队列的时间片大小不同；为每个子队列依次分配递减等级的优先级，第一个就绪队列拥有最高的优先级，第二个就绪队列的优先级次于第一个就绪队列，以此类推；在每个就绪队列中，根据该队列的优先级，划分大小不同的时间片，一般高优先级的队列中时间片更小，低优先级的队列中时间片更大。
    PS_1: 当一个作业的进程被创建并分配资源后，首先将其放入第一个就绪队列的末尾，并依据FCFS算法进行调度，如果该进程并调度执行后在一个时间片内未完成其任务，就会被降级到下一个队列，重新进行上述过程，一直到进程被降级到最低优先级的队列中，此时进程不会继续降级，而是在最低优先级的就绪队列中遵循时间片轮转调度算法（RR） 等待调度。
    PS_2: 调度时，按照队列的优先级进行调度，高优先级就绪队列中的进程会被优先调度，对于第i级队列，只有当1 ~ i-1队列都不存在就绪进程时，才可以调度i级队列中的进程；如果当前使用处理器资源的进程来自第i级队列，而此时第一级队列中进入了新的就绪进程，那么会立刻进行抢占式进程调度，并将此时正在运行的程序放回i级队列末尾。- 适用情景：通用操作系统，如Linux、Windows。- 优点：能较好地满足各类进程对处理器的需求；适合通用操作系统（许多现代操作系统使用的调度算法都是基于MLFQ的变体）。- 缺点：实现复杂，开销较大。

知识图解

  1. 七种调度算法的对比，如下图所示： image
  2. 多级队列调度算法，示意图如下：
    image
  3. 多级反馈队列调度算法，示意图如下：
    image

知识拓展

  • 在多道程序系统中，一个作业从被提交并加入等待队列开始，到运行结束这一过程中，可能发生三种层次的调度，分别是“作业调度”，“内存调度” 和 “进程调度”，根据调度发生的层次，又依次称为“高级调度”，“中级调度” 和 “低级调度”——
    1. 高级调度（High Level Scheduling）：又称作业调度 或 长程调度，调度的对象是外存中等待的作业，调度的行为是将作业从外存调度到内存中；高级调度的发生频率较低。
    2. 中级调度（Intermediate Scheduling）：又称内存调度，调度的对象是暂时不能运行的进程，调度的行为是将目标进程的相关数据和资源在内存和外存间移动，即将进程由就绪态→就绪挂起态，或者是阻塞态→阻塞挂起态（涉及到进程 / 线程的七状态模型）；中级调度的发生频率不高也不低。
    3. 低级调度（Low Level Scheduling）：又称进程调度，调度的对象是进程（或内核级线程），调度的行为是决定将处理器资源先分配给哪个进程；低级调度的发生频率很高。

进程调度算法有哪些？适用场景是什么？

面试时没有回答好问题是很正常的，被面试官质疑时，要有今天不会明天会的底气，面后做好复盘，不在同一道题目上跌倒第二次，今天就从 C++中的inline函数 vs #define宏的区别 背起来

你对进程调度算法的了解有哪些？适用场景是什么？

简要回答

进程调度算法是操作系统决定哪个就绪进程获得CPU时间的方法。

主要分为非抢占式（FCFS、SJF）和抢占式（RR、优先级调度、多级队列）。

现代系统采用多级反馈队列（MLFQ）结合多种策略，平衡响应时间、吞吐量和公平性。

详细回答

  • 调度算法分类体系：

批处理调度：FCFS、SJF、HRRN - 注重吞吐量

交互式调度：RR、优先级调度 - 注重响应时间

实时调度：EDF、RMS - 满足时间约束

混合调度：MLFQ - 自适应多种负载

  • 关键调度指标：

周转时间：从提交到完成的总时间

响应时间：从提交到首次响应的时间

吞吐量：单位时间完成的进程数

公平性：各进程获得CPU时间的均衡度

CPU利用率：CPU忙碌时间的比例

调度算法就像不同的管理风格：

FCFS（先来先服务）：排队文化，先到先得，简单公平但效率可能不高

SJF（短作业优先）：效率优先，让耗时小的作业先执行，但可能饿死大作业

RR（时间片轮转）：民主分配，每进程轮流用一会儿，保证响应速度

优先级调度：特权制度，重要任务优先，但要防止低优先级饿死

现代操作系统像经验丰富的项目经理，会根据任务特点动态调整策略。

进程调度算法特性比较表

调度算法 抢占性 公平性 响应时间 吞吐量 实现复杂度 主要特点
FCFS (先来先服务) 非抢占 高 差 中 低 • 简单公平 • 可能产生 convoy 效应 • 对长作业有利
SJF (短作业优先) 非抢占 低 好 高 中 • 最小化平均等待时间 • 可能饿死长作业 • 需要预知执行时间
SRTF (最短剩余时间优先) 抢占 低 很好 高 高 • SJF的抢占式版本 • 响应时间优秀 • 实现复杂度高
RR (时间片轮转) 抢占 高 好 中 中 • 公平性好 • 时间片大小影响性能 • 适合交互式系统
优先级调度 可选 低 好 高 中 • 支持优先级区分 • 可能饿死低优先级 • 可配置抢占性
MLFQ (多级反馈队列) 抢占 中 很好 高 高 • 自适应调度 • 平衡响应和吞吐 • 防止饿死机制
CFS (完全公平调度) 抢占 很高 很好 高 很高 • 红黑树管理进程 • 基于vruntime • 高度公平性

知识拓展

  • 各种调度算法的典型应用场景

FCFS适用场景： 批处理系统， 简单的嵌入式系统， 教学演示环境， 负载极轻的服务器

SJF/SRTF适用场景： 已知作业长度的批处理， 科学计算任务调度， 编译服务器， 需要最小化平均等待时间的场景

RR适用场景： 分时操作系统， 交互式系统（桌面、服务器）， 需要公平性的多用户环境， 实时性要求不高的通用系统

优先级调度适用场景： 实时系统， 关键任务系统， 有明确优先级区分的应用， 操作系统内核任务调度

MLFQ适用场景： 现代通用操作系统（Windows、macOS的某些版本）， 混合型工作负载（交互式+批处理）， 需要平衡响应时间和吞吐量的系统

CFS适用场景： Linux桌面和服务器系统， 需要高度公平性的环境， 虚拟化环境， 多核处理器系统

  • 知识图解

image

  • 面试官很能追问

Q1: 什么是 convoy效应？如何避免？

A1: Convoy效应是指一个长进程阻塞了后面多个短进程的执行。

表现：短进程需要等待长进程完成，导致平均等待时间增加

原因：FCFS调度算法对长进程友好，对短进程不利

避免方法：使用抢占式调度（如RR、SRTF）或设置最大执行时间限制

Q2: 多级反馈队列如何防止进程饿死？

A2: MLFQ通过以下机制防止饿死：

优先级提升：低优先级进程等待一定时间后提升到高优先级队列

时间片调整：低优先级队列使用更大的时间片，保证获得足够的CPU时间

周期重置：定期将所有进程移回最高优先级队列，重置调度历史

Q3: 实时调度中EDF和RMS的区别是什么？

A3: 主要区别：

EDF（最早截止时间优先）：动态优先级，选择绝对截止时间最早的任务

RMS（速率单调调度）：静态优先级，周期越短的任务优先级越高

可调度性：RMS有固定的CPU利用率上限（69%），EDF可达100%

适用性：RMS适合固定周期任务，EDF适合动态周期任务

中断与异常

什么是中断、异常？

简要回答

中断和异常都是CPU响应特殊事件的机制，会打断当前执行流程：

中断（Interrupt）：来自CPU外部的异步事件，如I/O设备请求、时钟信号

异常（Exception）：来自CPU内部的同步事件，如指令执行错误、系统调用

两者都会触发CPU从用户态切换到内核态，执行相应的处理程序。

专业回答

中断和异常是处理器响应突发事件的核心机制，统称为中断向量（Interrupt Vector）

  • 中断（Interrupt）

定义：由外部硬件设备产生的异步事件信号，用于通知CPU有需要处理的事件。

特性： 异步性：与CPU当前执行指令无关，随时可能发生；可屏蔽：可以通过中断屏蔽位暂时禁止某些中断；可嵌套：高级中断可以打断低级中断处理

分类： 硬件中断（Hardware Interrupt） 可屏蔽中断（INTR）：可通过CLI指令屏蔽 非屏蔽中断（NMI）：不可屏蔽，如内存奇偶校验错

软件中断（Software Interrupt） INT指令触发，如系统调用（Linux的int 0x80）

  • 异常（Exception）

定义：由CPU内部执行指令时检测到的同步事件。

特性： 同步性：特定指令执行必然产生；不可屏蔽：无法通过软件屏蔽；精确性：可以精确定位到出错指令

分类： 故障（Fault）：可恢复错误，如缺页异常、除零异常 陷阱（Trap）：有意产生，如断点调试、系统调用 终止（Abort）：严重错误，无法恢复，如硬件故障

知识拓展

  • 知识图解

image

  • 适用场景

中断适用场景 实时响应：键盘输入、网络包到达， 周期性处理：系统时钟、任务调度， 异步通知：DMA传输完成， 设备管理：磁盘I/O完成

异常适用场景 错误处理：除零、溢出、非法内存访问， 调试支持：断点、单步执行， 资源管理：页错误（虚拟内存）， 系统调用：从用户态陷入内核态

  • 面试官很能追问

Q1：中断处理为什么分上下半部？

A1：上半部（硬中断处理）快速响应，只做必要操作（保存数据），下半部（软中断/任务队列）处理耗时操作，减少中断屏蔽时间，提高系统响应性。

Q2：中断和异常处理时，CPU保存哪些上下文？

A2：至少包括程序计数器（PC）、处理器状态字（PSW）、关键寄存器。x86会保存EFLAGS、CS、EIP；ARM保存CPSR和返回地址。

Q3：页错误是中断还是异常？为什么？

A3：是异常（故障类）。因为它是同步的——访问无效页时立即触发，与当前指令直接相关，且必须处理才能继续执行。

中断和异常的区别

详细回答

异常和中断的基本概念

  • 当一条指令执行结束时，需要进行内部异常和外部中断请求的判断。如果存在异常或中断请求，需要进入异常或中断响应过程，主要任务是保存断点和程序状态，识别异常事件或中断源，并进入相应的服务程序进行处理。
  • 异常和中断机制是操作系统获得CPU控制权的唯一方式，当中断或者异常事件发生时，CPU切换至内核态，操作系统得以获得所有特权指令的权限，通过执行操作系统提供的 异常或中断处理程序 来处理异常或中断事件。
  • 异常：是指CPU执行一条指令时，由CPU在其内部检测到的、与正在执行的指令相关的同步事件。
  • 中断：是指一种典型的由外部设备触发的、与当前正在执行的指令无关的异步事件。

异常和中断的分类

  1. 内部异常（Exception） ：
    • 也被称为内部中断 或者 软件中断，异常是CPU执行当前指令产生的事件，是同步发生的，与CPU正在执行的指令密切相关。异常事件可进一步划分为故障（Fault），自陷（Trap），终止（Abort）。
    • 故障（Fault） ：通常是由指令执行引起的异常，如未定义指令、越权指令、段故障、缺页故障、除数为零、浮点溢出、整数溢出等。对于可恢复的故障（如数据缺页），可以由操作系统进行页面调度修复故障，再回到发生缺页故障的指令继续执行。此时的断点是当前指令而不是当前指令的下一条指令。对于不可恢复的故障（如未定义指令、越权指令），由操作系统终止当前进程的执行。
    • 自陷（Trap） ：是一种事先安排的“异常”事件，通过在程序中显式地调用自陷指令来触发异常，用于在用户态调用操作系统内核程序，以请求内核的服务，如系统调用，条件陷阱指令。自陷异常是由自陷指令执行触发的，类似于函数调用，但不存在程序断点（自陷指令不会在用户栈上保存返回地址），执行这些指令就会有条件地或无条件地调用操作系统内核程序并执行，执行完毕后返回自陷指令的下一条指令。
    • 终止（Abort） ：是指使CPU无法继续执行的硬件故障，和具体的指令无关。如机器校验错、总线错误、异常错误、异常处理中再次异常的双错等。此时当前程序无法继续执行，只能由操作系统终止，并由异常服务处理程序来重启系统。
  2. 外部中断（Interrupt） ：
    • 外部中断来自CPU外部，与具体的指令无关，是随机事件，中断是指外部设备向CPU发出的中断请求（如鼠标点击、键盘按键等），中断提供了外设与CPU交流的机制，它也是一种重要的I/O方式。CPU会在当前指令执行完毕后响应中断请求，进而转移到对应的中断处理程序，处理完毕后返回到发生中断的那条指令的下一条指令（因为被中断指令已经执行完毕）。
    • 按中断请求是否可被屏蔽分类，可分为可屏蔽中断 和 非屏蔽中断。
      ① 可屏蔽中断在关中断情况下不会被响应，属于硬件中断。
      ② 非屏蔽中断即使在关中断的情况下也会被响应，属于硬件中断。
    • 按中断事件能否直接提供中断服务地址分类，可分为向量中断 和 非向量中断。
      ① 向量中断是指中断事件可以提供中断服务程序入口地址的中断。
      ② 非向量中断是指中断事件不能直接提供中断服务程序入口地址的中断。
    • 按中断处理过程能否被打断分类，可分为单重中断 和 多重中断。
      ① 单重中断是指CPU执行中断服务程序过程中不能被其他中断请求打断的中断。
      ② 多重中断是指CPU执行中断服务程序过程中可以去响应更高优先级的中断请求的中断，又称为 “中断嵌套”。

异常和中断的处理

  • 异常与中断的处理方式基本一致，当发生中断事件时，CPU接收到中断请求，在当前指令结束时CPU进入中断周期进行中断响应，并在中断响应中引入中断服务程序，由中断服务程序执行后续的中断处理。当然也有例外，例如产生故障异常的指令并没有执行完毕，但必须立即进行中断响应。
  • 中断响应：当CPU检测到未被屏蔽的中断请求信号时，进入中断响应阶段，这一阶段由硬件自动完成。中断响应阶段主要有以下三个步骤：
    1. 关中断：CPU首先要关中断，禁止在进行中断处理时又去响应新的中断，防止保存的断点、程序状态字、现场信息被破坏。
    2. 保存断点和程序状态字：断点就是程序的返回地址，程序状态字是一个进程产生的各种状态信息。断点和程序状态字信息分别保存在特殊的寄存器PC 和 PSW中，CPU会将这两个寄存器内容压栈，以便后续恢复被中断进程的执行流和状态。
    3. 引出中断服务程序：CPU检测到中断信号后对具体中断源进行识别，以此引出对应的中断服务程序。
  • 中断处理：当中断响应引出中断服务程序后，CPU控制权交由操作系统，通过执行操作系统提供的中断服务程序完成中断处理过程。中断处理阶段主要有以下三个步骤：
    1. 保护现场：保存一些通用寄存器信息，防止接下来执行中断处理程序后寄存器内容被破坏。
    2. 执行中断处理程序：也就是具体的中断服务。
    3. 恢复现场：恢复保存的通用寄存器信息，开中断，恢复PC 和 PSW的信息，使得被中断进程完全恢复原来的状态。

知识拓展

程序中断方式流程图 和 中断处理流程图，如下图所示：
image

计算机中中断的过程是什么？

简要回答

中断是计算机系统中由硬件或软件触发的一种异步事件处理机制，它打断CPU当前正在执行的程序，转而执行预先定义好的中断处理程序，处理完毕后再恢复原程序的执行。

中断过程包括中断请求、中断响应、中断处理、中断返回四个阶段，涉及中断控制器、中断向量表、程序状态字、现场保护与恢复等关键组件和操作。

中断机制是实现CPU与外部设备并行工作、提高系统效率、处理紧急事件的基础。

专业回答

计算机中断过程是一个精心设计的硬件与软件协同机制，其本质是CPU对外部或内部事件的异步响应。

整个过程始于中断源的产生，这些源可以是外部硬件设备如键盘敲击、网络包到达、定时器超时，也可以是内部软件条件如除零错误、页故障、系统调用请求。

当中断事件发生时，中断控制器接收并仲裁多个同时发生的中断，根据优先级决定哪个中断被首先服务，然后向CPU发出中断请求信号。

CPU在每条指令执行结束时检查是否有待处理的中断请求，如果中断允许且当前优先级允许响应，则进入中断响应周期：

首先完成当前指令的执行，然后保存关键的处理器状态，包括程序计数器（指向下一条要执行的指令）和程序状态字（包含条件码、中断允许位等标志），接着根据中断类型从中断向量表中获取对应的中断处理程序入口地址，同时自动关闭中断允许（防止嵌套中断干扰）。

随后CPU跳转到中断服务程序开始执行，此时进入中断处理阶段，处理程序首先保存被中断程序的完整现场，然后根据中断原因执行相应的处理逻辑，处理过程中可能需要与设备控制器交互以清除中断源。

处理完成后，中断服务程序恢复之前保存的现场，执行中断返回指令，该指令将恢复之前保存的程序状态字和程序计数器，CPU由此返回到被中断的程序继续执行，整个过程对原程序透明，仿佛从未被打断过。

中断机制的精妙之处在于它通过硬件自动化的状态保存与恢复，以及分层的中断优先级管理，实现了CPU计算与I/O操作的高度重叠，极大提高了系统吞吐率和响应实时性。

  • 中断分类

硬中断：来自硬件设备（IRQ）

软中断：由INT指令触发

异常：执行指令时错误（除零、缺页）

不可屏蔽中断（NMI）：必须立即处理

同步与互斥

线程同步方式

  1. 内核级线程（KLT）的同步方式：
    • 互斥锁（Mutex）：确保同一时间只有一个线程进入临界区。
      ① 实现：通过系统调用（如pthread_mutex_lock）获取锁，竞争失败的线程被阻塞并移出调度队列。
      ② 优化：可配置为自适应自旋（如Linux的futex），减少上下文切换。
      ③ 适用场景：长临界区（如文件操作），避免忙等待浪费CPU。
    • 信号量（Semaphore）：控制资源访问数量，支持计数和二进制模式。
      ① 计数信号量：管理资源池（如数据库连接池）。
      ② 二进制信号量：等价于互斥锁，但支持跨进程（System V信号量）。
    • 条件变量（Condition Variable）：用于线程间状态通知，基于特定条件阻塞或唤醒线程，需搭配互斥锁使用。
      ① 实现：需与互斥锁配合，wait()释放锁并阻塞，signal()唤醒等待线程。
      ② 典型场景：生产者-消费者模型中的缓冲区空/满通知。
    • 读写锁（Read-Write Lock）：允许多读单写，提高读多写少场景的性能。
      ① 实现：读锁共享（允许多线程同时读），写锁独占（仅允许单线程写）。
      ② 适用场景：配置文件读取（多读）与更新（单写）。
    • 自旋锁（Spinlock）：忙等待锁，适用于短临界区。
      ① 实现：线程循环检测锁状态（如while(lock == BUSY);），不主动让出CPU。
      ② 适用场景：多核短临界区（如Linux内核中断处理）。
      ③ 风险：长时间自旋浪费CPU，需配合抢占式调度使用。
  2. 用户级线程（ULT）的同步方式：
    • 原子操作（Atomic）：通过原子指令如CAS（Compare-And-Swap），避免锁开销。
      ① 实现：通过CPU指令（如CAS、LL/SC）直接操作内存，无需锁。
      ② 适用场景：无锁计数器（如atomic.AddInt32）、标志位更新。
      ③ 局限性：仅适用于简单操作，复杂逻辑仍需锁。
    • 协程同步原语：通过调度器协作式切换，如Go的channel，通过消息传递替代共享内存。
      ① 实现：如Go的channel，通过通信传递数据所有权，避免共享内存。
      ② 适用场景：高并发I/O密集型任务（如网络服务器）。
      ② 优势：无锁竞争，依赖调度器协作切换（非抢占式）。
    • 轻量级锁：用户态实现的互斥锁（如Java的偏向锁）。
      ① 实现：先尝试用户态自旋，失败后升级为内核锁（如Java的锁膨胀）。
      ② 优势：减少内核切换次数，平衡性能与公平性。
    • 非阻塞数据结构：用户态实现的互斥锁（如Java的偏向锁）。
      ① 无锁队列：基于原子操作设计无锁队列、栈等数据结构（如Java的ConcurrentLinkedQueue）。
    • 协作式调度同步：
      ① 示例：用户态调度器主动让出CPU（如协程yield），通过事件循环协调任务，避免竞态条件。
      ② 缺点：依赖开发者手动控制切换时机，易引发死锁。

知识拓展

  • 自旋锁（Spinlock）的工作示意图，如下所示：
    image
  • 自旋与非自旋的流程图，如下图所示：
    image
  • 面试官可能的追问1 — 用户级线程（如Go的Goroutine）如何避免内核级同步的开销？：
    • Go通过channel通信替代锁，由调度器在用户态管理协程切换，仅在必要时（如系统调用）才进入内核态。
  • 面试官可能的追问2 — 自旋锁在什么场景下会失效？如何优化？：
    • 失效场景：单核环境（忙等待浪费CPU）、长临界区（自旋时间过长）。
    • 优化：设置最大自旋次数后转为阻塞锁，或结合自适应自旋（动态预测等待时间）。
  • 面试官可能的追问3：自旋锁在内核线程和用户线程中的使用有何差异？
    • 内核线程：可禁用中断确保原子性，防止死锁；支持多核并发自旋。
    • 用户线程：依赖原子指令或futex；单核环境需主动让出CPU（如调用sched_yield）。

典型锁

  1. 互斥锁（Mutex Lock）
    • 功能：互斥锁用于保护临界区，确保同一时间只有一个线程可以访问共享资源。
    • 实现方式：当一个线程获取锁后，其他线程必须等待锁释放后才能获取。
    • 使用场景：适用于需要独占访问共享资源的场景，如修改全局变量、访问共享数据结构等。
    • 与条件变量的配合使用：条件变量通常与互斥锁配合使用，用于实现线程间的条件同步。例如，在生产者-消费者模型中，生产者线程在条件不满足时等待，消费者线程在条件满足时通知生产者线程。
  2. 读写锁（Read-Write Lock）
    • 功能：允许多个读线程同时访问共享资源，但写线程必须独占资源。
    • 实现方式：分为共享锁（读锁）和独占锁（写锁）。读锁可以被多个线程同时持有，写锁只能被一个线程持有。
    • 使用场景：适用于读多写少的场景，如缓存系统、数据库等。
  3. 自旋锁（Spin Lock）
    • 功能：线程在获取锁时，如果锁已被占用，会一直循环检查锁的状态（忙等待），直到锁可用。
    • 实现方式：通过忙等待（Busy-Waiting）实现，避免线程切换的开销。
    • 使用场景：适用于锁占用时间极短的场景，如内核中的临界区保护。

知识拓展

信号量、锁和条件变量的关系？

  1. 信号量：
    • 信号量是一种通用的同步机制，通过计数器来控制对资源的访问，信号量机制可以实现各种同步机制，包括锁。
    • 互斥锁是信号量的一个特例，通常是一个二进制信号量（只能取0或1）。
    • 信号量可以用来实现各种同步问题，如生产者-消费者问题、读者-写者问题等。
  2. 锁：
    • 锁是一个更高级别的概念，通常用于保护临界区，确保同一时间只有一个线程访问共享资源。
    • 互斥锁是锁的一种，通常与信号量相关联，但它本身是锁的一个具体实现。
    • 读写锁和自旋锁也是锁的类型，但它们并不属于信号量的特例。
      • 读写锁允许多个读操作同时进行，但写操作是排他的。
      • 自旋锁是在获取锁失败时循环等待，而不是进入阻塞状态。
  3. 条件变量：
    • 条件变量通常与互斥锁一起使用，用于线程之间的通信。
    • 它允许线程在某个条件不满足时等待，直到其他线程发出通知。
    • 条件变量本身不是信号量，但可以与信号量结合使用来实现更复杂的同步逻辑。

为什么使用锁和条件变量而不是直接使用信号量？

  • 抽象层次：
    • 锁和条件变量提供了更高层次的抽象，使代码更易读、易写和易维护。
    • 信号量更底层，需要开发者手动管理计数器，容易出错。
  • 功能专门化：
    • 锁专门用于保护临界区，条件变量专门用于线程间通信，它们组合使用可以更清晰地表达同步逻辑。
    • 信号量虽然功能强大，但可能需要更多的代码来实现相同的功能，并且容易出现死锁或资源争用的问题。

读写锁和自旋锁是否属于信号量的特例？

  • 虽然“互斥锁”属于信号量的特例，但读写锁和自旋锁不属于信号量的特例；它们是锁的不同类型，用于不同的场景：
    1. 读写锁允许并发读取，但 exclusive 写入。
    2. 自旋锁适用于锁持有时间非常短的场景，避免线程切换的开销。