PowerPoint Presentation
Chapter 9: Virtual Memory
1
Chapter 9: Virtual Memory
Background
Demand Paging
Copy-on-Write
Page Replacement
Allocation of Frames
Thrashing
Memory-Mapped Files
Allocating Kernel Memory
Other Considerations
Operating-System Examples
2
Objectives
To describe the benefits of a virtual memory system
To explain the concepts of demand paging, page-replacement algorithms, and allocation of page frames
To discuss the principle of the working-set model
To examine the relationship between shared memory and memory-mapped files
3
Background
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 even if it is all necessary.
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 negative impact on response time or turnaround time
Less I/O needed to load or swap programs into memory -> each user program runs faster
4
Background
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 – removes burden on programmers
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
There’s no free lunch, as we have already seen..
Virtual memory is no different.
It is hard to implement and may substantially decrease performance if it is used carelessly.
5
Background (Cont.)
Virtual address space – logical view of how process is stored in memory
Usually starts at address 0, using 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
6
Virtual Memory That is Larger Than Physical Memory
7
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 virtual address spaces with holes left for growth, dynamically linked libraries, etc
System libraries shared via mapping into virtual address space
8
Shared Library Using Virtual Memory
9
Virtual Memory via Demand Paging
Rather than bring entire process into memory at load time, 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
Like process paging system with swapping (diagram on right)
Page is needed reference to it
invalid reference abort
not-in-memory bring to memory
10
Basic Concepts
With swapping, pager guesses which pages will be used before swapping out again
Pager brings in only those pages into memory
How to determine that set of pages?
Need new MMU (read: hardware) 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
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 page fault
12
Page Table When Some Pages Are Not in Main Memory
13
Page Fault
The first reference to that page will trap to operating system:
page fault
Operating system looks at another table (usually in the PCB) to decide:
Invalid reference abort
Just not in memory
Find free frame
Swap page into frame via scheduled disk operation
Reset tables to indicate page now in memory
Set validation bit = v
Restart the instruction that caused the page fault
14
Steps in Handling a Page Fault
15
Aspects of Demand Paging
Pure 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
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 and they are all on different pages
Pain decreased because of locality of reference
Hardware support needed for demand paging
Page table with valid / invalid bit
Secondary high-speed memory (swap device with swap space)
Instruction restart
Instruction Restart
Consider an instruction that could access several different locations
block move (IBM MVC instruction)
auto increment/decrement location
Restart the whole operation?
What if source and destination overlap?
17
Stages in Demand Paging (worst case)
Trap to the operating system
Save the user registers and process state
Determine that the interrupt was a page fault
Check that the page reference was legal and determine the location of the page on the disk
Issue a read from the disk to a free frame:
Wait in a queue for this device until the read request is serviced
Wait for the device seek and/or latency time
Begin the transfer of the page to a free frame
While waiting, allocate the CPU to some other user
Receive an interrupt from the disk I/O subsystem (I/O completed)
Save the registers and process state for the other user
Determine that the interrupt was from the disk
Correct the page table and other tables to show page is now in memory
Wait for the CPU to be allocated to this process again
Restore the user registers, process state, and new page table, and then resume the interrupted instruction
Assumes
multiprogramming environment
18
Performance of Demand Paging (Cont.)
Three Major activities
Service the interrupt – careful coding means just several hundred instructions needed (1-100 microseconds)
Read the page – lots of time – 8 milliseconds
Restart the process – again just a small amount of time
Page Fault Probability 0 p 1
if p = 0 no page faults
if p = 1, every reference is a fault
Effective Access Time (EAT)
EAT = (1 – p) * ma (memory access 10-200 nanoseconds)
+ p (page fault overhead
+ swap page out
+ swap page in )
19
Demand Paging Example
Memory access time = 200 nanoseconds
Average page-fault service time = 8 milliseconds
EAT = (1 – p) x 200 + p (8 milliseconds)
= (1 – p) * 200 + p * 8,000,000
= 200 + p * 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
20
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 (overwrite) rather than paging out when freeing frame
Used in Solaris and current BSD
Still need to write to swap space
Pages modified in memory but not yet written back to the file system
Mobile systems
Typically don’t support swapping
Instead, demand page from file system and reclaim read-only pages (such as code)
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
Let’s look at an example….
22
Before Process 1 Modifies Page C
23
After Process 1 Modifies Page C
24
Copy-on-Write
In general, free pages are allocated from a pool of zero-fill-on-demand pages
Pool should always have free frames for fast demand page execution
Don’t want to have to free a frame as well as other processing on page fault
Why zero-out a page before allocating it?
vfork() variation on fork() system call has parent suspend and child using address space of parent
Designed to have child call exec()otherwise changes made by child process will be visible to parent
Very efficient
25
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
26
Page Replacement
Prevent over-allocation of memory by modifying page-fault service routine to include page replacement
over-allocation occurs when a page fault occurs and there are no free frames in which to swap the required page
Use modify (dirty) bit to reduce overhead of page transfers – only modified pages are written to disk
modify (dirty) bit is set by the hardware whenever any byte on the page is written into
Page replacement completes separation between logical memory and physical memory – large virtual memory can be provided on a smaller physical memory
Let’s see how it works..
27
Need For Page Replacement
28
Basic Page Replacement
the location of the desired page on disk
Find
If there is a free frame, use it
- If there is no free frame, use a page replacement algorithm to select a victim frame a free frame:
-Write victim frame to disk IFF dirty
Find
the desired page into the (newly) free frame; update the page and frame tables
Bring
the process by restarting the instruction that caused the trap
Continue
now potentially 2-page transfers for page fault
Note
29
Page Replacement
Dirty bits are not shown
In this diagram…..
30
Let’s Review
With No Demand Paging
User addresses are mapped into physical addresses, and the two sets of addresses can be different.
All the pages of the process must be in physical memory.
With Demand Paging
The size of the logical address space is no longer constrained by physical memory.
If we have a user process of twenty pages, we can execute it in ten frames simply by using demand paging and a page replacement algorithm to find a free frame whenever necessary.
To implement Demand Paging we must solve two major problems:
Develop a frame-allocation algorithm (how many frames to a process)
Develop a page replacement algorithm (which frame to replace)
Because disk I/O is expensive … we have to get this right
Page and Frame Replacement Algorithms
Frame-allocation algorithm determines
How many frames to give each process
Page-replacement algorithm
Which frames to replace
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
32
Graph of Page Faults Versus The Number of Frames
The more frames you add, the fewer page faults you get… usually..
How do you get more frames?
33
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)
Can vary by reference string: consider 1,2,3,4,1,2,5,1,2,3,4,5
How to track ages of pages?
Just use a FIFO queue
15 page faults
34
FIFO Example 2
1
1
2
1
2
3
4
2
3
4
1
3
4
1
2
5
1
2
5
3
2
5
3
4
1 2 3 4 1 2 5 1 2 3 4 5
Adding more frames can cause more page faults!
Beladys Anomaly (see next slide)
FIFO Illustrating Belady’s Anomaly
36
Optimal Page Replacement
Replace page that will not be used for longest period of time
9 page faults ‘is’ optimal for the example
How do you know this?
Can’t read the future Ahh…the need for clairvoyance again!!
Used for measuring how well your algorithm performs
37
Least Recently Used (LRU) Algorithm
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?..... Requires hardware assistance
38
LRU Algorithm (Cont.)
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
For each memory access:
A search through table is required and an update to the page-table
39
LRU Algorithm (Cont.)
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 (assuming 6 pages in memory)
But each update more expensive
No search for replacement
LRU and OPT are cases of stack algorithms that don’t have Belady’s Anomaly
Let’s look at an example…
40
Use Of A Stack to Record Most Recent Page References
41
LRU Approximation Algorithms
LRU needs special hardware and is still slow
Few computer systems provide hardware support for true LRU algorithms
Reference bit (supported by some systems)
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 of the references, however
42
Additional Reference Bits Algorithm
By recording reference bits at regular intervals we gain additional ordering information.
An 8-bit byte is kept for each page.
At regular intervals (~every 100 milliseconds) control transferred to the operating system.
High order bit contains most recent report of reference/non reference. Others are shifted right to create a reference history.
If treated as unsigned numbers, the pages with the lowest numbers are the ones least recently used (since a 1 in the high order bits indicates recent usage) 00111111 vs 11000001
In the case of duplicate low values…
Either sweep them all out.. Or use FIFO to decide
LRU Approximation Algorithms
Second-chance algorithm
Generally FIFO, plus hardware-provided reference bit
aka Clock replacement algorithm
If page to be replaced has
Reference bit = 0 -> replace it
reference bit = 1 then:
set reference bit 0,
reset arrival time to current time
leave page in memory
replace next page, subject to same rules
When all bits are set, this degenerates to FIFO
44
Second-Chance (clock) Page-Replacement Algorithm
45
Enhanced Second-Chance Algorithm
Improve algorithm by using reference bit and modify bit (if available) in concert
Take ordered pair (reference, modify)
(0, 0) neither recently used not modified – best page to replace
(0, 1) not recently used but modified – not quite as good, must write out before replacement
(1, 0) recently used but clean – probably will be used again soon
(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 FIRST page in lowest non-empty class
Might need to search circular queue several times
Why?
46
Counting Algorithms
Keep a counter of the number of references that have been made to each page
Not common –both are expensive to implement and do not approximate OPT replacement
Least Frequently Used (LFU) Algorithm: replaces page with smallest count
Active pages have large reference counts so they stay in
But…Sometimes activity is limited to initial phase and then never used
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
47
Page-Buffering Algorithms
Keep a pool of free frames, always
Read page into free frame and select victim to evict and add to free pool
When convenient, evict victim
Process restarts quickly without incurring page write-out delay
OR, Keep list of modified pages
When backing store otherwise idle, write pages there and set to non-dirty increasing the chance that a page will be clean when chosen for replacement.
OR, keep free frame contents intact and note what is in them
When a page fault occurs check this list.
If referenced again before reused, no need to load contents again from disk
Useful to reduce penalty if wrong victim frame selected
These procedures are in addition to a specific page replacement algorithm.
Applications and Page Replacement
All of these algorithms have OS guessing about future page access
Some applications have better knowledge – i.e. databases and they will do worse when OS provides buffering
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
Data warehouses generally do a massive sequential reads followed by computations and writes.
LRU would remove old pages while the data warehouse would just be beginning reading those older pages first.
Operating system can given direct access to the disk, getting out of the way of the applications
Raw disk mode
Bypasses buffering, locking, etc
Limited to certain applications
Allocation of Frames
The questions to answer here are:
How do we allocate the fixed amount of free memory among the various processes?
If we have 93 frames and 2 processes, how many frames does each process get?
50
Frame Allocation
Single-user system is simplest case
Consider a single user system with 128MB of memory with 1MB page sizes.
There are 128 frames.
The OS takes up 35MB, leaving 93 frames.
Pure demand paging:
All 93 frames put on free-frame list
When user process starts executing it will generate a sequence of page faults
The first 93 page faults will get all the frames on the free-frames list
On the 94th fault, a Page Replacement algorithm will be used to select an in memory page ‘victim’ to be replaced.
When the process terminates, all 93 frames are returned to the free frame list.
Allocation of Frames
Frame allocation is constrained:
Maximum # of frames to be allocated is total frames in the system
Each process needs minimum number of frames
Example: IBM 370 – 6 pages to handle MVC instruction:
instruction is 6 bytes, might span 2 pages
2 pages to handle from
2 pages to handle to
Increasing levels of indirection add additional page requirements
52
Allocation of Frames
53
Major allocation schemes
Equal allocation
Proportional allocation (based on relative process size)
Priority allocation (based on priority or size-and-priority)
Many variations
Allocation Schemes
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
64
64
64
59
54
Priority Allocation
Use a proportional allocation scheme using (also) priorities rather than (only) size
Ratio of frames depends
Priorities of the processes
Combination of size and priority
55
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
Process execution time can vary greatly as it’s performance is dependent on the paging behavior of all other processes
Generally yields greater throughput so it is the more common choice
Local replacement – each process selects from only its own set of allocated frames
More consistent per-process performance
But possibly underutilized memory
Another important factor in the way frames are allocated to processes is page replacement.
Two broad categories of algorithms
56
Non-Uniform Memory Access
So far all memory accessed equally
Many systems are NUMA – speed of access to memory varies
Consider system boards containing CPUs and memory, interconnected over a system bus
They are slower than systems in which memory and CPUs are located on the same motherboard.
Optimal performance comes from allocating memory “close to” the CPU on which the process is scheduled
And modifying the scheduler to schedule the process on the same system board when possible
Non-Uniform Memory Access
Threads add more complexity as the threads may be distributed among multiple system boards
Solved by Solaris by creating lgroups (as in latency)
Structure to detect CPU / Memory low-latency groups
When possible schedule all threads of a process and allocate all memory for that process within the lgroup, and, if needed, on nearby lgroups.
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
59
Thrashing
This leads to:
Low CPU utilization
Operating system thinking that it needs to increase the degree of multiprogramming since CPU use is low
Another process added to the system
If the new process needs more frames, it takes them from existing processes and this waterfalls
Processes start queueing up for the paging device and…
CPU usage drops again…
So.. Operating System adds more processes.. Ad nauseum
Thrashing a process is spending more time paging than executing.
60
Thrashing (Cont.)
61
Locality Model
We can prevent thrashing by providing a process with as many frames as it needs. (Local Replacement Algorithm)
Locality model states that as a process executes, it moves from locality to locality.
A locality is a set of pages that are actually used together
If we allocate enough frames to a process to accommodate its current locality, once all its pages are in memory, it will not fault again until it changes locality
If we allocate too few frames to a process to accommodate its currently locality, it will thrash and continue to do so
The ‘working set’ model helps determine the pages that are appropriate for a process while in its current locality.
62
Locality In A Memory-Reference Pattern
63
Working-Set Model
working-set window a fixed number of page references
Example: 10,000 instructions
WSSi (working set of Process Pi) =
total number of pages referenced in the most recent (varies in time)
if too small will not encompass entire locality
if too large will encompass several localities
if = will encompass entire program
64
Working-Set Model
65
D = WSSi total demand frames
Approximation of locality
if D > m Thrashing (where m is the total number of available frames)
Policy if D > m, then suspend or swap out one of the processes
Keeping Track of the Working Set
Approximate with interval timer + a reference bit
Example: = 10,000
Timer interrupts after every 5,000 time units
Keep in memory 2 bits for each page
Whenever a timer interrupts:
copy and set the values of all reference bits to 0
If one of the bits in memory = 1 page in working set
Why is this not completely accurate?
Improvement = 10 bits and interrupt every 1,000 time units
Why is this better?
66
Page-Fault Frequency
More direct approach than WSS (Working Set)
Establish “acceptable” page-fault frequency (PFF) rate and use local replacement policy
We may need to swap out a process if no free frames are available
67
Working Sets and Page Fault Rates
Direct relationship between working set of a process and its page-fault rate
Working set changes over time
Peaks and valleys over time
Peaks occur when we demand-paging a new locality
The low occurs when the working set in in memory
Memory-Mapped Files
Memory-mapped file I/O allows file I/O to be treated as routine memory access by mapping a disk block to a page in memory
A file is initially read using demand paging
A page-sized portion of the file is read from the file system into a physical page
Subsequent reads/writes to/from the file are treated as ordinary memory accesses
Simplifies and speeds file access by driving file I/O through memory rather than read() and write() system calls
Also allows several processes to map the same file allowing the pages in memory to be shared
But when does written data make it to disk?
Periodically and / or at file close() time
For example, when the pager scans for dirty pages
69
Memory-Mapped File Technique for all I/O
Some OSes uses memory mapped files for standard I/O
Process can explicitly request memory mapping a file via mmap() system call
Now file mapped into process address space
For standard I/O (open(), read(), write(), close()), mmap anyway
But map file into kernel address space
Process still does read() and write()
Copies data to and from kernel space and user space
Uses efficient memory management subsystem
Avoids needing separate subsystem
COW can be used for read/write non-shared pages
Memory mapped files can be used for shared memory (although again via separate system calls)
Memory Mapped Files
71
Shared Memory via Memory-Mapped I/O
72
Shared Memory in Windows API
First create a file mapping for file to be mapped
Then establish a view of the mapped file in process’s virtual address space
Consider producer / consumer
Producer create shared-memory object using memory mapping features
Open file via CreateFile(), returning a HANDLE
Create mapping via CreateFileMapping() creating a named shared-memory object
Create view via MapViewOfFile()
Sample code in Textbook
73
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
74
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
75
Buddy System Allocator
76
Slab Allocator
Alternate strategy
Slab is one or more physically contiguous pages
Cache consists of one or more slabs
Single cache for each unique kernel data structure
Each cache filled with objects – instantiations of the data structure
When cache created, filled with objects marked as free
When structures stored, objects marked as used
If slab is full of used objects, next object allocated from empty slab
If no empty slabs, new slab allocated
Benefits include no fragmentation, fast memory request satisfaction
77
Slab Allocation
78
Slab Allocator in Linux
For example process descriptor is of type struct task_struct
Approx 1.7KB of memory
New task -> allocate new struct from cache
Will use existing free struct task_struct
Slab can be in three possible states
Full – all used
Empty – all free
Partial – mix of free and used
Upon request, slab allocator
Uses free struct in partial slab
If none, takes one from empty slab
If no empty slab, create new empty
79
Slab Allocator in Linux (Cont.)
Slab started in Solaris, now wide-spread for both kernel mode and user memory in various OSes
Linux 2.2 had SLAB, now has both SLOB and SLUB allocators
SLOB for systems with limited memory
Simple List of Blocks – maintains 3 list objects for small, medium, large objects
SLUB is performance-optimized SLAB removes per-CPU queues, metadata stored in page structure
80
Other Considerations — Prepaging
Prepaging
To reduce the large number of page faults that occurs at process startup
Prepage all or some of the pages a process will need, before they are referenced
But if prepaged pages are unused, I/O and memory was wasted
Assume s pages are prepaged and α of the pages is used
Is cost of s * α save pages faults > or < than the cost of prepaging
s * (1- α) unnecessary pages?
α near zero prepaging loses
81
Other Issues – Page Size
Sometimes OS designers have a choice
Especially if running on custom-built CPU
Page size selection must take into consideration:
Fragmentation
Page table size
Resolution
I/O overhead
Number of page faults
Locality
TLB size and effectiveness
Always power of 2, usually in the range 212 (4,096 bytes) to 222 (4,194,304 bytes)
On average, growing over time
82
Other Issues – TLB Reach
TLB Reach - The amount of memory accessible from the TLB
TLB Reach = (TLB Size) X (Page Size)
Ideally, the working set of each process is stored in the TLB
Otherwise there is a high degree of page faults
Increase the Page Size
This may lead to an increase in fragmentation as not all applications require a large page size
Provide Multiple Page Sizes
This allows applications that require larger page sizes the opportunity to use them without an increase in fragmentation
83
Other Issues – Program Structure
Program structure
int[128,128] data;
Each row is stored in one page
Program 1
for (j = 0; j <128; j++)
for (i = 0; i < 128; i++)
data[i,j] = 0;
128 x 128 = 16,384 page faults
Program 2
for (i = 0; i < 128; i++)
for (j = 0; j < 128; j++)
data[i,j] = 0;
128 page faults
84
Other Issues – I/O interlock
I/O Interlock – Pages must sometimes be locked into memory
Consider I/O - Pages that are used for copying a file from a device must be locked from being selected for eviction by a page replacement algorithm
Pinning of pages to lock into memory
85
Operating System Examples
Windows
86
Windows
Uses demand paging with clustering. Clustering brings in pages surrounding the faulting page
Processes are assigned working set minimum and working set maximum
Working set minimum is the minimum number of pages the process is guaranteed to have in memory
A process may be assigned as many pages up to its working set maximum
When the amount of free memory in the system falls below a threshold, automatic working set trimming is performed to restore the amount of free memory
Working set trimming removes pages from processes that have pages in excess of their working set minimum
87
Solaris
Maintains a list of free pages to assign faulting processes
Lotsfree – threshold parameter (amount of free memory) to begin paging
Desfree – threshold parameter to increasing paging
Minfree – threshold parameter to being swapping
Paging is performed by pageout process
Pageout scans pages using modified clock algorithm
Scanrate is the rate at which pages are scanned. This ranges from slowscan to fastscan
Pageout is called more frequently depending upon the amount of free memory available
Priority paging gives priority to process code pages
88
Solaris 2 Page Scanner
89
Send email to CISC3320.bc@gmail.com
Within the next 90 seconds
End of Chapter 9
91
.MsftOfcThm_Accent1_Fill {
fill:#4472C4;
}
.MsftOfcThm_Accent1_Stroke {
stroke:#4472C4;
}
.MsftOfcThm_Accent1_Fill {
fill:#4472C4;
}
.MsftOfcThm_Accent1_Stroke {
stroke:#4472C4;
}
j.11.eps
n
u
m
b
e
r
o
f
p
a
g
e
f
a
u
lts
16
14
12
10
8
6
4
2
1 2 3
number of frames
4 5 6 7
j.14.eps
2
1
0
4
7
stack
before
a
7
2
1
4
0
stack
after
b
reference string
4 7 0 7 1 0 1 2 1 2 27
a b
1
j.15.eps
circular queue of pages
(a)
next
victim
0
reference
bits
pages
0
1
1
0
1
1
……
circular queue of pages
(b)
0
reference
bits
pages
0
0
0
0
1
1
……
m
S
s
p
a
m
s
S
p
s
i
i
i
i
i
i
´
=
=
=
å
=
=
for
allocation
frames
of
number
total
process
of
size
m = 64
s1=10
s2 =127
a1 =
10
137
×62 ≈ 4
a2 =
127
137
×62 ≈ 57
m=64
s1=10
s
2
=127
a
1
=
10
137
´62»4
a
2
=
127
137
´62»57
.MsftOfcThm_Accent1_Fill {
fill:#4472C4;
}
.MsftOfcThm_Accent1_Stroke {
stroke:#4472C4;
}
.MsftOfcThm_Accent1_Fill {
fill:#4472C4;
}
.MsftOfcThm_Accent1_Stroke {
stroke:#4472C4;
}
.MsftOfcThm_Accent1_Fill {
fill:#4472C4;
}
.MsftOfcThm_Accent1_Stroke {
stroke:#4472C4;
}
.MsftOfcThm_Accent1_Fill {
fill:#4472C4;
}
.MsftOfcThm_Accent1_Stroke {
stroke:#4472C4;
}
j.17.eps
18
20
22
24
26
28
30
32
34
p
a
g
e
n
u
m
b
e
rs
m
e
m
o
ry
a
d
d
re
ss
execution time
18
20
22
24
26
28
30
32
34
p
a
g
e
n
u
m
b
e
r
s
m
e
m
o
r
y
a
d
d
r
e
s
s
execution time
j.19.eps
number of frames
increase number
of frames
upper bound
lower bound
decrease number
of frames
p
a
g
e
-f
a
u
lt
ra
te
j.21.eps
process A
virtual memory
1
1
1 2 3 4 5 6
2
3
3
4
5
5
4
2
6
6
1
2
3
4
5
6
process B
virtual memory
physical memory
disk file
a.102.eps
process1
memory-mapped
file
shared
memory
shared
memory
shared
memory
process2
9.600.eps
physically contiguous pages
256 KB
128 KB
A
L
64 KB
B
R
64 KB
B
L
32 KB
C
L
32 KB
C
R
128 KB
A
R
9.500.eps
3-KB
objects
7-KB
objects
kernel objects caches slabs
physically
contiguous
pages
j.20.eps
minfree
sc
a
n
r
a
te
100
slowscan
8192
fastscan
desfree
amount of free memory
lotsfree
.MsftOfcThm_Accent1_Fill {
fill:#4472C4;
}
.MsftOfcThm_Accent1_Stroke {
stroke:#4472C4;
}