١٦/٠١/١٤٣٨

Operating
Systems:
Internals
and Design Chapter 8
Principles Virtual Memory
Eighth Edition
William Stallings

Virtual memory A storage allocation scheme in which secondary memory can be

addressed as though it were part of main memory. The addresses a
program may use to reference memory are distinguished from the
addresses the memory system uses to identify physical storage sites, and
program-generated addresses are translated automatically to the
corresponding machine addresses.The size of virtual storage is limited by
the addressing scheme of the computer system and by the amount of
secondary memory available and not by the actual number of main storage
locations.
Virtual address The address assigned to a location in virtual memory to allow that location
to be accessed as though it were part of main memory.
Virtual address The virtual storage assigned to a process.
space
Address space The range of memory addresses available to a process.
Real address The address of a storage location in main memory.

Table 8.1 Virtual Memory Terminology

١
١٦/٠١/١٤٣٨

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

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

Operating system places the process

in a blocking state

Continued . . .

٢
١٦/٠١/١٤٣٨

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

٣
١٦/٠١/١٤٣٨

Real and Virtual Memory

Real Virtual
memory memory

main memory,
the actual memory on disk
RAM

allows for effective

multiprogramming
and relieves the user
of tight constraints
of main memory

Simple Paging Virtual Memory Simple Segmentation Virtual Memory

Paging Segmentation
Main memory partitioned into small fixed-size Main memory not partitioned
chunks called frames
Program broken into pages by the compiler or Program segments specified by the programmer to
memory management system the compiler (i.e., the decision is made by the
programmer)
Internal fragmentation within frames No internal fragmentation
Table 8.2
No external fragmentation External fragmentation Characteristics
Operating system must maintain a page table for Operating system must maintain a segment table of Paging and
each process showing which frame each page for each process showing the load address and Segmentation
occupies length of each segment
Operating system must maintain a free frame list Operating system must maintain a list of free holes
in main memory
Processor uses page number, offset to calculate Processor uses segment number, offset to calculate
absolute address absolute address
All the pages of a Not all pages of a All the segments of a Not all segments of a
process must be in main process need be in main process must be in main process need be in main
memory for process to memory frames for the memory for process to memory for the process
run, unless overlays are process to run. Pages run, unless overlays are to run. Segments may
used may be read in as used be read in as needed
needed
Reading a page into Reading a segment into
main memory may main memory may
require writing a page require writing one or
out to disk more segments out to
disk

٤
١٦/٠١/١٤٣٨

To avoid this, the

A state in which operating system tries
the system spends to guess, based on
most of its time recent history, which
swapping process pieces are least likely
pieces rather than to be used in the near
executing future
instructions

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

Avoids thrashing

٥
١٦/٠١/١٤٣٨

For virtual memory to be practical and

effective:
• hardware must support paging and
segmentation
• operating system must include software for
managing the movement of pages and/or
segments between secondary memory and
main memory

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

٦
١٦/٠١/١٤٣٨

Virtual Address
Page Number Offset

Page Table Entry

P MOther Control Bits Frame Number

(a) Paging only

Virtual Address
Segment Number Offset

Segment Table Entry

P MOther Control Bits Length Segment Base

(b) Segmentation only

Virtual Address
Segment Number Page Number Offset

Segment Table Entry

Control Bits Length Segment Base

Page Table Entry

P MOther Control Bits Frame Number P= present bit
M = Modified bit
(c) Combined segmentation and paging

Figure 8.1 Typical Memory Management Formats

Virtual Address Physical Address

Page # Offset Frame # Offset

Register
n bits Page Table Ptr

Page Table
m bits
Offset
Page
Page#

Frame
+
Frame #

Program Paging Mechanism Main Memory

Figure 8.2 Address Translation in a Paging System

٧
١٦/٠١/١٤٣٨

4-kbyte root
page table

4-Mbyte user
page table

4-Gbyte user
address space

Figure 8.3 A Two-Level Hierarchical Page Table

Virtual Address
10 bits 10 bits 12 bits Frame # Offset

Root page
table ptr

Page
Frame
+ +

4-kbyte page
Root page table table (contains
(contains 1024 PTEs) 1024 PTEs)

Program Paging Mechanism Main Memory

Figure 8.4 Address Translation in a Two-Level Paging System

٨
١٦/٠١/١٤٣٨

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

Virtual Address
n bits
Page # Offset
Control
n bits bits
Process
hash m bits Page # ID Chain
function 0

2m 1 Frame # Offset
m bits
Inverted Page Table Real Address
(one entry for each
physical memory frame)

Figure 8.5 Inverted Page Table Structure

٩
١٦/٠١/١٤٣٨

Inverted Page Table

Each entry in the page table includes:

Page Process Control Chain

number identifier bits pointer
• the process • includes • the index
that owns flags and value of the
this page protection next entry
and locking in the chain
information

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
cache called a translation
one to fetch the data
lookaside buffer

١٠
١٦/٠١/١٤٣٨

Secondary
Main Memory Memory
Virtual Address
Page # Offset

Translation
Lookaside Buffer

TLB hit
Offset

Load
page
Page Table

TLB miss

Frame # Offset
Real Address

Page fault

Figure 8.6 Use of a Translation Lookaside Buffer

Start
Return to
Faulted Instruction
CPU checks the TLB

Page Table Yes

Entry in
TLB?
No

Access Page Table

Page Fault
Handling Routine

OS Instructs CPU Page

No in Main
to Read the Page
from Disk Memory?

Yes
CPU Activates
I/O Hardware Update TLB

Page Transferred
from Disk to CPU Generates
Main Memory Physical Address

Memory Yes
Full?

No Perform Page
Replacement

Page Tables
Updated

Figure 8.7 Operation of Paging and Translation Lookaside Buffer (TLB) [FURH87]

١١
١٦/٠١/١٤٣٨

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

Virtual Address Virtual Address

Page # Offset Page # Offset
5 502 5 502

Page # PT Entries
19
511
37
27
14
37 1
211
5 37
90

37 502 37 502
Frame # Offset Translation Lookaside Buffer Frame # Offset
Real Address Real Address

Page Table

(a) Direct mapping (b) Associative mapping

Figure 8.8 Direct Versus Associative Lookup for Page Table Entries

١٢
١٦/٠١/١٤٣٨

TLB Operation
Virtual Address

Page # Offset
TLB
TLB miss
TLB
hit Cache Operation

Real Address

+ Tag Remainder Hit Value

Cache
Miss

Main
Memory

Page Table
Value

Figure 8.9 Translation Lookaside Buffer 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

١٣
١٦/٠١/١٤٣٨

Page Fault Rate

Page Fault Rate

P W N
(a) Page Size (b) Number of Page Frames Allocated

P = size of entire process

W = working set size
N = total number of pages in process

Figure 8.10 Typical Paging Behavior of a Program

Computer Page Size

Atlas 512 48-bit words

Honeywell-Multics 1024 36-bit words
Table 8.3
IBM 370/XA and 370/ESA 4 Kbytes
VAX family 512 bytes Example
IBM AS/400 512 bytes Page
DEC Alpha 8 Kbytes Sizes
MIPS 4 Kbytes to 16 Mbytes

UltraSPARC 8 Kbytes to 4 Mbytes

Pentium 4 Kbytes or 4 Mbytes
IBM POWER 4 Kbytes
Itanium 4 Kbytes to 256 Mbytes

١٤
١٦/٠١/١٤٣٨

Page Size
the design issue of main memory is
page size is related to getting larger and
the size of physical address space used by
main memory and applications is also
program size growing

Contemporary programming
techniques used in large
programs tend to decrease the most obvious on
personal computers
locality of references within a where applications are
process becoming increasingly
complex

Segmentation
Advantages:
Segmentation • simplifies handling
allows the of growing data
programmer to structures
view memory as • allows programs to
consisting of be altered and
multiple address recompiled
independently
spaces or
• lends itself to
segments sharing data
among processes
• lends itself to
protection

١٥
١٦/٠١/١٤٣٨

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

Virtual address Physical address

Seg # Offset = d + Base + d

Register
Seg Table Ptr

Segment table
d
Segment
Seg #

+
Length Base

Program Segmentation mechanism Main memory

Figure 8.11 Address Translation in a Segmentation System

١٦
١٦/٠١/١٤٣٨

Combined Paging and

Segmentation

In a combined
paging/segmentation system Segmentation is visible to the
a user’s address space is programmer
broken up into a number of
segments. Each segment is
broken up into a number of
fixed-sized pages which are Paging is transparent to the
equal in length to a main programmer
memory frame

Virtual Address
Seg # Page # Offset Frame # Offset

Seg Table Ptr

Segment Page
Table Table
Page#

Offset
Page
Seg#

Frame
+ +

Program Segmentation Paging Main Memory

Mechanism Mechanism

Figure 8.12 Address Translation in a Segmentation/Paging System

١٧
١٦/٠١/١٤٣٨

Virtual Address
Segment Number Page Number Offset

Segment Table Entry

Control Bits Length Segment Base

Page Table Entry

P MOther Control Bits Frame Number P= present bit
M = Modified bit
(c) 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

١٨
١٦/٠١/١٤٣٨

Operating System Software

The design of the memory management

portion of an operating system depends on
three fundamental areas of choice:
• 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

١٩
١٦/٠١/١٤٣٨

Fetch Policy Resident Set Management

Demand paging Resident set size
Prepaging Fixed
Variable
Placement Policy Replacement Scope
Global
Replacement Policy Local
Basic Algorithms
Optimal Cleaning Policy
Least recently used (LRU) Demand
First-in-first-out (FIFO) Precleaning
Clock
Page Buffering Load Control
Degree of multiprogramming

Table 8.4 Operating System Policies for Virtual Memory

Determines when a
page should be Two main
brought into types:
memory

Demand
Prepaging
Paging

٢٠
١٦/٠١/١٤٣٨

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

Algorithms used for

the selection of a
page to replace:
• Optimal
• Least recently used (LRU)
• First-in-first-out (FIFO)
• Clock

٢٣
١٦/٠١/١٤٣٨

Page address
stream 2 3 2 1 5 2 4 5 3 2 5 2

2 2 2 2 2 2 4 4 4 2 2 2
OPT 3 3 3 3 3 3 3 3 3 3 3
1 5 5 5 5 5 5 5 5
F F F

2 2 2 2 2 2 2 2 3 3 3 3
LRU 3 3 3 5 5 5 5 5 5 5 5
1 1 1 4 4 4 2 2 2
F F F F

2 2 2 2 5 5 5 5 3 3 3 3
FIFO 3 3 3 3 2 2 2 2 2 5 5
1 1 1 4 4 4 4 4 2
F F F F F F

2* 2* 2* 2* 5* 5* 5* 5* 3* 3* 3* 3*
CLOCK 3* 3* 3* 3 2* 2* 2* 2 2* 2 2*
1* 1 1 4* 4* 4 4 5* 5*
F F F F F

F = page fault occurring after the frame allocation is initially filled

Figure 8.14 Behavior of Four Page-Replacement Algorithms

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

٢٤
١٦/٠١/١٤٣٨

First--in-
First in-First-
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

٢٥
١٦/٠١/١٤٣٨

40
Page Faults per 1000 References

FIFO
35
30 CLOCK

25 LRU
20
OPT
15
10
5
0
6 8 10 12 14

Number of Frames Allocated

Figure 8.16 Comparison of Fixed-Allocation, Local Page Replacement Algorithms

٢٦
١٦/٠١/١٤٣٨

Improves paging A replaced page is

not lost, but
performance and rather assigned to
allows the use of one of two lists

a simpler page
replacement
policy
Free page list Modified page list

list of page frames

pages are written
available for
out in clusters
reading in pages

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

Local
• chooses only among the resident pages of the process that generated
the page fault

Global
• considers all unlocked pages in main memory

Local Replacement Global Replacement

Fixed Allocation •Number of frames allocated •Not possible.

to a process is fixed.

•Page to be replaced is chosen

from among the frames
allocated to that process.

Variable Allocation •The number of frames •Page to be replaced is chosen from

allocated to a process may be all available frames in main
changed from time to time to memory; this causes the size of the
maintain the working set of resident set of processes to vary.
the process.

•Page to be replaced is chosen

from among the frames
allocated to that process.

Table 8.5 Resident Set Management

٢٩
١٦/٠١/١٤٣٨

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

If allocation is too • increased processor idle time

large, there will be
too few programs • increased time spent in
in main memory swapping

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

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

Key elements:

• criteria used to determine

resident set size
• the timing of changes

٣١
١٦/٠١/١٤٣٨

Sequence of
Page
Window Size, ∆
References
2 3 4 5
24 24 24 24 24
15 24 15 24 15 24 15 24 15
18 15 18 24 15 18 24 15 18 24 15 18
23 18 23 15 18 23 24 15 18 23 24 15 18 23
24 23 24 18 23 24 • •
17 24 17 23 24 17 18 23 24 17 15 18 23 24 17
18 17 18 24 17 18 • 18 23 24 17
24 18 24 • 24 17 18 •
18 • 18 24 • 24 17 18
17 18 17 24 18 17 • •
17 17 18 17 • •
15 17 15 17 15 18 17 15 24 18 17 15
24 15 24 17 15 24 17 15 24 •
17 24 17 • • 17 15 24
24 • 24 17 • •
18 24 18 17 24 18 17 24 18 15 17 24 18

Figure 8.17 Working Set of Process as Defined by Window Size

Working Set Size

Transient Transient Transient Transient Time

Stable Stable Stable Stable

Figure 8.18 Typical Graph of Working Set Size [MAEK87]

٣٢
١٦/٠١/١٤٣٨

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

Evaluates the working set of a process at sampling instances based

on elapsed virtual time

Driven by three parameters:

the number of
the minimum the maximum page faults that
duration of the duration of the are allowed to
sampling sampling occur between
interval interval sampling
instances

٣٣
١٦/٠١/١٤٣٨

Cleaning Policy
Concerned with determining when a modified page should be
written out to secondary memory

Demand Cleaning
a page is written out to secondary memory only when it has been selected for
replacement

Precleaning
allows the writing of pages in batches

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

٣٤
١٦/٠١/١٤٣٨

Processor Utilization

Multiprogramming Level

Figure 8.19 Multiprogramming Effects

If the degree of multiprogramming is to be reduced, one or more

of the currently resident processes must be swapped out

Six possibilities exist:

• lowest-priority process
• faulting process
• last process activated
• process with the smallest resident set
• largest process
• process with the largest remaining execution window

٣٥
١٦/٠١/١٤٣٨

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
SVR4 and Solaris use
paged virtual memory

two separate schemes:

• paging system
• kernel memory allocator

Kernel Memory
Paging System
Allocator

provides a virtual memory

capability that allocates page frames allocates memory for the kernel
in main memory to processes

allocates page frames to disk block

buffers

٣٦
١٦/٠١/١٤٣٨

Copy
Page frame number Age on Mod- Refe- Valid Pro-
write ify rence tect

(a) Page table entry

Swap device number Device block number Type of storage

(b) Disk block descriptor

Reference Logical Block Pfdata

Page state
count device number pointer

(c) Page frame data table entry

Reference Page/storage
count unit number

(d) Swap-use table entry

Figure 8.20 UNIX SVR4 Memory Management Formats

Page Table Entry

Page frame number

Refers to frame in real memory.

Age
Indicates how long the page has been in memory without being referenced. The length and contents of this
Table 8.6
field are processor dependent.

Copy on write
Set when more than one process shares a page. If one of the processes writes into the page, a separate copy
of the page must first be made for all other processes that share the page. This feature allows the copy
operation to be deferred until necessary and avoided in cases where it turns out not to be necessary.
UNIX SVR4
Modify Memory
Indicates page has been modified.

Reference
Management
Indicates page has been referenced. This bit is set to 0 when the page is first loaded and may be periodically
reset by the page replacement algorithm. Parameters
Valid (page 1 of 2)
Indicates page is in main memory.

Protect
Indicates whether write operation is allowed.

Disk Block Descriptor

Swap device number

Logical device number of the secondary device that holds the corresponding page. This allows more than
one device to be used for swapping.

Device block number

Block location of page on swap device.

Type of storage
Storage may be swap unit or executable file. In the latter case, there is an indication as to whether the (Table can be found on page 379
virtual memory to be allocated should be cleared first. in the textbook)

٣٧
١٦/٠١/١٤٣٨

Page Frame Data Table Entry

Page state
Indicates whether this frame is available or has an associated page. In the latter case, the Table 8.6
status of the page is specified: on swap device, in executable file, or DMA in progress.

Reference count UNIX SVR4

Number of processes that reference the page. Memory
Logical device
Management
Logical device that contains a copy of the page. Parameters
(page 2 of 2)
Block number
Block location of the page copy on the logical device.

Pfdata pointer
Pointer to other pfdata table entries on a list of free pages and on a hash queue of pages.

Swap-Use Table Entry

Reference count
Number of page table entries that point to a page on the swap device.

Page/storage unit number (Table can be

Page identifier on storage unit. found on page 379
in the textbook)

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

٣٨
١٦/٠١/١٤٣٨

End of Beginning
page list of page list

fr
on
th
handspread

an
d

nd
ha
ck
ba

Figure 8.21 Two-Handed Clock Page-Replacement Algorithm

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

Initial value of Di is 0
After an operation, the value of Di is updated as follows

(I) if the next operation is a block allocate request:

if there is any free block, select one to allocate
if the selected block is locally free
then Di := Di + 2
else Di := Di + 1
otherwise
first get two blocks by splitting a larger one into two (recursive operation)
allocate one and mark the other locally free
Di remains unchanged (but D may change for other block sizes because of the
recursive call)

(II) if the next operation is a block free request

Case Di ≥ 2
mark it locally free and free it locally
Di := Di - 2
Case Di = 1
mark it globally free and free it globally; coalesce if possible
Di := 0
Case Di = 0
mark it globally free and free it globally; coalesce if possible
select one locally free block of size 2i and free it globally; coalesce if possible
Di := 0

Figure 8.22 Lazy Buddy System Algorithm

٤٠
١٦/٠١/١٤٣٨

Linux
Memory Management
Shares many characteristics with UNIX
Is quite complex

• process virtual
memory
Two main • kernel memory
aspects allocation

Three level page table structure:

Page directory Page middle directory Page table

process has a single page

may span multiple pages may also span multiple pages
directory

each entry points to one page each entry points to one page each entry refers to one
of the page middle directory in the page table virtual page of the process

must be in main memory for

an active process

٤١
١٦/٠١/١٤٣٨

Virtual address
Global Directory Middle Directory Page Table Offset

+
Page table

Page middle +
directory Page frame
in physical
memory
Page
directory
+

+
cr3
register

Figure 8.23 Address Translation in Linux Virtual Memory Scheme

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 in some time and is the best candidate for
replacement

A form of least frequently used policy

٤٢
١٦/٠١/١٤٣٨

Inactive Active
timeout

PG_active = 0 timeout PG_active = 1

PG_referenced = 0 PG_referenced = 0

ed
used timeout used timeout

us
PG_active = 0 PG_active = 1
PG_referenced = 1 PG_referenced = 1

used

Figure 8.24 Linux Page Reclaiming

Kernel memory capability manages physical main memory page frames

primary function is to allocate and deallocate frames for particular
uses
Possible owners of a frame include:
• user-space processes
• dynamically allocated kernel data
• static kernel code
• page cache

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

٤٤
١٦/٠١/١٤٣٨

0
64-Kbyte region for
NULL-pointer assignments
(inaccessible)

2-Gbyte user
address space
(unreserved, usable)

64-Kbyte region for

bad pointer assignments
(inaccessible)

2-Gbyte region for

the operating system
(inacessible)

0xFFFFFFFF

Figure 8.25 Windows Default 32-bit Virtual Address Space

Windows Paging
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:

available reserved committed

٤٥
١٦/٠١/١٤٣٨

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

Android Memory
Management
Android includes a number of extensions to the normal Linux kernel memory
management facility

These include:
ASHMem
this feature provides anonymous shared memory, which abstracts
memory as file descriptors
a file descriptor can be passed to another process to share memory
Pmem
this feature allocates virtual memory so that it is physically contiguous
this feature is useful for hardware that does not support virtual memory
Low Memory Killer
this feature enables the system to notify an app or apps that they need to
free up memory
if an app does not cooperate, it is terminated

٤٦
١٦/٠١/١٤٣٨

Summary
Hardware and control structures UNIX and Solaris memory
Locality and virtual memory management
Paging Paging system
Segmentation Kernel memory allocator
Combined paging and Linux memory management
segmentation
Linux virtual memory
Protection and sharing
Kernel memory allocation
OS software
Windows memory management
Fetch policy
Windows virtual address map
Placement policy
Windows paging
Replacement policy
Windows 8 swapping
Resident set management
Cleaning policy Android memory management
Load control

٤٧