*** 作系统15-22章课后答案

第15章——地址转换 15.1

用种子1、2 和3 运行，并计算进程生成的每个虚拟地址是处于界限内还是界限外?如果在界限内，请计算地址转换。

有效地址为

VA 1: 0x00000105 (decimal: 261)

转换后地址为 PA：0x00000105+ 0x0000363c=261+13384= 13645

//种子1
python2 relocation.py -s 1

ARG seed 1
ARG address space size 1k
ARG phys mem size 16k

Base-and-Bounds register information:

  Base   : 0x0000363c (decimal 13884)
  Limit  : 290

Virtual Address Trace
  VA  0: 0x0000030e (decimal:  782) --> PA or segmentation violation?
  VA  1: 0x00000105 (decimal:  261) --> PA or segmentation violation?
  VA  2: 0x000001fb (decimal:  507) --> PA or segmentation violation?
  VA  3: 0x000001cc (decimal:  460) --> PA or segmentation violation?
  VA  4: 0x0000029b (decimal:  667) --> PA or segmentation violation?

种子 -s 2

以下地址有效

VA 0: 0x00000039 (decimal: 57)

VA 1: 0x00000056 (decimal: 86)

转换后地址

PA 0 :0x00000039 + 0x00003ca9 =57+15529=15586

PA 1:0x00000056 + 0x00003ca9=86+15529=15615

nnilk@nnilk-VirtualBox:~/文档/ostep-homework/vm-mechanism$ python2 relocation.py -s 2

ARG seed 2
ARG address space size 1k
ARG phys mem size 16k

Base-and-Bounds register information:

  Base   : 0x00003ca9 (decimal 15529)
  Limit  : 500

Virtual Address Trace
  VA  0: 0x00000039 (decimal:   57) --> PA or segmentation violation?
  VA  1: 0x00000056 (decimal:   86) --> PA or segmentation violation?
  VA  2: 0x00000357 (decimal:  855) --> PA or segmentation violation?
  VA  3: 0x000002f1 (decimal:  753) --> PA or segmentation violation?
  VA  4: 0x000002ad (decimal:  685) --> PA or segmentation violation?

种子 -s 3

以下地址有效

VA 3: 0x00000043 (decimal: 67)

VA 4: 0x0000000d (decimal: 13)

转换后地址

PA 3: 0x00000043 + 0x00003ca9 =67+8916=8983

PA 4: 0x0000000d + 0x00003ca9=13+8916=8929

nnilk@nnilk-VirtualBox:~/文档/ostep-homework/vm-mechanism$ python2 relocation.py -s 3

ARG seed 3
ARG address space size 1k
ARG phys mem size 16k

Base-and-Bounds register information:

  Base   : 0x000022d4 (decimal 8916)
  Limit  : 316

Virtual Address Trace
  VA  0: 0x0000017a (decimal:  378) --> PA or segmentation violation?
  VA  1: 0x0000026a (decimal:  618) --> PA or segmentation violation?
  VA  2: 0x00000280 (decimal:  640) --> PA or segmentation violation?
  VA  3: 0x00000043 (decimal:   67) --> PA or segmentation violation?
  VA  4: 0x0000000d (decimal:   13) --> PA or segmentation violation?

15.3

使用以下标志运行:-s1-n10-1100。可以设置基址寄存器界限的最大值是多少,以便地址空间仍然完全放在物理内存中?

物理内存大小为2¹⁴ B,要是地址完全放在物理内存中,基址寄存器最大值为 2¹⁴ - 100 = 16284

nnilk@nnilk-VirtualBox:~/文档/ostep-homework/vm-mechanism$ python2 relocation.py -s 1 -n 10 -l 100

ARG seed 1
ARG address space size 1k
ARG phys mem size 16k

Base-and-Bounds register information:

  Base   : 0x00000899 (decimal 2201)
  Limit  : 100

Virtual Address Trace
  VA  0: 0x00000363 (decimal:  867) --> PA or segmentation violation?
  VA  1: 0x0000030e (decimal:  782) --> PA or segmentation violation?
  VA  2: 0x00000105 (decimal:  261) --> PA or segmentation violation?
  VA  3: 0x000001fb (decimal:  507) --> PA or segmentation violation?
  VA  4: 0x000001cc (decimal:  460) --> PA or segmentation violation?
  VA  5: 0x0000029b (decimal:  667) --> PA or segmentation violation?
  VA  6: 0x00000327 (decimal:  807) --> PA or segmentation violation?
  VA  7: 0x00000060 (decimal:   96) --> PA or segmentation violation?
  VA  8: 0x0000001d (decimal:   29) --> PA or segmentation violation?
  VA  9: 0x00000357 (decimal:  855) --> PA or segmentation violation?

第16章——分段 16.1

1．先让我们用一个小地址空间来转换一些地址。这里有一组简单的参数和几个不同的
随机种子。你可以转换这些地址吗？
segmentation.py -a 128 -p 512 -b 0 -l 20 -B 512 -L 20 -s 0

运行结果如下，转换后每个VA所在段计算如下

VA 0: 0x0000006c (decimal: 108) --> sPA(段1)(物理地址492)
VA 1: 0x00000061 (decimal: 97) --> segmentation violation(段1)
VA 2: 0x00000035 (decimal: 53) --> segmentation violation(段0)
VA 3: 0x00000021 (decimal: 33) --> segmentation violation(段0)
VA 4: 0x00000041 (decimal: 65) --> segmentation violation(段1)

1.种子 s -0
$ python2 segmentation.py -a 128 -p 512 -b 0 -l 20 -B 512 -L 20 -s 0

ARG seed 0
ARG address space size 128
ARG phys mem size 512

Segment register information:

  Segment 0 base  (grows positive) : 0x00000000 (decimal 0)
  Segment 0 limit                  : 20

  Segment 1 base  (grows negative) : 0x00000200 (decimal 512)
  Segment 1 limit                  : 20

Virtual Address Trace
  VA  0: 0x0000006c (decimal:  108) --> PA or segmentation violation?
  VA  1: 0x00000061 (decimal:   97) --> PA or segmentation violation?
  VA  2: 0x00000035 (decimal:   53) --> PA or segmentation violation?
  VA  3: 0x00000021 (decimal:   33) --> PA or segmentation violation?
  VA  4: 0x00000041 (decimal:   65) --> PA or segmentation violation?

segmentation.py -a 128 -p 512 -b 0 -l 20 -B 512 -L 20 -s 1

运行结果如下，转换后每个VA所在段计算如下

VA 0: 0x00000011 (decimal: 17) --> PA(段0)(物理地址:17)
VA 1: 0x0000006c (decimal: 108) --> PA(段1)(物理地址:492)
VA 2: 0x00000061 (decimal: 97) --> segmentation violation(段1)
VA 3: 0x00000020 (decimal: 32) --> segmentation violation(段0)
VA 4: 0x0000003f (decimal: 63) --> segmentation violation(段0)

$ python2 segmentation.py -a 128 -p 512 -b 0 -l 20 -B 512 -L 20 -s 1
ARG seed 1
ARG address space size 128
ARG phys mem size 512

Segment register information:

  Segment 0 base  (grows positive) : 0x00000000 (decimal 0)
  Segment 0 limit                  : 20

  Segment 1 base  (grows negative) : 0x00000200 (decimal 512)
  Segment 1 limit                  : 20

Virtual Address Trace
  VA  0: 0x00000011 (decimal:   17) --> PA or segmentation violation?
  VA  1: 0x0000006c (decimal:  108) --> PA or segmentation violation?
  VA  2: 0x00000061 (decimal:   97) --> PA or segmentation violation?
  VA  3: 0x00000020 (decimal:   32) --> PA or segmentation violation?
  VA  4: 0x0000003f (decimal:   63) --> PA or segmentation violation?

segmentation.py -a 128 -p 512 -b 0 -l 20 -B 512 -L 20 -s 2

运行结果如下，转换后每个VA所在段

Virtual Address Trace：
VA 0: 0x0000007a (decimal: 122) --> PA(段1)(物理地址:506)
VA 1: 0x00000079 (decimal: 121) --> PA(段1)(物理地址:505)
VA 2: 0x00000007 (decimal: 7) --> PA(段0)(物理地址:7)
VA 3: 0x0000000a (decimal: 10) --> PA(段0)(物理地址:10)
VA 4: 0x0000006a (decimal: 106) --> segmentation violation(段1)

$ python2 segmentation.py -a 128 -p 512 -b 0 -l 20 -B 512 -L 20 -s 2
ARG seed 2
ARG address space size 128
ARG phys mem size 512

Segment register information:

  Segment 0 base  (grows positive) : 0x00000000 (decimal 0)
  Segment 0 limit                  : 20

  Segment 1 base  (grows negative) : 0x00000200 (decimal 512)
  Segment 1 limit                  : 20

Virtual Address Trace
  VA  0: 0x0000007a (decimal:  122) --> PA or segmentation violation?
  VA  1: 0x00000079 (decimal:  121) --> PA or segmentation violation?
  VA  2: 0x00000007 (decimal:    7) --> PA or segmentation violation?
  VA  3: 0x0000000a (decimal:   10) --> PA or segmentation violation?
  VA  4: 0x0000006a (decimal:  106) --> PA or segmentation violation?

16.2

现在，让我们看看是否理解了这个构建的小地址空间（使用上面问题的参数）。段0中最高的合法虚拟地址是什么？段1 中最低的合法虚拟地址是什么？在整个地址空间中，最低和最高的非法地址是什么？最后，如何运行带有-A 标志的segmentation.py 来测试你是否正确？

段0 中最高的合法虚拟地址 19,

段 1 中最低的合法虚拟地址 108

在整个地址空间中,最低和最高的非法地址是 20,107

运行python2 segmentation.py -a 128 -p 512 -b 0 -l 20 -B 512 -L 20 -s 1 -A 19,108,20,107 -c

可以看到，虚拟地址19,108分别在段0和段1中是合法地址，虚拟地址20,107分别在段0和段1中是非法地址，验证正确

$ python2 segmentation.py -a 128 -p 512 -b 0 -l 20 -B 512 -L 20 -s 1 -A 
19,108,20,107 -c
ARG seed 1
ARG address space size 128
ARG phys mem size 512

Segment register information:

  Segment 0 base  (grows positive) : 0x00000000 (decimal 0)
  Segment 0 limit                  : 20

  Segment 1 base  (grows negative) : 0x00000200 (decimal 512)
  Segment 1 limit                  : 20

Virtual Address Trace
  VA  0: 0x00000013 (decimal:   19) --> VALID in SEG0: 0x00000013 (decimal:   19)
  VA  1: 0x0000006c (decimal:  108) --> VALID in SEG1: 0x000001ec (decimal:  492)
  VA  2: 0x00000014 (decimal:   20) --> SEGMENTATION VIOLATION (SEG0)
  VA  3: 0x0000006b (decimal:  107) --> SEGMENTATION VIOLATION (SEG1)

16.3

假设我们在一个128 字节的物理内存中有一个很小的16 字节地址空间。你会设置什么样的基址和界限，以便让模拟器为指定的地址流生成以下转换结果：有效，有效，违规，违反，有效，有效？假设用以下参数：
segmentation.py -a 16 -p 128 -A 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
–b0 ? --l0 ? --b1 ? --l1 ?

注: 原书问题为:valid, valid, violation, …, violation, valid, valid,即要求 0,1,14,15 有效,其余无效

段0只有虚拟地址为0和1有效，段1只有虚拟地址14,15有效，所以

L0 = L1 = 2

Base 0 = 0

Base 1 = 15

运行python2 segmentation.py -a 16 -p 128 -A 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 --b0 0 --l0 2 --b1 15 --l1 2 -c

可以看到只有虚拟地址0,1,14,15有效，验证正确

python2 segmentation.py -a 16 -p 128 -A 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 --b0 0 --l0 2 --b1 15 --l1 2 -c
ARG seed 0
ARG address space size 16
ARG phys mem size 128

Segment register information:

  Segment 0 base  (grows positive) : 0x00000000 (decimal 0)
  Segment 0 limit                  : 2

  Segment 1 base  (grows negative) : 0x0000000f (decimal 15)
  Segment 1 limit                  : 2

Virtual Address Trace
  VA  0: 0x00000000 (decimal:    0) --> VALID in SEG0: 0x00000000 (decimal:    0)
  VA  1: 0x00000001 (decimal:    1) --> VALID in SEG0: 0x00000001 (decimal:    1)
  VA  2: 0x00000002 (decimal:    2) --> SEGMENTATION VIOLATION (SEG0)
  VA  3: 0x00000003 (decimal:    3) --> SEGMENTATION VIOLATION (SEG0)
  VA  4: 0x00000004 (decimal:    4) --> SEGMENTATION VIOLATION (SEG0)
  VA  5: 0x00000005 (decimal:    5) --> SEGMENTATION VIOLATION (SEG0)
  VA  6: 0x00000006 (decimal:    6) --> SEGMENTATION VIOLATION (SEG0)
  VA  7: 0x00000007 (decimal:    7) --> SEGMENTATION VIOLATION (SEG0)
  VA  8: 0x00000008 (decimal:    8) --> SEGMENTATION VIOLATION (SEG1)
  VA  9: 0x00000009 (decimal:    9) --> SEGMENTATION VIOLATION (SEG1)
  VA 10: 0x0000000a (decimal:   10) --> SEGMENTATION VIOLATION (SEG1)
  VA 11: 0x0000000b (decimal:   11) --> SEGMENTATION VIOLATION (SEG1)
  VA 12: 0x0000000c (decimal:   12) --> SEGMENTATION VIOLATION (SEG1)
  VA 13: 0x0000000d (decimal:   13) --> SEGMENTATION VIOLATION (SEG1)
  VA 14: 0x0000000e (decimal:   14) --> VALID in SEG1: 0x0000000d (decimal:   13)
  VA 15: 0x0000000f (decimal:   15) --> VALID in SEG1: 0x0000000e (decimal:   14)

第17章——空闲内存管理 17.1

首先运行flag -n 10 -H 0 -p BEST -s 0 来产生一些随机分配和释放。你能预测malloc()/free()会返回什么吗？你可以在每次请求后猜测空闲列表的状态吗？随着时间的推移，你对空闲列表有什么发现？

1.ptr[0] = Alloc(3)

返回ptr[0]的起始地址空间1000

空闲链表当前只有一块size=97的空闲块

2.free(ptr[0])

返回0

空闲链表当前有一块size=3和size=97的空闲块

3.ptr[1] = Alloc(5)

返回ptr[1]的起始地址空间1003

空闲链表当前有一块size=3和size=92的空闲块

4.free(ptr[1]）

返回0

空闲链表当前有一块size=3，一块size=5和size=92的空闲块

5.ptr[2] = Alloc(8)

返回ptr[2]的起始地址空间1011

空闲链表当前有三个空闲块，size1 = 3，size2 =5 ，size3 = 84

6.free(ptr[2]）

返回0

空闲链表当前有4个空闲块，size1 = 3，size2 =5 ，size3 =8，size4 = 84

7.ptr[3] = Alloc(8)

返回ptr[3]的起始地址空间1016

空闲链表当前有3个空闲块，size1 = 3，size2 =5 ，size4 =84

8.free(ptr[3]）

返回0

空闲链表当前有4个空闲块，size1 = 3，size2 =5 ，size3 =8，size4 = 84

9.ptr[4] = Alloc(2)

返回1000

空闲链表当前有4个空闲块，size1 =1，size2 =5 ，size3 =8，size4 = 84

10.ptr[5] = Alloc(7)

返回1008

空闲链表当前有4个空闲块，size1 =1，size2 =5 ，size3 =1，size4 = 84

可以看出返回malloc和free，申请释放内存，空闲内存链表的空闲块增多，内存碎片在家

运行python2 malloc.py -n 10 -H 0 -p BEST -s 0 -c，验证正确

$ python2 malloc.py -n 10 -H 0 -p BEST -s 0 -c
seed 0
size 100
baseAddr 1000
headerSize 0
alignment -1
policy BEST
listOrder ADDRSORT
coalesce False
numOps 10
range 10
percentAlloc 50
allocList 
compute True

ptr[0] = Alloc(3)  returned 1000 (searched 1 elements)
Free List [ Size 1 ]:  [ addr:1003 sz:97 ] 

Free(ptr[0]) returned 0
Free List [ Size 2 ]:  [ addr:1000 sz:3 ] [ addr:1003 sz:97 ] 

ptr[1] = Alloc(5)  returned 1003 (searched 2 elements)
Free List [ Size 2 ]:  [ addr:1000 sz:3 ] [ addr:1008 sz:92 ] 

Free(ptr[1]) returned 0
Free List [ Size 3 ]:  [ addr:1000 sz:3 ] [ addr:1003 sz:5 ] [ addr:1008 sz:92 ] 

ptr[2] = Alloc(8)  returned 1008 (searched 3 elements)
Free List [ Size 3 ]:  [ addr:1000 sz:3 ] [ addr:1003 sz:5 ] [ addr:1016 sz:84 ] 

Free(ptr[2]) returned 0
Free List [ Size 4 ]:  [ addr:1000 sz:3 ] [ addr:1003 sz:5 ] [ addr:1008 sz:8 ] [ addr:1016 sz:84 ] 

ptr[3] = Alloc(8)  returned 1008 (searched 4 elements)
Free List [ Size 3 ]:  [ addr:1000 sz:3 ] [ addr:1003 sz:5 ] [ addr:1016 sz:84 ] 

Free(ptr[3]) returned 0
Free List [ Size 4 ]:  [ addr:1000 sz:3 ] [ addr:1003 sz:5 ] [ addr:1008 sz:8 ] [ addr:1016 sz:84 ] 

ptr[4] = Alloc(2)  returned 1000 (searched 4 elements)
Free List [ Size 4 ]:  [ addr:1002 sz:1 ] [ addr:1003 sz:5 ] [ addr:1008 sz:8 ] [ addr:1016 sz:84 ] 

ptr[5] = Alloc(7)  returned 1008 (searched 4 elements)
Free List [ Size 4 ]:  [ addr:1002 sz:1 ] [ addr:1003 sz:5 ] [ addr:1015 sz:1 ] [ addr:1016 sz:84 ] 

17.3

如果使用首次匹配（-p FIRST）会如何？使用首次匹配时，什么变快了？

首次匹配（first fit）找到第一个足够大的块，将请求的空间返回给用户。，有速度优势。

运行python2 malloc.py -n 10 -H 0 -p FIRST -s 0 -c

python2 malloc.py -n 10 -H 0 -p FIRST -s 0 -c
seed 0
size 100
baseAddr 1000
headerSize 0
alignment -1
policy FIRST
listOrder ADDRSORT
coalesce False
numOps 10
range 10
percentAlloc 50
allocList 
compute True

ptr[0] = Alloc(3)  returned 1000 (searched 1 elements)
Free List [ Size 1 ]:  [ addr:1003 sz:97 ] 

Free(ptr[0]) returned 0
Free List [ Size 2 ]:  [ addr:1000 sz:3 ] [ addr:1003 sz:97 ] 

ptr[1] = Alloc(5)  returned 1003 (searched 2 elements)
Free List [ Size 2 ]:  [ addr:1000 sz:3 ] [ addr:1008 sz:92 ] 

Free(ptr[1]) returned 0
Free List [ Size 3 ]:  [ addr:1000 sz:3 ] [ addr:1003 sz:5 ] [ addr:1008 sz:92 ] 

ptr[2] = Alloc(8)  returned 1008 (searched 3 elements)
Free List [ Size 3 ]:  [ addr:1000 sz:3 ] [ addr:1003 sz:5 ] [ addr:1016 sz:84 ] 

Free(ptr[2]) returned 0
Free List [ Size 4 ]:  [ addr:1000 sz:3 ] [ addr:1003 sz:5 ] [ addr:1008 sz:8 ] [ addr:1016 sz:84 ] 

ptr[3] = Alloc(8)  returned 1008 (searched 3 elements)
Free List [ Size 3 ]:  [ addr:1000 sz:3 ] [ addr:1003 sz:5 ] [ addr:1016 sz:84 ] 

Free(ptr[3]) returned 0
Free List [ Size 4 ]:  [ addr:1000 sz:3 ] [ addr:1003 sz:5 ] [ addr:1008 sz:8 ] [ addr:1016 sz:84 ] 

ptr[4] = Alloc(2)  returned 1000 (searched 1 elements)
Free List [ Size 4 ]:  [ addr:1002 sz:1 ] [ addr:1003 sz:5 ] [ addr:1008 sz:8 ] [ addr:1016 sz:84 ] 

ptr[5] = Alloc(7)  returned 1008 (searched 3 elements)
Free List [ Size 4 ]:  [ addr:1002 sz:1 ] [ addr:1003 sz:5 ] [ addr:1015 sz:1 ] [ addr:1016 sz:84 ] 

17.4

对于上述问题，列表在保持有序时，可能会影响某些策略找到空闲位置所需的时间。使用不同的空闲列表排序（-l ADDRSORT，-l SIZESORT +，-l SIZESORT-）查看策略和列表排序如何相互影响。

对于这三种排序方式，bestfit策略的alloc运行速度都不会有变化。

按照空闲块大小递减排序worstfit和firstfit的alloc运行速度会提升。

三种排序方式在 free 时会变慢,因为插入空闲块时需要遍历空闲列表,来达成某种排序方式,

默认按照地址排序

python2 malloc.py -n 10 -H 0 -p BEST -s 0 -l ADDRSORT

按照空闲块大小递增排序:

python2 malloc.py -n 10 -H 0 -p WORST -s 0 -l SIZESORT +

按照空闲块大小递减排序，该方式会让最差适应算法搜索更快

python2 malloc.py -n 10 -H 0 -p WORST -s 0 -l SIZESORT -

第18章——分页 18.1

在做地址转换之前，让我们用模拟器来研究线性页表在给定不同参数的情况下如何改变大小。在不同参数变化时，计算线性页表的大小。一些建议输入如下，通过使用-v 标志，你可以看到填充了多少个页表项。首先，要理解线性页表大小如何随着地址空间的增长而变化：
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
然后，理解线性页面大小如何随页大小的增长而变化：
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
在运行这些命令之前，请试着想想预期的趋势。页表大小如何随地址空间的增长而改变？随着页大小的增长呢？为什么一般来说，我们不应该使用很大的页呢？

Q1：页表大小如何随地址空间的增长而改变？随着页大小的增长呢？

linear page table size=addr size /page size

所有线性页面大小随地址空间增大而增大，随页面大小增大而减小。地址空间增长，页表大小也会增长；

如，paging-linear-translate.py -P 1k -a 1m -p 512m -v -n 0，linear page table size=1m/1k=1024

Q2：为什么一般来说，我们不应该使用很大的页呢？

过大的页会造成空间浪费

18.2

现在让我们做一些地址转换。从一些小例子开始，使用-u 标志更改分配给地址空间
的页数。例如：
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
paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 50
paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 75
paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 100
如果增加每个地址空间中的页的百分比，会发生什么？

依次运行以上案例，可以发现，页表中的有效页增多

paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 0（0个有效页表项）
paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 25（5个有效页表项）
paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 50（8个有效页表项）
paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 75（15个有效页表项）
paging-linear-translate.py -P 1k -a 16k -p 32k -v -u 100（15个有效页表项）

18.3

现在让我们尝试一些不同的随机种子，以及一些不同的（有时相当疯狂的）地址空
间参数：
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
哪些参数组合是不现实的？为什么？

第三个页太大，（页面默认大小为4KB）导致太多空间被浪费

第20章——分页：较小的表 20.1

对于线性页表，你需要一个寄存器来定位页表，假设硬件在TLB 未命中时进行查找。你需要多少个寄存器才能找到两级页表？三级页表呢？

不论是二级页表还是三级页表，都只需要一个寄存器就够

20.2

使用模拟器对随机种子0、1 和2 执行翻译，并使用-c 标志检查你的答案。需要多少内存引用来执行每次查找？

分别执行命令行

python2 paging-multilevel-translate.py -s 0

python2 paging-multilevel-translate.py -s 1

python2 paging-multilevel-translate.py -s 2

从运行结果可以看出，每次都需要10次内存引用

20.3

根据你对缓存内存的工作原理的理解，你认为对页表的内存引用如何在缓存中工作？它们是否会导致大量的缓存命中（并导致快速访问）或者很多未命中（并导致访问缓慢）？

经常访问和最近访问的数据一般会放在缓存中，所以会导致大量的缓存命中。当然这也去决定于缓存的替换算法和访问的行为模式，在一些情况下可能会导致极低的命中率。

第22章——超越物理内存：策略 22.1

使用以下参数生成随机地址：-s 0 -n 10，-s 1 -n 10 和-s 2 -n 10。将策略从FIFO 更改为LRU，并将其更改为OPT。计算所述地址追踪中的每个访问是否命中或未命中。

python2 paging-policy.py -s 0 -n 10

一共10次访存，9次未命中，一次命中

Access: 8 Miss State of Memory:[8]
Access: 7 Miss State of Memory:[8,7]
Access: 4 Miss State of Memory:[8,7,4]
Access: 2 Miss State of Memory:[7,4,2]
Access: 5 Miss State of Memory:[4,2,5]
Access: 4 Hit State of Memory:[4,2,5]
Access: 7 Miss State of Memory:[2,5,7]
Access: 3 Miss State of Memory:[5,7,3]
Access: 4 Miss State of Memory:[7,3,4]
Access: 5 Miss State of Memory:[3,4,5]

Access: 8  MISS FirstIn ->          [8] <- Lastin  Replaced:- [Hits:0 Misses:1]
Access: 7  MISS FirstIn ->       [8, 7] <- Lastin  Replaced:- [Hits:0 Misses:2]
Access: 4  MISS FirstIn ->    [8, 7, 4] <- Lastin  Replaced:- [Hits:0 Misses:3]
Access: 2  MISS FirstIn ->    [7, 4, 2] <- Lastin  Replaced:8 [Hits:0 Misses:4]
Access: 5  MISS FirstIn ->    [4, 2, 5] <- Lastin  Replaced:7 [Hits:0 Misses:5]
Access: 4  HIT  FirstIn ->    [4, 2, 5] <- Lastin  Replaced:- [Hits:1 Misses:5]
Access: 7  MISS FirstIn ->    [2, 5, 7] <- Lastin  Replaced:4 [Hits:1 Misses:6]
Access: 3  MISS FirstIn ->    [5, 7, 3] <- Lastin  Replaced:2 [Hits:1 Misses:7]
Access: 4  MISS FirstIn ->    [7, 3, 4] <- Lastin  Replaced:5 [Hits:1 Misses:8]
Access: 5  MISS FirstIn ->    [3, 4, 5] <- Lastin  Replaced:7 [Hits:1 Misses:9]

FINALSTATS hits 1   misses 9   hitrate 10.00

python2 paging-policy.py -s 1 -n 10 -c

8Miss，2Hit

Access: 1 Miss State of Memory:[1]
Access: 8 Miss State of Memory:[1,8]
Access: 7 Miss State of Memory:[1,8,7]
Access: 2 Miss State of Memory:[8,7,2]
Access: 4 Miss State of Memory:[7,2,4]
Access: 4 Hit State of Memory:[7,2,4]
Access: 6 Miss State of Memory:[2,4,6]
Access: 7 Miss State of Memory:[4,6,7]
Access: 0 Miss State of Memory:[6,7,0]
Access: 0 Hit State of Memory:[6,7,0]

$ python2 paging-policy.py -s 1 -n 10 -c
ARG addresses -1
ARG addressfile 
ARG numaddrs 10
ARG policy FIFO
ARG clockbits 2
ARG cachesize 3
ARG maxpage 10
ARG seed 1
ARG notrace False

Solving...

Access: 1  MISS FirstIn ->          [1] <- Lastin  Replaced:- [Hits:0 Misses:1]
Access: 8  MISS FirstIn ->       [1, 8] <- Lastin  Replaced:- [Hits:0 Misses:2]
Access: 7  MISS FirstIn ->    [1, 8, 7] <- Lastin  Replaced:- [Hits:0 Misses:3]
Access: 2  MISS FirstIn ->    [8, 7, 2] <- Lastin  Replaced:1 [Hits:0 Misses:4]
Access: 4  MISS FirstIn ->    [7, 2, 4] <- Lastin  Replaced:8 [Hits:0 Misses:5]
Access: 4  HIT  FirstIn ->    [7, 2, 4] <- Lastin  Replaced:- [Hits:1 Misses:5]
Access: 6  MISS FirstIn ->    [2, 4, 6] <- Lastin  Replaced:7 [Hits:1 Misses:6]
Access: 7  MISS FirstIn ->    [4, 6, 7] <- Lastin  Replaced:2 [Hits:1 Misses:7]
Access: 0  MISS FirstIn ->    [6, 7, 0] <- Lastin  Replaced:4 [Hits:1 Misses:8]
Access: 0  HIT  FirstIn ->    [6, 7, 0] <- Lastin  Replaced:- [Hits:2 Misses:8]

FINALSTATS hits 2   misses 8   hitrate 20.00

python2 paging-policy.py -s 2 -n 10 -c

6Miss，4Hit

Access: 9 Miss State of Memory:[9]
Access: 9 Hit State of Memory:[9]
Access: 0 Miss State of Memory:[9,0]
Access: 0 Hit State of Memory:[9,0]
Access: 8 Miss State of Memory:[9,0,8]
Access: 7 Miss State of Memory:[0,8,7]
Access: 6 Miss State of Memory:[8,7,6]
Access: 3 Miss State of Memory:[7,6,3]
Access: 6 Hit State of Memory:[7,6,3]
Access: 6 Hit State of Memory:[7,6,3]

$ python2 paging-policy.py -s 2 -n 10 -c
ARG addresses -1
ARG addressfile 
ARG numaddrs 10
ARG policy FIFO
ARG clockbits 2
ARG cachesize 3
ARG maxpage 10
ARG seed 2
ARG notrace False

Solving...

Access: 9  MISS FirstIn ->          [9] <- Lastin  Replaced:- [Hits:0 Misses:1]
Access: 9  HIT  FirstIn ->          [9] <- Lastin  Replaced:- [Hits:1 Misses:1]
Access: 0  MISS FirstIn ->       [9, 0] <- Lastin  Replaced:- [Hits:1 Misses:2]
Access: 0  HIT  FirstIn ->       [9, 0] <- Lastin  Replaced:- [Hits:2 Misses:2]
Access: 8  MISS FirstIn ->    [9, 0, 8] <- Lastin  Replaced:- [Hits:2 Misses:3]
Access: 7  MISS FirstIn ->    [0, 8, 7] <- Lastin  Replaced:9 [Hits:2 Misses:4]
Access: 6  MISS FirstIn ->    [8, 7, 6] <- Lastin  Replaced:0 [Hits:2 Misses:5]
Access: 3  MISS FirstIn ->    [7, 6, 3] <- Lastin  Replaced:8 [Hits:2 Misses:6]
Access: 6  HIT  FirstIn ->    [7, 6, 3] <- Lastin  Replaced:- [Hits:3 Misses:6]
Access: 6  HIT  FirstIn ->    [7, 6, 3] <- Lastin  Replaced:- [Hits:4 Misses:6]

FINALSTATS hits 4   misses 6   hitrate 40.00

22.2

对于大小为5 的高速缓存，为以下每个策略生成最差情况的地址引用序列：FIFO、LRU 和MRU（最差情况下的引用序列导致尽可能多的未命中）。对于最差情况下的引用序列，需要的缓存增大多少，才能大幅提高性能，并接近OPT？

FIFO:

python2 paging-policy.py -a 1,2,3,4,5,6,7,8 -C 5

LRU:

python2 paging-policy.py -a 1,2,3,4,5,6,7,8 -C 5 -p LRU

MRU:

python2 paging-policy.py -a 1,2,3,4,5,6,7,8 -C 5 -p MRU

最差情况需要缓存增大到与页号相同

22.3

生成一个随机追踪序列（使用Python 或Perl）。你预计不同的策略在这样的追踪序列上的表现如何？

该序列在OPT策略中表现一般，在其他策略的表现都相当糟糕

❯ python2 paging-policy.py -s 0 -n 10 -c -p FIFO
FINALSTATS hits 1   misses 9   hitrate 10.00

❯ python2 paging-policy.py -s 0 -n 10 -c -p LRU
FINALSTATS hits 2   misses 8   hitrate 20.00

❯ python2 paging-policy.py -s 0 -n 10 -c -p OPT
FINALSTATS hits 4   misses 6   hitrate 40.00

❯ python2 paging-policy.py -s 0 -n 10 -c -p UNOPT
FINALSTATS hits 0   misses 10   hitrate 0.00

❯ python2 paging-policy.py -s 0 -n 10 -c -p RAND
FINALSTATS hits 0   misses 10   hitrate 0.00

❯ python2 paging-policy.py -s 0 -n 10 -c -p CLOCK
FINALSTATS hits 1   misses 9   hitrate 10.00

22.4

现在生成一些局部性追踪序列。如何能够产生这样的追踪序列？LRU 表现如何？RAND比LRU 好多少？CLOCK 表现如何？CLOCK 使用不同数量的时钟位，表现如何？

可以使用tool.py生成具有空间和时间局部性序列

#tool.py
import random
import sys

numAddr = 10
# 空间局部性
def generate_spatial_locality_trace():
    trace = [random.randint(0, numAddr)]
    for i in range(8):
        l = trace[-1]
        rand = [l, (l + 1) % numAddr, (l - 1) % numAddr, random.randint(0, numAddr)]
        trace.append(random.choice(rand))
    # 问题给的paging-policy.py -a参数里, 逗号后不能空格,因此拼接再打印
    print(','.join([str(i) for i in trace]))


# 时间局部性
def generate_temporal_locality_trace():
    trace = [random.randint(0, numAddr)]
    for i in range(8):
        rand = [random.randint(0, numAddr), random.choice(trace)]
        trace.append(random.choice(rand))
    print(','.join([str(i) for i in trace]))


if len(sys.argv) != 1:
    if sys.argv[1] == '-t':
        generate_temporal_locality_trace()
    elif sys.argv[1] == '-s':
        generate_spatial_locality_trace()

tool.py 用法

python3 tool.py -s#产生具有空间局部性序列
python3 tool.py -t#产生具有时间局部性序列

运行以下命令行，比较各个策略的表现

可以看到LRU在具有空间局部性序列的内存访问中表现更好。时间局部性序列的命中率在44%左右

Rand策略在时间局部性的策略上优于LRU策略，高了11%的命中率，然而在空间局部性序列中表现不如LRU

CLOCK bit为2时表现差于LRU，提高bit时出现好于LRU的情况，且在一定数值内（5左右）bit越高表现越好。

python2 paging-policy.py -p LRU -c -a  $(python3 tool.py -t)
>>FINALSTATS hits 4   misses 5   hitrate 44.44

python2 paging-policy.py -p LRU -c -a  $(python3 tool.py -s)
>>FINALSTATS hits 6   misses 3   hitrate 66.67


python2 paging-policy.py -p RAND -c -a  $(python3 tool.py -t)
>>FINALSTATS hits 5   misses 4   hitrate 55.56

python2 paging-policy.py -p RAND -c -a  $(python3 tool.py -s)
>>FINALSTATS hits 3   misses 6   hitrate 33.33


python2 paging-policy.py -p CLOCK -c -a  $(python3 tool.py -t)
>>FINALSTATS hits 1   misses 8   hitrate 11.11

python2 paging-policy.py -p CLOCK -c -a  $(python3 tool.py -s)
>>FINALSTATS hits 1   misses 8   hitrate 11.11