Unit 3

Memory Management and protection

"Memory Management" refers to the function that controls how the

computer's primary memory is allocated and used by different
processes, tracking which memory locations are free or assigned to a
program, while "memory protection" is a security mechanism that
prevents unauthorized access to memory locations, ensuring each
program can only access its designated memory space and not
interfere with others.
What is Memory Management?
Memory management mostly involves management of main memory.
In a multiprogramming computer, the Operating System resides in a
part of the main memory, and the rest is used by multiple processes.
The task of subdividing the memory among different processes is
called Memory Management. Memory management is a method in
the operating system to manage operations between main memory and
disk during process execution. The main aim of memory management
is to achieve efficient utilization of memory.
Why is Memory Management Required?
● Allocate and de-allocate memory before and after process
execution.
● To keep track of used memory space by processes.
● To minimize fragmentation issues.
● To proper utilization of main memory.
● To maintain data integrity while executing of process.
Logical and Physical Address Space
● Logical Address Space: An address generated by the CPU is
known as a “Logical Address”. It is also known as a Virtual
address. Logical address space can be defined as the size of the
process. A logical address can be changed.
 The process accesses memory using logical addresses, which are
translated by the operating system into physical addresses. An
address that is created by the CPU while a program is running is
known as a logical address. Because the logical address is
virtual—that is, it doesn’t exist physically—it is also referred to
as such. The CPU uses this address as a reference to go to the
actual memory location. All logical addresses created from a
program’s perspective are referred to as being in the “logical
address space”.

● Physical Address Space: An address seen by the memory unit

(i.e. the one loaded into the memory address register of the
memory) is commonly known as a “Physical Address”. A
Physical address is also known as a Real address. The set of all
physical addresses corresponding to these logical addresses is
known as Physical address space. A physical address is
computed by MMU. The run-time mapping from virtual to
physical addresses is done by a hardware device Memory
Management Unit(MMU). The physical address always remains
constant.
What is Swapping in the Operating System?
Swapping in an operating system is a process that moves data or
programs between the computer’s main memory (RAM) and a
secondary storage (usually a hard disk or SSD). This helps manage
the limited space in RAM and allows the system to run more
programs than it could otherwise handle simultaneously.
It’s important to remember that swapping is only used when data isn’t
available in RAM. Although the swapping process degrades system
performance, it allows larger and multiple processes to run
concurrently. Because of this, swapping is also known as memory
compaction.
The CPU scheduler determines which processes are swapped in and
which are swapped out. Consider a multiprogramming environment
that employs a priority-based scheduling algorithm. When a high-
priority process enters the input queue, a low-priority process is
swapped out so the high-priority process can be loaded and executed.
When this process terminates, the low-priority process is swapped
back into memory to continue its execution. The below figure shows
the swapping process in the operating system:

Swapping has been subdivided into two concepts: swap-in and swap-
out.
● Swap-out is a technique for moving a process from RAM to the
hard disc.
● Swap-in is a method of transferring a program from a hard disc
to main memory, or RAM.
Process of Swapping
 ● When the RAM is full and a new program needs to run, the
operating system selects a program or data that is currently in
RAM but not actively being used.
● The selected data is moved to secondary storage, freeing up
space in RAM for the new program
● When the swapped-out program is needed again, it can be
swapped back into RAM, replacing another inactive program or
data if necessary.
Real Life Example of Swapping
Imagine you have a disk (RAM) that is too small to hold all your
books and papers (programs). You keep the most important items on
the desk and store the rest in a cabinet (secondary storage). When you
need something from the cabinet, you swap it with something on your
desk. This way, you can work with more items than your desk alone
could hold.

Contiguous memory allocation is a method used in operating systems

for managing memory where each process is allocated a single
contiguous block of memory. In this scheme, the operating system
assigns a contiguous block of memory to each process, meaning that
all the memory for a given process is located next to each other,
forming a continuous chunk.
Key Features of Contiguous Memory Allocation:

1. Simple and Fast: It is a simple memory management technique

because it does not require complex algorithms for memory
allocation and deallocation. It’s easy to implement, and
accessing the memory is quick because all addresses are
continuous.
2. Fixed or Variable Size: The allocated memory can either be
fixed in size or variable. In a fixed-size allocation, each process
gets a predetermined amount of memory, while in a variable
size allocation, memory is allocated based on the process’s
needs.
3. Fragmentation:
 ○ External Fragmentation: Over time, as processes are
loaded and removed, the system may experience external
fragmentation, meaning that the memory becomes
fragmented into small, unusable blocks. This happens
because processes come and go, leaving gaps between the
allocated memory blocks.
○ Internal Fragmentation: If the allocated memory block is
larger than the process needs, unused memory within the
block is wasted (this is internal fragmentation).
4. Limited Flexibility: The main limitation is that if a process
requires more memory than the initially allocated block, it
cannot easily expand without relocating the process. Also, it
might be difficult to find a large enough contiguous block of
free memory, especially in systems with high fragmentation.
Example:

Imagine a system with 100 MB of available RAM. A process requires

20 MB of memory. In contiguous memory allocation, the operating
system will allocate one continuous block of 20 MB for the process. If
another process needs memory, the operating system will search for
another free contiguous block of appropriate size. If free space is
fragmented into smaller blocks, a new process might not get the
required memory.

Memory allocation
Memory allocation in an operating system refers to the process of
assigning memory spaces to programs or processes during their
execution. The operating system must efficiently allocate and manage
memory to ensure that processes get the memory they need without
wasting resources or interfering with each other.
Types of Memory Allocation:

There are several ways to allocate memory in an operating system,

and they typically fall under two main categories:
 1. Static Memory Allocation:
○ Fixed at compile-time: In static memory allocation, the
memory required for a program is determined at compile
time, and it is fixed during program execution.
○ No runtime changes: The size of the memory required by
the program cannot be altered during execution, which can
result in wasted memory (if more memory is allocated than
needed) or memory shortages (if not enough memory is
allocated).
○ Example: Global variables and static arrays in C/C++
programs.
2. Dynamic Memory Allocation:
○ Allocated at runtime: Dynamic memory allocation occurs
at runtime, meaning the operating system allocates
memory for a process as needed. It allows processes to
request and release memory during their execution.
○ Flexible: This method provides flexibility because
memory is allocated only when required, reducing waste,
and the size of memory can be adjusted as needed.
○ Example: Functions like malloc() or free() in C/C+
+ allow a program to allocate and release memory during
execution.

Memory fragmentation
Memory fragmentation in an operating system refers to the
phenomenon where free memory is split into small, non-contiguous
blocks over time, which can lead to inefficient memory utilization.
Fragmentation occurs when memory is allocated and deallocated
dynamically, leaving gaps of unused memory that are not large
enough to satisfy new memory allocation requests.
There are two main types of fragmentation:
1. External Fragmentation:

External fragmentation happens when free memory is divided into

small, scattered blocks outside of any process's allocated space. Even
though there might be enough total free memory, it is not contiguous,
and therefore, a process may not be able to get the required memory
in one continuous block.
Example:

● Suppose a system has 100 MB of free memory but is

fragmented into blocks of 20 MB, 5 MB, and 30 MB. If a
process needs 25 MB of memory, there is enough total free
memory (55 MB), but there isn't a single contiguous 25 MB
block available. This is external fragmentation.
2. Internal Fragmentation:

Internal fragmentation occurs when memory is allocated in fixed-size

blocks, and a process uses less memory than the allocated block. The
leftover unused memory within the allocated block is wasted because
it cannot be used by other processes.
Example:

● If a process is allocated a 10 MB block but only needs 8 MB,

there will be 2 MB of unused memory in the allocated block.
This wasted space is called internal fragmentation.
Causes of Fragmentation:

● Dynamic Allocation: Memory fragmentation is primarily

caused by dynamic memory allocation and deallocation, as
processes are created, terminated, or resized.
● Fixed-Size Allocation: Systems that allocate memory in fixed
sizes are prone to internal fragmentation because processes
might not need the entire block.
● Process Creation/Termination: As processes come and go,
they leave behind gaps (external fragmentation), which may not
be usable for new processes.
Impact of Fragmentation:

● Memory Wastage: Fragmentation can lead to inefficient use of

memory, as free space may be scattered across the system and
may not be usable by processes.
 ● Performance Degradation: In the case of external
fragmentation, processes may not find large enough blocks of
free memory, leading to delays in memory allocation or the need
for memory compaction, which can slow down system
performance.
● Increased Overhead: The operating system may need to
perform additional tasks, such as memory compaction or
swapping, to manage fragmented memory, adding overhead.
Solutions to Fragmentation:

1. Compaction: The operating system can periodically rearrange

the memory to eliminate gaps and create larger contiguous
blocks of free memory. This process is called compaction, but it
can be costly in terms of time and resources.
2. Paging: A technique that breaks the physical memory into
fixed-size blocks called pages. This helps reduce fragmentation
because processes are allocated memory in small, fixed-size
pages, minimizing internal fragmentation. It also allows for non-
contiguous memory allocation, helping to alleviate external
fragmentation.
3. Segmentation: In segmentation, memory is divided into
variable-sized segments based on logical divisions like code,
data, and stack. This reduces fragmentation by better matching
the size of memory blocks to the process's needs.

Non-Contiguous Allocation

Non-Contiguous Allocation in Operating System

Non-contiguous allocation, also known as dynamic or linked allocation, is a
memory allocation technique used in operating systems to allocate memory to
processes that do not require a contiguous block of memory. In this technique,
each process is allocated a series of non-contiguous blocks of memory that can
be located anywhere in the physical memory.
Non-contiguous allocation involves the use of pointers to link the non-
contiguous memory blocks allocated to a process. These pointers are used by
the operating system to keep track of the memory blocks allocated to the
process and to locate them during the execution of the process.
Fundamental Approaches of Implementing Non-Contiguous Memory
Allocation
There are two fundamental approaches to implementing non-contiguous
memory allocation. Paging and Segmentation are the two ways that allow a
process’s physical address space to be non-contiguous. It has the advantage of
reducing memory wastage but it increases the overheads due to address
translation. It slows the execution of the memory because time is consumed in
address translation.
● Paging
● Segmentation
Paging in Operating System
In Operating Systems, Paging is a storage mechanism used to retrieve processes
from the secondary storage into the main memory in the form of pages.
The main idea behind the paging is to divide each process in the form of pages.
The main memory will also be divided in the form of frames.
One page of the process is to be stored in one of the frames of the memory. The
pages can be stored at the different locations of the memory but the priority is
always to find the contiguous frames or holes.
Pages of the process are brought into the main memory only when they are
required otherwise they reside in the secondary storage.
Different operating system defines different frame sizes. The sizes of each
frame must be equal. Considering the fact that the pages are mapped to the
frames in Paging, page size needs to be as same as frame size.
Example
Let us consider the main memory size 16 Kb and Frame size is 1 KB therefore
the main memory will be divided into the collection of 16 frames of 1 KB each.
There are 4 processes in the system that is P1, P2, P3 and P4 of 4 KB each.
Each process is divided into pages of 1 KB each so that one page can be stored
in one frame.
Initially, all the frames are empty therefore pages of the processes will get
stored in the contiguous way.
Frames, pages and the mapping between the two is shown in the image below.
 Page Replacement
● Segmentation
The process is divided into Segments. The chunks that a program
is divided into which are not necessarily all of the exact sizes are
called segments. Segmentation gives the user’s view of the
process which paging does not provide. Here the user’s view is
mapped to physical memory.
Types of Segmentation in Operating Systems
● Virtual Memory Segmentation: Each process is divided into
a number of segments, but the segmentation is not done all
at once. This segmentation may or may not take place at the
run time of the program.
 ● Simple Segmentation: Each process is divided into a number
of segments, all of which are loaded into memory at run
time, though not necessarily contiguously.

What is Segment Table?

It maps a two-dimensional Logical address into a one-
dimensional Physical address. It’s each table entry has:
● Base Address: It contains the starting physical address
where the segments reside in memory.
● Segment Limit: Also known as segment offset. It specifies
the length of the segment.

Translation
The address generated by the CPU is divided into:
 ● Segment number (s): Number of bits required to represent
the segment.
● Segment offset (d): Number of bits required to represent the
position of data within a segment.
Advantages of Segmentation in Operating System
● Reduced Internal Fragmentation : Segmentation can reduce
internal fragmentation compared to fixed-size paging, as
segments can be sized according to the actual needs of a
process. However, internal fragmentation can still occur if a
segment is allocated more space than it is actually used.
● Segment Table consumes less space in comparison to Page
table in paging.
● As a complete module is loaded all at once, segmentation
improves CPU utilization.
● The user’s perception of physical memory is quite similar to
segmentation. Users can divide user programs into modules
via segmentation. These modules are nothing more than
separate processes’ codes.
● The user specifies the segment size, whereas, in paging, the
hardware determines the page size.
● Segmentation is a method that can be used to segregate data
from security operations.
● Flexibility: Segmentation provides a higher degree of
flexibility than paging. Segments can be of variable size, and
processes can be designed to have multiple segments,
allowing for more fine-grained memory allocation.
● Sharing: Segmentation allows for sharing of memory
segments between processes. This can be useful for inter-
process communication or for sharing code libraries.
● Protection: Segmentation provides a level of protection
between segments, preventing one process from accessing or
modifying another process’s memory segment. This can
help increase the security and stability of the system.
Disadvantages of Segmentation in Operating System
● External Fragmentation : As processes are loaded and
removed from memory, the free memory space is broken
into little pieces, causing external fragmentation. This is a
notable difference from paging, where external
fragmentation is significantly lesser.
● Overhead is associated with keeping a segment table for
each activity.
● Due to the need for two memory accesses, one for the
segment table and the other for main memory, access time to
retrieve the instruction increases.
● Fragmentation: As mentioned, segmentation can lead to
external fragmentation as memory becomes divided into
smaller segments. This can lead to wasted memory and
decreased performance.
● Overhead: Using a segment table can increase overhead and
reduce performance. Each segment table entry requires
additional memory, and accessing the table to retrieve
memory locations can increase the time needed for memory
operations.
● Complexity: Segmentation can be more complex to
implement and manage than paging. In particular, managing
multiple segments per process can be challenging, and the
potential for segmentation faults can increase as a result.

Thrashing
Thrashing is a condition or a situation when the system is
spending a major portion of its time servicing the page faults,
but the actual processing done is very negligible.
Causes of thrashing:
1. High degree of multiprogramming.
2. Lack of frames.
 3. Page replacement policy.
Thrashing’s Causes
Thrashing has an impact on the operating system’s execution
performance. Thrashing also causes serious performance issues
with the operating system. When the CPU’s usage is low, the
process scheduling mechanism tries to load multiple processes
into memory at the same time, increasing the degree of Multi
programming.
In this case, the number of processes in the memory exceeds the
number of frames available in the memory. Each process is given
a set number of frames to work with.
Thrashing occurs when a system spends more time swapping
pages in and out of memory than executing processes, leading to a
significant drop in performance. Learning techniques to handle
thrashing is crucial for optimizing system performance.
If a high-priority process arrives in memory and the frame is not
vacant at the moment, the other process occupying the frame will
be moved to secondary storage, and the free frame will be allotted
to a higher-priority process.
We may also argue that as soon as the memory is full, the
procedure begins to take a long time to swap in the required
pages. Because most of the processes are waiting for pages, the
CPU utilization drops again.
As a result, a high level of multiprogramming and a lack of
frames are two of the most common reasons for thrashing in the
operating system.
The basic concept involved is that if a process is allocated to few
frames, then there will be too many and too frequent page faults.
As a result, no useful work would be done by the CPU and the
CPU utilization would fall drastically. The long-term scheduler
would then try to improve the CPU utilization by loading some
more processes into the memory thereby increasing the degree of
multi programming. This would result in a further decrease in the
CPU utilization triggering a chained reaction of higher page faults
followed by an increase in the degree of multi programming,
called Thrashing.
What is Kernel Memory Allocation?
In operating system design, the kernel memory allocation is a
critical aspect which involves the allocation of memory for kernel
level operations and data structures. When a process is executing
in user mode and it requests the additional memory, then the
kernel maintains the allocation of pages from the list of free page
frames.

Hence, the kernel memory allocation can be defined as under

"The process by which the kernel of the operating system
allocates memory for its internal operations and data structures is
called kernel memory allocation."
w hat is Buddy Memory Allocation System?
The parts of equal size of a block are called buddies. In context of
the operating system, the buddy system is an algorithm used for
memory allocation. In buddy system, the available memory
space is divided into blocks of a fixed and equal size. These
blocks are then organized in the form of a binary tree structure. In
this binary tree structure, each block has a buddy block whose
size is same as that of the adjacent block.

The buddy system is one of the efficient memory allocation

technique because it avoids the fragmentation of memory space.
Buddy system ensures that all the allocated blocks have the same
size so that they can be easily merged together with their buddy
blocks. Another major advantage of buddy system is that it allows
for quick allocation and deallocation of memory blocks that is an
important requirement in real time systems to give enhanced
performance.
In buddy system, whenever a request is made for memory
allocation, the memory allocator finds a bock of appropriate
memory size. If it found a block of a larger size than required, it is
repetitively divided into smaller blocks until a block of the
desired size is obtained. Once the block of the desired size is
found, the allocator marks it as allocated and sends a pointer to
the requesting process.
Also, if a memory block is freed from a process, then the allocator
searches for its buddy block and checks whether it is also free or
not. If the buddy block is also free, then the two blocks are
merged together to form a larger block. This larger block is then
marked as free and added back to binary tree structure. The
process of merging of free blocks is repeated until no more
merges are possible.

Storage Management
File Systems
A computer file is defined as a medium used for saving and managing data in the computer
system. The data stored in the computer system is completely in digital format, although there
can be various types of files that help us to store the data.
File systems are a crucial part of any operating system, providing a structured way to store,
organize, and manage data on storage devices such as hard drives, SSDs, and USB drives.
Essentially, a file system acts as a bridge between the operating system and the physical
storage hardware, allowing users and applications to create, read, update, and delete files in an
organized and efficient manner.

What is a File System?

A file system is a method an operating system uses to store, organize, and manage files and
directories on a storage device. Some common types of file systems include:

● FAT (File Allocation Table): An older file system used by older versions of Windows and
other operating systems.

4. NTFS (New Technology File System): A modern file system used by Windows. It
supports features such as file and folder permissions, compression, and encryption.

3. ext (Extended File System): A file system commonly used on Linux and Unix-based
operating systems.

● HFS (Hierarchical File System): A file system used by macOS.

● APFS (Apple File System): A new file system introduced by Apple for their Macs and
iOS devices.
A file is a collection of related information that is recorded on secondary storage. Or file is a
collection of logically related entities. From the user’s perspective, a file is the smallest
allotment of logical secondary storage.
The name of the file is divided into two parts as shown below:

● Name

● Extension, separated by a period.

What are File Access Methods in OS?

A file is a collection of bits/bytes or lines that is stored on secondary storage devices like a hard
drive (magnetic disks).

File access methods in OS are nothing but techniques to read data from the system's memory.
There are various ways in which we can access the files from the memory like:
 ● Sequential Access
● Direct/Relative Access, and
● Indexed Sequential Access.
These methods by which the records in a file can be accessed are referred to as the file access
mechanism. Each file access mechanism has its own set of benefits and drawbacks, which are
discussed further in this article.

Types of File Access Methods in the Operating System

1. Sequential Access
The operating system reads the file word by word in a sequential access method of file
accessing. A pointer is made, which first links to the file's base address. If the user wishes to
read the first word of the file, the pointer gives it to them and raises its value to the next word.
This procedure continues till the file is finished. It is the most basic way of file access. The data
in the file is evaluated in the order that it appears in the file and that is why it is easy and simple
to access a file's data using a sequential access mechanism. For example, editors and compilers
frequently use this method to check the validity of the code.

Advantages of Sequential Access:

● The sequential access mechanism is very easy to implement.

● It uses lexicographic order to enable quick access to the next entry.
Disadvantages of Sequential Access:

● Sequential access will become slow if the next file record to be retrieved is not present
next to the currently pointed record.
● Adding a new record may need relocating a significant number of records of the file.

2. Direct (or Relative) Access

A Direct/Relative file access mechanism is mostly required with the database systems. In the
majority of the circumstances, we require filtered/specific data from the database, and in such
circumstances, sequential access might be highly inefficient. Assume that each block of storage
holds four records and that the record we want to access is stored in the tenth block. In such a
situation, sequential access will not be used since it will have to traverse all of the blocks to get
to the required record, while direct access will allow us to access the required record instantly.
The direct access mechanism requires the OS to perform some additional tasks but eventually
leads to much faster retrieval of records as compared to sequential access.

Advantages of Direct/Relative Access:

● The files can be retrieved right away with a direct access mechanism, reducing the
average access time of a file.
● There is no need to traverse all of the blocks that come before the required block to
access the record.

Disadvantages of Direct/Relative Access:

● The direct access mechanism is typically difficult to implement due to its complexity.
● Organizations can face security issues as a result of direct access as the users may
access/modify the sensitive information. As a result, additional security processes must
be put in place.

3. Indexed Sequential Access

It's the other approach to accessing a file that's constructed on top of the sequential access
mechanism. This method is practically similar to the pointer-to-pointer concept in which we
store the address of a pointer variable containing the address of some other variable/record in
another pointer variable. The indexes, similar to a book's index (pointers), contain a link to
various blocks present in the memory. To locate a record in the file, we first search the indexes
and then use the pointer-to-pointer concept to navigate to the required file.

Primary index blocks contain the links of the secondary inner blocks which contain links to the
data in the memory.
Advantages of Indexed Sequential Access:

● If the index table is appropriately arranged, it accesses the records very quickly.
● Records can be added at any position in the file quickly.

File Sharing:

File Sharing in an Operating System(OS) denotes how information and files are shared between
different users, computers, or devices on a network; and files are units of data that are stored in
a computer in the form of documents/images/videos or any others types of information
needed.

For Example: Suppose letting your computer talk to another computer and exchange pictures,
documents, or any useful data. This is generally useful when one wants to work on a project
with others, send files to friends, or simply shift stuff to another device. Our OS provides ways
to do this like email attachments, cloud services, etc. to make the sharing process easier and
more secure.

Now, file sharing is nothing like a magical bridge between Computer A to Computer B allowing
them to swap some files with each other.

Various Ways to Achieve File Sharing

Let's see the various ways through which we can achieve file sharing in an OS.

1. Server Message Block (SMB)

SMB is like a network based file sharing protocol mainly used in windows operating systems. It
allows our computer to share files/printer on a network. SMB is now the standard way for
seamless file transfer method and printer sharing.
Example: Imagine in a company where the employees have to share the files on a particular
project . Here SMB is employed to share files among all the windows based operating
[Link] on projects. SMB/CIFS is employed to share files between Windows-based
computers. Users can access shared folders on a server, create, modify, and delete files.

2. Network File System (NFS)

NFS is a distributed based file sharing protocol mainly used in Linux/Unix based operating
System. It allows a computer to share files over a network as if they were based on local. It
provides a efficient way of transfer of files between servers and clients.

Example: Many Programmer/Universities/Research Institution uses Unix/Linux based

Operating System. The Institutes puts up a global server datasets using NFS. The Researchers
and students can access these shared directories and everyone can collaborate on it.

3. File Transfer Protocol (FTP)

It is the most common standard protocol for transferring of the files between a client and a
server on a computer network. FTPs supports both uploading and downloading of the files,
here we can download,upload and transfer of files from Computer A to Computer B over the
internet or between computer systems.

Example: Suppose the developer makes changes on the server. Using the FTP protocol, the
developer connects to the server they can update the server with new website content and
updates the existing file over there.

4. Cloud-Based File Sharing

It involves the famous ways of using online services like Google Drive, DropBox , One
Drive ,etc. Any user can store files over these cloud services and they can share that with
others, and providing access from many users. It includes collaboration in realtime file sharing
and version control access.

Ex: Several students working on a project and they can use Google Drive to store and share for
that purpose. They can access the files from any computer or mobile devices and they can
make changes in realtime and track the changes over there.

These all file sharing methods serves different purpose and needs according to the
requirements and flexibility of the users based on the operating system.

File System Implementation

A file is a collection of related information. The file system resides on secondary storage and
provides efficient and convenient access to the disk by allowing data to be stored, located, and
retrieved. File system implementation in an operating system refers to how the file system
manages the storage and retrieval of data on a physical storage device such as a hard drive,
solid-state drive, or flash drive.

File system implementation is a critical aspect of an operating system as it directly impacts the
performance, reliability, and security of the system. Different operating systems use different
file system implementations based on the specific needs of the system and the intended use
cases. Some common file systems used in operating systems include NTFS and FAT in
Windows, and ext4 and XFS in Linux.
Components of File System Implementation

The file system implementation includes several components, including:

● File System Structure: The file system structure refers to how the files and directories
are organized and stored on the physical storage device. This includes the layout of file
systems data structures such as the directory structure, file allocation table, and inodes.
● File Allocation: The file allocation mechanism determines how files are allocated on the
storage device. This can include allocation techniques such as contiguous allocation,
linked allocation, indexed allocation, or a combination of these techniques.
● Data Retrieval: The file system implementation determines how the data is read from
and written to the physical storage device. This includes strategies such as buffering
and caching to optimize file I/O performance.
● Security and Permissions: The file system implementation includes features for
managing file security and permissions. This includes access control lists (ACLs), file
permissions, and ownership management.
● Recovery and Fault Tolerance: The file system implementation includes features for
recovering from system failures and maintaining data integrity. This includes techniques
such as journaling and file system snapshots.

Implementation Issues

● Management of Disc space: To prevent space wastage and to guarantee that files can
always be stored in contiguous blocks, file systems must manage disc space effectively.
Free space management, fragmentation prevention, and garbage collection are
methods for managing disc space.
● Checking for Consistency and Repairing Errors: The consistency and error-free
operation of files and directories must be guaranteed by file systems. Journaling,
checksumming, and redundancy are methods for consistency checking and error
recovery. File systems may need to perform recovery operations if errors happen in
order to restore lost or damaged data.
● Locking Files and Managing Concurrency: To prevent conflicts and guarantee data
integrity, file systems must control how many processes or users can access a file at
once. File locking, semaphore, and other concurrency-controlling methods are
available.
● Performance Optimization: File systems need to optimize performance by reducing file
access times, increasing throughput, and minimizing system overhead. Caching,
buffering, prefetching, and parallel processing are methods for improving performance.

Key Steps Involved in File System Implementation

File system implementation is a crucial component of an operating system, as it provides an

interface between the user and the physical storage device. Here are the key steps involved in
file system implementation:

● Partitioning The Storage Device: The first step in file system implementation is to
partition the physical storage device into one or more logical partitions. Each partition is
formatted with a specific file system that defines the way files and directories are
organized and stored.
● File System Structures: File system structures are the data structures used by the
operating system to manage files and directories. Some of the key file system structures
include the superblock, inode table, directory structure, and file allocation table.
● Allocation of Storage Space: The file system must allocate storage space for each file
and directory on the storage device. There are several methods for allocating storage
space, including contiguous, linked, and indexed allocation.
● File Operations: The file system provides a set of operations that can be performed on
files and directories, including create, delete, read, write, open, close, and seek. These
 operations are implemented using the file system structures and the storage allocation
methods.
● File System Security: The file system must provide security mechanisms to protect files
and directories from unauthorized access or modification. This can be done by setting
file permissions, access control lists, or encryption.
● File System Maintenance: The file system must be maintained to ensure efficient and
reliable operation. This includes tasks such as disk defragmentation, disk checking, and
backup and recovery.

What is Free Space Management in OS?

There is a system software in an operating system that manipulates and keeps a track of free
spaces to allocate and de-allocate memory blocks to files, this system is called a file
management system in an operating system". There is a free space list in an operating system
that maintains the record of free blocks.

When a file is created, the operating system searches the free space list for the required space
allocated to save a file. While deletion a file, the file system frees the given space and adds
this to the free space list.

Methods of Free Space Management in OS

It is not easy work for an operating system to allocate and de-allocate memory blocks
(managing free space) simultaneously. The operating system uses various methods for adding
free space and freeing up space after deleting a file. There are various methods using which a
free space list can be implemented. We are going to explain them below-

Bitmap or Bit Vector

A bit vector is a most frequently used method to implement the free space list. A bit vector is
also known as a Bit map. It is a series or collection of bits in which each bit represents a disk
block. The values taken by the bits are either 1 or 0. If the block bit is 1, it means the block is
empty and if the block bit is 0, it means the block is not free. It is allocated to some files.
Since all the blocks are empty initially so, each bit in the bit vector represents 0.

Let us take an example:

Given below is a diagrammatic representation of a disk in which there are 16 blocks. There
are some free and some occupied blocks present. The upper part is showing block number.
Free blocks are represented by 1 and occupied blocks are represented by 0.

Advantages of Bit vector method

● Simple and easy to understand.

● Consumes less memory.
● It is efficient to find free space.

Disadvantages of the Bit vector method

● The operating system goes through all the blocks until it finds a free block. (block
whose bit is '0').
● It is not efficient when the disk size is large.

Linked List

A linked list is another approach for free space management in an operating system. In it, all
the free blocks inside a disk are linked together in a linked list. These free blocks on the disk
are linked together by a pointer. These pointers of the free block contain the address of the
next free block and the last pointer of the list points to null which indicates the end of the
linked list. This technique is not enough to traverse the list because we have to read each disk
block one by one which requires I/O time.
In the above example, we have three blocks of free memory, each represented by a node in
the linked list. The first block has 20 bytes of free memory, the second block has 20 bytes of
free memory, and the third block has 60 bytes of free memory. The operating system can use
this linked list to allocate memory blocks to processes as needed.

Advantage of the Linked list

● In this method, available space is used efficiently.

● As there is no size limit on a linked list, a new free space can be added easily.

Disadvantages

● In this method, the overhead of maintaining the pointer appears.

● The Linked list is not efficient when we need to reach every block of memory.

Grouping

The grouping technique is also called the "modification of a linked list technique". In this
method, first, the free block of memory contains the addresses of the n-free blocks. And the
last free block of these n free blocks contains the addresses of the next n free block of
memory and this keeps going on. This technique separates the empty and occupied blocks of
space of memory.

Example

Suppose we have a disk with some free blocks and some occupied blocks. The free block
numbers are 3,4,5,6,9,10,11,12,13,3,4,5,6,9,10,11,12,13,, and 1414. And occupied
block numbers are 1,2,7,8,15,1,2,7,8,15, and 1616 i.e.i.e., they are allocated to some
files.

When the "grouping technique" is applied, block 3 will store the addresses of blocks 4, 5, and
6 because block 3 is the first free block. In the same way, block 6 will store the addresses of
blocks 9, one 0, and one 1 because block 6 is the first occupied block.

Advantage of the Grouping method

1. By using this method, we can easily find addresses of a large number of free blocks
easily and quickly.
Disadvantage

1. We need to change the entire list if one block gets occupied.

Counting

In memory space, several files are created and deleted at the same time. For which memory
blocks are allocated and de-allocated for the files. Creation of files occupy free blocks and
deletion of file frees blocks. When there is an entry in the free space, it consists of two
parameters- "address of first free disk block (a pointer)" and "a number 'n'".

Example

Let us take an example where a disk has 16 blocks in which some blocks are empty and some
blocks are occupied as given below :

When the "counting technique" is applied, the block number 3 will represent block number 4
because block 3 is the first free block. Then, the block stores the number of free blocks
i.e.i.e. - there are 4 free blocks together. In the same way, the first occupied block number 9
will represent block number 10 and keeps the number of rest occupied blocks i.e.- there are 6
occupied blocks as shown in the above figure.

Advantages

● In this method, a bunch of free blocks takes place fastly.

● The list is smaller in size.

Disadvantage

● In the counting method, the first free block stores the rest free blocks, so it requires
more space.

Mass Storage Management

Disks are the mainly used mass storage devices. They provide the
bulk of secondary storage in operating systems today.
Disk Structure
Each modern disk contains concentric tracks and each track is
divided into multiple sectors. The disks are usually arranged as a
one dimensional array of blocks, where blocks are the smallest
storage [Link] can also be called as sectors. For each surface of
the disk, there is a read/write desk available. The same tracks on all
the surfaces is known as a cylinder.

Disk Scheduling

There are many disk scheduling algorithms that provide the total head movement for various requests to th

All these algorithms are explained using the following requests for the disk

10,95,23,78,80

First Come First Serve Scheduling (FCFS)

In first come first served scheduling, the requests are serviced in their coming order. This algorithm is fair as it all

In the above example, the requests are serviced in the order they appear i.e
10, 95, 23, 78, 80. The seek head is initially positioned at 50 and it starts
from there.

Shortest Seek Time First Scheduling

The requests that are closest to the current head are served first before moving away in shortest seek time first sch
In the above example, the requests are serviced in the order 23, 10, 78, 80,
95. The seek head is initially positioned at 50 and it starts from there. 23 is
closest to 50 so it is services first. Then 10 is closer to 23 than 78 so it is
services next. After this 78, 80 and 95 are serviced.

SCAN Scheduling

In this scheduling algorithm, the head moves towards one direction while servicing all the requests in that directio
In the above example, the requests are serviced in the order 23, 10, 78, 80,
95. The head is initially at 50 and moves towards the left while servicing
requests 23 and 10. When it reaches the end of the disk, it starts moving
right and services 78, 80 and 95 as they occur.

LOOK Scheduling

LOOK scheduling algorithm is similar to SCAN scheduling but is its practical version. In this algorithm, the head
In the above example, the requests are serviced in the order 23, 10, 78, 80,
95. The head is initially at 50 and moves towards the left while servicing
requests 23 and 10. When it reaches the last request on the left i.e. 10, it
starts moving right and services 78, 80 and 95 as they occur.