操作系统作业8

短命女 2021-12-24 03:17 277阅读 0赞

首先，了解线性页表大小随地址空间的增长而变化的方式：

paging-linear-translate.py -P 1k -a 1m -p 512m -v -n 0

paging-linear-translate.py -P 1k -a 2m -p 512m -v -n 0

paging-linear-translate.py -P 1k -a 4m -p 512m -v -n 0

ARG seed 0

ARG地址空间大小为1m

ARG 物理地址空间大小512m

ARG页面大小1k

ARG verbose true

高位（最左侧）位是VALID位。

paging-linear-translate.py -P 1k -a 2m -p 512m -v -n 0

继续实验：地址空间再增长：

paging-linear-translate.py -P 1k -a 4m -p 512m -v -n 0

### **第二：了解线性页表大小随页面大小增长而变化的方式：** ###

paging-linear-translate.py -P 1k -a 1m -p 512m -v -n 0

paging-linear-translate.py -P 2k -a 1m -p 512m -v -n 0

paging-linear-translate.py -P 4k -a 1m -p 512m -v -n 0

**问题：**

**Before running any of these, try to think about the expected trends. How should page-table size change as the address space grows? As the page size grows? Why shouldn’t we just use really big pages in general? **

回答：

页表大小由以下等式控制：address space size = number of page table entries \* page size和bits necesssary to address a page = log (physical memory size / page size )

页表条目的数量随地址大小线性增加，并且寻址页面所需的位数随地址大小呈对数增加：

*  \--asize=1m：1024个条目
 *  \--asize=2m：2048个条目
 *  \--asize=4m：4096个条目

页表条目的数量与页面大小的倒数成比例：页面大小加倍，条目数量减半。寻址页面所需的位数与页面大小的倒数的对数成正比关系。

*  \--pagesize=1k：1024个条目
 *  \--pagesize=2k：512个条目
 *  \--pagesize=4k：256个条目

总结：

### **随着地址空间的增长，页表大小应该如何变化？** ###

### **页表变长，因为需要更多的页面来覆盖到这个地址空间。** ###

### **随着页面大小的增长？为什么我们不应该只使用真正的大页面呢？** ###

### **页面大小减小，但是不能使用一个超级大的页面，因为会浪费很多的内存——一般进程所需要使用到的内存很少。** ###

### **第三问：现在做转换。** ###

paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 0

paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 25

前面两次尝试只有VA 0x2bc6有效。

由于地址空间为16KB，因此总共有14bits。页面大小为1kb所以后面10位保留，前面4位是页表的索引。0x2bc6的二进制数是10 1011 1100 0110，1010=10，通过查看页表得到第10个索引的0x13

剩下的是11 1100 0110，并上就是0011 1100 0110

然后并上0x2bc6

0011 1100 0110 OR 0100 1100 0000 0000 = 0x4FC6

paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 50

\-c的结果：

paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 75

\-c的结果：

paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 100

\-c的结果：

发现75和100都是全命中。

问题：What happens as you increase the percentage of pages that are allocate. What happens as you increase

### **增加在每个地址空间中分配的页面百分比时会发生什么** ###

随着在每个地址空间中分配的页面百分比的增加，触发页面错误的随机虚拟地址的百分比会按比例减少，但是空闲空间也减少。

paging-linear-translate.py -P 8 -a 32 -p 1024 -v -s 1

paging-linear-translate.py -P 8k -a 32k -p 1m -v -s 2

paging-linear-translate.py -P 1m -a 256m -p 512m -v -s 3

**问题：Which of these parameter combinations are unrealistic? Why? **

第一组，size太小了，每个页表必须包含128个条目，这些条目不可能适合32位地址空间

第二组每个只会产生4个页面处理。由于内部碎片，这可能会浪费大量空间

OK：第三组每个页表由256个条目组成，每个条目处理一个物理页面

**问题：Use the program to try out some other problems. Can you find the **

**limits of where the program doesn’t work anymore? For example, **

**what happens if the address-space size is *bigger*than physical memory? **

if the address-space size is bigger than physical memory，那么他就不会在工作了

如果虚拟地址空间更小，虚拟地址空间有足够的空间来引用物理地址空间中的所有内容嘛？

它有没有足够的空间根本不是问题。虚拟地址空间不需要覆盖所有物理内存。

而且我查阅了资料，其实在大多数计算机上几乎都不会发生这种情况。虚拟内存的目的是隔离每个进程的内存，并不是创造一个足够大的空间。

那什么情况是program不能再work的呢？

page size比address-space大

address space size 比physical memory大

physical memory size不能整除page size.

这个我试了。

address space不能整除page size

page size是负数

physical memory 是负数

address space是负数

这个作业思路是：多级page table用来解决page table体积过大的问题。

它的解决思路：将page table切割成page size大小的单元，如果一个单元内的page table项都是invalid(未使用）,那么就不存储它（不使用内存空间）。同时使用一个page directory的结构来保存有数据的page table段的PFN信息。一般来说进程不可能使用整个内存空间而是其很小一部分，所以这将大大地减小page table的体积。但是这也同意意味着在page table之外又加了一层对应关系，如果TLB miss使用page table寻址时会造成额外的开销。

*  **With a linear page table, you need a single register to locate the page table, assuming that hardware does the lookup upon a TLB miss. How many registers do you need to locate a two-level page table? A three-level table? **

一个，只需要记录跟页目录的位置就行了。

*  **Use the simulator to perform translations given random seeds 0, 1, and 2, and check your answers using the -c flag. How many memory references are needed to perform each lookup?**

Readme给定了py文件的默认格式：

\- The page size is an unrealistically-small 32 bytes

\- The virtual address space for the process in question (assume there isonly one) is 1024 pages, or 32 KB

\- physical memory consists of 128 pages

因此，虚拟地址需要15位（偏移量为5，VPN为10位）。

物理地址需要12位（5偏移，PFN为7）。

611c - > 11000（= 24）01000（= 8）11100（= 28） 110 0001 0001 1100

看108行

第24个：a1

PDE：a1 - > PFN 0010 0001（= 33）

PTE：b5 - > PFN 0011 0101（= 53）

Value=08

3次内存引用

3da8 - > 0 01111（= 15）01101（= 13）01000（= 8）

PDE：d6 - > PFN 0101 0110（= 86）

PTE：7f - >无效地址

两次内存引用

17f5 - > 0 00101（= 5）11111（= 31）10101（= 21）

PDE：d4 - > PFN 0101 0100（= 84）

PTE：ce - > PFN 0100 1110（= 78）

Value=1c

三次内存引用

7f6c - > 0 11111（= 31）11011（= 27）01100（= 12）

PDE：ff - > PFN 0111 1111（= 127）

PTE：7f - >无效地址

两次调用

0bad - > 0 00010（= 2）11101（= 29）01101（= 13）

PDE：fe - > PFN 0111 1110（= 126）

PTE：7f - >无效地址

两次调用

以上是seed=0的情况；

Seed=1:

6c74 - > 11011（= 27）00011（= 3）10100（= 20）

PDE：32

PTE：97

Value=06

三次调用

6b22 - > 11010（= 26）11001（= 25）00010（= 18）

PDE：82

PTE：71

Value=1a

三次调用

03df - > 00000（= 0）11110（= 30）11111（= 31）

PDE：90

PTE：5

Value=0f

三次调用

69dc - > 11010（= 0）01110（= 30）11100（= 31）

PDE：82

PTE：无效

两次调用

317a - > 01100（= 12）01011（= 11）11010（= 18）

PDE：24

PTE：53

Value=1e

三次调用

Seed=2

7570 - > 11101（= 29）01011（= 11）10000（= 16）

PDE：51

PTE：127

无效

7268 - > 11100（= 28）10011（= 19）01000（= 8）

PDE：94

PTE：101

Value=16

1f9f - > 00111（= 7）11100（= 28）11111（= 31）

PDE：47

PTE：127

无效

0325 - > 00000（= 0）11001（= 25）00101（= 8）

PDE：2

PTE：93

Value=0b

64c4 - > 11001（= 25）00110（= 6）10100（= 20）

PDE：56

PTE：127

无效

*  **Given your understanding of how cache memory works, how do you think memory references to the page table will behave in the cache? Will they lead to lots of cache hits (and thus fast accesses?) Or lots of misses (and thus slow accesses)? **

维基百科上写：现代x86处理器可以具有4路到16路缓存关联性，两级TLB，具有4way关联性，伪LRU缓存和TLB驱逐(就是eviction)策略。

那么假设没有TLB，Cache完全关联cache行eviction LRU，忽略除最后一级缓存之外的所有缓存，无法使用虚拟地址寻址缓存：首先需要解析为物理地址，这样的情况下，每一次内存引用是紧跟着页表的引用（或者多级页表）。如果高速缓存cache eviction LRU，则最多只保留一个高速缓存行的数据而高速缓存cache中没有相应的page table cache 行。

现在假设还有一个TLB，并且TLB命中不会用来计算eviction

在某些情况下，数据可能位于缓存中，但地址转换已被换下cache和TLB。

举个例子：如果在命中TLB时重复读取cache，那么cache行将更新但translation的cache将不更新，也就是过时了，并且可能被逐出eviction。在不同页面上进行几百次内存访问，然后再次读取原始数据，可能会遇到这种情况：从RAM读取的页表，同时数据在cache里面。

将TLB 的覆盖定义为TLB条目寻址的所有页面大小的总和。

1.  cache> TLB覆盖范围：超出TLB覆盖范围的缓存肯定一直会使TLB未命中（无论TLB缓存效率咋样）。然而，相应的页表行也可能在高速缓存中。
2.  cache<TLB覆盖范围：内存访问中具有高局部性的进程可能仅使用TLB条目就可以了，而不会导致TLB未命中，这个时候此过程的瓶颈是缓存大小，而不是TLB。