操作系统学习小结

cpu

计算机基本结构

运算器、控制器、存储器、输入设备、输出设备，这 5 个部分也被称为冯诺依曼模型。

执行过程

第一步,CPU读取「程序计数器」的值,这个值是指令的内存地址,然后CPU的「控制单元」操作
「地址总线」指定需要访问的内存地址,接着通知内存设备准备数据居,数据准备好后通过「数据总线」将指令数据传给CPU,CPU收到内存传来的数据后,将这个指旨令数据存入到「指令寄存器」

第二步,「程序计数器」的值自增,表示指向下一条指令。这个自增的大小,由CPU的位宽决定,比
如32位的CPU,指令是4个字节,需要4个内存地址存放,因此「程序计数器」的值会自增4;

第三步,CPU分析「指令寄存器」中的指令,确定指令的类型和参数,如果是计算类型的指令,就把
指令交给「逻辑运算单元」运算;如果是存储类型的指令,则交由「控制单元」执行;

简单总结一下就是,一个程序执行的时候,CPU会根据程序计数器里的内存地址,从内存里面把需要执行
的指令读取到指令寄存器里面执行,然后根据指令长度自增,开始顺序读取下一条指令。
CPU从程序计数器读取指令、到执行、再到下一条指令,这个过程会不断循环,直到程序执行结束,这个
不断循环的过程被称为CPU的指令周期。

位数

32 位和 64 位 CPU 最主要区别在于一次能计算多少字节数据

• 32 位 CPU 一次可以计算 4 个字节；
• 64 位 CPU 一次可以计算 8 个字节；

 32 位和 64 位，通常称为 CPU 的位宽，代表的是 CPU 一次可以计算（运算）的数据量

组件

CPU 内部还有一些组件，常见的有寄存器、CPU L1/L2/L3 Cache，控制单元和逻辑运算单元等。

控制单元负责控制 CPU 工作

逻辑运算单元负责计算

寄存器可以分为多种类，每种寄存器的功能又不尽相同

寄存器种类

最靠近 CPU 的控制单元和逻辑计算单元的存储器，就是寄存器

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

程序计数器，用来存储 CPU 要执行下一条指令「所在的内存地址」，注意不是存储了下一条要执行的指令，此时指令还在内存中，程序计数器只是存储了下一条指令「的地址」。

指令寄存器，用来存放当前正在执行的指令，也就是指令本身，指令被执行完成之前，指令都存储在这里

cpu cache

CPU Cache 用的是一种叫 SRAM（Static Random-Access Memory，静态随机存储器） 的芯片

L1 Cache

通常分成「数据缓存」和「指令缓存」，L1 是距离 CPU 最近的，因此它比 L2、L3 的读写速度都快、存储空间都小  L1 高速缓存的访问速度几乎和寄存器一样快，通常只需要 2~4 个时钟周期，而大小在几十 KB 到几百 KB 不等。

每个 CPU 核心都有一块属于自己的 L1 高速缓存，指令和数据在 L1 是分开存放的

L2 Cache

L2 高速缓存同样每个 CPU 核心都有，但是 L2 高速缓存位置比 L1 高速缓存距离 CPU 核心 更远，它大小比 L1 高速缓存更大，CPU 型号不同大小也就不同，通常大小在几百 KB 到几 MB 不等，访问速度则更慢，速度在 10~20 个时钟周期

L3 Cache

L3 高速缓存通常是多个 CPU 核心共用的，位置比 L2 高速缓存距离 CPU 核心 更远，大小也会更大些，通常大小在几 MB 到几十 MB 不等，具体值根据 CPU 型号而定。
访问速度相对也比较慢一些，访问速度在 20~60个时钟周期

CPU Cache 是由很多个 Cache Line 组成的，Cache Line 是 CPU 从内存读取数据的基本单位，而 Cache Line 是由各种标志（Tag）+ 数据块（Data Block）组成

CPU Cache 通常分为三级缓存：L1 Cache、L2 Cache、L3 Cache，级别越低的离 CPU 核心越近，访问速度也快，但是存储容量相对就会越小。其中，在多核心的 CPU 里，每个核心都有各自的 L1/L2 Cache，而 L3 Cache 是所有核心共享使用的

cache和内存数据一致性

写直达

保持内存与 Cache 一致性最简单的方式是，把数据同时写入内存和 Cache 中，这种方法称为写直达

写直达法很直观，也很简单，但是问题明显，无论数据在不在 Cache 里面，每次写操作都会写回到内存，这样写操作将会花费大量的时间，无疑性能会受到很大的影响

写回

既然写直达由于每次写操作都会把数据写回到内存，而导致影响性能，于是为了要减少数据写回内存的频率，就出现了写回（Write Back）的方法

在写回机制中，当发生写操作时，新的数据仅仅被写入 Cache Block 里，只有当修改过的 Cache Block「被替换」时才需要写到内存中，减少了数据写回内存的频率，这样便可以提高系统的性能

现在 CPU 都是多核的，由于 L1/L2 Cache 是多个核心各自独有的，那么会带来多核心的缓存一致性（Cache Coherence） 的问题，如果不能保证缓存一致性的问题，就可能造成结果错误

需要一种机制，来同步两个不同核心里面的缓存数据。要实现的这个机制的话

第一点，某个 CPU 核心里的 Cache 数据更新时，必须要传播到其他核心的 Cache，这个称为写传播（Write Propagation）；
 第二点，某个 CPU 核心里对数据的操作顺序，必须在其他核心看起来顺序是一样的，这个称为事务的串行化（Transaction Serialization）

MESI 协议

有一个协议基于总线嗅探机制实现了事务串行化，也用状态机机制降低了总线带宽压力，这个协议就是 MESI 协议，这个协议就做到了 CPU 缓存一致性

~Modified，已修改
• Exclusive，独占
• Shared，共享
• Invalidated，已失效

「已修改」状态就是我们前面提到的脏标记，代表该 Cache Block 上的数据已经被更新过，但是还没有写到内存里

「已失效」状态，表示的是这个 Cache Block 里的数据已经失效了，不可以读取该状态的数据。
「独占」和「共享」状态都代表 Cache Block 里的数据是干净的，也就是说，这个时候 Cache Block 里的数据和内存里面的数据是一致性的。

「独占」和「共享」的差别在于，独占状态的时候，数据只存储在一个 CPU 核心的 Cache 里，而其他 CPU 核心的 Cache 没有该数据。这个时候，如果要向独占的 Cache 写数据，就可以直接自由地写入，而不需要通知其他 CPU 核心，因为只有你这有这个数据，就不存在缓存一致性的问题了，于是就可以随便操作该数据。

另外，在「独占」状态下的数据，如果有其他核心从内存读取了相同的数据到各自的 Cache ，那么这个时候，独占状态下的数据就会变成共享状态

。
那么，「共享」状态代表着相同的数据在多个 CPU 核心的 Cache 里都有，所以当我们要更新 Cache 里面的数据的时候，不能直接修改，而是要先向所有的其他 CPU 核心广播一个请求，要求先把其他核心的 Cache 中对应的 Cache Line 标记为「无效」状态，然后再更新当前 Cache 里面的数据

伪共享

CPU 从内存中读取数据到 Cache 的时候，并不是一个字节一个字节读取，而是一块一块的方式来读取数据的，这一块一块的数据被称为 CPU Cache Line（缓存块），所以 CPU Cache Line 是 CPU 从内存读取数据到 Cache 的单位。
至于 CPU Cache Line 大小，在 Linux 系统可以用下面的方式查看到，你可以看我服务器的 L1 Cache Line 大小是 64 字节，也就意味着 L1 Cache 一次载入数据的大小是 64 字节

因为多个线程同时读写同一个 Cache Line 的不同变量时，而导致 CPU Cache 失效的现象称为伪共享

对于多个线程共享的热点数据，即经常会修改的数据，应该避免这些数据刚好在同一个 Cache Line 中，否则就会出现为伪共享的问题

解决方法

1使得变量在 Cache Line 里是对齐的

2 前置填充和后置填充

指令周期 

分为四个阶段

CPU 的工作就是一个周期接着一个周期，周而复始。

1. CPU 通过程序计数器读取对应内存地址的指令，这个部分称为 Fetch（取得指令）；
2. CPU 对指令进行解码，这个部分称为 Decode（指令译码）；
3. CPU 执行指令，这个部分称为 Execution（执行指令）；
4. CPU 将计算结果存回寄存器或者将寄存器的值存入内存，这个部分称为 Store（数据回写）

软中断

中断请求的处理程序应该要短且快，这样才能减少对正常进程运行调度地影响，而且中断处理程序可能会暂时关闭中断，这时如果中断处理程序执行时间过长，可能在还未执行完中断处理程序前，会丢失当前其他设备的中断请求

Linux 系统为了解决中断处理程序执行过长和中断丢失的问题，将中断过程分成了两个阶段，分别是「上半部和下半部分」

• 上半部用来快速处理中断，一般会暂时关闭中断请求，主要负责处理跟硬件紧密相关或者时间敏感的事情。
• 下半部用来延迟处理上半部未完成的工作，一般以「内核线程」的方式运行

中断处理程序的上部分和下半部可以理解为：
• 上半部直接处理硬件请求，也就是硬中断，主要是负责耗时短的工作，特点是快速执行；
• 下半部是由内核触发，也就说软中断，主要是负责上半部未完成的工作，通常都是耗时比较长的事情，特点是延迟执行

DMA

直接内存访问（Direct Memory Access） 技术

在进行 I/O 设备和内存的数据传输的时候，数据搬运的工作全部交给 DMA 控制器，而 CPU 不再参与任何与数据搬运相关的事情，这样 CPU 就可以去处理别的事务

零拷贝技术实现的方式通常有 2 种

• mmap + write
• sendfile

mmap + write

sendfile

对于支持网卡支持 SG-DMA 技术的情况下， sendfile() 系统调用的过程发生了点变化

进程管理

进程：运行中的程序，就被称为「进程」

在一个进程的活动期间至少具备三种基本状态，即运行状态、就绪状态、阻塞状态

控制结构

用进程控制块（process control block，PCB）数据结构来描述进程的

PCB 是进程存在的唯一标识，这意味着一个进程的存在，必然会有一个 PCB，如果进程消失了，那么 PCB 也会随之消失

进程描述信息：
• 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符；
• 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务；
进程控制和管理信息：
• 进程当前状态，如 new、ready、running、waiting 或 blocked 等；
• 进程优先级：进程抢占 CPU 时的优先级；
资源分配清单：
• 有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。
CPU 相关信息：
• CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行

上下文切换

各个进程之间是共享 CPU 资源的，在不同的时候进程之间需要切换，让不同的进程可以在 CPU 执行，那么这个一个进程切换到另一个进程运行，称为进程的上下文切换

进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源

线程

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

线程的优点：
• 一个进程中可以同时存在多个线程；
• 各个线程之间可以并发执行；
• 各个线程之间可以共享地址空间和文件等资源；

线程的缺点：
• 当进程中的一个线程崩溃时，会导致其所属进程的所有线程崩溃

上下文切换

当两个线程不是属于同一个进程，则切换的过程就跟进程上下文切换一样；
当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据

线程与进程的比较

线程与进程的比较如下：
• 进程是资源（包括内存、打开的文件等）分配的单位，线程是 CPU 调度的单位；
• 进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；
• 线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转换关系；
• 线程能减少并发执行的时间和空间开销；
对于，线程相比进程能减少开销，体现在：
• 线程的创建时间比进程快，因为进程在创建的过程中，还需要资源管理信息，比如内存管理信息、文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们；
• 线程的终止时间比进程快，因为线程释放的资源相比进程少很多；
• 同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间（虚拟内存共享），这意味着同一个进程的线程都具有同一个页表，那么在切换的时候不需要切换页表。而对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的；
• 由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的数据交互效率更高了；
所以，不管是时间效率，还是空间效率线程比进程都要高

进程通讯方式

每个进程的用户地址空间都是独立的，一般而言是不能互相访问的，但内核空间是每个进程都共享的，所以进程之间要通信必须通过内核

管道 依赖内核缓冲区

所谓的管道，就是内核里面的一串缓存。从管道的一段写入的数据，实际上是缓存在内核中的，另一端读取，也就是从内核中读取这段数据。另外，管道传输的数据是无格式的流且大小受限

进程写入的数据都是缓存在内核中，另一个进程读取数据时候自然也是从内核中获取，同时通信数据都遵循先进先出原则

管道传输数据是单向的，如果想相互通信，我们需要创建两个管道才行

缺点：管道这种通信方式效率低，不适合进程间频繁地交换数据

优点：自然就是简单，同时也我们很容易得知管道里的数据已经被另一个进程读取了

匿名管道 

它的通信范围是存在父子关系的进程  半双工

无名管道通常是在父子进程之间使用，创建无名管道时会同时返回读端和写端的文件描述符。如果在程序中创建了无名管道，但没有任何进程使用读端文件描述符进行读取操作，当有进程向管道写入数据时，写入操作不会因为没有读进程而立即阻塞。只要管道缓冲区还有空间，写入操作就可以正常进行，直到缓冲区被填满。当缓冲区满后，写入进程会阻塞，直到有进程从管道读取数据腾出空间

命名管道

 它可以在不相关的进程间也能相互通信

对于命名管道，在默认阻塞模式下，当一个进程以写模式打开命名管道时，如果此时没有其他进程以读模式打开该命名管道，打开操作会阻塞，直到有进程以读模式打开它。这是因为命名管道是一种独立于进程的文件系统对象，其设计机制要求在写入数据之前必须有读进程准备好接收数据

有点像golang中的无缓存的channel 但管道时有缓冲区的 只不过读进程和写进程要同时存在

消息队列   依赖内核缓冲区

全双工

消息队列是保存在内核中的消息链表

消息队列生命周期随内核，如果没有释放消息队列或者没有关闭操作系统，消息队列会一直存在，而前面提到的匿名管道的生命周期，是随进程的创建而建立，随进程的结束而销毁

缺点：

通信不及时

附件也有大小限制

消息队列不适合比较大数据的传输

消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销

有点像golang中的有缓存的channel

通信机制

• ​管道

  • ​同步阻塞：读写操作默认阻塞，需双方进程协作（如读端等待写端数据）
  • ​容量限制：通常缓冲区较小（如4KB），溢出时发送方阻塞

• ​消息队列

  • ​异步非阻塞：消息可暂存于队列中，发送方无需等待接收方处理
  • ​优先级支持：消息可设置优先级，高优先级消息优先被读取
  • ​容量限制：单条消息最大8KB，队列总容量受系统限制

• ​优先管道的场景：

  • 简单数据流传输（如日志、命令行参数）。
  • 需要同步协作的父子进程通信。

• ​优先消息队列的场景：

  • 需要异步传输或消息优先级管理（如任务调度系统）。
  • 复杂数据结构传输（如结构体、二进制数据块）

共享内存

共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中

这样这个进程写入的东西，另外一个进程马上就能看到了，都不需要拷贝来拷贝去，传来传去，大大提高了进程间通信的速度

信号量

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

信号量表示资源的数量，控制信号量的方式有两种原子操作：
• 一个是 P 操作，这个操作会把信号量减去 1，相减后如果信号量 < 0，则表明资源已被占用，进程需阻塞等待；相减后如果信号量 >= 0，则表明还有资源可使用，进程可正常继续执行。
• 另一个是 V 操作，这个操作会把信号量加上 1，相加后如果信号量 <= 0，则表明当前有阻塞中的进程，于是会将该进程唤醒运行；相加后如果信号量 > 0，则表明当前没有阻塞中的进程

信号

对于异常情况下的工作模式，就需要用「信号」的方式来通知进程

信号是进程间通信机制中唯一的异步通信机制，

因为可以在任何时候发送信号给某一进程，一旦有信号产生，我们就有下面这几种，用户进程对信号的处理方式。
1.执行默认操作。Linux 对每种信号都规定了默认操作，例如，上面列表中的 SIGTERM 信号，就是终止进程的意思。
2.捕捉信号。我们可以为信号定义一个信号处理函数。当信号发生时，我们就执行相应的信号处理函数。
3.忽略信号。当我们不希望处理某些信号的时候，就可以忽略该信号，不做任何处理。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP，它们用于在任何时候中断或结束某一进程

socket

想跨网络与不同主机上的进程之间通信，就需要 Socket 通信了

Socket 实际上不仅用于不同的主机进程间通信，还可以用于本地主机进程间通信，可根据创建 Socket 的类型不同，分为三种常见的通信方式，一个是基于 TCP 协议的通信方式，一个是基于 UDP 协议的通信方式，一个是本地进程间通信方式

内存管理

虚拟内存

操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来

如果程序要访问虚拟地址的时候，由操作系统转换成不同的物理地址，这样不同的进程运行的时候，写入的是不同的物理地址，这样就不会冲突了

我们程序所使用的内存地址叫做虚拟内存地址（Virtual Memory Address）
实际存在硬件里面的空间地址叫物理内存地址（Physical Memory Address）

进程持有的虚拟地址会通过 CPU 芯片中的内存管理单元（MMU）的映射关系，来转换变成物理地址，然后再通过物理地址访问内存

操作系统管理虚拟地址与物理地址之间的关系主要有两种方式

内存分段 分段是比较早提出的

内存分页

分段

程序是由若干个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的，所以就用分段（Segmentation）的形式把这些段分离出来

分段机制下的虚拟地址由两部分组成，段选择因子和段内偏移量

段选择子就保存在段寄存器里面。段选择子里面最重要的是段号，用作段表的索引。段表里面保存的是这个段的基地址、段的界限和特权等级等。
 虚拟地址中的段内偏移量应该位于 0 和段界限之间，如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址。

缺点

• 内存碎片
•  解决「外部内存碎片」的问题就是内存交换

• 内存交换的效率低 
• 对于多进程的系统来说，用分段的方式，外部内存碎片是很容易产生的，产生了外部内存碎片，那不得不重新 Swap 内存区域，这个过程会产生性能瓶颈。
• 因为硬盘的访问速度要比内存慢太多了，每一次内存交换，我们都需要把一大段连续的内存数据写到硬盘上。
  所以，如果内存交换的时候，交换的是一个占内存空间很大的程序，这样整个机器都会显得卡顿

分页

分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间，我们叫页（Page）。在 Linux 下，每一页的大小为 4KB

页表是存储在内存里的，内存管理单元 （MMU）就做将虚拟内存地址转换成物理地址的工作。
而当进程访问的虚拟地址在页表中查不到时，系统会产生一个缺页异常，进入系统内核空间分配物理内存、更新进程页表，最后再返回用户空间，恢复进程的运行

如果内存空间不够，操作系统会把其他正在运行的进程中的「最近没被使用」的内存页面给释放掉，也就是暂时写在硬盘上，称为换出（Swap Out）。一旦需要的时候，再加载进来，称为换入（Swap In）。所以，一次性写入磁盘的也只有少数的一个页或者几个页，不会花太多时间，内存交换的效率就相对比较高

缺点：

内存分页机制会有内部内存碎片

页表占用比较大的空间 需采用多级页表 比如二级分页

段页式

先将程序划分为多个有逻辑意义的段，也就是前面提到的分段机制；
 接着再把每个段划分为多个页，也就是对分段划分出来的连续空间，再划分固定大小的页

地址结构就由段号、段内页号和页内位移三部分组成

预读机制

Linux 操作系统为基于 Page Cache 的读缓存机制提供预读机制

磁盘的基本读写单位为 block（4KB）操作系统出于空间局部性原理（靠近当前被访问数据的数据，在未来很大概率会被访问到），会选择将磁盘块 offset [4KB,8KB)、[8KB,12KB) 以及 [12KB,16KB) 都加载到内存，于是额外在内存中申请了 3 个 page

好处

预读机制带来的好处就是减少了 磁盘 I/O 次数，提高系统磁盘 I/O 吞吐量

预读失效

如果这些被提前加载进来的页，并没有被访问，相当于这个预读工作是白做了，这个就是预读失效

如果使用传统的 LRU 算法，就会把「预读页」放到 LRU 链表头部，而当内存空间不够的时候，还需要把末尾的页淘汰掉。
如果这些「预读页」如果一直不会被访问到，就会出现一个很奇怪的问题，不会被访问的预读页却占用了 LRU 链表前排的位置，而末尾淘汰的页，可能是热点数据，这样就大大降低了缓存命中率

解决思路

让预读页停留在内存里的时间要尽可能的短，让真正被访问的页才移动到 LRU 链表的头部，从而保证真正被读取的热数据留在内存里的时间尽可能长

Linux 操作系统实现两个了 LRU 链表：活跃 LRU 链表（active_list）和非活跃 LRU 链表（inactive_list）

active list 活跃内存页链表，这里存放的是最近被访问过（活跃）的内存页；
 inactive list 不活跃内存页链表，这里存放的是很少被访问（非活跃）的内存页；

有了这两个 LRU 链表后，预读页就只需要加入到 inactive list 区域的头部，当页被真正访问的时候，才将页插入 active list 的头部。如果预读的页一直没有被访问，就会从 inactive list 移除，这样就不会影响 active list 中的热点数据

缓存污染

当我们在批量读取数据的时候，由于数据被访问了一次，这些大量数据都会被加入到「活跃 LRU 链表」里，然后之前缓存在活跃 LRU 链表（或者 young 区域）里的热点数据全部都被淘汰了，如果这些大量的数据在很长一段时间都不会被访问的话，那么整个活跃 LRU 链表（或者 young 区域）就被污染了

缺点

缓存污染带来的影响就是很致命的，等这些热数据又被再次访问的时候，由于缓存未命中，就会产生大量的磁盘 I/O，系统性能就会急剧下降

只要我们提高进入到活跃 LRU 链表（或者 young 区域）的门槛，就能有效地保证活跃 LRU 链表（或者 young 区域）里的热点数据不会被轻易替换掉。

• Linux 操作系统：在内存页被访问第二次的时候，才将页从 inactive list 升级到 active list 里

调度算法

进程调度算法

• 先来先服务调度算法

非抢占式的先来先服务（First Come First Severd, FCFS）算法

先来后到，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行

当一个长作业先运行了，那么后面的短作业等待的时间就会很长，不利于短作业。
FCFS 对长作业有利，适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统

• 最短作业优先调度算法

优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量

个长作业在就绪队列等待运行，而这个就绪队列有非常多的短作业，那么就会使得长作业不断的往后推，周转时间变长，致使长作业长期不会被运行

• 高响应比优先调度算法

每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行

• 时间片轮转调度算法

最古老、最简单、最公平且使用最广的算法就是时间片轮转（Round Robin, RR）调度算法

每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。
• 如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配另外一个进程；
• 如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换；
另外，时间片的长度就是一个很关键的点：
• 如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率；
• 如果设得太长又可能引起对短作业进程的响应时间变长。将
通常时间片设为 20ms~50ms 通常是一个比较合理的折中值

• 最高优先级调度算法

从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级（Highest Priority First，HPF）调度算法

进程的优先级可以分为，静态优先级或动态优先级：
• 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
• 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。
该算法也有两种处理优先级高的方法，非抢占式和抢占式：
• 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
• 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。
但是依然有缺点，可能会导致低优先级的进程永远不会运行

• 多级反馈队列调度算法

是「时间片轮转算法」和「最高优先级算法」的综合和发展

设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；
• 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
• 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行

页面置换算法

磁盘调度算法

当出现缺页异常，需调入新页面而内存已满时，选择被置换的物理页面，也就是说选择一个物理页面换出到磁盘，然后把需要访问的页面换入到物理页

• 最佳页面置换算法（OPT）

置换在「未来」最长时间不访问的页面

• 先进先出置换算法（FIFO）

选择在内存驻留时间很长的页面进行中置换

• 最近最久未使用的置换算法（LRU）

选择最长时间没有被访问的页面进行置换

• 时钟页面置换算法（Lock）

把所有的页面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的页面。
当发生缺页中断时，算法首先检查表针指向的页面

• 最不常用置换算法（LFU）

当发生缺页中断时，选择「访问次数」最少的那个页面，并将其淘汰

磁盘调度算法

• 先来先服务算法

先到来的请求，先被服务

比较简单粗暴，但是如果大量进程竞争使用磁盘，请求访问的磁道可能会很分散，那先来先服务算法在性能上就会显得很差，因为寻道时间过长

• 最短寻道时间优先算法

优先选择从当前磁头位置所需寻道时间最短的请求

但这个算法可能存在某些请求的饥饿，产生饥饿的原因是磁头在一小块区域来回移动

• 扫描算法

磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向，这就是扫描（Scan）算法

存在这样的问题，中间部分的磁道会比较占便宜，中间部分相比其他部分响应的频率会比较多，也就是说每个磁道的响应频率存在差异

• 循环扫描算法

只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求，该算法的特点，就是磁道只响应一个方向上的请求

• LOOK 与 C-LOOK 算法

针对 SCAN 算法的优化则叫 LOOK 算法 它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中会响应请求

针对 C-SCAN 算法的优化则叫 C-LOOK，它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中不会响应请求

文件系统

Linux 文件系统会为每个文件分配两个数据结构：索引节点（index node）和目录项（directory entry），它们主要用来记录文件的元信息和目录层次结构

• 索引节点，也就是 inode，用来记录文件的元信息，比如 inode 编号、文件大小、访问权限、创建时间、修改时间、数据在磁盘的位置等等。索引节点是文件的唯一标识，它们之间一一对应，也同样都会被存储在硬盘中，所以索引节点同样占用磁盘空间。
• 目录项，也就是 dentry，用来记录文件的名字、索引节点指针以及与其他目录项的层级关联关系。多个目录项关联起来，就会形成目录结构，但它与索引节点不同的是，目录项是由内核维护的一个数据结构，不存放于磁盘，而是缓存在内存

Linux 支持的文件系统也不少，根据存储位置的不同，可以把文件系统分为三类：
• 磁盘的文件系统，它是直接把数据存储在磁盘中，比如 Ext 2/3/4、XFS 等都是这类文件系统。
• 内存的文件系统，这类文件系统的数据不是存储在硬盘的，而是占用内存空间，我们经常用到的 /proc 和 /sys 文件系统都属于这一类，读写这类文件，实际上是读写内核中相关的数据。
• 网络的文件系统，用来访问其他计算机主机数据的文件系统，比如 NFS、SMB 等等。
文件系统首先要先挂载到某个目录才可以正常使用，比如 Linux 系统在启动时，会把文件系统挂载到根目录

文件的存储

• 连续空间存放方式

读写效率很高

但是有「磁盘空间碎片」和「文件长度不易扩展」的缺陷

• 非连续空间存放方式
其中，非连续空间存放方式又可以分为「链表方式」和「索引方式」

可以消除磁盘碎片，可大大提高磁盘空间的利用率，同时文件的长度可以动态扩展。根据实现的方式的不同，链表可分为「隐式链表」和「显式链接」两种形式

有时候我们希望给某个文件取个别名，那么在 Linux 中可以通过硬链接（Hard Link） 和软链接（Symbolic Link） 的方式来实现

硬链接

硬链接是多个目录项中的「索引节点」指向一个文件，也就是指向同一个 inode，但是 inode 是不可能跨越文件系统的，每个文件系统都有各自的 inode 数据结构和列表，所以硬链接是不可用于跨文件系统的。由于多个目录项都是指向一个 inode，那么只有删除文件的所有硬链接以及源文件时，系统才会彻底删除该文件

软链接

软链接相当于重新创建一个文件，这个文件有独立的 inode，但是这个文件的内容是另外一个文件的路径，所以访问软链接的时候，实际上相当于访问到了另外一个文件，所以软链接是可以跨文件系统的，甚至目标文件被删除了，链接文件还是在的，只不过指向的文件找不到了而已

网络系统

一致性哈希算法

解决了分布式系统在扩容或者缩容时，发生过多的数据迁移的问题

一致性哈希是指将「存储节点」和「数据」都映射到一个首尾相连的哈希环上

映射的结果值往顺时针的方向的找到第一个节点，就是存储该数据的节点

Reactor 模式

I/O 多路复用监听事件，收到事件后，根据事件类型分配（Dispatch）给某个进程 / 线程

常见的 Reactor 实现方案有三种。
第一种方案单 Reactor 单进程 / 线程，不用考虑进程间通信以及数据同步的问题，因此实现起来比较简单，这种方案的缺陷在于无法充分利用多核 CPU，而且处理业务逻辑的时间不能太长，否则会延迟响应，所以不适用于计算机密集型的场景，适用于业务处理快速的场景，比如 Redis（6.0之前 ） 采用的是单 Reactor 单进程的方案。
第二种方案单 Reactor 多线程，通过多线程的方式解决了方案一的缺陷，但它离高并发还差一点距离，差在只有一个 Reactor 对象来承担所有事件的监听和响应，而且只在主线程中运行，在面对瞬间高并发的场景时，容易成为性能的瓶颈的地方。
第三种方案多 Reactor 多进程 / 线程，通过多个 Reactor 来解决了方案二的缺陷，主 Reactor 只负责监听事件，响应事件的工作交给了从 Reactor，Netty 和 Memcache 都采用了「多 Reactor 多线程」的方案，Nginx 则采用了类似于 「多 Reactor 多进程」的方案。
Reactor 可以理解为「来了事件操作系统通知应用进程，让应用进程来处理」