找出全书你认为最重要的一章，深入重新学习一下，要求（期末占10分）：
完成这一章所有习题
详细总结本章要点
给你的结对学习搭档讲解你的总结并获取反馈
我选择教材第九章的内容来深入学习，一方面，虚拟内存这一部分内容本身就十分重要，另一方面，我在操作系统课上对这一部分的知识理解的很浅，在十一周自学教材这一部分内容时也因为知识点太多而没有学得很深入，正好借此机会来重新学习这一章的内容，加深理解。
为了更加有效地管理存储器且少出错，现代系统提供了对主存的抽象概念，叫做虚拟存储器(VM）。
虚拟存储器是硬件异常，硬件地址翻译，主存，磁盘文件和内核软件的完美交互。
为每个进程提供一个大的，一致的和 私有的地址空间。
3个重要能力。
将主存看成磁盘地址空间的高速缓存。
简化存储器管理虚拟内存在幕后工作，程序员为什么要理解它呢？
虚拟存储器是中心的。遍布在计算机系统所有层次，硬件异常，汇编器，连接器，加载器，共享对象，文件和进程中扮演重要角色。虚拟存储器是强大的。
例子
能读写存储器位置来修改磁盘文件内容。
加载文件到存储器不需要显式的拷贝。虚拟存储器是危险的
例子
一个带有错误指针的程序可以立即崩溃于段错误或者保护错误。
运行完成，却不产生正确结果。物理地址(Physical Address,PA):计算机系统的主存被组织为M个连续的字节大小的单元组成的数组。每个字节的地址叫物理地址.物理寻址。物理寻址。虚拟寻址(virtual addressing)的寻址形式。
虚拟地址(Virtual address,VA)来访问主存。
虚拟地址转换为物理地址叫做地址翻译(address translation)。地址翻译也需要CPU硬件和操作系统之间的紧密结合。
CPU芯片上有叫做存储器管理单元(Memory Management Unit,MMU)的专用硬件。
利用存储在主存中的查询表来动态翻译虚拟地址。
查询表由操作系统管理。地址空间(address space)是一个非负整数地址的有序集合。
如果地址空间中整数是连续的，我们说它是线性地址空间(linear address space)。
线性地址空间。N=2^n个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间(virtual address space)。最大地址所需要的位数来描述的。
N=2^n个地址的虚拟地址空间叫做n位地址空间。32位或64位。一个系统还有物理地址空间,它与系统中物理存储器的M=2^m(假设为2的幂)个字节相对应。
地址空间的概念很重要，因为它区分了数据对象(字节)和 它们的属性(地址)。
每个字节(数据对象)一般有多个 独立的地址(属性)。每个地址都选自不同的地址空间。
字节有一个在虚拟地址空间的虚拟地址。物理地址。访问到这个字节。虚拟存储器(VM) 被组织为一个存放在磁盘上的N个连续字节大小的单元组成的数组。
每个字节都有一个唯一的虚拟地址，这个虚拟地址作为到数组的索引。
磁盘上数组的内容被缓存到主存中。
同存储器层次结构其他缓存一样，磁盘上的数据被分割成块。
这些块作为磁盘和主存之间的传输单元。
虚拟页(Virtual Page,VP)就是这个块 物理页,大小也为P字节`` 也被称为``页帧(page frame)。虚拟页的集合都被分为3个不相交的子集。
还未分配(或者创建)的页。未分配的块没有任何数据与之相关联。
DRAM表示虚拟存储器系统的缓存，在主存中缓存虚拟页,有两个特点。
DRAM缓存不命中处罚十分严重。
磁盘比DRAM慢100000多倍。第一个字节的时间开销要比从该扇区中读连续的字节慢大约100000倍
DRAM缓存的组织结构由这种巨大的不命中开销驱动。因此有以下特点。
虚拟页往往很大。
DRAM缓存是全相联
精密的替换算法
DRAM缓存总是写回
访问时间很长直写
判断命中和替换由多种软硬件联合提供。
硬件和页表(page table)。
物理存储器的数据结构。
虚拟页映射到物理页。地址翻译硬件将虚拟地址转换为物理地址都会读取页表。维护页表的内容，以及磁盘及DRAM之间来回传送页。
页表就是一个页表条目(Page Table Entry,PTE)的数组.
固定偏移量处都有一个PTE.每个PTE有一个有效位和n位地址字段。
有效位表明虚拟页是否被缓存。
如果有效位存在，那么地址字段指向对应的物理存储器。
如果有效位不存在。 地址字段要么为NULL,要么指向虚拟页在磁盘所在的位置。
DRAM缓存不命中称为缺页。
处理过程如下：
PT。PTE有效位，发现未被缓存，触发缺页异常。缺页异常处理程序
牺牲页。写回)代替了牺牲页的位置。中断结束，重新执行最开始的指令。
在DRAM中读取成功。
块被称为页。
磁盘和DRAM之间传送页的活动叫做交换(swapping)或者页面调度(paging)。
有不命中发生时，才换入页面，这种策略叫做按需页面调度(demand paging)。
比如某个页面所指向地址为NULL，将这个地址指向磁盘某处，那么这就叫分配页面。
此时虚拟页从未分配状态 变为 未缓存。
操作系统为每个进程提供一个独立的页表。
因此，VM简化了链接和加载,代码和数据共享,以及应用程序的存储器分配。
相同的格式。
0x08048000(32位)处或0x400000(64位)处开始。数据，bss节,栈。设计和实现。从不实际拷贝任何数据从磁盘到存储器。虚拟存储系统完成。独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间的一致共享机制
操作系统内核代码
printf.即虚拟页连续(虚拟页还是单独的)，物理页可以不连续。使得分配更加容易。
任何现代操作系统必须为操作系统提供手段来控制对存储器系统的访问。
如果指令违反了许可条件，触发一般保护性异常，然后交给异常处理程序，Shell一般会报告为段错误(segmentaion fault)。
基址寄存器(Page Table Base Register,PTBR)指向当前页表。n位的虚拟地址包含两个部分
p位的虚拟页面偏移(Virtual Page Offset,VPO)
n-p位的虚拟页号(Virtual Page Number,VPN)
页面条目 (PTE)中物理页号(PPN)和虚拟地址中的VPO串联起啦，即是物理地址
VPN,PPN都是块，都是首地址而已，所以需要偏移地址PPO,VPO
图(a)展示页面命中,CPU硬件执行过程:
虚拟地址，把它传送给MMU。PTE地址(PTEA)，并从高速缓存/主存请求中得到它。返回PTE。物理地址(PA)，并把它传送给高速缓存/主存。处理器。页面命中完全由硬件处理，与之不同的是，处理缺页需要 硬件和操作系统内核协作完成。
PTE有效位是零，所以MMU触发异常，传递CPU中的控制到操作系统内核中的 缺页异常处理程序。缺页异常处理程序确定出物理存储页中的牺牲页，如果这个页面已经被修改，则把它换出到磁盘。缺页异常处理程序调入新的页面，并更新存储器中的PTE。缺页异常处理程序返回到原来的进程，再次执行导致缺页的指令，之后就是页面命中一样的步骤。在任何使用虚拟存储器又使用SRAM高速缓存的系统中，都存在应该使用虚拟地址 还是 使用 物理地址 来访问SRAM高速缓存的问题。
大多数系统是选择物理寻址。
存储块和共享来自相同虚拟页面的块成为简单的事。
(PTE)的一部分。
每次CPU产生一个虚拟地址，MMU就必须查阅一个PTE，以便将虚拟地址翻译为 物理地址。
PTE碰巧缓存在L1中，那么开销就下降到一到两个周期
许多系统都试图消除这样的开销，他们在MMU中包含了一个关于PTE的小缓存，称为翻译后备缓冲器(Translation Lookaside Buffer,TLB)。
TLB是一个小的，虚拟寻址的缓存。
单个PTE组成的块。TLB通常用于高度的相连性组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟页号中提取出来的。TLB有T=2^t个组
TLB索引(TLBI)是由VPN的t个最低位组成。(对应于VPO)TLB标记(TLBT)是由VPN中剩余位组成(对应于VPN)TLB命中步骤
TLB命中
虚拟地址。MMU从TLB取出对应的PTE。MMU将这个虚拟地址翻译成一个物理地址，发送到高速缓存/主存
TLB不命中的时候，MMU必须从L1缓存或内存中取出相应的PTE,并进行类似缺页处理过程。如果我们有一个32位地址空间，4KB大小的页面(p=2^12)和一个4B的PTE，即使应用所引用的只是虚拟地址空间中很小的一部分，也总是需要一个4MB的页表驻留在存储器中。
所以多级页表的诞生用于解决在很少使用时有一个很大的页表常驻于内存。
用来压缩页表的常用方式是使用层次结构的页表。
以下用上图的两层作为例子。
9KB个页面，PTE为4个字节。
2KB个页面分配给代码和数据。6KB个页面未分配1023个页面也未分配用户栈
PTE负责映射虚拟地址空间中一个4MB大小的片(chunk).
1024个连续的页面组成。4MB=1024个页面*PTE大小4字节。片i中每个页面都没有分配，那么一级PTE i就为空。
PTE 2~PTE 7片i中有一个被分配了，那么PTE i就不能为空。PTE为空，那么相应的二级页表就根本不会存在。
潜在节约，大部分时候内存都是未分配的。
k级页表层次结构的地址翻译。
k个VPN和一个VPO。每个VPN i都是i-1级页表到i级页表的索引。PPN存于k级页表。PPO依旧与VPO相同。此时TLB能发挥作用，因为层次更细，更利于缓存。使得多级页表的地址翻译不比单级页表慢很多。
一个在有一个TLB和L1 d-cache的小系统上。作出如下假设:
字节寻址的。一字节的字的。14位长(n=14)
12位长(m=12)
64字节(P=2^6)
16个条目L1 d-cache是物理寻址，高速缓存，直接映射(E=1)的，行大小为4字节，而总共有16个组。存储结构快照：
物理地址的字段来寻址。
E=1。命中。
TLB
4kb
块大小64字节Intel QuickPath技术外部I/O桥直接通信L3高速缓存DDR3存储器控制器
上图完整总结了Core i7地址翻译过程，从虚拟地址到找到数据传入CPU。
Core i7采用四级页表层次结构。
CR3 控制寄存器指向第一级页表(L1)的起始位置
CR3也是每个进程上下文的一部分。CR3也要被重置。一级，二级，三级页表PTE的格式:
P=1时 地址字段包含了一个40位物理页号(PPN)，指向适当的页表开始处。
4kb对齐。
PPO为12位 = 4kb
PPO的大小就跟物理页的大小有关。四级页表的PTE格式:
MMU翻译虚拟地址时，还会更新两个内核缺页处理程序会用到的位。
A位
MMU都会设置A位，称为引用位(reference bit).D位
脏位(dirty bit).四级页表如何将VPN翻译成物理地址
VPN被用作页表的偏移量。CR3寄存器包含L1页的物理地址
内核虚拟存储器
内核虚拟存储器包含内核中的代码和数据。
内核虚拟存储器的某些区域被映射到所有进程共享的物理页面
Linux也将一组连续的虚拟页面(大小等同于系统DRAM总量)映射到相应的一组物理页面。内核虚拟存储器包含每个进程不相同的数据。
页表，内核在进程上下文中时使用的栈，等等。Linux将虚拟存储器组织成一些区域(也叫做段)的集合。
连续片，这些片/页已某种形式相关联。
代码段，数据段，堆，共享库段，用户栈。虚拟页都保存在某个区域。
区域的概念很重要虚拟地址空间有间隙。一个进程中虚拟存储器的内核数据结构。
内核为系统中每个进程维护了一个单独的任务结构。任务结构中的元素包含或指向内核运行该进程所需要的全部信息。
task_struct
mm_struct
pgd
页表的基址。将pgd存放在CR3控制寄存器mmap
vm_area_structs(区域结构)vm_area_structs都描述了当前虚拟地址空间的一个区域(area).vm_start:指向这个区域的起始处。vm_end:指向这个区域的结束处。vm_port:描述这个区域内包含的所有页的读写许可权限。vm_flags:描述这个区域页面是否与其他进程共享，还是私有。vm_next: 指向链表的下一个区域。MMU在试图翻译虚拟地址A时，触发缺页 。这个异常导致控制转移到缺页处理程序，执行一下步骤。
解决方法:
缺页处理程序 搜索区域结构链表。vm_start 和vm_end 做比较。
树 的数据结构算法查找如果不合法 ，触发段错误 。
存储器是否合法?
读，写，执行这个页面的权限?不合法，触发保护异常，终止进程。正常的话
存储器映射: Linux通过将一个虚拟存储器区域与一个磁盘上的对象关联起来，以初始化这个虚拟存储器区域的内容，这个过程叫做存储器映射。
虚拟存储器区域可以映射到以下两种类型文件。
普通文件:一个区域可以映射到一个普通磁盘文件的连续部分。
可执行文件。文件区(section)被分成页大小的片，每一片包含一个虚拟页面的初始化内容。初始化，虚拟页面此时还并未进入物理存储器。
到CPU第一次引用这个页面。匿名文件 : 一个区域可以映射到一个匿名文件。
CPU第一次引用这样区域(匿名文件)的虚拟页面时。
二进制零覆盖。虚拟页面标记为驻留在存储器中。又叫请求二进制零的页(demand-zero page)。
交换文件，交换空间。(win下叫做paging file)
交换文件(swap file)之间换来换去。交换文件也叫交换空间或者交换区域。交换空间都限制着当前运行着的进程分配的虚拟页面总数。共享对象的由来
只读文本区域。
printfUinx shell的tcsh```存储器映射提供一种机制，来共享对象。一个对象被映射到虚拟存储器的一个区域，一定属于以下两种。
虚拟地址空间的一个区域。
虚拟存储器的进程是可见的。磁盘上的原始对象。共享区域。映射到私有对象的区域做出的改变，对于其他进程不可见.写操作不会反映到磁盘上。虚拟存储器那个区域叫做私有区域。
进程1，将共享对象映射到虚拟存储器中，然后虚拟存储器将这一段找一块物理存储器存储。
进程2也要引用同样的共享对象时。
进程1已经映射了这个对象。进程2的虚拟存储器直接指向了那一块进程1指向的物理存储器。共享区域，物理存储器依旧只有一个共享对象的拷贝。
物理存储器内存。
私有对象使用一种叫做写时拷贝(conpy-on-write)的巧妙技术。
私有对象开始生命周期的方式基本与共享对象一样。
私有对象的进程，相应私有区域的页表条目都被标记为只读。
vm_area_structs)被标记为私有的写时拷贝。过程:只要有进程试图写私有区域内的某个页面，那么这个写操作触发保护异常。
PTE)指向这个新的拷贝，恢复被修改页面的可写权限。CPU重新执行这个写操作。私有对象中的拷贝直到最后可能的时刻，写时拷贝充分使用了稀缺的物理存储器
了解fork函数如何创建一个带有自己独立虚拟地址空间的新进程。
fork函数被当前进程调用时。
PID。虚拟存储器。
的mm_struct,区域结构和页表的原样拷贝。只读。并给两个区域进程的每个区域结构都标记为私有的写时拷贝。fork函数在新进程返回时。
虚拟存储器相同。理解execve函数实际上如何加载和运行程序。
execve函数在当前进程加载并执行目标文件a.out中的程序，用a.out代替当前程序。
文本，数据，bss和栈区域创建新的区域结构。
a.out文件中的文件和数据区。bss区域是请求二进制零，映射到匿名文件。
a.out中a.out程序与共享对象链接。
动态链接到这个程序。虚拟地址的共享区域。execve最后一件事设置PC指向文本区域的入口点。
Unix进程可以使用mmap函数来创建新的虚拟存储器区域，并将对象映射到这些区域中。
#include <unistd.h>
#include <sys/mman.h>
void *mmap(void *start,size_t length,int prot,int flags,int fd,off_t offset);
返回:若成功时则为指向映射区域的指正，若出错则为MAP_FAILED(-1).
参数解释:
fd,start,length,offset:
mmap函数要求内核创建一个新的虚拟存储器区域，最好是从地址start开始的一个区域，并将文件描述符fd指定的对象的一个连续的片chunk映射到这个新的区域。
length字节offset字节的地方开始。statr地址仅仅是个暗示
NULL，让内核自己安排。prot
参数prot包含描述新映射的虚拟存储器区域的访问权限位。(对应区域结构中的vm_prot位)
PROT_EXEC:这个区域内的页面由可以被CPU执行的指令组成。PROT_READ:这个区域内的页面可读。PROT_WRITE:这个区域内的页面可写。PROT_NONE: 这个区域内的页面不能被访问。flag
参数flag由描述被映射对象类型的位组成。
MAP_ANON标记位:映射对象是一个匿名对象。MAP_PRIVATE标记位:被映射对象是一个私有的，写时拷贝的对象。MAP_SHARED标记位:被映射对象是一个共享对象。虽然可以使用更低级的mmap和munmap函数来创建和删除虚拟存储器的区域。
但是C程序员还是觉得用动态存储器分配器(dynamic memory allocator)更方便。
动态存储器分配器维护着一个进程的虚拟存储区域，称为堆(heap)。
二进制零的区域。bss区域，并向上生长(向更高的地址)。brk(break)，指向堆顶。块block的集合来维护。
虚拟存储器片，即页面大小。已分配，要么是空闲。
已分配
已分配的块显式地保留供应用程序使用。已分配的块保持已分配状态，直到它被释放。
应用程序显示执行。分配器自身隐式执行(JAVA)。空闲
空闲块可用于分配。空闲块保持空闲，直到显式地被应用分配。分配器有两种基本分格。
显式分配器(explict allocator)
malloc程序显示分配器
malloc和freenew和deleteimplicit allocator)垃圾收集器(garbage collector).垃圾收集(garbage collection).Lisp,ML以及Java等依赖这种分配器。malloc
C标准库提供了一个称为malloc程序包的显示分配器。
#include<stdlib.h>
void* malloc(size_t size);
返回:成功则为指针，失败为NULL
malloc 返回一个指针，指向大小为至少size字节的存储器块。
size字节，很有可能是4或8的倍数
数据对象类型做对齐。Unix系统用8字节对齐。malloc不初始化它返回的存储器。
calloc函数。
calloc是malloc一个包装函数。realloch函数malloc遇到问题。
NULL， 并设置errno。动态存储分配器，可以通过使用mmap和munmap函数，显示分配和释放堆存储器。
sbrk函数。#include<unistd.h>
void *sbrk(intptr_t incr);
返回:若成功则为旧的brk指针，若出错则为-1，并设置errno为ENOMEML.
free
程序通过调用free函数来释放已分配的堆块。
#include<stdlib.h>
void free(void *ptr);
返回:无
ptr参数必须指向一个从malloc,calloc,realloc获得的已分配块的起始位置。
free行为未定义。free没有返回值，不知道是否错了。
程序使用动态存储器分配的最重要原因是:
显式分配器有如下约束条件
堆。对齐块。
不修改已分配的块。目标
吞吐率最大化和存储器使用率最大化。这两个性能要求通常是相互冲突的。
n个分配和释放请求的某种序列R1,R2,R3.....Rn
吞吐率 :每个单位时间完成的请求数。最小化 来最大化吞吐率优秀的分配算法。峰值利用率(peak utilization)
吞吐率和存储器利用率是相互牵制的，分配器设计的一个有趣的挑战就是在两者之间找到一个平衡。造成堆利用率很低的主要原因是一种称为碎片(fragmentation)的现象。
碎片:虽然有未使用的存储器但不能满足分配要求时的现象。
内部碎片的数量取决于以前请求的模式和分配器的实现方式。
可计算的，可量化的。外部碎片的量化十分困难。
将来请求的模式。一个实际的分配器要在吞吐率和利用率把握平衡，必须考虑一下几个问题。
将堆组织为一个连续的已分配块和空闲块的序列。
这种结构就叫做隐式空闲链表
隐式 :
隐式链表。
指针(next)来链接起来。头部的长度隐含地链接起来。终止头部(类似与普通链表的NULL)
优点:简单缺点1:任何操作的开销都与已分配块和空闲块的总数呈线性关系O(N).
缺点2: 即使申请一个字节，也会分配2个字的块。空间浪费。有以下几种搜索放置策略：
首次适配
空闲块。下一次适配
最佳适配
空闲块，找一个满足条件的最小的空闲块(贪心)。优缺点
首次适配
优点
缺点
下一次适配
优点
缺点
最佳适配
优点
缺点
两种策略：
缺点:产生更多的内部碎片(但是如果内部碎片很少，可以接受)优点:能使得 空闲块+已分配块的数量减少
放置策略趋向于产生好的匹配中使用。
空闲块，内部碎片也很少。缺点:更多的空闲块和已分配块，搜索速度降低。优点:空间利用率更高。如果分配器不能为请求块找到合适的空闲块将发生什么?
合并相邻的空闲块。sbrk函数
最大化合并还不行的情况。空闲块
块插入链表。假碎片: 因为释放，使得某些时候会出现相邻的空闲块。
(碎片)，合并却可以(假性)，所以叫假碎片。何时合并?
立即合并
定义:块被释放时，合并所有相邻的块。缺点:对于某些请求模式，会产生抖动。推迟合并
定义: 一个稍晚的时候，再合并。
垃圾收集器(garbage collector)是一种动态存储分配器。
垃圾: 它自动释放不再需要的已分配块，这些块称为垃圾(garbage).垃圾收集(garbage collection) :自动回收堆存储的过程叫做垃圾收集。
应用显式分配堆块，但从不显式释放堆块。垃圾收集器定期识别垃圾快，并调用相应地free，将这些快放回空闲链表。垃圾收集可以追溯到John McCarthy在20世纪60年代早期在MIT开发的Lisp系统。
Java,ML,Perl和Mathematic等现代语言系统的一个重要部分。McCarthy自创的Mark&Sweep(标记&清除)算法。
malloc包的基础上，为C和C++提供垃圾收集。scanf("%d",&val)；
scanf("%d",val);
最好的情况 : 以异常中止。覆盖某个合法的读/写区域，造成奇怪的困惑的结果。堆存储器并不会初始化。
正确做法
calloc.y[i]=0;程序不检查输入串的大小就写入栈中的目标缓冲区
缓冲区溢出错误(buffer overflow bug)。gets()容易引起这样的错误fgets()限制大小。有的系统里，int和 int *都是四字节，有的则不同。
对指针的优先级用错。
忘记了指针的算术操作是以它们指向的对象的大小为单位来进行的，这种大小不一定是字节。
返回一个指针，指向栈里面一个变量的地址。但是这个变量在返回的时候已经从栈里被弹出。
栈。引用了某个已经free掉的块。在C++多态中经常容易犯这个错误。
回收垃圾。导致内存中垃圾越来越多。
重启程序，才能释放。虚拟存储器是对主存的一个抽象。
虚拟寻址的间接形式来引用主存。
虚拟地址，通过一种地址翻译硬件来转换为物理地址。
页表的内容由操作系统提供虚拟存储器提供三个功能
虚拟地址空间内容。
页
存储器管理，
简化了链接
共享数据。页表条目里添加保护位，从而简化了存储器保护。地址翻译的过程必须和系统中所有的硬件缓存的操作集合。
L1高速缓存中。
TLB的页表条目的片上高速缓存L1。现代系统通过将虚拟存储器片和磁盘上的文件片关联起来，以初始化虚拟存储器片，这个过程叫做存储器映射。
存储器映射为共享数据，创建新的进程 以及加载数据提供一种高效的机制。
mmap 手工维护虚拟地址空间区域。
malloc
两种类型。
显示分配器
C，C++隐式分配器
JAVAGC是通过不断递归访问指针来标记已分配块，在需要的时刻进行Sweep。
C，C++无法辨认指针导致无法实现完全的GC。
GC。p所指向的块书上课后练习题都有答案，就不在博客里详细写了。
A.虚拟地址0x027c
| 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
B.地址翻译
| 参数 | 值 |
|---|---|
| VPN | 0x09 |
| TLB索引 | 0x01 |
| TLB标记 | 0x02 |
| TLB命中 | No |
| 缺页 | No |
| PPN | 0x17 |
C.物理地址格式
| 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
D.物理地址引用
| 参数 | 值 |
|---|---|
| 字节偏移 | 0x0 |
| 缓存索引 | 0xF |
| 缓存标记 | 0x17 |
| 缓存命中 | No |
| 返回缓存字节 | - |
A.虚拟地址0x03a9
| 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
B.地址翻译
| 参数 | 值 |
|---|---|
| VPN | 0x0E |
| TLB索引 | 0x02 |
| TLB标记 | 0x03 |
| TLB命中 | No |
| 缺页 | No |
| PPN | 0x11 |
C.物理地址格式
| 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
D.物理地址引用
| 参数 | 值 |
|---|---|
| 字节偏移 | 0x1 |
| 缓存索引 | 0xA |
| 缓存标记 | 0x11 |
| 缓存命中 | No |
| 返回缓存字节 | - |
A.虚拟地址0x0040
| 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
B.地址翻译
| 参数 | 值 |
|---|---|
| VPN | 0x01 |
| TLB索引 | 0x01 |
| TLB标记 | 0x00 |
| TLB命中 | No |
| 缺页 | YES |
| PPN | - |
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
int main()
{
int fd;
char *start;
fd = open("hello.txt", O_RDWR, 0); //打开文件
start = mmap(NULL, 1, PROT_WRITE, MAP_SHARED, fd, 0);
close(fd);
if(start == MAP_FAILED) return -1;//判断是否映射成功
(*start) = 'J';
munmap(start, 1);
return 0;
} 
| 请求 | 块大小 | 块头部 |
|---|---|---|
| malloc(3) | 8 | 0x9 |
| malloc(11) | 16 | 0x11 |
| malloc(20) | 24 | 0x19 |
| malloc(21) | 32 | 0x21 |
对齐要求 | 已分配块|空闲块|最小块大小|
---|---|---|---|
单字 | 头部和脚部|头部和脚部|16字节|
单字 | 头部，但是没有脚部|头部和脚部|16字节|
双字 | 头部和脚部|头部和脚部|16字节|
双字 | 头部，但是没有脚部|头部和脚部|16字节|
空闲块至少是16字节。已分配块不需要pred和succ，所以这八个字节可以装数据，加上头和脚，就是16字节，而且满足单字双字对齐。
我们需要修改find_fit函数（之前的版本在practise习题中写过，书后有答案）。
代码可以参考9.18。
为此需要先定义一个全局的cur_point指针，表示上次搜索之后指向哪个块（有效载荷首地址）。
static void *find_fit(size_t asize)
{
void *bp = cur_point;
do{
if( !GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))) )
return cur_point = bp;
bp = (GET_SIZE(HDRP(bp)) == 0) ? heap_listp : NEXT_BLKP(bp);
}while(bp != cur_point);
return NULL;
}另外，需要释放cur_point指向的指针时，它可能和前面的空闲块合并，我们应该将cur_point指向前一个空闲块首地址。在coalesce()函数中需要做如下修改：
else if (!prev_alloc && next_alloc) { /* Case 3 */
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
if(cur_point == bp) cur_point = PREV_BLKP(bp);
bp = PREV_BLKP(bp);
}
else { /* Case 4 */
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));
if(cur_point == bp) cur_point = PREV_BLKP(bp);
bp = PREV_BLKP(bp);
}
需要考虑四个问题：
初始化的时候，序言块和结尾块是怎么样的。序言块八字节8|0x11。
结尾块四字节0|0x11.
堆申请更多空间的时候（sbrk），如何更改结尾块记录最后一个块的alloc。
结尾块向后延伸申请的空间，并将刚多出的空间作为一个空闲块。设置为size|(alloc<<1)。再合并该空闲块。这里如何合并呢？需要判断最后一块是否已分配，可通过epilogue来判断。
空闲块匹配的时候，如何设置头和下一块的头。我们基于以下假设：某个空闲块匹配，上一个和下一个一定不是空闲块（否则可以合并）。
所以头部就设置为（asize|0x011)。
如果要分割，则下一块的头部设置为（size-asize|0x010），不用合并，因为再下一块肯定是已经分配。
检查头部，alloc_prev = 上一块是否分配
检查下一个块的头部，alloc_next = 下一个块是否分配。
再根据那四种情况分别设置。
最后，如果下一块已分配，则需要将下一块头部设置为(原头部&(~0x010))。
另外，在mm_malloc中，分配多大的块也要发生相应的变化，因为现在最小块大小可以是DSIZE，而不是2*DSIZE。
1) a; 对于伙伴系统，如果要申请大小为33的空间，那么需要分配64个空间。如果申请大小为65的空间，那么块大小就需要128，所以最多可能有约50%的空间被浪费。b中，最佳适配要搜索所有空间，所以肯定比首次适配要慢一些。c，边界标记主要功能是释放一个块时，能立即和前后空闲块合并。如果空闲块不按顺序排列的话，其实也能够和前一个或者后一个空闲块进行合并，但如果要和前后一起合并，可能会有些困难，那需要搜索前后块在空闲链表中的位置，并且删除一个再进行合并。可以参考P576，LIFO方法。d，其实任何分配器都可能有外部碎片，只要剩余的空闲块大小和足够但是单个都不够，就会产生外部碎片。
2) d; 块大小递增，那么最佳适配法找到的块和首次适配找到的块是同一个，因为最佳适配总是想找一个刚好大于请求块大小的空闲块。a，块大小递减，首次适配很容易找到，所以分配性能会很高。b，最佳适配方法无论怎样，都要搜索所有的链表（除非维护成块大小递增的链表）。c，是匹配的最小的。
3) c; 保守的意思就是所有可能被引用的堆都会被标记，int像指针，所以可能认为它表示的地址是正在被引用的（实际上它只是个int）。
不会……
在深入学习之前我和同伴是带着这些疑问的，学习之后通过讨论，对这些问题有了一点理解。
Linux虚拟地址空间如何分布？问题1解决：
Linux 使用虚拟地址空间，大大增加了进程的寻址空间，由低地址到高地址分别为：
rodata 段(C常量字符串和#define```定义的常量) )数据段：保存全局变量、静态变量的空间；堆 ：就是平时所说的动态内存， malloc/new 大部分都来源于此。其中堆顶的位置可通过函数 brk 和 sbrk 进行动态调整。文件映射区域 ：如动态库、共享内存等映射物理空间的内存，一般是 mmap 函数所分配的虚拟地址空间。栈：用于维护函数调用的上下文空间，一般为 8M，可通过 ulimit –s 查看。内核虚拟空间：用户代码不可见的内存区域，由内核管理(页表就存放在内核虚拟空间)。64位系统拥有2^64的地址空间吗？问题2解决：
事实上，64 位系统的虚拟地址空间划分发生了改变：
2^32，也不是2^64，而一般是2^48。因为并不需要 2^64 这么大的寻址空间，过大空间只会导致资源的浪费。64位Linux一般使用48位来表示虚拟地址空间，40位表示物理地址，这可通过 /proc/cpuinfo来查看0x0000000000000000~0x00007fffffffffff表示用户空间， 0xFFFF800000000000~ 0xFFFFFFFFFFFFFFFF表示内核空间，共提供 256TB(2^48) 的寻址空间。这两个区间的特点是，第 47 位与 48~63 位相同，若这些位为 0 表示用户空间，否则表示内核空间。由低地址到高地址仍然是只读段、数据段、堆、文件映射区域和栈；问题3解决：
用ps -o majflt,minflt -C program命令查看。
majflt代表major fault，中文名叫大错误，minflt代表minor fault，中文名叫小错误。
这两个数值表示一个进程自启动以来所发生的缺页中断的次数。
问题4解决：
当一个进程发生缺页中断的时候，进程会陷入内核态，执行以下操作：虚拟地址是否合法查找/分配一个物理页填充物理页内容（读取磁盘，或者直接置0，或者啥也不干）映射关系（虚拟地址到物理地址）重新执行发生缺页中断的那条指令
堆内碎片不能直接释放，导致疑似“内存泄露”问题，为什么 malloc不全部使用 mmap 来实现呢(mmap分配的内存可以会通过 munmap 进行 free ，实现真正释放)？而是仅仅对于大于 128k的大块内存才使用 mmap ？问题5解决：
进程向 OS 申请和释放地址空间的接口 sbrk/mmap/munmap 都是系统调用，频繁调用系统调用都比较消耗系统资源的。并且， mmap 申请的内存被 munmap 后，重新申请会产生更多的缺页中断。例如使用 mmap 分配 1M 空间，第一次调用产生了大量缺页中断 (1M/4K 次) ，当munmap 后再次分配 1M 空间，会再次产生大量缺页中断。缺页中断是内核行为，会导致内核态CPU消耗较大。另外，如果使用 mmap 分配小内存，会导致地址空间的分片更多，内核的管理负担更大。
同时堆是一个连续空间，并且堆内碎片由于没有归还 OS ，如果可重用碎片，再次访问该内存很可能不需产生任何系统调用和缺页中断，这将大大降低 CPU 的消耗。 因此， glibc 的 malloc 实现中，充分考虑了 sbrk和 mmap 行为上的差异及优缺点，默认分配大块内存 (128k) 才使用 mmap 获得地址空间，也可通过 mallopt(M_MMAP_THRESHOLD, <SIZE>)来修改这个临界值。
无
-[20155318](http://www.cnblogs.com/lxy1997/)
- 结对照片
- 结对学习内容
- 教材第九章内容
- 跟着同伴回顾了第十二章的内容
- ...通过这一章的学习，进一步加深了对虚拟存储器的了解。
（statistics.sh脚本的运行结果截图）
| 代码行数（新增/累积） | 博客量（新增/累积） | 学习时间（新增/累积） | 重要成长 | |
|---|---|---|---|---|
| 目标 | 5000行 | 30篇 | 400小时 | |
| 第一周 | 133/133 | 1/1 | 8/8 | |
| 第三周 | 159/292 | 1/3 | 10/18 | |
| 第五周 | 121/413 | 1/5 | 10/28 | |
| 第七周 | 835/3005 | 2/7 | 10/38 | |
| 第八周 | 1702/4777 | 1/8 | 10/48 | |
| 第九周 | 1664/6441 | 3/11 | 10/58 | |
| 第十一周 | 300/6741 | 3/14 | 10/68 | |
| 第十三周 | 743/7484 | 2/16 | 10/78 |
尝试一下记录「计划学习时间」和「实际学习时间」，到期末看看能不能改进自己的计划能力。这个工作学习中很重要，也很有用。
耗时估计的公式
：Y=X+X/N ，Y=X-X/N，训练次数多了，X、Y就接近了。
计划学习时间:15小时
实际学习时间:10小时
改进情况：
(有空多看看现代软件工程 课件
软件工程师能力自我评价表)
转载于:https://www.cnblogs.com/guyanlin/p/8033903.html