logo

《操作系统随想录》

作者
Modified on
Reading time
67 分钟阅读:..评论:..

操作系统这门课程，其实只有以下几个部分，内存管理、进程、文件、IO、网络、硬件设备，思维导图如下图所示：

以下所有内容，均来自我当初校招求职时整理的资料，并备注转载链接，如有侵权请联系我处理。

课前复习

常问的操作系统问题，如果都知道，之后的知识选择性看就好了。 一日之计在于晨

什么是操作系统？

从本质上来说其实就是一个程序，只不过拥有很高的权限，类似于计算机的管家； 它主要是用来管理计算机硬件和软件资源，也可以为用户提供一个与系统交互的界面；

内存管理

更进一步的讲解，小林链接

连续与非连续管理

内存管理即是如何管理计算机的内存资源，是以什么形式来管理。 主要分为两类：连续和非连续分配管理。

操作系统有一个**链表，**记录存储的内存分配大小，而后程序释放之后，将对应的内存给放进去

连续分配管理：是指块式管理，内存分为几块固定的大小，一个进程一块，会造成很大的内存浪费； 非连续分配：是指页和段式管理；

  • 页式内存：把内存分为相等且固定的一页一页形式，提高了内存利用率；利用页表实现逻辑地址到物理地址的转换；
  • 段式内存：进程地址空间按照逻辑关系分段：代码段、数据段、堆栈段等，每一段在内存中独立分配；

段页式分配：进程先分段，段内又分页，也就是段与段之间分离，段内的页与页也可以分离； 其实分段式对程序而言，是逻辑上的分段，是为了程序的健壮性和安全； 分页是对实际存储而言，具体将段中的某部分数据存储到哪个位置，就是分页。 拓展阅读：分段与分页的前世今生

分段和分页区别

共同点 ： 分页机制和分段机制都是为了提高内存利用率，较少内存碎片。 页和段都是离散存储的，所以两者都是离散分配内存的方式。但是，每个页和段中的内存是连续的。 区别 ： 页的大小是固定的，由操作系统决定；而段的大小不固定，取决于我们当前运行的程序。 分页仅仅是为了满足操作系统内存管理的需求，而段是逻辑信息的单位，在程序中可以体现为代码段，数据段，能够更好满足用户设计程序的需要。

页框？页表？ 程序运行过程中生成的地址都是虚拟地址（仅在该程序内部即虚拟地址空间有意义），通过内存管理单元MMU将虚拟地址映射为物理地址。 页面大小通常为4K/64K/2M。（不定，根据体系来看） 页框：虚拟地址中称为页，物理地址称为页框；有几个页框就可以实现几个映射关系（毕竟页框是目标）；分页单元认为所有的RAM被分成了固定长度的页框。 页表：是指虚拟页号和实际的物理页框的映射关系。

逻辑地址/虚拟地址？物理地址？

逻辑地址是我们编程时直接打交道的地址，比如一个指针中存储的就是一个逻辑逻辑地址，这是由操作系统所决定的。（兼容远古段式内存的缘故，指的是机器语言指令中，用来指定一个操作数或者是一条指令的地址。） 物理地址是实际的内存地址，CPU在访问物理地址时需要由逻辑地址到物理地址转换。

虚拟地址的好处有很多！ 如果没有虚拟地址空间，程序可以直接访问物理内存，多个进程之间的内存可能会相互践踏（单片机就是直接操作内存地址），这可能就会造成系统崩溃，系统不稳定容易被黑客破坏。 而有了虚拟地址空间，使得各个进程间的内存隔离；还可以虚拟内存技术实现多进程运行；

虚拟内存

虚拟内存是计算机系统内存管理的一种技术，使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上（swap），在需要时进行数据交换。 一方面，是为了将不同进程的内存地址进行隔离； 另一方面，还是在于内存增长的速度没有程序膨胀的速度，程序大到内存无法容纳。 虚拟地址空间其实就是：眼见皆幻影，实触才为真。

程序所见的10G内存，但其实只是操作系统给了它一个错觉，当程序运行需要某一虚拟地址的数据时，击中或缺页中断从而访问实际的物理内存地址，即程序一般并没有全部加载进内存，其实只有一部分。

交换技术 当多个进程竞争内存资源时，会造成内存资源紧张，并且，如果此时没有就绪进程，处理机会空闲，I/0速度比处理机速度慢得多，可能出现全部进程阻塞等待I/O。 交换技术是直接换成一个程序的内存到硬盘；而虚拟内存是置换一部分页；

物理内存与虚拟内存？ 物理内存就是系统硬件提供的内存大小，虚拟内存就是为了满足物理内存的不足而提出的策略，它是利用磁盘空间虚拟出的一块逻辑内存，用作虚拟内存的磁盘空间被称为交换空间（Swap Space）。 作为物理内存的扩展，linux会在物理内存不足时，使用交换分区的虚拟内存，就是内核会将暂时不用的内存块信息写到交换空间，这样以来，物理内存得到了释放，这块内存就可以用于其它目的，当需要用到原始的内容时，这些信息会被重新从交换空间读入物理内存。 linux的内存管理采取的是分页存取机制，为了保证物理内存能得到充分的利用，内核会在适当的时候将物理内存中不经常使用的数据块自动交换到虚拟内存中，而将经常使用的信息保留到物理内存。 因此，合理规划和设计linux内存的使用，是非常重要的.

如何实现虚拟内存？

虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。 1 一定容量的内存和外存：在载入程序的时候，只需要将程序的一部分装入内存，而将其他部分留在外存，然后程序就可以执行了； 2 缺页中断：如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页面或段调入到内存，然后继续执行程序； **3 虚拟地址空间 ：**逻辑地址到物理地址的变换。

基本思想是，每个程序都有自己的地址空间，这个地址空间被划分为多个称为页面(page）的块。每一页都是连续的地址范围。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。 当程序引用到一部分在物理内存中的地址空间时，硬件会立刻执行必要的映射（击中）。当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令（缺页中断，比如malloc mmap等函数）。

CPU寻址与虚拟地址

现代处理器使用的是一种称为虚拟寻址(Virtual Addressing) 的寻址方式。 使用虚拟寻址，CPU需要将虚拟地址翻译成物理地址，这样才能访问到真实的物理内存。这需要借助MMU（内存管理单元，是一个硬件）

MMU内部构造

在上面这个简单的例子中，虚拟地址到物理地址的映射可以总结如下︰虚拟地址被分为虚拟页号(高位部分)和偏移量（低位部分)。如下：

TLB加速页查询机制

上述的页表映射关系简单，但是在32/64位机器上页表太大，代价高昂，每次上下文切换都必须重载整个页表。 添加硬件TLB快表（转换检测缓冲区，Translation Lookaside Buffer），或称相联存储区（associate memory），是一个单独的缓存。

该硬件可以直接将虚拟地址映射到物理地址，而不用访问页表。它其实存储了一部分转换关系。 ---->每次先查询TLB中是否存在该页，如果有则直接读取TLB（查询保护位权限）而不用访问页表；如果没有则从TLB中删除一个，再从内存中加载新页。 快表（TLB）解决：转换的快慢；类似于缓存，也是基于局部性原理；快表放在只需要一次内存访问，而页表转换需要两次内存访问！

分段下的虚拟地址

分段下的虚拟地址=段选择子+段内偏移量：

举个例子：
有两个缺点： 第一个就是内存碎片的问题。——外部是由于两个进程间的内存不够装入另外的进程；内部是由于有些内存不常用； 第二个就是内存交换的效率低的问题。——直接交换整个进程的空间，IO时间太长；

分页下的虚拟地址

在分页机制下，虚拟地址分为两部分，页号和页内偏移。页号作为页表的索引，页表包含物理页每页所在物理内存的基地址，这个基地址与页内偏移的组合就形成了物理内存地址，见下图。

多级页表的概念

链接

当虚拟空间太大时，管理页表造成巨大的性能损耗。如何解决呢？ 多级表解决：内存太大管理损耗较大；类似于，书/目录/章节/页 避免把所有的页表都放在内存中，不需要的页表就不保留。（局部性原理）

以下面这个二级页表为例：

偏移为12，故一个页面为4K，一共有2^20次方页面，也就是4G内存。 上一级页表中存储的是指向下一级列表的指针，以此类推。

每一个进程都有一个页表，当进程被加载时，页表（第一级页表）被加载进一个PTBR（Page Table Base Rigster）寄存器（不然访问第一级页表都要虚拟地址转换，你咋转？），而后通过二级表（如果有）来寻找最终的物理地址。

多级页表为什么可以节约内存 **第一，二级页表某些可以不存在，**因为有的程序一级页表其中的某些页表项不需要，可以省略空间； **第二，二级页表某些可以在硬盘中，**就好像是请求分页内存一样，用到了再加载进来；

页面置换算法？

最优页面置换算法：（OPT） 描述简单：选择一个最近不会使用的页面置换； 难以实现：操作系统无法得知一个页面下一次将在什么时候被访问。

先进先出置换算法（FIFO）： 第二次机会置换算法： 对FIFO的改进，在出链的时候做一个check：R位为0则退出，为1则置为0并重新将其入链；（涉及内存是否被修改）

最进未使用算法（LRU，Least、Recently Used）：自访问以来间隔时间最长的；重在时间； 代码：https://www.cnblogs.com/cpselvis/p/6272096.html 最少使用页面置换（Least Frequently Used）：访问就放头，所以尾就是最少使用的；重在频率； 代码：https://leetcode-cn.com/problems/lfu-cache/solution/lfuhuan-cun-by-leetcode-solution/

什么是颠簸现象

颠簸本质上是指频繁的页调度行为。 进程发生缺页中断时必须置换某一页。然而，其他所有的页都在使用，**它置换一个页，但又立刻再次需要这个页。**因此会不断产生缺页中断，导致整个系统的效率急剧下降，这种现象称为颠簸。

内存颠簸的解决策略包括：

  • 修改页面置换算法；
  • 降低同时运行的程序的数量；
  • 终止该进程或增加物理内存容量。

程序内存结构

进程加载过程

覆盖装入（Overlay）和页映射（Paging）是两种典型的动态装载方法。现在前者已经不用了。
创建一个进程，然后装载相应的可执行文件并且执行。上述过程最开始只需要做三件事情: ①创建一个独立的虚拟地址空间。主要是分配一个页目录（Page Directory）。 ②读取可执行文件的头，并且建立虚拟空间和可执行文件的映射关系。主要是把可执行文件映射到虚拟地址空间，即做虚拟页和物理页的映射，以便“缺页”时载入。 ③将CPU的指令寄存器设置成可执行文件的入口地址，启动运行。从ELF文件中的入口地址开始执行程序。页表用于虚拟内存到物理内存的映射； 段表用户访问权限控制，CPU平坦模式下，段就形同虚设了哈。

进程与线程

进程、线程与协程的区别

有人给出了很好的归纳： ** 对操作系统来说，线程是最小的执行单元，进程是最小的资源管理单元**。 1.进程是资源分配和系统调度的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。（进程是对运行时程序的封装，是系统进行资源调度和分配的基本单位）线程是进程执行（CPU调度）的最小单位。 2.线程依赖进程存在，一个进程至少有一个线程。 3.由于创建或撤销进程时，系统都要为之分配或回收资源，所付出的开销远大于创建或撤销线程时的开销，而线程切换时只需保存和设置少量寄存器内容，开销很小。 4.线程间通信十分便利，但是进程通信需要各种IPC。（进程间通信方式）

ps：更详细的区别

进程构成与创建

进程=程序、数据（内存映像）+进程控制块（PCB）； 进程控制块：大致包含四个部分，进程标识符（内部标识的ID号、外部供用户标识的父进程子进程）、处理机状态（各种寄存器的状态，比如通用寄存器、指令计数器用户栈等）、进程调度信息（进程状态、优先级、等待事件等）、进程控制信息（程序和数据地址、资源清单、链接下一PCB的指针）

进程创建过程 fork与exec

主要步骤分为4步： 1．申请空白PCB（过程控制块）。 2．为新工序分配资源。 3．初始化PCB。 4、将新进程插入就绪队列。

因为创建进程的时候未必会创建程序段和数据段，但一定会创建PCB，这取决于具体实现。如果只谈fork/exec，那么「创建进程」这一步是在fork()中完成的。 一个平凡的fork()实现会在「创建PCB」的同时创建一个新的地址空间——它包含了空的「数据段」和「程序段」，然后在exec()中填充「程序段」。 但如果你实现了「Copy-On-Write」，那么在fork()的时候只会创建新的PCB而不会创建新的地址空间，这一过程被延后到了exec()中，新进程在exec()之前和父进程共用相同的「程序段」和「数据段」。

fork 调用fork可以创建一个新的进程称为子进程, 调用fork函数的进程称为父进程, 子进程的所有内容都和父进程相同, 除了pcd(进程控制模块), 如果这两个进程都没有对内存做写操作的话, 那么两个进程共享调用fork函数的进程的内存页, 这样表面上看fork创建进程比exec创建进程快. 但只要两个进程其中一个对内存做了修改, 那么在修改之前, 就会把内存页复制一份给子进程用. 1.fork执行的时候,会有两个返回值,一个是父进程的返回值,一个是子进程的返回值。 2.在父进程中fork的返回值是子进程的PID。 3.在子进程中fork的返回值是0。 4**.fork失败,返回值为-1** exec() **相当于进行一次系统调用，**则用另一个（不相同的）进程映像替换当前进程映像，当前进程的“数据段”，“堆栈段”和“代码段”被新程序改写。 **fork()创建一个新的进程就产生了一个新的PID，因此子进程拥有自己的进程ID。**exec启动一个新程序，替换原有的进程，因此新程序会保持调用exec()进程的ID不变，即这个新的被exec执行的进程的PID不会改变，和调用exec函数的进程一样。

//创建子进程并调用函数execl
if( fork() == 0 )
{
// in clild
printf( “1------------execl------------\n” );
if( execl( “/bin/ls”, “ls”,"-a", NULL ) == -1 )
{
perror( "execl error " );
exit(1);
}
}

进程栈的自动增长？

https://zhuanlan.zhihu.com/p/137080378

a)linux内核支持栈的自动增长，这个自动增长是在8M这最大值下的（可配置）的自动增长，不是无限增长。 b)当超过最大值时出现栈空间溢出, 用户态出现的错误是段错误问题，因为此时返回的地址是一个不存的没有映射过的地址。读写都会出现异常。 c)运行过程栈的自动增长**都发生在写这个时候，同时遵循写时复制的原则。**先扩展线性地址空间，然后申请内存。 d)内核支持向下增长和向下增长两种试的栈，从_do_page_fault中实现可以看到只有向下增长的栈才支持自动增长栈空间。 e)对于向下增长这种方式，内核在内核除了将vma->vm_start不断调小，同时还需要更新到rsp寄存器。因为栈空间变大了，rsp的值反而变下了， 也就是开始地址反而变小， 所以称为向下增长。 f)栈空间内存本身是mmap内存本身在本质上没有区别，都是一段特理内存，有自己的vma, 写时申请真正的物理内存。区别栈空间的线性地址内核自动维护。

什么是协程

协程，又称微线程。 其实是在线程内实现的一种调度算法，类似于Go的GMP的概念。

https://blog.csdn.net/zheng199172/article/details/88800275

先说说进程和线程的痛点,线程之间是如何进行协作的呢？ 例如生产者和消费者模型,涉及到同步锁,线程阻塞和可运行态的切换,线程上下文的切换,这些都会造成性能损耗. 最重要的是，协程不是被操作系统内核所管理，而完全是由程序所控制（也就是在用户态执行）。 这样带来的好处就是性能得到了很大的提升，不会像线程切换那样消耗资源。

举例：

代码中创建了一个叫做consumer的协程，并且在主线程中生产数据，协程中消费数据。 其中 yield 是python当中的语法。当协程执行到yield关键字时，会暂停在那一行，等到主线程调用send方法发送了数据，协程才会接到数据继续执行。 但是，yield让协程暂停，和线程的阻塞是有本质区别的。协程的暂停完全由程序控制，线程的阻塞状态是由操作系统内核来进行切换。 因此，协程的开销远远小于线程的开销。

有哪些编程语言应用到了协程呢？我们举几个栗子： Lua语言、Python语言、Go语言、Java语言

总而言之： 进程：拥有自己独立的堆和栈，既不共享堆也不共享栈，进程由操作系统调度。 线程: 线程拥有自己独立的栈和共享的堆，共享堆，不共享栈，线程亦由操作系统调度(标准线程是的)。 协程：协程和线程一样共享堆，不共享栈，协程相应框架的协程调度器来负责调度。

超线程是什么？

IntelX86CPU上有超线程这个技术（SMT），对于单一处理器核心来说来说，虽然也可以每秒钟处理成千上万条指令，但是在某一时刻，只能够对一条指令(单个线程)进行处理，超线程技术能够把一个物理处理器在软件层变成两个逻辑处理器，可以使处理器在某一时刻，同步并行处理更多指令和数据(多个线程)，当然了实际效能不可实现双倍提升，毕竟干活的核心只有一个。

超线程的存在可以使系统、程序充分利用单个核心内实际未被使用的资源；如果两个线程对资源的需求量大于单个核心的供给量，此时必然会出现资源争夺的问题，反而会导致效率的下降。 常规的CPU想要执行多线程的时候，CPU要在线程之间不断地调度，在开启了超线程之后，CPU可以更充分地利用好自身的资源（CPU某些硬件有多个备份，比如程序计数器和寄存器文件）。例如当开启了超线程之后，可以在一个线程执行整数指令集的时候，而恰好在这个时候，另一个线程执行浮点指令集，而这两个指令集整数指令单元和浮点指令单元来执行。再比如一个线程必须要等到某些数据被加载到高速缓存中，那CPU就可以继续去执行另一个线程。 总之，超线程技术是CPU在处理一个任务的时候，并不能占满CPU的所有处理能力，这时候把剩余能力集合起来，虚拟出另一个核心。

超线程实际上就是在一个核里塞一倍的alu，两倍的寄存器，因为intel发现任务总是alu富余，寄存器不够用，这样就能把富余的alu给另一个线程用（intel的这个发现是对的，但富余的alu并不够另一个线程用的，于是两个线程就打架）

进程与线程调度

（1）R运行状态（runing）：并不意味着进程一定在运行中，也可以在运行队列里； （2）S睡眠状态（sleeping）：进程在等待事件完成；（浅度睡眠，可以被唤醒） （3）D磁盘睡眠状态（Disk sleep）:不可中断睡眠（深度睡眠，不可以被唤醒，通常在磁盘写入时发生） （4）T停止状态（stopped）：可以通过发送SIGSTOP信号给进程来停止进程，可以发送SIGCONT信号让进程继续运行 （5）X死亡状态（dead）:该状态是返回状态，在任务列表中看不到； （6）Z僵尸状态（zombie）:子进程退出，父进程还在运行，但是父进程没有读到子进程的退出状态，子进程进入僵尸状态； （7）t追踪停止状态（trancing stop）

僵尸/孤儿进程/init进程？

孤儿进程：父进程退出而子进程仍在运行，这些孤儿进程将会被init进程（id号为1）收养，并对其完成状态进行收集； 僵尸进程：fork 创建子进程，如果子进程退出，而父进程并没有调用 wait 或 waitpid 获取子进程的状态信息，那么子进程的进程控制块仍然保存在系统中的这些进程是僵尸进程。

这些PCB会驻留内存，浪费系统资源。

如何避免僵尸进程呢？ 父进程wait或waitpid； 信号SIGCHLD通知信号处理函数来wait； 让父进程先死，由init接手；

  • 当子进程结束运行时，子进程的退出状态（返回值）会回报给操作系统，系统则以**SIGCHLD信号将子进程被结束的事件告知父进程，**此时子进程的进程控制块（PCB）仍驻留在内存中。

init进程，它是内核启动的第一个用户级进程。init有许多很重要的任务，比如像启动getty（用于用户登录）、实现运行级别、以及处理孤立进程。

锁

死锁的产生与预防

死锁是如何产生的？ 死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。

我们举个例子，如果此时有一个线程A，按照先锁a再获得锁b的的顺序获得锁，而在此同时又有另外一个线程B，按照先锁b再锁a的顺序获得锁。 如下图所示：

概念： 多个并发进程因争夺系统资源而产生相互等待的现象。 原理： 当一组进程中的每个进程都在等待某个事件发生，而只有这组进程中的其他进程才能触发该事件，这就称这组进程发生了死锁。 本质原因： 1）、系统资源有限。 2）、进程推进顺序不合理。

产生死锁的必要条件：

  • **互斥条件：**进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。
  • **占有保持条件：**当进程因请求资源而阻塞时，对已获得的资源保持不放。
  • **不可抢占条件：**进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。
  • **循环等待条件：**在发生死锁时，必然存在一个进程--资源的环形链，使得每个进程都占有下一个进程所需的至少一种资源。

如何避免产生死锁？ **1 死锁预防 **确保系统始终无法进入死锁状态，即打破上面的四个条件（由于互斥条件一般不能打破，只只针对其他三种情况进行）

  • 只要有一个资源得不到分配，也不给这个进程分配其他的资源：（破坏占有保持条件）
  • 可剥夺资源：即当某进程获得了部分资源，但得不到其它资源，则释放已占有的资源（破坏不可剥夺条件）
  • 资源有序分配法： 可以通过定义资源类型的线性顺序来预防，可将每个资源编号，当一个进程占有编号为i的资源时，那么它下一次申请资源只能申请编号大于i的资源。（破坏环路等待条件）

2 避免死锁 在使用前判断，只给不会产生死锁的进程申请资源 如果一个进程的请求会导致死锁，则拒绝该请求 避免死锁的具体实现通常利用银行家算法  

什么是银行家算法？

是用来避免死锁的一种经典算法：将操作系统拟作银行家、管理的系统资源拟作银行资金、申请资源的进程拟作贷款者。该算法允许进程动态申请资源。详见：链接 在银行家算法中，有四个数据结构：

  1. 可利用资源向量Available，含有m个元素，表示m类资源的可利用情况；
  2. 最大需求矩阵Matrix，为n*m，表示n个进程对m类资源分别的最大需求量；
  3. 分配矩阵Allocated，为n*m，表示当前n个进程对m类资源已占用的情况；
  4. 需求矩阵Need，为n*m，表示当前n个进程对m类资源还需要的值；

这三个矩阵有如下关系：

Need[i,j] = Max[i,j] - allocation[i, j]

3 死锁检测与接触 在检测到运行系统进入死锁，进行恢复 利用上述矩阵来判断死锁出现了链接，那么如何打开死锁？ 1、**抢占资源：**从一个或多个进程中抢占足够数量的资源分配给死锁进程，以解除死锁状态。 2、**终止（或撤销）进程：**终止或撤销系统中的一个或多个死锁进程，直至打破死锁状态。

抢占与非抢占式调度

非抢占式是指各进程获取CPU使用权之后自行（运行完毕）或运行错误释放使用权而后操作系统调度其他进程； 而抢占是指，即便当前CPU被使用，新进程强制获取CPU使用权； 调度算法考量：抢占式、非抢占式；不同的应用环境：批处理（大批量入库信息）、交互式（服务器）、实时（只运行用来推进现有应用的程序）；各部件忙碌（CPU密集型和IO密集相结合）。

进程调度即从就绪队列中选取一个进程分配给处理机。 1.需要进行进程调度和切换的情况

  • 主动放弃

进程正常终止 运行过程中发生异常 进程主动请求阻塞（IO）

  • 被动放弃

时间片用完 更加紧急的事情需要处理 有优先级更高的进程进入就绪队列 2.不能进行进程调度和切换的情况 处理中断的过程中 进程在操作系统内核程序临界区 原子操作过程中

经典调度算法

这些调度算法的实现 批处理系统： 先来先服务 first-come first-serverd（FCFS） 按照请求的顺序进行调度。非抢占式，开销小，无饥饿问题，响应时间不确定（可能很慢）； 对短进程不利，对IO密集型进程不利。

最短作业优先 shortest job first（SJF） 按估计运行时间最短的顺序进行调度。非抢占式，吞吐量高，开销可能较大，可能导致饥饿问题； 对短进程提供好的响应时间，对长进程不利。

最短剩余时间优先 shortest remaining time next（SRTN） 按剩余运行时间的顺序进行调度。(最短作业优先的抢占式版本)。吞吐量高，开销可能较大，提供好的响应时间；可能导致饥饿问题，对长进程不利。

交互式系统： 交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。 时间片轮转 Round Robin 将所有就绪进程按 FCFS 的原则排成一个队列，用完时间片的进程排到队列最后。抢占式（时间片用完时），开销小，无饥饿问题，为短进程提供好的响应时间； 若时间片小，进程切换频繁，吞吐量低；若时间片太长，实时性得不到保证。

多级反馈队列调度算法 Multilevel Feedback Queue（MLFQ）

设置多个就绪队列1、2、3...，优先级递减，时间片递增。只有等到优先级更高的队列为空时才会调度当前队列中的进程。如果进程用完了当前队列的时间片还未执行完，则会被移到下一队列。

抢占式（时间片用完时），开销可能较大，对IO型进程有利，可能会出现饥饿问题。

优先级反转

高优先级的进程等待被一个低优先级进程占用的资源时，就会出现优先级反转，即优先级较低的进程比优先级较高的进程先执行。 解决方法：（主要是想办法让低优先级的进程尽快运行完）

  • 优先级天花板(priority ceiling)：当任务申请某资源时，把该任务的优先级提升到可访问这个资源的所有任务中的最高优先级，这个优先级称为该资源的优先级天花板。简单易行。
  • 优先级继承(priority inheritance)：当任务A申请共享资源S时，如果S正在被任务C使用，通过比较任务C与自身的优先级，如发现任务C的优先级小于自身的优先级，则将任务C的优先级提升到自身的优先级，任务C释放资源S后，再恢复任务C的原优先级。

优先级调度算法：每个进程都有优先级，首先执行优先级高的进程。相同优先级的的进程以FCFS调度。 **多级反馈队列：**多级优先级队列，优先级越高，时间片越少；同级采用先来先服务；完成不了就降级；最后一级时间片轮转；（重点）

PS：在所有的进程都可以运行的情况下，那么最短作业优先才是最优的；

线程切换和进程切换区别

进程切换有两步：切换页表以使用新的地址空间，切换内核栈和硬件上下文； 线程只有第二步，即上下文，切换栈；

性能损耗到底在哪？ 切换上下文需要将寄存器中内容换置；进程切换还会扰乱处理器缓存。

进程间通信

强力推荐：小林coding

有名管道FIFO：多个进程间 无名管道Pipe：亲属进程间，PIPE无名--文件索引，半双工，双方通信需要两个管道 管道通信方式效率较低，不适合频繁通信。

信号量、信号量是一个特殊的变量，它的本质是计数器，信号量里面记录了临界资源的数目，有多少数目，信号量的值就为多少，进程对其访问都是原子操作**（pv操作，p：占用资源，v：释放资源）**。它的作用就是，调协进程对共享资源的访问，让一个临界区同一时间只有一个进程在访问它。 信号、 共享内存（结合信号）、 消息队列、 套接字Socket（不同主机之间）。

哪种最快？废话，当然是共享内存啊！但是得注意互斥！

管道

对于匿名管道，它的通信范围是存在父子关系的进程。因为管道没有实体，也就是没有管道文件，只能通过 fork 来复制父进程 fd 文件描述符，来达到通信的目的。 对于命名管道，它可以在不相关的进程间也能相互通信。因为命令管道，提前创建了一个类型为管道的设备文件（FIFO不同与管道之处以FIFO的文件形式存储在文件系统中。有名管道是一个设备文件），在进程里只要使用这个设备文件，就可以相互通信。 https://www.cnblogs.com/zhaozhaodeboke/p/6678326.html https://blog.csdn.net/qianyayun19921028/article/details/81395564 https://blog.csdn.net/xunye_dream/article/details/109412580

在内存中开辟一块缓冲区，进程1把数据从用户空间拷到内核缓冲区，进程2再从内核缓冲区把数据读走。管道其实是内存中的一块缓存区，一般大小是一页（4096B），循环队列，所以一直往里写的话会出现数据覆盖。

如果是有名管道FIFO，可以这样用:

mkfifo myPipe
echo "hello" > myPipe  // 将数据写进管道
                         // 停住了 ...
cat < myPipe  // 读取管道里的数据
hello

管道这种通信方式效率低，不适合进程间频繁地交换数据。当然，它的好处，自然就是简单，同时也我们很容易得知管道里的数据已经被另一个进程读取了。 linux下管道由pipe系统调用函数创建，提供一个单向数据流。管道创建后，fildes[0]打开来读，fildes[1]打开来写。

一般来说，创建管道之后，读端和写端线程都具备，但是父子进程会各自关闭一个控制端，如果不关闭可以实现两个进程间的双向通信，但是！要特别注意会不会出现自己写的数据被自己给拿走的情况，因此可以考虑信号量或者信号！

注意，在shell里，A|B中a和b都是shell的子进程：

最好的方式还是开辟两个管道来实现双向通信。通过管道通信的两个进程，一个进程向管道写数据，另外一个从中读数据。写入的数据每次都添加到管道缓冲区的末尾，读数据的时候都是从缓冲区的头部读出数据的。

通常读取数据的程序并不知道有多少数据需要读取，所以常采用循环的方法读取数据，当没有数据可以读取时，read调用通常会阻塞，即他将暂停进程来等待直到有数据到达为止。 管道用于在两个进程之间进行单向通信，但是不只限于父子间进程，我们使用exec函数替换子进程，实现任意进程之间的管道通信。

消息队列 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。（先进先出） 最简单的消息队列的使用流程 ①ftok函数生成键值 ②msgget函数创建消息队列 ③msgsnd函数往消息队列发送消息 ④msgrcv函数从消息队列读取消息 ⑤msgctl函数进行删除消息队列

原文参考：链接

A 进程要给 B 进程发送消息，A 进程把数据放在对应的消息队列后就可以正常返回了，B 进程需要的时候再去读取数据就可以了。同理，B 进程要给 A 进程发送消息也是如此。 但邮件的通信方式存在不足的地方有两点，一是通信不及时，二是附件也有大小限制，这同样也是消息队列通信不足的点。 消息队列不适合比较大数据的传输，因为在内核中每个消息体都有一个最大长度的限制，同时所有队列所包含的全部消息体的总长度也是有上限。在 Linux 内核中，会有两个宏定义 MSGMAX 和 MSGMNB，它们以字节为单位，分别定义了一条消息的最大长度和一个队列的最大长度。 消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销，因为进程写入数据到内核中的消息队列时，会发生从用户态拷贝数据到内核态的过程，同理另一进程读取内核中的消息数据时，会发生从内核态拷贝数据到用户态的过程。

共享内存

共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。这样这个进程写入的东西，另外一个进程马上就能看到了，都不需要拷贝来拷贝去，传来传去，大大提高了进程间通信的速度。

具体的例子：链接 https://www.cnblogs.com/wuyepeng/p/9748889.html

信号量

用了共享内存通信方式，带来新的问题，那就是如果多个进程同时修改同一个共享内存，很有可能就冲突了。例如两个进程都同时写一个地址，那先写的那个进程会发现内容被别人覆盖了。为了防止多进程竞争共享资源，而造成的数据错乱，所以需要保护机制，使得共享的资源，在任意时刻只能被一个进程访问。 正好，信号量就实现了这一保护机制。信号量其实是一个整型的计数器，主要用于实现进程间的互斥与同步，而不是用于缓存进程间通信的数据。 信号量表示资源的数量，控制信号量的方式有两种原子操作：

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

信号

上面说的进程间通信，都是常规状态下的工作模式。对于异常情况下的工作模式，就需要用「信号」的方式来通知进程。 信号跟信号量虽然名字相似度 66.66%，但两者用途完全不一样，就好像 Java 和 JavaScript 的区别。 在 Linux 操作系统中， 为了响应各种各样的事件，提供了几十种信号，分别代表不同的意义。我们可以通过 kill -l 命令，查看所有的信号：

kill -l
 1) SIGHUP       2) SIGINT       3) SIGQUIT      4) SIGILL       5) SIGTRAP
 6) SIGABRT      7) SIGBUS       8) SIGFPE       9) SIGKILL     10) SIGUSR1
11) SIGSEGV     12) SIGUSR2     13) SIGPIPE     14) SIGALRM     15) SIGTERM
16) SIGSTKFLT   17) SIGCHLD     18) SIGCONT     19) SIGSTOP     20) SIGTSTP
21) SIGTTIN     22) SIGTTOU     23) SIGURG      24) SIGXCPU     25) SIGXFSZ
26) SIGVTALRM   27) SIGPROF     28) SIGWINCH    29) SIGIO       30) SIGPWR
31) SIGSYS      34) SIGRTMIN    35) SIGRTMIN+1  36) SIGRTMIN+2  37) SIGRTMIN+3
38) SIGRTMIN+4  39) SIGRTMIN+5  40) SIGRTMIN+6  41) SIGRTMIN+7  42) SIGRTMIN+8
43) SIGRTMIN+9  44) SIGRTMIN+10 45) SIGRTMIN+11 46) SIGRTMIN+12 47) SIGRTMIN+13
48) SIGRTMIN+14 49) SIGRTMIN+15 50) SIGRTMAX-14 51) SIGRTMAX-13 52) SIGRTMAX-12
53) SIGRTMAX-11 54) SIGRTMAX-10 55) SIGRTMAX-9  56) SIGRTMAX-8  57) SIGRTMAX-7
58) SIGRTMAX-6  59) SIGRTMAX-5  60) SIGRTMAX-4  61) SIGRTMAX-3  62) SIGRTMAX-2
63) SIGRTMAX-1  64) SIGRTMAX

Ctrl+C 产生 SIGINT 信号，表示终止该进程； Ctrl+Z 产生 SIGTSTP 信号，表示停止该进程，但还未结束，后台运行；

信号是进程间通信机制中唯一的异步通信机制，因为可以在任何时候发送信号给某一进程，一旦有信号产生，我们就有下面这几种，用户进程对信号的处理方式。 1.执行默认操作。Linux 对每种信号都规定了默认操作，例如，上面列表中的 SIGTERM 信号，就是终止进程的意思。Core 的意思是 Core Dump，也即终止进程后，通过 Core Dump 将当前进程的运行状态保存在文件里面，方便程序员事后进行分析问题在哪里。 2.捕捉信号。我们可以为信号定义一个信号处理函数。当信号发生时，我们就执行相应的信号处理函数。 3.忽略信号。当我们不希望处理某些信号的时候，就可以忽略该信号，不做任何处理。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP，它们用于在任何时候中断或结束某一进程。

线程间通信

  1. 互斥量(Mutex)：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。
  2. 信号量(Semphares) ：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量
  3. 事件(Event) :**Wait/Notify：**通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操。（或者叫做条件变量）

文件系统/IO

强烈推荐小林coding，可以先看看手写操作系统的文件系统那一章

零拷贝技术？Mmap？

传统的IO模式，主要包括 read 和 write 过程： read：把数据从磁盘读取到内核缓冲区，再拷贝到用户缓冲区 write：先把数据写入到 socket缓冲区，最后写入网卡设备 流程图如下：

（1）用户空间的应用程序通过read()函数，向操作系统发起IO调用，上下文从用户态到切换到内核态，然后再通过 DMA 控制器将数据从磁盘文件中读取到内核缓冲区 （2）接着CPU将内核空间缓冲区的数据拷贝到用户空间的数据缓冲区，然后read系统调用返回，而系统调用的返回又会导致上下文从内核态切换到用户态 （3）用户空间的应用程序通过write()函数向操作系统发起IO调用，上下文再次从用户态切换到内核态；接着CPU将数据从用户缓冲区复制到内核空间的 socket 缓冲区（也是内核缓冲区，只不过是给socket使用），然后write系统调用返回，再次触发上下文切换 （4）最后异步传输socket缓冲区的数据到网卡，也就是说write系统调用的返回并不保证数据被传输到网卡 在传统的数据 IO 模式中，读取一个磁盘文件，并发送到远程端的服务，就共有四次用户空间与内核空间的上下文切换，四次数据复制，包括两次 CPU 数据复制，两次 DMA 数据复制。但两次 CPU 数据复制才是最消耗资源和时间的，**这个过程还需要内核态和用户态之间的来回切换，**而CPU资源十分宝贵，要拷贝大量的数据，还要处理大量的任务，如果能把 CPU 的这两次拷贝给去除掉，既能节省CPU资源，还可以避免内核态和用户态之间的切换。而零拷贝技术就是为了解决这个问题。

如何解决？mmap和Sendfile！

https://blog.csdn.net/a745233700/article/details/122660332

Mmap+write **在传统 IO 模式的4次内存拷贝中，与物理设备相关的2次拷贝（把磁盘数据拷贝到内存 以及 把数据从内存拷贝到网卡）是必不可少的。**但与用户缓冲区相关的2次拷贝都不是必需的，如果内核在读取文件后，直接把内核缓冲区中的内容拷贝到 Socket 缓冲区，待到网卡发送完毕后，再通知进程，这样就可以减少一次 CPU 数据拷贝了。而 内存映射mmap 就是通过前面介绍的方式实现零拷贝的，**它的核心就是操作系统把内核缓冲区与应用程序共享（而一般情况下两者时隔离的），将一段用户空间内存映射到内核空间，当映射成功后，用户对这段内存区域的修改可以直接反映到内核空间；同样地，内核空间对这段区域的修改也直接反映用户空间。**正因为有这样的映射关系, 就不需要在用户态与内核态之间拷贝数据， 提高了数据传输的效率，这就是内存直接映射技术。

1）用户应用程序通过 mmap() 向操作系统发起 IO调用，上下文从用户态切换到内核态；然后通过 DMA 将数据从磁盘中复制到内核空间缓冲区 （2）mmap 系统调用返回，上下文从内核态切换回用户态（这里不需要将数据从内核空间复制到用户空间，因为用户空间和内核空间共享了这个缓冲区） （3）用户应用程序通过 write() 向操作系统发起 IO调用，上下文再次从用户态切换到内核态。接着 CPU 将数据从内核空间缓冲区复制到内核空间 socket 缓冲区；write 系统调用返回，导致内核空间到用户空间的上下文切换 （4）DMA 异步将 socket 缓冲区中的数据拷贝到网卡 mmap 的零拷贝 I/O 进行了4次用户空间与内核空间的上下文切换，以及3次数据拷贝；其中3次数据拷贝中包括了2次 DMA 拷贝和1次 CPU 拷贝。所以 mmap 通过内存地址映射的方式，节省了数据IO过程中的一次CPU数据拷贝以及一半的内存空间

Sendfile 只要我们的代码执行 read 或者 write 这样的系统调用，一定会发生 2 次上下文切换：首先从用户态切换到内核态，当内核执行完任务后，再切换回用户态交由进程代码执行。因此，如果想减少上下文切换次数，就一定要减少系统调用的次数，解决方案就是把 read、write 两次系统调用合并成一次，在内核中完成磁盘与网卡的数据交换。在 Linux 2.1 版本内核开始引入的 sendfile 就是通过这种方式来实现零拷贝的，具体流程图如下：

（1）用户应用程序发出 sendfile 系统调用，上下文从用户态切换到内核态；然后通过 DMA 控制器将数据从磁盘中复制到内核缓冲区中 （2）然后CPU将数据从内核空间缓冲区复制到 socket 缓冲区 （3）sendfile 系统调用返回，上下文从内核态切换到用户态 （4）DMA 异步将内核空间 socket 缓冲区中的数据传递到网卡 通过 sendfile 实现的零拷贝I/O使用了2次用户空间与内核空间的上下文切换，以及3次数据的拷贝。其中3次数据拷贝中包括了2次DMA拷贝和1次CPU拷贝。

有哪些磁盘调度算法？

FCFS先来先服务、最短寻道时间（SSTF）、扫描算法SCAN、循环扫描算法CSCAN。 第一个不说； 第二个选择进程请求磁道和当前磁道的距离，可能出现饥饿； 第三个是类似于电梯运行，综合远近和运行方向； 第四个，将最高和最低磁道“连”在一起，构成循环； 想不起就看：https://blog.csdn.net/qq_27607965/article/details/82355797

文件的索引分配

常见的文件分配方式有连续分配、链式分配和索引分配，连续分配无法改变文件的大小且易产生外部碎片，链式分配解决了以上的问题但是无法实现文件的随机访问、查找效率低。为此，便提出了一种更为高级的文件分配方式——索引分配。 1.直接索引： 直接索引不使用FAT文件分配表，而是在文件控制块（FCB）中设置一个区域，成为索引块或索引表（存储在磁盘上），每个文件都有一个FCB（Linux系统中使用inode索引节点），因此每个文件都有其对应的索引表。目录条目包括索引表的地址，索引表中不存储任何文件信息，而是存储一个个索引表项，每个索引表项都有一个指向分配给该文件某个磁盘块的指针，要读取文件的第i块数据，通过索引表的第i个表项中的指针来定位所需的块在磁盘中的位置。

从上图可以读出，文件1.txt在磁盘中的块分别为4、7、9、0、5 简单来说就是文件从该表就知道，自己被分配了哪些的磁盘区域。跟内存分页一样，索引表太大就浪费空间，太小，又无法支持大文件。于是······ 2.链接索引 在链接索引中，采取了链式分配相同的思想，由于索引表也是存储在磁盘上的，并且通常占用一个磁盘块的大小，因此可以将多个索引表用指针连接起来，以此来支持大文件的存取。（这个不像多级页表，单纯就是索引表指索引表，不存在上下级） 3.混合索引 混合索引指将多种分配方式与索引分配相结合的分配方式。如既采用连续分配的方式，又采用索引分配的方式，即一个文件前面的数据块采用连续分配，后面的数据块采用索引分配。 4.多层索引 类似于多级页表，但是命名方式却是反着来的。这里的一级索引（也叫直接块）指向若干个物理块，二级索引扩展到若干个一级索引，以此类推。
计算题参考链接： https://blog.csdn.net/weixin_42708321/article/details/109167349

GPT和MBR磁盘分区？

GUID分区表(简称GPT**。使用GUID分区表的磁盘称为GPT磁盘**)； 普遍使用的主引导记录(MBR)分区方案相比，GPT提供了更加灵活的磁盘分区机制。 1、MBR分区表最多只能识别2TB左右的空间；GPT分区表则能够识别2TB以上的硬盘空间。 2、MBR分区表最多只能支持4个主分区或三个主分区+1个扩展分区(逻辑分区不限制)；GPT分区表在Windows系统下可以支持128个主分区。 3、在MBR中，分区表的大小是固定的；在GPT分区表头中可自定义分区数量的最大值，也就是说GPT分区表的大小不是固定的。

面试题

CPU内部结构

（8086）微处理器一般分成总线接口单元BIU和执行单元EU。 EU执行单元

EU控制电路是什么？ 根据指令进行译码，并对电路加上对应的电压，从而产生确定的结果

BIU总线接口单元 总线接口单元BIU由1个20位地址加法器、4个16位段寄存器、1个16位指令指针IP、指令队列缓冲器和总线控制逻辑电路等组成（8086）。

指令队列缓存，就相当于后面CPU缓存中的L1 指令缓存

CPU的执行级别

x86特权级别（运行级别），**即操作系统和CPU一起合作来限制用户模式程序所能做的事情，**不同的特权级别下，CPU所能使用的寄存器、所能进行的指令是不一样的。

一般CPU有4个特权级别，编号为0(特权最大)到3(特权最小)，以及**3个受保护的主要资源：内存、I/O端口和执行某些机器指令的能力。Linux只取了ring0和ring3，分为内核态和用户态； **

什么是系统调用？

操作系统把进程分为两个级别：内核级别跟用户级别； 内核态几乎访问计算机任何资源，具有最高权限； 用户态的进程只可以访问对应程序的资源； 系统调用是指从应用程序从用户态到内核态的转变过程。

当应用程序需要调用系统有关资源的时候，就需要进行系统调用，向操作系统提出服务请求，并由操作系统代为完成，从用户态陷入内核态，从而获取想要的资源；这些系统调用按功能大致可分为如下几类： **·设备管理。**完成设备的请求或释放，以及设备启动等功能。 **·文件管理。**完成文件的读、写、创建及删除等功能。 **·进程控制。**完成进程的创建、撤销、阻塞及唤醒等功能。 **·进程通信。**完成进程之间的消息传递或信号传递等功能。 **·内存管理。**完成内存的分配、回收以及获取作业占用内存区大小及地址等功能。

中断和调用

系统调用：在我们运行的用户程序中，凡是与系统级别的资源有关的操作（例如文件管理、进程控制、内存管理等）都必须通过系统调用方式向OS提出服务请求，并由OS代为完成。其实是中断的一种特殊情况。

中断：中断是指计算机运行过程中，出现某些意外情况需主机干预时，机器能自动停止正在运行的程序并转入处理新情况的程序，处理完毕后又返回原被暂停的程序继续运行。 分为硬件中断和软件中断。 硬件中断（Hardware Interrupt）分为可屏蔽中断和非可屏蔽中断（non-maskable interrupt，NMI）。典型例子是时钟中断（一个硬件时钟以恒定频率—如50Hz—发出的中断）。 软件中断是一条CPU指令，用以自陷一个中断。由于软中断指令通常要运行一个切换CPU至内核态（Kernel Mode/Ring 0）的子例程，它常被用作实现系统调用（System call）。

中断向量表

中断向量表是存放中断处理程序入口地址的默认的内存区域。 在8086中，中断类型码乘以4得到向量表的入口，从此处读出4个字节内容即为中断向量。一般该向量表存在内存刚开始的地方；

CPU Cache与MESI

在看小林文章的时候，边看边查，加深了对CPU Cache了解。 包括什么是Cache？Cache的分级？缓存一致性？write through与wrte back等等

什么是Cache

小林开篇提了一个问题：请问以下两种初始化数组的方式，哪种方式执行速度更快？

回答这个问题，必须得有Cache相关的知识储备。 现阶段，计算机内存的速度远远低于CPU的访问速度，为了协调两者的速度差异以及利用好局部性原理，就在两者之间加了一个中间层——缓存Cache。

下图展示了从寄存器到远程存储器的存储器金字塔图：

从上往下的各类存储器，速度越来越慢，容量越来越大，造价越来越便宜。或许用表格和数字更直观一点，图片来源：
因此，CPU缓存（Cache Memory）是位于CPU与内存之间的临时存储器也可以叫做高速缓冲器，它的容量比内存小很多但交换速度快。

CPU每次访问数据之前都是先看看Cache里有没有，如果有，直接拿出Cache中的数据，如果没有，就先让Cache从内存中读取一段数据，然后CPU再读取Cache中的数据。

因此，在缓存中的数据是仅仅只是内存中的一小部分，但这一小部分可能是短时间内CPU经常访问的区域（局部性原理），这就可避开内存直接从缓存中调用，从而加快系统整体运行速度。 Intel i7的CPU Cache-Memory架构大致如下：

即一个CPU中有三级缓存，**每一个CPU核具有L1、L2两级缓存，这是每个核独占的，**其他核无法对其进行操作；而所有CPU公用一个缓存L3。L1、L2、L3的访问速度依次下降，存储空间大小依次上升。

为什么要设计多层Cache而且容量还这么小？ 简单来说，是由于只靠增加单个Cache的容量来提升性能的方式，**性价比太低了！**大容量的Cache的工艺难度以及成本上面都有许多问题，不利用大面积推广，只有少部分定制计算机才会采用较大的缓存，因此采用多级缓存以接力的方式即能够在CPU与内存之间搭上一座桥，又能控制成本。 Windows系统下可以直接打开任务管理器-性能-CPU，看到自己的CPU 各级Cache大小

回到最开始的问题，我们需要知道的是，对于数组而言，在内存中是顺序连续存放的，例如array[0][0] array[0][1].....array[1][0] array[1][1].....是存放在连续的内存区域。 **所以，形式一显然更快。**因为形式一的代码充分利用了Cache的优点，即将某一块内存数据读取到Cache中，而且之后的操作都基于这块数据进行，速度当然快；而第二种方式每次更新数据都涉及Cache缓存的切换，就会造成从内存中读取数据到缓存，这种操作时很耗时的。

Cache如何定位数据

复习的时候发现之前有一个盲点：那就是我知道了Cache缓存的原理，但是好像又什么都不知道。 它是内部结构是怎样的？怎么工作的？**CPU是如何确定某个内存地址的数据是否在Cache中呢？也就是说根据内存地址是如何命中的Cache的？**让我们一起来看看。

我们直接来看看Cache的物理结构，先看简化版：

CPU Cache内部其实由一个一个的Cache Line所构成的，这个时候可以想象excel表格，缓存中每一行就存储着内存中的一小块数据。 而这小块数据（Data block，缓存块）就是Cache与memory交换的最小单位，主流的CPU Cache的Data Block的大小一般为64Bytes。 举个例子，如果 L1 Data Block大小是 64 字节，也就意味着 L1 Cache 一次载入内存数据的大小是 64 字节。 ok，了解了简化版，我们来看看完整版：
由上图可知，缓存的物理结构可以用三个参数来描述：S、E、B，一一解释一下。 S：代表着Set的数目，什么是Set？表示将缓存分成了多组，而每一组里面有多个Cache Line； E：代表着Cache Line的数目，表示每一个Set中到底有多少个Cache Line； B：代表着Cache Line中所能存储的字节数，表示一个Cache Line里能够加载多少Bytes，比如之前所说的64Bytes。 先结合图和解释捋一捋三者的关系。 有个问题，为什么需要分Set？直接Cache Line不好么？ 答：不好，寻找Cache Line的过程需要一一比对，采用Set这种分表的方式可以加快搜索速度，不信就看看下面的寻址方式。

那么如何通过内存地址来确定是否在Cache中呢？我们可以将内存地址按照下图方式划分：

如果我们拿到一个内存地址，想查看其是否在Cache中： 第一步，取出中间s位进行hash，确定它位于哪一个Set； 之所以取中间几位进行hash，**个人认为还是考虑到局部性原理，如果采用高几位的数据，**在一个程序中相同的概率远大于取中间几位的概率（越高位的空间越大，越容易hash冲突）。因此取中间几位既可以照顾局部性原理，又避免了大面积的hash冲突。

第二步，取出高位的t位数据与Set中每个Cache Line的tag进行比较，是否相等，如果相等，查看v(valid)标志位是否为1，为1则表示Cache hit（缓存命中）；如果没有找到或者v为0，则表示Cache miss（缓存未命中），那么只能让Cache去内存中读对应的数据了，太惨了……

简单来说，tag就是比对高几位的数据。

第三步，如果第二步完成，取出低位的b位数据，根据该数据确定要取的字数据的位置，进行数据读取。

注意，cache中是以字节Byte为单位的。

补充一下，根据Set与Cache Line的数量关系，缓存大致可以分为三种：

  • **直接映射缓存：**多个Set，每一个Set仅有一个Cache Line；
  • **E-路组相连缓存：**多个Set，每一个Set有E个的Cache Line；
  • **全相连缓存：**仅一个Set，但是其中有多个Cache Line，这种效率极低，因为需要遍历所有的Cache Line；

CMU CASPP课程中举了两个例子，一个是直接映射缓存：

另一个是2-way 组相连缓存：

Write Through与Write Back

之前我们提到Cache可以加快CPU访问数据的速度，那么这里就有一个问题：CPU如果对缓存中的数据进行了修改，那么应该以什么方式、什么时候将其写回内存呢？即如何处理Cache与内存的数据同步问题。 有关Cache的写入，有两种方式：

  • Write Back（写回）
  • Write Through（写直达）

Write Through 如何保证Cache中修改的数据与内存中原数据的一致性问题？ 直观上最简单的方式就是，修改数据的时候，同时将数据写入Cache与内存。

简单来说，就是先更新Cache中的数据（如果该数据在Cache）中，而后再将数据写入内存。 这种方式最直观、最简单，但是也是最损耗性能的。因为每次对数据修改之后都需要将数据写入内存，这就不能很好的发挥出缓存的性能，得不偿失。

Write Back 写直达的操作无法很好的发挥出缓存应有的性能，那么如何对其进行优化？ 能不能……每次只更新Cache中的数据，只有当Cache必须得写回内存时，我们才将Cache写入内存。 可以预想，这种方式肯定比之前的方法效率更高。那么，什么叫做Cache必须得写回内存时？——就是Cache被替换的时候。 Cache的容量就那么小（以KB计量），读取的Cache数据不可能一直占据着空间，这其中也涉及Cache Line的替换，类似内存页置换，常用算法有LRU、LFU。

也就是说，当Cache Line没有被替换的时候，我们不需要将更新的数据写回内存，只需要更新Cache中数据即可，只有当该CacheLine被新的Cache数据给替换时，我们才将Cache中的数据写回内存。整体流程如下：

注意，图中所说的标记当前Cache Data Block为脏（dirty）即是在Cache Line中的Tag进行标记，后面在内存一致性中会进一步讲解。

缓存一致性协议MESI

写回机制可以充分发挥缓存的性能，于是如今大部分缓存机制都是采用这种方式。但是这又会带来一个问题：那就是如何保证多核场景下的缓存与内存的一致性？

假设CPU有两核，A，B，并且在他们的L1、L2是相互独立的，假设在A、B的缓存中都读入了变量i，此时i=0。 假设在A核中将i的值改为了1，但是B核所知道的i还是等于0，这就可能造成未知的错误。

这就是多核场景下缓存数据不一致问题。如何解决?

要想解决这个问题需要保证两点：

  • 某个CPU核对数据进行更新操作时，必须将该操作“告诉”其他的CPU核以及内存，这就是所谓的“写传播write propagation”（在多人协同文档中，也需要这种处理机制），也可以将其称为“广播”。实现这一点的常见方式是总线嗅探（Bus snooping），当某个核更新了数据时，会将数据通过总线来广播到其他核，其他核会时刻监督总线的动态，当收到数据更新时，会查看自己的缓存中是否存在对应的数据，如果有就进行更新。如果每次更新数据，都在总线上进行广播，这种方式会对总线产生巨大的负载压力。

  • 多核对于数据的修改必须**是串行事务化的。**简单来说，如果A核对i进行了修改，B核也对数据进行修改，它们会将相应的修改“传播”给其他核，这就必然涉及到AB核的消息谁先到达的问题。用小林画的图：

等等，这种类似的数据同步问题是不是在多线程的数据同步中也遇到过？当时我们引入了锁来解决，同理，在缓存一致性问题上我们同样可以引入锁机制，只有获取到锁的核，才能够对数据进行修改。

上面提到如果只靠总线嗅探的方式会加大总线负载，使用效果不好，实际广泛使用的是MESI协议，它将缓存中的数据标记为M、E、S、I四种状态，并通过这四种状态之间的关系来实现缓存一致。

  • M，modified，表示该数据已修改，即上述所说的“脏”数据，需要在合适的时机写回内存；
  • E，Exclusive，表示该数据独占，意指此时该数据只存在某个核中，其他核没有该数据，于是就不需要所谓的广播给其他的核，也就没有缓存一致性的问题；
  • S，Shared，表示数据共享，是从数据独占状态转移过来的。意指多个核中都有该数据，这个时候就会存在缓存一致性的问题；
  • I，Invalidated，表示数据已失效，可以丢弃掉Cache Block的数据了（高并发情况下可能出现两个CPU同时修改变量a，并同时向总线发出将各自的缓存行更改为M状态的情况，此时总线会采用相应的裁决机制进行裁决，将其中一个置为M状态，另一个置为I状态，且I状态的缓存行修改无效）；

MESI四种状态标志是存储在Cache Line中的

相信有些朋友已经隐约有点感觉了，这就是一个有限状态机：

单看有限状态机或许还比较难理解，我们以下面这个例子来一步一步分析MESI协议是如何工作的，借鉴链接： 首先，CPU 1核将内存中的变量i加载到自己的缓存中，并在缓存中将状态标记为E（独占）：
注：为简洁未画出L1、L2、L3缓存，可以认为图上的缓存表示L12，L3并入了内存中 随后，CPU 2读取了**变量i，**此时CPU1通过总线嗅探了解到CPU2的动作，将自身缓存I的状态标记为S（共享），CPU2的缓存也标记为S：
**而后，**CPU 1对变量i进行了修改，将缓存中的状态改为M（修改），CPU 2通过总线嗅探将自身的数据i标记为I（无效的）：
再之后，CPU1将变量i写回内存，并将自身状态标记为E（独占），注意，CPU2的变量a被置为I（无效）状态后，只是保证变量a的修改不会被写回内存，但CPU2有可能会在CPU1将变量a置为E（独占）状态之前重新读取内存中的变量a，这个取决于汇编指令是否要求CPU2重新加载内存：
**最后，**某个时刻CPU2需要访问变量i，但是发现已失效，于是需要重新去内存读取变量i，此时状态为：

上述只是一个MESI协议工作过程的简单描述，实际工作过程极其复杂，有三个比较重要的点：

  • 当一个处理器请求使用exclusive模式加载load一个缓存行时，其他的处理器会将所有它们自己关于该缓存行的副本都置为invalid。任何一个已修改过自己本地的该对应缓存行的处理器都需要首先将其写回到内存中，之后第一个处理器的load请求才可以被满足。
  • 当一个处理器请求使用shared模式加载load一个缓存行时，任何一个以exclusive模式加载该line的处理器都必须将其状态置为shared，并且任何一个已经修改过自己本地对应缓存行的处理器都必须将该line写回主内存，之后第一个处理器的load请求才可以被满足。
  • 如果缓存满了，则可能需要替换一个缓存行。如果该line是shared或exclusive状态，那么它可以直接简单的被丢弃。但是如果该line被修改过，那么它必须被首先写回内存之后再丢弃。

注意，MESI中对状态位的修改是基于总线嗅探机制实现的，并且整个过程在硬件层面上实现

内存屏障

CPU Cache与MESI协议解决的是多核CPU场景下的缓存一致性问题，主要是指指令的重排。

内存屏障看这个：链接 这部分还有一些东西没有写完： https://blog.csdn.net/qq_21125183/article/details/80590934 https://www.cnblogs.com/hxing/p/9416834.html http://csillustrated.berkeley.edu/illustrations.php https://www.zhihu.com/question/24612442/answer/156669729

参考链接 小林Coding CMU CASPP 存储器金字塔

< 操作系统
🔥《手写操作系统》 >