CSAPP-Virtural Memory

虚拟内存

为每个进程提供了一个大的，一致的和私有的地址空间。

1.把主存看成是一个存储在磁盘上的地址空间的高速缓存

2.为每个进程提供了一致的地址空间，简化了内存管理

3.保护每个进程的地址空间不被其他进程破坏

早期分页方式的概念

大白话：程序是在逻辑空间上写的，而是在物理空间上运行，所以要解决逻辑空间与物理空间之间的映射。

就是程序可能会有2^16byte长，但是物理容量只有4K

这个区号意思就是说，地址空间0-4095对应page 1，4096-8192对应page2

区间就是页(page)，主存中存放页的区域成为页框

分页

逻辑地址 1：30 1作为地址空间索引号（页号），30作为内容

14代表页框号

所以页表就是用来映射页号和物理地址中的页框号

页框之间内容可以离散，页框内部内容连续

虚拟存储系统

大白话：程序可能很长，但是主存容量有限，于是把活跃的程序段放到主存中运行，然后自动进行切换

实质：

1.程序员在比实际主存空间大得多的逻辑地址空间中编写程序

2.程序执行的时候，要把当前需要的程序段以及相应的数据块调入主存当中，不用的部分放在磁盘上

虚拟存储技术的实质

进程调入物理主存的空间（程序中活跃的片段占用了主存的物理空间）

每个程序会有一个页表来说明它这一页的情况
（在磁盘上/内存上/空页）

cpu拿到的是虚拟地址，要求转化为主存地址，而这个过程是在执行指令的时候完成的，只能通过硬件来完成

加载一个可执行文件，执行的时候，不会实际上把数据都加载到内存当中，而是生成该程序对应的一个页表。然后按照按需调页原则，通过pageFault异常来实现，把数据装入到内存当中。

主存–磁盘

因为访问磁盘的时间会比较长，因此要尽可能减少磁盘的次数

write back 只写主存，不写磁盘

页表

用结构数组来实现

装入位->valid bit

修改位->dirty bit

替换控制位->根据其使用情况，决定该page是淘汰掉还是保留
eg（LRU.LMU）

实页号->页框号

每个进程有一个页表，其中有装入位，dirty位，替换控制位，访问权限位（确定是否可读/可写）还有禁止缓存位，实页号

一个页数的项数有什么来决定？虚拟地址空间大小来决定

项数 = 虚拟地址空间大小 / 页大小

4GB/4KB = 2^20 项

每个进程的页表大小一样吗？

各个进程有相同虚拟空间，所以理论上一样。实际大小看具体实现方式，如“空洞：页面如何处理

页表分三种

逻辑地址转换为物理地址

VA：VIRTUAL ADDRESS

类比于全相连cache，地址只有两部分，高位的tag，低位的偏移量。这里也是类似，page no,表示页表索引，页表基址存放在一个寄存器当中，页表的地址 = 基址+页表索引×页框大小

PF： frame no. ，即物理页号，其加上disp偏移量就等于PA，物理地址。

V = 0时，发生缺页。

异常情况

这个时候就需要操作系统来帮忙处理

TLB（快表）

全相连中，tag = 标签号，没有组号

组相连当中，虚页号高位作为tag，低位作为组号（index）

1.从virtual page中得到虚页号，把虚页号与TLB中的tag作比较，如果valid=0 or valid = 1 but tag!=VA,then 发生缺页。

2.于是从主存的页表(慢表)开始寻找，由于页表中的表项是按照索引号排列的，所以并不需要tag号。如果V=0，还找不到，则时候就要到外存当中的磁盘找对应的表项。

3.如果找到了，可以直接从page frame中生成物理地址号，这样就不需要访问向前面部分介绍的那样，访问主存。

所以引入快表（在cache）目的就是减少主存的访问次数，提高逻辑地址与物理地址转换的速度。

最理想路径： VA->HIT1->HIT3->CPU 不用访问主存

如果发生了TLB缺失（miss1），在主存中的的页表中寻找，如果找到了就是hit2，继续送到cache里面，否则就是miss 2 ，发生page fault

如果送到cache，cache miss了，就发生miss 3，从主存那里找。

示意图

最上面那一段属于页表，中间段属于TLB，下面那一段是cache

大概过程：虚拟地址从TLB表中寻找，如果找不到就去页表找，然后映射为物理地址后，物理地址在cache中找，找不到就访问主存，从主存中找。

虚拟地址分为20位的虚拟页号，12位的页内地址

上图中由于是组相连，因此虚拟页号分为tag标记以及组索引，当v=1而且TLB标记等于标记号的时候，就找到了物理页号，然后物理页号与虚拟地址的业内地址结合起来，就找到了物理地址。然后物理地址就又分为标记号，组索引以及块内地址，于cache中寻找所要寻找的字节。

缺页处理是由操作系统来作的

如果不在页表当中，就绝对不可能再快表当中；如果页表缺失，说明信息不在主存，cache也一定不可能有！

三个都miss过程：

1.快表miss，去页表（在主存）中找，访存1次

2.页表miss，只能从磁盘中寻找，访问磁盘一次

3.cache miss，从主存当中寻找，访存第二次

一个例子

页表项数： 虚拟地址大小 / 页大小

虚拟地址中，高8位就是虚拟页号，低6位就是偏移量。

物理地址中，高6位是实页号，低6号是偏移量。

快表：

16个TLB项，4路组相连，说明TLBI是2，剩下6位就是tag位

快表中0A34数据有误，因为其VPN就是tag+set号

tag是0A,set是03，所以VPN为 00101011 就是0x2B

但是在慢表中，0x2Bvalid位是0，所以说明数据有误

cache：

一共有16行，所以CI是4，偏移量是2（主存块4B）

VPN = 0xF TLBI = 0x3 TLBT = 0x3

即在快表的第三组中找tag==3的，找到了，说明其命中，没有page fault，PPN是0D

0D = 1101

所以物理地址为（PPN+VPO）
001101010100

C0 = 00
CI = 0101
CT = 001101

在cache中找第5行，tag为001101的16位数据

B0 = 36 B1 = 72

所以要找的数据是7236(小端，高位数据在高位)

分段式虚拟存储器

分段方式很好管理，但是占的空间多，储存空间管理不好管理。

段页式存储器

练习题9.5

#include <unistd.h>
#include <sys/mman.h>
char *bufp

//fd 为open函数返回的文件描述符
void *mmap(void *start,size_t length,int prot,int flags,int fd,off_t offset)


//创建一个包含size字节的只读，私有，请求二进制0的虚拟内存区域，如果调用成功，bufp则为新区域的地址
bufp = Mmap(NULL,size,PROT_READ,MAP_PRIVATE|MAP_ANON,0,0);

用以上函数，讲一个任意大小的磁盘文件复制到stdout，文件名作为一个命令行参数传递。

#include <csapp.h>

void mmapcopy(int fd,int size){
    char *bufp;
    bufp = Mmap(NULL,size,PROT_READ,MAP_PRIVATE,fd,0);
    Write(1,bufp,size);
    return;
}


int main(int argc,char **argv){
    if(argc!=2){
        printf("usage: %s <filename>\n",argv[0]);
    }
    
    int fd;
    struct stat stat;
    fd = Open(argv[0],O_RDONLY,0);
    fstat(fd,&stat);
    mmapcopy(fd,stat.st_size);
    exit(0);
}

//文件描述符的用法
//https://blog.csdn.net/u012736748/article/details/74626145

文件描述符是一个索引，指向内核为每一个进程所维护的该进程打开文件的记录表。

删除虚拟地址

int mummap（void *start,size_t length）;

动态内存分配

usage of malloc package

可以通过诸如malloc,new等方法让程序运行的时候得到虚拟内存。动态内存分配器会管理一个虚拟内存区域，叫做堆。

分配器以块为单位来维护堆，可以进行分配或者释放。有两种类型：

1.显式分配器：应用分配并且回收空间（malloc & free）
2.隐式分配器，只负责分配，但是不负责回收（JAVA中的垃圾收集）

过程如下：

性能指标

假设给定一个malloc和free的请求的序列目标是尽可能提高吞吐量和内存利用率。

吞吐量： 单位时间内完成的请求数量。

内存利用率：主要影响因素是内存碎片。

内部碎片

外部碎片

Peak Memory Utilization

implementation

how to free

pointer 前面用一个word记录block size

free的时候，访问指针前一个word就可以知道blocksize了

keeping track of free blocks

implicit free lists

因为每一个block是8-byte alignment的，因此最后3位必定都是0，所以可以利用最后一位来存储该块是否已经分配

example

Finding a free block

这里的 p & -2 -> p & 1111111…110 即得到block的size ，i.e mask out the last bit

allocating in free block

freeing a block

Coalescing

next pointer points to where 2 stores

如果2开头的block是空的，那么 p = p +*next

意思就是说4 = 4+2 = 6

Explicit Free Lists

一些区别

explicit empty list & implicit empty list

隐式的话，分配时间是块总数线性时间，而显式的话，是空闲块数量的线性时间，一般来说显式会比隐式更快。

first fit && next fit && best fit

首次适配：从头开始搜索空闲链表，选择第一个合适的空闲块。

下一次适配：从上一次搜索结束的位置开始搜索。

最佳适配：检索每一个空闲块，选择适合需求的最小空闲块。