• Click to edit Master text styles
– Second level
Operating Systems Concepts
• Third level
– Fourth level
» Fifth level
1
Why Virtual Memory?
•• Click
Assume that we have, say 8 frames available, but the
to edit Master text styles
shortest program needs more than that. Those 8 frames
– Second level
will s tay un-used
• Third level
• m tha
A prog–raFourth t needs more memory than the total
level
physical m»em Fifth
orylevel
available, such program can not execute
at all
• In each program, some parts are executing more often,
while others are rarely used.
For example:
Those parts of a program that handle errors in the data. If
the data happe ns to be correct (which is likely), those parts
will not be used, but they occu py some memory
2
Virtual Memory
• Click to edit Master text styles
– Second level
• simu
Also call•edThird lated memory
level
• Virtual mem–orFourth
y – selevel
paration of user logical memory from physical
memory » Fifth level
Keep the whole logical space of the process on disk
Only part of the program needs to be in memory for
execution(that mean not require the complete program to in the
memory)
Logical address space can therefore be much larger than physical
address space(the total size of program in lager the total size of
main memory available )
Allows address spaces to be shared by several processes
Allows for more efficient process creation
• Can be implemented via demand paging
3
Virtual Memory That is Larger Than Physical Memory
• Click to edit Master text styles
– Second level
• Third level
– Fourth level
» Fifth level
4
Demand Paging
• Bring a page into memory only when it is
• Click to edit Master text styles
needed
– Second level
• Less I/O needed
Third level
Less memory
– Fourth level needed
Faster» response
Fifth level
More users
• A page is needed when there is a reference to
it in the process (user’s program)
invalid reference abort
not-in-memory page-fault
5
• The logical (virtual) space is divided into pages (as in paging)
• The physical space is divided into frames (as in paging)
• The swapping disk/drum holds the logical spaces of all
processes being executed
• Click to edit Master text styles
We will assume that the logical space of a process occupies a
– Second
contigulevel
ous area on disk, and consecutive pages occupy
• oThird
c nsecu level
tive blocks on the disk
– Fourth level
• Physical memory holds only some of the pages (part of the
» Fifth level
logical space)
6
Page-Fault Handler
1. Using the given page# (of the logical address),
the page-fault handler finds the block
• Click
conto
taedit
iningMaster
the detext
sirestyles
d page on the disk
– Second level
• lThird
2. Se a (victim) frame (out of the frames
ect level
alloc–aFourth to the process) from the FT
ted level
» Fifth level
3. Using the entry, for the selected frame in FT,
move the contents of the frame from physical
memory and store it back to its location on
disk (this is needed only if the data was
modified)
7
Page-Fault Handler cont.
Move
•4.Click editdesired
to the page
Master text (block) from disk into
styles
–the selected
Second level frame in physical memory
• Third level
5. Update thelevel
– Fourth FT (put disk address of page)
» Fifth level
6. Update the PT (put v and frame#)
7. Start the calculation of the physical address
(as discussed before)
8
Page Fault Handling cont.
• Click to edit Master text styles
– Second level
• Third level
– Fourth level
» Fifth level
9
Page Replacement
• Problems with replacing pages include:
• Click to edit
1. How Masteriftext
to decide stylesneeds to be written to disk
the page
(i.e. level
– Second the page has been modified/updated from its
• original
Third levelversion in memory)
– Fourth level
2. How to select
» Fifth levelthe victim frame that will be replaced in
memory
1
0
Solution to Problem 1
• The dirty bit (modify bit) plays a good role
• Click to edit Master text styles
• –ASecond e with every memory’s frame a dirty bit and
ssociatlevel
set• itThird . Whenever the contents of the frame is
to 0level
modifi–ed Fourth level
(via an instruction that stores something),
then set t»he Fifth level
dirty bit to 1
• If the dirty bit for a particular frame is 1, then swap it
out to disk
• Otherwise, no need to swap it out to disk, and the OS
saves a lot of time (because disk access is mechanical
and thus very time consuming)
1
1
Page Fault Rate
•• Click
Equals to: Master text styles
to edit
– Second level
How many page faults can occur
• Third level
– Fourth level
How many total pages were requested
» Fifth level
• Note: It is expected that an increase in the
number of frames allocated to the process
should result in a decrease of the page fault
rate
1
2
Terminology
• Suppose that a process P1 makes requests
• Click to edit Master text styles
for the following
– Second level
logical addresses:
• Third level
673, 123, 3467,
– Fourth level
4515, 4012, 2000, 3447
» Fifth level
• Also assume the page size is 1000
• Therefore: 673/1000 = 0, remainder=673
• Then the process is really making reference to
the following pages:
0 0 3 4 4 2 3
1
3
Terminology cont.
•• Click say
We to that
edit Master text stylesstring for process
the reference
–P1 is: level
Second
• Third level
0 0
– Fourth level 3 4 4 2 3
» Fifth level
• And the page fault rate will be equal to:
# of page faults / 7 (# of references)
1
4
Solution to Problem 2
• • We
Clickwill discuss
to edit the
Master textfollowing
styles algorithms
for selection
– Second level of the victim for replacement
• Third level
¸ First-In-First-Out
– Fourth level
» Fifth level
(FIFO) Algorithm
¸ Least Recently Used (LRU)
Algorithm
¸ Optimal Algorithm
1
5
a. First In First Out (FIFO)
•• Click
Also tocalled:
edit Master text styles
– Second level
Least Recently Swapped In
• Third level
– Fourth level
• The firs»tFifth me that was referenced will
fralevel
be the first out (the victim for
replacement)
1
6
Example # 1
•• Click to editaMaster
Suppose process styles size is 5 pages
text whose
was allocated
– Second level 3 frames, and the process
• Third level
has the reference
– Fourth level string:
» Fifth level
1 2 3 4 1 2 5 1 2 3 4 5
• Calculate the page fault rate if the FIFO
algorithm as used for victim replacement
1
7
Example # 1 solution
• FIFO using 3 frames
• Click to edit Master text styles
• Reference string: 1 2 3 4 1 2 5 1 2 3 4 5
– Second level
• Third level
1 2 3 4 1 2 5 1 2 3 4 5
– Fourth level
Frame #1 »1Fifth
1 level
1 4 4 4 5 5 5 5 5 5
Frame #2 2 2 2 1 1 1 1 1 3 3 3
Frame #3 3 3 3 2 2 2 2 2 4 4
fault f f f f f f f - - f f -
Fault Rate = 9 / 12
1
8
Example # 2
•• Click to editExample
Repeat #1styles
Master text assuming that the
Second levelwas
–process allocated 4 frames and
• Third level
FIFO– victim
Fourth level
replacement algorithm is
used » Fifth level
1
9
Example # 2 solution
• FIFO using 4 frames
• Click to edit Master text styles
• Reference string: 1 2 3 4 1 2 5 1 2 3 4 5
– Second level
• Third level
1 2 3 4 1 2 5 1 2 3 4 5
– Fourth level
» Fifth level
Frame #1 1 1 1 1 1 1 5 5 5 5 4 4
Frame #2 2 2 2 2 2 2 1 1 1 1 5
Frame #3 3 3 3 3 3 3 2 2 2 2
Frame #4 4 4 4 4 4 4 3 3 3
fault f f f f - - f f f f f f
Fault Rate = 10 / 12 2
0
Notice
•• Click
An toincrease in the
edit Master text number
styles of frames
–allocated
Second level to the process has resulted in
• Third level
– Fourth level of the page fault rate, and
an increase
not a decrease
» Fifth level
as we should expect
• This is called the Belady Effect (after the
first person to discover it)
2
1
b. Least Recently Used (LRU)
•• Click
Thetophilosophy is: previous
edit Master text styles behavior is
–an indication
Second level of the future
• Third level
– Fourth level
• Therefore, replace the page that was
» Fifth level
the least recently referenced
• اﺑﻌﺪ ﻋﻤﻠﻴﻪ ﻓﻲ اﻟﻤﺎﺿﻲ
• It can be proved that LRU does not
suffer of the Belady Effect
2
2
Example # 3
•• Click to editExample
Repeat # styles
Master text 2 assuming that the
Second levelwas
–process allocated 4 frames and
• Third level
LRU –victim replacement
Fourth level
algorithm is
used » Fifth level
2
3
Example # 3 solution
• LRU using 4 frames
• Click to edit Master text styles
• Reference string: 1 2 3 4 1 2 5 1 2 3 4 5
– Second level
• Third level
1
– Fourth 2
level3 4 1 2 5 1 2 3 4 5
» Fifth level
Frame #1 1 1 1 1 1 1 1 1 1 1 1 5
Frame #2 2 2 2 2 2 2 2 2 2 2 2
Frame #3 3 3 3 3 5 5 5 5 4 4
Frame #4 4 4 4 4 4 4 3 3 3
fault f f f f - - f - - f f f
Fault Rate = 8/ 12 2
4
c. Optimal Algorithm
•• Click to editthe
Replace page
Master that
text will not be used
styles
for the level
– Second longest period of time
• Third level
• اﺑﻌﺪ ﻋﻤﻠﻴﻪ ﻓﻲ اﻟﻤﺴﺘﻘﺒﻞ
– Fourth level
» Fifth level
• How do you know this?
• That is why optimal algorithm is used
primarily for measuring how well your
algorithm performs
2
5
Optimal Algorithm Example
• Optimal Algorithm using 4 frames
• Click to edit Master text styles
• Reference string: 1 2 3 4 1 2 5 1 2 3 4 5
– Second level
• Third level
1
– Fourth 2
level3 4 1 2 5 1 2 3 4 5
» Fifth level
Frame #1 1 1 1 1 1 1 1 1 1 1 4 4
Frame #2 2 2 2 2 2 2 2 2 2 2 2
Frame #3 3 3 3 3 3 3 3 3 3 3
Frame #4 4 4 4 5 5 5 5 5 5
fault f f f f - - f - - - f -
Fault Rate = 6 / 12 2
6
HOMEWORK 1
• Suppose a process whose size is 5 pages was
allocated 3 frames, and the process has the
• Click to edit Master text styles
reference string:
– Second level
• Third level
2 1level5 2 4 5 3 2 5 2
2 3 – Fourth
» Fifth level
• Calculate the page fault rate if the FIFO was used
for victim replacement
• Calculate the page fault rate if the LRU was used
for victim replacement
• Calculate the page fault rate if the OPTIMAL was
used for victim replacement
2
7
HOMEWORK 2
•• Click
Consider page
to edit reference
Master string
text styles
1, 3,
– Second 0, 3, 5, 6, 3 with 3 page frames.
level
• Third level
Find the –number
Fourth level
of page faults.
» Fifth level
• Calculate the page fault rate if the FIFO was
used for victim replacement
• Calculate the page fault rate if the LRU was
used for victim replacement
• Calculate the page fault rate if the OPTIMAL
was used for victim replacement
2
8
HOMEWORK 3
•• Consider the Master
Click to edit page references
text styles
7, 0,–1,Second 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4 page frame.
2, 0, level
• Third level
Find number of page
– Fourth level
fault.
» Fifth
• Calculate the page level
fault rate if the LRU was used for
victim replacement
• Calculate the page fault rate if the OPTIMAL was used
for victim replacement
2
9
HOMEWORK 4
•• Click
Consider theMaster
to edit styles by the CPU in the
referenced
Pagestext
order arelevel
– Second
• Third
6, 7, 8,level
9, 6, 7, 1, 6, 7, 8, 9, 1 with 3 frames
– Fourth level
• Calculate the page
» Fifth levelfault rate if the FIFO was used for
victim replacement
• Calculate the page fault rate if the LRU was used for
victim replacement
• Calculate the page fault rate if the OPTIMAL was
used for victim replacement
3
0
HOMEWORK 5
• Consider the reference string
6• , 1,
Click
1, 2to, 0
edit
, 3 ,Master
4 , 6 , 0text
, 2 ,styles
1, 2 , 1, 2 , 0 , 3 , 2 , 1, 2 , 0
– Second level
or a memory with 3 frames and calculate number of
• Third level
page faults.
– Fourth level
» Fifth level
• Calculate the page fault rate if the FIFO was used
for victim replacement
• Calculate the page fault rate if the LRU was used
for victim replacement
• Calculate the page fault rate if the OPTIMAL was
used for victim replacement
3
1
