20145314郑凯杰《信息安全系统设计基础》第14周学习总结

20145314郑凯杰《信息安全系统设计基础》第14周学习总结

明确教材学习目标

学习目标

1. 理解虚拟存储器的概念和作用
2. 理解地址翻译的概念
3. 理解存储器映射
4. 掌握动态存储器分配的方法
5. 理解垃圾收集的概念
6. 了解C语言中与存储器有关的错误

教材学习内容总结

虚拟存储器提供了三个重要的能力

• 它将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式，高效的使用了主存。
• 它为每个进程提供了一致的地址空间，从而简化了存储器管理。
• 它保护了每个进程的地址空间不被其他进程破坏。

程序员需要理解虚拟存储器的三个原因：

• 虚拟存储器是中心的：它是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的交互中心；
• 虚拟存储器是强大的：它可以创建和销毁存储器片、可以映射存储器片映射到磁盘某个部分等等；
• 虚拟存储器若操作不当则十分危险。

9.1 物理和虚拟寻址

1.物理寻址

计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组。每字节都有一个唯一的物理地址PA。第一个字节的地址为0，接下来的字节的地址为1，再下一个为2，依此类推。给定这种简单的结构，CPU访问存储器的最自然的方式就是使用物理地址，我们把这种方式称为物理寻址。

图1：

2.虚拟寻址

使用虚拟寻址时，CPU通过生成一个虚拟地址来访问主存，这个虚拟地址在被送到存储器之前先转换成适当的物理地址。将一个虚拟地址转换为物理地址的任务叫做地址翻译。

图2：

CPU芯片上叫做存储器管理单元的专用硬件，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容是由操作系统管理。

9.2 地址空间

1. 线性地址空间：地址空间中的整数是连续的一个非整数地址的有序集合：{0,1,2,...}。
2. 虚拟地址空间：在一个带虚拟存储器的系统中，CPU从一个有N = 2 ^ n个地址空间中生成虚拟地址。{0,1,2,3,...,N-1}。
3. 一个地址空间的大小是由表示最大地址所需要的倍数来描述的。

虚拟存储器的基本思想：允许每个数据对象有多个独立的地址，其中每个地址都选自一个不同的地址空间。

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

1. 虚拟存储器被组织为一个由存放在磁盘上N个连续的字节大小的单元组成的数组。每个字节都有一个唯一的虚拟地址，这个唯一的虚拟地址是作为到数组的索引的。
2. 每个虚拟页的大小为P = 2 ^ n字节。物理存储器被分割为物理页(PP)，大小也为P字节(物理页也称为页帧)。
3. 在任意时刻，虚拟页面的集合都分为三个不相交的子集：未分配的、缓存的、未缓存的
4. 页表：一个页表条目的数组。将虚拟地址映射为物理地址，每个页表项(PTE)，有一个有效位，标识该地址是否在内存的缓存中，还有物理页号或磁盘地址。

图3：

1. 缺页，如果地址不再页表中，则牺牲一条记录，加载进新的地址映射和内容。

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

1. 存储器映射：将一个虚拟存储器区域与一个磁盘上的对象关联起来，以初始化这个虚拟存储器区域的内容，一旦一个虚拟页面被初始化了，他就在一个由内核维护的专门的交换文件之间换来换去。
2. 简化链接、简化加载、简化共享、简化存储器分配

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

1. 每次CPU生成一个地址时，地址翻译硬件都会读一个PTE，所以再PTE上添加额外的许可位来控制对一个虚拟页面的访问

2. PTE的三个许可位：

    SUP：表示进程是否必须运行在内核模式下才能访问该页
   
    READ：读权限
   
    WRITE：写权限
   

9.6 地址翻译

图4：

1.页面命中时，CPU执行步骤：

第一步：处理器生成一个虚拟地址，并把它传送给MMU
第二步：MMU生成PTE地址，并从高速缓存/主存请求得到他
第三步：高速缓存/主存向MMU返回PTE
第四步：MMU构造物理地址，并把它传送给高速缓存/主存
第五步：高速缓存/主存返回所请求的数据字给处理器

2.处理缺页，要求硬件和操作系统协作完成

第一步到第三步同上
第四步：PTE中的有效位是0，MMU触发异常，传递CPU中的控制到操作系统内核中的缺页异常处理程序
第五步：程序确定物理存储器中的牺牲页，如果页面被修改，则换出到磁盘
第六步：程序页面调入新的页面，并更新存储器中的PTE
第七步：程序返回到原来的进程，再次执行导致缺页的指令

3.结合高速缓存和虚拟存储器

主要的思路：地址翻译发生在高速缓存查找之前

4.利用TLB加速地址翻译

翻译后备缓冲器TLB：是一个小的，虚拟寻址的缓存，其中每一行都保存着一个由单个PTE组成的块，具有高度的相连性

5.用来压缩页表的常用方法是使用层次结构的页表，这种方式从两个方面减少了存储器要求：

第一点：节约，如果一级页表中的PTE是空的，那么相应的二级页表就不会存在
第二点：减压，只有一级页表存在主存中，只有经常使用的二级页表才需要缓存在主存中

9.7 Linux虚拟存储器系统

图5：

1.Linux虚拟存储器区域

每个存在的虚拟页存在某个区域中，而不属于某个区域的虚拟页是不存在的，并且不能被进程引用。

2.一个具体区域结构包含的字段：

（1）vm_start：指向这个区域的起始处。
（2）vm_end：指向这个区域的结束处。
（3）vm_prot：描述这个区域的内包含的所有页的读写许可权限。
（4）vm_flags：描述这个区域内页面是与其他进程共享的，还是这个进程私有的(还描述了其他一些信息)。
（5）vm_next：指向链表中下一个区域结构。

9.8 存储器映射

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

映射对象：

• Unix文件系统中的普通文件
• 匿名文件（全都是二进制0）

一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的交换文件之间换来换去。交换文件也叫交换空间，或交换区域。

1.再看共享对象

（1）共享区域：

• 一个映射到共享对象的虚拟存储器区域叫做共享区域。
• 共享对象的关键点在于即使对象被映射到了多个共享区域，物理存储器也只需要存放共享对象的一个拷贝。一个共享对象物理页面不一定是连续的。

（2）私有对象是使用写时拷贝巧妙技术被映射到虚拟存储器中的。

2.再看fork函数

当fork函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID。

3.再看execve函数

execve函数在当前进程中加载并运行包含在可执行目标文件a.out中的程序，用a.out程序有效地替代了当前程序。

Execve("a.out",NULL,NULL);

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

mmap函数要求内核创建一个新的虚拟存储器区域，最好是从地址start开始的一个区域，并将文件描述符fd指定的对象的一个连续的片映射到这个新区域。

void *mmap(void *start,size_t length,int prot,int flags,int fd,off_t offest);
	若成功则为指向映射区域的指针，若出错则为MAP_FAILDE（-1）

munmap函数删除虚拟存储器的区域。

int munmap(void *start,size_t length);
	若成功则返回0，若失败则返回-1.

9.9 动态存储器分配

1.动态存储器分配器维护着一个进程的虚拟存储器区域，称为堆。

2.分配器的两种风格：

显示分配器
隐式分配器（垃圾收集器）

3.malloc和free函数

malloc函数从堆中分配块

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

返回一个指针，指向大小为至少size字节的存储器块，这个块可能会包含字啊这个块内的任何数据对象类型做对齐

动态存储器分配器还可以通过使用mmap和munmap函数，显式的分配和释放堆存储器，还可以使用sbrk函数

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

free函数释放已分配的堆块

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

原因是经常执行到程序实际运行时才能知道某数据结构的大小，硬编码不便于维护。一种更好的方法是在运行时，在已知了n的值之后，动态的分配这个数组

5.分配器的要求和目标

约束条件：

处理任意请求序列
立即响应要求
只使用堆
对齐块
不修改已分配的块

相互冲突的两个目标

目标1、最大化吞吐率
目标2、最大化存储器利用率

6.利用率低的主要原因是碎片，碎片分为内碎片和外碎片

7.隐式空闲链表

一个块是由一个字的头部，有效载荷以及可能的一些额外的填充组成

优点：简单

缺点：任何操作的开销

很重要的一点就是意识到系统对齐要求和分配器对块格式的选择会对分配器上的最小块大小有强制性要求

8.放置已分配的块

分配器执行这种搜索的方式是由放置策略确定的，常见的策略

首次适配
    优点：将最大的空闲块保留在链表的后面
    缺点：在靠近链表起始处留下小空闲的碎片，增加较大块的搜索时间
下一次适配
    优点：运行速度快
    缺点：利用率低
最佳适配
    优点：利用率好
    缺点：要求对堆进行彻底的搜查

9.获取额外的堆存储器

分配器额外的存储器转换成了一个大的空闲块，将这个块插入到空闲链表中，然后被请求的块放置在这个新的空闲块中

10.合并空闲块

假碎片：邻接的空闲块可能发生的现象。

为了解决假碎片，任何实际的分配器都必须合并相邻的空闲块，这个过程就叫合并，重要的合并策略：立即合并和推迟合并

11.实现一个简单的分配器

一般分配器设计
操作空闲列表的基本常数和宏
创建初空闲链表
释放和合并块
分配块

12.显式空闲链表

将空闲块组织成某种形式的显式数据结构

释放一个块的时间是线性的，取决于空闲链表中块的排序策略

后进先出：在一个常数时间内完成
地址顺序：比首次适配有更高的利用率，接近最佳适配的利用率

13.分离的空闲链表

分离存储：维护多个空闲链表，其中每个链表中的块由大致相等的大小

基本的方法：

简单分离存储：每个大小类的空闲链表包含大小相等的块，每个块的大小就是大小类总最大元素的大小
    优点：分配和释放都是很快的的常数时间操作
         每个块只有很少的存储器开销
         已分配块不需要头部脚部
         最小块大小就是一个字
    缺点：容易造成内部和外部碎片
         不会合并空闲块

分离适配：分配器维护着一个空闲链表的数组
    优点：快速高效

伙伴系统：分离适配的特例

9.10 垃圾收集

1.垃圾收集器是动态存储分配器，自动释放程序不在需要的已分配块

2.makr&sweep垃圾收集器有标记阶段和清除阶段

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

1.间接引用坏指针

进程的虚拟地址空间有较大的洞，没有映射到任何有意义的数据

经典的scanf错误

scanf（"%d",&val）---->scanf ("%d",val)

2.使用fgets函数限制输入串的大小

void bufoverflow()
{
    char buf[64]
    gets(buf)
    return;
}

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

int **makeArray1(int n ,int m)
{
    int i;
    int **A = (int **)Malloc(n sizeof(int))

    for(i = 0;i < n; i++)
        A[i] = (int *)Malloc(m *sideof(int))
    return A;
}

4.造成错位错误

int **makeArray2(int n ,int m)
{
    int i;
    int **A = (int **)Malloc(n sizeof(int))

    for(i = 0;i <= n; i++)
        A[i] = (int *)Malloc(m *sideof(int))
    return A;
}  

5.误解指针运算

int *search(int *p,int val)
{   
    while(*p && *p,int val)
        p + = sizeof(int);
    return p
}

6.引用不存在的变量

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

学习遇到的问题

在地址翻译部分的物理地址计算不是太明白，为什么将虚拟地址后半部分直接和物理页号串联起来就得到了物理地址？

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）	重要成长
目标	2000行	30篇	400小时
第九周	832/950	17/17	140/140
第十周	968/1050	18/18	160/160
第十一周	1100/1200	19/19	180/180
第十二周	1197/1300	21/21	200/200

| 第十三周 | 1300/1400 | 22/22 | 210/210 |

| 第十四周 | 1300/1500 | 23/23 | 230/230 | |

参考资料

• 《深入理解计算机系统V2》学习指导
• 2016-2017-1 《信息安全系统设计基础》教学进程
• Linux 基础入门
• 《深入理解计算机系统》