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.

0001 0001 0001 0010 0011 0100 0101 0110


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?

\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.

$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.

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 {. }$$


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?

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%

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