Transcript OperatingSystems-Lecture10

Operating System Concepts and Techniques
Lecture 10
Memory Management-3
M. Naghibzadeh
Reference
M. Naghibzadeh, Operating System Concepts and Techniques, First ed., iUniverse Inc., 2011.
To order: www.iUniverse.com, www.barnesandnoble.com, or www.amazon.com
Virtual Memory
Goals




Reduce memory waste
Eliminate program size restriction
Increase number of live programs
Move inactive parts of data, program, and
results out of main memory
2
Page-Based Virtual MM
Extended Page memory management to support
virtual memory
With virtual memory, disk becomes a virtual main
memory
During execution of a program, disk virtual area is the
permanent place for the program
Main memory is a temporary place for the program
To load a program, any page can take any page
frame
Executable files from slow devices such as CD has to
be moved to virtual area to improve performance
3
Page-Based Virtual MM...
Page table knows what page is where
No need to bring all pages to start running it
Can start running even if no page is brought to main
memory

Prefetch is possible, if you like and there is space
Page table is extended to show which page is in main
memory and which page is not

This is done by adding a column called present/absent
In theory, a very small main memory is adequate to
run a very large program
When the system wants to execute an instruction the
instruction and its operands have to be in main
memory
4
Page-Based Virtual MM...
Otherwise, a page fault occurs

the process is suspended until the page is brought to main
memory by memory manager
If the processor spends most of its time suspending
and resuming processes due to frequent page faults,
then a thrashing condition occurs
A reference to a logical address which has already
been loaded into main memory is called page success
In short time intervals, the program usually refers to
a small number of pages; this phenomenon is called
locality of reference
Page Frame Table (PFT) knows what page frames are
free
5
Ready to go
Put the first executable address of the
program in PC and we are ready to go, even if
no page is brought to main memory
Every logical address has to be translated to a
physical address
Next we talk about actual address translation
6
Address translation Using PT
Address translation using page table within MMU
Page number
Offset
Logical address
Page map table of the
running process with
present/absent field in
each entry
Offset is directly copied
from logical address to
physical address
Present?
No
Yes
Interrupt
Page frame number
Offset
Physical address aaddress
Page table is too big to fit in MMU; use cache memory
7
Address translation Using PFT
Have to use a content addressable memory
called Translation Lookaside Buffer (TLB)
The content addressable memory has to
house page frame table
We cannot have such a huge associative
memory
Will use Inverted Page Table (IPT)
8
Address translation Using IPT
Rows of IPT are created as needed
Virtual page# Page frame#
Protection Free/Allocated
Virtual page#
Other fields
Offset
Logical address
TLB
Present
?
No
Offset is directly
copied from
logical address to
physical address
Yes
Page frame number
Interrup
t
Offset
Physical address
aaddress
9
Concepts before page removal
If a running program need a page, OS must bring
it to main memory
If there is no free page frame, a page must be
removed
We have to respect:




Working set; every process is given a credit of MM
Per process or overall; do we remove pages from the same
process or from any process
Page locking; some pages are locked which means
they cannot be removed
What to do with removed pages? If necessary copy
them back to disk
10
First-In-First-Out Page removal
Page trace
1
2
3
4
1
2
5
1
2
3
4
5
Page frame 0
1
2
3
4
1
2
5
5
5
3
4
4
1
2
3
4
1
2
2
2
5
3
3
1
2
3
4
1
1
1
2
5
5
-
-
-
-
-
+
+
-
-
+
Page frame 1
Page frame 2
Hit?
-
-
FIFO behavior with three page frames, H=3, M=9, h=3/12, and m=9/12.
Simple to implement: use a single
linked list with two pointers
11
FIFO (Belady’s) Anomaly
Sometimes by increasing
frames page faults increase
memory
Page trace
1
2
3
4
1
2
5
1
2
3
4
5
Page frame 0
1
2
3
4
4
4
5
1
2
3
4
5
1
2
3
3
3
4
5
1
2
3
4
1
2
2
2
3
4
5
1
2
3
1
1
1
2
3
4
5
1
2
-
+
+
-
-
-
-
-
-
Page frame 1
Page frame 2
Page frame 3
Hit?
-
-
-
FIFO behaviour with four page frames, H=2, M=10, h=2/12, and m=10/12
FIFO does not have stack property
12
Clock policy/Second chance policy
Use reference bit
Page trace
4
0
2
3
Page frame 0
41
01
21
40
00
20
41
01
21
40
41
01
21
-
-
Page frame 1
Page frame 2
Hit?
-
-
0
4
3
2
31
31
00
00
20
20
40
00
4
41
41
30
21
21
31
00
00
41
30
30
01
20
31
31
00
41
41
+
-
+
-
+
Second chance behavior with three page frame, H=3, M=6, h=3/9, and m=6/9
13
Least Recently Used
Page trace
1
2
3
4
1
2
5
1
2
3
4
5
Page frame 0
1
2
3
4
1
2
5
1
2
3
4
5
1
2
3
4
1
2
5
1
2
3
4
1
2
3
4
1
2
5
1
2
3
-
-
-
-
-
+
+
-
-
+
Page frame 1
Page frame 2
Hit?
-
-
LRU with a main memory of three frames, H=2, M=10, h=2/12, and m=10/12
• Stack algorithm, but not practical
14
Some other page removals
Not Recently Used, uses modified bit
and reference bit
Least Frequently Used, uses a reference
counter
Most Frequently Used, Uses a reference
counter
Not Frequently used, uses a reference
bit and a reference bit update interval
15
Aging
Aging shifts every R bit to its corresponding
shift counter at the end of interval
It forgets far history
Page trace
1
2
3
Page frame 0
10000
10000
10000
20000
Page frame 1
Page frame 2
Hit?
-
-
2
5
3
10000
10000
50000
50000
20000
20000
21000
21000
30000
30000
30000
+
-
4
2
4
5
50000
40000
40000
41000
40100
40100
21000
20100
20100
21100
21100
20110
20110
30000
31000
30100
30100
30100
30100
30010
50000
-
+
-
+
+
-
Aging with a main memory of three frames, H=4, M=6, h=4/10, and m=6/10
16
Summary
Virtual memory management is the de facto MM
policy of contemporary computers
It has many good properties such as being able to run
extremely large programs and running numerous
simultaneous programs
With virtual memory management, comes a variety of
page removal methods with different complexities and
efficiencies
It has disadvantages too; increased execution time
and the need for special hardware module called
MMU are two main ones
17
Find out
The smallest size main memory which can run any
program though inefficiently
Optimal page size
The main property which makes aging to become a
good page replacement algorithm
The total space needed for all page tables of say 1000
programs of size 4giga bytes each
The format of a logical address in a four level page
table environment
The effective main memory access time with TLB and
a non-virtual page table
18
Any questions?
19