图解系统-小林coding笔记

整体架构图

一、硬件结构

当CPU要读写内存数据的时候，一般需要通过两个总线：

• 首先要通过地址总线来指定内存的地址；
• 再通过数据总线来传输数据。

线路位宽与CPU位宽

硬件的64位和32位指的是CPU的位宽，软件的64位和32位指的是指令到位宽。

程序执行的基本过程

⼀个程序执⾏的时候， CPU 会根据程序计数器⾥的内存地址，从内存⾥⾯把需要执⾏的指令读取到指令寄存器⾥⾯执⾏，然后根据指令⻓度⾃增，开始顺序读取下⼀条指令。
CPU 从程序计数器读取指令、到执⾏、再到下⼀条指令，这个过程会不断循环，直到程序执⾏结束，这个不断循环的过程被称为 CPU 的指令周期。

a=1+2执行具体过程

指令

不同的 CPU 有不同的指令集，也就是对应着不同的汇编语⾔和不同的机器码，接下来选⽤最简单的 MIPS指集，来看看机器码是如何⽣成的，这样也能明⽩⼆进制的机器码的具体含义。

编译器在编译程序的时候，会构造指令，这个过程叫做指令的编码。 CPU 执⾏程序的时候，就会解析指令，这个过程叫作指令的解码。

现代⼤多数 CPU 都使⽤来流⽔线的⽅式来执⾏指令，所谓的流⽔线就是把⼀个任务拆分成多个⼩任务，于是⼀条指令通常分为 4 个阶段，称为 4 级流⽔线，如下图：
CPU 通过程序计数器读取对应内存地址的指令，这个部分称为 Fetch（取得指令） ；
2. CPU 对指令进⾏解码，这个部分称为 Decode（指令译码） ；
3. CPU 执⾏指令，这个部分称为 Execution（执⾏指令） ；
4. CPU 将计算结果存回寄存器或者将寄存器的值存⼊内存，这个部分称为 Store（数据回写） ；
上⾯这 4 个阶段，我们称为指令周期（Instrution Cycle） ， CPU 的⼯作就是⼀个周期接着⼀个周期，周⽽复始。

指令的类型

指令从功能⻆度划分，可以分为 5 ⼤类：
数据传输类型的指令，⽐如 store/load 是寄存器与内存间数据传输的指令， mov 是将⼀个内存地
址的数据移动到另⼀个内存地址的指令；
运算类型的指令，⽐如加减乘除、位运算、⽐较⼤⼩等等，它们最多只能处理两个寄存器中的数据；
跳转类型的指令，通过修改程序计数器的值来达到跳转执⾏指令的过程，⽐如编程中常⻅的 ifelse 、 swtich-case 、函数调⽤等。
信号类型的指令，⽐如发⽣中断的指令 trap ；
闲置类型的指令，⽐如指令 nop ，执⾏后 CPU 会空转⼀个周期

指令的执行速度

CPU 的硬件参数都会有 GHz 这个参数，比如⼀个 1 GHz 的 CPU，指的是时钟频率是 1 G，代表着 1 秒会产⽣ 1G 次数的脉冲信号，每⼀次脉冲信号⾼低电平的转换就是⼀个周期，称为时钟周期。
对于 CPU 来说，在⼀个时钟周期内， CPU 仅能完成⼀个最基本的动作，时钟频率越⾼，时钟周期就越短，⼯作速度也就越快。

CPU时钟周期：指令数 $\times$ 每条指令的平均时钟周期数(CPI)，于是：

要想程序跑得更快，优化这三者即可：

• 指令数，表示执⾏程序所需要多少条指令，以及哪些指令。这个层⾯是基本靠编译器来优化，毕竟同样的代码，在不同的编译器，编译出来的计算机指令会有各种不同的表示⽅式。
• 每条指令的平均时钟周期数CPI，表示⼀条指令需要多少个时钟周期数，现代⼤多数 CPU 通过流⽔
  线技术（Pipline），让⼀条指令需要的 CPU 时钟周期数尽可能的少；
• 时钟周期时间，表示计算机主频，取决于计算机硬件。有的 CPU ⽀持超频技术，打开了超频意味着把 CPU 内部的时钟给调快了，于是 CPU ⼯作速度就变快了，但是也是有代价的， CPU 跑的越快，散热的压⼒就会越⼤， CPU 会很容易奔溃。

存储器金字塔

CPU Cache的数据结构和读取过程是什么样的？

CPU怎么知道要访问的内存数据，是否在Cache里，如果在的话，如何找到Cache对应的数据呢？

直接映射Cache

CPU 访问内存数据时，是⼀⼩块⼀⼩块数据读取的，具体这⼀⼩块数据的⼤⼩，取决于coherency_line_size 的值，⼀般 64 字节。在内存中，这⼀块的数据我们称为内存块（Block） ，读取的时候我们要拿到数据所在内存块的地址。

直接映射Cache采用取模运算策略，取模运算的结果就是内存块地址对应的 CPU Line（缓存块） 的地址。
CPU 在从 CPU Cache 读取数据的时候，并不是读取 CPU Line 中的整个数据块，⽽是读取 CPU 所需要的
⼀个数据⽚段，这样的数据统称为⼀个字（Word） 。那怎么在对应的 CPU Line 中数据块中找到所需的字
呢？答案是，需要⼀个偏移量（Offset） 。

⼀个内存的访问地址，包括组标记、 CPU Line 索引、偏移量这三种信息，于是 CPU 就能通过这些信息，在 CPU Cache 中找到缓存的数据。⽽对于 CPU Cache ⾥的数据结构，则是由索引 + 有效位 + 组标记 + 数据块组成。

全相连Cache（可了解）

组相连Cache（可了解）

CPU缓存一致性

在什么时机才把Cache中的数据写回到内存中：

• 写直达（ 把数据同时写⼊内存和 Cache 中，效率问题）
• 写回（在把数据写⼊到 Cache 的时候，只有在缓存不命中，同时数据对应的 Cache 中的 Cache Block 为<>脏标记的情况下，才会将数据写到内存中，⽽在缓存命中的情况下，则在写⼊后 Cache后，只需把该数据对应的 Cache Block 标记为脏即可，⽽不⽤写到内存⾥。）

解决写回引起的一致性问题：
1、写传播：某个 CPU 核⼼⾥的 Cache 数据更新时，必须要传播到其他核⼼的 Cache；
2、事务的串形化：某个 CPU 核⼼⾥对数据的操作顺序，必须在其他核⼼看起来顺序是⼀样的。

要实现事务串行化：
CPU 核⼼对于 Cache 中数据的操作，需要同步给其他 CPU 核⼼；
要引⼊「锁」的概念，如果两个 CPU 核⼼⾥有相同数据的 Cache，那么对于这个 Cache 数据的更新，只有拿到了「锁」，才能进⾏对应的数据更新。

MESI协议

MESI协议其实是 4 个状态单词的开头字⺟缩写，分别是：

• Modified，已修改(脏标记)
• Exclusive，独占
• Shared，共享
• Invalidated，已失效

这四个状态来标记 Cache Line 四个不同的状态。

CPU是如何执行任务的？

现代CPU的架构图：

CPU 从内存中读取数据到 Cache 的时候，并不是⼀个字节⼀个字节读取，⽽是⼀块⼀块的⽅式来读取数
据的，这⼀块⼀块的数据被称为 CPU Line（缓存⾏），所以 CPU Line 是 CPU 从内存读取数据到 Cache的单位。

伪共享

伪共享：因为多个线程同时读写同一个Cache Line的不同变量时，而导致CPU Cache失效的现象。
解决办法：用空间换时间，对齐地址。
有⼀个 Java 并发框架 Disruptor 使⽤「字节填充 + 继承」的⽅式，来避免伪共享的问题。

CPU如何选择线程的？

调度类

由于任务有优先级之分， Linux 系统为了保障⾼优先级的任务能够尽可能早的被执⾏，于是分为了这⼏种调度类：

Deadline 和 Realtime 这两个调度类，都是应⽤于实时任务的，这两个调度类的调度策略合起来共有这三种，它们的作⽤如下：

• SCHED_DEADLINE：是按照 deadline 进⾏调度的，距离当前时间点最近的 deadline 的任务会被优先调度；
• SCHED_FIFO：对于相同优先级的任务，按先来先服务的原则，但是优先级更⾼的任务，可以抢占低优先级的任务，也就是优先级⾼的可以「插队」；
• SCHED_RR：对于相同优先级的任务，轮流着运⾏，每个任务都有⼀定的时间⽚，当⽤完时间⽚的任务会被放到队列尾部，以保证相同优先级任务的公平性，但是⾼优先级的任务依然可以抢占低优先级的任务；

而 Fair 调度类是应⽤于普通任务，都是由 CFS 调度器管理的，分为两种调度策略：

• SCHED_NORMAL：普通任务使⽤的调度策略；
• SCHED_BATCH：后台任务的调度策略，不和终端进⾏交互，因此在不影响其他需要交互的任务，可以适当降低它的优先级。

完全公平调度

我们平⽇⾥遇到的基本都是普通任务，对于普通任务来说，公平性最重要，在 Linux ⾥⾯，实现了⼀个基于 CFS 的调度算法，也就是完全公平调度（Completely Fair Scheduling） 。
这个算法的理念是想让分配给每个任务的 CPU 时间是⼀样，于是它为每个任务安排⼀个虚拟运⾏时间vruntime，如果⼀个任务在运⾏，其运⾏的越久，该任务的 vruntime ⾃然就会越⼤，⽽没有被运⾏的任务， vruntime 是不会变化的。
那么， 在 CFS 算法调度的时候，会优先选择 vruntime 少的任务，以保证每个任务的公平性。

CPU运行队列

⼀个系统通常都会运⾏着很多任务，多任务的数量基本都是远超 CPU 核⼼数量，因此这时候就需要排队。
事实上，每个 CPU 都有⾃⼰的运⾏队列（Run Queue, rq） ，⽤于描述在此 CPU 上所运⾏的所有进程，其队列包含三个运⾏队列， Deadline 运⾏队列 dl_rq、实时任务运⾏队列 rt_rq 和 CFS 运⾏队列 csf_rq，其中 csf_rq 是⽤红⿊树来描述的，按 vruntime ⼤⼩来排序的，最左侧的叶⼦节点，就是下次会被调度的任务。

Deadline > Realtime > Fair
实时任务总是会⽐普通任务优先被执⾏

调整优先级

如果我们启动任务的时候，没有特意去指定优先级的话，默认情况下都是普通任务，普通任务的调度类是Fail，由 CFS 调度器来进⾏管理。 CFS 调度器的⽬的是实现任务运⾏的公平性，也就是保障每个任务的运⾏的时间是差不多的。

如果你想让某个普通任务有更多的执⾏时间，可以调整任务的 nice 值，从⽽让优先级⾼⼀些的任务执⾏更多时间。 nice 的值能设置的范围是 -20～19 ， 值越低，表明优先级越⾼，因此 -20 是最⾼优先级， 19则是最低优先级，默认优先级是 0。


nice 调整的是普通任务的优先级，所以不管怎么缩⼩ nice 值，任务永远都是普通任务，如果某些任务要求实时性⽐较⾼，那么你可以考虑改变任务的优先级以及调度策略，使得它变成实时任务，⽐如：

软中断

中断

在计算机中，中断是系统⽤来响应硬件设备请求的⼀种机制，操作系统收到硬件的中断请求，会打断正在执⾏的进程，然后调⽤内核中的中断处理程序来响应请求。

中断请求的响应程序，也就是中断处理程序，要尽可能快的执⾏完，这样可以减少对正常进程运⾏调度地影响。

什么是软中断？

硬中断：主要是负责耗时短的⼯作，特点是快速执⾏；
软中断：主要是负责上半部未完成的⼯作，通常都是耗时⽐较⻓的事情，特点是延迟执⾏；

系统里有哪些软中断？

在 Linux 系统⾥，我们可以通过查看 /proc/softirqs 的 内容来知晓「软中断」的运⾏情况，以及/proc/interrupts 的 内容来知晓「硬中断」的运⾏情况。

每个 CPU核⼼都对应着⼀个内核线程。

如何定位软中断CPU使用率过高的问题？

每⼀个 CPU 都有各⾃的软中断内核线程，我们还可以⽤ ps 命令来查看内核线程，⼀般名字在中括号⾥⾯到，都认为是内核线程。

如果在 top 命令发现， CPU 在软中断上的使⽤率⽐较⾼，⽽且 CPU 使⽤率最⾼的进程也是软中断ksoftirqd 的时候，这种⼀般可以认为系统的开销被软中断占据了。

这时我们就可以分析是哪种软中断类型导致的，⼀般来说都是因为⽹络接收软中断导致的，如果是的话，可以⽤ sar 命令查看是哪个⽹卡的有⼤量的⽹络包接收，再⽤ tcpdump 抓⽹络包，做进⼀步分析该⽹络包的源头是不是⾮法地址，如果是就需要考虑防⽕墙增加规则，如果不是，则考虑硬件升级等。

为什么0.1+0.2不等于0.3?

由于计算机的资源是有限的，所以是没办法⽤⼆进制精确的表示 0.1，只能⽤「近似值」来表示，就是在有限的精度情况下，最⼤化接近 0.1 的⼆进制数，于是就会造成精度缺失的情况。

为什么负数要用补码表示？

补码：所谓的补码就是把正数的⼆进制全部取反再加 1。

负数之所以⽤补码的⽅式来表示，主要是为了统⼀和正数的加减法操作⼀样，毕竟数字的加减法是很常⽤的⼀个操作，就不要搞特殊化，尽量以统⼀的⽅式来运算。

计算机是怎么存小数的?

二、操作系统结构

什么是内核？

对于内核的架构⼀般有这三种类型：

• 宏内核，包含多个模块，整个内核像⼀个完整的程序；
• 微内核，有⼀个最小版本的内核，⼀些模块和服务则由⽤户态管理；
• 混合内核，是宏内核和微内核的结合体，内核中抽象出了微内核的概念，也就是内核中会有⼀个小型的内核，其他模块就在这个基础上搭建，整个内核是个完整的程序；

Linux 的内核设计是采用了宏内核， Window 的内核设计则是采用了混合内核。
这两个操作系统的可执行文件格式也不⼀样， Linux 可执行文件格式叫作 ELF， Windows 可执行文件格式叫作 PE。

三、内存管理

虚拟内存

单片机的CPU是直接操作内存的「物理地址」。

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

内存分段

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

分段机制下的虚拟地址：段选择子和段内偏移量。

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

内存分页

分页是把整个虚拟和物理内存空间切成⼀段段固定尺寸的大小。这样⼀个连续并且尺寸固定的内存空间，我们叫页（Page）。在 Linux 下，每一页的大小为 4KB 。
页表是存储在内存里的， 内存管理单元 （MMU）就做将虚拟内存地址转换成物理地址的工作。

分页是怎么解决分段的内存碎片、内存交换效率低的问题？

采用了分页，那么释放的内存都是以页为单位释放的，也就不会产生无法给进程使用的小内存。

简单的分页的缺点

空间上的缺陷：操作系统可以同时运行非常多的进程，意味着页表会非常庞大。

如果使用了⼆级分页，⼀级页表就可以覆盖整个 4GB 虚拟地址空间，但如果某个⼀级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建⼆级页表。做个简单的计算，假设只有 20% 的⼀级页表项被用到了，那么页表占用的内存空间就只有 4KB（⼀级页表） + 20% * 4MB（二级页表） = 0.804MB ，这对比单级页表的 4MB 是不是⼀个巨⼤的节约？

那么为什么不分级的页表就做不到这样节约内存呢？我们从页表的性质来看，保存在内存中的页表承担的职责是将虚拟地址翻译成物理地址。假如虚拟地址在页表中找不到对应的页表项，计算机系统就不能工作了。所以页表⼀定要覆盖全部虚拟地址空间，不分级的页表就需要有 100 多万个页表项来映射，而二级分页则只需要 1024 个页表项（此时⼀级页表覆盖到了全部虚拟地址空间，而级页表在需要时创建）。
我们把二级分页再推广到多级页表，就会发现页表占用的内存空间更少了，这⼀切都要归功于对局部性原理的充分应用。

64位系统分为四级目录：

• 全局页目录项 PGD（Page Global Directory）；
• 上层页目录想PUD（Page Upper Directory）；
• 中间页目录项PMD（Page Middle Directory）；
• 页表项PTE（Page Table Entry）；

TLB

CPU 芯片中，加⼊了⼀个专门存放程序最常访问的页表项的 Cache，这个 Cache 就是 TLB（Translation Lookaside Buffer） ，通常称为⻚表缓存、转址旁路缓存、快表等。

Linux内存管理

Linux 系统主要采⽤了分⻚管理，但是由于 Intel 处理器的发展史， Linux 系统⽆法避免分段管理。于是Linux 就把所有段的基地址设为 0 ，也就意味着所有程序的地址空间都是线性地址空间（虚拟地址），相当于屏蔽了 CPU 逻辑地址的概念，所以段只被用于访问控制和内存保护。
Linux 系统中虚拟空间分布可分为用户态和内核态两部分，其中用户态的分布：代码段、全局变量、BSS、函数栈、堆内存、映射区。

四、进程与线程

进程

进程的7种状态：

• 创建状态
• 就绪状态
• 就绪挂起状态
• 运行状态
• 阻塞状态
• 阻塞挂起状态
• 结束状态

进程的控制结构

在操作系统中，是用进程控制块（process control block， PCB）数据结构来描述进程的。

PCB的组织形式

除了链接的组织方式，还有索引方式，它的工作原理：将同⼀状态的进程组织在⼀个索引表中，索引表项指向相应的 PCB，不同状态对应不同的索引表。
一般会选择链表，方便进程的创建、销毁等调度方式。

进程的控制

进程的上下文切换

CPU上下文切换分为：

• 进程上下文切换
• 线程上下文切换
• 终端上下文切换

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

发生进程上下文切换有哪些场景？

• 为了保证所有进程可以得到公平调度， CPU 时间被划分为⼀段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，进程就从运⾏状态变为就绪状态，系统从就绪队列选择另外⼀个进程运⾏；
• 进程在系统资源不⾜（⽐如内存不⾜）时，要等到资源满⾜后才可以运⾏，这个时候进程也会被挂起，并由系统调度其他进程运⾏；
• 当进程通过睡眠函数 sleep 这样的⽅法将⾃⼰主动挂起时，⾃然也会重新调度；
• 当有优先级更⾼的进程运⾏时，为了保证⾼优先级进程的运⾏，当前进程会被挂起，由⾼优先级进程来运⾏；
• 发⽣硬件中断时， CPU 上的进程会被中断挂起，转⽽执⾏内核中的中断服务程序；

线程

线程是进程当中的一条执行流程。

线程是调度的基本单位，而进程则是资源拥有的基本单位。

线程的上下文切换

线程的实现

用户线程如何理解？存在什么优势和缺陷？

⽤户线程是基于⽤户态的线程管理库来实现的，那么线程控制块（Thread Control Block, TCB） 也是在库⾥⾯来实现的，对于操作系统⽽⾔是看不到这个 TCB 的，它只能看到整个进程的 PCB。
⽤户线程的整个线程管理和调度，操作系统是不直接参与的，⽽是由⽤户级线程库函数来完成线程的管理，包括线程的创建、终⽌、同步和调度等。

内核线程如何理解？存在什么优势和缺陷？

内核线程是由操作系统管理的，线程对应的 TCB ⾃然是放在操作系统⾥的，这样线程的创建、终⽌和管理都是由操作系统负责。

轻量级线程如何理解？存在什么优势和缺陷？

轻量级进程（Light-weight process， LWP）是内核⽀持的⽤户线程，⼀个进程可有⼀个或多个 LWP，每个 LWP 是跟内核线程⼀对⼀映射的，也就是 LWP 都是由⼀个内核线程⽀持。
另外， LWP 只能由内核管理并像普通进程⼀样被调度， Linux 内核是⽀持 LWP 的典型例⼦。

LWP与普通进程的区别也在于它只有⼀个最⼩的执⾏上下⽂和调度程序所需的统计信息。

调度原则

5种调度原则：

• CPU利用率：调度程序应确保CPU是始终匆忙的状态，这可提高CPU的利用率；
• 系统吞吐量：吞吐量表示的是单位时间内CPU完成进程的数量，长时间的进程会占用较长的CPU资源，因此页降低吞吐量，相反，短作业的进程会提升系统吞吐量；
• 周转时间：周转时间是进程运行和阻塞总和，一个进程的周转时间越小越好；
• 等待时间：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；
• 响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

进程间通信

多线程同步与互斥

由于多线程执⾏操作共享变量的这段代码可能会导致竞争状态，因此我们将此段代码称为临界区（critical section），它是访问共享资源的代码⽚段，⼀定不能给多线程同时执⾏。
们希望这段代码是互斥（mutualexclusion）的，也就说保证⼀个线程在临界区执⾏时，其他线程应该被阻⽌进⼊临界区。

同步，就是并发进程/线程在⼀些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程/线程同步。

锁

锁用户保证决并发线程/进程的互斥问题。

当已经有⼀个线程加锁后，其他线程加锁则就会失败，互斥锁和⾃旋锁对于加锁失败后的处理⽅式是不⼀样的：

• 互斥锁加锁失败后，线程会释放CPU，给其他线程；
• 自旋锁加锁失败后，线程就会忙等待，直到它拿到锁。

互斥锁是⼀种「独占锁」，⽐如当线程 A 加锁成功后，此时互斥锁已经被线程 A 独占了，只要线程 A 没有释放⼿中的锁，线程 B 加锁就会失败，于是就会释放 CPU 让给其他线程， 既然线程 B 释放掉了 CPU，⾃然线程 B 加锁的代码就会被阻塞。

对于互斥锁加锁失败⽽阻塞的现象，是由操作系统内核实现的。当加锁失败时，内核会将线程置为「睡眠」状态，等到锁被释放后，内核会在合适的时机唤醒线程，当这个线程成功获取到锁后，于是就可以继续执⾏。

互斥锁加锁失败时，会从⽤户态陷⼊到内核态，让内核帮我们切换线程，虽然简化了使⽤锁的难度，但是存在⼀定的性能开销成本。会有两次线程上下文切换的成本。

所以，如果你能确定被锁住的代码执⾏时间很短，就不应该⽤互斥锁，⽽应该选⽤⾃旋锁，否则使⽤互斥锁。

公平读写锁⽐较简单的⼀种⽅式是：⽤队列把获取锁的线程排队，不管是写线程还是读线程都按照先进先出的原则加锁即可，这样读线程仍然可以并发，也不会出现「饥饿」的现象。
互斥锁和⾃旋锁都是最基本的锁，读写锁可以根据场景来选择这两种锁其中的⼀个进⾏实现。

死锁

死锁：两个线程都在等待对⽅释放锁，在没有外⼒的作⽤下，这些线程会⼀直相互等待，就没办
法继续运⾏，这种情况就是发⽣了死锁。

死锁的四个条件：

• 互斥条件；
• 持有并保持条件；
• 不可剥夺条件；
• 循环等待条件

避免死锁最常用并且可行的方法：使⽤资源有序分配法，来破环环路等待条件。

利用工具排查死锁问题

如果你想排查你的 Java 程序是否死锁，则可以使⽤ jstack ⼯具，它是 jdk ⾃带的线程堆栈分析⼯具。

五、调度算法

调度程序：选择⼀个进程运⾏这⼀功能是在操作系统中完成的。

调度时机

以下状态的变化会触发操作系统的调度：

• 从就绪态->运行态
• 从运行态->阻塞态
• 从运行态->结束态

如果硬件时钟提供某个频率的周期性中断，那么可以根据如何处理时钟中断，把调度算法分为两类:

• 非抢占式调度算法
• 抢占式调度算法

调度算法

进程调度算法

高响应比优先调度算法

时间片轮转调度算法

⼀般来说，时间片设为 20ms~50ms 通常是⼀个⽐较合理的折中值。

多级反馈队列调度算法

多级反馈队列（Multilevel Feedback Queue）调度算法是「时间⽚轮转算法」和「最⾼优先级算法」的综合和发展。

• 「多级」表示有多个队列，每个队列优先级从⾼到低，同时优先级越⾼时间⽚越短。
• 「反馈」表示如果有新的进程加⼊优先级⾼的队列时，⽴刻停⽌当前正在运⾏的进程，转⽽去运⾏优先级⾼的队列。

页面置换算法

缺页中断（缺页异常）：当 CPU 访问的⻚⾯不在物理内存时，便会产⽣⼀个缺⻚中断，请求操作系统将所缺⻚调⼊到物理内存。

缺页中断与一般中断的主要区别：

• 缺⻚中断在指令执⾏「期间」产⽣和处理中断信号，⽽⼀般中断在⼀条指令执⾏「完成」后检查和处理中断信号。
• 缺⻚中断返回到该指令的开始重新执⾏「该指令」，⽽⼀般中断返回回到该指令的「下⼀个指令」执⾏。

页表项通常有如下图所示的字段：

时钟页面置换算法

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

• 如果它的访问位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；
• 如果访问位是1就清除访问位，并把表针前移一个位置，重复这个过程直到找到一个访问位位为0的页面为止。

磁盘调度算法

扫描算法（电梯算法）

可以解决最短寻道时间优先算法导致的饥饿问题。
磁头在⼀个⽅向上移动，访问所有未完成的请求，直到磁头到达该⽅向上的最后的磁道，才调换⽅向，这就是扫描（Scan）算法。

循环扫描算法

扫描算法使得每个磁道响应的频率存在差异，那么要优化这个问题的话，可以总是按相同的⽅向进⾏扫描，使得每个磁道的响应频率基本⼀致。

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

LOOK与C-LOOK算法

六、文件系统

七、设备管理

八、网络系统

九、Linux命令

后记

持续更新积累。