20145212 《信息安全系统设计基础》第14周学习总结

教材学习内容总结

第9章网络编程
物理和虚拟寻址

虚拟存储器

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

物理地址
- 计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组，每字节都有一个唯一的物理地址PA。
- 根据物理地址寻址的是物理寻址。
- 虚拟存储器被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。
- 使用虚拟寻址时，CPU通过生成一个虚拟地址VA来访问主存，这个虚拟地址在被送到存储器之前先转换成适当的物理地址（这个过程叫做地址翻译，相关硬件为存储器管理单元MMU）

地址空间

地址空间是一个非负整数地址的有序集合：{0,1,2,……}
线性地址空间：地址空间中的整数是连续的。
虚拟地址空间：CPU从一个有 N=2^n 个地址的地址空间中生成虚拟地址，这个地址空间成为称为虚拟地址空间。
地址空间的大小由表示最大地址所需要的位数来描述。N=2^n：n位地址空间
主存中的每个字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。

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

虚拟存储器——虚拟页VP，每个虚拟页大小为P=2^p字节
物理存储器——物理页PP，也叫页帧，大小也为P字节。
任意时刻，虚拟页面的集合都被分为三个不相交的子集：

未分配的：VM系统还没分配/创建的页，不占用任何磁盘空间。
缓存的：当前缓存在物理存储器中的已分配页
未缓存的：没有缓存在物理存储器中的已分配页

DRAM缓存的组织结构

不命中处罚很大
是全相联的——任何虚拟页都可以放在任何的物理页中。
替换算法精密
总是使用写回而不是直写。

页表

页表是一个数据结构，存放在物理存储器中，将虚拟页映射到物理页
页表就是一个页表条目PTE的数组，组成为有效位+n位地址字段
如果设置了有效位：地址字段表示DRAM中相应的物理页的起始位置，这个物理页中缓存了该虚拟页
如果没有设置有效位：

(1)空地址：表示该虚拟页未被分配
(2)不是空地址：这个地址指向该虚拟页在磁盘上的起始位置。

缺页

缺页：就是指DRAM缓存不命中。
缺页异常：会调用内核中的缺页异常处理程序，选择一个牺牲页。
页：虚拟存储器的习惯说法，就是块
交换=页面调度：磁盘和存储器之间传送页的活动
按需页面调度：直到发生不命中时才换入页面的策略，所有现代系统都使用这个。

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

操作系统为每个进程提供了一个独立的页表，也就是一个独立的虚拟地址空间。
多个虚拟页面可以映射到同一个共享物理页面上。
存储器映射：将一组连续的虚拟页映射到任意一个文件中的任意位置的表示法。
按需页面调度和独立的虚拟地址空间的结合简化了链接和加载、代码和数据共享，以及应用程序的存储器分配。

简化链接：独立的地址空间允许每个进程的存储器映像使用相同的基本格式，而不管代码和数据实际存放在物理存储器的何处。
简化加载：虚拟存储器使得容易想存储器中加载可执行文件和共享文件对象。
简化共享：独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。
简化存储器分配：虚拟存储器为向用户进程提供一个简单的分配额外存储器的机制。

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

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

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

地址翻译

地址翻译：一个N元素的虚拟地址空间（VAS）中的元素和一个M元素的物理地址空间（PAS）之间的映射。

MAP: VAS → PAS ∪ ∅
MAP = A' ，如果虚拟地址A处的数据在PAS的物理地址A'处
MAP = ∅ ，如果虚拟地址A处的数据不在物理存储器中

CPU中的一个控制寄存器页表基址寄存器指向当前页表，n位的虚拟地址包含两个部分：一个p位的虚拟页面偏移（VPO）和一个（n-p）位的虚拟页号，页表条目中的物理页页号和虚拟地址中的VPO串联起来，就得到了相应的物理地址。
当页面命中时，CPU硬件执行步骤

处理器生成虚拟地址，传给MMU
MMU生成PTE地址，并从高速缓存/主存请求得到他
高速缓存/主存向MMU返回PTE
MMU构造物理地址，并把它传给高速缓存/主存
高速缓存/主存返回所请求的数据给处理器。

处理缺页时，CPU硬件执行步骤

处理器生成虚拟地址，传给MMU
MMU生成PTE地址，并从高速缓存/主存请求得到他
高速缓存/主存向MMU返回PTE
PTE中有效位为0，触发缺页异常
确定牺牲页
调入新页面，更新PTE
返回原来的进程，再次执行导致缺页的指令，会命中

利用TLB加速地址翻译

TLB：翻译后备缓冲器，是一个小的、虚拟存储的缓存，其中每一行都保存着一个由单个PTE组成的块

步骤：

CPU产生一个虚拟地址
MMU从TLB中取出相应的PTE
MMU将这个虚拟地址翻译成一个物理地址，并且将它发送到高速缓存/主存
高速缓存/主存将所请求的数据字返回给CPU

多级页表

多级页表——采用层次结构，用来压缩页表。

如果一级页表中的一个PTE是空的，那么相应的二级页表就根本不会存在；
只有一级页表才需要总是在主存中，虚拟存储器系统可以在需要时创建、页面调入或调出二级页表，只有最经常使用的二级页表才缓存在主存中。

案例研究：Intel Core i7/Linux存储器系统
core i7地址翻译

PTE的三个权限位

R/W位：确定内容是读写还是只读
U/S位：确定是否能在用户模式访问该页
XD位：禁止执行位，64位系统中引入，可以用来禁止从某些存储器页取指令

1.linux为每个进程维持了一个单独的虚拟地址空间，其中，内核虚拟存储器位于用户栈之上。
内核虚拟存储器包含内核中的代码和数据结构，还有一些被映射到一组连续的物理页面（主要是便捷地访问特定位置，比如执行I/O操作的时候需要的位置）。
2.linux将虚拟存储器组织成一些区域（也叫做段）的集合。
允许虚拟地址空间有间隙；内核不用记录那些不存在的页，这样的页也不用占用存储器。
区域结构：

vm _start:指向这个区域的起始处；
vm _end:指向这个区域的结束处；
vm _prot:描述这个区域内所包含的所有页的读写许可权限； 
vm _fags:描述这个区域内的页面是与其他进程共享的，还是这个进程私有的，等等；
vm _next:指向链表的下一个结构.

Linux虚拟存储器系统

Linux为每个进程维持了一个单独的虚拟地址空间
内核虚拟存储器包括：内核中的代码和数据结构
一部分区域映射到所有进程共享的物理页面,另一部分包含每个进程都不相同的数据。
区域是已分配的虚拟存储器的连续片,区域的例子：

代码段
数据段
堆
共享库段
用户栈
……

每个存在的虚拟页面都保存在某个区域中。内核为系统中的每个进程维护一个单独的任务结构task_struct
一个具体区域的区域结构包括：

vm_start：指向起始处
vm_end：指向结束处
vm_prot：描述这个区域包含的所有页的读写许可权限
vm_flags：是共享的还是私有的
vm_next：指向下一个区域

存储器映射

存储器映射即指Linux通过将一个虚拟存储器区域与一个磁盘上的对象关联起来，以初始化这个虚拟存储器区域的内容的过程。
映射对象：
1.Unix文件系统中的普通文件
2.匿名文件（全都是二进制0）
共享对象和私有对象

共享对象对于所有把它映射到自己的虚拟存储器进程来说都是可见的。即使映射到多个共享区域，物理存储器中也只需要存放共享对象的一个拷贝。
私有对象运用的技术：写时拷贝。

使用mmap函数的用户级存储器映射
1.创建新的虚拟存储器区域

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

2.参数含义：

start：这个区域从start开始
fd：文件描述符
length：连续的对象片大小
offset：距文件开始处的偏移量
prot：访问权限位，具体如下：
        PROT_EXEC:由可以被CPU执行的指令组成
        PROT_READ:可读
        PROT_WRITE:可写
        PROT_NONE:不能被访问
flag：由描述被映射对象类型的位组成，具体如下：
        MAP_ANON:匿名对象，虚拟页面是二进制0
        MAP_PRIVATE:私有的、写时拷贝的对象
        MAP_SHARED：共享对象

3.删除虚拟存储器：

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

动态存储器分配

当运行时需要额外虚拟存储器时，使用动态存储器分配器维护一个进程的虚拟存储器区域。
分配器有两种风格：
1.显示分配器：要求应用显式地释放任何已经分配的块。
2.隐式分配器：要求分配器检测一个已分配块何时不再被程序所使用，就释放这个块。也叫做垃圾收集器。

malloc和free函数

系统调用malloc函数，从堆中分配块：

#include <stdlib.h>
void *malloc(size_t size);//成功返回指针，指向大小至少为size字节的存储器块，失败返回NULL

系统调用free函数来释放已分配的堆块：

#include <stdlib.h>
void free(void *ptr);//无返回值

ptr参数必须指向一个从malloc、calloc或者reallov获得的已分配块的起始位置。
使用动态存储器分配原因：经常直到程序实际运行时，才知道某些数据结构的大小。
分配器的要求和目标
1.显示分配器的要求：

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

2.目标：

最大化吞吐率:最大化存储器利用率——峰值利用率最大化
吞吐率：每个单位时间里完成的请求数

碎片

碎片：虽然有未使用的存储器，但是不能用来满足分配请求。
内部碎片：发生在一个已分配块比有效载荷大的时候，易于量化。
外部碎片：发生在当空闲存储器合计起来足够满足一个分配请求，但是没有一个单独的空间块足以处理这个请求时发生。难以量化，不可预测。
隐式空闲链表
堆块的格式：由一个字的头部，有效荷载，和可能的额外填充组成。
将堆组织成一个连续的已分配块和空闲块的序列：

空闲块通过头部中的大小字段隐含地连接着，分配器可以通过遍历堆中所有的块，从而间接地遍历整个空闲块的集合。
需要：特殊标记的结束块。
系统对齐要求和分配器对块格式的选择会对分配器上的最小块大小有强制的要求。

放置已分配的块

分配方式有：
1.首次适配：从头开始搜索空闲链表，选择第一个合适的空闲块
2.下一次适配：从上一次搜索的结束位置开始搜索
3.最佳适配：检索每个空闲块，选择适合所需请求大小的最小空闲块
申请额外的堆存储器
sbrk函数

#include <unistd.h>
vid *sbrk(intptr_t incr);//成功则返回旧的brk指针，出错为-1

通过将内核的brk指针增加incr来扩展和收缩堆。
合并空闲块
合并是针对于假碎片问题的，任何实际的分配器都必须合并相邻的空闲块。
两种策略：
- 立即合并
- 推迟合并

垃圾收集

垃圾收集器是一种动态存储分配器，它自动释放程序不再需要的已分配块，这些块被称为垃圾，自动回收堆存储的过程叫做垃圾收集
垃圾收集器将存储器视作一张有向可达图，只有当存在一条从任意根节点出发并到达p的有向路径时，才说节点p是可达的，而不可达点就是垃圾。
Mark&Sweep垃圾收集器有两个阶段：
1.标记：标记出根节点的所有可达的和已分配的后继
2.清楚：释放每个未被标记的已分配块。
相关函数：
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的后继
C保守的Mark&Sweep——平衡二叉树：根本原因是C语言不会用类型标记来标记存储器位置

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

间接引用坏指针
scanf错误
读未初始化的存储器
假设堆存储器被初始化为0
允许栈缓冲区溢出
缓冲区溢出错误
假设指针和它们指向的对象是相同大小的

在远处起作用action at distance

造成错位错误
引用指针，而不是它所指向的对象
误解指针运算
引用不存在的变量
引用空堆块中的数据
引起存储器泄露

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）	重要成长
目标	5000行	30篇	400小时
第一周	0/0	1/2	10/10	使用虚拟机安装linux系统
第二周	341/341	1/3	20/30	掌握核心的linux命令
第三周	177/518	2/5	16/46	学会了虚拟机上的VC编程
第五周	161/679	1/6	15/61
第六周	73/752	1/7	15/76	安装了Y86处理器
第七周	134/886	1/8	12/88	建立了项目结构
第八周	0/886	2/10	12/100	进行了系统的复习
第九周	61/947	1/11	10/110	学习Linux操作系统的基本I/O服务
第十周	502/1449	1/12	10/120	通过实践加深了对指令的理解
第十一周	667/2116	2/16	15/125	学习了异常，通过实践了解了进程的并发
第十二周	69/2185	4/16	15/140	通过对前三周代码的复习，加深了对教材内容的认识
第十三周	473/2658	1/17	15/155	学习了网络编程和多线程的基本内容
第十四周	0/2658	1/18	15/170	学习了虚拟存储器的概念及其作用

20145212 《信息安全系统设计基础》第14周学习总结

20145212 《信息安全系统设计基础》第14周学习总结

教材学习内容总结

学习进度条

参考资料