Operating
Systems:
Internals
and Design Chapter 8
Principles Virtual Memory
Seventh Edition
William Stallings
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 memory
• main memory, the actual RAM
Virtual memory
• memory on disk
• allows for effective multiprogramming and relieves the
user of tight constraints of main memory
To avoid this, the
A state in which the operating system tries
system spends most to guess, based on
of its time swapping recent history, which
pieces are least likely
process pieces rather to be used in the near
than executing future
instructions
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
Each process has its own page table
each page table entry contains the frame number of
the corresponding page in main memory
Memory
Management
Formats
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 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
Segmentation allows the
Advantages:
programmer to view • simplifies handling of
memory as consisting of growing data structures
multiple address spaces or
segments • allows programs to be
altered and recompiled
independently
• lends itself to 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
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
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
Determines when a
page should be Two main
brought into memory types:
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
Pagingor combined paging with segmentation
placing is irrelevant because hardware performs
functions with equal efficiency
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
Algorithms used for
the selection of a
page to replace:
• Optimal
• Least recently used
(LRU)
• First-in-first-out (FIFO)
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