Virtual Memory

Question 1

1. [2pts] We’ve discussed the physical address space of the system and how it relates to the virtual address space of a process. The physical address space of the system is determined by what feature of the system?

Answer 1

• The amount of memory available

- Memory management system?

Question 2

2. One of the big problems we encountered as we managed physical memory was that of fragmentation.
   (a) [4pts] Name and define the two types of fragmentation.

Answer 2

Internal Fragmentation: Wasted space within a unit of allocation
External Fragmentation: Wasted space between units of allocation

Question 3

(b) [3pts] Why do we consider fragmentation to be a problem?

Answer 3

It’s wasted space

Question 4

3. One of the memory management techniques we studied was relocation.
   (a) [2pts] Relocation suffers from what type of fragmentation?

Answer 4

External fragmentation

Question 5

(b) [2pts] How do we eliminate that fragmentation with static relocation?

Answer 5

We don’t

Question 6

(c) [2pts] How do we eliminate that fragmentation with dynamic relocation?

Answer 6

Defragmentation (Compaction)

Question 7

Paging divides a process’s virtual address space into equally-sized pieces.
1. [2pts] How does the size of the virtual address space relate to the size of the physical address space?

Answer 7

The virtual address space is usually much bigger than the physical

Question 8

2. One day, at home, for fun, you decide to write a program in C. Unfortunately, your program is
very buggy (Did you just add a ’*’ ?), and so you use gdb to find and eliminate the bugs.

(a) [4pts] You print a stack backtrace, and gdb displays the stack along with the address of
each function call. Are these addresses virtual or physical?

Answer 8

Virtual

Question 9

(b) [10pts] How would the system use that address to access the data it represents? Please
describe the steps of the process in a numbered list, and please be sure to include the TLB! Each step should be no more than twenty words.

Answer 9

(1) A concurrent request is sent to the TLB and the page table to find the translation of page number to frame number.
(2) If the translation is found in the TLB, then the request to the page table is stopped, and the frame number is returned.
(3) If the translation is not found, the translation is found in the page table and the translation is added to the TLB.
(4) The offset from the virtual address is added to the frame number to get the physical address.

Question 10

As we studied virtual memory, we discovered that there are many places to improve efficiency, and therefore there are many policy decisions to be made. We discovered that many policies exist, largely because there are advantages and disadvantages to each.

1. [3pts] Most systems use demand paging. How does demand paging increase efficiency?

Answer 10

It doesn’t load in pages until you need them, preventing unnecessary work

Question 11

2. [3pts] Some systems use pre-paging. How might pre-paging increase efficiency?

Answer 11

Pre-paging might increase efficiency if you load in all the right pages because it will result in less page faults

Question 12

3. [3pts] We saw that there were many possible page replacement policies. Why is the page
   replacement policy important? How does it affect efficiency in the system?

Answer 12

It is important because it will run on every page fault, and will affect to the overall efficiency of the system

Question 13

4. [3pts] Some systems implement the working set technique in addition to using a page replacement algorithm. How might that combination increase efficiency?

Answer 13

Working set will decrease the amount of times the page fault handler needs to run by preemptively evicting pages and not letting memory fill up.

Question 14

5. [3pts] At this time, page sizes are increasing. How might a larger page size increase efficiency?

Answer 14

Larger page size can increase time efficiency because the system will page-fault less and increase space efficiency because the page table is smaller.

Question 15

Relocation
One of the memory management techniques we studied is known as relocation.
1. [4pts] What is the main idea behind relocation?

Answer 15

Increase degree of multi-programming

Question 16

2. [2pts] In relocation, what type of address is generated by the compiler?

Answer 16

Physical address.

Question 17

3. [2pts] In static relocation, what type of address is generated by the CPU?

Answer 17

Virtual address.

Question 18

4. [2pts] In dynamic relocation, what type of address is generated by the CPU?

Answer 18

Virtual address.

Question 19

3. For each of the space management technique below, list whether the technique suffered from
   internal fragmentation, external fragmentation, neither, or both. If you feel your answer needs
   justification, justify it.
   (a) [2pts] Relocation

Answer 19

External

Question 20

(b) [2pts] Paging

Answer 20

Internal

Question 21

(c) [2pts] Contiguous files

Answer 21

External

Question 22

(d) [2pts] Linked files

Answer 22

Internal

Question 23

(e) [2pts] Multilevel Indexed Files

Answer 23

Internal

Question 24

Memory Management
On just another day at AwesomeCompany, your fellow employee approaches you and comments that the paging system in use by AwesomeCompany’s OS seems unnecessarily complex, and that it would be simpler and more efficient to just place the processes contiguously in physical memory.
1. [4pts] Name two advantages to the suggested policy.

Answer 24

Less complex.

No overhead of page table lookup.

Question 25

2. [4pts] Name two disadvantages to the suggested policy.

Answer 25

External fragmentation. | Growing a process is hard.

Question 26

3. [2pts] Has the suggested policy been used before? If so, what was its name?

Answer 26

Yeah, static relocation

Question 27

4. [4pts] This suggested policy might work well in systems with certain characteristics. Name two.

Answer 27

Uniprogramming | A dire need to reduce overhead

Question 28

Overview 1. [3pts] One of our topics this semester is virtual memory. What are the goals of virtual memory in a computer system? Name two.

Answer 28

(a) Give the illusion of infinite memory | (b) Provide security between processes

Question 29

2. [3pts] What causes a memory exception? What is the end result?

Answer 29

(a) Page fault (b) Dereferencing null (c) accessing an address that does not belong to the process’s address space Page fault is a handled exception, but in the other two cases, the process is killed.

Question 30

3. [3pts] What causes a page fault? What is the end result?

Answer 30

Reference to unmapped page (1) unmapped is read in (2) page table updated (3) faulting process unblocked

Question 31

Early Memory Management 1. When we began to consider how the operating system manages memory, we first considered a uniprogramming environment. (a) [2pts] Considering our overall goals for the memory subsystem, name two limitations of Uniprogramming.

Answer 31

(a) Only one user can work at a time. | (b) There is no concurrency.

Question 32

(b) [2pts] In uniprogramming, how does the system assign physical addresses to a process and then adjust the process’s addresses to the assigned ones?

Answer 32

Process is always loaded starting at address 0.

Question 33

2. We solved at least one limitation of uniprogramming through relocation. (a) [2pts] What limitation of uniprogramming did relocation eliminate?

Answer 33

Allows for multiple processes to run concurrently.

Question 34

(b) [2pts] How does the system choose which physical addresses to allocate to a process?

Answer 34

*-fit algorithms

Question 35

(c) [2pts] In static relocation, how does the system adjust the process’s logical addresses to the assigned physical ones?

Answer 35

During load

Question 36

(d) [2pts] In dynamic relocation, how does the system adjust the process’s logical addresses to the assigned physical ones?

Answer 36

Bound and base registers

Question 37

(e) Both relocation models had some limitations. i. [2pts] In particular, in relocation each process must fit entirely in memory. What was an early solution to that problem (before paging)?

Answer 37

Overlays

Question 38

ii. [3pts] Name three other limitations of relocation algorithms.

Answer 38

(a) External fragmentation (b) Cannot grow processes easily (c) Can’t have processes larger than physical memory

Question 39

Managing Paging As with so many things we studied, the paging environment exists to manage hardware and yet requires a lot of management itself. 1. [4pts] One of the main ideas behind paging is the existence of pages and frames. What are they and how do they relate?

Answer 39

Every page is the unit of virtual memory that maps to a frame, which is the unit of physical memory. They have the same size.

Question 40

(b) [4pts] Since the executing process is clearly trying to access something on that page, what happens next? Describe how the system does or does not find that page.

Answer 40

The page is not in resident memory. This means that the page is in swap or has not been loaded from the filesystem yet. The page gets paged into the memory.

Question 41

(c) [2pts] Assume physical memory is full and that this system is using the clock page replacement algorithm. What information will it consider when choosing a page to evict?

Answer 41

Resident bit and reference bit

Question 42

(d) [4pts] Once you choose a page to evict, what steps do you need to take to complete the eviction? Be certain to remember to update metadata structures.

Answer 42

(1) Write the chosen page to swap if it is dirty, and clear the dirty bit (2) Update the page table entry to reflect where the page now resides (swap), and set resident bit to false. (3) Mark the associated frame as free.

Question 43

Virtual Memory Concepts | 1. [2pts] What is a page?

Answer 43

Unit of allocation in virtual memory

Question 44

2. [2pts] What is a frame?

Answer 44

Unit of allocation in physical memory

Question 45

3. [2pts] How does a page relate to a frame?

Answer 45

Same size

Question 46

4. [2pts] What is a TLB and what does it contain?

Answer 46

Translation Lookaside Buffer - it contains recent accessed page table, frame translations for the current process.

Question 47

5. [2pts] What is swap?

Answer 47

A partition on disk.

Question 48

6. [2pts] What is thrashing and why does it matter?

Answer 48

When pages are evicted right before they are needed. It dramatically decreases CPU performance.

Question 49

7. Paging gave us several advantages over prior memory management techniques. (a) [2pts] How does paging enable sharing?

Answer 49

Different page table entries can point to the same frame.

Question 50

(b) [2pts] How does paging enable multiprogramming?

Answer 50

Multiple processes can fit in physical memory at the same time. It provides support for processes larger than the physical memory itself.

Question 51

Memory Management 1. [4pts] We began this part of the course by discussing memory management in the operating system. Name two functionalities that the OS provides for the user as it manages memory. (Hint: Think of the hats!)

Answer 51

(a) Illusion of infinite memory (Ilusionist) | b) Protection around memory accesses (Referee

Question 52

2. In the pursuit of multiprogramming, the idea of relocation was introduced. (a) [4pts] We studied two forms of relocation. What are they and what is the essential difference between them?

Answer 52

Static and dynamic relocation when addresses are adjusted (at compile time, dynamically)

Question 53

(b) [3pts] Both forms of relocation suffer from a very big, wasteful drawback. What is it?

Answer 53

External fragmentation