OS Chap.7 HW

题目 1：动态分区分配算法（最坏适应）

【英文原题】

Another placement algorithm for dynamic partitioning is referred to as worst-fit. In this case, the largest free block of memory is used for bringing in a process. Discuss the pros and cons of this method compared to first-, next-, and best-fit. What is the average length of the search for worst-fit?

【中文翻译】

动态分区的另一种放置算法被称为最坏适应（worst-fit）。在这种情况下，使用最大的空闲内存块来装入进程。讨论这种方法与首次适应（first-fit）、下次适应（next-fit）和最佳适应（best-fit）相比的优缺点。最坏适应的平均搜索长度是多少？

【知识点讲解】 在动态分区内存管理中，当一个进程需要装入内存时，操作系统必须在空闲内存块列表中选择一个足够大的块。不同的选择策略会导致不同的内存碎片分布：

首次适应 (First-fit)：从头开始找，找到第一个能放下的就分配。
下次适应 (Next-fit)：从上次分配的位置继续往后找，找到第一个能放下的。
最佳适应 (Best-fit)：遍历所有空闲块，找到能放下且最小的块（即切分后剩下碎片最小的块）。
最坏适应 (Worst-fit)：遍历所有空闲块，找到能放下的最大的块。

【详尽解析与答案】

1. 优缺点比较分析 (Pros and Cons)

与“最佳适应 (Best-fit)”相比：
- 优点 (Pros)：最佳适应算法总是寻找刚好合适的小块，这会导致切分后留下大量极小、完全无法被利用的“外部碎片”。而最坏适应总是切割最大的块，因此切分后剩余的空闲块通常依然很大，仍有很大机会可以容纳其他后续进程。
- 缺点 (Cons)：最坏适应会迅速消耗掉系统中最大的连续空闲内存块。当未来有体积非常巨大的进程请求内存时，系统可能会因为缺乏足够大的单块连续内存而导致分配失败（即使系统总空闲内存足够）。
与“首次适应 (First-fit)”和“下次适应 (Next-fit)”相比：
- 优点 (Pros)：首次适应容易导致内存低地址端聚集大量小碎片；下次适应容易导致最大空闲块所在的内存末端也被碎片化。最坏适应一定程度上使得内存的分配更加均匀，避免了特定区域的碎片密集。
- 缺点 (Cons)：在查找速度上处于劣势。首次适应和下次适应通常不需要遍历整个空闲链表（找到合适的就停下），而最坏适应（如果链表未按大小排序）必须遍历完整个空闲链表才能确认哪一个块是最大的，增加了分配的计算开销。

2. 平均搜索长度 (Average length of the search)

平均搜索长度取决于操作系统内部如何维护空闲内存块的链表：

情况 A（未排序）：如果空闲块链表是按物理地址顺序排列的，那么为了找到“最大”的块，算法必须盲目地遍历整个链表中的每一个节点。假设当前有 $n$ 个空闲块，那么平均搜索长度就是 $n$ 。
情况 B（按大小降序排序）：如果操作系统在后台维护了一个按空间大小从大到小排列的空闲链表，那么最大的块永远在链表的头部。此时，找到最大块的搜索长度就是 1（即 $O(1)$ 的时间复杂度）。但代价是每次分配或释放内存时，都需要额外的时间来重新对链表进行排序。

题目 2：动态分区分配实战推演

【英文原题】 2. A dynamic partitioning scheme is being used, and the following is the memory configuration at a given point in time: (Image provided showing alternating allocated and free blocks. Shaded = allocated, White = free) The shaded areas are allocated blocks; the white areas are free blocks. The next three memory requests are for 40M, 20M, and 10M. Indicate the starting address for each of the three blocks using the following placement algorithms: a. First-fit b. Best-fit c. Next-fit. Assume the most recently added block is at the beginning of memory. d. Worst-fit

【中文翻译】 2. 当前正在使用动态分区方案，以下是特定时间点的内存配置：（图像显示分配和空闲块交替：20M 分配，20M 空闲，40M 分配，60M 空闲，20M 分配，10M 空闲，60M 分配，40M 空闲，20M 分配，30M 空闲，40M 分配，40M 空闲。阴影区域是已分配块；白色区域是空闲块。）接下来的三个内存请求分别为 40M、20M 和 10M。请使用以下放置算法指出这三个块的起始地址： a. 首次适应 (First-fit) b. 最佳适应 (Best-fit) c. 下次适应 (Next-fit)。假设最近添加的块位于内存的起始位置。 d. 最坏适应 (Worst-fit)

【知识点讲解与基础信息提取】 要准确计算起始地址，我们首先需要将图像转化为精确的数据模型。假设内存从地址 0 开始，我们将各个块的起始地址推导如下：

已分配 20M (地址 [0, 20) )
空闲块 1：20M，起始地址 20 (范围 [20, 40) )
已分配 40M (地址 [40, 80) )
空闲块 2：60M，起始地址 80 (范围 [80, 140) )
已分配 20M (地址 [140, 160) )
空闲块 3：10M，起始地址 160 (范围 [160, 170) )
已分配 60M (地址 [170, 230) )
空闲块 4：40M，起始地址 230 (范围 [230, 270) )
已分配 20M (地址 [270, 290) )
空闲块 5：30M，起始地址 290 (范围 [290, 320) )
已分配 40M (地址 [320, 360) )
空闲块 6：40M，起始地址 360 (范围 [360, 400) )

初始空闲块列表为：[20M@20], [60M@80], [10M@160], [40M@230], [30M@290], [40M@360]。请求序列：40M, 20M, 10M。

【详尽解析与答案】

a. 首次适应 (First-fit)：每次都从内存起始地址（0）开始扫描。

请求 40M：扫描 [20M@20] (太小) -> 找到 [60M@80] (满足)。
- 分配 40M，起始地址为 80。该空闲块剩余 20M，起始地址变为 120。
请求 20M：从头开始扫描。找到第一个空闲块 [20M@20] (恰好满足)。
- 分配 20M，起始地址为 20。该空闲块消耗殆尽。
请求 10M：从头开始扫描。由于原第一块已用完，遇到现在的第二块 [20M@120] (原60M剩下的部分，满足)。
- 分配 10M，起始地址为 120。

答案 a：起始地址分别为 80, 20, 120。

b. 最佳适应 (Best-fit)：每次扫描整个列表，找到满足要求且尺寸最小的空闲块。如果大小相同，通常选最前面的。

请求 40M：能满足的块有 60M, 40M, 40M。最佳选择是恰好为 40M 的块。第一个 40M 是 [40M@230]。
- 分配 40M，起始地址为 230。该空闲块消耗殆尽。
请求 20M：当前空闲列表为 [20M@20], [60M@80], [10M@160], [30M@290], [40M@360]。能满足且最小的是 20M 块，即 [20M@20]。
- 分配 20M，起始地址为 20。
请求 10M：当前空闲列表为 [60M@80], [10M@160], [30M@290], [40M@360]。能满足且最小的是 10M 块，即 [10M@160]。
- 分配 10M，起始地址为 160。

答案 b：起始地址分别为 230, 20, 160。

c. 下次适应 (Next-fit)：每次从上一次分配结束的位置继续扫描。题目提示初始扫描从内存起始位置开始。

请求 40M：从起始位置扫描。找到 [60M@80] (满足)。
- 分配 40M，起始地址为 80。剩余空闲块为 [20M@120]。下次扫描的指针停留在地址 120 处。
请求 20M：从地址 120 处继续扫描。发现紧接着的空闲块就是刚才剩下的 [20M@120] (恰好满足)。
- 分配 20M，起始地址为 120。该空闲块用完。下次扫描的指针移动到地址 140 处。
请求 10M：从地址 140 处继续扫描。找到下一个空闲块 [10M@160] (恰好满足)。
- 分配 10M，起始地址为 160。

答案 c：起始地址分别为 80, 120, 160。

d. 最坏适应 (Worst-fit)：每次扫描整个列表，找到满足要求且尺寸最大的空闲块。

请求 40M：当前最大的空闲块是 [60M@80]。
- 分配 40M，起始地址为 80。剩余空闲块变为 [20M@120]。
- 更新后的空闲块大小为：20M, 20M, 10M, 40M, 30M, 40M。
请求 20M：当前最大的空闲块是 40M（有两个，通常取第一个），即 [40M@230]。
- 分配 20M，起始地址为 230。剩余空闲块变为 [20M@250]。
- 更新后的空闲块大小为：20M, 20M, 10M, 20M, 30M, 40M。
请求 10M：当前最大的空闲块是 [40M@360]。
- 分配 10M，起始地址为 360。

答案 d：起始地址分别为 80, 230, 360。

题目 3：伙伴系统分配机制 (Buddy System)

【英文原题】 3. A 1-Mbyte block of memory is allocated using the buddy system. a. Show the results of the following sequence in a figure similar to Figure 7.6: Request 70; Request 35; Request 80; Return A; Request 60; Return B; Return D; Return C. b. Show the binary tree representation following Return B.

【中文翻译】 3. 使用伙伴系统分配一个 1-Mbyte 的内存块。 a. 用类似于图 7.6 的图形展示以下序列的结果：请求 70（设为 A）；请求 35（设为 B）；请求 80（设为 C）；返回 A；请求 60（设为 D）；返回 B；返回 D；返回 C。（单位：Kbyte） b. 展示在“返回 B”操作之后的二叉树表示。

【知识点讲解】 伙伴系统是一种折中的内存分配方式。它的核心规则是：内存块的大小必须是 $2^k$ 。

如果请求的内存大小大于块大小的一半，则分配整个块。
如果请求的内存大小小于或等于块大小的一半，则将该块对半平分为两个“伙伴 (Buddy)”。
当两个属于同一个父节点的空闲“伙伴”都被释放时，它们会立刻合并成一个更大的两倍大小的块。
单位转换：1 MByte = 1024 KBytes。我们将使用 KB 进行追踪。

【详尽解析与答案】

请求规格分析：

请求 A (70K)：需要向上取整到最接近的 $2^k$ ，即 128K。
请求 B (35K)：需要向上取整到最接近的 $2^k$ ，即 64K。
请求 C (80K)：需要 128K。
请求 D (60K)：需要 64K。

a. 序列状态跟踪 我们将使用文本结构直观展示每次操作后内存块的分布（从左至右，总和为 1024K）。

初始状态： [ 空闲: 1024K ]
请求 A (70K，需 128K)：系统将 1024 分裂为 512, 512；左 512 分裂为 256, 256；左 256 分裂为 128, 128。将 A 分配给第一个 128K。 [ A占: 128K ] | [ 空闲: 128K ] | [ 空闲: 256K ] | [ 空闲: 512K ]
请求 B (35K，需 64K)：将左侧第一个空闲的 128K 分裂为 64, 64。B 分配给第一个 64K。 [ A占: 128K ] | [ B占: 64K ] | [ 空闲: 64K ] | [ 空闲: 256K ] | [ 空闲: 512K ]
请求 C (80K，需 128K)：没有现成的 128K 空闲块，所以将 256K 块分裂为 128, 128。C 分配给第一个 128K。 [ A占: 128K ] | [ B占: 64K ] | [ 空闲: 64K ] | [ C占: 128K ] | [ 空闲: 128K ] | [ 空闲: 512K ]
返回 A： A 释放，变为 128K 空闲。由于其右侧紧邻的是被分割的两个 64K（其中一个被 B 占用），无法合并。 [ 空闲: 128K ] | [ B占: 64K ] | [ 空闲: 64K ] | [ C占: 128K ] | [ 空闲: 128K ] | [ 空闲: 512K ]
请求 D (60K，需 64K)：恰好有一个 64K 的空闲块（B 的右侧），将其分配给 D。 [ 空闲: 128K ] | [ B占: 64K ] | [ D占: 64K ] | [ C占: 128K ] | [ 空闲: 128K ] | [ 空闲: 512K ]
返回 B： B 释放，变为 64K 空闲。此时其伙伴（D 占据的 64K）并未空闲，因此不能合并。 [ 空闲: 128K ] | [ 空闲: 64K ] | [ D占: 64K ] | [ C占: 128K ] | [ 空闲: 128K ] | [ 空闲: 512K ]
返回 D： D 释放，变为 64K 空闲。此时它的伙伴（原 B 的 64K）也是空闲的，两者合并为 128K。合并后的 128K 的伙伴是最左侧的空闲 128K，两者再次合并为 256K。 [ 空闲: 256K ] | [ C占: 128K ] | [ 空闲: 128K ] | [ 空闲: 512K ]
返回 C： C 释放，变为 128K 空闲。它与右侧的空闲 128K 合并为 256K。该 256K 与最左侧的空闲 256K 合并为 512K。该 512K 与最右侧的空闲 512K 合并，恢复至整块。 [ 空闲: 1024K ]

b. “返回 B” 之后的二叉树表示 在步骤 7（返回 B）执行完毕后，内存的切分状态在二叉树结构中表现如下：（从根节点 1024K 向下分支）

text

                     [1024K]
                    /       \
            [512K]             [512K: 空闲]
           /      \
      [256K]      [256K]
      /    \      /    \
[128K:空闲] \   [C占:128K] [128K:空闲]
           / \
 [64K:空闲(原B)] [D占:64K]

题目 4：分页系统地址计算

【英文原题】 4. Consider a simple paging system with the following parameters: $2^{32}$ bytes of physical memory; page size of $2^{10}$ bytes; $2^{16}$ pages of logical address space. a. How many bits are in a logical address? b. How many bytes in a frame? c. How many bits in the physical address specify the frame? d. How many entries in the page table? e. How many bits in each page table entry? Assume each page table entry contains a valid/invalid bit.

【中文翻译】 4. 考虑一个具有以下参数的简单分页系统：物理内存为 $2^{32}$ 字节；页大小为 $2^{10}$ 字节；逻辑地址空间有 $2^{16}$ 页。 a. 逻辑地址中有多少位（bits）？ b. 一个页框（frame）中有多少字节？ c. 物理地址中有多少位用于指定页框？ d. 页表中有多少个条目（entries）？ e. 每个页表项中有多少位？假设每个页表项包含一个有效/无效位（valid/invalid bit）。

【知识点讲解】

页与页框等大：物理内存被划分为物理块（Frame，页框），逻辑内存（进程虚拟空间）被划分为逻辑页（Page）。两者的容量大小永远是严格相等的，这样才能实现无缝映射。
逻辑地址结构：逻辑地址由两部分组成：【页号位数】+【页内偏移量位数】。逻辑地址的总长度决定了进程的最大寻址空间。
物理地址结构：物理地址由两部分组成：【页框号位数】+【页内偏移量位数】。物理地址的总长度决定了系统能支持的最大物理内存。

【详尽解析与答案】

a. 逻辑地址中有多少位？

推导：逻辑空间由两部分计算得出：页面总数和每页大小。已知页面总数为 $2^{16}$ 页 $\rightarrow$ 需要 16 位来表示逻辑页号。已知页大小为 $2^{10}$ 字节 $\rightarrow$ 需要 10 位来表示页内偏移量。逻辑地址总位数 = 页号位数 + 偏移量位数 = $16 + 10 = 26$ 位。
答案 a：26 bits。

b. 一个页框中有多少字节？

推导：分页系统的核心规则是：页框（物理内存划分的块）的大小必须严格等于页（逻辑内存划分的块）的大小。题目给出页大小为 $2^{10}$ 字节。
答案 b： $2^{10}$ 字节 (或 1024 字节 / 1 KB)。

c. 物理地址中有多少位用于指定页框？

推导：物理内存总大小为 $2^{32}$ 字节。物理内存中的页框总数 = 物理内存总大小 / 页框大小 = $2^{32} / 2^{10} = 2^{22}$ 个页框。为了对这 $2^{22}$ 个单独的物理页框进行编号和寻址，我们需要 22 个二进制位。
答案 c：22 bits。

d. 页表中有多少个条目？

推导：页表的作用是记录逻辑页到物理页框的映射关系。进程有多少个逻辑页，它的页表就必须提供多少个映射条目。题目给出逻辑地址空间有 $2^{16}$ 页。
答案 d： $2^{16}$ 个条目 (即 65,536 个条目)。

e. 每个页表项中有多少位？

推导：页表项 (PTE, Page Table Entry) 的最基本功能是存储映射到的物理页框号。由 c 小题的计算结果可知，物理页框号需要 22 位来存储。题目补充要求包含 1 位的有效/无效位（Valid bit，用于判断页面当前是否已加载到真实的物理内存中）。每个页表项总位数 = 页框号位数 + 有效位 = $22 + 1 = 23$ 位。 (注：在真实的工业硬件实现中，位数通常会被向上对齐到字节的整数倍，例如 24 位即 3 字节，或者直接分配 32 位以保留用于保护权限、脏位等其他控制位。但从本题的纯理论计算角度，最严谨的答案就是各必须位数的精确总和。)
答案 e：23 bits。

题目 5：分段系统地址转换

【英文原题】 5. Consider a simple segmentation system that has the following segment table:

Starting Address	Length (bytes)
660	248
1752	422
222	198
996	604

For each of the following logical addresses, determine the physical address or indicate if a segment fault occurs: a. 0, 198 b. 2, 156 c. 1, 530 d. 3, 444 e. 0, 222

【中文翻译】 5. 考虑一个具有以下段表的简单分段系统：

起始物理地址 (Base)	长度/限长 (Limit)
660	248
1752	422
222	198
996	604

对于以下每个逻辑地址（以“段号, 偏移量”格式给出），确定其对应的物理地址，或指出是否会发生段错误 (segment fault)： a. 0, 198 b. 2, 156 c. 1, 530 d. 3, 444 e. 0, 222

【知识点讲解】 在分段系统中，逻辑地址通常表示为二元组：(段号 $s$ , 段内偏移量 $d$ )。将逻辑地址转换为物理地址的标准硬件步骤如下：

查表：根据逻辑地址中的段号 $s$ ，在段表中找到对应行，提取出该段在物理内存中的起始基址 (Base) 和该段的最大允许长度 (Limit)。 (注：段表通常从 0 开始索引。题目表格从上到下的四行分别隐式对应段号 0, 1, 2, 3)
越界检查：将给定的段内偏移量 $d$ 与该段的长度 Limit 进行比较。如果 $d \ge \text{Limit}$ ，说明程序正试图访问超出本段范围的内存区域，硬件将立刻拦截此次访问并触发段错误 (Segment Fault)。
计算物理地址：如果 $d < \text{Limit}$ ，则该内存访问合法。 $\text{Physical Address} = \text{Base} + d$

【详尽解析与答案】

首先，将表格参数明确列出：

段 0：Base = 660，Limit = 248
段 1：Base = 1752，Limit = 422
段 2：Base = 222，Limit = 198
段 3：Base = 996，Limit = 604

逐题推演：

a. 逻辑地址 (0, 198)

提取参数：段号 $s = 0$ $\rightarrow$ Base = 660, Limit = 248。
偏移量： $d = 198$ 。
越界检查： $198 < 248$ ，属于合法访问。
物理地址 = $Base + d = 660 + 198 = 858$ 。
答案 a：物理地址为 858。

b. 逻辑地址 (2, 156)

提取参数：段号 $s = 2$ $\rightarrow$ Base = 222, Limit = 198。
偏移量： $d = 156$ 。
越界检查： $156 < 198$ ，属于合法访问。
物理地址 = $Base + d = 222 + 156 = 378$ 。
答案 b：物理地址为 378。

c. 逻辑地址 (1, 530)

提取参数：段号 $s = 1$ $\rightarrow$ Base = 1752, Limit = 422。
偏移量： $d = 530$ 。
越界检查： $530 \ge 422$ 。请求的偏移量超出了段 1 的合法长度边界，这是典型的内存越界违规。
答案 c：发生段错误 (Segment fault)。

d. 逻辑地址 (3, 444)

提取参数：段号 $s = 3$ $\rightarrow$ Base = 996, Limit = 604。
偏移量： $d = 444$ 。
越界检查： $444 < 604$ ，属于合法访问。
物理地址 = $Base + d = 996 + 444 = 1440$ 。
答案 d：物理地址为 1440。

e. 逻辑地址 (0, 222)

提取参数：段号 $s = 0$ $\rightarrow$ Base = 660, Limit = 248。
偏移量： $d = 222$ 。
越界检查： $222 < 248$ ，属于合法访问。
物理地址 = $Base + d = 660 + 222 = 882$ 。
答案 e：物理地址为 882。

6. 什么是快表？它在地址转换中起什么作用？

【题目】 什么是快表？它在地址转换中起什么作用？

【解答与知识点解析】

什么是快表 (TLB, Translation Lookaside Buffer)：快表，又称转换后备缓冲器，是一种位于CPU内部的、容量小但访问速度极快的高速缓存（通常由相联存储器 Associative Memory 实现）。它专门用于存放当前进程中最常被访问的页表项（即逻辑页号到物理页框号的映射记录）。
在地址转换中的作用：在没有快表的分页系统中，每次内存访问都需要进行“两次访存”：第一次访问内存中的页表来获取物理地址，第二次才是真正访问该物理地址存取数据。快表的作用是加速地址转换，减少访存次数。当CPU给出逻辑地址时，硬件会首先在快表中并行查找对应的页号：
1. 若命中 (TLB Hit)：直接从快表中取出物理页框号，与页内偏移量拼接成物理地址，只需一次访存即可取得数据。
2. 若未命中 (TLB Miss)：再去主存中查找页表，取出页表项进行地址转换，并同时将该页表项自动更新到快表中，以便下次加速访问。

7. 简述存储管理中移动技术的优缺点。

【题目】 简述存储管理中移动技术的优缺点。

【解答与知识点解析】

概念背景：移动技术，通常也称为内存紧凑 (Compaction) 或拼接技术。在动态分区分配中，随着进程的装入和撤出，内存中会产生许多不连续的、极小而无法使用的空闲块，即“外部碎片”。移动技术就是通过在内存中移动进程的位置，把所有的进程靠紧在一起，从而将零散的空闲块拼接成一个大的连续空闲区。
优点：
1. 彻底消除外部碎片：能够将零散的小内存块聚集成一个大内存块，大大提高了主存的利用率。
2. 满足大进程的需求：当系统剩余内存总和足够，但缺乏连续空间时，通过移动技术可以腾出足够大的连续空间来装入大进程。
缺点：
1. 极大的时间与CPU开销：移动进程意味着要进行大量的数据拷贝，这会大量消耗CPU时间，影响系统性能。
2. 需要动态重定位硬件支持：进程在内存中的物理位置改变了，因此必须有硬件（如基址寄存器/重定位寄存器）支持动态地址映射。
3. 进程必须暂停：在移动某个进程期间，该进程必须处于挂起/等待状态，不能进行执行和 I/O 操作。

8. 页式和段式内存管理有什么区别？怎样才能实现共享和保护？

【题目】 页式和段式内存管理有什么区别？怎样才能实现共享和保护？

【解答与知识点解析】

页式与段式的主要区别：
1. 划分的依据与目的：
  - 页 (Page) 是信息的物理单位。分页是为了实现离散分配，解决内存碎片问题，提高内存利用率。它是系统底层管理的需要，对用户是透明的。
  - 段 (Segment) 是信息的逻辑单位（如主程序、子程序、数据区等）。分段是为了更好地满足用户编程和共享、保护的需要。它是用户可见的。
2. 大小是否固定：
  - 页的大小是固定的，由操作系统/硬件决定（如 4KB）。
  - 段的大小是可变的，取决于用户编写的程序逻辑。
3. 地址空间的维度：
  - 页式系统的逻辑地址空间是一维的。程序员只需给出一个线性地址，硬件自动将其拆分为页号和偏移量。
  - 段式系统的逻辑地址空间是二维的。程序员（或编译器）必须显式提供“段号”和“段内偏移量”。
4. 碎片问题：分页会产生内部碎片（最后一页装不满），没有外部碎片；分段会产生外部碎片（段之间留有空隙），没有内部碎片。
如何实现共享和保护：
- 共享：
  - 页式：让不同进程的页表项指向同一个物理页框号。
  - 段式：让不同进程的段表项指向同一个物理段的基址。分段更容易实现共享，因为段是逻辑完整的单元（比如一段纯代码），共享一个代码段非常自然。
- 保护：
  - 无论页式还是段式，都可以通过在页表项或段表项中设置保护控制位（如只读、可读写、可执行等标志位）来实现。当进行地址转换时，硬件会自动检查这些位，若操作非法（如试图写入只读代码段或越界访问），则触发越权中断。

9. 虚地址与物理地址的页表计算

【题目】 一台机器有48位虚地址和32位物理地址，若页长为8KB，问页表共有多少个页表项?如果设计一个反置页表，则有多少个页表项?

【解答与知识点解析】

基础参数解析：
- 虚拟地址 (VA) = $48$ 位。
- 物理地址 (PA) = $32$ 位。
- 页长 (Page Size) = $8\text{KB} = 2^{13}$ 字节 $\rightarrow$ 页内偏移量占用 13 位。
计算常规页表的页表项数量：常规页表的大小取决于虚拟页号 (VPN) 的位数。虚拟页号位数 = 虚拟地址位数 - 页内偏移位数 = $48 - 13 = 35$ 位。因此，常规页表共有 $2^{35}$ 个页表项。
计算反置页表 (Inverted Page Table) 的页表项数量：反置页表的核心思想是：不为每个虚拟页建表，而是为物理内存的每个页框 (Frame) 建表。物理页框号 (PFN) 位数 = 物理地址位数 - 页内偏移位数 = $32 - 13 = 19$ 位。因此，系统中实际存在的物理页框总数为 $2^{19}$ 个，反置页表共有 $2^{19}$ 个页表项。

10. 二级页表的逻辑地址计算

【题目】 一个32位地址的计算机系统使用二级页表，虚地址被分为9位顶级页表，11位二级页表和偏移。试问：页面长度是多少？虚地址空间共有多少个页面？

【解答与知识点解析】

逻辑地址结构解析：在 32 位虚地址系统中，逻辑地址被划分为三部分：[ 顶级页表号 | 二级页表号 | 页内偏移量 ]。已知：总长 = 32 位，顶级页表 = 9 位，二级页表 = 11 位。
计算页面长度：页内偏移量的位数 = 总位数 - (顶级页表位数 + 二级页表位数) 偏移量位数 = $32 - (9 + 11) = 32 - 20 = 12$ 位。页面长度取决于页内偏移量，因此页面长度 = $2^{12}$ 字节 = 4 KB。
计算虚地址空间共有多少个页面：决定页面总数的是表示“页号”的所有位数的总和。总页号位数 = 顶级页表位数 + 二级页表位数 = $9 + 11 = 20$ 位。虚地址空间的总页面数 = $2^{20}$ 个 = 1M (1,048,576) 个页面。

11. 快表命中率计算

【题目】 一台计算机的内存空间为1024个页面，页表放在内存中，从页表中读一个字的开销是500ns。为了减少开销，使用了有32个字的快表，查找速度为100ns。要把平均开销降到200ns需要的快表命中率是多少?

【解答与知识点解析】

参数梳理：这里所说的“开销”特指地址转换过程的耗时。
- $t_{TLB}$ = 访问快表的时间 = $100\text{ns}$ 。
- $t_{PT}$ = 访问内存中页表的时间 = $500\text{ns}$ 。
- 目标平均地址转换开销 $E_{trans}$ = $200\text{ns}$ 。
- 设所需的快表命中率为 $H$ 。
公式构建与计算：通常在没有明确说明“并行查找”的情况下，地址转换是顺序进行的。
1. 若命中快表 (概率 $H$ )：只需查快表，时间开销为 $100\text{ns}$ 。
2. 若未命中快表 (概率 $1 - H$ )：先查快表失败耗费 $100\text{ns}$ ，然后再去主存查页表耗费 $500\text{ns}$ ，总开销为 $100 + 500 = 600\text{ns}$ 。
平均开销公式如下：
$E_{trans} = H \times 100 + (1 - H) \times (100 + 500) = 200$
$100H + 600 - 600H = 200$
$600 - 500H = 200$
$500H = 400$
$H = \frac{400}{500} = 0.8 = 80\%$
答案：需要的快表命中率是 80%。

12. 位示图 (Bitmap) 分配主存空间计算

【题目】 现有一台16位字长的专用机，采用页式存储管理。主存储器共有4096块(块号为0～4095)，现用位示图分配主存空间。试问： (1)该位示图占用几个字?
(2)主存块号3999对应位示图的字号和位号(均从0开始)各是多少? (3)位示图字号199，位号9对应主存的块号是多少?

【解答与知识点解析】

概念背景：位示图 (Bitmap) 使用二进制的一位 (1 bit) 来表示主存中一个物理块的分配状态（如 0 表示空闲，1 表示已分配）。
- 字长：16 位（即 1 个字 = 16 bit）。
- 块数：4096 块，因此总共需要 4096 个二进制位。

（1）该位示图占用几个字？

计算：位示图所需的总字数 = 总物理块数 $\div$ 机器字长。总字数 = $4096 \div 16 = 256$ 个字。
答案：该位示图占用 256 个字。

（2）主存块号3999对应位示图的字号和位号(均从0开始)各是多少？

计算：因为字号和位号均从 0 开始，块号 $b$ 与字号 $i$ 、位号 $j$ 的关系为：字号 $i = \lfloor b \div 16 \rfloor$ 位号 $j = b \bmod 16$
代入块号 $b = 3999$ ：字号 $i = \lfloor 3999 \div 16 \rfloor = 249$ 位号 $j = 3999 \bmod 16 = 15$
答案：对应的字号是 249，位号是 15。

（3）位示图字号199，位号9对应主存的块号是多少？

计算：这是第 (2) 问的逆运算。块号 $b = i \times \text{机器字长} + j$
代入字号 $i = 199$ ，位号 $j = 9$ ：块号 $b = 199 \times 16 + 9 = 3184 + 9 = 3193$
答案：对应主存的块号是 3193。

OS Chap.7 HW ​

题目 1：动态分区分配算法（最坏适应） ​

题目 2：动态分区分配实战推演 ​

题目 3：伙伴系统分配机制 (Buddy System) ​

题目 4：分页系统地址计算 ​

题目 5：分段系统地址转换 ​

6. 什么是快表？它在地址转换中起什么作用？ ​

7. 简述存储管理中移动技术的优缺点。 ​

8. 页式和段式内存管理有什么区别？怎样才能实现共享和保护？ ​

9. 虚地址与物理地址的页表计算 ​

10. 二级页表的逻辑地址计算 ​

11. 快表命中率计算 ​

12. 位示图 (Bitmap) 分配主存空间计算 ​

OS Chap.7 HW

题目 1：动态分区分配算法（最坏适应）

题目 2：动态分区分配实战推演

题目 3：伙伴系统分配机制 (Buddy System)

题目 4：分页系统地址计算

题目 5：分段系统地址转换

6. 什么是快表？它在地址转换中起什么作用？

7. 简述存储管理中移动技术的优缺点。

8. 页式和段式内存管理有什么区别？怎样才能实现共享和保护？

9. 虚地址与物理地址的页表计算

10. 二级页表的逻辑地址计算

11. 快表命中率计算

12. 位示图 (Bitmap) 分配主存空间计算