Lecture (Chapter 10)

Presented By
Firoz Mahmud
Assistant Professor
Dept. of Computer Science & Engineering
Rajshahi University of Engineering & Technology
 Background
 Demand Paging
 Copy-on-Write
 Page Replacement
 Allocation of Frames
 Thrashing
 Memory-Mapped Files
 Allocating Kernel Memory
 Other Considerations
 Operating-System Examples
 To describe the benefits of a virtual memory
system.
 To explain the concepts of demand paging,

page-replacement algorithms, and allocation of
page frames.
 To discuss the principle of the working-set

model.
 Virtual memory – separation of user logical memory from
physical memory.
 Only part of the program needs to be in memory for execution.
 Logical address space can therefore be much larger than
physical address space.
 Allows address spaces to be shared by several processes.
 Allows for more efficient process creation.
 Virtual memory can be implemented via:

 Demand paging
 Demand segmentation
 A demand-paging system is similar to a paging system with
swapping.
 Processes reside on secondary memory (which is usually a
disk).
 When we want to execute a process, we swap it into memory.
Rather than swapping the entire process into memory.
 Lazy swapper – never swaps a page into memory unless
page will be needed
 Swapper that deals with pages is a pager.
 We thus use pager, rather than swapper, in connection with
demand paging.
 Bring a page into memory only when it is needed
 Less I/O needed
 Less memory needed
 Faster response
 More users
 Page is needed  reference to it

 invalid reference  abort
 not-in-memory  bring to memory
 When a process is to be swapped
in, the pager guesses which pages
will be used before the process is
swapped out again.
 Instead of swapping in a whole
process, the pager brings only those
necessary pages into memory.
 Thus, it avoids reading into memory
pages that will not be used anyway,
decreasing the swap time and the
amount of physical memory needed.
 With each page table entry a valid–invalid bit is associated
(v  in-memory, i  not-in-memory)
 Initially valid–invalid bit is set to i on all entries
 Example of a page table snapshot:
Frame # valid-invalid bit
v
v
v
v
i
….
i
i
page table
 During address translation, if valid–invalid bit in page table entry
is I  page fault
 If there is a reference to a page, first reference to that page will
trap to operating system:
page fault
1. Operating system looks at another table to decide:
 Invalid reference  abort
 Just not in memory
2. Get empty frame
3. Swap page into frame
4. Reset tables
5. Set validation bit = v
6. Restart the instruction that caused the page fault
 Restart instruction
 block move
 auto increment/decrement location

 Page Fault Rate 0  p  1.0
 if p = 0 no page faults
 if p = 1, every reference is a fault
 Effective Access Time (EAT)

EAT = (1 – p) x memory access
+ p (page fault overhead
+ swap page out
+ swap page in
+ restart overhead)
 Memory access time = 200 nanoseconds
 Average page-fault service time = 8 milliseconds
 EAT = (1 – p) x 200 + p (8 milliseconds)

= (1 – p x 200 + p x 8,000,000
= 200 + p x 7,999,800
 If one access out of 1,000 causes a page fault, then

EAT = 8.2 microseconds.
This is a slowdown by a factor of 40!!
 Prevent over-allocation of memory by modifying
page-fault service routine to include page
replacement.
 Use modify (dirty) bit to reduce overhead of page

transfers – only modified pages are written to disk
 Page replacement completes separation between

logical memory and physical memory – large virtual
memory can be provided on a smaller physical
memory
1. Find the location of the desired page on disk
2. Find a free frame:

- If there is a free frame, use it
- If there is no free frame, use a page
replacement algorithm to select a victim frame
3. Bring the desired page into the (newly) free frame;

update the page and frame tables
4. Restart the process

 Want lowest page-fault rate
 Evaluate algorithm by running it on a particular

string of memory references (reference string) and
computing the number of page faults on that string
 In all our examples, the reference string is
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
 The simplest page-replacement algorithm.
 When a page must be replaced, the oldest page
is chosen.
 We can create a FIFO queue to hold all pages in
memory.
 We replace the page at the head of the queue.
 When a page is brought into memory, we insert
it at the tail of the queue.
 Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
 3 frames (3 pages can be in memory at a time per process)
1 1 4 5
2 2 1 3 9 page faults
3 3 2 4
 4 frames
1 1 5 4
2 2 1 5 10 page faults
3 3 2
4 4 3
 Belady’s Anomaly: more frames  more page faults

 Replace page that will not be used for longest period of time
 4 frames example
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1 4
2 6 page faults
3
 How do you know this?4 5
 Used for measuring how well your algorithm performs

 Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1 1 1 1 5
2 2 2 2 2
3 5 5 4 4
4 4 3 3 3
 Counter implementation
 Every page entry has a counter; every time page is
referenced through this entry, copy the clock into the
counter
 When a page needs to be changed, look at the counters
to determine which are to change
 Stack implementation – keep a stack of
page numbers in a double link form:
 Page referenced:
move it to the top
requires 6 pointers to be changed
 No search for replacement
 Reference bit
 With each page associate a bit, initially = 0
 When page is referenced bit set to 1
 Replace the one which is 0 (if one exists)
 We do not know the order, however
 Second chance
 Need reference bit
 Clock replacement
 If page to be replaced (in clock order) has reference bit = 1 then:
 set reference bit 0
 leave page in memory
 replace next page (in clock order), subject to same rules
 Keep a counter of the number of references that
have been made to each page
 LFU Algorithm: replaces page with smallest

count
 MFU Algorithm: based on the argument that the

page with the smallest count was probably just
brought in and has yet to be used

Lecture (Chapter 10)

Uploaded by

Copyright:

Available Formats

Lecture (Chapter 10)

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture (Chapter 10)

Uploaded by

Copyright:

Available Formats

Presented By

 To explain the concepts of demand paging,

 To discuss the principle of the working-set

 Virtual memory can be implemented via:

 Page is needed  reference to it

 auto increment/decrement location

 Effective Access Time (EAT)

 Average page-fault service time = 8 milliseconds

 EAT = (1 – p) x 200 + p (8 milliseconds)

 If one access out of 1,000 causes a page fault, then

 Use modify (dirty) bit to reduce overhead of page

 Page replacement completes separation between

2. Find a free frame:

3. Bring the desired page into the (newly) free frame;

4. Restart the process

 Evaluate algorithm by running it on a particular

 In all our examples, the reference string is

 Belady’s Anomaly: more frames  more page faults

 How do you know this?4 5

 Used for measuring how well your algorithm performs

 LFU Algorithm: replaces page with smallest

 MFU Algorithm: based on the argument that the

You might also like