Midterm 1

Question 1

1 GB =

Answer 1

2^30

Question 2

1 MB =

Answer 2

2^20

Question 3

1 KB =

Answer 3

2^10

Question 4

giga-

Answer 4

10^9

Question 5

Static rewriting

Answer 5

rewrites two processes’ addresses to be distinct

Question 6

Static rewriting issues

Answer 6

1. relocation at runtime is hard (have to constantly rewrite process memory and pointers are hard to keep track of and manage)
2. security (no isolation, pointers can access any random location)

Question 7

Dynamic relocation

Answer 7

1. base:
   virtual address + base = physical address

can just change the base to automatically shift processes to new locations

2. bound:
   mem access checked by bound (if out of bound –> interrupt)

Question 8

can processes access base and bound registers?

Answer 8

NO!!!!

Question 9

base and bounds implementation

Answer 9

new CPU unit called memory management unit (MMU)

MMU has two registers: base and bounds

Question 10

dynamic relocation issues

Answer 10

programs aren’t contiguous (chunks of free space between allocated memory)

Question 11

Segmentation

Answer 11

using multiple base and bounds

Question 12

what is a segment?

Answer 12

a base and bound pair that can be efficiently resized

Question 13

segmentation implementation

Answer 13

uses MMU with a segment table containing variable # of segments

Question 14

segmentation issues

Answer 14

requires contiguous regions but also results in external fragmentation

Question 15

external fragmentation

Answer 15

combined space is large enough but memory is fragmented –> not individual free mem segment is useful

Question 16

internal fragmentation

Answer 16

the memory reserved for a process can’t be used by OS until the process terminates

Question 17

external fragmentation solution! (the bad one)

Answer 17

defragmentation: move previously allocated regions to get contiguous free space

Question 18

defragmentation issues

Answer 18

expensive! running process might be stopped and allocation takes too long

Question 19

external fragmentation solution! (the good one)

Answer 19

paging!

Question 20

Paging idea

Answer 20

fine-grained and regular (constant) division of memory (called pages)

Question 21

frames

Answer 21

fixed sized blocks of physical memory

Question 22

pages

Answer 22

fixed sized blocks of a process’ address space

Question 23

frame size = ?

Answer 23

page size

Question 24

pros of paging

Answer 24

1. don’t need a large contiguous region
   (process still sees the address space as contiguous)
2. any page can be mapped to any frame

Question 25

Page table

Answer 25

structure that maps a page to a frame using the virtual address

• uses the MMU
• only OS can change the page table

Question 26

each process has its own page table

Answer 26

true

Question 27

one-to-one paging

Answer 27

page table is just a linear array where each page has its own page table entry

the page table entry contains the final frame number

Question 28

address space (AS) limit/size

Answer 28

how much memory MAX the OS will allocate to one process

Question 29

equation relating AS limit, page size, # pages

Answer 29

AS limit/page size = # pages

Question 30

how to find a where page tables are stored in DRAM?

Answer 30

page table base register (ptbr)
- accessed only in S-mode
- shows physical address

if linear PT:
- can find any PTE from ptbr

if multi-page:
- ptbr points to highest level PT

Question 31

one-to-one (linear) paging issues?

Answer 31

a PT can require A LOT of contiguous space

= # PTEs * size of a PTE

Question 32

multi-level page tables

Answer 32

solve the space issue of linear PTs:

• multiple small PT instead of one big PT
• only allocate each table when needed
• remaining space in the address

Question 33

size of a PTE =

Answer 33

architectural size (64-bit systems have 64-bit PTEs)

Question 34

layout of a PTE (linear)

Answer 34

upper bits: physical frame #
lower bits: page permissions

Question 35

where are page tables stored: CPU cache or DRAM?

Answer 35

DRAM: cache is faster but much more expensive (not much memory space)

Question 36

multi-level paging issues?

Answer 36

memory access is expensive:
if you have N-levels of page tables, you need N + 1 DRAM accesses = N page tables + final frame access

Question 37

multi-paging issues solutions!

Answer 37

1. TLB - translation lookaside buffer
2. cache

Question 38

TLB

Answer 38

stores final translation (not the data itself)

• OS needs to clear old TLB entries if any changes to PT are made

Question 39

TLB issues

Answer 39

sometimes we need to:
1. check TLB to see if translation is cached

2. if not, store translation after walking the page table

** CPUs have optimization algorithms so TLB hits rates are very high and these issues are not significant

Question 40

cache for paging why?

Answer 40

DRAM is slow, regardless of TLB hit or not

Question 41

cache stores ___ while TLB stores ___

Answer 41

data, translation

Question 42

memory access steps

Answer 42

1. check cache
2. cache miss –> check TLB
   2a. TLB hit –> physical frame –> done

2b. TLB miss –> walk the PTs to find physical address
3. insert translation into TLB
4. insert data into cache

Question 43

library sharing

Question 44

lazy on-demand memory allocation