CIT11: Principles of Operating System

Principles of Operating
System
Course Code CIT11

Faculty of Computing and Information Technology

Computer Science Department
Spring, 2017/2018
These slides are based on lecture notes of the book’s author
& Portland University slides
& A. Frank - P. Weisberg slides
Wedad Al-Sorori 14 September 2017 Introduction 1/46
 CIT11: Principles of Operating System

Virtual Memory

• This lecture will cover the following topics:

• Background
• Demand Paging
• Page Replacement
• Allocation of Frames

Wedad Al-Sorori 14 September 2017 Introduction 2/46

 CIT11: Principles of Operating System

Objectives

• After completing this lecture, students will be able to:

• Describe the benefits of a virtual memory system

• Clarify the concepts of demand paging, page-replacement

algorithms, and allocation of page frames.
• Use and evaluate various page replacement algorithms.

Wedad Al-Sorori 14 September 2017 Introduction 3/46

 CIT11: Principles of Operating System

Background (1/3)
• Code needs to be in memory to execute, but entire program
rarely used
• Error code, unusual routines, large data structures
• Entire program code not needed at same time
• Consider ability to execute partially-loaded program
• Program no longer constrained by limits of physical memory
• Each program takes less memory while running -> more
programs run at the same time
• Increased CPU utilization and throughput with no increase in
response time or turnaround time
• Less I/O needed to load or swap programs into memory ->
each user program runs faster
Wedad Al-Sorori 14 September 2017 Introduction 4/46
 CIT11: Principles of Operating System

Background (2/3)
• 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
• More programs running concurrently
• Less I/O needed to load or swap processes

Wedad Al-Sorori 14 September 2017 Introduction 5/46

 CIT11: Principles of Operating System

Background (3/3)
• Virtual address space – logical view of how process is stored
in memory
• Usually start at address 0, contiguous addresses until end of space
• Meanwhile, physical memory organized in page frames
• MMU must map logical to physical
• Virtual memory can be implemented via:
• Demand paging
• Demand segmentation

Wedad Al-Sorori 14 September 2017 Introduction 6/46

 CIT11: Principles of Operating System

Virtual Memory That is Larger Than Physical

Memory

Wedad Al-Sorori 14 September 2017 Introduction 7/46

 CIT11: Principles of Operating System

Virtual Address Space

 Usually design logical address space for stack to start at Max
logical address and grow “down” while heap grows “up”
 Maximizes address space use
 Unused address space between the two is hole
 No physical memory needed until heap or stack grows
to a given new page
 Enables sparse address spaces with holes left for growth,
dynamically linked libraries, etc
 System libraries shared via mapping into virtual address
space
 Shared memory by mapping pages read-write into virtual
address space
 Pages can be shared during fork(), speeding process creation

Wedad Al-Sorori 14 September 2017 Introduction 8/46

 CIT11: Principles of Operating System

Shared Library Using Virtual Memory

Wedad Al-Sorori 14 September 2017 Introduction 9/46

 CIT11: Principles of Operating System

Demand Paging
• Could bring entire process into memory at load
time
• Or bring a page into memory only when it is
needed
• Less I/O needed, no unnecessary I/O
• Less memory needed
• Faster response
• More users
• Similar to paging system with swapping (diagram
on right)
• Page is needed  reference to it
• invalid reference  abort
• not-in-memory  bring to memory
• Lazy swapper – never swaps a page into
memory unless page will be needed
•Wedad
Swapper
Al-Sorori that deals with pages is14aSeptember
pager 2017 Introduction 10/46
 CIT11: Principles of Operating System

Basic Concepts
• With swapping, pager guesses which pages will be used before
swapping out again
• Instead, pager brings in only those pages into memory
• How to determine that set of pages?
• Need new MMU functionality to implement demand paging
• If pages needed are already memory resident
• No difference from non demand-paging
• If page needed and not memory resident
• Need to detect and load the page into memory from storage
• Without changing program behavior
• Without programmer needing to change code

Wedad Al-Sorori 14 September 2017 Introduction 11/46

 CIT11: Principles of Operating System

Valid-Invalid Bit
• With each page table entry a valid–invalid bit is associated
(v  in-memory – memory resident, i  not-in-memory)
• Initially valid–invalid bit is set to i on all entries
• Example of a page table snapshot:

• During MMU address translation, if valid–invalid bit in page table entry is i

Wedad Al-Sorori 14 September 2017 Introduction 12/46
 page fault
 CIT11: Principles of Operating System

Page Table When Some Pages Are Not in Main

Memory

Wedad Al-Sorori 14 September 2017 Introduction 13/46

 CIT11: Principles of Operating System

Page Fault
• If there is a reference to a page, first reference to that page will trap to
operating system:
page fault
[Link] system looks at another table to decide:
• Invalid reference  abort
• Just not in memory
[Link] free frame
[Link] page into frame via scheduled disk operation
[Link] tables to indicate page now in memory
Set validation bit = v
[Link] the instruction that caused the page fault

Wedad Al-Sorori 14 September 2017 Introduction 14/46

 CIT11: Principles of Operating System

Steps in Handling a Page Fault

Wedad Al-Sorori 14 September 2017 Introduction 15/46

 CIT11: Principles of Operating System

Aspects of Demand Paging

• Extreme case – start process with no pages in memory
• OS sets instruction pointer to first instruction of process, non-memory-
resident -> page fault
• And for every other process pages on first access
• Pure demand paging
• Actually, a given instruction could access multiple pages ->
multiple page faults
• Consider fetch and decode of instruction which adds 2 numbers from
memory and stores result back to memory
• Pain decreased because of locality of reference
• Hardware support needed for demand paging
• Page table with valid / invalid bit
• Secondary memory (swap device with swap space)
• Instruction restart
Wedad Al-Sorori 14 September 2017 Introduction 16/46
 CIT11: Principles of Operating System

Instruction Restart
• Consider an instruction that could access several different locations
• Block move

• Auto increment/decrement location

• Restart the whole operation?
• What if source and destination overlap?

Wedad Al-Sorori 14 September 2017 Introduction 17/46

 CIT11: Principles of Operating System

Performance of Demand Paging

• Stages in Demand Paging (worse case)
1. Trap to the operating system
2. Save the user registers and process state
3. Determine that the interrupt was a page fault
4. Check that the page reference was legal and determine the location of the page on the disk
5. Issue a read from the disk to a free frame:
1. Wait in a queue for this device until the read request is serviced
2. Wait for the device seek and/or latency time
3. Begin the transfer of the page to a free frame
6. While waiting, allocate the CPU to some other user
7. Receive an interrupt from the disk I/O subsystem (I/O completed)
8. Save the registers and process state for the other user
9. Determine that the interrupt was from the disk
[Link] the page table and other tables to show page is now in memory
[Link] for the CPU to be allocated to this process again
[Link] the user registers, process state, and new page table, and then resume the interrupted instruction

Wedad Al-Sorori 14 September 2017 Introduction 18/46

 CIT11: Principles of Operating System

What Happens if There is no Free Frame?

• Used up by process pages
• Also in demand from the kernel, I/O buffers, etc
• How much to allocate to each?
• Page replacement – find some page in memory, but not
really in use, page it out
• Algorithm – terminate? swap out? replace the page?
• Performance – want an algorithm which will result in
minimum number of page faults
• Same page may be brought into memory several times

Wedad Al-Sorori 14 September 2017 Introduction 19/46

 CIT11: Principles of Operating System

Page Replacement
• 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

Wedad Al-Sorori 14 September 2017 Introduction 20/46

 CIT11: Principles of Operating System

Need For Page Replacement

Wedad Al-Sorori 14 September 2017 Introduction 21/46

 CIT11: Principles of Operating System

Basic Page Replacement

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
- Write victim frame to disk if dirty

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

4. Continue the process by restarting the instruction that caused the trap
Note now potentially 2 page transfers for page fault – increasing EAT

Wedad Al-Sorori 14 September 2017 Introduction 22/46

 CIT11: Principles of Operating System

Page Replacement

Wedad Al-Sorori 14 September 2017 Introduction 23/46

 CIT11: Principles of Operating System

Page and Frame Replacement Algorithms

• Frame-allocation algorithm determines
• How many frames to give each process
• Which frames to replace
• Page-replacement algorithm
• Want lowest page-fault rate on both first access and re-access
• Evaluate algorithm by running it on a particular string of memory
references (reference string) and computing the number of page faults
on that string
• String is just page numbers, not full addresses
• Repeated access to the same page does not cause a page fault
• Results depend on number of frames available
• In all our examples, the reference string of referenced page numbers is
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
Wedad Al-Sorori 14 September 2017 Introduction 24/46
 CIT11: Principles of Operating System

Graph of Page Faults Versus The Number of

Frames

Wedad Al-Sorori 14 September 2017 Introduction 25/46

 CIT11: Principles of Operating System

First-In-First-Out (FIFO) Algorithm

• Reference string:
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
• 3 frames (3 pages can be in memory at a time per process)

15 page faults

• Can vary by reference string: consider

1,2,3,4,1,2,5,1,2,3,4,5
• Adding more frames can cause more page faults!
• Belady’s Anomaly

• Wedad
HowAl-Sorori
to track ages of pages?
14 September 2017 Introduction 26/46
• Just use a FIFO queue
 CIT11: Principles of Operating System

FIFO Illustrating Belady’s Anomaly

Wedad Al-Sorori 14 September 2017 Introduction 27/46

 CIT11: Principles of Operating System

Optimal Algorithm
• Replace page that will not be used for longest period of time
• 9 is optimal for the example
• How do you know this?
• Can’t read the future
• Used for measuring how well your algorithm performs

Wedad Al-Sorori 14 September 2017 Introduction 28/46

 CIT11: Principles of Operating System

Least Recently Used (LRU) Algorithm

(1/2)
• Use past knowledge rather than future
• Replace page that has not been used in the most amount of time
• Associate time of last use with each page

• 12 faults – better than FIFO but worse than OPT

• Generally good algorithm and frequently used
• But how to implement?

Wedad Al-Sorori 14 September 2017 Introduction 29/46

 CIT11: Principles of Operating System

LRU Algorithm (2/2)

• 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 find
smallest value
• Search through table needed
• 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
• But each update more expensive
• No search for replacement
• LRU and OPT are cases of stack
Wedad Al-Sorori algorithms
14 September 2017 that don’t have Belady’s
Introduction 30/46
 CIT11: Principles of Operating System

Use Of A Stack to Record Most Recent Page

References

Wedad Al-Sorori 14 September 2017 Introduction 31/46

 CIT11: Principles of Operating System

LRU Approximation Algorithms

• LRU needs special hardware and still slow
• Reference bit
• With each page associate a bit, initially = 0
• When page is referenced bit set to 1
• Replace any with reference bit = 0 (if one exists)
• We do not know the order, however
• Second-chance algorithm
• Generally FIFO, plus hardware-provided reference bit
• Clock replacement
• If page to be replaced has
• Reference bit = 0 -> replace it
• reference bit = 1 then:
• set reference bit 0, leave page in memory
• replace next page, subject to same rules
Wedad Al-Sorori 14 September 2017 Introduction 32/46
 CIT11: Principles of Operating System

Second-Chance (clock) Page-Replacement Algorithm

Wedad Al-Sorori 14 September 2017 Introduction 33/46

 CIT11: Principles of Operating System

Enhanced Second-Chance Algorithm

• Improve algorithm by using reference bit and modify bit (if
available) in concert
• Take ordered pair (reference, modify)
1.(0, 0) neither recently used not modified – best page to replace
2.(0, 1) not recently used but modified – not quite as good, must write out
before replacement
3.(1, 0) recently used but clean – probably will be used again soon
4.(1, 1) recently used and modified – probably will be used again soon and
need to write out before replacement
• When page replacement called for, use the clock scheme but use
the four classes replace page in lowest non-empty class
• Might need to search circular queue several times

Wedad Al-Sorori 14 September 2017 Introduction 34/46

 CIT11: Principles of Operating System

Counting Algorithms
• Keep a counter of the number of references that have been
made to each page
• Not common

• Lease Frequently Used (LFU) Algorithm: replaces page with

smallest count

• Most Frequently Used (MFU) Algorithm: based on the

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

Wedad Al-Sorori 14 September 2017 Introduction 35/46

 CIT11: Principles of Operating System

Page-Buffering Algorithms
• Keep a pool of free frames, always
• Then frame available when needed, not found at fault time
• Read page into free frame and select victim to evict and add
to free pool
• When convenient, evict victim
• Possibly, keep list of modified pages
• When backing store otherwise idle, write pages there and set
to non-dirty
• Possibly, keep free frame contents intact and note what is in
them
• If referenced again before reused, no need to load contents
again from disk
• Generally
Wedad Al-Sorori useful to reduce penalty
14 September 2017 if wrong victim frame
Introduction 36/46
 CIT11: Principles of Operating System

Applications and Page Replacement

• All of these algorithms have OS guessing about future page
access
• Some applications have better knowledge – i.e. databases
• Memory intensive applications can cause double buffering
• OS keeps copy of page in memory as I/O buffer
• Application keeps page in memory for its own work
• Operating system can given direct access to the disk, getting out
of the way of the applications
• Raw disk mode
• Bypasses buffering, locking, etc

Wedad Al-Sorori 14 September 2017 Introduction 37/46

 CIT11: Principles of Operating System

Allocation of Frames
• Each process needs minimum number of frames
• Example: IBM 370 – 6 pages to handle SS MOVE instruction:
• Instruction is 6 bytes, might span 2 pages
• 2 pages to handle from
• 2 pages to handle to
• Maximum of course is total frames in the system
• Two major allocation schemes
• Fixed allocation
• Priority allocation
• Many variations

Wedad Al-Sorori 14 September 2017 Introduction 38/46

 CIT11: Principles of Operating System

Fixed Allocation
• Equal allocation – For example, if there are 100 frames (after
allocating frames for the OS) and 5 processes, give each
process 20 frames
• Keep some as free frame buffer pool
• Proportional allocation – Allocate according to the size of
process
• Dynamic as degree of multiprogramming, process sizes
change
si size of process pi
S   si
m total number of frames
s
ai allocation for pi  i m
S

Wedad Al-Sorori 14 September 2017 Introduction 39/46

 CIT11: Principles of Operating System

Priority Allocation
• Use a proportional allocation scheme using priorities rather than
size

• If process Pi generates a page fault,

• Select for replacement one of its frames
• Select for replacement a frame from a process with lower
priority number

Wedad Al-Sorori 14 September 2017 Introduction 40/46

 CIT11: Principles of Operating System

Global vs. Local Allocation

• Global replacement – process selects a replacement frame
from the set of all frames; one process can take a frame from
another
• But then process execution time can vary greatly
• But greater throughput so more common
• Local replacement – each process selects from only its own set
of allocated frames
• More consistent per-process performance
• But possibly underutilized memory

Wedad Al-Sorori 14 September 2017 Introduction 41/46

 CIT11: Principles of Operating System

Allocating Kernel Memory

• Treated differently from user memory
• Often allocated from a free-memory pool
• Kernel requests memory for structures of varying sizes
• Some kernel memory needs to be contiguous
• I.e. For device I/O

Wedad Al-Sorori 14 September 2017 Introduction 42/46

 CIT11: Principles of Operating System

Buddy System
• Allocates memory from fixed-size segment consisting of physically-
contiguous pages
• Memory allocated using power-of-2 allocator
• Satisfies requests in units sized as power of 2
• Request rounded up to next highest power of 2
• When smaller allocation needed than is available, current chunk split into two
buddies of next-lower power of 2
• Continue until appropriate sized chunk available

• For example, assume 256KB chunk available, kernel requests 21KB

• Split into AL and AR of 128KB each
• One further divided into BL and BR of 64KB
• One further into CL and CR of 32KB each – one used to satisfy request

• Advantage – quickly coalesce unused chunks into larger chunk

• Disadvantage - fragmentation
Wedad Al-Sorori 14 September 2017 Introduction 43/46
 CIT11: Principles of Operating System

Buddy System Allocator

Wedad Al-Sorori 14 September 2017 Introduction 44/46

 CIT11: Principles of Operating System

Summary
• Virtual memory separates user logical memory from physical
memory that provides the ability to let only part of the program
needs to be in memory for execution.
• Virtual memory can be implemented via demand paging or
demand segmentation.
• Virtual address space is a logical view of how process is stored in
memory.
• Page replacement completes separation between logical memory
and physical memory – large virtual memory can be provided on
a smaller physical memory.

Wedad Al-Sorori 14 September 2017 Introduction 45/46

 CIT11: Principles of Operating System

Assignment
• Answer and submit questions in assignment12 that was attached
with this lecture on CLMS.

Wedad Al-Sorori 14 September 2017 Introduction 46/46

 CIT11: Principles of Operating System

Thanks

Wedad Al-Sorori 14 September 2017 Introduction 47/46