快速hodl，操作系统精华摘要

原创：小姐姐味道（微信公众号ID：xjjdog），欢迎分享，转载请保留出处。

在实践的道路上走的太远，就需要回头看一下理论。操作系统，可以说是基础知识中的重中之重。

它不像汽车的发动机一样，加油就可以跑。相反，操作系统并不是一个精密的、固定的仪器，它脆弱、多变，在不同的场景中充满了不确定性。

调度永远是操作系统的核心，包括进程调度、内存调度等。而I/O的调度是设计最困难的部分。

在整个的操作系统中，每个部件为了高效的完成工作，大量使用了缓存、缓冲、批量、对齐等手段。当然，核心还是数据结构。

在实际的落地中，操作系统也并不是枯燥无味的学术派。相反，它的某些关键部件，经过了严格的实践和多角度的评测，最终，我们所使用的操作系统，只是在整体上达到了比较好的状态，它仍然是大量互斥资源的tradeoff。

了解操作系统，可以助力设计效率更高的高并发应用、多线程应用，在高吞吐、稳定性方面也能有更多的思考。

【重要理论】根据局部性原理，当一块数据被取人高速缓存，以满足一次存储器访问时，很可能紧接着多次访问的数据是该块中的其他字节。

进程的两个基本元素，是程序代码和代码相关的数据集，而进程控制快包含了充分的信息，可以根据这些信息中断和恢复进程的执行，就好像进程未被中断过那样。

进程的5种状态：运行态、就绪态、阻塞/等待、新建态、退出态。另外，还有一个挂起的概念。进程的挂起，一般是交换（SWAP）的需要，在大内存容量的今天，处于这种状态的进程很少。挂起的进程有可能处于阻塞状态，也有可能处于就绪状态。

上面提到程序的基本元素，实际上，所有处理器设计，都包含一个或者一组称为程序状态字（PSW）的寄存器，操作系统设计要面对这些寄存器进行编程。举个例子，PSW通过状态位，就可以控制程序是运行在内核模式还是用户模式。

进程切换需要依靠中断。中断前，需要保存进程控制块部分，包括程序计数器、其他处理器寄存器和栈信息。操作系统如在用户进程内运行，则发生中断、陷阱或者系统调用的时候，处理器处于内核模式，控制权转交给操作系统，需要保存模式上细文并切换模式，再切换到一个操作系统例程，但此时，仍然是在当前用户进程内继续执行，不需要切换进程，只是在同一个进程内切换模式。

在UNIX中，只有在进程准备从内核模式转换到用户模式的时候才能发生抢占，所以UNIX并不适用于实时处理。

比起进程来，我们通常将分派的单位称为线程或者轻量级进程（LWP），而将拥有资源所有权的单位称为进程（process）或任务（task）。

进程中的所有线程共享该进程的状态和资源，所有线程都驻留在同一块地址空间中，并可以访问相同的数据，所以切换开销很小。

Linux提供一种不区分进程和线程的解决方案，这种解决方案使用一种类似Solaris轻量级进程的方法，将用户级线程映射到内核级别的进程，所以它们是一回事。Linux甚至都没有为线程定义专门的数据结构。pthread库（POSIX thread），根本就不属于内核。

虽然属于同一个进程组的克隆进程共享同一内存空间，但不能共享同一个用户栈。所以clone()调用会为每个进程创建独立的栈空间。

基于这种特性，Linux的命名空间可以对这些数据结构进行隔离，形成轻量级虚拟化的基础。

并发是所有问题的基础，也是操作系统设计的基础。对于并发来说，支持并发进程的基本需求是加强互斥能力。有三种互斥方式：信号量、管程和消息传递。

互斥软件通常会在硬件级别实现基本的互斥。spin waiting，也就是自旋方式获取控制权的方式（CAS），实际上是一种协同程序（coroutine）。为了提高效率，CAS会在硬件级别实现，也就是XCHG指令。自旋锁很容易实现，但有一个缺点，即锁外面的线程会以忙等待的方式继续执行。这里会涉及到两个非常著名的互斥算法：Dekker和Peterson。

互斥最好的例子就是生产者和消费者问题，在语言层面比在操作系统层面更容易理解。除了互斥（mutual exclusion），竞争进程还面临死锁（deadlock）和饥饿（starvation）的问题。这些不仅在操作系统，在语言级别也是大问题。

信号量是用于在进程间传递信号的一个整数值。如果只有0和1两个值，则它就变成了二元信号量。另外，还有一个互斥量（mutex）的概念，也是0和1，但它与二元信号量的区别是，为互斥量加锁的进程和解锁的进程，必须是同一个进程---解铃还需系铃人。

然后再提到管程。管程是由一个或者多个进程、一个初始化序列和局部数据组成的软件模块。Java的wait、notify，或者Contidion的wait和signal等，都是这样的实现。

死锁产生的条件，包括：互斥、占有且等待、不可抢占、循环等待等。

与并发管理中的其他问题不同，死锁问题并没有有效的通用解决方案。这是因为死锁发生的原因，通常隐藏在复杂的程序逻辑中，检测起来非常困难。处理可重用资源死锁的一个策略是，给系统设计施加关于资源请求顺序的约束。

在资源固定，请求也可知的情况下，可使用资源分配拒绝策略，也就是传说中的银行家算法（banker algorithm）。通过Resource和Available向量、Claim和Allocation矩阵，来判断接下来的操作是否会造成死锁。

死锁方面的问题有点多，包括常考的哲学家就餐问题。其实，基于上面的信号量和管程，都能够实现。

内存管理是操作系统中最复杂的部分。它包含重定位、保护、共享、逻辑组织和物理组织等内容。

其中，内存保护需求必须有处理器（硬件）而非操作系统（软件）来满足，因为操作系统不能预测程序可能产生的所有内存访问。内存的分段有助于实现保护机制和共享机制。

进程内的所有内存都是基于逻辑地址，这些逻辑地址会在运行时动态的转换为物理地址。简单的映射方案会导致内存访问时间加倍。为克服这个问题，大多数虚拟内存方案都为页表项使用了一个特殊的高速缓存，通常称为转换监测缓冲区（TLB）。

虚拟地址转换为实际地址时，需要访问页表项，而页表项可能在TLB中，也可能在内存或者磁盘中，而被访问的字可能在高速缓存中、内存中或者磁盘中。所以，一次内存访问可能产生两次缺页中断：第一次读取所需要的页表部分，第二次读取进程页。

一个进程可以划分为许多块（段和页），这些块不需要连续的位于内存中。在使用分页技术时，每个进程在内存中浪费的空间，仅仅是进程最后一页的一小部分形成的碎片。没有任何外部碎片。

其中，进程执行的任何时候，都在内存的部分称为进程的常驻集（resident set）。处理器需要访问一个不在内存中的逻辑地址时，会产生一个中断，这表明出现了内存访问故障。操作系统会把被中断的进程置于阻塞状态。要继续执行这个进程，操作系统必须把包含引发故障的逻辑地址的进程块读入内存。

使用磁盘来模拟内存，叫做虚拟内存（virtual memory）。虚存支持更有效的系统并发度，并能解除用户与内存之间没有必要的紧密约束。但是，虚存会导致一种称为系统抖动（thrashing）的情况：处理器大部分时间都用于交换块，而非执行指令。

Linux使用伙伴系统做内存分配。它将根据内存请求的大小动态的把内存的某一块，一分为2，直到找到合适的大小。用完之后，还会判断相近的内容，再来一次合并。

早期的UNIX实现中，不提供虚存的原因是，系统运行的处理器不支持分页或者分段。若没有对地址转换和其他基本功能的硬件支持，则这些技术都无法实际使用。

内存不够时，要交换到磁盘，所以会涉及到置换策略，在数据库环境中问题尤其突出。所有策略的目标，都是移出最近不可能访问的页。

但是，LRU在内存管理级别可能不那么现实，因为它在内核级别比较难以实现。一种实现方式是给每一个页增加一个最后一次访问的时间戳，并在每次访问的时候更新这个时间戳。但即使有支持这种方案的硬件，开销仍然非常大。另一种方法是维护一个关于访问页的栈，但开销同样很大。

FIFO虽然傻，但它是一种实现起来最简单的页面置换策略。

在Linux中，有后台进程会周期性的扫描全局页池，而当它在内存的所有页间循环时，将扫描的每一页的age变量减1。内核进程kswapd在后台周期性的执行各个区域的内存回收，它扫描那些与系统页框对应的页表项。

Linux的内核也会产生非常非常小的内存小块，为了适应它们，Linu在分配页的时候使用了SLAB分配方案。

处理器调度的目的，以满足系统目标（如响应时间、吞吐率、处理器效率）的方式，把进程分配到一个或者多个处理器上执行。从用户角度看，响应时间是系统中最重要的一个特性；从系统的角度来看，吞吐量或者处理器利用率是最重要的。

进程调度根据生命周期，分为长程调度、中程调度、短程调度。长程调度指的是进程的新建和销毁，中程调度指的是进行的挂起，而我们常说的调度，指的是短程调度。

调度算法要关注系统交互的响应时间，还有吞吐量，这和服务接口的指标是一致的。常用的调度算法是时间片（time slicing），因为每个进程在被抢占之前都会给定一片时间。注意，当一个时间片比运行时间最长的进程还要长的时候，轮转法就会退化成FCFS。

CPU调度的算法大多数是通过实验得来的，在多核环境下，简单的FCFS效率并不低，已经足够了。在多核环境下，操作系统必须保证多个处理器不会选择同一个进程，进程也不会从队列中丢失，因此必须采用某些技术来解决和同步对资源的竞争需求。

研究证明，多处理器系统中的时间分配问题，更加类似于单处理器中的存储器分配问题，而非单处理器中的调度问题。在这些理论基础上，一个类似于虚存中的工作集的术语--活动工作集（activity working set）被提了出来。

Linux在2.6采用了一个全新的优先级调度程序，称为O(1)调度。这个程序的设计原则是，不管系统的负载和处理器的数量如何变化，选择合适的任务并执行的时刻，都是恒定的。但事实证明，它太笨重，算法太复杂。

从2.6.23开始，Linux开发了完全公平调度器（CFS），CFS为每个任务维护一个虚拟的运行时间。一个任务的虚拟运行时间越短（即任务被允许访问处理器的时间越短），代表它对处理器的需求越强。

这个算法，到现在仍在运行着。

作者简介：小姐姐味道 (xjjdog)，一个不允许程序员走弯路的公众号。聚焦基础架构和Linux。十年架构，日百亿流量，与你探讨高并发世界，给你不一样的味道。