操作系统(上)

操作系统概述

操作系统(Operating System，OS)是计算机系统中的核心系统软件，用于管理计算机的硬件与软件资源，并控制程序的执行与系统资源的分配，从而为用户和应用程序提供高效、统一且易用的运行环境与接口

操作系统的作用

• OS是系统资源的管理者：负责提供处理机管理、存储器管理、文件管理、设备管理

• OS是用户与计算机硬件之间的接口：它为用户提供三种方式使用计算机：

  • GUI(用户图形界面)
  • 命令接口：包括联机命令接口(交互式命令接口)和 脱机命令接口(通过批处理脚本自动执行命令)
  • 系统调用：提供程序级接口，供应用程序请求操作系统服务
    loading

    

• OS实现了对计算机资源的抽象与拓展：完全没有软件的计算机称为裸机，它只提供硬件接口，难以使用。安装操作系统后，操作系统负责底层硬件的封装与抽象，裸机会被拓展为功能更强、使用更方便的机器，因此通常把覆盖了软件的机器成为扩充机器，又称之为虚拟机

OS的发展过程

• 人工操作方式：早期的计算机系统未配置操作系统，其操作方式人工通过纸带或卡片等物理介质将程序输入计算机，该过程中用户独占全机资源。该操作方式存在人机矛盾：即CPU需等待人工操作完成，CPU与I/O设备速度严重不匹配，资源利用率极低。
• 脱机输入/输出(Off-LineI/O)方式：该方式用来解决人机矛盾及CPU和I/O设备之间速度不匹配的矛盾，其核心特点是外围机提前将纸带上的数据/程序输入到磁带上，方便CPU使用时高速调用。输出时也类似，CPU把数据从内存输出到磁带上，然后在外围机的控制下，将磁带上的数据输出给输出设备。外围机是脱离主机运行的，因此由外围机负责I/O的方式称为脱机输入/输出方式
• 单道批处理系统：该方式引入了监督程序，以实现对作业的连续处理，在监督程序控制下，一批作业能自动地一个接一个连续处理，以减少机器的空闲等待时间。该方式缓解了一定程度的人机速度矛盾，资源利用率有所提升。但缺点是内存中仅能有一道程序运行，程序执行时若发起I/O操作，CPU必须等待，资源利用仍不充分
• 多道批处理系统：允许多道程序并发执行，共享计算机资源，如：程序A等待I/O操作时，调度程序可以调度程序B在CPU中运行，使多道程序交替执行。这样大幅提升了资源利用率，CPU和其他资源更能保持“忙碌”状态，系统吞吐量增大。
  其缺点是：由于作业要排队依次处理，因此作业平均周转时间长。且一旦将作业提交给系统后，用户无法与作业交互，不方便修改和调试程序，即没有人机交互功能
• 分时系统：批处理系统无法提供人机交互功能，为解决这一问题，分时系统彻底改变了系统的运行方式：

  • 作业进入内存：为提供人机交互功能，用户的作业必须驻留内存中
  • 采用轮转运行方式：引入时间片概念，为避免一个作业长期独占处理机，规定每个作业只能运行一个时间片，然后由调度系统调度下一个作业运行，这样可以使每个用户在一个不长的时间内，都能及时与自己的作业进行交互。
    分时系统的优点是用户请求可以被即时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。缺点是不能优先处理一些紧急任务。操作系统对各个用户/作业都是完全公平的，循环地为每个用户/作业服务一个时间片，不区分任务的紧急性。

• 实时系统：能够及时响应外部事件的请求，并在规定的严格时间内完成对事件的处理。相比分时系统，其首要目标是可靠性，能优先处理紧急任务，而非交互性或吞吐量。它可以分为：

  • 硬实时系统：必须在绝对严格的规定时间内完成关键任务，否则可能造成灾难性后果（如工业控制、飞行器自动驾驶）
  • 软实时系统：允许偶尔超时，但超时会导致服务性能下降（如信息查询系统、多媒体播放）

微机操作系统的发展

微型机上的操作系统的发展：

• 单用户单任务操作系统：只允许一个用户上机，且只允许用户程序作为一个任务运行，主要配置在8位和16位微机上，典型代表有：微软公司开发安装于IBM-PC的MS-DOS
• 单用户多任务操作系统：只允许一个用户上机，但允许用户把程序分为若干个任务，使它们并发执行，常用于32位微机，典型代表有微软公司的Windows95
• 多用户多任务操作系统：允许多个用户通过各自的终端，使用同一台机器，共享主机系统中的各种资源，而每个用户程序又可进一步分为几个任务，使它们能并发执行，典型代表有基于Windows NT内核的Windows 2000后续操作系统，GNU/Linux OS等

操作系统的基本特性

操作系统的四个基本特征：并发(Concurrence)、共享(Sharing)、虚拟(Virtual)、异步(Asynchronism)。

其中并发和共享是多用户(多任务)OS的两个最基本的特征，它们互为存在条件。如果失去并发性，系统只有一个进程在运行，系统所有资源都属于该进程，就不存在资源共享问题。如果失去共享性，多个进程不能共享资源，则无法实现并发

并发(Concurrence)

• 并发(Concurrence)：指两个或多个事件在同一时间间隔内发生。这些事件在宏观上是同时发生的，微观上是交替发生的
• 并行：指两个或多个事件在同一时刻发生

操作系统的并发性指操作系统中同时运行这多个程序：在多道程序环境下，并发性是指在一段时间内宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻却仅能有一道程序执行，故微观上这些程序只能是分时地交替执行。如，在1秒钟时间内，0-15 ms程序A运行;15-30ms程序B运行;30-45 ms程序C运行:45-60ms 程序D运行，因此可以说，在1秒钟时间间隔内，宏观上有四道程序在同时运行，但微观上，程序A、B、C、D是分时地交替执行的

共享(Sharing)

共享指的是资源共享(又称为资源复用)，是指系统中的资源可供内存中多个并发执行的进程共同使用(这里限定了时间：进程在内存期间，也限定了地点：内存)。目前主要实现资源共享的方式有如下两种:

• 互斥共享方式：一段时间内，只允许一个进程访问该资源。这些只能以互斥共享方式访问的资源，称为临界资源(或独占资源)，比如：摄像头、打印机、栈、变量等
• 同时共享方式：系允许在一段时间内由多个进程“同时”对它们进行访问。这里的“同时”，在单处理机环境下是宏观意义上的，而在微观上，这些进程对该资源的访问是交替进行的。这样的资源有：磁盘设备、音响设备等

虚拟(Virtual)

虚拟指通过虚拟技术，将一个物理实体变为若干个逻辑上的对应物。这里物理实体是实际存在的(如：硬件/系统资源)，而逻辑上的对应物指用户感觉到的东西(如通过虚拟内存技术让用户视角看到的逻辑主存比实际内存大小更大)，OS的虚拟特性表现：

• 利用时分复用技术，使得设备同时为多个进程/用户提供服务，如：

  • 虚拟处理器技术：在单处理机系统中，处理机在不同时间片中为不同的进程提供服务，使得每个进程似乎都独占了一个处理器，即将一台物理上的处理机虚拟为多台逻辑上的处理机。
  • 虚拟设备技术：通过时分复用，使得一台物理I/O设备虚拟为多台逻辑I/O设备，同时为多个用户/进程服务

• 空分复用技术，在OS中指利用存储器的空闲空间分区域存放和运行其它的多道程序，以此来提高内存的利用率。如：虚拟内存技术中，要将一个100MB的程序，运行在30MB的内存空间中。可以每次只把用户程序的一部分调入内存运行，运行完成后将该部分换出，再换入另一部分到内存中运行，通过这样的置换功能，便实现了用户程序的各个部分分时地进入内存运行，在逻辑上扩大了存储器容量

异步(Asynchronism)

异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。通常而言，操作系统需要提供“进程同步机制”以解决开发进程的异步性带来的问题

操作系统的主要功能

处理机管理功能

在传统的多道程序系统中，处理机的分配和运行都是以进程为基本单位的，处理机管理的功能包括:

• 进程控制:包括为所要处理的作业创建一个或多个进程；在进程运行结束时，撤销(终止)进程并回收该进程占用的资源；为进程创建若干线程，以提高系统的并发性；以及控制进程在运行过程中的状态转换
• 进程同步:协调各进程有序运行，常用的协调方式有两种：

  • 进程互斥方式：各进程在对临界资源进行访问时，通过锁等机制协调各进程互斥访问。
  • 进程同步方式：对于需要相互合作来完成共同任务的诸进程，通过同步机制(如：信号量机制)对它们的执行次序加以协调

• 进程通信:当有一组相互合作的进程需要完成共同任务时，它们之间通常需要交换信息，因此进程通信的任务是实现相互合作进程之间的信息交换。如：当这些进程处于同一计算机系统时，它们之间可以采用直接通信方式，即由源进程利用发送命令直接将消息(message)挂到目标进程的消息队列上，以后由目标进程利用接收命今从其消息队列中取出消息
• 调度：调度包括作业调度和进程调度两步：

  • 作业调度：其任务是从后备队列中按照某种算法选择出若干个作业，为它们分配运行所需的资源，在将这些作业调入内存后，分别为它们建立进程，使它们都成为可能获得处理机的就绪进程，并将它们插入就绪队列中
  • 进程调度：其任务是从进程就绪队列中按照一定的算法选出一个进程，将处理机分配给它，并为它设置运行现场，使其投入执行

存储器管理功能

• 内存分配：主要任务是：

  • 为每道程序分配内存
  • 提高存储器利用率，尽量减少内存碎片
  • 允许已经分配内存的程序申请附加内存，以适应程序和数据动态增长需要
  • OS分配内存通常采用两种方式：

    • 静态分配方式：每个作业的内存空间是在作业装入时确定的，在作业装入后的整个运行期间不允许该作业再申请新的内存空间，也不允许作业在内存中“移动”。
    • 动态分配方式：每个作业所要求的基本内存空间虽然也是在装入时确定的，但允许作业在运行过程中继续申请新的附加内存空间，以适应程序和数据的动态增长，也允许作业在内存中“移动”。

• 内存保护：其主要任务是：确保每道用户程序都仅在自己的内存空间内运行，彼此互不干扰。绝不允许用户程序访问操作系统的程序和数据，也不允许用户程序转移到非共享的其它用户程序中去执行。为实现该目标，OS通常会设置内存保护机制，如：设置两个界限寄存器，分别用于存放正在执行程序的上界和下界。程序运行时，系统对每条指令所要访问的地址进行检查，如果发生越界，便发出越界中断请求，以停止该程序的执行。
• 地址映射：在多道程序环境下，由于每道程序经编译和链接后所形成的可装入程序其地址都是从0开始的，但不可能将它们从“0”地址(物理)开始装入内存，致使(各程序段的)地址空间内的逻辑地址与其在内存空间中的物理地址并不相一致。为保证程序能正确运行，存储器管理必须提供地址映射功能，即能够将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址。该功能应在硬件的支持下完成。
• 内存扩充：通过虚拟存储技术，从逻辑上扩充内存容量，以便让更多的用户程序能并发运行。内存扩充机制的实现

  • 请求调入功能：系统允许在仅装入部分用户程序和数据的情况下，便能启动该程序运行。在程序运行过程中，若发现要继续运行时所需的程序和数据尚未装入内存，可向OS发出请求，由OS从磁盘中将所需部分调入内存，以便继续运行。如：将100MB的程序运行在30MB的存储空间上，可以每次只把用户程序的一部分调入内存运行，运行完成后换出，再换入另外一部分。
  • 置换功能(交换空间/换页)：若发现在内存中已无足够的空间来装入需要调入的程序和数据时，系统应能将内存中的一部分暂时不用的程序和数据调至硬盘上，以腾出内存空间，然后再将所需调入的部分装入内存。

设备管理功能

设备管理的主要任务，是完成用户提出的 I/O 请求，提高CPU、I/O 设备利用率，并为用户屏蔽物理设备的复杂性，设备管理通常有以下功能：

• 缓冲管理：在CPU与I/O设备之间引入缓冲，缓解CPU与I/O设备间速度不匹配的矛盾，常见的缓冲机制有：单缓冲、双缓冲、公用缓冲池机制等
• 设备分配：根据用户请求和系统现有资源，进行合理分配，为方便设备分配，系统中通常设置有：设备控制表（记录设备类型、状态等信息）、控制器控制表（记录控制器状态和连接设备）等
• 设备处理（设备驱动）：由设备驱动程序完成 CPU 与设备控制器之间的通信，包括CPU发出I/O命令，让I/O设备完成指定I/O操作；I/O设备发出中断请求，CPU进行响应和处理

文件管理功能

• 文件存储空间管理：负责对磁盘等外存空间进行组织、分配与回收
• 目录管理：主要任务是为每个文件建立一个目录项，目录项包括文件名、文件属性、文件在磁盘上的物理位置等，并提供按文件名存取、文件共享、目录查询等功能
• 文件读写：根据用户请求，从外存中读取数据，或将数据写入外存。包括根据文件名检索文件目录，从中获得文件在外存中的位置，帮用户管理文件读/写指针，进行读/写操作等
• 文件保护：在文件系统中提供存取控制功能，以防止文件被非法窃取和破坏

OS与用户之间的接口

操作系统提供了用户与操作系统之间的接口，包括两大类：

• 用户接口：有联机用户接口(用户通过终端/控制台执行命令)、脱机用户接口(执行批处理作业，如各类脚本)、图形用户接口(GUI)三种
• 程序接口：用于用户程序在执行过程中访问系统资源，是用户程序取得操作系统服务的唯一途径。它由一组系统调用组成的，每一个系统调用都是一个能完成特定功能的子程序。早期的系统调用由汇编语言提供，在高级语言以及C语言中，提供了与各系统调用一一对应的库函数，应用程序可通过调用对应的库函数来使用系统调用

现代操作系统的新功能

• 系统安全：包括身份鉴别、密码技术、访问控制、反病毒等
• 网络服务：提供电子邮件服务、Web服务等，因此操作系统需要拥有面向网络的功能，包括

  • 网络通信：用于在源主机和目标主机之间，无差错的数据传输，包括链路建立和拆除、传输控制、差错控制、流量控制等
  • 资源管理：管理网络中的共享资源，如：共享的硬盘、打印机等
  • 应用互操作：在由不同网络组成的互联网络中，需要能实现不同网络用户、数据之间的信息互通和兼容，如：访问不同网络中的文件系统和数据库系统等

• 支持多媒体：对多媒体进程的控制、调度和多媒体文件的存储等

OS用于管理的数据结构

操作系统在管理系统资源时，会为每类资源设置并管理一个数据结构，用于表征其实体，OS管理的数据结构一般分为以下四类：

• 内存表（Memory Table）：用于记录主存（RAM）使用情况，现代操作系统中，内存表实际上由多个表共同实现，如：页表、空闲页链表、页框数据库、虚拟内存管理等，它们共同组成内存管理系统。内存表中通常记录了内存块或页框编号、起始地址、大小、是否为共享页等信息
• 进程表（Process Table）：负责保存系统中所有进程的信息，进程表实际上就是所有进程控制块PCB的集合。通常记录了进程PID、进程状态(运行、就绪、阻塞等)、优先级等信息
• 文件表（File Table）：用于管理系统中已经打开的文件(注意它并不记录硬盘所有文件)，文件表一般记录inode（Linux）、文件大小、当前读写位置、文件权限等信息
• 设备表（Device Table）：用于管理计算机中的各种硬件设备，设备表通常保存设备编号、设备类型、当前状态（Busy/Idle）、驱动程序入口、中断号、DMA信息等内容

操作系统结构

随着OS的规模越来越大，OS的结构经历了以下阶段

无结构操作系统

早期的操作系统是众多的一组过程的集合，每个过程可以任意地相互调用其它过程，操作系统内部既复杂又混乱，因此这种OS是无结构的

模块化结构

OS按其功能划分为若干个具有一定独立性的模块，如：进程管理模块、存储器管理模块、I/O设备管理模块等，并规定好各模块间的接口，使各模块之间能通过接口实现交互。每个模块又可划分为子模块，如：把进程管理模块又分为进程控制、进程同步等子模块，同样也规定好各子模块之间的接口。

优点：

• 模块间逻辑清晰易于维护，确定模块接口后即可多模块同时开发
• 支持动态加载新的内核模块(如:安装设备驱动程序、安装新的文件系统模块到内核)，增强OS的可适应性
• 任何模块都可以直接调用其他模块，无需采用消息传递等方式进行通信，效率高

缺点：

• 模块间的接口定义很难做到合理、实用
• 模块间相互依赖，更难调试和验证

分层结构

分层结构是对模块化结构的进一步优化，其核心原则是：将操作系统划分为若干层，每一层都建立在下一层的基础上，仅能调用其直接下层的功能，不能跨层调用。底层通常封装硬件细节，高层则提供抽象的用户接口

优点：

• 易保证系统的正确性：自下而上的设计方式使所有设计中的决定都是有序的，或者说是建立在较为可靠的基础上的，这样比较容易保证整个系统的正确性。
• 易扩充和易维护性：在系统中增加、修改或替换一个层次中的模块或整个层次时，只要不改变相应层次间的接口，就不会影响其他层次，易于维护和扩充

缺点：系统效率降低。由于层次结构是分层单向依赖的，必须在每层之间都建立层次间的通信机制，OS每执行一个功能，通常要自上而下地穿越多个层次，这会增加系统的通信开销，从而导致系统效率的降低

微内核OS结构

核心思想是极端精简内核功能，仅保留最核心、最基础的功能放在内核态运行，如有限的进程调度与通信、虚拟内存低级管理、基本I/O中断处理等。而传统的文件系统、完整设备驱动、网络协议栈等功能，全部移至用户态，以独立服务进程的形式运行。系统功能通过消息传递机制进行交互，而不是直接函数调用。

优点：

• 安全性与可靠性高：由于大部分服务运行在用户态，即使某个服务崩溃，也不会直接影响内核，从而提高系统整体稳定性。
• 可扩展性好：内核小巧，系统更易扩展和维护，且可以方便地替换或升级单个服务模块，而不影响整个内核。
• 可移植性强：内核只包含最核心、最基础的功能，通常于硬件平台无关，把操作系统移植到另一个硬件平台所需要作的修改较小，这种结构也更适合分布式和嵌入式系统设计

缺点：

• 性能低，执行程序需要频繁的切换用户态/核心态，，会引入额外的运行开销
• 用户态下的各功能模块不可以直接相互调用，只能通过内核的”消息传递”来间接通信

宏内核OS结构

其基本思想是将操作系统的大部分功能模块集中放置在内核空间中统一运行。在这种结构中，进程管理、存储管理、文件系统、设备驱动以及网络协议等核心功能都作为内核的一部分存在，运行在同一特权级别下。模块之间通过函数调用的方式直接通信，共享同一内核地址空间。从实现角度看，宏内核更接近一个“功能高度集成的大型程序”，所有核心服务都紧密耦合在内核中

优点：

• 大多数模块位于内核中，避免了用户态与内核态之间频繁切换，也不需要额外的进程间通信机制，其执行效率较高
• 在工程实现上，宏内核的设计相对直接，符合传统单体程序的设计思路，因此开发成本较低，生态成熟

缺点：

• 可靠性与维护性较差：大量功能运行在内核态，一旦某个模块（例如驱动程序）发生错误，可能会直接导致整个系统崩溃
• 随着功能增加，内核规模不断扩大，代码复杂度显著提升，模块之间耦合增强，不利于维护与扩展

操作系统的引导

计算机开机过程本质上是一个从固件（Firmware）逐步加载操作系统内核（Kernel）的过程。由于CPU上电后并不知道操作系统在哪里，因此需要通过主板固件、磁盘引导结构以及引导加载程序（Bootloader）逐级完成启动

BIOS

BIOS全称为Basic Input/Output System（基本输入输出系统），是传统计算机主板上的固件程序，存储在主板上的 ROM/Flash 芯片中，它主要负责：上电自检、初始化硬件设备、查找启动设备、加载硬盘中的引导程序。BIOS 引导有以下特点：

• 运行在 16 位实模式（Real Mode）
• 地址空间有限（约 1MB）
• 使用 MBR 引导
• MBR分区表决定了只支持最大2.2TB硬盘寻址，最多只能分4个主分区
• 启动速度较慢

硬盘结构

loading

• 主引导记录MBR(Master Boot Record)：位于硬盘的0号逻辑扇区（LBA 0），共512字节，它负责管理整个硬盘的信息结构，且不会显示在分区记录里(如：windows的磁盘管理里)，它由三部分组成：

  • 引导程序(Boot Code)：占用446字节，BIOS启动时，固件会直接加载并执行这446字节的代码，然后查找活动分区并加载其PBR
  • 分区表(Partition Table)：64字节，用来记录分区信息，每个分区表项占用16个字节，因此最多只支持4个主分区项(但可在某个主分区内部再次分区突破该限制)。分区表项中用于记录分区大小的字段占用4个字节，因此最大支持 (2 ³²-1)个扇区 x 512字节/扇区 = 2.2 TB硬盘寻址
  • 结束标志(Signature)：占用2字节，固定为值为0x55AA

• 活动分区：MBR中的分区表会记录每个主分区的状态，当分区表项中的活动标志位值为 0x80 时表示该分区为活动分区。当硬盘上多个主分区都安装了不同的操作系统时，BIOS或MBR引导程序只会寻找并执行被标记为活动分区的PBR，其他主分区的PBR不会被引导，这确保了多系统环境下的启动唯一性。

  • 分区引导记录PBR(Partition Boot Record)：也叫卷引导记录VBR，位于每一个分区的第一个扇区，MBR引导程序找到活动分区后，就跳转执行PBR。PBR的代码负责加载该分区里真正的操作系统加载器，如Windows的 Boot Manager 或Linux的 GRUB。在多系统环境下，Windows Boot Manager或Linux GRUB会通过读取配置文件或扫描其他分区，来找到其他主分区中安装的系统，用户选择后，通过链式加载跳转到用户所选择的启动系统
  • 操作系统：存放着完整的操作系统文件（如内核、驱动、系统库等）
  • 其他数据：其余可用空间

• 恢复分区：该分区用于存放系统恢复环境、恢复工具以及厂商提供的恢复镜像等数据，如： Windows10/11的恢复分区(大约600MB左右)，macOS的APFS卷，Linux系统也有类似的恢复机制，但通常不会在硬盘上分出一个独立的分区
• 其他分区：如D盘/E盘或sda2/sdb1等

BIOS启动流程

• BIOS完成硬件初始化
• 查找启动硬盘(可通过BIOS设置修改)
• 读取硬盘的第一个扇区（MBR）
• 将MBR代码加载到内存并执行，由此识别出存在哪些分区，并找到活动分区
• 读取活动分区PBR
• 从PBR中加载操作系统引导程序Bootloader
• 最终由Bootloader负责选择系统、加载内核

UEFI

UEFI（Unified Extensible Firmware Interface，统一可扩展固件接口）是现代计算机取代 BIOS 的新型固件标准，该标准由操作系统和硬件厂商共同制定，提供比BIOS更加完整的启动环境，UEFI 引导有以下特点：

• 运行在32位或64位保护模式下
• 地址空间巨大（理论可达 16EB），因此支持加载大型驱动和复杂图形界面
• 使用GPT（GUID 分区表配合ESP系统分区引导
• GPT分区表最大支持18EB硬盘寻址，理论支持无限个主分区
• 支持安全启动（Secure Boot），能验证操作系统引导加载程序的数字签名，防止Rootkit和未授权的恶意系统启动
• 自检过程大为简化，支持并行硬件初始化，系统启动时间显著缩短

硬盘结构

loading

• Protective MBR（保护性MBR）：为了兼容旧BIOS工具，硬盘第0扇区仍然保留一个类似MBR的结构，它不再作为启动MBR使用，而是为了防止旧工具误认为磁盘为空，以及防止旧分区工具覆盖GPT，它通常只有一个特殊分区条目，类型为0xEE，范围覆盖整个GPT磁盘
• GPT：用于替代MBR，存储硬盘及其分区信息，它包含两部分：

  • GPT头(GPT Header)：位于第1扇区(LBA 1)，用于保存硬盘的GPT签名、分区表位置、分区数量、分区表大小、CRC校验值、备份GPT位置
  • GPT分区表(GPT Partition Entry Array)：位于LBA 2-LBA 33，GPT的每个分区表项占用了128个字节，并包含以下内容：

    • 使用8个字节来记录分区的起始逻辑块地址和结束逻辑块地址，使得GPT理论支持的最大分区容量达到了9.4 ZB，彻底解决了MBR只能寻址2.2TB的瓶颈。
    • 分区表数组理论上可以容纳任意数量的分区项，但通常情况下，GPT分区表只占用LBA 2-LBA 33的位置，因此默认限制为128个主分区，突破MBR最多4个主分区的约束
    • 通常情况下，GPT会在硬盘的末尾保存一份完整的分区表备份（即备份GPT Header和备份分区表数组），当硬盘起始位置的GPT主表因意外损坏或丢失时，系统可以自动从硬盘末尾的备份中恢复分区结构，具体备份位置取决于GPT头中的信息

• ESP（EFI System Partition，EFI系统分区）：UEFI启动的核心，ESP是一个FAT16或FAT32格式的特殊分区（Windows中通常标记为EFI分区，Linux中通常挂载于/boot/efi目录下），用于存放以下内容：

  • UEFI引导加载程序(Bootloader)，如：Windows Boot Manager的bootmgfw.efi或Linux GRUB的grubx64.efi
  • 启动配置文件：如：Windows环境下的\EFI\Microsoft\Boot\BCD（Boot Configuration Data）文件，或Linux环境下的/boot/efi/../grub.cfg文件
  • 多语言菜单资源文件（.mui）、UEFI驱动（.efi驱动文件）以及硬件诊断工具（如memtest.efi）等
    UEFI固件启动时，会依据主板NVRAM中记录的引导项，读取ESP分区中对应路径下的.efi文件，将其加载至内存并执行，进而通过该引导加载程序启动操作系统内核

• 其他分区：如用于数据存储的C盘/D盘或sda1/sda2等

UEFI启动流程

• UEFI固件执行硬件初始化，完成 POST（加电自检）
• UEFI 固件读取主板 NVRAM 中存储的启动顺序列表（Boot Order），按优先级依次尝试每个启动设备
• UEFI 固件识别到启动硬盘后，会检查硬盘分区表中是否存在 ESP（EFI 系统分区），该分区以特定的 GPT 分区类型 GUID 标识
• 在 ESP分区中查找 .efi 引导文件，将其加载到内存，并将控制权完全移交给该引导加载程序
• 引导加载程序查找ESP分区中的配置文件，如：Windows环境下的BCD文件，或Linux环境下的grub.cfg文件
• 引导加载程序根据配置文件中的参数，找到操作系统内核所在分区和路径，加载内核文件
• 引导加载程序将控制权移交给操作系统内核，内核接管硬件并继续完成系统的后续启动过程（加载驱动程序、挂载根文件系统、启动用户态服务等）

进程的描述与控制

进程的描述

进程的定义

进程(Process)：进程是程序的一次执行过程，是系统进行资源分配的基本单位。程序本身是静态的，是存储在磁盘中的一组指令和数据；而进程是程序运行时的动态实体（国外教材：A process is a program in execution，进程是正在执行的程序），包含了程序执行过程中所需的资源和运行状态。

进程实体：又称为进程映像，是进程在操作系统中的具体组成部分，由程序段、数据段、PCB三部分组成。进程是动态的，进程实体是静态的，它反映了进程在某一时刻的状态(如：进程的所拥有的系统资源——CPU寄存器、各标志位等资源的状态)，一般情况下，进程实体就简称为进程，进程实体所包含的内容：

• 程序段：程序的机器指令，进程需要执行的代码部分
• 数据段：程序运行过程中产生的数据，包括：全局变量、静态变量、堆区数据、用户输入的数据等
• 进程控制块 PCB：存放进程的管理和控制信息

进程控制块PCB

进程控制块 PCB（Process Control Block）：是系统为了管理进程而设置的一个专门的数据结构，用于记录进程的属性和状态，PCB是进程存在的唯一标志，系统通过PCB来感知和管理进程。创建进程，实质上是创建进程的PCB；撤销进程，实质上是撤销进程的PCB，PCB 中主要包含以下几类信息：

• 进程标识信息：用于唯一标识一个进程，包括进程标识符PID（Process ID）、父进程标识符PPID、用户标识符 UID
• 处理机状态信息：用于进程切换时保存和恢复 CPU 状态，包括程序计数器PC(保存下一条将执行指令的地址)，各类寄存器的值、堆栈指针、
• 进程调度信息：用于操作系统进行进程调度，包括：进程状态、进程优先级、调度队列指针、等待时间等
• 资源分配信息：记录进程拥有和使用的系统资源，包括内存分配信息、打开的文件、使用的 I/O 设备、信号量等
• 进程通信信息：于进程之间交换信息，包括消息队列、信号、共享内存相关信息

进程控制块PCB的组织方式

在一个系统中，通常可能拥有数十个、数百个乃至数千个PCB，它们的管理与组织方式有以下三种：

• 线性方式：即将系统中所有的PCB都组织在一张线性表中，将该表的首址存放在内存的一个专用区域中。该方式实现简单、开销小，但每次查找时都需要扫描整张表，因此适合进程数目不多的系统
• 链接方式：即把具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列。如：就绪队列、阻塞队列、空白队列等。对就绪队列而言，往往按进程的优先级将PCB从高到低进行排列，将优先级高的进程PCB排在队列的前面。同样，也可把处于阻塞状态进程的PCB根据其阻塞原因的不同，排成多个阻塞队列
• 索引方式：根据所有进程状态的不同，建立几张索引表，例如，就绪索引表、阻塞索引表等，并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表的表目中，记录具有相应状态的某个PCB在PCB表中的地址

进程的特征

• 动态性：进程由创建、运行、阻塞、结束等生命周期阶段组成，是动态变化的。
• 并发性：多个进程可以同时存在，并发执行。
• 独立性：进程是系统进行资源分配和调度的基本单位，每个进程拥有独立的地址空间和资源，能独立地接受调度
• 异步性：进程按照各自不可预知的速度推进，执行顺序可能发生变化。

进程的层次结构

在操作系统中，一个进程可以创建另一个进程，通常把创建进程的进程称为父进程（Parent Process），而把被创建的进程称为子进程（Child Process），子进程可继续创建更多的孙进程，因此多个进程之间可以形成层次关系。不同操作系统对于这种进程关系采用了不同的设计方式，其中 UNIX/Linux 强调进程之间的父子关系，而 Windows 则采用基于句柄的进程管理方式。

• UNIX/Linux：在 UNIX/Linux 系统中，进程之间存在明确的父子关系，子进程可以继承父进程所拥有的资源，例如，继承父进程打开的文件，继承父进程所分配到的缓冲区等。操作系统会在进程控制块（PCB，Linux 中对应 task_struct）中维护进程之间的家族关系，包括当前进程的父进程信息以及子进程列表

• Windows中不存在任何进程层次结构的概念，所有的进程都具有相同的地位。当一个进程创建另一个进程时，创建进程会获得一个指向新进程对象的句柄（Handle）。句柄本质上是一个指向内核对象的引用，有目标进程句柄的进程，可以根据权限对目标进程进行控制，例如等待目标进程结束、获取目标进程信息、终止目标进程等。默认情况下，Windows的子进程不会自动继承父进程的系统资源，而是需要在创建进程时显式指定资源继承。

进程的状态与转换

多个进程在并发执行时共享系统资源，致使它们在运行过程中呈现间断性的运行规律，所以进程在其生命周期内可能具有多种状态

进程的状态

进程有三个基本状态，以及两个常用状态：

• 创建状态：进程的创建是个复杂的过程，需要一定的流程，因此进程刚刚被创建，但还没有完成初始化的状态称为创建状态。当处于创建状态的进程，获得了所需的资源以及对其PCB的初始化工作完成后，便可转为就绪状态，进程会被插入到就绪队列中。
• 就绪状态（Ready）：指进程已经具备运行条件，但由于 CPU 资源不足，暂时无法运行。该状态下，进程已经获取除CPU以外的所有必要资源，只需要获得CPU，便可立即执行。多个就绪状态的进程，会形成就绪队列
• 运行状态（Running）：进程已经获得 CPU，正在执行程序指令。在单处理机系统中，只有一个进程处于执行状态，而在多处理机系统中，可能有多个进程处于执行状态。
• 阻塞状态（Blocked）：进程因为等待某个事件发生（如：等待I/O操作完成、等待锁资源释放等）而暂时无法运行，又称为等待状态或封锁状态。多个阻塞状态的进程，会形成阻塞队列(可能有多个阻塞队列)
• 终止状态：进程执行结束，操作系统等待/正在回收PCB空间等资源。进程执行结束的原因可能是程序正常执行完毕，也可能是出现异常被操作系统终止。处于终止状态的进程不能再被执行，但操作系统中依旧会保留一个记录（可能包含进程保留状态码和数据），供其他进程收集。一旦信息收集结束，操作系统将删除该进程，并回收PCB等资源。

挂起状态

除了三种基本状态外，进程还可以处于挂起状态，它可以与就绪、阻塞结合形成挂起就绪（Ready Suspend）和挂起阻塞（Blocked Suspend）等状态。

进程挂起（Suspend）是指操作系统暂时停止某个进程的执行，并将其从正常的调度体系中移除，使其在一段时间内不会获得CPU运行机会。被挂起的进程仍然存在，其PCB等管理信息通常保留在内存中，操作系统可以在适当的时候重新恢复其运行。进程被挂起通常伴随着以下事件：

• 进程被冻结（Freeze），其线程停止运行
• 如果内存资源不足，操作系统可能将该进程的部分或全部地址空间换出（Swap Out）到外存交换区，但挂起并于意味着进程一定会被换出到虚拟内存中
• Android等支持内存压缩的系统，可能优先压缩该进程占用的内存页面

引起进程挂起的事件：

• 用户操作：用户根据需要暂停进程运行，如：Linux中通过ctrl+Z使进程挂起并转入后台，或通过kill发送SIGTSTP信号
• 父进程请求：父进程主动挂起某个子进程
• 操作系统因系统资源紧张(如内存不足)等原因挂起进程，通常阻塞状态的进程更容易被挂起，该过程通常伴随着进程资源被Swapping-out到外存
• 操作系统进入睡眠、休眠等电源管理状态，如：合上笔记本盖子

挂起就绪/挂起阻塞

挂起(Suspend)与就绪(Ready)/阻塞(Blocked)是独立的状态，挂起通常由用户或操作系统发起，而阻塞通常由进程自行发起。处于就绪或阻塞状态的进程也可以被挂起，变成挂起就绪(Ready/Suspend)和挂起阻塞(Blocked/Suspend)，正在执行的进程也可以被挂起，在暂停执行后会变成Ready/Suspend，而不存在Running/Suspend。挂起就绪与挂起阻塞可以相互切换：

• 处于挂起阻塞的进程，就算其内存空间被换出到了硬盘，由于其PCB依旧存活于内存中，因此当它的请求资源到达系统缓冲区，进程也可以从挂起阻塞切换到挂起就绪。
• 新创建的进程，如果内存资源不足，有可能一创建完就变成挂起就绪状态

三种状态的转换

• 就绪态 → 运行态：进程被调度程序选中，获得 CPU，程序指令可以开始执行
• 运行态 → 就绪态：进程失去 CPU（如：时间片用完或更高优先级进程到达，处理机被抢占），但仍具备运行条件，
• 运行态 → 阻塞态：进程主动等待某个事件(如：等待I/O数据到达)，因此进入阻塞态是进程主动请求的
• 阻塞态 → 就绪态：进程等待的事件已经发生，但还没有获得 CPU，因此进入就绪态。进程不能直接从阻塞态转换为运行态

loading

七种状态转换

loading

进程控制

进程控制是进程管理中最基本的功能，主要包括创建新进程、终止进程、实现进程状态转换等功能。进程控制需要修改操作系统中的核心数据结构，如：PCB、就绪队列、阻塞队列、资源分配表等，这些数据结构属于系统共享资源，如果修改过程中被打断，可能导致系统状态不一致，因此进程控制一般是由 OS 内核中的原语操作来实现。

原语操作

原语（Primitive）是由若干条机器指令组成的一组基本、不可分割的操作，其执行过程必须具有不可分割性，即具备原子性。原语是原子操作，操作系统内核包含很多原语，如：链表操作原语、进程同步原语等。在单处理器早期系统中，原语通过关中断/开中断的方式来防止执行过程中发生进程切换；现代多处理器系统则主要依靠CPU提供的原子指令(TS、Swap等指令)，结合自旋锁、互斥锁等同步机制实现。

原子操作（Atomic Operation）是指一个操作中的所有动作要么全做，要么全不做，它是一个不可分割的基本单位，其他操作无法观察到其中间状态。

创建进程

当系统需要创建新进程时，OS会调用创建原语按以下步骤创建新进程：

• 申请空白PCB：为新进程分配一个唯一的进程标识符（PID）和空白的 PCB 结构
• 为新进程分配所需资源，如：内存、文件、I/O设备、CPU时间等
• 初始化PCB：将分配的PID、资源信息写入PCB，初始化处理机状态，并将进程状态设置为就绪状态
• 将新进程插入就绪队列

引起进程创建的事件：

• 用户登录：分时系统中，用户登录成功，系统会建立为其建立一个新的进程
• 作业调度：多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程
• 提供服务：用户向操作系统提出某些请求时，会新建一个进程处理该请求
• 应用请求：由用户进程主动请求创建一个子进程

终止进程

终止原语的步骤：

• 从PCB集合中找到终止进程的PCB
• 若进程正在运行，立即终止进程的执行，剥夺CPU
• 终止其所有子进程
• 将该进程拥有的所有资源归还给父进程或操作系统
• 将终止进程的PCB从所在队列移出，等待其他程序收集信息，最终删除PCB

引起进程终止的事件：

• 正常结束：进程任务完成，正常退出
• 异常结束：进程在运行过程中发生了异常，致使进程无法继续运行，常见的异常事件有：程序越界(越出程序所允许访问的存储区)，进程访问不允许的资源，进程执行非法指令，运行超时等
• 外界干预：用户或操作系统干预，父进程终止等

进程阻塞与唤醒

当出现阻塞事件，进程调用阻塞原语(block)自行切换到阻塞状态，其执行步骤：

• 找到要阻塞的进程对应的PCB
• 保护进程运行现场，将PCB状态信息设置为“阻塞态”，暂时停止进程运行
• 将PCB插入相应事件的等待队列

引起进程阻塞的事件：

• 进程无新工作可执行
• 需要等待系统分配某种资源
• 需要等待相互合作的其他进程完成工作

当阻塞进程期待的事件发生，有关进程调用唤醒原语(wakeup)唤醒阻塞的进程，其执行步骤为：

• 在事件等待队列中找到PCB
• 将进程从等待队列移除，设置进程为就绪态
• 将进程插入就绪队列，等待被调度
  引起进程唤醒的事件：进程所等待的事件发生，如：所启动的I/O操作完成，所需要的数据到达等

进程切换

进程切换指中断当前进程的执行，转而调度并执行另外一个进程，切换原语：

• 将运行环境信息存入PCB
• 进程PCB移入相应队列
• 选择另一个进程执行，并更新其PCB
• 根据PCB恢复新进程所需的运行环境
  引起进程切换的事件：
• 当前进程时间片到
• 有更高优先级的进程到达
• 当前进程需要等待I/O等资源，主动阻塞
• 当前进程终止，如：程序出错时

现代操作系统进行进程切换时一定伴随着着模式切换，即需要从用户态陷入内核态执行，因为调度器以及进程上下文切换通常在内核态完成。切换过程通常借助中断(尤其是时钟中断)完成两个进程的上下文切换。但模式切换不一定涉及进程切换，可以在一个进程内部进行模式切换。

进程挂起与激活

OS通过挂起原语suspend将处于就绪或阻塞状态的进程挂起，处于阻塞状态的进程通常会被优先挂起，如果系统资源不足，刚创建的进程也可能被挂起。

OS通过激活原语active将指定进程激活，如果进程位于外存交换空间，则需要首先将其调入内存，然后将其加入就绪队列或阻塞队列。

进程通信IPC

进程通信(Inter-Process Communication，IPC)指进程之间的信息交换。多进程环境下，各进程拥有独立的虚拟地址空间，无法直接访问彼此的数据，必须依靠内核提供的通信机制才能安全、有序地交换信息

共享存储器

相互通信的进程共享某些数据结构或存储区，这些内存区域会映射到通信进程的虚拟空间地址方便操作，主要分为两种方式：

• 基于共享数据结构的通信：各进程公用某些数据结构，用于进行数据交换。这种通信方式仅适用于少量的数据传递，通信效率低下，属于低级通信。
• 基于共享存储区的通信：操作系统在内存中提供一块存储区，数据的形式、存放位置都有进程控制。该共享方式速度快，是一种高级通信方式

管道(pipe)通信

管道是一个特殊的共享文件，称为pipe文件，本质上是在内存中开辟一个固定大小的内存缓冲区。管道通信具有以下特点：

• 管道采用半双工通信，数据只能在一个方向上流动，如果需要双向通信，就必须创建两根管道，分别用于不同方向
• 管道传输的数据是无结构的字节流，管道本身不提供任何消息边界
• 管道严格保证数据按写入的顺序被读出，不允许随机存取
• 管道在内核中维护着一个固定大小的环形缓冲区（通常是一页内存，如 4KB）。当缓冲区写满时，写进程会被阻塞；当缓冲区为空时，读进程会被阻塞
• 管道中的数据一旦被读出，就彻底消失，管道允许多个写进程和多个读进程，为了防止读出错乱，操作系统会严格控制读进程的轮流读取

消息传递

• 直接通信方式：进程的PCB中包含消息队列，需要发送消息的进程直接通过发送原语发送消息，由操作系统将其加入接收进程PCB的消息队列中，再由接收进程通过接收原语，将其接收到自己的内存地址空间中
• 间接通信方式：以信箱作为中间实体交换信息，信箱可由操作系统或用户进程创建/撤销，当某个进程需要交换信息时，可以通过发送原语将消息发送到指定信箱，接收方可以通过接收原语从指定信箱接收消息。

客户机-服务器系统

功能最强大的 IPC 机制，不仅可用于同一台主机进程间通信，更广泛用于跨网络的不同主机进程间通信，其主要实现方法有：

• 套接字：分为两种：

  • 基于文件型：通信进程都运行在同一台机器的环境中，套接字是基于本地文件系统支持的，一个套接字关联到一个特殊的文件，通信双方通过对这个特殊文件的读写实现通信，类似于管道
  • 基于网络型：使用非对称方式通信，通信双方的进程运行在不同主机的网络环境下，一个属于接收进程(或服务器端)，一个属于发送进程(或客户端)，使用套接字和不同协议完成通信，是使用最为广泛的的进程通信方式。

• 远程过程调用和远程方法调用：远程过程调用RPC(Remote Procedure Call)，是一个通信协议，用于通过网络连接的系统。该协议允许运行于一台主机(本地)系统上的进程调用另一台主机(远程)系统上的进程，而对程序员表现为常规的过程调用，无需额外地为此编程。如果涉及的软件采用面向对象编程，那么远程过程调用亦可称做远程方法调用

信号

进程间的异步通信机制，用于通知进程有某事件发生，可在任何时刻发送给进程，无需知道进程状态。如：Linux定义了64种信号，比如SIGINT用于中断进程，SIGKILL用于强制终止进程，这些信号已经定义好了默认工作方式，进程收到信号时可以选择：默认处理、忽略信号或自定义捕捉并修改信号的响应执行(但不是所有信号都能被忽略和捕获)

线程

在20世纪60年代中期，人们在设计多道程序OS时，引入了进程的概念，从而解决了在单处理机环境下的程序并发执行问题。此后在长达20年的时间里，在多道程序OS中一直是以进程作为能拥有资源和独立调度(运行)的基本单位的。

进程是资源的拥有者，在进程创建、撤销、切换过程中，系统需要付出较大的时空开销，为此，80年代中期，人们又提出了比进程更小的基本单位——线程，用来进一步提高程序并发执行的能力，并减少系统开销。

线程的概念

线程（Thread）：线程是进程中的一个基本执行单元，也是操作系统进行CPU调度的基本单位。一个进程可以包含一个或多个线程，多个线程可以并发执行，同一进程中的所有线程共享该进程拥有的大部分资源(如：虚拟地址空间、打开的文件等)，而线程通常不单独拥有系统资源，仅拥有少量独立的资源(大部分资源来源于所属进程)，以保障多个线程能够独立执行不同的任务，因此说进程是资源分配的基本单位，线程是操作系统进行CPU调度的基本单位

线程与进程

线程具有许多进程所具有的特征，因此线程又称为轻型进程(Light-WeightProcess)或进程元，传统进程称为重型进程(Heavy-Weight Process)， 线程和进程比较有以下特点：

• 进程是系统进行资源分配的基本单位，持有大量资源。而线程通常不单独拥有系统资源，仅拥有保证自身运行所必需的少量资源(如：线程控制器TCB、寄存器集合、存储局部变量、返回参数的堆栈空间等)，其所需的大部分资源都来自所属进程
• 进程的切换需要进行大量上下文切换，开销较大，线程的切换只需要少量寄存器等内容切换，代价较低。同一进程中的线程切换不会引起进程切换，但从一个进程中的线程切换到另一个进程中的线程，必然引起进程切换
• 同样，创建/撤销一个线程的代价比创建/撤销进程的代价远远要小
• 同一进程中的线程共享地址空间和系统资源，线程之间的通信不需要借助复杂的进程间通信（IPC）机制，不会触发用户态到内核态的模式切换
• 线程创建、状态切换、撤销和线程间通信开销低的特点，进一步提高了系统的并发能力
• 一个仅包含一个线程的进程称为单线程进程；一个包含多个线程的进程称为多线程进程
• 多处理机环境下，各线程可占用不同的CPU
• 线程也拥有线程控制块(TCB)、线程ID，以及就绪、阻塞、运行三种基本状态
• 多进程OS中，进程不再是可执行的实体，而是将线程作为独立运行/调度的基本单位，即便如此，进程仍然拥有可执行的相关状态。如：挂起一个进程会挂起该进程中的所有线程，撤销进程也会撤销进程中的所有线程

线程控制块TCB

类似于每个进程拥有进程控制块，每个线程也拥有一个线程控制块TCB，用于记录和管理线程信息，包括：

• 每个线程唯一的线程标识符，类似于进程的PID
• 线程所属寄存器的内容，包括程序计数器PC、状态寄存器、通用寄存器的内容
• 线程运行状态
• 线程执行的优先级
• 线程专用存储区，用于存放线程切换时的上下文信息等内容
• 堆栈指针，如：线程进行函数调用时保存局部变量、返回地址等

线程的状态与控制

线程也有就绪、执行、阻塞三种基本状态，也有创建和终止状态，其表现、引发状态改变的事件原因与进程类似，其中线程的创建称为派生(Spawn)，多数语言（如C++/Java）的spawn走的是1:1内核线程模型（由操作系统调度，重量级）；而Go的goroutine、Erlang的进程是M:N模型（用户态调度器，轻量级，可创建百万级）

线程的实现

用户级线程ULT

早期的操作系统中，OS只支持进程，不支持线程，因此当时的“线程”是由开发者们通过代码和线程库在用户层面实现的逻辑线程

loading

用户级线程ULT(User Level Threads)指线程的管理（创建、调度、同步、销毁）全部在用户空间完成，操作系统内核完全不知道线程的存在，它具有以下特点：

• 线程的创建、撤销、同步与通信等功能，都与内核无关，内核完全不知道用户级线程的存在
• 线程的TCB由线程库在用户空间维护，这些数据结构都位于进程的用户堆区，内核不可见
• 线程的切换可以在用户态下完成，无需切换到内核态
• 线程管理开销小、效率高
• 一个线程阻塞后(如：等待I/O)，整个进程会被改为阻塞状态，导致该进程内的所有其他ULT也被阻塞，并发度不高
• 内核只能感知到进程，并以进程为单位分配CPU时间，因此多个线程无法在多核处理机上并行运行

内核支持线程KST

loading

内核支持线程KST(Kernel Supported Threads) 指线程的创建、调度、管理和销毁全部由操作系统内核完成，内核负责维护线程控制块（TCB）并管理其生命周期，它具有以下特点：

• 线程的管理工作由操作系统内核完成，内核需为每个线程分配一定大小的内核栈及TCB，内存开销显著
• 线程调度、切换等工作都由内核负责，线程切换都要陷入用户态→内核态→用户态，消耗大量 CPU 时间
• 当线程数量极大时，内核调度负担过重，导致系统性能下降
• CPU 调度的基本单位是线程，同一进程内的多个线程可同时运行在多核 CPU 的不同核心上
• 单线程阻塞后，进程内其他线程依然能获得 CPU 调度
• 线程间同步（如：互斥量、信号量）可直接调用内核 API，功能完善
• 适合计算密集型+I/O密集型混合任务

组合模型(M:N模型)

组合模型（M:N 模型）指 M 个用户级线程（ULT） 多路复用到 N 个内核支持线程（KST）上（通常 M ≥ N），真正被CPU执行的是 N 个KST，用户线程只是逻辑上的执行流，该方式结合二者的优点，并克服各自的不足。实现同一个进程内的多个线程可以同时在多个处理器上并行执行，且在阻塞一个线程时不会阻塞整个进程，并有较低的系统开销。

loading

M个用户级线程到N个内核支持线程的映射有以下几种方式：

• 一对一模型：:一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。其优点是当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。缺点是一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
• 多对一模型：多个用户级线程映射到一个内核级线程，仅当用户线程需要访问内核时，才进行映射，且每次只允许一个线程进行映射。其优点是开销小，效率高，缺点是如果一个线程访问内核时阻塞，则整个进程都会被阻塞，此外，任一时刻，只能有一个进程访问内核，多个线程不能同时在多个处理机上运行
• 多对多模型：M个用户线程映射到N个内核级线程(M ≥ N)。每个用户进程对应N个内核级线程。克服了多对一模型并发度不高的缺点(一个阻塞全体阻塞)，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。内核级线程中可以运行任意一个有映射关系的用户级线程代码，只有N个内核级线程中正在运行的代码逻辑都阻塞时，这个进程才会阻塞

处理机调度

调度（Scheduling）指操作系统按照一定的调度算法，在多个作业（Job）、进程（Process）或线程（Thread）之间分配系统资源（尤其是CPU资源），其目的是提高系统资源利用率、吞吐量和响应速度，并保证系统能够公平、高效地运行

处理机调度的层次

操作系统通常将调度划分为三级：

• 高级调度（High-Level Scheduling）：又称为作业调度（Job Scheduling）或长程调度（Long-term scheduling），它的调度对象是作业（Job），主要负责从外存后备队列中选择一个或多个作业，为其创建进程并分配必要资源，使其进入就绪状态，正式成为系统中的进程。由于一个作业通常只会被创建一次，因此高级调度对同一作业一般只执行一次。如：银行的大型批处理机，工作人员于下班前提交任务，调度程序在夜晚调入硬盘中的Job1,Job2…，进行批量结算。在分时、实时操作系统中，由于用户程序通常直接创建进程，因此一般不存在独立的高级调度。如：用户直接通过shell执行任务，会立即创建进程，不再经历作业调度。
• 中级调度（Medium-Level Scheduling）：又称为内存调度（Memory Scheduling）或中程调度（Medium-term scheduling），主要负责在内存和外存之间调度进程，它的调度对象是处于挂起状态的进程。当系统内存不足或需要提高吞吐量时，操作系统会将部分暂时不能运行的进程挂起（Suspend），并将其所占内存换出（Swap Out）到外存等待；当条件满足后，再将其重新换入（Swap In）内存并恢复运行。中级调度实际上就是存储器管理中的内存交换功能(Swap)。
• 低级调度（Low-Level Scheduling）：又称为进程调度、CPU调度、中程调度（Short-term scheduling），主要负责从就绪队列中选择一个进程，为其分配CPU，使其进入运行状态，其调度对象是就绪的进程，是最基本、最频繁发生的一种调度。当出现以下情况时，通常需要重新进行低级调度：

  • 当前进程时间片用完（通过时钟中断发起）
  • 当前进程主动阻塞（如等待I/O，通过I/O中断发起）
  • 当前进程结束运行
  • 更高优先级进程进入就绪队列（抢占式调度）
  • 中断或异常导致需要重新选择运行进程

调度器与闲逛进程

调度器（Scheduler））是操作系统中负责决定哪个进程（或线程）获得 CPU 执行权的核心组件，它属于操作系统内核的一部分，对于不支持内核级线程的操作系统，调度器的处理对象是进程；对于支持内核级线程的操作系统，调度器的处理对象是内核线程。现代操作系统中，调度器通常会维护多个就绪队列（Ready Queue），并通过调度算法从就绪队列选择一个进程或线程分配CPU，调度程序的运行通常由以下几类事件触发：

• 当前进程时间片耗尽（时钟中断）
• 当前进程主动阻塞（如等待 I/O）
• 当前进程退出
• 更高优先级的进程进入就绪队列
• CPU 从中断处理程序返回时

闲逛进程

闲逛进程（Idle Process）又称空闲进程，是操作系统在启动时创建的一个特殊进程（或线程），它具有最低的调度优先级，始终处于就绪状态。当系统中没有任何其他可运行进程时，调度器就会选择闲逛进程运行。闲逛进程的主要作用包括：

• 保证调度器始终有可调度对象，避免调度程序设计需要处理就绪队列空这一异常情况
• CPU需要时刻执行指令，不存在”什么都不执行”这种状态，闲逛进程提供了一段合法、安全执行的代码，它通常会调用 HLT、MWAIT等省电指令，使 CPU 进入低功耗状态，等待中断或新的可运行任务到来
• 操作系统可以利用闲逛进程的运行时间统计 CPU 空闲率和利用率

进程调度的方式

• 非抢占方式(Nonpreemptive Mode)：又称非剥夺方式，非抢占式调度只允许进程主动放弃处理机，即便有更紧急的任务到达，当前进程也会继续使用处理机，决不会因为时钟中断或任何原因去抢占当前进程的处理机。这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统。但它不能用于分时系统和大多数实时系统。该方式下引起进程调度的原因只可能有：

  • 正在执行的进程运行完毕，或因异常无法再继续运行
  • 正在执行中的进程(因请求I/O)主动进入阻塞状态

• 抢占方式(Preemptive Mode)：又称剥夺方式，抢占式调度允许调度程序暂停某个正在执行的进程，将处理机重新分配给另一进程。该方式可以优先处理紧急任务，并且能防止一个长进程长时间地占用处理机。在分时系统中，只有采用抢占方式才能及时响应用户操作，实现人机交互。该调度方式比较复杂，所需付出的系统开销也较大。抢占式调度出现的原因可能是：

  • 优先级高的进程到达，需要优先执行。此时将打断当前进程的执行，即便它的当前时间片还有剩余，CPU都将执行高优先级进程并启动一个新的时间片
  • 当前进程时间片用完，CPU通过时钟中断调度下一个进程运行

调度算法的评价指标

调度方式和调度算法，应当能尽量提高以下设计指标：

• CPU利用率：设备利用率=忙碌时间/总时间，因此：CPU利用率=CPU有效工作时间/(CPU有效工作时间+CPU空闲等待时间)
• 系统吞吐量：单位时间内完成作业的数量，系统吞吐量=总共完成作业数量/总共花费时间；
• 尽可能让诸进程都获得合理的CPU时间，避免一个进程长时间占用处理机，导致其他进程饥饿
• 能识别并平衡不同类型进程的调度优先级，如计算型进程(如：数据排序、挖矿程序等)大部分时间都在用 CPU 做运算，很少请求 I/O 操作，而I/O 型进程(如：数据库服务、文本编辑器(多数时间等待用户输入))大部分时间在等待 I/O 操作，CPU 使用时间极短，但会频繁请求 I/O 并阻塞等待。因此可以让I/O型进程获得优先响应，让其在后台等待I/O，再调度执行计算型进程，让CPU和I/O设备都处于忙碌状态
• 对批处理系统，周转时间应该短。周转时间指从作业被提交系统开始，到作业完成的时间间隔，它包括四部分：作业在外存的等待时间、进程在就绪队列的等待时间、进程在CPU上执行时间、进程等待I/O操作的时间，周转时间的评估参数有：

  • 平均周转时间=各作业周转时间之和/作业数
  • 带权周转时间=作业周转时间/作业实际运行时间。该值必然≥1，其值越接近1，说明该作业实际执行时间与用户等待时间越接近，用户满意度越高
  • 平均带权周转时间=各作业周转时间之和/各作业实际运行时间之和

• 对分时系统，响应时间应该短。响应时间指用户输入请求开始，到屏幕显示处理结果的时间间隔，它包含三部分：请求从输入到传送给处理机的时间、处理机处理时间、处理结果回送到终端显示器的时间
• 对实时系统，需要保证任务必须开始执行的时间或必须完成的最迟时间

调度算法

先来先服务FCFS

先来先服务（FCFS，First Come First Serve）：按照进程（或作业）到达就绪队列的先后顺序进行调度，先到先执行，直到完成或主动阻塞才切换

特点：

• 非抢占式调度算法。
• 实现最简单，公平地按照到达顺序执行。
• 对长作业有利，对短作业不利。
  优点：
• 算法简单，实现开销小。
• 不会发生饥饿现象。
• 适用于批处理系统。
  缺点：
• 平均周转时间较长。
• 容易产生”护航效应（Convoy Effect）”，长作业阻塞大量短作业。
• 响应速度差，不适合交互式系统。

最短作业优先SJF

最短作业优先（SJF，Shortest Job First）：每次选择预计运行时间（CPU Burst）最短的作业或进程执行。可分为非抢占式SJF和抢占式SRTF（Shortest Remaining Time First）

特点：

• 非抢占式SJF：作业开始执行后不会被抢占。
• 抢占式SRTF：若新到达进程剩余时间更短，则立即抢占CPU。
• 需要预测进程运行时间。
  优点：
• 平均等待时间、平均周转时间最小。
• CPU利用率较高。
  缺点：
• 难以准确预测运行时间。
• 长作业可能长期得不到调度，产生饥饿现象。
• 不适用于交互系统。

最高响应比优先HRRN

最高响应比优先（HRRN，Highest Response Ratio Next）：选择响应比最高的作业运行，其中响应比 = (等待时间 + 要求服务时间) / 要求服务时间，这意味着等待越久，响应比越高；运行时间越短，响应比也越高

特点：

• 非抢占式调度算法。
• 综合考虑等待时间和运行时间。
• 是FCFS和SJF的折中方案。
  优点：
• 平均周转时间较短。
• 长作业不会一直等待，基本不会发生饥饿。
• 调度较公平。
  缺点：
• 每次调度都需要计算所有作业响应比。
• 不适用于实时系统。

时间片轮转RR

时间片轮转（RR，Round Robin）：为每个进程分配固定时间片，时间片用完后立即发生时钟中断，将CPU分配给下一个就绪进程；一个时间片未用完，进程完成也会激活调度程序，调度新的进程并启动一个新的时间片

特点：

• 抢占式调度算法。
• 所有进程循环获得CPU。
• 时间片大小影响系统性能。
  优点：
• 响应速度快。
• 公平性好。
• 不会产生饥饿。
• 是分时操作系统最常用算法。
  缺点：
• 时间片过大，退化为FCFS。
• 时间片过小，频繁上下文切换，系统开销增大。
• 不考虑作业长短。

优先级调度

优先级调度（Priority Scheduling）：根据优先级大小选择进程运行，可分为静态优先级和动态优先级，也可分为抢占式和非抢占式：

• 静态优先级：进程优先级在创建进程时确定，在整个调度期间不变，其优先级靠进程类型、进程对资源的需求、用户要求等内容确定，该方法的特点是系统开销小，但不够精确
• 动态优先级：进程创建之初拥有初始优先级，之后其优先级可以随着等待时间或其他事件的发生进行调整，可以获得更好的调度性能

特点：

• 高优先级进程优先执行。
• 优先级可由系统或用户指定。
• 动态优先级可随着等待时间调整。
  优点：
• 能保证重要任务优先执行。
• 适用于实时系统。
• 调度灵活。
  缺点：
• 低优先级进程可能长期得不到执行，发生饥饿。
• 通常需要采用”老化（Aging）”机制提高等待进程优先级。

多级队列调度

多级队列调度（Multilevel Queue）：按照进程类型划分多个固定队列（如系统进程、前台进程、后台进程、批处理进程等），每个队列采用不同调度算法，进程进入后通常不能在队列间移动

特点：

• 每个队列拥有固定优先级或固定CPU时间比例。
• 队列之间可采用固定优先级调度，也可按时间比例共享CPU。
• 队列内部可采用FCFS、RR等不同算法。
  优点：
• 不同类型任务可采用最适合的调度策略。
• 实现简单。
• 适用于职责明确的系统。
  缺点：
• 队列固定，缺乏灵活性。
• 低优先级队列可能发生饥饿。
• 无法根据进程行为动态调整优先级。

多级反馈队列MLFQ

MLFQ（MLFQ，Multilevel Feedback Queue）：建立多个优先级队列，不同队列采用不同时间片。新进程首先进入最高优先级队列，若时间片用完仍未完成，则降至下一队列；等待时间过长时可提升优先级（老化）。

loading

执行方式：

• 队列1优先级最高，队列2其次，然后逐级降低
• 队列1时间片最小，队列2时间片稍长，然后逐级变长
• 新进程进入内存时，都放到队列1的末尾，依次调度。
• 进程执行时，如果它能在队列1的时间片内完成，则执行完毕后撤出；若无法执行完成，则时间片结束后暂停执行，并转入队列2末尾进行排队
• 调度器总是优先调度队列1，只有当队列1空时才调度队列2中的进程，以此类推
• 若当前处理机正在处理队列i的进程，而有更高优先级的进程到达时，调度器将打断执行(且该过程不会等待时间片执行完，而是立即打断)，并将当前进程重新放回队列i的末尾进行排队

特点：

• 是现代通用操作系统最常见的调度思想（如Windows、Linux中的部分调度策略）
• 抢占式调度算法。
• 综合FCFS、RR和优先级调度思想。
• 不需要预先知道作业运行时间。
• 短作业通常停留在高优先级队列，长作业逐渐下降。
  优点：
• 兼顾交互任务和后台任务。
• 响应速度快。
• 吞吐量高。
• 能较好平衡公平性与效率。
  缺点：
• 算法复杂，实现成本高。
• 队列数量、时间片大小、升级降级规则较难设计。
• 参数设置不合理会影响整体性能

多处理机调度

多处理机环境下，需要考虑两个目标：

• 负载均衡：尽可能让所有每次CPU都同等忙碌
• 处理机亲和性：尽量让一个进程的多轮调度到同一个CPU上运行，以发挥CPU中缓存的作用(Cache)

公共就绪队列

所有CPU共享同一个就绪进程队列。每个CPU时运行调度程序，从公共就绪队列中选择一个进程运行(每个CPU访问公共就绪队列时需要上锁，确保互斥)。该方案优点是可以天然地实现负载均衡，缺点是各个进程可能会频繁地换CPU运行，“亲和性”不好

为提高公共就绪队列方式下的处理器亲和度，有以下两种方式：

• 软亲和：由进程调度程序尽量保证“亲和性”
• 硬亲和：由用户进程通过系统调用，主动要求操作系统分配固定的CPU，确保“亲和性”

公共就绪队列

每个CPU有一个私有的就绪进程队列。每个CPU时运行调度程序，从私有就绪队列中选择一个进程运行，该方案优点是天然地实现了“处理机亲和性”，缺点是负载均衡差，为提高负责均衡能力，通常提供以下方式：

• 拉迁移(pull)：周期性检查每个处理器的一个特定的系统程序一载，如果负载不平衡，就从忙碌CPU的就绪队列中“推”一些就绪进程到空闲CPU的就绪队列
• 推迁移(push)：如果一个CPU负载很低，就从其他高负载CPU的就绪队列中“拉”一些就绪进程到自己的就绪队列

实时系统与实时调度

实时系统指系统的正确性不仅取决于计算的逻辑结果，还取决于产生结果的时间，必须在规定的时间内完成事件的处理。实时系统又分为：

• 硬实时系统：对时间的约束绝对严格，任务执行必须满足截止时间。错过截止时间意味着系统失败，可能导致灾难性事故，在最坏情况下也要保证所有关键任务按期完成。常用于如：汽车安全气囊、航空航天飞控系统、生命维持系统、实时交易系统等领域
• 软实时系统：对时间的约束相对宽松，错过截止时间只会导致服务质量下降，因此目标是尽可能满足更多任务的截止时间，降低平均响应延迟。常用于视频播放、网络电话、在线游戏等领域

实时系统的特征

• 时间约束性强：最根本特征，任务有明确的截止时间。
• 可预测性：系统行为在时间上必须是可预知的，而非平均速度快。
• 可靠性：系统崩溃或错过截止时间可能导致灾难性后果。
• 与交互性的区别：交互式系统追求“快”，实时系统追求“准时”。

实时调度核心概念

实时系统中的任务通常由三个要素循环描述：

• 周期：周期性任务两次实例之间的固定间隔。
• 执行时间：任务单次实例完成所需的最坏情况执行时间，必须小于等于周期。
• 相对截止时间：任务实例从释放（就绪）到必须完成的时间长度。通常等于周期。

速度单调调度RMS

速度单调调度RMS（Rate Monotonic Scheduling）会为任务分配静态的、固定的优先级，其核心思想是周期越短，优先级越高(一个任务的执行频率越高，它的优先级就越高)，周期短的任务将被优先调度。该调度算法的优点是：简单可靠，运行时完全按照既定的“频率排序”来执行，行为可预测，是静态优先级调度中的最优算法，且系统过载时周期短、更关键的高优先级任务依然能按时完成。但缺点是：CPU利用率上限较低，对非周期性任务处理不直接，且算法的唯一依据是“执行频率”，会使得周期长而紧急的任务反而有更低的优先级。

最早截止时间优先EDF算法

最早截止时间优先EDF(Earliest Deadline First)指根据任务实例的绝对截止时间进行动态优先级分配。规则是：截止时间越近，优先级越高。该算法优点是能自适应处理周期或时间变化的任务，灵活性高，缺点是运行时需动态计算和比较绝对截止时间，开销较大

最低松弛度优先算法

• 最低松弛度优先LLF(Least Laxity First)：其中松弛度 = 距离绝对截止时间 - 剩余执行时间，即计算出当前时刻到截止时间之间，任务还能被推迟多久，松弛度为零意味着任务必须立即执行，否则必定超期。调度优先级由任务的松弛度决定：松弛度越小，优先级越高。其优点是直接地反映了任务的紧急程度，缺点是需要频繁、实时地计算每个任务的松弛度，系统开销巨大

优先级倒置

优先级倒置问题(priority inversion problem)是指当高、低优先级任务共享互斥资源（如锁）时，可能出现：高优先级任务被中优先级任务阻塞，而中优先级任务却先于高优先级任务执行的情况，如以下场景中：

1. 低优先级任务获得共享锁，进入临界区。
2. 高优先级任务就绪，先被调度执行，并抢占了低优先级任务执行时间，但试图获取同一个锁时被阻塞。
3. 中优先级任务就绪，由于它不依赖该锁，会抢占低优先级任务运行。结果是高优先级任务看似在等待中优先级任务，导致其错过截止时间。

解决方案：

• 优先级继承协议：当高优先级任务因锁被低优先级任务占有所而阻塞时，低优先级任务会临时继承高优先级任务的优先级，从而不被中优先级任务抢占，直到其释放锁后恢复原优先级
• 优先级天花板协议：为每个互斥资源分配一个“优先级天花板”（即所有可能访问该资源的任务中的最高静态优先级）。一个任务获取锁后，其优先级会立即抬升至该锁的天花板优先级。这能防止死锁，避免连锁阻塞

并发控制

在多道程序系统中，进程并发执行极大地提升了系统的资源利用率和吞吐量。当一个进程因等待I/O而阻塞时，CPU可以立即转去执行另一个就绪进程，从而让CPU和I/O设备并行工作，显著提高了整体效率。

但进程执行的异步性，会导致多个并发执行的进程会以独立、不可预知的速度向前推进。这会引发一系列问题。多个进程共享数据时，交替执行可能导致数据不一致；协作进程之间需要相互等待，若协调不当，会造成执行顺序错乱；进程间可能因争夺资源而陷入死锁，因此，并发控制的目标，就是在利用并发优势的同时，通过互斥、同步、死锁处理等机制，确保系统正确且稳定运行。

进程同步

多个进程（或线程）在并发执行时，如果需要共同完成某项任务，或共享一份数据，则必须协调它们之间的执行顺序，否则可能导致数据不一致、资源竞争等问题。同步（Synchronization）是一种协调机制，它通过约束多个进程（或线程）的执行先后关系，使它们能够按照预期的时序协同工作。例如，一个写进程负责向管道（Pipe）写入数据，另一个读进程负责从管道读取数据。只有当写进程写入数据后，读进程才能成功读取；若管道为空，读进程则需要等待写进程完成写入。这种具有先后依赖关系的协作过程称为同步。

进程互斥与临界资源

临界资源（Critical Resource）是指一次只允许一个进程（或线程）访问的共享资源，例如打印机、共享变量、文件、缓冲区等。进程对临界资源的访问，必须互斥地进行，为此，可以把一个访问临界资源的循环进程在逻辑上分为以下四部分：

• 进入区（Entry Section）：通常用来检查是否能够访问临界资源，执行加锁或其他同步操作
• 临界区（Critical Section）：真正访问临界资源的代码，只允许一个进程（或线程）进入
• 退出区（Exit Section）：释放临界资源，执行解锁或唤醒等待进程等操作
• 剩余区（Remainder Section）：除上述部分之外的其他代码，与临界资源无关，可并发执行

互斥访问需要遵循的原则

为了实现进程（或线程）的互斥访问，操作系统中的同步机制（如锁、信号量、互斥量等）应满足以下四项基本准则：

• 空闲让进：当无进程（或线程）处于临界区，表明临界资源处于空闲状态，应允许请求进入的进程（或线程）立即进入，不应无故阻塞
• 忙则等待：当临界区已有进程（线程）占用时，其他请求进入者必须等待，以保证对临界资源的互斥访问
• 有限等待：对要求访问临界资源的进程，应保证有限时间内能进入临界区，以免陷入死等状态，
• 让权等待：当进程（线程）无法进入临界区时，应主动放弃处理机（如进入阻塞状态），以免陷入忙等状态(持续占用CPU)

实现进程互斥的方法有

• 软件实现方法
• 硬件实现方法
• 信号量
• 管程
• 消息传递

软件同步机制

早期计算机没有提供任何原子操作，CPU也没有提供Test-and-Set等硬件同步指令，因此研究者只能依靠对某一变量的读写操作，设计互斥算法。以下软件同步算法只用于解决两个进程间的互斥。

单标志法

其核心思想是每个进程进入临界区的权限只能被另一个进程赋予，两个进程在访问完临界区后会将临界区的权限转交给另一个进程

缺点：如果初始允许进入临界区的进程P0一直不访问临界区，则P1将永远无法访问临界区，即使临界区空闲，违反了空闲让进原则

双标志检查法

loading

loading

Peterson算法

loading

假设程序并发执行导致上述步骤按照1,2,3,6,7,8..执行，则P1会在while语句进入循环，进入自旋状态，P0和P1不会同时访问临界区。

缺点：Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则，进程会在while语句处循环等待。不让出CPU资源。

软件同步机制的局限性

软件同步机制是早期操作系统在缺乏硬件原子操作支持时提出的一类进程互斥方案，它们仅依靠共享变量和程序逻辑即可实现进程互斥，证明了无需专门硬件支持也能够正确解决临界区问题，但通过软件实现进程互斥存在以下问题：

• 只能解决固定数量进程互斥问题，如：Peterson等算法只能满足两个进程的互斥访问，一些改进的算法如Bakery虽然支持多进程，但复杂度较高，根本无法满足现代操作系统成百上千的并发进程
• 忙等待（Busy Waiting）：上述算法中的 while(flag[j] && turn==j)会导致进程处于忙等状态，进程不进入阻塞状态，CPU无法释放，不满足让权等待原则
• 软件算法依赖于 flag=true; turn=1; 等语句，且执行顺序不能改变，但现代CPU会乱序执行，可能会彻底打乱上述语句执行顺序
• 软件算法中，进入区检查、上锁操作不是一个整体，不具有原子性，可能出现两个进程同时进入临界区的情况
• 软件实现依赖于共享变量，但现代多核CPU有各自的多级缓存，软件算法几乎不能直接使用

软件同步机制的忙等待、实现复杂、可扩展性差等缺点，以及难以适应现代多核处理器的缓存一致性和乱序执行等硬件特性，导致软件方式很少在实际操作系统中使用。随着 CPU 提供 Test-and-Set、Compare-and-Swap（CAS）等硬件原子指令，现代操作系统普遍采用基于硬件支持的信号量、互斥锁、管程等同步机制来实现进程互斥与同步

硬件同步机制

硬件同步机制是操作系统实现并发控制的底层基础，主要依靠处理器提供的原子指令来实现，这些原子指令会不可分割地一次性完成“读-改-写”操作，以此来安全地检查和修改锁变量，从而构建出互斥锁等同步原语，它们是上层软件同步（如信号量、管程）的硬件基石

硬件同步机制的实现分为两大类：

• 通过关中断实现
• 通过专用机器指令实现，如：TestAndSet指令、Swap指令等，这些机器指令是通过硬件实现(下文的伪代码只是描述其工作流程)的原语，执行过程中不允许被中断，只能一气呵成

关中断

单核CPU中，进程在进入临界区前关中断，出临界区后开中断，使得进程在访问临界区期间，CPU都不响应中断，就不会发生进程切换，因此也不会发生两个进程同时访问临界区的情况，由此从根本上保证了只会有单个进程访问临界资源。该方法的特点是：

• 简单、高效
• 只适用于内核进程，用户进程滥用关中断权力可能带来安全问题
• 关中断时间过长可能丢失重要中断
• 一个处理器上的关中断无法阻止进程在其他处理器上执行临界段代码，因此不适用于多处理机

因此该方法仅适用于操作系统内核的极短临界区，非通用方案

Test-and-Set指令

Test-and-Set指令(简称TS指令，又称为TestAndSetLock或TSL指令)，其指令包含两个过程：读取旧值和设置锁为true，这两个动作在硬件中作为一个整体执行，硬件保证其原子性，其处理过程描述如下：

进程在进入临界区之前，首先通过TS指令测试lock的值，如果为false表示没有进程在临界区内，可以进入，且进入后TS指令会帮忙自行加锁。如果lock值为true，则需要等待：

假设P1，P2进程同时想访问临界区：

• 初始时 lock = false；
• P1执行 TS(lock)，返回得old = false，并加锁使得lock = true，且由于while(false)，使得p1可以跳过while的自选等待，进入临界区
• P2执行 TS(lock)，返回得old = true，p2会在while (TS((&lock)))语句中反复检测，循环等待，直到P1退出执行了 lock = false，P2才有可能获得资源

Swap指令

Swap指令称为对换指令，在Intel 80x86中又称为XCHG指令，用于交换两个字的内容，硬件保证交换过程不可被打断，其处理过程描述如下：

利用Swap指令实现进程互斥的的循环进程描述如下：

假设P1，P2进程同时想访问临界区：

• 初始时 lock = false；
• P1的key为true，执行Swap(lock,key)后lock=true；key=false，于是while(false)后进入临界区
• P1的key为true，执行Swap(lock,key)后lock=true；key=true，于是while(true)处循环等待
• P1退出时，lock=false，于是P2的下一次Swaplock=true，key=false，随后可以进入临界区

硬件指令实现进程互斥的特点

通过硬件指令实现进程互斥有以下优点：

• 实现简单
• 支持多处理器环境
• 保证互斥

但有以下缺点：

• 忙等（Busy Waiting）：等待进程不断循环锁资源是否释放，占用CPU资源，不满足让权等待原则
• 可能导致进程饥饿，多个进程竞争时，某些进程可能长时间抢不到进入临界区的机会
• 可能出现死锁：当低优先级进程正在使用临界资源时，有高优先级进程到达，并抢断调度，低优先级进程无法继续执行并释放临界资源，而高优先级进程也需要访问该资源时，就会产生死锁

信号量机制

无论是软件同步机制还是硬件同步机制，进程在等待临界资源释放时都处于忙等状态，不符合“让权等待”原则。

1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法——信号量(Semaphores)机制，信号量本质上是一个受保护变量(下文表示为S，它可以是一个整数，也可以是更复杂的记录型变量)，用户进程只能通过操作系统提供的一对原子操作来访问信号量：

• wait(S)：又称为P操作(来源于荷兰语proberen，简写为P(S))，用于尝试获取资源，若资源不足则转为阻塞状态等待
• signal(S)：又称为V操作(来源于荷兰语verhogen，简写为V(S))，用于释放资源，并唤醒一个等待进程

通常用一个信号量来表示系统中某种资源的数量，比如:系统中只有一台打印机，就可以设置一个初值为1的信号量。从而实现了进程互斥、进程同步。

整形信号量

用一个整型变量作为信号量，用来表示系统中某种资源的数量，然后通过原子操作wait(S)和signal(S)访问信号量，以保证资源检查和上锁操作不会被分开。该方式下wait(S)原语中进程也会在while循环时自旋忙等，依旧不满足“让权等待”原则。

int S = 1 ; //初始化整形信号量，假设临界资源只有一份

void wait (int S) { //wait原语，相当于进入区
  while (S <= 0); //如果资源不足，就一直循环等待
  S = S - 1; //跳出了while，说明资源足够，占用一个资源使用
}

void signal (int S) { //signal原语，相当于退出区
 S = S + 1 ;  //使用完资源后释放，资源数+1
}

//进程使用信号量的方式
...
wait(S);  //进入区，申请资源
.......   //临界区，访问并使用资源
signal(S);//退出区，释放资源
.....

记录型信号量

为了解决整形信号量的忙等问题，记录型信号量使用记录型数据结构，不仅记录临界资源数量，同时通过一个队列记录哪些进程在等待资源，以方便管理正在等待资源的进程在阻塞和唤醒状态之间切换。该方式进程在等待资源时会进入阻塞队列，释放处理机资源，遵循了“让权等待”原则。

/*记录型信号量的定义*/
typedef struct {
 int value ; //剩余资源数量
 struct process *list; //等待队列
} semaphore;

//wait原语，申请资源
void wait (semaphore S) {
  S.value--; //消耗一个资源
  if (S.value < 0) { //进程消耗资源后发现资源数量为负，说明当前并没有剩余可用资源，需要等待
    block (S.list);   //当资源数不足，通过block原语使进程进入阻塞态，并挂到信号量S的阻塞队列中等待
  }
}

//signal原语，释放资源
void signal (semaphore S) {
  S.value++; //释放一个资源
  if(S.value <= 0){ //释放资源后发现剩余资源数<=0，说明有进程在阻塞队列等待
    wakeup(S.list); //通过wakeup原语唤醒阻塞队列中等待的进程，使其变为就绪态
  }
}

信号量的运用

在使用信号量实现进程互斥、进程同步时，一个信号量通常对应一种临界资源，有多种临界资源时需要声明相应数量的信号量，信号量的值代表了临界资源的剩余数量(值小于0说明有阻塞的进程在等待资源)，此时，PV操作分别代表以下：

• P(S)：申请一个资源S，如果资源不足则阻塞等待
• V(S)：释放一个资源S，如果此时有进程在等待该资源，则还需要唤醒一个进程

信号量实现进程互斥

用信号量实现进程互斥的逻辑通常固定：

• 定义互斥信号量(以下声明为mutex，表示Mutual Exclusion，互斥)，初始值代表临界资源的数量 (为1代表该临界资源只有一份，在同一时刻只允许一个进程进入)，如果有多个类型的互斥资源，每一类互斥资源都要声明一个独立的互斥信号量
• 划分出临界区的代码(如：对临界资源打印机的访问)
• 每个进程在进入临界区前执行P(mutex)，退出时执行V(mutex)

工作机制：

• 假设进程P1先执行，执行完 P(mutex)后mutex 变为0，P1进入临界区。此时P2若执行 P(mutex)，mutex 变为 -1，P2被阻塞并进入等待队列
• P1执行完 V(mutex)，mutex 变为 0（因为此前是-1），会唤醒P2，P2从阻塞态转为就绪态，获得临界区访问权
• P、V操作必须成对出现，缺少P(mutex)操作就无法保证临界资源的互斥访问，缺少V(mutex)会导致资源永不释放，等待进程不再被唤醒

信号量实现进程同步

并发执行的进程由于其异步性，二者交替推进的次序是不确定的，进程同步要求各并发进程按要求有序地推进，如：下述进程中要求“代码4”一定在“代码2”之后才会执行，使用信号量实现该同步关系的核心要点为先V后P，步骤如下：

• 分析必须保证哪些操作的“一前一后”的执行顺序
• 设置信号量S，初始值为0
• 在前操作之后执行V(S)
• 在后操作之前执行P(S)

• 如果V(S)操作先被调度执行，则V(S)内部S++后S=1，之后执行P2中的P(S)后将能够继续执行到代码4
• 如果P(S)操作先被调度执行，则P(S)内部由于S–后S=-1，P2进程会主动请求阻塞，不再向下执行。等到V(S)操作被执行后，唤醒P2进程并继续执行到代码4，由此实现代码4一定在代码2之后执行

信号量实现前驱图

前驱图（Precedence Graph）是一种有向无循环图(DAG，Directed Acyclic Graph)，用于描述程序的执行顺序和并发执行情况，图中的每个结点表示一个程序、程序段或者语句，如：有向边 Pi → Pj 表示 Pi 必须在 Pj 开始执行前完成，即 Pi是 Pj 的前驱。前驱图必须无环，否则会产生无法解决的死锁或循环等待。

通过信号量机制实现前驱关系的步骤：

• 为每一对前驱关系各设置一个同步信号量
• 在前操作之后执行V(信号量)操作
• 在后操作之前执行P(信号量)操作

loading

生产者消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程生产产品放入共享缓冲池，消费者进程从池中取产品，缓冲池有n个缓冲区，需保证：

• 对缓冲池的访问需要互斥，不能同时读写
• 缓冲区满时，生产者不能继续放（阻塞）
• 缓冲区空时，消费者不能继续取（阻塞）

信号量设置
上述要求有两个同步需求、一个互斥需求，由此设置以下信号量：

semaphore mutex = 1 ;
semaphore empty = n ;
semaphore full = 0 ;

生产者进程(无限循环)

producer () {
    while(1) {
       生产产品;
       P(empty);  //消耗一个空闲缓冲区
       P(mutex);  // 申请进入临界资源(缓冲区)
       将产品放入缓冲区;
       V(mutex); //释放临界区资源
       V(full);  //增加一个产品
    }
}

消费者进程(无限循环)

consumer () {
    while(1) {
       P(full);  //消耗一个产品(非空闲缓冲区)
       P(mutex); // 申请进入临界资源(缓冲区)
       从缓冲区取出产品
       V(mutex); //释放临界区资源
       V(empty); //增加一个空闲缓冲区
       使用产品;
    }
}

死锁的产生

• P 操作的顺序必须严格先执行 P(empty/full) 再执行 P(mutex)
• 如果先执行 P(mutex) 后执行 P(empty)，则生产者进程在进入临界资源后，如果遇到缓冲区已满，则会进入阻塞状态等待消费者消费(但没有释放临界资源)
• 随后消费者进程被调度时，无法进入临界区访问缓冲区，因此无法消费产品，也就无法唤醒阻塞的消费者进程，由此产生死锁
• 上述V操作不会导致进程阻塞，因此两个V操作顺序可以交换

多生产者多消费者问题

假设有大小为1的缓冲区，生产者进程P1生产商品A，生产者进程P2生产商品B，消费者进程C1只消费商品A，消费者进程C2也只消费商品B，使用信号量机制实现该过程的分析如下：

• 互斥关系：缓冲区需要互斥访问
• 同步关系：

  • 进程P1生产产品A后，C1才能执行
  • 进程P2生产产品B后，C2才能执行
  • C1和C2的执行，都会使得缓冲区为空，并使得P1或P2执行

信号量设置

semaphore mutex = 1 ;//互斥信号量
semaphore A = 0 ;//缓冲区中的商品A
semaphore B = 0 ;//缓冲区中的商品B
semaphore buffer = 1 ;//缓冲区剩余空闲数量

进程实现

• 如果消费者进程C1/C2先被调度执行，会在执行P(A)/P(B)语句时进入阻塞状态，等待商品产生
• 如果P1先被调度执行，放入商品A后，会唤醒C1，P2如果被调度，会因为P(buffer)阻塞，C2会因为P(B)阻塞，只有C1能执行
• 由于临界区资源为1，因此即便不设置互斥信号量mutex也能完成上述功能，信号量buffer能同时完成它的职责，但如果临界资源值为其他值，则必须需要互斥信号量，buffer无法保证两个生产者进程不会同时进入临界区

读者-写者问题

系统中有一组读者进程和一组写者进程，它们共享一个文件或数据区，对文件的读写有以下要求:

• 允许多个读进程同时读（读-读不互斥）
• 一次只允许一个写进程写入，且此时不允许读（写-读、写-写均互斥）
• 与生产者-消费者问题不同，读进程不会带走临界资源内容

读优先

设置以下信号量和变量

写者进程(无限循环)

读者进程(无限循环)

reader ( ) {
  while (1) {
  P(mutex); //保证对read_count的判断和修改两个步骤能一起发生(原子性)
  if(read_count == 0){ //多个读进程一起读时，第二个读进程开始的进程不再执行下述锁操作
    P(rw);
  }
    read_count ++ ; //读进程数量增加
  V(mutex);//read_count值的操作结束，释放锁
  执行读操作
  P(mutex); //同样锁住对read_count的操作
  read_count --; //读进程读取结束，数量减少
  if( read_count == 0){ //最后一个结束的读进程，释放文件资源，之后写进程将可以访问
    V(rw);
  }
  V(mutex); //释放对read_count的锁
 }
}

读者进程代码演变：

上述代码依旧存在以下问题：

• 首个读进程P1执行P(mutex); if(read_count == 0)等语句后，被中断，没有执行V(mutex);
• 后续读进程执行时会被P(mutex)阻塞，需要等待P1再次被调度并执行完V(mutex)才能进入临界区，降低了读者并发性
• 该方法核心展示如何协调读者共享以及写者互斥，但它不是高性能读写锁
• 当有多个读进程和多个写进程时，当临界区中已经有读进程时，读进程可以直接进入临界区，因此它们能连续访问文件资源，写进程将一直被阻塞，因此该方式对文件的访问是读优先的，有可能引发写进程饥饿

公平策略

为防止写进程饥饿，需要添加一个信号量以让写进程能够锁住后续到达读进程的进入临界区的步骤(该方法书上描述为写优先，但实际读写是按照进程到达顺序进行的，属于公平策略)

信号量

写进程(无限循环)

读进程(无限循环)

• 当读进程1+读进程2连续访问时，读进程1执行完P(w)-V(w)之间的操作，进入临界区，读进程2也可以以同样方式进入临界区，实现多个进程同时读
• 写进程1+写进程2访问时，写进程1执行完P(w)，写进程2执行P(w)时会被阻塞，实现两个写进程的互斥
• 写进程1+读进程1访问时，写进程执行P(w)后，读进程执行p(w)会阻塞，实现读写进程的互斥访问
• 读进程1+写进程1+读进程2访问时，读进程1执行完P(rw)后rw=0，写进程执行P(rw)时阻塞；写进程执行完P(w)后w=0，读进程2执行P(w)时阻塞，无法插队读取
• 由此，读进程与写进程是按照进程到达顺序排队因此执行，不会出现写进程饥饿情况

哲学家进餐问题

问题描述：5位哲学家围坐在圆桌旁，桌上有5根筷子，每两位哲学家之间各放一根，每位哲学家交替进行思考和进餐，进餐时需要同时拿起左右两根筷子，有以下约束条件：

• 哲学家拿起一根筷子后，若另一根被占用，则必须等待（且已拿起的筷子不放回）
• 保证不发生死锁（所有哲学家各拿一根筷子等另一根）
• 保证不发生饥饿（无哲学家永远吃不上饭）

loading

死锁的产生

设一个互斥信号量数组chopstick[5]，初始值全为1表示初始时所有筷子可用，哲学家编号为0-4，第 i 号哲学家左边的筷子编号为 i ，右边的筷子编号为 (i+1)%5

假设所有哲学家依次请求左边的筷子、再请求右边的筷子来完成进餐，则所有进程在执行 P(chopstick[(i+1)%5]) 时都会被阻塞，都等待右手边的筷子资源释放，变成循环等待，形成死锁。

解决方案1：限制进餐人数

限制最多只能有 4 名哲学家同时进餐，这样即便 4 名哲学家依次拿起了左边的筷子，由于第 5 名哲学家不占用资源，因此第 4 名哲学家能同时凑齐左右两侧的临界资源，完成进餐，从而打破循环等待条件。等待第 4 名哲学家完成进餐后释放临界资源，第3,2,1,5名哲学家将可以依次用餐

semaphore chopstick[5] = {1,1,1,1,1};
semaphore room = 4 ; //通过信号量限制并发进餐人数 ≤ 4
//第i号哲学家的进程
Pi ( ) {   
  while (1) {
    P(room);  //申请进餐许可（最多4人同时进餐）
    P(chopstick[i]) ; 
    P(chopstick[(i+1)%5]) ; 
    执行吃饭操作 ;    
    V(chopstick[i]) ; 
    V(chopstick[(i+1)%5]) ; 
    V(room);  //释放进餐许可资源
    执行思考操作 ;
  }
}

解决方案2：奇偶位改变拿筷顺序

奇数位的哲学家先左后右取筷子，偶数位哲学家先右后左取筷子，破坏循环等待，不会出现所有哲学家都拿同一只手边的筷子。该方法不需要额外信号量。

semaphore chopstick[5] = {1,1,1,1,1};
//第i号哲学家的进程
Pi ( ) {   
  while (1) {
    if(i%2 == 0){ // 偶数号（0,2,4）：先右后左
    P(chopstick[(i+1)%5]) ; 
    P(chopstick[i]) ; 
    } else {     // 奇数号（1,3）：先左后右
    P(chopstick[i]) ;   
    P(chopstick[(i+1)%5]) ; 
    }
    执行吃饭操作 ;    
    V(chopstick[i]) ; 
    V(chopstick[(i+1)%5]) ; 
    执行思考操作 ;
  }
}

假设所有哲学家依次请求，并发运行：

• 0 号哲学家能拿到右手边的筷子，1 号哲学家想要左手边的筷子，但已被占用，因此阻塞等待。
• 2 号哲学家也能拿到右手边的筷子，同样会让 3 号哲学家阻塞
• 4 号哲学家拿到右手边的筷子
• 调度回到 0 号，0 号左手边的筷子被4号占用，阻塞
• 2 号拿到左手边的筷子，可以开始进餐
• 4 号拿到左手边的筷子，可以开始进餐
• 2 号和4 号进餐结束后，资源逐步被释放，其余哲学家将可以进餐

解决方案3：仅当两根筷子均可用时才拿

用信号量 mutex 保护“拿起左筷子+拿起右筷子”两步操作能原子执行，原子申请所有资源，或使用 AND型信号量，同时申请(Swait(chopstick[i], chopstick[(i+1)%5]))、同时释放资源(Ssignal(chopstick[i], chopstick[(i+1)%5]))

semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1 ;
//第i号哲学家的进程
Pi ( ) {   
  while (1) {
    P(mutex);
    P(chopstick[i]) ;   
    P(chopstick[(i+1)%5]) ; 
    V(mutex);
    执行吃饭操作 ;    
    V(chopstick[i]) ; 
    V(chopstick[(i+1)%5]) ; 
    执行思考操作 ;
  }
}

• 假设第 0 号哲学家申请吃饭，执行 P(mutex) 后调度，然后其他哲学家也申请，但都会被 P(mutex) 阻塞，无法占用资源。第 0 号哲学家的下次调度将可以获取 0,1号筷子完成进餐
• 假设第 0 号哲学家获得0,1筷子后，执行吃饭过程中被调度，此时如何哲学家都能执行 P(mutex) 不被阻塞。且2，3号能申请其他筷子的所有权。但1号和4号哲学因为P(chopstick[i])和P(chopstick[(i+1)%5])尚未释放会被阻塞

管程机制

虽然信号量机制是方便高效的进程同步机制，但每个想要访问临界资源的进程都必须自备同步操作wait(S)和signal(S)，这会导致大量的同步操作分散在各进程中，维护麻烦，且使用不当会造成死锁。

管程（Monitor）使用面向对象的思想，将共享的数据结构及其操作过程封装在一个模块内(如 Java synchronized、Pthreads 条件变量)，通过管程的内部实现来保证同一时刻最多只有一个进程在执行访问临界资源的代码，并由编译器或运行时系统负责加锁/解锁操作，这样程序员无需手动编写 P/V 操作，其基本特征是：

• 管程内部封装好了共享数据结构以及访问这些数据结构的函数
• 各外部进程/线程只能通过管程提供的特定函数入口才能访问共享数据结构
• 同一时刻最多只有一个进程/线程访问这些共享数据结构
• 各进程互斥访问管程的操作由编译器或者运行环境负责实现执行

死锁

死锁的定义与原因

资源分类

死锁的产生通常源于多个进程对资源的争夺，资源根据是否可重用大致分为：

• 可重用资源：可供用户重复使用的资源，其在系统中的单元数目相对固定，一次只能分配给一个进程使用，不允许多进程共享，进程在运行期间既不能创建也不能删除它，它的使用包含请求、使用、释放三个步骤，这类资源有打印机、磁带机等
• 可消耗资源：又称为临时性资源，它在进程运行期间由进程动态地创建和消耗(通常由生产者进程创建，消费者进程消耗)，其单元数目在进程运行期间可以不断变化，进程在请求并消耗该资源后，不再将其返回给该资源类中(如资源缓冲区中)，这类资源包括进程间通信的消息等

根据是否可抢占又分为：

• 可抢占资源：进程在获得这类资源后，依旧可能会被其他进程或系统抢占，如：优先级高的进程抢占优先级低进程的处理机；如：挂起进程被换出到硬盘上，其主存资源被其他进程抢占。这类资源有CPU、主存等，这类资源不会引起死锁
• 不可抢占资源：一旦系统把资源分配给该进程后，不能强行收回，只能等待进程自行释放，如：如果将正在进行刻录的刻录机分配给另外一个进程，必然导致光盘的损坏，因此打印机、磁带机属于这类资源

死锁的定义

死锁（Deadlock）指多个进程（或线程）因竞争资源而造成的一种相互等待状态，或者说一组进程因竞争资源而造成的永久阻塞现象，若无外力作用，它们都将无法再向前推进。

传统死锁通常描述多个进程之间因资源竞争产生的循环等待，但在现代操作系统中有以下特殊情况：

• 单个进程内部的多个线程也会死锁，如：同一进程中的多个线程分别持有不同资源，并相互等待对方释放资源，形成循环等待。
• 单线程形成自锁（self-deadlock），如：单线程重复申请自己已经持有的资源而陷入等待
  如：单线程持有一个不可重入互斥锁，第二次再次请求lock()，且锁的释放在第二次请求之后，但该线程会在第二次请求lock()就进入阻塞状态，无法执行到unlock() lock(mutex); ... lock(mutex); // 再次加锁 unlock(mutex);

产生死锁的必要条件

产生死锁必须同时具备以下四个必要条件，只要其中任意一个条件不成立，死锁就不会发生：

• 互斥条件（Mutual Exclusion）：某资源在同一时间内只能被一个进程占用，不能被多个进程同时访问，只有竞争想要互斥访问的资源才会导致死锁，如果资源可以共享使用，则不会因为竞争该资源产生死锁
• 请求和保持条件（Hold and Wait）：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放
• 不可抢占条件（No Preemption）：进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完时由自己释放，又称为不可剥夺条件
• 循环等待条件（Circular Wait）：发生死锁时，必然存在一个进程资源的循环等待链，但发生循环等待时不一定死锁(如：一组进程循环等待，但随时会有循环外的进程提供资源来终止该循环等待)

产生死锁的原因

死锁的产生主要有两个方面的原因:

• 竞争不可抢占资源、消耗性资源
• 进程推进顺序不当，导致进程请求和释放资源的顺序不当，使系统进入 了不安全区

死锁的处理策略

针对死锁问题，通常有以下四种基本处理策略：

• 预防死锁：通过设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个，从而防止死锁的发生
• 避免死锁：在资源的动态分配过程中，用某种方法防止系统进入不安全状态。最典型的算法是银行家算法
• 检测死锁：通过资源分配图等工具检测系统是否处于死锁状态
• 解除死锁：当检测到死锁发生后，采取相应措施解除死锁，常用方法包括：抢占资源(从其他进程中抢占足够数量的资源，分配给死锁进程)、终止进程(终止一个或多个死锁进程，以打破循环等待)

预防死锁

通过设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个，从而防止死锁的发生

破坏互斥条件

互斥条件通常是非共享设备的必须条件，反而需要加以保证，但在某些场景下，仍然可以将互斥使用的资源改造为可以共享使用的资源，如：通过假脱机(通过SPOOLing等技术实现)，将独占设备在逻辑上改造为共享设备

破坏不可抢占条件

当一个保持了不可抢占资源的进程，提出新的资源请求而无法得到满足时，它必须放弃已经持有的资源，等到需要时再重新申请，从而破坏其不可抢占条件。但该策略有以下缺点：

• 需要进程释放已经获得的资源，可能会造成进程前一阶段的工作失效
• 进程的需求可能被无限推迟，造成进程“饥饿”
• 进程反复申请、释放资源，会增加系统开销，降低吞吐量

破坏请求和保持条件

有以下策略：

• 静态分配法：进程在运行前一次性申请它所需要的资源，该策略会让进程在整个运行期间持有资源，而有些资源可能只在运行初期或末期才使用，这些资源会被严重浪费；此外，进程只有在一次性申请到所有资源后才能运行，可能导致某些资源长时间获取不到而导致进程“饥饿”
• 动态分配：进程只获得运行初期所需的资源，然后在运行过程中逐步释放用完的资源，并请求新的资源

破坏循环等待条件

使用顺序资源分配法：首先给系统中的资源编号，每个进程只有已占有小编号的资源时，才有资格申请更大编号的资源，而不允许持有大编号资源的进程逆向申请小编号资源。假如某进程已持有大编号的资源，又想申请小编号资源时，必须先释放所有具有更高编号的资源，以此避免环路的出现。该策略不方便增加新的设备，且不同场景/公司会有不同编号，不利于用户自主编程。

避免死锁

在死锁避免方法中，把系统状态分为安全状态和不安全状态，系统处于安全状态下，一定不会发生死锁，但如果系统进入不安全状态，则有可能发生死锁(死锁发生时一定处于不安全状态，但不安全状态不一定产生死锁)。

安全状态：如果系统按照安全序列分配资源，直至满足每个进程对资源的最大需求，使得每个进程都能顺利完成，则此时系统处于安全状态，系统中的安全序列可能有多个。

银行家算法

银行家算法由荷兰学者Dijkstra提出，其设计思想源于银行系统的信贷策略，后被运用到了OS中。其核心思想为：每一个进程在进入系统时，必须先申明运行过程中所需要资源的最大数量，且不应超过系统拥有的资源总量。当进程申请资源时，系统首先通过算法判断该次分配是否会导致系统进入不安全状态，若会，则暂不分配，让进程等待；若不会，则予以分配。

银行家算法的数据结构

OS中的资源通常有多种类型，这些资源的数量通常用一个向量(或数组)来表示，由此银行家算法有以下数据结构：

• 可利用资源向量Available：是一个长为m的数组，表示m类资源的可用数量，初始值为系统中该类资源的最大可用数量
• 最大需求矩阵Max：是一个 n * m的矩阵，表示系统中 n 个进程对 m 类资源的最大需求
• 分配矩阵Allocation：一个 n * m的矩阵，表示已经为 n 个进程分配的 m 类资源的数量
• 需求矩阵Need：一个 n * m的矩阵，表示 n 个进程各自还需要的资源数量，第 i 个进程还需的资源数量表示为：Need[i,j] = Max[i,j] - Allocation[i,j]

算法步骤

设Request是进程i的请求向量，当进程发出资源请求后，按下述步骤检查：

1. 如果 Request ≤ Need 则转向步骤2；否则出错，因为它所需资源数超出了它所宣布的最大值
2. 如果 Request ≤ Available，则转向步骤3；否则说明系统所剩资源不够，进程 i 需要阻塞等待
3. 系统试探性将进程申请的资源分配给它，并修改以下数据结构的值：

   • 系统剩余资源：Available = Available - Request;
   • 进程i已经获得的资源：Allocation = Allocation + Request;
   • 进程还需要的资源：Need = Need - Request;

4. 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程i ，否则分配失效，让进程阻塞等待

安全性算法

安全性算法用于判断系统是否处于安全状态，其核心步骤是检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并试探把该进程持有的资源全部回收。不断重复上述过程，看最终是否能让所有进程都加入安全序列。

示例

死锁的检测

死锁预防和死锁避免通过限制资源申请方式或在资源分配前进行安全性判断的方式从源头避免死锁的发生，但这些方式会一定程度降低系统资源的利用率和并发度。

死锁检测策略允许系统进入死锁状态，但会通过检测机制及时发现死锁，并采取相应措施予以解除。死锁检测不是实时进行的，通常在以下时机触发：

• 定时检测
• 资源请求失败时触发
• CPU 利用率下降时检测
• 用户手动触发

资源分配图

资源分配图是一种有向图，用于描述系统中进程与资源之间的请求和分配关系，方便分析死锁是否产生，资源分配图由以下内容构成：

• 使用圆圈代表一个进程
• 用方框代表一类资源，方框中的点代表资源数量
• 请求边：由资源指向进程，表示该资源的一个实例已分配给该进程
• 分配边：由进程指向资源，表示该进程正在请求该资源的一个实例

loading

如上图，表示

• 进程P1已经获得了两个R1资源，并请求一个R2资源
• 进程P2已经获得了一个R1和一个R2资源，并请求一个R1资源

死锁检测流程

• 在资源分配图中，找出既不阻塞又不是孤点的进程Pi(即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如上图中，P1和P2都有有向边与它们相连，都不是孤点。P1和P2都在请求新资源，R1没有空闲资源，R2有一个空闲资源，因此P1可以获得资源R2，不会被阻塞，P2会被阻塞)，进程Pi能继续运行直至完成，然后释放它所占有的所有资源。这相当于消去它所有的请求边和分配边，使之称为孤立的结点。
• P1释放所有资源后，可使P2获得资源而继续运行，直至P2完成并释放其所有资源，随后也可以消去其所有请求边和分配边
• 重复上述步骤，若是能消去所有边，使所有进程结点都称为孤点，则称该图是可完全简化的

死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

死锁的解除

用死锁检测算法化简资源分配图后，还连着边的进程即为死锁进程，一旦检测出死锁的发生，就应该立即解除死锁，解除死锁的主要方法有：

• 剥夺资源：挂起(换出外存上)某些死锁进程，并抢占它的资源，将这些资源分配给其他死锁进程，以打破循环等待
• 终止进程：终止一个、多个甚至所有死锁进程，剥夺这些进程的资源。这种方式的优点是实现简单，但有些进程可能已经运行了很长时间，已经接近结束了，如果终止需要重来，所付出的代价可能会很大。因此终止进程时需要考虑进程优先级、已运行时间和完成所需时间、已占用资源数、进程类型等因素