MEMORY MANAGEMENT

Definition

• Memory management is the process of

– allocating primary memory to user programs
– reclaiming that memory when it is no longer
needed
– protecting each user’s memory area from
other user programs; i.e., ensuring that each
program only references memory locations
that have been allocated to it.
Requirements

• In order to manage memory effectively

the OS must have
– Memory allocation policies
– Methods to track the status of memory
locations (free or allocated)
– Policies for preempting memory from one
process to allocate to another
Memory
Management
Terms
Memory Management
Requirements
• Memory management is intended to satisfy the
following requirements:
– Relocation
– Protection
– Sharing
– Logical organization
– Physical organization
Relocation

• Relocation is the process of adjusting program

addresses to match the actual physical addresses
where the program resides when it executes
• Why is relocation needed?
– Programmer/translator don’t know which other
programs will be memory resident when
the program executes
Relocation

• Why is relocation needed? (continued)

– Active processes need to be able to be swapped in and out
of main memory in order to maximize processor utilization
– Specifying that a process must be placed in the same
memory region when it is swapped back
in would be limiting
• Consequently it must be possible to
adjust addresses whenever a program
is loaded.
Addressing Requirements

Simplified Process Image

Protection

• Processes need to acquire permission to

reference memory locations for reading or
writing purposes
• Location of a program in main memory is
unpredictable
• Memory references generated by a process
must be checked at run time
• Mechanisms that support relocation also
support protection
Sharing
• Advantageous to allow each process access to the same copy of the
program rather than have their own separate copy
• Memory management must allow controlled access to shared areas
of memory without compromising protection
• Mechanisms used to support relocation support sharing capabilities
• Main memory is organized as a linear (1-D) address space consisting of
a sequence of bytes or words.
• Programs aren’t necessarily organized this way

• Paging versus segmentation

Physical Organization

• Two-level memory for program storage:

– Disk (slow and cheap) & RAM (fast and more expensive)
– Main memory is volatile, disk isn’t
• User should not have to be responsible for
organizing movement of code/data between the
two levels.
Physical Organization
Memory Partitioning
Table 7.2
Memory
Management
Techniques
Fixed Partitioning

• Equal-size partitions
– any process whose size is less than
or equal to the partition size can be
loaded into an available partition
• The operating system can swap
out a process if all partitions are
full and no process is in the
Ready or Running state
• A program may be too big to fit in a partition
• program needs to be designed with the use of overlays
• Main memory utilization is inefficient
• any program, regardless of size, occupies an entire
partition
• internal fragmentation
– wasted space due to the block of data loaded being
smaller than the partition
• Using unequal size partitions
helps lessen the problems
– programs up to 16M can be
accommodated without overlays
– partitions smaller than 8M allow smaller
programs to be accommodated with less
internal fragmentation
Memory Assignment
• The number of partitions specified at system
generation time limits the number of active
processes in the system
• Small jobs will not utilize partition space efficiently
• Partitions are of variable length and number
• Process is allocated exactly as much memory as it
requires
• This technique was used by IBM’s mainframe operating
system, OS/MVT
Effect of
Dynamic
Partitioning
Dynamic Partitioning
Placement Algorithms
Memory
Configuration
Example
Buddy System
• Comprised of fixed and dynamic partitioning
schemes
• Space available for allocation is treated as a
single block
• Memory blocks are available of size 2K words,
L ≤ K ≤ U, where
• 2L = smallest size block that is allocated
• 2U = largest size block that is allocated; generally 2U
is the size of the entire memory available for
allocation
Buddy System Example
Addresses
• Partition memory into equal fixed-size chunks that are relatively
small
• Process is also divided into small fixed-size chunks of the same size
Assignment of
Process to Free
Frames
Page Table

• Maintained by operating system for each process

• Contains the frame location for each page in the process
• Processor must know how to access the page table for the current
process
• Used by processor to produce a physical address
Data Structures
Logical Addresses
Segmentation

• A program can be subdivided into segments

 may vary in length
 there is a maximum length
• Addressing consists of two parts:
 segment number
 an offset
• Similar to dynamic partitioning
• Eliminates internal fragmentation
Logical-to-Physical Address
Translation - Segmentation
Buffer Overflow Attacks

• Security threat related to memory management

• Also known as a buffer overrun
• Can occur when a process attempts to store data beyond the limits
of a fixed-sized buffer
• One of the most prevalent and dangerous types of security attacks
Defending Against
Buffer Overflows
• Prevention
• Detecting and aborting
• Countermeasure categories:
VIRTUAL MEMORY
Hardware and Control Structures

• Two characteristics fundamental to memory

management:
1) all memory references are logical addresses that are
dynamically translated into physical addresses at run time
2) a process may be broken up into a number of pieces that
don’t need to be contiguously located in main memory
during execution
– If these two characteristics are present, it is not
necessary that all of the pages or segments of a
process be in main memory during execution
Terminology
• Operating system brings into main memory a few pieces of the
program
• Resident set - portion of process that is in main memory
• An interrupt is generated when an address is needed that is not in
main memory (segment/page fault)
• Operating system places the process in a
blocking state
Execution of a Process

• Piece of process that contains the logical address is brought into

main memory
– operating system issues a disk I/O Read request
– another process is dispatched to run while the disk I/O takes
place
– an interrupt is issued when disk I/O is complete, which causes
the operating system to place the affected process in the Ready
state
Implications

• More processes may be maintained in main memory

– only load in some of the pieces of each process
– with so many processes in main memory, it is very likely a
process will be in the Ready state at any particular time
• A process may be larger than all of main memory
Table 8.2
Characteristics of
Paging and
Segmentation
Principle of Locality

• Program and data references within a process tend to cluster

• Only a few pieces of a process will be needed over a short period
of time
• Therefore it is possible to make intelligent guesses about which
pieces will be needed in the future
• Making good guesses avoids thrashing
Paging Behavior

• During the lifetime

of the process,
references are
confined to a
subset of pages
Paging

• The term virtual memory is usually associated with systems that

employ paging
• Use of paging to achieve virtual memory was first reported for
the Atlas computer
• Each process has its own page table
– each page table entry contains the frame number of the
corresponding page in main memory
• Entry k contains the frame # of page k
(if page k is in memory)
Memory
Management
Formats
Address Translation
Simple PT Structure

• Simple page table: one PT per process

• Size is a problem – for 32-bit addresses, half
for OS, half for user space, the number of
pages in a user process is 232/pagesize. For
pagesize = 210, page table would have 222
entries. PER PROCESS!
• Solution? Page the page table!
Hierarchical PT Structure

• Still, one PT per process, but only load the

parts being used; e.g, a two-level page table
consists of
– A page directory, or root page table, in which
each entry points to a small page table
– The individual page tables, each of which points
to a portion of the total virtual address space
Hierarchical PT Example

• For a 32-bit address, 4-Kbyte (212) pages:

– Simple address: 20-bit page #, 12-bit offset
– Hierarchical address: 20-bit page # is now split
into two parts: 10 bits to select an entry in the
root page table and 10 bits to select an entry in
the corresponding smaller page table
– Regardless of the page table format, there are
220 pages of length 212.
Two-Level
Hierarchical Page Table
Address Translation
Inverted PT Structure

• Simple page tables, hierarchical page tables

occupy a lot of space: each process has its own PT,
size of each PT is proportional to size of virtual
address space.
• Another approach: one page table maps
everything in memory. Page table size is fixed.
Inverted PT Structure

• Page number portion of a virtual address is mapped into a hash

value
– hash value points to inverted page table
• Fixed proportion of real memory is required for the tables
regardless of the number of processes or virtual pages
supported
• Structure is called inverted because it indexes page table entries
by frame number rather than by virtual page number
Inverted Page Table

Each entry in the page table includes:

Virtual Memory Problems

• Page tables can occupy large amounts of memory

– Solution: hierarchical or inverted page tables
• Address translation using page tables increases
execution time
– Solution: Translation Lookaside Buffer (TLB)
Translation Lookaside
Buffer (TLB)

• Each virtual memory • To overcome the effect of

reference can cause two doubling the memory
physical memory accesses: access time, most virtual
– one to fetch the page memory schemes make
table entry use of a special high-speed
– one to fetch the data (or cache called a translation
the next instruction) lookaside buffer
Use of a TLB
TLB Operation
Associative Mapping

• The TLB only contains some of the page table entries so we cannot
simply index into the TLB based on page number
– each TLB entry must include the page number as well as the
complete page table entry
• The processor is equipped with hardware that allows it to
interrogate simultaneously a number of TLB entries to determine if
there is a match on page number
Direct Versus
Associative Lookup
TLB and Cache Operation
Page Size

• The smaller the page size, the lesser the amount of internal
fragmentation
– however, more pages are required per process
– more pages per process means larger page tables
– for large programs in a heavily multiprogrammed environment
some portion of the page tables of active processes must be in
virtual memory instead of main memory
– the physical characteristics of most secondary-memory devices
favor a larger page size for more efficient block transfer of data
Paging Behavior of a Program
Example: Page Sizes
• Contemporary programming
techniques used in large programs
tend to decrease the locality of
references within a process
Segmentation

• Segmentation
allows the
programmer to
view memory as
consisting of
multiple address
spaces or
segments
Segment Organization

• Each segment table entry contains the starting address of the

corresponding segment in main memory and the length of the
segment
• A bit is needed to determine if the segment is already in main
memory
• Another bit is needed to determine if the segment has been
modified since it was loaded in main memory
Address Translation
Combined Paging and Segmentation
Address Translation
Combined Segmentation
and Paging
Protection and Sharing

• Segmentation lends itself to the implementation of protection and

sharing policies
• Each entry has a base address and length so inadvertent memory
access can be controlled
• Sharing can be achieved by segments referencing multiple
processes
Protection Relationships
Operating System Software
Policies for Virtual Memory
• Key issue: Performance
 minimize page faults
• Determines when a
page should be
brought into memory
Demand Paging

• Demand Paging
– only brings pages into main memory when a reference is made
to a location on the page
– many page faults when process is first started
– principle of locality suggests that as more and more pages are
brought in, most future references will be to pages that have
recently been brought in, and page faults should drop to a very
low level
Prepaging

• Prepaging
– pages other than the one demanded by a page fault are brought
in
– exploits the characteristics of most secondary memory devices
– if pages of a process are stored contiguously in secondary
memory it is more efficient to bring in a number of pages at one
time
– ineffective if extra pages are not referenced
– should not be confused with “swapping”
Placement Policy

• Determines where in real memory a process piece

is to reside
• Important design issue in a segmentation system
• Paging or combined paging with segmentation
placing is irrelevant because hardware performs
functions with equal efficiency
• For NUMA systems an automatic placement
strategy is desirable
Replacement Policy

• Deals with the selection of a page in main memory to

be replaced when a new page must be brought in
– objective is that the page that is removed be the
page least likely to be referenced in the near future

– The more elaborate the replacement policy

the greater the hardware and software
overhead to implement it
 When a frame is locked the page currently stored in that frame may
not be replaced
 kernel of the OS as well as key control structures are held in
locked frames
 I/O buffers and time-critical areas may be locked into main
memory frames
 locking is achieved by associating a lock bit with each frame
 Selects the page for which the time to the
next reference is the longest
 Produces three page faults after the frame
allocation has been filled
Least Recently Used (LRU)

• Replaces the page that has not been referenced for the longest
time
• By the principle of locality, this should be the page least likely to
be referenced in the near future
• Difficult to implement
– one approach is to tag each page with the time of last
reference
• this requires a great deal of overhead
LRU Example
First-in-First-out (FIFO)

• Treats page frames allocated to a process as a circular buffer

• Pages are removed in round-robin style
 simple replacement policy to implement
• Page that has been in memory the longest is replaced
Clock Policy
• Requires the association of an additional bit with each frame
• referred to as the use bit
• When a page is first loaded in memory or referenced, the use bit is
set to 1
• The set of frames is considered to be a circular buffer
• Any frame with a use bit of 1 is passed over by the algorithm
• Page frames visualized as laid out in a circle
Combined Examples
• Improves paging
performance and
allows the use of
a simpler page
replacement
policy
Replacement Policy and Cache Size

• With large caches, replacement of pages can have a performance

impact
– if the page frame selected for replacement is in the cache, that
cache block is lost as well as the page that it holds
– in systems using page buffering, cache performance can be
improved with a policy for page placement in the page buffer
– most operating systems place pages by selecting an arbitrary
page frame from the page buffer
• The OS must decide how many pages to bring into main memory
– the smaller the amount of memory allocated to each process,
the more processes can reside in memory
– small number of pages loaded increases page faults
– beyond a certain size, further allocations of pages will not effect
the page fault rate
Resident Set Size

Fixed-allocation Variable-allocation
• gives a process a fixed • allows the number of page
number of frames in main frames allocated to a
memory within which to process to be varied over
execute the lifetime of the process
– when a page fault occurs,
one of the pages of that
process must be replaced
• The scope of a replacement strategy can be categorized as
global or local
– both types are activated by a page fault when there are no free
page frames
VM Policies - Review
• Key issue: Performance
 minimize page faults
Fixed Allocation, Local Scope

• Necessary to decide ahead of time the amount of

allocation to give a process
• If allocation is too small, there will be a high page fault
rate
Variable Allocation
Global Scope
• Easiest to implement
– adopted in a number of operating systems
• OS maintains a list of free frames
• Free frame is added to resident set of process when a page fault
occurs
• If no frames are available the OS must choose a page currently in
memory
• One way to counter potential problems is to use page buffering
• When a new process is loaded into main memory, allocate to it a
certain number of page frames as its resident set
• When a page fault occurs, select the page to replace from among
the resident set of the process that suffers the fault
• Periodically, reevaluate the allocation provided to the process and
increase or decrease it to improve overall performance
Variable Allocation
Local Scope

• Decision to increase or decrease a resident set size is based

on the assessment of the likely future demands of active
processes
Figure 8.19

Working Set of
Process as
Defined by
Window Size

W(t, Δ)
Page Fault Frequency
(PFF)

• Requires a use bit to be associated with each page in memory

• Bit is set to 1 when that page is accessed
• When a page fault occurs, the OS notes the virtual time since the
last page fault for that process
• Does not perform well during the transient periods when there is a
shift to a new locality
• Time-between-page-faults: easier to measure & is equal to 1/PFF so
may be a good substitute
• Evaluates the working set of a process at sampling instances based
on elapsed virtual time
• Driven by three parameters:
• Concerned with determining when a modified page should be
written out to secondary memory
Load Control

• Determines the number of processes that will be resident in main

memory
– multiprogramming level
• Critical in effective memory management
• 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
Multiprogramming
• If the degree of multiprogramming is to be reduced, one or more of
the currently resident processes must be swapped out
Unix

• Intended to be machine independent so its

memory management schemes will vary
– early Unix: variable partitioning with no virtual
memory scheme
– current implementations of UNIX and Solaris
make use of paged virtual memory
Unix
UNIX SVR4 Memory
Management Formats
Table 8.6

UNIX SVR4
Memory
Management
Parameters
(page 1 of 2)
Table 8.6

UNIX SVR4
Memory
Management
Parameters
(page 2 of 2)
• The page frame data table is used for page replacement
• Pointers are used to create lists within the table
– all available frames are linked together in a list of free frames
available for bringing in pages
– when the number of available frames drops below a certain
threshold, the kernel will steal a number of frames to
compensate
“Two Handed” Clock
Page Replacement
• The kernel generates and destroys small tables and buffers
frequently during the course of execution, each of which requires
dynamic memory allocation.
• Most of these blocks are significantly smaller than typical pages
(therefore paging would be inefficient)
• Allocations and free operations must be made as fast as possible
• Technique adopted for SVR4
• UNIX often exhibits steady-state behavior in kernel memory
demand
– i.e. the amount of demand for blocks of a particular size
varies slowly in time
• Defers coalescing until it seems likely that it is needed, and then
coalesces as many blocks as possible
Lazy Buddy System Algorithm
Linux
Memory Management

• Shares many characteristics with Unix

• Is quite complex
• Three level page table structure:
Address Translation
• Based on the clock algorithm
• The use bit is replaced with an 8-bit age variable
– incremented each time the page is accessed
• Periodically decrements the age bits
– a page with an age of 0 is an “old” page that has not been
referenced is some time and is the best candidate for
replacement
• A form of least frequently used policy
• Kernel memory capability manages physical
main memory page frames
– primary function is to allocate and deallocate frames for particular uses

• A buddy algorithm is used so that memory for the kernel can be allocated
and deallocated in units of one or more pages
• Page allocator alone would be inefficient because the kernel requires small
short-term memory chunks in odd sizes
• Slab allocation
• used by Linux to accommodate small chunks
Windows
Memory Management

• Virtual memory manager controls how memory is allocated and

how paging is performed
• Designed to operate over a variety of platforms
• Uses page sizes ranging from 4 Kbytes to 64 Kbytes
Windows Virtual Address Map

• On 32 bit platforms each user process sees a separate 32 bit

address space allowing 4 Gbytes of virtual memory per process
 by default half is reserved for the OS
• Large memory intensive applications run more effectively
using 64-bit Windows
• Most modern PCs use the AMD64 processor architecture
which is capable of running as either a 32-bit or 64-bit
system
32-Bit Windows Address Space
• On creation, a process can make use of the entire user space of
almost 2 Gbytes
• This space is divided into fixed-size pages managed in contiguous
regions allocated on 64 Kbyte boundaries
• Regions may be in one of three states:
• Windows uses variable allocation, local scope
• When activated, a process is assigned a data structure to manage
its working set
• Working sets of active processes are adjusted depending on the
availability of main memory