There are some classical synchronization problems that are used to illustrate the challenges of

process synchronization and inter-process communication (IPC) in an operating system.

These problems help in understanding how to manage concurrent processes and ensure data
consistency across multiple entities (processes or threads in the cases of OS)
Here are some of the most well-known classical synchronization problems −
 Dining Philosophers Problem
 Producer Consumer Problem
 Reader Writer Problem
 Sleeping Barber Problem

Reader–Writer Problem
Definition
The Reader–Writer Problem is a classic problem in Operating Systems that deals with
synchronization of processes accessing a shared resource (like a file or database).
 Readers → Only read data
 Writers → Modify (write) data
Problem:
Allow multiple readers simultaneously, but writers must have exclusive access.
Basic Concept Diagram
+----------------------+
| Shared Resource |
| (File/Database) |
+----------------------+
/ \
/ \
+-----------+ +-----------+
| Readers | | Writers |
+-----------+ +-----------+

Rules:
- Many Readers → Allowed at same time
- Writer → Only one at a time
- No Reader during Writing
🔹 Key Requirements
 1. Mutual Exclusion
o Writers must access resource one at a time

2. Concurrency
o Multiple readers can read simultaneously

3. No Starvation (Fairness)
o

o No process (reader/writer) should wait forever

🔹 Types of Reader–Writer Problems

1. Reader Priority Problem

 Readers are given priority
 Writers may starve (wait for long time)
2. Writer Priority Problem
 Writers are given priority
 Readers may be delayed
3. Fair (Balanced) Solution
 Equal priority to both
 No starvation
Working Diagram (Flow)
Start
|
Process arrives
|
-------------------
| |
Reader Writer
| |
If no writer If no reader &
writing → Read no writer → Write
| |
Else Wait Else Wait
| |
+-----------+
| Finish |
+-----------+
Solution Using Semaphore (Concept)
 Use semaphores to control access:
o mutex → protects reader count

o wrt → controls writer access

 Readers increase count and read together

 Writers wait until no readers are active
Real-Life Example
 Library system:
o Many students can read books at same time

o Only one person can edit/update the record

🔹 Advantages

 Efficient resource usage

 Supports concurrency
🔹 Disadvantages

 Starvation may occur

 Complex synchronization

Dining Philosophers Problem

Introduction

The Dining Philosophers Problem is a classical problem in Operating Systems introduced by

Edsger W. Dijkstra. It illustrates issues in process synchronization, deadlock, and resource

sharing.

Problem Description
  There are 5 philosophers sitting around a circular table.

 Each philosopher has:

o A plate of food

o One fork between each pair of philosophers (total 5 forks)

 To eat, a philosopher needs both left and right forks.

🔄 States of Philosopher:

1. Thinking

2. Hungry

3. Eating

Problems in Dining Philosophers

1. Deadlock

 If all philosophers pick up their left fork at the same time, none can pick the right

fork.

 Result: System gets stuck forever.

2. Starvation

 A philosopher may never get both forks, while others keep eating.

🎯 Objectives
  Avoid deadlock

 Avoid starvation

 Ensure fair resource allocation

✅ Solutions to Dining Philosophers Problem

✔️1. Resource Ordering Solution

 Number the forks (1 to 5).

 Each philosopher picks lower-numbered fork first, then higher.

👉 Prevents circular wait → avoids deadlock.

✔️2. At Most 4 Philosophers Solution

 Allow only 4 philosophers to sit at the table at once.

👉 At least one philosopher can always eat → no deadlock.

✔️3. Monitor (Best Standard Solution)

Use a monitor to control access.

Each philosopher can eat only if both neighbors are not eating.

4. Semaphore Solution

 Use 5 semaphores (one per philosopher) and one mutex.

🧠 Idea:

 Philosopher checks neighbors before eating.

 Uses wait() and signal() operations.

✔️5. Chandy/Misra Solution (Advanced)

 Uses tokens (fork ownership).

 Philosophers request forks only when needed.

👉 Avoids both deadlock and starvation.

Monitors in Process Synchronization

A Monitor (synchronization construct) is a high-level synchronization mechanism used to
control access to shared resources. It was introduced by C. A. R. Hoare to simplify process
synchronization and avoid errors that occur with low-level tools like semaphores.

Definition

A monitor is a programming construct that allows only one process to execute inside it at a
time, ensuring mutual exclusion automatically.

A monitor consists of:

 Shared variables → Data used by processes

 Procedures (functions) → Operations on shared data

 Condition variables → Used for waiting and signaling

Structure of Monitor
🔑 Key Features

 Ensures mutual exclusion automatically

 No need to use explicit wait() and signal() for locking

 Supports condition synchronization

 Easy to use and less error-prone than semaphores

Introduction of Deadlock in Operating System

Deadlock is a state in an operating system where two or more processes are stuck forever

because each is waiting for a resource held by another. It happens only when four

conditions exist: mutual exclusion, hold and wait, no preemption, and circular wait. For

example, P1 holds R1 and needs R2, while P2 holds R2 and needs R1, so both wait

forever. Deadlock can be handled using prevention, avoidance (Banker’s algorithm), or

detection and recovery.

Causes of Deadlock in Operating System

A process in an operating system typically uses resources in the following sequence:

 Request a resource

 Use the resource

 Release the resource

Deadlock arises when processes hold some resources while waiting for others.
Examples of Deadlock

There are several examples of deadlock. Some of them are mentioned below.

1. The system has 2 tape drives. P0 and P1 each hold one tape drive and each needs

another one.

2. Semaphores A and B, initialized to 1, P0, and P1 are in deadlock as follows:

 P0 executes wait(A) and preempts.

 P1 executes wait(B).

 Now P0 and P1 enter in deadlock.

P0 Action P1 Action

wait(A) wait(B)

wait(B) wait(A)

3. Assume the space is available for allocation of 200K bytes, and the following sequence

of events occurs.

P0 P1

Request 80KB; Request 70KB;

 P0 P1

Request 60KB; Request 80KB;

Deadlock occurs if both processes progress to their second request.

Necessary Conditions:
There are four conditions that must be met in order to achieve deadlock as follows.

1. Mutual Exclusion -
At least one resource must be kept in a non-shareable state; if another process
requests it, it must wait for it to be released.

2. Hold and Wait -

A process must hold at least one resource while also waiting for at least one
resource that another process is currently holding.

3. No preemption -
Once a process holds a resource (i.e. after its request is granted), that resource
cannot be taken away from that process until the process voluntarily releases it.

4. Circular Wait -
There must be a set of processes P0, P1, P2,..., PN such that every P[I] is waiting for
P[(I + 1) percent (N + 1)]. (It is important to note that this condition implies the
hold-and-wait condition, but dealing with the four conditions is easier if they are
considered separately).
The above image demonstrates a circular wait deadlock, here's how:

 P1 is holding R1 and waiting for R2 (which is held by P2).

 P2 is holding R2 and waiting for R3 (which is held by P3).

 P3 is holding R3 and waiting for R4 (which is held by P4).

 P4 is holding R4 and waiting for R1 (which is held by P1).

Methods for Handling Deadlocks

Deadlock is a situation in which a set of processes are blocked because each process is
holding a resource and waiting for another resource held by another process.

There are four main methods to handle deadlocks:

1. Deadlock Prevention

Deadlock prevention ensures that at least one of the necessary conditions for deadlock
never occurs.

Deadlock Conditions (must be prevented):

 Mutual Exclusion

 Hold and Wait

 No Preemption
 

 Circular Wait

Techniques:

 Eliminate Hold and Wait: Processes request all resources at once.

 Allow Preemption: Resources can be taken back if needed.

 Avoid Circular Wait: Assign ordering to resources and request in order.

Disadvantages:

 Leads to low resource utilization

 May cause process starvation

2. Deadlock Avoidance

Deadlock avoidance ensures the system never enters an unsafe state.

 Requires advance knowledge of resource requirements.

 The system checks whether allocation leads to a safe state.

Key Concept: Safe State

A system is in a safe state if there exists a sequence of processes such that each can
complete without causing deadlock.

Algorithm Used:

 Banker’s Algorithm

Advantages:

 More flexible than prevention

Disadvantages:

 Requires complete information about future requests

 Not suitable for dynamic systems

3. Deadlock Detection and Recovery

In this method, deadlocks are allowed to occur, then detected and corrected.

Detection:

 Use Resource Allocation Graph (RAG)

 Or Wait-for Graph

Recovery Techniques:

1. Process Termination

o Abort all deadlocked processes

o Abort one process at a time

2. Resource Preemption

o Temporarily take resources from processes

o Rollback and restart processes

Disadvantages:

 Loss of work

 Recovery is complex

 Not always efficient

4. Ignoring Deadlocks (Ostrich Algorithm)

 The system ignores deadlocks completely.

 Assumes deadlocks occur rarely.

Used In:

 Operating systems like UNIX and Windows

Advantages:

 Simple and no overhead

Disadvantages:
  System may freeze if deadlock occurs

Deadlock Detection:

 If deadlocks cannot be avoided, another approach is to detect them and recover in

some way.

 Aside from the performance hit of constantly checking for deadlocks, a

policy/algorithm for recovering from deadlocks must be in place, and when
processes must be aborted or have their resources preempted, there is the possibility
of lost work.

Recovery From Deadlock:

There are three basic approaches to getting out of a bind:

1. Inform the system operator and give him/her permission to intervene manually.

2. Stop one or more of the processes involved in the deadlock.

3. Prevent the use of resources.

Approach of Recovery from Deadlock:

Here, we will discuss the approach of Recovery From Deadlock as follows.

Approach-1:
Process Termination:
There are two basic approaches for recovering resources allocated to terminated processes
as follows.

1. Stop all processes that are involved in the deadlock. This does break the deadlock,
but at the expense of terminating more processes than are absolutely necessary.

2. Processes should be terminated one at a time until the deadlock is broken. This
method is more conservative, but it necessitates performing deadlock detection after
each step.

In the latter case, many factors can influence which processes are terminated next as
follows.

1. Priorities in the process

 2. How long has the process been running and how close it is to completion.

3. How many and what kind of resources does the process have? (Are they simple to
anticipate and restore?)

4. How many more resources are required for the process to be completed?

5. How many processes will have to be killed?

6. Whether the process is batch or interactive.

Approach-2:
Resource Preemption :
When allocating resources to break the deadlock, three critical issues must be addressed:

1. Selecting a victim -
Many of the decision criteria outlined above apply to determine which resources to
preempt from which processes.

2. Rollback -
A preempted process should ideally be rolled back to a safe state before the point at
which that resource was originally assigned to the process. Unfortunately,
determining such a safe state can be difficult or impossible, so the only safe rollback
is to start from the beginning. (In other words, halt and restart the process.)

3. Starvation -
How do you ensure that a process does not go hungry because its resources are
constantly being pre-empted? One option is to use a priority system and raise the
priority of a process whenever its resources are pre-empted. It should eventually
gain a high enough priority that it will no longer be pre-empted.

Memory Management in Operating System

Memory management is the process of controlling and organising a computer’s
memory by allocating portions, called blocks, to different executing
programmes to improve the overall system performance.
 The most important function of an operating system is to manage primary
memory.
  Supports multiple processes simultaneously in memory.
 Protects processes from unauthorised access.
 Enables swapping and virtual memory efficiently.

Levels (Top → Bottom)

1️⃣ Registers

 Located inside CPU

 Fastest memory

 Very small size

 Used for immediate operations

2️⃣ Cache Memory

 Very fast, close to CPU

 Stores frequently used data

 Faster than main memory

3️⃣ Main Memory (RAM)

 Stores programs currently in use

 Medium speed

 Volatile (data lost when power off)

4️⃣ Electronic Disk (SSD)

 Faster than traditional disks

 Non-volatile storage

 Used in modern systems

5️⃣ Magnetic Disk (Hard Disk)

 Slower than SSD

 Large storage capacity

 Stores OS, files, applications

6️⃣ Optical Disk

 Examples: CD, DVD

 Used for storage and backups

 Slower access

7️⃣ Magnetic Tapes

 Slowest memory

 Very large storage

 Used for backup and archival

 RAM (Random Access
Feature ROM (Read Only Memory)
Memory)

Meaning Temporary memory Permanent memory

Lost when power OFF Retained even when power OFF (Non-
Data Retention
(Volatile) volatile)

Usage Stores running programs & data Stores firmware/boot program

Speed Faster Slower than RAM

Read/Write Read and Write Mostly Read only

Examples DRAM, SRAM PROM, EPROM, EEPROM

Techniques in Memory Allocation

Used by an operating system to efficiently allocate, utilize, and manage memory resources for

processes. Various techniques help the operating system manage memory effectively. They

can be broadly categorized into:

Memory management is a fundamental function of an Operating System (OS) that manages

primary memory (RAM). It ensures efficient allocation, deallocation, and utilization of

memory among processes.

👉 Goals:

 Efficient use of memory

 Fast access for CPU

 Protection of processes

 Support multiprogramming

Swapping

Swapping is a memory management technique where processes are temporarily moved

between main memory and secondary storage to free up memory for other processes.

 Allows multiple processes to run efficiently.

 Lower-priority processes can be swapped out for higher-priority ones.

 Swapped-out processes resume when loaded back into memory.

 Transfer time depends on the amount of data moved.

Contiguous Memory Allocation

Each process is allocated a single continuous block of memory. All instructions and data of a

process are stored in adjacent memory locations.

Single Contiguous Memory Allocation

Simplest form of memory management. In this technique, the main memory is divided into

two parts:

 One part is reserved for the Operating System

 The remaining part is allocated to a single user process

Characteristics

 Only one user process can reside in memory at a time

 The operating system occupies a fixed portion of memory

 No multiprogramming is possible

 Simple to implement and manage

Advantages

 Simple memory management

 No fragmentation issues

Disadvantages

 Poor memory utilization

 No support for multitasking or multiprogramming

Partitioned Memory Allocation

Main memory is divided into multiple contiguous partitions, and each partition can hold one

process. This technique supports multiprogramming.

Partitioned memory allocation is further classified into:

a. Fixed Partition Allocation

 Memory is divided into a fixed number of partitions

 Each partition has a fixed size

 Each partition can store only one process

  Leads to internal fragmentation

b. Variable Partition Allocation

 Memory is divided into partitions dynamically based on process size

 Reduces internal fragmentation

 Suffers from external fragmentation

Advantages

 Supports multiprogramming

 Better memory utilization compared to single contiguous allocation

Disadvantages

 Fragmentation issues

 Complex memory management compared to single contiguous allocation

Non-Contiguous Memory Allocation

Memory management technique in which a process is divided into smaller parts and these

parts are stored in different, non-adjacent locations in main memory. Unlike contiguous

allocation, the entire process does not need to be placed in a single continuous block of

memory.

This technique is widely used in modern operating systems because it improves memory

utilization and reduces fragmentation problems.

Features of Non-Contiguous Memory Allocation

 A process can be stored in multiple memory locations

 Improves utilization of available memory

 Reduces external fragmentation

 Requires address translation using hardware support (MMU)

Advantages

 Better memory utilization

 Supports large programs

  Eliminates the need for contiguous free memory

Disadvantages

 More complex than contiguous allocation

 Additional overhead for address translation

 Requires extra memory for tables (page table / segment table)

Techniques Used in Non-Contiguous Memory Allocation

1. Paging: Divides a process into fixed-size pages and memory into frames of the same

size

2. Segmentation: Divides a process into logical segments of variable size such as code,

data, and stack

3. Segmentation with Paging: Combines logical segmentation with paging to reduce

fragmentation

Memory Management Mechanisms

Virtual Memory

 Lets a program run even if it is larger than physical RAM.

 Uses disk as an extension of main memory.

Page Replacement Algorithms(PRA)

 PRA Decide which page to remove from memory when it is full.

 FIFO: Remove the page that came first.

 LRU: Remove the page least recently used.

 Optimal: Remove the page not needed for the longest future time.

 LFU: Remove the page used least frequently.

Demand Paging

 Demand Paging loads only the pages a process actually needs into memory.

 Reduces unnecessary memory usage and I/O.

Memory Management Problems

Fragmentation

 Fragmentation Occurs when processes are loaded into and removed from memory,

resulting in unused memory spaces that cannot be efficiently utilized.

 Internal Fragmentation: Occurs when a process is allocated more memory than it

actually needs, leading to wasted space inside the allocated memory block.

 External Fragmentation: Occurs when free memory is divided into small, scattered

blocks, making it impossible to allocate a large contiguous block even though enough

total free memory exists.

Thrashing

 Thrashing occurs when the system spends most of its time swapping pages between

memory and disk instead of executing processes, causing very low CPU utilization.

Memory Allocation Strategies

Fixed Partition Allocation: Memory is divided into fixed-sized partitions, and each partition

can hold only one process. The OS keeps track of free and occupied partitions using

a partition table.

Dynamic Partition Allocation: Memory is divided into variable-sized partitions based on the

size of the processes. This helps avoid wastage of memory but can result in fragmentation.

Placement Algorithms: When allocating memory, the OS uses placement algorithms to

decide which free block should be assigned to a process:

 First Fit: Allocates the first available partition large enough to hold the process.

 Best Fit: Allocates the smallest available partition that fits the process, reducing

wasted space.

 Worst Fit: Allocates the largest available partition, leaving the largest remaining

space.
  Next Fit: Similar to First Fit but starts searching for free memory from the point of

the last allocation.

🔹 Basic Concepts

1. Logical Address vs Physical Address

 Logical Address: Generated by CPU

 Physical Address: Actual address in memory

 Address binding is done during:

o Compile time

o Load time

o Execution time

2. Memory Allocation

Memory is divided into partitions:

 Fixed Partitioning

 Dynamic Partitioning

🔹 Fragmentation

1. Internal Fragmentation

 Wasted space inside allocated memory

 Occurs in fixed partitioning

2. External Fragmentation

 Free memory scattered in small blocks

 Occurs in dynamic allocation

👉 Solution: Compaction (combine free spaces)

🔹 Non-Contiguous Memory Allocation.

Allows processes to be stored in different locations.

1. Paging
  Memory divided into:

o Pages (logical memory)

o Frames (physical memory)

 Fixed size blocks

 Eliminates external fragmentation

📌 Address structure:

 Page number + Offset

👉 Uses Page Table to map pages to frames

2. Segmentation

 Memory divided based on logical units:

o Code

o Data

o Stack

📌 Each segment has:

 Segment number

 Offset

👉 Provides better logical view but may cause external fragmentation

3. Segmentation with Paging

 Combination of both techniques

 Reduces fragmentation and improves efficiency

🔹 Virtual Memory

Virtual memory allows execution of processes larger than physical memory.

👉 Uses disk space as extension of RAM

Benefits:

 Large program execution

  Better memory utilization

 Increased multiprogramming

🔹 Demand Paging

 Pages are loaded only when required

 Reduces memory usage

Page Fault:

Occurs when required page is not in memory

👉 Steps:

1. Trap to OS

2. Load page from disk

3. Update page table

🔹 Page Replacement Algorithms

When memory is full, OS replaces pages using algorithms:

1. FIFO (First In First Out)

2. LRU (Least Recently Used)

3. Optimal Algorithm

👉 Goal: Minimize page faults

Swapping
Swapping is a memory management technique where processes are temporarily moved

between main memory and secondary storage to free up memory for other processes.

 Allows multiple processes to run efficiently.

 Lower-priority processes can be swapped out for higher-priority ones.

 Swapped-out processes resume when loaded back into memory.

 Transfer time depends on the amount of data moved.

Contiguous Memory Allocation

Each process is allocated a single continuous block of memory. All instructions and data of a

process are stored in adjacent memory locations.

Single Contiguous Memory Allocation

Simplest form of memory management. In this technique, the main memory is divided into

two parts:

 One part is reserved for the Operating System

 The remaining part is allocated to a single user process

Characteristics

 Only one user process can reside in memory at a time

 The operating system occupies a fixed portion of memory

 No multiprogramming is possible

 Simple to implement and manage

Advantages

 Simple memory management

 No fragmentation issues

Disadvantages

 Poor memory utilization

 No support for multitasking or multiprogramming

Partitioned Memory Allocation

Main memory is divided into multiple contiguous partitions, and each partition can hold one

process. This technique supports multiprogramming.

Partitioned memory allocation is further classified into:

Fixed Partition Allocation

 Memory is divided into a fixed number of partitions

 Each partition has a fixed size

 Each partition can store only one process

  Leads to internal fragmentation

 Once partitions are defined operating system keeps track of the status of memory

partitions it is done through a data structure called a partition table.

Variable Partition Allocation

 Memory is divided into partitions dynamically based on process size

 Reduces internal fragmentation

 Suffers from external fragmentation

Advantages

 Supports multiprogramming

 Better memory utilization compared to single contiguous allocation

Disadvantages

 Fragmentation issues

 Complex memory management compared to single contiguous allocation

Non-Contiguous Memory Allocation

Memory management technique in which a process is divided into smaller parts and these

parts are stored in different, non-adjacent locations in main memory. Unlike contiguous

allocation, the entire process does not need to be placed in a single continuous block of

memory.

This technique is widely used in modern operating systems because it improves memory

utilization and reduces fragmentation problems.

Features of Non-Contiguous Memory Allocation

 A process can be stored in multiple memory locations

 Improves utilization of available memory

 Reduces external fragmentation

  Requires address translation using hardware support (MMU)

Advantages

 Better memory utilization

 Supports large programs

 Eliminates the need for contiguous free memory

Disadvantages

 More complex than contiguous allocation

 Additional overhead for address translation

 Requires extra memory for tables (page table / segment table)

Techniques Used in Non-Contiguous Memory Allocation

1. Paging: Divides a process into fixed-size pages and memory into frames of the same

size

2. Segmentation: Divides a process into logical segments of variable size such as code,

data, and stack

3. Segmentation with Paging: Combines logical segmentation with paging to reduce

fragmentation

Memory Management Problems

Fragmentation

 Fragmentation Occurs when processes are loaded into and removed from memory,

resulting in unused memory spaces that cannot be efficiently utilized.

 Internal Fragmentation: Occurs when a process is allocated more memory than it

actually needs, leading to wasted space inside the allocated memory block.

 External Fragmentation: Occurs when free memory is divided into small, scattered

blocks, making it impossible to allocate a large contiguous block even though enough

total free memory exists.

Thrashing
  Thrashing occurs when the system spends most of its time swapping pages between

memory and disk instead of executing processes, causing very low CPU utilization.

Memory Allocation Strategies

 First Fit: Allocates the first available partition large enough to hold the process.

 Best Fit: Allocates the smallest available partition that fits the process, reducing

wasted space.

 Worst Fit: Allocates the largest available partition, leaving the largest remaining

space.

 Next Fit: Similar to First Fit but starts searching for free memory from the point of

the last allocation.

First-Fit Allocation in Operating Systems

In an operating system (OS), memory management is a critical function that ensures

efficient allocation and utilization of memory resources. When processes are initiated,

they require execution time and storage space, which is allocated in memory blocks. The

OS uses various memory allocation algorithms to manage the assignment of memory to

these incoming processes.

The following are the most used algorithms:

1. First Fit

2. Best Fit

3. Worst Fit

4. Next Fit

First-Fit Memory Allocation

The First Fit method works by searching through memory blocks from the beginning,

looking for the first block that can fit the process.

 For any process Pn, the operating system looks through the available memory blocks.

 It allocates the first block that is free and large enough to hold the process.
In simple terms, First Fit simply finds the first available block that can fit the process and

assigns it there. It's a straightforward and fast way to allocate memory.

Advantages of First Fit Algorithm

The First Fit algorithm in operating systems offers several benefits:

1. It is straightforward to implement and easy to understand, making it ideal for systems

with limited computational power.

2. Memory can be allocated quickly when a suitable free block is found at the start.

3. When processes have similar memory sizes, First Fit can help minimize fragmentation

by utilizing the first available block that fits the process.

Disadvantages of First Fit Algorithm

Despite its advantages, the First Fit algorithm has a few downsides:

1. Over time, First Fit can lead to both external fragmentation, where small free memory

blocks are scattered, and internal fragmentation, where allocated memory exceeds the

process’s requirement, wasting space.

2. It may not always allocate memory in the most efficient manner, leading to

suboptimal use of available memory.

 3. For large processes, First Fit can be less efficient, as it may need to search through

numerous smaller blocks before finding an appropriate one, which can slow down

memory allocation.

Memory Blocks: 100, 500, 200, 300, 600

Processes: 212, 417, 112, 426

🔹 Step-by-Step Allocation

Process Allocation Remaining Block

212 500 → (500-212) 288
417 600 → (600-417) 183
112 288 → (288-112) 176
426 ❌ Not Allocated —

Final Blocks: 100, 176, 200, 300, 183

Not Allocated: 426 KB

2. What is Best Fit Algorithm?
The Best Fit Algorithm allocates searches the entire memory to find

the smallest available block that is large enough to accommodate the process. This

means that, the algorithm looks for the block that will leave the least amount of unused

space after allocation. The main aim of the Best Fit Algorithm is reduce fragmentation

and wastage of memory.

Advantages of Best Fit Algorithm

The Best Fit Algorithm have the following advantages −

 Reduced External Fragmentation − By allocating the smallest possible block to a

process, the Best Fit Algorithm helps in reducing external fragmentation.

 Efficient Memory Utilization − The Best Fit Algorithm ensures that memory is

utilized efficiently by minimizing the amount of wasted space after allocation.

  Best for Small Processes − The Best Fit Algorithm is considered to be more suitable

for small processes.

Disadvantages of Best Fit Algorithm

The Best Fit Algorithm has some drawbacks −

 High Search Time − The Best Fit Algorithm requires searching the entire memory

for the smallest suitable block, which can increase allocation time.

 Fragmentation − Even though it reduces external fragmentation, it can cause internal

fragmentation. Because processes may not fully utilize the allocated blocks.

 Not Suitable for Large Processes − The Best Fit Algorithm may struggle to find

suitable blocks for larger processes. This leads to more "Not Allocated" statuses.

3. Worst fit:

Worst-Fit Memory Allocation

In Worst-Fit Memory Allocation allocation technique, the process traverses the whole

memory and always search for the largest hole/partition, and then the process is placed in that

hole/partition. It is a slow process because it has to traverse the entire memory to search the

largest hole.

Advantages of Worst-Fit Allocation

 Reduces Chances of Small Fragments: By allocating the largest available block,

worst fit leaves larger leftover fragments, which are more likely to be useful for future

allocations.

 Simple to Implement: The logic is straightforward: find the largest block that can fit

the process and allocate it.

 Efficient for Large Processes: It always looks for the biggest space, large processes

may find better fits compared to other strategies like Best Fit or First Fit.
Disadvantages of Worst-Fit Allocation

 External Fragmentation: Worst-Fit Allocation can lead to significant external

fragmentation. By allocating the largest available block, it often leaves behind many

smaller, unusable fragments of memory.

 Inefficient Memory Usage: Allocating the largest block to a process, even if it's

much larger than required, can lead to inefficient memory usage.

 Lower Allocation Time: Worst-Fit requires the operating system to search for the

largest available block, which can be slower than methods like First-Fit or Next-Fit,

especially if there are many free blocks.

Logical and Physical Address in Operating System

Memory access in operating systems happens through two types of addresses: logical

(virtual) and physical. The Memory Management Unit (MMU) sits between the CPU and

the physical memory. Its job is to translate every logical address into the correct physical

address.

 Programs to believe they have a large, continuous memory space

 The OS protects one process’s memory from another process

 Efficient use of RAM through paging, segmentation, or both

Whenever the CPU accesses memory, it sends a logical address → the MMU converts it

→ the corresponding physical address in RAM is accessed.

Logical Address

A logical address is generated by the CPU while a program runs. It represents the address

from the process’s perspective and does not exist physically, hence it is also called a

virtual address.

 The logical address space is the set of all logical addresses a process can generate.
 Programs use logical addresses to reference memory, and the MMU translates them

into physical addresses when accessing actual memory.

Physical Address

A physical address is the real location in main memory (RAM) where data or instructions

are stored. The physical address space consists of all physical addresses corresponding to

logical addresses.

 The MMU performs address translation using a page table, mapping each logical page

to a physical frame.

 This allows processes to access memory transparently, without knowing actual

memory locations.

Similarities in Logical and Physical Addresses

 Both logical and physical addresses are used to identify a specific location in memory.

 Each address type can be represented in different formats such as binary,

hexadecimal, or decimal.

 They have a finite range, which is determined by the number of bits used to represent

them.

Memory Management Unit

The Memory Management Unit (MMU) is a hardware component in the computer system

that handles all memory and caching operations associated with the CPU. Its main

function is to translate logical (virtual) addresses generated by the CPU into physical

addresses in main memory.

Key functions of Memory Management Unit

 Logical addresses provide abstraction, so processes don’t need to know physical

locations.

 These logical addresses are translated into physical addresses using a page table.

 Translation is transparent and handled by hardware (MMU).

 Enables efficient memory management through paging and segmentation.

Logical Address vs. Physical Address

Logical Address Physical Address

Generated by the CPU during program Generated by the Memory Management

execution Unit (MMU)

Logical Address Space is set of all Physical Address is set of all physical

logical addresses generated by CPU in addresses mapped to the corresponding

reference to a program. logical addresses.

User can view and access the logical

User can never view physical address of
ad
program.
dress of a program.

Can change during program execution Generally fixed once assigned in

(due to relocation, paging, etc.) memory

The user can use the logical address to The user can indirectly access physical

access the physical address. address but not directly.

Logical address can be change. Physical address will not change.

Virtual address. Real address.

Paging and Segmentation
Paging divides memory into fixed-size blocks called pages, which simplifies management by

treating memory as a uniform structure. In contrast, segmentation divides memory into

variable-sized segments based on logical units such as functions, arrays, or data structures.

Both methods offer distinct advantages and are chosen based on the specific needs and

complexities of applications and system architectures. Often, modern systems combine both

techniques to leverage the benefits of each.

Paging

Paging is a method or technique which is used for non-contiguous memory allocation. It is a

fixed-size partitioning theme (scheme). In paging, both main memory and secondary memory

are divided into equal fixed-size partitions. The partitions of the secondary memory area unit

and main memory area unit are known as pages and frames respectively.

Features of Paging

 Fixed-Size Division: Memory is divided into fixed-size pages, simplifying memory

management.

 Hardware-Defined Page Size: Page size is set by hardware and is uniform across all

pages.

 OS-Managed: The operating system handles paging, including maintaining page

tables and free frame lists.

 Eliminates External Fragmentation: Paging avoids external fragmentation but can

suffer from internal fragmentation.

 Invisible to User: Paging is transparent to programmers and users, simplifying

software development.
Paging is a memory management method accustomed to fetching processes from the

secondary memory into the main memory in the form of pages. in paging, each process is

split into parts wherever the size of every part is the same as the page size.

The size of the last half could also be but the page size. The pages of the process area unit

hold on within the frames of main memory relying upon their accessibility.

Segmentatio

Segmentation is another non-contiguous memory allocation scheme, similar to paging.

However, unlike paging which divides a process into fixed-size pages segmentation divides

memory into variable-sized segments that correspond to logical units such as functions,

arrays, or data structures.

Features of Segmentation

 Variable-Size Division: Memory is divided into logical segments of varying sizes

based on program structure.

 User/Programmer-Defined Sizes: Segment sizes are defined by the programmer or

compiler, reflecting logical program units.

  Compiler-Managed: Segmentation is primarily managed by the compiler, with OS

support for memory allocation.

 Supports Sharing and Protection: Segmentation facilitates sharing code/data between

processes and easy implementation of protection.

 Visible to User: Segmentation is visible to programmers, allowing better control over

logical memory organization.

In segmentation, both main memory and secondary memory are not divided into equal-sized

partitions. Instead, they are split into segments of varying sizes. These segments are tracked

using a data structure called the segment table.

The segment table stores information about each segment, primarily:

 Base: The starting physical address of the segment in memory.

 Limit: The length (or size) of the segment.

When accessing memory, the CPU generates a logical address composed of:

 A Segment Number

 A Segment Offset

The MMU (Memory Management Unit) uses the segment number to find the corresponding

base and limit in the segment table. If the offset is less than the limit, the address is

considered valid, and the physical address is computed by adding the offset to the base.

If the offset exceeds the limit, an error (segmentation fault) occurs, indicating an invalid

address access attempt.

The above figure shows the translation of a logical address to a physical address.

Paging vs. Segmentation

Feature Paging Segmentation

Division Unit Fixed-size pages Variable-size segments

Managed By Operating system Compiler

Unit Size Determined By Hardware User/programmer

Page number + page Segment number + segment

Address Structure offset offset

Data Structure Used Page table Segment table

Fragmentation Type Internal fragmentation External fragmentation

Feature Paging Segmentation

Speed Faster Slower

Programmer Visibility Invisible to the user Visible to the user

Sharing Difficult Easy

Data Structure Handling Inefficient Efficient

Protection Hard to implement Easier to apply

Size Constraints Page = Frame size No fixed size required

Memory Unit
Physical unit Logical unit
Perspective

System Efficiency Less efficient More efficient

Assignment Questions :

1. What is contiguous memory allocation?

2. What is virtual memory?
3. What is swapping?
4. What is monitor?
5. Define Paging.
6. Explain reader-writers problem.
7. Write note on Semaphore.
8. Explain deadlock avoidance with example.
9. Briefly explain Logical versus Physical Address Space?
10. Discuss in detail Contiguous Memory Allocation.