CSAPP-虚拟存储器

编程/技术 2019-05-12 @ 09:59:29 浏览数: 207 净访问: 174 By: skyrover

本博客采用创作共用版权协议, 要求署名、非商业用途和保持一致. 转载本博客文章必须也遵循署名-非商业用途-保持一致的创作共用协议


CSAPP真是本好书啊,读的时候酣畅淋漓,读完豁然开朗

虚拟存储器是对主存的抽象概念,是硬件异常,硬件地址翻译,主存,磁盘文件和内核软件的完美交互,为每个进程提供了一个大的,一致的和私有的地址空间。

9.1 物理和虚拟寻址

CPU访问存储器最自然的方式就是使用物理地址。

虚拟寻址就是CPU通过生成一个虚拟地址来访问主存,虚拟地址在被送到存储器之前先转换为适当的物理地址。这一过程是地址翻译,CPU上的存储器管理单元进行这一工作,使用主存中的查询表来动态翻译虚拟地址。

9.2 地址空间

CPU从一个N=2^n个地址的地址空间生成虚拟地址,成为虚拟地址空间,它也被称为一个n位地址空间。比如有32位和64位地址空间,这一个属性是描述操作系统能力的,表示操作系统可以使用32位或者64位的地址空间。

物理地址空间和系统中物理存储器的M个字节相对应,可以假设M=2^m

9.3 虚拟存储器作为缓存的工具

虚拟存储器被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。磁盘上的数组被缓存在主存中。磁盘和主存中的传输单元是块。对于虚拟存储器来说这个块叫做虚拟页,而物理存储器中是物理页(页帧)

虚拟存储器(虚拟页)和物理存储器(物理页)的对应关系可以分为三个状态:

  • 未分配的:虚拟页没有数据和它关联
  • 已缓存的:物理存储器上有数据和它关联
  • 未缓存的:没有缓存在物理存储器上的已经分配的页

9.3.1 DRAM缓存的组织结构

DRAM缓存的组织结构完全是由巨大的不命中开销驱动的,而且虚拟页很大,由于大的不命中处罚,DRAM缓存是全相联的。因为如果不是全相联而是组相联或者直接映射,就会导致冲突(来回替换),导致性能降低。全相联意味着任何虚拟页都可以放置在任何的物理页中,任何物理页都可以包含任意虚拟页。

不命中时候的策略也很重要。

另外DRAM缓存总是使用写回,而不是直写,因为对磁盘的访问时间很长。

9.3.2 页表

页表将虚拟页映射到物理页。页表就是一个页表条目(PTE)的数组。虚拟地址空间的每个页在页表中一个固定偏移量处都有一个PTE。每个PTE会是由一个有效位和一个n位地址字段组成。

  • 如果设置有效位,则地址字段表示DRAM中相应物理页的开始位置
  • 如果没有设置有效位,那么空地址表示虚拟页还未分配
  • 如果没有设置有效位,那么地址指向虚拟页在磁盘上的起始位置

9.3.3 页命中

当CPU读取虚拟存储器中的一个字,首先地址翻译硬件将虚拟地址作为索引来定位PTE,然后读取,如果有设置有效位,则说明数据缓存在DRAM中,然后使用对应的地址构造物理存储器地址并且读取。

9.3.4 缺页

CPU读取虚拟存储器中一个字,但是没有设置有效位,则说明数据没有缓存在DRAM上,所以引发一个缺页异常。

缺页异常调用内核中的缺页异常处理程序,选择一个牺牲页,如果牺牲页有修改则内核将牺牲页拷回磁盘,然后修改对应页表条目。

后面内核从异常处理程序返回,重启导致缺页的指令,这样就可以正常工作了。

9.3.5 分配页面

当操作系统分配一个新的虚拟存储器页时候(比如调用malloc),会在磁盘上创建空间并且更新页表条目,使得它指向磁盘上这个新创建的页面。

9.3.6 又是局部性救了我们

虽然在整个过程中程序引用的不同页面的总数可能超过物理存储器总大小,但是局部性会保证在任意时刻,程序将往往在一个较小的活动页面集合上工作,这个集合叫做工作集或者常驻集。

如果工作集大小超过了物理存储器的大小,那么程序会进入一种颠簸的状态。这时候页面将不断的换进换出。

使用getrusage函数监测缺页数量。

虚拟存储器作为存储器管理的工具

操作系统为每个进程提供了一个独立的页表,也就是独立的虚拟地址空间,并且多个虚拟页面可以映射到同一个共享物理页面上。

  • 简化链接:独立地址空间允许每个进程的存储器映像使用相同的基本格式,这样允许链接器生成全链接的可执行文件,因为使用的是虚拟地址,而虚拟地址是独立于物理存储器中的最后位置的。
  • 简化加载:可以直接将某些虚拟页标记无效,然后将页表条目指向目标文件中适当的位置,这样就不需要拷贝任何数据从磁盘到存储器,在页初次被引用时候,虚拟存储器系统按照需要自动的调入数据页。将一组连续的虚拟页映射到任意一个文件中的任意位置叫做存储器映射(mmap)
  • 简化共享:操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面。
  • 简化存储器分配:连续的虚拟地址页面映射到物理存储器不一定连续。

虚拟存储器作为存储器保护的工具

通过在PTE上添加一些额外的许可位来控制对一个虚拟页面内容的访问。

  • SUP位表示进程是否必须运行在内核模式下才能访问该页
  • READ位
  • WRITE位 控制对页面的读写访问

如果指令违反了许可条件,则CPU触发一个一般保护故障,将控制传递给一个内核中的异常处理程序,一般报告为段错误。

地址翻译

地址翻译是一个N元素的虚拟地址空间中的元素和一个M元素的物理地址空间中元素的映射。

CPU中一个控制寄存器,页表基址寄存器指向当前页表,n位的虚拟地址包含两个部分:p位的虚拟页面偏移和n-p位的虚拟页号。通过虚拟页号找到对应页表项,将页表项中的物理页号和虚拟地址中的虚拟页面偏移串联起来就得到对应物理地址。

9.6.1 结合高速缓存和虚拟存储器

在既使用虚拟存储器又使用SRAM高速缓存的系统中,一般都会选择使用物理寻址来访问SRAM高速缓存。

书上给了一个物理寻址的高速缓存和虚拟存储器结合起来的例子,主要就是MMU(地址翻译)在高速缓存查找之前。

首先去找页表项(页表项也是缓存在高速缓存中的),不命中则去存储器查找,命中返回,返回后构建物理地址,在高速缓存中查找,命中返回,不命中去存储器找。

9.6.2 利用TLB加速地址翻译

TLB(Translation Lookaside Buffer)翻译后备缓冲器。TLB是一个小的,虚拟寻址的缓存,每一行都保存着一个由单个PTE组成的块,TLB通常有高度的相联性。用于组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟页号中提取出来的。如果TLB有T=2^t个组,那么TLB索引是由虚拟页号的t个最低位组成的,TLB标记是由虚拟页号剩余的位组成的。

9.6.3 多级页表

对于一个32位地址空间,4KB页面和4字节的PTE(页表项)来说,需要的页表大小是:2^32字节/4KB页面大小 = 1024*1024个页面,所以总共需要1024**1024*4字节=4MB,也就是说即使引用是虚拟空间很小一部分,也需要一个4MB的页表驻留在存储器中。

用来压缩页表的常用方法是使用层次结构的页表。书中介绍的是两级页表,所以只需要1024个一级页表PTE就足够表示4GB的地址空间了,每个一级页表PTE都会负责虚拟地址空间的一个4MB的片,并且页面大小是4KB,所以二级页表每块需要1024个页表项,同时使一级页表每个PTE指向二级页表的每块的基址就可以构成整个二级页表的结构了。

P.S. 书上举的例子提到的虚拟地址空间的形式:前2K个页面是代码和数据,6K个页面是未分配,1023个页面也未分配,接下来一个页面分配给了用户栈。当时我还算了下,总共9K个页面,每个页面4KB,那也就36K(KB)=36MB数据?后来才意识到这仅仅是为了例子简单而只假设虚拟地址空间有这么些数据。一般来说32位虚拟地址空间应该有2^32字节/4KB大小=1024×1024个页面

  1. 如果一级页表的一个PTE是空的,那么相应二级页表不会存在,所有节省了空间。
  2. 只有一级页表才需要总是在主存中,虚拟存储器系统可以在需要的时候创建,页面调入或者调出二级页表,减少了主存的压力。

地址翻译过程:虚拟地址被划分成了k个VPN和一个VPO,每个VPN i都是到第i级页表的索引,然后对应每级页表的每个页表项都指向下级页表的基址,最后一级页表指向了物理页面的PPN或者磁盘块的地址。

访问k个PTE,主要是TLB会将不同层次上页表的PTE缓存起来。

9.6.4 端到端的地址翻译

这一节稍微比较麻烦,需要把前面的知识综合起来。这里我记录下我理解的全过程

首先书中给了一些条件:

  • 存储器是按照字节寻址的
  • 存储器访问是针对一字节的字的(不是通常的4字节的字)
  • 虚拟地址是14位长,也就是说4KB的地址空间
  • 物理地址是12位长,也就是说2KB的地址空间
  • 页面大小是64字节的,2^6,也就是占6位地址,即在虚拟地址和物理地址的页偏移
  • TLB是四路组相连的,总共16个条目,所以组索引2位,剩下6位就是标记位(用于区别映射到同一个组的不同VPN)
  • L1 d-cache是物理寻址,直接映射的,行大小有4个字节,总共有16个组(数据4字节,所以数据块偏移2位,16组所以组索引4位,剩下6位是标记位)

书上的图关于地址和TLB以及缓存的地址分配展示的很清楚,详细看下即可理解。另外页表总共是2^14/2^6=2^8=256个页表项,图中只展示了前16个页表项。TLB是用来做地址翻译的缓存的。高速缓存中后面的块0,块1等的值实际上是不在地址中的,地址中只是块偏移,为了方便展示才把数据放到高速缓存中的。

后面是一个实际的例子,比如CPU读地址0x03d4处字节的加载指令(读取1字节的字),首先是将地址写出来并且对应解析,这里需要解析的是根据地址得到VPN,VPO,然后通过VPN得到物理页号,通过物理页号PPN+VPO就可以得到实际物理地址,而TLB是对翻译进行缓存的,所以得到VPN后直接查TLB看能不能直接得到PPN。书中表格给的很详细,VPN是0x0F,检查TLB,TLBI是0x03即第4组,TLBT是0x03,匹配可以得到PPN是0x0D,和VPO链接起来物理地址是0x354

接下来,会根据物理地址得到数据,此时会先访问高速缓存,其中CO(0x0),CI(0x5),也就是第6组的第一块数据,如果CT(0x0D)匹配的话,最终发现匹配,所以返回数据0x36

如果TLB不命中,就需要读取页表,取出PPN。如果PTE无效,则产生缺页,内核必须调入合适的页面,重新运行这条加载指令。也可能是PTE有效,但是所需要的存储器块在缓存中不命中。

9.7 Intel Core i7/Linux存储器系统

这个例子其实地址翻译部分和上面一小节的东西大同小异,不过就是这是一个实际的处理器翻译的例子。其中涉及了一些细节,其实对我目前的需求来说,没必要,所以这里直接略过了。

9.7.2 Linux虚拟存储器系统

内核虚拟存储器包含内核中的代码和数据结构,其中某些区域被映射到所有进程共享的物理页面。比如每个进程共享内核的代码和全局数据结构。

内核虚拟存储器的其他区域包含每个进程都不相同的数据。

  • Linux虚拟存储器区域

Linux将虚拟存储器组织成一些区域的集合,一个区域就是已经存在着的(已分配的)虚拟存储器的连续片,这些页是以某种方式相关联的。而且允许虚拟地址空间有间隙,内核不用记录那些不存在的虚拟页。

内核位系统中每个进程维护一个单独的任务结构,任务结构中的元素包含或者指向内核运行该进程所需要的所有信息(PID,指向用户栈的指针)

pgd指向第一级页表的基址,在内核运行这个进程时候,就将pgd存放在CR3控制寄存器中。

mmap指向一个vm_area_structs区域结构的链表,每个结构都描述了当前虚拟地址空间的一个区域。

这块比较深入了,看来是不是要看源代码了,233333

  • Linux缺页异常处理

产生缺页的时候,进行下面步骤:

  1. 虚拟地址A是否合法?遍历区域结构链表,看是否能找到对应地址,找不到则出发段错误。
  2. 进行的存储器访问是否合法?是否有读,写或者执行这个区域页面的权限?不合法则触发保护异常。
  3. 选择牺牲页面,如果牺牲页面被修改过,则交换出去,换入新的页面并且更新页表,缺页处理程序返回的时候,CPU重新启动引起缺页的指令。

哈!终于翻过了一座高山,第9章内容指日可下!

9.8 存储器映射

Linux通过将一个虚拟存储器区域与一个磁盘上的对象关联起来,以初始化这个虚拟存储区域的内容,被称为存储器映射

  • Unix文件系统中普通文件
  • 匿名文件:匿名文件是内核创建的,包含的全是二进制0,CPU第一次引用这样的一个区域内的虚拟页面时候,内核就在物理存储器中找到合适的牺牲页面,让二进制0覆盖牺牲页面并且更新页表。但是磁盘和存储器之间没有实际的数据传送。

9.8.1 再看共享对象

有两种对象,分别是共享对象和私有对象。

共享对象就是一个对象可以被映射到虚拟存储器的一个区域,某个进程对这个区域的写操作,对其他进程是可见的,而且变化也会反映在磁盘的原始对象上。

私有对象则是相反,不可见,也不会反映在磁盘上。

而且在加载的时候因为每个对象有一个唯一的文件名,所以在加载第二个进程相同对象的时候,可以直接将页表条目指向对应的物理页面,所以物理存储器只需要存放共享对象的一份拷贝。

对于私有区域,使用了写时拷贝,所以只有再写某一个页的时候将其复制出来,更新当前进程对应页表的条目,指向这个新的拷贝。这样有效的利用了物理存储器。

9.8.2 再看fork函数

fork被调用后,内核位新进程创建数据结构以及虚拟存储器,虚拟存储器里面的mm_struct,区域结构和页表是拷贝自以前的进程,但是都是私有区域,所以在任意一个进程进行写操作的时候,就会创建新页面,所以就为每个进程保持了私有地址空间的抽象概念。

简直精彩啊!

9.8.3 再看execve函数

比如进行Execve("a.out", NULL, NULL),加载并运行需要以下步骤:

  • 删除已存在的用户区域:当前进程虚拟地址的用户部分已存在的区域结构
  • 映射私有区域:创建新的区域结构,私有的,写时拷贝
  • 映射共享区域
  • 设置程序计数器

P.S. bss段是全局未初始化变量,全局已初始化变量段在data

9.8.4 使用mmap函数的用户级存储器映射

创建新的虚拟存储器区域,并且将对象映射到这些区域中

#include <unistd.h>
#include <sys/mman.h>

void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);

9.9 动态存储器分配

dynamic memory allocator,可以使用mmapmnumap来创建和删除虚拟存储器的区域,但是使用动态存储器分配器会更方便以及移植性。

动态存储器分配器维护着一个进程的虚拟存储器区域,叫做堆。同时每个进程,内核维护着一个变量brk(break),指向堆的顶部。

分配器将对分为块,有已分配块和空闲块。分配器有两种,而且都要求应用显式的分配块,不同在于谁来释放已分配的块

  • 显式分配器:malloc->free, new->delete
  • 隐式分配器:垃圾收集器(gc)

9.9.1 malloc和free函数

#include <stdlib.h>
void *malloc(size_t size);

返回指针,指向大小至少位size字节的存储器块,这个块会为可能包含在这个块的任何数据对象类型做对齐。Unix上,malloc返回一个8字节(双字)边界对齐的块。

malloc可以通过使用mmapmunmap函数,显式分配和释放堆存储器,或者使用sbrk函数

#include <unistd.h>
void *sbrk(intptr_t incr);

P.S. 调用malloc分配内存后,指向的指针并不会因为调用free而释放,所以需要手动释放这个指针。

9.9.2 为什么要使用动态存储器分配

主要是为了在程序运行时候才知道分配多少内存。

9.9.3 分配器的要求和目标

这里有一个概念,对齐要求,主要作用是使得分配的块可以保存任何类型的数据对象,一般来说,分配器返回的块是8字节(双字)边界对齐的。

有两个目标:

  • 最大化吞吐率:每个单位时间内完成的请求数
  • 最大化存储器利用率:虚拟存储器有限

峰值利用率~

9.9.4 碎片

包含内部碎片和外部碎片

  • 内部碎片:一个已分配块比有效载荷大时候发生的
  • 外部碎片:没有单独的空闲块足够大来处理分配请求

一般来说需要来试图维持少量的大空闲块,而不是维持大量的小空闲块

9.9.5 实现问题

有几个部分:

  1. 空闲块组织
  2. 放置(新分配的块)
  3. 分割(放置后空闲块剩余部分)
  4. 合并(处理刚被释放的块)

9.9.6 隐式空闲链表

这是书中给的一个堆块的根式,如果有双字(8字节)的对齐约束条件,那么块大小就是8的倍数,那么就说明块大小最低3位总是0,这样块大小数据就在高29位上存储,低3位存储的就是其他比如是否分配的信息。

比如有个块大小24(0x18)字节,已经分配,那么头部就是

0x18 | 0x1 = 0x00000019

按照上面块的格式可以将堆组织成一个连续的已分配块和空闲块的序列,这样的结构是隐式空闲链表(空闲块是通过头部的字段隐含的链接着)

9.9.7 放置已分配的块

当应用请求分配块的时候,分配器搜索空闲链表,查找一个足够大的可以放置请求块的空闲块。有几种常见放置策略:首次适配,下一次适配和最佳适配。

9.9.8 分割空闲块

找到空闲块之后,如果分配这个空闲块中多少空间,要么使用整个空闲块,要么将空闲块分割。

9.9.9 获取额外的堆存储器

如果找不到合适空闲块,那么第一可以合并那些在存储器中物理上相邻的空闲块来创建更大的空闲块。或者调用sbrk函数,向内核请求额外的堆存储器。

9.9.10 合并空闲块

假碎片,解决这个问题,分配器必须合并相邻的空闲块。可以有立即合并,也可以有推迟合并。

立即合并可能会导致抖动,块反复的合并,反复的分割。

9.9.11 带边界标记的合并

合并空闲块和下一块空闲块比较简单,但是合并当前空闲块和上一个空闲块需要遍历链表,记住前面块的位置,直到到达当前块。

可以加上边界标记,在每个块的结尾处加上脚部,脚部就是头部的副本,而且这个脚部总是距当前块开始位置一个字的距离。

有四种合并情况,这个具体看书吧,比较简单,需要注意合并细节。但是这样可能会增大存储器开销,所以一般优化方法是将前面块的已分配/空闲位存放在当前块中多出来的低位中,就不用脚部了。但是空闲块还是需要脚部,要不然只知道前面块是否空闲,而不知道空闲块大小。

9.9.12 实现一个简单的分配器

这种综合的小节一般都是硬骨头啊,硬着头皮啃吧。。

实现的是一个基于隐式空闲链表,使用立即边界标记合并方式的分配器。链表具有以下形式,第一个字是双字边界对齐的不使用的填充字,后面紧跟着一个特殊的序言块,8字节已分配块,只由一个头部和一个脚部构成。序言块后面是多个由malloc和free调用创建的普通块。堆总以一个特殊的结尾块结束,块是大小为0的已分配块,只由一个头部组成。

static char *mem_heap;  /*堆的第一字节位置*/
static char *mem_brk;   /*堆最后一个字节加一位置*/
static char *mem_max_addr; /*堆最大合法位置加一*/

void mem_init(void){
    mem_heap = (char *)Malloc(MAX_HEAP);
    mem_brk = (char *)mem_heap;
    mem_max_addr = (char *)(mem_heap + MAX_HEAP);
}

void *mem_sbrk(int incr){
    char *old_brk = mem_brk;
    if ((incr < 0) || ((mem_brk + incr) > mem_max_addr)){
        errno = ENOMEM;
        fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
        return (void *)-1;
    }
    mem_brk += incr;
    return (void *)old_brk;
}
  • 操作空闲链表的基本常数和宏

大量使用强制类型转换和指针运算

#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12)

#define MAX(x, y) ((x) > (y)? (x):(y))
/*将大小和已分配位结合起来返回一个值,放在头部或者脚部,参考9.9.6*/
#define PACK(size, alloc) ((size)|(alloc))

/*读取和返回参数p引用的字,因为p是一个(void *)指针,不可以直接进行间接引用*/
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))

/*从p处的头部或者脚部返回大小和已分配位*/
#define GET_SIZE(p) (GET(p) & -0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

/*块指针的操作,获取块的头部和脚部,块指针指向第一个有效载荷字节*/
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/*指向后面的块和前面的块指针*/
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

定义这些宏就可以很方便的比如计算出存储器中后面的块的大小:size_t size = GET_SIZE(HDRP(NEXT_BLKP(bp)));

  • 创建初始空闲链表
int mm_init(void){
    if ((heap_listp == mem_sbrk(4*WSIZE)) == (void *)-1){
        return -1;
    }
    PUT(heap_Listp, 0); // 堆的起始位置,双字边界对齐的填充字
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); // 序言块的头
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); // 序言块的脚部
    PUT(heap_listp + (3*WSIZE), PACK(0, 1)); // 结束块
    heap_listp += (2*WSIZE); // 指向序言块

    // 将空堆扩展到为CHUNKSIZE字节,创建初始的空闲块
    if (extend_heap(CHUNKSIZE/WSIZE) == null){
        return -1;
    }
    return 0;
}

static void *extend_heap(size_t words){
    char *bp;
    size_t size;

    // 双字对齐
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1){
        return NULL;
    }

    PUT(HDRP(bp), PACK(size, 0)); // 将之前mem_sbrk指针指向的区域设置为空闲块,HDRP(bp)得到的是之前的结束块头部
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // 设置结束块

    return coalesce(bp); // 合并两个空闲块
}
  • 释放和合并块
void mm_free(void *bp){
    size_t size = GET_SIZE(HDRP(bp));

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp); // 释放后合并块
}

static void *coalesce(void *bp){
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));

    // 第一种情况,前后都已经分配
    if (prev_alloc && next_alloc){
        return bp;
    }

    // 第二种情况,前面已分配,后面未分配,合并后面的
    else if (prev_alloc && !next_alloc){
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        // 头部设置size之后,后面再引用脚部,就是加上size之后的数据了
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }

    // 第三种情况,前面未分配,后面已经分配,合并前面的
    else if (!prev_alloc && next_alloc){
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }

    // 第四种情况,合并两者

    else{
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    return bp;
}

这里有一个技巧,就是前面的序言块和结束块都设置为已分配,这样就减少了边界检查的情况。

  • 分配块
void *mm_malloc(size_t size){
    size_t asize;
    size_t extendsize;
    char *bp;

    if (size == 0){
        return NULL;
    }

    if (size <= DSIZE){
        asize = 2*DSIZE;
    }else{
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
    }

    if ((bp = find_fit(asize)) != NULL){
        place(bp, asize);
        return bp;
    }

    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL){
        return NULL;
    }
    place(bp, asize);
    return bp;
}

9.9.13 显式空闲链表

堆可以组织为一个双向空闲链表,对应的前驱和后继指针放在空闲块的主体里面。

这样使得首次适配的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。释放一个块可能是线性的也可能是常数的。

  • 后进先出维护链表:所以释放块是线性的,如果使用边界标记,则合并也可以在常数时间内完成。
  • 地址顺序维护链表:释放一个块需要线性时间搜索来找到合适前驱。

缺点是空闲块必须足够大,用来包含所有需要的指针,头部和脚部,导致了更大的最小块大小,潜在的提高了内部碎片的程度。

9.9.14 分离的空闲链表

减少分配时间的方法:分离存储,维护多个空闲链表,每个链表中的块有大致相等的大小。一般是将可能的块大小分为一些等价类,叫做大小类。

分配的时候,搜索相应空闲链表。

  • 简单分离存储
  • 分离适配 常用方法
  • 伙伴系统

9.10 垃圾收集

垃圾收集器是一种动态存储分配器,自动释放程序不再需要的已分配块。

9.10.1 垃圾收集器的基本只是

垃圾收集器将存储器视为一张有向可达图,图中节点被分成一组根节点和一组堆节点,堆结点对应于堆中的一个已分配块。根节点对应于不在堆中的位置,包含指向堆中的指针。这些位置可能是寄存器,栈中的变量或者是虚拟存储器中读写数据区域内的全局变量。

所以垃圾收集器工作内容是维护可达图,定期释放不可达节点并且将它们返回给空闲链表。对于Java的垃圾收集器,因为对于应用如何创建和使用指针有着严格的控制,所以能够维护可达图的精确表示,也就能够回收所有垃圾。但是C/C++不能,这样也叫作保守的垃圾收集器,因为一些不可达节点可能被错误的标记为可达。

9.10.2 Mark&Sweep 垃圾收集器

标记阶段标记出根节点的所有可达和已分配后继,清除节点释放每个未被标记的已分配块。

  • ptr isPtr(ptr p) 如果p指向了一个已分配块中的某个字,那么返回一个指向这个块的起始位置的指针b,否则返回NULL
void mark(ptr p){
    if ((b = isPtr(p)) == NULL){
        return;
    }
    if (blockMarked(b)){
        return;
    }

    markBlock(b);
    len = length(b);
    for (i=0; i<len; i++){
        mark(b[i]);
    }
    return;
} 

void sweep(ptr b, ptr end){
    while (b < end){
        if (blockMarked(b)){
            unmarkBlock(b);
        }else if (blockAllocated(b)){
            free(b);
        }
        b = nextBlock(b);
    }
    return;
}

9.10.3 C程序的保守 Mark&Sweep

有两个不容易实现的:

  • isPtr 没有一种明显的方式来判断它的输入参数p是不是一个指针
  • 即使知道是指针,也没有明显的方式来判断p是否指向一个已分配块的有效载荷中的某个位置

9.11 C程序中常见的与存储器有关的错误

9.11.1 间接引用坏指针

比如应该是 scanf("%d", &val) 而不是 scanf("%d", val)

9.11.2 读未初始化的存储器

bss存储器位置(未初始化的全局C变量)总是被加载器初始化位0,但是对于堆存储器并不是这样。

9.11.3 允许栈缓冲区溢出

9.11.4 假设指针和它们指向的对象是相同大小的

9.11.5 造成错位错误

9.11.6 引用指针,而不是它所指向的对象

(*size)--而不是*size--

9.11.7 误解指针运算

9.11.8 引用不存在的变量

int *stackref(){
    int val;
    return &val;
}

错误的指向了栈中的一个存储器地址

9.11.9 引用空闲堆块中的数据

9.11.10 引起存储器泄露


点赞走一波😏


评论

提交评论