操作系统学习手记01

最近在啃操作系统里的进程与线程管理

L9 多进程图像

我们学习的起点，要从“进程”这个核心概念说起。

简单来说，一个进程（Process）就是一个正在执行的程序的实例。当我们双击运行一个 .exe 文件时，操作系统就会为它创建一个进程。这个进程是操作系统进行资源分配和调度的基本单位。

为了管理好进程，操作系统需要为每个进程维护一个信息集合，这包括：

• 程序代码：也就是程序的指令序列。
• 数据：程序运行过程中需要用到的变量、工作空间、缓冲区等。
• 资源：进程持有的系统资源，比如打开的文件、分配的内存、使用的I/O设备。
• 进程控制块（PCB - Process Control Block）：这是进程存在的唯一标识。它是一个数据结构，里面存储了操作系统管理进程所需的所有信息，比如进程ID、进程当前状态（就绪、运行、阻塞）、CPU寄存器现场、内存管理信息、I/O状态信息等。

所谓的“多进程图像”，其实就是操作系统在内存中维护的、所有进程的PCB集合以及它们之间的关系。操作系统通过这张“图”，掌握着系统中所有进程的动态，从而能够有效地进行管理和调度。正是通过在不同进程之间快速切换（上下文切换），操作系统在宏观上实现了多任务并行处理的假象，即便是在单核CPU上，也能让我们感觉电脑可以“一心多用”。

L11 & L12：用户级线程 vs 核心级线程

多进程模型虽然实现了并发，但它有两个显著的缺点：一是创建进程的开销大，需要分配独立的地址空间和大量内核资源；二是进程间上下文切换成本高，需要保存和恢复大量的状态信息。

为了解决这些问题，“线程”（Thread）的概念应运而生。线程也被称为轻量级进程（Lightweight Process），它是一个进程内部的执行单元，是CPU调度的基本单位。一个进程可以包含多个线程，这些线程共享该进程的地址空间和大部分资源（如文件句柄），但每个线程拥有自己独立的执行栈、寄存器和程序计数器。

由于线程间的切换只涉及少量私有资源的切换，而不需要切换整个进程的地址空间，因此效率远高于进程切换。关于线程的实现，主要有两种模型：

L11 用户级线程（User-level Threads）

在这种模型中，线程的管理（创建、销毁、同步、调度）完全由用户空间的线程库来完成，操作系统内核对此一无所知。内核只看得到进程，看不到进程内部的线程。

• 优点：
  1. 高效：线程切换不需要进入内核态，没有系统调用的开销，速度非常快。
  2. 灵活性高：调度算法可以由应用程序根据自身需求定制。
• 缺点：
  1. 阻塞问题：如果一个线程因为执行了一个阻塞式的系统调用（如 read() 文件）而被阻塞，内核会认为整个进程都被阻塞了，从而暂停该进程的执行。这会导致该进程内所有其他本可以运行的线程也无法执行。
  2. 无法利用多核：由于内核只将CPU时间片分配给进程，它无法将一个进程内的多个线程分别调度到多个CPU核心上并行执行。

L12 核心级线程（Kernel-level Threads）

在这种模型中，线程的管理工作由操作系统内核来完成。线程的创建、销毁和切换都需要通过系统调用陷入内核。

• 优点：
  1. 真正的并行：内核可以识别到进程内的多个线程，因此可以将它们调度到不同的CPU核心上同时运行。
  2. 阻塞健壮性：当一个线程被阻塞时，内核可以立刻调度该进程内的其他就绪线程来运行，整个进程的执行不会被中断。
• 缺点：
  1. 开销较大：线程管理的任何操作都需要从用户态切换到内核态，相比用户级线程，存在一定的性能开销。

目前主流的现代操作系统，如 Windows 和 Linux，都主要采用核心级线程模型，因为它能更好地利用多核处理器的硬件优势，并解决阻塞问题，这在现代计算环境中至关重要。

L13 核心级线程实现实例

了解了理论模型，我们来看看实际的实现。以 Linux 为例，它的线程实现非常有特点。在Linux内核中，并没有严格区分进程和线程，它们都被统一视为“任务”（task），并用 task_struct 结构体来描述。

Linux 通过 clone() 系统调用来创建新任务。fork() 系统调用是创建一个几乎与父进程完全一样的子进程（采用写时复制技术共享初始内存），而 clone() 则提供了更细粒度的控制，允许新创建的任务与父任务有选择地共享资源。

clone() 调用时可以传入一系列标志位，来指定哪些资源需要共享，例如：

• CLONE_VM：共享地址空间。
• CLONE_FS：共享文件系统信息。
• CLONE_FILES：共享打开的文件描述符。
• CLONE_SIGHAND：共享信号处理器。

当一个新任务通过 clone() 创建，并与父任务共享了地址空间和其他关键资源时，从操作系统的角度看，这个新任务就是一个线程。如果创建时选择不共享这些资源，那么它就是一个传统的进程。我们平时在应用层调用的 pthread_create 库函数，其底层实现就是封装了 clone() 系统调用。这种将进程和线程统一为任务的设计，非常优雅和高效。

L14 CPU 调度策略

系统中通常有大量处于就绪状态的进程/线程，但CPU核心数量有限。CPU调度器的任务就是，根据某种策略，从就绪队列中选择一个任务，将CPU的使用权分配给它。一个好的调度策略对系统性能至关重要，影响着系统的吞吐量、周转时间和响应时间。

以下是一些经典的调度策略：

1. 先来先服务（FCFS, First-Come, First-Served）
   • 机制：按进程到达就绪队列的先后顺序进行调度。实现简单。
   • 问题：对短作业不友好。如果一个计算量很大的长作业先到达，会导致后续的短作业长时间等待，即“护航效应”。
2. 最短作业优先（SJF, Shortest Job First）
   • 机制：优先选择预计运行时间最短的作业。可以证明其平均等待时间是最优的。
   • 问题：需要预测作业的运行时间，这很难做到。可能导致长作业一直得不到调度，产生“饥饿”现象。其抢占式版本称为“最短剩余时间优先”（SRTN）。
3. 轮转调度（RR, Round Robin）
   • 机制：为每个进程分配一个固定的“时间片”。进程运行一个时间片后，如果还未完成，就中断它，并将其放回就绪队列的末尾，然后调度下一个进程。
   • 优点：公平，响应及时，非常适合分时和交互式系统。
   • 缺点：性能受时间片大小影响。时间片过大则退化为FCFS，过小则上下文切换的开销占比过高。
4. 优先级调度（Priority Scheduling）
   • 机制：为每个进程分配一个优先级，CPU总是选择优先级最高的进程执行。
   • 问题：可能导致低优先级进程“饥饿”。
   • 解决方案：可以采用“老化”（Aging）技术，动态提升长时间等待的进程的优先级。
5. 多级队列调度（Multilevel Queue Scheduling）
   • 机制：将就绪队列划分为多个独立的队列，如前台（交互式）队列和后台（批处理）队列。每个队列有自己的调度算法（如前台用RR，后台用FCFS），队列之间也可以设置优先级。
   • 问题：不够灵活，进程被分配到某个队列后通常不能移动。
6. 多级反馈队列调度（Multilevel Feedback Queue Scheduling）
   • 机制：是多级队列的改进版，允许进程在队列之间移动。例如，新进程进入最高优先级队列，若在一个时间片内未完成，则降级到次一级队列。这种机制能够很好地满足不同类型进程的需求，是现代操作系统中广泛采用的一种调度策略。

L15 一个实际的 schedule 函数

schedule() 函数是操作系统内核调度器的具体实现。它在需要进行CPU调度的时刻被调用，例如：

• 当前进程的时间片耗尽（由时钟中断触发）。
• 当前进程主动放弃CPU（例如，等待I/O完成而进入阻塞状态）。
• 一个更高优先级的进程变为就绪状态（在抢占式系统中）。
• 当前进程执行完毕。

schedule() 函数的核心逻辑通常包括：

1. 旧进程状态保存：如果需要切换，首先要保存当前正在运行进程的上下文（即所有CPU寄存器的值、程序计数器、栈指针等）到其PCB中。
2. 新进程选择：根据系统的调度策略，从就绪队列中选择出下一个要运行的进程。
3. 新进程状态恢复：将选中的新进程的上下文从其PCB中加载到CPU的相应寄存器中。
4. 控制权转移：CPU从新加载的程序计数器所指向的地址开始执行，从而将控制权交给新进程。

这个从一个进程切换到另一个进程的过程，被称为“上下文切换”（Context Switch），它是实现多任务处理的基础，但本身也存在一定的性能开销。

L16 进程同步与信号量

当多个线程共享数据时，如果没有适当的同步机制，就可能引发问题。其中最典型的是“竞态条件”（Race Condition）。

• 临界区（Critical Section）：指程序中访问共享资源（如共享变量、共享文件）的一段代码。
• 竞态条件：当多个线程并发执行，进入同一个临界区时，最终结果取决于这些线程执行的相对时序。这种不确定性常常会导致程序错误。

为了保证数据的一致性，我们需要实现“互斥”（Mutual Exclusion），即确保在任何时刻最多只有一个线程能进入临界区。

信号量（Semaphore） 是由Dijkstra提出的一种经典的同步工具。它是一个受保护的整型变量，只能通过两种原子的（不可中断的）操作来访问：

• P(S) 或 wait(S)：申请资源。S的值减1。如果结果小于0，表示资源不足，则调用该操作的线程被阻塞。
• V(S) 或 signal(S)：释放资源。S的值加1。如果结果小于或等于0，表示有线程正在等待该资源，则唤醒一个等待中的线程。

根据初始值的不同，信号量可分为：

• 二值信号量（Mutex Lock）：初始值为1，用于实现互斥锁，保证临界区只有一个线程进入。
• 计数信号量：初始值大于1，用于管理一组有限的资源，例如，一个有N个缓冲区的生产者-消费者问题。

L17 对信号量的临界区保护

这里有一个关键问题：P 和 V 操作本身也访问了共享变量 S，它们自身也构成了临界区。如果不对P和V操作的执行过程加以保护，让它们可以被中断，那么信号量机制本身就会因为竞态条件而出错。因此，P和V必须是原子操作。

实现原子性的方法依赖于硬件支持：

1. 单处理器系统：可以在执行P或V操作期间禁用中断。当中断被禁用时，就不会发生进程切换，从而保证了操作的原子性。操作完成后再重新启用中断。
2. 多处理器系统：禁用中断的方法不再有效，因为其他CPU核心仍在运行。此时需要依赖硬件提供的特殊原子指令，例如：
   • Test-and-Set：原子地读取一个内存位置的值，并同时将其设置为1。
   • Compare-and-Swap (CAS)：原子地比较内存中的值与一个给定值，如果相等，则将该内存位置更新为一个新值。

这些硬件指令为上层同步机制的实现提供了最底层的原子性保证。

L18 信号量的代码实现

我们可以用伪代码来描述信号量的数据结构和操作：

typedef struct {
    int value; // 信号量的值
    struct process *list; // 等待该信号量的进程/线程队列
} semaphore;

void wait(semaphore *S) {
    // 禁用中断或使用原子指令保护
    S->value--;
    if (S->value < 0) {
        add_this_process_to(S->list);
        block(); // 阻塞当前进程
    }
    // 恢复中断
}

void signal(semaphore *S) {
    // 禁用中断或使用原子指令保护
    S->value++;
    if (S->value <= 0) {
        process P = remove_process_from(S->list);
        wakeup(P); // 唤醒一个等待的进程
    }
    // 恢复中断
}

这段代码直观地展示了信号量的工作原理。当资源不足时（value < 0），进程将自己加入等待队列并阻塞。当有进程释放资源时（signal），如果等待队列不为空（value <= 0），就唤醒一个等待者。

L19 死锁处理

同步机制虽然解决了竞态问题，但也可能引入一种更棘手的问题——死锁（Deadlock）。

死锁是指两个或多个进程因互相持有对方正在等待的资源，而都无法向前推进的僵持状态。

死锁的发生必须同时满足以下四个必要条件：

1. 互斥：资源一次只能被一个进程使用。
2. 持有并等待：进程至少持有一个资源，并且在等待获取其他进程持有的资源。
3. 非抢占：资源不能被强制地从持有它的进程中剥夺。
4. 循环等待：存在一个进程等待链 {P0, P1, …, Pn}，其中 P0 等待 P1 的资源，P1 等待 P2 的资源，…，Pn 等待 P0 的资源。

处理死锁的策略主要有四种：

1. 死锁预防（Prevention）
   • 思路：通过设计系统规则，破坏四个必要条件中的一个或多个。例如，要求进程一次性申请所有资源（破坏“持有并等待”），或对资源类型进行排序，要求进程按序申请（破坏“循环等待”）。
   • 缺点：通常会降低资源利用率，对编程的限制也较大。
2. 死锁避免（Avoidance）
   • 思路：在资源分配时，系统动态地检查这次分配是否可能导致未来发生死锁。如果存在风险，则不予分配。
   • 经典算法：银行家算法。通过检查是否存在一个“安全序列”，来判断系统是否处于安全状态。
   • 缺点：需要进程预先声明所需的最大资源量，且算法开销较大。
3. 死锁检测与解除（Detection & Recovery）
   • 思路：允许死锁发生，但系统会定期运行检测算法（如基于资源分配图）来判断当前是否已发生死锁。
   • 解除方法：如果检测到死锁，则采取措施来打破循环等待，例如终止一个或多个死锁进程，或者抢占某些进程的资源。
4. 忽略该问题（Ostrich Algorithm）
   • 思路：假定死锁不会发生。这是因为在通用操作系统中，死锁发生的概率较低，而预防或避免死锁的机制会带来显著的性能开销。因此，很多系统选择不处理死锁，而将问题留给用户（例如，手动重启卡死的程序）。

总结

梳理完这一章，我对操作系统如何管理并发任务有了更深入的理解。从进程的抽象，到线程的引入，再到CPU调度策略的权衡，以及为保证数据一致性而设计的复杂同步机制，最后还要应对死锁这样的疑难杂症，整个体系充满了精巧的设计与权衡。