Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CMPT 300 > Virtual Memory Part 2 > Flashcards

Virtual Memory Part 2 Flashcards

1
Q

What 6 steps are required when handling a page fault?

A 
1. OS figures out:
  •Invalid reference
    ➔abort process
  •Just not in memory 
    ➔bring page in
2. Locate page on disk
3. Find a free page frame
4. Swap page from disk to frame (I/O operation)
5. Reset page table, set valid bit to 1
6. Restart the instruction that caused page fault
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

If the OS doesn’t have enough memory when swapping, it needs to ______ an __________ page in physical memory to make room for the _______ page

A

evict, existing, incoming

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What does a page replacement policy do?

A

It handles the eviction of existing pages in physical memory to make room for the incoming page

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are 3 page replacement policies?

A
  • First-in-first-out
  • Least recently used
  • Second-chance (Clock)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

We can save swap out _______ if the victim page was ___ ________

A

overhead, not modified

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

The goal of Page Replacement Algorithms is to…

A

minimize page-fault rate

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

To evaluate a _____ __________ ________, we compute the number of page faults that will occur if we follow a set sequence of memory page references

A

Page Replacement Algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

We expect the number of page faults to ________ as the number of physical frames allocated to process ________

A

decreases, increases

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

For the sequence
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
how many page faults do we get with 3 page frames using the FIFO algorithm?

A

9

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

For the sequence
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
how many page faults do we get with 4 page frames using the FIFO algorithm?

A

10

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is Belady’s Anomaly?

A

More frames may result in more page faults

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

A pro of the FIFO replacement algorithm is that it is…

A

easy to understand an implement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Why is performance not always good with the FIFO replacement algorithm?

A
  • May replace a page that is used heavily

- Suffers from Belady’s Anomaly

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

The optimal replacement algorithm would replace the page that has not been used for the _______ time

A

longest

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

For the sequence
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
how many page faults do we get with 4 page frames using the optimal replacement algorithm?

A

6

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Can we implement the optimal replacement algorithm? If so, how? If not, why?

A

No, because we cannot predict the future

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the optical replacement algorithm used for?

A

It is used as a benchmark for comparing algorithms

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

With the Least Recently Used Algorithm, we try to ________ the optimal policy by __________ the future based on the _______

A

approximate, inferring, past

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

With the Least Recently Used Algorithm, we replace the page that has not been used for the _________ time

A

longest

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Why do we replace the page that has not been used for the longest time in the LRU algorithm?

A

The page may not be needed anymore. Ex. pages of an initialization module

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Does LRU suffer from Belady’s Anomaly?

A

No

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

For the sequence
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
how many page faults do we get with 4 page frames using the LRU algorithm?

A

8

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

In the LRU counter implementation, each page-table entry has a ______-___-____ field

A

time-of-use

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

In the LRU counter implementation, the CPU ______ _____ is copied into the time-of-use field upon page ________

A

logical clock, reference

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What are 4 cons of the LRU counter implementation?

A
  • Search overhead
  • Memory write overhead
  • Clock overflow
  • Need hardware support
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

LRU _____ implementation is not common in practice

A

counter

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

In the LRU stack implementation, a _____ of page numbers is stored in a _______-linked list

A

stack, doubly

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

In the LRU stack implementation, the least recently used page sinks to the _______

A

bottom

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What is a pro of the LRU stack implementation?

A

There is no need to search when replacing a page

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What are 2 cons of the LRU stack implementation?

A
  • Each memory reference becomes more expensive

- Needs hardware support

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Can we implement LRU without hardware support? Why or why not?

A

No. It is too costly and will slow every memory reference by a factor of at least 10

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

The second chance replacement is also known as the ______ replacement

A

clock

33
Q

Clock replacement is an __________ of LRU

A

approximation

34
Q

In the clock replacement algorithm, each page has a ________ bit, initially set to ____

A

reference, zero

35
Q

In the clock replacement algorithm, the _______ is set to one when a page is referenced

A

ref_bit

36
Q

In the clock replacement algorithm, the algorithm maintains a ______ pointer to the next ______

A

moving, victim

37
Q

In the clock replacement algorithm, explain the process of choosing a page to replace.

A 
If  ref_bit== 0 {
replace it
}
Else {
set ref_bit to 0 
move pointer to next page
}
38
Q

What is thrashing?

A

a process is busy swapping pages in and out more than executing on CPU

39
Q

What happens when the page-fault rate is very high?

A
  • Low CPU utilization
  • Makes OS think it needs to increase multiprogramming
  • OS admits another process to system
40
Q

How do we prevent trashing?

A

Give a process as many page frames as it needs

41
Q

In the locality model only pages needed to execute the _______ _______ are kept. Once we execute another _______, we bring in the new ______

A

current function, function, pages

42
Q

________ refers to the set of pages actively used together

A

locality

43
Q

We can figure out the size of a locality using the ______-___ model

A

working-set

44
Q

The working set is the set of _____- in the most recent delta memory __________

A

pages, references

45
Q

The working set is a ______ _______

A

moving window

46
Q

At each reference, a new reference is added at one end and _______ at the other from the working set

A

dropped

47
Q

In the WS model, what happens if delta is too small?

A

it will not encompass entire locality

48
Q

In the WS model, what happens if delta is too large?

A

it will encompass several localities

49
Q

___________ the entire working set is costly

A

maintaining

50
Q

We can approximate the WS with an _______ timer and _________ bit

A

interval, reference

51
Q

There is a direct relation between the ________ _____ of a process and its _______ ____ rate

A

working set, page fault

52
Q

To control trashing using page fault rate, we can ________ page-fault rate and ______/______ allocated frames accordingly

A

monitor, increase/ decrease

53
Q

To control trashing using page fault rate, we need to establish an ________ page fault rate

A

acceptable

54
Q

______ memory is treated differently from user memory

A

kernel

55
Q

Some kernel memory needs to be _________

A

contiguous

56
Q

Kernel memory cannot afford a ____ _____, and thus virtual memory is too ________

A

page fault, expensive

57
Q

Often, a ____-_______ pools is dedicated to kernel which it allocates the needed memory

A

free-memory

58
Q

The _______ system and ____ allocation are two examples of allocating kernel memory

A

buddy, slab

59
Q

How does the buddy system allocate memory?

A

Allocates memory from fixed-size segment consisting of physically-contiguous pages

60
Q

In the buddy system, memory is allocated in powers of ___

A

two

61
Q

In the buddy system, when a ______ allocation is needed than what is available, split the _____ into the next lower power of 2

A

smaller, chunk

62
Q

In the buddy system, adjacent chunks are ________ to form a large segment

A

combined

63
Q

The slab allocator creates _______, each consisting of one or more ______

A

caches, slabs

64
Q

In the slab allocator, a slab is one or more ________ __________ pages

A

physically contiguous

65
Q

In the slab allocator, each cache is filled with object __________

A

instantiations

66
Q

In the slab allocator, there is a cache for each unique kernel _______ __________

A

data structure

67
Q

In the slab allocator, objects are initially marked as _____

A

free

68
Q

In the slab allocator, when structures are stored, the objects are marked as _____

A

used

69
Q

In the slab allocator, what are 2 benefits?

A
  • Fast memory allocation

- No fragmentation

70
Q

For memory-mapped files, we ____ a file into memory address space

A

map

71
Q

What is the process if mapping a file into memory address space?

A

A page-sized portion of the file is read from the file system into a physical frame

72
Q

Memory-mapped files is one way of implementing ______ _______ for IPC

A

shared memory

73
Q

What are 2 benefits of memory mapped files?

A
  • Efficient, as memory accesses are less costly then I/O

- Simple, as I/O operations in files are treated as memory accesses

74
Q

What are 4 things page size selection impacts?

A
  • Fragmentation
  • Page table size
  • I/O overhead
  • Locality
75
Q

In pre-paging, the OS brings in ____ or ____ of the pages a process will need, before they are _______

A

some, all, referenced

76
Q

What is the tradeoff for pre-paging?

A

Pro: reduce number of page faults at process start-up
Con: May waste memory and I/O because some of these pages may not be used

77
Q

In what scenario do we need to use I/O interlock?

A
  • Process uses page for I/O request
  • the page is replaced
  • I/O comes back, but page is gone
78
Q

What does I/O interlock do?

A

Locks the buffer/page in memory

CMPT 300 (21 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions