Operating Systems:

Internals and Design Principles, 6/E

William Stallings
Roadmap
• Hardware and Control Structures
• Operating System Software
• UNIX and Solaris Memory Management
Chapter 8
• Linux Memory Management
Virtual Memory
Click to edit Master subtitle style • Windows Memory Management

Dave Bremer
9/30/10 Otago Polytechnic, N.Z.
©2008, ice all

Terminology Key points in

Memory Management
1) Memory references are logical addresses
dynamically translated into physical
addresses at run time
– A process may be swapped in and out of main
memory occupying different regions at different
times during execution
2) A process may be broken up into pieces
that do not need to located contiguously in
main memory

Breakthrough in Execution of a Process

Memory Management
• If both of those two characteristics are • Operating system brings into main
present, memory a few pieces of the program
– then it is not necessary that all of the pages or • Resident set - portion of process that is in
all of the segments of a process be in main main memory
memory during execution.
• An interrupt is generated when an address
• If the next instruction, and the next data is needed that is not in main memory
location are in memory then execution can •
proceed Operating system places the process in a
–
blocking state
at least for a time
 Execution of a Process Implications of
this new strategy
• Piece of process that contains the logical • More processes may be maintained in
address is brought into main memory main memory
– – Only load in some of the pieces of each
Operating system issues a disk I/O Read
request process
– – With so many processes in main memory, it is
Another process is dispatched to run while the
disk I/O takes place very likely a process will be in the Ready state
– An interrupt is issued when disk I/O complete at any particular time
which causes the operating system to place • A process may be larger than all of main
the affected process in the Ready state memory

Real and Thrashing

Virtual Memory
• Real memory • A state in which the system spends most
– Main memory, the actual RAM of its time swapping pieces rather than
• Virtual memory executing instructions.
– • To avoid this, the operating system tries to
Memory on disk
– Allows for effective multiprogramming and guess which pieces are least likely to be used in
relieves the user of tight constraints of main the near future.
memory • The guess is based on recent history

Principle of Locality A Processes Performance

in VM Environment
• Program and data references within a process • Note that during
tend to cluster the lifetime of the
• Only a few pieces of a process will be needed process,
over a short period of time references are
• Therefore it is possible to make intelligent confined to a
guesses about which pieces will be needed in subset of pages.
the future
• This suggests that virtual memory may work
efficiently
 Support Needed for Paging
Virtual Memory
• • Each process has its own page table
Hardware must support paging and
segmentation • Each page table entry contains the frame
• Operating system must be able to manage number of the corresponding page in main
the movement of pages and/or segments memory
• Two extra bits are needed to indicate:
between secondary memory and main
– whether the page is in main memory or not
memory
– Whether the contents of the page has been
altered since it was last loaded
(see next slide)

Paging Table Address Translation

Page Tables Two-Level

Hierarchical Page Table
• Page tables are also stored in virtual
memory
• When a process is running, part of its
page table is in main memory
 Address Translation for Page tables
Hierarchical page table grow proportionally
• A drawback of the type of page tables just
discussed is that their size is proportional
to that of the virtual address space.

• An alternative is Inverted Page Tables

Inverted Page Table Inverted Page Table

• Used on PowerPC, UltraSPARC, and IA- Each entry in the page table includes:
64 architecture • Page number
• Page number portion of a virtual address • Process identifier
is mapped into a hash value – The process that owns this page.
• Hash value points to inverted page table • Control bits
• Fixed proportion of real memory is – includes flags, such as valid, referenced, etc
required for the tables regardless of the • Chain pointer
number of processes – the index value of the next entry in the chain.

Inverted Page Table 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)
– Contains page table entries that have been most
recently used
 TLB Operation Looking into the
Process Page Table
• Given a virtual address, • First checks if page is already in main
– processor examines the TLB memory
• – If not in main memory a page fault is issued
If page table entry is present (TLB hit),
– the frame number is retrieved and the real • The TLB is updated to include the new
address is formed page entry
• If page table entry is not found in the TLB
(TLB miss),
– the page number is used to index the process
page table

Translation Lookaside TLB operation

Buffer

Associative Mapping Translation Lookaside

Buffer
• As the TLB only contains some of the
page table entries we cannot simply index
into the TLB based on the page number
– Each TLB entry must include the page
number as well as the complete page table
entry
• The process is able to simultaneously
query numerous TLB entries to determine
if there is a page number match
 TLB and Page Size
Cache Operation
• Smaller page size, less amount of internal
fragmentation
• But 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

Page Size Further complications

to Page Size
• • Small page size, large number of pages will
Secondary memory is designed to
efficiently transfer large blocks of data so be found in main memory
a large page size is better • 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.

Page Size Example Page Size

 Segmentation Segment Organization
• • Starting address corresponding segment in
Segmentation allows the programmer to
view memory as consisting of multiple main memory
• Each entry contains the length of the segment
address spaces or segments.
– May be unequal, dynamic size • A bit is needed to determine if segment is
– Simplifies handling of growing data structures already in main memory
– • Another bit is needed to determine if the
Allows programs to be altered and recompiled
independently segment has been modified since it was
– Lends itself to sharing data among processes loaded in main memory
– Lends itself to protection

Segment Table Entries Address Translation in

Segmentation

Combined Paging and Combined Paging and

Segmentation Segmentation
• Paging is transparent to the programmer
• Segmentation is visible to the programmer
• Each segment is broken into fixed-size
pages
 Address Translation Protection and sharing
• Segmentation lends itself to the
implementation of protection and sharing
policies.
• As each entry has a base address and
length, inadvertent memory access can be
controlled
• Sharing can be achieved by segments
referencing multiple processes

Protection Relationships Roadmap

• Hardware and Control Structures
• Operating System Software
• UNIX and Solaris Memory Management
• Linux Memory Management
• Windows Memory Management

Memory Management Key Design Elements

Decisions
• Whether or not to use virtual memory
techniques
• The use of paging or segmentation or both
• The algorithms employed for various
aspects of memory management

• Key aim: Minimise page faults

– No definitive best policy
 Fetch Policy Demand Paging
and Prepaging
• Determines when a page should be • Demand paging
brought into memory – only brings pages into main memory when a
• Two main types: reference is made to a location on the page
– Many page faults when process first started
– Demand Paging
•
– Prepaging Prepaging
– brings in more pages than needed
– More efficient to bring in pages that reside
contiguously on the disk
– Don’t confuse with “swapping”

Placement Policy Replacement Policy

• Determines where in real memory a • When all of the frames in main memory
process piece is to reside are occupied and it is necessary to bring
• Important in a segmentation system in a new page, the replacement policy
• Paging or combined paging with determines which page currently in
segmentation hardware performs address memory is to be replaced.
translation

But… Replacement Policy:

Frame Locking
• Which page is replaced? • Frame Locking
• – If frame is locked, it may not be replaced
Page removed should be the page least
– Kernel of the operating system
likely to be referenced in the near future
– – Key control structures
How is that determined?
– – I/O buffers
Principal of locality again
– Associate a lock bit with each frame
• Most policies predict the future behavior
on the basis of past behavior
 Basic Replacement Examples
Algorithms
• There are certain basic algorithms that are • An example of the implementation of
used for the selection of a page to replace, these policies will use a page address
they include stream formed by executing the program
– Optimal is
– Least recently used (LRU) – 232152453252
– First-in-first-out (FIFO) • Which means that the first page
– Clock referenced is 2,
• Examples – the second page referenced is 3,
– And so on.

Optimal policy Optimal Policy

Example
• Selects for replacement that page for
which the time to the next reference is the
longest
• But Impossible to have perfect knowledge
of future events
• The optimal policy produces three page
faults after the frame allocation has been
filled.

Least Recently LRU Example

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
• Difficult to implement • The LRU policy does nearly as well as the
– One approach is to tag each page with the optimal policy.
time of last reference. – In this example, there are four page faults
– This requires a great deal of overhead.
 First-in, first-out (FIFO) FIFO Example
• 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 • The FIFO policy results in six page faults.
is replaced –
–
Note that LRU recognizes that pages 2 and 5
But, these pages may be needed again very are referenced more frequently than other
soon if it hasn’t truly fallen out of use pages, whereas FIFO does not.

Clock Policy Clock Policy Example

• Uses and additional bit called a “use bit”
• When a page is first loaded in memory or
referenced, the use bit is set to 1
• When it is time to replace a page, the OS
scans the set flipping all 1’s to 0
• The first frame encountered with the use
bit already set to 0 is replaced. • Note that the clock policy is adept at
protecting frames 2 and 5 from
replacement.

Clock Policy Clock Policy

 Clock Policy Combined Examples

Comparison Page Buffering

• LRU and Clock policies both involve
complexity and overhead
– Also, replacing a modified page is more costly
than unmodified as needs written to secondary
memory
• Solution: Replaced page is added to one of
two lists
– Free page list if page has not been modified
– Modified page list

Replacement Policy Resident Set

and Cache Size Management
• Main memory size is getting larger and the • The OS must decide how many pages to
locality of applications is decreasing. bring into main memory
– So, cache sizes have been increasing – The smaller the amount of memory allocated
• With large caches, replacement of pages to each process, the more processes that can
reside in memory.
can have a performance impact
– Small number of pages loaded increases
– improve performance by supplementing the
page faults.
page replacement policy with a with a policy
– Beyond a certain size, further allocations of
for page placement in the page buffer
pages will not affect the page fault rate.
 Resident Set Size Replacement Scope
• Fixed-allocation • The scope of a replacement strategy can
– Gives a process a fixed number of pages be categorized as global or local.
within which to execute – Both types are activated by a page fault when
– When a page fault occurs, one of the pages of there are no free page frames.
that process must be replaced – A local replacement policy chooses only
• Variable-allocation among the resident pages of the process that
– Number of pages allocated to a process generated the page fault
– A global replacement policy considers all
varies over the lifetime of the process
unlocked pages in main memory

Fixed Allocation, Variable Allocation, Global

Local Scope Scope
• Decide ahead of time the amount of • Easiest to implement
allocation to give a process – Adopted by many operating systems
• If allocation is too small, there will be a • Operating system keeps list of free frames
high page fault rate • Free frame is added to resident set of
• If allocation is too large there will be too process when a page fault occurs
few programs in main memory • If no free frame, replaces one from
– Increased processor idle time or another process
– Increased swapping. – Therein lies the difficulty … which to replace.

Variable Allocation, Resident Set

Local Scope Management Summary
• 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
 Cleaning Policy Cleaning Policy
• A cleaning policy is concerned with • Best approach uses page buffering
determining when a modified page should • Replaced pages are placed in two lists
be written out to secondary memory. – Modified and unmodified
• Demand cleaning • Pages in the modified list are periodically
– A page is written out only when it has been written out in batches
selected for replacement • Pages in the unmodified list are either
• Precleaning reclaimed if referenced again or lost when
– Pages are written out in batches its frame is assigned to another page

Load Control Multiprogramming

• Determines the number of processes that
will be resident in main memory
– The multiprogramming level
• 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

Process Suspension Suspension policies

• If the degree of multiprogramming is to be • Lowest priority process
reduced, one or more of the currently • Faulting process
resident processes must be suspended – This process does not have its working set in
(swapped out). main memory so it will be blocked anyway
• Six possibilities exist… • Last process activated
– This process is least likely to have its working
set resident
 Suspension policies cont. Roadmap
• Process with smallest resident set • Hardware and Control Structures
– This process requires the least future effort to • Operating System Software
reload • UNIX and Solaris Memory Management
• Largest process • Linux Memory Management
– Obtains the most free frames
• Windows Memory Management
• Process with the largest remaining
execution window

Unix Paging System and

Kernel Memory Allocator
• • Paging system provides a virtual memory
Intended to be machine independent so
implementations vary capability that allocates page frames in main
–
memory to processes
Early Unix: variable partitioning with no virtual – Also allocates page frames to disk block buffers.
memory to paged
• Kernel Memory Allocator allocates memory for the
– Recent Unix (SVR4 & Solaris) using paged
kernel
virtual memory – The paging system is less suited for this task
• SVR4 uses two separate schemes:
– Paging system and a kernel memory
allocator.

Paged VM Page Table Entry Fields

Data Structures
 Disk Block Page Frame and
Descriptor Fields Swap Use fields

Page Replacement “Two Handed” Clock

Page Replacement
• The page frame data table is used for
page replacement
• Pointers used to create several lists within
the table
– Free frame list
– When the number of free frames drops below
a threshold, the kernel will steal a number of
frames to compensate.

Parameters for Kernel Memory

Two Handed Clock Allocator
• Scanrate: • The kernel generates and destroys small
– The rate at which the two hands scan through tables and buffers frequently during the
the page list, in pages per second course of execution, each of which
requires dynamic memory allocation.
• Handspread: • Most of these blocks significantly smaller
– The gap between fronthand and backhand than typical pages,
• – Therefore normal paging would be inefficient
Both have defaults set at boot time based
on physical memory • Variation of “buddy system” is used
 Lazy Buddy Lazy Buddy
System Parameters
• UNIX often exhibits steady-state behavior • Ni = current number of blocks of size 2i
in kernel memory demand; • Ai = current number of blocks of size 2i
– i.e. the amount of demand for blocks of a that are allocated (occupied).
particular size varies slowly in time. • Gi = current number of blocks of size 2i
• To avoid unnecessary joining and splitting that are globally free.
of blocks, •
–
Li = current number of blocks of size 2i
the lazy buddy system defers coalescing until
that are locally free
it seems likely that it is needed, and then
coalesces as many blocks as possible.

Lazy Buddy Linux

System Allocator Memory Management
• Shares many characteristics with Unix
– But is quite complex
• Two main aspects
– Process virtual memory, and
– Kernel memory allocation.

Linux Linux Virtual Memory

Memory Management
• Page directory • Three level page table structure
• – Each table is the size of one page
Page middle directory
• • Page directory
Page table
– Each process has one page directory
– 1 page in size, must be in main memory
• Page middle directory:
– May be multiple pages, each entry points to
one page in the page table
 Linux Memory cont Address Translation
• Page table
– May also span multiple pages.
– Each page table entry refers to one virtual
page of the process.

Page Replacement Windows

Memory Management
• Based on the clock algorithm • The Windows virtual memory manager
• The “use bit” is replace with an 8-bit age controls how memory is allocated and how
variable paging is performed.
– • Designed to operate over a variety of
Incremented with each page access
• Periodically decrements the age bits platforms
–
– Any page with an age of 0 is “old” and is a uses page sizes ranging from 4 Kbytes to 64
candidate for replacement Kbytes.
• A form of Least Frequently Used policy

Windows Virtual 32 bit Windows

Address Map Address Space
• On 32 bit platforms each user process
sees a separate 32 bit address space
– Allowing 4G per process
• Some reserved for the OS,
– Typically each user process has 32G of
available virtual address space
– With all processes sharing the same 2G
system space
 Windows Paging Resident Set
Management System
• On creation, a process can make use of • Windows uses “variable allocation, local
the entire user space of almost 2 Gbytes. scope”
• This space is divided into fixed-size pages • When activated a process is assigned
managed in contiguous regions allocated data structures to manage its working set
on 64Kbyte boundaries • Working sets of active processes are
• Regions may be in one of three states adjusted depending on the availability of
– Available main memory
– Reserved
– Committed