Operating systems

Question 1. Consider a system that translates virtual addresses to physical addresses using hierarchical page tables. Every page table page comprises 1024 entries, with each entry having a size of 8 bytes. The size of both the virtual and the physical address spaces is 8 TiB. The page size is 8192 bytes.

How many levels L do we need in a hierarchical (multi-level) page table that can map the complete virtual address space to physical addresses? At each level, what is the maximum of page table pages that we can have?

Note: Level 1 designates the lowest level, Level L the highest level. For example, standard 32 bit Intel x86 has one page at L2 (=Page Directory) and (up to) 1024 pages at L1 (=Page Table)

Maximum number of pages for paging data structures at level L (L is between 1 and 4. Enter "-" for fields of non-existing levels):

L1: ?

L2: ?

L3: ?

L4: ?

Question 2. Modern Intel x86 CPUs support page tables with huge pages of 1 GiB size. What is the main benefit of using such huge pages? What would be a main disadvantages if a Linux system used these huge pages as the default page size for all applications?

Question 3.

Assume you have a system with 4-level page tables. A TLB lookup takes 1 ns, a memory access 100 ns (no other caches considered here). Calculate the average (effective) memory access time (EAT) of the access to the data array in the inner loop.

You may assume that initially the TLB is empty, and that no other activities concurrent to the execution of loop() take place. Your answer must show the EAT value you calculated, rounded to multiples of 1 ns, and the way how you calculated the value.

uint16_t data[2048]; uint32_t sum=0; void loop() { for(int i=0; i<1000; i++) { for(int j=0; j<2000; j++) { sum += data[j]; } } }

Question 4

What difficulties exist when implementing the CLOCK algorithm in a virtual memory system that uses paging with hardware support that sets a bit in the page table entry (PTE) when a page is accessed, and supports shared memory?

(Assume standard multi-level page tables)

A. [ Select "true" or "false"] It is difficult to set the accessed bit in the PTE, as this may require additional hardware support to track page accesses on a per-process basis.

B. [ Select "true" or "false"] It is difficult to synchronize the access to shared pages, as multiple processes may attempt to access the same shared page simultaneously.

C. [ Select "true" or "false"] It is difficult to determine if a shared page has been accessed, as the accessed bit in the PTE may be set by any of the processes sharing the page. The OS has to check all PTEs that map the same page.

D. [ Select "true" or "false"] No difficulties exist, as the CLOCK algorithm is designed to work well with systems that support shared memory.

Question 5.

Pick the (most) correct choices for the following statements about physically-tagged CPU caches:

A. [ Select "true" or "false"] Physically tagged CPU caches have to be invalidated whenever the dispatcher switches to a different virtual address space

B. [ Select "true" or "false"] Physically tagged CPU caches are faster (lower latency), as they operate closer to the hardware, directly using physical addresses without virtual-to-physical translation overhead

C. [ Select one option: "the virtual address", "the full physical address", "the least significant bits (line offset) of the physical address", "the part above (at higher order bits) the line offset of the physical address"]

is the indexing / tagging combination that is of no practical relevance in real systems

D. [ Select one option: "the virtual address", "the full physical address", "the least significant bits (line offset) of the physical address", "the part above (at higher order bits) the line offset of the physical address"]

is used as the tag in a physically-tagged CPU cache.