UNIT III

MEMORY MANAGEMENT AND FILE SYSTEMS

Main Memory – Background, Swapping, Contiguous Memory Allocation, Paging, Segmentation –
Virtual Memory – Demand Paging, Page Replacement, Allocation, Thrashing; Allocating Kernel
Memory. Mass Storage system – HDD Scheduling – File concept, Access methods, Directory
Structure, Sharing and Protection; File System Structure, Directory implementation, Allocation
Methods, Free Space Management

3.1 MAIN MEMORY

An address generated by the CPU is commonly referred as Logical Address, whereas the
address seen by the memory unit that is one loaded into the memory address register of the
memory is commonly refereed as the Physical Address. The compile time and load time address
binding generates the identical logical and physical addresses. However, the execution time
addresses binding scheme results in differing logical and physical addresses.
The set of all logical addresses generated by a program is known as Logical Address Space,
where as the set of all physical addresses corresponding to these logical addresses is Physical
Address Space. Now, the run time mapping from virtual address to physical address is done by a
hardware device known as Memory Management Unit. Here in the case of mapping the base
register is known as relocation register. The value in the relocation register is added to the
address generated by a user process at the time it is sent to memory Memory-Management Unit
(MMU).
Hardware device that maps virtual to physical address In MMU scheme, the value in the
relocation register is added to every address generated by a user process at the time it is sent to
memory

Fig.3.1.1 logical vs physical address

The user program deals with logical addresses; it never sees the real physical addresses.
The user program never sees the real physical address space, it always deals with the
Logical addresses. As we have two different type of addresses Logical address in the range (0
to max) and Physical addresses in the range(R to R+max) where R is the value of
relocation register. The user generates only logical addresses and thinks that the process runs
in location to 0 to max. As it is clear from the above text that user program supplies only logical
addresses, these logical addresses must be mapped to physical address before they are used.
Base and Limit Registers
A pair of base and limit registers define the logical address space

Fig.3.1.2 Hardware Protection with Base And Limit

Fig.3.1.3 Base and limit Registers

Binding of Instructions and Data to Memory
Address binding of instructions and data to memory addresses can happen at three different
stages Compile time: If memory location known a priori, absolute code can be generated; must
recompile code if starting location changes Load time: Must generate re locatable code if
 memory location is not known at compile time Execution time: Binding delayed until run
time if the process can be moved during its execution from one memory segment to another.
Need hardware support for address maps (e.g., base and limit registers)

Fig.3.1.4 Multistep process in user program

Dynamic Loading
Routine is not loaded until it is called Better memory-space utilization; unused routine is never
loaded.
Useful when large amounts of code are needed to handle infrequently occurring cases .No
special support from the operating system is required implemented through program design.
Dynamic Linking
Linking postponed until execution time mall piece of code, stub, used to locate the appropriate
memory-resident library routine Stub replaces itself with the address of the routine, and
executes the routine linking is particularly useful for libraries System also known as shared
libraries.
3.2 SWAPPING
 A process can be swapped temporarily out of memory to a backing store, and then brought back
into memory for continued execution Backing store fast disk large enough to accommodate
copies of all memory images for all users; must provide direct access to these memory images
Roll out, roll in swapping variant used for priority-based scheduling algorithms; lower-priority
process is swapped out so higher-priority process can be loaded and executed Major part of
swap time is transfer time; total transfer time is directly proportional to the amount of memory
swapped and Modified versions of swapping are found on many systems (i.e., UNIX, Linux, and
Windows)
System maintains a ready queue of ready-to-run processes which have memory images on disk

Fig.3.2.1 Schematic view of Swapping

Swapping is the process of transferring the entire process, or parts of it, from main memory to a
secondary storage (usually a disk) and then bringing it back into main memory when needed. This
technique helps to manage the limited physical memory available by temporarily offloading
inactive or less frequently used processes to free up memory for active processes.
Key Concepts
1. Swap Space: A dedicated area on the disk where processes are swapped out from the main
memory. The size of the swap space can significantly impact the performance of the swapping
process.

2. Swapping In: When a process needs to be executed but is currently in the swap space, it is
brought back into main memory.

3. Swapping Out: When the main memory is full, and a new process needs to be loaded, an
inactive or lower-priority process is moved to the swap space.
How Swapping Works
1. Process Execution: When a process is loaded for execution, it is placed in the main memory.
2. Memory Full: If the main memory is fully occupied and a new process needs to be executed,
the operating system selects an existing process to swap out.
3. Swapping Out: The selected process is moved to the swap space on the disk.
4. Swapping In: When the swapped-out process needs to be executed again, it is moved back
into the main memory, possibly displacing another process.
Benefits of Swapping
 Efficient Memory Utilization: Allows the operating system to handle more processes than
the available physical memory by temporarily moving inactive processes to disk.
 Multiprogramming: Enables multiple processes to be loaded and run concurrently, improving
the utilization of the CPU and system resources.
Drawbacks of Swapping
 Performance Overhead: Swapping involves disk I/O operations, which are significantly
slower than memory operations, leading to potential performance degradation.
 Latency: The time taken to swap processes in and out can introduce delays, especially for
real-time applications.
 Fragmentation: Over time, swapping can cause fragmentation of memory and swap space,
requiring additional management and potentially reducing efficiency.
Swapping vs. Paging
 Swapping: Entire process is moved between main memory and swap space.
 Paging: Only fixed-size pages of the process are moved between main memory and
secondary storage, allowing for more granular memory management.
Swapping in Modern Systems
In modern operating systems, swapping is often combined with other memory management
techniques such as paging and virtual memory to balance the trade-offs between memory
utilization and performance. Systems may use a combination of these techniques to achieve
efficient and effective memory management.

3.3 CONTIGUOUS MEMORY ALLOCATION

 Contiguous Memory Allocation is a memory management technique in which each process
is allocated a single continuous (unbroken) block of memory.
 This means all the bytes for that process are placed next to each other in RAM.
Why it is Needed?
 OS must assign memory to processes efficiently.
  Contiguous blocks make address translation simple.
 Useful in early operating systems and embedded systems.
How It Works
The main memory is divided into two parts:

 OS region – Lower memory reserved for operating system.

 User region – Remaining memory split into contiguous blocks for user processes.
Each process gets:
One base address (starting point)
One limit (size of the block)
Logical address is converted to physical address as:
Physical Address = Base + Logical Address
Types of Contiguous Allocation
1. Single-Partition Allocation
 Entire memory is one large partition for user processes.
 OS is placed in lower memory.
 Only one user process can run at a time.
 Very simple but inefficient.
2. Multiple-Partition Allocation
 Memory is divided into multiple fixed or variable-sized partitions.
 Fixed Partitioning
 Memory is divided into fixed-size blocks.
 Each process is assigned to one partition.

Fig.3.3.1 Multiple-partition allocation

Advantages
 Simple, less overhead.
Disadvantages
 Internal fragmentation (wasted space inside partition).
 Number of processes limited by number of partitions.

B. Variable Partitioning
 Memory is divided dynamically based on process size.
 Partitions are created at runtime.
Advantages
 No internal fragmentation.
 Exact-fit blocks possible.
Disadvantages
 External fragmentation (free blocks scattered).
 Requires compaction to remove scattered holes.
 Allocation Methods (Placement Algorithms)
When a process arrives, OS must choose a free block:
1. First Fit
Allocate the first free block that is big enough.
Fast, widely used.
2. Best Fit
Allocate the smallest free block that fits.
Minimizes leftover space but slower.
3. Worst Fit
Allocate the largest free block.
Leaves large remainders for future processes.

Fig 3.3.2 Memory Allocation Strategies (First-Fit, Best-Fit, Worst-Fit) for a 13K Request
Fragmentation Issues
1. External Fragmentation
Total free memory exists, but in small scattered blocks.
Prevents allocation even if enough memory is available.
2. Internal Fragmentation
 Space inside allocated block is unused.
 Happens in fixed partitions.
 Solution: Compaction
 OS shifts processes to make large contiguous free blocks.
 Time-consuming.

Fig.3.3.3 Fragmentation Technique

Advantages
 Simple to implement.
 Fast address translation.
 Good for small/embedded systems.
Disadvantages
 Leads to fragmentation.
 Memory utilization is low.
 Hard to resize processes.
 Not suitable for modern, multi-programming systems.
3.4 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.

Paging Hardware

Fig.3.4.1 Address Translation

Address Translation
 Page address is called logical address and represented by page number and the offset.
Frame address is called physical address and represented by a frame number and the
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.

Logical Address = Page number + page offset

Physical Address = Frame n

Paging Example
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.
32-byte memory and 4-byte pages

Free Frames
 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.
Implementation of Page Table
 Page table is kept in main memory
 Page-table base register (PTBR) points to the page table
 Page-table length register (PRLR) indicates size of the page table
 In this scheme every data/instruction access requires two memory accesses. One for the
page table and one for the data/instruction. The two memory access problem can be solved
by the use of a special fast-lookup hardware cache called associative memory or translation
look-aside buffers (TLBs)
Paging Hardware With TLB
 Fig.3.4.2 Paging hardware with TLB hit
Memory Protection

Memory protection implemented by associating protection bit with each frame

Valid-invalid bit attached to each entry in the page table:

Valid (v) or Invalid (i) Bit In A

Page Table

Fig.3.4.3 Memory Protection

Shared Pages Shared code
 One copy of read-only (reentrant) code shared among processes (i.e., text editors,
compilers, window systems).
 Shared code must appear in same location in the logical address space of all processes
 Private code and data
 Each process keeps a separate copy of the code and data
 The pages for the private code and data can appear anywhere in the logical address
space
Shared Pages Example
 Fig.3.4.4 Shared Pages Example
3.5 SEGMENTATION
Memory-management scheme that supports user view of memory A program is a collection
of segments
A segment is a logical unit such as:
 Main program
 Procedure
 Function method
 Object
local variables, global variables common block stack symbol table arrays

Fig 3.5.1 User view of program

Segmentation Architecture
 Logical address consists of a two tuple:
<segment-number, offset>,
 Base -contains the starting physical address where the segments reside in memory
 Limit- specifies the length of the segment
 Segment-table base register (STBR)
 Segment-table length register (STLR) indicates number of segments used by a program;
segment number s is legal if s < STLR
Protection With each entry in segment table associate:
 validation bit = 0 Þ illegal segment
 read/write/execute privileges ,Protection bits associated with segments; code sharing
occurs at segment level. Since segments vary in length, memory allocation is a dynamic
storage-allocation problem A segmentation example is shown in the following diagram
Segmentation Hardware

Fig 3.5.2 segmentation hardware

 Fig.3.5.3 Segmentation
3.6 VIRTUAL MEMORY
 Virtual Memory is a space where large programs can store themselves in form of
pages while their execution and only the required pages or portions of processes are
loaded into the main memory. This technique is useful as large virtual memory is
provided for user programs when a very small physical memory is there.
In real scenarios, most processes never need all their pages at once, for
following reasons :
 Error handling code is not needed unless that specific error occurs, some of which are
quite rare.
 Arrays are often over-sized for worst-case scenarios, and only a small fraction of the
arrays are actually used in practice. Certain features of certain programs are rarely
used.
 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
 Fig.3.6.1 Diagram showing virtual memory that is larger than physical memory.
.Benefits of having Virtual Memory :
 Large programs can be written, as virtual space available is huge compared to physical
memory.
 Less I/O required, leads to faster and easy swapping of processes.
 More physical memory available, as programs are stored on virtual memory, so they
occupy very less space on actual physical memory.
3.7 DEMAND PAGING
 A demand paging is similar to a paging system with swapping. When we want to execute
a process, we swap it into memory. Rather than swapping the entire process into
memory.
 When a process is to be swapped in, the pager guesses which pages will be used before
the process is swapped out again Instead of swapping in a whole process, the pager
brings only those necessary pages into memory. Thus, it avoids reading into memory
pages that will not be used in anyway, decreasing the swap time and the amount of
physical memory needed.
 Hardware support is required to distinguish between those pages that are in memory and
those pages that are on the disk using the valid-invalid bit scheme. Where valid and
invalid pages can be checked checking the bit and marking a page will have no effect if
the process never attempts to access the pages. While the process executes and
accesses pages that are memory resident, execution proceeds normally.
Fig. Transfer of a paged memory to continuous disk space
 Fig.3.7.1 Demand Paging
 Access to a page marked invalid causes a page-fault trap. This trap is the result of the
operating system's failure to bring the desired page into memory.
 Initially only those pages are loaded which will be required the process immediately. The
pages that are not moved into the memory are marked as invalid in the page table.
 For an invalid entry the rest of the table is empty. In case of pages that are loaded in the
memory, they are marked as valid along with the information about where to find the
swapped out page.
 When the process requires any of the page that is not loaded into the memory, a page
fault trap is triggered and following steps are followed,
The memory address which is requested by the process is first checked, to verify the request
made by the process.
 If its found to be invalid, the process is terminated.
 In case the request by the process is valid, a free frame is located, possibly from a free-
frame list, where the required page will be moved.
A new operation is scheduled to move the necessary page from disk to the specified memory
location. (This will usually block the process on an I/O wait, allowing some other process to use
the CPU in the meantime. )
When the I/O operation is complete, the process's page table is updated with the new frame
number, and the invalid bit is changed to valid.
 Fig.3.7.2 Steps in handling a page fault
The instruction that caused the page fault must now be restarted from the beginning. There are
cases when no pages are loaded into the memory initially, pages are only loaded when
demanded by the process by generating page faults. This is called Pure Demand Paging.
The only major issue with Demand Paging is, after a new page is loaded, the process starts
execution from the beginning. It is not a big issue for small programs, but for larger programs it
affects performance drastically.
What is dirty bit?
When a bit is modified by the CPU and not written back to the storage, it is called as a dirty bit.
This bit is present in the memory cache or the virtual storage space.
Advantages of Demand Paging:
 Large virtual memory.
 More efficient use of memory.
 Unconstrained multiprogramming. There is no limit on degree of multiprogramming.
Disadvantages of Demand Paging:
Number of tables and amount of processor over head for handling page interrupts are greater
than in the case of the simple paged management techniques.
due to the lack of an explicit constraints on a jobs address space size.
3.8 PAGE REPLACEMENT
 Page Replacement is a memory management technique used in paging-based virtual
memory systems.
 When a page fault occurs and no free frames are available in physical memory, the
operating system selects a victim page to remove (swap out) so that the required page
can be loaded into memory.
Why Page Replacement is Needed
 Physical memory (RAM) is limited
 Programs are larger than available memory
 Improves memory utilization
 Supports multiprogramming
 Enables virtual memory
Page Replacement Process
1. CPU references a page
2. Page is not present in memory → Page Fault
3. OS checks for a free frame
o If available → load page
 o If not available → Page Replacement
[Link] page is selected using a replacement algorithm
[Link] page is written to disk (if dirty)
[Link] page is loaded into memory
[Link] table is updated
[Link] resumes
Page Replacement Algorithm
 Page Replacement Algorithm is used by the Operating System to decide which page to
remove from physical memory when a page fault occurs and no free frame is available.
For Example consider the following Sequence Address -123, 215,600,1234,76,96 .
If page size is 100, then the reference string is 1,2,6,12,0,0 First
 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

Reference String

Fig 3.8.1 FIFO

 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.
 Fig 3.8.2 Optimal Page Algorithm
 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.

Fig 3.8.3 LRU Algorithm

 Second chance page replacement algorithm
Rule:
A modified FIFO using a reference bit (R-bit).
Working:
 If R = 0 → replace page
 If R = 1 → give second chance and reset R
Advantage:
 Better than FIFO
Implementation:
Add a "second chance" bit to each memory frame.
Each time a memory frame is referenced, set the "second chance" bit to ONE (1) - this will give
the frame a second chance...
A new page read into a memory frame has the second chance bit set to ZERO (0)
When you need to find a page for removal, look in a round robin manner in the memory frames: If
the second chance bit is ONE, reset its second chance bit (to ZERO) and continue.
If the second chance bit is ZERO, replace the page in that memory frame.
The following figure shows the behavior of the program in paging using the Second Chance
page replacement policy:

Fig 3.8.4 Second chance page replacement algorithm

We can see notably that the bad replacement decision made by FIFO is not present in
Second chance!!!
There are a total of 9 page read operations to satisfy the total of 18 page requests - just as good
as the more computationally expensive LRU method.
NRU (Not Recently Used) Page Replacement Algorithm - This algorithm requires that each page
have two additional status bits 'R' and 'M' called reference bit and change bit respectively. The
reference bit(R) is automatically set to 1 whenever the page is referenced. The change bit (M) is
set to 1 whenever the page is modified. These bits are stored in the PMT and are updated on
every memory reference. When a page fault occurs, the memory manager inspects all the pages
and divides them into 4 classes based on R and M bits.

Class 1: (0,0) - the best page to replace.

Class 2: (0,1)- - the page will need to be written out before replacement
Class 3: (1,0) - probably will be used again soon.
Class 4: (1,1)
- probably will be used again, and write out will be needed before replacing it.
This algorithm removes a page at random from the lowest numbered non-empty class.

3.9 ALLOCATION
 The main memory of the system is divided into frames.
 The OS has to allocate a sufficient number of frames for each process and to do so, the OS
uses various algorithms.
 The five major ways to allocate frames are as follows:
1) Proportional frame allocation
 The proportional frame allocation algorithm allocates frames based on the size that is
necessary for the execution and the number of total frames the memory has.
 The only disadvantage of this algorithm is it does not allocate frames based on priority.
 This situation is solved by Priority frame allocation.
2) VPriority frame allocation
 Priority frame allocation allocates frames based on the priority of the processes and
the number of frame allocations.
 If a process is of high priority and needs more frames then the process will be
allocated that many frames.
 The allocation of lower priority processes occurs after it.
3) Global replacement allocation
 When there is a page fault in the operating system, then the global replacement
allocation takes care of it.
 The process with lower priority can give frames to the process with higher priority to
avoid page faults.
4) Local replacement allocation
 In local replacement allocation, the frames of pages can be stored on the same page.
  It doesn’t influence the behavior of the process as it did in global replacement
allocation.
5) Equal frame allocation
 In equal frame allocation, the processes are allocated equally among the processes in
the operating system.
 The only disadvantage in equal frame allocation is that a process requires more frames
for allocation for execution and there are only a set number of frames.
3.10 THRASHING
Thrashing is a condition in a computer system where the CPU spends most of its time
handling page faults instead of executing processes, due to insufficient physical memory.
To know more clearly about thrashing, first, we need to know about page fault and swapping.
 Page fault: We know every program is divided into some pages. A page fault occurs
when a program attempts to access data or code in its address space but is not currently
located in the system RAM.
 Swapping: Whenever a page fault happens, the operating system will try to fetch that
page from secondary memory and try to swap it with one of the pages in RAM. This process
is called swapping.
 Thrashing is when the page fault and swapping happens very frequently at a higher rate, and
then the operating system has to spend more time swapping these pages. This state in the
operating system is known as thrashing. Because of thrashing, the CPU utilization is going to
be reduced or negligible.
Algorithms during Thrashing
Whenever thrashing starts, the operating system tries to apply either the Global page
replacement Algorithm or the Local page replacement algorithm.
 Global Page Replacement
Since global page replacement can bring any page, it tries to bring more pages whenever
thrashing is found. But what actually will happen is that no process gets enough frames, and as a
result, the thrashing will increase more and more. Therefore, the global page replacement
algorithm is not suitable when thrashing happens.
 Local Page Replacement
Unlike the global page replacement algorithm, local page replacement will select pages which
only belong to that process. So there is a chance to reduce the thrashing. But it is proven that
there are many disadvantages if we use local page replacement. Therefore, local page
replacement is just an alternative to global page replacement in a thrashing scenario.
 Causes of Thrashing
  Too many processes in memory
 Insufficient number of frames
 Poor page replacement algorithm
 High degree of multiprogramming
 Processes do not have their working set in memory

How to Eliminate Thrashing

Thrashing has some negative impacts on hard drive health and system performance. Therefore,
it is necessary to take some actions to avoid it. To resolve the problem of thrashing, here are the
following methods, such as:
 Adjust the swap file size: If the system swap file is not configured correctly, disk thrashing
can also happen to you.
 Increase the amount of RAM: As insufficient memory can cause disk thrashing, one solution
is to add more RAM to the laptop. With more memory, your computer can handle tasks easily
and don't have to work excessively. Generally, it is the best long-term solution.
 Decrease the number of applications running on the computer: If there are too many
applications running in the background, your system resource will consume a lot. And the
remaining system resource is slow that can result in thrashing. So while closing, some
applications will release some resources so that you can avoid thrashing to some extent.
3.11 KERNAL MEMORY
 Kernel Memory is the portion of main memory (RAM) reserved exclusively for the
Operating System kernel.
 It stores core OS data structures and code required to manage hardware, processes,
memory, and system resources.
Why Kernel Memory is Needed
 Execute kernel functions
 Handle system calls
 Manage processes, memory, and I/O
 Ensure system security and stability
 Prevent user programs from accessing critical OS data
Components of Kernel Memory
1. Kernel Code
 Core OS instructions
 System call handling
 Interrupt and exception handlers
 2. Kernel Data Structures
 Process Control Blocks (PCB)
 Page tables
 File system metadata
 Open file tables
3. Kernel Stack
 Separate stack for each process
 Used during system calls and interrupts
 Prevents corruption by user programs

4. Device Drivers
 Code to communicate with hardware devices
 Executes in kernel mode
5. Buffer Cache
 Stores disk blocks temporarily
 Improves I/O performance
3.12 MASS STORAGE
A mass storage system in the context of operating systems refers to the infrastructure and
mechanisms that enable the management and utilization of large-scale storage devices such as
hard drives, solid-state drives (SSDs), network-attached storage (NAS), and other storage arrays.
Here’s an overview of what constitutes a mass storage system and its role within operating systems:

Fig.3.12.1 Mass Storage

Components of a Mass Storage System
 Storage Devices

Hard Drives (HDDs): Traditional mechanical drives that store data on spinning platters.

Solid-State Drives (SSDs): Flash-based storage devices that offer faster access speeds than
HDDs.

Network-Attached Storage (NAS): Storage devices connected to a network, providing file-level

data access to clients.
 Storage Controllers
 Hardware or software components responsible for managing data transfers between the storage
devices and the rest of the system. This includes handling read and write operations, caching, and
error detection/correction.
 File Systems

File System Drivers: Software components within the operating system responsible for interpreting
the structure of storage devices and managing data access. Examples include NTFS and FAT32 on
Windows, ext4 on Linux, and HFS+ on macOS.

Volume Management: Tools and utilities for creating, resizing, and managing partitions or logical
volumes on storage devices.
 Data Access and Management

I/O Management: Operating system functions that control input and output operations to and from
storage devices, ensuring efficient data transfer and minimizing latency.

Caching: Techniques to store frequently accessed data in faster memory (such as RAM or SSD
caches) to improve overall system performance.

Data Integrity: Mechanisms to ensure data consistency and reliability, including error detection and
correction algorithms.
 Role within Operating Systems

Data Storage and Retrieval

The primary function of a mass storage system is to store large volumes of data persistently and
provide mechanisms for retrieving that data efficiently when needed by applications or users.

Resource Management

Operating systems manage access to storage resources, allocating storage space, scheduling I/O
operations, and ensuring fair access among competing processes.

Integration with File Systems

Mass storage systems interact closely with file systems to organize and manage data stored on
storage devices, translating file operations (such as read and write requests) into physical storage
device operations.

Security and Data Protection

Implementing access control mechanisms, encryption, and backup strategies to protect data integrity
and confidentiality stored on mass storage devices.
 Challenges and Advancements

Performance Optimization

Advances in storage technologies (such as SSDs and NVMe) and improvements in I/O scheduling
algorithms aim to reduce latency and increase throughput for data-intensive applications.

Scalability

Managing large-scale storage systems efficiently as the volume of data and number of users grow,
requiring robust scalability and fault-tolerance mechanisms.

Data Migration and Mobility

Facilitating seamless data movement between different storage tiers (e.g., from local storage to
cloud storage) while maintaining accessibility and data integrity.

Integration with Cloud Services

 Modern operating systems increasingly integrate with cloud storage services, enabling hybrid
deployments and extending storage capabilities beyond traditional local devices.
 In essence, a mass storage system forms a critical infrastructure within operating systems,
enabling persistent data storage and efficient data access across a wide range of storage
devices.
 The continual evolution of storage technologies and operating system capabilities plays a vital
role in meeting the growing demands for scalable, secure, and high-performance data storage
solutions.
3.13 HDD SCHEDULING
Disk scheduling and management in operating systems are critical for optimizing the access and
utilization of storage devices like hard disk drives (HDDs) and solid-state drives (SSDs). Here's a
detailed overview of disk scheduling and management:
 Disk Scheduling

Disk scheduling refers to the method by which the operating system decides the order in which
pending requests for disk I/O (Input/Output) are processed. The goal is to minimize seek time (the
time taken to position the disk's read/write heads over the desired track) and rotational latency (the
time for the desired sector to rotate under the read/write heads). Efficient disk scheduling algorithms
improve overall system performance by reducing the time spent waiting for disk operations.

Fig.3.13.1 Disk Scheduling

Common Disk Scheduling Algorithms

 First-Come, First-Served (FCFS):

Requests are serviced in the order they arrive. Simple but can lead to poor performance if there are
frequent requests far apart on the disk.
 Shortest Seek Time First (SSTF):

Services the request that requires the least head movement from its current position. Minimizes seek
time but may result in starvation for requests located far from the current position.
 SCAN (Elevator) Algorithm:

The disk arm moves in one direction (typically from one end to the other), servicing all requests in
that direction, and then reverses direction. Prevents starvation of requests at one end but may cause
delays for requests near the reversal point.
 C-SCAN Algorithm:

Similar to SCAN but always moves in one direction (e.g., towards higher sector numbers), servicing
requests, and then jumps to the beginning of the disk. Reduces maximum wait time compared to
SCAN.
 LOOK and C-LOOK Algorithms:

Variants of SCAN and C-SCAN that only move to the end of the requests and reverse direction
without moving to the end of the disk.
 Optimization Algorithms:

Algorithms like Shortest Positioning Time (SPT) and Elevator with Look-Ahead (Elevator-Look) aim
to predict and optimize disk head movement patterns based on historical data or predictive models.

 Disk Management

Disk management involves various aspects of managing storage devices within an operating
system, including partitioning, formatting, and maintaining file systems. Key components and
operations include:
 Partitioning:

Dividing a physical disk into one or more logical units called partitions, each of which can be
independently managed and formatted with a file system.
 Formatting:

Preparing a partition with a specific file system (e.g., NTFS, FAT32, ext4) that includes creating
necessary data structures (like file allocation tables or inode tables) for organizing files.
 File System Management:

Managing file systems involves creating, deleting, reading, writing, and modifying files and
directories. This includes managing metadata (file attributes, permissions, timestamps) and
allocating space for files on disk.
 Disk Quotas:

Setting limits on the amount of disk space users or groups can consume, ensuring fair and efficient
use of storage resources.
 Error Handling and Recovery:

Implementing mechanisms to detect and correct errors on disk drives, such as bad sectors, and
recovering data from damaged areas using redundancy techniques (e.g., RAID).
 Storage Virtualization:

Abstracting physical storage resources into virtual storage pools that can be dynamically allocated
and managed, facilitating scalability and resource optimization.

 Challenges and Advances

 Solid-State Drives (SSDs): Different disk scheduling strategies are often required due to the
absence of mechanical components like moving heads, which drastically reduces seek time.
 Hybrid Storage Solutions: Integrating SSDs with traditional HDDs to optimize cost and
performance, requiring intelligent management and caching strategies.
 Cloud Storage Integration: Operating systems increasingly support seamless integration with
cloud storage services, enhancing scalability and enabling remote data access and synchronization.

Effective disk scheduling and management are crucial for maximizing the performance, reliability,
and efficiency of storage systems within operating environments. The choice of disk scheduling
algorithm and the implementation of robust disk management strategies significantly impact the
overall responsiveness and stability of computer systems, especially in environments with high I/O
demands and diverse storage configurations.

3.14 FILE SYSTEM INTERFACE

File Concept

Computers can store information on various storage media such as, magnetic disks, magnetic tapes,
optical disks. The physical storage is converted into a logical storage unit by operating system. The
logical storage unit is called FILE. A file is a collection of similar records. A record is a collection of
related fields that can be treated as a unit by some application program. A field is some basic
element of data. Any individual field contains a single value. A data base is collection of related data.

Student Marks Marks Fail/Pas

KUMA 85 86 P

LAKSH 93 92 P

Data File

Student name, Marks in sub1, sub2, Fail/Pass is fields. The collection of fields is called a RECORD.

Record

LAKSH 93 92 P

Collection of these records is called a data file.

FILE CONCEPT
 File Attributes

Name : A file is named for the convenience of the user and is referred by its name. A name is
usually a string of characters.

Identifier : This unique tag, usually a number ,identifies the file within the file system.

Type : Files are of so many types. The type depends on the extension of the file.

Example:

.exe Executable file

.obj Object file

.src Source file

Location : This information is a pointer to a device and to the location of the file on that device.

Size : The current size of the file (in bytes, words, blocks).

Protection : Access control information determines who can do reading, writing, executing and so
on.

Time, Date, User identification : This information may be kept for creation, last modification, last use.

Fig 3.14.1 Hierarchical Structure of a File System

 File Operations

Creating a file : Two steps are needed to create a file.

They are:

Check whether the space is available or not.

If the space is available then made an entry for the new file in the directory. The entry includes
name of the file, path of the

Writing a file : To write a file, we have to know 2 things. One is name of the file and second is the
information or data to be written on the file, the system searches the entired given location for the
file. If the file is found, the system must keep a write pointer to the location in the file where the next
write is to take place.

Reading a file : To read a file, first of all we search the directories for the file, if the file is found, the
system needs to keep a read pointer to the location in the file where the next read is to take place.
Once the read has taken place, the read pointer is updated.

Repositioning within a file : The directory is searched for the appropriate entry and the current file
position pointer is repositioned to a given value. This operation is also called file seek.
Deleting a file : To delete a file, first of all search the directory for named file, then released the file
space and erase the directory entry.

Truncating a file : To truncate a file, remove the file contents only but, the attributes are as it is.
 F
ile Types: The name of the file split into 2 parts. One is name and second is Extension. The
file type is depending on extension of the file.

File Type Extension Purpose

.exe Ready to run (or)ready

Executable .com To run

.bin machine

.c

Source code .cpp Source code in various languages.

.asm

.obj
Object Compiled, machine
.o

.bat Commands to
Batch
.sh the command

.txt
Text Textual data, documents
.doc

.doc
Word Various word proc
.wp
processor essor form ats
.rtf

.lib Libraries of
Library
.dll routines for

.pdf Binary file in a

Print or View
.jpg format for

.arc Related files

Archive
.zip grouped into a
 .mpeg
Binaryfile containing audio
Multimedia .mp3
or audio/video
.avi

 File Structure
A file has a certain defined structure according to its type.
A text file is a sequence of characters organized into lines - txt, doc A
source file is a sequence of procedures and functions - c, cpp, java

An object file is a sequence of bytes organized into blocks that are understandable by the machine –
obj,o

An Executable file ready to run machine language program - exe, com, bin
Batch file commands to the command interpreter - bat, sh
Word Processor file various word processor formats - wp, tex, rrf, doc Archive
file related files grouped into one compressed file - arc, zip, tar Multimedia file
containing audio/video information - mpeg, mov, rm, mp3,avi

3.15 FILE ACCESS METHODS

Files stores information, this information must be accessed and read into computer memory.
There are so many ways that the information in the file can be accessed.

Sequential file access

Information in the file is processed in order i.e. one record after the other. Magnetic tapes are
supporting this type of file accessing.

th
Eg : A file consisting of 100 records, the current position of read/write head is 45 record, suppose
th
we want to read the 75 record then, it access sequentially from 45, 46, 47

Fig.3.15.1 sequential access

Direct access

Direct access is also called relative access. Here records can read/write randomly without any
order. The direct access method is based on a disk model of a file, because disks allow random
access to any file block.
 th
Eg : A disk containing of 256 blocks, the position of read/write head is at 95 block. The block is to
th th
be read or write is 250 block. Then we can access the 250 block directly without any restrictions.

Eg : CD consists of 10 songs, at present we are listening song 3, If we want to listen song 10, we
can shift to 10.

Fig.3.15.2 Direct Access

Indexed access

The main disadvantage in the sequential file is, it takes more time to access a Record.

Records are organized in sequence based on a key field.

Eg :

A file consisting of 60000 records, the master index divide the total records into 6 blocks, each block
consisting of a pointer to secondary index. The secondary index divides the 10,000 records
into 10 indexes. Each index consisting of a pointer to its original location. Each record in the index
file consisting of 2 field, A key field and a pointer field.
 Fig.3.15.3 Indexed Sequential File access

3.16 DIRECTORY STRUCTURE

Collection of files is a file is called Directory.
Directory can be defined as the listing of the related files on the disk. The directory contains information
about the files, including attributes, location and ownership.

Fig.3.16.1 Directory Structure

A hard disk can be divided into the number of partitions of different sizes. The partitions are
also called
 volumes or mini disks. Each partition must have at least one directory in which, all the files of
the partition can be listed. A directory entry is maintained for each file in the directory which stores
all the information related to that file. A directory can be viewed as a file which contains the Meta
data of the bunch of files.

Directory operations
 File Creation New files need to be created and added to the directory
 Search for the file A particular file in a directory by their names.
 File deletion When a file is no longer needed, we want to be able to
remove it from the directory.
 Renaming the file The name of a file represents its contents to its users, we must be able to
change the name when the contents or use of the file changes. Renaming a file may also allow
its position within the directory structure to be changed.

 Traversing Files We may wish to access every directory and every file within a directory
structure. For reliability, it is a good idea to save the contents and structure of the entire file
system at regular intervals.

 Listing of files We need to be able to list the files in a directory and the contents of the
directory entry for each file in the list.

Advantages
 Efficiency: A file can be located more quickly.
 Naming: It becomes convenient for users as two users can have same name for different files
or may have different name for same file.
 Grouping: Logical grouping of files can be done by properties e.g. all java programs, all games
etc.

3.17 SHARING AND PROTECTION

In a multi-user and multiprogramming environment, an Operating System must allow sharing of
resources while ensuring protection against misuse. Sharing improves resource utilization, whereas
protection ensures system safety and reliability. Both are essential for correct and secure system
operation.

Sharing in Operating Systems

Definition
Sharing refers to the controlled access of system resources by multiple users or processes
simultaneously.
Resources Shared
 1. CPU – Shared using time-sharing and scheduling
2. Main Memory – Shared via paging and segmentation
3. Files and Directories – Shared with access permissions
4. I/O Devices – Shared using spooling and buffering
5. Data and Programs – Shared through shared memory and IPC
Advantages of Sharing
 Efficient utilization of hardware resources
 Increased system throughput
 Supports multitasking and collaboration

 Reduces duplication of data and programs

Protection in Operating Systems

Definition

Protection refers to the mechanisms used by the OS to control access to system

resources and prevent unauthorized or accidental misuse.
Need for Protection
 Prevents one process from affecting another
 Avoids data corruption and system crashes
 Ensures confidentiality and integrity of data
 Enforces user privileges and policies

Protection Mechanisms
1. Protection Domains
A protection domain defines a set of resources (objects) and access rights
available to a process.
2. Access Control Matrix
A table that specifies the rights of each domain over each object.

DOMAIN FiLe Printer Memory

Read,
D1 Print –
Write

D2 Read – Read
3. Access Control Lists (ACL)
Each object maintains a list of users and their permitted operations.
4. Capability Lists
Each domain maintains a list of objects and access rights it possesses.
5. Authentication and Authorization
 Authentication verifies user identity
 Authorization determines allowed actions
Relationship Between Sharing and Protection
 Sharing increases accessibility, protection restricts access
 Excessive sharing without protection leads to security risks
 Over-protection reduces resource utilization
 OS balances both to ensure efficiency and safety

3.18 FILE SYSTEM STRUCTURE

 Disk provides the bulk of secondary storage on which a file system is maintained. They
have 2 characteristics that make them a convenient medium for storing multiple files.

 A disk can be rewritten in place. It is possible to read a block from the disk, modify the
block, and write it back into same place.

 A disk can access directly any block of information it contains.

I/O Control: consists of device drivers and interrupt handlers to transfer information between the
main memory and the disk system. The device driver writes specific bit patterns to special locations
in the I/O controllers memory to tell the controller which device location to act on and what actions
to take.

The Basic File System needs only to issue commands to the appropriate device driver to read and
write physical blocks on the disk. Each physical block is identified by its numeric disk address (Eg.
Drive 1, cylinder 73, track2, sector 10).
 Fig 3.18.1 Structure of File System

The File Organization Module knows about files and their logical blocks and physical blocks. By
knowing the type of file allocation used and the location of the file, file organization module can
translate logical block address to physical addresses for the basic file system.

The Logical File System manages all file system structure except the actual data (contents of
file). It maintains file structure via file control blocks. A file control block (inode in Unix file
systems) contains information about the file, ownership, permissions, location of the file
contents.

3.19 DIRECTORY IMPLEMENTATION

Linear List

In this algorithm, all the files in a directory are maintained as singly lined list. Each file contains
the pointers to the data blocks which are assigned to it and the next file in the directory.

Characteristics

When a new file is created, then the entire list is checked whether the new file name is matching
to a existing file name or not. In case, it doesn't exist, the file can be created at the beginning or at
the end. Therefore, searching for a unique name is a big concern because traversing the whole
list takes time.
The list needs to be traversed in case of every operation (creation, deletion, updating, etc) on the
files therefore the systems become inefficient.

Fig.3.19.1 Linear List

Hash Table

 To overcome the drawbacks of singly linked list implementation of directories, there is an

alternative approach that is hash table. This approach suggests to use hash table along
with the linked lists.

 A key-value pair for each file in the directory gets generated and stored in the hash table.
The key can be determined by applying the hash function on the file name while the key
points to the corresponding file stored in the directory.

 Now, searching becomes efficient due to the fact that now, entire list will not be searched
on every operating. Only hash table entries are checked using the key and if an entry
found then the corresponding file will be fetched using the value.

Fig.3.19.2 Hash Table

3.20 ALLOCATION METHODS
 An allocation method refers to how disk blocks are allocated for files:

 Contiguous allocation each file occupies set of contiguous blocks o Best performance
in most cases

 Simple only starting location (block #) and length (number of blocks) are required, problems
include finding space for file, knowing file size, external fragmentation, need for
compaction off-line (downtime) or on-line.

Fig.3.20.1 Contiguous Allocation Method

Linked allocation each file a linked list of blocks, File ends at nil pointer
 No external fragmentation
 Each block contains pointer to next block
 No compaction, external fragmentation
 Free space management system called when new block needed
 Improve efficiency by clustering blocks into groups but increases internal fragmentation
 Reliability can be a problem
 Locating a block can take many I/Os and disk seeks FAT (File Allocation Table) variation
 Beginning of volume has table, indexed by block number
 Much like a linked list, but faster on disk and cacheable
 Fig.3.20.2 Allocation of Linked List
Indexed Allocation Instead of maintaining a file allocation table of all the disk pointers, Indexed
allocation scheme stores all the disk pointers in one of the blocks called as indexed block.
Indexed block doesn't hold the file data, but it holds the pointers to all the disk blocks allocated to
that particular file. Directory entry will only contain the index block address.

Fig 3.20.3 Indexed allocation

4.15 FREE-SPACE MANAGEMENT

 File system maintains free-space list to track available blocks/clusters Linked list (free
list)
 Cannot get contiguous space easily
 No waste of space
 No need to traverse the entire list
Bitmap or Bit vector

A Bitmap or Bit Vector is series or collection of bits where each bit corresponds to a disk block.
The bit can take two values: 0 and 1: 0 indicates that the block is allocated and 1 indicates a
free block. The given instance of disk blocks on the disk in Figure 1 (where green blocks are
allocated) can be represented by a bitmap of 16 bits as: 0000111000000110.

Advantages
 Simple to understand.
 Finding the first free block is efficient. It requires scanning the words (a group of 8 bits) in
a bitmap for a non-zero word. (A 0-valued word has all bits 0). The first free block is then
found by scanning for the first 1 bit in the non-zero word.

Fig.4.15.1 Free-Space Management

Fig.4.15.2 Linked Free Space List on Disk

In this approach, the free disk blocks are linked together i.e. a free block contains a pointer to the
next free block. The block number of the very first disk block is stored at a separate location on
disk and is also cached in memory.

Grouping

 Modify linked list to store address of next n-1 free blocks in first free block, plus a pointer
to next block that contains free-block-pointers (like this one).

 An advantage of this approach is that the addresses of a group of free disk block scan be
found easily

Counting

 Because space is frequently contiguously used and freed, with contiguous- allocation
allocation, extents, or clustering.

 Keep address of first free block and count of following free blocks. Free space list then
has entries containing addresses and counts.
 PART- A
1. Which of the following best describes the concept of swapping in the context of
memory management?
A) Moving data between disk and main memory to free up space.
B) Allocating more memory to a process when needed.
C) Reducing the size of the memory available to processes.
D) Compressing data stored in memory.
2. In contiguous memory allocation, what is a primary disadvantage?
A) External fragmentation
B) Internal fragmentation
C) Increased access time
D) Inefficient page table management
3. What is the main purpose of paging in memory management?
A) To reduce the size of the memory footprint of processes.
B) To allow non-contiguous allocation of memory.
C) To increase the access speed to memory.
D) To simplify the swapping mechanism.
4. Which of the following terms refers to the fixed-size blocks used in paging?
A) Frames
B) Pages
C) Segments
D) Blocks
5. What information is typically stored in a page table entry?
A) The physical address of the page.
B) The size of the page.
C) The location of the page on disk.
D) The permissions associated with the page.
6. In segmentation, how is memory divided?
A) Into fixed-size blocks called pages.
B) Into variable-sized segments based on logical divisions of a program.
C) Into equal-sized partitions.
D) Into clusters of contiguous memory blocks.
7. What advantage does segmentation with paging offer over pure segmentation?
A) It eliminates all types of fragmentation.
 B) It provides a way to manage both logical divisions and non-contiguous memory
allocation.
C) It speeds up access to memory by using larger segments.
D) It simplifies the management of the page table.
8. What is the main benefit of virtual memory?
A) It allows processes to use more memory than is physically available.
B) It speeds up the CPU's execution time.
C) It eliminates the need for swapping.
D) It reduces the complexity of memory management.
9. In demand paging, when does a page get loaded into memory?
A) When the process is initially loaded into memory.
B) When the page is referenced for the first time.
C) When the process starts execution.
D) When the page table is created.
10. What is the main advantage of the Copy on Write (CoW) technique?
A) It allows efficient sharing of pages between processes.
B) It speeds up the swapping process.
C) It reduces the need for paging.
D) It eliminates internal fragmentation.
11. Which algorithm is commonly used for page replacement?
A) Least Recently Used (LRU)
B) First In, First Out (FIFO)
C) Optimal Page Replacement
D) All of the above
12. How are frames allocated to processes in a system that uses paging?
A) Frames are allocated in contiguous blocks.
B) Frames are allocated based on the priority of the process.
C) Frames are allocated dynamically as needed by the process.
D) Frames are allocated based on the size of the process.
13. What is thrashing in the context of virtual memory?
A) The condition where processes are unable to execute due to excessive paging.
B) The condition where the system has excessive free memory.
C) The condition where the CPU is overutilized.
D) The condition where processes are blocked due to insufficient page tables.
14. Which of the following is true about semaphores?
 A)They can be used for both signaling and mutual exclusion.
B) They can be used only for signaling.
C) They cannot be shared among processes.
D) None of the above.

15. Which of the following is NOT a condition for deadlock?

A)Mutual exclusion.
B) Hold and wait.
C) Preemption.
D) Circular wait.

PART – B
1. Define logical address space.
2. Define physical address space.
3. What is paging?
4. Define Demand paging.
5. What is page fault?.
6. What is virtual memory?.
7. Define Segmentation.
8. What is page hit?
9. Why page should be replaced in the memory?
10. List out the algorithms for page replacement.
11. Define thrashing.
12. What is meant by swap space and why it is used for?
13. What are the essential content(s) in each entry of a page table?
14. Define dynamic loading.
15. Define compaction.
16. What is fragmentation?
17. Draw the structure of page table.
18. Difference between internel and Externel fragmentation?
19. Compare Swapping and Overlays.
20. Define swapping.(April/May 2023)
21. What is the need for segmentation? (April/May 2023).
22. Define the concept of Fragmentation. (Nov/Dec 2024)
 PART-C&D
1. Explain Swapping and Paging.
2. Explain Contiguous Memory Allocation.
3. Describe Structure of Paging Table.
4. Explain the following Page Replacement Algorithm in detail.
[Link] . II. FIFO
5. Explain about Logical & Physical Addressing
6. Describe Allocation of Frames mechanism
7. Explain the concept of Segmentation.
8. Consider a system with three page frames for user level applications, and consider the
following reference string:5 6 9 3 5 6 3 6 9 4 3 9 6 4 9 How many page faults will there
be ,when one considers FIFO,LRU, and the optimal page replacement algorithms?
9. Draw the architecture diagram of paging and explain it in all aspects and explain how
segmentation is adopted in paging.
10. Identify and explain the uses of implementing Contiguous Memory Allocation in Operating
systems.(April/May 2023)
11. Apply Least Recently used Page Replacement and find the number of page faults for the
below string 3, 1, 2, 1, 6, 5, 1, 3 with 3-page frames.(April/May 2023)
12. Consider the following set of processes with the length of CPU burst time given in ms.

13. Outline the Gantt Chart for execution of these processes using FCFS, SJF (Non preemptive
and Preemptive), Preemptive Priority, Round Robin with a time slice of 2ms. Find the average
waiting time and turnaround time for each of the method.(April/May 2023)
(i) Identify the concept of Segmentation memory management
scheme.
(ii) Determine the significance of Contiguous Memory Allocation.
(Nov/Dec 2024)
14. Organize the different components in the architecture of demand paging. (Nov/Dec 2024)