操作系统

• 1: 计算机系统概述
• 1.1: 操作系统概念
• 1.2: 程序运行环境
• 1.3: 操作系统结构
• 2: 进程管理
• 2.1: 进程和线程
• 2.2: 处理机调度
• 2.3: 同步和互斥
• 2.4: 经典同步问题
• 2.5: 死锁
• 3: 内存管理
• 3.1: 内存管理概念
• 3.2: 虚拟内存管理
• 4: 文件管理
• 4.1: 文件
• 4.2: 目录
• 4.3: 文件系统
• 5: I/O管理
• 5.1: I/O设备
• 5.2: 设备管理
• 5.3: 磁盘

1 - 计算机系统概述

# 操作系统基础

## 操作系统的基本概念

## 操作系统发展历程

## 程序运行环境

- CPU运行模式：内核模式、用户模式
- 中断和异常的处理
- 系统调用
- 程序的链接和装入
- 程序运行时的内存映像与地址空间

## 操作系统结构

- 分层、模块化
- 宏内核、微内核
- 外核

## 操作系统引导

## 虚拟机

1.1 - 操作系统概念

概念

操作系统是计算机系统中的一个核心软件组件，负责管理和控制计算机硬件，为用户和应用程序提供服务。

操作系统特征

1. 并发（Concurrence）：操作系统具备同时处理和调度多个程序的能力。
2. 共享（Sharing）：系统中的资源可供内存中多个并发的进程共同使用。
3. 虚拟（Virtual）：将物理的实物虚拟为逻辑上的对应物。
4. 异步（Asynchronism）：任务可以不按固定的顺序执行，因此同一操作的结果可能因执行的时序而异。

目标和功能

• 作为用户语句计算机硬件系统之间的接口。
• 作为计算机系统资源的管理者。
• 实现了对计算机资源的抽象。

发展历程

1. 手工操作阶段：
   • 时间背景：计算机的早期阶段。
   • 特点：没有操作系统，用户直接使用计算机硬件。
   • 操作方式：用户在一个时刻将自己的程序载入计算机，然后执行。执行完毕后，将结果记录并释放计算机。
   • 问题：效率低，CPU大部分时间处于空闲状态。
2. 批处理操作系统：
   • 单道批处理系统：
     • 特点：系统一次只执行一个任务。完成后再执行下一个。
     • 操作方式：用户的多个作业被收集到一个作业队列中，操作系统按照队列的顺序逐一执行。
     • 问题：CPU利用率仍然不高，因为在I/O操作时，CPU仍然处于空闲状态。
   • 多道批处理系统：
     • 特点：在内存中同时加载多个作业，并使它们共享CPU。
     • 操作方式：当一个作业进行I/O操作时，CPU可以切换到另一个作业，从而提高了CPU的利用率。
     • 优势：提高了系统吞吐量和CPU利用率。
3. 分时操作系统：
   • 时间背景：20世纪60年代。
   • 特点：允许多个用户通过终端同时访问计算机。
   • 操作方式：操作系统为每个用户提供了一个“虚拟机”的概念，使每个用户感觉自己独占了整个系统。实际上，系统在用户之间快速切换，为每个用户提供少量的CPU时间。
   • 优势：提高了交互性和多用户并发访问的能力。
   • 示例：Unix操作系统在其初期就是一个分时系统。
4. 实时操作系统：
   • 特点：系统必须在严格的时间限制内响应外部输入。
   • 分类：
     • 硬实时系统：不满足时限会导致严重的后果，如飞行控制系统。
     • 软实时系统：不满足时限可能会降低系统的性能，但不会导致灾难，如多媒体播放器。
   • 操作方式：实时操作系统的任务调度是基于优先级的，且通常会预先定义每个任务的执行时间。
   • 优势：满足特定应用场景的实时需求，如嵌入式系统和工业控制系统。

操作系统引导

引导流程

简单而言，包含如下步骤：

从ROM中读取BIOS、读取MBR中的分区引导程序、执行bootloader、加载操作系统

具体而言

1. 电源开机（Power-On）：
   • 当计算机电源被打开时，系统会执行加电自检（Power-On Self-Test, POST）。
   • 这是由系统的BIOS或UEFI固件负责的，其目的是检查并确保基本硬件组件（如CPU、RAM和主板）处于工作状态。
2. BIOS/UEFI 阶段：
   • BIOS/UEFI会初始化并检查硬件。
   • 根据其配置，BIOS/UEFI会决定从哪个设备（例如硬盘、光盘、USB或网络）启动。
   • 之后，它会读取该设备的启动扇区。
3. 引导加载器（Bootloader）：
   • 启动扇区中包含的代码被执行。这通常是引导加载器的第一部分。
   • 引导加载器的主要任务是加载操作系统内核。它可能由多个阶段组成，特别是当操作系统存储在硬盘的非连续扇区时。
4. 加载操作系统内核：
   • 一旦引导加载器被执行，它会从文件系统中找到并加载操作系统的内核到RAM中。
5. 内核初始化：
   • 操作系统内核开始运行并进行自我初始化。
   • 它会检测和配置系统上的硬件资源，例如设置中断、初始化设备驱动、建立内存管理结构等。
6. 启动系统服务和守护进程：
   • 在内核初始化后，它会启动一系列的系统进程或服务来管理各种系统任务。

1.2 - 程序运行环境

CPU运行模式

CPU的两种运行模式：内核模式（又称为特权模式、系统模式或超级用户模式）和用户模式是操作系统设计中用于隔离系统关键任务与普通任务的机制，以提高系统的安全性和稳定性。

1. 内核模式（Kernel Mode）：
   • 当CPU运行在内核模式时，它可以执行所有的指令集和直接访问所有的硬件资源。
   • 操作系统的核心部分（即内核）通常会在这种模式下运行。这允许内核进行如管理内存、任务调度、直接硬件访问等关键操作。
   • 如果程序（通常是设备驱动）在内核模式下出现错误或异常，往往会导致整个系统崩溃或出现蓝屏等严重故障。
   • 由于其对硬件的直接访问能力，恶意软件如果能在内核模式下运行，可能会对系统造成严重的损害。因此，确保只有受信任的代码能在内核模式下执行是非常重要的。
2. 用户模式（User Mode）：
   • 当CPU运行在用户模式时，执行的代码受到严格限制，不能直接访问硬件或执行某些特权指令。
   • 大多数应用程序都是在用户模式下运行的。这样做的好处是，即使应用程序出现问题或崩溃，也不会直接影响到整个系统的稳定性。
   • 要从用户模式访问硬件或执行其他特权操作，应用程序必须通过系统调用（system call）来请求操作系统提供的服务。这样的设计提供了一层保护，确保了用户程序不能直接干扰系统的关键部分。

系统调用

系统调用（system call）是运行在用户模式的应用程序与操作系统内核之间的接口。当应用程序需要执行一些它在用户模式下不能直接完成的任务（如文件操作、网络通信、创建进程等）时，它可以通过系统调用来请求操作系统内核在内核模式下为其执行这些操作。

特点

• 特权级的转换：应用程序通常在用户模式下运行，而操作系统内核在内核模式下运行。系统调用提供了从用户模式到内核模式的一种安全的转换机制，这样内核可以代表应用程序执行特权操作。
• 系统调用的类型：常见的系统调用类型包括进程管理（如创建、终止进程）、文件操作（如打开、读取、写入、关闭文件）、网络通信、设备控制、内存管理等。
• 性能开销：执行系统调用涉及上下文切换，从用户模式到内核模式，然后再返回。这会带来一定的性能开销。因此，频繁地进行系统调用可能会影响应用程序的性能。

程序的链接

程序的链接是将编译后的代码模块（通常是目标文件）和其他所需的库组合在一起，生成一个可以执行的程序或库的过程。链接过程由链接器（linker）完成。

静态链接和动态链接

根据所使用的库的链接方式，链接可以分为静态链接和动态链接。

• 静态链接：
  • 当使用静态链接时，外部代码和库在链接阶段被整合到最终的可执行文件中。这意味着，如果程序使用了某个库的函数，那么这些函数的代码会被复制到最终的二进制文件中。
  • 结果是一个较大的可执行文件，因为它包含了所有必要的代码以独立运行。
• 动态链接：
  • 使用动态链接时，外部库不会被直接嵌入到最终的可执行文件中。相反，程序包含了对动态链接库（如Linux中的.so文件或Windows中的.dll文件）的引用。当程序启动时，这些库会被加载到内存中供程序使用。
  • 动态链接的库通常称为动态链接库（Dynamic Link Libraries，DLL）或共享对象（Shared Object

程序的装入

程序的装入是指将程序或进程的代码和数据从磁盘加载到主存（RAM）中的过程，使其准备好被CPU执行。装入过程在程序执行周期中是必不可少的一部分，通常由操作系统中的装入器（loader）完成。

绝对装入

适用于单道程序环境。在编译时，若知道程序驻留在内存的某个位置，则编译程序将产生绝对地址的目标地址。绝对装入程序按照装入模块的地址，将程序和数据装入内存。由于程序中的逻辑地址与实际地址完全相同，因此不需要对程序和数据的地址进行修改。

另外，程序中所用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。而通常情况下在程序中采用的是符号地址，编译或汇编时在转换为绝对地址。

可重定位装入

在多道程序环境下，多个目标模块的起始地址通常都从0开始，程序中的其他地址都是相对于起始地址的，此时应采用可重定位装入方式。根据内存的当前情况，将装入模块装入内存的适当位置。在装入时对目标程序中指令和数据地址的修改过程称为重定位，又因为地位变换通常是在进程装入时一次完成的，故称为 静态重定位。

当一个作业装入内存时，必须给它分配要求的全部内存空间，若没有足够的内存，则无法装入。此外，作业一旦装入内存，整个运行期间就不能在内存中移动，也不能再申请内存空间。

动态运行时装入

也称为 动态重定位。装入程序把装入模块装入内存后，并不立即把装入模块的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时进行。因此，装入内存后的所有地址都是相对地址。这种地址需要一个重定位寄存器的支持。

动态重定位的优点在于可以将程序分配到不连续的存储区；在程序运行之前可以只装入部分代码即可运行，然后在程序运行期间，根据需要动态申请分配内存。

1.3 - 操作系统结构

分层和模块化

操作系统的设计和结构在历史上经历了多种不同的方法和技巧，为了增加可维护性、灵活性和可扩展性。分层和模块化是操作系统设计中两种主要的技术方法。

• 分层结构：
  • 概念：在分层的操作系统中，系统被划分为多个层次或“层”，每层都为其上的层提供服务，并依赖于其下的层。
  • 优点：
    • 每层只需与其直接的上下层进行交互，简化了设计和调试。
    • 提高了灵活性，因为改变某一层的实现不会影响到其他层。
    • 有助于保护和安全性，因为较低的层（如硬件访问层）被封装起来，上层代码不能直接访问。
• 模块化结构：
  • 概念：模块化操作系统基于模块的概念，每个模块都有一个特定的功能，各个模块之间的交互通过定义良好的接口进行。模块化与面向对象编程中的封装和抽象概念类似。
  • 优点：
    • 易于维护和更新。如果某个模块需要更改或修复，可以独立于其他模块进行。
    • 提高了可扩展性。新的功能或模块可以相对容易地添加到系统中。
    • 增加了系统的可靠性和稳定性，因为每个模块的功能都被限定在明确的边界内。

微内核和宏内核

• 宏内核（Monolithic Kernel）：
  • 特点：
    • 在单一的地址空间中运行大部分系统服务，如设备驱动、文件系统、网络协议等。
    • 所有的内核服务都运行在内核态。
  • 优点：
    • 由于所有的服务都在同一个地址空间中运行，因此服务间的通信较快。
    • 传统上，宏内核系统比微内核系统性能更高。
  • 缺点：
    • 如果内核中的一个部分失败，整个系统都可能崩溃。
    • 随着功能的增加，内核可能会变得臃肿，导致维护困难。
  • 示例：传统的UNIX系统、Linux都是基于宏内核的。
• 微内核（Microkernel）：
  • 特点：
    • 只有最基本的服务（如基本的进程和线程管理、地址空间和IPC）运行在内核态。
    • 其他服务，如设备驱动、文件系统等，作为用户空间的独立进程运行。
    • 内核和服务间通过消息传递进行通信。
  • 优点：
    • 更高的系统稳定性。用户空间的服务（如驱动程序）如果崩溃，不会影响整个系统。
    • 更加灵活，允许在运行时更改或添加服务。
    • 更容易扩展和维护。
  • 缺点：
    • 由于需要频繁的上下文切换和消息传递，通常性能会稍逊于宏内核。
  • 示例：IOS是基于微内核的系统。

虚拟机

虚拟机（Virtual Machine, VM）是一种模拟真实计算机的软件实现，能够在物理机上模拟出多个和真实硬件环境相似的独立的虚拟计算机环境。每个虚拟计算机环境都可以运行独立的操作系统并运行应用程序，就好像它们在真实的物理机上一样。

Hypervisor，也称为虚拟机监视器（Virtual Machine Monitor, VMM），是一种在主机操作系统和虚拟机之间的中间软件层，它允许多个操作系统同时在同一台物理硬件上运行。Hypervisor的主要职责是创建、运行和管理虚拟机，同时提供硬件资源的抽象，从而使每个虚拟机都认为自己是唯一运行在物理硬件上的操作系统。

2 - 进程管理

# 进程管理

## 进程和线程

- 进程、线程概念
- 进程、线程状态和转换
- 线程的实现
- 进程、线程的组织和控制
- 进程间通信

## CPU调度和上下文切换

- 概念和目标
- 调度实现方式
- 调度算法
- 上下文及其切换机制

## 同步与互斥

- 概念
- 软件和硬件实现方法
- 锁
- 信号量
- 条件变量
- 经典同步问题

## 死锁

- 概念
- 死锁预防
- 死锁避免
- 死锁检测和解除

2.1 - 进程和线程

进程和线程

两者的对比

进程主要特点如下：

• 系统资源分配的基本单位： 进程拥有独立的系统资源，包括内存空间、文件描述符、CPU 时间片等，这些资源的分配由操作系统负责。

线程主要特点如下：

• 系统调度的基本单位： 多核处理器可以将系统中的不同线程调度到不同的CPU逻辑核心上，所以在同一个时刻，系统中的线程可能会在不同的逻辑核心上并行运行。

进程的状态

状态种类

1. 创建状态（New）：当进程被创建但还未分配资源或执行时，它处于创建状态。
2. 就绪状态（Ready）：在就绪状态中，进程已准备好执行，但由于操作系统调度算法或其他原因，尚未获得CPU时间片。
3. 运行状态（Running）：在运行状态中，进程正在执行指令并占用CPU。
4. 阻塞状态（Blocked）：当进程在等待某些事件发生时，如等待I/O操作完成或等待其他资源时，它会进入阻塞状态。在阻塞状态下，进程暂停执行，直到等待的事件发生。
5. 终止状态（Terminated）：当进程执行完毕或被操作系统终止时，它进入终止状态。

状态转化

1. 就绪状态到运行状态:
   • 调度: 当操作系统的调度器选择一个就绪状态的进程分配给处理器时，该进程就会从就绪状态转换到运行状态。
2. 运行状态到就绪状态:
   • 时间片用完: 如果系统使用时间共享调度，当进程的时间片用完，它会被中断并放回就绪队列。
   • 优先级更高的进程就绪: 在优先级调度算法中，如果一个优先级更高的进程变为就绪状态，当前运行的进程可能会被挂起。
   • 自愿放弃CPU: 进程可能主动放弃CPU，比如它发出了一个系统调用请求其他资源。
3. 运行状态到阻塞状态:
   • I/O请求: 进程进行I/O操作，由于I/O设备比CPU慢得多，进程会被挂起直到I/O完成。
   • 等待资源: 进程等待不可用的资源，如信号量、互斥锁等。
   • 等待事件: 如等待其他进程的信号、消息或者某个条件的发生。
4. 阻塞状态到就绪状态:
   • I/O完成: 当I/O操作完成，相应的进程会被移至就绪队列。
   • 资源获得: 进程所等待的资源变得可用，如获得了互斥锁。
   • 事件发生: 进程所等待的事件发生了，如接收到了另一个进程发出的信号。

进程内存空间

• 用户空间（User Space）：包含进程执行的用户程序代码和数据。在用户空间中，进程可以执行各种任务，如运行应用程序、访问文件系统等。用户空间对于应用程序是可见的，但对于操作系统中的核心功能是不可见的。
  1. 代码区（Text Segment）：也称为"可执行代码区"，存储了进程的可执行代码，包括程序的指令和只读数据。这个区域通常是只读的，因为程序的指令在运行时不应该被修改。
  2. 数据区（Data Segment）， 数据区分为两个子区域：
     • 初始化数据区（Initialized Data Segment）：存储全局和静态变量以及初始化的数据。这些变量在程序运行前就已经分配了内存并初始化。
     • 未初始化数据区（Uninitialized Data Segment）：也称为"BSS"（Block Started by Symbol）段，存储全局和静态变量，但这些变量没有显式的初始化值。操作系统会在程序启动时自动将这个区域初始化为零。
  3. 堆区（Heap）：堆区是动态分配内存的地方，用于存储程序运行时需要的变量和数据结构。在堆中分配的内存需要手动释放，以避免内存泄漏。
  4. 栈区（Stack）：栈区用于存储函数调用和局部变量。每个函数调用都会在栈上创建一个栈帧，栈帧包含了函数的参数、局部变量以及函数返回地址。栈是一种后进先出（LIFO）的数据结构，它的大小通常有限，由操作系统或编程语言定义。
  5. 内存映射区域（Memory Mapped Region）：这是一些操作系统或运行时库的扩展，用于存储动态链接库（DLL）和共享库的信息以及其他系统数据结构。
• 内核空间（Kernel Space）：内核空间包含了操作系统的核心代码和数据结构，如页表、调度程序和系统调用接口等。内核空间具有更高的特权级别，可以执行特权指令并且访问系统的各种资源，内核空间对于用户程序是不可见的。

进程间通信

• 共享内存（Shared Memory）：共享内存允许多个进程访问相同的物理内存区域，这样它们可以直接共享数据，而不需要复制数据。这是一种高效的通信方式，但需要谨慎管理共享数据以避免竞态条件。
• 管道（Pipes）：管道是一种单向通信方式，通常用于父子进程之间或兄弟进程之间的通信。有命名管道和匿名管道两种，匿名管道只能在有亲缘关系的进程之间使用。
• 消息队列（Message Queues）：消息队列是一种进程间通信的机制，允许进程通过消息来进行异步通信。消息队列通常由操作系统维护，可以支持多个读者和写者。
• 信号（Signals）：信号是一种轻量级的通信机制，用于通知进程发生了某些事件。进程可以发送信号给其他进程，比如终止信号、挂起信号等。
• 套接字（Sockets）：套接字是一种通用的进程间通信方式，通常用于不同计算机之间的网络通信。它支持多种协议，如TCP和UDP，可以实现客户端-服务器通信。
• 信号量（Semaphores）：信号量是一种计数器，用于控制多个进程对共享资源的访问。信号量可以用于解决竞争条件和进程同步的问题。

用户级线程和内核级线程

• 用户级线程（user level thread）：用户级线程是在用户空间中创建和管理的线程，不依赖于操作系统的内核支持。这些线程由用户程序或用户级线程库管理，而不需要操作系统内核的介入。
• 内核级线程（kernel level thread）：内核级线程是由操作系统内核管理和调度的线程。每个内核级线程都有自己的内核数据结构（例如，进程控制块，PCB），由操作系统内核负责创建、销毁和调度。

这个东西其实不太好理解，以真实的应用场景为例，当我们使用linux的pthread library创建线程时，这个线程其实是由操作系统进行管理和调度的，并不需要用户程序进行管理，所以当我们使用系统调用创建线程时，可以理解为创建的实际是内核级线程。

那么用户级线程在实际应用中到底是怎样的呢，根据其定义，用户级线程由程序或用户级线程库管理，这里举实际的例子的话，就是go语言中的goroutine或者python异步库asyncio中的的coroutine，这两者都是协程模型的实现，协程可以理解为更轻量的线程，协程库在用户空间内实现了一个调度机制，可以在系统执行一个线程的时间片内，创建多个协程并且在这个时间片内调度多个协程执行。由于协程的切换是在用户空间内实现的，不需要系统调用，所以效率更高，占用的资源更少。

用户级线程和内核级线程的映射方式（这里了解即可）包含多对一、一对一、多对多模型：

视频讲解

2.2 - 处理机调度

调度的指标

1. CPU利用率:
   • 定义：它是CPU活跃时间与总观察时间的比率。通常表示为百分比。
   • 说明：CPU利用率是衡量CPU工作效率的一个关键指标。如果CPU利用率接近100%，则表示CPU几乎一直在工作。如果利用率很低，可能意味着CPU有大量的空闲时间。
2. 系统吞吐量:
   • 定义：在单位时间内系统完成的工作量或进程数。
   • 说明：高吞吐量意味着系统能在短时间内完成更多的工作或处理更多的进程。
3. 周转时间:
   • 定义：进程从提交到完成所经过的总时间。这包括了进程在等待、执行以及在其他各种队列中的时间。
   • 说明：较短的周转时间通常是预期的，因为这意味着进程更快地得到处理和完成。
4. 等待时间:
   • 定义：进程在就绪队列中等待CPU时间的总时间。
   • 说明：等待时间不包括任何I/O操作或其他需要的资源的等待时间。较低的等待时间是理想的，因为这意味着进程花费较少的时间只是在等待执行。
5. 响应时间:
   • 定义：从提交一个请求到收到第一个响应所经过的时间。在交互式系统中，响应时间通常非常关键。
   • 说明：对于交互式任务（例如在GUI系统中的任务），响应时间尤为重要，因为用户通常期望快速的反馈。较短的响应时间提供了更好的用户体验。

系统调度过程

进程调度是计算机操作系统中的一种核心功能，它决定了哪个进程应该在给定的时间段内使用处理器。为了有效地管理和调度进程，操作系统通常采用多级调度机制。这些调度机制分为三个层次：高级调度、中级调度和初级调度。

1. 高级调度（长程调度，Long-term Scheduling）:
   • 功能：高级调度主要决定哪些进程应当被加载到内存中成为一个可运行的进程。
   • 主要目标：保持内存中适当数量的进程。不要过多也不要过少。
   • 当进程首次进入系统时，它们首先被放置在磁盘的一个区域，称为作业池。高级调度器从作业池中选择进程，根据某种策略将其加载到内存中，从而使其成为一个可运行的进程。
2. 中级调度（中程调度，Mid-term Scheduling）:
   • 功能：中级调度涉及到进程的暂停和重启。当系统的进程数超过内存容量时，中级调度器可能会将一些进程从内存移出到磁盘上（这称为交换或页面置换），从而为新的或等待的进程腾出空间。
   • 主要目标：为高级和初级调度器优化内存使用。
   • 中级调度器在必要时将进程从内存交换到磁盘，并在适当的时机将其交换回内存。
3. 初级调度（短程调度，Short-term Scheduling）:
   • 功能：初级调度决定哪个进程应当被赋予CPU时间片，即决定下一个运行在处理器上的进程。
   • 主要目标：确保CPU的高效利用。
   • 它的决策频率非常高，因为在多任务环境中，每个时间片的长度可能只有几十毫秒。因此，初级调度器必须是非常快速的。

调度的实现

调度器

调度器/调度程序（scheduler）:

• 调度器是操作系统中负责决定下一个要执行的进程或线程的部分。
• 基于特定的调度算法（如轮转、优先级调度、短作业优先等），它决定哪个进程或线程应当获得CPU时间。
• 调度器通常分为长程、中程和短程调度器，如前文所述。

调度时机

调度的时机可能包括以下情况：

• 进程进入或退出系统
• 进程从运行状态变为阻塞状态
• 或者一个时间片结束。

调度方式

• 抢占式调度（Preemptive）：在这种调度方式下，当一个进程正在执行时，操作系统可以中断该进程的执行并将CPU分配给另一个进程。这常常发生在一个更高优先级的进程变为就绪状态时。
• 非抢占式调度（Non-Preemptive）：在这种方式下，一旦CPU分配给一个进程，它会继续运行直到完成或者转为非运行状态（例如，等待I/O操作）。

闲逛进程

当没有其他进程可以执行时，系统会运行一个特殊的进程，称为闲逛进程或空闲任务。它的主要任务通常是简单的：使CPU保持忙碌。在某些系统中，闲逛进程可能会执行一些简单的任务，如背景清理。该进程通常具有最低的优先级，因此只有在没有其他进程可以运行时才会执行。

两种线程的调度

• 内核级线程：由操作系统内核直接支持的线程。操作系统知道这些线程的存在，并可以直接进行调度。
• 用户级线程：完全在用户空间中实现的线程，不需要内核的介入。
• 对于内核级线程，操作系统可以直接调度它们，并可以利用多核或多处理器的优势。
• 对于用户级线程，因为内核不知道它们的存在，所以内核无法直接调度它们。线程之间的上下文切换可能比内核级线程更快，但在多处理器系统中，它们可能无法充分利用所有的处理器。

调度算法

1. 先来先服务

先来先服务（First-Come, First-Served，FCFS）按照进程到达的顺序分配CPU时间。先到达的进程先执行，直到完成或阻塞。

2. 最短作业优先

最短作业优先（Shortest Job First，SJF）该算法选择具有最短执行时间的进程，以最小化平均等待时间。它需要知道每个进程的执行时间，通常在实际系统中难以获得。

3. 优先级调度

进程被分配一个优先级，CPU总是分配给具有最高优先级的进程。这种算法可以是静态的（进程创建时分配优先级）或动态的（根据进程的行为和状态进行动态调整）。

4. 最高响应比优先

最高响应比优先（Highest Response Ratio Next，HRRN）这种算法根据进程的等待时间和执行时间比来选择下一个执行的进程，以提高响应性。

5. 时间片轮转

时间片轮转（Round Robin，RR）这是一种基于时间片的算法，每个进程被分配一个固定的时间片，当时间片用完时，进程被放回队列尾部，下一个进程开始执行。这样可以实现公平的CPU时间分配。

6. 多级反馈队列

多级反馈队列（Multilevel Feedback Queue）这是一种混合算法，将进程分为多个队列，每个队列有不同的优先级和时间片大小。新创建的进程进入最高优先级队列，如果没有完成，它将下降到较低优先级的队列，直到完成。

上下文及其切换机制

进程的上下文是进程执行的环境。在操作系统中，它指的是一个进程在特定时间点上的系统状态，包括多种信息，这些信息使得进程在被中断后可以再次恢复并继续执行。当操作系统从一个进程切换到另一个进程时，它会保存当前进程的上下文并恢复下一个进程的上下文。这个过程被称为上下文切换。

进程上下文内容

1. 寄存器值：这包括通用寄存器、程序计数器、栈指针、状态寄存器等。它们保存了进程的当前执行位置和状态。
2. 程序计数器：表示进程的下一个指令的位置。
3. 虚拟内存信息：这包括进程的页表、页目录等信息，描述了进程的地址空间布局。
4. I/O状态信息：包括打开的文件描述符、网络连接、I/O指针等。
5. CPU调度信息：例如进程优先级、计划器状态等。
6. 资源使用情况：这可能包括该进程所使用的各种资源的跟踪信息，如内存、文件句柄等。

上下文切换流程

1. 保存当前进程的状态：操作系统保存当前正在运行的进程的上下文。这意味着它会将当前的寄存器值、程序计数器等保存到进程的进程控制块（PCB）中。
2. 选择下一个要执行的进程：调度器决定下一个要运行的进程。
3. 恢复下一个进程的状态：操作系统从新进程的PCB中恢复其上下文信息，包括寄存器值、程序计数器等。
4. 开始执行新进程。

2.3 - 同步和互斥

实现互斥的方法

软件互斥

Peterson’s Algorithm

Peterson’s Algorithm 基于两个线程之间的竞争条件来实现互斥。它使用两个布尔变量和一个整数变量，分别表示两个线程的意愿和当前正在运行的线程。通过这些变量的协作，可以确保只有一个线程能够进入临界区。

Peterson’s Algorithm 通常用于理论教学和理解互斥原理，但在实际多线程编程中并不常用，因为它只适用于两个线程之间的互斥。

// 初始化
bool flag[2] = {false, false};  // 两个线程的意愿
int turn = 0;                   // 当前运行的线程（0 或 1）

// 线程 1 希望进入临界区
void thread0() {
    flag[0] = true;
    turn = 1; // 通知线程 2 你可以运行了
    while (flag[1] && turn == 1) {
    // 等待线程 2 退出临界区或让出 CPU
    }
    // 进入临界区
    // ...
    // 退出临界区
    flag[0] = false;
}

// 线程 2 希望进入临界区
void thread1() {
    flag[1] = true;
    turn = 0; // 通知线程 1 你可以运行了
    while (flag[0] && turn == 0) {
    // 等待线程 1 退出临界区或让出 CPU
    }
    // 进入临界区
    // ...
    // 退出临界区
    flag[1] = false;
}

硬件互斥

硬件互斥是一种在计算机体系结构层面实现的互斥机制，通常用于保护共享资源，以确保在多核处理器系统中同时只有一个线程或核心能够访问这些资源。硬件互斥的实现通常依赖于底层硬件支持，包括原子指令和特殊的寄存器。

原子指令：原子指令（Atomic Instructions），也称为原子操作或原子操作指令，是计算机体系结构中的一种特殊指令，它们被设计为在单个处理器指令周期内执行完毕，不会被中断或其他线程干扰。

这里主要掌握 TAS 和 CAS 两种原子指令即可：

• Test-and-Set（TAS）指令：TAS 指令用于原子地设置一个内存位置的值，并返回该位置的先前值。互斥锁可以用一个整数变量表示，0 表示锁是空闲的，1 表示锁已经被占用。锁定操作可以使用 TAS 指令来尝试将锁的值从 0 设置为 1，如果返回的先前值为 0，则表示锁定成功。解锁操作将锁的值设置为 0。
• Compare-and-Swap（CAS）指令：CAS 指令用于原子地比较内存位置的当前值与一个预期值，并只有在它们匹配时才会更新该位置的值。互斥锁可以用 CAS 指令来实现。例如，锁定操作可以使用 CAS 指令来将锁的值从 0 修改为 1，如果 CAS 操作成功，则表示锁定成功。解锁操作可以使用 CAS 来将锁的值从 1 修改为 0。

利用 TAS 来实现互斥：

• TAS
• CAS

// TAS 原子指令相当于以下函数被原子性地执行
bool TestAndSet(bool *lock) {
    bool old = *lock;
    *lock = true;
    return old;
}

// 通过 TAS 实现自旋锁
void acquire_lock(bool *lock) {
    while (!TestAndSet(lock)) {
        // 锁被占用，继续自旋等待
    }
}

void release_lock(bool *lock) {
    *lock = false;
}

// CAS 原子指令相当于以下函数被原子性地执行
bool CompareAndSet(bool *lock, bool expected, bool new_value) {
    if (*lock == expected) {
        *lock = new_value;
        return true;  // 操作成功
    } else {
        return false; // 操作失败
    }
}

// 通过 CAS 实现自旋锁
void acquire_lock(bool *lock) {
    while (!CompareAndSet(lock, false, true)) {
        // 锁被占用，继续自旋等待
    }
}

void release_lock(bool *lock) {
    *lock = false;
}

C 语言通过 TAS 实现自旋锁

互斥锁

互斥锁（Mutex，来源于“mutual exclusion”，即相互排斥）是并发编程中用于确保多个线程不会同时访问共享资源或执行特定代码段的同步原语。互斥锁提供了一种机制，确保在任何时刻只有一个线程能够持有该锁，从而确保共享资源的安全访问。

基本特点：

• 互斥性：任何时候，只有一个线程可以持有互斥锁。其它试图获取该互斥锁的线程将被阻塞，直到持有锁的线程释放该锁。
• 所有权：只有锁的持有者才能释放它。这确保了非持有者不能误释放锁。

基本操作：

• 锁定（Lock 或 Acquire）：当线程试图获取互斥锁时，如果锁已被其他线程持有，则该线程将被阻塞，直到锁被释放。
• 解锁（Unlock 或 Release）：持有互斥锁的线程在完成其对共享资源的访问后，应该释放锁以使其他线程可以获取锁。

线程是如何在互斥锁操作中被阻塞或唤醒的？

当线程尝试获取一个已经被持有的锁时，它会被挂起，并且不会消耗 CPU 资源。只有当锁被释放并且该线程被选择为下一个获取锁的线程时，它才会恢复执行。这样的机制确保了临界区的互斥访问，同时也尽量减少了不必要的 CPU 浪费。

• 阻塞：
  • 当线程尝试获取一个已经被其他线程持有的互斥锁时，该线程会进入一个等待状态，也称为阻塞状态。
  • 操作系统维护了一个与该互斥锁关联的等待队列。尝试获取锁但未成功的线程会被放入这个队列中。
  • 被阻塞的线程会从“运行”状态转为“等待”或“睡眠”状态。这意味着该线程将不再获得 CPU 时间，直到它被唤醒。
• 唤醒：
  • 当持有互斥锁的线程释放该锁时，操作系统会检查与该锁关联的等待队列。
  • 通常，队列中的下一个线程（取决于调度策略，可能是队列的第一个线程或其他）会被选中并被唤醒，允许它获取锁。
  • 被唤醒的线程转换为“就绪”状态，并在适当的时候由调度器重新分配 CPU 时间，从而继续执行。

需要注意的是，上述描述是一个高级和简化的过程。实际的操作系统实现可能会有更多的优化和特性，如优先级反转控制、超时机制、自旋锁等。

条件变量

条件变量（Condition Variable） 是一种同步原语，用于线程之间的有条件同步。它允许线程等待某个条件成立，同时释放已获取的锁，这样其他线程可以获取锁并可能更改共享数据的状态，使得条件成立。

用途

• 实现同步操作：有时，线程需要等待某个条件才能继续执行。条件变量使线程可以等待，直到其他线程更改了共享数据的状态并满足了该条件。
• 避免忙等（busy-waiting）：而不是使线程不停地轮询共享数据以检查条件是否满足（这会浪费 CPU 资源），条件变量使线程可以休眠直到条件满足。

操作

• wait()：这个操作做两件事。首先，它会释放与条件变量关联的锁，从而使其他线程可以获取锁并更改共享数据的状态。其次，它会使调用它的线程休眠，直到另一个线程来唤醒它。
• signal()：这个操作用于唤醒等待在条件变量上的某个线程。如果多个线程在等待，通常只有一个线程被唤醒（但这取决于具体实现）。唤醒的线程将重新获取锁并从其调用 wait() 的地方继续执行。
• broadcast() 或 notify_all()：这个操作唤醒所有等待在条件变量上的线程。当共享数据的状态变化可能影响多个等待的线程时，这很有用。

信号量

信号量（Semephore）是一个同步原语，相比锁，信号量可以解决一些更加复杂的同步问题。

在逻辑上我们将信号量理解为一个整数值，信号量提供两个原子操作：

• P （proberen，荷兰语的“尝试”之意）
• V （verhogen，荷兰语的“增加”之意）。

P 操作

P 操作也被称为 wait 操作， P 操作的具体流程如下：

• 如果信号量值大于 0，则减少信号量的值，并继续执行后续代码。
• 如果信号量值为 0，则执行 P 操作的线程将被阻塞，直到信号量变为正值。

简而言之，就是尝试（正如荷兰语的原义）将信号量的值减一，若不至于将信号量的值减为负数。 则尝试成功，线程可继续执行后续代码。若尝试失败，则线程被阻塞。

V 操作

V 操作也被称为 signal 操作， V 操作的具体流程如下：

增加信号量的值。如果有任何线程因为 P 操作被阻塞，则选取一个被阻塞的线程（选择机制可能依赖于具体的实现）并唤醒它。 接着继续执行后续代码。

信号量是如何实现的

只需要在逻辑上理解信号量的机制即可，信号量中有维护有一个整数值，并且与一个阻塞队列和运行队列相关联。

• 当线程的 P 操作执行成功后，线程被加入信号量的运行队列。
• 当线程的 P 操作执行失败后，线程被加入信号量的阻塞队列。
• 当线程的 V 操作执行成果后，线程被从运行队列中移除，并尝试从阻塞队列中选取线程继续执行 P 操作。

线程是如何在 PV 操作中被阻塞或唤醒的？

当一个线程尝试执行 P 操作并发现信号量的值为 0 或负数时，该操作会导致该线程阻塞。具体地说，线程会被移出运行队列并放入一个特定的阻塞队列。这个阻塞队列是与信号量关联的，其中保存了因该信号量被阻塞的所有线程。

当其他线程对该信号量执行 V 操作并增加其值时，一个被阻塞的线程（或多个，具体取决于实现和信号量的增量）会从等待队列中被选出并被唤醒，随后它可以继续执行。

信号量应用

用信号量实现同步操作

先执行 P1 中的 code1，再执行 P2 中的 code2：

semphore S = 0;

P1() {
    code1;       // 先执行 code1
    V(S);        // 告诉线程 P2，code1 已经完成
    ...
}

P2() {
    ...
    P(S);        // 检查 code1 是否完成
    code2;       // 检查无误，运行 code2
}

用信号量实现互斥操作

当信号量的初始值为 1 时，可以把信号量当作锁使用：

semaphore S = 1;

P1() {
    P(S);
    // critical section
    V(S);
}

P2() {
    P(S);
    // critical section
    V(S);
}

用信号量实现前驱关系

semphore a1 = a2 = b1 = b2 = c = d = e = 0;

S1() {
    ...;
    V(a1); V(a2);
}

S2() {
    P(a1);
    ...
    V(b1); V(b2);
}

S3() {
    P(a2);
    V(e);
}

S4() {
    P(b1);
    V(c);
}

S5() {
    P(b2);
    V(d);
}

S6() {
    P(c); P(d); P(e);
}

管程

管程（Monitor）是一个并发编程中的同步原语，用于封装共享数据及其操作以确保对共享数据的并发访问是安全的。它提供了一种结构化的方式来封装共享数据、对数据的操作方法以及同步机制（如条件变量）。

管程的核心思想是仅在给定的时间允许一个线程进入并执行管程中的代码，从而实现对共享资源的互斥访问。当其他线程试图进入同一管程时，它们将被阻塞，直到当前执行的线程退出管程。

管程基本组成：

• 共享数据：管程封装了需要被多个线程共享和访问的数据。
• 方法：定义了如何操作共享数据的函数或方法。这些方法是唯一可以访问和修改共享数据的方式。
• 条件变量：用于控制线程的执行顺序，让线程在某些条件下等待，或通知等待的线程继续执行。

管程和锁、信号量的区别？

锁和信号量是更低级的同步原语。尽管它们非常有用并且广泛应用，但在某些情况下直接使用它们可能导致代码复杂且难以理解。另外，使用这些低级原语可能会增加死锁、饥饿或其他同步问题的风险。

管程的设计是为了将这些低级的细节隐藏起来，并提供一个更高级、更抽象的接口，使得程序员可以更容易地编写正确、安全的并发代码。

管程的实际例子

用管程封装生产者消费者问题。

视频讲解

2.4 - 经典同步问题

生产者消费者问题

生产者-消费者问题是并发编程中的经典问题，涉及到两种线程——生产者和消费者，它们共享一个固定大小的缓冲区或存储区。生产者的任务是生成数据并将其放入缓冲区，而消费者的任务是从缓冲区中取出并消费这些数据。关键的挑战在于确保生产者不会在缓冲区满时添加数据，同时确保消费者不会在缓冲区空时尝试消费数据。

semaphore mutex = 1;          // 临界区互斥信号量
semaphore empty = n;          // 空闲缓冲区数量
semaphore full  = 0;          // 忙缓冲区数量

producer() {
    while (1) {
        P(empty)              // 等待一个空位置
        P(mutex)              // 进入临界区前先获取mutex
        ....                  // 将数据项添加到缓冲区
        V(mutex)              // 离开临界区，释放mutex
        V(full)               // 增加一个数据项的计数
    }
}

consumer() {
    while (1) {
        P(full)               // 等待一个数据项
        P(mutex)              // 进入临界区前先获取mutex
        ...                  // 从缓冲区取出数据项并消费
        V(mutex)              // 离开临界区，释放mutex
        V(empty)              // 增加一个空位置的计数
    }
}

生产者消费者问题C代码实现

读者-写者问题

读者-写者问题是另一个经典的并发编程问题，涉及到对共享数据或资源的访问，这些资源可以被多个读者同时读取，但只能被一个写者写入，而且当写者正在写入数据时，没有其他读者或写者可以访问该资源。

这个问题的挑战在于：

• 允许多个读者同时读取资源。
• 确保当有一个写者访问资源时，没有其他读者或写者可以同时访问。

• 读者优先
• 写者优先
• 公平算法

int read_count = 0;
semaphore wrt  = 1;
semphore mutex = 1;

reader() {
    while (1) {
        P(mutex)                     // 获取互斥访问权，以修改read_count
        read_count += 1
        if (read_count == 1) {       // 如果这是第一个读者，需要锁定资源，防止写者写入
            P(wrt)
        }
        V(mutex)                     // 释放互斥访问权
        ...                          // 读取资源
        P(mutex)                     // 获取互斥访问权，以修改read_count
        read_count -= 1
        if (read_count == 0) {       // 如果没有读者在读取，释放资源，允许写者写入
            V(wrt)
        }
        V(mutex)                     // 释放互斥访问权
    }
}

writer() {
    while (1) {
        P(wrt)                       // 获取资源的互斥访问权
        ...                          // 写入资源
        V(wrt)                       // 释放资源的互斥访问权
    }
}

int read_count = 0;
int write_count = 0;
semaphore wrt = 1;
semaphore mutex = 1;
semaphore write_mutex = 1;

reader() {
    while (1) {
        P(write_mutex)                  // 在读取之前，确保没有写者正在等待或写入
        P(mutex)                        // 获取互斥访问权，以修改read_count
        read_count += 1
        if (read_count == 1) {
            P(wrt)
        }
        V(mutex)
        V(write_mutex)

        ...                             // 读取资源

        P(mutex)                        // 获取互斥访问权，以修改read_count
        read_count -= 1
        if (read_count == 0) {
            V(wrt)
        }
        V(mutex)
    }
}

writer() {
    while (1) {
        P(write_mutex)                  // 获取互斥访问权，以修改write_count
        write_count += 1
        if (write_count == 1) {         // 如果这是第一个写者，锁定资源，防止新的读者读取
            P(wrt)
        }
        V(write_mutex)

        ...                             // 写入资源

        P(write_mutex)                  // 获取互斥访问权，以修改write_count
        write_count -= 1
        if (write_count == 0) {         // 如果没有其他写者在等待或写入，释放资源
            V(wrt)
        }
        V(write_mutex)
    }
}

int read_count = 0;
int write_count = 0;
semaphore wrt = 1;
semaphore mutex = 1;
semaphore queue = 1; // 新增队列信号量，以确保公平性

reader() {
    while (1) {
        P(queue);                 // 进入队列
        P(mutex);                 // 获取互斥访问权，以修改read_count
        read_count += 1;
        if (read_count == 1) {
            P(wrt);               // 如果是第一个读者，锁定资源
        }
        V(mutex);
        V(queue);                 // 离开队列
        ...                       // 读取资源
        P(mutex);                 // 获取互斥访问权，以修改read_count
        read_count -= 1;
        if (read_count == 0) {
            V(wrt);               // 如果是最后一个读者，释放资源
        }
        V(mutex);
    }
}

writer() {
    while (1) {
        P(queue);                 // 进入队列
        P(wrt);                   // 锁定资源
        ...                       // 写入资源
        V(wrt);                   // 释放资源
        V(queue);                 // 离开队列
    }
}

读者优先C代码实现

哲学家就餐问题

假设有五位哲学家坐在一个圆桌周围，每两位哲学家之间有一把叉子。哲学家的生活由思考和吃饭两种活动组成。为了吃饭，一个哲学家需要两把叉子——左边和右边的一把。问题在于，如何设计一个算法使得哲学家们可以正常就餐，而不会因为竞争叉子而导致死锁或饥饿。

哲学家就餐问题有多种解法，这里只提供一种最直观的解法，对于包含N各哲学家的问题：

• 前N-1个哲学家先拿起左边的叉子，再拿起右边的叉子
• 最后一个哲学家先拿起右边的叉子，再拿起左边的叉子

semaphore fork[5] = {1, 1, 1, 1, 1};      // 五个叉子，初始都是可用的

void philosopher(int i) {
    if (i < 5) {
        // 对于前面的哲学家，先左后右
        first = i;
        second = (i + 1) % 5;
    } else {
        // 对于最后一个哲学家，先右后左
        first = (i + 1) % 5;
        second = i;
    }
    while (1) {
        think();
        P(fork[first]);
        P(fork[second]);
        eat();
        V(fork[first]);
        V(fork[second]);
    }
}

哲学家就餐问题C代码实现

视频讲解

2.5 - 死锁

死锁产生的必要条件

只有以下四个条件同时满足，死锁才会发生：

1. 互斥条件 （Mutual Exclusion）: 指的是至少有一个资源必须处于非共享模式，也就是说，一次只有一个线程可以使用资源。如果其他线程请求该资源，那么请求的线程必须等到该资源的持有者释放该资源。
2. 占有并等待 （Hold and Wait）: 指的是一个线程因请求资源而阻塞时，对当前获得的资源保持不放。换句话说，线程至少已经持有一个资源，但又申请新的资源；由于其他线程持有这些资源，所以它现在是阻塞的。
3. 非抢占 （No Preemption）: 资源不能被抢占，也就是说，只有资源的持有者才可以释放它。资源在完全自愿的基础上被释放，不能被强行从持有线程中夺走。
4. 循环等待 （Circular Wait）： 存在一个线程资源的等待链，链中的每一个线程都在等待下一个线程所持有的资源。这导致了一个循环的等待链。

为了避免死锁，需要破坏上述的任意一个条件。

死锁处理策略

1. 死锁预防：设置限制条件，破坏产生死锁的 4 个必要条件之一。
2. 死锁避免：在资源的动态分配过程中，用某种算法避免系统进入不安全状态。
3. 死锁的检测和解除：允许线程在运行过程中发生死锁，通过系统检测机构及时检测出死锁的发生，然后采取某种措施解除死锁。

死锁预防

死锁预防是通过确保系统永远不会满足死锁产生的四个必要条件中的某些条件，从而避免死锁的发生：

1. 破坏互斥条件
   • 互斥条件在某些情况下是不可避免的，例如打印机等硬件资源。但在某些场景下，通过资源复制或虚拟化技术，可以尝试减少资源的互斥使用。
2. 破坏占有并等待
   • 要求线程在开始时一次性申请其需要的所有资源。只有当所有资源都可用时，线程才被分配资源并开始执行。这样，线程在执行期间不会等待其他资源。
   • 另一个方法是，如果线程申请新资源而被拒绝，则它必须释放所有已分配的资源，再重新申请。
3. 破坏非抢占
   • 当一个线程需要的资源被另一个线程所占有时，它可以抢占另一个线程的资源。
4. 破坏循环等待
   • 对线程申请资源的顺序进行限制

死锁避免

死锁避免是系统级的算法，需要对系统的资源和实体进行抽象，进行统筹规划，其中最经典的算法是银行家算法。

银行家算法

这里首先说一下次算法的命名，为什么叫“银行家”。一般而言，银行家都具备以下特点：

• 掌管金库（即资源），可以放贷（即满足线程申请的资源）
• 理性地作出决策，避免银行破产（即系统进入不安全状态）

相对于银行家的就是客户（即线程），线程需要申请一定量的资源。 但是线程可能不会立即申请全部的资源，线程也许会依次申请所有请求资源中的一部分， 当线程申请完全部的资源之后，它才会释放这些资源。

为了对刚刚描述的过程进行建模，我们需要定义如下的 数据结构：

• 系统
  • Available：表示每种资源的可用数量。
• 线程
  • Max：表示每个线程对每种资源的最大需求量。
  • Allocation：表示已经分配给每个线程的资源数量。
  • Need：表示每个线程还需要的资源数量，Need = Max - Allocation

算法步骤：

1. 初始化：为每个线程和每种资源设置 Max、Allocation 和 Need。
2. 当一个线程请求资源时，检查请求的资源数量是否小于等于 Need，如果大于则请求失败。
3. 检查请求的资源数量是否小于等于 Available，如果大于则请求失败。
4. 如果请求合法（满足上述两个条件），则模拟分配资源给该线程（预分配），即将资源从系统的 Available 减去，加到线程的 Allocation 中，并从线程的 Need 中减去相应数量的资源。
5. 然后，进行安全性检查，判断是否存在一种 安全分配序列，使得所有线程都能顺利执行完成。
6. 如果存在安全分配序列，则执行资源分配，否则拒绝请求，因为分配资源可能导致死锁，并且回收预先模拟分配的资源。
7. 当线程完成任务时，释放已分配的资源，将它们从 Allocation 减去，加到 Available 中。

什么是安全分配序列：

安全分配序列是线程的一个排列，它保证了对于序列中的每个线程，当这些线程都申请 Need 中的全部资源时，系统都能够满足这些需求。

如果系统存在一个安全分配序列，则系统处于 安全状态。

注意：不安全状态不意味着死锁，但它意味着有死锁的风险。不安全状态只是死锁的一个先兆，但不是死锁本身。

如何判断是否存在安全分配序列

假设系统中存在 N 个线程的话，则最多进行 N 轮遍历，每一轮至少找到一个 need 小于或等于 available 的线程，如果可以找到的话，就回收这些线程的 allocation，并将其加入 available 中，直到回收了所有线程的资源。如果有一轮存在这种情况：剩余的线程（任务未完成的线程）中的每一个 need 都大于 available，那么则说明无法找到一个安全分配序列，系统处于不安全状态。

这种判断方式的背后具有这样的逻辑：因为线程必须申请完所有需要的资源（即max）才能返还已申请的资源，所以系统在当下肯定是尽量满足那些可以返还资源的线程，因为只有回收了一些资源之后，才能满足之前可能无法满足的线程。

但是如果在某一个时刻，剩余的线程的资源一个都无法回收了，那么系统就进入了不安全状态。

这里还要需要注意的是，在实际的算法中，我们需要用 work 替代 available 来帮助我们完成安全性检查的过程，因为检查只是一种 “逻辑推演”，我们并不希望实际修改系统中的资源情况，具体的代码实现可以参考如下链接：

银行家算法代码实现

死锁的检测和删除

为了能对系统是否已发生了死锁进行检测，必须：

1. 用某种数据结构来保存资源的请求和分配信息：
2. 提供一种算法， 利用上述信息来检测系统是否已进入死锁状态。

一般来说，一种简单的建模方式是使用资源分配图：

• 将系统中的所有资源和进程表示为图中的节点。
• 如果进程 P1 请求资源 R1，绘制从 P1 到 R1 的有向边。
• 如果资源 R1 分配给了进程 P2，绘制从 R1 到 P2 的有向边。

在构建完资源分配图，可以通过使用 DFS 检查图中是否存在环路以判断是否存在死锁。

视频讲解

3 - 内存管理

# 内存管理

## 基础

- 基本概念：虚拟和逻辑地址，地址转换，内存共享，内存保护，内存分配和回收
- 连续分配管理方式
- 页式管理
- 段式管理
- 段页式管理

## 虚拟内存

- 基本概念
- 请求页式管理
- 页框分配
- 页置换算法
- 内存映射文件
- 虚拟存储器性能的影响因素和改进方法

3.1 - 内存管理概念

内存管理的基本概念

• 逻辑地址和物理地址空间
• 地址变换
• 内存共享

共享内存（Shared Memory）是多个进程共享的内存区域。它是最快的IPC（进程间通信）机制之一，因为进程直接读写内存，无需进入内核态。但是，因为多个进程可以同时访问这些内存，所以可能需要某种同步机制（如信号量）来防止竞态条件。

• 内存保护

内存保护是现代操作系统中的一个核心功能，用于防止一个进程访问另一个进程的内存空间。这不仅保障了系统的稳定性，而且提高了安全性，因为它可以防止恶意软件损害其他进程或篡改其数据。

可以通过如下机制实现内存保护机制：

1. 分段与分页:
   • 分段: 内存被划分为不同的段，每个段都有其起始地址和长度。段常常用于表示高级的数据结构，如函数或对象。
   • 分页: 内存被划分为固定大小的页面，例如4KB。操作系统为每个进程维护一个页表，来映射其虚拟地址到物理地址。
2. 访问权限: 每个段或页面都有与之相关的访问权限。例如，一个页面可能被标记为只读，这意味着任何尝试写入该页面的操作都会引发一个异常。
3. 隔离: 由于每个进程都有其独立的地址空间，所以一个进程不能直接访问另一个进程的内存。这为每个进程提供了一种形式的隔离，确保了一个出错的进程不会影响其他进程。

连续分配管理方式

1. 单一连续分配

内存在此方式下分为系统区和用户区，系统区仅供操作系统使用，通常在低地址部分；在用户区内存中，仅有一道用户程序，即整个内存的用户空间都由该程序独占。

这种方式的优点是简单、无外部碎片，无需进行内存保护，因为内存中永远只有一道程序。缺点是只能用于单用户、单任务的操作系统中，存储器的利用率极低。

2. 固定分区分配

固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可再从外存的后备作业队列中选择适当大小的作业装入该内存，如此循环。

为了方便内存分配，通常将分区按大小排队，并为之建立一张分区说明表，其中各表项包含每个分区的起始地址、大小和状态。当有用户程序需要装入时，便检索该表，以找到合适的分区基于分配并将其状态设置为“已分配”；未找到合适分区时，则拒绝为给程序分配内存。

3. 动态分区分配

内存空间中的空闲区域可能大小不一，且分布在内存中不同的位置。当进程申请一块新的内存时，必须从已有的空闲空间中选出一块分配给进程。动态分区的分配策略包含以下几种算法：

• First Fit（首次适应）
  • 当需要分配内存时，它不从内存的开始位置开始，而是从上一次分配内存的地方开始。
• Next Fit（临近适应）
  • 这种策略与首次适应相似，但当需要分配内存时，它不从内存的开始位置开始，而是从上一次分配内存的地方开始。
• Best Fit（最佳适应）
  • 为了满足内存请求，最佳适应策略会在所有可用的内存块中查找并选择最小的、但足够大的内存块（申请内存/内存块大小最大），这种策略的目标是最大限度地减少浪费的内存空间。。
• Worst Fit（最坏适应）
  • 与最佳适应的目标相反，其思想是留下最大的连续空闲区域，希望这样可以满足后续的大请求。

页式管理

段式管理

段式内存管理是一种内存组织方法，它将程序的不同部分（例如代码、数据和堆栈）划分为不同的段（segments）。每个段在物理内存中可以不连续，但在逻辑上都被视为连续的。这种方法的主要优点是它允许更为灵活的内存使用，并有助于提供更好的保护和共享机制。

段定义

• 每个段都有一个明确的角色，例如代码段、数据段或堆栈段。
• 每个段都有一个起始地址和长度。
• 段内的地址是连续的，但不同段之间的地址可以不连续。

段表

• 段表是一种数据结构，用于存储每个段的基地址（在物理内存中的起始地址）和限制（段的长度或末尾地址）。
• 当一个程序需要访问其内存段时，会使用段号和段内偏移作为地址。这个地址被称为逻辑地址或段地址。
• 逻辑地址通过段表转换为物理地址。

地址转换

• 为了从逻辑地址获取物理地址，首先需要从逻辑地址中提取段号，然后使用段号在段表中查找相应的基地址和限制。
• 然后，检查逻辑地址中的偏移量是否小于该段的限制。如果偏移量超出限制，则产生段越界错误。
• 如果偏移量有效，则将偏移量加到段的基地址上，得到物理地址。

段页式管理

段页式管理是一种将段式内存管理与分页式内存管理相结合的策略。它结合了两者的优势，旨在提供灵活性和减少内存碎片。在段页式管理中，程序首先被划分为逻辑上的段，然后每个段进一步被划分为固定大小的页。

3.2 - 虚拟内存管理

页框分配

驻留集大小

驻留集是指当前在物理内存中实际驻留的进程页面的集合。驻留集大小是表示这个集合中页面数量的指标，通常以页框（或页面框）的数量来度量。这个指标决定了进程可以直接访问的物理内存页面数量，以及在物理内存中保持的页面的范围。

驻留集大小的合理设置对系统性能至关重要。如果驻留集大小太小，进程可能经常发生页面置换，导致频繁的缺页中断，从而降低性能。如果驻留集大小太大，可能会浪费物理内存资源，并导致其他进程无法获得足够的内存。

什么是抖动

抖动（Thrashing）是指操作系统中发生的一种现象，当它花费大量时间在页面置换（将内存中的页面换入换出到磁盘）上而非执行实际的计算。这通常发生在系统的物理内存非常紧张，多个进程频繁请求的页面不在物理内存中时。

当系统为一个进程分配的物理内存不足以满足其工作集（当前活跃的页面集合）的需求时，就会频繁发生缺页中断。操作系统必须不停地从磁盘读取所需的页面到内存中，同时写出其他页面以释放空间。因为磁盘访问速度远慢于内存访问，这种频繁的磁盘I/O活动显著减慢了系统性能。

抖动的直接后果是CPU使用率下降，因为CPU在等待必要的页面从磁盘加载时处于空闲状态。系统资源被过多地用于管理内存和磁盘之间的数据交换，而非执行用户程序。抖动严重时，系统的吞吐量下降，响应时间增加，用户和应用程序都会感受到系统变得迟钝和无响应。

内存分配和置换策略

分配策略

• 固定分配
  • 内存被划分为固定大小的区块。
  • 每个程序或进程被分配一个或多个这样的区块，不管它们实际上需要多少内存。
• 可变分配
  • 内存不是被划分为固定大小的区块，而是根据每个程序的需求动态分配。
  • 当一个程序请求内存时，操作系统查看可用内存并分配足够的连续空间给该程序，这个空间刚好满足其需求。

置换策略

• 局部置换
  • 每个运行的进程被分配了一定数量的内存帧（物理内存中的页面），并且仅在这些分配给它的帧中进行页面置换。
  • 当一个进程需要更多的内存空间时，它只能换出自己的页面，而不能影响到其他进程的页面。
• 全局置换
  • 操作系统可以从整个物理内存的范围内选择页面进行置换，不局限于特定进程的内存帧。
  • 如果一个进程需要更多的内存，操作系统可以从其他进程占用的帧中换出页面。

分配和置换策略的组合

可以选择分配策略和置换策略之一进行组合，但不存在固定分配全局置换方式。

页置换算法

OPT

OPT（Optimal）页面置换算法，也称为最佳页面置换算法，是一种理论上的页面置换算法，其目标是选择最佳的页面来置换，以最大程度地减少未来的页面访问次数。

由于OPT算法需要知道未来的页面引用序列，这在实际情况下是不可能的，因此OPT算法通常用于理论研究和性能评估，以作为其他页面置换算法的性能上限的比较基准。

FIFO

FIFO（First-In-First-Out）页面置换算法是一种简单的页面置换策略，其中最早进入内存的页面被置换出去。它的工作原理类似于排队，即首先进入内存的页面也是首先离开内存的页面。

LRU

LRU（Least Recently Used）页面置换算法是一种常用的页面置换策略，它基于最近的页面访问历史来决定哪个页面应该被置换出内存。LRU算法的基本思想是，总是选择最长时间没有被访问的页面进行置换，以期望最小化未来的缺页次数。

LRU替换策略如下：

假设内存中Mem最多可以容纳N个页面（将其看成一个长度最大为N的队列），当访问一个页面P时

• 如果P在队列中出现
  • 将P移动到队列末尾
• 如果P不在队列中
  • 如果队列没有满的话，将P加入队列末尾
  • 如果队列满的话，将队列头部的页面淘汰，并且将P加入队列末尾

LRU代码实现

Clock

简单clock替换算法

CLOCK算法的核心思想是使用一个类似时钟的数据结构，以跟踪每个页面的访问状态。CLOCK算法维护一个环形链表，其中每个页面都有一个位（也称为访问位或引用位）。算法以时钟指针的方式扫描环形链表，查找可以被替换的页面。

Clock替换策略如下：

假设内存中Mem最多可以容纳N个页面（将其看成一个长度最大为N的循环队列），当访问一个页面P时

• 如果P在队列中出现
  • 将P的引用为标记为1
• 如果P不在队列中，判断指针指向的页面引用位的数值
  • 引用位为0，则替换该页面，并将指针移动到下一个位置
  • 引用位为1，将该页面的引用位置为0，将指针移动到下一个位置继续判定

clock算法代码实现

改进型clock算法

CLOCK-Pro算法通过引入更多的信息来更准确地确定页面是否被访问，以便更好地进行页面替换决策并且减少磁盘I/O次数。

CLOCK-Pro算法引入了两个新的位来跟踪页面的状态：

• Reference Bit (R位)：与标准CLOCK算法相同，R位用于标记页面是否最近被访问，0表示未被访问，1表示已被访问。
• Modified Bit (M位)：M位用于标记页面是否被修改，0表示未修改，1表示已修改。

1. 当页面需要进入内存时，R位和M位都被设置为0，表示页面最近未被访问且未被修改。
2. 当访问一个页面时，R位被设置为1，表示页面最近被访问。
3. 当修改一个页面时，M位被设置为1，表示页面已被修改。
4. 当需要替换页面时，CLOCK-Pro算法首先查看R位，选择R位为0的页面进行替换，这是与标准CLOCK算法相同的部分。
5. 如果所有页面的R位都为1，CLOCK-Pro算法会选择M位为0的页面进行替换，以便选择一个未被修改的页面进行替换。
6. 如果所有页面的R位和M位都为1，CLOCK-Pro算法会选择最早满足这两个条件的页面进行替换，以模拟LRU策略。

LFU

LFU（Least Frequently Used）算法的核心思想是：当主存没有足够的空间加载新的页面时，系统会选择那些在过去使用次数最少的页面进行置换。

基本步骤：

1. 初始化：当一个页面首次加载到内存中时，为其分配一个计数器并将其设置为1（表示该页面被访问过一次）。
2. 页面命中：如果要访问的页面已经在内存中，则增加该页面的访问计数。
3. 页面置换：当需要为新的页面腾出空间时（也就是说，当内存中的页面已满并且需要加载一个新页面时），系统会查看所有当前在内存中的页面的访问计数，选择访问次数最少的那个页面进行置换。

内存映射文件

mmap 是一种在 Unix/Linux 操作系统中用于实现内存映射文件的系统调用。内存映射文件是一种非常有用的技术，它允许将文件映射到进程的地址空间中，使文件的内容可以像内存一样被访问。

• mmap 允许将文件映射到进程的虚拟地址空间，使文件的内容可以像内存一样直接访问，而不需要显式的读取或写入文件。
• 这意味着当你修改映射到内存中的文件内容时，实际上是在修改物理存储设备上的文件。因此，内存映射文件对于高性能 I/O 操作非常有用，因为可以避免显式的 I/O 操作。

视频讲解

4 - 文件管理

# 文件管理

## 文件

- 基本概念
- 元数据和索引结点
- 文件的操作
- 文件的保护
- 文件的逻辑结构
- 文件的物理结构

## 目录

- 基本概念
- 树形目录
- 目录的操作
- 硬链接和软链接

## 文件系统

- 全局结构
- 外存空闲空间管理方法
- 虚拟文件系统
- 文件系统挂载

4.1 - 文件

文件元信息

在UNIX和类UNIX操作系统中，inode（索引节点）是一个非常重要的数据结构，用于表示文件系统中的文件和目录。每个文件或目录都有一个与之对应的inode，它包含了关于该文件的大部分元数据，但不包括文件名和文件实际内容。

inode信息：

• 文件类型：文件是普通文件、目录还是链接文件等。
• 权限：文件的访问控制信息，如用户、组和其他用户的读、写、执行权限。
• 所有者：文件的所有者和组ID。
• 大小：文件的大小（字节数）。
• 时间戳：文件的创建时间、最后修改时间和最后访问时间。
• 链接计数：指向该文件的硬链接数量。当计数为0时，文件会被删除。
• 数据块指针：文件内容所在的数据块（block）的位置信息。这包括直接指针、间接指针、二级间接指针和三级间接指针，用于指向存储文件内容的磁盘块。

进程文件管理

• 文件描述符表：每个进程都有自己的文件描述符表，这个表对应于该进程打开的文件描述符。文件描述符是进程范围内的一个小的非负整数。
• 文件表：操作系统维护一个全局的文件表，该表记录了所有打开文件的状态信息。每次 open 调用成功时，都会创建一个新的文件表条目。
• inode表：系统还维护了一个inode表，该表包含了文件的元数据和指向文件实际数据的指针。如果多个进程打开同一个文件，它们的文件表条目将指向inode表中的同一inode。

在进程1中执行fdA1 = open("fileA.txt", O_RDONLY)和fdAdup = dup(fdA)系统调用，在进程2中执行fdA2 = open("fileA.txt", O_RDONLY)，系统中的数据结构如下图所示：

文件的逻辑结构

1. 顺序文件：
   • 记录顺序：顺序文件中的数据以记录的顺序排列。每个记录都按顺序存储在文件中，一个接一个。
   • 访问方式：顺序文件通常按照记录的顺序进行访问。要查找或修改文件中的某个记录，必须从文件的开头开始逐个读取记录，直到找到所需的记录或到达文件末尾。
   • 应用场景：适用于需要按顺序读取和处理数据的应用程序，如批处理任务和日志文件。
2. 随机文件（或称为索引文件）：
   • 记录随机排列：在随机文件中，数据记录可以按任意顺序排列，而不需要按照特定的顺序。
   • 访问方式：随机文件支持随机访问，这意味着可以直接访问文件中的任何记录，而不必按照顺序逐个读取。
   • 索引结构：为了支持随机访问，随机文件通常使用索引结构（如哈希表或B树）来跟踪记录的位置。
   • 应用场景：适用于需要快速查找和访问特定记录的应用程序，如数据库系统和文件系统。

文件的物理结构

1. 连续分配方案（Contiguous Allocation）

连续分配该方案中，每个文件占用磁盘上一个连续的块集。例如，如果一个文件需要n个块，并且给定一个块b作为起始位置，那么分配给该文件的块将是b, b+1, b+2，……b+n-1。这意味着给定起始块地址和文件的长度，我们可以确定文件占用的块。具有连续分配的文件的目录条目包含分配部分的起始块长度的地址。

连续分配方案对应的目录包含如下信息：

• 文件的其实地址
• 分配块数量

下图中的文件 “file3” 从区块19开始，长度为6个区块。因此，它占用19、20、21、22、23、24个块。