深入理解计算机系统 | 对齐

另一个我的梦想园2019-02-15 13:27:02


深入了解计算机系统之内存对齐

ALIGNMENT


今天想尝试一种新的风格~咳咳,想厚颜地走学术路线。当然知道我现在还只能算小白。感觉看得东西很快就会忘记了,还不如找个地方把搜集起来。


为什么想写“内存对齐”呢?

其实只是脑子一热而已。


以下的内容很多都出自于网络上的博客。我只是以我自己的思路进行了整理。如果有表述错误的地方,欢迎指正~



我一直觉得带着问题学习会比较有意思。那么这篇文章的目的就是为了解决以下三个问题:

  • 对齐是什么?

  • 为什么要对齐?

  • 该怎么对齐?



    对齐是什么?  


内存对齐”应该是编译器的“管辖范围”。编译器为程序中的每个“数据单元”安排在适当的位置上。但是C语言的一个特点就是太灵活,太强大,它允许你干预“内存对齐”。如果你想了解更加底层的秘密,“内存对齐”对你就不应该再透明了。

内存对齐只是指数据存储在内存时的起始地址是否是某个值的整数倍。如果只是放在内存中,是否对齐本身并没有什么问题。问题是读取、写入的时候。访问一个不对齐的数据(unaligned memory access)可能会导致程序运行效率慢,结果出错,甚至是程序当掉。


那这些情况是怎么出现的呢?


    想要弄清楚这个问题,需要我们先来了解一下关于内存的读写原理。【因为是资料整理,那么我们就从最开始的CPU工作原理开始,再了解DRAM的存储原理。CPU工作需要知道指令或数据的内存地址,那么地址又如何与内存这样的硬件联系在一起的呢?访问机制又是什么呢?】


 CPU工作原理 


    计算机的发展这里就不再赘述了,硬件的发展为计算机提供更快的处理速度,而软件的发展给用户提供更好的体验感受。而这一切都是在满足人们日益增长的物质文化需求和对美好生活的向往。


    现在计算机,大部分都是基于冯诺依曼体系结构。犹记得《三体》中用秦始皇的军队从最基本的与或非门开始用人堆出计算机的片段的小激动。而冯诺依曼的核心是:存储程序,顺序执行。所以不管计算机如何发展,基本原理都是在用计算机程序告诉计算机该做什么事情


冯诺依曼体系结构    


        冯诺依曼体系结构如下图所示。计算机硬件由运算器、控制器、存储器、输入设备和输出设备五大部分组成。

其具有以下特点:  

     计算机处理的数据和指令一律用二进制数表示;    

     指令和数据不加区别混合存储在同一个存储器中;    

     顺序执行程序的每一条指令;




    而计算机程序如何告诉计算机应该完成什么事情,也就是计算机如何与计算机程序进行“交流”呢?


 CPU指令


    因为在计算机中指令和数据都用二进制来表示,也就是说它只认识0和1这样的数字。最早期的计算机程序通过在纸带上打洞来人工操操作的方式来模拟0和1,根据不同的组合来完成一些操作。后来直接通过直0和1编程程序,这种称之为机器语言。这里就会有一个疑问,计算机怎么知道你这些组合的意思? 于是就有了CPU指令。所以CPU指令其实就是对应了我们所说的0和1的组合。每款CPU在设计时就规定了一系列与其硬件电路相配合的指令系统。有了CPU指令集的文档你就可以通过这个编写CPU认识的机器代码了。所以对于不同CPU来说可能会有不同的机器码。而随着计算机的发展,CPU支持的指令也越来越多,功能也越来越强。


    使用0和1这样的机器语言好处是CPU认识,可以直接执行,但是对于程序本身来说,没有可读性,难以维护,容易出错。所以就出现了汇编语言,它用助记符(代替操作码指令,用地址符号代替地址码。实际是对机器语言的一种映射,可读性高。汇编语言的出现大大提高了编程效率,但是有一个问题就是不同CPU的指令集可能不同,这样就需要为不同的CPU编写不同的汇编程序。


    于是又出现了高级语言比如C,或者是后来的C++,JAVA,C#。 高级语言把多条汇编指令合成成为了一个表达式,并且去除了许多操作细节(比如堆栈操作,寄存器操作),而是以一种更直观的方式来编写程序,而面向对象的语言的出现使得程序编写更加符合我们的思维方式。我们不必把尽力放到低层的细节上,而更多的关注程序的本身的逻辑的实现。


    对于高级语言来说需要一个编译器来完成高级语言到汇编语言的转换。汇编语言再转换成机器能识别的机器语言。所以对比不同的CPU结构,只需要有不同编译器和汇编器就能使得我们的程序在不同CPU上都能运行了。


CPU基本功能


指令控制: 指令控制也称为程序的顺序控制,控制程序严格按照规定的顺序执行。

操作控制: 将取出的指令的产生一系列的控制信号(微指令),分别送往相应的部件,从而控制这些部件按指令的要求进行工作。 

时间控制: 有些控制信号在时间上有严格的先后顺序,如读取存储器的数据,只有当地址线信号稳定以后,才能通过数据线将所需的数据读出,否则读出的数据是不正确的数据,这样计算机才能有条不紊地工作。

数据加工: 所谓数据加工,就是对数据进行算术运算和逻辑运算处理。


CPU基本工作    


CPU的基本工作是执行存储的指令序列,即程序。程序的执行过程实际上是不断地取出指令、分析指令、执行指令的过程。几乎所有的冯诺伊曼型计算机的CPU,其工作都可以分为5个阶段:取指令、指令译码、执行指令、访存取数和结果写回。 

指令周期 

CPU取出一条指令并执行该指令所需的时间称为指令周期。指令周期的长短与指令的复杂程度有关。

CPU周期

从主存读取一条指令的最短时间来规定CPU周期。指令周期常常用若干个CPU周期数来表示。

时钟周期

时钟周期是处理操作的最基本时间单位,由机器的主频决定。一个CPU周期包含有若干个时钟周期。



    从上面的定义可以知道,对于CPU来说取出和执行任何一条指令所需的最短时间为两个CPU周期。

    所以频率越高,那么时钟周期越短,这样CPU周期和指令周期也就越短,理论上程序执行的速度也越快。但是频率不能无限的提高,而且频率的提高也带来了功耗,发热等问题,所以目前也有超线程,流水线等技术来提高CPU执行的速度。关于超线程,流水线以后再来讨论。


    从时间上来说,取指令事件发生在指令周期的第一个CPU周期中,即发生在“取指令”阶段,而取数据事件发生在指令周期的后面几个CPU周期中,即发生在“执行指令”阶段。从空间上来说,如果取出的代码是指令,那么一定送往指令寄存器,如果取出的代码是数据,那么一定送往运算器。从而区分了内存中的指令与数据。


        通过以上我们了解了CPU的工作过程。简单来说就是CPU要顺序执行一个程序的指令,首先是控制器获得第一条指令的地址,当CPU取得这个指令并执行后,控制器需要生成下一条要执行的指令的地址。ALU单元负责一些运算操作。


 存储器工作原理 


    存储器为了匹配CPU和外设之间不同的访问速度,考虑到成本和局部性的原因而设计的存储器层次结构这里就不再多说了。


    这里简单补充一下局部性的概念。


    局部性


    CPU在执行一个程序的指令时,它后面的指令有很大的可能在下一个指令周期被执行。而一个存储区被访问后,也可能在接下来的操作中再次被访问。

    这就是局部性的两种形式: 时间局部性和空间局部性。

    对于现代计算机来说,无论是应用程序,操作系统,硬件的各个层次我们都是用了局部性。

硬件:通过引入Cache存储器来保存最近访问的指令数据来提高对主存的访问速度。

操作系统: 允许是用主存作为虚拟地址空间被引用块的高速缓存以及从盘文件的块的高速缓存。

应用程序:将一些远程服务比如HTTP Server的HTML页面缓存在本度的磁盘中。 

理解局部性可以通过下面的一个例子

        以上2段代码差别只有for循环的顺序,但是局部性却相差了很多。我们知道数组在内存中是按照行的顺序来存储的。但是CODE1确实按列去访问,这可能就导致缓存不命中(需要的数据并不在Cache中,因为Cache存储的是连续的内存数据,而CODE1访问的是不连续的),也就降低了程序运行的速度。 

内存的工作原理


DRAM芯片结构


上图是DRAM芯片一个单元的结构图。一块DRAM被分为了N个超单元,每个单元由M个DRAM单元组成。我们知道一个DRAM单元可以存放1bit数据, 所以描述一个DRAM芯片可以存储N*M位数据上图就是一个有16个超单元,每个单元8位的存储模块,我们可以称为16*8bit 的DRAM芯片。【这里再强调一下16*8的意思是:有16个超单元,每个超单元里有8bit的数据被存储】

    而超单元(2,1)我们可以通过如矩阵的方式访问,比如 data = DRAM[2.1] 。这样每个超单元都能有唯一的地址,这也是内存地址的基础。


        每个超单元的信息通过地址线和数据线传输查找和传输数据。如上图有2根地址线和8根数据线连接到存储控制器(注意这里的存储控制器和北桥的内存控制器不是一回事),存储控制器电路一次可以传送M位数据到DRAM芯片或从DRAM传出M位数据。为了读取或写入(i,j)超单元的数据,存储控制器需要通过地址线传入行地址i 和列地址j。这里我们把行地址称为RAS(Row Access Strobe)请求, 列地址称为CAS(Column Access Strobe)请求。


        但是我们发现地址线只有2为,也就是寻址空间是0-3。而确定一个超单元至少需要4位地址线,那么是怎么实现的呢?

 

        解决这个问题采用的是分时传送地址码的方法。看上图我们可以发现在DRAM芯片内部有一个行缓冲区,实际上获取一个cell的数据,是传送了2次数据,第一次发送RAS,将一行的数据放入行缓冲区,第二期发送CAS,从行缓冲区中取得数据并通过数据线传出。这些地址线和数据线在芯片上是以管脚(PIN)与控制电路相连的。将DRAM电路设计成二维矩阵而不是一位线性数组是为了降低芯片上的管脚数量。入上图如果使用线性数组,需要4根地址管脚,而采用二维矩阵并使用RAS\CAS两次请求的方式只需要2个地址管脚。但这样的缺点是增加了访问时间。


内存模块是如何扩展字长和容量


    位扩展的方法很简单,只需将多片RAM的相应地址端、读/写控制端 和片选信号CS并接在一起,而各片RAM的I/O端并行输出即可。 如上图,我们采用了8个DRAM芯片分别编号为0-7,每个超单元中存储8位数据。在获取add(row=i,col=j)地址的数据的时候,从每个DRAM芯片的【i, j】单元取出一个字节的数据,这样传送到CPU的一共是8*8b = 64b的数据。我们通过8个8M*8b的内存颗粒扩展为了8M*64b的内存模块。


    RAM的字扩展是利用译码器输出控制各片RAM的片选信号CS来实现的。RAM进行字扩展时必须增加地址线,而增加的地址线作为高位地址与译码器的输入相连。同时各片RAM的相应地址端、读/写控制端 、相应I/O端应并接在一起使用。下图是我们通过4个2M*8b的内存颗粒,将内存容量扩展到了8M,字长为8位。 



内存模块


    内存模块也就是我们常说的内存条。我们在购买内存是经常会听到我这个内存采用的是什么颗粒。我们看到内存PCB上的一块块的就是内存颗粒。也就是我们DRAM芯片。通过管脚和PCB连接。不同厂商,不同类型的内存可以的大小,管脚,性能,封装都不一样,但是原理都是一样。这里我们就不展开介绍了。



内存编址


        前面我们知道了DRAM颗粒以及内存模块是如何扩展字长和容量的。一个内存可能是8位,也可能是64位,容量可能是1M,也可能是1G。那么内存是如何编址的呢?这和地址总线,计算机字长之间又有什么关系呢?


字长


    计算机在同一时间内处理的一组二进制数称为一个计算机的“字”,而这组二进制数的位数就是“字长”。通常称处理字长为8位数据的CPU叫8位CPU,32位CPU就是在同一时间内处理字长为32位的二进制数据。 所以这里的字并不是我们理解的双字节(Word)而是和硬件相关的一个概念。一般来说计算机的数据线的位数和字长是相同的。这样从内存获取数据后,只需要一次就能把数据全部传送给CPU。


地址总线


        前面我们已经介绍过地址总线的功能。地址总线的数量决定了他最大的寻址范围。就目前来说一般地址总线先字长相同。比如32位计算机拥有32为数据线和32为地线,最大寻址范围是4G(0x00000000 ~ 0xFFFFFFFF)。当然也有例外,Intel的8086是16为字长的CPU,采用了16位数据线和20位数据线。


内存编址


        从前面我们知道个内存的大小和它芯片扩展方式有关

        比如我们内存模块是采用 16M*8bit的内存颗粒,那么我们使用4个颗粒进行位扩展,成为16M*32bit,使用4个颗粒进行字容量扩展变为64M*32bit。那么我们内存模块使用了16个内存颗粒,实际大小是256MB

  

         我们需要对这个256M的内存进行编址以便CPU能够使用它,通常我们多种编址方式:

按字编址

对于这个256M内存来说,它的寻址范围是64M(因为是64*32),而每个内存地址可以存储32bit数据。

按半字编址

对于这个256M内存来说,它的寻址范围是128M,而每个内存地址可以存储16bit数据。

按字节编址

对于这个256M内存来说,它的寻址范围是256M,而每个内存地址可以存储8bit数据。


      对于我们现在的计算机来说,主要都是采用按字节编址的方式。所以我们可以把内存简单的看成一个线性数组数组每个元素的大小为8bit,我们称为一个存储单元。这一点很重要,因为后面讨论的所有问题内存都是以按字节编址的方式。 这也是为什么对于32位计算机来说,能使用的最多容量的内存为4GB。如果我们按字编地址,能使用的最大内存容量就是16GB了。   

        于是很容易想到一个问题,为什么我们要采用字节编址的方式呢?  另一方面的问题是,内存编址方式和DRAM芯片是否有关呢? 在网上有人认为还是有一定关系。现在的DRAM芯片cell都是8bit,所以采用按字节编址。另一方面应该也和数据总线位宽有关。


内存数据


        内存是按字节编址,每个地址的存储单元可以存放8bit的数据。我们也知道CPU通过内存地址获取一条指令和数据,而他们存在存储单元中。现在就有一个问题:我们的数据和指令不可能刚好是8bit,如果小于8位,没什么问题,顶多是浪费几位(或许按字节编址是为了节省内存空间考虑)。但是当数据或指令的长度大于8bit呢?因为这种情况是很容易出现的,比如一个16bit的Int数据在内存是如何存储的呢?


        内存数据存放   其实一个简单的办法就是使用多个存储单元来存放数据或指令。比如Int16使用2个内存单元,而Int32使用4个内存单元。当读取数据时,一次读取多个内存单元。于是这里又出现两个问题: 多个存储单元存储的顺序? 如何确定要读几个内存单元?


    这里就要谈谈大小端的存放方式。小端存储 Little-Endian 就是低位字节排放在内存的低地址端,高位字节排放在内存的高地址端(就是和我们正常阅读顺序相反)。大端 Big-Endian 就是高位字节排放在内存的低地址端,低位字节排放在内存的高地址端。(就是和我们正常阅读顺序相同)


        需要说明的是,计算机采用大端还是小端存储是CPU来决定的, 我们常用的X86体系的CPU采用小端,一下ARM体系的CPU也是用小端,但有一些CPU却采用大端比如PowerPC、Sun。



 CPU与存储器之间的连接 



    在这里就需要介绍关于总线的相关概念。所谓总线是各种功能部件之间传送信息的公共通信干线,它是由导线组成的传输线束。我们知道计算机有运算器,控制器,存储器,输入输出设备这五大组件,所以总线就是用来连接这些组件的导线。

     按照计算机所传输的信息种类,计算机的总线可以划分为:


数据总线

数据总线DB是双向三态形式的总线,即它既可以把CPU的数据传送到存储器或输入输出接口等其它部件,也可以将其它部件的数据传送到CPU。数据总线的位数是微型计算机的一个重要指标,通常与微处理的字长相一致。我们说的32位,64位计算机指的就是数据总线。 

地址总线

地址总线AB是专门用来传送地址的,由于地址只能从CPU传向外部存储器或I/O端口,所以地址总线总是单向三态的,这与数据总线不同。地址总线的位数决定了CPU可直接寻址的内存空间大小。 

控制总线

控制总线主要用来传送控制信号和时序信号。控制总线的传送方向由具体控制信号而定,一般是双向的,控制总线的位数要根据系统的实际控制需要而定。其实数据总线和控制总线可以共用。 


总线也可以按照CPU内外来分类: 


内部总线

在CPU内部,寄存器之间和算术逻辑部件ALU与控制部件之间传输数据所用的总线称为片内部总线。

外部总线

通常所说的总线指片外部总线,是CPU与内存RAM、ROM和输入/输出设备接口之间进行通讯的通路,也称系统总线


    前面我面介绍了总线的分类,在我们的简单模型中。CPU通过总线和存储器之间直接进行通信。【按道理这里没有考虑MMU】


    实际上在现代的计算机中,存在一个控制芯片的模块。CPU需要和存储器,I/O设备等进行交互,会有多种不同功能的控制芯片,我们称之为控制芯片组(Chipset)。 


 CPU读取内存数据的方式 


        前面我们多次提到了指令的概念,也知道指令是0和1组成的,而汇编代码提高了机器码的可读性。为什么突然在这里介绍CPU指令呢? 主要是解释当CPU读取一个数据或指令时,CPU怎么知道需要读取多少个内存单元?


常见的CPU指令格式如下:


A1为被操作数地址,也称源操作数地址;

A2为操作数地址,也称终点操作数地址; 

A3为存放结果的地址。 

        同样,A1,A2,A3以是内存中的单元地址,也可以是运算器中通用寄存器的地址。所以就有一个寻址的问题。

        从上图来看我们知道CPU的指令长度是变长的。所以CPU并不能确定一条指令需要占用几个内存单元,那么CPU又是如何确定一条指令是否读取完了呢?


CPU指令的读取


        现在的CPU多数采用可变长指令系统。关键是指令的第一字节。 当CPU读指令时,并不是一下把整个指令读近来,而是先读入指令的第一个字节。指令译码器分析这个字节,就知道这是几字节指令。接着顺序读入后面的字节。每读一个字节,程序计数器PC加一。整个指令读入后,PC就指向下一指令(等于为读下一指令做好了准备)。

        比如上面这条MOV汇编指令,把立即数00存入AL寄存器。而CPU获取指令过程如下: 

从程序计数器获取当前指令的地址0x0001 

存储控制器从0x0001中读出整个字节,发送给CPU

PC+1 = 0X0002

CPU识别出【10110000】表示:操作是MOV AL,并且立即数长度为一个字节,所以整个指令的字长为2字节

CPU从地址0x0002取出指令的最后一个字节 CPU将立即数00存入AL寄存器

我们可以比较一下2条指令第一个字节的区别,发现这里的MOV  AL是1010 0000,而不是Sample1中的1011 000。

CPU读取了第一个字节后识别出,操作是MOV AL [D16],表示是一个寄存器间接寻址,A3操作是存放的是一个16位就是地址偏移量(为什么是16位?),CPU就判定这条指令长度3个字节。于是从内存0x0002~0x0003读出指令的后2个字节,进行寻址找到真正的数据内存地址,再次通过CPU读入,并完成操作。

    

     从上面我们可以看出一个指令会根据不同的寻址格式,有不同的机器码与之对应。而每个机器码对应的指令的长度都是在CPU设计时就规定好了。8086采用变长指令,指令长度是1-6个字节,后面可以添加8位或16位的偏移量或立即数。


内存数据的操作


        操作数可以是立即数,可以存放在寄存器,也可以存放在内存。对于第一个例子,指令已经说明,操作时是一个字节,于是CPU可以从下一个内存地址读取操作时,而对于第二个例子,操作数只是地址偏移,所以当CPU获得这个数据后,需要转换成实际的内存地址,在进行一次内存访问,把数据读入到寄存器中。这里就出现我们前面提到的问题,这个数据我们要读几个存储单元呢? 


         在8086中只能进行字节或字操作,而现在CPU都可以进行双字操作。同样,当我们要从一个内存读取数据的时候,也要指定读取数据的操作类型,这里也是双字操作。这样以来,就能从内存中正确的读出需要的长度了。虽然在写代码中就这么一个简单的赋值操作,获取你从来没想过在内存中怎么存放,又是怎么读取的。这一切都是编译器和CPU在背后为我们完成了。


    为什么要对齐?  


前面铺垫了这么多CPU和内存的工作原理。终于要开始解释为什么要对齐了。

对于大部分程序员来说,内存对齐应该是透明的。内存对齐是编译器的管辖范围。编译器为程序中的每个数据单元安排在适当的位置上。


从前面我们知道,目前计算机内存按照字节编址,每个地址的内存大小为1个字节。而读取数据的大小和数据线有关。比如数据线为8位那么一次读取一个字节,而如果数据线为32位,那么一次需要读取4个字节,这样是为了一次更多的获取数据提高效率。否则读取一个int变量就需要进行4次内存操作。对于内存访问一般有以下两个条件: CPU进行一次内存访问读取的数据和字长相同。 有些CPU只能对字长倍数的内存地址进行访问。

对于第一个条件一般来说,目前存储器一个cell是8bit,进行位扩展使他和字长还有数据线位数是相同,那么一次就能传送CPU可以处理最多的数据。而前面我们说过目前是按字节编址可能是因为一个cell是8bit,所以一次内存操作读取的数据就是和字长相同。 也正是因为和存储器扩展有关,每个DRAM位扩展芯片使用相同RAS如果需要跨行访问,那么需要传递2次RAS。所以以32位CPU为例,CPU只能对0,4,8,16这样的地址进行寻址。而很多32位CPU禁掉了地址线中的低2位A0,A1,这样他们的地址必须是4的倍数,否则会发送错误。



如上图,当计算机数据线为32位时,一次读入4个地址范围的数据。当一个int变量存放在0-3的地址中时,CPU一次就内存操作就可以取得int变量的值。但是如果int变量存放在1-4的地址中呢? 根据上面条件2的解释,这个时候CPU需要进行2次内存访问,第一次读取0-4的数据,并且只保存1-3的内容,第二次访问读取4-7的数据并且只保存4的数据,然后将1-4组合起来。如下图:


大部分的参考资料解释内存对齐有两个原因:

平台原因(移植原因):不是所有的硬件平台都能访问任意地址上的任意数据的;某些硬件平台只能在某些地址处取某些特定类型的数据,否则抛出硬件异常。

性能原因:数据结构(尤其是栈)应该尽可能地在自然边界上对齐。原因在于,为了访问未对齐的内存,处理器需要作两次内存访问;而对齐的内存访问仅需要一次访问。


 所以内存对齐不但可以解决不同CPU的兼容性问题,还能减少内存访问次数,提高效率。  


    如何对齐?  


内存对齐有一个对齐系数,一般是2,4,8,16字节这样。而不同平台上的对齐方式不同,这个主要是编译器来决定的。


Win32平台下的微软C编译器(cl.exefor 80×86)的对齐策略:

1)结构体变量的首地址是其最长基本类型成员的整数倍;

备注:编译器在给结构体开辟空间时,首先找到结构体中最宽的基本数据类型,然后寻找内存地址能是该基本数据类型的整倍的位置,作为结构体的首地址。将这个最宽的基本数据类型的大小作为上面介绍的对齐模数。

2)结构体每个成员相对于结构体首地址的偏移量(offset)都是成员大小的整数倍,如有需要编译器会在成员之间加上填充字节(internal adding);

备注:为结构体的一个成员开辟空间之前,编译器首先检查预开辟空间的首地址相对于结构体首地址的偏移是否是本成员的整数倍,若是,则存放本成员,反之,则在本成员和上一个成员之间填充一定的字节,以达到整数倍的要求,也就是将预开辟空间的首地址后移几个字节。

3)结构体的总大小为结构体最宽基本类型成员大小的整数倍,如有需要,编译器会在最末一个成员之后加上填充字节(trailing padding)

备注:

a、结构体总大小是包括填充字节,最后一个成员满足上面两条以外,还必须满足第三条,否则就必须在最后填充几个字节以达到本条要求。

b、如果结构体内存在长度大于处理器位数的元素,那么就以处理器的倍数为对齐单位;否则,如果结构体内的元素的长度都小于处理器的倍数的时候,便以结构体里面最长的数据元素为对齐单位。

4) 结构体内类型相同的连续元素将在连续的空间内,和数组一样。




 小结 


        以上整理了关于内存对齐的一些资料,解释了内存对齐是什么,为什么要内存对齐和怎样进行内存对齐。顺便介绍了一下CPU和存储器的工作原理。


        这也算是我第一次尝试吧。希望以后能坚持下来~

        欢迎指正!



Copyright © 古田计算器虚拟社区@2017