VM-concepts

Question 1

What’s the difference between sequential access and random access?

Answer 1

Sequential access - accessing the elements in an ordered way: 1,2,3,…
Random access- accessing the elements in an unordereed way: 4, 8, 5, 1, 9,7,3,…

Question 2

What’s the page cache?

Answer 2

The memory area that caches (synchronized) disk data
– Is called a “page cache”
Because DRAM is much faster
– OS caches disk content in DRAM

Question 3

What happens when we write or read from disk?

Answer 3

If a process reads from disk
– Data brought to DRAM
– Stays there until OS decides
differently

If a process writes to disk
– First written to OS DRAM buffer
– Later sync-ed to disk

Question 4

What’s the difference between a page and a frame?

Answer 4

– “Page” = chunk of contagious data (in virtual or physical space)
– “Frame” = physical memory exactly big enough to hold one page
– |page| = |frame| = 2^k (bytes)
– Typically, k = 12, namely a page (and frame) size is 4KB
- Pages & frames are always aligned on 2^k boundaries

Question 5

What is the division of labor between HW and OS in VM implementation?

Answer 5

OS sets the VA=>PA mappings (“control path”)

• HW does on-the-fly translation from VA to PA (“data path”)

Question 6

What can a PTE point to?

Answer 6

An address in DRAM or on disk or nothing

Question 7

What happens on every Memory access?

Answer 7

If ( valid == 1 )
– Page is in main memory @ PA stored in table
– Data is readily available & can be used

• Else if ( page resides on disk ) // HW generates page fault (“major”)
– OS suspends process
– Fetches page from disk and adds VA=>PA mapping to page table
– Resumes process, which will re-execute faulting instruction

• Else if ( should be, but still isn’t allocated ) // page fault (“minor”)
– OS allocates pages and adds VA=>PA mapping to page talble

• Else if ( some other legal situations for which OS is responsible )
– Resolve (example: CoW)

• Else // process performed an illegal memory ref
– OS (which handles the page fault interrupts) delivers a signal
(SIGSEGV/SIGBUS) to the offending process
– The matching signal handler terminates process by default

Access Control
– R=read-only, R/W=read/write, X=execute
– If access type incompatible with specified access rights
1.  protection violation fault
2.  interrupt
3. resolve if OS’s fault (as in CoW),
or deliver signal if process’s fault

Question 8

What’s a major page fault? and what is the algorithm for handling?

Answer 8

Major => need to retrieve page from disk

1. CPU detects the situation (valid bit = 0)
   • It cannot remedy the situation on its own
   – CPU doesn’t communicate with disks
   – Moreover, CPU has no say regarding page table contents
2. CPU generates interrupt and transfers control to the OS
   • Invoking the OS page-fault handler
3. OS regains control, realizes page is on disk, initiates I/O read ops
   • To read missing page from disk to DRAM
   • Possibly need to write victim page(s) to disk (if no room & dirty)
4. OS suspends process & context switches to another process
   • It might take a few milliseconds for I/O ops to complete
5. Upon read completion, OS makes suspended process runnable again
   • It’ll soon be chosen for execution
6. When process is resumed, faulting operation is re-executed
   • Now it will succeed because the page is there

Question 9

What’s a minor page fault? give examples

Answer 9

A page fault where we don’t need to go to disk in order to resolve it.

Examples:
1. CoW (copy-on-write)
2. Demand-based (lazy) memory allocation
3. Reading a file content that is already found in the “page cache”
• OS caches previously read files, possibly by other processes
• All read/write ops go through the page cache

Question 10

What’s the difference between a page cache and the DRAM?

Answer 10

the page cache is just a portion of the DRAM.
for example a page might have been accessed from an earlier process, for our process it will be invalid page but it’s in the dram and not disk.
hence, in the page cache

Question 11

What is the purpose of the mmap syscall?

Answer 11

Map a given file in a given virtual address in the process’s memory space.

A file becomes an “array of bytes” (backed by disk), and gets a VA
• With the right mmap() flags, reading/writing from/to the array
(more or less) translates to reading/writing from/to the file

A mmap()ed file is said to be a “memory-mapped file”

Question 12

What are the pros of mmap?

Answer 12

1. Can make programming easier
2. Saves overhead of read/write system calls (user/kernel switches)
3. Integrated with “page cache”…
   • All disk load/store ops are cached in memory by “page cache”
   • By default, all I/O goes through page cache, not directly to disk
   • Mmap sets process’s PTEs to point to the page cache pages
   – …So we get “zero copy” I/O
   • Saves copying to/from user buffers
   • May reduces memory pressure

Question 13

What are Anonymous and named pages?

Answer 13

Anonymous pages
– Heap/stack pages; not mmap-ed files

Named pages
– Backed by a file (via mmap-ing)

Question 14

Can an anonymous page be allocated with mmap?

Answer 14

Yes. by using the flag MAP_ANONYMOUS

Question 15

What’s shared and private mmaping?

Answer 15

MAP_SHARED = changes affect the actual file (visible to other processes)
MAP_PRIVATE = changes don’t affect the actual file; rather, there will be
a copy-on-write for the process (other processes will not see changes)

Question 16

What are the cons of mmap?

Answer 16

1. Mapped buffer must be page-aligned
2. There’s a subtle consistency issue arising from an interaction
   between mmap(MAP_PRIVATE) and write(fd):
   • It is unspecified whether changes made to the file via fd,
   after the mmap() call, are visible in the mapped region

Namely…
– P1: arr = mmap(MAP_PRIVATE, some_file)
– P2: fd = open(some_file);
write(fd, “…”);
– What is arr[0]?
– Is it the information there before the write? Or after?
– Unspecified.

Question 17

do we need to page out named pages?

Answer 17

only if they are “dirty”

Question 18

when we read() a file’s page (with the read syscall), is it named?

Answer 18

seemingly no, but actually depends on the buffer pointer passed to the
read system call

Question 19

can anonymous pages reside on disk?

Answer 19

Yes. if swapping occures.

Question 20

is reading (via read() or mmap-ed buffer) always slow as disk?

Answer 20

depends on whether or not the corresponding area being read already
resides in the page cache

Question 21

is writing (via write() or mmap-ed buffer) slow as disk?

Answer 21

no, writing is asynchronous (explicit fsync-ing, however, will make it slow
by making the process wait until the data is actually written to disk)

Question 22

What is the swap space?

Answer 22

– Disk area (file) where anonymous pages are written, if the OS decides
they have no room in DRAM

– Page is said to be “swapped out” when this occurs
(and “swapped in” for the reverse operation)

– Swap area contains anonymous pages (including mmap anonymity)

Question 23

What’s on-demand paging?

Answer 23

OS maps / reads page from disk into DRAM only if/when the process
attempts to access it for the first time (and, hence, a page fault occurs)

Question 24

What is the working set of p? Formally: WS_p(k)

Answer 24

– Pages accessed by process (or thread) P in the last k accesses
For a fixed value of k, smaller WSP(k) indicates more locality

the Working set is the union of all working sets.

Question 25

What’s thrashing and when does it occur?

Answer 25

Thrashing is when Virtual memory is in a constant state of paging, rapidly exchanging
data between memory & disk
therefore Nearly nothing else is done in the system (causes performance to
degrade/collapse)

happens when e.g. there isn’t enough physical memory to back the
currently-in-active-use virtual memory

Question 26

What are the clock and NRU(not recently used) page reclamation algorithms?

Answer 26

1. clock - every frame has a “accessed” bit, every few seconds we zero the bits for all frames.
   we hold a “current” pointer, and when we need to evict we start from “current” and search the first frame with “accessed == 0” that is the victim.
2. NRU -
   - Prefer keeping referenced over unreferenced
   • Prefer keeping modified (dirty) over unmodified