OSTEP Chapter 15 回顾

这里回顾第15章，本章介绍了机制：地址转换。

书籍介绍：

• https://book.douban.com/subject/34994608/

学习资料：

• https://pages.cs.wisc.edu/~remzi/OSTEP/
• https://github.com/remzi-arpacidusseau/ostep-translations/tree/master/chinese
• https://github.com/joshuap233/Operating-Systems-Three-Easy-Pieces-NOTES

参考资料：

• https://github.com/joshuap233/Operating-Systems-Three-Easy-Pieces-NOTES/blob/main/15.%E7%AC%AC%E5%8D%81%E4%BA%94%E7%AB%A0-%E6%9C%BA%E5%88%B6:%E5%9C%B0%E5%9D%80%E8%BD%AC%E6%8D%A2/%E9%97%AE%E9%A2%98%E7%AD%94%E6%A1%88.md

第15 章 机制：地址转换

内容回顾

• 实现虚拟内存的目标

  • 高效
  • 控制
  • 提供虚拟化
  • 灵活性

• 地址转换

  • 将虚拟地址转换为数据实际存储的物理地址

• 动态重定位（dynamic relocation）/ 界限机制（base and bound）

  • 每个CPU有两个硬件寄存器：基址（base）寄存器和界限（bound）寄存器，也称为限制（limit）寄存器

  • 目的是将虚拟地址转化为物理地址

  • 基地寄存器作用：

    physical address = virtual address + base

  • 界限寄存器检查进程访问的地址是否有效

  • CPU中负责地址转换地址的部分称为内存管理单元（Memory Management Unit，MMU）

• 硬件需要提供的支持

  • 特权模式
  • 基址/界限寄存器
  • 能够转换虚拟地址并检查它是否越界
  • 修改基址/界限寄存器的特权指令
  • 注册异常处理程序的特权指令
  • 能够触发异常

• 操作系统需要提供的支持

  • 内存管理
  • 基址/界限管理
  • 异常处理

作业

1

Case 1：

λ python .\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?

For each virtual address, either write down the physical address it translates to
OR write down that it is an out-of-bounds address (a segmentation violation). For
this problem, you should assume a simple virtual address space of a given size.

计算：

VA  0: 0x0000030e (decimal:  782) --> segmentation violation
VA  1: 0x00000105 (decimal:  261) --> 14145
VA  2: 0x000001fb (decimal:  507) --> segmentation violation
VA  3: 0x000001cc (decimal:  460) --> segmentation violation
VA  4: 0x0000029b (decimal:  667) --> segmentation violation

答案：

λ python .\relocation.py -s 1 -c

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) --> SEGMENTATION VIOLATION
  VA  1: 0x00000105 (decimal:  261) --> VALID: 0x00003741 (decimal: 14145)
  VA  2: 0x000001fb (decimal:  507) --> SEGMENTATION VIOLATION
  VA  3: 0x000001cc (decimal:  460) --> SEGMENTATION VIOLATION
  VA  4: 0x0000029b (decimal:  667) --> SEGMENTATION VIOLATION

Case 2：

λ python .\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?

For each virtual address, either write down the physical address it translates to
OR write down that it is an out-of-bounds address (a segmentation violation). For
this problem, you should assume a simple virtual address space of a given size.

计算：

VA  0: 0x00000039 (decimal:   57) --> 15586
VA  1: 0x00000056 (decimal:   86) --> 15615
VA  2: 0x00000357 (decimal:  855) --> segmentation violation
VA  3: 0x000002f1 (decimal:  753) --> segmentation violation
VA  4: 0x000002ad (decimal:  685) --> segmentation violation

答案：

λ python .\relocation.py -s 2 -c

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) --> VALID: 0x00003ce2 (decimal: 15586)
  VA  1: 0x00000056 (decimal:   86) --> VALID: 0x00003cff (decimal: 15615)
  VA  2: 0x00000357 (decimal:  855) --> SEGMENTATION VIOLATION
  VA  3: 0x000002f1 (decimal:  753) --> SEGMENTATION VIOLATION
  VA  4: 0x000002ad (decimal:  685) --> SEGMENTATION VIOLATION

Case 3：

λ python .\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?

For each virtual address, either write down the physical address it translates to
OR write down that it is an out-of-bounds address (a segmentation violation). For
this problem, you should assume a simple virtual address space of a given size.

计算：

VA  0: 0x0000017a (decimal:  378) --> segmentation violation
VA  1: 0x0000026a (decimal:  618) --> segmentation violation
VA  2: 0x00000280 (decimal:  640) --> segmentation violation
VA  3: 0x00000043 (decimal:   67) --> 8983
VA  4: 0x0000000d (decimal:   13) --> 8929

答案：

λ python .\relocation.py -s 3 -c

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) --> SEGMENTATION VIOLATION
  VA  1: 0x0000026a (decimal:  618) --> SEGMENTATION VIOLATION
  VA  2: 0x00000280 (decimal:  640) --> SEGMENTATION VIOLATION
  VA  3: 0x00000043 (decimal:   67) --> VALID: 0x00002317 (decimal: 8983)
  VA  4: 0x0000000d (decimal:   13) --> VALID: 0x000022e1 (decimal: 8929)

2

翻译有点问题，问的的是base的极限位置：

• https://pages.cs.wisc.edu/~remzi/OSTEP/vm-mechanism.pdf

首先运行程序：

λ python .\relocation.py -s 0 -n 10

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

Base-and-Bounds register information:

  Base   : 0x00003082 (decimal 12418)
  Limit  : 472

Virtual Address Trace
  VA  0: 0x000001ae (decimal:  430) --> PA or segmentation violation?
  VA  1: 0x00000109 (decimal:  265) --> PA or segmentation violation?
  VA  2: 0x0000020b (decimal:  523) --> PA or segmentation violation?
  VA  3: 0x0000019e (decimal:  414) --> PA or segmentation violation?
  VA  4: 0x00000322 (decimal:  802) --> PA or segmentation violation?
  VA  5: 0x00000136 (decimal:  310) --> PA or segmentation violation?
  VA  6: 0x000001e8 (decimal:  488) --> PA or segmentation violation?
  VA  7: 0x00000255 (decimal:  597) --> PA or segmentation violation?
  VA  8: 0x000003a1 (decimal:  929) --> PA or segmentation violation?
  VA  9: 0x00000204 (decimal:  516) --> PA or segmentation violation?

For each virtual address, either write down the physical address it translates to
OR write down that it is an out-of-bounds address (a segmentation violation). For
this problem, you should assume a simple virtual address space of a given size.

由于base地址为0，所以应该设置为$929+0+1=930$。

测试1：

λ python .\relocation.py -s 0 -n 10 -l 929 -c

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

Base-and-Bounds register information:

  Base   : 0x0000360b (decimal 13835)
  Limit  : 929

Virtual Address Trace
  VA  0: 0x00000308 (decimal:  776) --> VALID: 0x00003913 (decimal: 14611)
  VA  1: 0x000001ae (decimal:  430) --> VALID: 0x000037b9 (decimal: 14265)
  VA  2: 0x00000109 (decimal:  265) --> VALID: 0x00003714 (decimal: 14100)
  VA  3: 0x0000020b (decimal:  523) --> VALID: 0x00003816 (decimal: 14358)
  VA  4: 0x0000019e (decimal:  414) --> VALID: 0x000037a9 (decimal: 14249)
  VA  5: 0x00000322 (decimal:  802) --> VALID: 0x0000392d (decimal: 14637)
  VA  6: 0x00000136 (decimal:  310) --> VALID: 0x00003741 (decimal: 14145)
  VA  7: 0x000001e8 (decimal:  488) --> VALID: 0x000037f3 (decimal: 14323)
  VA  8: 0x00000255 (decimal:  597) --> VALID: 0x00003860 (decimal: 14432)
  VA  9: 0x000003a1 (decimal:  929) --> SEGMENTATION VIOLATION

测试2：

λ python .\relocation.py -s 0 -n 10 -l 930 -c

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

Base-and-Bounds register information:

  Base   : 0x0000360b (decimal 13835)
  Limit  : 930

Virtual Address Trace
  VA  0: 0x00000308 (decimal:  776) --> VALID: 0x00003913 (decimal: 14611)
  VA  1: 0x000001ae (decimal:  430) --> VALID: 0x000037b9 (decimal: 14265)
  VA  2: 0x00000109 (decimal:  265) --> VALID: 0x00003714 (decimal: 14100)
  VA  3: 0x0000020b (decimal:  523) --> VALID: 0x00003816 (decimal: 14358)
  VA  4: 0x0000019e (decimal:  414) --> VALID: 0x000037a9 (decimal: 14249)
  VA  5: 0x00000322 (decimal:  802) --> VALID: 0x0000392d (decimal: 14637)
  VA  6: 0x00000136 (decimal:  310) --> VALID: 0x00003741 (decimal: 14145)
  VA  7: 0x000001e8 (decimal:  488) --> VALID: 0x000037f3 (decimal: 14323)
  VA  8: 0x00000255 (decimal:  597) --> VALID: 0x00003860 (decimal: 14432)
  VA  9: 0x000003a1 (decimal:  929) --> VALID: 0x000039ac (decimal: 14764)

3

运行程序：

λ python .\relocation.py -s 1 -n 10 -l 100 c

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?

For each virtual address, either write down the physical address it translates to
OR write down that it is an out-of-bounds address (a segmentation violation). For
this problem, you should assume a simple virtual address space of a given size.

约束要求为：

base + 100 < 16 * 1024
base < 16284

即结果为：

$$\text{mem size} - \text{limit}$$

4

同上。

5

参考资料：

• https://github.com/joshuap233/Operating-Systems-Three-Easy-Pieces-NOTES/blob/main/15.%E7%AC%AC%E5%8D%81%E4%BA%94%E7%AB%A0-%E6%9C%BA%E5%88%B6:%E5%9C%B0%E5%9D%80%E8%BD%AC%E6%8D%A2/%E9%97%AE%E9%A2%98%E7%AD%94%E6%A1%88.md

题意理解：

虚拟地址$x$服从$[0, l]$范围的整数均匀分布，合理的概率为

$$\frac{\min(limit+base,l) -base}{l}$$

解释：

|--------------------------|	0 ~ l
			|-----|			  base ~ base + limit
					  |--|	  base ~ l