1. Some terms

Explain the following terms：

• Fragmentation fault
• TLB
• Page fault
• Demand paging

Solution

Segmentation fault occurs when illegally accessing the memory block.

The following are some typical causes of a segmentation fault:

• Attempting to access a non-existent memory address (outside process’s address space)
• Attempting to access memory the program does not have rights to (such as kernel structures in process context)
• Attempting to write read-only memory (such as code segment)

These in turn are often caused by programming errors that result in invalid memory access:

• Dereferencing a null pointer, which usually points to an address that’s not part of the process’s address space
• Dereferencing or assigning to an uninitialized pointer (wild pointer, which points to a random memory address)
• Dereferencing or assigning to a freed pointer (dangling pointer, which points to memory that has been freed/deallocated/deleted)
• A buffer overflow
• A stack overflow
• Attempting to execute a program that does not compile correctly. (Some compilers will output an executable file despite the presence of compile-time errors.)

(From Wikipedia)

TLB: Translation Look-aside Buffer

The high-speed memory (some kind of cache) used to improve the conversion speed of virtual address to physical address, which stores some small page table files (conversion table from virtual address to physical address).

More specifically:

The TLB is associative, high-speed memory. Each entry in the TLB consists of two parts: a key (or tag) and a value. When the associative memory is presented with an item, the item is compared with all keys simultaneously. If the item is found, the corresponding value field is returned. The search is fast; a TLB lookup in modern hardware is part of the instruction pipeline, essentially adding no performance penalty.

Page Fault

A page fault occurs when CPU tries to access a page which is not currently in the memory or the MMU finds that a virtual involved is invalid. Through page fault, we can really allocate the physical address for a page when the process wants to access the page.

Demand paging

Page allocation is performed in a lazy manner, that is, when a process applies for memory, only a virtual address is allocated to it, and no physical memory is allocated. When a page access occurs in a process, a real physical page is allocated to it through page fault.

 
 

2. Thrashing

Introduce the concept of thrashing, and explain under what circumstance thrashing will happen.

Solution:

If a process does not have enough frames - number of frames required to support pages in active use, which causes frequent page fault ( replace a page that will be needed again right away). In this cases, a process spend more time paging than executing which is called thrashing.

Thrashing may occur when we use high degree of multiprogramming and global page replacement.

 
 

3. Memory accessing time and TLB

Consider a paging system with the page table stored in memory.

a. If a memory reference takes 50 nanoseconds, how long does a paged memory reference take?

b. If we add TLBs, and 75 percent of all page-table references are found in the TLBs, what is the effective memory reference time? (Assume that finding a page-table entry in the TLBs takes 2 nanoseconds, if the entry is present.)

Solution

a.

100 ns : 50 ns for accessing page table , 50 ns for accessing the target data in the memory.

b.

$$time_{avg}=0.75*(50ns+2ns)+0.25*(2ns+50ns+50ns)=64.5ns$$

 
 

4. TLB Hit Scenario

Assume a program has just referenced an address in virtual memory. Describe a scenario how each of the following can occur: (If a scenario cannot occur, explain why.)

• TLB miss with no page fault
• TLB miss and page fault
• TLB hit and no page fault
• TLB hit and page fault

Solution

• TLB miss with no page fault

  The page is in the memory and the page table entry is not cached in the TLB

• TLB miss and page fault

  The page is not in the memory and the page table entry is not cached in the TLB

• TLB hit and no page fault

  The page is in the memory and the page table entry is also cached in the TLB

• TLB hit and page fault

  It won’t happen. If TLB hit happens , it means the page table entry is in TLB which suggests that the page must be in the memory.

 
 

5. TLB Hit and Page Replacement

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?

Solution

Assume that the page fault rate is p, then we can easily derive the following inequality:

$$(1-p)*100 nsec+0.3*p*8 msec+0.7*p*20 msec \le 200 nsec\\Approximately： p<=6.09756*10^{-6}$$

The max rate is about p= 6.09*10^-6

 
 

6. Page Replacement Algorithm

Consider the following page reference string: 7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1. Assuming demand paging with three frames, how many page faults would occur for the following replacement algorithms?

• LRU replacement
• FIFO replacement
• Optimal replacement

Solution

• LRU replacement ：18 page faults
• FIFO replacement ： 17 page faults
• Optimal replacement ：13 page faults