操作系统结构
操作系统内核
内核负责抽象并管理硬件设备，应用程序只需要直接交互内核，不需要关心硬件的具体实现。
内核的功能有进程管理、内存管理、硬件设备管理和向应用程序提供服务（系统调用）。
宏内核和微内核
宏内核结构中，内核的所有功能，如进程管理、内存管理、文件系统、硬件管理都在内核态中运行。不过，linux可以动态加载内核模块，比如设备驱动等可以动态加载。
微内核架构中，内核只保留最基本的能力，如进程调度、进程间通信、内存管理等。将其他功能放到用户空间，因此将不同服务隔离，单个服务出现故障或遭受攻击不会影响其他服务。
混合类型内核是一种大一些的微内核，将部分开销大的关键服务，如文件系统、网络协议栈放回内核态，以减少用户态和内核态之间的切换开销。是一种折中方案
宏内核：内核态模块之间交互方便，驱动直接交互硬件延迟低。但是模块耦合度高，单个模块故障或受攻击可能导致系统级故障，且维护更新难度大，不易扩展。
微内核：一个服务崩溃不会影响其他服务，容易动态加载更新和扩展；但是需要频繁进程间通信和上下文切换（访问硬件时），需要设计复杂的消息传递机制
混合内核：将图形驱动等系统调用频繁的功能放在内核态减少切换开销。比微内核的通信和切换开销小，比宏内核更灵活。
硬件结构
图灵机和冯诺依曼模型
图灵机模型：由纸带和读写头组成。纸带相当于内存，读写头上有计算、存储单元（寄存器）和控制单元。在纸带上写入1、2、+，对于数字，读写头按照顺序读入到存储单元中。读取到+时，控制单元发现是运算符，就按照运算操作计算存储单元中的数字，并将结果放到存储单元中。最后将结果写到纸带上。
冯诺依曼模型基于图灵机的设计：将计算机分为运算器、控制器、存储器、输入设备、输出设备。其中运算器和控制器在CPU中，存储器、输入输出设备通过总线连接到CPU。
常见的寄存器有通用寄存器（参与计算的操作数）、程序计数器（指向下一条指令的地址）、指令寄存器（存放当前执行的指令本身）
总线一般分为数据总线、地址总线和控制总线
CPU位宽尽量不要小于总线位宽，否则32位CPU计算64为数据，需要分高低位计算，效率低。
CPU采用4级流水线，4个阶段是取指、译码、执行、回写。统称为指令周期。
CPU的时钟频率，如1GHz代表1秒产生1G次脉冲信号，倒数是时钟周期。一个时钟周期不一定能执行完一条指令，如乘法指令和加法指令都是一条指令，但乘法比加法慢得多。
CPU的执行时间=时钟周期数时钟周期时间=指令数CPI(指令的平均时钟周期数)*时钟周期时间
优化：编译器优化 - 减少指令数；CPU架构优化 - 流水线 - CPI；超频 - 减少时钟周期时间（散热压力大，容易崩溃）
32位和64位
32位计算机一次只能计算32位数据，超过32位需要分高低位计算，而64位计算机一次可以计算64位数据。32位计算机一般地址总线也是32位，因此只能寻址4G。64位计算机一般可以寻址48位。
从数据计算的角度，如果需要计算的数据不超过32位，则64位没有优势。
对于软件，32位和64位是指令格式的区别。32位的软件可以以兼容模式运行在64位电脑上，但64位软件无法运行在32位电脑上。
缓存命中
对于2维数组，按行遍历比按列遍历块，因为一行是连续的，一列不是连续的。连续的可以预读命中。
计算密集型线程可以绑定到某一个CPU核心上，避免缓存命中率下降，因为不同的核心有不同的缓存。
缓存一致性
多核心有不同的cache，一个核心修改数据后写到cache，但还未写回。导致不同核心无法读取到最新的数据，这叫缓存不一致。
解决缓存一致性：写传播+事务串行化
• 写传播：每个CPU更新缓存后，必须同步到其他cache • 事务串行化：保证不同核心收到同步的顺序相同，如A、B都修改了某一变量，则所有核心都应该先收到A的修改然后收到B的修改，或者反过来。需要引入锁机制。
基于总线嗅探的MESI协议：总线嗅探就是每个核心监听总线上是否有核心广播自己修改了cache，从而实现写传播。MESI是4个状态缩写，即已修改、独占、共享、失效。已修改是一种脏标记，表示已经修改缓存项但还未写回内存。失效代表缓存项已经失效，不能读取。独占和共享代表缓存项是干净的，独占是数据指缓存在一个CPU的cache中，因此修改了不需要广播。共享代表缓存项存在多个核心的cache中，修改之前必须先广播一个请求，将其他cache中该项置为无效，然后更新当前缓存，并将当前缓存标记为已修改。读取失效缓存项需要先检查其他核心cache是否有副本，没有则读主存。
伪共享问题：多个线程看似操作不同变量，但是由于这些变量存储在同一缓存行中，一个变量的修改会影响同一缓存行的其他变量，导致缓存行频繁失效 。因此需要将高频修改的变量与其他变量隔离。
补码、小数
负数用补码表示是为了和正数统一加减法操作。十进制转换为二进制用除二取余法，二进制转换为十进制用乘二取整法。
计算机以浮点数形式存储小数，包含符号位、指数位（小数点在数据中的位置）、尾数位（小数点右侧数字）尾数长度决定数的精度。单精度是32位（尾数23位），双精度是64位（尾数52位）。
0.1+0.2！=0.3是因为小数无法用完整的二进制表示，必须根据精度舍入。因此浮点数存储的是近似值，不能直接比较，必须使用误差范围比较。金融场景必须用高精度库。
内存管理
内存是与CPU直接交换数据的存储器
冯诺依曼体系的计算机是存算分离的，也就是数据放置在内存上。计算时加载到CPU的寄存器中，计算结束后把结果输出到内存上。
与CPU越接近的存储器，读写速度必须越快，否则会导致CPU等待IO时间长，影响CPU效率。然而对于存储器来说，一般越快的存储器，容量越小，价格越高。另一方面，快速存储器常常是易失性的，也就是掉电数据就没有了，比如寄存器，SRAM，DRAM等；而非易失性的存储器往往比较慢，比如磁盘，磁带等。当然，也有非易失性的内存，但是并不常用。
因此，CPU只操作内存数据，任何外存上的数据都必须先加载进内存，然后才能被CPU加载到寄存器。
存储的金字塔层次结构
因此，现代计算机系统会有一个金字塔型的存储结构，由上到下依次是寄存器（一个CPU时钟周期，纳秒级）、L1、2、3级缓存（SRAM，几十个时钟周期，纳秒级）、内存（DRAM，百纳秒级别）、外存（HDD、SSD、磁带、光盘等，SSD的读延迟在几十微秒，写延迟在几毫秒；HDD的读写延迟在十几毫秒）、远程存储（分布式文件系统、服务器，延迟取决于网络连接）。
每一层都可以看做是下一层的缓存，根据局部性原理，这样可以使得存储系统在性能上接近金字塔上层，在容量和价格上接近金字塔下层。
内存需要操作系统管理
如果操作系统不提供内存的管理，程序员就必须使用绝对物理地址，会出现两个问题：
- 编写程序低效：程序员必须手动管理内存，保证自己的程序能够独占一段内存。
- 不安全：每个进程都有可能访问到其他进程的数据，缺乏隔离性。
虚拟内存是操作系统给每个进程提供的独立连续地址空间
为了高效安全编写程序，引入虚拟内存的概念。
操作系统给每个进程都提供一个独立、连续的虚拟地址空间。空间的大小由地址长度决定，例如，32位机器上进程地址空间为4G，用户态3G，内核态1G；64位机器上由于地址空间太大，进程只用其中48位，就是内核态、用户态各128TB。注意内核态的地址空间是各个内核进程共享的，task_struct中的mm_struct用于管理虚拟地址空间，mm_struct中的task_size用于定义内核态与用户态的分界线（地址值）。
虚拟地址空间可以比真实物理内存更大，这是基于局部性原理，认为每个进程在最近一段时间更可能反复使用一部分页面。多余的页面如果分配了就交换到外存。
虚拟地址空间按一定的方式映射到物理地址上，有分段、分页、段页式。Linux采用多级页表管理。
虚拟内存具有隔离性，解决了编程效率和安全性问题：每个进程认为自己独占内存空间，不用担心内存分配的问题，也不用管理页面的物理布局；每个进程只能访问自己的地址空间，不能访问其他地址空间，因此免受恶意进程或故障进程的破坏。
但是，内核态进程都是共享地址空间的。从高效和安全两个方面来分析：
• 操作系统内核是操作系统开发人员精心设计的，了解内核地址布局，通过锁和信号量等机制确保了不会产生数据竞争问题。反而隔离内核态进程会导致进程通信的开销，妨碍内核的高效实现。 • 内核态的进程执行的代码是操作系统本身提供的，因此认为不会有恶意。
缺点在于内核也是有漏洞的，病毒程序可能利用操作系统内核漏洞发起攻击。
分段机制导致内外碎片，需要频繁交换和紧凑
分段机制是一种内存管理机制，原理是将虚拟地址空间分为若干段，例如代码段、数据段等。每个段独立映射到物理内存上的一段空间，通过段基址加偏移量索引段内内容。
可以实现物理内存的离散分配，但是会导致外碎片，也就是多个段之间的空闲空间是分散的，即使总大小足够分配也无法分配。其次，我认为分段机制也有内碎片问题，比如应用程序不一定需要一个段这么大，并且可能本来是需要的，后来因为某些原因释放了，但是段内的空间又无法分配给别的程序使用。
因此需要频繁紧凑，也就是挪动段的位置让他们相邻。具体是先将原来段占用的内存写回磁盘，然后再装载回紧跟着另一个段的地方。
分页机制有内碎片无外碎片，交换效率高
分页机制是将虚拟地址空间和物理地址空间都划分为一系列大小相同的页，页的大小一般是4K，但是也有大页。操作系统将这些虚拟页映射到物理页上，这些物理页可以是离散的，从而不需要分配连续的物理内存空间。因此没有外碎片问题。
但是进程可能不需要一个页，例如只需要几百字节，却也必须分配4K。但是页本身是比较小的，因此内碎片总体来看开销小。换出时也仅需要换出部分页，而不是一整个段，交换效率高。
分页机制还允许进程无需一次性将所有内容加载进内存，只有需要用到的时候再载入。
单级页表导致页表太大，造成内存开销。Linux采用多级页表机制减少页表大小。原理是如果用不到某个上级页表的表项，就不需要创建下级页表。也就是说不用覆盖整个虚拟地址空间。
虚拟地址通过MMU映射到物理地址
https://blog.csdn.net/lyndon_li/article/details/135392221 https://juejin.cn/post/7269276349654155275#heading-15
MMU是CPU内部的单元，专门用于虚拟地址到物理地址的翻译。
在多级页表模式下，页表本身也是放在内存中的，页表中的条目称为页表项，页表项包括该虚拟页的物理页帧号（PPN）、该页是否为脏页、保护权限等信息。查询页表项可以得到虚拟页的物理页框号，和虚拟地址的页内偏移量一起可以组成物理内存的地址。
虚拟地址分为虚拟页号和页内偏移量两部分。虚拟页号用于定位虚拟页所在页表的页表项，页内偏移量用于和物理页框号组成物理地址。这是因为内存页通常是4KB的，而地址是按字节寻址的。因此某个地址会在所在内存页的某个偏移量处。而物理页和虚拟页的偏移量是相同的。
在多级页表模式下，虚拟页号也可分为多个部分，如常见的4级页表分为PGD、PUD、PMD和PTE。只要知道PGD的物理内存地址，就可以通过虚拟页号的各部分一直查到物理页框号。
每个进程的虚拟地址空间是独立的，也就意味着每个进程有自己的页表。在Linux中，页表基地址保存在进程结构体task_struct下用来表示地址空间的mm_struct中的pgd，MMU在翻译某个进程的地址之前，先将该进程的页表基址加载到页表基址寄存器上。
TLB是CPU中的一种高速缓存，专门用于存放地址转换的映射，命中后就不用逐级查询页表了。因为高速缓存采用SRAM，延迟就是几个时钟周期，但是内存是DRAM，一次访问内存需要几百个时钟周期，更不用说逐级查询了。
内存大页
内存大页是指内存页的大小不止4K，有可能是2M甚至更大。
大页的作用在于减少页表层级和表项数目，更容易在TLB中命中，加快地址转换过程，并且可以减少缺页异常。例如，应用需要2M内存，直接分配一个大页就够了。
大页的缺点在于存在空间浪费，因为程序未必需要一个大页的大小。其次，对于局部性很好的应用来说并不能改善性能。
大页需要大段的连续物理内存，由于系统长时间运行后会产生碎片，很难找到连续大段物理内存，因此会在系统启动时分配足够的大页内存，放在大页内存池中。
大页内存池是锁定的，不能分配给其他虚拟页，也不允许换出。大页内存池耗尽之后无法分配大页。
Linux整个都是一个段
Linux本来想用分页管理，但是由于英特尔处理器的历史原因必须有段机制，因此就把整个地址空间看成一个大段，相当于没有用段机制。
mm_struct是进程管理虚拟内存空间的结构体
每个进程由进程控制块管理，在Linux中进程控制块是task_struct结构体。
进程控制块中用于管理虚拟内存空间的是mm_struct结构体，由于不同线程共享地址空间，因此线程共享mm_struct结构体。进程和线程都是task_struct，进程和线程的唯一区别是有没有独立的地址空间。
注意，不同的线程并不共享栈，因此线程的栈指针并不在mm_struct中。与线程有关的资源应该保存在一个叫thread_union的结构体中，里面有线程的栈和寄存器等相关资源。task_struct通过一个宏可以找到thread_union。
内核栈也不在mm_struct中，而是在task_struct->stack。
VMA表示一段连续的虚拟地址范围
vm_area_struct（VMA）是用于描述和管理进程虚拟内存空间的结构体，每一个task_struct使用mm_struct结构体管理进程的虚拟地址空间，每个VMA代表一段连续的虚拟地址空间，mm_struct通过VMA链表管理所有用到的虚拟地址空间。
VMA同时以红黑树的形式组织，mm_struct有指向链表的头指针mmap和红黑树的根节点mm_rb。VMA在链表中顺序串联，在红黑树中可以高效查找。 • 应用可能频繁申请内存空间，有大量的VMA，红黑树方便增删改查，平均时间复杂度为Ologn。 • 链表方便遍历VMA（比如用户通过proc/pid/maps文件查看虚拟内存使用情况时），红黑树则要用栈或者递归，有空间复杂度。
VMA中包括区域的起始地址、结束地址、上一个和下一个VMA的指针（形成链表）、用于连接到红黑树的成员、所属的mm_struct、访问权限、操作函数集等。
进程的虚拟地址空间布局
32位地址按3G/1G划分用户和内核虚拟地址空间
32位地址的最大寻址范围是4G，按照3：1划分。64位地址则是用户态内核态各占128T，中间还有很大的空洞canonical space，可以根据地址头部快速判断是用户态还是内核态。
用户态虚拟空间布局
进程用户态虚拟地址空间的布局是代码段、数据段、bss段、堆、文件映射与匿名映射区、栈。各区域的起始地址在mm_struct中。
内核态虚拟空间布局
32位内核态虚拟空间只有1G，因此要精打细算使用
• 直接映射区占用896M：直接映射到0-896M的物理内存空间上 ◦ 前16M：DMA区域，以前ISA总线的DMA控制器只能使用物理内存的前16M ◦ 普通区域：内核代码段、数据段、BSS段、进程相关数据结构、内核栈（非常小且固定，溢出危害巨大） • 高端内存：128M动态映射 ◦ vmalloc动态映射区 ◦ 永久映射区 ◦ 固定映射区 ◦ 临时映射区：例如操作page cache时，需要将page cache的物理地址映射到临时映射区操作
64位内核态虚拟空间有128T • 8T空洞 • 64T直接映射区 • 32Tvmalloc动态映射区（类似于用户态的堆） • 1T虚拟内存映射区，存放struct page • 512M直接映射区，存放代码段、全局变量、BSS等
库函数malloc通过系统调用brk或mmap为进程分配虚拟内存
进程需要使用内存时，就向操作系统申请分配一些虚拟页使用，这叫做分配内存。分配的虚拟内存不一定对应了物理内存，只有访问时才会触发page fault映射到物理内存。 内存可以在创建进程时静态分配，例如代码段、全局变量、静态变量等。也可以在进程运行过程中动态分配，比如通过brk在堆中分配或通过mmap在文件映射区分配。
一般通过brk分配小块内存，通过mmap分配大块内存。
malloc会分配更大的空间
malloc在分配虚拟地址空间时，会预分配更大的空间作为内存池，这是为了避免频繁系统调用，并且减少内存碎片。
brk在堆上分配内存
brk系统调用的原型只有一个参数，就是堆顶的地址。如果高于当前堆顶就是分配了新的地址空间，如果低于当前堆顶就是回收地址空间。还有一个更方便的系统调用sbrk，参数是堆顶偏移量，也就是只需要指定堆顶指针移动的偏移量。
brk是堆不是栈，因此可能堆顶的还没释放，堆里面的已经释放了。但是堆顶这时还不能往下移动，因此free并不会马上归还，而是会留在堆里面分配给新的请求。只有进程终止或者堆顶释放的时候才会归还。
堆的分配方式会导致碎片化，因此只适合分配小块内存。
mmap在文件映射区分配虚拟内存
https://www.cnblogs.com/Courage129/p/14232306.html
mmap允许将文件或设备的内容从内核的page cache映射到进程的地址空间中，这样进程可以像直接访问内存一样访问文件，而不是通过read/write系统调用接口访问。
如果没有mmap，进程要访问文件就要先用read系统调用把文件内容先复制到用户态的缓冲区中，修改缓冲区再写回page cache。有了mmap就可以直接操作page cache，减少了一次复制。
除了映射文件之外，mmap还可以映射匿名页，以达到动态分配内存空间的目的。
mmap的参数有起始地址、分配长度、一些标志位比如访问权限，可读可写等，是私有还是共享映射，文件描述符和文件内偏移量等。 • 起始地址只是一个暗示，如果可以分配就分配，如果不可以就由操作系统自己找一个（一般进程可以指定NULL） • 分配长度是必提供 • 只有文件页需要文件描述符，匿名页指定-1，偏移量为0
每次调用mmap都会产生一个VMA，返回值就是指向起始地址的指针。
free会归还mmap分配的空间。
mmap的文件通过munmap和msync刷盘
mmap将page cache映射到用户空间，默认情况下操作系统会有线程异步刷盘（根据脏页比例或者时间阈值）。
msync函数可以将内存中的修改强制同步到磁盘文件，确保数据持久性 • MS_SYNC同步刷盘，意思是mync函数阻塞直到数据落盘 • MS_ASYNC异步刷盘，意思是只是通知内核调度刷盘，不等待完成
munmap解除映射或者close关闭文件描述符时会触发脏页刷盘，但不是立刻的，依赖于内核的调度。
注意：msync同步指定内存范围的脏页，默认不同步文件的元数据，适合局部数据更新场景。fsync以文件为单位强制下刷文件所有的脏页和元数据
匿名页和文件页
内存中的页有两种：匿名页和文件页。
匿名页是没有关联到文件系统，不需要持久化的页。这些页通常保存进程运行过程中的临时变量、和动态分配的堆等数据，理论上是不需要落盘的。但是实际上有可能在内存紧张的时候被换出到磁盘上。
匿名页通过映射机制映射到虚拟地址空间的某页。
文件页是与磁盘存在映射关系的某页。一般来说应当是先从磁盘上将文件读入内存中的page cache，然后再映射到进程的文件映射区。
区别：文件页是持久化到磁盘上的数据，而匿名页仅仅存在于内存。内存紧张时匿名页需要交换到磁盘上的交换分区或者创建一个交换文件，而文件页则写回脏页或者不脏就直接丢弃。
联系：匿名页和文件页都使用struct page结构体，只是文件页的mapping指向page cache，而匿名页的mapping指向anon_vma结构用来追踪对应的VMA。并且匿名页不会是脏页。通过检查page结构mapping的最低位判断是否是匿名页（1：匿名，0：文件）
注意，匿名页在换入换出时会暂时使用page cache，但是正常使用的时候不涉及page cache
私有映射和共享映射
私有映射是隔离性的一部分，意思是映射的地址空间不能被其他进程访问。例如，一个文件可以通过私有文件映射映射到了多个进程的文件映射区，但是多个进程可以独立读写映射而不会相互影响。这是依赖于写时拷贝。而共享映射是一种进程间通信的方式，例如一个文件通过共享映射被多个进程映射，则需要锁或信号量机制避免数据竞争的问题。
私有映射的文件是不会写回盘的，而共享映射会。
库函数mmap和系统调用mmap
库函数mmap实际上是对系统调用的封装，方便用户编程。
mmap的使用：首先用open打开一个文件，获得文件描述符；然后用stat或fstat获取文件大小，从而知道需要映射空间的大小；接着调用mmap指定起始地址（通常为NULL）、长度、保护标志、文件描述符、偏移量；mmap会返回映射区域的指针；用完后使用munmap解除映射；最后使用close关闭文件。
stat和fstat用于获取文件的状态信息，包括文件大小、访问时间等元数据。两者区别在于前者使用路径名，后者使用文件描述符。
分配和映射的虚拟内存不会立刻访问
分配和映射内存后，不会立刻将虚拟内存与物理内存关联，也不会立刻将文件读上来。意思是PTE表项是空的。只有在访问虚拟页时，才会触发page fault为虚拟内存页分配并映射物理内存页。
私有文件映射
进程的task_struct结构体通过file_struct管理打开的文件，file_struct中有文件描述符数组，文件描述符就是这个数组的下标，数组的每一项都是struct file结构。通过file可以获取文件的索引，如果进程想read/write有这个就够了。但是如果要映射到虚拟内存区域，还需要把文件从page cache映射过来。
映射的本质就是使用PTE表项，将文件映射区的虚拟地址空间翻译成page cache对应的物理地址空间，因此操作映射就是直接操作page cache。优势在于用户态进程本来不能直接访问内核态的page cache，而映射后就可以直接在用户态访问，不需要拷贝。
私有文件映射采用写时拷贝技术避免数据竞争。私有文件映射的PTE表项设置为只读的，当进程写入的时候会产生写保护类型的缺页中断。这时会分配一个新的物理页并且写入修改后的数据，并且将PTE映射到新页。
私有文件映射中，脏页不会回写，其他进程看不到。
私有文件映射避免了拷贝，主要用于进程加载数据，比如代码段、数据段等。
共享文件映射
共享文件映射和私有文件映射的唯一区别在于不采用写时拷贝技术，PTE表项直接就是可写的。因此一个进程修改文件后另一个进程也可以看到。因此需要锁或信号量等机制避免数据竞争。
共享文件映射可以写回脏数据，对文件做真正的修改。
共享文件映射是一种进程间通信的机制。
私有和共享匿名映射
匿名页不对应磁盘上的文件，也没有page cache。
对于私有匿名映射来说，使用mmap分配一段虚拟内存空间之后，真正使用到这段空间时，没有相应的PTE表项，因此MMU会触发缺页中断。分配一个物理页后再更新页表。
对于共享匿名映射，由于另一个进程不知道本进程将虚拟地址映射到了哪一个物理页，因此共享匿名映射是借助文件实现的。
内核有一个tmpfs虚拟文件系统，内核在tmp方式中创建一个匿名文件。因此进程通过匿名文件仿照共享文件映射完成共享匿名映射。
共享匿名映射只适合父子进程之间的通信，这是因为其他进程无法看到本进程创建的匿名文件，只有子进程可以共享虚拟内存空间和页表。
direct io不能使用文件映射
文件映射mmap是将page cache中的内存页映射到用户空间，而direct io没有page cache，一般是应用程序自己实现了一个缓存，所以不会使用mmap机制。
RCU机制允许读者无锁访问
传统的读写锁中，写者持有写锁时读者不能读取。
在RCU机制中，读者总是可以读取数据，如果写者要写入数据，则先拷贝一份副本去修改副本，修改完后将指向旧数据的指针指向新副本
适用于读远大于写的场景。
3种物理内存模型
FLATMEM平坦内存模型
将物理内存空间看作一块连续的大数组，数组的每一项是page结构，下标就是物理页号
DISCONTIGMEM非连续内存模型
没必要为没用到的物理页分配page结构，经常要管理小片不连续的物理内存。
用node表示一小段连续的物理内存，node内部用page数组管理这段连续物理内存页。
SPARSEMEM稀疏内存模型
node粒度大，node内部可能不连续。node多了开销大。
将物理内存空间划分为一系列section，每个section内部有page数组。section自身构成一个连续数组。
每个section可以上线或下线从而支持内存的热插拔。
当section下线之前，内核会将这部分地址隔离开，并将该section的内容迁移至其他section。包括复制和重新映射。迁移成功后将section标记为不可用并拔掉内存模块。而上线则仅需要初始化section并标记为可用。
对于用户态地址空间，所有的虚拟内存地址都可以重新映射。对于内核态地址空间，直接映射区对应的物理地址不能改变，因此这段物理内存是不可迁移的，也就是不可拔出的。
多核CPU的内存访问架构：一致性和非一致性
对称多处理器架构SMP
所有CPU访问内存的距离是一样的。内存和所有的核心在总线两侧。因此是一致性内存访问UMA
缺点：总线成为性能瓶颈。
非一致性内存访问NUMA架构
将内存划分为多个内存结点，每个CPU有自己的本地内存。CPU访问本地内存更近并且不用竞争总线。CPU也可以通过QPI跨节点访问其他内存但是比较慢。因此每个CPU最好优先使用自己的物理内存，也就是执行映射到自己物理内存的进程。（处理器亲和性）
每个numa节点用pglist_data结构体管理，pglist_data放在全局数组node_data中，通过nodeid索引。
每个pglist_data主要包括：numaid，指向物理页page的数组，第一个页的pfn，可用物理页总数等。还有一个自旋锁用于数据竞争。
物理页的PFN是全局唯一的。
NUMA节点的状态用位图表示，包括上线、有高端内存、有普通内存等
物理内存的回收
虚拟内存没有映射到物理页上，访问的时候就会触发缺页中断。缺页中断如果没有足够的物理内存，就会触发内存回收。
物理内存紧张时，会唤醒内核线程kswapd来后台异步回收。如果仍不够就会同步直接回收。
如果kswapd和同步回收都不够，就会触发OOM机制杀死一些高占用进程。
回收内存的步骤：文件页和匿名页是可以回收的，对于文件页，可以写回或丢弃。对于匿名页，需要swap换出。文件页和匿名页的回收基于LRU算法。有active和inactive两个双向链表，可以优先回收不活跃的页。
优先回收文件页而不是回收匿名页：干净文件页可以直接丢弃，藏文件页写回只有一次磁盘写入。匿名页的换入换出均为随机IO，无法合并也无法预读，而文件页通常对应磁盘的连续逻辑块，写回时可以合并IO实现顺序访问
只有直接丢弃文件页不会影响性能，写回和swap都是会影响性能的。
为了减少性能影响，可以调整更倾向回收文件页，也可以尽早触发kswapd来避免触发直接同步回收。
内存水位（阈值）用来触发后台回收线程，分为页高阈值、页低阈值和页最小阈值。 高于页高阈值：内存充足 页低阈值-页高阈值：有一定压力 页最小阈值-页低阈值：触发kswapd线程后台回收，直到高于页高阈值 小于页最小阈值：触发主动同步回收
页高阈值和页低阈值根据页最小阈值计算，可以调整页最小阈值。调高了：早触发回收，预留过多空闲内存导致频繁换入换出甚至OOM。预留少了则会影响内存分配性能。
在NUMA架构下，本地内存不足时除了回收本地内存，还可以使用其他node的内存。可以设置倾向。默认设置为先找远端内存，因为访问远端内存（内存IO）的开销比回收内存（磁盘IO）的影响要小。
OOM根据算法选择victim
OOM选择算法为可用页面数*当前进程校准值除以1000+当前进程已用物理页数
也就是和校准值、已用页面数正相关。因此可以调低校准值保护某个进程不被杀死。但是假如某个进程发生了内存泄漏而不能被杀死，会导致逐渐占满物理空间。
在4G物理内存机器上申请8G虚拟内存空间 • 在32位机器上直接申请失败，因为用户态进程最多可以申请3G。 • 在64位机器上，理论上可以分配128T ◦ 如果设置了overcommit_memory参数，则会检查请求分配的合理性，有可能分配失败 ◦ 由于虚拟内存的VMA等管理资源也是占用空间的，因此8G应该可以申请，但没办法申请到128T。会在某个时刻触发OOM杀死当前进程。 ◦ 如果开启了swap机制，内核可以将部分没有用到的管理资源换出，因此可以申请到127T。但是进程本身的运行也会占用一定地址空间，因此不可能正好申请完128T。
预读失效和缓存污染
每一级存储都是下一级的缓存。缓存基于局部性原理。当数据的访问模式不符合局部性原理时，会导致缓存失效。
缓存的逐出通常采用FIFO、LRU、时钟或者LFU算法。
FIFO算法并不考虑数据最近使用情况，因此性能不佳。
LRU、LFU和时钟算法等考虑到了数据最近使用情况，基于局部性原理。
LRU：活跃/非活跃
LRU算法将最近最少使用的数据逐出，基于最近访问时间。当缓存命中时就提升到首部，当加载新缓存时逐出尾部。使用双向链表和unordered_map实现。 • 预读失效：对于随机IO，基于空间局部性的预读就失效了，因此效果不佳 • 缓存污染：对于大规模顺序IO，每个页面虽然最近访问过，但不会再次访问，因此时间局部性失效，效果不佳。
改进方法：在Linux中，page cache实现了两个链表：活跃LRU和非活跃LRU。第一次访问数据时会将数据放在非活跃链表中，第二次访问才会将其提升到活跃LRU链表中。因此提高了进入活跃LRU的门槛，不会污染活跃LRU链表。逐出时会优先逐出非活跃LRU链表中的数据页。
LFU：年龄老化
LFU算法根据页面的最近访问次数，逐出最近最少访问的页面。问题在于工作集切换时，会导致新工作集的页面频繁逐出。因此可以给每个页面记录年龄，年龄越高排序越低。或者对于所有的页面，每隔一段时间将访问次数减半。
Linux采用4KB作为内存页的默认大小
页面大小必须是2的整数幂，为了方便计算(1. 通过左移右移的方法得到各级页表地址和页内偏移量2. 如果不是2的幂次会产生地址浪费，如5B页面，用2位2进制表示页内偏移量会有1KB无法访问，用3位会浪费3个地址)。
如果页太小，则页表等管理开销大。
如果页太大，会浪费内存页的空间。
struct folio用于表示大页和复合页
Linux中的默认内存页大小是4K，但是可以创建更大的页面来减少缺页次数、减少页表条目，提高分配效率。
复合页是连续的小页组合成的，但仍是小页的组合。
Linux引入folio用来表示大页和复合页，能够简化代码逻辑，比如不用每次都检查一个page是不是大页的第一个页。并且释放的时候只需要一次调用就可以。
内核分配物理页的结构
alloc_pages用于分配2的order次幂个物理内存页。返回的是物理地址。由于进程只能直接使用虚拟地址，所以提供了另一个__get_free_pages函数直接返回虚拟内存地址供进程使用。由于物理页中可能还有原来的数据，因此get_zeroed_page能够返回填充0的物理页，更安全。
释放物理页时，free_pages传入虚拟地址和阶。转换物理地址之后调用__free_pages释放。
内存分配根据gfp掩码指定内存分配行为，比如高优先级、允许swap、必须原子等。
alloc_pages底层使用伙伴系统分配物理内存。
伙伴系统将内存划分为多个块，每个块都是2的幂次大小。进程请求一定量页面时，伙伴系统会优先分配所需阶数的连续块，如果该阶没有就把更大阶数的伙伴块平分成低阶，直到分到所需的大小。
释放内存的时候检查相邻伙伴块是否空闲，如果空闲就合并成更高阶。
通过合并伙伴块能够减少外部碎片，快速分配2的幂次大小连续物理空间。
但是会有内碎片，因为所需的大小不一定是2的幂次，会浪费。并且不适合小内存块分配，因为会频繁划分小的伙伴块。并且伙伴系统最少分配一个物理页，如果只是new一个对象，可能根本用不到4K。
小内存块结合slab分配器使用
针对小内存块的分配，内核采用slab内存池。
slab分配器首先会向伙伴系统一次性申请多个物理内存页面组成slab内存池。并将这些连续物理空间划分为多个相同大小的小内存块，内核会针对多种尺寸预先创建多个slab内存池。比如会对task_struct、page等常用结构体建立slab内存池。这是为了方便频繁分配和释放这些结构体。
内核使用kmalloc接口分配小块内存
kmalloc基于slab分配器实现，kmalloc会创建一系列大小的内存池，根据用户指定选择一个最合适的内存池slab cache。也可以用户自己通过kmem_cache_create创建一个合适的内存池。 内核通过vmalloc接口分配大块连续虚拟内存
vmalloc不保证内存在物理上连续，只是虚拟地址连续。
内核通过get_free_pages函数获得大量连续物理内存
get_free_pages通过伙伴系统分配大量连续物理内存。
文件系统
文件及文件系统的概念
文件是一系列数据和元数据的集合。其中，元数据定义了文件的属性信息，数据则是文件存储的实际内容。
文件的元数据一般包括所有者，访问权限，访问模式，创建时间，修改时间，大小等属性，还包括文件数据块的索引，即文件中某个数据块的逻辑地址。
文件最重要的元数据是inode。inode是文件系统中的一个结构，唯一标识了一个文件。inode通过inode号相互区别。在同一个文件系统中，inode号是唯一的。不同的文件系统可能不唯一。进程打开文件后，可以通过struct file结构中的vfsmount成员确定文件系统。
inode号一般从3开始分配，2号是根目录，1号在ext中是lost+found（恢复无主文件的目录），0号保留（比如删除一个文件之后可以将文件名映射到0）
注意：在Linux中，文件名并不属于inode，因为不同的硬链接可以有不同的文件名，但是他们共享一个inode。文件名与inode的映射关系存储在目录文件的目录项中。目录文件就由该目录下目录或文件的目录项组成，目录项在目录文件中组织成哈希表从而便于查询。为了避免逐级从目录文件中查询，操作系统会将最近读取到的目录项缓存在dentry中。dentry是内存中的结构，用于缓存文件名到inode之间的映射，避免逐级查找。
文件的数据是文件存储的实际内容，数据可以是有结构的，也可以是无结构的。结构化数据是具有某种标准格式的数据，例如数据库中的某个表格。结构化数据便于计算机处理和分析。非结构化数据是指没有标准格式的数据，比如文本文件，二进制文件等。非结构化数据通常占数据量的绝大多数。半结构化数据一般是一些自描述文件，数据的结构和内容混在一起，需要解析标签。例如json文件，html文件等。
文件可以进行一系列操作，比如创建，打开，读取，写入，删除，截断等。不同的文件系统实现操作的方式不同，Linux中除了具体的文件系统，还有对文件系统的抽象也就是虚拟文件系统VFS。VFS可以给应用提供统一的操作接口，便于用户编程。
文件系统是操作系统中用于组织和管理文件的部分。文件系统一方面提供了对文件的操作管理方法，另一方面是对底层磁盘的抽象，使得用户无需关心数据在盘上是如何放置的，而将存储空间的管理交给文件系统完成。
文件系统的主要功能包括提供对文件的操作，提供目录结构，管理文件的数据块在磁盘上的放置。保护文件的一致性和崩溃恢复等。
文件的操作
文件的操作包括创建，打开，读取，写入，删除和截断等。
要打开或者创建一个文件，可以使用open系统调用。open系统调用有3个参数。第一个是文件的路径和文件名，第二个是文件的访问模式和操作，第三个是在创建文件时，定义文件的访问权限。
首先，内核需要解析路径名。解析路径名的方式就是从根目录开始，逐级读取目录文件，并确定下一级目录文件的位置。如果目录较长，这个过程可能会很慢。为了加速，可以为深层目录文件创建一个软链接。另外，文件系统提供dentry缓存机制加快解析。如果最近访问过某个文件或目录，就会把该文件对应的目录项缓存在内存中，不会逐目录查找。
其次，open第二个参数需要指定文件打开以后的访问模式，包括只读，只写和读写。如果文件不存在，可以用O_CREAT指定创建一个文件，还可以指定是否要追加写、截断等。O_EXCL和O_CREAT合用，表示如果文件本身存在就返回创建失败。O_TRUNC表示如果文件存在就把长度截断到0。O_APPEND表示文件打开后总是往尾部追加写。
创建一个文件的流程包括：路径解析（已经提到），检查该目录是否有权限创建文件，为文件分配inode结构，将文件的名字和inode号更新到目录中。如果需要写入还要分配数据块并更新元数据索引。如果是direct io或者同步写还需要将数据块落盘。
open第三个参数代表权限。在创建文件的模式下，第三个参数指定了文件的访问权限，包括文件创建者，所在组和其他成员的读取，写入，执行权限。
read和write系统调用负责文件的读写。均有三个参数。第一个参数是文件描述符，第二个是缓冲区指针，第三个是读或写的字节数。
read和write都从文件的读写指针开始，可以通过lseek修改读写指针。lessk的三个参数是文件描述符，偏移量和偏移起始地址。偏移起始地址可以是文件开头，末尾或者当前读写指针。
https://blog.csdn.net/weixin_44698673/article/details/125729055
删除文件用unlink系统调用，参数是文件路径。之所以参数是文件路径，是因为不同的文件可能对应同一个inode，也就是硬链接。如果通过文件描述符找到文件，就不知道具体想要删除哪一个硬链接。当删除最后一个硬链接的时候，文件的空间才会真正释放。删除文件的过程包括从目录中删除该文件的表项，减少硬链接计数。如果是最后一个硬链接，就调用具体文件系统的删除操作。
删除目录用rmdir系统调用，参数是目录路径，因为打开目录不会返回一个整数形式的描述符。只能删除空目录，目录不空就要递归删除。
截断文件是指定一个长度，如果文件超过这个长度就把多余部分删除，如果不足这个长度就用\0填充到这个长度。truncate和ftruncate系统调用可以截断。前者的参数是路径名和长度，后者的参数是文件描述符和长度。
区别：truncate之前无需先打开文件，ftruncate需要在打开文件的情况下截断。truncate可能会收到符号链接攻击，意思是高权限的文件被链接到低权限的链接，如果文件系统不完善，那么低权限的用户可能可以操作高权限的文件。
文件在进程中的形式
进程通过open可以打开一个文件，打开以后通过文件描述符操作这个文件。
在linux中，进程是task_struct结构体表示的，其中file_struct成员存放了进程打开文件的信息。
file_struct中的主要成员有：引用计数、读写锁，文件描述符表。
引用计数是说，子进程会共享父进程的file_struct，不同线程也会共享file_struct。因此还需要读写锁来避免数据竞争。
文件描述符表有两种形式，一种是fd_array数组，还有一种是fdt链表。当打开的文件不太多时，用数组（可以随机访问）。打开比较多时用链表。文件描述符实际上就是数组下标或链表中的索引。每一项指向一个struct file结构体，保存了文件在当前进程中的使用情况。主要成员有文件的inode指针，page cache指针（叫做address_space），vfsmount指针，dentry指针，操作函数集指针。这些是打开这一个文件的所有file结构共享的。此外还有文件的读写指针f_pos，访问模式（只读只写还是读写），权限等。
文件的存储
文件在盘上的占用形式：连续存放和非连续存放
对于HDD来说，最好连续访问数据以减少寻道时间。因此数据在盘上最好是连续存放的。
连续存放方式是指文件在磁盘上连续存放，这样只需要在inode中指定文件的起始地址和长度就可以表示文件的存放。优点在于访问效率高，并且不需要索引。缺点在于不方便扩展和存在碎片。 不方便扩展：如果文件的末尾以后已经被占用，则没有办法继续申请连续的空间，必须要将文件整个搬移到新的更大的连续空间。 碎片：文件中的某些块不再使用，或者文件被删除，就会在磁盘上留下空缺。那么有可能磁盘本来有足够的空间，但是放不下大于空缺的数据。因此需要频繁整理紧凑空间 因此需要引入非连续存放方式。
• 链表方式 采用链表的方式就可以充分利用空间，不会产生碎片，还可以动态扩展文件大小。分为隐式链接和显式链接。缺点：只要某个数据块损坏或者链接表损坏，就会导致文件丢失 ◦ 隐式链接：inode保存第一个数据块和最后一个数据块的地址，每一个数据块保存下一个数据块的地址。优点：没有链接表开销；缺点：一个数据块损坏以后整个文件丢失，必须按照顺序读取目标数据块之前的每一个数据块 ◦ 显式链接：inode保存首位数据块的地址，同时将每个数据块中的指针放在一个全局链接表中。链接表放在内存中，查询快速。缺点：链接表占用内存开销大，显式链接也要顺序扫描表 • 索引方式 ◦ 为每个文件创建索引数据，存放每个数据块的位置。inode指向索引数据块。 ▪ 优点：没有碎片，也可以扩展文件，还可以快速定位数据块而不是顺序读取。 ▪ 缺点：索引额外占用空间，索引块的大小限制了整个文件的大小，索引块损坏导致文件丢失 ◦ 链式索引 ▪ 允许存在多个索引块，以链表组织 • 优点：不限制文件大小 • 缺点：指针损坏导致文件丢失 ◦ 多级索引块 ▪ 索引块存放二级索引的地址，甚至可以有更多级别索引。
ext2/3中结合了直接索引和间接索引：inode中直接存放一些数据块的索引，多余的采用间接索引，更多的采用二级或高级索引。因此对于小文件可以直接查找，大文件可以多级索引。
ext4引入了extent机制，一个extent表示连续的数据块的集合而不是单独的地址。利用extent可以减少索引条目。如果一个大文件完全是顺序的，只需要一个extent就可以表示。
ext4中extent组织成树形结构。文件更倾向于连续存储合并extent。
空闲空间的管理
在为文件分配地址时需要快速找到可用的空闲空间。常用的方法有空闲表，空闲链表和位图
• 空闲表 ◦ 建立一张全局空闲表，每一个条目包括空闲空间的起始位置和空闲块数量，通过顺序扫描找到足够的空闲空间，适合分配连续空间 ◦ 如果有很多细碎的空闲空间，性能会变差，表也会变大。 • 空闲链表 ◦ 每一个空闲块指向下一个空闲块，需要分配时从链头上取下足够数量的块 ◦ 不适合连续分配，大型文件系统中链表会很大 • 位图 ◦ 用位图表示每一个块的使用情况。 ◦ linux中用位图管理数据空闲块和inode空闲块 • 成组链接 ◦ 将空闲块分成若干个组，每一组指向下一组的头部，这样可以减少链接表的大小。并且可以在组内分配连续空间，类似于ext4里面的extent。本来文件系统管理数据需要记录所有数据块的索引，但是如果数据块是连续的就只需要记录起始位置和长度，那么就减少了索引量。
符号链接（软链接）和硬链接
符号链接（软链接）类似于快捷方式，有自己的inode，其中内联地存放链接指向文件的路径。软链接可以对文件或目录创建，可以跨文件系统创建。
硬链接没有自己的inode，或者说所有的硬链接共享一个inode，只是路径和文件名不一样。也就是说硬链接实际上是所在目录中的一个条目。inode中保存硬链接计数，只有删除最后一个硬链接的时候才真正删除文件。
不能跨文件系统建立硬链接，因为不同文件系统的inode号是冲突的。
每个目录本身包含自己的硬链接. 和父目录的硬链接..，从而方便用户引用当前目录和导航到上一级。但是不能人为对目录建立硬链接，为了避免循环引用导致目录无法删除。
文件系统的结构
EXT系列文件系统
https://www.cnblogs.com/f-ck-need-u/p/7016077.html
ext系列文件系统将盘上逻辑地址空间划分为多个块组。
为了在块组中分配数据块，每个块组有自己的数据块位图，用于表示数据块是否空闲
为了索引一个文件，文件的inode会存放每个数据块的地址。这是直接索引，此外还会有间接索引
一个inode的大小比块小。因此一个块可以存多个inode。
每个块组会管理一定序号的inode，inode的位置存放在该块组的inode表中。
为了分配inode号，每个块组还有inode位图，用于记录该块组中的空闲inode号。
之所以要划分块组，是因为如果不划分块组，就会导致块位图、inode位图和inode表过大，不方便查询。
块组的元数据保存在块组描述符GD中，包括一个块组管理块的范围、块位图、inode位图、inode表的地址、空闲块和inode数量。
每个块组的GD组织成一个全局的块组描述符表GDT。还有一个保留GDT为了防止扩容以后块组描述符放不下。
文件系统的全局元数据除了块组描述符以外，还有超级块，包含inode总数、块总数、块组总数等。
全局元数据非常重要，损坏会导致全盘数据丢失。早期存放在每个块组中，后来采用稀疏技术，就是只写入0、1和其他序号为3，5，7的幂次的块组中。只有前面的元数据无法访问才会读取后面的副本。
inode结构中没有文件名和inode号。要查询一个inode，实际上是先从目录文件或者dentry中通过文件名查询到对应的inode号，每个块组管理哪些inode号在格式化的时候就已经确定，可以直接计算出所在块组。根据块组中inode表查询到inode位置。
有一些文件比较特殊，如软链接（符号链接）、套接字、设备文件等只需要inode本身就可以内联地存放，所以不占用数据块。
ext4文件系统引入了extent机制，一个extent是地址连续的数据块集合，索引这些数据块时只需要所以extent起始地址和偏移量。减少了元数据中索引的大小。
文件系统的崩溃一致性
ext3中引入了日志机制，将盘划分为数据区，元数据区和日志区。每次存储数据时，将数据块落盘后，再将元数据写入日志区并提交，最后再将元数据转写到盘上。 断电时机：写数据时断电 - 根本没有更新元数据，相当于没有写入 写日志时断电 - 没有提交，因此不会恢复 日志提交后断电 - 可以重放日志恢复
EXT系列文件系统中文件的操作
读取：读取某个文件之前需要确定inode号。如果内存中有相应的dentry缓存，就会从dentry缓存中查询，否则就要通过读取目录文件逐级查询。
读取目录文件：找到块组描述符表（开机时已经加载到内存中），找到inode表并查询根目录的inode（inode号为2）所在的数据块。从数据块中取出根目录的inode并查询下一级目录的inode号，并再查表。直到查到文件所在目录，就从inode表中找到文件inode，并定位数据块，再将数据块复制到用户空间。当然，每次查询的时候都会检查inode中的权限，看是否有权限读取。
删除：
删除普通文件：找到文件所在inode和数据块，如果硬链接计数大于1就减少硬链接计数，否则才真正删除文件。接下来从inode表中将inode的表项删除，并且更新inode map，再从所在目录数据块中删除该文件条目，最后在块位图bmap中更新该文件数据块所在位，设置为可用。
删除目录文件：需要首先递归删除目录下所有文件和目录，目录空后再删除该目录。首先在inode表中删除目录文件的inode条目，然后更新imap和bmap将目录占用的inode和数据块设置为可用，最后在该目录所在目录文件中删除目录条目。
重命名：不会更改inode号
同目录内重命名（仅修改文件名）：找到所在目录的数据块并更新条目。如果有冲突，会让用户选择是否覆盖，覆盖的过程就是先删除冲突项，然后重命名。
非同目录内重命名（修改路径）：修改目标目录的数据块，添加该文件记录，然后从源目录删除文件记录。
将文件移动到不同文件系统则需要先复制再删除。
存储文件：
读取GDT，找到有空闲inode号的块组，并且查imap分配一个inode号，在bmap中查空闲块并位文件的inode分配，再把空闲块地址写入inode表中。最后查bmap表分配数据块并填充数据块、更新inode中索引。只能按4K粒度分配
EXT系列文件系统的缺点
ext系列文件系统本身经过很多年，已经非常可靠和稳定了，只是说相比于一些新的文件系统，他缺少一些更新的功能，比如数据去重，数据压缩、加密和快照等。
F2FS文件系统
https://www.cnblogs.com/Linux-tech/p/12961293.html
F2FS文件系统的优缺点
缺点：作为一种日志结构文件系统，必须要经常垃圾回收，这样带来写放大。
冷热温机制比较简单，是静态定义的。比如对于冷数据，就是通过后缀名来判断，或者是GC以后的数据就是冷数据。那么可以尝试设计一些更准确的冷热区分算法。另外，也可以让用户区指定一个冷热参数。
Linux的存储软件栈
应用程序 - VFS - 文件系统 - 块层 - 设备驱动 - HDD/SSD
Page Cache
Linux上会将文件先读入内存，作为page cache映射到进程的虚拟地址空间。page cache就是struct page中的address_space结构体。每个文件会在内核中只有一份page cache。但是可以有多个进程中的struct file指向。
page cache不仅是缓存基于文件的数据页，还用于元数据的缓存。不同的page有不同的操作函数，定义在address_space_operations操作集中。
page cache的数据结构是基数树，用于快速定位某些状态，如脏的页。基数树是一种利用前缀索引快速检索的数据结构，检索复杂度是Ok，k是所有字符串最大长度
使用page cache和不使用page cache有什么区别
使用page cache的就是buffer io，不使用page cache的是direct io。他们之间的区别有几点。第一是buffer io的读写性能更好，因为可以在内存中命中，而direct io每次都要访存。第二是buffer io需要占用一定内存存放page cache，但是direct io不需要。第三个是buffer io 不用管理一致性问题和崩溃恢复问题，因为page cache已经实现了这个机制，但是direct io需要自己管理。buffer io适合大多数场景，但是数据库等需要精细控制IO或者是已经实现了自己的缓存的应用就可以跳过page cache。
使用direct IO需要注意什么
首先需要手动管理数据的一致性，因为direct io只是保证数据落盘，但不会保证元数据都落盘，需要频繁调用fsync保证所有的元数据都落盘。其次还需要自己实现崩溃恢复，出错重发等机制，然后为了保证性能还需要自己实现批量写入和预读的策略，自己实现读写缓冲区。最后还需要把写入数据块的大小和文件系统数据块的大小对齐。
使用direct io需要在打开文件的时候设置O_DIRECT标志。
Page Cache的一致性与可靠性
更新page cache上的页就成了脏页。一方面操作系统内核线程定期写回脏页，另一方面用户可以主动调用fsync和sync同步某个文件和整个文件系统的数据。最后内存压力大时会导致回收文件页（丢弃或回写）
3个系统调用：fsync：将fd文件的所有脏数据和脏元数据写回磁盘；fdatasync：将fd文件所有的脏数据和必要的元数据写回磁盘。必要的元数据是对访问文件有关键作用的元数据，比如文件大小。但是文件修改时间就不写回。sync：将整个文件系统的脏数据和脏元数据写回磁盘。
写回和写穿
page cache就是写回模式，direct io就是写穿模式。上面比较过优缺点
写回实现机制
每个存储设备会有一个脏文件链表，需要回写时会遍历这个链表确定需要回写的文件。文件的struct page中有脏页标志。
当write等系统调用修改文件的内容后，内核会调用set_page_dirty将对应脏页置脏。
目录的存储
文件名与inode的映射关系存储在目录文件的目录项中。目录文件就由该目录下目录或文件的目录项组成，目录项在目录文件中组织成哈希表从而便于查询。为了避免逐级从目录文件中查询，操作系统会将最近读取到的目录项缓存在dentry中。dentry是内存中的结构，用于缓存文件名到inode之间的映射，避免逐级查找。
文件IO
缓冲和非缓冲IO
缓冲IO是指利用标准库的缓冲区加速文件访问并累积写回，为了减少系统调用次数。适合大量小规模的数据传输，可以累积写回减少系统调用次数。 非缓冲IO是每次都用系统调用访问文件，可以及时更新。适合数据库等一致性较高的场景。
buffer io和direct io
已经说过
阻塞、非阻塞、同步、异步
阻塞io是指一个进程发起IO请求后就挂起等待，直到IO请求返回。
非阻塞IO是指一个进程发起IO请求后，如果不能立刻得到IO结果，就返回错误或提示，并执行其他任务。择机重新发起IO。
同步io是指进程发起IO后必须等待IO操作完成才能执行后续代码，阻塞和非阻塞IO都可以是同步的。阻塞的同步IO就是等待，非阻塞的同步IO就是轮询或者其他IO多路复用技术。关键在于进程是否需要等待IO的结果。
异步io就是允许进程发起io后立即执行其他任务，而不用等待IO结果。IO完成后内核会通过回调函数或者信号机制通知进程。
无论是阻塞、非阻塞轮询还是非阻塞多路复用都是同步的，因为他们接下来的操作依赖于IO的结果，在数据从内核拷贝到用户态的过程中都要等待。
真正的异步io是内核数据准备好之后从内核态拷贝到用户态，都不用等待。到了用户态以后再通知进程。
网络系统
网络系统是操作系统中负责管理网络通信、协议处理和资源共享的模块，通过分层架构实现对物理网络设备的抽象化，并为上层提供统一的接口。
零拷贝技术
传统的网络工作方式：硬盘读取数据 - （DMA）- 内核缓冲区 - 用户缓冲区 - 内核socket缓冲区 - （DMA）- 网卡
2次系统调用（read、write），4次用户态内核态切换（1个系统调用2次），4次数据拷贝（硬盘到内核读缓冲区，读缓冲区到用户缓冲区，用户缓冲区到socket缓冲区，socket缓冲区到网卡）。
通过零拷贝技术优化：减少系统调用次数 - 减少内核态切换和不使用用户缓冲区 - 减少内存拷贝次数。
mmap+write实现三次拷贝
mmap将内核缓冲区数据映射到用户空间，不需要拷贝，应用程序将数据从内核缓冲区拷贝到socket缓冲区，然后再拷贝到网卡缓冲区。
4次内核态切换（一次mmap一次write），拷贝三次（硬盘 - 内核缓冲区 - socket缓冲区 - 网卡）
sendfile
一次系统调用，直接将内核缓冲区复制到socket缓冲区。
2次内核态切换（一次sendfile），拷贝三次
SG-DMA零拷贝
如果网卡支持聚散DMA技术，可以直接用DMA将磁盘数据复制到内核缓冲区，再用SGDMA将内核缓冲区数据拷贝到网卡。0拷贝是指不需要CPU来拷贝，实际上发生了2次数据拷贝。
Page Cache也有预读失效和缓存污染的问题
凡是cache就有预读失效和缓存污染，因此page cache不适合大文件的传输，而只适合热点小文件。
高并发大文件传输应该使用异步IO+直接IO。工作模式为：前半部分，内核向磁盘发起读请求，但是不等待数据就位就返回。后半部分，当内核将磁盘中的数据拷贝到进程用户缓冲区中，通知进程处理。
直接IO的应用场景有：应用程序自己实现了缓存、大文件传输（无法命中，还会挤占缓存空间）。
直接IO无法享受page cache的优化：需要自己调度合并IO请求以减少磁盘寻道
总之，传输小文件应该使用零拷贝技术、大文件用异步IO+直接IO
IO多路复用
基本socket模型
网络通信实际上是进程通信中的跨主机进程通信。
对于TCP socket，服务端需要先调用socket函数创建一个IPv4以及TCP协议的socket，再调用bind函数将器绑定到IP地址和端口号上。
绑定IP地址：一台机器可能有多个网卡，每个网卡都有对应IP地址。内核收到指定网卡的数据包才会转发给进程，绑定端口：指定通信进程
绑定IP地址和端口后，调用listen监听。因此可以使用netstat命令查看指定端口有无监听判断网络服务是否启动。
服务端调用accept获取客户端连接，并从全连接队列中拿出一个已经完成三次握手的socket用于应用程序的网络传输。注意，监听的socket和已连接socket是不同的。
socket文件的inode指向内核中的socket结构，结构体中有两个队列：发送队列和接收队列。队列中保存的是struct sk_buff，用链表的形式串起来。
为了减少数据拷贝，网络栈各层次都用一个sk_buff结构描述数据包。通过调整结构体中data的指针剥离和增加各级协议的首部。
多进程模型
服务器连接数受文件描述符数量和系统内存的限制。
如果服务器为每个客户端都分配一个进程处理请求，则进程数量越多，占用资源也越多，并且切换进程开销大。
多线程模型
为每个连接分配一个线程服务请求。线程的频繁创建和销毁占用系统开销，虽然可以采用线程池的方法避免频繁创建和销毁线程，但创建线程数量过多，服务器仍然服务不过来。
IO多路复用
用一个进程监控多个IO事件（网络套接字、文件描述符等），从而以更低的资源消耗实现高并发处理。
select/poll
select实现多路复用的方式是将需要监听的文件描述符放在一个集合中，调用select函数将集合拷贝入内核，内核每次扫描所有文件描述符，当某个文件描述符上有IO事件则标记该描述符。扫描完后将文件描述符集合拷贝回用户态，用户态接着遍历文件描述符集合找出有标记的并处理。
因此，select需要2次遍历，2次拷贝文件描述符集合。
select使用固定长度位图表示文件描述符集合，因此受到位图长度限制。
poll采用链表形式的动态数组表示文件描述符集合，能存更多文件描述符，但是还收到系统文件描述符个数限制。
但poll和select的原理几乎相同，因此开销还是很大。
epoll
epoll在内核中维护了一颗红黑树，用来跟踪进程所有待检测的文件描述符。进程新增监控socket时只需要传入这一个socket，而不需要复制整个集合。
epoll使用事件驱动机制，维护了一个记录就绪IO链表。当某个socket或文件描述符上有IO事件发生时，通过回调函数将其加入就绪事件链表中。用户调用epoll_wait时只会返回有IO事件的文件描述符，而不需要遍历。
使用epoll：epoll_create创建epoll对象，epoll_ctl将待检测的socket传入红黑树，epoll_wait得到有IO事件的文件描述符。
因此epoll可以解决c10k问题，因为监听socket数量增加时不会大幅降低性能。
边缘触发和水平触发
边缘触发是指当监控的文件描述符上有IO事件时，epoll_wait只会返回fd一次，因此需要保证一次性处理完IO事件，例如将数据从内核缓冲区读取完。
水平触发是指监控的文件描述符上有IO事件时，每次epoll_wait都会返回该fd，直到处理完IO事件。
边缘触发适用于高并发、高性能系统，能够减少重复通知，但是开发时需要小心事件丢失。并且边缘触发只能用于非阻塞IO，以避免没有一次性处理完数据导致事件丢失。
例如使用阻塞IO读取数据，
- 客户端发送 2000 字节数据，触发一次 EPOLLIN 事件。
- 服务端调用 read 读取 1024 字节（缓冲区剩余 1024 字节）。
- 由于未处理完数据且使用阻塞 I/O，线程将阻塞在下一个 read 调用上。
后果： • 剩余字节数据滞留在内核缓冲区，但 ET 模式不会再次触发 EPOLLIN 事件。当前线程阻塞，但其他的线程也无法感知该fd。 如果循环调用read，可能会使得缓冲区读完后read卡在空缓冲区上。
水平触发适用于并发量较低，需要快速调试，容错性强的应用，容易实现。但是性能不如边缘触发，因为存在不必要的事件通知、每次通知都存在上下文切换开销。
Reactor模式
reactor模式是对IO多路复用的封装，是一种高性能网络模式。
reactor模式包含3种组件：reactor，acceptor和handler
reactor负责监听IO事件（epoll监控文件描述符）并分发给对应处理器
acceptor负责接收新连接并注册到reactor的监控列表中
handler负责处理具体业务逻辑
工作流程是应用程序将感兴趣的事件，如某些文件描述符上的读、写等注册到reactor；reactor监听事件；事件触发后reactor根据事件类型分发给响应handler，handler通过非阻塞IO执行业务逻辑，或者委派给某个线程池中线程执行，完成后重新注册事件（边缘触发：如有剩余数据则可以下一次事件到来时继续处理；水平出发：可以明确事件监听范围，如从读切换到写，减少无效事件通知）
单线程reactor模型：三种组件的功能在一个线程中执行，因此没有多线程竞争问题，避免线程切换。但是无法利用多核CPU，并且线程崩溃会导致服务不可用。适合客户端数量少，业务快速的场景。
多线程reactor模型：主线程负责事件的监听与分发，业务逻辑由线程池中线程异步处理。可以利用多核CPU处理计算密集型任务，使用线程池可以减少创建销毁线程的开销。但是主线程可能成为瓶颈，多线程存在数据竞争。适用客户端数量适中，业务处理较长的场景。
主从reactor模型：引入负责连接的主reactor和多个负责IO的子reactor，主reactor将连接分配到子reactor中由子reactor负责后续IO事件。可以减少单点压力，并且可以动态调整子reactor数量以适应负载。但是复杂度高，适用于高并发系统。
Proreact模式
reactor是非阻塞同步网络模式，每次感知到由IO事件就需要应用主动调用read读取，因此是同步的，基于待完成的IO事件
proreact是异步网络模式，发起异步读写请求时需要传入数据缓冲区的地址，内核会处理IO事件并将结果通知给应用。是异步的，基于已完成的IO事件。
linux不支持真正的异步io，windows支持。
负载均衡问题
多个节点如何分配客户端请求。
引入一个中间的负载均衡层，负责分配请求。
对于每个节点存储数据相同的情况，可以使用加权轮询算法，即根据节点的硬件配置设置权值，将请求轮流转发给各节点。
对于分布式系统，每个节点存储的数据不同。使用哈希算法则可以根据key定位到数据所在节点。但是不便于系统扩容和节点故障的情况，因为会破坏哈希映射至，导致大量数据迁移。
一致性哈希算法将数据与节点映射到同一个哈希环上，数据根据哈希值定位到环上位置后，沿顺时针找到最近的节点作为归属，则增加节点只影响顺时针相邻的后继节点，从而减少数据迁移量。
但是一致性哈希算法不能保证节点在哈希环上均匀分布。可以引入虚拟节点机制将物理节点映射成多个虚拟节点分散到哈希环的不同位置。因为物理节点直接计算出的哈希值可能是很集中的，但可以对每个物理节点计算多个虚拟哈希值。
虚拟节点优点在于：1. 解决物理节点分布不均2. 高性能节点可以分配更多虚拟节点3.移除某个物理节点时数据均匀迁移到不同其他节点，避免单一节点承受过多压力，分散影响。
进程管理
进程，线程，协程
进程是操作系统资源调度的基本单位，拥有自己的资源，包括内存地址空间，堆和栈。优点：拥有自己的地址空间，稳定性和安全性（无法访问其他进程的地址空间和堆栈资源）较高。缺点：切换进程的开销较大，需要保存上下文，进程之间通信比较复杂
线程是CPU调度的基本单位，和同一进程中的其他线程共享资源。优点：创建线程资源开销小，线程之间通信方便（可以直接共享内存），切换线程方便（只需要保存线程级别的上下文，不需要保存进程状态）。缺点：线程之间存在数据竞争的问题，需要同步和互斥机制解决。
协程是一种轻量级的用户态线程，调度由用户程序控制，不需要内核参与。因此没有上下文切换开销，适合大量并发任务。缺点就是实现比较复杂。
Linux用task_struct管理进程
https://zhuanlan.zhihu.com/p/457403125
每个进程由进程控制块管理，在Linux中进程控制块是task_struct结构体。
其中有一个指针叫做stack，指向内核栈。
与线程有关的资源在thread_struct中，比如寄存器状态等，具体和硬件架构有关。
一个进程崩溃不会影响其他进程
进程之间具有隔离性，一个进程崩溃不会影响其他进程的地址空间、网络连接等资源。
什么是分配给进程的资源
包括虚拟内存，比如代码段，全局变量静态变量区域，堆文件描述符，还有信号量，网络套接字等。
为什么要在进程之下设计线程
当一个软件的功能比较复杂的时候，需要一种程序运行的实体，既能并发执行，又能够方便的相互通信。如果单独采用进程的话，一个进程只能同步执行一系列操作，没办法并发。采用多个进程的话，进程之间通信不方便，并且消耗系统资源多。因此在一个进程下面设计线程，能够满足并发执行和通信方便的需要。
多线程和单线程的比较
多线程可以并发或者并行处理多个任务，提高执行效率，充分利用CPU计算能力。但是可能导致数据竞争和死锁，并且会占用更多CPU和内存资源。 如果线程过多，总体上占用的系统资源（栈，程序计数器，寄存器状态，线程控制块等）也会上升。并且C++中一个线程崩溃还会导致所属的进程崩溃。
C++中线程崩溃导致进程崩溃
如果某个线程非法访问了地址，例如访问了只读内存、不存在的地址或者没有权限的地址（内核地址空间），那么会产生segmentation fault，导致进程崩溃。这是因为线程共享地址空间，出现非法访问可能会导致内存的不确定性，进而影响其他线程，因此会将进程崩溃。
具体是发现非法访问内存后，内核会给进程发送kill信号
进程切换和线程切换
进程切换的开销比线程切换要大。进程切换时需要保存虚拟地址空间里的信息，比如全局变量，堆，栈，文件描述符，等等用户空间的资源，还要保存内核态的栈，寄存器(CPU寄存器、程序计数器)。这些信息保存在进程控制块内。然后我们取出另一个进程的进程控制块，并且恢复这个进程的上下文。取出PCB的过程可能涉及缺页。
如果两个线程是同一个进程的，那线程切换比进程切换简单，只需要保存上一个线程的栈，程序计数器还有其他寄存器。地址空间是共享的。如果属于不同进程那就和进程切换一样。
进程的状态
运行态，就绪态，阻塞态，创建态和结束态。如果大量进程处于阻塞状态就会交换到外存，那么就是挂起态。挂起有阻塞挂起和就绪挂起。
进程的控制
进程的控制信息保存在PCB结构里，包括进程的id，用户的id，进程的状态，进程的资源比如地址空间mmstruct，文件描述符等，还有CPU寄存器的值（切换上下文的时候保存）。
相同状态的PCB组织成链表。形成各种队列，比如就绪队列，阻塞队列
创建进程：首先创建一个PCB结构，并且填入进程相关信息，比如pid，用户和组。然后分配必须资源，如地址空间。最后插入到就绪队列等待调度
阻塞进程：首先从运行队列中找到PCB，然后保存上下文，并且修改状态为阻塞，最后插入阻塞队列
唤醒进程：首先从阻塞队列找到PCB，然后修改状态为就绪，最后插入就绪队列
终止进程：首先从队列中找到PCB，如果正在运行就停止运行并调度其他的进程。然后检查是否有子进程并将子进程转移给1号进程收养，再释放进程的资源，最后删除PCB。
进程的终止有自己正常终止（比如main函数返回，或者调用exit），也可能异常终止（如被kill掉。有可能是程序逻辑错误或者访问非法内存，也可能是被手动kill掉）。
父进程终止：子进程变成孤儿进程，被1号进程收养。子进程终止：将资源归还给父进程。
进程阻塞一般是去等待某些IO事件，或者等待锁和子进程终止。注意时间片耗尽不会导致阻塞，而是导致进入就绪队列。
进程的用户态和内核态
用户态：是CPU运行用户程序的一种模式，权限较低，不能直接访问硬件资源。用户态负责运行用户应用程序。
内核态：是CPU运行操作系统内核的一种模式，拥有最高权限，可以直接访问硬件资源。内核态负责管理系统的核心功能，如进程调度、内存管理、驱动等。
之所以要区分内核态和用户态，是为了保证操作系统的隔离性。一方面，恶意的用户应用可能攻击操作系统，正常的应用也可能会故障。如果这些应用能够执行特权指令可能会导致整个系统的崩溃。另一方面，把内核态和应用态区分开也可以方便用户编程，不用考虑底层的实现和不同硬件的差异。只需要使用操作系统提供的抽象。
用户态切换到内核态的方式有系统调用、中断、异常。只有系统调用是用户主动陷入内核的。
系统调用：注意系统调用中不涉及进程切换，始终是同一个进程，只是状态变了。系统调用属于一种陷阱
进程的上下文包括CPU中寄存器的值，进程的状态以及栈的内容。linux中进程的上下文保存在task struct结构体中。但是在特权模式切换的时候只需要保存寄存器级别的上下文，比如程序计数器，寄存器状态和栈指针，因为系统调用以后还是同一个进程，并没有切换进程。
- 用户态进程调用某个系统调用函数
- 系统调用函数将参数和对应的系统调用号写入特定的寄存器，并执行syscall指令触发CPU状态切换，跳转到内核入口函数
- 把用户态的上下文压入内核栈中保存，比如pt regs结构体
- 设置内核栈指针，并从寄存器取得系统调用号并调用相应的系统调用处理函数，并将参数从寄存器传递给该函数
- 内核态任务执行完后将返回结果存入寄存器中并通过sysret指令回到用户态。这个过程中还会恢复用户态的上下文。
系统调用由应用程序主动触发，完成服务后返回原执行流。
异常和中断由程序错误或外部事件强制触发，可能终止原执行流
异常：异常是程序运行中出现的非预期情况或错误。比如程序要执行一个非法操作（除以0），或者访问的页面不在内存中。异常发生后会被操作系统捕获，并执行异常处理函数。
发生异常同样会切换到内核态。对于page fault会从外存中调入页面，对于除以0等错误，会直接杀死进程或重启进程。
中断就是CPU停止执行当前任务，去处理其他的事情，处理完再返回当前任务。
中断分为硬中断和软中断。硬中断是由于外部硬件设备的变化导致的中断，分为可屏蔽和不可屏蔽的。可屏蔽的中断通常是一些设备的IO事件，比如敲键盘，点鼠标，还有可能是打印机缺页等。这些中断不处理不会导致操作系统崩溃，所以可以屏蔽。不可屏蔽中断一般是一些致命错误，比如突然断电等。
软中断是软件触发的中断机制，不直接由硬件产生。主要用于延迟处理，将不需要立即执行的任务安排到稍后执行。
为了避免中断处理程序过长，将中断分为上半部和下半部。上半部一般是硬件触发的硬中断，用来快速处理和硬件紧密相关或者时间敏感的请求，下半部一般是内核触发的软中断，以内核线程的方式延迟处理上半部未完成的工作。除了下半部外，一些内核自定义事件也属于软中断，比如内核调度、RCU锁等
硬中断是外部硬件设备触发的，是异步随机发生的，可以设置优先级，有些可以屏蔽，要求尽快响应完成，支持中断嵌套，在中断上下文中执行。
软中断是内部软件指令触发的，是同步触发的，没有优先级，不可以屏蔽，可以延迟执行，可重入（允许被硬中断抢占），在进程上下文或内核线程中执行。
软中断的调度时机一般是某个硬中断退出时，或在cpu负载较低时唤醒ksoftirqd线程处理软中断。
中断通常是异步的，陷阱通常是同步的。意思是中断通常是CPU执行某些任务时被打断。而陷阱是CPU主动在已知的地方发生
中断的过程首先是接收到中断信号，如果没有屏蔽该中断，就保存当前现场，包括寄存器和栈指针，程序计数器等。接着根据中断向量号找到对应的中断处理函数，并切换到内核态执行中断处理函数。中断处理结束后再恢复上下文，并切换回用户态接着执行之前的指令。
正常状态下中断处理并不切换进程。
用户线程和内核线程
https://www.cnblogs.com/FengZeng666/p/14219477.html
用户线程就是有用户态应用程序或者函数库管理的线程，这类线程只运行在用户态，操作系统是看不见的。优点：不需要切换内核模式，节省开销；允许应用自行调度，更加灵活；缺点：操作系统只能看到进程，所以一个用户线程阻塞会导致进程阻塞；一个进程中的用户线程也没办法利用不同的CPU并行执行；一个线程不可能抢占另一个线程，因为没有这个特权；时间片是分配给进程的，所以用户线程需要共享时间片，一个线程得到的时间片较少。
内核线程是操作系统直接支持管理的，优点：一个线程阻塞了，还可以调度别的线程运行；同一个进程的不同线程可以在不同CPU并行执行；得到的时间片比较多。缺点：线程调度需要切换内核态；
线程的映射：用户态线程在系统调用等与内核有关的操作需要内核线程协助。用户线程和内核线程的映射有多对一，一对一，多对多。
多对一就是用一个内核线程服务多个用户线程，那么其他想进入内核态的用户线程就被堵塞了。一对一是每个用户态线程都可以映射到一个内核线程。但是创建内核线程会有一定开销。Linux和windows都是一对一的。
多对多就是用少量的内核线程服务大量的用户线程，可以减轻阻塞其他用户线程，也可以减少占用资源。但是管理复杂。
进程间通信
进程通过虚拟地址空间实现了隔离性，因此进程之间的协作需要专门的通信机制。
宏内核进程间通信有管道、消息队列、共享内存、信号量、信号和socket机制。 • 管道：字节流、两个进程、单向、匿名和命名 • 消息队列：消息体、多个进程、单向或双向 • 共享内存：内存区间、多进程、单向或双向 • 信号量：计数器、多进程、单向或双向、同步和互斥 • 信号：事件编号、多进程、单向 • 套接字：数据报文、两个进程、单向或双向、网络栈
管道
管道就是一个单向队列，一端发送一端接收。
有匿名管道和命名管道。 • 匿名管道就是bash命令中的竖线，只允许临时将前面的输出传递给后面的输入。 • 命名管道需要用mkfifo创建，将数据写入命名管道后终端会阻塞，直到另一端被读出。 • 管道通信效率低，不适合进程之间频繁交换数据
匿名管道通过系统调用pipe，在内核中开辟了一块内存缓冲区，并返回两个文件描述符。文件描述符用于读和写缓冲区。
匿名管道只能用于父子进程和子进程之间的通信，这是因为子进程会继承父进程的文件描述符表，从而找到内核缓冲区。
命名管道通过函数mkfifo创建，可以用于不相关进程之间的通信。因为命名管道有一个具体的路径名，可以像文件一样打开。不过实际上并不存在于磁盘，而是一个内存缓冲区。
由于匿名管道和命名管道文件都是先进先出的，所以不支持lseek操作。
管道传递的是无格式的字节流。
消息队列
消息队列是一个保存在内核的消息链表，链表的每一个节点都是一个消息体。消息的发送方和接收方约定好消息体的格式，发送方将数据放在消息队列中就返回，接收方需要时去队列中取得数据，因此是非阻塞的。
消息队列的生命周期随内核，如果不释放消息队列或关闭操作系统，则消息队列一直存在。但是管道的生命周期随进程，引用管道的进程终止则管道消失。
消息队列适合频繁交换数据，因为是非阻塞的。但缺点是不适合大量数据传输，因为消息体有大小限制，并且消息队列在内核，因此有用户态和内核态之间的数据拷贝开销。管道比消息队列更快，因为不需要消息体的封装与解封装。
共享内存
管道和消息队列都要利用内核缓冲区，因此会有拷贝开销。
共享内存机制是将不同进程的虚拟地址空间映射到相同的物理地址空间。优点是不需要用户态和内核态之间的拷贝，缺点是产生数据竞争。
信号量
为了解决数据竞争引入信号量实现进程之间的互斥与同步。
信号量就是一个整形计数器，因此并不能缓存数据，而是表示能进入临界区的进程数量。
信号量有两个原子操作：P是信号量-1，V是信号量+1.P时信号量<0则P阻塞，V后信号量<=0则表示有进程需要唤醒。P和V必须成对使用。
信号量初始化为1则为互斥锁。信号量初始化为0可以实现进程同步：另一个进程执行完后再V，这是当前进程就可以P然后执行。
信号
信号用于单向的事件通知而不是数据传输。信号量也可以通知，但是需要进程主动查询信号量。信号则可以随时通知另一个进程，并且另一个进程不需要阻塞等待，内核会切换到处理函数。
Linux内核为sigint等信号提供了默认处理函数，也可以自己定义信号处理函数。还可以屏蔽信号。但是sigkill等有些信号是不能屏蔽的，因为用于终止一个进程。
信号处理并不是中断处理。因为处理信号的时机一般是进程从内核态返回用户态之前。信号处理函数一般在用户态执行，上下文会保存在用户栈上。如果信号处理函数中有系统调用则再次进入内核态。
信号与中断的联系与区别： • 联系：1. 都是异步通信机制；2. 处理完毕时返回原来的断点；3. 有些中断或信号可以屏蔽 • 区别：1.中断有优先级，信号没有优先级；2.信号处理程序在用户态运行，中断处理程序在内核态运行；3. 中断响应是即时的，而信号响应有一定延迟。
socket
不同主机进程之间通信需要跨网络。
socket创建参数有协议、报文类型。可以实现TCP、UDP和本地进程间通信。
• TCP通信过程 ◦ 服务端通过socket创建套接字，并使用bind将套接字绑定到特定的IP地址和端口上。接着调用listen监听客户端的连接请求。 ◦ 客户端通过socket创建套接字后，调用connect向服务端指定IP地址和端口发起连接请求 ◦ 服务端正在监听该端口并不超过最大连接数，则完成三次握手并建立连接。调用accept返回一个文件描述符代表与客户端的连接并开始数据交换。 ◦ 客户端断开连接则调用close，服务端读取数据时读到EOF，处理完数据后调用close表示连接关闭。 ◦ 注意：监听的socket和建立连接的socket并不一样。建立连接后双方通过read write或send recv向建立连接的socket读写数据。 • UDP通信过程 ◦ 服务端和客户端分别使用socket创建套接字并绑定到某个端口。 ◦ 通信时通过sendto和recvfrom。 ◦ 通信完成后调用close关闭套接字 • 本地socket ◦ 可以是有连接的，也可以是无连接的 ◦ 区别是在socket绑定时绑定一个本地文件系统中的路径作为地址。
线程的互斥、同步和锁、信号量
多线程同时操作竞争变量时，非原子操作和并发会导致不可预期的结果。含有竞争变量的代码是临界区，我们希望同一时间只有一个线程进入临界区。这叫做线程的互斥。
多个线程协作时，有些线程需要等待另一些线程的执行结果。因此需要保证线程之间的执行顺序，这叫做线程的同步。
主要采用锁和信号量机制实现线程之间的互斥与同步。
锁
任何进入临界区的线程必须先获得锁，然后进入。如果一个线程持有锁，其他请求锁的线程需要等待。
• 自旋锁 ◦ 属于一种互斥锁，但被锁住的线程会一直请求锁而不会阻塞，避免线程切换开销 ◦ 只能适用于非常轻量的临界区 • 无等待锁 ◦ 当线程获取不到锁的时候就阻塞，进入锁的等待队列
操作系统中常见的锁
• 互斥锁 ◦ 只有获得锁的线程能访问资源，其他线程必须等待锁的释放 ◦ 依赖于硬件的test and set原子操作实现。一个线程获取互斥锁时检查状态，如果空闲则设置上锁，如果已锁则被阻塞 • 读写锁 ◦ 支持并发读取，但只允许一个线程写入。 ◦ 有读锁时可以获取读锁，但是写者阻塞；有写锁时读写均阻塞 ◦ 两个计数器实现，一个记录读者数量，另一个记录是否有写者 • 条件变量 ◦ 多线程之间传递信号和状态信息 ◦ 用于实现阻塞互斥锁。允许线程在得不到锁的时候阻塞而不是自旋，当锁释放后可以通过条件变量唤醒一个或所有阻塞的线程。 • 信号量 ◦ 通用的同步互斥原语 ◦ 用于实现互斥：信号量代表可以同时访问临界区的线程数量，小于0时阻塞 ◦ 用于实现同步：上一个线程获取信号量并置为0，下一个线程需要等上一个线程V之后才能执行。 • 乐观锁 ◦ 并不实际加锁，认为数据冲突不常见。通过在执行临界区后检查数据版本号或者时间戳查看是否发生了数据竞争。如果发生了就回滚 ◦ 例如在线文档、git等。git就是允许用户各自修改，只有提交时冲突了才要求各自修改后提交。 ◦ 不适合经常冲突的场景，因为回滚的成本高 • 悲观锁 ◦ 通过严格的锁或信号量机制保证某一时刻只有一个线程访问临界区
生产者-消费者问题
问题描述：生产者生成数据后放在一个缓冲区，消费者从缓冲区取出数据处理，任意时刻只能有一个生产者或消费者可以访问缓冲区。
需要3个信号量：互斥信号量用于所有进程互斥进入临界区、资源信号量用于消费者进程等待生产者进程生产、空槽信号量用于生产者进程等待消费者产生空槽。
生产者进程和消费者进程都是死循环，生产者先P空槽、再P互斥、进入临界区、V互斥、V资源。消费者P资源、P互斥、进入临界区、V互斥、V空槽。
哲学家就餐问题
问题描述：5个哲学家围成圆圈，每人中间有一把叉子。哲学家必须拿起两把叉子吃饭，吃完后会放回两把叉子。不能死锁
如果只有叉子信号量，则有可能每个哲学家都拿起左手的叉子。
可以增加互斥信号量，认为拿叉子是临界操作，同一时刻只有一个哲学家拿叉子。但是并发性低。改进：为哲学家定义状态：饥饿、进餐、思考。只有两个邻居都没有进餐的时候才能进餐。因此在获取互斥量之前检查两边哲学家状态。如果不是都饥饿就阻塞。吃完后通知其他哲学家。实际上将这个互斥信号量用于同步。 还可以为哲学家编号，让偶数哲学家先拿左边叉子，奇数哲学家先拿右边叉子。
读者写者问题
问题描述：允许同时读、没有写者才能读、没有读者才能写、没有其他写者才能写。
读者优先策略：采用一个临界区互斥信号量、读者计数器和一个读者互斥信号量，临界区互斥信号量用于控制进入临界区、读者计数器用于记录当前读者数量，读者互斥信号量用于控制读者计数器的修改。 读计数代表了一个读者等待队列，当队列中有读进程时，就可以到达更多的读进程，而写进程被则阻塞在写等待信号量上，因此会导致写者饥饿。
写者优先策略：对读写进程分别计数，并对计数变量分别用mutex保护。增加写互斥信号量用于写者之间互斥，增加读等待信号量用于读者等待写者。这种方案中写者来后不允许读者进入，读者来后却允许写者堵塞读者。因此对写者有利 读写计数分别代表了两个读写等待队列。当读队列中有读进程时，可以来更多的读进程。但是来了一个写进程就会导致更多的读进程被阻塞在读等待信号量上，因此读队列会慢慢减少。反之，写队列中有写进程，则允许更多的写进程进入写队列排队，但来读进程并不能阻塞更多的写进程进入写队列。所以会导致读进程饥饿。
读写公平策略：在读者优先策略上增加一个初始为1的flag信号量。读者和写者必须先获取flag信号量再进入逻辑。这是为了写者来后可以阻塞后来的所有进程，读者来后也可以阻塞后来的写进程。 flag信号量可以让写进程阻止更多的读进程进入读队列，而读进程也可以将写进程阻塞在写等待信号量上。
伪代码： • 读者优先
| |
• 写者优先
| |
• 读写公平
| |
避免死锁
死锁就是多个线程相互等待对方释放锁。
死锁产生条件
互斥、持有等待、不可剥夺、环路等待。
互斥：多个线程不能同时访问资源
持有等待：线程在请求锁时不会释放自己的锁
不可剥夺：线程的锁在主动释放之前不能被其他线程获取
环路等待：多个线程获取资源的顺序构成环形图
排查死锁问题
Linux下可以使用pstack和gdb定位死锁。pstack可以显示每个线程的栈跟踪信息：pstack pid。查看进程下线程的函数调用过程，对比结果查看哪几个线程一直没有变化，并且被锁住的线程一般会卡在某某lock wait函数处。还可以通过gdb工具查看线程等待的互斥锁对象信息，看看是不是被对方持有。
避免发生死锁问题
破坏互斥、持有等待、不可剥夺或环路等待之一。
资源有序分配法破坏环路等待。资源有序分配是给会产生竞争的资源编号，每个线程总是按序号从小到大申请资源，这样不会导致先申请大号资源再申请小号资源带来的环路问题。
破坏互斥就是乐观锁或者将所有资源都拷贝，比如RCU机制，破坏持有等待就是要求线程一次性申请所有需要的资源，不太实际。破坏不可剥夺条件是抢占式分配，就是释放低优先级进程资源并分配给高优先级线程，要求低优先级线程稍后重新申请。
银行家算法:一个进程申请使用资源时，先试探分配所需资源，检查分配后的系统是否处于安全状态。若是则分配，否则不分配。 其中，安全状态是指系统可以通过调整进程执行顺序，即存在安全序列，使得所有进程都能获得所需资源并顺序完成。 银行家算法的缺点在于，需要事先直到进程所需的最大资源总数，但是进程的需求是变化的。并且实现复杂，需要用到很多数据结构。算法倾向保持一定余量放置不安全状态，因此会产生浪费。安全性检查耗时影响性能。不适合实时系统，因为进程会被阻塞直到找到安全序列。
进程可以创建多少个线程
进程在虚拟地址空间上创建线程，在32位系统下，因为用户态空间只有3G，所以线程的上限与线程的栈空间大小有关（线程的资源就是栈和一些寄存器）。理论上3G除以栈大小。 64位系统下，虚拟地址空间非常大，因此主要受操作系统参数或性能限制，有参数控制整个系统的最大线程个数。
设备管理
CPU通过设备控制器操作设备
每个设备都有对应的设备控制器，其中有自己的芯片、寄存器等，可以自行执行逻辑。
设备控制器有三类寄存器：数据寄存器、命令寄存器和状态寄存器。
操作系统通过写入命令寄存器，向设备发送命令；写入数据寄存器向设备输出数据；设备完成命令后将状态写入状态寄存器，CPU读取状态寄存器了解命令执行情况；CPU读取数据寄存器输入数据。
IO设备分为块设备和字符设备
块设备以数据块为数据处理单位，每个块有自己的地址。如硬盘、闪存等。
字符设备以字符为单位发送或接收字节流，字符设备不可寻址。如鼠标等。
块设备的数据传输量大，在控制器中存在数据缓冲区。读写数据时会累积读写提升性能。
CPU通过端口和内存映射与设备控制器通信。端口IO（Port IO）：每个寄存器分配一个IO端口，通过汇编指令操作。内存映射IO（MMIO）：所有的寄存器映射到内存空间中，像读写内存一样控制数据缓冲区。
端口IO：不占用内存地址空间，通信相对简单。但是需要专门指令访问。端口与处理器架构相关
MMIO：可以利用内存管理机制，更通用。但消耗一部分内存地址空间，不适合资源受限的嵌入式环境。可能导致内存与IO访问之间的冲突。
IO控制方式：轮询、中断、DMA
CPU向设备控制器发送命令后，设备将完成状态放入状态寄存器。
轮询：CPU一直查询状态寄存器，直到IO完成。简单，效率低
中断：设备完成任务后触发中断控制器，中断控制器通知CPU。不适合大量数据传输，因为频繁打断CPU。
DMA：DMA控制器在CPU不参与的情况下，自行将数据写入内存。CPU只负责一开始的指令。效率高、适合大量数据传输，但成本高，实现复杂。 ◦ CPU向DMA控制器发送指令，将某些数据读取到内存什么地方或写到某个设备的什么地方 ◦ DMA控制器将磁盘控制器发送指令，将数据从磁盘控制器的缓冲区或主机缓冲区读取到自己的缓冲区，再写入内存指定地址或设备缓冲区 ◦ DMA完成后，DMA控制器通过中断通知主机
设备驱动程序屏蔽设备控制器差异
每种设备的控制器使用模式不同，需要厂商配套驱动程序向操作系统提供统一的接口
通用块层管理不同的块设备
通用块层向上为文件系统提供访问块设备的标准接口，向下将不同的磁盘抽象成统一的块设备，提供一个管理驱动程序的框架。其次将发送给块设备的IO请求合并、重排、调度从而提高磁盘IO的效率。
块层调度算法有： • 无调度：即不对IO做任何处理，主要用于虚拟机IO，将调度交给物理机做 • FIFO • 完全公平调度 • 优先级调度 • deadline调度
缓存机制提高IO效率
为了提高文件访问效率，使用page cache、dentry缓存等机制减少访问磁盘。对于块设备还会使用数据缓冲区实现累积读写。
从键盘输入一个字符
从键盘输入一个字符，则键盘控制器会产生扫描码数据，并将其缓冲在键盘控制器的数据缓冲区中，键盘控制器向CPU发送中断请求。CPU收到中断请求后保存进程上下文，然后调用键盘的中断处理程序。键盘的中断处理程序是在安装键盘驱动程序时注册的，中断处理函数的功能是从键盘控制器的缓冲区读取扫描码，并根据扫描码找到键盘输入的字符。
如果输入的是显示字符，就将其翻译成ASCII码，并将其写入读缓冲区队列（存储从输入设备接收到的数据，因为输入可能快于处理），显示器的驱动程序定期从读缓冲区队列读取到写缓冲区队列（存储准备发送给输出设备的数据队列），将写缓冲区队列的数据写入显示器数据缓冲区，显示到屏幕上。最后恢复中断上下文，返回进程。
调度算法
操作系统中的调度主要有三类：进程调度，页面置换和磁盘调度
进程调度
作业类型
进程调度的目的是让不同的作业都能及时快速得到响应。作业可以分为长作业和短作业，CPU密集型作业和IO密集型作业。
长作业和短作业：需要CPU服务时间较长的和较短的作业。
CPU密集型作业：需大量CPU计算的作业，等待IO的情况少。
IO密集型作业：需要大量等待IO的作业，会频繁阻塞。
进程调度算法
进程调度算法类型
抢占式调度算法：可以在当前作业没有执行完的时候迫使其挂起，然后执行另一个作业
非抢占式调度算法：必须等待当前作业执行完再调度下一个作业
对于实时操作系统来说，为了保证有些高优先级任务及时得到响应，必须要抢占式调度。
凡是基于优先级的调度算法，都可以实现程抢占式的。但是基于优先级的算法都有可能导致饥饿。
常见进程调度算法
先来先服务：最简单的算法，按照先来后到的顺序将作业加入一个队列，每次从队列中取出一个作业执行。优点是实现简单，缺点是对长作业有利，对短作业不利。因为短作业会被堵在长作业之后，响应时间长。对CPU密集型的作业有利，对IO密集型的作业不利，因为IO密集型的作业堵塞后需要重新排队。
短作业优先算法：每次调度时都选择需要时间最短的作业。优点：保证短作业及时得到响应；缺点：长作业可能饥饿。
高响应比优先算法：定义一个响应比来平衡长短作业，响应比是服务时间加等待时间除以服务时间。对于长作业来说，等待时间越长会提升优先级，对于短作业来说，除了等待时间以外，服务时间越短也会提升优先级。优点：兼顾长短作业；缺点：实现较为复杂，计算有开销，需要准确预测进程的服务时间，这是有难度的。如果短作业不断到达，还是有可能导致长作业饥饿，没有考虑实时性。
时间片轮转：给每个作业分配一定时间片，时间片用完就切换下一个作业。优点：实现简单，公平。缺点：没有考虑到不同作业的优先级，时间片大小难设置（太长退化成FCFS，太短频繁切换开销大），不利于IO密集，因为时间片可能没用完就睡眠了。
高优先级作业优先：给每个作业静态分配优先级，或者基于其他指标动态分配优先级，每次调度优先级高的作业。优点：即时响应高优先级请求。缺点：低优先级请求饥饿
多级反馈队列：设置多个不同优先级的服务队列，优先级越低的队列时间片越长。每次作业加入优先级最高的队列，如果时间片用完就加入低一级队列。高级队列执行完再调度低优先级。优点：兼顾高低优先级，低优先级的服务时间也更长。缺点：低优先级还是有可能饥饿，可以定期重新加回高优先级，不利于IO密集型，因为即使时间长也可能睡眠，缺乏实时性
deadline：给每个作业分配截止时间，优先调度接近截止时间的。缺点是有可能再多个截止时间接近的作业中频繁切换，那么都超时
Linux中的进程调度器
普通任务：CFS完全公平调度器，为调度器队列中的每个进程设置一个虚拟时钟vruntime，表示进程使用了多少虚拟时间，虚拟时间与实际时间成比例，但是会根据进程的权重调整。优先级越高的进程vruntime增长越慢。每次选择vruntime最小的进程执行。使用红黑树存储队列，每次选择红黑树最左边节点（vruntime最小）
实时任务：deadline调度器、RT实时调度器，deadline调度器选择当前待处理任务中离截止期限最近的任务，红黑树管理（有序），RT调度器由两种模式，一种是先入先出队列，但是支持高优先级随时抢占。另一种是时间片先入先出，优先级相同的任务按时间片轮转。
页面替换
虚拟内存机制使得每个进程可以使用比真实内存更大的虚拟内存空间。当内存空间不够时需要将一些内存页替换到外存释放空间。
选择哪些内存页调度？
常见页面替换算法
最优替换：最好的选择就是选择最远时间内不会使用的页面替换出去，但是这是不可能实现的，因为我们不知道内存页将来的访问情况。所以这是作为一个基准衡量其他算法的性能。
先入先出：将所有内存页面按照创建时间加入队列，每次从队列尾部取出一个内存页替换出去。优点：实现简单，缺点：没有考虑到页面的最近使用情况，效果差。
LRU：最近最少使用考虑将内存页面组织成一个双向链表，将最近访问过的页面提升到链表头部，这样链表尾部就是最近没有使用过的页面。基于局部性原理，认为最近访问过的页面将来也可能再次访问。优点：考虑使用情况，命中率更高。缺点：实现复杂（需要双向链表和映射），如果IO模式不符合局部性原理就会失效（1. 预读失效：对于随机IO来说，预读加载进链表的页面不会访问2. 缓存污染：对于大文件的顺序读来说，读上来的页面看起来都是最近使用过的，但是实际上不会再次访问，并且又把缓存填满了）优化：可以和FIFO配合使用，第一次访问某个页面的时候先加入FIFO队列，用来避免一次性页面污染缓存。第二次访问再加入LRU队列。同理可以设计更多级。
时钟算法：将所有页面组织成一个环形链表，指针指向某个节点。每个节点都有一个标志位，标志最近是否访问过。需要替换的时候，指针就扫描链表中的节点，如果标志位是1就置为0，如果标志位是0就换出。优点：考虑到了最近使用情况，实现比LRU简单，因为不用双向链表只用单向，还不需要映射，并且不需要频繁的移动节点。缺点：还是有一定实现成本，并且只用一个位表示最近访问频率不精确。总体来说比较好
LFU：记录每个页面最近被访问的频率，每次替换访问频率最低的页面。优点：考虑到最近访问的次数，不会被一次性数据污染。缺点：实现还是比较复杂，和LRU差不多，并且对工作集切换的情况不友好。因为上一个工作集之前经常访问，但是现在又不访问了，就占着缓存。当前工作集的页面因为访问次数不多所以频繁替换。改进：可以随着时间推移减少每个页面的访问次数，比如除以2.这样兼顾时间局部性。
磁盘调度
目的是为了尽量减少磁头的移动，减少寻道时间
常见磁盘调度算法
先来先服务：按照IO时间顺序服务。优点：实现简单，缺点：可能导致频繁移动，性能差
最短寻道时间优先：下一次优先服务离当前磁道最近的IO。优点：性能比FCFS好，并且实现比较简单。缺点：导致远的IO饥饿
电梯调度和循环电梯调度：电梯调度就是类似于汽车的雨刮器，每次从一个方向的起点扫描到终点再回头。优点：不会导致远处饥饿，缺点：中间的比较有利。循环电梯调度：到一个方向的终点以后回到起点，返程不服务。优点：更加公平，缺点：一个方向上可能后续没有IO，但是还是要扫描到终点。
LOOK和CLOOK：就是对电梯和循环电梯的改进，一个方向没有了就立刻掉头。优点：减少扫描终点的开销。缺点：一个方向上一直来IO会导致背后的IO饥饿。
deadline：也可以deadline，但是可能导致频繁来回移动，多个请求都超时。
缓存逐出算法
一般有LRU，FIFO，LFU，TTL等。
• LRU：最近最少使用。将所有的缓存项组织成一个双向链表，并且用一个映射管理链表节点，目的是让查找，更新，删除的时间复杂度都是O1.当缓存命中时，就将节点移动到表头。当缓存更新后，也移动到表头这样就可以保证表尾的数据是最近使用最少的。如果缓存没有命中，就将数据读出来并安放在表头，同时逐出表尾的节点。基于局部性原理假设
• FIFO：将缓存项目按照时间顺序放入队列，每次逐出队列尾部
• LFU：记录过去一段时间内缓存项目的使用情况，每次逐出最近访问次数最少的
• TTL：给每个项目设置一个存活时间，超过存活时间就逐出
优缺点：
• LRU：实现复杂，预读失效，缓存污染 ◦ 随机IO不符合局部性原理，导致预读页面无法命中 ◦ 大文件的顺序读是最近访问过但之后又不会访问的，这种一次性数据会污染缓存 ◦ 解决：可以和FIFO结合使用，每个缓存项先进入FIFO，第二次访问再进入LRU链表，可以避免一次性数据的污染
• FIFO：实现简单，性能差
• LFU：实现复杂，存在工作集切换时的颠簸 ◦ 工作集突然切换的时候，旧工作集内容不会再访问，但占着缓存，导致新工作集被频繁逐出 ◦ 解决：可以每隔一段时间就将最近访问次数减少或者除以二，或者给每一项安排一个生存时间，从而将数据的访问时间纳入考量
• TTL：优点，可以保证缓存的新鲜度，利用时间局部性，但是可能导致大量缓存同时失效，并且生存时间不易确定