Chapter 3:
Memory Management
Operating System Concepts 5.1 Silberschatz, Galvin and Gagne 2002
Chapter 3:
Memory Management
Basic memory management
Multiprogramming with variable partitions - swapping
Virtual memory
Shared pages
segmentation
Operating System Concepts 5.2 Silberschatz, Galvin and Gagne 2002
3.1 Basic memory management
Memory management is the functionality of an operating
system which handles or manages primary memory.
Memory management :
mechanism
Keep track of memory in use
Keep track of unused (“free”) memory
Protect memory space
Allocate, deallocate space for processes
Swap processes: memory <–> disk
Operating System Concepts 5.3 Silberschatz, Galvin and Gagne 2002
Policies
Decide when to load each process into
memory
Decide how much memory space to allocate
each process
Decide when a process should be removed
from memory
Input queue – collection of processes on the disk that are
waiting to be brought into memory to run the program.
Operating System 5.4 Silberschatz, Galvin and Gagne 2002
Binding of Instructions and Data to Memory
Address binding of instructions and data to memory addresses
can happen at three different stages:
1. Compile time: compile time binding is used to generate the
absolute code. must recompile code if starting location changes.
2. Load time: Must generate relocatable code if memory location is
not known at compile time.
3. Execution time: Binding delayed until run time if the process can
be moved during its execution from one memory segment to
another.
Operating System Concepts 5.5 Silberschatz, Galvin and Gagne 2002
3.2 Swapping
Swapping is a mechanism in which a process can be swapped
temporarily out of main memory to a backing store , and then brought
back into memory for continued execution.
Backing store – fast disk large enough to accommodate copies of all
memory images for all users;
Roll out, roll in – swapping variant used for priority-based scheduling
algorithms; lower-priority process is swapped out so higher-priority
process can be loaded and executed.
Operating System Concepts 5.6 Silberschatz, Galvin and Gagne 2002
Schematic View of Swapping
Operating System Concepts 5.7 Silberschatz, Galvin and Gagne 2002
Partitioning
An early method of managing memory
Pre-virtual memory
Not used much now
But, it will clarify the later discussion of virtual memory if we
look first at partitioning:
Virtual Memory has evolved from the partitioning
methods
Operating System Concepts 5.8 Silberschatz, Galvin and Gagne 2002
A) 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 a process out of a partition
If none are in a ready or running state
Operating System Concepts 5.9 Silberschatz, Galvin and Gagne 2002
Fixed Partitioning Problems
A program may not fit in a partition.
Main memory use is inefficient.
Solution – Unequal Size Partitions
Operating System Concepts 5.10 Silberschatz, Galvin and Gagne 2002
B) Dynamic Partitioning
Partitions are of variable length and number
Process is allocated exactly as much memory as required
Dynamic Partitioning Example
External Fragmentation
Operating System Concepts 5.11 Silberschatz, Galvin and Gagne 2002
Placement Algorithm
Operating system must decide which free block to allocate to a process
Best-fit algorithm
Chooses the block that is closest in size to the request
First-fit algorithm
Scans memory from the beginning and chooses the first available block that is large
enough
Fastest
Next-fit
Scans memory from the location of the last placement
Operating System Concepts 5.12 Silberschatz, Galvin and Gagne 2002
Relocation
The programmer does not know where the program will be
placed in memory when it is executed,
it may be swapped to disk and return to main memory at a
different location (relocated)
Operating System Concepts 5.13 Silberschatz, Galvin and Gagne 2002
3.3 Virtual memory
is a technique that allows the execution of processes
which are not completely available in memory.
separation of user logical memory from physical memory.
This separation allows an extremely large virtual memory to
be provided for programmers when only a smaller physical
memory is available.
Operating System Concepts 5.14 Silberschatz, Galvin and Gagne 2002
Virtual memory can be implemented via:
Demand paging
Demand segmentation
Operating System Concepts 5.15 Silberschatz, Galvin and Gagne 2002
Demand paging
When we want to execute a process, we swap it into memory.
Rather than swapping the entire process into memory, however,
we use a lazy swapper called pager.
When a process is to be swapped in, the pager guesses which
pages will be used before the process is swapped out again.
Instead of swapping in a whole process, the pager brings only
those necessary pages into memory.
Operating System Concepts 5.16 Silberschatz, Galvin and Gagne 2002
Bring a page into memory only when it is needed.
Less I/O needed
Less memory needed
Faster response
More users
Divide logical memory into blocks of same size called
pages.
Operating System Concepts 5.17 Silberschatz, Galvin and Gagne 2002
Example of paging
Operating System Concepts 5.18 Silberschatz, Galvin and Gagne 2002
ADVANTAGES OF DP
Following are the advantages of Demand Paging
Large virtual memory.
More efficient use of memory.
Unconstrained multiprogramming. There is no limit on
degree of multiprogramming.
Operating System Concepts 5.19 Silberschatz, Galvin and Gagne 2002
Page Replacement Algorithm
Page replacement algorithms are the techniques using which
Operating System decides which memory pages to swap out,
write to disk when a page of memory needs to be allocated.
We’ve the following page replacement algorithm:
Operating System Concepts 5.20 Silberschatz, Galvin and Gagne 2002
First In First Out (FIFO) algorithm
Oldest page in main memory is the one which will be
selected for replacement.
Easy to implement, keep a list, replace pages from the tail
and add new pages at the head.
Operating System Concepts 5.21 Silberschatz, Galvin and Gagne 2002
Operating System Concepts 5.22 Silberschatz, Galvin and Gagne 2002
Optimal Page algorithm
An optimal page-replacement algorithm has the lowest page-
fault rate of all algorithms.
Replace the page that will not be used for the longest period of
time.
Use the time when a page is to be used.
Operating System Concepts 5.23 Silberschatz, Galvin and Gagne 2002
Operating System Concepts 5.24 Silberschatz, Galvin and Gagne 2002
Least Recently Used (LRU)
algorithm
Page which has not been used for the longest time in main
memory is the one which will be selected for replacement.
Easy to implement, keep a list, replace pages by looking back
into time.
Operating System Concepts 5.25 Silberschatz, Galvin and Gagne 2002
Operating System Concepts 5.26 Silberschatz, Galvin and Gagne 2002
Segmentation
Memory-management scheme that supports user view of
memory.
A program is a collection of segments. A segment is a logical
unit such as:
main program,
procedure,
function,
method,
object,
local variables, global variables,
common block,
stack,
symbol table, arrays
Operating System Concepts 5.27 Silberschatz, Galvin and Gagne 2002
Operating System Concepts 5.28 Silberschatz, Galvin and Gagne 2002
Operating System Concepts 5.29 Silberschatz, Galvin and Gagne 2002
Assignment 1
Discuss deadlocks in operating systems
with at least two examples.
Discuss the functionalities of an
operating system.
Operating System Concepts 5.30 Silberschatz, Galvin and Gagne 2002
