Contiguous Allocation

• Main memory must support both OS and user processes

• Limited resource, must allocate efficiently
• Contiguous allocation is one early method
• Main memory usually into two partitions:
• Resident operating system, usually held in low memory with interrupt
vector
• User processes then held in high memory
• Each process contained in single contiguous section of memory
Contiguous Allocation (Cont.)
• Relocation registers used to protect user processes from each other,
and from changing operating-system code and data
• Base register contains value of smallest physical address
• Limit register contains range of logical addresses – each logical
address must be less than the limit register
• MMU maps logical address dynamically
• Can then allow actions such as kernel code being transient and
kernel changing size
Hardware Support for Relocation and Limit Registers
Multiple-partition allocation
• Multiple-partition allocation
• Degree of multiprogramming limited by number of partitions
• Variable-partition sizes for efficiency (sized to a given process’ needs)
• Hole – block of available memory; holes of various size are scattered throughout
memory
• When a process arrives, it is allocated memory from a hole large enough to
accommodate it
• Process exiting frees its partition, adjacent free partitions combined
• Operating system maintains information about:
a) allocated partitions b) free partitions (hole)
Contiguous Allocation (Cont.)
Partitioning :
1. Fixed Sized Partitioning
2. Variable Sized Partitioning

100KB

50KB
375KB
150KB

75KB
Fragments - Holes
Internal Fragmentation – Within a partition the left out memory after placing a process in the partition is said
to be “Internal Fragmentation”

P1 = 50KB
P1 100KB
100KB
Hole=50KB

P2 100KB 100KB
Fragmentation

• External Fragmentation – total memory space exists to satisfy a

request, but it is not contiguous
• Internal Fragmentation – allocated memory may be slightly
larger than requested memory; this size difference in memory
internal to a partition, but not being used
• Reduce external fragmentation by compaction
• Shuffle memory contents to place all free memory together in
one large block
• Compaction is possible only if relocation is dynamic, and is
done at execution time
Fragments - Holes
External Fragmentation – total memory space exists to satisfy a request, but it
is not contiguous is said to be “External Fragmentation”

P1 = 50KB IF a process p3 is to be stored in the

p1 memory with 100KB. Even though

Hole=50KB the total memory space available is

100KB, it cannot be used since it is
not contiguous
P2 = 50KB

p2
Hole=50KB
Compaction or Garbage Collection
Compaction: Collecting all internal fragments to form a free block which is contiguous is called
compaction or Garbage Collection. Holes or Internal fragments can be used only after
compaction

P1 = 50KB P1 = 50KB

p1 Allocated
Partitions
Hole=50KB P2 = 50KB

P2 = 50KB
Contiguous Free
p2 block of contiguous
100KB Block
Hole=50KB
Dynamic Storage-Allocation Problem
How to satisfy a request of size n from a list of free holes?

• First-fit: Allocate the first hole that is big enough

• Best-fit: Allocate the smallest hole that is big enough;

must search entire list, unless ordered by size
• Produces the smallest leftover hole

• Worst-fit: Allocate the largest hole; must also search

entire list
• Produces the largest left over hole

First-fit and best-fit better than worst-fit in terms of speed and storage utilization
First Fit Method

• This method works as for any process Pn, the OS searches from
starting block again and again and allocates a block to process Pn such
that –
• Block is available
• Can fit the process
• In simple words First Fit algorithm finds, the first block to fix the
process.
PROBLEM Blocks

Process Process Size

Block Block Size
Process 1 90 Block 1 20
Process 2 50 Block 2 100
Process 3 30 Block 3 40
Process 4 40 Block 4 200
Block 5 10

Process Size Allocated to Block size Memory Wastage

Process 1 90 Block 2 100 10

Process 2 50 Block 4 200 150

Process 3 30 Block 3 40 10

Process 4 40 Unallocated – –
EXPLANATION
• Process P1 • Block 4 size (200K) > p2 size (50K)
• All Blocks 1 – 5 are available • Block 4 allocated to P2
• P1 checks for block 1, Block 1 Size (20K) • Process 3
< P1 size (90K), can’t fit • Block 1 size (20K) < p3 size (30K)
• P2 checks for block 2, Block 2 Size (100 k) • Block 2 unavailable
> p1 size (90K)
• Block 3 size (40K) > p3 size (30K)
• P2 goes to block 2
• Block 3 allocated to p3
• Process 2
• Process 4
• Block 1 size (20K) < P2 size (50K), can’t
fit • Block 1 size (20K) < p4 size (40K)
• Block 2 is already occupied by P1, • Block 2, 3, 4 are unavailable
unavailable • Block 5 size (10K) < p4 size (40K)
• Block 3 size (40K) < p2 size (50K), can’t fit• Process 4 remains unallocated
BEST FIT
• This method works as for any process Pn, the OS searches from
starting block again and again and allocates a block to process P n such
that –
• Block can accommodate process
• Memory wastage is minimum
Process Size Blocks Size
Process 1 40 Block 1 100
Process 2 10 Block 2 50
Process 3 30 Block 3 30
Process 4 60 Block 4 120
Block 5 35

Process Size Allocated to Block size Wastage

Process 1 40 Block 2 50 10
Process 2 10 Block 3 30 20
Process 3 30 Block 5 35 5
Process 4 60 Block 1 100 40
• Job 1 (size – 40K) block 3
• Block 3 and 5 can not place as their size • Job 3 (size – 30K)
is lesser than 40K • Block 2, 3 unavailable
• Block 1 Memory wastage : 100 – 40 = • Block 1 memory wastage : 100 – 30 =
60K 70
• Block 2 Memory wastage : 50 – 40 = • Block 4 memory wastage : 120 – 30 =
20K 90
• Block 4 Memory wastage : 120 – 40 = • Block 5 memory wastage : 35 – 30 = 5
80K
• Thus, block is the best, P3 placed in
• Thus Block 2 is best, P1 placed in block block 5
2
• Job 4 (size 60K)
• Job 2 (size – 10K)
• Block 2, 3 and 5 are unavailable
• Block 2 is unavailable now
• Block 1 memory wastage : 100 – 60 =
• Block 1 memory wastage: 100 – 10 = 90 40
• Block 3 memory wastage: 10 – 10 = 20 • Block 4 memory wastage : 120 – 60 =
• Block 4 memory wastage : 120 – 10 = 60
110 • Thus, block 1 is the best P4 goes to
• Block 5 memory wastage: 35 – 10 = 25 block 1
• Thus, block 3 is the best, P2 placed in
Worst fit
• This method works as for any process Pn, the OS searches from
starting block again and again and allocates a block to process P n such
that –
• Block can accommodate process
• Memory wastage is maximum
Process Size Blocks Size
Process 1 40 Block 1 100
Process 2 10 Block 2 50
Process 3 30 Block 3 30
Process 4 60 Block 4 120
Block 5 35

Process Size Allocated to Block size Wastage

Process 1 40 Block 4 120 80
Process 2 10 Block 1 100 90
Process 3 30 Block 2 50 20
Process 4 60 Unallocated – –
Problem
Consider six memory partitions of size 200 KB, 400 KB, 600 KB, 500
KB, 300 KB and 250 KB. These partitions need to be allocated to four
processes of sizes 357 KB, 210 KB, 468 KB and 491 KB in that order.
• Perform the allocation of processes using-
[Link] Fit Algorithm
[Link] Fit Algorithm
[Link] Fit Algorithm
Block sizes - 200 KB, 400 KB, 600 KB, 500
KB, 300 KB and 250 KB

FIRST FIT
Process Size Allocated to Block size Wastage
Process 1 357 Block 2 400 43
Process 2 210 Block 3 600 210
Process 3 468 Block 4 500 32
Process 4 491 Unallocated – –
BEST FIT

Process Size Allocated to Block size Wastage

Process 1 357 Block 2 400 43
Process 2 210 Block 6 250 40
Process 3 468 Block 4 500 32
Process 4 491 Block 3 600 109
WORST FIT

Process Size Allocated to Block size Wastage

Process 1 357 Block 3 600 243
Process 2 210 Block 4 500 290
Process 3 468 UNALLOCATED
Process 4 491 UNALLOCATED
PROBLEM – VARIABLE SIZE
PARTITION
Consider the following heap (figure) in which blank regions are
not in use and hatched regions are in use-

The sequence of requests for blocks of size 300, 25, 125, 50 can be satisfied if we
use-
[Link] first fit or best fit policy (any one)
[Link] fit but not best fit policy
[Link] fit but not first fit policy
[Link] of the above
Allocation Using First Fit Algorithm

• Process P1 = 300 units

• Process P2 = 25 units
• Process P3 = 125 units
• Process P4 = 50 units
Process Size Allocated to Block size Remaining
Process 1 300 Block 4 350 50
Process 2 25 Block 2 150 125
Process 3 125 Block 2 125 0
Process 4 50 Block 4 50 0
 Allocation Using Best Fit Algorithm

• Process P1 = 300 units

• Process P2 = 25 units
• Process P3 = 125 units
• Process P4 = 50 units
Process Size Allocated to Block size Remaining
Process 1 300 Block 4 350 50
Process 2 25 Block 4 50 25
Process 3 125 Block 2 125 25
Process 4 50 Block 4 Unallocated 0

Thus,
Only first fit allocation
policy succeeds in allocating
memory to all the processes.
•Option (B) is correct.
PRACTICE PROBLEM
• Process requests are given as;
• 25 K , 50 K , 100 K , 75 K

Determine the algorithm which can optimally satisfy this

requirement.
[Link] Fit algorithm
[Link] Fit Algorithm
[Link] of the two
[Link] of them