صفحه 1:
Virtual Memory
Chapter 8
صفحه 2:
Hardware and Control
Structures
* Memory references are dynamically
translated into physical addresses at run
time
~ A process may be swapped in and out of main
memory such that it occupies different
regions
۰ A process may be broken up into pieces
that do not need to located contiguously
in main memory
* All pieces of a process do not need to be
loaded in main memory during execution
2
صفحه 3:
Execution of a Program
° Operating system brings into
main memory a few pieces of the
program
° Resident set - portion of process
that is in main memory
° An interrupt is generated when
an address is needed that is not
in main memory
° Operating system places the
process in a blocking state
صفحه 4:
Execution of a Program
° Piece of process that contains the
logical address is brought into
main memory
~ Operating system issues a disk I/O
Read request
- Another process is dispatched to run
while the disk I/O takes place
~ An interrupt is issued when disk I/O
complete which causes the
operating system to place the
affected process in the Ready state
4
صفحه 5:
Advantages of
Breaking up a Process
* More processes may be
maintained in main memory
~ Only load in some of the pieces of
each process
~ With so many processes in main
memory, it is very likely a process
will be in the Ready state at any
particular time
* A process may be larger than all of
main memory
صفحه 6:
Types of Memory
° Real memory
~ Main memory
° Virtual memory
~ Memory on disk
~ Allows for effective
multiprogramming and relieves
the user of tight constraints of
main memory
صفحه 7:
Thrashing
° Swapping out a piece of a
process just before that piece is
needed
° The processor spends most of
its time swapping pieces rather
than executing user instructions
صفحه 8:
Principle of Locality
° Program and data references
within a process tend to cluster
° Only a few pieces of a process
will be needed over a short period
of time
° Possible to make intelligent
guesses about which pieces will
be needed in the future
° This suggests that virtual memory
may work efficiently
8
صفحه 9:
Support Needed for
Virtual Memory
° Hardware must support paging
and segmentation
° Operating system must be able
to management the movement
of pages and/or segments
between secondary memory and
main memory
صفحه 10:
Paging
° Each process has its own page
table
° Each page table entry contains
the frame number of the
corresponding page in main
memory
° A bit is needed to indicate
whether the page is in main
memory or not
صفحه 11:
صفحه 12:
Modify Bit in
Page Table
° Modify bit is needed to indicate
if the page has been altered
since it was last loaded into
main memory
° If no change has been made,
the page does not have to be
written to the disk when it
needs to be swapped out
صفحه 13:
13
Page
۳
Main Memory
Physical Address
sat ares
ast ممت Framed oe
ب]
: Register
rete |g
I
ییا . و eer :
‘ :
agent’ 6 زو Macias :
Figure 83 Address Translation in a Paging System
صفحه 14:
Two-Level Scheme for
32-bit Address
wa O لل
NS
ae ies
صفحه 15:
Page Tables
° The entire page table may take
up too much main memory
° Page tables are also stored in
virtual memory
° When a process is running, part
of its page table is in main
memory
صفحه 16:
Inverted Page Table
° Used on PowerPC, UltraSPARC, and
1A-64 architecture
* Page number portion of a virtual
address is mapped into a hash value
° Hash value points to inverted page
table
° Fixed proportion of real memory is
required for the tables regardless of
the number of processes
صفحه 17:
Inverted Page Table
° Page number
۰ Process identifier
° Control bits
° Chain pointer
صفحه 18:
ملد اشوین
bits
Page? | Ome
Control
a bits 3
Process
Trash Page# ID Chain
function
Inverted Page Table سف م
(one entry for cach
physical memory frame)
ure 8.6 Inverted Page Table Structure
18
صفحه 19:
Translation Lookaside
Buffer
° Each virtual memory reference can
cause two physical memory
accesses
~ One to fetch the page table
~ One to fetch the data
° To overcome this problem a high-
speed cache is set up for page table
entries
~ Called a Translation Lookaside Buffer
(TLB)
19
صفحه 20:
Translation Lookaside
Buffer
° Contains page table entries that
have been most recently used
صفحه 21:
Translation Lookaside
Buffer
° Given a virtual address, processor
examines the TLB
° If page table entry is present (TLB
hit), the frame number is retrieved
and the real address is formed
° If page table entry is not found in
the TLB (TLB miss), the page
number is used to index the
process page table
صفحه 22:
Translation Lookaside
Buffer
° First checks if page is already
in main memory
- If not in main memory a page fault
is issued
° The TLB is updated to include
the new page entry
صفحه 23:
‘Secondary
Vit Ars Main Mary ee
Page f | Offset rt)
مد
aside Bt
— TLR hit ‘comet |
Page Tate i
TLB iiss اس
framed] Gat
Real Address LAN
Page ful
Lookaside Buffer
Figure 8.7 Use of a Transl
23
صفحه 24:
24
Figure 88 Operation of Paging aa Translation Lookasdde Bulfer(TL.B) [FURHST]
صفحه 25:
مضت غيم
ont هو
020030300
igure 89 Direct Versus Associative Lookup for Page Table Entries
25
(Diet mapping
صفحه 26:
Main
Memory
Page Table
LAN
Figure 8.10 Translation Lookaside Buffer and Cache Operation
26
صفحه 27:
Page Size
Smaller page size, less amount of
internal fragmentation
Smaller page size, more pages required
per process
More pages per process means larger
page tables
Larger page tables means large portion
of page tables in virtual memory
Secondary memory is designed to
efficiently transfer large blocks of data
so a large page size is better
27
صفحه 28:
Page Size
° Small page size, large number of
pages will be found in main
memory
۰ As time goes on during execution,
the pages in memory will all contain
portions of the process near recent
references. Page faults low.
° Increased page size causes pages to
contain locations further from any
recent reference. Page faults rise.
28
صفحه 29:
29
Number of Page Frames Ata )0( موس
P= sre ot ete proses.
Figure 8.11 ‘Typical Paging Behavior of a Program
صفحه 30:
Example Page Sizes
Table &2_ Example Page Sizes
Page Size
S12 48-bit words
1024 36.6 word
4 Kbytes
‘S12 bytes
S12 bytes
اه
4 مرها to 16 Mbytes
§ Kites to4 Mbytes
4 Kobytes or 4 Mbytes
4 Kes
4 Rytes ro 286 Mbytes
30
Compuier
‘alas
Honeywell-Malties
TBM 370:XA and 3708S
VAX fonily
IBM AS/400
DEC Alpha
Ips
‘UkeaSPARC
Penta
PowaPe
Tenn
صفحه 31:
Segmentation
° May be unequal, dynamic size
° Simplifies handling of growing
data structures
° Allows programs to be altered
and recompiled independently
° Lends itself to sharing data
among processes
° Lends itself to protection
صفحه 32:
Segment Tables
* Corresponding segment in main
memory
° Each entry contains the length of
the segment
° A bit is needed to determine if
segment is already in main memory
° Another bit is needed to determine if
the segment has been modified since
it was loaded in main memory
صفحه 33:
Segment Table Entries
صفحه 34:
34
ای
Main Memory
Segment Table
[gti Tie
Mechanism
Virtual Address
| =a
Figure 8.12 Address Translation in a Segmentation System
صفحه 35:
Combined Paging and
Segmentation
° Paging is transparent to the
programmer
° Segmentation is visible to the
programmer
° Each segment is broken into
fixed-size pages
صفحه 36:
Combined
Segmentation and
Paging
صفحه 37:
Main Memory
framed Ont
Page
۳۹
Paging
Mechanism
:
مه ١
fet
:
Be tae
Segmentation
Mechanism
Page 0۳۰
Virtual Address
Program
Figure 8.13 Address Translation in a Segmentation/Paging System
37
Sah
صفحه 38:
38
Adres Main Memory
20K
3K
50K
0K
90K.
Figure 8.14 Protection Relationships Between Segments
صفحه 39:
Fetch Policy
* Fetch Policy
~ Determines when a page should be
brought into memory
~ Demand paging only brings pages
into main memory when a reference
is made to a location on the page
* Many page faults when process first
started
~ Prepaging brings in more pages than
needed
* More efficient to bring in pages that
reside contiguously on the disk
39
صفحه 40:
Placement Policy
° Determines where in real
memory a process piece is to
reside
° Important in a segmentation
system
° Paging or combined paging
with segmentation hardware
performs address translation
صفحه 41:
Replacement Policy
° Placement Policy
~ Which page is replaced?
~ Page removed should be the page
least likely to be referenced in the
near future
~ Most policies predict the future
behavior on the basis of past
behavior
صفحه 42:
Replacement Policy
° Frame Locking
~ If frame is locked, it may not be
replaced
~ Kernel of the operating system
~ Control structures
- 1/0 buffers
~ Associate a lock bit with each
frame
صفحه 43:
Basic Replacement
Algorithms
° Optimal policy
~ Selects for replacement that page
for which the time to the next
reference is the longest
~ Impossible to have perfect
knowledge of future events
صفحه 44:
Basic Replacement
Algorithms
* Least Recently Used (LRU)
~ Replaces the page that has not been
referenced for the longest time
~ By the principle of locality, this
should be the page least likely to be
referenced in the near future
~ Each page could be tagged with the
time of last reference. This would
require a great deal of overhead.
صفحه 45:
Basic Replacement
Algorithms
° First-in, first-out (FIFO)
~ Treats page frames allocated to a
process as a circular buffer
~ Pages are removed in round-robin style
~ Simplest replacement policy to
implement
~ Page that has been in memory the
longest is replaced
~ These pages may be needed again very
soon
صفحه 46:
Basic Replacement
Algorithms
۰ Clock Policy
~ Additional bit called a use bit
~ When a page is first loaded in memory,
the use bit is set to 1
~ When the page is referenced, the use bit
is set to 1
~ When it is time to replace a page, the
first frame encountered with the use bit
set to 0 is replaced.
~ During the search for replacement, each
use bit set to 1 is changed to 0
46
صفحه 47:
47
و 2 3 8 4 2 8 1 2 3 2
ese 52 2 5 5 5 ۳۲ ۳۲ 77
ل ل لفط ل ل ل ل ل 1
Dea ee eee
mF 58
2 سم تچ 57 2 2 2 كك 727
5 اک Cs) ]= | لک oy اد
oo & ل 0
589 7
Ss esx Sse 2 ۲2 22 ۲۳۲ كك 727
7ARaAaoaeeaee
Toe ee ۶
PF ee
ی(
2
7
2
1 اما
3
۱
Figure 8.15 Behavior of Four Page-Replacement Algorithms
ركه م 85 م
1
Page address
stream
opr
LRU
FIFO
cLock
صفحه 48:
صفحه 49:
49
Example of Clock Policy Operation 816 عمسي
صفحه 50:
Comparison of Placement
Algorithms
Figure 8.17 Comparison of Fixed-Allocation, Local Page Replacement Algorithms
صفحه 51:
fects procs
rept
jure 8.18 ‘The Clock Page-Replacement Algorithm [GOLD89]
صفحه 52:
Basic Replacement
Algorithms
° Page Buffering
~ Replaced page is added to one of
two lists
° Free page list if page has not been
modified
* Modified page list
صفحه 53:
Resident Set Size
° Fixed-allocation
~ Gives a process a fixed number of
pages within which to execute
~ When a page fault occurs, one of the
pages of that process must be
replaced
° Variable-allocation
- Number of pages allocated to a
process varies over the lifetime of
the process
53
صفحه 54:
Fixed Allocation, Local
Scope
° Decide ahead of time the
amount of allocation to give a
process
° If allocation is too small, there
will be a high page fault rate
° If allocation is too large there
will be too few programs in
main memory
صفحه 55:
Variable Allocation,
Global Scope
° Easiest to implement
° Adopted by many operating systems
* Operating system keeps list of free
frames
° Free frame is added to resident set
of process when a page fault occurs
° If no free frame, replaces one from
another process
صفحه 56:
Variable Allocation,
Local Scope
° When new process added, allocate
number of page frames based on
application type, program request,
or other criteria
° When page fault occurs, select page
from among the resident set of the
process that suffers the fault
* Reevaluate allocation from time to
time
صفحه 57:
Cleaning Policy
° Demand cleaning
~ A page is written out only when it
has been selected for replacement
° Precleaning
~ Pages are written out in batches
صفحه 58:
Cleaning Policy
° Best approach uses page buffering
~ Replaced pages are placed in two
lists
* Modified and unmodified
~ Pages in the modified list are
periodically written out in batches
~ Pages in the unmodified list are
either reclaimed if referenced again
or lost when its frame is assigned to
another page
58
صفحه 59:
Load Control
° Determines the number of
processes that will be resident in
main memory
° Too few processes, many
occasions when all processes will
be blocked and much time will
be spent in swapping
* Too many processes will lead to
thrashing
صفحه 60:
Multiprogramming
Miltpragramming tert
Figure 8.21 Multiprogramming Effects
صفحه 61:
Process Suspension
° Lowest priority process
° Faulting process
- This process does not have its
working set in main memory so it
will be blocked anyway
° Last process activated
~ This process is least likely to have
its working set resident
صفحه 62:
Process Suspension
° Process with smallest resident
set
- This process requires the least
future effort to reload
° Largest process
~- Obtains the most free frames
° Process with the largest
remaining execution window
صفحه 63:
UNIX and Solaris
Memory Management
° Paging System
~ Page table
~ Disk block descriptor
~ Page frame data table
~ Swap-use table
صفحه 64:
‘Table 8.5 UNIX SVR4 Memory Management Parameters (page | of 2)
Page Table Entry
}rage frame number
Refers taftame in cel memory.
be
‘nates ow lon the page hae bean in mernery without being referenced The length and لاه موه
oe et
Jcopy on write
Sethen more than one proces chates apage one of the process rites into the pase, a sepaste copy
ofthe page aust fist be made forall other processes hat share the page This featne allows the copy
opeationo be defemed unl necessary and avoidedia cases wheres Iams our nat b be neces.
laity
مدقم page has bom همه
Reference
Tncicates page hasbeen referenced, This itis sett ero when the page is frst loaded and may be
pesiodicelly reset bythe page placement cigs.
waa
Incicates pages in rain memory
میت[
Indicates whether write operations allowed,
Disk lock: Decergter
swap device number
9 ae es cere pee Cheese م عست
oe device to be sed fot svapping
[Device bck: number
‘Block leation of page on swap device
[type of storage
Storage may be stp nt or executable file Tn the ater cae, here ea indication as to whether the
‘Firma memory 1 be allocated should be cecred fst.
صفحه 65:
65
Table 4
UNIX SVR4 Memory Management Parameters (page 2 of 2)
Page Frame Data Table Entry
[Page State
Tadicaces whether this frame is available or has an associated page. In the later case, the
stars of the page is specified: on swap device, in executable fle, or DMA in progress.
Reference count
‘Nimbor of processes tha reference the page
[Logical device
Logical device that contains a copy of the page.
Block mamber
‘Block location of the page copy on the logical device
Ptdata pointer
Pointer to other plata table enties om a ist of ftee pages and on a hack queue of pages.
Swap-use Table Entry
[Reference count
‘Number of page table entries that point toa page on the swap device.
Page/storage unit number
‘Page identifier oa storage unit.
صفحه 66:
[aw ESP] هسریم
(a Page table entry
(by Disk block descriptor
(@)Swapaase table entry
Figure 8.22 UNIX SVR4 Memory Management Formats
66
صفحه 67:
UNIX and Solaris
Memory Management
* Page Replacement
Figure 823
صفحه 68:
68
Kernel Memory
Allocator
° Lazy buddy
Thal value of Dj 0
‘After sa opeatioa, the value of is updated as follows
(D i the next eperation i a block allocate seques:
‘hare is any ee block, select one t allocate
‘the selected block is locally eee
then;
:هماه
00
fist get ovo blocks by splitiag a laraer oa into to (recursive operation)
allsete one and mark the othe locally fee
yremains unchanged (but D may chaage for othr block sizes because ofthe
recursive call)
(Fe next operations ablock Kee request
Case D,22
smack it locally fee and fre it locally
‘mark it slabally fe and Sree وهای coalesce i possible
Select one locally fie blak of size 2 sad eee it globally: coalesce if posible
2
Figure 824 Lazy Buddy System Algorithm
صفحه 69:
Linux Memory
Management
° Page directory
° Page middle directory
° Page table
صفحه 70:
Page frame
واه
من
Viena adress
Page Tale
Page table
fs
2
‘Middle Directory
Page midale
دس
‘Global Directory
Pase
tiretory
ها
Eq
Figure 825 Address Translation in Linux Virtual Memory Scheme
70
صفحه 71:
رك تنج
NULL
مس مراد
Kite gin or
]
ا
Ine operating ste
تست
Figure 8.26 Windows Default Virtual Address Space
71
صفحه 72:
Windows Memory
Management
° Paging
~ Available
~ Reserved
~ Committed
