CS计算机代考程序代写 cache database file system scheme data structure algorithm PowerPoint Presentation

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; }