透过内存读写看计算机体系结构(三)

前面主要讲了cpu层面的寻址, 接下来, 讲下cache是如何工作的.当然,我们依旧化简成单核的场景的来简单介绍下cache的工作原理.

  • cache的最小管理单元
    cache的最小单元是cacheline,一般是32或者64个字节,在x86上,是64个字节;在arm上,是32个字节
    也就是说,你更新8个字节,其实会更新他所在的完整的64个字节进cacheline, 而不是只有那个8个字节更新了

  • cache的层次结构
    cache会分为多层,离cpu最近的叫做L1,然后是L2, L3(一般只有3层,所以L3也叫做LLC)
    L1容量最小,访问速度最快,离cpu最近
    LLC容量最大.访问速度最慢,离cpu最远
    L2介于两者之间

  • cache的写入方式
    这里用一个例子来做cpu写cache的对比: 我们通过redis做数据库的缓存

    • write-through(x86的cpu几乎不存在这个情况了; arm, mips表示不清楚)
      写cache的行为, 等待写完下一层存储再返回
      更新完redis的数据, 还要等待db的数据更新完, 再返回
    • write-back
      更新完redis的数据, 立即返回, 后台同步redis的数据到db
    • write-combining
      缓存一批需要更新的数据(对于x86来说是4个cacheline), 然后统一通过更新cache(可以是write-back,也可以是write-through)
      积攒一批数据,统一提交给redis, 相当于batch写
  • cache和地址的关系
    cache_set_index = hash(addr)

    • cache set
      在现代cpu实现中,一般来说,为了防止cache太容易被覆盖, 会把cacheline分成N组, 每组由M个cacheline组成
      首先, cpu通过hash算出cache_set_index, 然后, 比较这个cache_set里面的每个cacheline是否和地址匹配
    • N-way
      所谓的N-way就是指上文的cache_set里面的cacheline数目
  • prefetch

    • hareware prefetch
      cpu检测到连续的虚拟内存访问的时候, cpu会提前把接下来的虚拟内存地址中的数据,加载到cache中来
    • software prefetch
    • 通过prefetch指令, 通知cpu记载目标虚拟内存地址的数据
    • 通过普通的内存读写指令, 提前访问需要访问目标虚拟内存地址, 让cpu提前加载数据到内存中, 后续的访问, 就可以避免cache miss
  • LLC(last level cache)的特殊作用
    某些外设, 比如显卡,网卡, 他们的数据,可以直接通过pcie总线写到llc中, 避免从内存中读取.
    如果说一段地址是交给外设作为io地址使用的,那么, cpu是无法从cache中访问对应内存地址中的数据的, 因为DMA的情况下,外设可以不通过cpu修改制定的内存.
    这个时候,cpu去读取最新的数据,就不得不直接访问内存,这将花费大量的时间.

  • cache的延迟
    内存 > LLC > L2 > L1 > 寄存器, 点我查看访问延迟

然后,我们简单看下啥情况下会导致cache miss, 同样,我们分成下面几个简单的场景来看

  • read dcache miss

    看下面一段代码

这是一个很典型的案例, 先说结论: 场景1会比场景2快.
因为数组元素只有4个字节,一个cacheline有64个字节,所以当我们访问a[n][0] -> a[n][15]的时候,其实都是读同一个cacheline的内容
换句话说,不考虑任何预取的场景下, 场景1的情况下16次读才有一次cache miss,场景2的情况下,只要n的大小大于16, 那么, 几乎每次读都是cache miss

  • icache miss
    branch instruction
    条件跳转, call指令这些会导致指令执行出现大的内存地址跨度的时候, 可能就会导致, cache不在icache中

  • write dcache miss
    这里我们主要关注下write-back, write-through, write-combining 性能的区别
    write-through对于write而言,其实cache是没有意义的,他保证的是数据的一致性,只对read场景有意义
    write-back对于write而言,只要还有空闲的cache(和下层存储状态一致)立即返回,所以cache miss的成本比较低
    write-combining本质是提供了一个额外的写缓冲区, 可以一次提交多份数据, 在吞吐量大的情况下, 可以提高性能

最后,我们看下如何避免cache miss

  • 延迟初始化, 在c++和java中, 有一条规则叫做,对象真的要用的时候再去new
    数据在需要使用的时候, 再去初始化.
    因为数据的初始化需要写cache, 写cache也就意味着, 如果这部分数据原本不在cache中,那么需要占用cache(抢占其他内存对象的cache), 但是这个对象在不立即用的情况下, 等于降低了cache的有效使用率
  • 数据的局部性
    因为cacheline的大小是64个字节, 外加连续的内存访问硬件会做prefetch,因此尽可能采用连续的数据存储

  • array, array, array
    参考上述理由, 数组是最好的数据结构,如果可能,尽可能选择数组

  • 其他cache-oblivious数据结构
    不展开, 有兴趣大家可以看看

  • 恰当的prefetch
    对于指针的访问, 比如list的遍历, 程序确定需要访问后续的内存, 可以考虑使用prefetch, 但是prefetch不是立即生效的, 所以, 一定要严格测试对比, 确定有性能提升

老问题,继续引出几个问题

  • 多核情况下, cache的工作方式有啥不同
  • 多核情况下, 又有啥需要额外的注意cache访问方式
  • 前面一直提的流水线又是个什么玩意

透过内存读写看计算机体系结构(二)

前面简单介绍了下,操作系统层面是如何处理内存访问的,其中跳过了很多细节,比如在x86下的段管理等东西.我也不打算很详细的写那些东西一个是因为历史包袱,绝大部分处理器都没有这么奇怪的内存管理模式了,另外一个是,那些东西,不是我们考虑的重点

下面简单介绍下,通常cpu是如何读写内存的.
为了简化问题,我们暂时只考虑单核的场景.

首先,我们看下cpu是如何和内存交互的. 在讨论这个问题前,我们需要先看下,cpu的结构是如何的

[cpu] [L1 cache] [L2 cache] [LLC cache] ------bus------> [main memory]
注意,cache都是很小的,我们可以可以简单看下

首先解释点前置知识:

  • 虚拟地址
    cpu为了支持多任务管理,特别引入了虚拟地址的概念.对于cpu来说,叫做多任务,对于操作系统而言,这就是所谓的多进程.虚拟地址体现在,不同进程看到的都是虚拟地址了,包括cpu的指令集,看到的也是虚拟地址,cpu在执行的过程中,通过MMU把虚拟地址翻译成物理地址.对于不同的进程而言,同一个虚拟地址可以映射到不同物理地址上去,这就给进程造成了一种假象,他拥有了整个内存的使用权同时,cpu也通过这种机制,隔离了不同进程之间的内存访问权限

  • instruction和data的区别
    instruction和data在内存层面,似乎是没有区别的,我们完全可以把一段数据当作指令(比如jit就是这么做的).但是,在cpu层面,数据和指令是严格分开存储的.从数据存储单元取出来的数据,就一定是被cpu当作数据看待,从指令存储单元里面取出来的数据,就一定是被cpu当作指令来看待

  • cache
    这里需要注意的是, L1和L2是区分icache和dcache的, LLC一般来说是数据和指令混合存储的所谓icache就是instruction cache, dcache就是data cache

  • TLB
    instruction和data在内存中的地址,都是用虚拟地址来描述的,数据最终是在物理地址的,因此cpu需要有把虚拟地址翻译成物理地址的能力操作系统实现的页表功能,就是用来做虚拟地址和物理地址转换的,但是,查询页表太慢了,因此,cpu设计的时候,在cpu上留了一小块独立的cache叫做TLB他里面存储的是虚拟地址和物理地址的映射关系,如果一个地址,在这里被找到了,他就不用去查页表了,加快了地址翻译的速度同样,对于TLB而言,他会区分ITLB和DTLB, 同样也分成L1 TLB和L2 TLB

  • 流水线
    cpu在执行指令的时候,是分成N个步骤做完的,最简单的,是一个四级流水线(当然实际的cpu会远比这个复杂)
    取指 -> 译码 -> 发射 -> 回写
    流水线是为了提高吞吐量设计的,通过这种方式,可以简单的提高加速比,当然实际的流水线,会比这个更加复杂(更长,然后每个步骤,有多个执行单元,超线程就是流水线冗余执行单元的副产品)

然后,cpu内存访问过程是,先去L1中,看数据是否命中,没有命中,去L2中查询,然后LLC,然后才是内存这里需要特别提的是,
L1的访问速度 > L2的访问速度 > LLC的访问速度
不是因为他们的存储介质不同,而是因为他们离cpu的远近不同,信号的传输是需要时间的.然后呢,这个过程中,查找的其实是物理地址,所以,cpu在此之前,他还得通过TLB把地址翻译成物理地址,如果L1 TLB没找到,那么L2 TLB, 然后L3 TLB,还没找到, 去操作系统提供的页表中查询(注意,页表在内存里,但是这个地址是固定的,操作系统的运行过程中,这个地址一直是确定的)

下面简单看下一条指令的被cpu执行的过程比如一条指令 mov eax, dword ptr [0x1234], 我们假设这条指令存储在虚拟地址0x10000的内存地址, 他对应的物理地址假设是0x20000, 0x1234的虚拟地址对应的物理地址是0x2234那么上一条指令还没执行完成的时候, ip指向了0x10000

  • cpu先去ITLB中查询0x10000这个地址对应的物理地址,0x20000
  • cpu从0x20000的物理内存中,取出这条指令,放到icache中
  • cpu开始解析,这条指令到底代表啥意思
  • cpu开始执行这条指令,发现,他要读虚拟内存0x1234, 于是cpu再去DTLB中查询,0x1234这个虚拟地址在0x2234
  • cpu把数据从0x2234中读取出来,写入eax这个寄存器
  • cpu把ip寄存器指向下一条指令的位置,顺带完成清理工作

看完了整体流程,接下来,我们看下一些比较细节的东西

  1. cache什么时候回失效
  2. cache失效的成本是多少

下一篇,我们具体探讨下cache,顺带扩展到多核cpu下cache的基本工作原理

透过内存读写看计算机体系结构(一)

很早之前,在微博看到一条微博,mov %rax, [0x12345678]会发生啥,当时也没细想,回头仔细琢磨了下,发现东西还是不少的。试试展开写点吧,关于这块。不过首先声明,我体系结构也是半吊子,有问题的话,欢迎指正。其实呢,这个问题用通俗的话说就是,读写内存过程中,到底会发生哪些事。

对于读和写的场景,在特定场合,还是有点区别的,我们从读开始吧.也就是说,mov %rax, (%rax)会发生啥呢?

先简单点,只从操作系统角度来说
有以下这段代码

首先,当访问一段非法内存,可能出现segment fault的,也就是大名鼎鼎的段错误…顺带好了,引出第一个小问题,怎么定义一个非法内存?

在现代操作系统中,应用层访问的内存都是虚拟内存,关于虚拟内存的概念,这里不做太过于详细的阐述简单点说吧,操作系统配合cpu的mmu机制,会做下面2个关系的转换

cpu在实际访问内存的时候,要从虚拟地址翻译成物理地址,当cpu访问的一段虚拟地址,没有办法找到对应的物理地址的时候,那么cpu会抛出一个异常(page fault的来源),然后,操作系统会处理这个page fault,进行一系列的异常处理。

在操作系统层面看来,如果一段虚拟地址空间[start, end),内核已经分配给了应用层,那么任何一段内存只要只要落在[start, end)这个区间内部都叫做合法内存,同时,内核会记录这块虚拟地址空间是有效的。
反之,称之为非法内存

实际的场景下,很多内存的申请,可能应用并不会立即使用,或者说,并不会使用到全部的内存为了避免物理内存浪费的场景,因此,内核尽可能会推迟给应用分配真正物理内存的时机,那么最简单的处理手段就是,在应用真的对内存发生了读写操作的时候,再分配但是,这样一来,就会导致一个问题,即使对于一段应用有权限的内存,也可能出现没有对应物理内存的情况,那么,cpu会抛出page fault,操作系统会通过中断向量接到这个异常,当他发现发生中断的进程访问的这段内存地址.

  • 应用已经成功申请过的内存的.他会认为这是一个合法的行为,会进行一些尝试恢复异常的处理内存是有权限的,比如可读,可写,可执行,这些权限位,同样是操作系统维护的,他们维护在内存页面的page层面(操作系统最小的内存管理单位是page)

    • 这段内存对应的page,没有读权限,抛出segment fault
    • 这段内存对应的page,有读权限

      • 这段内存之前被swap出去了
        从物理内存中分配一个new_page, 这个原来这个page在swap中对应的内容content, copy(content, new_page)
      • 这段内存之前没有被访问过
        从物理内存中分配一个new_page,如果这个时候申请不出物理内存了,会触发一系列内核的内存回收工作,可能导致OOMK(out of memory kill),这里也就不展开阐述了

  做完这件事以后, 继续做一些剩余的清理工作,把控制权交还给应用层,同时把状态回退到执行读内存操作之前,让应用层重新操作读内存

  • 应用没有成功申请过这段内,那么这个操作是一个非法操作,会抛出一个segment fault

顺带,这里引出几个问题

  • 如何申请一段保证有物理内存映射的虚拟内存?
  • 哪些内存会被置换到swap中去
  • 什么时候会触发swap的行为

然后,继续复杂化场景,在操作系统外边再套一层hypervisor,又是如何一个处理流程呢?
这里就涉及到不少vt相关的东西,其实当发生page fault的时候, 对于x86的cpu来说,会触发一个vmexit事件,hypervisor会接管控制权.hypervisor在处理他自己的物理内存和vm内存的转换关系(对于hypervisor来说,vm就是一个普通的进程),把物理页面映射好,然后把控制权还给vm,然后重复走上述的流程,也就是说实际的处理流程变成了:

application in vm page fault -> hypervisor page fault hanlder -> os in vm page fault hanlder -> application in vm running

下一篇,我们开始讲,在cpu层面,上述的处理过程中,又有哪些更加细节的处理