先修课程：计算机组成原理、数据结构与算法、计算机体系结构（这门课如果学过是最好的）。

0. 导论

程序运行时会发生什么？答案：执行指令。处理器从内存中获取（fetch） 一条指令，对其进行解码（decode）（弄清楚这是哪条指令），然后执行（execute）它（做它应该做的事情，如两个数相加、访问内存、检查条件、跳转到函数等）。完成这条指令后， 处理器继续执行下一条指令，依此类推，直到程序最终完成。

……很麻烦对吧？

实际上，有一类软件负责让程序运行变得容易（甚至允许你同时运行多个程序），允许 程序共享内存，让程序能够与设备交互，以及其他类似的有趣的工作。这些软件称为操作 系统（Operating System，OS），因为它们负责确保系统既易于使用又正确高效地运行。

0.1 从计算机系统到操作系统

0.1.1 计算机组成原理

需要掌握的计算机组成原理的重点，概念相通：

  1. 计算机的组成结构

    1. 概述：

      • 控制单元CU 运算单元（ALU是核心） 存储器 输入单元和输出单元 以及连接它们的总线(Bus)

    2. 硬件

      • 处理器 存储器 主存 辅存 IO设备 注意辅存属于IO设备

    3. PU = CU + ALU + Register

      • ALU = 加法器 + 逻辑运算 + 移位器 + 求补器

      • CU = 程序计数器 PC + 指令译码器ID + 其它三个

      • Register 分为 数据寄存器 地址寄存器 标志寄存器

  2. 存储系统

    1. 存储器分类与性能评价

      • 第一种分类方式

        • 处理器直接访问：主存 / 辅存

        • 掉电后信息丢失：易失性（volatile） / 非易失性

        • 支持访问类型：可读写 / 只读ROM

        • 访问方式：按地址访问 / 按内容访问CAM / 指定位置访问

        • 实现介质：半导体 / 磁表面 / 光盘

      • 第二种分类方式

        • 按存储介质：有明确两个物理状态表示01

        • 按存取方式：

          • 随机访问（RAM SRAM DRAM NVRAM ROM）

          • 串行访问（顺序存取 直接存取）

        • 在计算机存储体系中的作用：主存、闪存缓存（Flash Cache）和辅存

    2. 半导体存储器（需要理解，是OS的前置知识）

      • 随机访问半导体存储器 RAM

        • 静态 RAM SRAM：用于片内CPU高速缓存 Cache

        • 动态 RAM DRAM：用于片外作为系统主存

      • 只读半导体存储器 ROM： 用于存放计算机的基本程序和数据，如BIOS ROM、EEPROM等

        • 操作系统的引导程序位于 ROM 中！它的作用是定位到OS内核并加载到内存

    3. 缓存 Cache

      • 概念：它位于CPU和主存储器（如RAM）之间。它的主要目的是减少CPU访问主存储器所需的时间，因为主存储器的访问速度通常比CPU的处理速度慢得多。缓存存储器能够暂时存储CPU频繁访问的数据和指令

  3. 输入输出系统

    1. I/O 接口的组成与工作原理

      • I/O接口是计算机内部总线和外部设备之间的桥梁。它由硬件电路和软件驱动程序组成，负责数据在计算机和外部设备之间的传输。

      • 可以分为同步操作和异步操作。

    2. 程序中断系统

      • 中断系统是计算机硬件和软件的一个机制，它允许外部设备或软件程序在CPU执行当前任务时“打断”CPU，请求其处理紧急任务。例如，当键盘上按下一个键时，键盘会发送一个中断信号给CPU，CPU会暂停当前任务，处理键盘输入，然后再返回到原来的任务。

      • 软件的中断可以通过系统调用来触发。

      • 中断向量：中断处理程序的指针表，管理中断请求与终端服务之间的关系。

    3. 直接内存访问 DMA

      • DMA是一种允许某些硬件子系统直接访问主存储器的技术，而不需要CPU的介入。这样，数据传输可以在外设和内存之间直接进行，减少了CPU的负担，提高了IO效率。例如，当从硬盘读取数据到内存时，DMA控制器可以接管这一过程，让CPU去处理其他任务。

0.1.2 计算机系统体系结构

计算机系统可能通过许多不同途径来组成。

计科专业的同学会上一门4学分的课叫“计算机体系结构”，软工不学，但是这东西应该是操作系统的先修课。

计算机体系结构课程研究计算机系统的结构和组织，指令集架构、处理器设计、存储体系结构、并行计算等。

  • 单处理器系统：

    • 系统只有一个CPU。

    • 带有其它专用处理器如磁盘、键盘、图形控制器。

  • 多处理器系统：

    • 多个CPU共享总线，有时需要共享时钟、内存、外设等。

    • SMP 无主从关系 / AMP 主从关系：SMP可以让CPU相互独立执行

    • 多核处理器：

      • 每个CPU核也要有自己的寄存器与Cache

  • 集群系统：两个或多个独立系统（节点组成）

    • 自治系统、并行分布式系统、松耦合、高可用、高性能计算

0.1.3 操作系统的结构

刚才讨论的是计算机系统，现在来讨论操作系统。以下是各个操作系统的不同点。

计算机系统是如何与操作系统产生关系的呢？最初的计算机只能接受一些特定的指令，用户每输入一个指令，计算机就做出一个操作。当用户在思考或者输入时，计算机就在等待。这样效率非常低下，在很多时候，计算机都处在等待状态。

后来有了批处理操作系统，把一系列需要操作的指令写下来，形成一个清单，一次性交给计算机。用户将多个需要执行的程序写在磁带上，然后交由计算机去读取并逐个执行这些程序，并将输出结果写在另一个磁带上。

批处理操作系统在一定程度上提高了计算机的效率，但是由于批处理操作系统的指令运行方式仍然是串行的，内存中始终只有一个程序在运行，后面的程序需要等待前面的程序执行完成后才能开始执行，而前面的程序有时会由于I/O操作、网络等原因阻塞，并且是由人来调度CPU和内存使用利率的，所以批处理操作效率也不高。

  • 多道程序系统

单个程序并不能让 CPU 和 I/O 设备始终忙碌。

多道程序设计通过安排作业使得CPU总有一个执行作业，从而提高 CPU利用率。

作业需要保存到硬盘中的作业池中。内存的作业集是作业池的子集，操作系统选择内存的一个作业集中执行一个作业。在该作业需要等待时，CPU会切换到另一个作业。

多道程序系统提供了一个环境，以便充分利用各种系统资源（CPU、内存、外设等）；但是没有提供用户与计算机系统的交互（会因为I/O阻塞）。

  • 分时操作系统

分时操作系统是多道程序设计的自然延伸，虽然CPU还是通过切换作业来执行多个作业，但是由于切换频率很高，用户可以在程序运行时与其交互。

它要求计算机系统是可交互的：用户通过输入设备（键盘等）向操作系统发出指令，并等待输出设备的即时结果。

0.1.4 用户模式与内核模式

也就是说，现代操作系统是中断驱动的。有时候，个别中断是由软件引起的。

由于操作系统和用户共享计算机系统的硬件和软件，需要确保用户程序的出错仅仅影响自己。例如一个错误的程序在多道程序系统的情况下，可能出现更多微妙错误，可能修改另外程序的数据甚至操作系统本身。

为了保护操作系统的代码，大多数计算机系统的硬件会支持两种执行模式：用户模式和内核模式

  • 用户模式时，用户掌握计算机的控制权，运行用户代码

  • 内核模式时，操作系统掌握计算机的控制权，运行系统代码

计算机硬件可以通过一个模式位来表示：内核模式（0）和用户模式（1）；

如系统调用（System Call），当用户程序调用系统调用函数的时候，操作系统的运行模式从用户模式转变成内核模式，如调用 printf() 函数：

系统调用提供操作系统的服务接口（面向程序），通常以C/C++编写，若直接访问硬件可能以汇编语言指令编写。

通常应用程序开发人员根据 API 来设计程序，如：

  • Windows API

  • POSIX API 如 libc

  • JVM API

下图是用户应用程序调用 “系统调用open()”后，操作系统的处理：

左下角蓝框是系统调用番号表，内含系统调用的id。

向操作系统传递参数有三种方法：

  • 寄存器

  • 内存块：数据放入内存块，寄存器放地址

  • 压入栈内存

0.2 操作系统能够担当什么角色呢？

0.2.1 虚拟化CPU

操作系统可以实现在我们只有一个处理器的时候同时运行多个程序。

操作系统负责提供系统拥有非常多的虚拟 CPU 的假象。单个 CPU（或其中一小部分）转换为看似无限数量的 CPU， 从而让许多程序看似同时运行，这就是所谓的虚拟化 CPU（virtualizing the CPU）。

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <assert.h>
#include "common.h"

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "usage: cpu <string>\n");
        exit(1);
    }

    char *str = argv[1];

    while (1) {
        // Spin() 函数会反复检查时间并在运行一秒后返回。
        Spin(1);
        printf("%s\n", str);
    }

    return 0;
}

cpu.c 可以尝试在 shell 中执行 ./cpu A & ; ./cpu B & ; ./cpu C & ; ./cpu D & 以同时运行四个实例。

0.2.2 虚拟化内存

每个进程访问自己的私有虚拟地址空间（virtual address space）（有时称为地址空间，address space）， 操作系统以某种方式映射到机器的物理内存上。一个正在运行的程序中的内存引用不会影响其他进程（或操作系统本身）的地址空间。

对于正在运行的程序，它完全拥有自己的物 理内存。但实际情况是，物理内存是由操作系统操理的共享资源。

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "common.h"

int main(int argc, char *argv[]) {
    // 分配一些内存并将其地址赋值给指针 p
    int *p = malloc(sizeof(int)); 
    assert(p != NULL);// 确保内存分配成功

    // 打印 p 的内存地址和正在运行的进程的 PID
    printf("(%d) memory address of p: %08x\n", getpid(), (unsigned)p); 
    
    // 将分配的内存位置初始化为 0
    *p = 0; 

    // 进入一个无限循环，每秒递增一次内存中的值
    while (1) {
        Spin(1);     // 延迟循环一秒
        *p = *p + 1; // 增加 p 指向的地址中的值
        // 打印当前进程的 PID 以及 p 指向的地址中当前存储的值
        printf("(%d) p: %d\n", getpid(), *p); 
    }

    return 0; // 程序结束（由于无限循环，实际上不会到达这里）
}

每个正在运行的程序都在相同的地址处分配了内存，但每个似乎都独立更新了 00200000 处的值！

0.2.3 并发

如果有多个线程对于共享内存的访问没有原子性（所有指令一次性执行），会有线程安全问题。

#include <stdio.h>
#include <stdlib.h>
#include "common.h"

volatile int counter = 0; // 全局变量 counter，用于计数，并声明为 volatile，防止编译器优化
int loops; // 循环次数

// 线程工作函数，递增 counter
void *worker(void *arg) {
    int i;
    for (i = 0; i < loops; i++) { // 循环递增 counter
        counter++;
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    // 检查输入参数是否正确
    if (argc != 2) {
        fprintf(stderr, "usage: threads <value>\n");
        exit(1);
    }

    loops = atoi(argv[1]); // 将输入参数转换为整数，赋值给 loops
    pthread_t p1, p2; // 定义两个线程 p1 和 p2

    printf("Initial value : %d\n", counter); // 输出初始 counter 值

    // 创建两个线程，分别执行 worker 函数
    Pthread_create(&p1, NULL, worker, NULL);
    Pthread_create(&p2, NULL, worker, NULL);

    // 等待两个线程执行完成
    Pthread_join(p1, NULL);
    Pthread_join(p2, NULL);

    // 输出最终 counter 值
    printf("Final value : %d\n", counter);
    return 0;
}

0.2.4 持久性

操作系统需要为硬件与磁盘提供文件系统，需要将数据写入 I/O 设备与磁盘中。

#include <stdio.h>
#include <unistd.h>
#include <assert.h>
#include <fcntl.h>
#include <sys/types.h>

int main(int argc, char *argv[]) {
    // 打开或创建文件 "/tmp/file"，以只写模式打开，并设置权限为用户读写执行
    int fd = open("/tmp/file", O_WRONLY | O_CREAT | O_TRUNC, S_IRWXU);
    assert(fd > -1); // 确保文件打开成功

    // 向文件写入字符串 "hello world\n"，共13个字符
    int rc = write(fd, "hello world\n", 13);
    assert(rc == 13); // 确保写入的字符数为13

    // 关闭文件
    close(fd);

    return 0; 
}

1. 进程管理：CPU 虚拟化

1.1 进程概念

上文提到了分时操作系统，它的工作单元就是进程。

所有 CPU 活动可以分为：

  • 批处理系统执行作业（job）

  • 分时系统执行任务（task）

作业是任务的一个实例，是一个具体的任务。

进程与程序的区别：

  • 程序是被动实体，如磁盘上的可执行二进制文件

  • 进程是活动实体，把可执行文件加载进内存就变成了进程。它需要程序计数器表示下一个执行指令和一组相关资源。

进程状态

  • 新的 (new): 进程正在被创建。

  • 就绪 (ready): 进程等待分配处理器。

  • 运行 (running): 指令正在被执行。

  • 等待（阻塞） (waiting / blocking): 进程等待某个事件的发生。

  • 终止 (terminated): 进程完成执行。

1.2 进程控制块 PCB

操作系统的每个进程表示都要采用进程控制块PCB，是一个管理进程的数据结构。

  • 进程 ID：PID ：大部分操作系统通过唯一的进程标识符（PID）来识别系统中的进程。（书上没有特意讲）

  • 进程状态：包括新的、就绪、运行、等待、停止等状态，表示进程当前的执行状态。

  • 进程计数器：表示进程要执行的下一个指令的地址，用于跟踪执行流程。

  • CPU 寄存器：包括累加器、索引寄存器、堆栈指针、通用寄存器和其他条件码信息寄存器，存储执行过程中的重要信息

  • CPU 调度信息：包含进程的优先级、调度队列的指针和其他调度参数，用于控制进程的执行顺序。

  • 内存管理信息：包括基地址和界限地址、页表或段表等，用于管理进程的虚拟内存空间。

  • 记账信息：记录 CPU 使用时间、时间限制等信息，便于系统监控资源的分配与使用。

  • I/O 状态信息：记录 I/O 设备分配状态和打开文件表等信息，帮助系统管理进程的 I/O 资源。

// 简单的 Linux 进程控制块实现 仅供理解
struct task_struct {
    pid_t pid;                     /* 进程标识符 */
    long state;                    /* 进程状态 */
    unsigned int time_slice;       /* 调度信息 */
    struct task_struct *parent;    /* 父进程的指针 */ 
    struct list_head children;     /* 子进程的列表 */
    struct files_struct *files;    /* 打开的文件列表 */
    struct mm_struct *mm;          /* 进程的地址空间 */
};

// 改变当前进程的状态
current->state = new_state;

  • 父进程：创建它的进程；子进程：它创建的进程

仅供理解：进程间CPU的上下文切换会用到PCB：

1.3 进程调度初步

现在进程已经在内存里了，我们需要在CPU执行它。

进程调度器：需要在分时操作系统中选择一个可用进程到CPU上执行。

1.3.1 调度队列

  • 作业队列：进程进入系统时，会被加到作业队列，包括系统内的所有进程。

  • 就绪队列：驻留在内存、就绪的、等待CPU运行的进程保存在就绪队列。

  • 设备队列：若进程向一个共享设备（如磁盘）发送 I/O 请求，但磁盘忙于其它进程的 I/O 请求，则把该进程放到该设备的设备队列里进行等待（阻塞）。

最初新进程被加入到就绪队列，在就绪队列中等待，直到被选中执行。当进程被分配到CPU并在运行状态时，以下事件可能发生：

  • 进程可能发出I/O请求，并被放到I/O队列。

  • 进程可能创建一个新的子进程，并等待其终止。

  • 进程可能由于中断，被强制释放CPU，并被放回到就绪队列。

进程重复这一循环直到终止，然后它就会从所有队列中删除，其PCB和资源被释放。

在上图中“就绪队列”属于CPU队列，进程处于 就绪Ready 状态

“I/O队列”中，进程处于 等待Waiting/阻塞Blocking 状态

1.3.2 调度程序与上下文切换【重点】

下面将上图的“就绪队列->CPU” 与 “中断发生”两部分做进一步切入。

进程在整个生命周期中，会在各种调度队列之间迁移。操作系统为了调度需要按照一定方式在这些队列中选择进程。

  • 长期调度程序：控制内存中的进程数量（多道程序调度），需要选择合理的 I/O 密集型进程 和 CPU密集型进程 的组合放在内存里。执行并不频繁。

UNIX 和 Windows 的分时操作系统没有长期调度程序，简单的将所有新进程放入内存，供短期调度程序使用。

  • 短期调度程序（CPU调度程序）：从CPU就绪队列（即内存）中选择新的进程，必须快速。

  • 中期调度程序：将进程从内存（CPU竞争）中换出，在后来再换入。被换出的进程并不是结束了，而是换到了硬盘（虚拟内存）去了。

进程在中断时，系统需要保存当前运行的CPU上进程的上下文（挂起进程），然后在处理后恢复上下文（恢复进程）。

进程的上下文用 PCB 表示。

在状态保存时，CPU 当前状态（即用户模式 / 内核模式）也需要保存。

1.4 进程的生命周期

Linux 系统启动时会启动一个进程 PID 1 ，用于管理其余所有的服务和进程。

在控制台输入 htop 回车，并按下 F5 ：

可以看到进程树：每一个进程都有它的 Parent 进程（除了 PID 1），而每个进程都可以由许多子进程。

htop 可以被看作是 ps -ef 的一个更广泛的版本，它可以实时更新进程统计信息。

应该可以用过 apt安装。

第一个 init 进程其上还会有一个调度进程（又叫上帝进程、schedule、sched）

1.4.1 Linux 创建新进程 fork()

以下是一段可以获得当前进程PID的C语言代码 henlo.c ：

#include<stdio.h>
int main( void ) {
   printf( "henlo: %d\n", getpid() );
}

编译并运行它，我们可以得到：

# gcc henlo.c -o henlo
# ./henlo
henlo: 10455

使用C语言的 fork() ，我们可以直接复制当前进程，在当前进程上创建一个子进程：

/* linux下： */
 
#include <stdio.h>
#include <unistd.h>
 
int main() {
    // #define pit_t int
    pid_t pid;
    pid = fork();
    if(pid == 0) {
        // 返回子进程
        printf("child pid: %d\n", getpid());
    } else {
        printf("pid: %d\n", pid);   //父进程中返回子进程的pid
        printf("father pid: %d\n", getpid());
    }
}
# gcc fork.c -o fork
# ./fork
pid: 13895
father pid: 13894
child pid: 13895

fork调用的一个奇妙之处就是它仅仅被调用一次，却能够返回两次，它可能有三种不同的返回值：

1）在父进程中，fork返回新创建子进程的进程ID；

2）在子进程中，fork返回0；

3）如果出现错误，fork返回一个负值；

1.4.2 子进程的执行方式

我们可以在子进程内编写一些命令：

#include<stdio.h>
int main( void ) {
    if ( fork() > 0 ) {
        /* parent process */
        wait( NULL );
    } else {
        /*child process 执行了 exec命令*/
        execv( “/bin/bash”, NULL );
    }
}
// 之后在命令行连续三次运行编译好的exec文件

  • 子进程会复制父进程的地址空间到一个新的地址空间，继承父进程的代码指令与数据副本。

  • 若子进程执行 exec则抹掉子进程的地址空间，重新在此 pid 执行 exec 的内容

  • 若父进程执行 wait() 需要等待子进程执行结束后，在继续执行。

1.4.3 僵尸进程

若子进程先于父进程退出 （如C语言的 exit(1) ），且父进程：

  • 没有调用 wait()无暇回收子进程的资源

  • 没有主动终止子进程

则子进程就会变为僵尸进程。

僵尸进程无法使用 kill 命令杀死。

解决方案：杀死父进程，这些僵尸子进程会被 init 线程领养并继续回收。

1.5 进程间通信机制

进程间通信有两种：共享内存、消息传递。

1.5.1 共享内存

通过缓冲区来实现共享内存。

#define BUFFER_SIZE 10

typedef struct {
    ...
}item;

// 共享内存缓冲区
item buffer[BUFFER_SIZE];
// 数据指针
int in = 0;
int out = 0;

  • in 是写位置，指向缓冲区下一个空位

  • out 是读位置，指向缓冲区第一个满位

  • 若 in == out 缓冲区为空

  • 若 (in + 1)%BUFFER_SIZE == out时，缓冲区为满

生产者进程：若缓冲区满则必须等待

while(true){
    while((in + 1)%BUFFER_SIZE == out){ ;} // 缓冲区满，阻塞
    
    buffer[in] = next_produced;
    in = (in + 1)%BUFFER_SIZE;
}

消费者进程：若缓冲区空则必须等待

while(true){
    while(in == out){ ;} // 缓冲区空，阻塞
    
    next_consumed = buffer[out];
    out = (out + 1)%BUFFER_SIZE;
}

1.5.2 消息队列

消息队列需要提供两种操作：发送send(msg)和接受 receive(msg)

这里有三个问题：

  • 直接与间接的通信

    • 直接通信

      • 对称性：一对一 指定收件人 指定发件人

      • 非对称性：一对多 指定收件人 不指定发件人

    • 间接通信：通过端口/邮箱通信

      • 只有两个进程共享一个邮箱时，才能建立通信链路

      • 一个链路 可以与两个或更多进程相关联 可以是多对多

  • 同步或异步的通信（也称阻塞/非阻塞）

  • 自动或显式的缓冲

1.5.3 进程间通信应用【可能考】

套接字 Socket

  • 有 ip 和端口

  • 通过 api 定义其属性，提供收发信息服务，但仅在进程活着的时候接受

  • TCP / UDP

远程过程调用 RPC

（怎么考我也不知道）

管道

  • 是 IPC 的一种

  • 分匿名管道和命名管道

  • 介质是文件

1.6 进程与线程

虽然进程的出现，使得操作系统的性能大大提升，但是随着时间的推移，人们并不满足一个进程在一段时间只能做一件事情，如果一个进程有多个子任务时，只能逐个得执行这些子任务，很影响效率。

比如杀毒软件在检测用户电脑时，如果在某一项检测中卡住了，那么后面的检测项也会受到影响。或者说当你使用杀毒软件中的扫描病毒功能时，在扫描病毒结束之前，无法使用杀毒软件中清理垃圾的功能，这显然无法满足人们的要求。

线程的提出

那么能不能让这些子任务同时执行呢？于是人们又提出了线程的概念，让一个线程执行一个子任务，这样一个进程就包含了多个线程，每个线程负责一个单独的子任务。

使用线程之后，事情就变得简单多了。当用户使用扫描病毒功能时，就让扫描病毒这个线程去执行。同时，如果用户又使用清理垃圾功能，那么可以先暂停扫描病毒线程，先响应用户的清理垃圾的操作，让清理垃圾这个线程去执行。响应完后再切换回来，接着执行扫描病毒线程。

注意：操作系统是如何分配时间片给每一个线程的，涉及到线程的调度策略，有兴趣的同学可以看一下《操作系统》，本文不做深入详解。

总之，进程和线程的提出极大的提高了操作提供的性能。进程让操作系统的并发性成为了可能，而线程让进程的内部并发成为了可能。

多进程的方式也可以实现并发，为什么我们要使用多线程？

多进程方式确实可以实现并发，但使用多线程，有以下几个好处：

  • 进程间的通信比较复杂，而线程间的通信比较简单，通常情况下，我们需要使用共享资源，这些资源在线程间的通信比较容易。

  • 进程是重量级的，而线程是轻量级的，故多线程方式的系统开销更小。

进程和线程的区别

进程是一个独立的运行环境，而线程是在进程中执行的一个任务。他们两个本质的区别是是否单独占有内存地址空间及其它系统资源（比如I/O）：

  • 进程单独占有一定的内存地址空间，所以进程间存在内存隔离，数据是分开的，数据共享复杂但是同步简单，各个进程之间互不干扰；而线程共享所属进程占有的内存地址空间和资源，数据共享简单，但是同步复杂。

  • 进程单独占有一定的内存地址空间，一个进程出现问题不会影响其他进程，不影响主程序的稳定性，可靠性高；一个线程崩溃可能影响整个程序的稳定性，可靠性较低。

  • 进程单独占有一定的内存地址空间，进程的创建和销毁不仅需要保存寄存器和栈信息，还需要资源的分配回收以及页调度，开销较大；线程只需要保存寄存器和栈信息，开销较小。

另外一个重要区别是，进程是操作系统进行资源分配的基本单位，而线程是操作系统进行调度的基本单位，即CPU分配时间的单位 。

1.7 多线程模型

分用户线程和内核线程。

  • 多对一模型：多个用户线程对应一个内核线程。一旦阻塞，全要等待。

    • 早期 Java 使用，现已抛弃

    • 无法利用多核

  • 一对一模型：创建一个用户线程就对应一个内核线程。

    • Linux、Windows 使用

    • 限制了系统支持的线程数量

  • 多对多模型：多路复用多个用户级线程到同样数量或更少数量的内核线程

    • 开发人员可以创建任意多的用户线程，并且相应内核线程能在多处理器系统上并发执行。

  • 双层模型：多对多模型 与 一对一模型 的组合

1.8 进程调度基本概念

进程执行的周期：

  • CPU 执行：少量长 CPU 执行

  • I/O 执行：大量短时间 CPU 执行

控制权的获取方式：

  • 抢占式调度：

    • 在这种调度方式下，操作系统可以在任何时候中断当前正在运行的进程，并将CPU控制权分配给另一个进程。这意味着进程在运行时可以被“抢占”。

    • 进程可以在运行状态被直接中断并切换到等待状态，或者被终止。

  • 非抢占式调度：

    • 在这种调度方式下，一旦CPU控制权被分配给某个进程，该进程就会一直运行，直到它自己主动释放CPU（比如通过I/O操作进入等待状态，或者完成任务后终止）。操作系统不会在进程运行期间中断它。

    • 进程在运行状态下不会直接被中断，它会在完成运行后进入就绪状态等待下一次调度，或者在等待状态时因条件满足而切换到就绪状态。

分派程序的功能包括：

  • 切换上下文

  • 切换到用户模式

  • 跳转到用户程序的合适位置，以便重启程序

进程调度准则：

  • CPU使用率：应该使得 CPU 尽可能忙碌。

  • 吞吐量：一个时间单元内进程完成的数量。

  • 周转时间：从进程提交到进程完成的时间。包括了等待进入内存、在就绪队列中等待、在CPU执行、在I/O执行的时间。

  • 等待时间：在就绪队列中等待所花时间之和。CPU调度只影响等待时间，不影响CPU执行和I/O时间。

  • 响应时间：从提交请求到产生第一响应的时间。

1.9 进程调度算法

1.9.1 先到先服务算法 FCFS

FCFS 调度，使用 FIFO 队列维护

非抢占式调度

  • 平均等待时间长

  • 可能会出现护航效果：I/O密集的小进程一直跟在CPU密集的大进程之后

1.9.2 最短作业优先调度算法 SJF

SJF 调度，小进程先做

可以是抢占和非抢占式调度

  • 算法最优

  • 不可行，无法知道下次 CPU 执行的长度

1.9.3 优先级调度算法

优先级调度，优先级小的进程先做

可以是抢占和非抢占式调度

  • 无穷阻塞/饥饿：会让某个低优先级算法一直等待CPU

  • 解决方案：老化 逐渐增加在系统中等待很长时间的进程的优先级（待的越久 优先级越高）

1.9.4 轮转调度算法 RR

RR 调度

为每个进程分配一个时间片。若时间片内的进程执行完成，则直接执行下一个进程；若未完成，则上下文切换到下一个进程，把原进程放到队列尾部。

抢占式调度

  • 算法性能取决于时间片的大小

    • 时间片太小：上下文切换多

    • 时间片太大：变成FCFS

1.9.5 多级队列调度

把就绪队列分成多个单独队列

  • 每个队列有自己的调度算法

  • 队列之间也有调度，如优先级算法 或 时间片

1.9.6 多级反馈队列调度

在多级队列调度的基础上，允许进程在队列之间迁移。

假如有一组队列，优先级从高到低的队列分别使用 RR（时间片=8）、RR（时间片=16）、FCFS

  • 若进程占用过多的CPU时间，超出时间片太多，则分配到更低的优先级队列（I/O 密集型和交互会放到更高优先级队列）

  • 若在较低的优先级队列等待时间过长，则会被移到更高优先级队列（老化解决饥饿）

1.10 线程调度

线程是调度的最小单位，内核级线程是OS所调度的。

LWP（轻量级进程）：LWP是用户线程和内核线程之间的中间数据结构。对于用户级线程库，LWP表现为虚拟处理器，以便应用程序调度并运行用户线程

  • 每个LWP都连接到一个内核线程上，该内核线程被操作系统调度到物理处理器上运行

  • 如果内核线程阻塞（例如等待I/O操作完成），则LWP也会阻塞，进而导致连接到LWP的用户级线程阻塞

回调处理程序（upcall handler）：当内核需要通知应用程序某个特定事件（如一个线程即将阻塞或已经准备好运行）时，会通过回调处理程序来实现。线程库中的回调处理程序会处理这些回调，例如，当一个用户线程要阻塞时，内核会发出一个upcall，线程库中的回调处理程序会保存阻塞线程的状态，并释放其运行的LWP之后，回调处理程序会调度另一个适合在新的LWP上运行的线程。

进程竞争范围 PCS：

  • 系统线程库调度用户级线程，在可用 LWP 上运行。

  • 多对一、多对多模型

  • 一般采用优先级调度，优先级可由程序员设置

系统竞争范围 SCS：

  • 决定内核级线程调度到一个处理器上

  • 一对一模型

1.11 多处理器调度

  • 非对称多处理：

    • 一个处理器处理调度任务，其它所有处理器只执行用户代码

    • 允许处理器移动

  • 对称多处理 SMP：

    • 每个处理器有私有的就绪进程队列，每个处理器自我调度

    • 一般不允许处理器移动（CPU亲和性）

为什么要 CPU 亲和性？若进程移到其它 CPU 上，则原CPU的缓存要设成无效，新CPU缓存要重新填充。

  • 软亲和性：允许进程在处理器间移动

  • 硬亲和性：提供系统调用支持某个进程只在一个处理器子集上

负载平衡：在SMP系统中设法将负载平均分配到所有处理器。（会抵消掉 CPU 亲和性的优点，失去缓存）

  • 推迁移：由忙的发起

    • 一个特定任务周期检查每个 CPU 的负载，若不平衡则把超载处理器的进程 push 到闲的处理器

  • 拉迁移：由闲的发起

    • 空闲处理器从超载处理器 pull 一个等待任务

缓存有效 与 负载均衡 是无法同时满足的

1.12 实时 CPU 调度

实时操作系统：当一个实时进程需要 CPU 时，立即响应。

  • 软实时系统：必需，不保证调度关键实时进程，只保证优先级。

  • 硬实时系统：必须，任务必须在截止时间前完成。若在截止时间后完成则等同于没有完成。

提供抢占的、基于优先级的调度程序都仅保证软实时功能，硬实时系统需要进一步保证实时任务在截止期限内得到服务。

（以下都讨论硬实时系统）

1.12.1 调度进程的特性

这些进程是周期性的，若获得 CPU ，其具有：

  • 固定的处理时间 t

  • CPU 应处理的截止时限 d

  • 周期 p

应保证： p >= d >= t

准入控制：进程向调度器公布截止时限，若调度程序不能保证任务能在截止时间前得以服务，拒绝请求，否则承认进程。

1.12.2 实时调度算法

若较低优先级任务正在运行，而较高优先级进程可以运行时，抢占

  • 单调速率调度（RM调度）：“积极的优先级高”

    • 周期越短的任务，优先级越高

    • 优先级固定

    • 最优，但CPU利用率有限，无法最大化CPU资源；不能保证可以调度满足其截止时限

  • 最早截止期限有限（EDF调度）：“急的先做”

    • 截止期限越早，优先级越高

    • 优先级可能进行调整

    • 不要钱进程是周期性的，唯一要求是进程变成可运行时应宣布截止期限

  • 比例分享调度

  • POSIX 实时调度……

2. 进程管理：并发

2.1 临界区问题及同步机制【重点】

2.1.1 临界区的概念与保护机制

竞争条件：多个进程并发访问和操作统一数据，且执行结果与特定访问顺序有关

临界区：操作共享数据的代码段

剩余区：剩余区是指进程代码中除了进入区、临界区和退出区之外的其余部分。在这部分代码中，进程不访问临界资源，可以与其他进程并发执行，不受互斥约束。

这两个区域是进程在并发执行时对共享资源进行访问和操作的基本结构。进程在执行时，首先会进入进入区（Entry Section），在进入区会进行检查以确保可以安全进入临界区。一旦进入临界区，进程将访问或修改共享资源。离开临界区后，进程将进入退出区（Exit Section），在这里会进行一些清理工作，比如释放锁，以便其他进程可以进入临界区。退出区之后，进程将继续执行剩余区的代码。

所有解决方案需要满足三条要求：

  1. 互斥：某一个进程进入了临界区，其他进程就不能进入。

  2. 前进：如果没有进程在临界区执行，则必须确保一个进程进入临界区。

  3. 有限等待：一个进程从请求进入临界区，直到该请求被允许，必须有限等待。

2.1.2 Peterson 解决方案

基于软件，对双进程有效，对单资源共享有效

int turn;            // 用来指示哪个进程可以进入临界区，初始化时可以设置为0或1
boolean flag[2];     // 用来表示两个进程是否准备进入临界区，flag[0]对应进程P0，flag[1]对应进程P1

do {
    // 进程Pi（这里用i表示）想要进入临界区
    flag[i] = true;  // 进程Pi设置flag[i]为true，表示它想要进入临界区
    turn = j;        // 进程Pi设置turn为j，表示它允许进程Pj先进入临界区（如果Pj也想进入）

    // 等待直到进程Pi可以进入临界区
    while (flag[j] && turn == j){;}
        // 如果进程Pj也想进入临界区（flag[j]为true）并且按照turn的指示应该Pj先进入（turn==j），
        // 那么进程Pi就会在这里等待，直到条件不再满足（即Pj离开临界区或者turn的值改变）

    //
    // 临界区
    // 在这部分代码中，进程Pi可以安全地访问共享资源，因为已经确保了没有其他进程会同时进入临界区
    //

    flag[i] = false; // 进程Pi完成对临界资源的访问后，设置flag[i]为false，表示它不再想要进入临界区
    // 
    // 剩余区
    // 在这部分代码中，进程Pi执行除了访问共享资源之外的其他任务，此时它不会进入临界区
    // 
    
} while(true)

2.1.3 硬件同步的原子指令 TAS 与 CAS

原子指令：

  • 不可中断

  • 若同时执行在不同 CPU 上，要按照任意次序来执行

两个原子指令：

  • 不可被中断

  • 若两个指令同时执行在不同 CPU 上，那么它们会按照任意次序顺序执行

TAS：

// 将 *target 改为 true，并返回原来的值
boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    
    return rv;
}

CAS：原子性赋值

// 若 *value 等于 预期旧值 则更新，否则不更新 返回旧值
int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    
    if (*value == expected) *value = new_value;
    
    return temp;
}

2.1.4 互斥锁 Mutex

acquire() {
    // 忙等待
    while (!available) {;}
    
    available = false;
}

release() {
    available = true;
}

  • 忙等待

  • 自旋锁：线程进入时需要连续循环地调用 acquire()

类似 “乐观锁” 自旋

2.1.5 信号量 Semaphore 【考应用级别】

整个过程会出现上下文切换。

typedef struct {
    int value;
    struct process *list;
} semaphore;

// 减操作 原子指令
wait(semaphore *S) {
    S->value --;
    if (S->value < 0) {
        add this process to S->list;
        block();
    }
}

// 加操作 原子指令
signal(semaphore *S) {
    S->value ++;
    if (S->value >= 0) {
        remove a process P from S->list;
        wakeup(P);      // 放到就绪队列中，等待CPU调度
    }
}

类似 “悲观锁” 阻塞

这些原子指令都需要使用硬件的CAS、自旋锁等以确保原子执行。

需要会用这个信号量来进行编程，可以自行看考试题。

2.1.6 管程 Monitor

2.2 经典同步问题

2.2.1 有界缓冲问题

类似生产者—消费者模型

回到 #1.5.1 共享内存模型：

生产者进程：若缓冲区满则必须等待

消费者进程：若缓冲区空则必须等待

// 共享内存缓冲区
item buffer[BUFFER_SIZE];
// 数据指针
int in = 0;  // 写位置，指向缓冲区下一个空位
int out = 0; // 读位置，指向缓冲区第一个满位

// producer
while(true){
    while((in + 1)%BUFFER_SIZE == out){ ;} // 缓冲区满，阻塞
    
    buffer[in] = next_produced;
    in = (in + 1)%BUFFER_SIZE;
}
// consumer
while(true){
    while(in == out){ ;} // 缓冲区空，阻塞
    
    next_consumed = buffer[out];
    out = (out + 1)%BUFFER_SIZE;
}

这种实现有一个缺点：只允许缓冲区同时最多只有 BUFFER_SIZE - 1 项，需要浪费一个位置来区分“满”和“空”的情况。

解决方案：增加一个整型变量 int counter = 0，缓冲区增加一项 counter++，缓冲区减少一项 counter--，这样就能利用 BUFFER_SIZE 项数据，不至于浪费一项数据。

// 共享内存缓冲区
item buffer[BUFFER_SIZE];
// 数据指针
int in = 0;  // 写位置，指向缓冲区下一个空位
int out = 0; // 读位置，指向缓冲区第一个满位
int counter = 0;

// producer
while(true){
    while(counter == BUFFER_SIZE){ ;} // 缓冲区满，阻塞
    
    buffer[in] = next_produced;
    in = (in + 1)%BUFFER_SIZE;
    counter++;
}

// consumer
while(true){
    while(counter == 0){ ;} // 缓冲区空，阻塞
    
    next_consumed = buffer[out];
    out = (out + 1)%BUFFER_SIZE;
    counter--;
}

不过显然，这种实现方式是会出现不安全问题的：有两个进程在共享 counter这个变量。我们需要用上面的并发同步原语去解决这个问题。

参考书上直接换了一种想法：使用 n 个缓冲区，每个缓冲区存 1 个数据项；再用信号量来满足互斥要求，并维护空和满的缓冲区数量：

int n;                 // n 个缓冲区 每个缓冲区存 1 个数据项
semaphore mutex = 1;   // 提供缓冲区访问的互斥要求
semaphore empty = n;   // 空缓冲区数量
semaphore full = 0;    // 满缓冲区数量

// producer
do {
    wait(empty); // 原子性地 empty--，若 empty < 0 ，为满不可写
    wait(mutex); // 互斥要求，并发控制
    
    // 执行生产过程 
   
    signal(mutex)； // 释放锁
    signal(empty);  // empty++
} while(true);

// consumer 与 producer 对称即可
do {
    wait(full);
    wait(mutex);
    
    // 执行消费过程
     
    signal(mutex);
    signal(full);
} while(true);

2.2.2 读者-写者问题

类似数据库的读写锁

多个读者的情况下，如何实现“读写锁”：读读共享、读写互斥；同时我要统计读者数量。

  • Semaphore rw_mutex: 初始化为1，用于保护对共享资源的写操作，确保写者互斥访问。

  • Semaphore mutex: 初始化为1，用于保护对read_count变量的访问，确保其操作的原子性。

  • int read_count: 计数器，记录当前正在读的读者数量，初始化为0。

我怎么感觉这个 read_count 其实就是个信号量呢，只不过我要知道它具体的值，所以用了另外一个信号量锁区维护……

  • 写过程拿到 rw_mutex 就可以写

  • 读过程就比较麻烦了

    • 读者首先等待mutex，以确保对read_count的修改是原子的。

    • 增加read_count，如果这是第一个读者（read_count == 1），则等待rw_mutex，阻止写者访问。

    • 释放mutex，然后进行读操作。

    • 读操作完成后，再次等待mutex，减少read_count，如果read_count变为0，则释放rw_mutex，允许写者访问。

    • 释放mutex，完成读者进程。

semaphore rw_mutex = 1; // 保护对共享资源的写操作
semaphore mutex = 0;    // 保护对read_count变量的访问，确保操作原子性
int read_count = 0;     // 记录当前正在读的读者数量

// writer
do {
    wait(rw_mutex);
    
    // 写过程
    
    signal(rw_mutex);
} while(true);

// reader
do {
    wait(mutex);   // 等待mutex，以确保对read_count的修改是原子的
    read_count++;
    // 如果这是第一个读者（read_count == 1），则等待rw_mutex，阻止写者访问。
    if (read_count == 1) wait(rw_mutex); 
    // 由于读读共享，所以要释放mutex，然后进行读操作
    signal(mutex);
    
    // 读过程
    
    wait(mutex);   // 等待mutex，以确保对read_count的修改是原子的
    read_count--;
    // 如果read_count变为0，则释放rw_mutex，允许写者访问。
    if (read_count == 0) signal(rw_mutex);
    // 释放mutex，完成读者进程。
    signal(mutex);
} while(true);

2.2.3 哲学家就餐问题

死锁的经典场景

信号量一开始的解决方法，可能会出现死锁：

semaphore chop[5]; // 五支筷子

do {
    wait(chop[i]);           // 拿左手筷子
    wait(chop[(i + 1) % 5]); // 拿右手筷子
    
    // 进食
    
    signal(chop[i]);            // 放左手筷子
    siganl(chop[(i + 1) % 5]);  // 放右手筷子
} while(true);

无死锁的解决方案 1：原子性地左右手拿筷子

semaphore chop[5]; // 五支筷子
semaphore mutex = 1;

do {
    wait(mutex);
    {
        wait(chop[i]);           // 拿左手筷子
        wait(chop[(i + 1) % 5]); // 拿右手筷子
    }
    signal(mutex);
    
    // 进食
    
    signal(chop[i]);            // 放左手筷子
    siganl(chop[(i + 1) % 5]);  // 放右手筷子
} while(true);

无死锁的解决方案 2：使用管程，我不会，考试考我就空着，祝大家好运。

2.3 死锁【重点】

2.3.1 死锁的必要条件【pxf说必考】

  • 互斥：一个资源只能由一个进程占用。

  • 占有并等待：一个进程必须占用一个资源，并等待另一个资源。

  • 非抢占：资源被一个进程占有时，不能被另一个进程抢占。

  • 循环等待：A 请求 B 的资源，B 请求 C 的资源，C 请求 A 的资源，而它们都占用自己的资源。

四个条件同时成立才会出现死锁。

2.3.2 死锁和饥饿的区别【理解】

  • 死锁是多个进程之间的互相等待，导致所有相关进程都无法继续执行。

  • 饥饿是单个进程由于资源分配不公平，长时间无法获得资源，导致无法执行。

两者的根本区别在于：

  • 死锁涉及多个进程的循环等待。

  • 饥饿是单个进程被无限期推迟，没有循环等待。

2.3.3 资源分配图

  • 进程节点P：圆圈

  • 资源节点R：方块

  • 申请边 P -> R：进程 P 已经申请使用资源 R 的一个实例

  • 分配边 R -> P: 资源 R 的一个实例已经被分配给进程 P

一个进程多个实例是什么意思？待补充

如果是单实例的情况下出现环，则一定发生死锁

如果是多实例的情况下出现环，则可能发生死锁

2.3.4 死锁预防方法

  • 针对互斥：

    • 只读文件、共享资源

  • 针对占有并等待：

  • 非抢占：资源被一个进程占有时，不能被另一个进程抢占。

  • 循环等待：A 请求 B 的资源，B 请求 C 的资源，C 请求 A 的资源，而它们都占用自己的资源。

2.3.5 死锁避免方法【考考考】

  • 单实例：资源分配图算法

对资源的申请，把申请边变成分配边后，如果没有环就允许申请，如有环就不允许申请

  • 多实例：银行家算法

IF ( req_i <= need_i )
    IF ( req_i <= avail_i )
         _____________________;
        alloc_i = alloc_i + req_i;
         _____________________;
        do safety check algorithm;
    ELSE
        waiting;
    End IF
ELSE
    output error message;
End IF

  • 安全性算法伪代码

safety check algorithm:
    work = avail_i;
    For all i, finish[i] = false;
    For all i do
        IF ( finish[i] == false && need_i <= work )
             _____________________;
             _____________________;
        End IF
    End For
    IF for all i,  _____________________
        Then the system is safety
    End IF

2.3.6 死锁检测

类似上面的死锁避免算法，它和死锁避免的区别是：

  • 死锁避免是采用某个协议

  • 死锁检测是不采用协议，确保死锁不发生，先检测再恢复。

大多数系统都会假设死锁不会发生，既不采用任何协议进行死锁避免，也不在系统进入死锁的时候进行检测和恢复，为了减少代价，操作系统会完全忽略这个问题。

也就是说，死锁问题在这些系统中不归操作系统管，归用户管。

2.4 抛开多线程：基于事件的并发

原书第 33 章

之前我们学过可以用多线程模型来解决并发问题，但是这里有几个显著的问题：

  • 锁机制复杂，容易发生线程安全、死锁等问题；

  • 操作系统来决定CPU调度，用户进程无法控制线程调度；

  • 对于I/O密集型任务来说，上下文切换频繁，开销大

当一个线程执行I/O操作时，它会被操作系统挂起（阻塞），直到I/O操作完成。在此期间，CPU会切换到其他线程以继续执行任务。如果有大量线程都在等待I/O操作完成，操作系统会频繁地在这些线程之间进行上下文切换，以确保CPU资源被充分利用。

为了规避这几个问题，举两个适合使用单线程的场景：

场景1 缓存：众所周知由于I/O的原因，通过硬盘访问的数据比较慢，可能会出现慢查询的情况，因此我们必须采用多线程模型以防阻塞；然而对于缓存来说，我们可以把数据放进易失性内存中以加快访问速度，这样会大幅提高数据的存取速度，不可能出现慢查询，于是可以干脆抛弃多线程与锁机制，直接使用单线程。最典型的一个实现就是 Redis。

场景2 浏览器渲染进程的JS内核引擎：JS引擎线程负责解析Javascript脚本，运行代码。由于JavaScript是可操纵DOM的，如果在修改这些元素属性同时渲染界面（即JS线程和UI线程同时运行），那么渲染线程前后获得的元素数据就可能不一致了。因此为了防止渲染出现不可预期的结果，浏览器设置GUI渲染线程与JS引擎为互斥的关系，当JS引擎执行时GUI线程会被挂起，GUI更新则会被保存在一个队列中等到JS引擎线程空闲时立即被执行。

参考

  1. pxf 操作系统

  2. Operating Systems: Three Easy Pieces