1 冯诺伊曼体系

1.1 冯诺伊曼体系简介

现代计算机之父冯诺伊曼最先提出程序存储的思想，并成功将其运用在计算机的设计之中，该思想约定了用二进制进行计算和存储，还定义计算机基本结构为 5 个部分，分别是中央处理器（CPU）、内存、输入设备、输出设备、总线。

1. 存储器：代码跟数据在RAM跟ROM中是线性存储， 数据存储的单位是一个二进制位。最小的存储单位是字节。

2. 总线：总线是用于 CPU 和内存以及其他设备之间的通信，总线主要有三种：

1. 地址总线：用于指定 CPU 将要操作的内存地址。

2. 数据总线：用于读写内存的数据。

3. 控制总线：用于发送和接收信号，比如中断、设备复位等信号，CPU 收到信号后响应，这时也需要控制总线。

1. 输入/输出设备：输入设备向计算机输入数据，计算机经过计算后，把数据输出给输出设备。比如键盘按键时需要和 CPU 进行交互，这时就需要用到控制总线。

2. CPU：中央处理器，类比人脑，作为计算机系统的运算和控制核心，是信息处理、程序运行的最终执行单元。CPU用寄存器存储计算时所需数据，寄存器一般有三种：

1. 通用寄存器：用来存放需要进行运算的数据，比如需进行加法运算的两个数据。

2. 程序计数器：用来存储 CPU 要执行下一条指令所在的内存地址。

3. 指令寄存器：用来存放程序计数器指向的指令本身。

在冯诺伊曼体系下电脑指令执行的过程：

1. CPU读取程序计数器获得指令内存地址，CPU控制单元操作地址总线从内存地址拿到数据，数据通过数据总线到达CPU被存入指令寄存器。

2. CPU分析指令寄存器中的指令，如果是计算类型的指令交给逻辑运算单元，如果是存储类型的指令交给控制单元执行。

3. CPU 执行完指令后程序计数器的值通过自增指向下个指令，比如32位CPU会自增4。

4. 自增后开始顺序执行下一条指令，不断循环执行直到程序结束。

CPU位宽：32位CPU一次可操作计算4个字节，64位CPU一次可操作计算8个字节，这个是硬件级别的。平常我们说的32位或64位操作系统指的是软件级别的，指的是程序中指令多少位。
线路位宽：CPU操作指令数据通过高低电压变化进行数据传输，传输时候可以串行传输，也可以并行传输，多少个并行等于多少个位宽。

1.2 CPU 简介

Central Processing Unit 中央处理器，作为计算机系统的运算和控制核心，是信息处理、程序运行的最终执行单元。

1. CPU核心：一般一个CPU会有多个CPU核心，平常说的多核是指在一枚处理器中集成两个或多个完整的计算引擎。核跟CPU的关系是：核属于CPU的一部分。

2. 寄存器：最靠近CPU对存储单元，32位CPU寄存器可存储4字节，64位寄存器可存储8字节。寄存器访问速度一般是半个CPU时钟周期，属于纳秒级别，

3. L1缓存：每个CPU核心都有，用来缓存数据跟指令，访问空间大小一般在32～256KB，访问速度一般是2～4个CPU时钟周期。

   cat /sys/devices/system/cpu/cpu0/cache/index0/size # L1 数据缓存 cat /sys/devices/system/cpu/cpu0/cache/index1/size # L1 指令缓存 

4. L2缓存：每个CPU核心都有，访问空间大小在128KB～2MB，访问速度一般是10～20个CPU时钟周期。

   cat /sys/devices/system/cpu/cpu0/cache/index2/size # L2 缓存容量大小 

5. L3缓存：多个CPU核心共用，访问空间大小在2MB～64MB，访问速度一般是20～60个CPU时钟周期。

   cat /sys/devices/system/cpu/cpu0/cache/index3/size # L3 缓存容量大小 

6. 内存：多个CPU共用，现在一般是4G～512G，访问速度一般是200～300个CPU时钟周期。

7. 固体硬盘SSD：现在台式机主流都会配备，上述的寄存器、缓存、内存都是断电数据立马丢失的，而SSD里不会丢失，大小一般是128G～1T，比内存慢10～1000倍。

8. 机械盘HDD：很早以前流行的硬盘了，容量可在512G～8T不等，访问速度比内存慢10W倍不等。

9. 访问数据顺序：CPU在拿数据处理的时候几乎也是按照上面说得流程来操纵的，只有上面一层找不到才会找下一层。

10. Cache Line:  CPU读取数据时会按照 Cache Line 方式把数据加载到缓存中，每个Cacheline = 64KB，因为L1、L2是每个核独有到可能会触发伪共享，就是 所以可能会将数据划分到不同到CacheLine中来避免伪共享，比如在JDK8 新增加的 LongAdder 就涉及到此知识点。

1. 伪共享：缓存系统中是以缓存行（cache line）为单位存储的，当多线程修改互相独立的变量时，如果这些变量共享同一个缓存行，就会无意中影响彼此的性能，这就是伪共享。

1. JMM: 数据经过种种分层会导致访问速度在不断提升，同时也带来了各种问题，多个CPU同时操作相同数据可能会造成各种BU个，需要加锁，这里在JUC并发已详细探讨过。

1.3 CPU 访问方式

1. Cache Line Index ：CPU缓存读取数据时不是按照字节来读取的，而是按照CacheLine方式存储跟读取数据的。

2. Valid Bit : 有效位标志符，值为0时表示无论 CPU Line 中是否有数据，CPU 都会直接访问内存，重新加载数据。

3. Tag：组标记，用来标记内存中不同BLock映射到相同CacheLine，用Tag来区分不同的内存Block。

4. Data：真实到内存数据信息。

CPU真实访问内存数据时只需要指定三个部分即可。

1. Cache Line Index ：要访问到Cache Line 位置。

2. Tag：表示用那个数据块。

3. Offset：CPU从CPU Cache 读取数据时不是直接读取Cache Line整个数据块，而是读取CPU所需的数据片段，称为Word。如何找到Word就需要个偏移量Offset。

1.4 CPU 访问速度

1. 指令缓存：尽可能的提供有规律的条件分支语句，让 CPU 的分支预测器发挥作用，进一步提高执行的效率，因为CPU是自带分支预测器，自动提前将可能需要的指令放到指令缓存区。

2. 线程绑定到CPU：一个任务A在前一个时间片用CPU核心1 运行，后一个时间片用CPU核心2 运行，这样缓存L1、L2就浪费了。因此操作系统提供了将进程或者线程绑定到某一颗 CPU 上运行的能力。如 Linux 上提供了 sched_setaffinity 方法实现这一功能，其他操作系统也有类似功能的 API 可用。当多线程同时执行密集计算，且 CPU 缓存命中率很高时，如果将每个线程分别绑定在不同的 CPU 核心上，性能便会获得非常可观的提升。

1.5  操作系统

2 内存管理

你的电脑是32位操作系统，那可支持的最大内存就是4G，你有没有好奇为什么可以同时运行2个以上的2G内存的程序。应用程序不是直接使用的物理地址，操作系统为每个运行的进程分配了一套虚拟地址，每个进程都有自己的虚拟内存地址，进程是无法直接进行物理内存地址的访问的。至于虚拟地址跟物理地址的映射，进程是感知不到的！操作系统自身会提供一套机制将不同进程的虚拟地址和不同内存的物理地址进行映射。

2.1  MMU

Memory Management Unit 内存管理单元是一种负责处理CPU内存访问请求的计算机硬件。它的功能包括虚拟地址到物理地址的转换、内存保护、中央处理器高速缓存的控制。现代 CPU 基本上都选择了使用 MMU。

当进程持有虚拟内存地址的时候，CPU执行该进程时会操作虚拟内存，而MMU会自动的将虚拟内存的操作映射到物理内存上。

2.2  内存管理方式

操作系统主要采用内存分段和内存分页来管理虚拟地址与物理地址之间的关系，其中分段是很早前的方法了，现在大部分用的是分页，不过分页也不是完全的分页，是在分段的基础上再分页。

2.2.1 内存分段

我们以上图的JVM内存模型举例，程序员会认为我们的代码是由代码段、数据段、栈段、堆段组成。不同的段是有不同的属性的，用户并不关心这些元素所在内存的位置，而分段就是支持这种用户视图的内存管理方案。逻辑地址空间是由一组段构成。每个段都有名称和长度。地址指定了段名称和段内偏移。因此用户段编号和段偏移来指定不同属性的地址。而虚拟内存地址跟物理内存地址中间是通过段表进行映射的，口说无凭，看图吧。

如上虚拟地址有 5 个段，各段按如图所示来存储。每个段都在段表中有一个条目，它包括段在物理内存内的开始的基地址和该段的界限长度。例如段 2 为 400 字节长，开始于位置 4300。因此对段 2 字节 53 的引用映射成位置 4300 + 53 = 4353。对段 3 字节 852 的引用映射成位置 3200 + 852 = 4052。

分段映射很简单，但是会导致内存碎片跟内存交互效率低。这里先普及下在内存管理中主要有内部内存碎片跟外部内存碎片。

1. 内部碎片：已经被分配出去的的内存空间不经常使用，并且分配出去的内存空间大于请求所需的内存空间。

2. 外部碎片：指可用空间还没有分配出去，但是可用空间由于大小太小而无法分配给申请空间的新进程的内存空间空闲块。

以上图为例，现在系统空闲是1400 +  800 + 600 = 2800。那如果有个程序想要连续的使用2000，内存分段模式下提供不了啊！上述三个是外部内存碎片。当然可以使用系统的Swap空间，先把段0写入到磁盘，然后再重新给段0分配空间。这样可以实现最终可用，可是但凡涉及到磁盘读写就会导致内存交互效率低。

2.2.2 内存分页

内存分页，整个虚拟内存和物理内存切成一段段固定尺寸的大小。每个固定大小的尺寸称之为页Page，在 Linux 系统中Page = 4KB。然后虚拟内存跟物理内存之间通过页表来实现映射。

采用内存分页时内存的释放跟使用都是以页为单位的，也就不会产生内存碎片了。当空间还不够时根据操作系统调度算法，可能将最少用的内存页面 swap-out换出到磁盘，用时候再swap-in换入，尽可能的减少磁盘刷写量，提高内存交互效率。

分页模式下虚拟地址主要有页号跟页内偏移量两部分组成。通过页号查询页表找到物理内存地址，然后再配合页内偏移量就找到了真正的物理内存地址。

32位操作系统环境下进程可操作的虚拟地址是4GB，假设一个虚拟页大小为4KB，那需要4GB/4KB =2^20个页信息。一行页表记录为4字节，2^20等价于4MB页表存储信息。这只是一个进程需要的，如果10个、100个、1000个呢？仅仅是页表存储都占据超大内存了。

为了解决这个问题就需要用到多级页表，核心思想就是局部性分配。在32位的操作系统中将将4G空间分为 1024 行页目录项目(4KB)，每个页目录项又对应1024行页表项。如下图所示：

分页后一级页就等价于4G虚拟地址空间，并且如果一级页表中那些地址没有就不需要再创建二级页表了！核心思想就是按需创建，当系统给每个进程分配4G空间，进程不可能占据全部内存的，如果一级目录页只有10%用到了，此时页表空间 = 一级页表4KB + 0.1 * 4MB  。这比单独的每个进程占据4M好用多了！

多层分页的弊端就是访问时间的增加。

1. 使用页表时读取内存中一页内容需要2次访问内存，访问页表项 + 并读取的一页数据。

2. 使用二级页表的话需要三次访问，访问页目录项 + 访问页表项 + 访问并读取的一页数据。访存次数的增加也就意味着访问数据所花费的总时间增加。

而对于64位系统，二级分页就无法满足了，Linux 从2.6.11开始采用四级分页模型。

1. Page Global Directory 全局页目录项

2. Page Upper Directory 上层页目录项

3. Page Middle Directory 中间页目录项

4. Page Table Entry 页表项

5. Offset 偏移量。

2.2.2 TLB

Translation Lookaside Buffer 可翻译为地址转换后援缓冲器，简称为快表，属于CPU内部的一个模块，TLB是MMU的一部分，实质是cache，它所缓存的是最近使用的数据的页表项（虚拟地址到物理地址的映射）。他的出现是为了加快访问数据（内存）的速度，减少重复的页表查找。当然它不是必须要有的，但有它，速度就更快。

1. 全部刷新：很简单，但花销大，很多不必刷新的数据也进行刷新，增加了无畏的花销。

2. 部分刷新：根据标志位，刷新需要刷新的数据，保留不需要刷新的数据。

2.2.3 段页式管理

内存分段跟内存分页不是对立的，这俩可以组合起来在同一个系统中使用的，那么组合起来后通常称为段页式内存管理。段页式内存管理实现的方式：

1. 先对数据不同划分出不同的段，也就是前面说的分段机制。

2. 然后再把每一个段进行分页操作，也就是前面说的分页机制。

3. 此时 地址结构 = 段号 + 段内页号 + 页内位移。

每一个进程有一张段表，每个段又建立一张页表，段表中的地址是页表的起始地址，而页表中的地址则为某页的物理页号。

1. 逻辑地址：指的是没被段式内存管理映射的地址。

2. 线性地址：通过段式内存管理映射且页式内存管理转换前的地址，俗称虚拟地址。

目前 Intel X86 CPU 采用的是内存分段 +  内存分页的管理方式，其中分页的意思是在由段式内存管理所映射而成的的地址上再加上一层地址映射。

2.2.4 Linux 内存管理

先说结论：Linux系统基于X86 CPU 而做的操作系统，所以也是用的段页式内存管理方式。

1. 内核空间：操作系统内核访问的区域，独立于普通的应用程序，是受保护的内存空间。内核态下CPU可执行任何指令，可自由访问任何有效地址。

2. 用户空间：普通应用程序可访问的内存区域。被执行代码会受到CPU众多限制，进程只能访问映射其地址空间的页表项中规定的在用户态下可访问页面的虚拟地址。

那为啥要搞俩空间呢?现在嵌入式环境跟以前的WIN98系统是没有区分俩空间的，须知俩空间是CPU分的，而操作系统是在上面运行的，单一用户、单一任务服务的操作系统，是没有分所谓用户态和内核态的必要。用户态和内核态是因为有多用户，多任务的需求，然后在CPU硬件厂商配合之后，产生的一个操作系统解决多用户多任务需求的方案。方案就是限制，通过硬件手段（也只能硬件手段才能做到），限制某些代码，使其无法控制整个物理硬件，进而使各个不同用户，不同任务的代码，无权修改整个物理硬件，再进而保护操作系统的核心底层代码和其他用户的数据不被无意或者有意地破坏和盗取。

用户态想要使用计算机设备或IO需通过系统调用完成sys call，系统调用就是让内核来做这些操作。而系统调用是影响整个当前进程上下文的，ＣＰＵ提供了个软中断来是实现保护线程，获取系统调用号跟参数，交给内核对应系统调用函数执行。

3 进程管理

3.1 进程基础知识

进程是程序的一次执行，是一个程序及其数据在机器上顺序执行时所发生的活动，是具有独立功能的程序在一个数据集合上的一次运行过程，是系统进行资源分配和调度的一个基本单位。进程的调度状态如下：

1. 阻塞一般是当系统执行IO操作时，此时进程进入阻塞状态，等待某个事件的返回。

2. 挂起是指进程没有占有物理内存，被写到磁盘上了。这时进程状态是挂起状态。

1. 阻塞挂起：进程被写入硬盘并等待某个事件的出现。

2. 就绪挂起：进程被写入硬盘，进入内存可直接进入就绪状态。

3.2 PCB

为了描述跟控制进程的运行，系统为每个进程定义了一个数据结构——进程控制块 Process Control Block，它是进程实体的一部分，是操作系统中最重要的记录型数据结构。

PCB 的作用是使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程 :

1. 作为独立运行基本单位的标志

2. 实现间断性的运行方式

3. 提供进程管理所需要的信息

4. 提供进程调度所需要的信息

5. 实现与其他进程的同步与通信

3.2.1 PCB 信息

PCB为实现上述功能，内部包含众多信息：

1. 进程标识符：用于唯一地标识一个进程，一个进程通常有两种标识符：

1. 内部进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符，设置内部标识符主要是为了方便系统使用。

2. 外部进程标识符：它由创建者提供，可设置用户标识，以指示拥有该进程的用户。往往是由用户进程在访问该进程时使用。一般为了描述进程的家族关系，还应设置父进程标识及子进程标识。

1. 处理机状态：由各种寄存器组成。包含许多信息都放在寄存器中，方便程序restart。

1. 通用寄存器、指令计数器、程序状态字PSW、用户栈指针等信息。

1. 进程调度信息

1. 进程状态：指明进程的当前状态，作为进程调度和对换时的依据。

2. 进程优先级：用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机

3. 进程调度所需的其它信息：与所采用的进程调度算法有关，如进程已等待CPU的时间总和、进程已执行的时间总和等。

4. 事件：指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。

1. 资源清单

有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。

3.2.2 PCB 组织方式

操作系统中有太多 PCB，如何管理是个问题，一般有如下方式。

1. 线性方式：

1. 将系统所有PCB都组织在一张线性表中，将该表首地址存在内存的一个专用区域

2. 实现简单，开销小，但是每次都需要扫描整张表，适合进程数目不多的系统

1. 索引方式：

1. 将同一状态的进程组织在一个索引表中，索引表项指向相应的 PCB，不同状态对应不同的索引表。

1. 链接方式：

1. 把同一状态的PCB链接成一个队列，形成就绪队列、阻塞队列、空白队列等。对其中的就绪队列常按进程优先级的高低排列，优先级高排在队前。

2. 因为进程创建、销毁、调度频繁，所以一般采用此模式。

3.3 进程控制

进程控制是进程管理最基本的功能，主要包括创建新进程，终止已完成的进程，将发生异常的进程置于阻塞状态，将进程唤醒等。

3.3.1 进程创建

父进程可创建子进程，父进程终止后子进程也会被终止。子进程可继承父进程所有资源，子进程终止需将自己所继承的资源归还父进程。接下来看下创建的大致流程。

1. 为新进程分配唯一进件标识号，然后创建一个空白PCB，需注意PCB数量是有限的，所以可能会创建失败。

2. 尝试为新进程分配所需资源，如果资源不足进程会进入等待状态。

3. 初始化PCB，有如下几个操作。

1. 标识信息：将系统分配的标识符和父进程标识符填入新PCB

2. 处理机状态信息：使程序计数器指向程序入口地址，使栈指针指向栈顶

3. 处理机控制信息：将进程设为就绪/静止状态，通常设为最低优先级

1. 如果进程调度队列能接纳新进程，就将进程插入到就绪队列，等待被调度运行。

3.3.2 进程终止

进程终止情况一般分为正常结束、异常结束、外界干预三种。

1. 正常结束

2. 异常结束

1. 越界错：访问的存储区越出该进程的区域

2. 保护错：试图访问不允许访问的资源，或以不适当的方式访问（写只读）

3. 非法指令：试图执行不存在的指令（可能是程序错误地转移到数据区，数据当成了指令）

4. 特权指令出错：用户进程试图执行一条只允许OS执行的指令

5. 运行超时：执行时间超过指定的最大值

6. 等待超时：进程等待某件事超过指定的最大值

7. 算数运算错：试图执行被禁止的运算（被0除）

8. I/O故障

1. 外界干预

1. 操作员或OS干预（死锁）

2. 父进程请求，子进程完成父进程指定的任务时

3. 父进程终止，所有子进程都应该结束

终止过程：

1. 根据被终止进程的标识符，从PCB集合中检索出该PCB，读取进程状态

2. 若处于执行状态则立即终止执行，将CPU资源分配给其他进程。

3. 若进程有子孙进程则将其所有子孙进程终止。

4. 全部资源还给父进程或操作系统。

5. 该进程的PCB从所在队列/链表中移出。

3.3.3 进程阻塞

意思是该进程执行半路被阻塞，必须由某个事件进程唤醒该进程。常见的就是IO读取操作。常见阻塞时机/事件如下：

1. 请求共享资源失败，系统无足够资源分配

2. 等待某种操作完成

3. 新数据尚未到达（相互合作的进程）

4. 等待新任务

阻塞流程：

1. 找到要被阻塞进程标识号对应的 PCB。

2. 将该进程由运行状态转换为阻塞状态。

3. 将该 进程PCB 插入的阻塞队列中去。

3.3.4 进程唤醒

唤醒 原语 wake up，一般和阻塞成对使用。唤醒过程如下：

1. 从阻塞队列找到所需PCB。

2. PCB从阻塞队列溢出，然后变为就绪状态。

3. 从阻塞队列溢出该PCB然后插入到就绪状态队列等待被分配CPU资源。

3.4 进程调度

进程数一般会大于CPU个数，进程状态切换主要由调度程序进行调度。一般情况下CPU调度时主要分为抢占式调度跟非抢占式调度。

1. 非抢占式：让进程运行直到结束或阻塞的调度方式， 容易实现，适合专用系统。

2. 抢占式：每个进程获得时间片才可以被CPU调度运行， 可防止单一进程长时间独占CPU 系统开销大。

3.4.1 进程调度原则

1. CPU 利用率

1. CPU利用率 = 忙碌时间 / 总时间。

2. 调度程序应该尽量让 CPU 始终处于忙碌的状态，这可提高 CPU 的利用率。比如当发生IO读取时候，不要傻傻等待，去执行下别的进程。

1. 系统吞吐量

1. 系统吞吐量 = 总共完成多少个作业 / 总共花费时间。

2. 长作业的进程会占用较长的 CPU 资源导致降低吞吐量，相反短作业的进程会提升系统吞吐量。

1. 周转时间

1. 周转时间 = 作业完成时间 - 作业提交时间。

2. 平均周转时间 = 各作业周转时间和 / 作业数

3. 带权周转时间 = 作业周转时间 / 作业实际运行时间

4. 平均带权周转时间 = 各作业带权周转时间之和 / 作业数

5. 尽可能使周转时间降低。

1. 等待时间

1. 指的是进程在等待队列中等待的时间，一般也需要尽可能短。

2. 响应时间
   响应时间 = 系统第一次响应时间 - 用户提交时间，在交互式系统中响应时间是衡量调度算法好坏的主要标准。

3.4.2 调度算法

FCFS 算法

1. First Come First Severd 先来先服务算法，遵循先来后端原则，每次从就绪队列拿等待时间最久的，运行完毕后再拿下一个。

2. 该模式对长作业有利，适用 CPU 繁忙型作业的系统，不适用 I/O 型作业，因为会导致进程CPU利用率很低。

SJF 算法

1. Shortest Job First 最短作业优先算法，该算法会优先选择运行所需时间最短的进程执行，可提高吞吐量。

2. 跟FCFS正好相反，对长作业很不利。

SRTN 算法

1. Shortest Remaining Time Next 最短剩余时间优先算法，可以认为是SJF的抢占式版本，当一个新就绪的进程比当前运行进程具有更短完成时间时，系统抢占当前进程，选择新就绪的进程执行。

2. 有最短的平均周转时间，但不公平，源源不断的短任务到来，可能使长的任务长时间得不到运行。

HRRN 算法

1. Highest Response Ratio Next 最高响应比优先算法，为了平衡前面俩而生，按照响应优先权从高到低依次执行。属于前面俩的折中权衡。

2. 优先权 = (等待时间 + 要求服务时间) / 要求服务时间

RR 算法

1. Round Robin 时间片轮转算法，操作系统设定了个时间片Quantum，时间片导致每个进程只有在该时间片内才可以运行，这种方式导致每个进程都会均匀的获得执行权。

2. 时间片一般20ms~50ms，如果太小会导致系统频繁进行上下文切换，太大又可能引起对短的交互请求的响应变差。

HPF 算法

1. Highest Priority First 最高优先级调度算法，从就绪队列中选择最高优先级的进程先执行。

2. 优先级的设置有初始化固定死的那种，也有在代码运转过程中根据等待时间或性能动态调整 这两种思路。

3. 缺点是可能导致低优先级的一直无法被执行。

MFQ 算法

1. Multilevel Feedback Queue 多级反馈队列调度算法 ，可以认为是 RR 算法 跟 HPF 算法 的综合体。

2. 系统会同时存在多个就绪队列，每个队列优先级从高到低排列，同时优先级越高获得是时间片越短。

3. 新进程会先加入到最高优先级队列，如果新进程优先级高于当前在执行的进程，会停止当前进程转而去执行新进程。新进程如果在时间片内没执行完毕需下移到次优先级队列。

   多级反馈队列调度算法

3.5 线程

3.5.1 线程定义

早期操作系统是没有线程概念的，线程是后来加进来的。为啥会有线程呢？那是因为以前在多进程阶段，经常会涉及到进程之间如何通讯，如何共享数据的问题。并且进程关联到PCB的生命周期，管理起来开销较大。为了解决这个问题引入了线程。

线程是进程当中的一个执行流程。同一个进程内的多个线程之间可以共享进程的代码段、数据段、打开的文件等资源。同时每个线程又都有一套独立的寄存器和栈来确保线程的控制流是独立的。

进程有个PCB来管理，同理操作系统通过Thread Control Block线程控制块来实现线程的管控。

3.5.2 线程优缺点

优点

1. 一个进程中可以同时存在1~N个线程，这些线程可以并发的执行。

2. 各个线程之间可以共享地址空间和文件等资源。

缺点

1. 当进程中的一个线程奔溃时，会导致其所属进程的所有线程奔溃。

2. 多线程编程，让人头大的东西。

3. 线程执行开销小，但不利于资源的隔离管理和保护，而进程正相反。

3.5.3 进程跟线程关联

进程：

1. 是系统进行资源分配和调度的一个独立单位.

2. 是程序的一次执行，每个进程都有自己的地址空间、内存、数据栈及其他辅助记录运行轨迹的数据

线程：

1. 是进程的一个实体，是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位

2. 所有的线程运行在同一个进程中，共享相同的运行资源和环境

3. 线程一般是并发执行的，使得实现了多任务的并行和数据共享。

进程线程区别：

1. 一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。

2. 线程的划分尺度小于进程(资源比进程少)，使得多线程程序的并发性高。

3. 进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。

4. 资源分配给进程，同一进程的所有线程共享该进程的所有资源。

5. CPU分配资源给进程，但真正在CPU上运行的是线程。

6. 线程不能够独立执行，必须依存在进程中。

线程快在哪儿？

1. 线程创建的时有些资源不需要自己管理，直接从进程拿即可，线程管理寄存器跟栈的生命周期即可。

2. 同进程内多线程共享数据，所以进程数据传输可以用zero copy技术，不需要经过内核了。

3. 进程使用一个虚拟内存跟页表，然后多线程共用这些虚拟内存，如果同进程内两个线程进行上下文切换比进程提速很多。

3.5.4 线程实现

在前面的内存管理中说到了内核态跟用户态。相对应的线程的创建也分为用户态线程跟内核态线程。

3.5.4.1 用户态线程

在用户空间实现的线程，由用户态的线程库来完成线程的管理。操作系统按进程维度进行调度，当线程在用户态创建时应用程序在用户空间内要实现线程的创建、维护和调度。操作系统对线程的存在一无所知！操作系统只能看到进程看不到线程。所有的线程都是在用户空间实现。在操作系统看来，每一个进程只有一个线程。

好处：

1. 及时操作系统不支持线程模式也可以通过用户层库函数来支持线程模式，TCB 由用户级线程库函数来维护。

2. 使用库函数模式实现线程可以避免用户态到内核态的切换。

坏处：

1. CPU不知道线程存在，CPU的时间片切换是以进程为维度的，某个线程因为IO等操作导致线程阻塞，操作系统会阻塞整个进程，即使这个进程中其它线程还在工作。

2. 用户态线程没法打断正在运行中的线程，除非线程主动交出CPU使用权。

3.5.4.2 内核态线程

在内核中实现的线程，是由内核管理的线程，线程对应的 TCB 在操作系统里，这样线程的创建、终止和管理都是由操作系统负责。内线程模式下一个用户线程对应一个内核线程。

优点：

1. 一个进程中某个线程阻塞不会影响其他内核线程运行。

2. 用户态模式一个时间片分给多个线程，内核态模式直接分配给线程的时间片增加。

缺点：

1. 内核级线程调度开销较大。调度内核线程的代价可能和调度进程差不多昂贵，代价要比用户级线程大很多。一个线程默认栈=1M，线程多了会导致内存消耗很大。

2. 线程表是存放在操作系统固定的表格空间或者堆栈空间里，所以内核级线程的数量是有限的。

3.4.4.3 轻量级进程

最初的进程定义都包含程序、资源及其执行三部分，其中程序通常指代码，资源在操作系统层面上通常包括内存资源、IO资源、信号处理等部分，而程序的执行通常理解为执行上下文，包括对CPU的占用，后来发展为线程。在线程概念出现以前，为了减小进程切换的开销，操作系统设计者逐渐修正进程的概念，逐渐允许将进程所占有的资源从其主体剥离出来，允许某些进程共享一部分资源，例如文件、信号，数据内存，甚至代码，这就发展出轻量进程的概念。

Light-weight process 轻量级进程是内核支持的用户线程，它是基于内核线程的高级抽象，系统只有先支持内核线程才能有 LWP。一个进程可有1~N个LWP，每个 LWP 是跟内核线程一对一映射的，也就是 LWP 都是由一个内核线程支持。

轻量级进程本质还是进程，只是跟普通进程相比LWP跟其他进程共享大部分逻辑地址空间跟系统资源，LWP轻量体现在它只有一个最小的执行上下文和调度程序所需的统计信息。他是进程的执行部分，只带有执行相关的信息。

Linux特性：

1. Linux中没有真正的线程，因为Linux并没有为线程准备特定的数据结构。在内核看来只有进程而没有线程，在调度时也是当做进程来调度。Linux所谓的线程其实是与其他进程共享资源的进程。但windows中确实有线程。

2. Linux中没有的线程，线程是由进程来模拟实现的。

3. 所以在Linux中在CPU角度看，进程被称作轻量级进程LWP。

3.5.5 协程

3.5.5.1 协程定义

大多数web服务跟互联网服务本质上大部分都是 IO 密集型服务，IO 密集型服务的瓶颈不在CPU处理速度，而在于尽可能快速的完成高并发、多连接下的数据读写。以前有两种解决方案：

1. 多进程：存在频繁调度切换问题，同时还会存在每个进程资源不共享的问题，需要额外引入进程间通信机制来解决。

2. 多线程：高并发场景的大量 IO 等待会导致多线程被频繁挂起和切换，非常消耗系统资源，同时多线程访问共享资源存在竞争问题。

此时协程出现了，协程 Coroutines 是一种比线程更加轻量级的微线程。类比一个进程可以拥有多个线程，一个线程也可以拥有多个协程。可以简单的把协程理解成子程序调用，每个子程序都可以在一个单独的协程内执行。

3.5.5.2 协程注意事项

协程运行在线程之上，并且协程调用了一个阻塞IO操作，此时操作系统并不知道协程的存在，它只知道线程，因此在协程调用阻塞IO操作时，操作系统会让线程进入阻塞状态，当前的协程和其它绑定在该线程之上的协程都会陷入阻塞而得不到调度。

因此在协程中不能调用导致线程阻塞的操作，比如打印、读取文件、Socket接口等。协程只有和异步IO结合起来才能发挥最大的威力。并且协程只有在IO密集型的任务中才会发挥作用。

3.6 进程通信

进程的用户地址空间是相互独立的，不可以互相访问，但内核空间是进程都共享的，所以进程之间要通信必须通过内核。进程间通信主要通过管道、消息队列、共享内存、信号量、信号、Socket编程。

3.6.1 管道

管道主要分为匿名管道跟命名管道两种，可以实现数据的单向流动性。使用起来很简单，但是管道这种通信方式效率低，不适合进程间频繁地交换数据。

匿名管道：

1. 日常Linux系统中的|就是匿名管道。指令的前一个输入是后一个指令的输出。

命名管道：

1. 一般通过mkfifo SoWhatPipe创建管道。通过echo "sw" > SoWhatPipe跟cat < SoWhatPipe实现输入跟输出。

匿名管道的实现依赖int pipe(int fd[2])函数，其中fd[0]是读取断描述符，fd[1]是管道写入端描述符。它的本质就是在内核中创建个属于内存的缓存，从一端输入无格式数据一端输出无格式数据，需注意管道传输大小是有限的。

1. 父进程关闭读取的 fd[0]，只保留写入的 fd[1]。

2. 子进程关闭写入的 fd[1]，只保留读取的 fd[0]。

3.6.2 消息队列

3.6.3 共享内存

3.6.4 信号量

既然共享内存容易造成数据紊乱，那为了简单的实现共享数据在任意时刻只能被一个进程访问，此时需要信号量。

信号量其实是一个整型的计数器，主要用于实现进程间的互斥与同步，而不是用于缓存进程间通信的数据。

信号量表示资源的数量，核心点在于原子性的控制一个数据的值，控制信号量的方式有PV两种原子操作：

1. P 操作会把信号量减去 -1，相减后如果信号量 < 0，则表明资源已被占用，进程需阻塞等待。相减后如果信号量 >= 0，则表明还有资源可使用，进程可正常继续执行。

2. V 操作会把信号量加上 1，相加后如果信号量 <= 0，则表明当前有阻塞中的进程，于是会将该进程唤醒运行。相加后如果信号量 > 0，则表明当前没有阻塞中的进程。

3.6.5 信号

对于异常状态下进程工作模式需要用到信号工作方式来通知进程。比如Linux系统为了响应各种事件提供了很多异常信号kill -l，信号是进程间通信机制中唯一的异步通信机制，可以在任何时候发送信号给某一进程。比如：

1. kill -9 1412 ，表示给 PID 为 1412 的进程发送 SIGKILL 信号，用来立即结束该进程。

2. 键盘 Ctrl+C 产生 SIGINT 信号，表示终止该进程。

3. 键盘 Ctrl+Z 产生 SIGTSTP 信号，表示停止该进程，但还未结束。

有信号发生时，进程一般有三种方式响应信号：

1. 执行默认操作：Linux操作系统为众多信号配备了专门的处理操作。

2. 捕捉信号：给捕捉到的信号配备专门的信号处理函数。

3. 忽略信号：专门用来忽略某些信号，但 SIGKILL 和 SEGSTOP是无法被忽略的，为了能在任何时候结束或停止某个进程而存在。

3.6.6 Socket编程

前面提到的管道、消息队列、共享内存、信号量和信号都是在同一台主机上进行进程间通信，那要想跨网络与不同主机上的进程之间通信，就需要 Socket 通信。

int socket(int domain, int type, int protocal) 

[sowhat@localhost ~]$ ln [选项] 源文件 目标文件
选项：
-s：建立软链接文件。如果不加 "-s" 选项，则建立硬链接文件；
-f：强制。如果目标文件已经存在，则删除目标文件后再建立链接文件；

buf = mmap(file, len);
write(sockfd, buf, len);

ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);
out_fd : 目的文件描述符
in_fd:源文件描述符
offset:源文件内偏移量
count:打算复制数据长度 ssize_t:实际上复制数据的长度

$ ethtool -k eth0 | grep scatter-gather
scatter-gather: on