CHAPTER 3
MEMORY
MANAGEMENT
PART I
memory management
2
In a multiprogramming system, in order to
share the processor, a number of processes
must be kept in memory.
Memory management is achieved through
memory management algorithms.
Each memory management algorithm
requires its own hardware support.
In this chapter, we shall see the
partitioning, paging and segmentation
methods.
Memory Management
3
In order to be able to load programs at
anywhere in memory, the compiler must
generate relocatable object code.
Also we must make it sure that a
program in memory, addresses only its
own area, and no other program’s area.
Therefore, some protection mechanism
is also needed.
3.1 Fixed Partitioning
4
memory In this method,
OS memory is divided
into partitions whose
n KB small
sizes are fixed.
3n Medium OS is placed into the
KB
lowest bytes of
memory.
6n Large
KB
Relocation of
processes is not
needed
3.1 Fixed Partitioning
5
memory Processes are
OS classified on entry to
the system
n KB small
according to their
3n Medium memory they
KB
requirements.
We need one
6n Large large area Q
KB Process Queue (PQ)
for each class of
process.
3.1 Fixed Partitioning
6
memory If a process is selected to
allocate memory, then it
OS goes into memory and
competes for the
n KB small processor.
The number of fixed
3n Medium partition gives the degree
KB
of multiprogramming.
Since each queue has its
6n Large large area Q own memory region, there
KB is no competition between
queues for the memory.
3.1 Fixed Partitioning
7
memory The main problem
OS with the fixed
partitioning method
n KB small
is how to determine
3n
KB Medium the number of
partitions, and how
6n
KB to determine their
Large large area Q
sizes.
Fixed Partitioning with
8
Swapping
memory This is a version of
fixed partitioning that
OS uses RRS with some
time quantum.
2K P1 P3
When time quantum
6K P2 P4 P5 for a process expires,
it is swapped out of
memory to disk and
the next process in
12K empty empty the corresponding
process queue is
swapped into the
memory.
Fixed Partitioning with
9
Swapping
memory
OS
2K P1 P3
Secondary
storage 6K P2 P4 P5
12K empty empty
Fixed Partitioning with
10
Swapping
memory
OS
Swap out
P1 P3 P1
2K
Secondary
storage 6K P2 P4 P5
12K empty empty
Fixed Partitioning with
11
Swapping
memory
OS
Swap in
P3 P1
2K P3
Secondary
storage 6K P2 P4 P5
12K empty empty
Fixed Partitioning with
12
Swapping
memory
OS
2K P3 P1
Secondary
storage 6K P2 P4 P5
12K empty empty
Fixed Partitioning with
13
Swapping
memory
OS
Swap out
P3 P1 P3
2K
Secondary
storage 6K P2 P4 P5
12K empty empty
Fixed Partitioning with
14
Swapping
memory
OS
Swap in
P1 P3
2K P1
Secondary
storage 6K P2 P4 P5
12K empty empty
Fixed Partitioning with
15
Swapping
memory
OS
2K P1 P3
Secondary
storage 6K P2 P4 P5
12K empty empty
fragmentation
16
memory
If a whole partition is
OS currently not being
used, then it is called
2K an external
P1 (2K) fragmentation.
6K Empty (6K)
If a partition is being
P2 (9K) used by a process
12K empty requiring some
memory smaller than
Empty (3K) the partition size,
then it is called an
internal
fragmentation.
3.2 Variable Partitioning
17
With fixed partitions we have to deal with the
problem of determining the number and sizes of
partitions to minimize internal and external
fragmentation.
If we use variable partitioning instead, then
partition sizes may vary dynamically.
In the variable partitioning method, we keep a
table (linked list) indicating used/free areas in
memory.
3.2 Variable Partitioning
18
Initially, the whole memory is free and it is
considered as one large block.
When a new process arrives, the OS searches for
a block of free memory large enough for that
process.
We keep the rest available (free) for the future
processes.
If a block becomes free, then the OS tries to
merge it with its neighbors if they are also free.
3.2 Variable Partitioning
19
There are three algorithms for searching the list
of free blocks for a specific amount of memory.
First Fit
Best Fit
Worst Fit
first fit
20
First Fit : Allocate the first free block that
is large enough for the new process.
This is a fast algorithm.
first fit
21
OS
P1 12 KB
Initial <FREE> 10 KB
memory
mapping
P2 20 KB
<FREE> 16 KB
P3 6 KB
<FREE> 4 KB
first fit
22
OS
P1 12 KB
P4 of 3KB <FREE> 10 KB
arrives
P2 20 KB
<FREE> 16 KB
P3 6 KB
<FREE> 4 KB
first fit
23
OS
P1 12 KB
P4 of 3KB
loaded here P4 3 KB
by <FREE> 7 KB
FIRST FIT
P2 20 KB
<FREE> 16 KB
P3 6 KB
<FREE> 4 KB
first fit
24
OS
P1 12 KB
P5 of 15KB P4 3 KB
arrives <FREE> 7 KB
P2 20 KB
<FREE> 16 KB
P3 6 KB
<FREE> 4 KB
first fit
25
OS
P1 12 KB
P5 of 15 KB
loaded here P4 3 KB
by <FREE> 7 KB
FIRST FIT
P2 20 KB
P5 15 KB
<FREE> 1 KB
P3 6 KB
<FREE> 4 KB
Best fit
26
Best Fit : Allocate the smallest block among those
that are large enough for the new process.
In this method, the OS has to search the entire list, or
it can keep it sorted and stop when it hits an entry
which has a size larger than the size of new process.
This algorithm produces the smallest left over block.
However, it requires more time for searching all the
list or sorting it
If sorting is used, merging the area released when a
process terminates to neighboring free blocks,
becomes complicated.
best fit
27
OS
P1 12 KB
Initial <FREE> 10 KB
memory
mapping
P2 20 KB
<FREE> 16 KB
P3 6 KB
<FREE> 4 KB
best fit
28
OS
P1 12 KB
P4 of 3KB <FREE> 10 KB
arrives
P2 20 KB
<FREE> 16 KB
P3 6 KB
<FREE> 4 KB
best fit
29
OS
P1 12 KB
P4 of 3KB
loaded here <FREE> 10 KB
by
BEST FIT
P2 20 KB
<FREE> 16 KB
P3 6 KB
P4 3 KB
<FREE> 1 KB
best fit
30
OS
P1 12 KB
P5 of 15KB <FREE> 10 KB
arrives
P2 20 KB
<FREE> 16 KB
P3 6 KB
P4 3 KB
<FREE> 1 KB
best fit
31
OS
P1 12 KB
P5 of 15 KB
loaded here <FREE> 10 KB
by
BEST FIT
P2 20 KB
P5 15 KB
<FREE> 1 KB
P3 6 KB
P4 3 KB
<FREE> 1 KB
worst fit
32
Worst Fit : Allocate the largest block among those
that are large enough for the new process.
Again a search of the entire list or sorting it is
needed.
This algorithm produces the largest over block.
worst fit
33
OS
P1 12 KB
Initial <FREE> 10 KB
memory
mapping
P2 20 KB
<FREE> 16 KB
P3 6 KB
<FREE> 4 KB
worst fit
34
OS
P1 12 KB
P4 of 3KB <FREE> 10 KB
arrives
P2 20 KB
<FREE> 16 KB
P3 6 KB
<FREE> 4 KB
worst fit
35
OS
P1 12 KB
P4 of 3KB
Loaded here <FREE> 10 KB
by
WORST FIT
P2 20 KB
P4 3 KB
<FREE> 13 KB
P3 6 KB
<FREE> 4 KB
worst fit
36
OS
P1 12 KB
No place to <FREE> 10 KB
load P5 of 15K
P2 20 KB
P4 3 KB
<FREE> 13 KB
P3 6 KB
<FREE> 4 KB
worst fit
37
OS
P1 12 KB
No place to <FREE> 10 KB
load P5 of 15K
P2 20 KB
P4 3 KB
<FREE> 13 KB
Compaction
is needed !! P3 6 KB
<FREE> 4 KB
compaction
38
Compaction is a method to overcome the
external fragmentation problem.
All free blocks are brought together as one large
block of free space.
Compaction requires dynamic relocation.
Certainly, compaction has a cost and selection of
an optimal compaction strategy is difficult.
One method for compaction is swapping out
those processes that are to be moved within the
memory, and swapping them into different
memory locations
compaction
39
OS
P1 12 KB
Memory
mapping <FREE> 10 KB
before
compaction
P2 20 KB
P4 3 KB
<FREE> 13 KB
P3 6 KB
<FREE> 4 KB
compaction
40
OS
P1 12 KB
P2 20 KB
Swap out
P4 3 KB P2
P3 6 KB
compaction
41
OS
P1 12 KB
P2 20 KB Swap in
P2
Secondary
storage
P4 3 KB
P3 6 KB
compaction
42
OS
P1 12 KB
P2 20 KB
Secondary
storage
P4 3 KB
Swap out
P4
P3 6 KB
compaction
43
OS
P1 12 KB
P2 20 KB
P4 3 KB
Swap in Secondary
P4 with a storage
different
starting
address
P3 6 KB
compaction
44
OS
P1 12 KB
P2 20 KB
P4 3 KB
Secondary
storage
Swap out
P3
P3 6 KB
compaction
45
OS
P1 12 KB
P2 20 KB
P4 3 KB Swap in
P3
P3 6 KB
Secondary
storage
compaction
46
OS
P1 12 KB
Memory P2 20 KB
mapping after
P4 3 KB
compaction
P3 6 KB
<FREE> 27 KB
Now P5 of
15KB can be
loaded here
compaction
47
OS
P1 12 KB
P2 20 KB
P4 3 KB
P3 6 KB
P5 12 KB
<FREE> 12 KB P5 of 15KB is
loaded
relocation
48
Static relocation: A process may be loaded into
memory, each time possibly having a different
starting address
Necessary for variable partitioning
Dynamic relocation: In addition to static
relocation, the starting address of the process
may change while it is already loaded in memory
Necessary for compaction
