Category: 笔记
Paper Recap 2:用Rust写内核态文件系统 (High Velocity Kernel File Systems with Bento, FAST ’21 Best Paper)
Paper Recap 1:信息存储的价值 (Economics of Information Storage: The Value in Storing the Long Tail)
A Primer on Memory Consistency & Cache Coherence 笔记1
本文是对《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. […]
《人有人的用途》 读书笔记2
《人有人的用途》(The Human Use of Human Beings — Cybernetics and Society)这本书是控制论鼻祖维纳(Norbert Wiener)的一本“科普书”,虽然只有100多页,我却是一本有深度的好书。第二部分笔记是书的第4~6章。 我曾经看过两本和经济学相关的畅销书,这种经济科普书中,常见类似“让你像经济学家一样思考”的宣传。书呢看了的确挺爽,思考世界的方式也很新鲜,但是看完之后并不能在头脑中留下系统的经济学知识体系,因此,这让我一直认为这类“经济科普”都是速食垃圾,读不得。 但这次再看完《人有人的用途》的几章,却动摇了我对那些科普书的看法。这是因为虽然我的专业与维纳相关,但我却从没有像他那样用信息、控制、反馈、计算、博弈的观点重新审视过这个世界。我虽不完全同意维纳所说,但就像经济学家可以用经济学的视角看世界,维纳也在用他的控制论视角看世界。如此看来,那些经济畅销书,还是有用的,不过我还是感觉先学经济知识,再看它们也许更好。 这三章中,维纳分别从控制论的角度描述了人类语言、有机生命和社会法律和人类的关系,下面是摘录和思考。。 第四章 语言的机制和历史 维纳的父亲是个语言学家,这章的篇幅也算是书中很长的。 (摘录)语言,从某种意义上讲来,就是通信自身的别称。 维纳认为人的语言、符号能力要远强于动物,这在于两方面:第一,信码是精巧和复杂的;第二,信码是有高度任意性的。 (摘录)人对语言的兴趣似乎是一种天生的对编码和译码的兴趣,它看来在人的任何兴趣中最近乎人所独有的。 虽然人类的语言的通信一般用于任何人的交流,但是维纳认为,用到人和机器、机器和人、机器和机器之间也是完全可能的。 (摘录)从线路到机器,中间还有一个转换过程,在这个阶段中,信息可以逸失而永不再得。……如前所述,这乃是热力学第二定律的控制论形式。 语言在进化的过程中也在和自然的通信干扰作博弈,比如一些人造语的词长分布和自然语言明显不同。 (摘录)语言的磨损可能是由几个原因引起的。语言也许只是力图反抗跟它捣乱的自然趋势,也许只是力图反抗人们有目的地搅乱其名义的企图。 把语言看成博弈,可以区分语言的两个变种:其一的主要目的是传送信息,另一的主要目的是把自己的观点强加到顽固不化的反对者头上。 维纳把人看做一种终端机器,那人和人之间就构成了通信网络,人和人的通信就分成了3个阶段: 语音阶段:人耳和脑中可能还存在类似滤波器的东西,高于或低于某个频率的声音即使有再多信息也无法接收。 语义阶段:如上所述,首先输入脑中的语音才能被解析出语义;且语义的翻译依赖长期的历史记忆;当一种语言和另一种语言不完全对等,就存在语义流动上的障碍。 (摘录:外国人讲的英语,是语义学上好的而语音学上差的英语;而普通人的酒后谈话,则是语音学上好的,语义学上不好的。) 行为阶段:指的是人由接收到语义可能导致的行为。 这三个阶段,信息量其实都是在减少的,这也符合热力学第二定律,如果信息在信道中被进行了任何干预,原有信息量必然是减小的,除非中途进行 馈进 。 (摘录)作为一门控制语言逸失的学科,控制论应用于语义学方面的愿望已经在若干问题上得到了实现……对行动有重要意义的,与其说是发出的信息量,不如说是进入通讯装置和存储装置的足以行动扳机的信息量。 第五章 作为消息的有机体 本章把有机体生命类比成消息。(有机体与混乱瓦解,正如消息与噪声间的关系) (摘录)在趋于毁灭的世界中,声明就是此时此地的一个孤岛,生命体抗拒毁灭和衰退这一总流的过程叫做稳态。 (摘录)……(我们会)生活到我们衰老速度大于更新速度为止 维纳认为人类等有机体可以看成一种 模式,这是因为我们的身体在不断代谢,组成人体的物质并非一成不变,只有“模式”是永存的。维纳的这种思想让我想到了当今的软件之于硬件,磨具之于产品,更直接的:3D打印。不过维纳更想说明的是,人类等有机体只是一种信息的形式,信息的传递比物质的传递更重要。(摘录:模式就是消息,它可以作为消息来传递。) 如果通信分为两种:物质运输和信息运输,那么两种之间也没有什么不可过渡的,只是当前的技术无法实现如此大量的基因数据传递(即使现在也不行),但是即使是人被交通运输向其他地方,维纳还是认为那本质上来说还是信息的运输。 以人体生殖细胞的结合与分裂为例,维纳认为“两部原先不相耦合的大型机器有可能耦合起来,从而从该阶段起像一部单一的机器那样工作。”,这我不禁想到当今的分布式系统、云计算的概念。 第六章 法律和通讯 正如第四章所说,语言是通信的形式之一,而法律则是语言的作用之一:用来“道德控制”。我觉得,媒体或者舆论应该在这方面也是类似的,都是用语言作为信息,让发信的一方的思想影响接收信息的思想,法律、新闻、舆论引起的社会后果便是信息传递后的反馈,这种反馈会再次作用到发信方,进行下一次“控制”。这种思想在维纳的这本书中也有体现。 维纳不仅强调了法律和语言通信的关系,还以契约法为例指出了法律必须有解释机构。“如果所用术语的意义未经确定或者它们的意义随法庭的不同而不同,则契约的双发就不能以任何正义来弄清订契约的意义了。”。我觉得,既然执行法律被类比为了通信,那么契约法律就类似我们现在常说的通信协议,收发双发事先的一致,才能有效的让有用的信息传递。 维纳还表达了他对当时刑法的不满,他说这是因为有人将刑法看做惩罚罪犯的手段,有人看做赎罪的仪式,有人看做隔离罪犯的手段,还有人看做道德改造的手段。因此,这导致了刑法制定的混乱。 (摘录)因为立法者或法官要对法律作出唯一正确的解释,因此,法律可以看做通信问题或者控制论问题,也就是说,法律的问题就是对若干危险情况进行只需和可重复的控制。 维纳还将当事人力图用法律条文赢得法官和陪审员的支持、律师有意图地引入混乱设法让对方的陈述无效类比为冯诺依曼博弈行为,或者一种互相的信息阻塞行为。 [1] 豆瓣读书–人有人的用处, https://book.douban.com/subject/1455960/
《人有人的用途》 读书笔记1
《人有人的用途》(The Human Use of Human Beings — Cybernetics and Society)这本书是控制论鼻祖维纳(Norbert Wiener)的一本“科普书”,虽然只有100多页,还是32开纸,但是我觉得却是一本有深度的好书。首先,这本书并没有任何公式和严谨的控制理论,还有很多恰当的小例子,因此特别易读;但是虽易读,并非无营养,相反,每一段、每个观点都可以细读,引发思考。 与“科普书”的定位相比,更应当注意的是这本书的副标题:“控制论和社会”,作者不仅让人信服的解释了熵的概念、(机器)学习的概念、语言信息传递的原理;也对法律、社会政策等方面的思考和讨论;最后时甚至对未来发展进行预测……行文间,作者的例子不仅涉及自己的控制论,还包括信息论、生物学、热力学、社会学等多方面的思考。更令人叹服的是,虽1954年成书时人工智能之一概念才刚刚起步,作者在这本当时的“科普”书中,就已经能够看出各种现在很火的统计机器学习、仿生神经网络等让机器从历史经验进行未来预测的思想! 我读这本书并不快,但第一次也只是匆匆略过,现在想抽时间再读一遍,准备记下好的观点和自己对应的思考。总之,这是一本连相关专业学生都无法当科普书来读的科普书。 第一章 历史上的控制论 其实控制论是属于信息论的。 在控制与通信中,我们要与组织性降低和含义受损的自然趋势( 熵增 理论)做斗争。 一个复杂的动作可以有如下定义:为了影响外部( 输出 )而引入了可以有大量组合的数据( 输入 ),这些数据可能是当下刚放入的数据,也可能来自过去 存储 的数据(记忆)。(我感觉这种观点其实类似计算机系统的输入输出I/O和存储区memory/storage) 机器对自己的动作的后果作为下一步动作的所需信息,即是 反馈 。 作者认为生命个体和机器都是利用反馈来控制熵的,控制中枢用 自己打算做的(目的信息) 和 外界运演过的(反馈信息) 进行动作。 第二章 进步和熵 这一章作者进一步通过热力学第二定律的角度解释 熵增 的概念。 机器不一定可以称作“生命”,但和生命类似的地方是都在 整体的熵增 中,实现了 局部的熵减 。 消息传递的产生,一定伴随着能量的损失。 第三章 定型和学习–通讯行为的两种模式 (关于反馈) (定型应该指的是人的构造决定了人的多样和创造力,学习比较类似反馈思想或者现在的机器学习思想,从发生过的事总结经验,或者发生过的对未发生的动作产生影响) (摘录)学习,和比较简单的反馈形式一样,也是一种从未来看过去和从过去看未来的有所不同的过程。 (摘录)能学习的生物是从已知的过去走向未知的未来,而未来是不能和过去互换的。 作者认为,双向通信在控制中很重要,(其实就是反馈)。作者还进一步讲了“ 社会反馈 ”的概念,比如阶层之间、君臣之间的通信有着特殊的限制,不同于一般人与人间的通信。 (人类社会与昆虫社会的区别源自机械定型) […]
OSTEP笔记3–持久化存储
大部分截图来自原书,贴出书的官方主页: 《Operating Systems: Three Easy Pieces》 (作者Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau)。感谢原作者这么好的书。 本篇笔记是书的第三部分(Persistence),讲述了操作系统和外存系统相关的内容。 第一节 I/O Device 1.1 IO 总线 一般情况下, IO设备的性能较差(慢),所以用Peripheral IO Bus,为什么不用像显卡一样用的PCI呢?因为1)越快的总线越短,这样空间不够插;2)越快的总线制作成本越高,如果存储设备照总线的性能差的远,没必要用高性能总线。 这张图为总线的层次结构,memory bus是最快的也是最近的,IO Bus比较远,也是最慢的,中间有用于显卡的PCI等总线。 1.2 典型设备的组成部分 一个典型的外围设备如图所示,包括两部分: 接口 和 内部结构 。 接口: 类似软件接口的功能,硬件接口是留给OS和设备交互的。 内部结构: 比如㓟CPU、MEM等基本组件,还有称为固件(firmware)的软件来实现内部功能。 1.3 两种IO模式(Polling和Interrupt) Polling的形式,而interrupt。 一种典型的协议是 Polling (轮询),称为programmed IO,步骤有4: 循环等待STATUS寄存器直到设备状态为不busy 写数据到DATA寄存器 写命令到COMMAND寄存器 循环等待STATUS直到设备为不busy Polling显著的缺点就是太浪费CPU时间,这是因为IO相对于CPU是很慢的,大量的CPU时间被用在了等待上。 Interrupt (中断)方法(也称为interrupt-handling IO)可以解决这个问题,用Interrupt方法进行IO时,当设备完成操作时,会raise一个硬件interrupt。但是这样的话,如果设备很快(比如现在的NVMe SSD设备),Interrupt由于需要进程上下文的切换、以及中断的控制等原因,会拖慢IO的速度。所以两种方法各有利弊: Polling […]
OSTEP笔记2–内存虚拟化
大部分截图来自原书,贴出书的官方主页: 《Operating Systems: Three Easy Pieces》 (作者Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau)。感谢原作者这么好的书。 本篇笔记是书的第一部分(Virtualization)的下半部分,讲述了操作系统是怎么通过地址空间的抽象,将内存资源进行虚拟化的。 第一节 地址空间 1.1 内存虚拟化 多进程OS的资源共享策略 本书上半部分讲了CPU的共享策略:通过进程(process)这个抽象,OS将时间片分给进程。 对于内存资源的共享:为了让昂贵的计算机能够支持多个程序同时运行,如果在切换某个进程时将内存数据从磁盘换入(进程共享磁盘,内存和寄存器都不共享),由于磁盘IO太慢,不现实。所以现在的系统,都是将相对较快的寄存器换入换出 ,所有进程数据共享内存资源( 寄存器不共享,内存共享 )。为了实现这种想法,并更好地管理内存, 地址空间(Address Space) 的抽象被引入(如下图),相对为每个程序固定分配一定大小的内存空间更灵活,用地址空间进行管理更加灵活。 地址空间在 结构 上主要分为Code、Heap和Stack,Code部分用来存程序运行的代码,Heap是用户程序动态分配内存(malloc/free)所使用空间,Stack是变量使用的空间。除非程序递归很多,一般Stack都是够用的;如果程序视图访问非法地址,可能出现Segmentation fault的错误。 每个进程都会有一个自己地址空间,且每个进程都认为自己的地址空间是从0开始的,并且地址空间的地址也不必和物理地址相等,甚至地址空间的总大小可以大于物理内存大小,这就体现了一种 内存虚拟化 的概念,OS的内存管理系统也可以称为 虚拟内存系统(virtual memory system, VM) 。因此,我们编写的程序中,所有我们可以得到的地址也都是虚拟地址,并非物理地址。 VM系统设计的三个目标:透明(transparency)、高效(efficency) 和 保护(protection) 。其中保护即隔离(isolation),进程间的地址空间需要隔离,进程和OS间也需要隔离,(甚至在有些微内核操作系统中,OS的一部分和OS的另一部分也进行了隔离),这样可以保证安全性。 1.2. memory API 对于用户程序,Stack中的变量是自动管理的,比如用int声明一个整数变量,而Heap中的内存是由程序(程序员)负责的,什么时候malloc/free都要程序员进行考虑,所以要格外小心一些常见的malloc错误,比如忘记分配内存、分配的不够导致buffer overflow、忘记初始化所分配内存内容、忘记free等。 purify 和 valgrind 这两个工具可以协助检测内存分配的问题。 1.3. malloc、free和mmap的关系** 要注意 […]
OSTEP笔记1–CPU虚拟化
截图来自原书,贴出书的官方主页: 《Operating Systems: Three Easy Pieces》 (作者Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau)。感谢原作者这么好的书。 本篇笔记是书的第一部分(Virtualization)的上半部分,讲述了操作系统是怎么通过进程的抽象,将CPU计算资源进行虚拟化的。 第一节 进程的抽象 1.1. 策略和机制 Policy在mechanism(策略和机制)在操作系统中通常是分开设计的。比如如何切换上下文是一个low-level的mechanism,指底层的方法或者协议。当前时刻应该让哪个进程运行更好是一个high-level的policy的问题,指一些“智能”的调度。 1.2. 虚拟化和OS OS本身就可以看做是“虚拟机”(virtual machine)。系统通过在可以被接受的合理开销(时间、空间)范围内,将计算机CPU、内存、存储等资源进行虚拟化(抽象),目的是为了用户的方便使用。 CPU虚拟化 主要体现在将任务抽象为 进程(process) ,将资源按进程隔离,然后多个进程轮转使用计算资源; 内存虚拟化 主要体现在 虚拟地址空间(virtual address space 或 adress space) ;而对于持久化的 存储 ,OS让文件共享,没有那么多私有隔离,OS假定用户会用文件来共享数据。 (????) 第二节 进程API 2.1. fork和exec exec()函数组和fork()的区别是:fork()复制当前进程为一个子进程执行,exec()会执行一个新的程序;exec()执行以后就再也不会返回。 2.2. shell和stdout redirect 例如shell就是一个普通的用户程序,利用了fork和exec的组合。给出一个提示符,你输入可执行程序时,会先fork(),然后在fork出的子进程中exec()这个命令,然后调用wait()来结束。这种fork和exec的组合使用,可以在让shell在fork后运行一些其他代码:fork后的子进程可以redirect操作再exec;fork后的父进程可以执行wait操作在exec结束后再显示提示符prompt。 stdout redirect的原理很简单,stdout一般的fd都是0,在fork后的子进程中close掉stdout,然后打开要redirect到的文件,这个文件就会获得为0的fd,这时执行新命令的exec,则会把这个为0的文件看做stdout进行输出,程序清单如下图: 2.3. 其他 kill()可以向进程发送信号,让程序sleep, die。 第三节 […]