Unit 4_Part 2

Basic Knowledge
● 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;
hence more programs run at the same time
4 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; hence, each user program runs faster

2
 Virtual Memory
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
● Virtual memory can be implemented via:
● Demand paging
● Demand segmentation

3
Virtual Memory That is Larger Than Physical Memory

4
 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

5
Shared Library Using Virtual Memory

6
 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
● Swapper that deals with pages is a
pager

7
 Basic Concepts
● 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 in
only those “guessed” pages into memory
● Need new MMU functionality to implement demand paging.
Need to distinguish between the pages that are in memory and
the pages that are on the disk. Use a variation of the
valid-invalid scheme used for protection (see next slide)
● 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

8
 Valid-Invalid Bit
● 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:

● During MMU address translation, if valid–invalid bit in page

table entry is i ⇒ page fault

9
Page Table When Some Pages are Not in Main Memory

10
 Page Fault
If there is a reference to a page, first reference to
that page will trap to operating system:

page fault

Actions when a page fault occurs

1. Operating system looks at another table to decide:
● Invalid reference ⇒ abort
● Just not in memory. Go to step (2).
2. Find free frame
3. Swap page into frame via scheduled disk operation
4. Reset tables to indicate page now in memory
Set validation bit = v
5. Restart the instruction that caused the page fault

11
Steps in Handling a Page Fault

12
 Aspects of Demand Paging
● Pure demand paging – start process with no pages in memory
● OS sets instruction-pointer to the first instruction of the
process, non-memory-resident -> page fault
● And for every other process pages on first access
● 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
● The two numbers may reside in two different pages
● Hardware support needed for demand paging
● Page table with valid / invalid bit
● Secondary memory (swap device with swap space)
● Instruction restart

13
 Instruction Restart
● Consider an instruction that could access several different
locations
● Block move
● Page fault during the move
● Restart the whole operation?
● What if source and destination overlap?

● Several solution. Simplest one is to figure out all the pages

that are needed to execute the instruction to completion and
ensure that these pages are in memory before the instruction
starts executing.

14
 Stages in 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 I/O 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

15
 Stages in Demand Paging (Cont.)
Stages in Demand Paging (Cont.)

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
10. Correct the page table and other tables to show page is
now in memory
11. Wait for the CPU to be allocated to this process again
12. Restore the user registers, process state, and new page
table, and then resume the interrupted instruction

16
 Performance of Demand Paging
● Three major activities
● Service the interrupt – careful coding means just several
hundred instructions needed
● Read in the page – lots of time
● Restart the process – again just a small amount of time
● Page Fault Rate 0 ≤ p ≤ 1
● 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 )

17
 EAT Example
● 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!!
● If want performance degradation < 10 percent
● 220 > 200 + 7,999,800 x p
20 > 7,999,800 x p
● p < .0000025
● < one page fault in every 400,000 memory accesses

18
 Demand Paging Optimizations
● Swap space I/O faster than file system I/O even if on the same device
● Swap allocated in larger chunks, less management needed than file
system
● Copy entire process image to swap space at process load time
● Then page in and out of swap space
● Used in older BSD Unix
● Demand page in from program binary on disk, but discard rather than
paging out when freeing frame
● Used in Solaris and current BSD
● Still need to write to swap space
4 Pages not associated with a file (like stack and heap) –
anonymous memory
4 Pages modified in memory but not yet written back to the file
system

19
 Demand Paging in Mobile Systems
● Typically don’t support swapping
● Instead, demand page from file system and reclaim
read-only pages (such as code)

20
 Copy-on-Write
● Copy-on-Write (COW) allows both parent and child processes to initially
share the same pages in memory
● If either process modifies a shared page, only then is the page copied
● COW allows more efficient process creation as only modified pages are
copied
● In general, free pages are allocated from a pool of zero-fill-on-demand
pages (pages whose content has been zeroed out before allocation)
● Pool should always have free frames for fast demand page execution
4 Don’t want to have to free a frame as well as other processing on
page fault
● vfork() variation on fork() system call has parent suspend and
child using copy-on-write address space of parent
● Designed to have child call exec()
● Very efficient

21
Before and after Process 1 Modifies Page C

Before

After

22
 Page Replacement
● Page replacement occurs when:
● A page fault occurs and we need to bring the desired
page into memory
● There are NO free frames.
● Page replacement – find some page in memory, but not
really in use, page it out
● Algorithm – decide which frame to free
● Performance – want an algorithm which will result in
minimum number of page faults
● Same page may be brought into memory several times

23
 Need For Page Replacement
All frames are used. No free fames. User 2 needs B

24
 Page Replacement (Cont.)

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

transfers – only modified pages are written to back to
disk
● Page replacement completes separation between
logical memory and physical memory – large virtual
memory can be provided on a smaller physical
memory

25
 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:
- 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

26
Page Replacement

27
 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

28
Graph of Page Faults Versus The Number of Frames

29
 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

● How to track ages of pages?

● Just use a FIFO queue

30
 Number of Frames vs Page Faults

● One would expect that the more frames are

allocated to a process the fewer page faults
● Consider the reference string:
1,2,3,4,1,2,5,1,2,3,4,5
● How many page faults if we have 3 frames?
● How many page faults if we have 4 frames?

31
 Belady’s Anomaly

● If we use FIFO for page replacement we can encounter the

anomaly that more frames may lead to more page faults
● FIFO Illustrating Belady’s Anomaly

32
 Optimal Algorithm
● Replace page that will not be used for longest period of time
● With 3 frame, 9 is optimal for the example reference.

● How do you know which page will not be used for longest period
of time
● Can’t read the future
● Used mainly for measuring how well a given algorithm performs

33
 Least Recently Used (LRU) Algorithm
● Use past knowledge rather than future
● Replace page that has not been used for the longest period 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 do we implement?

34
 LRU Algorithm (Cont.)
● Counter (time-of-use) implementation
● Every page-table entry has a counter associated with it; every time
a page is referenced through this entry, the content of the clock is
copied into the counter
● We replace the page with the smallest time value.
4 Search through table needed
● Stack implementation
● Keep a stack of page numbers in a double link form:
● Page referenced:
4 move it to the top
4 requires 6 pointers to be changed
● No search for replacement
● LRU needs special hardware and is still slow
● LRU and OPT are cases of stack algorithms that don’t suffer from
Belady’s Anomaly

35
 Stack Algorithm Example
Use of a stack to record the most recent page references

36
 Effective Access time (EAT)
● A page fault occurs when the referenced page is not found in the main memory.
● Page fault handling routine is executed on the occurrence of page fault.
● The time taken to service the page fault is called as page fault service time.
● Effective Access time-
● In a multilevel paging scheme using TLB without any possibility of page fault,
effective access time is given by-

37
 Effective Access time (EAT)
● In a multilevel paging scheme using TLB with a possibility of page fault, effective
access time is given by-

38
 Practice Problems Based on Page Faults

● Problem-01:
● Let the page fault service time be 10 ms in a computer with average
memory access time being 20 ns. If one page fault is generated for every
106 memory accesses, what is the effective access time for the memory?
a) 21 ns
b) 30 ns
c) 23 ns
d) 35 ns

39
 Practice Problems Based on Page Faults

● Solution-
● Given-
● Page fault service time = 10 ms
● Average memory access time = 20 ns
● One page fault occurs for every 106 memory accesses
● Page Fault Rate-
It is given that one page fault occurs for every 106 memory accesses.
Thus,
Page fault rate = 1 / 106 = 10-6

40
 Practice Problems Based on Page Faults

● Effective Access Time With Page Fault-

● It is given that effective memory access time without page fault = 20 ns.
● Now, substituting values in the above formula, we get-
● Effective access time with page fault
= Page fault rate x { Effective Access time without page fault + Page fault
service time } + (1 – Page fault rate ) x {Effective Access time without
page fault }
= 10-6 x { 20 ns + 10 ms } + ( 1 – 10-6 ) x { 20 ns }
= 10-6 x 10 ms + 20 ns
= 10-5 ms + 20 ns
= 10 ns + 20 ns
= 30 ns
● Thus, Option (B) is correct.

41
 Practice Problems Based on Page Faults

● Problem-02:
● Suppose the time to service a page fault is on the average 10 milliseconds,
while a memory access takes 1 microsecond. Then, a 99.99% hit ratio
results in average memory access time of-
a) 1.9999 milliseconds
b) 1 millisecond
c) 9.999 microseconds
d) 1.9999 microseconds
e) None of these

42
 Practice Problems Based on Page Faults

● Solution-
● Given-
● Page fault service time = 10 msec
● Average memory access time = 1 μsec
● Hit ratio = 99.99% = 0.9999
● Page Fault Rate-
● Page fault rate
= 1 – Hit ratio
= 1 – 0.9999
= 0.0001

43
 Practice Problems Based on Page Faults

● Effective Access Time With Page Fault-

● It is given that effective memory access time without page fault =
1 μsec.
● Substituting values in the above formula, we get-
● Effective access time with page fault
= Page fault rate x { Effective Access time without page fault + Page
fault service time } + (1 – Page fault rate ) x {Effective Access time
without page fault }
= 0.0001 x { 1 μsec + 10 msec } + 0.99999 x 1 μsec
= 0.0001 μsec + 0.001 msec + 0.9999 μsec
= 1 μsec + 0.001 msec
= 1 μsec + 1 μsec
= 2 μsec or 0.002 msec
● Thus, Option (E) is correct.

44
 Practice Problems Based on Page Faults

● Problem-03:
● If an instruction takes i microseconds and a page fault takes an additional j
microseconds, the effective instruction time if on the average a page fault
occurs every k instruction is-
a) i+j/k
b) i+jxk
c) (i + j) / k
d) (i + j) x k

45
 Practice Problems Based on Page Faults

● Solution-
● Given-
● Page fault service time = j μsec
● Average memory access time = i μsec
● One page fault occurs every k instruction
● Page Fault Rate-

● It is given that one page fault occurs every k instruction.

Thus, Page fault rate = 1 / k

46
 Practice Problems Based on Page Faults

● Effective Access Time With Page Fault-

● It is given that effective memory access time without page fault = i μsec
● Now, substituting values in the above formula, we get-
● Effective access time with page fault
= Page fault rate x { Effective Access time without page fault + Page
fault service time } + (1 – Page fault rate ) x {Effective Access time
without page fault }
= (1 / k) x { i μsec + j μsec } + ( 1 – 1 / k) x { i μsec }
= j / k μsec + i μsec
= i + j / k μsec
● Thus, Option (A) is correct.

47
 Practice Problems Based on Page Faults

● Problem-04:
● Consider a system with a two-level paging scheme in which a regular
memory access takes 150 nanoseconds and servicing a page fault takes 8
milliseconds. An average instruction takes 100 nanoseconds of CPU time
and two memory accesses. The TLB hit ratio is 90% and the page fault rate
is one in every 10,000 instructions. What is the effective average instruction
execution time?
a) 645 nanoseconds
b) 1050 nanoseconds
c) 1215 nanoseconds
d) 1230 nanoseconds
e) None of these

48
 Practice Problems Based on Page Faults

● Solution-
● Given-
● Number of levels of page table = 2
● Main memory access time = 150 ns
● Page fault service time = 8 msec
● Average instruction takes 100 ns of CPU time and 2 memory accesses
● TLB Hit ratio = 90% = 0.9
● Page fault rate = 1 / 104 = 10-4
● Assume TLB access time = 0 since it is not given in the question.
● Also, TLB access time is much less as compared to the memory access
time.

49
 Practice Problems Based on Page Faults

● Effective Access Time Without Page Fault-

● Substituting values in the above formula, we get-

● Effective memory access time without page fault
= Hit ratio of TLB x { Access time of TLB + Access time of main
memory } + Miss ratio of TLB x {Access time of TLB + (L+1) x
Access time of main memory }
= 0.9 x { 0 + 150 ns } + 0.1 x { 0 + (2+1) x 150 ns }
= { 0.9 x 150 ns } + { 0.1 x 450 ns }
= 135 ns + 45 ns
= 180 ns

50
 Practice Problems Based on Page Faults

● Effective Access Time With Page Fault-

● Substituting values in the formula, we get-
● Effective access time with page fault
= Page fault rate x { Effective Access time without page fault + Page fault
service time } + (1 – Page fault rate ) x {Effective Access time without
page fault }
= 10-4 x { 180 ns + 8 msec } + (1 – 10-4) x 180 ns
= 8 x 10-4 msec + 180 ns
= 8 x 10-7 sec + 180 ns
= 800 ns + 180 ns
= 980 ns

51
 Practice Problems Based on Page Faults

● Effective Average Instruction Execution Time-

● Effective Average Instruction Execution Time
= 100 ns + 2 x Effective memory access time with page fault
= 100 ns + 2 x 980 ns
= 100 ns + 1960 ns
= 2060 ns
● Thus, Option (E) is correct.

52
 Practice Problems Based on Page Faults

● Problem-05:
● A demand paging system takes 100 time units to service a page fault and
300 time units to replace a dirty page. Memory access time is 1 time unit.
The probability of a page fault is p. In case of a page fault, the probability of
page being dirty is also p. It is observed that the average access time is 3
time units. Then the value of p is-
a) 0.194
b) 0.233
c) 0.514
d) 0.981
e) None of these

53
 Practice Problems Based on Page Faults

● Solution-
● Given-
● Page fault service time = 100 time units
● Time taken to replace dirty page = 300 time units
● Average memory access time = 1 time unit
● Page fault rate = p
● Probability of page being dirty = p
● Effective access time = 3 time units

54
 Practice Problems Based on Page Faults

● Now, According to question-

On solv3 time units = p x { 1 time unit + p x { 300 time units } + (1 – p) x {
100 time units } } + (1 – p) x { 1 time unit }
3 = p x { 1 + 300p + 100 – 100p } + (1 – p)
3 = p x { 101 + 200p } + (1 – p)
3 = 101p + 200p2 + 1 – p
3 = 100p + 200p2 + 1
200p2 + 100p – 2 = 0
● solving this quadratic equation,
we get p = 0.019258
● Thus, Option (E) is correct.

55
 Page-Buffering Algorithms
Other procedures are often used in addition to a specific
page-replacement algorithm. Several schemes:

● Keep a pool of free frames

● When a page fault occurs, a victim page is chosen as before.
● The desired page that needs to brought into memory is read into
one of the free frame from the pool before the victim page is
written out. Start the process immediately.
● When the victim page is finally written out, the frame is added to
pool of free framed
● Maintain a list of modified pages
● Whenever a backing store is idle, a modified page is selected and
written to the disk and its modified bit is reset.
● Possibly, keep a pool of free frame and remember which page was in
each frame
● If page is referenced again before the frame is reused, no need to
load contents again from disk
● Generally useful to reduce penalty if wrong victim frame selected

56
 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

57
 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

58
 Thrashing
● If a process does not have “enough” pages, the page-fault
rate is very high
● Page fault to get page
● Replace existing frame
● But quickly need replaced frame back
● This leads to:
4 Low CPU utilization
4 Operating system thinking that it needs to increase
the degree of multiprogramming
4 Another process added to the system
● Thrashing ≡ a process is busy swapping pages in and out

59
Thrashing (Cont.)

60