---
# System prepended metadata

title: 'Final chp 9,10'
tags: [EXAM]

---

# Final chp 9,10


###### tags: `EXAM`



## Page




## Segment table


### 2017

![](https://i.imgur.com/R6HMZL0.png =60%x)

1. What are the physical addresses for the following logical addresses?

a. 0,430 
b. 1,10
c. 2,500
d. 3,400 
e. 4,112


$ans$
:::info
<font color=#000>

a. 219+430=649
b. 2300+10=2310
c. illegal reference, trap to operating system
d. 1327+400=1727
e. illegal refernce, trap to operating system
</font>
:::



## Page-replacement algorithm

### 2017

2. Suppose that there are 4 frames. How many page faults are incurred when considering the reference string by each of the following algorithms?

1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2

(a) FIFO  <font color=#f00>13</font>
![](https://i.imgur.com/5McgWcl.png =80%x)


(b) LRU   <font color=#f00> 13</font>
![](https://i.imgur.com/UBn5SmC.png =80%x)


\(c\) The optimal policy  <font color=#f00>11</font>
![](https://i.imgur.com/WmekWMh.png =80%x)

### 2018

10. Consider a page reference string as follows:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
How many page faults would occur for the following page replacement algorithms assuming demand paging with four frames?


a. FIFO replacement.
![](https://i.imgur.com/aaSzGnL.png)


b. Optimal replacement.
![](https://i.imgur.com/XitVH83.png)


c. LRU replacement.
![](https://i.imgur.com/YqV9u25.png)



## virtual memory

### 2017
3. What is the benefit of using sparse addresses in virtual memory ?

$ans$
:::info
<font color=#000>
Virtual address spaces that include holes between the heap and stack are known as sparse address spaces. Using a sparse address space is beneficial because the holes can be filled as the stack or heap segments grow, or when we wish to dynamically link libraries (or possibly other shared objects) during program execution.
</font>
:::

### 2018

8. Which of the following statements are correct for virtual-memory management


(A) Virtual memory makes the task of programming much easier because the programmer no longer needs to worry about the address binding issue.
(B) The use of modify (dirty) bit is to determine whether a page reference is a
valid or invalid memory access.
<font color=#F00>\(C\)</font> When the copy-on-write technique is used, only the pages that are modified
by either process are copied; all unmodified pages can be shared by the parent
and child processes.
<font color=#F00>(D)</font> The LRU page-replacement algorithm can be thought as the optimal page-
replacement one looking backward in time.
(E) Page fault rate will always decrease as the number of allocated frames
increase, which are known as Belady’s Anomaly.


## illegal page addresses

### 2017
4. How are illegal page addresses recognized and trapped by the operating system


$ans$
:::info
<font color=#000>
Illegal addresses are trapped by the use of a valid-invalid bit, which is generally attached to each entry in the page table. When this bit is set to "valid," the associated page is in the process's logical address space and is thus a legal (or valid) page. When the bit is set to "invalid," the page is not in the process's logical address space. The operating system sets this bit for each page to allow or disallow access to the page.
</font>
:::



## Effective Access Time (EAT)

### 2017
6. Please explain the meaning of Effective Access Time (EAT)? And please calculate the EAT of the following 1-level paging system. Ignore the overheads to revise the TLB and the page table, and suppose that each page fault involves page replacement (considering both swap-in and swap-out overhead).

TLB hit ratio = 90%
TLB access time = 200ns
Memory access time = 100us
Page-fault ratio = 0.001%
To access a page on a disk = 15ms (including memory access time)
(You only need to list your calculation process, don’t waste your life to calculate the final result.)


:::info
<font color=#000>
EAT 指存取一個分頁資料所需的時間，除了記憶體存取時間外，也包含分頁 錯誤等處理時間。
(1) TLB hit: 90% * (200ns+100us)
(2) TLB miss and the page is in RAM: 10%*99.999%* (200ns+100us+100us)
(3) TLB miss and the page is not in RAM (1 swap-out + 1 swap-in): 10%*0.001%*(200ns+100us+15ms+15ms)
EAT = (1) + (2) + (3)
</font>
:::

### 2018

7. There is a 1-level paging system running with Translation Look-aside Buffer (TLB) whose hit-rate is 90%. We have known that memory access takes 100ns and TLB search takes 10ns. Please calculate the effective memory-access time in this system. 


$ans$
:::info
<font color=#000>
0.9*(10+100) + 0.1*(10+100+100) = 120 (ns)
</font>
:::

## Segmentation $v.s.$ Paging

## 2017 

7. Briefly describe the segmentation memory management scheme. How does it differ from the paging memory management scheme in terms of the user's view of memory?


$ans$
:::info 
<font color=#000>

Segmentation views a logical address as a collection of segments. Each segment has a name and length. The addresses specify both the segment name and the offset within the segment. The user therefore specifies each address by two quantities: a segment name and an offset. In contrast, in a paging scheme, the user specifies a single address, which is partitioned by the hardware into a page number and an offset, all invisible to the programmer.

</font>
:::


## Internal and external fragmentation

8. Distinguish between internal and external fragmentation.

$ans$
:::info 
<font color=#000>

Fragmentation occurs when memory is allocated and returned to the system. As this occurs, free memory is broken up into small chunks, often too small to be useful. External fragmentation occurs when there is sufficient total free memory to satisfy a memory request, yet the memory is not contiguous, so it cannot be assigned. Some contiguous allocation schemes may assign a process more memory than it actually requested (i.e. they may assign memory in fixed-block sizes). Internal fragmentation occurs when a process is assigned more memory than it has requested and the wasted memory fragment is internal to a process.

</font>
:::