OPERATING SYSTEMS CS F372

BIJU K RAVEENDRAN & TEAM

LECT #36: MEMORY MANAGEMENT

•
Allocation
Contiguous allocation
Mechanisms
– Single partition allocation
• Base and limit registers are used
– Multiple partition allocation
• Holes [external fragmentation]
• Partitioned allocation
– Equal size partitions
• Program should fit in a partition else design with overlays
• Internal fragmentation
– Unequal size partitions
• Queue for each partition
Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 2
 Contiguous Allocation
• Main memory usually into two partitions:
– Resident operating system, usually held in low memory with
interrupt vector
– User processes then held in high memory
• Single-partition allocation
– 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

Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 3

Hardware support for Relocation and Limit Registers

Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 4

 Contiguous Allocation
• Multiple-partition allocation
– 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
– Operating system maintains information about:
a) allocated partitions b) free partitions (hole)

Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 5

 Contiguous Allocation

OS OS OS OS

process 5 process 5 process 5 process 5

process 9 process 9

process 8 process 10

process 2 process 2 process 2 process 2

Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 6

 Fixed Partitioning
• Equal-size partitions
– A process size <= partition size can be loaded into an
available partition
– If all partitions are full, the operating system can
swap a process out of a partition
– A program may not fit in a partition.
• Main memory use is inefficient. Any program, no
matter how small, occupies an entire partition.
– Results in internal fragmentation.

Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 7

Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 8
 Placement Algorithm with Partitions
• Equal-size partitions
– Because all partitions are of equal size, it
does not matter which partition is used
• Unequal-size partitions
– Can assign each process to the smallest
partition within which it will fit
– Queue for each partition
– Processes are assigned in such a way as to
minimize wasted memory
Friday, April 11, 2025
within a partition
Biju K Raveendran @ BITS Pilani Goa 9
Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 10
 Multiprogramming with Fixed Partitions

• Fixed memory partitions

– separate input queues for each partition
– single input queue
Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 11
 Dynamic Partitioning
• Partitions are of variable length and number
• Process is allocated exactly as much memory as
required
• Eventually get holes in the memory. This is
called external fragmentation
• Must use compaction to shift processes so they
are contiguous and all free memory is in one
block

Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 12

Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 13
 Dynamic Partitioning Placement Algorithm
• Operating system must decide which free block to
allocate to a process
• FIT algorithms to find the block
– Best-fit algorithm
• Chooses the block that is closest in size to the request
– First-fit algorithm
• Chooses the first available [from top] block that is large enough
– Next-fit
• Scans memory from the location of the last placement
– Worst-fit
• Allocate the largest hole
Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 14
Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 15
 Buddy System
• Entire space available is treated as a single block
of 2U
• If a request of size s such that 2U-1 < s <= 2U,
entire block is allocated
– Otherwise block is split into two equal
buddies
– Process continues until smallest block greater
than or equal to s is generated

Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 16

Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 17
Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 18
 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 is memory internal to a partition,
but not being used
• 50 % rule. ( N allocated block & 0.5N waste) [1/3 may be unusable]
• 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
– I/O problem
• Latch job in memory while it is involved in I/O
• Do I/O only into OS buffers
Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 19
 Paging
• Divide physical memory into fixed-sized blocks [frames]
– Size is power of 2
• Divide logical memory into blocks of same size [pages]
• Keep track of all free frames
• To run a process of size N pages, need to find N free
frames [Max]
• Set up a page table to translate logical to physical
addresses
• Backing storage split into pages
• Internal fragmentation
Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 20
 Paging
• Logical address space of a process can be noncontiguous; process is
allocated physical memory whenever the latter is available
• Divide physical memory into fixed-sized blocks called frames (size is
power of 2, between 512 bytes and 8,192 bytes)
• Divide logical memory into blocks of same size called pages
• Keep track of all free frames
• To run a program of size n pages, need to find n free frames and
load program
• Set up a page table to translate logical to physical addresses
• Backing storage split into pages
• Internal fragmentation

Friday, April 11, 2025 Biju K Raveendran @ BITS Pilani Goa 21