9.4 A certain computer provides its users with a virtual-memory space of $2^{32}$ bytes. The computer has $2^{18}$ bytes of physical memory. The virtual memory is implemented by paging, and the page size is 4096 bytes. A user process generates the virtual address 11123456. Explain how the system establishes the corresponding physical location. Distinguish between software and hardware operations.

答: 十六进制 11123456 转为二进制为

0001 0001 0001 0010 0011 0100 0101 0110

根据题意,虚拟空间用 32 bit 地址表示。而物理地址只有 $18$ bit 。页面大小表示所需 bit 为 $12$ ,则剩下 20 bit 用于编号页。即:

0001 0001 0001 0010 0011 表示页编号

0100 0101 0110 表示页内偏移

Assume we have a demand-paged memory. The page table is held in registers. It takes 8 milliseconds to service a page fault if an empty page is available or the replaced page is not modified, and 20 milliseconds if the replaced page is modified. Memory access time is 100 nanoseconds.Assume that the page to be replaced is modified 70 percent of the time. What is the maximum acceptable page-fault rate for an effective access time of no more than 200 nanoseconds?

假设页错误率为 $\lambda $。 若没有出现缺页错误,则有效访问时间等于内存访问时间。 若出现缺页错误,那么需要先进行调页,然后再访问。

$$ \left\{\begin{array}{cc} \begin{align} 200 \times 10 ^{-9} &= (1 - \lambda ) t_1 + \lambda t_2 \\ t_1 &= 100 \times 10 ^{-9} \\ t_2 &= 0.7 \cdot 20 \times 10^{-3} + 0.3 \cdot 8 \times 10^{-3} \end{align} \end{array}\right. $$

解得 $\lambda = 6.1 \times 10 ^{-6}$

$ 9.13 $ A page-replacement algorithm should minimize the number of page faults. We can do this minimization by distributing heavily used pages evenly over all of memory, rather than having them compete for a small number of page frames. We can associate with each page frame a counter of the number of pages that are associated with that frame. Then, to replace a page, we search for the page frame with the smallest counter.

简言之,要让常用页均匀分布。实现方式是各页帧计数,置换最小计数页帧。

a. Define a page-replacement algorithm using this basic idea. Specifically address the problems of

(1) what the initial value of the counters is, (2) when counters are increased, (3) when counters are decreased, and (4) how the page to be replaced is selected.

值域 [0,7] 初始值设为 7,每次查询全部递减。用到的页自增。替换值最小的。

b. How many page faults occur for your algorithm for the following reference string, for four page frames?

$$ 1,2,3,4,5,3,4,1,6,7,8,7,8,9,7,8,9,5,4,5,4,2 \text {. } $$

我使用 js 进行了模拟,代码如下:


let mylist = [1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2]

let counter = [0,0,0,0]
let myframes = [-1,-1,-1,-1]

function findMinIdx(counter) {
    let min = 256;
    let minIdx = -1;
    for (let i = 0; i < counter.length; i++) {
        const element = counter[i];
        if(element < min){
            min = element;
            minIdx = i;
        }
    }
    return minIdx
}

function printVec({counter, myframes}) {
    var buff = "i\t";
    for (let i = 0; i < counter.length; i++) {        
        buff+= i.toString() + " ";
    }
    buff += "\ncnt\t"
    for (let i = 0; i < counter.length; i++) {
        buff+= counter[i].toString() + " ";
    }
    buff += "\npage\t"
    for (let i = 0; i < myframes.length; i++) {
        buff+= myframes[i].toString() + " ";
    }
    buff +="\n"
    console.log(buff);
}

function hit({counter, myframes, page}) {
    for (let i = 0; i < counter.length; i++) {
        if(myframes[i] == page)
        {
            counter[i] != 7 && counter[i]++;
            return i;
        }
    }
    return -1;
}

function decrease({counter, exceptIdx}) {
    for (let i = 0; i < counter.length; i++) {
        if(exceptIdx != i){
            counter[i] != 0 && counter[i]--;
        }            
    }
}
let faultCounter = 0;
for (let i = 0; i < mylist.length; i++) {
    const page = mylist[i];
    console.log("search ", page);
    var hitIdx = hit({counter, myframes, page})
    // 命中则跳过
    if(hitIdx != -1){
        console.log("hit");
        decrease({counter, hitIdx})
        continue;
    }
    console.log("page fault");
    faultCounter++;
    // miss
    var minIdx = findMinIdx(counter)
    console.log('minIdx',minIdx);
    myframes[minIdx] = page;
    counter[minIdx] = 7;
    decrease({counter, minIdx})
    printVec({counter, myframes})
}

console.log("faultCounter", faultCounter);

结果如下:

PS C:\Doc\less-bug.com\util> node .\tmp.js
search  1
page fault
minIdx 0
i       0 1 2 3
cnt     6 0 0 0
page    1 -1 -1 -1

search  2
page fault
minIdx 1
i       0 1 2 3
cnt     5 6 0 0
page    1 2 -1 -1

search  3
page fault
minIdx 2
i       0 1 2 3
cnt     4 5 6 0
page    1 2 3 -1

search  4
page fault
minIdx 3
i       0 1 2 3
cnt     3 4 5 6
page    1 2 3 4

search  5
page fault
minIdx 0
i       0 1 2 3
cnt     6 3 4 5
page    5 2 3 4

search  3
hit
search  4
hit
search  1
page fault
minIdx 1
i       0 1 2 3
cnt     3 6 2 3
page    5 1 3 4

search  6
page fault
minIdx 2
i       0 1 2 3
cnt     2 5 6 2
page    5 1 6 4

search  7
page fault
minIdx 0
i       0 1 2 3
cnt     6 4 5 1
page    7 1 6 4

search  8
page fault
minIdx 3
i       0 1 2 3
cnt     5 3 4 6
page    7 1 6 8

search  7
hit
search  8
hit
search  9
page fault
minIdx 1
i       0 1 2 3
cnt     3 6 1 4
page    7 9 6 8

search  7
hit
search  8
hit
search  9
hit
search  5
page fault
minIdx 2
i       0 1 2 3
cnt     0 3 6 1
page    7 9 5 8

search  4
page fault
minIdx 0
i       0 1 2 3
cnt     6 2 5 0
page    4 9 5 8

search  5
hit
search  4
hit
search  2
page fault
minIdx 1
i       0 1 2 3
cnt     4 6 3 0
page    4 2 5 8

faultCounter 13

13 次页错误。

c. What is the minimum number of page faults for an optimal pagereplacement strategy for the reference string in part $ \mathrm{b} $ with four page frames?

如果采用最优页置换,即所选择的被淘汰页面,将是以后永不使用的,结果为 11 次未命中:

t	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
ref		1	2	3	4	5	3	4	1	6	7	8	7	8	9	7	8	9	5	4	5	4	2
f		1	2	3	4	5	5	5	5	6	7	8	8	8	9	9	9	9	9	4	4	4	2
f			1	2	3	4	4	4	4	5	5	7	7	7	8	8	8	8	8	8	8	8	8
f				1	2	3	3	3	3	4	4	5	5	5	7	7	7	7	7	7	7	7	7
f					1	1	1	1	1	1	1	4	4	4	5	5	5	5	5	5	5	5	5
hit	 	✗	✗	✗	✗	✗	✓	✓	✓	✗	✗	✗	✓	✓	✗	✓	✓	✓	✓	✗	✓	✓	✗
v						2				3	6	1			4					9			4

9.14 Consider a demand-paging system with a paging disk that has an average access and transfer time of 20 milliseconds. Addresses are translated through a page table in main memory, with an access time of 1 microsecond per memory access. Thus, each memory reference through the page table takes two accesses. To improve this time, we have added an associative memory that reduces access time to one memory reference, if the page-table entry is in the associative memory. Assume that 80 percent of the accesses are in the associative memory and that, of the remaining, 10 percent (or 2 percent of the total) cause page faults. What is the effective memory access time?

答:

  • 平均访问传输时间 20ms
  • 每次访存 1us
  • 每次页表引用访存两次
  • 使用相联存储器则是一次(占 80%)
  • 页错误占 2%

有效访问时间:0.8 * 1us + 0.1 * 2us + 0.1 * (5ms + 2us) = 0.5ms

What is the cause of thrashing? How does the system detect thrashing? Once it detects thrashing, what can the system do to eliminate this problem?

当计算机的虚拟内存资源被过度使用时会发生系统颠簸,从而导致页面调度和页面错误的持续状态。改进措施:

  1. 改进置换算法
  2. 降低并发数量
  3. 内存扩容
  4. 杀死进程

Assume there is an initial 1024 KB segment where memory is allocated using the Buddy System. Using Figure 9.27 as a guide, draw the tree illustrating how the following memory requests are allocated:

  • request 240 bytes
  • request 120 bytes
  • request 60 bytes
  • request 130 bytes

Next, modify the tree for the following releases of memory. Perform coalescing whenever possible:

  • release 240 bytes
  • release 60 bytes
  • release 120 bytes

req seg
request 240 bytes 256B
request 120 bytes 128B
request 60 bytes 64B
request 130 bytes 256B

剩余:

64B, 256B, 1K, 2K, 3K, 8K, 16K, 32K,64K, 128K, 256K, 512K

释放后剩余: 256B, 512B, 1K, 2K, 4K, 8K, 16K, 32K, 64K, 128K, 256K, 512K