神鹰网站建设公司,openresty wordpress,网站开发商换了,自己购买域名做网站笔试得刷算法题#xff0c;那面试就离不开八股文#xff0c;所以特地对着小林coding的图解八股文系列记一下笔记。
这一篇笔记是图解系统的内容。
硬件结构
CPU执行程序
计算机基本结构为 5 个部分#xff0c;分别是运算器、控制器、存储器、输入设备、输出设备#xf…笔试得刷算法题那面试就离不开八股文所以特地对着小林coding的图解八股文系列记一下笔记。
这一篇笔记是图解系统的内容。
硬件结构
CPU执行程序
计算机基本结构为 5 个部分分别是运算器、控制器、存储器、输入设备、输出设备这 5 个部分也被称为冯诺依曼模型。
存储单元和输入输出设备的通讯如下 内存地址从0编号自增排列。
CPU一次计算的数据量分为32位4个字节以及64位8个字节CPU中有寄存器来存储计算时数据有通用寄存器、程序计数器以及指令寄存器。
总线有地址总线、数据总线以及控制总线分为完成寻址、读写内存数据以及发送和接收信号。
CPU位宽一般不小于线路位宽32位CPU一般为32位地址总线。
程序执行的时候耗费的 CPU 时间少就说明程序是快的对于程序的 CPU 执行时间可以拆解成 CPU 时钟周期数CPU Cycles和时钟周期时间Clock Cycle Time的乘积。 CPU 时钟周期数可以进一步拆解成「指令数 x 每条指令的平均时钟周期数Cycles Per Instruction简称 CPI」由此继续化简公式 磁盘与内存
CPU中有数据存储也就是CPU Cache成为CPU高速缓存通常分为L1、L2、L3三成L1 Cache通常分为“数据缓存”和“指令缓存”。
CPU中操作最快的是寄存器然后依次是CPU Cache然后是内存最后是硬盘。
CPU Cache 用的是一种叫 SRAMStatic Random-Access Memory静态随机存储器 的芯片。而三层Cache如下所示 L1 高速缓存的访问速度几乎和寄存器一样快通常只需要 2~4 个时钟周期而大小在几十 KB 到几百 KB 不等。每个CPU核心都有且会分成指令缓存和数据缓存。
L2 高速缓存同样每个 CPU 核心都有但是 L2 高速缓存位置比 L1 高速缓存距离 CPU 核心 更远它大小比 L1 高速缓存更大CPU 型号不同大小也就不同通常大小在几百 KB 到几 MB 不等访问速度则更慢速度在 10~20 个时钟周期。
L3 高速缓存通常是多个 CPU 核心共用的位置比 L2 高速缓存距离 CPU 核心 更远大小也会更大些通常大小在几 MB 到几十 MB 不等具体值根据 CPU 型号而定。访问速度相对也比较慢一些访问速度在 20~60个时钟周期。
内存用的芯片和 CPU Cache 有所不同它使用的是一种叫作 DRAM Dynamic Random Access Memory动态随机存取存储器 的芯片。访问速度更慢内存速度大概在 200~300 个 时钟周期之间。
CPU访问内存中数据的流程 提升CPU中代码运行效率
CPU Cache 的数据是从内存中读取过来的它是以一小块一小块读取数据的而不是按照单个数组元素来读取数据的在 CPU Cache 中的这样一小块一小块的数据称为 Cache Line缓存块。Cache Line 是 CPU 从内存读取数据的基本单位而 Cache Line 是由各种标志Tag 数据块Data Block组成。
一般CPU访问内存就会通过直接映射Cache来完成Direct Mapped Cache。一个内存的访问地址包括组标记、CPU Cache Line 索引、偏移量这三种信息于是 CPU 就能通过这些信息在 CPU Cache 中找到缓存的数据。而对于 CPU Cache 里的数据结构则是由索引 有效位 组标记 数据块组成。 如果 CPU 所要操作的数据在 CPU Cache 中的话这样将会带来很大的性能提升。访问的数据在 CPU Cache 中的话意味着缓存命中缓存命中率越高的话代码的性能就会越好CPU 也就跑的越快。
按照内存布局顺序访问将可以有效的利用 CPU Cache 带来的好处这样我们代码的性能就会得到很大的提升提升数据缓存的命中率。
现代 CPU 都是多核心的线程可能在不同 CPU 核心来回切换执行这对 CPU Cache 不是有利的虽然 L3 Cache 是多核心之间共享的但是 L1 和 L2 Cache 都是每个核心独有的如果一个线程在不同核心来回切换各个核心的缓存命中率就会受到影响相反如果线程都在同一个核心上执行那么其数据的 L1 和 L2 Cache 的缓存命中率可以得到有效提高缓存命中率高就意味着 CPU 可以减少访问内存的频率。所以可以把线程绑定到某个CPU核心来提升多核CPU的缓存命中率。
CPU的缓存一致性
把CPU的Cache数据写回到内存的时机很重要。
为了要减少数据写回内存的频率就出现了写回Write Back的方法。 当发生写操作时新的数据仅仅被写入 Cache Block 里只有当修改过的 Cache Block「被替换」时才需要写到内存中减少了数据写回内存的频率这样便可以提高系统的性能。 由于CPU当前大多是多核的而L1和L2都是多个核心独有的就会有缓存一致性问题Cache Coherence。
写传播的原则就是当某个 CPU 核心更新了 Cache 中的数据要把该事件广播通知到其他核心。最常见实现的方式是总线嗅探Bus Snooping。但是这就需要 CPU 时刻监听总线负担很重。
MESI协议则通过添加状态机来改善总线嗅探的问题。具体的方法可以在面试前直接看下面的表格熟悉一下 CPU执行任务
多个线程同时读写同一个 Cache Line 的不同变量时而导致 CPU Cache 失效的现象称为伪共享False Sharing。在 Linux 内核中存在 __cacheline_aligned_in_smp 宏定义其可以在原先a、b两个在物理内存地址上连续的变量通过这个宏定义将b的地址设置为 Cache Line 对齐地址避免伪共享。
CPU选择执行的线程在 Linux 中线程和进程都是用 task_struct 结构体表示调度器调度这个结构体来完成执行。这些任务分为普通任务和实时任务。优先级数值越小则优先级越高。
对于普通任务一般用完全公平调度Completely Fair Scheduling算法优先选择虚拟运行时间 vruntime 少的任务来执行当然还要考虑普通任务的权重值nice 级别越低权重值越大。nice 的值能设置的范围是 -2019 值越低表明优先级越高因此 -20 是最高优先级19 则是最低优先级默认优先级是 0。 软中断
Linux 系统为了解决中断处理程序执行过长和中断丢失的问题将中断过程分成了两个阶段分别是「上半部和下半部分」。
上半部用来快速处理中断一般会暂时关闭中断请求主要负责处理跟硬件紧密相关或者时间敏感的事情。下半部用来延迟处理上半部未完成的工作一般以「内核线程」的方式运行。
中断处理程序的上部分和下半部可以理解为
上半部直接处理硬件请求也就是硬中断主要是负责耗时短的工作特点是快速执行下半部是由内核触发也就说软中断主要是负责上半部未完成的工作通常都是耗时比较长的事情特点是延迟执行
数据存储
计算机中负数通过补码来完成保存。所谓的补码就是把正数的二进制全部取反再加 1。用了补码的表示方式对于负数的加减法操作实际上是和正数加减法操作一样的。
存小数的方法可以直接去看这个链接小林图解系统中的数据存储部分
内存管理
虚拟内存
操作系统引入了虚拟内存进程持有的虚拟地址会通过 CPU 芯片中的内存管理单元MMU的映射关系来转换变成物理地址然后再通过物理地址访问内存。
为了减少传统的分段管理导致的内存碎片提出了内存分页Paging方法把整个虚拟和物理内存空间切成一段段固定尺寸的大小。这样一个连续并且尺寸固定的内存空间我们叫页Page。在 Linux 下每一页的大小为 4KB。 内存管理单元MMU会负责映射工作采用了分页页与页之间是紧密排列的所以不会有外部碎片。
如果内存空间不够操作系统会把其他正在运行的进程中的「最近没被使用」的内存页面给释放掉也就是暂时写在硬盘上称为换出Swap Out。一旦需要的时候再加载进来称为换入Swap In。所以一次性写入磁盘的也只有少数的一个页或者几个页不会花太多时间内存交换的效率就相对比较高。 在分页机制下虚拟地址分为两部分页号和页内偏移。页号作为页表的索引页表包含物理页每页所在物理内存的基地址这个基地址与页内偏移的组合就形成了物理内存地址。但这种简单的分页存在空间缺陷因为页表由于多个进程会变得非常庞大故采用多级页表Multi-Level Page Table来解决。
例如在32位 CPU 下页大小 4KB 一个进程的页表需要 4 MB 空间而对其进行二次分页将页表一级页表分为 1024 个页表二级页表每个表二级页表中包含 1024 个「页表项」形成二级分页。这样如果某个一级页表的页表项没有被用到也就不需要创建这个页表项对应的二级页表了即可以在需要时才创建二级页表。 但是多级页表会造成虚拟内存到物理地址上更多的转换步骤所以把最常访问的几个页表项存储到访问速度更快的硬件于是计算机科学家们就在 CPU 芯片中加入了一个专门存放程序最常访问的页表项的 Cache这个 Cache 就是 TLBTranslation Lookaside Buffer 通常称为页表缓存、转址旁路缓存、快表等。
内存分段和内存分页并不是对立的它们是可以组合起来在同一个系统中使用的那么组合起来后通常称为段页式内存管理。
Linux 系统中的每个段都是从 0 地址开始的整个 4GB 虚拟空间32 位环境下也就是所有的段的起始地址都是一样的。这意味着Linux 系统中的代码包括操作系统本身的代码和应用程序代码所面对的地址空间都是线性地址空间虚拟地址这种做法相当于屏蔽了处理器中的逻辑地址概念段只被用于访问控制和内存保护。
在 Linux 操作系统中虚拟地址空间的内部又被分为内核空间和用户空间两部分 32 位系统的内核空间占用 1G位于最高处剩下的 3G 是用户空间。
内核空间与用户空间的区别
进程在用户态时只能访问用户空间内存只有进入内核态后才可以访问内核空间的内存
其中用户态的分布代码段、全局变量、BSS、函数栈、堆内存、映射区。
虚拟内存作用
第一虚拟内存可以使得进程对运行内存超过物理内存大小因为程序运行符合局部性原理CPU 访问内存会有很明显的重复访问的倾向性对于那些没有被经常使用到的内存我们可以把它换出到物理内存之外比如硬盘上的 swap 区域。第二由于每个进程都有自己的页表所以每个进程的虚拟内存空间就是相互独立的。进程也没有办法访问其他进程的页表所以这些页表是私有的这就解决了多进程之间地址冲突的问题。第三页表里的页表项中除了物理地址之外还有一些标记属性的比特比如控制一个页的读写权限标记该页是否存在等。在内存访问方面操作系统提供了更好的安全性。
malloc分配内存
malloc 申请内存的时候会有两种方式向操作系统申请堆内存。
方式一通过 brk() 系统调用从堆分配内存方式二通过 mmap() 系统调用在文件映射区域分配内存
方式一实现的方式很简单就是通过 brk() 函数将「堆顶」指针向高地址移动获得新的内存空间。方式二通过 mmap() 系统调用中「私有匿名映射」的方式在文件映射区分配一块内存也就是从文件映射区“偷”了一块内存。这两个方法切换的阈值是 128KB 小于 128KB 就会采用 brk() 来分配。
malloc会分配的时虚拟内存且会预分配更大的空间作为内存池。free 内存后堆内存还存在是针对 malloc 通过 brk() 方式申请的内存的情况。如果 malloc 通过 mmap 方式申请的内存free 释放内存后就会归归还给操作系统。
如果都用 mmap 来分配内存等于每次都要执行系统调用。执行系统调用会需要切换进入内核态然后回到用户态需要消耗时间。同时mmap 分配内存释放会归还给操作系统所以分配的地址都会缺页第一次访问该虚拟地址就会触发缺页中断而 brk() 申请的堆空间连续再次申请只需要从内存池取出但如果都用 brk()会造成堆内大量不可用碎片导致内存泄漏。
缺页中断出发后进程从用户态进入内核态缺页中断函数会查看是否有空余的物理内存有的话就分配并建立映射关系。
内存满了会发生什么
缺页中断触发如果没有空闲物理内存就会进行回收内存。
后台内存回收kswapd在物理内存紧张的时候会唤醒 kswapd 内核线程来回收内存这个回收内存的过程异步的不会阻塞进程的执行。直接内存回收direct reclaim如果后台异步回收跟不上进程内存申请的速度就会开始直接回收这个回收内存的过程是同步的会阻塞进程的执行。
如果直接内存回收后空闲的物理内存仍然无法满足此次物理内存的申请那么内核就会放最后的大招了 ——触发 OOM Out of Memory机制。OOM Killer 机制会根据算法选择一个占用物理内存较高的进程然后将其杀死以便释放内存资源如果物理内存依然不足OOM Killer 会继续杀死占用物理内存较高的进程直到释放足够的内存位置。 主要有两类内存可以被回收而且它们的回收方式也不同。
文件页File-backed Page内核缓存的磁盘数据Buffer和内核缓存的文件数据Cache都叫作文件页。大部分文件页都可以直接释放内存以后有需要时再从磁盘重新读取就可以了。而那些被应用程序修改过并且暂时还没写入磁盘的数据也就是脏页就得先写入磁盘然后才能进行内存释放。所以回收干净页的方式是直接释放内存回收脏页的方式是先写回磁盘后再释放内存。匿名页Anonymous Page这部分内存没有实际载体不像文件缓存有硬盘文件这样一个载体比如堆、栈数据等。这部分内存很可能还要再次被访问所以不能直接释放内存它们回收的方式是通过 Linux 的 Swap 机制Swap 会把不常访问的内存先写到磁盘中然后释放这些内存给其他更需要的进程使用。再次访问这些内存时重新从磁盘读入内存就可以了。
从文件页和匿名页的回收操作来看文件页的回收操作对系统的影响相比匿名页的回收操作会少一点因为文件页对于干净页回收是不会发生磁盘 I/O 的而匿名页的 Swap 换入换出这两个操作都会发生磁盘 I/O。所以尽可能先回收文件页。
尽早触发 kswapd 内核线程异步回收内存。具体看这里kswapd 回收设置
在 32 位操作系统因为进程理论上最大能申请 3 GB 大小的虚拟内存所以直接申请 8G 内存会申请失败。在 64位 位操作系统因为进程理论上最大能申请 128 TB 大小的虚拟内存即使物理内存只有 4GB申请 8G 内存也是没问题因为申请的内存是虚拟内存。如果这块虚拟内存被访问了要看系统有没有 Swap 分区 如果没有 Swap 分区因为物理空间不够进程会被操作系统杀掉原因是 OOM内存溢出如果有 Swap 分区即使物理内存只有 4GB程序也能正常使用 8GB 的内存进程可以正常运行
如何避免预读失效和缓存污染
LInux 中读取的文件数据缓存在文件系统中的 Page Cache大小有限所以希望通过保留频繁访问的数据在其中经典的是采用 LRULeast recently used算法完成一般采用链表头部是最近使用的数据尾部就是最久没被使用的。
预读机制会把多个 Page 数据装入 Page Cache以此减少磁盘 I/O 次数提高吞吐量。但如果这些被提前加载进来的页并没有被访问相当于这个预读工作是白做了这个就是预读失效。为了避免此类问题最好就是让预读页停留在内存里的时间要尽可能的短让真正被访问的页才移动到 LRU 链表的头部从而保证真正被读取的热数据留在内存里的时间尽可能长。Linux 操作系统实现两个了 LRU 链表活跃 LRU 链表active_list和非活跃 LRU 链表inactive_list将数据分为了冷数据和热数据然后分别进行 LRU 算法。预读页就只需要加入到 inactive list 区域的头部当页被真正访问的时候才将页插入 active list 的头部。
缓存污染当我们在批量读取数据的时候由于数据被访问了一次这些大量数据都会被加入到「活跃 LRU 链表」里然后之前缓存在活跃 LRU 链表或者 young 区域里的热点数据全部都被淘汰了如果这些大量的数据在很长一段时间都不会被访问的话那么整个活跃 LRU 链表或者 young 区域就被污染了。为了解决缓存污染只要我们提高进入到活跃 LRU 链表或者 young 区域的门槛就能有效地保证活跃 LRU 链表或者 young 区域里的热点数据不会被轻易替换掉。在 Linux 中只有内存页被访问第二次才将页从 inactive list 升级到 active list 中。
Linux 虚拟内存管理、物理内存管理
直接看这里Linux 虚拟内存
进程管理
基础知识
进程
编写的代码只是一个存储在硬盘的静态文件通过编译后就会生成二进制可执行文件当我们运行这个可执行文件后它会被装载到内存中接着 CPU 会执行程序中的每一条指令那么这个运行中的程序就被称为「进程」Process。
单核的 CPU 在某一个瞬间只能运行一个进程。但在 1 秒钟期间它可能会运行多个进程这样就产生并行的错觉实际上这是并发。
在一个进程的活动期间至少具备三种基本状态即运行状态、就绪状态、阻塞状态。 再加上创建状态和结束状态完整的进程状态图如下 同时阻塞装填太多进程可能占用大量物理内存空间可以把这些空间换出到硬盘也就是 swap out那么需要一个挂起状态来描述没有占用实际物理内存空间的情况。同时挂起还需分成阻塞挂起和就绪挂起。那么就变成了下图 PCB 是进程存在的唯一标识这意味着一个进程的存在必然会有一个 PCB如果进程消失了那么 PCB 也会随之消失。包含了进程描述信息、进程控制和管理信息、资源分配清单以及 CPU 相关信息。
PCB 一般通过链表形式组织把具有相同状态的进程链在一起组成各种队列。
01 创建进程
操作系统允许一个进程创建另一个进程而且允许子进程继承父进程所拥有的资源。
创建进程的过程如下
申请一个空白的 PCB并向 PCB 中填写一些控制和管理进程的信息比如进程的唯一标识等为该进程分配运行时所必需的资源比如内存资源将 PCB 插入到就绪队列等待被调度运行
02 终止进程
进程可以有 3 种终止方式正常结束、异常结束以及外界干预信号 kill 掉。
当子进程被终止时其在父进程处继承的资源应当还给父进程。而当父进程被终止时该父进程的子进程就变为孤儿进程会被 1 号进程收养并由 1 号进程对它们完成状态收集工作。
终止进程的过程如下
查找需要终止的进程的 PCB如果处于执行状态则立即终止该进程的执行然后将 CPU 资源分配给其他进程如果其还有子进程则应将该进程的子进程交给 1 号进程接管将该进程所拥有的全部资源都归还给操作系统将其从 PCB 所在队列中删除
03 阻塞进程
当进程需要等待某一事件完成时它可以调用阻塞语句把自己阻塞等待。而一旦被阻塞等待它只能由另一个进程唤醒。
阻塞进程的过程如下
找到将要被阻塞进程标识号对应的 PCB如果该进程为运行状态则保护其现场将其状态转为阻塞状态停止运行将该 PCB 插入到阻塞队列中去
04 唤醒进程
进程由「运行」转变为「阻塞」状态是由于进程必须等待某一事件的完成所以处于阻塞状态的进程是绝对不可能叫醒自己的。
如果某进程正在等待 I/O 事件需由别的进程发消息给它则只有当该进程所期待的事件出现时才由发现者进程用唤醒语句叫醒它。
唤醒进程的过程如下
在该事件的阻塞队列中找到相应进程的 PCB将其从阻塞队列中移出并置其状态为就绪状态把该 PCB 插入到就绪队列中等待调度程序调度
进程的上下文切换一个进程切换到另一个进程。进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源还包括了内核堆栈、寄存器等内核空间的资源。通常会把交换的信息保存在进程的 PCB当要运行另外一个进程的时候我们需要从这个进程的 PCB 取出上下文然后恢复到 CPU 中这使得这个进程可以继续执行。
线程
线程是进程当中的一条执行流程。同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源但每个线程各自都有一套独立的寄存器和栈这样可以确保线程的控制流是相对独立的。
线程是调度的基本单位而进程则是资源拥有的基本单位。那么对于线程的上下文切换就得分成两种两个线程不属于同一个进程那么切换就跟进程上下文切换一样当两个线程是属于同一个进程因为虚拟内存是共享的所以在切换时虚拟内存这些资源就保持不动只需要切换线程的私有数据、寄存器等不共享的数据。
线程的实现方式有三种
用户线程User Thread在用户空间实现的线程不是由内核管理的线程是由用户态的线程库来完成线程的管理内核线程Kernel Thread在内核中实现的线程是由内核管理的线程轻量级进程LightWeight Process在内核中来支持用户线程
以上三种实现方式第一种是多个用户线程对一个内核线程第二种则是一对一第三种是多对多。
用户线程是基于用户态的线程管理库来实现的那么线程控制块Thread Control Block, TCB 也是在库里面来实现的对于操作系统而言是看不到这个 TCB 的它只能看到整个进程的 PCB。所以用户线程的整个线程管理和调度操作系统是不直接参与的而是由用户级线程库函数来完成线程的管理包括线程的创建、终止、同步和调度等。内核线程是由操作系统管理的线程对应的 TCB 自然是放在操作系统里的这样线程的创建、终止和管理都是由操作系统负责。轻量级进程Light-weight processLWP是内核支持的用户线程一个进程可有一个或多个 LWP每个 LWP 是跟内核线程一对一映射的也就是 LWP 都是由一个内核线程支持而且 LWP 是由内核管理并像普通进程一样被调度。在大多数系统中LWP与普通进程的区别也在于它只有一个最小的执行上下文和调度程序所需的统计信息。
调度
调度程序scheduler操作系统中选择一个进程运行。在进程的生命周期中当进程从一个运行状态到另外一状态变化的时候其实会触发一次调度。如果硬件时钟提供某个频率的周期性中断那么可以根据如何处理时钟中断 分为非抢占式调度和抢占式调度。调度算法的原则如下
CPU 利用率调度程序应确保 CPU 是始终匆忙的状态这可提高 CPU 的利用率系统吞吐量吞吐量表示的是单位时间内 CPU 完成进程的数量长作业的进程会占用较长的 CPU 资源因此会降低吞吐量相反短作业的进程会提升系统吞吐量周转时间周转时间是进程运行阻塞时间等待时间的总和一个进程的周转时间越小越好等待时间这个等待时间不是阻塞状态的时间而是进程处于就绪队列的时间等待的时间越长用户越不满意响应时间用户提交请求到系统第一次产生响应所花费的时间在交互式系统中响应时间是衡量调度算法好坏的主要标准。
一些调度算法小林总结的调度算法
进程间通信方式
管道
在 Linux 命令中的「|」这个竖线就是管道将左边的输出作为右边的输入。这里管道是匿名管道用完就销毁也可以用mkfifo命令指定管道名字。
管道这种通信方式效率低不适合进程间频繁地交换数据。
匿名创建管道会用到系统调用
int pipe(int fd[2])返回了两个描述符一个是管道的读取端描述符 fd[0]另一个是管道的写入端描述符 fd[1]。且只存在于内存之中。
所谓的管道就是内核里面的一串缓存。如果在 Linux 中使用 fork 创建子进程那么创建的子进程会复制父进程的文件描述符为了避免混乱传输一般会关闭父进程的 fd[0]关闭子进程的 fd[1]从而实现父进程可传输到子进程中。如果要双向传输那么就需要创建两个管道。
对于匿名管道它的通信范围是存在父子关系的进程。对于命名管道它可以在不相关的进程间也能相互通信。
消息队列
为了频繁交换数据就可以用消息队列。比如A 进程要给 B 进程发送消息A 进程把数据放在对应的消息队列后就可以正常返回了B 进程需要的时候再去读取数据就可以了。同理B 进程要给 A 进程发送消息也是如此。
消息队列是保存在内核中的消息链表消息队列生命周期随内核如果没有释放消息队列或者没有关闭操作系统消息队列会一直存在。
消息队列不适合比较大数据的传输消息队列通信过程中存在用户态与内核态之间的数据拷贝开销。
共享内存
共享内存的机制就是拿出一块虚拟地址空间来映射到相同的物理内存中。
信号量
为了防止多进程竞争共享资源而造成的数据错乱所以需要保护机制使得共享的资源在任意时刻只能被一个进程访问。正好信号量就实现了这一保护机制。
信号量其实是一个整型的计数器主要用于实现进程间的互斥与同步而不是用于缓存进程间通信的数据。
信号量的控制有两种原子操作
一个是 P 操作这个操作会把信号量减去 1相减后如果信号量 0则表明资源已被占用进程需阻塞等待相减后如果信号量 0则表明还有资源可使用进程可正常继续执行。另一个是 V 操作这个操作会把信号量加上 1相加后如果信号量 0则表明当前有阻塞中的进程于是会将该进程唤醒运行相加后如果信号量 0则表明当前没有阻塞中的进程
P 操作是用在进入共享资源之前V 操作是用在离开共享资源之后这两个操作是必须成对出现的。
信号初始化为 1就代表着是互斥信号量可以保证共享内存任意时刻只有一个进程访问。用信号量来实现多进程同步的方式我们可以初始化信号量为 0代表着同步信号量可用于保证某一进程一定在前执行。
信号
对于异常情况下的工作模式就需要用「信号」的方式来通知进程。
这个例如在 Linux 中一共有 64 种信号例如 Ctrl C 就是发送 SIGINT 信号来终止进程而常用的 kill -9 PID就是发送 SIGKILL 信号来立即结束 PID 进程。
信号是进程间通信机制中唯一的异步通信机制。
socket
想跨网络与不同主机上的进程之间通信就需要 Socket 通信了。
创建 socket 的系统调用如下
int socket(int domain, int type, int protocal)一般通过前两个参数完成protocal 直接设为 0domain 来制定协议族例如IPV4type 指定通信特性SOCK_STREAM 表示的是字节流对应 TCP、SOCK_DGRAM 表示的是数据报对应 UDP、SOCK_RAW 表示的是原始套接字。
有三种常见的通信方式一个是基于 TCP 协议的通信方式一个是基于 UDP 协议的通信方式一个是本地进程间通信方式。具体的在图解网络应该会有。
多线程冲突
竞争条件race condition当多线程相互竞争操作共享变量时由于运气不好即在执行过程中发生了上下文切换我们得到了错误的结果事实上每次运行都可能得到不同的结果因此输出的结果存在不确定性indeterminate。
由于多线程执行操作共享变量的这段代码可能会导致竞争状态因此我们将此段代码称为临界区critical section它是访问共享资源的代码片段一定不能给多线程同时执行。
我们希望这段代码是互斥mutualexclusion的也就说保证一个线程在临界区执行时其他线程应该被阻止进入临界区说白了就是这段代码执行过程中最多只能出现一个线程。
同步就是并发进程/线程在一些关键点上可能需要互相等待与互通消息这种相互制约的等待与互通信息称为进程/线程同步。
互斥和同步主要可以采用锁/信号量来完成信号量比锁的功能更加强大。这其中均涉及原子操作就是要么全部执行要么都不执行不能出现执行到一半的中间状态。
信号量实现临界区的互斥访问将信号量初值均设置为 1信号量实现临界区的同步访问将信号量初值均设置为 0。
生产者——消费者模型需要互斥信号量以及两个用于生产者和消费者对缓存区访问的同步信号量一共三个信号量。
哲学家就餐问题设置五个互斥信号量同时对于奇数和偶数哲学家区分先拿的叉子避免同时只能一个哲学家就餐。对于互斥访问有限的竞争问题如 I/O 设备一类的建模过程十分有用。
读者——写者问题可以有多个读者只能一个写者分别设置两个互斥信号量同时写一个rCount记录读者数量只有rCount为零才可以进行对写信号量的 V 操作同时为了实现公平策略需要设置一个互斥信号量 flag无论是writer还是reader都需要对 flag 信号量先操作在进入写/读的互斥信号量操作。对数据库建模非常有用。
避免死锁
死锁当两个线程为了保护两个不同的共享资源而使用了两个互斥锁那么这两个互斥锁应用不当的时候可能会造成两个线程都在等待对方释放锁在没有外力的作用下这些线程会一直相互等待就没办法继续运行。
同时满足以下四个条件才可能发生
互斥条件持有并等待条件不可剥夺条件环路等待条件
避免死锁问题就只需要破环其中一个条件就可以最常见的并且可行的就是使用资源有序分配法来破环环路等待条件。也就是说比如两个进程来获取两个资源那只要将两者请求获取的顺序改成一样即可。
悲观锁、乐观锁
互斥锁、自旋锁
最底层的两种所两者对加锁失败的处理方式不同
互斥锁加锁失败后线程会释放 CPU 给其他线程自旋锁加锁失败后线程会忙等待直到它拿到锁
互斥锁是一种独占锁如果加锁失败那么加锁代码会被阻塞对于互斥锁加锁失败而阻塞的现象是由操作系统内核实现的会从用户态陷入到内核态让内核帮助切换线程。但这会造成有一定的开销成本也就是两次线程上下文切换的成本。因此如果能确定被锁住的代码执行时间很短就不应该用互斥锁而应该选用自旋锁否则使用互斥锁。
自旋锁是最比较简单的一种锁一直自旋利用 CPU 周期直到锁可用。需要注意在单核 CPU 上需要抢占式的调度器即不断通过时钟中断一个线程运行其他线程。否则自旋锁在单 CPU 上无法使用因为一个自旋的线程永远不会放弃 CPU。自旋锁适合异步、协程等在用户态切换请求的编程方式但如果被锁住的代码执行时间过长自旋的线程会长时间占用 CPU 资源所以自旋的时间和被锁住的代码执行的时间是成「正比」的关系。
当加锁失败时互斥锁用「线程切换」来应对自旋锁则用「忙等待」来应对。
读写锁
读写锁适用于能明确区分读操作和写操作的场景。读写锁在读多写少的场景能发挥出优势。
工作原理如下
当「写锁」没有被线程持有时多个线程能够并发地持有读锁这大大提高了共享资源的访问效率因为「读锁」是用于读取共享资源的场景所以多个线程同时持有读锁也不会破坏共享资源的数据。但是一旦「写锁」被线程持有后读线程的获取读锁的操作会被阻塞而且其他写线程的获取写锁的操作也会被阻塞。
根据实现不同读写锁可以分为「读优先锁」和「写优先锁」。公平读写锁比较简单的一种方式是用队列把获取锁的线程排队不管是写线程还是读线程都按照先进先出的原则加锁即可这样读线程仍然可以并发也不会出现「饥饿」的现象。
乐观锁与悲观锁
上文中的互斥锁、自旋锁和读写锁都属于悲观锁。悲观锁认为多线程同时修改共享资源的概率比较高于是很容易出现冲突所以访问共享资源前先要上锁。
乐观锁做事比较乐观它假定冲突的概率很低它的工作方式是先修改完共享资源再验证这段时间内有没有发生冲突如果没有其他线程在修改资源那么操作完成如果发现有其他线程已经修改过这个资源就放弃本次操作。乐观锁全程并没有加锁所以它也叫无锁编程。乐观锁的一大应用场景就是在线文档。只有在冲突概率非常低且加锁成本非常高的场景时才考虑使用乐观锁。
一个进程最多创建几个线程
有以下两个影响因素
进程的虚拟内存空间上限因为创建一个线程操作系统需要为其分配一个栈空间如果线程数量越多所需的栈空间就要越大那么虚拟内存就会占用的越多。系统参数限制虽然 Linux 并没有内核参数来控制单个进程创建的最大线程个数但是有系统级别的参数来控制整个系统的最大线程个数。
在 Linux 中可通过 ulimit -a 这条命令查看进程创建线程是默认分配的栈空间大小。针对 32 位 Linux 系统一个进程的虚拟空间有 4G内核分走 1G用户空间 3G。那么可创建的线程数最多可有 3G 大小。
如果想要修改默认的栈大小可以通过 ulimit -s number 来调整number 就是调整后的大小为 number kb。
当然如果是 64 位系统用户空间的虚拟内存最大能到 128T理论上可以创建无数个线程。但是有三个内核参数会影响线程的上限
/proc/sys/kernel/threads-max表示系统支持的最大线程数默认值是 14553/proc/sys/kernel/pid_max表示系统全局的 PID 号数值的限制每一个进程或线程都有 IDID 的值超过这个数进程或线程就会创建失败默认值是 32768/proc/sys/vm/max_map_count表示限制一个进程可以拥有的VMA(虚拟内存区域)的数量具体什么意思我也没搞清楚反正如果它的值很小也会导致创建线程失败默认值是 65530。
线程崩溃进程会崩溃吗
一般来说如果线程是因为非法访问内存引起的崩溃那么进程肯定会崩溃为什么系统要让进程崩溃呢这主要是因为在进程中各个线程的地址空间是共享的既然是共享那么某个线程对地址的非法访问就会导致内存的不确定性进而可能会影响到其他线程这种操作是危险的操作系统会认为这很可能导致一系列严重的后果于是干脆让整个进程崩溃。
例如针对只读内存写入数据访问了进程无权限访问的空间如内核空间访问了不存在的内存。以上均会导致进程崩溃。
进程崩溃——信号机制
线程崩溃之后由于信号会导致进程崩溃。
机制CPU执行进程调用 kill 系统调用向进程发送信号进程收到信号CPU 暂停并将控制权转交给操作系统调用 kill 系统调用向进程发送信号操作系统根据情况执行相应的信号处理程序函数一般执行完信号处理程序逻辑后会让进程退出。如果注册了自己的信号处理函数就会调用没注册就会执行默认的信号处理程序。
调度算法
进程调度算法
通常如下情况就会发生 CPU 调度
当进程从运行状态转到等待状态当进程从运行状态转到就绪状态当进程从等待状态转到就绪状态当进程从运行状态转到终止状态
1 和 4 两种情况下的调度称为「非抢占式调度」2 和 3 两种情况下发生的调度称为「抢占式调度」。
常见的调度算法如下。
先来先服务First Come First Severd, FCFS算法
每次从就绪队列选择最先进入队列的进程然后一直运行直到进程退出或被阻塞才会继续从队列中选择第一个进程接着运行。
FCFS 对长作业有利适用于 CPU 繁忙型作业的系统而不适用于 I/O 繁忙型作业的系统。
最短作业优先Shortest Job First, SJF算法
优先选择运行时间最短的进程来运行这有助于提高系统的吞吐量。
但显然对长作业不利很容易造成一种极端现象。
高响应比优先 Highest Response Ratio Next, HRRN算法
每次进行进程调度时先计算「响应比优先级」然后把「响应比优先级」最高的进程投入运行权衡了短作业和长作业。
「响应比优先级」计算公式如下 时间片轮转Round Robin, RR算法
每个进程被分配一个时间段称为时间片Quantum即允许该进程在该时间段中运行。
如果时间片用完进程还在运行那么将会把此进程从 CPU 释放出来并把 CPU 分配另外一个进程如果该进程在时间片结束前阻塞或结束则 CPU 立即进行切换
通常时间片设为 20ms~50ms 通常是一个比较合理的折中值。
最高优先级Highest Priority FirstHPF算法
对于多用户计算机系统就有不同的看法了它们希望调度是有优先级的即希望调度程序能从就绪队列中选择最高优先级的进程进行运行。
进程的优先级可以分为静态优先级或动态优先级
静态优先级创建进程时候就已经确定了优先级了然后整个运行时间优先级都不会变化动态优先级根据进程的动态变化调整优先级比如如果进程运行时间增加则降低其优先级如果进程等待时间就绪队列的等待时间增加则升高其优先级也就是随着时间的推移增加等待进程的优先级。
该算法也有两种处理优先级高的方法非抢占式和抢占式
非抢占式当就绪队列中出现优先级高的进程运行完当前进程再选择优先级高的进程。抢占式当就绪队列中出现优先级高的进程当前进程挂起调度优先级高的进程运行。
该算法可能会导致低优先级的进程永远不会运行。
多级反馈队列Multilevel Feedback Queue算法
该算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。
这个工作的逻辑可以直接看下面这张图 对于短作业可能可以在第一级队列很快被处理完。对于长作业如果在第一级队列处理不完可以移入下次队列等待被执行虽然等待的时间变长了但是运行时间也会更长了所以该算法很好的兼顾了长短作业同时有较好的响应时间。
内存页面置换算法
首先要了解缺页异常缺页中断。这个在之前有学习过不再赘述。
主要流程就是访问虚拟内存后发现不存在对应的物理内存就会产生缺页中断去请求操作系统查询空闲的磁盘空间将他分配到物理内存并分配给这一块虚拟内存。
如果找不到物理内存中的空闲页说明内存满了那就需要「页面置换算法」选择一个物理页如果该物理页有被修改过脏页则把它换出到磁盘然后把该被置换出去的页表项的状态改成「无效的」最后把正在访问的页面装入到这个物理页中。
虚拟内存的整个管理流程如下图所示 综上页面置换算法的功能是当出现缺页异常需调入新页面而内存已满时选择被置换的物理页面也就是说选择一个物理页面换出到磁盘然后把需要访问的页面换入到物理页。
最佳页面置换算法OPT
思路是置换在「未来」最长时间不访问的页面。这就需要计算内存中每个逻辑页面的「下一次」访问时间然后比较选择未来最长时间不访问的页面。但是实际系统中无法实现因为程序访问页面时是动态的我们是无法预知每个页面在「下一次」访问前的等待时间。所以最佳页面置换算法作用是为了衡量你的算法的效率你的算法效率越接近该算法的效率那么说明你的算法是高效的。
先进先出置换算法FIFO
可以选择在内存驻留时间很长的页面进行中置换这个就是「先进先出置换」算法的思想。
最近最久未使用置换算法LRU
思想是选择最长时间没有被访问的页面进行置换也就是说该算法假设已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。该种算法近似最优置换算法。
虽然 LRU 在理论上是可以实现的但代价很高。为了完全实现 LRU需要在内存中维护一个所有页面的链表最近最多使用的页面在表头最近最少使用的页面在表尾。困难的是在每次访问内存时都必须要更新「整个链表」。在链表中找到一个页面删除它然后把它移动到表头是一个非常费时的操作。实际中比较少使用。
时钟页面置换算法Clock
时钟页面置换算法就可以两者兼得它跟 LRU 近似又是对 FIFO 的一种改进。
该算法的思路是把所有的页面都保存在一个类似钟面的「环形链表」中一个表针指向最老的页面。发生缺页就首先检查表针指向的页面
如果它的访问位位是 0 就淘汰该页面并把新的页面插入这个位置然后把表针前移一个位置如果访问位是 1 就清除访问位并把表针前移一个位置重复这个过程直到找到了一个访问位为 0 的页面为止
最不常用置换算法LFU
当发生缺页中断时选择「访问次数」最少的那个页面并将其淘汰。
实现方式是对每个页面设置一个「访问计数器」每当一个页面被访问时该页面的访问计数器就累加 1。在发生缺页中断时淘汰计数器值最小的那个页面。
计数器对于硬件成本而言是较高的而且查找链表本身如果链表长度很大也是很耗时的。
还有个问题LFU 算法只考虑了频率问题没考虑时间的问题比如有些页面在过去时间里访问的频率很高但是现在已经没有访问了而当前频繁访问的页面由于没有这些页面访问的次数高在发生缺页中断时就会可能会误伤当前刚开始频繁访问但访问次数还不高的页面。针对这个问题可以定期减少访问的次数以前的高访问次数的页面会慢慢减少相当于加大了被置换的概率。
磁盘调度算法
磁盘调度算法的目的很简单就是为了提高磁盘的访问性能一般是通过优化磁盘的访问请求顺序来做到的。寻道的时间是磁盘访问最耗时的部分如果请求顺序优化的得当必然可以节省一些不必要的寻道时间从而提高磁盘的访问性能。
先来先服务算法FCFS
顾名思义就是先来的先被服务。
最短寻道时间优先算法Shortest Seek FirstSSF
优先选择从当前磁头位置所需寻道时间最短的请求。
但这个算法可能存在某些请求的饥饿这里产生饥饿的原因是磁头在一小块区域来回移动。
扫描算法Scan
为了解决磁头只在一个小区域来回运动可以规定磁头在一个方向上移动访问所有未完成的请求直到磁头到达该方向上的最后的磁道才调换方向这就是扫描Scan算法。
扫描调度算法性能较好不会产生饥饿现象但是存在这样的问题中间部分的磁道会比较占便宜中间部分相比其他部分响应的频率会比较多也就是说每个磁道的响应频率存在差异。
循环扫描算法Circular Scan, C-SCAN
只有磁头朝某个特定方向移动时才处理磁道访问请求而返回时直接快速移动至最靠边缘的磁道也就是复位磁头这个过程是很快的并且返回中途不处理任何请求该算法的特点就是磁道只响应一个方向上的请求。
LOOK 与 C-LOOK算法
为了优化磁头移动到磁盘「最始端或最末端」才开始调换方向的问题可以磁头在移动到「最远的请求」位置然后立即反向移动。
针对 SCAN 算法的优化则叫 LOOK 算法它的工作方式磁头在每个方向上仅仅移动到最远的请求位置然后立即反向移动而不需要移动到磁盘的最始端或最末端反向移动的途中会响应请求。
针 C-SCAN 算法的优化则叫 C-LOOK它的工作方式磁头在每个方向上仅仅移动到最远的请求位置然后立即反向移动而不需要移动到磁盘的最始端或最末端反向移动的途中不会响应请求。
文件系统
文件系统全家桶
基本组成
Linux 文件系统会为每个文件分配两个数据结构索引节点index node和目录项directory entry它们主要用来记录文件的元信息和目录层次结构。
索引节点也就是 inode用来记录文件的元信息比如 inode 编号、文件大小、访问权限、创建时间、修改时间、数据在磁盘的位置等等。索引节点是文件的唯一标识它们之间一一对应也同样都会被存储在硬盘中所以索引节点同样占用磁盘空间。目录项也就是 dentry用来记录文件的名字、索引节点指针以及与其他目录项的层级关联关系。多个目录项关联起来就会形成目录结构但它与索引节点不同的是目录项是由内核维护的一个数据结构不存放于磁盘而是缓存在内存。
目录项和索引节点的关系是多对一。注意目录也是文件也是用索引节点唯一标识和普通文件不同的是普通文件在磁盘里面保存的是文件数据而目录文件在磁盘里面保存子目录或文件。目录是个文件持久化存储在磁盘而目录项是内核一个数据结构缓存在内存。
磁盘读写的最小单位是扇区扇区的大小只有 512B 大小所以文件系统把多个扇区组成了一个逻辑块每次读写的最小单位就是逻辑块数据块Linux 中的逻辑块大小为 4KB也就是一次性读写 8 个扇区这将大大提高了磁盘的读写的效率。
总结一下索引节点、目录项以及文件数据的关系如下图所示 上图中可见磁盘格式化的时候会被分成三个存储区域分别是超级块、索引节点区和数据块区。
超级块用来存储文件系统的详细信息比如块个数、块大小、空闲块等等。索引节点区用来存储索引节点数据块区用来存储文件或目录数据
为了加速文件访问通常把索引节点加载到内存中且只在需要时加载
超级块当文件系统挂载时进入内存索引节点区当文件被访问时进入内存
虚拟文件系统
操作系统希望对用户提供一个统一的接口于是在用户层与文件系统层引入了中间层这个中间层就称为虚拟文件系统Virtual File SystemVFS。
VFS 定义了一组所有文件系统都支持的数据结构和标准接口在 Linux 文件系统中用户空间、系统调用、虚拟文件系统、缓存、文件系统以及存储之间的关系如下图 Linux 支持的文件系统也不少根据存储位置的不同可以把文件系统分为三类
磁盘的文件系统它是直接把数据存储在磁盘中比如 Ext 2/3/4、XFS 等都是这类文件系统。内存的文件系统这类文件系统的数据不是存储在硬盘的而是占用内存空间我们经常用到的 /proc 和 /sys 文件系统都属于这一类读写这类文件实际上是读写内核中相关的数据。网络的文件系统用来访问其他计算机主机数据的文件系统比如 NFS、SMB 等等。
文件系统首先要先挂载到某个目录才可以正常使用比如 Linux 系统在启动时会把文件系统挂载到根目录。
文件的使用
打开了一个文件后操作系统会跟踪进程打开的所有文件所谓的跟踪呢就是操作系统为每个进程维护一个打开文件表文件表里的每一项代表「文件描述符」所以说文件描述符是打开文件的标识。
而操作系统会在打开文件表中维护打开文件的状态信息
文件指针系统跟踪上次读写位置作为当前文件位置指针这种指针对打开文件的某个进程来说是唯一的文件打开计数器文件关闭时操作系统必须重用其打开文件表条目否则表内空间不够用。因为多个进程可能打开同一个文件所以系统在删除打开文件条目之前必须等待最后一个进程关闭文件该计数器跟踪打开和关闭的数量当该计数为 0 时系统关闭文件删除该条目文件磁盘位置绝大多数文件操作都要求系统修改文件数据该信息保存在内存中以免每个操作都从磁盘中读取访问权限每个进程打开文件都需要有一个访问模式创建、只读、读写、添加等该信息保存在进程的打开文件表中以便操作系统能允许或拒绝之后的 I/O 请求
文件系统的基本操作单位是数据块。
文件的存储
可以分为连续空间和非连续空间的存放。
连续空间存放方式顾名思义文件存放在磁盘「连续的」物理空间中。这种模式下读写效率很高。
使用连续存放的方式有一个前提必须先知道一个文件的大小所以文件头里需要指定「起始块的位置」和「长度」有了这两个信息就可以很好的表示文件存放方式是一块连续的磁盘空间。
连续空间存放的方式虽然读写效率高但是有「磁盘空间碎片」和「文件长度不易扩展」的缺陷。另外一个缺陷是文件长度扩展不方便。
非连续存放方式分为「链表方式」和「索引方式」。
链表的方式存放是离散的可大大提高磁盘空间的利用率同时文件的长度可以动态扩展。根据实现的方式的不同链表可分为「隐式链表」和「显式链接」两种形式。文件要以「隐式链表」的方式存放的话实现的方式是文件头要包含「第一块」和「最后一块」的位置并且每个数据块里面留出一个指针空间用来存放下一个数据块的位置。缺点在于无法直接访问数据块只能通过指针顺序访问文件以及数据块指针消耗了一定的存储空间。隐式链接分配的稳定性较差系统在运行过程中由于软件或者硬件错误导致链表中的指针丢失或损坏会导致文件数据的丢失。「显式链接」它指把用于链接文件各数据块的指针显式地存放在内存的一张链接表中该表在整个磁盘仅设置一张每个表项中存放链接指针指向下一个数据块号。内存中的这样一个表格称为文件分配表File Allocation TableFAT。可通过这种方法解决隐式链表的两个不足不仅显著地提高了检索速度而且大大减少了访问磁盘的次数。但也正是整个表都存放在内存中的关系它的主要的缺点是不适用于大磁盘。
索引的实现是为每个文件创建一个「索引数据块」里面存放的是指向文件数据块的指针列表。另外文件头需要包含指向「索引数据块」的指针这样就可以通过文件头知道索引数据块的位置再通过索引数据块里的索引信息找到对应的数据块。索引的方式优点在于文件的创建、增大、缩小很方便不会有碎片的问题支持顺序读写和随机读写但问题就是存储索引带来的开销可能会因为文件很大导致一个索引数据块存不下索引信息。
链表 索引的组合这种组合称为「链式索引块」它的实现方式是在索引数据块留出一个存放下一个索引数据块的指针于是当一个索引数据块的索引信息用完了就可以通过指针的方式找到下一个索引数据块的信息。那这种方式也会出现前面提到的链表方式的问题万一某个指针损坏了后面的数据也就会无法读取了。
索引 索引的方式这种组合称为「多级索引块」实现方式是通过一个索引块来存放多个索引数据块一层套一层索引。
对以上方法进行总结 Unix 文件系统则总结了以上的优缺点根据文件大小选择不同的存放方式
如果存放文件所需的数据块小于 10 块则采用直接查找的方式如果存放文件所需的数据块超过 10 块则采用一级间接索引方式如果前面两种方式都不够存放大文件则采用二级间接索引方式如果二级间接索引也不够存放大文件这采用三级间接索引方式
则文件头Inode需要包含 13 个指针10个指向数据块的指针和分别指向索引块的三个指针。
这个方案就用在了 Linux Ext 2/3 文件系统里虽然解决大文件的存储但是对于大文件的访问需要大量的查询效率比较低。
空闲空间管理
为了寻找可供保存数据块的空间有三种方法空闲表法、空闲链表法以及位图法。
空闲表法就是为所有空闲空间建立一张表表内容包括空闲区的第一个块号和该空闲区的块个数注意这个方式是连续分配的。当请求分配磁盘空间时系统依次扫描空闲表里的内容直到找到一个合适的空闲区域为止。这种方法仅当有少量的空闲区时才有较好的效果也适用于建立连续文件。
空闲链表法就是使用「链表」的方式来管理空闲空间每一个空闲块里有一个指针指向下一个空闲块这样也能很方便的找到空闲块并管理起来。同样不适合用于大型文件系统。
位图是利用二进制的一位来表示磁盘中一个盘块的使用情况磁盘上所有的盘块都有一个二进制位与之对应。当值为 0 时表示对应的盘块空闲值为 1 时表示对应的盘块已分配。在 Linux 文件系统中就采用了这种方法。
文件系统结构
采用「一个块的位图 一系列的块」外加「一个块的 inode 的位图 一系列的 inode 的结构」能表示的最大空间也就 128M。
在 Linux 文件系统把这个结构称为一个块组那么有 N 多的块组就能够表示 N 大的文件。
目录的存储
普通文件的块里面保存的是文件数据而目录文件的块里面保存的是目录里面一项一项的文件信息。
在目录文件的块中最简单的保存格式就是列表就是一项一项地将目录下的文件信息如文件名、文件 inode、文件类型等列在表里。列表中每一项就代表该目录下的文件的文件名和对应的 inode通过这个 inode就可以找到真正的文件。 为了提升效率保存目录的格式改成哈希表对文件名进行哈希计算把哈希值保存起来如果我们要查找一个目录下面的文件名可以通过名称取哈希。如果哈希能够匹配上就说明这个文件的信息在相应的块里面。
软链接和硬链接
希望给某个文件取个别名那么在 Linux 中可以通过硬链接Hard Link 和软链接Symbolic Link 的方式来实现它们都是比较特殊的文件但是实现方式也是不相同的。
硬链接是多个目录项中的「索引节点」指向一个文件也就是指向同一个 inode但是 inode 是不可能跨越文件系统的每个文件系统都有各自的 inode 数据结构和列表所以硬链接是不可用于跨文件系统的。由于多个目录项都是指向一个 inode那么只有删除文件的所有硬链接以及源文件时系统才会彻底删除该文件。
软链接相当于重新创建一个文件这个文件有独立的 inode但是这个文件的内容是另外一个文件的路径所以访问软链接的时候实际上相当于访问到了另外一个文件所以软链接是可以跨文件系统的甚至目标文件被删除了链接文件还是在的只不过指向的文件找不到了而已。
文件I/O
文件操作的标准库是可以实现数据的缓存那么根据「是否利用标准库缓冲」可以把文件 I/O 分为缓冲 I/O 和非缓冲 I/O
缓冲 I/O利用的是标准库的缓存实现文件的加速访问而标准库再通过系统调用访问文件。非缓冲 I/O直接通过系统调用访问文件不经过标准库缓存。
比方说很多程序遇到换行时才真正输出而换行前的内容其实就是被标准库暂时缓存了起来这样做的目的是减少系统调用的次数毕竟系统调用是有 CPU 上下文切换的开销的。
根据是否「利用操作系统的缓存」可以把文件 I/O 分为直接 I/O 与非直接 I/O
直接 I/O不会发生内核缓存和用户程序之间数据复制而是直接经过文件系统访问磁盘。非直接 I/O读操作时数据从内核缓存中拷贝给用户程序写操作时数据从用户程序拷贝给内核缓存再由内核决定什么时候写入数据到磁盘。
如果使用文件操作类的系统调用函数时指定了 O_DIRECT 标志则表示使用直接 I/O。如果没有设置过默认使用的是非直接 I/O。采用默认方法则在以下几种情况会触发内核缓存写入磁盘
在调用 write 的最后当发现内核缓存的数据太多的时候内核会把数据写到磁盘上用户主动调用 sync内核缓存会刷到磁盘上当内存十分紧张无法再分配页面时也会把内核缓存的数据刷到磁盘上内核缓存的数据的缓存时间超过某个时间时也会把数据刷到磁盘上
阻塞 I/O当用户程序执行 read 线程会被阻塞一直等到内核数据准备好并把数据从内核缓冲区拷贝到应用程序的缓冲区中当拷贝过程完成read 才会返回。注意阻塞等待的是「内核数据准备好」和「数据从内核态拷贝到用户态」这两个过程。非阻塞 I/O非阻塞的 read 请求在数据未准备好的情况下立即返回可以继续往下执行此时应用程序不断轮询内核直到数据准备好内核将数据拷贝到应用程序缓冲区read 调用才可以获取到结果。这里最后一次 read 调用获取数据的过程是一个同步的过程是需要等待的过程。这里的同步指的是内核态的数据拷贝到用户程序的缓存区这个过程。设置了 O_NONBLOCK 标志那么就表示使用的是非阻塞 I/O 的方式访问而不做任何设置的话默认是阻塞 I/O。
为了解决轮询 I/O 多路复用技术就出来了如 select、poll它是通过 I/O 事件分发当内核数据准备好时再以事件通知应用程序进行操作。最大的优势在于用户可以在一个线程内同时处理多个 socket 的 IO 请求。
总结一下无论是阻塞 I/O、非阻塞 I/O还是基于非阻塞 I/O 的多路复用都是同步调用。因为它们在 read 调用时内核将数据从内核空间拷贝到应用程序空间过程都是需要等待的也就是说这个过程是同步的如果内核实现的拷贝效率不高read 调用就会在这个同步过程中等待比较长的时间。而真正的异步 I/O 是「内核数据准备好」和「数据从内核态拷贝到用户态」这两个过程都不用等待。
真正的异步是发起 aio_read 之后就立即返回内核自动将数据从内核空间拷贝到应用程序空间这个拷贝过程同样是异步的内核自动完成的和前面的同步操作不一样应用程序并不需要主动发起拷贝动作。
整个 I/O 过程分为两个过程的
数据准备的过程数据从内核空间拷贝到用户进程缓冲区的过程
阻塞 I/O 会阻塞在「过程 1 」和「过程 2」而非阻塞 I/O 和基于非阻塞 I/O 的多路复用只会阻塞在「过程 2」所以这三个都可以认为是同步 I/O。异步 I/O 则不同「过程 1 」和「过程 2 」都不会阻塞。
进程写文件时的缓存
进程写文件使用缓冲 IO过程中写一半的时候进程发生了崩溃已写入的数据不会丢失 进程在执行 write 使用缓冲 IO系统调用的时候实际上是将文件数据写到了内核的 page cache它是文件系统中用于缓存文件数据的缓冲所以即使进程崩溃了文件数据还是保留在内核的 page cache我们读数据的时候也是从内核的 page cache 读取因此还是依然读的进程崩溃前写入的数据。内核会找个合适的时机将 page cache 中的数据持久化到磁盘。但是如果 page cache 里的文件数据在持久化到磁盘化到磁盘之前系统发生了崩溃那这部分数据就会丢失了。在程序里调用 fsync 函数在写文文件的时候立刻将文件数据持久化到磁盘这样就可以解决系统崩溃导致的文件数据丢失的问题。
Page Cache
Page Cache 的本质是由 Linux 内核管理的内存区域。通过 mmap 以及 buffered I/O 将文件读取到内存空间实际上都是读取到 Page Cache 中。
Page Cache Buffers Cached SwapCached。
page 是内存管理分配的基本单位 Page Cache 由多个 page 构成。page 在操作系统中通常为 4KB 大小32bits/64bits而 Page Cache 的大小则为 4KB 的整数倍。
Linux 系统上供用户可访问的内存分为两个类型即
File-backed pages文件备份页也就是 Page Cache 中的 page对应于磁盘上的若干数据块对于这些页最大的问题是脏页回盘Anonymous pages匿名页不对应磁盘上的任何磁盘数据块它们是进程的运行是内存空间例如方法栈、局部变量表等属性
Swap 机制指的是当物理内存不够用内存管理单元Memory Mangament UnitMMU需要提供调度算法来回收相关内存空间然后将清理出来的内存空间给当前内存申请方。也就是之前一直说到的缺页中断之后主内存没有可用空间操作系统会从选择合适的物理内存页驱逐回磁盘为新的内存页让出位置选择待驱逐页的过程在操作系统中叫做页面替换Page Replacement替换操作又会触发 swap 机制。
Linux 通过一个 swappiness 参数来控制 Swap 机制这个参数值可为 0-100控制系统 swap 的优先级
高数值较高频率的 swap进程不活跃时主动将其转换出物理内存。低数值较低频率的 swap这可以确保交互式不因为内存空间频繁地交换到磁盘而提高响应延迟。
SwapCached 也是 Page Cache 的一部分。这是因为当匿名页Inactive(anon) 以及 Active(anon)先被交换swap out到磁盘上后然后再加载回swap in内存中由于读入到内存后原来的 Swap File 还在所以 SwapCached 也可以认为是 File-backed page即属于 Page Cache。
**Page Cache 用于缓存文件的页数据buffer cache 用于缓存块设备如磁盘的块数据。**两者的共同目的都是加速数据 I/O。在 Linux 2.4 版本内核之后两块缓存近似融合在了一起如果一个文件的页加载到了 Page Cache那么同时 buffer cache 只需要维护块指向页的指针就可以了。现在提起 Page Cache基本上都同时指 Page Cache 和 buffer cache 两者。
操作系统为基于 Page Cache 的读缓存机制提供预读机制PAGE_READAHEAD。
Page Cache与文件持久化的一致性可靠性
Linux 提供多种机制来保证数据一致性但无论是单机上的内存与磁盘一致性还是分布式组件中节点 1 与节点 2 、节点 3 的数据一致性问题理解的关键是 trade-off吞吐量与数据一致性保证是一对矛盾。
首先需要我们理解一下文件的数据。文件 数据 元数据。元数据用来描述文件的各种属性也必须存储在磁盘上。因此我们说保证文件一致性其实包含了两个方面数据一致元数据一致。
当前 Linux 下以两种方式实现文件一致性
Write Through写穿向用户层提供特定接口应用程序可主动调用接口来保证文件一致性Write back写回系统中存在定期任务表现形式为内核线程周期性地同步文件系统中文件脏数据块这是默认的 Linux 一致性方案
Write Through 与 Write back 在持久化的可靠性上有所不同
Write Through 以牺牲系统 I/O 吞吐量作为代价向上层应用确保一旦写入数据就已经落盘不会丢失Write back 在系统发生宕机的情况下无法确保数据已经落盘因此存在数据丢失的问题。不过在程序挂了例如被 kill -9Page Cache 中的数据操作系统还是会确保落盘
Page Cache 优劣势
优势
加快数据访问减少 I/O 次数提高系统磁盘 I/O 吞吐量
劣势
最直接的缺点是需要占用额外物理内存空间物理内存在比较紧俏的时候可能会导致频繁的 swap 操作最终导致系统的磁盘 I/O 负载的上升。
Page Cache 的另一个缺陷是对应用层并没有提供很好的管理 API几乎是透明管理。
最后一个缺陷是在某些应用场景下比 Direct I/O 多一次磁盘读 I/O 以及磁盘写 I/O。
设备管理
为了屏蔽设备之间的差异每个设备都有一个叫设备控制器Device Control 的组件比如硬盘有硬盘控制器、显示器有视频控制器等。 设备控制器里有芯片它可执行自己的逻辑也有自己的寄存器用来与 CPU 进行通信。控制器是有三类寄存器它们分别是状态寄存器Status Register、 命令寄存器Command Register以及数据寄存器Data Register。
输入输出设备可分为两大类 块设备Block Device和字符设备Character Device。
块设备把数据存储在固定大小的块中每个块有自己的地址硬盘、USB 是常见的块设备。字符设备以字符为单位发送或接收一个字符流字符设备是不可寻址的也没有任何寻道操作鼠标是常见的字符设备。
块设备通常传输的数据量会非常大于是控制器设立了一个可读写的数据缓冲区。
I/O 控制方式
设备控制器对 CPU 的通知方法可以通过查询控制器的寄存器的状态标志位通过轮询来完成但这会占用 CPU 的全部时间。
也可以通过中断来通知 CPU。中断有两种一种软中断例如代码调用 INT 指令触发一种是硬件中断就是硬件通过中断控制器触发的。但中断的方式对于频繁读写数据的磁盘并不友好这样 CPU 容易经常被打断会占用 CPU 大量的时间。对于这一类设备的问题的解决方法是使用 DMADirect Memory Access 功能它可以使得设备在 CPU 不参与的情况下能够自行完成把设备 I/O 数据放入到内存。那要实现 DMA 功能要有 「DMA 控制器」硬件的支持。 CPU 当要读取磁盘数据的时候只需给 DMA 控制器发送指令然后返回去做其他事情当磁盘数据拷贝到内存后DMA 控制机器通过中断的方式告诉 CPU 数据已经准备好了可以从内存读数据了。仅仅在传送开始和结束时需要 CPU 干预。
设备驱动程序
每种设备的控制器的寄存器、缓冲区等使用模式都是不同的所以为了屏蔽「设备控制器」的差异引入了设备驱动程序。设备驱动程序会提供统一的接口给操作系统。
通常设备驱动程序初始化的时候要先注册一个该设备的中断处理函数。 通用块层
Linux 通过一个统一的通用块层来管理不同的块设备。
通用块层是处于文件系统和磁盘驱动中间的一个块设备抽象层它主要有两个功能
第一个功能向上为文件系统和应用程序提供访问块设备的标准接口向下把各种不同的磁盘设备抽象为统一的块设备并在内核层面提供一个框架来管理这些设备的驱动程序第二功能通用层还会给文件系统和应用程序发来的 I/O 请求排队接着会对队列重新排序、请求合并等方式也就是 I/O 调度主要目的是为了提高磁盘读写的效率。
存储系统 I/O 软件分层
把 Linux 存储系统的 I/O 由上到下可以分为三个层次分别是文件系统层、通用块层、设备层。 有了文件系统接口之后不但可以通过文件系统的命令行操作设备也可以通过应用程序调用 read、write 函数就像读写文件一样操作设备所以说设备在 Linux 下也只是一个特殊的文件。
存储系统的 I/O 是整个系统最慢的一个环节所以 Linux 提供了不少缓存机制来提高 I/O 的效率。
为了提高文件访问的效率会使用页缓存、索引节点缓存、目录项缓存等多种缓存机制目的是为了减少对块设备的直接调用。为了提高块设备的访问效率 会使用缓冲区来缓存块设备的数据。
网络系统
零拷贝
为了改善磁盘的 I/O 读写速度CPU会发出对应指令然后磁盘控制器就会把数据传入内部缓冲区并产生中断收到中断信号后 CPU 会把数据读入寄存器然后再写入内存。这一期间 CPU 是不执行其他任务的。所以引入了 DMA 技术也就是直接内存访问Direct Memory Access 技术。在进行 I/O 设备和内存的数据传输的时候数据搬运的工作全部交给 DMA 控制器而 CPU 不再参与任何与数据搬运相关的事情这样 CPU 就可以去处理别的事务。 CPU 不再参与「将数据从磁盘控制器缓冲区搬运到内核空间」的工作这部分工作全程由 DMA 完成。
针对网络传输如果服务端需要文件传输传统方法就是从磁盘读出再通过网络协议发给客户端。这个过程中调用系统调用 read 和 write会发生 4 次用户态和内核态的上下文切换还发生了 4 次数据拷贝两次 DMA 和两次 CPU 拷贝。所以要想提高文件传输的性能就需要减少「用户态与内核态的上下文切换」和「内存拷贝」的次数。
减少上下文切换就要减少系统调用次数。针对传统传输需要将数据通过用户缓冲区来完成传输但实质上用户空间内并不需要处理数据因此用户的缓冲区是没有必要存在的。
零拷贝一共 2 种实现方法
mmap writesendfile
mmap write
read() 系统调用的过程中会把内核缓冲区的数据拷贝到用户的缓冲区里于是为了减少这一步开销我们可以用 mmap() 替换 read() 系统调用函数。
buf mmap(file, len);
write(sockfd, buf, len);mmap() 系统调用函数会直接把内核缓冲区里的数据「映射」到用户空间这样操作系统内核与用户空间就不需要再进行任何的数据拷贝操作。此时 mmap() 通过 DMA 把磁盘数据拷贝到内核缓冲区并与进程共享缓冲区之后调用 write() 那么操作系统会直接将内核缓冲区数据拷贝到 socket 缓冲区最后由 DMA 把 socket 缓冲区数据拷贝到网卡缓冲区。那么 mmap() 替换 read() 就可以减少一次数据拷贝。
sendfile
在 LInux 内核 2.1 中提供了专门发送文件的系统调用 sendfile() 如下
#include sys/socket.h
ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);可以替代前面的 read() 和 write() 这两个系统调用这样就可以减少一次系统调用也就减少了 2 次上下文切换的开销。并且该系统调用可以直接把内核缓冲区里的数据拷贝到 socket 缓冲区里不再拷贝到用户态这样就只有 2 次上下文切换和 3 次数据拷贝。如下图
如果网卡支持 SG-DMAThe Scatter-Gather Direct Memory Access技术和普通的 DMA 有所不同我们可以进一步减少通过 CPU 把内核缓冲区里的数据拷贝到 socket 缓冲区的过程。可以查看网卡是否支持 scatter-gather 特性
$ ethtool -k eth0 | grep scatter-gather
scatter-gather: on从 Linux 2.4 开始sendfile() 开始支持 SG-DMA 技术更加优化
第一步通过 DMA 将磁盘上的数据拷贝到内核缓冲区里第二步缓冲区描述符和数据长度传到 socket 缓冲区这样网卡的 SG-DMA 控制器就可以直接将内核缓存中的数据拷贝到网卡的缓冲区里此过程不需要将数据从操作系统内核缓冲区拷贝到 socket 缓冲区中这样就减少了一次数据拷贝
此时就只需要 2 次数据拷贝 这就是零拷贝Zero-copy技术因为我们没有在内存层面去拷贝数据也就是说全程没有通过 CPU 来搬运数据所有的数据都是通过 DMA 来进行传输的。零拷贝技术的文件传输方式相比传统文件传输的方式减少了 2 次上下文切换和数据拷贝次数只需要 2 次上下文切换和数据拷贝次数就可以完成文件的传输而且 2 次的数据拷贝过程都不需要通过 CPU2 次都是由 DMA 来搬运。所以总体来看零拷贝技术可以把文件传输的性能提高至少一倍以上。
文件传输过程其中第一步都是先需要先把磁盘文件数据拷贝「内核缓冲区」里这个「内核缓冲区」实际上是磁盘高速缓存PageCache。读写磁盘相比读写内存的速度慢太多了所以我们应该想办法把「读写磁盘」替换成「读写内存」。于是我们会通过 DMA 把磁盘里的数据搬运到内存里这样就可以用读内存替换读磁盘。而内存很小就可以用 PageCache 来缓存最近被访问的数据而且 PageCache 运用了 「预读功能」使得读取后面的顺序数据非常方便。但是在传输大文件GB 级别的文件的时候PageCache 会不起作用那就白白浪费 DMA 多做的一次数据拷贝造成性能的降低即使使用了 PageCache 的零拷贝也会损失性能。
之前最开始说的 CPU 会阻塞等待的问题可以通过异步 I/O 来解决 异步 I/O 并不涉及 PageCache使用 PageCache 的 I/O 是缓存 I/O而通常对于磁盘异步 I/O 只支持直接 I/O。
在高并发的场景下针对大文件的传输的方式应该使用「异步 I/O 直接 I/O」来替代零拷贝技术。
所以传输文件的时候我们要根据文件的大小来使用不同的方式
传输大文件的时候使用「异步 I/O 直接 I/O」传输小文件的时候则使用「零拷贝技术」
I/O 多路复用
服务端的 Socket 编程如下
服务端首先调用 socket() 函数创建网络协议为 IPv4以及传输协议为 TCP 的 Socket 接着调用 bind() 函数给这个 Socket 绑定一个 IP 地址和端口绑定这两个的目的是什么
绑定端口的目的当内核收到 TCP 报文通过 TCP 头里面的端口号来找到我们的应用程序然后把数据传递给我们。绑定 IP 地址的目的一台机器是可以有多个网卡的每个网卡都有对应的 IP 地址当绑定一个网卡时内核在收到该网卡上的包才会发给我们
绑定完 IP 地址和端口后就可以调用 listen() 函数进行监听此时对应 TCP 状态图中的 listen如果我们要判定服务器中一个网络程序有没有启动可以通过 netstat 命令查看对应的端口号是否有被监听。服务端进入了监听状态后通过调用 accept() 函数来从内核获取客户端的连接如果没有客户端连接则会阻塞等待客户端连接的到来。
客户端发起连接如下
客户端在创建好 Socket 后调用 connect() 函数发起连接该函数的参数要指明服务端的 IP 地址和端口号然后万众期待的 TCP 三次握手就开始了。在 TCP 连接的过程中服务器的内核实际上为每个 Socket 维护了两个队列
一个是「还没完全建立」连接的队列称为 TCP 半连接队列这个队列都是没有完成三次握手的连接此时服务端处于 syn_rcvd 的状态一个是「已经建立」连接的队列称为 TCP 全连接队列这个队列都是完成了三次握手的连接此时服务端处于 established 状态
当 TCP 全连接队列不为空后服务端的 accept() 函数就会从内核中的 TCP 全连接队列里拿出一个已经完成连接的 Socket 返回应用程序后续数据传输都用这个 Socket。
这里有两个 Socket一个是监听的一个是真正传输数据的。 以上的 TCP Socket 调用流程基本只能一对一通信使用的是同步阻塞服务端没处理完一个客户端的网络 I/O 或者是读写阻塞其他客户端就无法连接服务端。
TCP 连接是由四元组唯一确认的这个四元组就是本机IP, 本机端口, 对端IP, 对端端口。
服务器作为服务方通常会在本地固定监听一个端口等待客户端的连接。因此服务器的本地 IP 和端口是固定的于是对于服务端 TCP 连接的四元组只有对端 IP 和端口是会变化的所以最大 TCP 连接数 客户端 IP 数×客户端端口数。
对于 IPv4客户端的 IP 数最多为 2 的 32 次方客户端的端口数最多为 2 的 16 次方也就是服务端单机最大 TCP 连接数约为 2 的 48 次方。服务器肯定承载不了那么大的连接数主要会受两个方面的限制
文件描述符Socket 实际上是一个文件也就会对应一个文件描述符。在 Linux 下单个进程打开的文件描述符数是有限制的没有经过修改的值一般都是 1024不过我们可以通过 ulimit 增大文件描述符的数目系统内存每个 TCP 连接在内核中都有对应的数据结构意味着每个连接都是会占用一定内存的
多进程模型
基于最原始的阻塞网络 I/O 如果服务器要支持多个客户端其中比较传统的方式就是使用多进程模型也就是为每个客户端分配一个进程来处理请求。服务器的主进程负责监听客户的连接一旦与客户端连接完成accept() 函数就会返回一个「已连接 Socket」这时就通过 fork() 函数创建一个子进程实际上就把父进程所有相关的东西都复制一份包括文件描述符、内存地址空间、程序计数器、执行的代码等。这两个进程刚复制完的时候几乎一模一样。不过会根据返回值来区分是父进程还是子进程如果返回值是 0则是子进程如果返回值是其他的整数就是父进程。可以直接使用「已连接 Socket 」和客户端通信了。
针对这种方法子进程不需要关心「监听 Socket」只需要关心「已连接 Socket」父进程则相反将客户服务交给子进程来处理因此父进程不需要关心「已连接 Socket」只需要关心「监听 Socket」。
当**「子进程」退出时实际上内核里还会保留该进程的一些信息也是会占用内存的**如果不做好“回收”工作就会变成僵尸进程随着僵尸进程越多会慢慢耗尽我们的系统资源。有两种方式可以在子进程退出后回收资源分别是调用 wait() 和 waitpid() 函数。
进程间上下文切换非常占用资源所以很难满足大量客户端的需求。
多线程模型
线程是运行在进程中的一个“逻辑流”单进程中可以运行多个线程同进程里的线程可以共享进程的部分资源比如文件描述符列表、进程空间、代码、全局数据、堆、共享库等这些共享些资源在上下文切换时不需要切换而只需要切换线程的私有数据、寄存器等不共享的数据因此同一个进程下的线程上下文切换的开销要比进程小得多。所以可以通过多线程模型来应对多用户的需求。
当服务器与客户端 TCP 完成连接后通过 pthread_create() 函数创建线程然后将「已连接 Socket」的文件描述符传递给线程函数接着在线程里和客户端进行通信从而达到并发处理的目的。可以使用线程池的方式来避免线程的频繁创建和销毁所谓的线程池就是提前创建若干个线程这样当由新连接建立时将这个已连接的 Socket 放入到一个队列里然后线程池里的线程负责从队列中取出「已连接 Socket 」进行处理。这个队列是全局的每个线程都会操作为了避免多线程竞争线程在操作这个队列前要加锁。
I/O多路复用
为每个请求分配一个进程/线程的方式不合适那有没有可能只使用一个进程来维护多个 Socket 呢答案是有的那就是 I/O 多路复用技术。
一个进程虽然任一时刻只能处理一个请求但是处理每个请求的事件时耗时控制在 1 毫秒以内这样 1 秒内就可以处理上千个请求把时间拉长来看多个请求复用了一个进程这就是多路复用这种思想很类似一个 CPU 并发多个进程所以也叫做时分多路复用。进程可以通过一个系统调用函数从内核中获取多个事件。
select 实现多路复用的方式是将已连接的 Socket 都放到一个文件描述符集合然后调用 select 函数将文件描述符集合拷贝到内核里让内核来检查是否有网络事件产生检查的方式很粗暴就是通过遍历文件描述符集合的方式当检查到有事件产生后将此 Socket 标记为可读或可写 接着再把整个文件描述符集合拷贝回用户态里然后用户态还需要再通过遍历的方法找到可读或可写的 Socket然后再对其处理。所以对于 select 这种方式需要进行 2 次「遍历」文件描述符集合一次是在内核态里一个次是在用户态里 而且还会发生 2 次「拷贝」文件描述符集合先从用户空间传入内核空间由内核修改后再传出到用户空间中。select 使用固定长度的 BitsMap表示文件描述符集合在 Linux 系统中由内核中的 FD_SETSIZE 限制 默认最大值为 1024只能监听 0~1023 的文件描述符。
poll 不再用 BitsMap 来存储所关注的文件描述符取而代之用动态数组以链表形式来组织突破了 select 的文件描述符个数限制当然还会受到系统文件描述符限制。
但是 poll 和 select 并没有太大的本质区别都是使用「线性结构」存储进程关注的 Socket 集合因此都需要遍历文件描述符集合来找到可读或可写的 Socket时间复杂度为 O(n)而且也需要在用户态与内核态之间拷贝文件描述符集合这种方式随着并发数上来性能的损耗会呈指数级增长。
对于 epoll 而言先用epoll_create 创建一个 epol l对象 epfd再通过 epoll_ctl 将需要监视的 socket 添加到epfd中最后调用 epoll_wait 等待数据。epoll 在内核里使用红黑树来跟踪进程所有待检测的文件描述字把需要监控的 socket 通过 epoll_ctl() 函数加入内核中的红黑树里红黑树是个高效的数据结构增删改一般时间复杂度是 O(logn)。epoll 使用事件驱动的机制内核里维护了一个链表来记录就绪事件当某个 socket 有事件发生时通过回调函数内核会将其加入到这个就绪事件列表中当用户调用 epoll_wait() 函数时只会返回有事件发生的文件描述符的个数不需要像 select/poll 那样轮询扫描整个 socket 集合大大提高了检测的效率。
所以解决多用户请求的问题大多使用 epoll 来完成 epoll 支持两种事件触发模式分别是边缘触发edge-triggeredET和水平触发level-triggeredLT。
使用边缘触发模式时当被监控的 Socket 描述符上有可读事件发生时服务器端只会从 epoll_wait 中苏醒一次即使进程没有调用 read 函数从内核读取数据也依然只苏醒一次因此我们程序要保证一次性将内核缓冲区的数据读取完使用水平触发模式时当被监控的 Socket 上有可读事件发生时服务器端不断地从 epoll_wait 中苏醒直到内核缓冲区数据被 read 函数读完才结束目的是告诉我们有数据需要读取
如果使用边缘触发模式I/O 事件发生时只会通知一次而且我们不知道到底能读写多少数据所以在收到通知后应尽可能地读写数据以免错失读写的机会。因此我们会循环从文件描述符读写数据那么如果文件描述符是阻塞的没有数据可读写时进程会阻塞在读写函数那里程序就没办法继续往下执行。所以边缘触发模式一般和非阻塞 I/O 搭配使用程序会一直执行 I/O 操作直到系统调用如 read 和 write返回错误错误类型为 EAGAIN 或 EWOULDBLOCK。
一般来说边缘触发的效率比水平触发的效率要高因为边缘触发可以减少 epoll_wait 的系统调用次数系统调用也是有一定的开销的的毕竟也存在上下文的切换。select/poll 只有水平触发模式epoll 默认的触发模式是水平触发但是可以根据应用场景设置为边缘触发模式。
高性能网络模式Reactor 和 Proactor
基于 I/O 多路复用是面向过程的方式写代码的这样的开发的效率不高所以基于面向对象的思想对 I/O 多路复用作了一层封装并取了 Reactor 模型的名字。Reactor 模式也叫 Dispatcher 模式即 I/O 多路复用监听事件收到事件后根据事件类型分配Dispatch给某个进程 / 线程。
Reactor 模式主要由 Reactor 和处理资源池这两个核心部分组成它俩负责的事情如下
Reactor 负责监听和分发事件事件类型包含连接事件、读写事件处理资源池负责处理事件如 read - 业务逻辑 - send
Reactor 模式是灵活多变的可以应对不同的业务场景灵活在于
Reactor 的数量可以只有一个也可以有多个处理资源池可以是单个进程 / 线程也可以是多个进程 /线程
常用的有 3 个方案
单 Reactor 单进程 / 线程单 Reactor 多线程 / 进程多 Reactor 多进程 / 线程
单 Reactor 单进程 / 线程
一般来说C 语言实现的是「单 Reactor 单进程」的方案因为 C 语编写完的程序运行后就是一个独立的进程不需要在进程中再创建线程。 对象里的 select、accept、read、send 是系统调用函数dispatch 和 「业务处理」是需要完成的操作其中 dispatch 是分发事件操作。
单 Reactor 单进程的方案因为全部工作都在同一个进程内完成所以实现起来比较简单不需要考虑进程间通信也不用担心多进程竞争。但是这种方案存在 2 个缺点
第一个缺点因为只有一个进程无法充分利用多核 CPU 的性能第二个缺点Handler 对象在业务处理时整个进程是无法处理其他连接的事件的如果业务处理耗时比较长那么就造成响应的延迟
所以单 Reactor 单进程的方案不适用计算机密集型的场景只适用于业务处理非常快速的场景。
单 Reactor 多线程/多进程
要克服「单 Reactor 单线程 / 进程」方案的缺点那么就需要引入多线程 / 多进程这样就产生了单 Reactor 多线程 / 多进程的方案。 这里与单进程的区别在于
Handler 对象不再负责业务处理只负责数据的接收和发送Handler 对象通过 read 读取到数据后会将数据发给子线程里的 Processor 对象进行业务处理子线程里的 Processor 对象就进行业务处理处理完后将结果发给主线程中的 Handler 对象接着由 Handler 通过 send 方法将响应结果发送给 client
单 Reator 多线程的方案优势在于能够充分利用多核 CPU 的性能那既然引入多线程那么自然就带来了多线程竞争资源的问题。避免多线程由于竞争共享资源而导致数据错乱的问题就需要在操作共享资源前加上互斥锁以保证任意时间里只有一个线程在操作共享资源待该线程操作完释放互斥锁后其他线程才有机会操作共享数据。
单 Reactor 多进程相比单 Reactor 多线程实现起来很麻烦主要因为要考虑子进程 - 父进程的双向通信并且父进程还得知道子进程要将数据发送给哪个客户端。而多线程间可以共享数据虽然要额外考虑并发问题但是这远比进程间通信的复杂度低得多因此实际应用中也看不到单 Reactor 多进程的模式。
「单 Reactor」的模式还有个问题因为一个 Reactor 对象承担所有事件的监听和响应而且只在主线程中运行在面对瞬间高并发的场景时容易成为性能的瓶颈的地方。
多 Reactor 多进程/线程
要解决「单 Reactor」的问题就是将「单 Reactor」实现成「多 Reactor」这样就产生了第 多 Reactor 多进程 / 线程的方案。 多 Reactor 多线程的方案虽然看起来复杂的但是实际实现时比单 Reactor 多线程的方案要简单的多原因如下
主线程和子线程分工明确主线程只负责接收新连接子线程负责完成后续的业务处理。主线程和子线程的交互很简单主线程只需要把新连接传给子线程子线程无须返回数据直接就可以在子线程将处理结果发送给客户端。
Proactor
前面提到的 Reactor 是非阻塞同步网络模式而 Proactor 是异步网络模式。
这里再强调一次无论 read 和 send 是阻塞 I/O还是非阻塞 I/O 都是同步调用。因为在 read 调用时内核将数据从内核空间拷贝到用户空间的过程都是需要等待的也就是说这个过程是同步的如果内核实现的拷贝效率不高read 调用就会在这个同步过程中等待比较长的时间。而真正的异步 I/O 是「内核数据准备好」和「数据从内核态拷贝到用户态」这两个过程都不用等待。
发起 aio_read 异步 I/O 之后就立即返回内核自动将数据从内核空间拷贝到用户空间这个拷贝过程同样是异步的内核自动完成的和前面的同步操作不一样应用程序并不需要主动发起拷贝动作。
对比一下 Reactor 和 Proactor 的区别
Reactor 是非阻塞同步网络模式感知的是就绪可读写事件。在每次感知到有事件发生比如可读就绪事件后就需要应用进程主动调用 read 方法来完成数据的读取也就是要应用进程主动将 socket 接收缓存中的数据读到应用进程内存中这个过程是同步的读取完数据后应用进程才能处理数据。Proactor 是异步网络模式 感知的是已完成的读写事件。在发起异步读写请求时需要传入数据缓冲区的地址用来存放结果数据等信息这样系统内核才可以自动帮我们把数据的读写工作完成这里的读写工作全程由操作系统来做并不需要像 Reactor 那样还需要应用进程主动发起 read/write 来读写数据操作系统完成读写工作后就会通知应用进程直接处理数据。
Reactor 可以理解为「来了事件操作系统通知应用进程让应用进程来处理」而 Proactor 可以理解为「来了事件操作系统来处理处理完再通知应用进程」。这里的「事件」就是有新连接、有数据可读、有数据可写的这些 I/O 事件这里的「处理」包含从驱动读取到内核以及从内核读取到用户空间。无论是 Reactor还是 Proactor都是一种基于「事件分发」的网络编程模式区别在于 Reactor 模式是基于「待完成」的 I/O 事件而 Proactor 模式则是基于「已完成」的 I/O 事件。 在 Linux 下的异步 I/O 是不完善的 aio 系列函数是由 POSIX 定义的异步操作接口不是真正的操作系统级别支持的而是在用户空间模拟出来的异步并且仅仅支持基于本地文件的 aio 异步操作网络编程中的 socket 是不支持的这也使得基于 Linux 的高性能网络程序都是使用 Reactor 方案。
而 Windows 里实现了一套完整的支持 socket 的异步编程接口这套接口就是 IOCP是由操作系统级别实现的异步 I/O真正意义上异步 I/O因此在 Windows 里实现高性能网络程序可以使用效率更高的 Proactor 方案。
一致性哈希
大多数网站背后肯定不是只有一台服务器提供服务因为单机的并发量和数据量都是有限的所以都会用多台服务器构成集群来对外提供服务。那如何来分配客户端的请求就很重要。
这个问题就是「负载均衡问题」。解决负载均衡问题的算法很多不同的负载均衡算法对应的就是不同的分配策略适应的业务场景也不同。
最简单的方式引入一个中间的负载均衡层让它将外界的请求「轮流」的转发给内部的集群。可以引入权重值将硬件配置更好的节点的权重值设高然后根据各个节点的权重值按照一定比重分配在不同的节点上让硬件配置更好的节点承担更多的请求这种算法叫做加权轮询。
加权轮询算法使用场景是建立在每个节点存储的数据都是相同的前提。但是加权轮询算法是无法应对「分布式系统数据分片的系统」的因为分布式系统中每个节点存储的数据是不同的。
想提高系统的容量就会将数据水平切分到不同的节点来存储也就是将数据分布到了不同的节点。比如一个分布式 KVkey-valu 缓存系统某个 key 应该到哪个或者哪些节点上获得应该是确定的不是说任意访问一个节点都可以得到缓存结果的。
这个映射可以想到哈希算法但是如果节点数量发生了变化也就是在对系统做扩容或者缩容时必须迁移改变了映射关系的数据否则会出现查询不到数据的问题。这就需要我们进行迁移数据假设总数据条数为 M哈希算法在面对节点数量变化时最坏情况下所有数据都需要迁移所以它的数据迁移规模是 O(M)这样数据的迁移成本太高了。
一致性哈希算法就很好地解决了分布式系统在扩容或者缩容时发生过多的数据迁移的问题。一致哈希算法也用了取模运算但与哈希算法不同的是哈希算法是对节点的数量进行取模运算而一致哈希算法是对 2^32 进行取模运算是一个固定的值。
一致性哈希是需要两次哈希操作的一致性哈希是指将「存储节点」和「数据」都映射到一个首尾相连的哈希环上。对「数据」进行哈希映射得到一个结果映射的结果值往顺时针的方向的找到第一个节点就是存储该数据的节点。也就是说需要对指定的 key 值进行读写需要 2 步
首先对 key 进行哈希计算确定此 key 在环上的位置然后从这个位置沿着顺时针方向走遇到的第一节点就是存储 key 的节点。
在一致哈希算法中如果增加或者移除一个节点仅影响该节点在哈希环上顺时针相邻的后继节点其它数据也不会受到影响。但是一致性哈希算法并不保证节点能够在哈希环上分布均匀这样就会带来一个问题会有大量的请求集中在一个节点上。所以一致性哈希算法虽然减少了数据迁移量但是存在节点分布不均匀的问题。
要想解决节点能在哈希环上分配不均匀的问题就是要有大量的节点节点数越多哈希环上的节点分布的就越均匀。但问题是实际中我们没有那么多节点。所以这个时候就加入虚拟节点也就是对一个真实节点做多个副本。具体做法是不再将真实节点映射到哈希环上而是将虚拟节点映射到哈希环上并将虚拟节点映射到实际节点所以这里有「两层」映射关系。虚拟节点除了会提高节点的均衡度还会提高系统的稳定性。当节点变化时会有不同的节点共同分担系统的变化因此稳定性更高。带虚拟节点的一致性哈希方法不仅适合硬件配置不同的节点的场景而且适合节点规模会发生变化的场景。
Linux 命令
查看网络性能指标
Linux 网络协议栈是根据 TCP/IP 模型来实现的TCP/IP 模型由应用层、传输层、网络层和网络接口层共四层组成每一层都有各自的职责。 通常是以 4 个指标来衡量网络的性能分别是带宽、延时、吞吐率、PPSPacket Per Second它们表示的意义如下
带宽表示链路的最大传输速率单位是 b/s 比特 / 秒带宽越大其传输能力就越强。延时表示请求数据包发送后收到对端响应所需要的时间延迟。不同的场景有着不同的含义比如可以表示建立 TCP 连接所需的时间延迟或一个数据包往返所需的时间延迟。吞吐率表示单位时间内成功传输的数据量单位是 b/s比特 / 秒或者 B/s字节 / 秒吞吐受带宽限制带宽越大吞吐率的上限才可能越高。PPS全称是 Packet Per Second包 / 秒表示以网络包为单位的传输速率一般用来评估系统对于网络的转发能力。
当然除了以上这四种基本的指标还有一些其他常用的性能指标比如
网络的可用性表示网络能否正常通信并发连接数表示 TCP 连接数量丢包率表示所丢失数据包数量占所发送数据组的比率重传率表示重传网络包的比例
网络配置
可以使用 ifconfig 或者 ip 命令来查看。这两个命令功能都差不多不过它们属于不同的软件包ifconfig 属于 net-tools 软件包ip 属于 iproute2 软件包我的印象中 net-tools 软件包没有人继续维护了而 iproute2 软件包是有开发者依然在维护所以更推荐你使用 ip 工具。 第一网口的连接状态标志。其实也就是表示对应的网口是否连接到交换机或路由器等设备如果 ifconfig 输出中看到有 RUNNING或者 ip 输出中有 LOWER_UP则说明物理网络是连通的如果看不到则表示网口没有接网线。
第二MTU 大小。默认值是 1500 字节其作用主要是限制网络包的大小如果 IP 层有一个数据报要传而且网络包的长度比链路层的 MTU 还大那么 IP 层就需要进行分片即把数据报分成若干片这样每一片就都小于 MTU。事实上每个网络的链路层 MTU 可能会不一样所以你可能需要调大或者调小 MTU 的数值。
第三网口的 IP 地址、子网掩码、MAC 地址、网关地址。这些信息必须要配置正确网络功能才能正常工作。
第四网络包收发的统计信息。通常有网络收发的字节数、包数、错误数以及丢包情况的信息如果 TX发送 和 RX接收 部分中 errors、dropped、overruns、carrier 以及 collisions 等指标不为 0 时则说明网络发送或者接收出问题了。
socket 信息
可以使用 netstat 或者 ss这两个命令查看 socket、网络协议栈、网口以及路由表的信息。其中 ss 命令性能更好。 都包含了 socket 的状态State、接收队列Recv-Q、发送队列Send-Q、本地地址Local Address、远端地址Foreign Address、进程 PID 和进程名称PID/Program name等。
接收队列Recv-Q和发送队列Send-Q比较特殊在不同的 socket 状态。它们表示的含义是不同的。
当 socket 状态处于 Established时
Recv-Q 表示 socket 缓冲区中还没有被应用程序读取的字节数Send-Q 表示 socket 缓冲区中还没有被远端主机确认的字节数
而当 socket 状态处于 Listen 时
Recv-Q 表示全连接队列的长度Send-Q 表示全连接队列的最大长度
网络吞吐率和 PPS
可以使用 sar 命令当前网络的吞吐率和 PPS用法是给 sar 增加 -n 参数就可以查看网络的统计信息比如
sar -n DEV显示网口的统计数据sar -n EDEV显示关于网络错误的统计数据sar -n TCP显示 TCP 的统计数据
对于带宽我们可以使用 ethtool 命令来查询它的单位通常是 Gb/s 或者 Mb/s不过注意这里小写字母 b 表示比特而不是字节。
连通性和延时
要测试本机与远程主机的连通性和延时通常是使用 ping 命令它是基于 ICMP 协议的工作在网络层。
从日志分析 PV、NV
日志涵盖的信息远不止于此比如对于 nginx 的 access.log 日志我们可以根据日志信息分析用户行为。比如分析出哪个页面访问次数PV最多访问人数UV最多以及哪天访问量最多哪个请求访问最多等等。
要分析日志的时候先用 ls -lh 命令查看日志文件的大小如果日志文件大小非常大最好不要在线上环境做。当发现日志很大的时候我们可以使用 scp 命令将文件传输到闲置的服务器再分析。
对于大文件我们应该养成好习惯用 less 命令去读文件里的内容而不是直接用 cat 来查看文件内容。想看日志最新部分的内容可以使用 tail 命令。想实时看日志打印的内容你可以使用 tail -f 命令。
PV 分析
PV 的全称叫 Page View用户访问一个页面就是一次 PV比如大多数博客平台点击一次页面阅读量就加 1所以说 PV 的数量并不代表真实的用户数量只是个点击量。对于 nginx 的 acess.log 日志文件来说直接使用 wc -l 命令就可以查看整体的 PV 了。
按时间分组首先我们先「访问时间」过滤出来这里可以使用 awk 命令来处理awk 是一个处理文本的利器。awk 命令默认是以「空格」为分隔符由于访问时间在日志里的第 4 列因此可以使用 awk ‘{print $4}’ access.log 命令把访问时间的信息过滤出来。如果只想显示年月日的信息可以使用 awk 的 substr 函数可以使用 sort 对日期进行排序然后使用 uniq -c 进行统计于是按天分组的 PV 就出来了。使用 uniq -c 命令前先要进行 sort 排序。
UV 分析
UV 的全称是 Uniq Visitor它代表访问人数比如公众号的阅读量就是以 UV 统计的不管单个用户点击了多少次最终只算 1 次阅读量。可以用「客户端 IP 地址」来近似统计 UV。
这里同样可以按天分组分析如下命令相当于把「日期 IP地址」过滤出来并去重 如果需要对当天的 UV 统计在上面的命令再拼接 awk ‘{uv[$1];next}END{for (ip in uv) print ip, uv[ip]}’ 命令就可以了。
终端分析
nginx 的 access.log 日志最末尾关于 User Agent 的信息主要是客户端访问服务器使用的工具可能是手机、浏览器等。User Agent 的信息在日志里的第 12 列因此我们先使用 awk 过滤出第 12 列的内容后进行 sort 排序再用 uniq -c 去重并统计最后再使用 sort -rnr 表示逆向排序 n 表示按数值排序 对统计的结果排序。
分析 TOP3 的请求
access.log 日志中第 7 列是客户端请求的路径先使用 awk 过滤出第 7 列的内容后进行 sort 排序再用 uniq -c 去重并统计然后再使用 sort -rn 对统计的结果排序最后使用 head -n 3 分析 TOP3 的请求。
