Memory Management in Operating

System (OS)
What do you mean by memory management?

Memory is the important part of the computer that is used to store the data. Its
management is critical to the computer system because the amount of main
memory available in a computer system is very limited. At any time, many
processes are competing for it. Moreover, to increase performance, several
processes are executed simultaneously. For this, we must keep several
processes in the main memory, so it is even more important to manage them
effectively.

Role of Memory management

Following are the important roles of memory management in a computer
system:

o Memory manager is used to keep track of the status of memory

locations, whether it is free or allocated. It addresses primary memory
by providing abstractions so that software perceives a large memory
is allocated to it.
o Memory manager permits computers with a small amount of main
memory to execute programs larger than the size or amount of
available memory. It does this by moving information back and forth
between primary memory and secondary memory by using the
concept of swapping.
o The memory manager is responsible for protecting the memory
allocated to each process from being corrupted by another process. If
 this is not ensured, then the system may exhibit unpredictable
behavior.
o Memory managers should enable sharing of memory space between
processes. Thus, two programs can reside at the same memory
location although at different times.

Memory Management Techniques:

The memory management techniques can be classified into following main
categories:

o Contiguous memory management schemes

o Non-Contiguous memory management schemes

Contiguous memory management schemes:

In a Contiguous memory management scheme, each program occupies a
single contiguous block of storage locations, i.e., a set of memory locations with
consecutive addresses.

Single contiguous memory management schemes:

The Single contiguous memory management scheme is the simplest memory
management scheme used in the earliest generation of computer systems. In
this scheme, the main memory is divided into two contiguous areas or
partitions. The operating systems reside permanently in one partition,
generally at the lower memory, and the user process is loaded into the other
partition.

Advantages of Single contiguous memory management schemes:

 o Simple to implement.
o Easy to manage and design.
o In a Single contiguous memory management scheme, once a process
is loaded, it is given full processor's time, and no other processor will
interrupt it.
Disadvantages of Single contiguous memory management schemes:

o Wastage of memory space due to unused memory as the process is

unlikely to use all the available memory space.
o The CPU remains idle, waiting for the disk to load the binary image
into the main memory.
o It can not be executed if the program is too large to fit the entire
available main memory space.
o It does not support multiprogramming, i.e., it cannot handle multiple
programs simultaneously.

Multiple Partitioning:
The single Contiguous memory management scheme is inefficient as it limits
computers to execute only one program at a time resulting in wastage in
memory space and CPU time. The problem of inefficient CPU use can be
overcome using multiprogramming that allows more than one program to run
concurrently. To switch between two processes, the operating systems need to
load both processes into the main memory. The operating system needs to
divide the available main memory into multiple parts to load multiple
processes into the main memory. Thus multiple processes can reside in the
main memory simultaneously.

The multiple partitioning schemes can be of two types:

o Fixed Partitioning
o Dynamic Partitioning

Fixed Partitioning
The main memory is divided into several fixed-sized partitions in a fixed
partition memory management scheme or static partitioning. These partitions
can be of the same size or different sizes. Each partition can hold a single
process. The number of partitions determines the degree of
multiprogramming, i.e., the maximum number of processes in memory. These
partitions are made at the time of system generation and remain fixed after
that.

Advantages of Fixed Partitioning memory management schemes:

o Simple to implement.
 o Easy to manage and design.
Disadvantages of Fixed Partitioning memory management schemes:

o This scheme suffers from internal fragmentation.

o The number of partitions is specified at the time of system generation.

Dynamic Partitioning
The dynamic partitioning was designed to overcome the problems of a fixed
partitioning scheme. In a dynamic partitioning scheme, each process occupies
only as much memory as they require when loaded for processing. Requested
processes are allocated memory until the entire physical memory is exhausted
or the remaining space is insufficient to hold the requesting process. In this
scheme the partitions used are of variable size, and the number of partitions is
not defined at the system generation time.

Advantages of Dynamic Partitioning memory management schemes:

o Simple to implement.
o Easy to manage and design.
Disadvantages of Dynamic Partitioning memory management schemes:

o This scheme also suffers from internal fragmentation.

o The number of partitions is specified at the time of system
segmentation.

Non-Contiguous memory management schemes:

In a Non-Contiguous memory management scheme, the program is divided
into different blocks and loaded at different portions of the memory that need
not necessarily be adjacent to one another. This scheme can be classified
depending upon the size of blocks and whether the blocks reside in the main
memory or not.

What is paging?
Paging is a technique that eliminates the requirements of contiguous
allocation of main memory. In this, the main memory is divided into fixed-size
blocks of physical memory called frames. The size of a frame should be kept the
same as that of a page to maximize the main memory and avoid external
fragmentation.

Advantages of paging:

o Pages reduce external fragmentation.

o Simple to implement.
 o Memory efficient.
o Due to the equal size of frames, swapping becomes very easy.
o It is used for faster access of data.

What is Segmentation?
Segmentation is a technique that eliminates the requirements of contiguous
allocation of main memory. In this, the main memory is divided into variable-
size blocks of physical memory called segments. It is based on the way the
programmer follows to structure their programs. With segmented memory
allocation, each job is divided into several segments of different sizes, one for
each module. Functions, subroutines, stack, array, etc., are examples of such
modules.

Operating System - Memory

Management

Next
Memory management is the functionality of an operating system which
handles or manages primary memory and moves processes back and forth
between main memory and disk during execution. Memory management
keeps track of each and every memory location, regardless of either it is
allocated to some process or it is free. It checks how much memory is to be
allocated to processes. It decides which process will get memory at what
time. It tracks whenever some memory gets freed or unallocated and
correspondingly it updates the status.

This tutorial will teach you basic concepts related to Memory Management.

Process Address Space

The process address space is the set of logical addresses that a process
references in its code. For example, when 32-bit addressing is in use,
addresses can range from 0 to 0x7fffffff; that is, 2^31 possible numbers, for
a total theoretical size of 2 gigabytes.

The operating system takes care of mapping the logical addresses to physical
addresses at the time of memory allocation to the program. There are three
types of addresses used in a program before and after memory is allocated −

S.N. Memory Addresses & Description

1 Symbolic addresses
 The addresses used in a source code. The variable names, constants, and instruction
labels are the basic elements of the symbolic address space.

Relative addresses
2 At the time of compilation, a compiler converts symbolic addresses into relative
addresses.

Physical addresses
3 The loader generates these addresses at the time when a program is loaded into main
memory.

Virtual and physical addresses are the same in compile-time and load-time
address-binding schemes. Virtual and physical addresses differ in execution-
time address-binding scheme.

The set of all logical addresses generated by a program is referred to as

a logical address space. The set of all physical addresses corresponding to
these logical addresses is referred to as a physical address space.

The runtime mapping from virtual to physical address is done by the memory
management unit (MMU) which is a hardware device. MMU uses following
mechanism to convert virtual address to physical address.

• The value in the base register is added to every address generated by a

user process, which is treated as offset at the time it is sent to memory.
For example, if the base register value is 10000, then an attempt by the
user to use address location 100 will be dynamically reallocated to
location 10100.
• The user program deals with virtual addresses; it never sees the real
physical addresses.

Swapping
Swapping is a mechanism in which a process can be swapped temporarily out
of main memory (or move) to secondary storage (disk) and make that
memory available to other processes. At some later time, the system swaps
back the process from the secondary storage to main memory.

Though performance is usually affected by swapping process but it helps in

running multiple and big processes in parallel and that's the reason Swapping
is also known as a technique for memory compaction.
The total time taken by swapping process includes the time it takes to move
the entire process to a secondary disk and then to copy the process back to
memory, as well as the time the process takes to regain main memory.

Let us assume that the user process is of size 2048KB and on a standard
hard disk where swapping will take place has a data transfer rate around 1
MB per second. The actual transfer of the 1000K process to or from memory
will take

2048KB / 1024KB per second

= 2 seconds
= 2000 milliseconds

Now considering in and out time, it will take complete 4000 milliseconds plus
other overhead where the process competes to regain main memory.

Memory Allocation
Main memory usually has two partitions −

• Low Memory − Operating system resides in this memory.

• High Memory − User processes are held in high memory.

Operating system uses the following memory allocation mechanism.

S.N. Memory Allocation & Description

 Single-partition allocation
In this type of allocation, relocation-register scheme is used to protect user processes
1 from each other, and from changing operating-system code and data. Relocation
register contains value of smallest physical address whereas limit register contains
range of logical addresses. Each logical address must be less than the limit register.

Multiple-partition allocation
In this type of allocation, main memory is divided into a number of fixed-sized
2 partitions where each partition should contain only one process. When a partition is
free, a process is selected from the input queue and is loaded into the free partition.
When the process terminates, the partition becomes available for another process.

Fragmentation
As processes are loaded and removed from memory, the free memory space
is broken into little pieces. It happens after sometimes that processes cannot
be allocated to memory blocks considering their small size and memory
blocks remains unused. This problem is known as Fragmentation.

Fragmentation is of two types −

S.N. Fragmentation & Description

External fragmentation
1 Total memory space is enough to satisfy a request or to reside a process in it, but it is
not contiguous, so it cannot be used.

Internal fragmentation
2 Memory block assigned to process is bigger. Some portion of memory is left unused,
as it cannot be used by another process.

The following diagram shows how fragmentation can cause waste of memory
and a compaction technique can be used to create more free memory out of
fragmented memory −
External fragmentation can be reduced by compaction or shuffle memory
contents to place all free memory together in one large block. To make
compaction feasible, relocation should be dynamic.

Internal Fragmentation is a problem that occurs due to poor memory

allocation and it results in wastage of memory. When a process is loaded
into the system it requests memory which is essential for its working. The
operating system allocates memory to processes to work with but if the
memory happens to be smaller and bigger than the process requirement
the extra space goes unused. This small amount of memory unutilization
is the major Internal Fragmentation appearing in the Operating System.
The internal fragmentation can be reduced by effectively assigning the
smallest partition but large enough for the process.

Paging
A computer can address more memory than the amount physically installed
on the system. This extra memory is actually called virtual memory and it is
a section of a hard that's set up to emulate the computer's RAM. Paging
technique plays an important role in implementing virtual memory.

Paging is a memory management technique in which process address space

is broken into blocks of the same size called pages (size is power of 2,
between 512 bytes and 8192 bytes). The size of the process is measured in
the number of pages.

Similarly, main memory is divided into small fixed-sized blocks of (physical)

memory called frames and the size of a frame is kept the same as that of a
page to have optimum utilization of the main memory and to avoid external
fragmentation.
Address Translation
Page address is called logical address and represented by page number and
the offset.

Logical Address = Page number + page offset

Frame address is called physical address and represented by a frame

number and the offset.

Physical Address = Frame number + page offset

A data structure called page map table is used to keep track of the relation
between a page of a process to a frame in physical memory.
When the system allocates a frame to any page, it translates this logical
address into a physical address and create entry into the page table to be
used throughout execution of the program.

When a process is to be executed, its corresponding pages are loaded into

any available memory frames. Suppose you have a program of 8Kb but your
memory can accommodate only 5Kb at a given point in time, then the paging
concept will come into picture. When a computer runs out of RAM, the
operating system (OS) will move idle or unwanted pages of memory to
secondary memory to free up RAM for other processes and brings them back
when needed by the program.

This process continues during the whole execution of the program where the
OS keeps removing idle pages from the main memory and write them onto
the secondary memory and bring them back when required by the program.

Advantages and Disadvantages of Paging

Here is a list of advantages and disadvantages of paging −

• Paging reduces external fragmentation, but still suffer from internal

fragmentation.
• Paging is simple to implement and assumed as an efficient memory
management technique.
• Due to equal size of the pages and frames, swapping becomes very easy.
• Page table requires extra memory space, so may not be good for a
system having small RAM.
Segmentation
Segmentation is a memory management technique in which each job is
divided into several segments of different sizes, one for each module that
contains pieces that perform related functions. Each segment is actually a
different logical address space of the program.

When a process is to be executed, its corresponding segmentation are loaded

into non-contiguous memory though every segment is loaded into a
contiguous block of available memory.

Segmentation memory management works very similar to paging but here

segments are of variable-length where as in paging pages are of fixed size.

A program segment contains the program's main function, utility functions,

data structures, and so on. The operating system maintains a segment map
table for every process and a list of free memory blocks along with segment
numbers, their size and corresponding memory locations in main memory.
For each segment, the table stores the starting address of the segment and
the length of the segment. A reference to a memory location includes a value
that identifies a segment and an offset.

Print Page
 Operating System - Virtual Memory
Next

A computer can address more memory than the amount physically installed
on the system. This extra memory is actually called virtual memory and it is a
section of a hard disk that's set up to emulate the computer's RAM.

The main visible advantage of this scheme is that programs can be larger
than physical memory. Virtual memory serves two purposes. First, it allows
us to extend the use of physical memory by using disk. Second, it allows us
to have memory protection, because each virtual address is translated to a
physical address.

Following are the situations, when entire program is not required to be

loaded fully in main memory.

• User written error handling routines are used only when an error
occurred in the data or computation.
• Certain options and features of a program may be used rarely.
• Many tables are assigned a fixed amount of address space even though
only a small amount of the table is actually used.
• The ability to execute a program that is only partially in memory would
counter many benefits.
• Less number of I/O would be needed to load or swap each user program
into memory.
• A program would no longer be constrained by the amount of physical
memory that is available.
• Each user program could take less physical memory, more programs
could be run the same time, with a corresponding increase in CPU
utilization and throughput.

Modern microprocessors intended for general-purpose use, a memory

management unit, or MMU, is built into the hardware. The MMU's job is to
translate virtual addresses into physical addresses. A basic example is given
below −
Virtual memory is commonly implemented by demand paging. It can also be
implemented in a segmentation system. Demand segmentation can also be
used to provide virtual memory.

Demand Paging
A demand paging system is quite similar to a paging system with swapping
where processes reside in secondary memory and pages are loaded only on
demand, not in advance. When a context switch occurs, the operating
system does not copy any of the old program’s pages out to the disk or any
of the new program’s pages into the main memory Instead, it just begins
executing the new program after loading the first page and fetches that
program’s pages as they are referenced.
While executing a program, if the program references a page which is not
available in the main memory because it was swapped out a little ago, the
processor treats this invalid memory reference as a page fault and transfers
control from the program to the operating system to demand the page back
into the memory.

Advantages
Following are the advantages of Demand Paging −

• Large virtual memory.

• More efficient use of memory.
• There is no limit on degree of multiprogramming.

Disadvantages
• Number of tables and the amount of processor overhead for handling
page interrupts are greater than in the case of the simple paged
management techniques.
Page Replacement Algorithm
Page replacement algorithms are the techniques using which an Operating
System decides which memory pages to swap out, write to disk when a page
of memory needs to be allocated. Paging happens whenever a page fault
occurs and a free page cannot be used for allocation purpose accounting to
reason that pages are not available or the number of free pages is lower than
required pages.

When the page that was selected for replacement and was paged out, is
referenced again, it has to read in from disk, and this requires for I/O
completion. This process determines the quality of the page replacement
algorithm: the lesser the time waiting for page-ins, the better is the
algorithm.

A page replacement algorithm looks at the limited information about

accessing the pages provided by hardware, and tries to select which pages
should be replaced to minimize the total number of page misses, while
balancing it with the costs of primary storage and processor time of the
algorithm itself. There are many different page replacement algorithms. We
evaluate an algorithm by running it on a particular string of memory
reference and computing the number of page faults,

Reference String
The string of memory references is called reference string. Reference strings
are generated artificially or by tracing a given system and recording the
address of each memory reference. The latter choice produces a large
number of data, where we note two things.

• For a given page size, we need to consider only the page number, not
the entire address.
• If we have a reference to a page p, then any immediately following
references to page p will never cause a page fault. Page p will be in
memory after the first reference; the immediately following references
will not fault.
• For example, consider the following sequence of addresses −
123,215,600,1234,76,96
• If page size is 100, then the reference string is 1,2,6,12,0,0

First In First Out (FIFO) algorithm

• Oldest page in main memory is the one which will be selected for
replacement.
• Easy to implement, keep a list, replace pages from the tail and add new
pages at the head.
Optimal Page algorithm
• An optimal page-replacement algorithm has the lowest page-fault rate
of all algorithms. An optimal page-replacement algorithm exists, and has
been called OPT or MIN.
• Replace the page that will not be used for the longest period of time.
Use the time when a page is to be used.

Least Recently Used (LRU) algorithm

• Page which has not been used for the longest time in main memory is
the one which will be selected for replacement.
• Easy to implement, keep a list, replace pages by looking back into time.
 Operating System - File System

File
A file is a named collection of related information that is recorded on
secondary storage such as magnetic disks, magnetic tapes and optical disks.
In general, a file is a sequence of bits, bytes, lines or records whose meaning
is defined by the files creator and user.

File Structure
A File Structure should be according to a required format that the operating
system can understand.

• A file has a certain defined structure according to its type.

• A text file is a sequence of characters organized into lines.
• A source file is a sequence of procedures and functions.
• An object file is a sequence of bytes organized into blocks that are
understandable by the machine.
• When operating system defines different file structures, it also contains
the code to support these file structure. Unix, MS-DOS support minimum
number of file structure.

File Type
File type refers to the ability of the operating system to distinguish different
types of file such as text files source files and binary files etc. Many operating
systems support many types of files. Operating system like MS-DOS and
UNIX have the following types of files −

Ordinary files
• These are the files that contain user information.
• These may have text, databases or executable program.
• The user can apply various operations on such files like add, modify,
delete or even remove the entire file.

Directory files
• These files contain list of file names and other information related to
these files.

Special files
• These files are also known as device files.
• These files represent physical device like disks, terminals, printers,
networks, tape drive etc.

These files are of two types −

• Character special files − data is handled character by character as in case

of terminals or printers.
• Block special files − data is handled in blocks as in the case of disks and
tapes.

File Access Mechanisms

File access mechanism refers to the manner in which the records of a file
may be accessed. There are several ways to access files −

• Sequential access
• Direct/Random access
• Indexed sequential access

Sequential access
A sequential access is that in which the records are accessed in some
sequence, i.e., the information in the file is processed in order, one record
after the other. This access method is the most primitive one. Example:
Compilers usually access files in this fashion.

Direct/Random access
 • Random access file organization provides, accessing the records directly.
• Each record has its own address on the file with by the help of which it
can be directly accessed for reading or writing.
• The records need not be in any sequence within the file and they need
not be in adjacent locations on the storage medium.

Indexed sequential access

• This mechanism is built up on base of sequential access.
• An index is created for each file which contains pointers to various
blocks.
• Index is searched sequentially and its pointer is used to access the file
directly.

Space Allocation
Files are allocated disk spaces by operating system. Operating systems
deploy following three main ways to allocate disk space to files.

• Contiguous Allocation
• Linked Allocation
• Indexed Allocation

Contiguous Allocation
• Each file occupies a contiguous address space on disk.
• Assigned disk address is in linear order.
• Easy to implement.
• External fragmentation is a major issue with this type of allocation
technique.

Linked Allocation
• Each file carries a list of links to disk blocks.
• Directory contains link / pointer to first block of a file.
• No external fragmentation
• Effectively used in sequential access file.
• Inefficient in case of direct access file.

Indexed Allocation
• Provides solutions to problems of contiguous and linked allocation.
• A index block is created having all pointers to files.
• Each file has its own index block which stores the addresses of disk space
occupied by the file.
• Directory contains the addresses of index blocks of files.
Secondary Input and Output
One of the important jobs of an Operating System is to manage various I/O devices including
mouse, keyboards, touch pad, disk drives, display adapters, USB devices, Bit-mapped screen,
LED, Analog-to-digital converter, On/off switch, network connections, audio I/O, printers etc.

An I/O system is required to take an application I/O request and send it to the physical device,
then take whatever response comes back from the device and send it to the application.

I/O devices can be divided into two categories −

Block devices − A block device is one with which the driver communicates by sending entire
blocks of data. For example, Hard disks, USB cameras, Disk-On-Key etc.

Character devices − A character device is one with which the driver communicates by sending
and receiving single characters (bytes, octets). For example, serial ports, parallel ports, sounds
cards etc.

Device Controllers
Device drivers are software modules that can be plugged into an OS to handle
a particular device. Operating System takes help from device drivers to handle
all I/O devices.
The Device Controller works like an interface between a device and a device
driver. I/O units (Keyboard, mouse, printer, etc.) typically consist of a
mechanical component and an electronic component where electronic
component is called the device controller.
There is always a device controller and a device driver for each device to
communicate with the Operating Systems. A device controller may be able to
handle multiple devices. As an interface its main task is to convert serial bit
stream to block of bytes, perform error correction as necessary.
Any device connected to the computer is connected by a plug and socket, and
the socket is connected to a device controller. Following is a model for
connecting the CPU, memory, controllers, and I/O devices where CPU and
device controllers all use a common bus for communication.
Disk structure
• Modern magnetic disk drives are addressed as large one-dimensional
arrays of logical blocks, where the logical block is the smallest unit of
transfer.
• The size of a logical block is usually 512 bytes, although some disks can
be low-level formatted to have a different logical block size, such as
1,024 bytes.
• The one-dimensional array of logical blocks is mapped onto the sectors
of the disk sequentially.
• Sector 0 is the first sector of the first track on the outermost cylinder.
• The mapping proceeds in order through that track, then through the rest
of the tracks in that cylinder, and then through the rest of the cylinders
from outermost to innermost.
• The number of sectors per track has been increasing as disk technology
improves, and the outer zone of a disk usually has several hundred
sectors per track. Similarly, the number of cylinders per disk has been
increasing; large disks have tens of thousands of cylinders.

Disk Scheduling Algorithms

Disk scheduling is a technique operating systems use to manage the order in which disk I/O
(input/output) requests are processed. Disk scheduling is also known as I/O Scheduling. The
main goals of disk scheduling are to optimize the performance of disk operations, reduce the
time it takes to access data and improve overall system efficiency.

In this article, we will explore the different types of disk scheduling algorithms and their
functions. By understanding and implementing these algorithms, we can optimize system
performance and ensure faster data retrieval.

What are Disk Scheduling Algorithms?

Disk scheduling algorithms are crucial in managing how data is read from and written to a
computer’s hard disk. These algorithms help determine the order in which disk read and write
requests are processed, significantly impacting the speed and efficiency of data access.
Common disk scheduling methods include First-Come, First-Served (FCFS), Shortest Seek
Time First (SSTF), SCAN, C-SCAN, LOOK, and C-LOOK. By understanding and
implementing these algorithms, we can optimize system performance and ensure faster data
retrieval.

Importance of Disk Scheduling in Operating System

• Multiple I/O requests may arrive by different processes and only one I/O request can
be served at a time by the disk controller. Thus other I/O requests need to wait in the
waiting queue and need to be scheduled.
 • Two or more requests may be far from each other so this can result in greater disk arm
movement.

• Hard drives are one of the slowest parts of the computer system and thus need to be
accessed in an efficient manner.

Key Terms Associated with Disk Scheduling

• Seek Time: Seek time is the time taken to locate the disk arm to a specified track
where the data is to be read or written. So the disk scheduling algorithm that gives a
minimum average seek time is better.

• Rotational Latency: Rotational Latency is the time taken by the desired sector of the
disk to rotate into a position so that it can access the read/write heads. So the disk
scheduling algorithm that gives minimum rotational latency is better.

• Transfer Time: Transfer time is the time to transfer the data. It depends on the
rotating speed of the disk and the number of bytes to be transferred.

• Disk Access Time:

Disk Access Time = Seek Time + Rotational Latency + Transfer Time

Total Seek Time = Total head Movement * Seek Time

Disk Access Time and Disk Response Time

• Disk Response Time: Response Time is the average time spent by a request waiting
to perform its I/O operation. The average Response time is the response time of all
requests. Variance Response Time is the measure of how individual requests are
serviced with respect to average response time. So the disk scheduling algorithm that
gives minimum variance response time is better.

Goal of Disk Scheduling Algorithms

• Minimize Seek Time

• Maximize Throughput

• Minimize Latency
 • Fairness

• Efficiency in Resource Utilization

1. FCFS (First Come First Serve)

FCFS is the simplest of all Disk Scheduling Algorithms. In FCFS, the requests are addressed
in the order they arrive in the disk queue. Let us understand this with the help of an example.

First Come First Serve

Example:

Suppose the order of request is- (82,170,43,140,24,16,190)

And current position of Read/Write head is: 50

So, total overhead movement (total distance covered by the disk arm) =
(82-50)+(170-82)+(170-43)+(140-43)+(140-24)+(24-16)+(190-16) =642

Advantages of FCFS

Here are some of the advantages of First Come First Serve.

• Every request gets a fair chance

• No indefinite postponement
Disadvantages of FCFS

Here are some of the disadvantages of First Come First Serve.

• Does not try to optimize seek time

• May not provide the best possible service

2. SSTF (Shortest Seek Time First)

In SSTF (Shortest Seek Time First), requests having the shortest seek time are executed first.
So, the seek time of every request is calculated in advance in the queue and then they are
scheduled according to their calculated seek time. As a result, the request near the disk arm
will get executed first. SSTF is certainly an improvement over FCFS as it decreases the average
response time and increases the throughput of the system. Let us understand this with the help
of an example.

Example:

Shortest Seek Time First

Suppose the order of request is- (82,170,43,140,24,16,190)

And current position of Read/Write head is: 50

So,

total overhead movement (total distance covered by the disk arm) =

(50-43)+(43-24)+(24-16)+(82-16)+(140-82)+(170-140)+(190-170) =208

Advantages of Shortest Seek Time First

Here are some of the advantages of Shortest Seek Time First.

• The average Response Time decreases

 • Throughput increases

Disadvantages of Shortest Seek Time First

Here are some of the disadvantages of Shortest Seek Time First.

• Overhead to calculate seek time in advance

• Can cause Starvation for a request if it has a higher seek time as compared to
incoming requests

• The high variance of response time as SSTF favors only some requests

3. SCAN

In the SCAN algorithm the disk arm moves in a particular direction and services the requests
coming in its path and after reaching the end of the disk, it reverses its direction and again
services the request arriving in its path. So, this algorithm works as an elevator and is hence
also known as an elevator algorithm. As a result, the requests at the midrange are serviced
more and those arriving behind the disk arm will have to wait.

Example:

SCAN Algorithm

Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is

at 50, and it is also given that the disk arm should move “towards the larger value”.

Therefore, the total overhead movement (total distance covered by the disk arm) is calculated
as

= (199-50) + (199-16) = 332

Advantages of SCAN Algorithm

Here are some of the advantages of the SCAN Algorithm.

• High throughput

• Low variance of response time

• Average response time

Disadvantages of SCAN Algorithm

Here are some of the disadvantages of the SCAN Algorithm.

• Long waiting time for requests for locations just visited by disk arm

4. C-SCAN

In the SCAN algorithm, the disk arm again scans the path that has been scanned, after reversing
its direction. So, it may be possible that too many requests are waiting at the other end or there
may be zero or few requests pending at the scanned area.

These situations are avoided in the CSCAN algorithm in which the disk arm instead of reversing
its direction goes to the other end of the disk and starts servicing the requests from there. So,
the disk arm moves in a circular fashion and this algorithm is also similar to the SCAN
algorithm hence it is known as C-SCAN (Circular SCAN).

Example:

Circular SCAN
Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is
at 50, and it is also given that the disk arm should move “towards the larger value”.

So, the total overhead movement (total distance covered by the disk arm) is calculated as:

=(199-50) + (199-0) + (43-0) = 391

Advantages of C-SCAN Algorithm

Here are some of the advantages of C-SCAN.

• Provides more uniform wait time compared to SCAN.

5. LOOK

LOOK Algorithm is similar to the SCAN disk scheduling algorithm except for the difference
that the disk arm in spite of going to the end of the disk goes only to the last request to be
serviced in front of the head and then reverses its direction from there only. Thus it prevents
the extra delay which occurred due to unnecessary traversal to the end of the disk.

Example:

LOOK Algorithm

Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is

at 50, and it is also given that the disk arm should move “towards the larger value”.

So, the total overhead movement (total distance covered by the disk arm) is calculated as:

= (190-50) + (190-16) = 314

6. C-LOOK

As LOOK is similar to the SCAN algorithm, in a similar way, C-LOOK is similar to the
CSCAN disk scheduling algorithm. In CLOOK, the disk arm in spite of going to the end goes
only to the last request to be serviced in front of the head and then from there goes to the other
end’s last request. Thus, it also prevents the extra delay which occurred due to unnecessary
traversal to the end of the disk.

Example:

1. Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the

Read/Write arm is at 50, and it is also given that the disk arm should move “towards
the larger value”

C-LOOK

So, the total overhead movement (total distance covered by the disk arm) is calculated as

= (190-50) + (190-16) + (43-16) = 341

7. RSS (Random Scheduling)

It stands for Random Scheduling and just like its name it is natural. It is used in situations
where scheduling involves random attributes such as random processing time, random due
dates, random weights, and stochastic machine breakdowns this algorithm sits perfectly.
Which is why it is usually used for analysis and simulation.

8. LIFO (Last-In First-Out)

In LIFO (Last In, First Out) algorithm, the newest jobs are serviced before the existing ones
i.e. in order of requests that get serviced the job that is newest or last entered is serviced first,
and then the rest in the same order.

Advantages of LIFO (Last-In First-Out)

Here are some of the advantages of the Last In First Out Algorithm.

• Maximizes locality and resource utilization

• Can seem a little unfair to other requests and if new requests keep coming in, it cause
starvation to the old and existing ones.

9. N-STEP SCAN

It is also known as the N-STEP LOOK algorithm. In this, a buffer is created for N requests.
All requests belonging to a buffer will be serviced in one go. Also once the buffer is full no
new requests are kept in this buffer and are sent to another one. Now, when these N requests
are serviced, the time comes for another top N request and this way all get requests to get a
guaranteed service

Advantages of N-STEP SCAN

Here are some of the advantages of the N-Step Algorithm.

• It eliminates the starvation of requests completely

10. F-SCAN

This algorithm uses two sub-queues. During the scan, all requests in the first queue are
serviced and the new incoming requests are added to the second queue. All new requests are
kept on halt until the existing requests in the first queue are serviced.

Advantages of F-SCAN

Here are some of the advantages of the F-SCAN Algorithm.

• F-SCAN along with N-Step-SCAN prevents “arm stickiness” (phenomena in I/O

scheduling where the scheduling algorithm continues to service requests at or near the
current sector and thus prevents any seeking)

Each algorithm is unique in its own way. Overall Performance depends on the number and
type of requests.

Client Server Communication in Operating System

Last Updated : 27 Dec, 2023

•
 •

In an Operating System, Client Server Communication refers to the exchange of data and Services
among multiple machines or processes. In Client client-server communication System one process or
machine acts as a client requesting a service or data, and Another machine or process acts like a
server for providing those Services or Data to the client machine. This Communication model is
widely used for exchanging data among various computing environments like Distributed Systems,
Internet Applications, and Networking Application communication. The communication between
Server and Client takes place with different Protocols and mechanisms.

Different Ways of Client-Server Communication

In Client Server Communication we can use different ways.

1. Sockets Mechanism

2. Remote Procedure Call

3. Message Passing

4. Inter-process Communication

5. Distributed File Systems

Sockets Mechanism

The Sockets are the End Points of Communication between two machines. They provide a way for
processes to communicate with each other, either on the same on machine or over through Internet
also possible. The Sockets enable the communication connection between Serthe er and the client to
transfer data in a bidirectional way.

Client Server Communication using Sockets

Remote Procedure Call (PRC)

Remote Procedure Call is a Protocol. A Protocol is set of Instructions. It allows a client to execute a
procedure call on remote server, as if it is local procedure call. PRC is commonly used in Client Server
communication Architecture. PRC Provide high level of abstraction to the programmer. In This The
client Program issues a procedure call , which is translated into message that is sent over the
network to the Server, The Server execute the call and send back to the Client Machine.

Remote Procedure Call Process

Message Passing

Message Passing is a communication Method. Where the machines communicated with each one by
send and receiving the messages. This approach is commonly used in Parallel and Distributed
Systems, This approach enables data exchange among the System.

Message Passing Process

Inter process Communication

The Inter Process Communication also called IPC. It allows communication between processes within
the same Machine. The IPC can enable data sharing and Synchronous between different processes
running concurrently on an operating system. And it includes Sharing Memory, message queues,
semaphores and pipes among others.

Inter process Communication Process

Distributed File Systems

Distributed File Systems provide access to files from multiple machines in network. Client can access
and manipulate files stored on Remote Server, Through Standard Interface Example Network File
System and Server Message Block.

Distributed File Systems Process

What is peer-to-peer model?

When we talk about networks, the first thing that comes to mind is how data transfers from one
device to another. Sharing digital information and resources is a vital part of information technology.
A peer-to-peer (P2P) network connecting devices may improve connectivity and access to shared
assets, allowing your organization to run more efficiently.

When devices are linked together, they share resources without requiring separate server or server
software. To understand the peer-to-peer model, let’s take the example of a torrent. As we already
know, torrent software is used for downloading movies and files. How is this peer-to-peer model
working in this torrent file? Suppose your organization has four personal computers, PC1, PC2, PC3,
and PC4. In PC1, when we use torrent, PC1 checks all devices on the internet running that particular
software that has torrent. As soon as PC1 finds any other PC that is running torrent software, it will
ask for the file it wants to download. Suppose PC2 is running that software and it is nearest to PC1,
so this PC1 asks PC2 to give him that file, and PC1 will download that file. But what if PC2 does not
have that file? Then the data or the query will be forwarded to the next device, PC3. If PC3 has that
file, it will revert to PC1 and give him that file access. This entire process is known as a peer-to-peer
model in networks.

Types of Peer-to-Peer Model

• Unstructured peer-to-peer model

 • Structured peer-to-peer model

• Hybrid peer-to-peer model

1. Unstructured peer-to-peer model : As the name suggests, devices are connected randomly in
networks in this type of model. This model is easy to build since there is no structure imposed.
However, because it is unstructured, it is hard to discover information.

2. Structured peer-to-peer model: In this model, devices are connected in a specific topology.
Distributed hash tables are commonly used to construct structured networks. The software used to
build a structured peer-to-peer model integrates the network’s virtual layer into a predefined
structure.

3. Hybrid peer-to-peer model: This model is the combination of the peer-to-peer model and the
client-server model. There are numerous types of hybrid networks, and a popular hybrid network
uses a central server to help users locate each other.

Advantages of Peer-to-Peer Model

Due to its architecture, a peer-to-peer model offers many advantages to its user, including:

1. Easy to maintain: A peer-to-peer model has no server in between their devices. So maintaining
this type of network is very useful and easy to handle.

2. Cost-effective: This model doesn’t require a particular server for a specific device, which reduces
its cost. It does not demand the use of a network operating system or the services of a full-time
System Administrator.

3. Easy file sharing: A strong peer-to-peer model can instantly distribute files over long distances. You
can access your files from anywhere.

4. Adaptability: The peer-to-peer model can simply expand to add new customers. Because of this
advantage, these networks are more adaptable than the client-server model, and its scalability is one
of its most appealing features.

5. Efficiency: Developing a peer-to-peer model enables collaboration amongst devices with different
resources that can benefit the entire system.

Application of Peer-to-Peer Model

1. File sharing: The activity of offering files and allowing others to obtain them over the internet is
known as file sharing. File sharing is based on the peer-to-peer network concept, in which clients’
personal computers are considered peers in the network.
2. Bioinformatics: Peer-to-peer networks have also begun to capture the interest of scientists and
researchers, particularly those working with extensive data, such as bioinformatics. Peer-to-peer
networks can execute huge systems that deal with extensive data.
3. Artificial intelligence: Swarm intelligence (SI) is an artificial intelligence method focused on
observing collective actions in fragmented, self-organized systems. A peer-to-peer network can be
used to develop swarm intelligence, with each peer referring to a single person.
4. Grid computing: Grid computing is a growing computer model that allows for high bandwidth
processing. Grids utilize the resources of several different computers (peers) connected by a network
to solve large-scale calculation problems, usually over the Internet.