Memory Management: Demand Paging

Question 1

What is Virtual/Logical Address Space?

Answer 1

It is the memory the programmer perceives their program to have.

Question 2

What is Physical Address Space?

Answer 2

It refers to the actual location of the program within the physical memory.

Question 3

List the Memory Mapping Methods.

Answer 3

○ Base and bounds
○ Segmentation
○ Paging

Question 4

Explain Segmentation.

Answer 4

Segmentation enables memory sharing between processes. This is achieved by:
● Creating a segment for the shared data.
● Adding a segment entry in the segment table for each process, pointing to the shared segment in memory.
For instance, running the same program in different processes might require sharing code, or reading the same file in different processes might involve sharing memory corresponding to the file. Segmentation allows for this memory sharing that base and bounds cannot

Question 5

What is the base and bounds memory mapping method?

Answer 5

A method of memory mapping that uses a base register to store the starting address of a process’s memory in physical memory and a bounds register to store the size of the process’s memory.

Question 6

What is external fragmentation?

Answer 6

External fragmentation occurs when there is enough free memory to satisfy a request, but the memory is not contiguous.

Question 7

What is memory compaction? What are its drawbacks?

Answer 7

Memory compaction is a technique used to reduce external fragmentation. It involves rearranging segments in physical memory to get rid of holes.
○ Memory compaction is expensive and inefficient.

Question 8

○
What is paging? What are a page and a frame?

Answer 8

○ Paging is a memory mapping method that divides a process’s address space into fixed-size portions called pages and physical memory into fixed-size portions called frames.
○ The size of a page is equal to the size of a frame.

Question 9

What are the two components of a virtual address in paging?

Answer 9

○ VPN: Virtual page number
○ Offset: offset within the page

Question 10

What is a page table?

Answer 10

A data structure used to map virtual addresses to physical addresses. It is indexed by page number and contains the frame number of the page in memory. Each process has its own page table.

Question 11

What problems arise from large page tables?

Answer 11

○ Page tables can become very large, especially with large address spaces.
○ A large amount of memory may be required just to store page tables.
○ Address spaces are often sparsely used, meaning that a significant portion of the page table may be unused.
○ Access to unused portions of the address space may appear valid, which is undesirable.

Question 12

What is the valid/invalid bit in a page table entry?

Answer 12

○ A bit that indicates whether a page is currently in memory (valid) or not (invalid).

Question 13

What are multi-level page tables?

Answer 13

○ A solution to the problem of large page tables. They use a hierarchy of page tables, where entries in higher-level page tables point to lower-level page tables.

Question 14

What is internal fragmentation?

Answer 14

○ Internal fragmentation occurs when a portion of a page is unused.

Question 15

What is the problem with paging address translation performance?

Answer 15

○ Paging address translation requires two memory accesses: one to access the page table and another to access the actual data.
○ This can significantly reduce performance, as memory access speeds are often a bottleneck.

Question 16

What is the TLB?

Answer 16

○ A small, fast hardware cache that stores recent page table entries to speed up address translation.

Question 17

○
Describe the steps involved in a TLB hit.

Answer 17

○ The MMU looks up the virtual page number in the TLB.
○ If the mapping is found, the MMU uses the frame number from the TLB to access the physical memory.
○ Only a single memory access is required.

Question 18

Describe the steps involved in a TLB miss.

Answer 18

○ The MMU looks up the virtual page number in the TLB.
○ If the mapping is not found, a TLB miss occurs.
○ The MMU then accesses the page table in memory to get the frame number.
○ The (frame number, page number) mapping is added to the TLB.
○ The MMU retries the address translation, which now results in a TLB hit.

Question 19

How is the TLB implemented to be fast?

Answer 19

○ The TLB is implemented using associative memory, which allows for parallel lookup by content.

Question 20

Why is the TLB small?

Answer 20

○ Associative memory, used to implement the TLB, is expensive.

Question 21

What are temporal and spatial locality?

Answer 21

○ Temporal locality: Recently accessed data is likely to be accessed again soon.
○ Spatial locality: Data near recently accessed data is likely to be accessed soon.

Question 22

How can TLB hit rate be improved?

Answer 22

○ Take advantage of temporal and spatial locality.

Question 23

What is the issue with context switching and the TLB?

Answer 23

○ When switching between processes, the TLB may contain entries for the previous process.
○ If the new process accesses a virtual page that is mapped in the TLB but belongs to the previous process, it may access the wrong memory.

Question 24

Describe two solutions to the context switching issue with the TLB.

Answer 24

○ Solution 1: Invalidate all TLB entries on process switch. This ensures that the new process starts with an empty TLB and avoids accessing wrong memory. Drawbacks: makes process switch expensive and new process incurs 100% TLB misses initially.

○ Solution 2: Add a process identifier (PID) to TLB entries. This allows the TLB to distinguish between entries from different processes. The TLB match occurs only when both the page number and PID match. This solution is cheaper because nothing needs to be done during context switching.

Question 25

What is demand paging?

Answer 25

○ A memory management technique where only the necessary pages of a process are loaded into memory. The remaining pages are kept on disk and loaded on demand when they are accessed.

Question 26

What is swapping? How does demand paging differ from swapping?

Answer 26

○ Swapping involves moving an entire process between memory and disk.
○ Demand paging loads individual pages on demand, while swapping moves the entire process.

Question 27

What are the benefits of demand paging?

Answer 27

○ Shorter process startup latency
○ Better use of main memory

Question 28

Where is a program stored when it is not entirely in memory?

Answer 28

○ Parts of the program that are currently being used are in memory.
○ The entire program is stored on disk in a special partition called the backing store or swap memory.

Question 29

What is a page fault?

Answer 29

An event that occurs when a process attempts to access a page that is not currently in memory.

Question 30

Describe the steps involved in demand paging mechanism.

Answer 30

1.
The process attempts to access a page that is not in memory, causing a page fault.
2.
The process is suspended.
3.
The operating system takes control.
4.
The operating system locates the required page on disk (backing store).
5.
The operating system finds a free frame in memory or selects a page to be replaced.
6.
If the chosen frame is dirty (modified), it is written back to disk.
7.
The operating system initiates a disk transfer to load the required page into the free frame.
8.
While the disk transfer is in progress, the operating system may schedule another process to run.
9.
Upon completion of the disk transfer, the operating system updates the page table, setting the valid bit to 1 and the frame number to the newly allocated frame.
10.
The operating system marks the process as ready to run.
11.
The scheduler may eventually resume the process.
12.
The process restarts the faulting instruction, which now successfully accesses the required page in memory.

Question 31

What is a page replacement policy?

Answer 31

An algorithm that decides which page to remove from memory when a page fault occurs and there are no free frames available

Question 32

List some page replacement policies.

Answer 32

○ Random
○ FIFO (First-In, First-Out)
○ OPT (Optimal)
○ LRU (Least Recently Used)

Question 33

Describe the Random page replacement policy.

Answer 33

○ A page is chosen randomly for replacement.
○ Easy to implement.
○ Does not take advantage of locality.

Question 34

Describe the FIFO page replacement policy.

Answer 34

○ The oldest page in memory (the one that was loaded first) is replaced.
○ Easy to implement using a queue.
○ Fair in the sense that all pages receive equal residency time.
○ Does not consider page usage frequency, so it may replace frequently used pages.

Question 35

Describe the OPT page replacement policy.

Answer 35

○ Replaces the page that will not be used for the longest period in the future.
○ Theoretically optimal.
○ Not practically implementable because it requires knowledge of future page accesses.

Question 36

Describe the LRU page replacement policy.

Answer 36

○ Replaces the page that has not been used for the longest period.
○ Approximates OPT by assuming that past usage patterns predict future usage.
○ More complex to implement than FIFO or Random.
○ May perform poorly for certain access patterns.

Question 37

How is LRU approximated with hardware support?

Answer 37

○ A reference bit is used in the page table entry.
○ Hardware sets the reference bit to 1 when a page is accessed.
○ Periodically, the operating system reads and stores the reference bits and then resets them to 0.
○ By keeping a history of reference bits, the operating system can approximate which pages have been used recently

Question 38

How is the page to replace selected in an LRU approximation?

Answer 38

○ The page with the smallest value in its reference bit history is chosen for replacement.

Question 39

What is the modified bit in a page table entry?

Answer 39

○ A bit that indicates whether a page has been modified (dirty) since it was loaded into memory.

Question 40

What is the purpose of the modified bit?

Answer 40

○ It helps optimize page replacement by avoiding unnecessary disk writes. If a page has not been modified, it can be replaced without writing it back to disk.

Question 41

What are huge pages?

Answer 41

○ Larger page sizes, such as 2MB or 1GB, that can be used to reduce page table size and improve TLB hit rate.

Question 42

What is an inverted page table?

Answer 42

○ A page table structure that has one entry per physical frame instead of one entry per virtual page. It stores the process ID and virtual page number that is mapped to each physical frame.