BCS401 Operating System Semester IV · AY 2025-26 onward
Unit 4 · Memory Management

Lecture 3: Multiprogramming with variable partitions

Back to contents ← Previous Next →

Learning outcomes

  • Explain variable partitioning and the issues of external fragmentation.
Lecture Notes

Main content

Study Notes: Multiprogramming with Variable Partitions, Protection Schemes, and Paging

These notes explain three important memory-management concepts in Operating Systems: multiprogramming with variable partitions, memory protection schemes, and paging. The aim is to understand how memory is allocated, protected, and translated efficiently in a multiprogrammed system.

Memory Management Contiguous Allocation Protection Paging TLB

1. Multiprogramming with Variable Partitions

1.1 Meaning

In a multiprogramming system, several processes are kept in main memory at the same time so that the CPU always has work to do. In variable partition allocation, memory is divided dynamically according to the actual size required by each process. Unlike fixed partitions, the operating system does not define partition sizes in advance.

Key idea: A process is allocated a contiguous block of memory just large enough for it. If a free block is larger than needed, it is split into an allocated part and a remaining free hole.
OS P1 120 KB Hole 80 KB P2 150 KB Hole 95 KB P3 60 KB Hole 70 KB Main Memory with Dynamically Created Variable Partitions
Figure 1: Memory is split into allocated partitions and free holes of different sizes.

1.2 How it works

  1. Main memory initially contains the operating system and one large free block.
  2. When a process arrives, the OS searches for a hole large enough to hold it.
  3. If the hole is larger than needed, the hole is split.
  4. When a process terminates, its memory becomes free again.
  5. If adjacent free holes exist, they are merged to create a larger hole.

1.3 Allocation strategies

Strategy Idea Advantage Drawback
First Fit Allocate the first hole that is large enough. Fast and simple. May leave many small holes near the beginning of memory.
Best Fit Allocate the smallest hole that is still large enough. Tries to reduce leftover waste in one allocation. Usually requires more searching and may create many tiny unusable holes.
Worst Fit Allocate the largest available hole. Leaves a relatively large remaining hole. Often performs poorly overall.

1.4 Fragmentation

The major problem of variable partition allocation is external fragmentation. Total free memory may be sufficient, but it may be split into many small noncontiguous holes. As a result, a process still cannot be loaded.

Type of Fragmentation Meaning Common in Variable Partitions?
External Fragmentation Free memory exists, but it is scattered into small pieces. Yes, this is the main problem.
Internal Fragmentation Unused memory exists inside an allocated block. Usually much less important here than external fragmentation.

1.5 Compaction

Compaction is a technique used to reduce external fragmentation. The OS moves processes so that all free memory is combined into one large block. This makes allocation easier, but compaction is expensive because moving processes in memory takes time and requires relocation support.

Mini Example

Suppose free holes are 40 KB, 15 KB, 70 KB, 25 KB and a new process needs 20 KB.

  • First Fit allocates from 40 KB, leaving 20 KB.
  • Best Fit allocates from 25 KB, leaving 5 KB.
  • Worst Fit allocates from 70 KB, leaving 50 KB.

Which one is best depends on future requests, so there is no magic wand here.

1.6 Advantages

  • Better flexibility than fixed partitions.
  • Processes of different sizes can be loaded.
  • Memory is allocated roughly according to actual need.

1.7 Disadvantages

  • External fragmentation is serious.
  • Searching and bookkeeping overhead are present.
  • Compaction may be required and is costly.

2. Protection Schemes

2.1 Why memory protection is needed

Memory protection prevents one process from reading or writing another process’s memory and also prevents user programs from damaging the operating system area. Without protection, one faulty program can corrupt the whole system.

2.2 Base (Relocation) and Limit Register Scheme

In contiguous memory allocation, a simple and effective protection mechanism uses two hardware registers:

  • Relocation/Base Register: stores the starting physical address of the process.
  • Limit Register: stores the size of the process address space.
If logical address < limit, then physical address = base + logical address
Else trap to operating system
CPU Base Register = 1400 Limit Register = 500 Address Check Valid Access Physical = 1400 + logical Invalid Access Trap / Protection Fault
Figure 2: The relocation/base and limit register scheme checks every address reference.

2.3 Working of the scheme

  1. The CPU generates a logical address.
  2. The hardware checks whether the logical address is less than the limit.
  3. If it is valid, the base register is added to generate the physical address.
  4. If it is invalid, a protection trap occurs.

2.4 Protection in paging

Paging supports protection more flexibly because each page-table entry can contain control bits.

Protection Item Purpose
Valid / Invalid Bit Shows whether the page belongs to the logical address space of the process.
Read / Write / Execute Bits Control permitted operations on a page.
Trap on Violation If a process performs an illegal access, the hardware transfers control to the OS.
Memory protection summary: In contiguous allocation, protection is usually enforced with base and limit registers. In paging, protection is enforced using page-table bits such as valid-invalid and access bits.

3. Paging

3.1 Meaning

Paging is a noncontiguous memory-allocation technique that divides a process’s logical memory into fixed-size pages and physical memory into fixed-size frames. A page can be placed in any free frame.

Main benefit: Paging eliminates the need for contiguous physical memory and removes the major external-fragmentation problem of variable partition allocation.

3.2 Basic terms

Term Meaning
Page A fixed-size block of logical memory.
Frame A fixed-size block of physical memory.
Page Table A table that maps page numbers to frame numbers.
Offset The displacement within a page or frame.
Logical Address [ Page No | Offset ] Page Table Page 0 → Frame 5 Page 1 → Frame 2 Physical Address [ Frame No | Offset ] Physical Memory Frame 0 Frame 1 Frame 2 ← Page 1 Frame 3 Frame 4 Frame 5 ← Page 0 Frame 6
Figure 3: Paging translates a logical page number into a physical frame number.

3.3 Address translation

If the page size is 2n bytes, then a logical address is divided into:

  • p: page number
  • d: offset within the page
Physical Address = (Frame Number × Frame Size) + Offset

3.4 Numerical example

Given: Page size = 1024 bytes

Logical address: 2050

Page number = 2050 / 1024 = 2
Offset = 2050 mod 1024 = 2

If the page table says Page 2 → Frame 7, then:

Physical Address = (7 × 1024) + 2 = 7170

3.5 Translation Lookaside Buffer (TLB)

A TLB is a small, fast associative memory that stores recently used page-table entries. Without a TLB, every memory reference may require an extra access to the page table. With a TLB hit, translation becomes much faster.

CPU TLB Fast lookup Page → Frame Hit / Miss Page Table Main memory lookup Memory Access
Figure 4: TLB speeds up page translation by caching recent page-table entries.

3.6 Advantages of paging

  • Eliminates external fragmentation.
  • Does not require contiguous physical allocation.
  • Supports protection at page level.
  • Supports sharing of code and data pages.
  • Forms the basis of virtual memory.

3.7 Disadvantages of paging

  • Causes internal fragmentation, especially in the last page.
  • Requires page-table storage overhead.
  • Adds address-translation overhead.
  • Needs hardware support such as page tables and TLB.

4. Variable Partitions vs Paging

Basis Variable Partitions Paging
Allocation style Contiguous Noncontiguous
Size of blocks Variable Fixed-size pages and frames
Main issue External fragmentation Internal fragmentation
Protection method Base/relocation + limit register Valid-invalid bit and protection bits
Need for compaction Often yes No, not for external fragmentation
Page table needed No Yes

5. Quick Exam Notes

Multiprogramming with Variable Partitions: Memory is allocated dynamically in variable-size contiguous blocks. It is flexible but suffers from external fragmentation.

Protection Schemes: Protection ensures one process cannot damage another or the OS. Base-limit registers are used in contiguous allocation; protection bits are used in paging.

Paging: Logical memory is divided into pages and physical memory into frames. It removes external fragmentation and supports virtual memory, but adds page-table and translation overhead.

6. Likely University Questions

  1. Explain multiprogramming with variable partitions with diagram.
  2. Differentiate between first fit, best fit, and worst fit.
  3. What is external fragmentation? Explain compaction.
  4. Explain memory protection using relocation and limit registers.
  5. What is paging? Explain address translation with a neat diagram.
  6. What is a TLB? Why is it needed?
  7. Differentiate between variable partition allocation and paging.