20135333苏正生——信息安全系统设计基础第十四周学习总结 20135333苏正生——信息安全系统设计基础第十四周学习总结 第九章 虚拟存储器

第九章 虚拟存储器


第一节 物理和虚拟寻址

1.物理地址——【物理寻址】

2.虚拟地址——【虚拟寻址】

第二节 地址空间
1.地址空间
地址空间是一个非负整数地址的有序集合:

{0,1,2,……}

2.线性地址空间

3.虚拟地址空间
CPU从一个有 N=2^n 个地址的地址空间中生成虚拟地址,这个地址空间成为称为虚拟地址空间。

4.地址空间大小表示:
由最大地址所需要的位数来描述。

N=2^nn位地址空间

第三节 虚拟存储器作为缓存的工具

1.DRAM缓存的组织结构
2.页表
页表是一个数据结构,存放在物理存储器中,将虚拟页映射到物理页。

页表就是一个页表条目PTE的数组,组成为:有效位+n位地址字段
1.如果设置了有效位:
地址字段表示DRAM中相应的物理页的起始位置,这个物理页中缓存了该虚拟页

2.如果没有设置有效位:
(1)空地址:表示该虚拟页未被分配

(2)不是空地址:这个地址指向该虚拟页在磁盘上的起始位置。
20135333苏正生——信息安全系统设计基础第十四周学习总结
20135333苏正生——信息安全系统设计基础第十四周学习总结
第九章 虚拟存储器
3.缺页
DRAM缓存不命中。

4.虚拟存储器中的局部性
局部性原则保证了在任意时刻,程序将往往在一个较小的活动页面集合上工作,这个集合叫做工作集/常驻集。

颠簸:工作集大小超出了物理存储器的大小。

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

操作系统为每个进程提供了一个独立的页表,多个虚拟页面可以映射到同一个共享物理页面上。

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

PTE的三个许可位:

  • SUP:表示进程是否必须运行在内核模式下才能访问该页

  • READ:读权限

  • WRITE:写权限

第六节 地址翻译

20135333苏正生——信息安全系统设计基础第十四周学习总结
20135333苏正生——信息安全系统设计基础第十四周学习总结
第九章 虚拟存储器

一、结合高速缓存和虚拟存储器
在既使用SRAM高速缓存又使用虚拟存储器的系统中,
大多数系统选择物理寻址
主要思路是地址翻译发生在高速缓存之前
页表目录可以缓存,就像其他的数据字一样
二、利用TLB加速地址翻译
TLB:翻译后备缓冲器,是一个小的、虚拟存储的缓存,其中每一行都保存着一个由单个PTE组成的块
20135333苏正生——信息安全系统设计基础第十四周学习总结
20135333苏正生——信息安全系统设计基础第十四周学习总结
第九章 虚拟存储器
三、多级页表

第七节 案例研究

一、Core i7地址翻译
20135333苏正生——信息安全系统设计基础第十四周学习总结
20135333苏正生——信息安全系统设计基础第十四周学习总结
第九章 虚拟存储器

二、Linux虚拟存储器系统
20135333苏正生——信息安全系统设计基础第十四周学习总结
20135333苏正生——信息安全系统设计基础第十四周学习总结
第九章 虚拟存储器
一、Linux虚拟存储器区域
区域:就是已分配的虚拟存储器的连续片。

一个具体区域的区域结构包括:

  • vm_start:指向起始处

  • vm_end:指向结束处

  • vm_prot:描述这个区域包含的所有页的读写许可权限

  • vm_flags:是共享的还是私有的

  • vm_next:指向下一个区域

第八节 存储器映射

一、共享对象和私有对象

  1. 共享对象

  2. 私有对象
    于execve函数:
    20135333苏正生——信息安全系统设计基础第十四周学习总结
20135333苏正生——信息安全系统设计基础第十四周学习总结
第九章 虚拟存储器

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

  1. 创建新的虚拟存储器区域

  2.  #include <unistd.h>
     #include <sys/mman.h>
    
     void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);
    

参数含义:

  • start:这个区域从start开始

  • fd:文件描述符

  • length:连续的对象片大小

  • offset:距文件开始处的偏移量

  • prot:访问权限位,具体如下:

    • PROT_EXEC:由可以被CPU执行的指令组成

    • PROT_READ:可读

    • PROT_WRITE:可写

    • PROT_NONE:不能被访问

  • flag:由描述被映射对象类型的位组成,具体如下:

    • MAP_ANON:匿名对象,虚拟页面是二进制0

    • MAP_PRIVATE:私有的、写时拷贝的对象

    • MAP_SHARED:共享对象

2.删除虚拟存储器:

include
include <sys/mman.h>
int munmap(void *start, size_t length);

成功返回0,失败返回-1

从start开始删除,由接下来length字节组成的区域。

第九节 动态存储器分配

一、malloc和free函数:

malloc函数:从堆中分配块:

#include <stdlib.h>

void *malloc(size_t size);

free函数:释放已分配的堆块:

#include <stdlib.h>

void free(void *ptr);

二、分配器的要求和目标:

1.要求
处理任意请求序列、立即响应请求、只使用堆、对齐块、不修改已分配的块
2.目标:
最大化吞吐率、最大化存储器利用率

三、碎片

  1. 内部碎片

  2. 外部碎片

四、隐式空闲链表

堆块的格式:
20135333苏正生——信息安全系统设计基础第十四周学习总结
20135333苏正生——信息安全系统设计基础第十四周学习总结
第九章 虚拟存储器

五、放置策略

  1. 首次适配

  2. 下一次适配

  3. 最佳适配

六、申请额外的堆存储器

sbrk函数:

#include <unistd.h>

vid *sbrk(intptr_t incr);

成功则返回旧的brk指针,出错为-1
通过将内核的brk指针增加incr来扩展和收缩堆。

七、合并空闲块

策略:

立即合并
推迟合并

八、带边界的合并

20135333苏正生——信息安全系统设计基础第十四周学习总结
20135333苏正生——信息安全系统设计基础第十四周学习总结
第九章 虚拟存储器

九、实现简单的分配器

序言块和结尾块

十、显式空闲链表

1.区别
(1)分配时间
隐式:分配时间是块总数的线性时间

显式:分配时间是空闲块数量的线性时间。

(2)链表形式
隐式——隐式空闲链表

显式——双向链表,有前驱和后继,比头部脚部好使。

2.排序策略:
后进先出
按照地址顺序维护

十一、分离的空闲链表

分离存储,是一种流行的减少分配时间的方法。一般思路是将所有可能的块大小分成一些等价类/大小类。

分配器维护着一个空闲链表数组,每个大小类一个空闲链表,按照大小的升序排列。

有两种基本方法:

  1. 简单分离存储
    每个大小类的空闲链表包含大小相等的块,每个块的大小就是这个大小类中最大元素的大小。

  2. 分离适配

  3. 伙伴系统——分离适配的特例

第十节 垃圾收集

  1. 基本知识
    垃圾收集器

  2. Mark&Sweep垃圾收集器
    两个阶段:标记、清除
    相关函数:

     ptr定义为typedef void *ptr
     ptr isPtr(ptr p):如果p指向一个已分配块中的某个字,那么就返回一个指向这个块的起始位置的指针b,否则返回NULL
     int blockMarked(ptr b):如果已经标记了块b,那么就返回true
     int blockAllocated(ptr b):如果块b是已分配的,那么久返回ture
     void markBlock(ptr b):标记块b
     int length(ptr b):返回块b的以字为单位的长度,不包括头部
     void unmarkBlock(ptr b):将块b的状态由已标记的改为未标记的
     ptr nextBlock(ptr b):返回堆中块b的后继
    
  3. C保守的Mark&Sweep——平衡二叉树
    根本原因是C语言不会用类型标记来标记存储器位置。

第十一节 C程序中常见的与存储器有关的错误

  1. 间接引用坏指针
    常见错误——scanf错误

  2. 读未初始化的存储器
    常见错误——假设堆存储器被初始化为0

  3. 允许栈缓冲区溢出
    常见错误——缓冲区溢出错误

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

  5. 造成错位错误

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

  7. 误解指针运算

  8. 引用不存在的变量

  9. 引用空堆块中的数据

  10. 引起存储器泄露

参考:

  1. 《深入理解计算机系统》

  2. 有道云笔记
    http://note.youdao.com/share/web/file.html?id=0b10aca28173bc7c8306ff7aa608e79e&type=note