Brainscape's Knowledge GenomeTM

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


See full index

CS3106: Operating Systems > Page replacement design > Flashcards

Page replacement design Flashcards

1
Q

What design decisions have to be made?

A

Frame allocation algorithm: How memory frames are allocated among processes

Page replacement algorithm: How victims will be chosen

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

How are algorithms evaluated?

A

Run the algorithm against some test data, where the test data is a sequence of reference strings.

Can also trace a running system to produce large amounts of data.

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

What is a reference string??

A

Record only page number, consecutive duplicates are eliminated.

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

How does FIFO replacement work?

A

Replace the page that was brought in first.

Record the time that each page was faulted.

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

How can we optimise the FIFO solution?

A

Interested in order, not time. Create FIFO queue and replace pages at the head of the queue.

When page is faulted, insert at back.

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

What are the drawback of FIFO replacement?

A

May replace heavily used pages. IE:

Variable written at start of program that is used throughout but will be replaced.

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

What is the FIFO anomaly?

A

intuitive results due to Belady’s anomaly.

Page fault rate may increase when number of frames is increased.

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

What is an optimal algorithm for page replacement?

A

Replace the page that will not be used for the longest time

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

What is the implication of the optimal algorithm?

A

Impossible to implement as we can’t predict the future.

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

What is the optimal algorithm used for?

A

Comparison purposes, calculate the best possible performance of a reference string.

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

What is LRU?

A

Least recently used , replace the page that hasn’t been used for the longest time.

Optimal algorithm except it looks back in time.

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

How is memory determined by the LR?

A

Pages in memory are the n most recently used pages.

For n+1 frames these n pages would still be in memory.

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

How does LRU work with counters?

A

Logical CPU clock held in register, incremented on each memory reference.

Page table entry contains counter value at last use, have to search page table for smallest value.

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

How does LRU work with the stack?

A

Maintain a stack of page numbers.

On reference, remove from stack and push on top.

Replace page at bottom of stack.

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

What support does LRU require?

A

Hardware support, clock or stack approach require memory update on every reference.

Interrupt on ever memory reference.

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

What is used when there isn’t enough hardware support for LRU?

A

Reference bits, associated with each page table entry and set by hw when page is referenced. All bits cleared periodically.

Identifies pages used since bits were last cleared.

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

What is the drawback of reference bits?

A

Can’t tell what order pages were used in.

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

How does the OS interact with reference bits?

A

OS records reference bits at regular intervals.

On timer interrupt, OS shifts byte for each page right 1 bit and copies in current value of reference bit into left-most bit.

Interpret this as integers and replace lowest number.

19
Q

How can reference bits be used in FIFO?

A

Pages have their reference bit checked before being replaced.

If it is kept in the queue, clear reference but and reset arrival time to present.

20
Q

How does the clock algorithm work?

A

Circular queue of pages, pointer indicates next victim. When page is needed pointer advances until page with a 0 reference bit is found.

Reference bits cleared as they are passed.

21
Q

What is the worst case of the clock algorithm?

A

All bits are set and pointer cycles through all pages. Head then becomes the victim.

22
Q

How can we enhance second chance?

A

Use reference bit and modified bit as ordered par.

Use clock algorithm, interpret pair as integer and replace a page in the lowest non-empty class.

23
Q

How does free frame pool work?

A

Keep some frames free all the time.

Choose victim frame as normal, read new page into a free frame immediately, don’t wait on write back.

Victim frame added to free pool when write completes.

24
Q

what is Background write back?

A

List of modified pages, opportunistically write modified pages back to disk and reset dirty bit.

Page more likely to be unmodified when replaced.

25
Q

How can page fault rate be reduced?

A

By allocating more frames to a process.

26
Q

How is mininum frame allocation used?

A

Instruction set dictates minimum allocation

Instruction restarted on page fault.

Must have enough frames to hold all pages a single instruction can reference.

27
Q

What determined the minimum number of frames needed?

A

Indirection

28
Q

How does allocation among processes work?

A
  • Equal share among processes OR

Proportional allocation: Allocate frames in proportion to size or priority of the process. Can pre-emptively takes frames from lower priority process.

29
Q

In terms of replacement, what is the global scope and how does it work?

A

Frame can be selected from the set of all frames.

Performance of process depends on external circumstances (depends on paging behaviour of process and other processes.)

30
Q

How does the local replacement scope work?

A

Process must choose only from its allocated frames

Set of pages in memory is dependent on the process alone, system may have under-used frames.

31
Q

What are the problems with minimum allocation?

A

Allocation must be big enough to hold all active pages, however reduced performance as pages are continually replaced even when they are about to be used.

32
Q

What is thrashing?

A

High paging to disk, when process spends more time paging to disk than executing

33
Q

What causes thrashing?

A

Too much multi-programming.

There’s a fixed number of framers and too many process get an allocation too small.

34
Q

What is the impact of thrashing

A

Small increase in page fault greatly increasing effective memory access time.

Reduced CPU utilisation.

35
Q

How do we limit the impact of thrashing?

A

Local replacement algorithm, page fault evicts a page of the same process. One process thrashing cannot cause others to thrash.

Thrashing process increases IO load and EAT time increases for non-thrashing processes.

36
Q

How do we prevent thrashing?

A

Define the locality model

model of process execution, process locality is a set of pages actively used together.

Process moves between localities as it executes.

37
Q

What is locality?

A

Locality of a function: Instructions, local variables, subset of global variables.

Leave the locality on return from the function.

38
Q

How is locality determined?

A

Locality is determined by program structure and data structures

39
Q

What is the relationship between locality and frames?

A

Allocate enough frames to hold locality, initially pages in locality are faulted but there is no more faulting until locality changes.

40
Q

When does thrashing occur on localities?

A

When frame allocation is too small to hold the locality.

41
Q

What is a working set?

A

Pages referenced in the last working-set window of memory references.

42
Q

What are the attributes of a working set?

A

Pages in active use remain in the set.

Pages not used for a while drop out of the set

Size of working set may change.

Approximates program locality

43
Q

How is the accuracy of the working-set window determined?

A

Too small: Doesn’t contain whole locality

Too large: overlaps several localities.

Thrashing occurs if the sum of all sizes > number of frames.
Each process is allocated enough frames to contain the working set.

44
Q

How is the working set determined?

A

Use reference bits

interrupt after fixed number of memory references, record and clear reference bits.

Page is in the working set if some of the bits are set.

CS3106: Operating Systems (20 decks)

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