by ·0 Comments

本文是对《A Primer on Memory Consistency and Cache Coherence》这本书前一半内容的记录和理解，主要涉及memory consistency model。 1. 引言 对于多处理器共享内存系统来说，consistency和coherence都关注的是共享内存(shared memory)及cache的正确性问题，而人们把这个问题拆成两个方面是为了更好地将这个复杂问题分治解决。 1.1 Consistency 一般需要被详细讨论的是多核(或线程)共享内存(shared memory)的consistency模型，因为单核单线程问题相对简单直观。内存consistency模型规定的是：多线程同时进行load/store操作时，怎样的执行顺序是对的，怎样是错的。比较简单直接的consistency模型包括sequential consistency、TSO(total store consitency，x86使用)等。 1.2 Coherence 本文主要记录与consistency有关的内容，但因为consistency的实现与coherence有关，所以要简单介绍下coherence及其与consistency的关系。 虽然coherence的中文也翻译成“一致性”，但coherence这个词通常跟在cache后面，即缓存一致性(cache coherence)，解决缓存一致性问题的方法也被称为缓存一致性协议(cache coherence protocol)。那么共享内存系统的cache为什么需要coherence协议保证共享内存系统正确性呢？这是因为cache一般分为L1、L2和L3等很多层，L1等比较高的层级中，cache是每个核所独占的，一般只有L3、memory等层级才是共享的。在每个核独占的层级中，可能出现统一内存地址的数据在不同独占cache中数值不一样的情况，这时cache的状态可以称为incoherent。通过无效化等coherence协议，可以保证多核系统cache的正确性。 1.3 Consistency 和 Coherence的关系 对于sequential consistency和TSO等比较简单的consistency model来说，保证了coherence的cache可以被看成一个“黑盒”甚至对consistency model透明，黑盒中有cache实现有保证cache使用正确的coherence protocol，而consistency更关注程序(或处理器核)的访存顺序。因此对于简单的consistency model和coherence protocol来说，两者是解耦的。 1.4 一个小例子 如果上边几段不易理解，作者在书中用一个例子解释了这两个名词的基本含义，简单记录如下，有改编： consistency的例子 设想有三个人，计算机体系结构课程老师、教务处网站管理员和上课的学生，老师最开始在教务处上登记了上课的地点是152教室，但是开学第一节课后发现选课的人太多了152坐不下，于是准备下节课开始换到更大的252教室，于是老师先①找教务处网站管理员说“请你把网站上我课的教室信息改到252（要求①），随后通知学生们去教务处网站查询下节课的上课地点（要求②）。这就产生了一个问题，网站管理员可能是第二天才更新的网站，而学生是接到老师的通知马上重新查看了教务处网站，因此学生下周又来到了152教室，老师的计划和最后的结果出现了不一致情况。 问题就出在老师的做法无法保证学生在网站被修改之后再去网站查询。要想保证学生查到正确的信息，一种简单的办法就是保证管理员的确更新了数据，然后再通知学生们。这种简单的办法就可以称为一种一致性模型。 我们把这个例子对应到实际的内存系统中，给管理员和学生要做的两件事（要求①和②）可以分别看成一条store命令和一条load命令，目标都是教务处网站上老师的教室号，这个目标可以看成同一块内存地址，因此对同一内存地址执行的store和load命令是否可以调换顺序(管理员在学生查询才修改了网站)，调换顺序后是否破坏了程序的正确性，就是内存一致性模型memory consistency model所负责的。也就是说，出现上述情况算不算错，应该是当前的一致性模型所判断的：相对于我们每个人心中直觉上的一致性模型，这种走错教室的情况肯定是错了，但是对于一个性格怪异的老师，也许他觉得这样也是对的，比如他可以找他的同事帮他上152教室的课，他自己上252教室的课，也正因他如此怪异，所以他最开始联系网站管理员时也遵循了他心中的怪异的一致性模型，没有等网站确实修改就给学生们发了查询教室的通知。 coherence的例子 紧接上个例子，与之不同的是，很多学生在最开始选课的时候就把《体系结构》这门课的教室152记在了自己的小本本上，但是后来，管理员将网站上教室信息改成了252。虽然学生的小本本上和教务处网站上的信息应该是同一个信息，应该是一样的，但是这时两者一个152，一个252，这就出现了incoherent的情况。 在内存系统中，学生的小本本就相当于cache，而教务处网站相当于memory，学生将memory中的某个值拷贝到了cache中，当memory被其他人更新时，学生自己的cache就应该同时立即处于无效的状态。这里出现incoherent的原因就是没有一个cache coherence protocol来保证cache的正确性。比如，一个简单的coherence protocol可以这么干：在网站更新后，老师挨个找到每个学生，把他们的小本本记的152划掉?，无效化协议就是这种思想。 2. […]

by ·0 Comments

（发布于 April 3, 2013， 意译于12/9/2016） 原文链接 ：https://lwn.net/Articles/545244/ 另一个版本的翻译(有些句子没有翻): http://kernel.taobao.org/index.php?title=%E5%86%85%E6%A0%B8%E6%9C%88%E6%8A%A52013-04#In-kernel_memory_compression 吐槽 : 我的天呐！！翻译完我才发现有人翻译过了，早知道我就不自己翻译了，痛苦死我了。。 PS :内容我还没有完全理解，仅供参考，以原文为准。 阿姆达尔定律告诉我们一个计算机系统肯定存在一个瓶颈。历史上，对于很多工作负载这个瓶颈都是cpu，所以人们在不断提升cpu性能。所以现在，渐渐地，ram成为了瓶颈。有时当数据在ram和disk之间来回传递时，cpu就在一边干瞪眼呢。增大ram有时并不是一个好的或者经济的做法，更快的I/O或者ssd可以缓解问题，但是不能消除这个瓶颈。 如果可以增大ram中数据的有效容量，不是很好吗？既然cpu闲置，也许我们可以拿闲置的cpu周期来专注这件事。这就是内核内压缩的目标：用闲置的cpu周期来做ram中的压缩和解压缩。 算上刚刚发布的zswap，现在有3个内核内实现的压缩方法在被建议merge到内核的内存管理(memory management, MM) 子系统：zram, zcache和zswap。乍一看可能会让人觉得一个就够了吧，但是他们三个却有很大的不同，可能面向着不同的用户群。所以就像现在内核中存在很多文件系统一样，有一天内核中也会存在多种压缩方案吧，不过这还得李纳斯大神和主要的内核开发者说了算。。。为了方便说明，本文把这些方案统称“zproject”，并对比了这些方案。我们先说明一些关键原则和压缩遇到的挑战。然后我们会从三个层次说明并详细地阐释这些zprojects设计上的不同选择，之后我们还讨论zprojects怎么和内核其他部分交互，最后给出结论。 压缩基础 要让压缩在内核中工作，内核必须把字节序列放入内存中再压缩，之后内存中也应保有压缩后的版本，以备这些数据被再次使用。压缩状态下的数据不能被读写，所以对压缩版本的数据再进行解压缩后才能继续读写这些数据。 字节序列压缩多少都可以，但还是以一个固定大小的单元压缩较方便。贯穿整个内核的一种基本的存储单元是page，一个page由PAGE_SIZE个字节组成，通常的linux支持的架构中，page的大小是4KB。如果这个page对准了PIGE_SIZE的地址分界，那么它就被称为page frame。对于每个page frame，内核在ram中都有相应的struct page结构。所有这三个zprojects都用page作为压缩的单元，并且通过开辟和管理page frames来存储压缩页。 有很多可用的压缩算法，但总的来说，高压缩比意味着高cpu周期，运行的快的算法一般压缩比较低。在时间效率和压缩率之间做出权衡很重要。这三种zprojects，默认都使用内核lib/文件夹中的LZO(1X)算法，这种算法做出了很好的权衡。然而，算法的选择还是很灵活的，也许cpu运行的算法还会被一些特殊架构的硬件压缩引擎取代呢。 一般，存在一些数据一会儿压缩一会儿解压缩的循环，数据序列大概和序列中的字节数成正比。因为页比较大，页压缩和解压缩都是很昂贵的操作，所以我们希望限制这些操作的数量。因此我们必须谨慎的选择哪些页要被压缩，尽可能找到那些可能会被再次用到同时最近不会用的页，以免把cpu时间浪费在重复的压缩然后立刻又解压缩上。因为压缩页不能直接访存某个字节，我们必须要保证内核清楚地辨识出哪个是压缩页，避免对压缩页中的字节尝试cpu的线性地址操作，同时保证压缩页可以被找到并可以在被访问时解压缩。