Notes: S1-Introduction: Operating System and Functions

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define operating system.(Unistructural) Open LMS (https://gulms.galgotiasuniversity.org/)
2. Describe the main functions of an operating Go to course Operating System(R1UC403B)
system. (Multistructural) Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

OS Definition
Operating system is a system software that acts as an intermediary between the user of a computer and computer hardware. It is
considered as the brain of the computer. It controls the internal activities of the computer hardware and provides the user interface.
This interface enables a user to utilize the hardware resources very efficiently. It is the first program that gets loaded into the
computer memory through the process called “booting”.
Some popular operating System are windows9x(95,98), Linux, Unix, Windows xp. vista etc.

A computer system has many resources (hardware and software), which may be required to complete a task. The commonly required
resources are input/output devices, memory, file storage space, CPU, etc. The operating system acts as a manager of the above
resources and allocates them to specific programs and users, whenever necessary to perform a particular task. Therefore the
operating system is the resource manager i.e. it can manage the resource of a computer system internally.
In simple terms, an operating system is an interface between the computer user and the machine.
Below we have an abstract view of the components of the computer system.

In the above picture:

The Computer Hardware contains a central processing unit(CPU), the memory, and the input/output (I/O) devices and it provides
the basic computing resources for the system. The Application programs like spreadsheets, Web browsers, word processors, etc. are
used to define the ways in which these resources are used to solve the computing problems of the users. And the System program
mainly consists of compilers, loaders, editors, OS, etc. The Operating System is mainly used to control the hardware and coordinate
its use among the various application programs for the different users.

Two Views of Operating System

1. User's View
2. System View

Operating System: User View

The user view of the computer refers to the interface being used. Such systems are designed for one user to monopolize its resources,
to maximize the work that the user is performing. In these cases, the operating system is designed mostly for ease of use, with some
attention paid to performance, and none paid to resource utilization.

Operating System: System View

The operating system can be viewed as a resource allocator also. A computer system consists of many resources like - hardware and
software - that must be managed efficiently. The operating system acts as the manager of the resources, decides between conflicting
requests, controls the execution of programs, etc.
Functions of Operating System:
Operating System performs a number of functions for the computer system that are follows:

1.It acts as a Command Interpreter:

Generally the CPU cannot understand the commands given by user. It is the function of operating System to translate this command
(human understandable) into machine understandable instructions that the system (CPU) can understand. After the execution of
instructions by CPU, it retranslates the output back into a human understandable language. To execute the user jobs, the Operating
System interacts with the computer hardware.

2. It acts as the Resource Manager:

An Operating System acts as a resource manager in two ways
Time multiplexing
In time multiplexing the different resources (hardware or software) can be shared among different users for a optimal or fixed time
slot. e.g. the Operating System allocates a resource such as CPU to program A for a fixed time slot. When the time slot of process
A is over, the CPU is allocated to another program B. If program A needs more CPU attention, then the CPU again allocated to
program A after the time slice period allocated to program B is over.
Space multiplexing
In space multiplexing, different resources are shared at the same time among different programs .e.g. sharing of hard disk and main
memory by different users at the same time.

3.Memory Management:
It keeps track of the resources (memory),what part of memory is in use and by whom, which part of the memory is not in use.

4.Process Management:
A process(task) is an instance of a program in execution. A program is just a passive entity, but a process is an active entity. To
accomplish its task ,a process needs certain resources like CPU time, memory, files and I/O devices. These resources are allocated
to process either at the time of creation or when it is executing. The operating system is responsible for functions related to process
management.

5.Peripheral or I/O device Management:

Keep track of resources (device, channels, control units) attached to the system. Communication between these devices and CPU is
observed by operating system. An operating system will have device drivers to facilitate I/O functions involving device like
keyboard, mouse, monitor, disk, FDD, CD-ROM, printer etc. Allocation and De allocation of resources to initiate I/O operation.

6.File Management:
A file is a collection of related information or record defined by the user. The operating system is responsible for various activities
of file management like Creation and deletion of files ,Creation and deletion of directories Manipulation of files and directories.

7.Secondary storage Management:

It is a larger memory used to store huge amount of data. Its capacity is much larger than primary memory . The operating system is
responsible for handling various activities like Free space management ,Storage allocation (allocation of storage space when new
files have to be written), Disk scheduling (scheduling the request for memory access).

8.Protection/Security Management:
If a computer system has a multiple processor, then the various processes must be protected of one another’s activities. Protection
refers to mechanism for controlling user access of programs or processes or user to resources defined by the computer system.

9.Error detection and Recovery:

Error may occur during execution like divide by zero by a process, memory access violation, deadlock, I/O device error or a
connection failure. The operating system should detect such errors and handles them.
 Notes: S2-Operating System Services
[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/, https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. List the main services provided by an Open LMS (https://gulms.galgotiasuniversity.org/)
operating system.(Unistructural) Go to course Operating System(R1UC403B)
2. Describe the purpose of each OS service. Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
Click on “Session-wise Pre & Post Class Assessments”
(Multistructural)
 Attempt Assessment quizzes.

The terms Operating System (OS) functions and OS services are often used interchangeably, but they refer to slightly different
aspects of an operating system. Here's a clear differentiation:

OS Services
OS services refer to the specific functionalities or tools provided by the operating system to users and applications. These services
are built on top of the core OS functions and are designed to make the system more user-friendly and efficient. Like-
 Program Execution: Loads and runs programs. Example: Running a web browser or a word processor.
 I/O Operations: Facilitates input and output operations for devices. Example: Reading from a file or printing a document.
 File System Manipulation: Allows users to create, delete, and modify files. Example: Saving a document or renaming a file.
 Communication: Enables communication between processes or systems. Example: Sending data over a network or using inter-
process communication (IPC).
 Error Detection and Handling: Detects and resolves errors in hardware or software. Example: Displaying an error message
when a program crashes.
 User Interface: Provides interfaces (CLI, GUI, or touch-based) for user interaction. Example: Using a graphical interface to
open apps or typing commands in a terminal.
 Resource Allocation: Allocates resources like CPU, memory, and devices to processes. Example: Assigning more CPU power
to a high-priority task.
 Protection and Security: Ensures data and system integrity. Example: Requiring a password to log in or encrypting files.

Analogy:
OS Functions: Like the engine of a car (internal operations that keep the car running).
OS Services: Like the steering wheel, pedals, and dashboard (tools provided to the driver to control and interact with the car).
OS Service Errors or Abnormal Behaviours
1. Infinite Loop: Program gets stuck in an endless loop.
2. Crash: Program terminates unexpectedly.
1. Program Execution 3. Memory Leak: Program fails to release memory.
4. Deadlock: Program waits indefinitely for resources.
5. Incorrect Output: Program produces wrong results due to logic errors.
1. Device Not Found: I/O device is not detected.
2. I/O Errors: Errors during read/write operations.
2. I/O Operations 3. Buffer Overflow: Data exceeds allocated buffer size.
4. Device Busy: Device is already in use.
5. Data Corruption: Data is altered or lost during I/O operations.
1. File Corruption: File data becomes unreadable.
2. Permission Denied: Unauthorized access to files.
3. File System Manipulation 3. Disk Full: No storage space available.
4. File Not Found: Attempt to access a non-existent file.
5. Fragmentation: Files stored in non-contiguous blocks, reducing performance.
1. Network Congestion: High traffic slows down communication.
2. Packet Loss: Data packets are lost during transmission.
4. Communication 3. Connection Timeout: Network connection fails due to delays.
4. DNS Failure: Domain name resolution fails.
5. Unauthorized Access: Intruder gains access to the network.
1. Undetected Errors: Errors go unnoticed by the OS.
2. Incorrect Error Handling: Errors are handled improperly.
5. Error Detection and Handling 3. Silent Failures: Errors occur without notification.
4. Recovery Failure: System fails to recover from an error.
5. False Positives: Normal behavior is incorrectly flagged as an error.
1. UI Freeze: Interface becomes unresponsive.
2. Display Glitches: Visual artifacts or incorrect rendering.
6. User Interface 3. Input Lag: Delayed response to user input.
4. Crash: Application or system crashes, closing the UI.
5. Accessibility Issues: UI not usable by people with disabilities.
1. Resource Starvation: Process denied necessary resources.
2. Over-Allocation: Too many resources allocated to a single process.
7. Resource Allocation 3. Under-Allocation: Insufficient resources allocated, causing poor performance.
4. Deadlock: Resources held by processes waiting for each other.
5. Resource Leak: Resources not released after use.
1. Unauthorized Access: Unauthorized user accesses system resources.
2. Virus/Malware Infection: Malicious software compromises system security.
8. Protection and Security 3. Data Breach: Sensitive data is accessed or stolen.
4. Privilege Escalation: User gains higher access rights illegally.
5. Firewall Failure: Unauthorized network access due to firewall misconfiguration.
1. Incorrect Logging: System fails to log job activities accurately.
2. Data Loss: Job accounting data is lost due to system errors.
9. Job Accounting 3. Unauthorized Access: Unauthorized user accesses job accounting data.
4. Resource Overuse: System fails to track resource usage accurately.
5. Incomplete Records: Job accounting records are missing or incomplete.
OS
OS Services Real-Life Examples
Functions
Resource Program Execution Running a web browser or a game on your computer.
Management Resource Allocation Allocating more CPU power to a video editing software for faster rendering.
Program Execution Switching between multiple apps on your smartphone
Process
Management Communication Using inter-process communication (IPC) for apps to share data (e.g., copying text
from one app to another).
Your computer slowing down when too many apps are open due to insufficient
Memory Resource Allocation
RAM.
Management
Program Execution Loading a game level into memory for faster access.
Saving a Word document to the "Documents" folder or organizing photos into
File System File System Manipulation folders.
Management
I/O Operations Copying files from a USB drive to your computer.
Device I/O Operations Printing a document from your laptop to a wireless printer.
Management Resource Allocation Allocating printer resources to one user at a time in a shared office environment.
Security and Protection and Security Logging into your computer with a password or fingerprint.
Protection Error Detection and Handling An antivirus blocking unauthorized access or malware.
Your computer showing a "Blue Screen of Death" (BSOD) and restarting to
Error Detection and Handling
Error recover.
Handling A program crashing and the OS displaying an error message like "This program has
Program Execution
stopped working."
Communication Browsing the internet, streaming Netflix, or sending an email.
Networking
Resource Allocation A server distributing bandwidth to multiple users accessing a website.
User User Interface Using a touchscreen on your smartphone or typing commands in the terminal (CLI).
Interface Program Execution Opening apps using a graphical user interface (GUI).
 Notes : S3-Classification of Operating Systems

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. List and describe the characteristics of each Open LMS (https://gulms.galgotiasuniversity.org/)
type of operating system (Multistructural). Go to course Operating System(R1UC403B)
2. Compare and contrast different types of operating Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
systems (Relational). Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

1. Batch Operating System:

The users of a batch operating system do not interact with the computer directly. Each user prepares his job on an off-line device
like punch cards and submits it to the computer operator. To speed up processing, jobs with similar needs are batched together and
run as a group. The programmers leave their programs with the operator and the operator then sorts the programs with similar
requirements into batches.

Advantages of Batch Operating System:

 Processors of the batch systems know how long the job would be when it is in queue.
 Multiple users can share the batch systems
 The idle time for batch system is very less
 It is easy to manage large work repeatedly in batch systems
Disadvantages of Batch Operating System:
 The computer operators should be well known with batch systems
 Batch systems are hard to debug
 It is sometime costly
 The other jobs will have to wait for an unknown time if any job fails Examples of Batch based

Operating System: Payroll System, Bank Statements etc.

2. Multiprogramming Systems
Sharing the processor, when two or more programs reside in memory at the same time, is referred as multiprogramming.
Multiprogramming assumes a single shared processor. Multiprogramming increases CPU utilization by organizing jobs so that the
CPU always has one to execute. The following figure shows the memory layout for a multiprogramming system.

An OS does the following activities related to multiprogramming.

 The operating system keeps several jobs in memory at a time.
 This set of jobs is a subset of the jobs kept in the job pool.
 The operating system picks and begins to execute one of the jobs in the memory.
 Multiprogramming operating systems monitor the state of all active programs and system resources using memory
management programs to ensure that the CPU is never idle, unless there are no jobs to process.
Advantages
 High and efficient CPU utilization.
 User feels that many programs are allotted CPU almost simultaneously.
Disadvantages
 CPU scheduling is required.
 To accommodate many jobs in memory, memory management is required.

3. Multitasking Operating System

A Multitasking Operating System is an OS that allows multiple processes to run simultaneously by efficiently managing CPU time
and system resources. It achieves this by quickly switching between tasks, giving the illusion that they are executing at the same
time.
Advantages of Multitasking OS
 Efficient CPU Utilization – Maximizes CPU usage by ensuring that idle time is minimized.
 Improved Productivity – Users can run multiple applications (e.g., browsing while downloading files).
 Better System Responsiveness – Quick switching between tasks enhances user experience.
 Resource Sharing – Multiple processes can share system resources efficiently.
 Parallel Execution – Some multitasking OSes (like those on multi-core processors) support true parallel execution.
Disadvantages of Multitasking OS
 Increased Resource Usage – Requires more RAM and processing power to handle multiple tasks.
 Complex Process Management – Needs a sophisticated scheduling algorithm, increasing system complexity.
 Potential System Slowdown – Running too many tasks can slow down performance.
 Higher Risk of Crashes – If one process malfunctions, it may affect others.
 Security Risks – Multiple processes running simultaneously increase vulnerability to attacks

4. Time-Sharing Operating Systems :

Time-sharing is a technique which enables many people, located at various terminals, to use a particular computer system at the
same time. Time-sharing or multitasking is a logical extension of multiprogramming. Processor's time which is shared among
multiple users simultaneously is termed as time-sharing.
Multiple jobs are executed by the CPU by switching between them, but the switches occur so frequently. Thus, the user can receive
an immediate response. For example, in a transaction processing, the processor executes each user program in a short burst or
quantum of computation. That is, if n users are present, then each user can get a time quantum. When the user submits the command,
the response time is in few seconds at most.
The operating system uses CPU scheduling and multiprogramming to provide each user with a small portion of a time. Computer
systems that were designed primarily as batch systems have been modified to time-sharing systems.

Advantages of Time-Sharing OS:

 Each task gets an equal opportunity
 CPU idle time can be reduced

Disadvantages of Time-Sharing OS:

 One must have to take care of security and integrity of user programs and data
 Data communication problem

Examples of Time-Sharing OSs are: Multics, Unix etc.

5. Distributed Operating System:

Distributed systems use multiple central processors to serve multiple real-time applications and multiple users. Data processing
jobs are distributed among the processors accordingly.
The processors communicate with one another through various communication lines (such as high- speed buses or telephone
lines). These are referred as loosely coupled systems or distributed systems. Processors in a distributed system may vary in size
and function. These processors are referred as sites, nodes, computers, and so on.
Advantages of Distributed Operating System:
 Failure of one will not affect the other network communication, as all systems are independent from each other
 Since resources are being shared, computation is highly fast and durable
 Load on host computer reduces
 These systems are easily scalable as many systems can be easily added to the network
 Delay in data processing reduces

Disadvantages of Distributed Operating System:

 Failure of the main network will stop the entire communication
 To establish distributed systems the language which are used are not well defined yet
 These types of systems are not readily available as they are very expensive. Not only that the underlying software is
highly complex and not understood well yet

Examples of Distributed Operating System are- LOCUS etc.

6. Real-Time Operating System:

A real-time system is defined as a data processing system in which the time interval required to process and respond to inputs is so
small that it controls the environment. The time taken by the system to respond to an input and display of required updated
information is termed as the response time. So in this method, the response time is very less as compared to online processing.
Real-time systems are used when there are rigid time requirements on the operation of a processor or the flow of data and real-time
systems can be used as a control device in a dedicated application. A real-time operating system must have well-defined, fixed time

constraints, otherwise the system will fail. For example, scientific experiments, medical image systems, industrial control systems,
weapon systems, robots, air traffic control systems, etc. There are two types of real-time operating systems.

Hard real-time systems

Hard real-time systems guarantee that critical tasks complete on time. In hard real-time systems, secondary storage is limited or
missing and the data is stored in ROM. In these systems, virtual memory is almost never found.

Soft real-time systems

Soft real-time systems are less restrictive. A critical real-time task gets priority over other tasks and retains the priority until it
completes. Soft real-time systems have limited utility than hard real-time systems. For example, multimedia, virtual reality,
Advanced Scientific Projects likes undersea exploration and planetary rovers, etc.

Advantages of RTOS:
 Maximum Consumption: Maximum utilization of devices and system, thus more output from all the resources
 Task Shifting: Time assigned for shifting tasks in these systems are very less. For example in older systems it takes
about 10 micro seconds in shifting one task to another and in latest systems it takes 3 micro seconds.
 Focus on Application: Focus on running applications and less importance to applications which are in queue.
 Real time operating system in embedded system: Since size of programs is small, RTOS can also be used in embedded
systems like in transport and others.
  Error Free: These types of systems are error free.
 Memory Allocation: Memory allocation is best managed in these types of systems.

Disadvantages of RTOS:
 Limited Tasks: Very few tasks run at the same time and their concentration is very less on few applications to avoid
errors.
 Use heavy system resources: Sometimes the system resources are not so good and they are expensive as well.
 Complex Algorithms: The algorithms are very complex and difficult for the designer to write on.
 Device driver and interrupt signals: It needs specific device drivers and interrupts signals to response earliest to
interrupts.
 Thread Priority: It is not good to set thread priority as these systems are very less prone to switching tasks.

Examples of Real-Time Operating Systems are: Scientific experiments, medical imaging systems, industrial control systems,
weapon systems, robots, air traffic control systems, etc.

7. Network operating System

A Network Operating System runs on a server and provides the server the capability to manage data, users, groups, security,
applications, and other networking functions. The primary purpose of the network operating system is to allow shared file and
printer access among multiple computers in a network, typically a local area network (LAN), a private network or to other networks.
Examples of network operating systems include Microsoft Windows Server 2003, Microsoft Windows Server 2008, UNIX, Linux,
Mac OS X, Novell NetWare, and BSD.

Advantages of Network operating systems:

 Centralized servers are highly stable.
 Security is server managed.
 Upgrades to new technologies and hardware can be easily integrated into the system.
 Remote access to servers is possible from different locations and types of systems.

Disadvantages of network operating systems

 High cost of buying and running a server.
 Dependency on a central location for most operations.
 Regular maintenance and updates are required.

8. Multi-User Operating System

A Multi-User Operating System is an OS that allows multiple users to access and use the computer system simultaneously. It
manages and allocates system resources like CPU, memory, and storage efficiently among users.

Advantages of Multi-User OS
 Resource Sharing – Multiple users can share hardware and software resources efficiently.
 Cost-Effective – Reduces the need for individual computers by allowing multiple users on one system.
 Centralized Data Management – Users can store and access data from a central location, improving collaboration.
 Improved Security – User accounts and permissions help maintain data privacy and restrict unauthorized access.
 Remote Accessibility – Users can access the system from different locations over a network.
Disadvantages of Multi-User OS
 High Cost of Maintenance – Requires advanced hardware and software to support multiple users efficiently.
 Slower Performance – If too many users are active, the system might experience delays.
 Security Risks – A vulnerability in one user’s session could impact the entire system.
 Complex System Management – Requires system administrators to manage users, permissions, and resources.
 Dependence on Network – If the network fails, user access and system functionality can be disrupted.

Examples of Multi-User Operating Systems

 Unix – Used in servers and workstations for multi-user operations.
 Linux (Ubuntu Server, CentOS, Red Hat Enterprise Linux) – Common in enterprise environments.
 Windows Server – Supports multiple remote users through Remote Desktop Services.
 Mainframe OS (IBM z/OS) – Used for large-scale computing in banks and organizations.

**Parallel Processing:
Parallel processing requires multiple processors and all the processor works simultaneously in the system. Here, the task is divided
into subparts and these subparts are then distributed among the available processors in the system. Parallel processing completes
the job on the shortest possible time. All the processors in the parallel processing environment should run on the same operating
system. All processors here are tightly coupled and are packed in one casing. All the processors in the system share the common
secondary storage like the hard disk.
The user need not to be aware of the inner architecture of the machine. He should feel that he is dealing with the single processor
only and his interaction with the system would be the same as in a single processor.

Advantages
1. It saves time and money as many resources working together will reduce the time and cut potential costs.
2. It can be impractical to solve larger problems on Serial Computing.
3. It can take advantage of non-local resources when the local resources are finite.
4. Serial Computing ‘wastes’ the potential computing power, thus Parallel Computing makes better work of the hardware.
Disadvantages
1. It addresses such as communication and synchronization between multiple sub-tasks and processes which is difficult to achieve.
2. The algorithms must be managed in such a way that they can be handled in a parallel mechanism.
3. The algorithms or programs must have low coupling and high cohesion. But it’s difficult to create such programs.
4. More technically skilled and expert programmers can code a parallelism-based program well.

Operating systems (OS) can be classified based on various criteria, such as their architecture, purpose, number of users, task
handling, and interactivity. Below is a detailed classification of operating systems:

1. Based on Architecture

Type Description Examples

Monolithic OS The entire OS works in kernel space as a single program. All components are tightly coupled. UNIX, MS-DOS
Microkernel Only essential services (e.g., memory management, process scheduling) run in kernel space.
Mach, QNX
OS Other services run in user space.
Combines features of monolithic and microkernel architectures. Some services run in kernel
Hybrid OS Windows NT
space, while others run in user space.
Provides minimal abstraction over hardware, allowing applications to manage resources
Exokernel OS ExOS, Nemesis
directly.

2. Based on Purpose

Type Description Examples

General-Purpose OS Designed to handle a wide range of tasks and applications for general use. Windows
Designed for specific tasks or devices, such as embedded systems or real-time
Special-Purpose OS Android
applications.
3. Based on Number of Users

Type Description Examples

Single-User OS Supports only one user at a time. Windows (Home editions), MS-DOS
Multi-User OS Supports multiple users simultaneously. UNIX, Linux, Windows Server

4. Based on Task Handling

Type Description Examples

Single-Tasking OS Allows only one task (process) to run at a time. MS-DOS
Multi-Tasking OS Allows multiple tasks to run concurrently by switching between them. Windows, macOS, Linux

5. Based on Interactivity

Type Description Examples

Interactive OS Allows users to interact directly with the system in real-time. Windows
Batch Processing OS Processes jobs in batches without user interaction. IBM OS/360
Time-Sharing OS Allows multiple users to share system resources by dividing CPU time among them. UNIX, Linux

6. Based on Real-Time Processing

Type Description Examples

Real-Time OS (RTOS) Designed for real-time applications where response time is critical. VxWorks, FreeRTOS
Hard Real-Time OS Guarantees strict deadlines for task completion. QNX, RTLinux
Soft Real-Time OS Prioritizes critical tasks but does not guarantee strict deadlines. Windows CE, LynxOS

7. Based on Network Handling

Type Description Examples

Manages network resources and provides services like file sharing, printing, and Windows Server, Novell
Network OS
security. NetWare
Distributed Manages a group of independent computers as a single system, providing
Amoeba, LOCUS
OS transparency and scalability.

8. Based on Device Type

Type Description Examples

Desktop OS Designed for personal computers and workstations. Windows, macOS, Linux
Mobile OS Designed for mobile devices like smartphones and tablets. Android, iOS
Embedded OS Designed for embedded systems like IoT devices, routers, and smart appliances. FreeRTOS, Embedded Linux
9. Based on Open Source

Type Description Examples

Open-Source OS Source code is publicly available and can be modified and distributed. Linux, FreeBSD
Proprietary OS Source code is not available, and the OS is owned by a company. Windows, macOS

10. Based on Boot Process

Type Description Examples

Older versions of Windows,
BIOS-Based OS Uses the Basic Input/Output System (BIOS) for booting.
Linux
Uses the Unified Extensible Firmware Interface (UEFI) for booting, offering Modern Windows, Linux
UEFI-Based OS
faster and more secure booting. distributions
Type of OS Scenario 1 Scenario 2
Bank processes transactions at the end Weather forecasting system processes
Batch OS
of the day. 24-hour data in one batch.
University server allows multiple Online coding platform lets users
Time-Sharing OS
students to run programs. compile code simultaneously.
Global company collaborates on a Google Drive synchronizes files across
Distributed OS
project using multiple systems. devices in real-time.
Office employees access shared files School computer lab provides shared
Network OS
and printers. network access for students.
Real-Time OS Car’s ABS adjusts brake pressure in Flight control system adjusts altitude
(RTOS) real-time. and direction in real-time.
Smart thermostat controls home Fitness tracker monitors heart rate and
Embedded OS
temperature. steps.
User switches between apps on a Mobile gamer plays online while
Mobile OS
smartphone. receiving notifications.
Computer runs browser, word
Multiprogramming Developer writes code while running a
processor, and music player
OS compiler and debugger.
simultaneously.
Server uses multiple CPUs for video Data center processes large-scale
Multiprocessing OS
rendering. analytics tasks.
Personal computer allows one user at a Graphic designer edits high-resolution
Single-User OS
time. images without sharing resources.
 Notes : S4-Operating System Structure

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Explain the structure of an operating system. Open LMS (https://gulms.galgotiasuniversity.org/)
2. Describe the functions of each layer in the OS Go to course Operating System(R1UC403B)
layered structure. Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Operating System Layers:

The structure of any Operating System comprises of 4 layers.
 Hardware
 Kernel
 System call interface(shell)
 Application programs

Hardware Layer:
o This is the lowest layer and interacts directly with the physical hardware (e.g., CPU, memory, storage devices).
o It handles hardware-specific operations and provides an abstraction to the upper layers.
o Example: Managing memory allocation or handling interrupts.
Kernel Layer:
o The kernel is the core of the operating system and resides above the hardware layer.
o It manages system resources like memory, CPU, and I/O devices.
o Example: Scheduling processes, managing memory, and handling device communication.
System Call Layer:
o This layer provides an interface between the kernel and user applications.
o It allows applications to request services from the kernel, such as file operations or process management.
o Example: A program requesting to read a file from the disk.
Application Layer:
o This is the topmost layer and is closest to the user.
o It includes user applications like web browsers, word processors, and games.
o Example: Running a web browser or editing a document.

Types of OS structure:

1. Simple Structure
▪ MS-DOS is an operating system created for personal computers. It was developed by Microsoft. It is a classic example of
an operating system with a layered structure.
▪ MS-DOS operating system is split into various layers and each of the layers have different functionalities.
▪ Layering provides a distinct advantage in the MS-DOS operating system because all the layers can be defined separately
and interact with each other as required.
▪ Also, it is easier to create, maintain and update the system if it is done in the form of layers. Change in one layer
specification does not affect the rest of the layers.
▪ However, the layers in MS-DOS are not that sharply defined and the layer specifications often bleed into each other.
2. Monolithic systems
 Entire operating system is working in kernel space.
 A set of primitives or system calls implement all operating system services such as process management, concurrency,
and memory management. Device drivers can be added to the kernel as modules.
 User services and kernel services are implemented under same address space. As both services are implemented
under same address space, this makes operating system execution faster.
 If any service fails the entire system crashes, and it is one of the drawbacks of this kernel. The entire operating system
needs modification if user adds a new service.
 Acts as a virtual machine which controls all hardware parts
 Examples: Linux, Unix like kernels, BSD, OS/360

1. Layered systems
 A layered system consists of a series of layers, each of which depends only on the correct operation of the
layer immediately beneath it.
 The lowest layer represents the hardware interface, and the highest layer the application interface.
 All the layers can be defined separately and interact with each other as required. Also, it is easier to create,
maintain and update the system if it is done in the form of layers. Change in one layer specification does not
affect the rest of the layers.
 A key problem in a layered system is deciding on the ordering of the layers. (This is critical because of the
requirement that each layer can ultimately only use services provided by layers below it - so the ordering
cannot have any cycles.)
 Examples OS/2, window NT

Advantages of a Layered Structure

 Modularity: Each layer can be developed and maintained independently, making the system easier to manage.
 Simplified Design: The layered structure simplifies the design of the OS by breaking it into smaller, manageable parts.
 Ease of Debugging: Since each layer has a specific function, it is easier to identify and fix issues.
 Portability: The layered structure makes it easier to port the OS to different hardware platforms.
Disadvantages of a Layered Structure
 Performance Overhead: Communication between layers can introduce performance overhead, as each layer must pass
data to the next.
 Complexity: While the layered structure simplifies design, it can also add complexity due to the interactions between
layers.
  Rigidity: Changes in one layer may require changes in adjacent layers, making the system less flexible.
Importance of Layered Structure
 The layered structure is a fundamental concept in operating system design.
 It provides a clear separation of concerns, making the OS easier to develop, maintain, and extend.
 Understanding the layered structure helps in designing efficient and scalable operating systems.

2. Microkernel structure
 Kernel is made as small as possible only the most important services are put inside the kernel and rest of the
OS service are present in the system application program.
 The user can easily interact with those not-so important services within the system applications kernel is
solely responsible for the three most important services of operating system namely:
o Inter-Process communication
o Memory management
o CPU scheduling
 Microkernel and system applications can interact with each other by message passing as and when required.
 This is extremely advantageous architecture since burden of kernel is reduced and less crucial services are
accessible to the user and hence security is improved too. It is being highly adopted in the present-day systems.
 MacOSX, Eclipse IDE is a good example of Microkernel Architecture.

3. Modular structure
▪ A modular operating system is built with its various functions broken up into distinct processes, each with its own
interface.
▪ The primary benefit of the modular approach is that each process operates independently, and if one of them fails or
needs an update, it won’t affect any of the other functions.
▪ The main elements of a modular operating system are a kernel and a set of dynamically loadable applications with their
own discrete memory spaces. The kernel is protected from service and application failures.
▪ The Linux kernel is modular, which means it can extend its capabilities through dynamically-loaded kernel modules.
Comparison table for the types of operating system (OS) structures, highlighting their key characteristics, advantages, and
disadvantages:
OS Structure Description Advantages Disadvantages Examples
- Difficult to maintain and
- High performance due to update.
The entire OS runs as a single
Monolithic direct communication - Lack of modularity. UNIX, MS-
program in kernel space. All
OS between components. - Vulnerable to crashes (one DOS
components are tightly coupled.
- Simple design. failure affects the entire
system).
- Modular and easy to
- Slower performance due to
Only essential services (e.g., memory extend.
frequent context switching
Microkernel management, process scheduling) run - More stable (kernel
between user and kernel modes. Mach, QNX
OS in kernel space. Other services run in crashes are less likely).
- Increased complexity in
user space. - Easier to maintain and
design.
debug.
- Balances performance
- More complex than
Combines features of monolithic and and modularity.
monolithic OS.
microkernel architectures. Some - More stable than Windows NT,
Hybrid OS - May still have performance
services run in kernel space, while monolithic OS. macOS
overhead due to user-kernel
others run in user space. - Easier to extend than
mode switching.
monolithic OS.
- Modular and easy to
The OS is divided into layers, where design. - Performance overhead due to
each layer provides services to the - Easier to debug and layer-to-layer communication. THE OS,
Layered OS
layer above and uses services from the maintain. - Rigid structure (changes in MULTICS
layer below. - Clear separation of one layer may affect others).
concerns.
- High performance and
Provides minimal abstraction over flexibility. - Complex to develop and use.
ExOS,
Exokernel OS hardware, allowing applications to - Applications have fine- - Requires applications to
Nemesis
manage resources directly. grained control over handle low-level details.
resources.
- Isolation between OS
instances.
Provides an abstraction of the - Performance overhead due to
- Efficient resource VMware,
Virtual underlying hardware, allowing virtualization.
utilization. VirtualBox,
Machine OS multiple OS instances to run on a - Requires significant hardware
- Supports running multiple Xen
single physical machine. resources.
OS environments
simultaneously.
- Modular and scalable.
- Performance overhead due to
- Easier to maintain and
Divides the OS into client and server communication between clients
Client-Server update.
components, where clients request and servers. Amoeba,
OS - Fault isolation (server
services from servers. - Requires robust networking
crashes do not affect
infrastructure.
clients).
 Notes: S 5- Components of Operating System
[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define and explain the primary components of Open LMS (https://gulms.galgotiasuniversity.org/)
an operating system. Go to course Operating System(R1UC403B)
2. Describe the function of each component and how Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
they interact with each other Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Key components of an operating system (OS) along with their related sub-activities:
OS Component Related Sub-Activities Examples
- Creation/Termination: Opening and closing a web browser.
- Process creation and termination.
- Scheduling: Allocating CPU time to a video editor.
1. Process - Process scheduling.
- IPC: Sharing data between a music player and a speaker driver.
Management - Inter-process communication (IPC).
- Deadlock Handling: Resolving a situation where two processes
- Deadlock handling.
are waiting for each other to release resources.
- Allocation: Assigning memory to a new application.
- Allocation and deallocation of
- Virtual Memory: Using disk space as RAM when physical
memory.
2. Memory memory is full.
- Virtual memory management.
Management - Memory Protection: Preventing a game from accessing system-
- Memory protection.
critical memory.
- Swapping.
- Swapping: Moving a background process to disk to free up RAM.
- File creation, deletion, and renaming. - File Creation: Saving a Word document.
3. File System - Directory management. - Directory Management: Organizing files into folders.
Management - File access control. - Access Control: Setting read-only permissions for a file.
- Disk space allocation. - Disk Allocation: Allocating space for a new file on the hard drive.
- Device driver management. - Driver Management: Installing a printer driver.
4. Device - Input/output operations. - I/O Operations: Typing on a keyboard or printing a document.
Management - Plug and Play. - Plug and Play: Automatically detecting a USB drive.
- Buffering and caching. - Buffering: Temporarily storing data from a network download.
- User authentication. - Authentication: Logging into a computer with a password.
5. Security and - File and resource permissions. - Permissions: Restricting access to a confidential file.
Access Control - Firewall and antivirus management. - Firewall: Blocking unauthorized network access.
- Encryption and decryption. - Encryption: Securing sensitive data with AES encryption.
- Command-Line Interface (CLI)
- CLI: Running commands in Terminal (Linux) or Command
management.
Prompt (Windows).
- Graphical User Interface (GUI)
6. User Interface - GUI: Clicking icons on a desktop.
management.
- Touch Interface: Swiping on a smartphone screen.
- Touch interface management.
- Voice Commands: Using Siri or Google Assistant.
- Voice command processing.
- Network communication management. - Communication: Sending an email over the internet.
- Network device management. - Device Management: Configuring a router.
7. Networking
- Network security. - Security: Using a VPN to encrypt internet traffic.
- Data packet routing. - Routing: Sending data packets between devices on a network.
- Providing an interface for applications
to request OS services.
- Handling system calls for file - File Operations: Opening or saving a file.
8. System Calls operations, process control, and device - Process Control: Starting or stopping a process.
management. - Device Management: Requesting access to a printer.
- Managing communication between
user programs and the OS kernel.
- Managing system resources.
- Resource Management: Allocating CPU time to a process.
- Handling interrupts and exceptions.
- Interrupts: Handling a keyboard input.
9. Kernel - Ensuring system stability and security.
- Stability: Preventing a crash when a program misbehaves.
- Managing communication between
- Communication: Sending data from an application to a printer.
hardware and software.

How Components Work Together

When a user runs a program, the Process Manager creates a process and allocates CPU time. The Memory Manager allocates
memory to the process.  The File System accesses necessary files from storage. The Device Manager handles input/output
operations.  The Security Manager ensures the process has the necessary permissions. The User Interface allows the user to
interact with the program.
 Notes: S6-Process Concept and Process Generation

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Understanding the concept of system calls Open LMS (https://gulms.galgotiasuniversity.org/)
and process. Go to course Operating System(R1UC403B)
2. Apply fork(), execlp(), wait(), getpid(), getppid() Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
Click on “Session-wise Pre & Post Class Assessments”
system calls for process generation and
 Attempt Assessment quizzes.
management.

Process
A process is a program in execution. It is the basic unit of work in an operating system . Each process has its own address space,
which includes the code, data, and stack. Processes are managed by the operating system, which allocates resources and ensures
that processes do not interfere with each other.

Differences between a Process and a Program:

Aspect Program Process
A set of instructions written in a programming
Definition An instance of a program that is being executed by the CPU.
language to perform a task.
State Static (stored on disk as a file). Dynamic (active and running in memory).
Exists temporarily in memory during execution and terminates
Lifetime Exists permanently on storage until deleted.
afterward.
Resource Does not consume system resources (e.g., CPU, Consumes system resources (e.g., CPU, memory, I/O devices)
Usage memory) until executed. during execution.
Execution Not executed by itself; requires a process to run. Actively executed by the CPU.
Created by a programmer using a text editor or Created by the OS when a program is loaded into memory for
Creation
IDE. execution.
Examples A .exe file on Windows or a .py script on Linux. Running an instance of Microsoft Word or a Python script.

Role of the Operating System in Process Management

The operating system is responsible for Process Scheduling , Resource Allocation , Process Synchronization , Process
Communication

Process Generation :
In Unix-like systems, processes are fundamental to the execution of programs. Below is an explanation of process
creation, execution, and synchronization in Unix-like systems, along with simple C programs to demonstrate these concepts.

Some Keywords related to process generation:

#include <unistd.h>: This header file provides access to POSIX operating system APIs (Application Programming Interfaces).

getpid(): Returns the process ID (PID) of the calling process.

pid_t: A data type defined in <sys/types.h> (included by <unistd.h>). Used to store process IDs (PIDs).

fork(): A system call that creates a new process by duplicating the calling process. Returns:
 0 to the child process.
 Child's PID to the parent process.
 -1 if the fork() fails.
o If fork() returns -1, it means the system call failed (e.g., due to insufficient resources).
o The program prints an error message and returns 1 to indicate failure.

getpid(): A system call that returns the PID of the calling process.
1. Process Creation
In Unix-like systems, processes are created using the fork() system call. The fork() function creates a new process (child process)
by duplicating the calling process (parent process). Both processes continue execution from the point where fork() was called.
Example: Process Creation Using fork()

Explanation:
 The fork() system call creates a child process.
 The child process executes the code inside the if (pid == 0) block.
 The parent process executes the code inside the else if (pid > 0) block.

2. Process Execution
After creating a process, you can use the exec() family of system calls to replace the current process image with a new program.
This is often used in the child process to run a different program.
Example: Process Execution Using execl()

Explanation:
 The child process replaces itself with the ls -l command using execl().
 The parent process continues execution independently.

3. Process Synchronization
Process synchronization ensures that processes coordinate their actions, especially when sharing resources. In Unix-like systems,
the wait() system call is commonly used to synchronize parent and child processes.
Example: Process Synchronization Using wait()
Explanation:
 The parent process waits for the child process to terminate using wait().
 The child process simulates some work using sleep(2) and then exits.
 After the child process terminates, the parent process resumes execution.

4. Combining Process Creation, Execution, and Synchronization

Here’s an example that combines all three concepts:

Explanation:
 The child process runs the ls -l command using execl().
 The parent process waits for the child to finish using wait().
 After the child process terminates, the parent process resumes execution.
System call
A system call is a mechanism used by programs to request services from the operating system's kernel. It acts as an interface
between user-level applications and the operating system, allowing programs to perform tasks that require privileged access to
hardware or system resources, such as file operations, process control, or network communication.

System Call vs. Library Function:

 System Call: Directly interacts with the kernel (e.g., read(), write()).
 Library Function: May or may not use system calls internally (e.g., printf() uses write() internally).

System calls are fundamental to how applications interact with the operating system and are a core concept in operating system
design and programming.

How System Calls Work:

1. A program invokes a system call by executing a specific instruction.
2. The CPU switches from user mode to kernel mode.
3. The kernel identifies the requested service and executes it.
4. Once the operation is complete, control is returned to the user program, and the CPU switches back to user mode.

Example in C:

In this example, the write() function is for the write system call, which writes data to a file .

Table summarizing the common types of system calls along with examples:

Category Description Examples

Process Control Manage processes (create, terminate, wait, etc.). fork(), exec(), exit(), wait()
Perform operations on files (open, read, write,
File Management open(), read(), write(), close(), chmod(), stat()
close, etc.).
Device Management Interact with hardware devices. ioctl()
Information Maintenance Retrieve or modify system information. getpid(), time(), setuid()
Facilitate inter-process communication (IPC) or
Communication pipe(), shmget(), send(), recv()
network communication.
Memory Management Allocate or deallocate memory for processes. brk(), mmap()
Process Control System Calls
Process Control System Calls are used to manage processes in an operating system. They allow programs to create, terminate, and
control processes, as well as manage their execution and synchronization. These system calls are essential for multitasking and
process management in modern operating systems.
Below is a detailed explanation of the most common process control system calls:

1. fork()
Purpose: Creates a new process by duplicating the calling process. The new process is called the child process, and the original
process is called the parent process.
How it works: The child process is an exact copy of the parent process, including code, data, and open files. Both processes
continue execution from the point where fork() was called.
Example:

Explanation:
1. fork() creates a new child process by duplicating the parent process.
2. Both the parent and child processes continue execution from the point where fork() was called.
3. The order of execution between the parent and child processes is non-deterministic. This means either the parent or child
process may execute first, depending on the OS scheduler.
4. The if (pid == 0) block is executed by the child process, and the else block is executed by the parent process.

2. exec() Family
Purpose: Replaces the current process image with a new program. This is often used after fork() to run a different program in the
child process.
Variants: execl(), execv(), execle(), execve(), etc.
How it works: The exec() system call loads a new program into the current process's memory space and starts its execution.
The original program's code, data, and stack are replaced by the new program.
Example:

Explanation:
1. execl() replaces the current process image with the program specified (/bin/ls in this case).
2. Once execl() is called, the current program stops executing, and the ls -l command takes over.
3. The return 0; statement is never reached because the process image is replaced by ls.
3. exit()
Purpose: Terminates the calling process and returns an exit status to the parent process.
How it works: The exit status is a small integer value (typically 0 for success and non-zero for failure). All open file descriptors
are closed, and any child processes are inherited by the init process.

4. wait()
Purpose: Suspends the calling process until one of its child processes terminates.
How it works: The parent process waits for the child process to finish and collects its exit status. If the child has already
terminated, wait() returns immediately.
Example:
Explanation:
1. fork(): Creates a child process by duplicating the parent process. The child process starts execution from the point
where fork() was called. The parent process receives the PID of the child process, and the child process receives 0.
2. Child Process: The if (pid == 0) block is executed by the child process. It prints "Child Process" and then calls exit(0) to
terminate.
3. Parent Process: The else block is executed by the parent process. The parent calls wait(NULL), which suspends its
execution until the child process terminates. After the child process terminates, the parent resumes execution and
prints "Parent Process".
4. Order of Execution: The child process always prints "Child Process" first because the parent process waits for the child to
finish before printing "Parent Process".

5. waitpid()
Purpose: Similar to wait(), but allows the parent process to wait for a specific child process.
How it works: The parent process specifies the PID of the child process to wait for. Additional options can be provided
(e.g., WNOHANG to return immediately if no child has exited).
Example:

Explanation:
1. fork(): Creates a child process by duplicating the parent process. The child process starts execution from the point
where fork() was called. The parent process receives the PID of the child process, and the child process receives 0.
2. Child Process: The if (pid == 0) block is executed by the child process. It prints "Child Process" and then calls exit(0) to
terminate.
3. Parent Process: The else block is executed by the parent process. The parent calls waitpid(pid, NULL, 0), which suspends
its execution until the specific child process (with the PID stored in pid) terminates. After the child process terminates,
the parent resumes execution and prints "Parent Process".
4. Order of Execution: The child process always prints "Child Process" first because the parent process waits for the
specific child to finish before printing "Parent Process".

6. getpid() and getppid()

getpid(): Returns the process ID (PID) of the calling process.
getppid(): Returns the parent process ID (PPID) of the calling process.
Example:
7. kill()
Purpose: Sends a signal to a process (e.g., to terminate it).
How it works: The process ID and the signal to send are specified (e.g., SIGKILL to forcefully terminate a process).
Example:

Summary of Process Control System Calls:

System Call Purpose
fork() Creates a new process (child) by duplicating the calling process.
exec() Replaces the current process image with a new program.
exit() Terminates the calling process and returns an exit status.
wait() Suspends the calling process until a child process terminates.
waitpid() Waits for a specific child process to terminate.
getpid() Returns the process ID of the calling process.
getppid() Returns the parent process ID of the calling process.
kill() Sends a signal to a process (e.g., to terminate it).
 Notes : S7-Process Control Block (PCB)

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define what a Process Control Block (PCB) is Open LMS (https://gulms.galgotiasuniversity.org/)
and its role in an operating system Go to course Operating System(R1UC403B)
(Unistructural). Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
2. Describe the components of the PCB & understand Click on “Session-wise Pre & Post Class Assessments”
how the PCB supports context  Attempt Assessment quizzes.
switching.(Multistructural).

Process Control Block (PCB)

The Process Control Block (PCB) is a data structure used by the operating system to store information about a process.
The PCB contains information such as:
1. Pointer-It stores the starting address of the process.
2. Process State- This field stores or represent the current state of the process whether it is in
ready/running/new/waiting/terminating.
3. Process ID/Number-Each process has unique ID or serial no. Each process is shown a unique no. known as its
Process ID.
4. Program Counter- It stores the address of the next instruction to be executed.
5. Register-This field contains the name of the registers which are currently used by the processor.
6. Scheduling Information-This field stores the information about the scheduling algo. used by operating System for
scheduling that process.
7. Memory Management Information-This field contains the value of the base table, segment table and page table.
8. Account Information-This field contains the total no. processes, time slice period it used.
9. File Management Information- It stores various information about the files used by the process.
10. I/O Status Information-It stores the information about various allocated I/O devices to the process, a list of open
files & so on.

Process in Memory
A process resides in memory through following section i.e.
1) Stack : Stack section contains local variable
2) Heap : Heap section contains memory which will be dynamically allocated during runtime.
3) Data : Data section contains global variable
4) Text : Text section contains code or instruction.
Context Switching
When CPU switches to another process, the system must save the state of the old process and load the saved state for the new
process via a context switch .Context of a process represented in the PCB. Context-switch time is overhead; the system does no
useful work while switching. CS time dependent on hardware support.

The OS uses the PCB to perform context switching and manage processes effectively.
The Process Table keeps a list of all active processes, and the PCB holds details about each process. The PCB enables smooth
process switching, effective multitasking, and efficient resource allocation.
 Notes : S8-Process States and Transition Diagram

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. List the different states of a process Open LMS (https://gulms.galgotiasuniversity.org/)
(Unistructural). Go to course Operating System(R1UC403B)
2. Describe the transitions between process states Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
(Multistructural). Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Process States
A process can be in one of several states during its lifecycle. These states represent the current activity or status of the process.
The operating system manages these states and ensures that processes transition smoothly between them.

Process States
 New: The process is being created.
 Ready: The process is waiting to be assigned to the CPU.
 Running: The process is currently being executed by the CPU.
 Waiting: The process is waiting for an event to occur (e.g., I/O completion).
 Terminated: The process has finished execution.

Transition Diagram
The transition diagram shows the possible states of a process and the events that cause transitions between these states.
The diagram typically includes the following transitions:

How Does a Process Move From One State to Other State?

a) New ->Ready : OS creates process and prepares the process to be executed, then OS moved the process into ready queue.
b) Ready->Running : OS selects one of the Jobs from ready Queue and move them from ready to Running.
c) Running->Terminated : When the Execution of a process has Completed, OS terminates that process from running state.
Sometimes OS terminates the process for some other reasons including Time exceeded, memory unavailable, access violation,
protection Error, I/O failure and soon.
d) Running->Ready : When the time slot of the processor expired (or) If the processor received any interrupt signal, the OS
shifted Running -> Ready State.
e) Running -> Waiting : A process is put into the waiting state, if the process need an event occur (or) an I/O Device require.
f) Waiting->Ready : A process in the waiting state is moved to ready state when the event for which it has been Completed.

Following is a more detailed diagram for the process state transition :

The image illustrating how processes move between different states. Here's a breakdown of the components and their meanings:
1. Main Memory: This is where processes reside when they are being actively managed by the operating system.
2. New: This is the initial state when a process is first created.
3. Admit: The process is moved from the "New" state to the "Ready" state, indicating it is ready to be executed.
4. Ready: The process is waiting to be assigned to a processor. It is in the main memory and is eligible for execution.
5. Dispatch: The process is selected by the scheduler to run on the CPU.
6. Running: The process is currently being executed by the CPU.
7. Release: The process has completed its execution and is terminated.
8. Exit: The process is removed from the system.
9. Timeout: The process is moved from the "Running" state back to the "Ready" state, typically due to the expiration of a
time slice in a time-sharing system.
10. Event wait: The process moves from the "Running" state to the "Blocked" state because it is waiting for an event (like
I/O completion).
11. Event Occur: The event the process was waiting for has occurred, moving it from the "Blocked" state back to the
"Ready" state.
12. Blocked: The process is waiting for an event to occur and cannot proceed until then.
13. Suspended Ready: The process is in the "Ready" state but has been moved to secondary memory (swapped out) to free up
main memory.
14. Activate: The process is moved back from secondary memory to main memory, transitioning from "Suspended Ready" to
"Ready".
15. Suspend: The process is moved from the "Ready" or "Blocked" state to the "Suspended Ready" or "Suspended Blocked"
state, respectively, and is swapped out to secondary memory.
16. Suspended Blocked: The process is in the "Blocked" state but has been moved to secondary memory.
17. Secondary Memory: This is where processes are stored when they are swapped out of main memory, typically due to
system resource constraints.

The flow in the image represents the lifecycle of a process in an operating system, showing how a process transitions between
different states from creation to termination. Here's a step-by-step explanation of the flow:
1. New: The process is created and enters the "New" state.
2. Admit: The process is admitted to the system and moves to the "Ready" state, where it waits to be assigned to a
processor.
3. Ready: The process is in main memory and is ready to execute. It waits in the ready queue for the scheduler to dispatch it
to the CPU.
4. Dispatch: The scheduler selects the process from the ready queue and dispatches it to the CPU for execution.
5. Running: The process is now executing on the CPU.
6. Timeout: If the process's time slice expires (in a time-sharing system), it is moved back to the "Ready" state to allow
other processes to run.
7. Event Wait: If the process needs to wait for an event (like I/O completion), it moves from the "Running" state to the
"Blocked" state.
8. Blocked: The process is waiting for an event to occur and cannot proceed until the event happens.
9. Event Occur: Once the event the process was waiting for occurs, the process moves back to the "Ready" state.
10. Release: After the process completes its execution, it moves to the "Release" state.
11. Exit: The process is terminated and removed from the system.

Additionally, there are transitions involving suspension:

 Suspend: A process in the "Ready" or "Blocked" state can be suspended and moved to secondary memory, transitioning
to the "Suspended Ready" or "Suspended Blocked" state, respectively.
 Activate: A suspended process can be activated and moved back to main memory, transitioning from "Suspended Ready"
to "Ready" or from "Suspended Blocked" to "Blocked".
 Suspended Ready: The process is in the "Ready" state but is swapped out to secondary memory.
 Suspended Blocked: The process is in the "Blocked" state but is swapped out to secondary memory.
Process states in an operating system and the real-life bank analogy:
Process State Description Real-Life Analogy
New The process is created. A customer enters the bank.
The process is admitted and moves to the "Ready"
Admit The customer takes a ticket and waits in the waiting area.
state.
The process is in main memory, waiting to be The customer is in the queue, waiting for their turn to be
Ready
assigned to the CPU. served.
The process is selected by the scheduler to run on the The bank teller calls the customer's number, and they
Dispatch
CPU. move to the counter.
Running The process is executing on the CPU. The customer is being served by the teller.
The process is moved back to the "Ready" state due to The teller pauses serving the customer to handle another
Timeout
time slice expiration. task or take a break.
The process moves to the "Blocked" state, waiting for The customer steps aside to wait for a document to be
Event Wait
an event (e.g., I/O). printed or verified.
Blocked The process is waiting for an event to complete. The customer is waiting for the document to be ready.
The event occurs, and the process moves back to the The document is ready, and the customer can proceed
Event Occur
"Ready" state. with their transaction.
The customer finishes their transaction and leaves the
Release The process completes its execution.
counter.
The process is terminated and removed from the
Exit The customer leaves the bank.
system.
The process is moved to secondary memory (swapped The bank asks the customer to leave and come back later
Suspend
out). due to high traffic.
The process is moved back to main memory from The bank calls the customer back to continue their
Activate
secondary memory. transaction when it’s less busy.
Suspended The process is in the "Ready" state but swapped out to The customer is waiting outside but ready to come back
Ready secondary memory. when called.
Suspended The process is in the "Blocked" state but swapped out The customer is waiting outside for a document to be
Blocked to secondary memory. ready.
 Notes : S9-Schedulers

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Describe the different types of schedulers Open LMS (https://gulms.galgotiasuniversity.org/)
2. Explain the functions and responsibilities of each Go to course Operating System(R1UC403B)
type of scheduler. Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Schedulers
The scheduler is a program that decides:
1. Which process should run next on the CPU.
2. How long a process should run (time slicing in time-sharing systems).
3. The order in which processes are executed.
It ensures that the CPU is used efficiently, processes are handled fairly, and system resources are allocated optimally.
There are three main types of schedulers:
1. Long-Term Scheduler (Job Scheduler):
2. Short-Term Scheduler (CPU Scheduler):
3. Medium-Term Scheduler:

Long Term Scheduler

 It loads a process from disk to main memory for execution. The new process to the ‘Ready State’.
 It mainly moves processes from Job Queue to Ready Queue.

 It controls the Degree of Multi-programming, i.e., the number of processes present in a ready state or in main memory at
any point in time.
 It is important that the long-term scheduler make a careful selection of both I/O and CPU-bound processes. I/O-bound
tasks are which use much of their time in input and output operations while CPU-bound processes are which spend their
time on the CPU. The job scheduler increases efficiency by maintaining a balance between the two.
 In some systems, the long-term scheduler might not even exist. For example, in time-sharing systems like Microsoft
Windows, there is usually no long-term scheduler. Instead, every new process is directly added to memory for the short-
term scheduler to handle.
 Slowest among the three (that is why called long term).

Medium-Term Scheduler:
 Medium Term Scheduler (MTS) is responsible for moving a process from memory to disk (or swapping).
 It reduces the degree of multiprogramming (Number of processes present in main memory).
 A running process may become suspended if it makes an I/O request. A suspended processes cannot make any progress
towards completion. In this condition, to remove the process from memory and make space for other processes, the
suspended process is moved to the secondary storage. This process is called swapping, and the process is said to be
swapped out or rolled out. Swapping may be necessary to improve the process mix (of CPU bound and IO bound)
 When needed, it brings process back into memory and pick up right where it left off.
  It is faster than long term and slower than short term.

Short-Term Scheduler:
 Maximizes CPU utilization and system throughput.
 STS (Short Term Scheduler) must select a new process for the CPU frequently to avoid starvation.
 The CPU scheduler uses different scheduling algorithms to balance the allocation of CPU time.
 It picks a process from ready queue.
 Its main objective is to make the best use of CPU.
 It mainly calls dispatcher.
 Fastest among the three (that is why called Short Term).

Comparison of the Long-Term Scheduler, Medium-Term Scheduler, and Short-Term Scheduler in operating systems:
Aspect Long-Term Scheduler Medium-Term Scheduler Short-Term Scheduler
Also Known As Job Scheduler Swapper CPU Scheduler
Controls the admission of Selects which process in the ready
Manages the swapping of processes between
Purpose processes into the ready queue will execute next on the
memory and disk.
queue. CPU.
Frequency of Infrequent (when a new Very frequent (every few
Moderate (depends on system load).
Operation process is created). milliseconds).
Decides which processes
Decides which processes are swapped out to disk Decides which process gets CPU
Responsibility are loaded into memory
or brought back into memory. time next.
for execution.
Manages the degree of
multiprogramming Balances the system's memory usage and Ensures efficient CPU utilization
Focus
(number of processes in performance. and responsiveness.
memory).
Process State Moves processes Moves processes Moves processes
Transition from New to Ready. between Ready/Suspend and Blocked/Suspend. between Ready and Running.
Affects the overall system
Impact on Affects the system's ability to handle memory Directly impacts CPU utilization
throughput and resource
Performance pressure. and response time.
utilization.
 Notes : S10-CPU Scheduling Concepts and Criteria

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define CPU scheduling and its purpose in an Open LMS (https://gulms.galgotiasuniversity.org/)
operating system (Unistructural). Go to course Operating System(R1UC403B)
2. Explain the criteria used to evaluate CPU Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
scheduling algorithms (Relational). Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

CPU Scheduling:
CPU Scheduling is a process that allows one process to use the CPU while another process is delayed due to unavailability of
any resources such as I / O etc, thus making full use of the CPU. In short, CPU scheduling decides the order and priority of the
processes to run and allocates the CPU time based on various parameters such as CPU usage, throughput, turnaround, waiting
time, and response time. The purpose of CPU Scheduling is to make the system more efficient, faster, and fairer.
It is done by Short-term scheduler (CPU scheduler).
Dispatcher
The dispatcher is responsible for loading the process selected by the Short-term scheduler on the CPU (Ready to Running State).
Context switching is done by the dispatcher only.
Time taken by dispatcher is called dispatch latency or process context switch time.

The objective of multiprogramming is to have some process running at all times, to maximize CPU utilization.
Process execution = cycle of CPU + I/O wait.

CPU scheduling decisions may take place when a process:

1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates
▪ For situations 1 and 4, there is no choice in terms of scheduling. A new process (if one exists in the ready queue) must be
selected for execution.
▪ For situations 2 and 3, however, there is a choice.
 When scheduling takes place only under circumstances 1 and 4, the scheduling scheme is non-preemptive
(In this case once the CPU has been allocated to a process, the process keeps the CPU until it releases the CPU by terminating
or by switching to the waiting state. That is when it is (process)is computed or required any I/O operation.)
Otherwise, it is preemptive.
(In this case CPU can be released forcefully. Under this scheduling the process has to leave the CPU forcefully on when interrupt
occur or due to completion of time slice period).

▪ Virtually all modern operating systems including Windows, MacOS, Linux, and UNIX use preemptive scheduling algorithms

Preemptive and non-preemptive scheduling algorithms:

Preemptive Scheduling Non-Preemptive Scheduling

Round Robin (RR) First-Come-First-Serve (FCFS)
Priority Scheduling Shortest Job First (SJF)
Shortest Remaining Time First (SRTF) Non-Preemptive Priority Scheduling
Multilevel Queue Scheduling Non-Preemptive SRTF
Multilevel Feedback Queue Scheduling

Criteria of CPU Scheduling

CPU scheduling criteria, such as turnaround time, waiting time, and throughput, are essential metrics used to evaluate the
efficiency of scheduling algorithms.
1. CPU utilization
The main objective of any CPU scheduling algorithm is to keep the CPU as busy as possible. Theoretically, CPU utilization
can range from 0 to 100 but in a real-time system, it varies from 40 to 90 percent depending on the load upon the system.

2. Throughput
A measure of the work done by the CPU is the number of processes being executed and completed per unit of time. This is
called throughput. The throughput may vary depending on the length or duration of the processes.

3. Turnaround Time
For a particular process, an important criterion is how long it takes to execute that process. The time elapsed from the time of
submission of a process to the time of completion is known as the turnaround time. Turn-around time is the sum of times spent
waiting to get into memory, waiting in the ready queue, executing in CPU, and waiting for I/O.
Turn Around Time = Completion Time – Arrival Time.

4. Waiting Time
A scheduling algorithm does not affect the time required to complete the process once it starts execution. It only affects the
waiting time of a process i.e. time spent by a process waiting in the ready queue.
Waiting Time = Turnaround Time – Burst Time.

5. Response Time
In an interactive system, turn-around time is not the best criterion. A process may produce some output fairly early and
continue computing new results while previous results are being output to the user. Thus another criterion is the time taken
from submission of the process of the request until the first response is produced. This measure is called response time.
Response Time = CPU Allocation Time(when the CPU was allocated for the first) – Arrival Time

What to maximize: Throughput, CPU Utilization

What to minimize: Waiting Time, Turn Around Time, Response Time

Some other keywords related to CPU Scheduling:

1.Burst Time
Burst time, also referred to as “execution time”. It is the amount of CPU time the process requires to complete its execution. It
is the amount of processing time required by a process to execute a specific task or unit of a job. Factors such as the task’s
complexity, code efficiency, and the system’s resources determine the process’s burst time.

2. Arrival Time
In CPU Scheduling, the arrival time refers to the moment in time when a process enters the ready queue and is awaiting execution
by the CPU. In other words, it is the point at which a process becomes eligible for scheduling.

3. Completion Time
Completion time is when a process finishes execution and is no longer being processed by the CPU. It is the summation of the
arrival, waiting, and burst times.
 Notes : S11- Scheduling Algorithms – Preemptive

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define preemptive scheduling and its purpose Open LMS (https://gulms.galgotiasuniversity.org/)
in an operating system (Unistructural). Go to course Operating System(R1UC403B)
2. Describe the different preemptive scheduling Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
algorithms (Multistructural). Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Preemptive scheduling algorithms :

Preemptive scheduling algorithms fall under the category of process scheduling technique in which a running process can be
interrupted by another process and sent to the ready queue even when it has not completed its entire execution in CPU.
CPU scheduling decisions may take place when a process:
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates
preemptive. In this case CPU can be released forcefully. Under this scheduling the process has to leave the CPU forcefully on
when interrupt occur or due to completion of time slice period.
Preemptive Scheduling Algorithms:
 Round Robin (RR) Scheduling
 Shortest Remaining Time Next (SJF Preemptive)
 Priority Preemptive Scheduling

Round Robin (RR):

Each process is assigned a fixed time slice (quantum) in a cyclic order. If a process does not complete within its time slice, it is
preempted and moved to the end of the ready queue.
Advantage: Ensures fair CPU time for all processes.
Disadvantage: High overhead due to frequent context switching.

Example:
Make a gantt chart for following table and calculate average turn around time and waiting time by implementing Round Robin.
(Time slice=4ms and context switch time=1 ms)
Shortest Remaining Time First (SRTF):
The process with the shortest remaining burst time is selected for execution.
If a new process arrives with a shorter burst time, the current process is preempted.
Advantage: Minimizes average waiting time.
Disadvantage: Can lead to starvation of longer processes.

Example:
Make a gantt chart for following table and calculate average turn around time and waiting time by implementing Preemptive SJF
Scheduling(SRTF)

Process Arrival Time Burst Time

P0 0 10
P1 1 6
P2 3 2
P3 5 4
* When two processes have the same burst time, the tie is broken using the arrival time.
Gantt Chart:
P0 P1 P2 P1 P3 P0
0 1 3 5 9 13 22

To Calculate Avg TAT and Avg WT:

Process Arrival Time Burst Time Finish time TAT Waiting Time
(Finish time-Arrival time) (TAT-Burst time)
P0 0 10 22 22-0=22 22-10=12
P1 1 6 9 9-1=8 8-6=2
P2 3 2 5 5-3=2 2-2=0
P3 5 4 13 13-5=8 8-4=4
Result Avg TAT=(22+8+2+8)/4=10 Avg WT=(4+0+2+12)/4=4.5

Priority Scheduling:
Processes are executed based on their priority. Higher priority processes are executed first. If a higher priority process arrives, the
current process is preempted. Advantage: Allows for prioritization of important processes. Disadvantage: Can lead to starvation of
lower priority processes.
Examples:
Make a gantt chart for following table and calculate average turn around time and waiting time by implementing Preemptive
Priority based algorithm.(Low number , High priority)

Process Arrival Time Burst Time Process priority

P0 0 10 5
P1 1 6 4
P2 3 2 2
P3 5 4 0
Gantt Chart:
P0 P1 P2 P3 P1 P0
0 1 3 5 9 13 22

To Calculate Avg TAT and Avg WT:

Process Arrival Time Burst Time Finish time TAT Waiting Time
(Finish time-Arrival time) (TAT-Burst time)
P0 0 10 22 22-0=22 22-10=12
P1 1 6 13 13-1=12 12-6=6
P2 3 2 5 5-3=2 2-2=0
P3 5 4 9 9-5=4 4-4=0
Result Avg TAT=(22+12+2+4)/4=10 Avg WT=(12+6+0+0)/4=4.5
Real-world examples of preemptive scheduling

# System/Application How Preemption Works Why Preemptive? Key Benefit

CPU switches tasks based on priority/time
Ensures fair CPU allocation Prevents process
1 Operating Systems
quantum (e.g., Round Robin scheduling) and responsiveness monopolization
Emergency Vehicle Traffic lights preempt normal cycles for Saves lives by prioritizing Reduces emergency
2
Traffic Signals ambulances/police via sensors emergency response response time
Higher-priority flights (emergencies, VIP)
Prevents collisions and Ensures safety in congested
3 Air Traffic Control
get runway access immediately manages critical operations airspace
Real-Time Stock High-frequency trades interrupt lower- Capitalizes on market Maximizes profit in volatile
4
Trading priority transactions opportunities in milliseconds markets
Robotic Surgery Surgeon can override autonomous tools Allows human intervention Combines AI precision with
5
Systems during critical moments in life-or-death scenarios human expertise
Critical infrastructure (hospitals) gets
Maintains essential services Prevents cascading system
6 Smart Grids (Power)
power during outages, preempting othersduring disasters failures
Optimizes resource
VM resources reallocated dynamically Reduces costs and improves
7 Cloud Computing utilization and SLA
based on demand/priority scalability
compliance
Autonomous Emergency braking interrupts navigation Prioritizes safety over route Prevents accidents in
8
Vehicles to avoid collisions optimization unpredictable environments
Ensures timely
Breaking news interrupts scheduled Maintains public trust and
9 Live TV Broadcasts dissemination of critical
programming safety
information

Question:
1. Make a gantt chart and calculate Completion Time (CT) for each process, Turnaround Time (TAT = CT - Arrival Time),
Waiting Time (WT = TAT - Burst Time), Average TAT and WT for all processes.for following table while implementing Round
Robin (RR) with time quantum = 4 ms .
Process Arrival Time (ms) Burst Time (ms)
P1 0 10
P2 1 4
P3 2 8
P4 3 5

2. Make a gantt chart and calculate Completion Time (CT) for each process ,Turnaround Time (TAT = CT - Arrival Time) ,
Waiting Time (WT = TAT - Burst Time) , Average TAT and WT for all processes.for following table while implementing Shortest
Remaining Time Next (SRTN - Preemptive SJF)
Process Arrival Time (ms) Burst Time (ms)
P1 0 10
P2 1 4
P3 2 8
P4 3 5

3. Make a gantt chart and calculate Completion Time (CT) for each process,Turnaround Time (TAT = CT - Arrival Time),
Waiting Time (WT = TAT - Burst Time) ,Average TAT and WT for all processes.
for following table while implementing Priority Preemptive Scheduling (Lower number = Higher priority)
Process Arrival Time (ms) Burst Time (ms) Priority
P1 0 10 3
P2 1 4 1
P3 2 8 2
P4 3 5 4
 Notes : S12- CPU Scheduling Algorithms – Non-Preemptive

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define non-preemptive CPU scheduling. Open LMS (https://gulms.galgotiasuniversity.org/)
2. Describe the different non-preemptive CPU Go to course Operating System(R1UC403B)
scheduling algorithms Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Non-Preemptive Scheduling
Non-preemptive scheduling is a type of CPU scheduling where a process runs to completion without being interrupted by the
operating system . Once a process is assigned to the CPU, it cannot be preempted until it finishes its execution or voluntarily gives
up the CPU (e.g., by waiting for an I/O operation). Non-preemptive scheduling is simpler to implement but may lead to longer
waiting times for some processes.

Real-world examples of non-preemptive scheduling:

# Example How It Works Why Non-Preemptive? Contrast with Preemptive
Follows a fixed path (FCFS/SCAN) Emergency override
Elevator Safety and energy efficiency (avoids
1 without stopping for new requests mid- (preemptive) would cause
Systems abrupt stops).
motion. chaos.
Print Processes jobs in order; large jobs aren’t Prevents paper jams and ensures job Print spoolers (preemptive)
2
Queues interrupted for smaller ones. integrity. could corrupt files.
Batch
Runs payroll calculations start-to-finish Data integrity and audit trails (partial Real-time payroll (preemptive)
3 Payroll
without interruption. runs could cause errors). risks miscalculations.
Systems
Washing Completes the selected cycle even if a Prevents mechanical damage (e.g., "Pause" features (preemptive)
4
Machines shorter cycle is requested mid-run. stopping mid-spin harms the motor). are rare for durability.
Coffee Brews a full pot without pausing if "stop" Ensures consistent brew quality Single-serve machines
5
Makers is pressed midway. (half-brewed coffee is useless). (preemptive) are exceptions.

First-Come, First-Served (FCFS):

Processes are executed in the order they arrive in the ready queue. Advantage: Simple to implement. Disadvantage: Can lead to
long waiting times for short processes if a long process is ahead in the queue (known as the "convoy effect").
Example:Make a gantt chart for following table and calculate average turn around time and waiting time by implementing FCFS.

Process Arrival Time Burst Time

P0 0 10
P1 1 6
P2 3 2
P3 5 4
Gantt Chart:

P0 P1 P2 P3
0 10 16 18 22

To Calculate Avg TAT and Avg WT:

Process Arrival Time Burst Time Finish time TAT Waiting Time
(Finish time-Arrival time) (TAT-Burst time)
P0 0 10 10 10-0=10 10-10=0
P1 1 6 16 16-1=15 15-6=9
P2 3 2 18 18-3=15 15-2=13
P3 5 4 22 22-5=17 17-4=13
Result Avg TAT=(10+15+15+17)/4=14.25 Avg WT=(0+9+13+13)/4=8.75
Significant variation of FCFS:
Table is:
Process Arrival Time Burst Time
P0 5 10
P1 3 6
P2 1 2
P3 O 4

Gantt chart will be for this table:

P3 P2 P1 P0
0 4 6 12 22

Now calculation table will be:

Process Arrival Time Burst Time Finish time TAT Waiting Time
(Finish time-Arrival time) (TAT-Burst time)
P0 5 10 22 22-5=17 17-10=7
P1 3 6 12 12-3=9 9-6=3
P2 1 2 6 6-1=5 5-2=3
P3 O 4 4 4-0=4 4-4=0
Result Avg TAT=(17+9+5+4)/4=8.75 Avg WT=(7+3+3+0)/4=3.25

Here you can see the average waiting time is decreased from 8.75 to 3.25. that is much better from the first solution.
So in this algorithm if we get short process behind long process it decreases the avg WT this particular effect is known as Convoy
Effect.

Shortest Job First (SJF):

The process with the shortest burst time is selected for execution. Advantage: Minimizes average waiting time. Disadvantage: Can
lead to starvation of longer processes.
Example:
Make a gantt chart for following table and calculate average turn around time and waiting time by implementing Non Preemptive
SJF Scheduling
Process Arrival Time Burst Time
P0 0 10
P1 1 6
P2 3 2
P3 5 4
Gantt Chart:

P0 P2 P3 P1
0 10 12 16 22
To Calculate Avg TAT and Avg WT:

Process Arrival Time Burst Time Finish time TAT Waiting Time
(Finish time-Arrival time) (TAT-Burst time)
P0 0 10 10 10-0=10 10-10=0
P1 1 6 22 22-1=21 21-6=15
P2 3 2 12 12-3=9 9-2=7
P3 5 4 16 16-5=11 11-4=7
Result Avg TAT=(10+21+9+11)/4=12.75 Avg WT=(0+15+7+7)/4=7.25

Priority Scheduling:
Processes are executed based on their priority. Higher priority processes are executed first. Advantage: Allows for prioritization of
important processes. Disadvantage: Can lead to starvation of lower priority processes.
Example:
Make a gantt chart for following table and calculate average turn around time and waiting time by implementing Non Preemptive
Priority based algorithm.
Process Arrival Time Burst Time Process priority
P0 0 10 5
P1 1 6 4
P2 3 2 2
P3 5 4 0
Gantt Chart:

P0 P3 P2 P1
0 10 14 16 22

To Calculate Avg TAT and Avg WT:

Process Arrival Time Burst Time Finish time TAT Waiting Time
(Finish time-Arrival time) (TAT-Burst time)
P0 0 10 10 10-0=10 10-10=0
P1 1 6 22 22-1=21 21-6=15
P2 3 2 16 16-3=13 13-2=11
P3 5 4 14 14-5=9 9-4=5
Result Avg TAT=(10+21+13+9)/4=13.25 Avg WT=(0+15+11+5)/4=7.75

Multilevel Queue Scheduling

 Ready queue is partitioned into separate queues: foreground (interactive) background (batch)
 Each queue has its own scheduling algorithm o foreground – RR o background – FCFS
 Scheduling must be done between the queues o Fixed priority scheduling; (i.e., serve all from foreground then from
background). Possibility of starvation. o Time slice – each queue gets a certain amount of CPU time which it can schedule
amongst its processes; i.e., 80% to foreground in RR o 20% to background in FCFS

Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling

In a multilevel queue-scheduling algorithm, processes are permanently assigned to a queue on entry to the system, and processes
are allowed to move between queues.

Features of Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling:

Multiple queues:
MLFQ scheduling divides processes into multiple queues based on their priority levels. However, unlike MLQ scheduling, processes
can move between queues based on their behavior and needs.
Priorities adjusted dynamically:
The priority of a process can be adjusted dynamically based on its behavior, such as how much CPU time it has used or how often
it has been blocked. Higher-priority processes are given more CPU time and lower-priority processes are given less.
Time-slicing:
Each queue is assigned a time quantum or time slice, which determines how much CPU time a process in that queue is allowed to
use before it is preempted and moved to a lower priority queue.
Feedback mechanism:
MLFQ scheduling uses a feedback mechanism to adjust the priority of a process based on its behavior over time. For example, if a
process in a lower-priority queue uses up its time slice, it may be moved to a higher-priority queue to ensure it gets more CPU time.
Preemption:
Preemption is allowed in MLFQ scheduling, meaning that a higher-priority process can preempt a lower-priority process to ensure
it gets the CPU time it needs.

Advantages of Multilevel Feedback Queue Scheduling:

 It is more flexible.
 It allows different processes to move between different queues.
 It prevents starvation by moving a process that waits too long for the lower priority queue to the higher priority queue.
Disadvantages of Multilevel Feedback Queue Scheduling:
 The selection of the best scheduler, it requires some other means to select the values.
 It produces more CPU overheads.
 It is the most complex algorithm.

Multilevel feedback queue scheduling, however, allows a process to move between queues. Multilevel Feedback Queue
Scheduling (MLFQ) keeps analyzing the behavior (time of execution) of processes and according to which it changes its priority.
Now, look at the diagram and explanation below to understand it properly.

What is the need for such complex Scheduling?

 Firstly, it is more flexible than multilevel queue scheduling.
 To optimize turnaround time algorithms like SJF are needed which require the running time of processes to schedule them.
But the running time of the process is not known in advance. MFQS runs a process for a time quantum and then it can
change its priority(if it is a long process). Thus it learns from past behavior of the process and then predicts its future
behavior. This way it tries to run a shorter process first thus optimizing turnaround time.
 MFQS also reduces the response time.

Question:
1. Make a gantt chart and calculate

a) Completion Time (CT) for each process.

b) Turnaround Time (TAT = CT - Arrival Time).
c) Waiting Time (WT = TAT - Burst Time).
d) Average TAT and WT for all processes.
for following table while implementing FCFS.

Process Arrival Time (ms) Burst Time (ms)

P1 0 10
P2 1 4
P3 2 8
P4 3 5

2. Make a gantt chart and calculate

a) Completion Time (CT) for each process.

b) Turnaround Time (TAT = CT - Arrival Time).
c) Waiting Time (WT = TAT - Burst Time).
d) Average TAT and WT for all processes.
for following table while implementing Non Preemptive SJF Scheduling.

Process Arrival Time (ms) Burst Time (ms)

P1 0 10
P2 1 4
P3 2 8
P4 3 5
 Notes : S13- Threads and Their Management

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define what a thread is and its role in an Open LMS (https://gulms.galgotiasuniversity.org/)
operating system (Unistructural). Go to course Operating System(R1UC403B)
2. Explain how threads are created and concept Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
of multithreading (Relational). Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Threads
 A thread is the smallest unit of execution within a process. Threads are often referred to as lightweight processes because
they share the same address space and resources as the process that created them.
 Threads allow for concurrent execution of tasks within a single process, improving application responsiveness and
performance.
 All threads belonging to the same process share – code section, data section, and OS resources (e.g. open files and signals)
But each thread has its own (thread control block) – thread ID, program counter, register set, and a stack.
 Any operating system process can execute a thread. we can say that single process can have multiple threads.

Threads are like workers in the same office (shared space, fast communication). Processes are separate offices (isolated, secure,
but slower to coordinate).
Threads can share common data so they do not need to use inter-process communication. Like the processes, threads also have
states like :
1. Born State: A thread that has just been created.
2. Ready State: The thread is waiting for the processor (CPU).
3. Running: The System assigns the processor to the thread means that the thread is being executed.
4. Blocked State: The thread is waiting for an event to occur or waiting for an I/O device.
5. Sleep: A sleeping thread becomes ready after the designated sleep time expires.
6. Dead: The execution of the thread is finished.

Why Do We Need Thread?

Threads are essential in modern computing because they enable efficient resource utilization and improved performance in
various scenarios. Here’s why they’re crucial:
1. Parallelism & Improved Performance
 Multi-core Utilization: Threads allow a program to split work across multiple CPU cores, speeding up computation.
o Example: Rendering a video while compressing files simultaneously.
 Responsiveness: Keep applications responsive while performing background tasks.
o Example: A word processor auto-saving while you continue typing.
2. Efficient Resource Sharing
 Threads within the same process share:
o Memory (global variables, heap)
o File descriptors
o Code segments
 Advantage: Much faster communication than between processes (no IPC overhead).
3. Economical Compared to Processes
Feature Threads Processes
Creation Time Faster (shared memory space) Slower (new memory space)
Context Switch Less expensive More expensive
Memory Usage Low (shared resources) High (separate memory)
4. Real-World Use Cases
 Web Servers: Handle thousands of concurrent requests (e.g., Apache, Nginx).
 GUI Applications: Keep the interface responsive while processing data.
 Scientific Computing: Parallelize matrix operations or simulations.

Types of Thread in Operating System

Threads are of two types. These are described below. User Level Thread & Kernel Level Thread
User-Level Threads (ULTs) Vs Kernel-Level Threads (KLTs):
Feature User-Level Threads (ULTs) Kernel-Level Threads (KLTs)
Managed by User-space library (e.g., pthread) OS Kernel
Kernel Awareness No (kernel sees only the process) Yes (kernel manages threads directly)
Creation Speed Fast (no kernel interaction) Slow (system call required)
Context Switching Fast (user-mode only) Slow (kernel-mode switch needed)
Blocking Behavior One blocked thread blocks entire process One blocked thread doesn’t block others
Multi-Core Support No (runs on single core) Yes (true parallelism)
Scheduling Control User-defined (flexible) OS-controlled (fixed policies)
Examples Java "Green Threads," GNU Portable Threads Windows OS threads, Linux pthreads
Best For Lightweight, high-speed thread switching CPU-bound tasks, multi-core utilization

How Threads are Created

 Threads can be created using libraries like POSIX Threads (pthread)
 In C, pthread_create() is used to create threads.
 Each thread runs independently and shares process resources.
How Threads are Scheduled
 The OS scheduler decides which thread gets CPU time.
 Scheduling policies include FIFO, Round Robin, and Priority Scheduling.
 Preemptive and Non-preemptive scheduling affect execution order.
How Threads are Synchronized
 Synchronization prevents race conditions and ensures data integrity.
 Mechanisms include Mutexes, Semaphores, and Monitors.
 Synchronization ensures orderly execution of shared resources.

What is Multi-Threading?
Multithreading is a technique used in operating systems to improve the performance and responsiveness of computer systems.
Multithreading allows multiple threads (i.e., lightweight processes) to share the same resources of a single process, such as the
CPU, memory, and I/O devices.
All the threads must have a relationship between them (i.e., user threads and kernel threads). Here is a list of three common ways
of establishing this relationship.
 Many-to-One Model: The many-to-one model plots several user-level threads to a single kernel thread.
 One-to-One Model: The one-to-one model maps every user thread to a kernel thread and provides more concurrency
than the many-to-one model.
 Many-to-Many Model: In the many-to-many model, many user-level threads get mapped to a smaller or equal quantity
of kernel threads. The number of kernel threads might be exact to a particular application or a specific machine

Creation of thread and implementing multithreading using C program

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
void* creating_thread();
// Let us create a global variable to change it in threads
int g = 0;
int main()
{ int i;
pthread_t tid;
// Let us create three threads
for (i = 0; i < 3; i++)
pthread_create(&tid, NULL, creating_thread, NULL);
pthread_exit(NULL);
return 0;
}

// The function to be executed by all threads

void* creating_thread()
{ // Getting unique thread id for each thread
int thread_id = pthread_self();
// Let us create a static variable to observe its changes
static int s = 0;
// Change static and global variables
s=s+1;
g=g+1;
// Print the argument, static and global variables
printf("Thread ID: %d, Static: %d, Global: %d\n", thread_id, s, g);
}
This program creates three threads that concurrently modify and print shared variables (g and s). Here's how it works:
 g and s are shared across threads. All threads increment these variables, causing unpredictable results.
 Thread Creation:
for (i = 0; i < 3; i++)
pthread_create(&tid, NULL, creating_thread, NULL);
Creates 3 threads using the same function creating_thread.
 Thread Function:
void* creating_thread()
{ int thread_id = pthread_self(); // Gets the thread’s unique ID
s++; g++; // Modifies shared variables
printf("Thread ID: %d, Static: %d, Global: %d\n", thread_id, s, g);
}

 pthread_exit(NULL): Ensures the main thread waits for all child threads to finish.

How It Demonstrates Multithreading

1. Concurrent Execution: Threads run simultaneously, leading to mixed output order (non-sequential).
Thread ID: 123, Static: 1, Global: 1
Thread ID: 456, Static: 3, Global: 3
Thread ID: 789, Static: 2, Global: 2
The order changes on each run due to CPU scheduling.
2. Shared Memory Access : All threads modify the same g and s.
3. Unique Thread IDs: pthread_self() returns a unique ID per thread, proving they are distinct entities.

Single-Threaded Vs Multi-Threaded Processes:

Feature Single-Threaded Process Multi-Threaded Process

A process with one thread executing tasks A process with multiple threads running concurrently within the
Definition
sequentially. same memory space.
Execution
Sequential (one task at a time). Parallel/concurrent (multiple tasks at once).
Model
Slower for CPU-bound tasks (no
Performance Faster for CPU-bound tasks (utilizes multiple cores).
parallelism).
Responsiveness Poor (blocks on I/O operations). Better (one thread can run while another waits for I/O).
Resource Usage Lower memory & CPU overhead. Higher memory & CPU usage (due to thread management).
Complexity Simple (no race conditions or deadlocks). Complex (requires synchronization—locks, semaphores).
Error Handling Crashes affect only the single thread. One crashing thread can kill the entire process.
- Web servers
Use Cases Small utilities - Games
- Real-time systems

Examples of multithreading with explanations:

# Example Explanation
Handles multiple client requests simultaneously using threads (e.g., Apache HTTP Server). Each client
1 Web Servers
connection is managed by a separate thread.
GUI Keeps the UI responsive by running background tasks (e.g., file loading, computations) in separate threads
2
Applications while the main thread handles user input.
Database
3 Uses multiple threads to process concurrent queries, improving performance (e.g., MySQL thread pool).
Systems
Runs physics, AI, rendering, and input handling in separate threads to improve performance and
4 Video Games
responsiveness.
Decodes audio/video in one thread while another handles UI updates and user interactions for smooth
5 Media Players
playback.
Scientific Parallelizes heavy computations (e.g., matrix operations, simulations) across multiple CPU cores using
6
Computing threads.
Real-Time
7 Uses threads to handle multiple sensors/actuators simultaneously (e.g., robotics, automotive systems).
Systems
File
8 Downloads multiple files concurrently by assigning each download to a separate thread.
Downloaders
Blockchain
9 Validates transactions and mines blocks in parallel using multiple threads for faster processing.
Networks
 Notes : S14- Principles of Concurrency: Mutual Exclusion, Critical Section Problem

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define concurrency, mutual exclusion, and Open LMS (https://gulms.galgotiasuniversity.org/)
the critical section problem (Unistructural). Go to course Operating System(R1UC403B)
2. Describe the conditions required to solve the Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
critical section problem (Multistructural). Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Multiple Processes:
Central to the design of modern Operating Systems is managing multiple processes–
 Multiprogramming(multiple processes within a uniprocessor system)
 Multiprocessing(multiple processes within a multiprocessor)
 Distributed Processing(multiple processes executing on multiple ,distributed processing)
Big Issue is Concurrency – Managing the interaction of all of these processes

Principle of Concurrency:
 Cooperating process is one that can affect or be affected by the other processes executing in system. Cooperating processes
may either share a logical address space or be allowed to share data only through files.
 It is necessary because: information sharing, computation speed up, modularity.
 When several process access and manipulate the same data at a time they are said to be concurrent processes.
 Process synchronization is a mechanism to ensure a systematic sharing of resources amongst concurrent processes. So to
resolve concurrency we have to employ some protocols to ensure a systematic sharing of resources amongst concurrent
processes.

Operating System Concerns

What design and management issues are raised by the existence of concurrency??
The OS must
a. Keep track of various processes(PCB)
b. Allocate and de-allocate resources(PROCESSOR TIME,MEMORY,FILES,I/O DEVICES)
c. Protect the data and resources against interference by other processes.
d. Ensure that the processes and outputs are independent of the processing speed

Concurrency affects a number of design issues : • Communication among processes • Sharing resources • Synchronization of
multiple processes • Allocation of processor time

Why Concurrency Matters?

Concurrency is a fundamental concept in modern computing because it enables efficient resource utilization, improves performance,
and allows systems to handle multiple tasks simultaneously. Here’s why it matters:
1. Better CPU & Resource Utilization
2. Improved Responsiveness (User Experience)
3. Scalability & Performance
4. Real-World Systems Are Naturally Concurrent

Key Concurrency Terms

Term Definition
Thread A lightweight unit of execution within a process (shares memory space).
Process An independent program instance with its own memory space.
Race Condition Unpredictable behavior when threads access shared data unsynchronized.
Deadlock Threads stuck waiting indefinitely for each other’s resources.
Mutex (Lock) Synchronization primitive allowing exclusive access to a resource.
Semaphore A counter-based lock allowing limited concurrent access (e.g., 3 threads max).
Atomic Operation An indivisible action (e.g., read-modify-write) guaranteed to complete uninterrupted.
Message Passing Threads/processes communicate via messages (e.g., channels in Go).
Immutable Data Data that cannot be modified after creation.
Real world example of concurrency
Example Explanation
Handles thousands of simultaneous HTTP requests by using multi-threading or event-driven architectures.
Web Servers
Without concurrency, only one user could connect at a time.
Processes multiple read/write operations concurrently using transactions and locking. Without concurrency,
Databases
queries would execute one-by-one, causing delays.
Runs each tab in a separate process for stability and speed. JavaScript, downloads, and rendering happen
Web Browsers
concurrently. Without it, the browser would freeze.
Operating Manages multiple apps simultaneously via CPU time-slicing and multi-threading. Without concurrency, only
Systems one app could run at a time.
Uses multi-threading for rendering, physics, and AI to ensure smooth gameplay. Without concurrency, games
Video Games
would lag or stutter.
Ride-Sharing Tracks real-time driver locations and matches rides using concurrent backend services. Without it, updates would
Apps be slow and unreliable.
Scientific Splits massive computations across CPU/GPU cores for faster results. Without concurrency, simulations would
Computing take impractical amounts of time.

Challenges in Concurrency
Challenge Description Real-World Impact Common Solutions
Race Occurs when multiple threads access shared data Crashes, corrupted data (e.g., bank Locks (mutexes), atomic
Conditions simultaneously, leading to unpredictable results. transactions updating wrong balances). operations, immutable data.
Frozen apps (e.g., database hangs
Two or more threads block forever, each waiting Timeouts, deadlock
Deadlocks when two queries lock each other’s
for the other to release a resource. detection, lock ordering.
tables).
Some threads get perpetually denied resources Slow performance (e.g., background Fair scheduling (round-
Starvation
due to unfair scheduling. tasks never completing). robin), priority adjustments.

Critical Section Problem:

The Critical Section Problem is a fundamental challenge in concurrent programming where multiple threads/processes compete
to access a shared resource (e.g., a variable, file, or hardware device) in a way that can lead to race conditions and inconsistent
data. For Example:
What Goes Wrong?
Time Transaction 1 (ATM) Transaction 2 (Online) Balance
T1 Reads balance (Rs.500) - Rs 500
T2 Paused by OS Reads balance (Rs 500) Rs 500
T3 - Withdraws 400 Rs 100
T4 Resumes, withdraws Rs 300 - -Rs 200 (Fraud!)

Critical Section:
Critical section refers to the code segment of a process, whereby it accesses shared resources.
CS Problem:
Consider a set of concurrent processes {P0,P1,P2…,Pn-1} sharing a common resource R, through the execution of their critical
sections. These processes have to cooperate with each other to provide a solution to the critical section problem.
Requirements of a CS Solution:
An ideal critical section solution should meet the following three requirements:
Critical section solution: general structure

There are three main types of solutions to the critical section problem:
1. Software Solutions
These are algorithmic approaches that rely solely on programming logic—no special hardware instructions are needed.
Examples:
 Peterson’s Algorithm (for two processes)
 Dekker’s Algorithm
 Lamport’s Bakery Algorithm (for multiple processes)

2. Hardware Solutions
These solutions use special hardware instructions that support atomic operations, which ensure mutual exclusion by preventing
interruption during key steps.
Examples:
 Test-and-Set
 Compare-and-Swap
 Disable/Enable Interrupts (in uniprocessor systems)

3. Operating System (OS) or Library-Based Solutions

Modern operating systems and languages offer high-level synchronization tools built on top of hardware or software primitives.
Examples:
 Mutexes (Locks)
 Semaphores
 Monitors
 Condition Variables
 Spinlocks
 Barriers

Mutual exclusion
 Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous
use of a common resource, such as a global variable, by pieces of computer code called critical sections.

 A mutex is also a common name for a program object that negotiates mutual exclusion among threads, also called a lock.
 Notes: S15-Software Solution to CS Problem: Dekker’s and Peterson’s Solutions

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Explain the steps involved in Dekker’s Open LMS (https://gulms.galgotiasuniversity.org/)
Algorithm. Go to course Operating System(R1UC403B)
2. Explain the steps involved in Peterson’s Algorithm. Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

There are three main types of solutions to the critical section problem:
1. Software Solutions
These are algorithmic approaches that rely solely on programming logic—no special hardware instructions are needed.
 Peterson’s Algorithm (for two processes)
 Dekker’s Algorithm

2. Hardware Solutions
These solutions use special hardware instructions that support atomic operations, which ensure mutual exclusion by preventing
interruption during key steps.
Examples:
 Test-and-Set
3. Operating System (OS) or Library-Based Solutions
Modern operating systems and languages offer high-level synchronization tools built on top of hardware or software primitives.
Examples:
 Semaphores

Peterson’s Algorithm:
 A Classic software-based solution to the critical-section problem known as Peterson’s solution.
 May not work correctly on modern computer architecture. How ever, It provides a good algorithmic description of
solving the critical-section problem and illustrates some of the complexities involved in designing software that
addresses the requirements of mutual exclusion, progress, and bounded waiting.
 Peterson’s solution is restricted to two processes that alternate execution between their critical sections and remainder
sections.
 It ensures that if a process is in the critical section, no other process must be allowed to enter it. This property is termed
mutual exclusion.
 If more than one process wants to enter the critical section, the process that should enter the critical region first must be
established. This is termed progress.
 There is a limit to the number of requests that processors can make to enter the critical region, provided that a process has
already requested to enter and is waiting. This is termed bounding.

Advantages of Peterson’s Solution

 Peterson's solution allows multiple processes to share and access a resource without conflict between the resources.
 Every process gets a chance of execution.
 It is simple to implement and uses simple and powerful logic.
 It can be used in any hardware as it is completely software dependent and executed in the user mode.
 Prevents the possibility of a deadlock.
Disadvantages of Peterson’s Solution
 The process may take a long time to wait for the other processes to come out of the critical region. It is termed as
Busy waiting.
 This algorithm may not work on systems having multiple CPUs.
 The Peterson solution is restricted to only two processes at a time.

Pseudocode:
do {
flag[i] = true;
turn = j;
while (flag[j] && turn == j); // busy wait
// critical section
flag[i] = false;

// remainder section
} while (true);
Line of Code Explanation Purpose
do { Starts an infinite loop for process i. Ensures continuous execution of the process.
Indicates that process i wants to enter the critical section
flag[i] = true; Sets flag[i] to true.
(CS).
turn = j; Assigns the value j to turn. Gives priority to process j to ensure fairness.
Busy-waits while:
Ensures mutual exclusion by making process i wait if j is in
while (flag[j] && turn == j); 1. flag[j] is true (process j wants CS).
or wants CS.
2. turn == j (it's j's turn).
// critical section Placeholder for critical section code. Code here accesses shared resources safely.
flag[i] = false; Sets flag[i] to false. Signals that process i has exited the CS, allowing j to enter.
// remainder section Placeholder for non-critical code. Code here executes outside the CS.
} while (true); Closes the infinite loop. Ensures the process repeats indefinitely.

For example:

Process 1 (P₁) Process 2 (P₂)

do { do {
flag[1] = true; flag[2] = true;
// Step 1: P₁ signals it wants to enter // Step 1: P₂ signals it wants to enter
turn = 2; turn = 1;
// Step 2: P₁ gives priority to P₂ // Step 2: P₂ gives priority to P₁
while (flag[2] && turn == 2); while (flag[1] && turn == 1);
// Step 3: Wait if P₂ is active & has priority // Step 3: Wait if P₁ is active & has priority
// CRITICAL SECTION (P₁ runs here) // CRITICAL SECTION (P₂ runs here)
flag[1] = false; flag[2] = false;
// Step 4: P₁ exits critical section // Step 4: P₂ exits critical section
// REMAINDER SECTION (Non-critical work) // REMAINDER SECTION (Non-critical
} while (TRUE); work)
} while (TRUE);

Dekker`s Algorithm:

If two processes attempt to enter a critical section at the same time, the algorithm will allow only one process in, based on whose
turn it is. If one process is already in the critical section, the other process will busy wait for the first process to exit. This is done
by the use of two flags, flag[0] and flag[1], which indicate an intention to enter the critical section and a turn variable which
indicates who has priority between the two processes.

Pseudocode
do {
flag[i] = true;
while (flag[j]) {
if (turn != i) {
flag[i] = false;
while (turn != i); // busy wait
flag[i] = true;
}
}
// critical section
turn = j;
flag[i] = false;
// remainder section
} while (true);
Line of Code Explanation Purpose
Ensures the process continuously attempts to enter
do { Starts an infinite loop for process i
critical section
Declares process i's intent to enter the critical section
flag[i] = true; Sets flag[i] to true
(CS)
Prevents both processes from entering CS
while (flag[j]) { Checks if process j also wants to enter CS
simultaneously
if (turn != i) { Verifies if it's not process i's turn Ensures fairness by yielding to the other process
flag[i] = false; Temporarily lowers process i's flag Allows process j to proceed if it's its turn
while (turn != i); Busy-waits until turn becomes i Ensures process i waits its turn
flag[i] = true; Re-raises process i's flag Re-attempts to enter CS after waiting
} Ends the yield condition block
} Exits the busy-wait loop when safe to proceed
// critical section Protected code section (accesses shared resources) Only one process executes this at a time
turn = j; Passes the turn to process j Ensures fairness by alternating turns
flag[i] = false; Lowers process i's flag Signals CS exit, allowing other processes to enter
// remainder section Non-critical code (doesn't access shared resources) Process performs other tasks
} while (true); Restarts the infinite loop Process continues operation

For example:
Process 1 (P₁) Process 2 (P₂)

do { do {
flag[1] = true; flag[2] = true;
// Step 1: P₁ signals it wants to enter // Step 1: P₂ signals it wants to enter
while (flag[2]) while (flag[1])
{ // Step 2: If P₂ is active, check turn { // Step 2: If P₁ is active, check turn
if (turn == 2) if (turn == 1)
{ // Step 3: If it's P₂'s turn, yield { // Step 3: If it's P₁'s turn, yield
flag[1] = false; flag[2] = false;
// Step 4: P₁ resets its flag // Step 4: P₂ resets its flag
while (turn == 2); while (turn == 1);
// Step 5: Wait until turn changes // Step 5: Wait until turn changes
flag[1] = true; flag[2] = true;
// Step 6: P₁ tries again // Step 6: P₂ tries again
} }
} }
// CRITICAL SECTION (P₁ runs here) // CRITICAL SECTION (P₂ runs here)
turn = 2; // Step 7: Pass turn to P₂ turn = 1; // Step 7: Pass turn to P₁
flag[1] = false; // Step 8: P₁ exits critical section flag[2] = false; // Step 8: P₂ exits critical section
// REMAINDER SECTION (Non-critical work) // REMAINDER SECTION (Non-critical work)
} while (TRUE); } while (TRUE);

In general above algorithms can be expressed as:

 Notes : S16- Semaphores, Test and Set operation

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define semaphores and Test & Set operations. Open LMS (https://gulms.galgotiasuniversity.org/)
2. Explain Semaphores and Test & Set operations. Go to course Operating System(R1UC403B)
Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

There are three main types of solutions to the critical section problem:
1. Software Solutions
These are algorithmic approaches that rely solely on programming logic—no special hardware instructions are needed.
Examples:
 Peterson’s Algorithm (for two processes)
 Dekker’s Algorithm

2. Hardware Solutions
These solutions use special hardware instructions that support atomic operations, which ensure mutual exclusion by preventing
interruption during key steps.
Examples: Test-and-Set

3. Operating System (OS) or Library-Based Solutions

Modern operating systems and languages offer high-level synchronization tools built on top of hardware or software primitives.
Examples: Semaphores

Software solutions already covered in session 15. In this session we are going to explore Semaphores and Test & Set operations.

Operating System (OS) or Library-Based Solutions :

Semaphore:
Semaphores are a synchronization mechanism used in concurrent programming to control access to shared resources by multiple
processes or threads. They were introduced by Edsger Dijkstra in 1965 to solve critical section problems and avoid race conditions.
A semaphore is a special integer variable that apart from initialization, is accessed only through two standard operations.
wait() and signal()
A simple way to understand wait() and signal() operations are:
wait():
Decrements the value of semaphore variable by 1. If the value becomes negative or 0, the process executing wait() is blocked (like
sleep), i.e., added to the semaphore's queue.
signal():
Increments the value of semaphore variable by 1. After the increment, if the pre-increment value was negative (meaning there are
processes waiting for a resource), it transfers a blocked process from the semaphore's waiting queue to the ready queue. (like Wake
up)

Semaphore Operations
Implementation of wait:
wait (S){
value--;
if (value < 0) {
add this process to waiting queue
block(); }
}
Implementation of signal:
Signal (S){
value++;
if (value <= 0) {
remove a process P from the waiting queue
wakeup(P); }
}

Problems Solved by Semaphores

(A) Mutual Exclusion (Mutex)
(B) Process Synchronization (Order Enforcement)
(C) Producer-Consumer Problem (Bounded Buffer)
(D) Readers-Writers Problem

There are two types of semaphores as follows:

Binary Semaphore:
Semaphores which are restricted to the values 0 and 1 (or locked/unlocked, unavailable/available, up/down) are
called binary semaphores.
Example:
Semaphore S = 1; // Initially available
Process P1:
wait(S); // Enters critical section
// Critical Section
signal(S); // Exits critical section

Counting Semaphore:
Semaphores which allow an arbitrary resource count are called counting semaphores(can have possible values more than two)
Example:
Semaphore S = 5; // 5 resources available

Process P1:
wait(S); // Decrements S (if S > 0)
// Uses resource
signal(S); // Releases resource (increments S)

Limitations of Semaphores
 Deadlocks: If processes wait in a circular manner.
 Starvation: Some processes may never get access.
 Priority Inversion: A high-priority process may wait for a low-priority one.

Real-World Applications
 Operating Systems: Process scheduling, memory management.
 Database Systems: Transaction locking.
 Embedded Systems: Resource allocation in RTOS.
 Traffic Control: Managing shared lanes in automated systems.
Hardware Solutions:
There are three algorithms in the hardware approach of solving Process Synchronization problem: Test and Set ,Swap ,Unlock and
Lock
Introduction to Test-and-Set
The Test-and-Set (TAS) operation is a hardware-supported atomic instruction used to implement synchronization mechanisms
like semaphores. It ensures mutual exclusion in concurrent programming by allowing only one process/thread to access a critical
section at a time.
Key Properties:
 Atomicity: The operation executes without interruption (CPU guarantees no interference).
 Used for Mutual Exclusion: Helps prevent race conditions in multi-threaded environments.
 Hardware Implementation: Typically provided by the CPU (e.g., xchg in x86, ldrex/strex in ARM).

Test and Set Pseudocode –

//Shared variable lock initialized to false
boolean lock;
boolean TestAndSet (boolean &target){
boolean rv = target;
target = true;
return rv;
}

while(1){
while (TestAndSet(lock));
critical section
lock = false;
remainder section
}
How Test-and-Set Works
The characteristics of this synchronization mechanism are-
 It ensures mutual exclusion.
 It is deadlock free.
 It does not guarantee bounded waiting and may cause starvation.
 It suffers from spin lock.
 It is not architectural neutral since it requires the operating system to support test-and-set instruction.
 It is a busy waiting solution which keeps the CPU busy when the process is actually waiting.

**C program that simulates Semaphore: pthread_join(t1, NULL);

#include <stdio.h> pthread_join(t2, NULL);
#include <pthread.h> return 0;
#include <unistd.h> }

// Binary semaphore using mutex **C program that simulates Test-and-Set operations
typedef struct { #include <stdio.h>
pthread_mutex_t mutex; #include <pthread.h>
int value; #include <stdatomic.h>
} Semaphore;
// Atomic Test-and-Set lock
void init(Semaphore *s, int value) { typedef struct {
s->value = value; atomic_flag flag;
pthread_mutex_init(&s->mutex, NULL); } TASLock;
}
void init_lock(TASLock *lock) {
void wait(Semaphore *s) { atomic_flag_clear(&lock->flag);
pthread_mutex_lock(&s->mutex); }
while (s->value <= 0) {
pthread_mutex_unlock(&s->mutex); void lock(TASLock *lock) {
usleep(1000); // Prevent busy-waiting while (atomic_flag_test_and_set(&lock->flag)) {
pthread_mutex_lock(&s->mutex); usleep(1000); // Reduce CPU usage
} }
s->value--; }
pthread_mutex_unlock(&s->mutex);
} void unlock(TASLock *lock) {
atomic_flag_clear(&lock->flag);
void signal(Semaphore *s) { }
pthread_mutex_lock(&s->mutex);
s->value++; // Example usage
pthread_mutex_unlock(&s->mutex); TASLock tas_lock;
}
void* thread_func(void* arg) {
// Example usage lock(&tas_lock);
Semaphore sem; printf("Thread %ld entered critical section\n", (long)arg);
sleep(1); // Simulate work
void* thread_func(void* arg) { unlock(&tas_lock);
wait(&sem); return NULL;
printf("Thread %ld entered critical section\n", (long)arg); }
sleep(1); // Simulate work
signal(&sem); int main() {
return NULL; init_lock(&tas_lock);
} pthread_t t1, t2;
pthread_create(&t1, NULL, thread_func, (void*)1);
int main() { pthread_create(&t2, NULL, thread_func, (void*)2);
init(&sem, 1); // Binary semaphore (mutex) pthread_join(t1, NULL);
pthread_t t1, t2; pthread_join(t2, NULL);
pthread_create(&t1, NULL, thread_func, (void*)1); return 0;
pthread_create(&t2, NULL, thread_func, (void*)2); }
 Notes: S17-Classical problems of concurrency : Dining Philosopher’s problem

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Explain the role of synchronization in Open LMS (https://gulms.galgotiasuniversity.org/)
concurrent processing within operating Go to course Operating System(R1UC403B)
systems. (Unistructural). Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
2. Describe the Dining Philosophers Problem. Click on “Session-wise Pre & Post Class Assessments”
(Multistructural).  Attempt Assessment quizzes.

1. Dining Philosopher’s problem

Problem statement :
The Dining Philosophers problem is a classic synchronization problem in computer science that illustrates challenges in resource
allocation and deadlock avoidance. It was formulated by Edsger Dijkstra in 1965.
Scenario:
 Five philosophers sit around a circular table.
 Each philosopher alternates between thinking and eating.
 There is one chopstick placed between each pair of philosophers (total: 5 chopsticks).
 To eat, a philosopher must pick up both adjacent chopsticks (left and right).
 If a philosopher cannot get both chopsticks, they wait (block).

How can you design rules to ensure:

1. Every philosopher gets a fair chance to eat?
2. No deadlocks occur (no infinite waiting)?
3. No philosopher starves indefinitely?

Key Challenges:
1. Deadlock:
 If all philosophers pick up their left chopstick simultaneously, none can pick up the right one.
 Result: All philosophers starve (infinite waiting).
 (Like threads holding partial resources and waiting indefinitely.)
2. Starvation
 Some philosophers may never get both chopsticks due to unfair scheduling.
 (Like low-priority threads never getting CPU time.)
3. Race Conditions
 Uncontrolled access to chopsticks → data corruption (e.g., two philosophers grabbing the same
chopstick).

The structure of Philosopher i:

while (true) {
wait(chopstick[i]); // Pick up left chopstick
wait(chopstick[(i + 1) % 5]); // Pick up right chopstick
// Eat (critical section)
signal(chopstick[i]); // Release left chopstick
signal(chopstick[(i + 1) % 5]); // Release right chopstick
// Think (non-critical section)
}
This code represents a naive implementation of the Dining Philosophers problem, which leads to a deadlock if not modified. Let's
break it down:

Step-by-Step Explanation
Code Explanation

while (true) { ... } Infinite loop where each philosopher continuously thinks and eats

wait(chopstick[i]); Attempts to pick up left chopstick (blocks if unavailable)

wait(chopstick[(i+1)%5]); Attempts to pick up right chopstick (circular table) - may deadlock

// eat Critical section (requires both chopsticks)

signal(chopstick[i]); Releases left chopstick

signal(chopstick[(i+1)%5]); Releases right chopstick

// think Non-critical section (no synchronization needed)

Why This Causes Deadlock

 If all 5 philosophers simultaneously pick up their left chopstick:
o None can pick up the right chopstick (since each right chopstick is held by the next philosopher).
o Result: All philosophers wait forever → deadlock.

One of the approaches to avoid deadlock

Odd-numbered philosophers pick left first, even-numbered pick right first.
if (i % 2 == 0)
{
wait(chopstick[i]); // Left first for even
wait(chopstick[(i + 1) % 5]);
}
else
{
wait(chopstick[(i + 1) % 5]); // Right first for odd
wait(chopstick[i]);

Dining Philosopher’s problem :Solution in C language:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>

#define NUM_PHILOSOPHERS 5

sem_t chopsticks[NUM_PHILOSOPHERS]; // One semaphore per chopstick

sem_t mutex; // Ensures only one philosopher picks up chopsticks at a time

void *philosopher(void *arg);

void eat(int id);

int main() {
pthread_t philosophers[NUM_PHILOSOPHERS];
int ids[NUM_PHILOSOPHERS];

// Initialize semaphores
sem_init(&mutex, 0, 1);
for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
sem_init(&chopsticks[i], 0, 1); // Each chopstick starts as available (1)
}

// Create philosopher threads

for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
ids[i] = i;
pthread_create(&philosophers[i], NULL, philosopher, &ids[i]);
 }

// Wait for threads to finish (though they run indefinitely)

for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
pthread_join(philosophers[i], NULL);
}

// Clean up semaphores
sem_destroy(&mutex);
for (int i = 0; i < NUM_PHILOSOPHERS; i++) {
sem_destroy(&chopsticks[i]);
}

return 0;
}
void *philosopher(void *arg) {
int id = *(int *)arg;
while (1) {
printf("Philosopher %d is thinking...\n", id);
sleep(1); // Thinking time

printf("Philosopher %d is hungry and tries to pick up chopsticks...\n", id);

// Use mutex to prevent deadlock (only one philosopher picks up chopsticks at a time)
sem_wait(&mutex);

// Pick up left chopstick

sem_wait(&chopsticks[id]);
printf("Philosopher %d picked up left chopstick (%d)\n", id, id);

// Pick up right chopstick

sem_wait(&chopsticks[(id + 1) % NUM_PHILOSOPHERS]);
printf("Philosopher %d picked up right chopstick (%d)\n", id, (id + 1) % NUM_PHILOSOPHERS);

sem_post(&mutex); // Release the mutex after picking up both chopsticks

// Eat
eat(id);

// Put down chopsticks

sem_post(&chopsticks[id]);
printf("Philosopher %d put down left chopstick (%d)\n", id, id);

sem_post(&chopsticks[(id + 1) % NUM_PHILOSOPHERS]);
printf("Philosopher %d put down right chopstick (%d)\n", id, (id + 1) % NUM_PHILOSOPHERS);
}
}
void eat(int id) {
printf("Philosopher %d is eating...\n", id);
sleep(2); // Simulate eating time
}
Some other Classical problems of concurrency
2. Producer Consumer problem (Bounded buffer problem):
The Producer-Consumer problem is a classical multi-process synchronization problem, that is we are trying to achieve
synchronization between more than one process. It is also known as Bounded Buffer Problem in (multi-process synchronization
problem). Consider two processes Producer and Consumer , who share common, fixed size buffer. Producer puts information into
the buffer. Consumer consume this information from buffer. Trouble arises when the producer wants to put a new item in the buffer,
but it is already full. And consumer wants to remove a item from buffer, but it is already empty.
Problem statement:
1. A producer must not overwrite a full buffer.
2. A consumer must not consume an empty buffer.
3. Producer and consumer must access buffers in a mutually exclusive manner.
4. Information must be consumed in the same order in which it is put in to buffers(FIFO)
Sleeping barber problem:

Problem statement:
1. Hair cutting saloon has N chair in its waiting room and 1 chair in barber’s cabin for giving hair cut
2. If there is no customer in the saloon, barber goes to sleep.
3. When a customer arrives at the saloon, one of the following happens
(a). If there is no customer, customer walks in to cabin, wakes up the barber, and starts getting haircut.
(b)When customer is already getting hair cut in the cabin then the customer looks for an empty chair in the
waiting room. if yes then he occupy and wait if no he walks away without haircut.
4. Order will be FCFS.
 Notes : S18- Deadlock System Models

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define deadlock and Deadlock System Model. Open LMS (https://gulms.galgotiasuniversity.org/)
(Unistructural). Go to course Operating System(R1UC403B)
2. Explain the conditions required for deadlock Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
to occur (Relational). Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Introduction to Deadlock
Deadlock is a situation in which two or more processes are unable to proceed because each is waiting for the other to release a
resource. Deadlock is a significant problem in operating systems because it can lead to system halts and resource wastage.
Understanding deadlock is essential for designing efficient and reliable systems.
Imagine four cars arriving at a four-way intersection at the same time, each coming from a different direction. Each driver politely
waits for the others to go first, but no one moves. As a result, all cars remain stuck indefinitely. This is called Deadlock situation.
The processes are the cars. The resources are the spaces occupied by the cars

In other words A deadlock consists of a set of blocked processes, each holding a resource and waiting to acquire a resource held
by another process in the set.
For Example: two processes each want to record a scanned document on a CD. process 1 requests for scanner & gets it. process 2
requests for CD writer & gets it. process 1 requests CD writer but is blocked. process 2 requests scanner but is blocked. At this
point both processes are blocked and will remain so forever, this situation is called a deadlock

For example, in the below diagram, Process 1 is holding Resource 1 and waiting for resource 2 which is acquired by process 2,
and process 2 is waiting for resource 1.

System model:
In the context of deadlocks, "System Models" refer to the formal representations of how processes, resources, and their interactions
are structured in an operating system. These models help in analyzing, detecting, preventing, and resolving deadlocks systematically.
Purpose of System Models in Deadlock
System models provide:
 A theoretical framework to understand deadlock conditions.
 Mathematical representations (like graphs) to detect deadlocks.
 Algorithms (e.g., Banker’s Algorithm) to avoid deadlocks.
 Strategies for prevention, avoidance, and recovery.

1. A process may utilize a resource in the following sequence:

REQUEST: The process requests the resource. If the request cannot be granted immediately (if the resource is being used by another
process), then the requesting process must wait until it can acquire the resource.
USE: The process can operate on the resource .if the resource is a printer, the process can print on the printer.
RELEASE: The process release the resource.
A system consists of a finite number of resources to be distributed among a number of competing processes. The resources are
partitioned into several types, each consisting of some number of identical instances. Memory space, CPU cycles, files, I/O devices
are examples of resource types. If a system has 2 CPUs, then the resource type CPU has 2 instances. A process must request a
resource before using it and must release the resource after using it. A process may request as many resources as it requires to carry
out its task. The number of resources as it requires to carry out its task. The number of resources requested may not exceed the total
number of resources available in the system. A process cannot request 3 printers if the system has only two.

2. RESOURCE ALLOCATION GRAPH

The existence of deadlock in the system is shown by using a graph named as RAG.
It is a directed graph. RAG consists of several no. of nodes and edges. It contains
i) Process node :

ii) Resource node :

The bullet symbol within the resource is known as instances of that resource.
Instance of resources means identical resources of same type.
There exist 2 kinds of edges.
i) Request edge: Whenever a process request for resources then it is called a request edge. A request edge is drawn from the process
to resource.
ii) Allocation / assignment edge : Whenever a resource is allocated to a process the request edge is converted to an assignment
edge from the instance of the resource to the process.

The sets P, R, E:
P= {P1, P2, P3}
R= {R1, R2, R3, R4}
E= {P1 ->R1, P2 ->R3, R1 ->P2, R2 ->P2, R2 ->P1, R3 ->P3}

 This graph consists of a set of vertices V and a set of edges E. the set of vertices V is partitioned into 2 different types of
nodes: P = {P1, P2….Pn}, the set consisting of all the active processes in the system. R= {R1, R2….Rm}, the set consisting
of all resource types in the system.
 A directed edge from process Pi to resource type Rj is denoted by Pi ->Rj. It signifies that process Pi has requested an
instance of resource type Rj and is currently waiting for that resource.
 A directed edge from resource type Rj to process Pi is denoted by Rj ->Pi, it signifies that an instance of resource type Rj
has been allocated to process Pi.
 A directed edge Pi ->Rj is called a requested edge.
 A directed edge Rj->Pi is called an assignment edge.
 We represent each process Pi as a circle, each resource type Rj as a rectangle.
 Since resource type Rj may have more than one instance. We represent each such instance as a dot within the rectangle. A
request edge points to only the rectangle Rj.
 An assignment edge must also designate one of the dots in the rectangle.
 When process Pi requests an instance of resource type Rj, a request edge is inserted in the resource allocation graph.
 When this request can be fulfilled, the request edge is instantaneously transformed to an assignment edge.
 When the process no longer needs access to the resource, it releases the resource, as a result, the assignment edge is deleted.
NOTE:-
If the RAG contains NO CYCLE , then there is NO DEADLOCK in the system.
If the RAG contains a CYCLE, then there MAY BE A DEADLOCK in the system.
If the resources have exactly one instance then a cycle indicates a deadlock.
If the resources have multiple instances per resource then a cycle indicates that “there may be deadlock”.

Deadlock Characterization/ REASONS/NECESSARY CONDITIONS FOR ARISING DEADLOCK:

A deadlock situation can arise if the following four condition hold simultaneously in the system.
1. Mutual exclusion
2. Hold and wait
3. No pre-emption
4. Circular wait

1.Mutual exclusion:
 At least one resource type in the system which can be used in non-shareable mode (i.e. one at a time) for example
printer.
 Because many resources can be shared by more than one process at a time (e.g., Memory location).
 In the diagram below, there is a single instance of Resource 1 and it is held by Process 1 only.

2.Hold and Wait:

 Processes are allowed to request for new resources without releasing the resources they are currently holding.
 In the diagram given below, Process 2 holds Resource 2 and Resource 3 and is requesting the Resource 1 which is held
by Process 1.

3.No pre-emption:
 A resource cannot be preempted from a process by force. A process can only release a resource voluntarily.
 In the diagram below, Process 2 cannot preempt Resource 1 from Process 1. It will only be released when Process 1
relinquishes it voluntarily after its execution is complete.
4. Circular wait:
Two or more processes must form a circular chain in which each process is waiting for a resource that is held by the next member
of the chain.

All four of these conditions must hold simultaneously in a system for a deadlock to occur.

Examples of Deadlock in Action

Real-Life Example Explanation

1. Four-Way Traffic Four cars arrive at an intersection simultaneously, each waiting for another to move first. Since
Gridlock none yield, all remain stuck indefinitely (circular wait + mutual exclusion).

2. Dining Philosophers Five philosophers share forks, but each need two to eat. If all pick up one fork and wait, no one
Problem can proceed (hold & wait + circular dependency).

3. Office Printer- Employee A holds the printer and waits for the scanner, while Employee B holds the scanner
Scanner Deadlock and waits for the printer. Both are stuck (resource contention).

4. Construction Crane Two cranes need each other’s space to lift a beam but neither moves, halting progress (mutual
Standoff exclusion + no Preemption).

5. Bank Transaction Account X waits for a transfer from Account Y, which is itself waiting for X to release a lock
Deadlock (circular dependency).

6. Team Project Alice won’t submit code until Bob reviews it, but Bob won’t review until Alice submits (cyclic
Dependency wait).

7. Single-Track Train Two trains face each other on a single track, each waiting for the other to reverse (no
Deadlock Preemption).

8. Video Game Loot Player 1 holds a sword and waits for a shield (held by Player 2), who waits for the sword (hold
Standoff & wait).

9. Kitchen Knife & Chef A holds a knife and waits for a cutting board (held by Chef B), who waits for the knife (all
Cutting Board 4 conditions met).
 Notes : S19-Deadlock Prevention and Avoidance

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define deadlock prevention and avoidance . Open LMS (https://gulms.galgotiasuniversity.org/)
2. Explain Banker`s algorithm in context Go to course Operating System(R1UC403B)
deadlock prevention and avoidance Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Strategies to handle deadlocks:

1. Prevention – constraints are imposed on the way in which processes request resources in order to prevent deadlocks.
2. Avoidance – resources are carefully allocated to avoid deadlocks.
3. Detection and recovery – deadlocks are allowed to occur and a detection algorithm is used to detect them. After
deadlock is detected, it is resolved by certain means.
4. Ignore – do nothing, just ignore the problem.

Deadlock Prevention
Deadlocks can be prevented from occurring by preventing one of the necessary four conditions. i.e. mutual exclusion, hold and wait,
no pre-emption and circular wait. If one of the conditions can be prevented from occurring then deadlock will not occur.
Eliminate Mutual Exclusion
It is not possible to dis-satisfy the mutual exclusion because some resources, such as the tape drive and printer, are inherently non-
shareable.
Eliminate Hold and wait
Allocate all required resources to the process before the start of its execution, this way hold and wait condition is eliminated but it
will lead to low device utilization. for example, if a process requires printer at a later time and we have allocated printer before the
start of its execution printer will remain blocked till it has completed its execution. The process will make a new request for resources
after releasing the current set of resources. This solution may lead to starvation.
Eliminate No Preemption
Preempt resources from the process when resources required by other high priority processes.
Eliminate Circular Wait
Each resource will be assigned with a numerical number. A process can request the resources increasing/decreasing. order of
numbering. For Example, if P1 process is allocated R5 resources, now next time if P1 ask for R4, R3 lesser than R5 such request
will not be granted, only request for resources more than R5 will be granted.

Deadlock Avoidance
To avoid deadlock it is required to keep the additional information of the process i.e. the operating System will be given prior
information about the process such that
- Which process will request for which resource.
- At what time and for how long time.
So that the operating System find out a sequence of execution. If all the process execute in the sequence then system will never
enter into a deadlock state.

SAFE STATE: A state is safe if the system can allocate the available resources to each process in same order and still avoid deadlock.
SAFE SEQUENCE: A sequence of processes (P1, P2, and P3----------Pn) is a safe sequence if the available resources can be allowed
to the processes in that sequence and avoid deadlock. If no safe sequence exists the system is said to be unsafe state. An unsafe
state may lead to a deadlock.

If system contain one type of resource having multiple instances

Ex. Suppose a system contains 12 tape drives

Process Maximum Allocation Need

P0 10 5 5
P1 4 2 2
P2 9 2 7
Free 12-9 = 3
If the system will always remain in safe state then deadlock will never occur. So, when a process requests for a resource that is
currently available the system must decide whether that resource will be allocated or the process will wait. The request will be
granted only if the allocation leaves the system in a safe state. This method is used only when the system contain one type of resource
having multiple instances.
If the system contains different types of resources but each is having single instances.
We can use Resource allocation graph for deadlock avoidance.
 In this graph, beside assignment edge and request edge, third edge known as “claim edge” is added.
 A claim edge from process Pi to Ri indicates that the process Pi may request for resource Rj in FUTURE. Claim edge is
similar to request edge but it is represented as dashed line,
 If a process request for resource Rj then that request only be granted if by converting the requesting edge Pi->Rj to the
assignment edge Rj->Pi does not form a cycle.
 If there are two claim edges for the same resource then it can avoid. If only one of the processes is allocated the resource
R1 then a deadlock can arise.

If the system contains Multiple Resources having multiple instances

we apply Banker’s algorithm to avoid Deadlock.
When a new process enters into the system
- It must declare maximum number of instances of each resource type that it may need.
- This number should be less than the total number of resources.
When a process requests a set of resources, the system must determine:-
- Whether the allocation of these resources will leave the system in a safe state.

Banker’s algorithm consists of two parts. - Safety algorithm & - Resource request algorithm.

Safety algorithm
The safety algorithm is used to determine whether a system is in safe state or not.
The algorithm uses several data structures such as vector & matrixes. Ex. Let in a system there are ‘n’ processes and ‘m’ resources.
1) AVAILABLE: - It is an array/vector of length ‘m’ indicates the number of available resources of each type. If available [J] =k
means there are k instances of resource type Rj available.
2) MAX: - It is am matrix defines the maximum demand of each process. If max [i,j]=k, then the process Pi may request at most k
instances of resource type Rj.
3) ALLOCATION: - It is an n*m matrix defines the number of resources of each type currently allocated to each process. Ex. If
allocation [i,j]=k, then process Pi is currently allocated k instances of resource to Rj.
4) NEED: - It is an n*m matrix indicates the remaining resources need each process if need [i,j]=k, then the process Pi may need k
more instances of resource type Rj to complete its task. Need[i,j]=max[i,j] – allocation[i,j].
Algorithm: 1.Let Work and Finish be vectors of length m and n, respectively. Initialize:
Work = Available
Finish [i] = false for i = 0, 1, …, n- 1
2.Find an i such that both:
(a) Finish [i] = false
(b) Needi ≤ Work
If no such i exists, go to step 4
3.Work = Work + Allocationi
Finish[i] = true
go to step 2
4.If Finish [i] == true for all i, then the system is in a safe state
Resource request algorithm
The resource request algorithm is used determine whether or not a request generated by a process for a resource, would lead the
system to an unsafe state.
Resource-Request Algorithm for Process Pi
Requesti = request vector for process Pi. If Requesti [j] = k then process Pi wants k instances of resource type Rj
1.If Requesti ≤ Needi go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim
2.If Requesti ≤ Available, go to step 3. Otherwise Pi must wait, since resources are not available
3.Pretend to allocate requested resources to Pi by modifying the state as follows:
Available = Available – Requesti;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;
If safe ⇒ the resources are allocated to Pi
If unsafe ⇒ Pi must wait, and the old resource-allocation state is restored
Problem:
Considering a system with 5 processes P0 to P4 and three resource types A,B,C. Resource type A has 10 instances, B has 5
instances ,C has 7 instances. Suppose at time t0 following snapshot of the system has been taken:
Process Allocation Max Available
ABC ABC ABC
P0 0,1,0 7,5,3 3,3,2
P1 2,0,0 3,2,2
P2 3,0,2 9,0,2
P3 2,1,1 2,2,2
P4 0,0,2 4,3,3

(i) What will be the content of Need matrix?

(ii) Is the system in safe state? If yes, then what is the safe sequence?
(iii) What will happen if process Pi requests one additional instance of resource type A and two instance of C.(1,0,2).
(iv) If a request (3,3,0) by process P4 arrives in the state defined by (iii),can it be granted immediately?
(v) If a request (0,2,0)by process P0 arrives then check whether it is granted or not?

Solution:
(i) Matrix:
Need[i][j]
Process max[i][j]-allocation[i][j]
A B C
P0 7,5,3-0,1,0 7 4 3
P1 3,2,2-2,0,0 1 2 2
P2 9,0,2-3,0,2 6 0 0
P3 2,2,2-2,1,1 0 1 1
P4 4,3,3-0,0,2 4 3 1

(ii) Is the system in safe state? If yes, then what is the safe sequence?
Solution: Applying safety algorithm: Iteration -1: (R=Right, W=Wrong)
Process 1. 2. 3. 4.
(Pi) Initialize: Find an i such that Work=work+allocationi If finish[i]=true for all i
work=Available both Finish[i]=true Then the system is in
Finish[i] =false Finish[i]=false Go to step (2) safe state.
for i=1,2,3,…n. Needi<=work are
right then go to step
3.
If no such i exists,
go to step 4

P0 Work=3,3,2 Finish[0]=falseR NA P0 must wait.

7,4,3<=3,3,2W Finish[0]=False
so go to 4 Set for iteration-2
P1 Work=3,3,2 Finish[1]=falseR Work=3,3,2+2,0,0=5,3,2 P1 can be taken in safe
1,2,2<=3,3,2R Finish[1]=true sequence.
Go to 3 as both are R Finish[1]=true
Safe sequence number=1
P2 Work=5,3,2 Finish[2]=falseR NA P2 must wait
6,0,0<=5,3,2W Finish[2]=false
so go to 4 Set for iteration-2

P3 Work=5,3,2 Finis[3]=falseR Work=5,3,2+2,1,1=7,4,3 P3 can be taken in safe

0,1,1<=5,3,2R Finish[3]=true sequence
Go to 3 as both are R. Finish[3]=true
Safe sequence number=2

P4 Work=7,4,3 Finish[4]=falseR Work=7,4,3+0,0,2=7,4,5 P4 can be taken in safe

4,3,1<=7,4,3R Finish[4]=true sequence Finish[4]=true
Go to 3 as both are R. Safe sequence number=3
Result after Iteration-1 Safe Sequence <P1,P3,P4,

After iteration-1, P0,P2 are waiting. Now for iteration two we have current available(745) in this case either P0 or P2 can
be kept in safe sequence. In this particular example we are taking P2 first for consideration:
Iteration -2:
Process 1. 2. 3. 4.
(Pi) Initialize: Find an i such that both Work=work+allocationi If finish[i]=true for all i
work=Available Finish[i]=false Finish[i]=true Then the system is in
Finish[i] =false Needi<=work Go to step (2) safe state.
for i=1,2,3,…n. If no such i exists, go to
step(4)

P2 Work=7,4,5 Finish[2]=falseR Work=7,4,5+3,0,2=10,4, Now P2 can be taken in

6,0,0<=7,4,5right so go 7 safe sequence with
to 3 Finish[2]=true sequence number=4
Finish[2]=true

P0 Work=10,4,7 Finish[0]=falseR Work=10,4,7+0,1,0=10,5 Now P0 can be taken in

7,4,3<=10,4,7R ,7 safe sequence.
so go to 3 Finish[0]=true sequence number=5
Finish[0]=true
Result after Iteration-2(Final Result) Safe Sequence <P1,P3,P4,P2,P0>

(iii)What will happen if process P1 requests one additional instance of resource type A and two instance of C.(1,0,2).
Solution:
Since P1 request some additional instance such that requesti=(1,0,2) We have available (3, 3, 2) now 1,0,2<=3,3,2 yes of course
request may be granted.
Now applying Resource request algorithm:
1. If requesti<=Needi 1,0,2<=1,2,2 Yes
Go to step 2; otherwise raise an error condition, since the process has exceeded its maximum claim.
2. If requesti<=available 1,0,2<=3,3,2 Yes
Go to step 3; otherwise, Pi must wait, since the resources are not available.
3. Have the system pretend to have allocated the requested resources to process Pi by modifying the state as follows:
Available=available-requesti Available=3,3,2-1,0,2=2,3,0
Allocationi= Allocationi+ requesti Allocation1=2,0,0+1,0,2=3,0,2
Needi= Needi- requesti Need1=1,2,2-1,0,2=0,2,0
If resulting resource allocation state is safe the transaction is completed and process P i is allocated its resources .if not
then Pi must wait for requesti and the old R-A state is restored.
Now new snapshot will be
Process Allocation need Available
ABC ABC ABC
P0 0,1,0 7,4,3 2,3,0
P1 3,0,2 0,2,0
P2 3,0,2 6,0,0
P3 2,1,1 0,1,1
P4 0,0,2 4,3,1
*Now we check again it`s safety sequence and got that it is safe to grant the request P1 immediately .Applying safety
algorithm we got the safe sequence<P1, P3, P4, P0, P2>.

(iv) If a request (3, 3, 0) by process P4 arrives in the state defined by (iii), can it be granted immediately?
Solution: Available=2,3,0, Request=3,3,0
3,3,0<=2,3,0 False so request of P4 can’t be granted as resources are unavailable.

(v)If a request (0, 2, 0) by process P0 arrives then check whether it is granted or not?
Solution: Available=2,3,0, Request=0,2,0
0,2,0<=2,3,0 True so request of P0 can be granted as resources are available. And new system will be like:
Available=available-requesti Available=2,3,0-0,2,0=2,1,0
Allocationi= Allocationi+ requesti Allocation1=0,1,0+0,2,0=0,3,0
Needi= Needi- requesti Need1=7,4,3-0,2,0=7,2,3
Process Allocation need Available
ABC ABC ABC
P0 0,3,0 7,2,3 2,1,0
P1 3,0,2 0,2,0
P2 3,0,2 6,0,0
P3 2,1,1 0,1,1
P4 0,0,2 4,3,1
Applying safety algorithm on this system found that system will be in unsafe state.
Question:
Consider the following snapshot for the banker's algorithm:

1. calculate the content of the need matrix?

2. Check if the system is in a safe state?

Question:
 Notes : S20- Recovery from Deadlock

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Explain the basic concept of Deadlock Open LMS (https://gulms.galgotiasuniversity.org/)
Recovery. Go to course Operating System(R1UC403B)
2. Describe the strategies used for deadlock Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
recovery. Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Recovery from Deadlock

Once a deadlock is detected, the OS must recover it. There are two main approaches to recover from a deadlock:
Process Termination – Killing one or more processes to free up resources.
Resource Preemption – Forcibly taking resources from some processes and reallocating them.

Process Termination
This method used to recover from deadlock. We use one of two methods for process termination. a. Abort all deadlock processes b.
Abort one by one process until the deadlock cycle is broken

Resource Preemption
There are three methods to eliminate deadlocks using resource pre-emption. They are-  Selection of a victim.  Roll back
.
Some Real-life scenarios related to deadlock recovery
# Scenario Deadlock Situation Possible Recovery Strategies OS Equivalent

1. Librarian forcibly reclaims a

book (Preemption).
Library Book Students hold books in a 2. Student gives up and leaves Resource allocation
1
Standoff circular wait. (Termination). deadlock.
3. New rule: "No holding while
waiting" (Prevention).

1. Traffic cop reroutes one car

Four cars block each other at (Preemption). Thread/process
2 Traffic Gridlock
an intersection. 2. One car reverse (Rollback). contention.
3. Add traffic lights (Avoidance).

1. Waiter enforces fork limits

(Arbitration).
Dining Philosophers starve holding 2. Philosopher times out Circular wait in shared
3
Philosophers one fork each. (Termination). resources.
3. Odd/even fork pickup order
(Ordering).

1. Foreman takes a tool

(Preemption).
Construction Workers need two tools but 2. Hire extra workers (Resource
4 Hold-and-wait deadlock.
Team hold one each. addition).
3. Require all tools upfront
(Prevention).

1. Admin teleports a player

(Preemption).
Multiplayer Players block paths in a 2. Player disconnects Deadlock in game
5
Game dungeon. (Termination). servers.
3. Design non-blocking paths
(Avoidance).

1. Dispatcher reroutes a train

(Preemption). Network/resource
6 Train Deadlock Trains wait on circular tracks.
2. One train backs up (Rollback). deadlock.
3. Use sidings (Resource addition).

1. IT revokes printer access

(Preemption).
Office Printer Employees hold
7 2. Employee gives up I/O device contention.
War printers/paper in a cycle.
(Termination).
3. Central print queue (Scheduling).

1. Director confiscates props

(Preemption).
Actors hoard props needed by 2. Actor exits the scene
8 Theater Props Memory/object deadlock.
others. (Termination).
3. Assign props beforehand
(Prevention).

1. Supervisor reallocates parts

Robots wait for parts held by (Preemption). Manufacturing process
9 Robot Factory
others. 2. Shut down a robot (Termination). deadlock.
3. Use assembly lines (Avoidance).
 Notes : S21- Inter-Process Communication (IPC)

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define Inter-Process Communication (IPC) Open LMS (https://gulms.galgotiasuniversity.org/)
and its role in operating systems. Go to course Operating System(R1UC403B)
2. Describe the different methods of IPC. Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

IPC:
Processes in system can be independent or cooperating.
Independent processes cannot affect or be affected by the execution of another process.
Cooperating processes can affect or be affected by the execution of another process.
Inter-process communication (IPC) is a set of methods for the exchange of data among multiple threads in one or more processes.
Processes may be running on one or more computers connected by a network. IPC may also be referred to as inter-thread
communication and inter-application communication.

Why IPC
There are several reasons for providing an environment that allows process cooperation:
Information sharing: Since several users may be interested in the same piece of information (for instance, a shared file), we must
provide an environment to allow concurrent access to these types of resources.
Computation speedup: If we want a particular task to run faster, we must break it into subtasks, each of which will be executing
in parallel with the others. Such a speedup can be achieved only if the computer has multiple processing elements (such as CPUS
or I/O channels).
Modularity: We may want to construct the system in a modular fashion, dividing the system functions into separate processes or
threads.
Convenience: Even an individual user may have many tasks on which to work at one time. For instance, a user may be editing,
printing, and compiling in parallel.

Method of Communication:
The communication between these processes can be seen as a method of co-operation between them. Processes can communicate
with each other using these two ways:
a. Message Passing (Process A send the message to Kernel and then Kernel sends that message to Process B)
b. Shared Memory (Process A put the message into Shared Memory and then Process B read that message from Shared
Memory)
 Notes : S22- Memory Management: Basic Bare Machine, Resident Monitor

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define and explain the concepts of a basic Open LMS (https://gulms.galgotiasuniversity.org/)
bare machine. Go to course Operating System(R1UC403B)
2. Define and explain the concepts of a resident Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
monitor . Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

What is Main Memory?

The main memory is central to the operation of a Modern Computer. Main Memory is a large array of words or bytes, ranging in
size from hundreds of thousands to billions. Main memory is a repository of rapidly available information shared by the CPU and
I/O devices. Main memory is the place where programs and information are kept when the processor is effectively utilizing
them. Main memory is associated with the processor, so moving instructions and information into and out of the processor is
extremely fast. Main memory is also known as RAM (Random Access Memory). This memory is volatile. RAM loses its data when
a power interruption occurs.

Memory Management in Operating System

Memory management is a crucial aspect of computer systems, ensuring that programs have access to the memory they need for
execution while also efficiently utilizing system resources. There are three important criteria as far as memory is concerned:
Size – larger size of memory is desirable.
Access time – small access time is desirable.
Per unit cost – less per unit cost is desirable.
In computer architecture there is following memory hierarchy design-

All the programs are loaded in the main memory for execution. Sometimes the complete program is loaded into the memory, but
sometimes a certain part or routine of the program is loaded into the main memory only when it is called by the program, this
mechanism is called Dynamic Loading, which enhances the performance. Also, at times one program is dependent on some other
program. In such a case, rather than loading all the dependent programs, the CPU links the dependent programs to the main executing
program when required. This mechanism is known as Dynamic Linking.

What is Memory Management in Operating System?

Memory Management is the process of coordinating and controlling the memory in a computer, Blocks are assigning portions that
are assigned to various running programs in order to optimize the overall performance of the system. This technique helps in keeping
the track of each and every memory location, whether the memory location is allocated to some process or it is free.

Need for Memory Management in OS

Memory management technique is needed for the following reasons:
 This technique helps in placing the programs in memory in such a way so that memory is utilized at its fullest extent.
 This technique helps to protect different processes from each other so that they do not interfere with each other's operations.
 It helps to allocate space to different application routines.
 This technique allows you to check how much memory needs to be allocated to processes that decide which processor
should get memory at what time.
 It keeps the track of each memory location whether it is free or allocated.
 This technique keeps the track of inventory whenever memory gets freed or unallocated and it will update the status
accordingly.
Methods Involved in Memory Management
There are various methods and with their help Memory Management can be done intelligently by the Operating System:

Logical Address & Physical Address:-

Logical Address: Address generated by a CPU is called as logical address. The logical address is known as “virtual address”. The
set of all logical unit or address generated by programs referred as “logical address space”.
Physical Address:-Address generated by memory management unit is called as physical address. The set of physical address
corresponding to logical address is referred as “physical address space”.

Suppose the base is at 14000, then an attempt by the user to address location 0 is relocated dynamically to 14000; thus access to
location 356 is mapped to 14356.

It is important to note that the user program never sees the real physical addresses.

Difference Between Logical Address and Physical Address

Swapping
Swapping is a memory management technique and is used to temporarily remove the inactive programs from the main memory of
the computer system. Any process must be in the memory for its execution, but can be swapped temporarily out of memory to a
backing store and then again brought back into the memory to complete its execution. Swapping is done so that other processes get
memory for their execution.
Due to the swapping technique performance usually gets affected, but it also helps in running multiple and big processes in
parallel. The swapping process is also known as a technique for memory compaction. Basically, low priority processes may be
swapped out so that processes with a higher priority may be loaded and executed.
The procedure by which any process gets removed from the hard disk and placed in the main memory or RAM commonly known
as Swap In.
On the other hand, Swap Out is the method of removing a process from the main memory or RAM and then adding it to the Hard
Disk.

Advantages of Swapping
The advantages/benefits of the Swapping technique are as follows:
1. The swapping technique mainly helps the CPU to manage multiple processes within a single main memory.
2. This technique helps to create and use virtual memory.
3. With the help of this technique, the CPU can perform several tasks simultaneously. Thus, processes need not wait too long
before their execution.
4. This technique is economical.
5. This technique can be easily applied to priority-based scheduling in order to improve its performance.

Disadvantages of Swapping
The drawbacks of the swapping technique are as follows:
1. There may occur inefficiency in the case if a resource or a variable is commonly used by those processes that are
participating in the swapping process.
2. If the algorithm used for swapping is not good then the overall method can increase the number of page faults and thus
decline the overall performance of processing.
3. If the computer system loses power at the time of high swapping activity then the user might lose all the information related
to the program.

In the early days of computing, before the development of modern operating systems, the execution of programs was done directly
on the hardware. This was made possible by two fundamental components: Bare Machine and Resident Monitor.

Bare Machine
A Bare Machine is a computer system that operates directly with its hardware. It executes programs in machine language without
the need for an operating system. Before the development of operating system, the only drawback was that it accepted instructions
in only machine language due to which only people with sufficient knowledge about Computer field are able to operate a computer.
Hence, after the development of the operating system, Bare machine is considered as inefficient.
Working of Bare Machine
 The processor executes machine language instructions provided by the user.
 There is no abstraction between the user and the machine. Hence, the system is highly dependent on the knowledge of
machine code.
 Each instruction is processed by the hardware without the help of an operating system which results in a basic, raw
computing environment.
Advantages of Bare Machine
1. Direct Control: Users can directly control the hardware without any interference from an operating system which can be
beneficial in low-level tasks or specialized applications.
2. Efficiency in Simple Tasks: For basic, single-task operations, Bare Machines can be faster than using an operating system
as there is no overhead.
3. Low Resource Requirement: Bare Machines do not require resources or memory needed by an operating system which
makes them useful in environments with limited resources.
Disadvantages of Bare Machine
1. Lack of User-Friendliness: Bare Machines only accept machine language. Users must have a understanding of low-level
programming.
2. No Multitasking: Unlike systems with operating systems, Bare Machines cannot handle multiple tasks simultaneously
which makes them inefficient for most general-purpose use cases.
3. Limited Scope: Bare Machines are inefficient for complex applications as they lack the abstraction and multitasking
features provided by modern operating systems.
Resident Monitor
The Resident Monitor is program that runs on Bare Machines. The resident monitor works like a primitive operating system that
controls the instructions and performs all necessary functions such as job scheduling, memory management, and interrupt
processing.

Parts of Resident Monitor

It is divided into 4 parts as:
 Control Language Interpreter: The first part of the Resident monitor is control language interpreter which is used to read
and carry out the instruction from one level to the next level.
 Loader: The second part of the Resident monitor which is the main part of the Resident Monitor is Loader which Loads
all the necessary system and application programs into the main memory.
 Device Driver: The third part of the Resident monitor is Device Driver which is used to manage the connecting input-
output devices to the system. So basically it is the interface between the user and the system. it works as an interface
between the request and response. request which user made, Device driver responds that the system produces to fulfill
these requests.
 Interrupt Processing: The fourth part as the name suggests, it processes the all occurred interrupt to the system.

Working of Resident Monitor

 It works like job sequencer as it sequences job and sends them to the processor.
 After scheduling the job Resident monitors loads the programs one by one into the main memory according to their
sequences.
 It controls the execution of instructions and ensures that programs are executed without any interruption in between.
 The Interrupt Processing feature allows the system to handle signals or requests from the hardware during execution,
ensuring smooth operations.

Advantages of Resident Monitor

1. Job Sequencing: The Resident Monitor handles job sequencing and memory management.
2. Faster Execution: There is no time gap between job scheduling and execution, making the system faster compared to
manual job handling.
3. No OS Overhead: The Resident Monitor allows program execution without the overhead of a operating system, making
it lighter in terms of resource consumption.
4. Basic System Control: It provides a minimal, yet effective level of control over hardware resources.

Disadvantages of Resident Monitor

1. Limited Functionality: The Resident Monitor provides only basic control over the system, and lacks the extensive features
of a modern operating system.
2. No Multitasking: Like the Bare Machine, Resident Monitors cannot handle multiple programs running simultaneously,
which limits their use in more complex environments.
3. Not Scalable: The Resident Monitor is not scalable for larger applications or systems that require more advanced
management.
4. Error Handling: As with Bare Machines, error handling is more difficult because there is no higher-level operating system
to catch and handle errors gracefully.
Bare Machine Vs Resident Monitor:

Feature Bare Machine Resident Monitor

A computer without any pre-installed A primitive OS that provides basic control and
Definition
software or OS. management.

Control Direct hardware access (no OS layer). Managed by a simple supervisor program (monitor).

User Interaction Manual input via switches/buttons. Basic command-driven interface.

Manually loaded via physical input (e.g.,

Program Loading Automatically loaded from storage (e.g., tape, disk).
punch cards, switches).

Memory
No memory protection; user manages all. Basic memory allocation & protection.
Management

I/O Operations Direct hardware programming required. Simplified via monitor-provided routines.

Error Handling No safeguards; crashes are likely. Basic error detection & recovery.

Example Systems ENIAC, early mainframes. IBM 360, early batch-processing systems.

Use Case Research, low-level development. Early business & scientific computing.
 Notes : S23- Multiprogramming with Fixed Partitions

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Describe how fixed partitions are used to Open LMS (https://gulms.galgotiasuniversity.org/)
allocate memory to multiple processes. Go to course Operating System(R1UC403B)
2. Explain the Partition Allocation (Memory Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
Allocation) Strategies. Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Memory Management Techniques

Memory management techniques are methods used by an operating system to efficiently allocate, utilize, and manage memory
resources for processes. These techniques ensure smooth execution of programs and optimal use of system memory
Different Memory Management techniques are:

The main memory must accommodate both operating system and various user processes. Generally, the main memory is divided
into 2 partitions. Operating system. & Application program/user processes. Multiprogramming is the ability of a system to run
multiple processes concurrently, improving CPU utilization and system throughput.
Generally, there are two methods used for partitioning the memory allocation.
1. Contiguous memory allocation
2. Non-Contiguous memory allocation

Contiguous Memory Allocation is again divided into two parts.

1. Fixed Partition Scheme.
2. Variable Partition Scheme

What is Fixed (or static) Partitioning in the Operating System?

Fixed (or static) partitioning is one of the earliest and simplest memory management techniques used in operating systems.
1. In fixed partitioning, the memory is divided into fixed-size chunks, with each chunk being reserved for a specific process.
When a process requests memory, the operating system assigns it to the appropriate partition. Each partition is of the same
size, and the memory allocation is done at system boot time.
2. Fixed partitioning has several advantages over other memory allocation techniques. First, it is simple and easy to
implement. Second, it is predictable, meaning the operating system can ensure a minimum amount of memory for each
process. Third, it can prevent processes from interfering with each other’s memory space, improving the security and
stability of the system.
3. However, fixed partitioning also has some disadvantages. It can lead to internal fragmentation, where memory in a partition
remains unused. This can happen when the process’s memory requirements are smaller than the partition size, leaving some
memory unused. Additionally, fixed partitioning limits the number of processes that can run concurrently, as each process
requires a dedicated partition.
Overall, fixed partitioning is a useful memory allocation technique in situations where the number of processes is fixed, and the
memory requirements for each process are known in advance. It is commonly used in embedded systems, real-time systems, and
systems with limited memory resources.

Fixed Partitioning:
This is the oldest and simplest technique used to put more than one process in the main memory. In this partitioning, the number of
partitions (non-overlapping) in RAM is fixed but the size of each partition may or may not be the same. As it is
a contiguous allocation, hence no spanning is allowed. Here partitions are made before execution or during system configure.
 As illustrated in above figure, first process is only consuming 1MB out of 4MB in the main memory. Hence, Internal
Fragmentation in first block is (4-1) = 3MB. Sum of Internal Fragmentation in every block = (4-1)+(8-7)+(8-7)+(16-14)=
+1+1+2=7MB. Suppose process P5 of size 7MB comes. But this process cannot be accommodated in spite of available free
space because of contiguous allocation (as spanning is not allowed). Hence, 7MB becomes part of External Fragmentation.

Advantages of Fixed Partitioning

 Easy to implement: The algorithms required are simple and straightforward.
 Low overhead: Requires minimal system resources to manage, ideal for resource-constrained systems.
 Predictable: Memory allocation is predictable, with each process receiving a fixed partition.
 No external fragmentation: Since the memory is divided into fixed partitions and no spanning is allowed, external
fragmentation is avoided.
 Suitable for systems with a fixed number of processes: Ideal for systems where the number of processes and their
memory requirements are known in advance.
 Prevents process interference: Ensures that processes do not interfere with each other’s memory, improving system
stability.
 Efficient memory use: Particularly in systems with fixed, known processes and batch processing scenarios.
 Good for batch processing: Works well in environments where the number of processes remains constant over time.
 Better control over memory allocation: The operating system has clear control over how memory is allocated and
managed.
 Easy to debug: Fixed Partitioning is easy to debug since the size and location of each process are predetermined.

Disadvantages of Fixed Partitioning

1. Internal Fragmentation: Main memory use is inefficient. Any program, no matter how small, occupies an entire partition.
This can cause internal fragmentation.
2. Limit process size: Process of size greater than the size of the partition in Main Memory cannot be accommodated. The
partition size cannot be varied according to the size of the incoming process size. Hence, the process size of 32MB in the
above-stated example is invalid.
3. Limitation on Degree of Multiprogramming: Partitions in Main Memory are made before execution or during system
configure. Main Memory is divided into a fixed number of partitions . Number of processes greater than the number of
partitions in RAM is invalid in Fixed Partitioning.
Fragmentation
Fragmentation is defined as when the process is loaded and removed after execution from memory, it creates a small free hole.
These holes cannot be assigned to new processes because holes are not combined or do not fulfil the memory requirement of the
process. In the operating systems two types of fragmentation are:
 Internal fragmentation: Internal fragmentation occurs when memory blocks are allocated to the process more than their
requested size. Due to this some unused space is left over and creating an internal fragmentation
problem. Example: Suppose there is a fixed partitioning used for memory allocation and the different sizes of blocks 3MB,
6MB, and 7MB space in memory. Now a new process p4 of size 2MB comes and demands a block of memory. It gets a
memory block of 3MB but 1MB block of memory is a waste, and it cannot be allocated to other processes too. This is
called internal fragmentation.
 External fragmentation: In External Fragmentation, we have a free memory block, but we cannot assign it to a process
because blocks are not contiguous. Example: Suppose (consider the above example) three processes p1, p2, and p3 come
with sizes 2MB, 4MB, and 7MB respectively. Now they get memory blocks of size 3MB, 6MB, and 7MB allocated
respectively. After allocating the process p1 process and the p2 process left 1MB and 2MB. Suppose a new process p4
comes and demands a 3MB block of memory, which is available, but we cannot assign it because free memory space is not
contiguous. This is called external fragmentation.

Solutions to Internal Fragmentation: Use variable-size memory allocation & Paging.

Solutions to External Fragmentation: Memory compaction: Rearranges memory contents to place all free memory together.
Compaction
Moving all the processes toward the top or towards the bottom to make free available memory in a single continuous place is called
compaction. Compaction is undesirable to implement because it interrupts all the running processes in the memory.

Partition Allocation (Memory Allocation) Strategies

In the figure given below, there are strategies that are used to select a hole from the set of available holes.

1. First Fit Allocation

According to this strategy, allocate the first hole or first free partition to the process that is big enough. This searching can start
either from the beginning of the set of holes or from the location where the previous first-fit search ended.
Searching can be stopped as soon as we find a free hole that is large enough.
Let us take a look at the example given below:
Process P1 of size 10KB has arrived and then the first hole that is enough to meet the requirements of size 20KB is chosen and
allocated to the process.

2. Best Fit Allocation

With this strategy, the smallest free partition/ hole that is big enough and meets the requirements of the process is allocated to the
process. This strategy searches the entire list of free partitions/holes in order to find a hole whose size is either greater than or equal
to the size of the process.
Let us take a look at the example given below:
Process P1 of size 10KB is arrived and then the smallest hole to meet the requirements of size 10 KB is chosen and allocated to the
process.
3. Worst Fit Allocation
With this strategy, the Largest free partition/ hole that meets the requirements of the process is allocated to the process. It is done so
that the portion that is left is big enough to be useful.
This strategy searches the entire list of holes in order to find the largest hole and then allocate the largest hole to process.
Let us take a look at the example given below:
Process P1 of size 10KB has arrived and then the largest hole of size 80 KB is chosen and allocated to the process.

Example: Consider the following memory blocks (in KB): Block sizes: 100 KB, 500 KB, 200 KB, 300 KB, 600 KB. Processes
arrive needing memory as follows: Process sizes: 212 KB, 417 KB, 112 KB, 426 KB. Apply First Fit, Best Fit, Worst Fit and
Next Fit algorithms to determine which process gets allocated to which block. Show the allocation and the remaining sizes of the
memory blocks after allocation.
Answer:
Memory Blocks (Initial):
Block 1: 100 KB
Block 2: 500 KB
Block 3: 200 KB
Block 4: 300 KB
Block 5: 600 KB
Processes (In Order):
P1: 212 KB
P2: 417 KB
P3: 112 KB
P4: 426 KB

1. First Fit
Approach: Allocate the first block that is large enough for the process.
Allocation Steps:
 P1 (212 KB) → Block 2 (500 KB) → Allocated (500 - 212 = 288 KB left)
 P2 (417 KB) → Block 5 (600 KB) → Allocated (600 - 417 = 183 KB left)
 P3 (112 KB) → Block 3 (200 KB) → Allocated (200 - 112 = 88 KB left)
 P4 (426 KB) → No suitable block remaining
Result:
Process Allocated Block Remaining Block Size
P1 Block 2 (500 KB) 288 KB
P2 Block 5 (600 KB) 183 KB
P3 Block 3 (200 KB) 88 KB
P4 Not allocated -

2. Best Fit
Approach: Allocate the smallest block that is large enough for the process.
Allocation Steps:
 P1 (212 KB) → Best fit: Block 4 (300 KB) → Allocated (300 - 212 = 88 KB left)
  P2 (417 KB) → Best fit: Block 2 (500 KB) → Allocated (500 - 417 = 83 KB left)
 P3 (112 KB) → Best fit: Block 3 (200 KB) → Allocated (200 - 112 = 88 KB left)
 P4 (426 KB) → Best fit: Block 5 (600 KB) → Allocated (600 - 426 = 174 KB left)
Result:
Process Allocated Block Remaining Block Size
P1 Block 4 (300 KB) 88 KB
P2 Block 2 (500 KB) 83 KB
P3 Block 3 (200 KB) 88 KB
P4 Block 5 (600 KB) 174 KB

3. Worst Fit
Approach: Allocate the largest available block that fits the process.
Allocation Steps:
 P1 (212 KB) → Worst fit: Block 5 (600 KB) → Allocated (600 - 212 = 388 KB)
 P2 (417 KB) → Worst fit: Block 5 (388 KB) no longer sufficient → next is Block 2 (500 KB) → Allocated (500 - 417 =
83 KB)
 P3 (112 KB) → Worst fit: Block 5 (388 KB) → Allocated (388 - 112 = 276 KB)
 P4 (426 KB) → No suitable block remaining
Result:
Process Allocated Block Remaining Block Size
P1 Block 5 (600 KB) 388 KB → 276 KB after P3
P2 Block 2 (500 KB) 83 KB
P3 Block 5 276 KB remaining
P4 Not allocated -
 Notes : S24- Multiprogramming with Variable Partitions

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Describe how variable partitions are used to Open LMS (https://gulms.galgotiasuniversity.org/)
allocate memory to multiple processes Go to course Operating System(R1UC403B)
(Multistructural). Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
2. Explain the advantages and limitations of Click on “Session-wise Pre & Post Class Assessments”
multiprogramming with variable partitions  Attempt Assessment quizzes.
(Relational).

Variable Partitioning –
It is a part of the Contiguous allocation technique. It is used to alleviate the problem faced by Fixed Partitioning. In contrast with
fixed partitioning, partitions are not made before the execution or during system configure. Various features associated with variable
Partitioning-
1. Initially, RAM is empty and partitions are made during the run-time according to the process’s need instead of partitioning
during system configure.
2. The size of the partition will be equal to the incoming process.
3. The partition size varies according to the need of the process so that the internal fragmentation can be avoided to ensure
efficient utilization of RAM.
4. The number of partitions in RAM is not fixed and depends on the number of incoming processes and Main Memory’s size.

Dynamic partitioning tries to overcome the problems caused by fixed partitioning. In this technique, the partition size is not declared
initially. It is declared at the time of process loading. The first partition is reserved for the operating system. The remaining space is
divided into parts. The size of each partition will be equal to the size of the process. The partition size varies according to the need
of the process so that the internal fragmentation can be avoided.

Advantages of Dynamic Partitioning over fixed partitioning

1. No Internal Fragmentation
Given the fact that the partitions in dynamic partitioning are created according to the need of the process, It is clear that there will
not be any internal fragmentation because there will not be any unused remaining space in the partition.
2. No Limitation on the size of the process
In Fixed partitioning, the process with the size greater than the size of the largest partition could not be executed due to the lack of
sufficient contiguous memory. Here, In Dynamic partitioning, the process size can't be restricted since the partition size is decided
according to the process size.
3. Degree of multiprogramming is dynamic
Due to the absence of internal fragmentation, there will not be any unused space in the partition hence more processes can be loaded
in the memory at the same time.

Disadvantages of dynamic partitioning

1.External Fragmentation
Absence of internal fragmentation doesn't mean that there will not be external fragmentation.
Let's consider three processes P1 (1 MB) and P2 (3 MB) and P3 (1 MB) are being loaded in the respective partitions of the main
memory.
After some time P1 and P3 got completed and their assigned space is freed. Now there are two unused partitions (1 MB and 1 MB)
available in the main memory but they cannot be used to load a 2 MB process in the memory since they are not contiguously located.
The rule says that the process must be contiguously present in the main memory to get executed. We need to change this rule to
avoid external fragmentation.

2.Complex Memory Allocation

In Fixed partitioning, the list of partitions is made once and will never change but in dynamic partitioning, the allocation and
deallocation is very complex since the partition size will be varied every time when it is assigned to a new process. OS has to keep
track of all the partitions.
Due to the fact that the allocation and deallocation are done very frequently in dynamic memory allocation and the partition size
will be changed at each time, it is going to be very difficult for OS to manage everything.

Difference between Fixed Partitioning and Variable Partitioning

Fixed Partitioning Variable Partitioning

Memory is divided into fixed-sized partitions. Memory is allocated dynamically in varying sizes.

Only one process can be placed in each partition. A process is allocated a chunk of free memory as needed.

Inefficient memory utilization due to internal More efficient memory utilization with less internal
fragmentation. fragmentation.

Internal and external fragmentation occur. Only external fragmentation occurs.

Limited degree of multi-programming. Higher degree of multi-programming due to flexible allocation.

Easier to implement. More complex to implement.

Restricts process size based on partition size. No size limitation on processes.

 Notes : S25- Paging

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define paging and identify its basic Open LMS (https://gulms.galgotiasuniversity.org/)
components (e.g., page, frame, page table). Go to course Operating System(R1UC403B)
2. Explain the process of paging and how it Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
maps logical addresses to physical addresses. Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Non-Contiguous Memory Allocation

It allows to store parts of a single process in a non-contiguous fashion. Thus, different parts of the same process can be stored at
different places in the main memory. Non-Contiguous memory allocation techniques are basically of two types:
1. Paging
2. Segmentation
The main disadvantage of Dynamic Partitioning is External fragmentation. Although, this can be removed by Compaction but as
we have discussed earlier, the compaction makes the system inefficient. That’s why we come up with an idea of non-contiguous
memory allocation.

Paging in Operating System

Paging is a memory management scheme that eliminates the need for a contiguous allocation of physical memory. The process of
retrieving processes in the form of pages from the secondary storage into the main memory is known as paging. The basic purpose
of paging is to separate each procedure into pages.

Why Paging is used for memory Management?

Paging is a memory management technique that addresses common challenges in allocating and managing memory efficiently. Here
we can understand why paging is needed as a Memory Management technique:
 Memory isn’t always available in a single block: Programs often need more memory than what is available in a single
continuous block. Paging breaks memory into smaller, fixed-size pieces, making it easier to allocate scattered free spaces.
 Processes size can increase or decrease: programs don’t need to occupy continuous memory, so they can grow
dynamically without the need to be moved.

Terminologies Associated with Memory Control

 Logical Address or Virtual Address: The Logical Address, also known as the Virtual Address, is the address generated
by the CPU when a program accesses memory.
 Logical Address Space or Virtual Address Space: The Logical Address Space, also known as the Virtual Address Space,
refers to the set of all possible logical addresses that a process can generate during its execution. It is a conceptual range of
memory addresses used by a program and is independent of the actual physical memory (RAM).
 Physical Address: A Physical Address is the actual location in the computer’s physical memory (RAM) where data or
instructions are stored. It is used by the memory hardware to access specific data in the system’s memory.
 Physical Address Space: The Physical Address Space refers to the total range of addresses available in a computer’s
physical memory (RAM). It represents the actual memory locations that can be accessed by the system hardware to store
or retrieve data.
 Physical memory (Main Memory)is divided into fixed sized block called frames.
 Logical address space (Secondary Memory) is divided into blocks of fixed size called pages.
 Page and frame will be of same size.
 Whenever a process needs to get execute on CPU, its pages are moved from hard disk to available frame in main memory.

How Paging Works?

Paging is a method used by operating systems to manage memory efficiently. In paging, the physical memory is divided into fixed-
size blocks called page frames, which are the same size as the pages used by the process. The process’s logical address space is also
divided into fixed-size blocks called pages, which are the same size as the page frames.
When a process requests memory, the operating system allocates one or more page frames to the process and maps the
process’s logical pages to the physical page frames. When a program runs, its pages are loaded into any available frames in the
physical memory.
This approach prevents fragmentation issues by keeping memory allocation uniform. Each program has a page table, which the
operating system uses to keep track of where each page is stored in physical memory. When a program accesses data, the system
uses this table to convert the program’s address into a physical memory address.
Paging allows for better memory use and makes it easier to manage. It also supports virtual memory, letting parts of programs be
stored on disk and loaded into memory only when needed. This way, even large programs can run without fitting entirely into main
memory.
This technique keeps the track of all the free frames.
The Frame has the same size as that of a Page. A frame is basically a place where a (logical) page can be (physically) placed.

Each process is mainly divided into parts where the size of each part is the same as the page size.
There is a possibility that the size of the last part may be less than the page size.
 Pages of a process are brought into the main memory only when there is a requirement otherwise they reside in the
secondary storage.
 One page of a process is mainly stored in one of the frames of the memory. Also, the pages can be stored at different
locations of the memory but always the main priority is to find contiguous frames.

Let us now cover the concept of translating a logical address into the physical address:
Before moving on further there are some important points to note:
 The CPU always generates a logical address.
 In order to access the main memory always a physical address is needed.
Every address generated by CPU mainly consists of two parts:
1. Page Number(p)
2. Page Offset (d)
where, Page Number is used as an index into the page table that generally contains the base address of each page in the physical
memory. Page offset is combined with base address in order to define the physical memory address which is then sent to the memory
unit. If the size of logical address space is 2 raised to the power m and page size is 2 raised to the power n addressing units then
the high order m-n bits of logical address designates the page number and the n low-order bits designate the page offset.
The logical address is as follows:

where p indicates the index into the page table, and d indicates the displacement within the page. The Page size is usually defined
by the hardware. The size of the page is typically the power of 2 that varies between 512 bytes and 16 MB per page.

Following steps are followed to translate logical address into physical address-
Step-01:CPU generates a logical address consisting of two parts-Page Number, Page Offset.
Page Number specifies the specific page of the process from which CPU wants to read the data.
Page Offset specifies the specific word on the page that CPU wants to read.
Step-02: For the page number generated by the CPU, Page Table provides the corresponding frame number (base address of the
frame) where that page is stored in the main memory.
Step-03: The frame number combined with the page offset forms the required physical address.
Frame number specifies the specific frame where the required page is stored.
Page Offset specifies the specific word that has to be read from that page.
Paging Example
In order to implement paging, one of the simplest methods is to implement the page table as a set of registers. As the size of registers
is limited but the size of the page table is usually large thus page table is kept in the main memory.
There is no External fragmentation caused due to this scheme; Any frame that is free can be allocated to any process that needs it.
But the internal fragmentation is still there.
 If any process requires n pages then at least n frames are required.
 The first page of the process is loaded into the first frame that is listed on the free-frame list, and then the frame
number is put into the page table.

The frame table is a data structure that keeps the information of which frames are allocated or which frames are available and many
more things. This table mainly has one entry for each physical page frame.
The Operating system maintains a copy of the page table for each process in the same way as it maintains the copy of the instruction
counter and register contents. Also, this copy is used to translate logical addresses to physical addresses whenever the operating
system maps a logical address to a physical address manually.
This copy is also used by the CPU dispatcher in order to define the hardware page table whenever a process is to be allocated to the
CPU.

What is Page Table?

The Page table mainly contains the base address of each page in the Physical memory. The base address is then combined with
the page offset in order to define the physical memory address which is then sent to the memory unit.
Thus page table mainly provides the corresponding frame number (base address of the frame) where that page is stored in the main
memory.

Multilevel paging:
Multilevel paging is a paging scheme where there exists a hierarchy of page tables.
Need –The need for multilevel paging arises when- The size of page table is greater than the frame size. As a result, the page table
cannot be stored in a single frame in main memory.
Working-In multilevel paging, the page table having size greater than the frame size is divided into several parts. The size of each
part is same as frame size except possibly the last part. The pages of page table are then stored in different frames of the main
memory. To keep track of the frames storing the pages of the divided page table, another page table is maintained. As a result, the
hierarchy of page tables get generated. Multilevel paging is done till the level is reached where the entire page table can be stored
in a single frame.

*Translation of look-aside buffer(TLB)

In the following diagram indicates the translation of the Logical address into the Physical address. The PTBR in the diagram means
page table base register and it basically holds the base address for the page table of the current process. The PTBR is mainly a
processor register and is managed by the operating system. Commonly, each process running on a processor needs its own logical
address space. With the scheme, two memory accesses are needed in order to access a byte( one for the page-table entry and one for
byte). Thus memory access is slower by a factor of 2 and in most cases, this scheme slowed by a factor of 2.

There is the standard solution for the above problem that is to use a special, small, and fast-lookup hardware cache that is commonly
known as Translation of look-aside buffer(TLB).
 TLB is associative and high-speed memory.
 Each entry in the TLB mainly consists of two parts: a key(that is the tag) and a value.
 When associative memory is presented with an item, then the item is compared with all keys simultaneously. In case if the
item is found then the corresponding value is returned.
 The search with TLB is fast though the hardware is expensive.
 The number of entries in the TLB is small and generally lies in between 64 and 1024.

TLB is used with Page Tables in the following ways:

The TLB contains only a few of the page-table entries. Whenever the logical address is generated by the CPU then its page number
is presented to the TLB.
 If the page number is found, then its frame number is immediately available and is used in order to access the memory.
The above whole task may take less than 10 percent longer than would if an unmapped memory reference were used.
 In case if the page number is not in the TLB (which is known as TLB miss), then a memory reference to the Page table
must be made.
 When the frame number is obtained it can be used to access the memory. Additionally, page number and frame number is
added to the TLB so that they will be found quickly on the next reference.
 In case if the TLB is already full of entries then the Operating system must select one for replacement.
  TLB allows some entries to be wired down, which means they cannot be removed from the TLB. Typically TLB entries
for the kernel code are wired down.

Paging Hardware With TLB

Effective Access Time calculation:

Question: 80 percent hit ratio in TLB, if it takes 20 nanoseconds to search in TLB, 100 nanoseconds to access main memory, then
what is the effective access time to find a page?
Solution: A- Hit ratio is 80 percent and miss ratio is 20 percent
Effective access time = H(TLB+MM )+ M(TLB+PT+MM)
= H(TLB+MM )+ M(TLB+2MM)
= 0.8(20+100) + 0.2(20+100+100)

Advantages and Disadvantages of Paging

Advantages of Paging
 Eliminates External Fragmentation: Paging divides memory into fixed-size blocks (pages and frames), so processes can
be loaded wherever there is free space in memory. This prevents wasted space due to fragmentation.
 Efficient Memory Utilization: Since pages can be placed in non-contiguous memory locations, even small free spaces
can be utilized, leading to better memory allocation.
 Supports Virtual Memory: Paging enables the implementation of virtual memory, allowing processes to use more
memory than physically available by swapping pages between RAM and secondary storage.
 Ease of Swapping: Individual pages can be moved between physical memory and disk (swap space) without affecting the
entire process, making swapping faster and more efficient.
 Improved Security and Isolation: Each process works within its own set of pages, preventing one process from accessing
another’s memory space.

Disadvantages of Paging
 Internal Fragmentation: If the size of a process is not a perfect multiple of the page size, the unused space in the last
page results in internal fragmentation.
 Increased Overhead: Maintaining the Page Table requires additional memory and processing. For large processes, the
page table can grow significantly, consuming valuable memory resources.
 Page Table Lookup Time: Accessing memory requires translating logical addresses to physical addresses using the page
table. This additional step increases memory access time, although Translation Lookaside Buffers (TLBs) can help reduce
the impact.
 I/O Overhead During Page Faults: When a required page is not in physical memory (page fault), it needs to be fetched
from secondary storage, causing delays and increased I/O operations.
 Complexity in Implementation: Paging requires sophisticated hardware and software support, including the Memory
Management Unit (MMU) and algorithms for page replacement, which add complexity to the system.

Questions Based on Paging:

For Main Memory Formula :

 Physical Address Space = Size of main memory
 Size of main memory = Total number of frames x Page size
 Frame size = Page size
 If number of frames in main memory = 2X, then number of bits in frame number = X bits
 If Page size = 2X Bytes, then number of bits in page offset = X bits
 If size of main memory = 2X Bytes, then number of bits in physical address = X bits
For Process:
 Virtual Address Space = Size of process
 Number of pages the process is divided = Process size / Page size
 If process size = 2X bytes, then number of bits in virtual address space = X bits
 In general, if the given address consists of ‘n’ bits, then using ‘n’ bits, 2n locations are possible. Then, size of memory =
2n x Size of one location.
 If the memory is byte-addressable, then size of one location = 1 byte. Thus, size of memory = 2n bytes.
 If the memory is word-addressable where 1 word = m bytes, then size of one location = m bytes. Thus, size of memory =
2n x m bytes.
For Page Table:
 Size of page table = Number of entries in page table x Page table entry size
 Number of entries in pages table = Number of pages the process is divided
 Page table entry size = Number of bits in frame number + Number of bits used for optional fields if any

Q1. Calculate the size of memory if its address consists of 22 bits and the memory is 2-byte addressable.
Solution-
• Number of locations possible with 22 bits = 2 22 locations
• t is given that the size of one location = 2 bytes
Thus, Size of memory= 222 x 2 bytes = 223 bytes== 8 MB

Q2. Calculate the number of bits required in the address for memory having size of 16 GB. Assume the memory is 4-byte
addressable.
Solution:
Let ‘n’ number of bits are required. Then, Size of memory = 2n x 4 bytes.
Since, the given memory has size of 16 GB, so we have-
2n x 4 bytes = 16 GB
2n x 4 = 16 G
2n x 22 = 234
2n = 232
∴ n = 32 bits

In paging scheme, there are mainly two overheads-

1. Overhead of Page Tables-
• Paging requires each process to maintain a page table.
• So, there is an overhead of maintaining a page table for each process.
2. Overhead of Wasting Pages-
• There is an overhead of wasting last page of each process if it is not completely filled.
• On an average, half page is wasted for each process.
Thus,
Total overhead for one process
= Size of its page table + (Page size / 2)
Optimal Page Size-Optimal page size is the page size that minimizes the total overhead.
It is given as-

Problem: In a paging scheme, virtual address space is 4 KB and page table entry size is 8 bytes. What should be the optimal
page size?
Solution-
Given-
• Virtual address space = Process size = 4 KB
• Page table entry size = 8 bytes
We know-
Optimal page size
= (2 x Process size x Page table entry size)1/2
= (2 x 4 KB x 8 bytes)1/2
= (216 bytes x bytes)1/2
= 28 bytes
= 256 bytes
Thus, Optimal page size = 256 bytes.
 Notes : S26- Demand Paging

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define demand paging and identify its basic Open LMS (https://gulms.galgotiasuniversity.org/)
components (e.g., page fault, page Go to course Operating System(R1UC403B)
replacement). Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
2. Explain the process of demand paging and Click on “Session-wise Pre & Post Class Assessments”
how it differs from traditional paging.  Attempt Assessment quizzes.

What is Demand Paging in Operating System?

Demand paging is a technique used in virtual memory systems where pages enter main memory only when requested or needed by
the CPU. In demand paging, the operating system loads only the necessary pages of a program into memory at runtime, instead of
loading the entire program into memory at the start. A page fault occurred when the program needed to access a page that is not
currently in memory.
The operating system then loads the required pages from the disk into memory and updates the page tables accordingly. This process
is transparent to the running program and it continues to run as if the page had always been in memory.

The demand paging system is somehow similar to the paging system with swapping where processes mainly reside in the main
memory(usually in the hard disk). Thus demand paging is the process that solves the above problem only by swapping the pages on
Demand. This is also known as lazy swapper( It never swaps the page into the memory unless it is needed).
Swapper that deals with the individual pages of a process are referred to as Pager.

What is Page Fault?

The term "page miss" or "page fault" refers to a situation where a referenced page is not found in the main memory.
When a program tries to access a page, or fixed-size block of memory, that isn't currently loaded in physical memory (RAM), an
exception known as a page fault happens. Before enabling the program to access a page that is required, the operating system must
bring it into memory from secondary storage (such a hard drive) in order to handle a page fault.
In modern operating systems, page faults are a common component of virtual memory management. By enabling programs to
operate with more data than can fit in physical memory at once, they enable the efficient use of physical memory. The operating
system is responsible for coordinating the transfer of data between physical memory and secondary storage as needed.

Working Process of Demand Paging

Let us understand this with the help of an example. Suppose we want to run a process P which have four pages P0, P1, P2, and P3.
Currently, in the page table, we have pages P1 and P3.

Steps in Demand Paging (as shown in the image):

1. CPU Requests a Page
 The CPU generates a logical address for a process (e.g., for process P1).
 It checks the Page Table to find whether the required page is in main memory.
2. Page Table Lookup
  The Page Table maps each process's page to a frame in main memory.
 If the page is not in memory, a page fault occurs and the OS is notified.
3. OS Handles Page Fault
 The Operating System (OS) checks the Secondary Memory (like a hard disk or SSD) for the missing page (e.g., P1 or
P3).
4. Page is Fetched from Secondary Memory
 The OS locates the page (e.g., P1 or P3) in secondary memory.
 It selects a free frame (or uses page replacement if necessary) in main memory.
5. Page Loaded into Main Memory
 The missing page is copied from secondary storage into a free frame in main memory (e.g., P3 into frame f3, P1 into
frame f5).
 The page table is updated with the new frame number.
6. CPU Continues Execution
 After the page is loaded, control returns to the CPU.
 The CPU resumes executing the instruction that caused the page fault using the now-loaded page.

How Demand Paging in OS Affects System Performance?

Demand paging can improve system performance by reducing the memory needed for programs and allowing multiple programs to
run simultaneously. However, if not implemented properly, it can cause performance issues. When a program needs a part that isn’t
in the main memory, the operating system must fetch it from the hard disk, which takes time and pauses the program. This can cause
delays, and if the system runs out of memory, it will need to frequently swap pages in and out, increasing delays and reducing
performance.

Performance of DP:
Effective access time for demand paging memory:
EAT=(1-P)*ma+P*page fault time
Where ma=memory access time, P=Probability of a page fault(0<=P<=1)

Common Algorithms Used for Demand Paging in OS

Demand paging is a memory management technique that loads parts of a program into memory only when needed. If a program
needs a page that isn’t currently in memory, the system fetches it from the hard disk. Several algorithms manage this process:
 FIFO (First-In-First-Out): Replaces the oldest page in memory with a new one. It’s simple but can cause issues if pages
are frequently swapped in and out, leading to thrashing.
 LRU (Least Recently Used): Replaces the page that hasn’t been used for the longest time. It reduces thrashing more
effectively than FIFO but is more complex to implement.
 LFU (Least Frequently Used): Replaces the page used the least number of times. It helps reduce thrashing but requires
extra tracking of how often each page is used.

Advantages of Demand Paging

So in the Demand Paging technique, there are some benefits that provide efficiency of the operating system.
 Efficient use of physical memory: Query paging allows for more efficient use because only the necessary pages are loaded
into memory at any given time.
 Support for larger programs: Programs can be larger than the physical memory available on the system because only the
necessary pages will be loaded into memory.
 Faster program start: Because only part of a program is initially loaded into memory, programs can start faster than if
the entire program were loaded at once.
 Reduce memory usage: Query paging can help reduce the amount of memory a program needs, which can improve system
performance by reducing the amount of disk I/O required.

Disadvantages of Demand Paging

 Page Fault Overload: The process of swapping pages between memory and disk can cause a performance overhead,
especially if the program frequently accesses pages that are not currently in memory.
 Degraded Performance: If a program frequently accesses pages that are not currently in memory, the system spends a lot
of time swapping out pages, which degrades performance.
 Fragmentation: Query paging can cause physical memory fragmentation, degrading system performance over time.
 Complexity: Implementing query paging in an operating system can be complex, requiring complex algorithms and data
structures to manage page tables and swap space.
Difference Between Swapping and Demand Paging in OS
Aspects Paging Swapping

Basic A memory management technique to store and A technique for temporarily removing inactive
acquire data in the RAM. applications from the computer system's main
memory.

Purpose Allows the memory of the process address space to Allows multiple programs in the os to run
be non-contiguous. simultaneously.

Occurrence Occurs when only a part of the princess gets Occurs when the entire process is transferred to the
transferred to the disk. disk.

Processes Paging allows many processes in the main memory Swapping reduces the number of processes in the
to exist and is performed by active processes. memory and is performed by inactive processes.

Adaptability More adaptable as relocation of the process is Less adaptable as the operation goes back and forth.
allowed.

Workloads Appropriate for heavy workloads. Appropriate for light to medium workloads.

Memory Used in Non-contiguous Memory Management. Can be performed without any memory management.
Management

Usage Helps to implement virtual memory. Helps CPU to access processes faster.
 Notes : S27- Page Replacement Algorithms

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define page replacement and page fault Open LMS (https://gulms.galgotiasuniversity.org/)
management mechanism. Go to course Operating System(R1UC403B)
2. Explain how different page replacement Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
algorithms work (e.g., FIFO, LRU, Optimal). Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Page Replacement Algorithms in Operating System

As studied in Demand Paging, only certain pages of a process are loaded initially into the memory. This allows us to get more
processes into memory at the same time. but what happens when a process requests for more pages and no free memory is available
to bring them in. Following steps can be taken to deal with this problem :
1. Put the process in the wait queue, until any other process finishes its execution thereby freeing frames.
2. Or, remove some other process completely from the memory to free frames.
3. Or, find some pages that are not being used right now, move them to the disk to get free frames. This technique is
called Page replacement and is most commonly used.

In this case, if a process requests a new page and supposes there are no free frames, then the Operating system needs to decide which
page to replace. The operating system must use any page replacement algorithm in order to select the victim frame. The Operating
system must then write the victim frame to the disk then read the desired page into the frame and then update the page tables. And
all these require double the disk access time.
 Page replacement prevents the over-allocation of the memory by modifying the page-fault service routine.
 To reduce the overhead of page replacement a modify bit (dirty bit) is used in order to indicate whether each page is
modified.
 This technique provides complete separation between logical memory and physical memory.

Page Replacement in OS
In Virtual Memory Management, Page Replacement Algorithms play an important role. The main objective of all the Page
replacement policies is to decrease the maximum number of page faults.
Page Fault – It is basically a memory error, and it occurs when the current programs attempt to access the memory page for mapping
into virtual address space, but it is unable to load into the physical memory then this is referred to as Page fault.
Demand Paging – Page Fault

Basic Page Replacement Algorithm in OS

Page Replacement technique uses the following approach. If there is no free frame, then we will find the one that is not currently
being used and then free it. A-frame can be freed by writing its content to swap space and then change the page table in order to
indicate that the page is no longer in the memory.
1. Find the location of the desired page on disk.
2. Find a free frame:
- If there is a free frame, use it.
- If there is no free frame, use a page replacement algorithm to select a victim frame
- Write victim frame to disk if dirty
3. Bring the desired page into the (newly) free frame; update the page and frame tables
 4. Continue the process by restarting the instruction that caused the trap

Page Replacement Algorithms in OS

This algorithm helps to decide which pages must be swapped out from the main memory in order to create a room for the incoming
page. This Algorithm wants the lowest page-fault rate.
Various Page Replacement algorithms used in the Operating system are as follows;

Common Page Replacement Techniques: First In First Out (FIFO), Optimal Page replacement, Least Recently Used (LRU)

First In First Out (FIFO)

This is the simplest page replacement algorithm. In this algorithm, the operating system keeps track of all pages in the memory in a
queue, the oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for
removal. Performance is not so good.as it suffers from belady`s anamoly.

Example 1: Consider page reference string 1, 3, 0, 3, 5, 6, 3 with 3-page frames. Find the number of page faults using FIFO Page
Replacement Algorithm.

Initially, all slots are empty, so when 1, 3, 0 came they are allocated to the empty slots —> 3 Page Faults.
when 3 comes, it is already in memory so —> 0 Page Faults. T
hen 5 comes, it is not available in memory, so it replaces the oldest page slot i.e 1. —> 1 Page Fault.
6 comes, it is also not available in memory, so it replaces the oldest page slot i.e 3 —> 1 Page Fault.
Finally, when 3 come it is not available, so it replaces 0 ->1-page fault.

Question:Given reference string:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 .Implement FIFO on the string and calculate the number of
faults.(Frame =3,given)
Answer:
Reference 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
string

Head 7 7 7 2 2 2 4 4 4 0 0 0 7 7 7
0 0 0 3 3 3 2 2 2 1 1 1 0 0
Tail 1 1 1 0 0 0 3 3 3 2 2 2 1
Page Fault F F F F F F F F F F F F F F F TOTAL
PAGE
FAULT=15
Example to explain belady`s anamoly:
Q:Let the string is:1,2,3,4,1,2,5,1,2,3,4,5.Implement FIFO with 3 Frames and 4 Frames.
A:With frame =3.
Reference string 1 2 3 4 1 2 5 1 2 3 4 5

Head 1 1 1 4 4 4 5 3 3 3
2 2 2 1 1 1 1 4 4
Tail 3 3 3 2 2 2 2 5
Page Fault F F F F F F F F F F TOTAL PAGE FAULT=10
With frame=4
Reference string 1 2 3 4 1 2 5 1 2 3 4 5
Exercise for student:
Head

Tail
Page Fault F F F F F F F F F F TOTAL PAGE FAULT=9
**We notice that the number of faults for four frames(10) is greater than the number of faults for three frames(9)! This most
unexpected resut is known as belady`s anomaly.

Optimal Page Replacement

Replace the page that will not be used longest period of time. Removes belady`s anomaly. Some times impractical as it requires
knowledge of the future behaviour of the program,which we do not have generally.

Example: Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4-page frame. Find number of page fault using
Optimal Page Replacement Algorithm.

Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page faults
0 is already there so —> 0 Page fault.
when 3 came it will take the place of 7 because it is not used for the longest duration of time in the future—> 1 Page fault.
0 is already there so —> 0 Page fault.
4 will takes place of 1 —> 1 Page Fault.
Now for the further page reference string —> 0 Page fault because they are already available in the memory.

Example:
Question:Given reference string:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 .Implement Optimal PRA on the string and calculate the
number of faults.(Frame =3,given)
Answer:
Reference 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
number
Reference 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
string

Head 7 7 7 2 2 2 2 2 7
0 0 0 0 4 0 0 1
Tail 1 1 3 3 3 1 1
Page Fault F F F F F F F F F TOTAL
PAGE
FAULT=9
Least Recently Used
In this algorithm, page will be replaced which is least recently used.
Example Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4-page frames. Find number of page faults
using LRU Page Replacement Algorithm.

Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page faults
0 is already there so —> 0 Page fault.
when 3 came it will take the place of 7 because it is least recently used —> 1 Page fault
0 is already in memory so —> 0 Page fault.
4 will takes place of 1 —> 1 Page Fault
Now for the further page reference string —> 0 Page fault because they are already available in the memory.

Example:
Question:Given reference string:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 .Implement LRU PRA on the string and calculate the
number of faults.(Frame =3,given)
Answer:
Reference 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
number
Reference 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
string

Head 7 7 7 2 2 4 4 4 0 1 1 1
0 0 0 0 0 0 3 3 3 0 0
Tail 1 1 3 3 2 2 2 2 2 7
Page Fault F F F F F F F F F F F F TOTAL
PAGE
FAULT=12
 Notes : S28- Segmentation

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define segmentation. Open LMS (https://gulms.galgotiasuniversity.org/)
2. Explain how segmentation divides memory Go to course Operating System(R1UC403B)
into variable-sized segments and how it Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
differs from paging. Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Segmentation in Operating System

A 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. Works on the user point of view, logical address space of any process is a collection of code, data and stack.
Here the logical address space of a process is divided into blocks of varying size, called segments.

Each segment contains a logical unit of process. Whenever a process is to be executed, its segments are moved from secondary
storage to the main memory. Each segment is allocated a chunk of free memory of the size equal to that segment. OS maintains one
table known as segment table, for each process. It includes size of segment and location in memory where the segment has been
loaded.
Characteristics of Segmentation
Some characteristics of the segmentation technique are as follows:
 The Segmentation partitioning scheme is variable-size.
 Partitions of the secondary memory are commonly known as segments.
 Partition size mainly depends upon the length of modules.
 Thus with the help of this technique, secondary memory and main memory are divided into unequal-sized partitions.

Need of Segmentation
One of the important drawbacks of memory management in the Operating system is the separation of the user's view of memory
and the actual physical memory. and Paging is a technique that provides the separation of these two memories.
User' view is basically mapped onto physical storage. And this mapping allows differentiation between Physical and logical memory.
It is possible that the operating system divides the same function into different pages and those pages may or may not be loaded into
the memory at the same time also Operating system does not care about the User's view of the process. Due to this technique system's
efficiency decreases. Segmentation is a better technique because it divides the process into segments.

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.
There is no simple relationship between logical addresses and physical addresses in segmentation. A table stores the information
about all such segments and is called Segment Table.

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.

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.

Segmentation Hardware
Given below figure shows the segmentation hardware :

Advantages of Segmentation
 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.
 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
 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.

Differences between Paging and Segmentation

Now, we will cover the differences between Paging and Segmentation in the table given below:
Paging Segmentation

Paging is a memory management technique where Segmentation is also a memory management technique where
memory is partitioned into fixed-sized blocks that are memory is partitioned into variable-sized blocks that are commonly
commonly known as pages. known as segments.

With the help of Paging, the logical address is divided into With the help of Segmentation, the logical address is divided
a page number and page offset. into segment number and segment offset.

This technique may lead to Internal Fragmentation. Segmentation may lead to External Fragmentation.

The page table mainly contains the base address of each The segment table mainly contains the segment number and the
page. offset.

This technique is faster than segmentation. On the other hand, segmentation is slower than paging.

In Paging, a list of free frames is maintained by the In Segmentation, a list of holes is maintained by the Operating
Operating system. system.

In this technique, in order to calculate the absolute address In this technique, in order to calculate the absolute address segment
page number and the offset both are required. number and the offset both are required.

Question :A certain computer system has the segmented paging architecture for virtual memory. The memory is byte addressable.
Both virtual and physical address spaces contain 216 bytes each. The virtual address space is divided into 8 non-overlapping equal
size segments. The memory management unit (MMU) has a hardware segment table, each entry of which contains the physical
address of the page table for the segment. Page tables are stored in the main memory and consists of 2 byte page table entries. What
is the minimum page size in bytes so that the page table for a segment requires at most one page to store it?
Solution
Virtual Address Space = Process size = 216 bytes
Physical Address Space = Main Memory size =2 16 bytes
Process is divided into 8 equal size segments
Page table entry size = 2 bytes
Let page size = n bytes.
Now, since page table has to be stored into a single page, so we must have- Size of page table <= Page size
Size of each segment
= Process size / Number of segments
= 216 bytes / 8= 216 bytes / 23= 213 bytes= 8 KB
Number of pages each segment is divided
= Size of segment / Page size= 8 KB / n bytes = (8K / n) pages
Size of each page table
= Number of entries in page table x Page table entry size
= Number of pages the segment is divided x 2 bytes
= (8K / n) x 2 bytes= (16K / n) bytes

Page Size-Substituting values in the above condition, we get-

(16K / n) bytes <= n bytes
(16K / n) <= n
n2 >= 16K
n2 >= 214
n >= 27
Thus, minimum page size possible = 2 7 bytes = 128 bytes.
 Session Plan : S29- Virtual Memory & Thrashing

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define virtual memory and its significance in Open LMS (https://gulms.galgotiasuniversity.org/)
operating systems . Go to course Operating System(R1UC403B)
2. Explain the concept of thrashing and its Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
causes . Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Virtual Memory in Operating System

 Virtual memory is a memory management technique used by operating systems to give the appearance of a large,
continuous block of memory to applications, even if the physical memory (RAM) is limited. It allows larger applications
to run on systems with less RAM.
 The main objective of virtual memory is to support multiprogramming, The main advantage that virtual memory provides
is, a running process does not need to be entirely in memory.
 Programs can be larger than the available physical memory. Virtual Memory provides an abstraction of main memory,
eliminating concerns about storage limitations. A memory hierarchy, consisting of a computer system’s memory and a disk,
enables a process to operate with only some portions of its address space in RAM to allow more processes to be in memory.
 A virtual memory is what its name indicates- it is an illusion of a memory that is larger than the real memory. We refer to
the software component of virtual memory as a virtual memory manager. The basis of virtual memory is the non-contiguous
memory allocation model. The virtual memory manager removes some components from memory to make room for other
components.
 The size of virtual storage is limited by the addressing scheme of the computer system and the amount of secondary memory
available not by the actual number of main storage locations.

How Virtual Memory Works?

Virtual Memory is a technique that is implemented using both hardware and software. It maps memory addresses used by a program,
called virtual addresses, into physical addresses in computer memory.
 All memory references within a process are logical addresses that are dynamically translated into physical addresses at run
time. This means that a process can be swapped in and out of the main memory such that it occupies different places in the
main memory at different times during the course of execution.
 A process may be broken into a number of pieces and these pieces need not be continuously located in the main
memory during execution. The combination of dynamic run-time address translation and the use of a page or segment table
permits this.
If these characteristics are present then, it is not necessary that all the pages or segments are present in the main memory during
execution. This means that the required pages need to be loaded into memory whenever required. Virtual memory is implemented
using Demand Paging or Demand Segmentation.

Types of Virtual Memory

In a computer, virtual memory is managed by the Memory Management Unit (MMU), which is often built into the CPU. The CPU
generates virtual addresses that the MMU translates into physical addresses.
There are two main types of virtual memory:
 Paging
 Segmentation
Already explained in previous sessions.
What is Thrashing in OS?
Thrashing in OS is a phenomenon that occurs in computer operating systems when the system spends an excessive amount of
time swapping data between physical memory (RAM) and virtual memory (disk storage) due to high memory demand and low
available resources.
Thrashing can occur when there are too many processes running on a system and not enough physical memory to accommodate
them all. As a result, the operating system must constantly swap pages of memory between physical memory and virtual memory.
This can lead to a significant decrease in system performance, as the CPU is spending more time swapping pages than it is
actually executing code.

Symptoms and How to Detect it?

The following are some of the symptoms of thrashing in an operating system:
1. High CPU utilization:
When a system is thrashing, the CPU is spending a lot of time swapping pages of memory between physical memory and disk.
This can lead to high CPU utilization, even when the system is not performing any significant work.
2. Increased Disk Activity:
When the system is Thrashing in os, the disk activity increases significantly as the system tries to swap data between physical
memory and virtual memory.
3. High page fault rate:
A page fault is an event that occurs when the CPU tries to access a page of memory that is not currently in physical memory.
Thrashing can cause a high page fault rate, as the operating system is constantly swapping pages of memory between physical
memory and disk.
4. Slow Response Time:
When the system is Thrashing in os, its response time slows significantly.

If you are experiencing any of these symptoms, it is possible that your system is thrashing. You can use a system monitoring
tool to check the CPU utilization, page fault rate, and disk activity to confirm this.

Algorithms during Thrashing

At the time, when thrashing starts then the operating system tries to apply either the Global page replacement Algorithm or
the Local page replacement algorithm.

Global Page Replacement

The Global Page replacement has access to bring any page, whenever thrashing found it tries to bring more pages. Actually, due to
this, no process can get enough frames and as a result, the thrashing will increase more and more. Thus the global page
replacement algorithm is not suitable whenever thrashing happens.

Local Page Replacement

Unlike the Global Page replacement, the local page replacement will select pages which only belongs to that process. Due to this,
there is a chance of a reduction in the thrashing. As it is also proved that there are many disadvantages of Local Page replacement.
Thus local page replacement is simply an alternative to Global Page replacement.

Causes of Thrashing in OS
The main causes of thrashing in an operating system are:
1. High degree of multiprogramming:
When too many processes are running on a system, the operating system may not have enough physical memory to accommodate
them all. This can lead to thrashing, as the operating system is constantly swapping pages of memory between physical memory and
disk.

2. Lack of frames:
Frames are the units of memory that are used to store pages of memory. If there are not enough frames available, the operating
system will have to swap pages of memory to disk, which can lead to thrashing.
3. Page replacement policy:
The page replacement policy is the algorithm that the operating system uses to decide which pages of memory to swap to disk. If
the page replacement policy is not effective, it can lead to thrashing.
4. Insufficient physical memory:
If the system does not have enough physical memory, it will have to swap pages of memory to disk more often, which can lead to
thrashing.
5. Inefficient memory management:
If the operating system is not managing memory efficiently, it can lead to fragmentation of physical memory, which can also lead
to thrashing.
6. Poorly designed applications:
Applications that use excessive memory or that have poor memory management practices can also contribute to thrashing.

Techniques to Prevent Thrashing

There are a number of ways to eliminate thrashing, including:
 Increase the amount of physical memory: This is the most effective way to eliminate thrashing, as it will give the
operating system more space to store pages of memory in physical memory.
 Reduce the degree of multiprogramming: This means reducing the number of processes that are running on the system.
This can be done by terminating or suspending processes, or by denying new processes from starting.
 Use an effective page replacement policy: The page replacement policy is the algorithm that the operating system uses
to decide which pages of memory to swap to disk. An effective page replacement policy can help to minimize the number
of page faults that occur, which can help to eliminate thrashing.
 Optimize applications: Applications should be designed to use memory efficiently and to avoid memory management
practices that can lead to thrashing. For example, applications should avoid using excessive memory or using inefficient
data structures.
 Monitor the system's resource usage: Monitor the system's CPU utilization, memory usage, and disk activity. If you
notice that any of these resources are being overutilized, you may need to take steps to reduce the load on the system.
 Use a system monitoring tool: A system monitoring tool can help you to identify bottlenecks in your system and to track
the system's resource usage over time. This information can help you to identify potential problems before they cause
thrashing.

Effects on System Performance and User Experience

Thrashing has a significant negative impact on system performance and user experience. Here are some of the specific effects of
thrashing on system performance and user experience:
 Slow application response times: Thrashing can cause applications to take longer to load and respond to user input. This
is because the operating system is spending a lot of time swapping pages of memory between physical memory and disk,
rather than executing the application's code.
 Increased system load: Thrashing can cause the system to become more overloaded. This is because the CPU is spending
a lot of time swapping pages of memory between physical memory and disk, rather than executing code. This can lead to
increased CPU utilization, memory usage, and disk activity.
 System crashes: In severe cases, thrashing can cause the system to crash. This is because the operating system may not be
able to allocate enough memory to all of the running processes, or it may not be able to swap pages of memory between
physical memory and disk quickly enough.

Real-life Examples of Thrashing and their Impact on Applications

Here are some real-life examples of thrashing and their impact on applications:
1. A Web Server: A web server may thrash if it is overloaded with requests and does not have enough memory to handle
them all. This can cause the server to become unresponsive and even crash. Impact: A web server that is thrashing may be
unable to respond to requests from users, resulting in down time and lost revenue.
2. A database server: A database server may thrash if it is trying to process too many queries at the same time and does not
have enough memory to store all of the data that it needs. This can cause the server to become slow and
unresponsive. Impact: A database server that is thrashing may be unable to process transactions quickly enough, resulting
in delays for users and businesses.
3. A video editing application: A video editing application may thrash if it is trying to edit a large video file and does not
have enough memory to store the entire file in memory. This can cause the application to become slow and unresponsive,
and it may even crash. Impact: A video editing application that is thrashing may be unable to edit videos smoothly,
resulting in unusable footage.
4. A video game: A video game may thrash if it is trying to render a large scene and does not have enough memory to store
all of the textures and other resources that it needs. This can cause the game to become slow and laggy. Impact: A video
game that is thrashing may be unplayable, due to lag and stuttering.
 Notes : S30- Cache Memory Organization

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define cache memory and identify its basic Open LMS (https://gulms.galgotiasuniversity.org/)
components (e.g., cache lines, cache blocks). Go to course Operating System(R1UC403B)
2. Explain how cache memory is organized . Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

Cache Memory in Computer Organization

Cache Memory is a special very high-speed memory. The cache is a smaller and faster memory that stores copies of the data from
frequently used main memory locations. There are various different independent caches in a CPU, which store instructions and
data. The most important use of cache memory is that it is used to reduce the average time to access data from the main memory.
The concept of cache works because there exists locality of reference (the same items or nearby items are more likely to be
accessed next) in processes.

Characteristics of Cache Memory

 Extremely fast memory type that acts as a buffer between RAM and the CPU.
 Holds frequently requested data and instructions, ensuring that they are immediately available to the CPU when needed.
 Costlier than main memory or disk memory but more economical than CPU registers.
 Used to speed up processing and synchronize with the high-speed CPU.

Levels of Memory
 Level 1 or Register: It is a type of memory in which data is stored and accepted that are immediately stored in the CPU.
The most commonly used register is Accumulator, Program counter , Address Register, etc.
 Level 2 or Cache memory: It is the fastest memory that has faster access time where data is temporarily stored for faster
access.
 Level 3 or Main Memory: It is the memory on which the computer works currently. It is small in size and once power is
off data no longer stays in this memory.
 Level 4 or Secondary Memory: It is external memory that is not as fast as the main memory but data stays permanently
in this memory.

Cache Performance
When the processor needs to read or write a location in the main memory, it first checks for a corresponding entry in the cache.
 If the processor finds that the memory location is in the cache, a Cache Hit has occurred and data is read from the cache.
 If the processor does not find the memory location in the cache, a cache miss has occurred. For a cache miss, the cache
allocates a new entry and copies in data from the main memory, then the request is fulfilled from the contents of the
cache.
The performance of cache memory is frequently measured in terms of a quantity called Hit ratio.

We can improve Cache performance using higher cache block size, and higher associativity, reduce miss rate, reduce miss penalty,
and reduce the time to hit in the cache.

Locality of reference
Locality of reference refers to a phenomenon in which a computer program tends to access same set of memory locations for a
particular time period. In other words, Locality of Reference refers to the tendency of the computer program to access instructions
whose addresses are near one another. The property of locality of reference is mainly shown by loops and subroutine calls in a
program.
Locality of Reference and Cache Operation in Cache Memory

In the above figure, you can see that the CPU wants to read or fetch the data or instruction. First, it will access the cache memory
as it is near to it and provides very fast access. If the required data or instruction is found, it will be fetched. This situation is
known as a cache hit. But if the required data or instruction is not found in the cache memory then this situation is known as a
cache miss. Now the main memory will be searched for the required data or instruction that was being searched and if found will
go through one of the two ways:
1. First way is that the CPU should fetch the required data or instruction and use it and that’s it but what, when the same
data or instruction is required again. CPU again has to access the same main memory location for it and we already know
that main memory is the slowest to access.
2. The second way is to store the data or instruction in the cache memory so that if it is needed soon again in the near future
it could be fetched in a much faster way.

Cache Operation:
Temporal Locality – Temporal locality means current data or instruction that is being fetched may be needed soon. So we should
store that data or instruction in the cache memory so that we can avoid again searching in main memory for the same data.
Spatial locality means instruction or data near to the current memory location that is being fetched, may be needed soon in the
near future. This is slightly different from the temporal locality. Here we are talking about nearly located memory locations while
in temporal locality we were talking about the actual memory location that was being fetched.

Application of Cache Memory

Here are some of the applications of Cache Memory.
 Primary Cache: A primary cache is always located on the processor chip. This cache is small and its access time is
comparable to that of processor registers.
 Secondary Cache: Secondary cache is placed between the primary cache and the rest of the memory. It is referred to as
the level 2 (L2) cache. Often, the Level 2 cache is also housed on the processor chip.
 Spatial Locality of Reference: Spatial Locality of Reference says that there is a chance that the element will be present
in close proximity to the reference point and next time if again searched then more close proximity to the point of
reference.
 Temporal Locality of Reference: Temporal Locality of Reference uses the Least recently used algorithm will be used.
Whenever there is page fault occurs within a word will not only load the word in the main memory but the complete page
fault will be loaded because the spatial locality of reference rule says that if you are referring to any word next word will
be referred to in its register that’s why we load complete page table so the complete block will be loaded.

Advantages
 Cache Memory is faster in comparison to main memory and secondary memory.
 Programs stored by Cache Memory can be executed in less time.
 The data access time of Cache Memory is less than that of the main memory.
 Cache Memory stored data and instructions that are regularly used by the CPU, therefore it increases the performance of
the CPU.
Disadvantages
 Cache Memory is costlier than primary memory and secondary memory .
 Data is stored on a temporary basis in Cache Memory.
 Whenever the system is turned off, data and instructions stored in cache memory get destroyed.
 The high cost of cache memory increases the price of the Computer System.
 Notes : S31- I/O Devices and I/O Subsystems

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define I/O devices. Open LMS (https://gulms.galgotiasuniversity.org/)
2. Explain how I/O subsystems manage data Go to course Operating System(R1UC403B)
transfer between the CPU and I/O devices. Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

I/O Systems and Subsystems

I/O devices are very important in the computer systems. They provide users the means of interacting with the system. So there is a
separate I/O system devoted to handling the I/O devices.

The different Components of the I/O systems are −

I/O Application Interface

I/O Hardware
 There are many I/O devices handled by the operating system such as mouse, keyboard, disk drive etc.
 There are different device drivers that can be connected to the operating system to handle a specific device.
 The device controller is an interface between the device and the device driver.

The I/O software

 The I/O software contains the user level libraries and the kernel modules. The libraries provide the interface to the
user program to perform input and output.
 The kernel modules provide the device drivers that interact with the device controllers.
 The I/O software should be device independent so that the programs can be used for any I/O device without
specifying it in advance.
 For example - A program that reads a file should be able the read the file on a hard disk, floppy disk, CD-ROM etc.
without having to change the program each time.
The user applications can access all the I/O devices using the device drivers, which are device specific codes. The application
layer sees a common interface for all the devices. Most of the devices are either block I/O and character I/O devices. Block
devices are accessed one block at a time whereas character devices are accessed one character at a time.

The kernel I/O services are: I/O scheduling, Caching, Buffering, Spooling, Device Reservation, I/O Protection, and Error
1. Scheduling
It means to determine a good order in which to execute input/output requests called disk scheduling.
Scheduling I/O requests can greatly improve overall efficiency. Priorities can also play a vital role in request scheduling and can
reduce the average waiting time for I/O to complete.
By this device access, permissions will be fair to all jobs. When an application issues a blocking I/O system call, the request is
placed on the job queue for that device. The order of the queue rearranges by the Kernel I/O scheduler to improve the overall
system efficiency.

2. Caching
It involves keeping a copy of data in a faster access location than where the data is normally stored.
For example, when you request a file by looking at a Web page are stored on your hard disk in a cache subdirectory under the
directory for your browser. When you get back to a page you have recently visited, the browser can get those files from the cache
rather than the original server, saving you time and saving the network the burden of additional traffic.
There is a difference between cache and buffer is cache is a duplicate copy of some other data stored elsewhere whereas buffer
stores copy of an existing data item.

3. Buffering
Buffer is a memory area maintains by Kernel I/O Subsystem that stores data while they are transferred between two devices or
between a device with an application.
Buffering is done for three reasons.
1. One reason is to adapt to devices that have different data transfer sizes.
2. A second use of buffering is to support copy semantics for an application I/O. An application wants to write data on disk
which is stored in its buffer, it is called “copy semantic ”. it calls the write() system call, providing a pointer to the buffer
and the integer specify the number of bytes to write.
3. A third one is to cope with the speed mismatch between the producer and consumer of the data stream.

4. Spooling
A spool is a type of buffer that holds output for a device. It is the process in which jobs from the cards are read directly onto the
disk and the location of that card in the disk is recorded in a table by the operating system. When that job is required for execution,
it is read from the disk.
For example, several applications may wish to print their output concurrently, so spooling solves this problem by maintaining a
queue for the output. A printer does not accept interleaved data. The output of all application is spooled in a separate disk file.
When an application finishes printing then the spooling system queues the corresponding spool file for output to the printer.

5. Device Reservation
It provides exclusive device access. Allocation of devices when required by the processes and that device when it is no longer
needed. It prevents deadlock. Many operating systems provide features that enable processes to coordinate and give exclusive
access to them.

6. I/O Protection
I/O must be performed via system calls. User processes may accidentally or purposefully attempt to disrupt normal operation via
illegal I/O instructions. To prevent a user from do all I/O instructions defined to be privileged.

7. Error Handling
An operating system that uses protected memory that can guard against many kinds of hardware and application errors. Devices
and I/O transfers may fail in some manner, either for transient reasons, as when a network becomes overloaded or for permanent
reasons, as when a disk controller becomes defective.
 Notes : S32- I/O Buffering in Operating Systems

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define I/O buffering and identify its basic Open LMS (https://gulms.galgotiasuniversity.org/)
purpose. Go to course Operating System(R1UC403B)
2. Explain how I/O buffering works and the Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
different types of buffering techniques (e.g., Click on “Session-wise Pre & Post Class Assessments”
single buffering, double buffering, circular  Attempt Assessment quizzes.
buffering).

I/O buffering and its Various Techniques

A buffer is a memory area that stores data being transferred between two devices or between a device and an application.

What is I/O Buffering?

I/O buffering is a technique used in computer systems to improve the efficiency of input and output (I/O) operations. It involves
the temporary storage of data in a buffer, which is a reserved area of memory, to reduce the number of I/O operations and manage
the flow of data between fast and slow devices or processes
Uses of I/O Buffering
 Buffering is done to deal effectively with a speed mismatch between the producer and consumer of the data stream.
 A buffer is produced in the main memory to heap up the bytes received from the modem.
 After receiving the data in the buffer, the data gets transferred to disk from the buffer in a single operation.
 This process of data transfer is not instantaneous; therefore the modem needs another buffer to store additional incoming
data.
 When the first buffer is filled, then it is requested to transfer the data to disk.
 The modem then starts filling the additional incoming data in the second buffer while the data in the first buffer gets
transferred to the disk.
 When both buffers complete their tasks, then the modem switches back to the first buffer while the data from the second
buffer gets transferred to the disk.
 The use of two buffers disintegrates the producer and the consumer of the data, thus minimizing the time requirements
between them.
 Buffering also provides variations for devices that have different data transfer sizes.

Types of I/O Buffering Techniques

1. Single Buffer
Using one buffer to store data temporarily. A buffer is provided by the operating system to the system portion of the main memory.
Block Oriented Device
 The system buffer takes the input.
 After taking the input, the block gets transferred to the user space by the process and then the process requests for another
block.
 Two blocks work simultaneously, when one block of data is processed by the user process, the next block is being read
in.
 OS can swap the processes.
 OS can record the data of the system buffer to user processes.
Stream Oriented Device
 Line- at a time operation is used for scroll-made terminals. The user inputs one line at a time, with a carriage return
signalling at the end of a line.
 Byte-at-a-time operation is used on forms mode, terminals when each keystroke is significant.
2. Double Buffer
In this technique the operating system Uses two buffers to allow continuous data transfer between two process or two devices.
Block Oriented
 There are two buffers in the system.
 One buffer is used by the driver or controller to store data while waiting for it to be taken by higher level of the hierarchy.
 Other buffer is used to store data from the lower level module.
 Double buffering is also known as buffer swapping.
 A major disadvantage of double buffering is that the complexity of the process get increased.
 If the process performs rapid bursts of I/O, then using double buffering may be deficient.
Stream Oriented
 Line- at a time I/O, the user process need not be suspended for input or output, unless process runs ahead of the double
buffer.
 Byte- at a time operations, double buffer offers no advantage over a single buffer of twice the length.

3. Circular Buffer
In this technique the operating system Uses a circular buffer to manage continuous data streams efficiently.
 When more than two buffers are used, the collection of buffers is itself referred to as a circular buffer.
 In this, the data do not directly pass from the producer to the consumer because the data would change due to overwriting
of buffers before they had been consumed.
 The producer can only fill up to buffer i-1 while data in buffer i is waiting to be consumed.

Buffering Type Example Scenario Technical Implementation

- OS provides a 16-byte buffer for keystrokes

Single Buffering Keyboard input processing - CPU blocks while keypress is written to buffer
- Process consumes entire buffer before next input

- Front buffer: Displayed on screen

Double Buffering GPU frame rendering
- Back buffer: GPU renders next frame

- Ring buffer stores incoming Ethernet packets

- NIC writes to head pointer
Circular Buffering Network packet reception
- Kernel reads from tail pointer
- Head wraps around at buffer end
Differences Between Spooling and Buffering
Spooling Buffering

It overlap the input/output of one job with the It overlaps the input/output of one job with the
Basic Difference execution of another job. execution of the same job.

Full form (stands

Simultaneous peripheral operation online No full form
for)

Efficiency Spooling is more efficient than buffering buffering is less efficient than spooling.

Consider Size It consider disk as a huge spool or buffer. Buffer is limited area in main memory.

remote processing It can process data at remote places. It does not support remote processing.

Implemented using spoolers which manage Implemented through software or hardware-based

input/output requests and allocate resources as mechanisms such as circular buffers
Implementation needed or FIFO queues

Can handle large amounts of data since spooled Limited by the size of memory available for
Capacity data is stored on disk or other external storage buffering.

Since data is stored on external storage, spooling

Error can occur if buffer overflow happens, which
can help recover from system crashes or other
can cause data loss or corruption.
Error handling errors

More complex than buffering since spooling

Less complex than spooling since buffering is a
requires additional software to manage
simpler technique for managing data transfer.
Complexity input/output requests.
 Notes : S33- Disk Scheduling Algorithms

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define disk scheduling and identify common Open LMS (https://gulms.galgotiasuniversity.org/)
disk scheduling algorithms (e.g., FCFS, SSTF, Go to course Operating System(R1UC403B)
SCAN, C-SCAN). Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
2. Explain how different disk scheduling Click on “Session-wise Pre & Post Class Assessments”
algorithms work (e.g., FCFS, SSTF, SCAN,  Attempt Assessment quizzes.
C-SCAN).

Disk storage (also sometimes called drive storage) is a data storage mechanism based on a rotating disk. The recording employs
various electronic, magnetic, optical, or mechanical changes to the disk's surface layer. A disk drive is a device implementing such
a storage mechanism. Notable types are hard disk drives (HDD), containing one or more non-removable rigid platters; the floppy
disk drive (FDD) and its removable floppy disk; and various optical disc drives (ODD) and associated optical disc media.

Disk Scheduling Algorithms

• A process needs two type of time, CPU time and IO time. For I/O, it requests the Operating system to access the disk.
• Operating system must be fair enough to satisfy each request and at the same time, operating system must maintain the
efficiency and speed of process execution.
• The technique that operating system uses to determine the request which is to be satisfied next is called disk scheduling.

Disk scheduling algorithms are crucial in managing how data is read from and written to a computer’s hard disk. These algorithms
help determine the order in which disk read and write requests are processed, significantly impacting the speed and efficiency of
data access. Common disk scheduling methods include First-Come, First-Served (FCFS), Shortest Seek Time First (SSTF), SCAN,
C-SCAN, LOOK, and C-LOOK. By understanding and implementing these algorithms, we can optimize system performance and
ensure faster data retrieval.
 Disk scheduling is a technique operating systems use to manage the order in which disk I/O (input/output) requests are
processed.
 Disk scheduling is also known as I/O Scheduling.
 The main goals of disk scheduling are to optimize the performance of disk operations; reduce the time it takes to access
data and improve overall system efficiency.

Importance of Disk Scheduling in Operating System

 Multiple I/O requests may arrive by different processes and only one I/O request can be served at a time by the disk
controller. Thus other I/O requests need to wait in the waiting queue and need to be scheduled.
 Two or more requests may be far from each other so this can result in greater disk arm movement.
 Hard drives are one of the slowest parts of the computer system and thus need to be accessed in an efficient manner.

Key Terms Associated with Disk Scheduling

 Seek Time: Seek time is the time taken to locate the disk arm to a specified track where the data is to be read or written.
So the disk scheduling algorithm that gives a minimum average seek time is better.
 Rotational Latency: Rotational Latency is the time taken by the desired sector of the disk to rotate into a position so that
it can access the read/write heads. So the disk scheduling algorithm that gives minimum rotational latency is better.
 Transfer Time: Transfer time is the time to transfer the data. It depends on the rotating speed of the disk and the number
of bytes to be transferred.
 Disk Access Time:
Disk Access Time = Seek Time + Rotational Latency + Transfer Time
Total Seek Time = Total head Movement * Seek Time
Disk Access Time and Disk Response Time
 Disk Response Time: Response Time is the average time spent by a request waiting to perform its I/O operation. The
average Response time is the response time of all requests. Variance Response Time is the measure of how individual
requests are serviced with respect to average response time. So the disk scheduling algorithm that gives minimum
variance response time is better.

Goal of Disk Scheduling Algorithms

 Minimize Seek Time
 Maximize Throughput
 Minimize Latency
 Fairness
 Efficiency in Resource Utilization

Disk Scheduling Algorithms

There are several Disk Several Algorithms.
1. FCFS (First Come First Serve)
2. SSTF (Shortest Seek Time First)
3. SCAN
4. C-SCAN
5. LOOK
6. C-LOOK

1. FCFS (First Come First Serve)

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

Example:
Suppose the order of request is- (82,170,43,140,24,16,190)
And current position of Read/Write head is: 50
So, total overhead movement (total distance covered by the disk arm) =
(82-50)+(170-82)+(170-43)+(140-43)+(140-24)+(24-16)+(190-16) =642

Advantages of FCFS: Every request gets a fair chance , No indefinite postponement

Disadvantages of FCFS: Does not try to optimize seek time, May not provide the best possible service

2. SSTF (Shortest Seek Time First)

In SSTF (Shortest Seek Time First), requests having the shortest seek time are executed first. So, the seek time of every request is
calculated in advance in the queue and then they are scheduled according to their calculated seek time. As a result, the request near
the disk arm will get executed first. SSTF is certainly an improvement over FCFS as it decreases the average response time and
increases the throughput of the system. Let us understand this with the help of an example.
Example:
Suppose the order of request is- (82,170,43,140,24,16,190)
And current position of Read/Write head is: 50
So, total overhead movement (total distance covered by the disk arm) =
(50-43)+(43-24)+(24-16)+(82-16)+(140-82)+(170-140)+(190-170) =208

Advantages of Shortest Seek Time First

Here are some of the advantages of Shortest Seek Time First.
 The average Response Time decreases
 Throughput increases

Disadvantages of Shortest Seek Time First

Here are some of the disadvantages of Shortest Seek Time First.
 Overhead to calculate seek time in advance
 Can cause Starvation for a request if it has a higher seek time as compared to incoming requests
 The high variance of response time as SSTF Favors only some requests

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

Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at 50, and it is also given that the
disk arm should move “towards the larger value”.
Therefore, the total overhead movement (total distance covered by the disk arm) is calculated as
= (199-50) + (199-16) = 332

Advantages of SCAN Algorithm

Here are some of the advantages of the SCAN Algorithm.
 High throughput
 Low variance of response time
 Average response time

Disadvantages of SCAN Algorithm

Here are some of the disadvantages of the SCAN Algorithm.
 Long waiting time for requests for locations just visited by disk arm
4. C-SCAN
In the SCAN algorithm, the disk arm again scans the path that has been scanned, after reversing its direction. So, it may be
possible that too many requests are waiting at the other end or there may be zero or few requests pending at the scanned area.
These situations are avoided in the CSCAN algorithm in which the disk arm instead of reversing its direction goes to the other end
of the disk and starts servicing the requests from there. So, the disk arm moves in a circular fashion and this algorithm is also
similar to the SCAN algorithm hence it is known as C-SCAN (Circular SCAN).
Example:

Circular SCAN
Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at 50, and it is also given that the
disk arm should move “towards the larger value”.
So, the total overhead movement (total distance covered by the disk arm) is calculated as:
=(199-50) + (199-0) + (43-0) = 391

Advantages of C-SCAN Algorithm

Here are some of the advantages of C-SCAN.
 Provides more uniform wait time compared to SCAN.

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

LOOK Algorithm
Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at 50, and it is also given that the
disk arm should move “towards the larger value”.
So, the total overhead movement (total distance covered by the disk arm) is calculated as:
= (190-50) + (190-16) = 314
6. C-LOOK
As LOOK is similar to the SCAN algorithm, in a similar way, C-LOOK is similar to the CSCAN disk scheduling algorithm. In
CLOOK, the disk arm in spite of going to the end goes only to the last request to be serviced in front of the head and then from
there goes to the other end’s last request. Thus, it also prevents the extra delay which occurred due to unnecessary traversal to the
end of the disk.
Example:
1. Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at 50, and it is also given
that the disk arm should move “towards the larger value”

So, the total overhead movement (total distance covered by the disk arm) is calculated as
= (190-50) + (190-16) + (43-16) = 341
 Notes : S34- RAID

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define RAID and identify its basic purpose. Open LMS (https://gulms.galgotiasuniversity.org/)
2. Explain how different RAID levels work Go to course Operating System(R1UC403B)
Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

RAID (Redundant Arrays of Independent Disks)

RAID (Redundant Arrays of Independent Disks) is a technique that makes use of a combination of multiple disks for storing the
data instead of using a single disk for increased performance, data redundancy, or to protect data in the case of a drive failure. The
term was defined by David Patterson, Garth A. Gibson, and Randy Katz at the University of California, Berkeley in 1987.

What is RAID?
RAID (Redundant Array of Independent Disks) is like having backup copies of your important files stored in different places on
several hard drives or solid-state drives (SSDs). If one drive stops working, your data is still safe because you have other copies
stored on the other drives. It’s like having a safety net to protect your files from being lost if one of your drives breaks down.
RAID (Redundant Array of Independent Disks) in a Database Management System (DBMS) is a technology that combines multiple
physical disk drives into a single logical unit for data storage. The main purpose of RAID is to improve data reliability, availability,
and performance. There are different levels of RAID, each offering a balance of these benefits.

How RAID Works?

Let’s understand how RAID (Redundant Array of Independent Disks) works through a relatable example:
Imagine you have a favourite book that you want to keep safe. Instead of giving the entire book to just one friend for safekeeping,
you take a smart approach:
1. Splitting the Book: You divide the book into smaller pieces (like chapters or sections) and give each piece to a different
friend.
2. Making Copies: For extra security, you might also create duplicate pieces and give them to multiple friends.
Now, if one friend misplaces their piece, you can still recreate the entire book using the pieces held by the others. This way, your
book is safe even if someone loses their portion.
This is exactly how RAID works with hard drives! RAID splits your data across multiple drives (similar to dividing the book into
pieces). Depending on the RAID configuration, it may also create duplicates (like making extra copies). If one drive fails, the
remaining drives can help reconstruct the lost data.

What is a RAID Controller?

A RAID controller is like a boss for your hard drives in a big storage system. It works between your computer’s operating system
and the actual hard drives, organizing them into groups to make them easier to manage. This helps speed up how fast your computer
can read and write data, and it also adds a layer of protection in case one of your hard drives breaks down. So, it’s like having a
smart helper that makes your hard drives work better and keeps your important data safer.

Types of RAID Controller

There are three types of RAID controller:

Hardware Based: In hardware-based RAID, there’s a physical controller that manages the whole array. This controller can handle
the whole group of hard drives together. It’s designed to work with different types of hard drives, like SATA (Serial Advanced
Technology Attachment) or SCSI (Small Computer System Interface). Sometimes, this controller is built right into the computer’s
main board, making it easier to set up and manage your RAID system. It’s like having a captain for your team of hard drives, making
sure they work together smoothly.
Software Based: In software-based RAID, the controller doesn’t have its own special hardware. So it use computer’s main processor
and memory to do its job. It perform the same function as a hardware-based RAID controller, like managing the hard drives and
keeping your data safe. But because it’s sharing resources with other programs on your computer, it might not make things run as
fast. So, while it’s still helpful, it might not give you as big of a speed boost as a hardware-based RAID system

Firmware Based: Firmware-based RAID controllers are like helpers built into the computer’s main board. They work with the
main processor, just like software-based RAID. But they only implement when the computer starts up. Once the operating system
is running, a special driver takes over the RAID job. These controllers aren’t as expensive as hardware ones, but they make the
computer’s main processor work harder. People also call them hardware-assisted software RAID, hybrid model RAID, or fake
RAID.

Key Evaluation Points for a RAID System

When evaluating a RAID system, the following critical aspects should be considered:
1. Reliability
Definition: Refers to the system’s ability to tolerate disk faults and prevent data loss.
Key Questions:
 How many disk failures can the RAID configuration sustain without losing data?
 Is there redundancy in the system, and how is it implemented (e.g., parity, mirroring)?
Example:
 RAID 0 offers no fault tolerance; if one disk fails all data is lost.
 RAID 5 can tolerate one disk failure due to parity data.
 RAID 6 can handle two simultaneous disk failures.
2. Availability
Definition: The fraction of time the RAID system is operational and available for use.
Key Questions:
 What is the system’s uptime, and how quickly can it recover from failures?
 Can data be accessed during disk rebuilds or replacements?
Example:
 RAID 1 (Mirroring) allows immediate data access even during a single disk failure.
 RAID 5 and 6 may degrade performance during a rebuild, but data remains available.
3. Performance
Definition: Measures how efficiently the RAID system handles data processing tasks. This includes:
 Response Time: How quickly the system responds to data requests.
 Throughput: The rate at which the system processes data (e.g., MB/s or IOPS).
Key Factors:
 RAID levels affect performance differently:
 RAID 0 offers high throughput but no redundancy.
 RAID 1 improves read performance by serving data from either mirrored disk but may not improve write performance
significantly.
 RAID 5/6 introduces overhead for parity calculations, affecting write speeds.
 Workload type (e.g., sequential vs. random read/write operations).
Performance Trade-offs: Higher redundancy often comes at the cost of slower writes (due to parity calculations).
4. Capacity
Definition: The amount of usable storage available to the user after accounting for redundancy mechanisms.
Key Calculation: For a set of N disks, each with B blocks, the available capacity depends on the RAID level:
 RAID 0: All N×B blocks are usable (no redundancy).
 RAID 1: Usable capacity is B (only one disk’s capacity due to mirroring).
 RAID 5: Usable capacity is (N−1)×B (one disk’s worth of capacity used for parity).
 RAID 6: Usable capacity is (N−2)×B (two disks’ worth used for parity).
Trade-offs: Higher redundancy (RAID 5/6) reduces available capacity compared to non-redundant setups (RAID 0).
RAID is very transparent to the underlying system. This means, that to the host system, it appears as a single big disk presenting
itself as a linear array of blocks. This allows older technologies to be replaced by RAID without making too many changes to the
existing code.

Different RAID Levels

 RAID-0 (Stripping)
 RAID-1 (Mirroring)
 RAID-2 (Bit-Level Stripping with Dedicated Parity)
 RAID-3 (Byte-Level Stripping with Dedicated Parity)
 RAID-4 (Block-Level Stripping with Dedicated Parity)
 RAID-5 (Block-Level Stripping with Distributed Parity)
 RAID-6 (Block-Level Stripping with two Parity Bits)
Standard RAID Levels
1. RAID 0 (block-level striping without parity or mirroring) provides improved performance and additional storage but
no redundancy or fault tolerance (making it not true RAID, according to the acronym's definition). However, because of
the similarities to RAID (especially the need for a controller to distribute data across multiple disks), simple stripe sets are
normally referred to as RAID 0. Any disk failure destroys the array, and the likelihood of failure increases with more disks
in the array (at a minimum, catastrophic data loss is twice as likely compared to single drives without RAID). A single disk
failure destroys the entire array because when data is written to a RAID 0 volume, the data is broken into fragments called
blocks. The number of blocks is dictated by the stripe size, which is a configuration parameter of the array. The blocks are
written to their respective disks simultaneously on the same sector. This allows smaller sections of the entire chunk of data
to be read off the drive in parallel, increasing bandwidth. RAID 0 does not implement error checking, so any error is
uncorrectable. More disks in the array mean higher bandwidth, but greater risk of data loss.

Pros:
 Greatly improves read/write performance
 Inexpensive and easy to implement
 Has high storage efficiency
Cons:
 Has no data redundancy at all
 Failure probability increases with each additional disk

2. In RAID 1 (mirroring without parity or striping), data is written identically to multiple disks (a "mirrored set"). Although
many implementations create sets of 2 disks, sets may contain 3 or more disks. Array provides fault tolerance from disk
errors or failures and continues to operate as long as at least one drive in the mirrored set is functioning. Increased read
performance occurs when using a multi-threaded operating system that supports split seeks, as well as a very small
performance reduction when writing. Using RAID 1 with a separate controller for each disk is sometimes called duplexing.
Pros:
 Greatly improves fault tolerance
 Greatly improves read performance
 Inexpensive and easy to implement
 Easier to rebuild data after failure
 Can sometimes sustain multiple failures
Cons:
 Has no write performance increase
 Has low redundancy/storage efficiency

3. In RAID 2 (bit-level striping with dedicated Hamming-code parity), all disk spindle rotation is synchronized, and data
is striped such that each sequential bit is on a different disk. Hamming-code parity is calculated across corresponding bits
on disks and stored on one or more parity disks. Extremely high data transfer rates are possible.
4. In RAID 3 (byte-level striping with dedicated parity), all disk spindle rotation is synchronized, and data is striped such
that each sequential byte is on a different disk. Parity is calculated across corresponding bytes on disks and stored on a
dedicated parity disk. Very high data transfer rates are possible.
5. RAID 4 (block-level striping with dedicated parity) is identical to RAID 5 (see below), but confines all parity data to a
single disk, which can create a performance bottleneck. In this setup, files can be distributed between multiple disks. Each
disk operates independently which allows I/O requests to be performed in parallel, though data transfer speeds can suffer
due to the type of parity. The error detection is achieved through dedicated parity and is stored in a separate, single disk
unit.

6. RAID 5 (block-level striping with distributed parity) distributes parity along with the data and requires all drives but
one to be present to operate; drive failure requires replacement, but the array is not destroyed by a single drive failure.
Upon drive failure, any subsequent reads can be calculated from the distributed parity such that the drive failure is masked
from the end user. The array will have data loss in the event of a second drive failure and is vulnerable until the data that
was on the failed drive is rebuilt onto a replacement drive. A single drive failure in the set will result in reduced performance
of the entire set until the failed drive has been replaced and rebuilt.
Pros:
 Greatly improves fault tolerance
 Greatly improves read performance
 Has high redundancy/storage efficiency
Cons:
 Expensive and difficult to implement
 More difficult to rebuild data after failure

7. RAID 6 (block-level striping with double distributed parity) provides fault tolerance from two drive failures; array
continues to operate with up to two failed drives. This makes larger RAID groups more practical, especially for high-
availability systems. This becomes increasingly important as large-capacity drives lengthen the time needed to recover
from the failure of a single drive. Single-parity RAID levels are as vulnerable to data loss as a RAID 0 array until the failed
drive is replaced and its data rebuilt; the larger the drive, the longer the rebuild will take. Double parity gives time to rebuild
the array without the data being at risk if a single additional drive fails before the rebuild is complete.
 Notes : S35- File Concept and Organization

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define a file and identify its basic attributes Open LMS (https://gulms.galgotiasuniversity.org/)
(e.g., name, size, type). Go to course Operating System(R1UC403B)
2. Explain how files are organized and managed Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
by the operating system. Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

 A file can be defined as a data structure which stores the sequence of records. Files are stored in a file system, which may
exist on a disk or in the main memory. Files can be simple (plain text) or complex (specially-formatted).
 The collection of files is known as Directory.
 The collection of directories at the different levels, is known as File System. File system is the part of the operating system
which is responsible for file management. It provides a mechanism to store the data and access to the file contents including
data and programs. Some Operating systems treats everything as a file for example Ubuntu.
 The major concern about the file is deciding where to store the files on the hard disk. There are various disks scheduling
algorithm which will be covered later in this tutorial. A File may or may not be stored within only one block. It can be
stored in the noncontiguous blocks on the disk. We need to keep track of all the blocks on which the part of the files resides.

File Systems in Operating System

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.

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.
 NTFS (New Technology File System): A modern file system used by Windows. It supports features such as file and folder
permissions, compression, and encryption.
 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.

Files Attributes And Their Operations

1.Name:
Every file carries a name by which the file is recognized in the file system. One directory cannot have two files with the same
name.
2.Identifier:
Each File has its own extension which identifies the type of the file. For example, a text file has the extension .txt, A video
file can have the extension .mp4.
3.Type :
In a File System, the Files are classified in different types such as video files, audio files, text files, executable files, etc.
4.Location:
In the File System, there are several locations on which, the files can be stored. Each file carries its location as its attribute.
5.Size:
The Size of the File is one of its most important attributes. By size of the file, we mean the number of bytes acquired by the
file in the memory.
6.Protection:
The admin of the computer may want the different protections for the different files. Therefore, each file carries its own set of
permissions to the different group of Users.
7.Time and Date:
Every file carries a time stamp which contains the time and date on which the file is last modified.
File Types and Their Content
 Notes : S36- File Directories

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define a file directory and identify its basic Open LMS (https://gulms.galgotiasuniversity.org/)
purpose. Go to course Operating System(R1UC403B)
2. Explain how directories are structured and Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
managed by the operating system. Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

File Directory
 Directory can be defined as the listing of the related files on the disk. The directory may store some or the entire file
attributes.
 To get the benefit of different file systems on the different operating systems, 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.

Every Directory supports a number of common operations on the file:

1. File Creation
2. Search for the file
3. File deletion
4. Renaming the file
5. Traversing Files
6. Listing of files

File Directories
The collection of files is a file directory. The directory contains information about the files, including attributes, location, and
ownership. Much of this information, especially that is concerned with storage, is managed by the operating system. The directory
is itself a file, accessible by various file management routines.
Below are information contained in a device directory.
 Name
 Type
 Address
 Current length
 Maximum length
 Date last accessed
 Date last updated
 Owner id
 Protection information

The operation performed on the directory are:

 Search for a file
 Create a file
  Delete a file
 List a directory
 Rename a file
 Traverse the file system

Advantages of Maintaining Directories

 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.

Structures of Directory in Operating System

A directory is a container that is used to contain folders and files. It organizes files and folders in a hierarchical manner. In other
words, directories are like folders that help organize files on a computer. Just like you use folders to keep your papers and documents
in order, the operating system uses directories to keep track of files and where they are stored. Different structures of directories can
be used to organize these files, making it easier to find and manage them.
Understanding these directory structures is important because it helps in efficiently organizing and accessing files on your computer.
Following are the logical structures of a directory, each providing a solution to the problem faced in the previous type of directory
structure.

Different Types of Directories in OS

In an operating system, there are different types of directory structures that help organize and manage files efficiently.
Directories in an OS can be single-level, two-level, or hierarchical.
Each type of directory has its own way of arranging files and directories, offering unique benefits and features. These are:
 Single-Level Directory
 Two-Level Directory
 Tree Structure/ Hierarchical Structure

1) Single-Level Directory
The single-level directory is the simplest directory structure. In it, all files are contained in the same directory which makes it
easy to support and understand.
A single level directory has a significant limitation, however, when the number of files increases or when the system has more than
one user. Since all the files are in the same directory, they must have a unique name. If two users call their dataset test, then the
unique name rule violated.

Advantages
 Since it is a single directory, so its implementation is very easy.
 If the files are smaller in size, searching will become faster.
 The operations like file creation, searching, deletion, updating are very easy in such a directory structure.
 Logical Organization : Directory structures help to logically organize files and directories in a hierarchical structure. This
provides an easy way to navigate and manage files, making it easier for users to access the data they need.
  Increased Efficiency: Directory structures can increase the efficiency of the file system by reducing the time required to
search for files. This is because directory structures are optimized for fast file access, allowing users to quickly locate the
file they need.
 Improved Security : Directory structures can provide better security for files by allowing access to be restricted at the
directory level. This helps to prevent unauthorized access to sensitive data and ensures that important files are protected.
 Facilitates Backup and Recovery : Directory structures make it easier to backup and recover files in the event of a system
failure or data loss. By storing related files in the same directory, it is easier to locate and backup all the files that need to
be protected.
 Scalability: Directory structures are scalable, making it easy to add new directories and files as needed. This helps to
accommodate growth in the system and makes it easier to manage large amounts of data.

Disadvantages
 There may chance of name collision because two files can have the same name.
 Searching will become time taking if the directory is large.
 This cannot group the same type of files together.

2) Two-Level Directory
As we have seen, a single level directory often leads to confusion of files names among different users. The solution to this problem
is to create a separate directory for each user.
In the two-level directory structure, each user has their own user files directory (UFD). The UFDs have similar structures, but each
list only the files of a single user. System’s master file directory (MFD) is searched whenever a new user id is created.

Advantages
 The main advantage is there can be more than two files with same name, and would be very helpful if there are multiple
users.
 A security would be there which would prevent user to access other user’s files.
 Searching of the files becomes very easy in this directory structure.

Disadvantages
 As there is advantage of security, there is also disadvantage that the user cannot share the file with the other users.
 Unlike the advantage users can create their own files, users don’t have the ability to create subdirectories.
 Scalability is not possible because one user can’t group the same types of files together.

3) Tree Structure/ Hierarchical Structure

Tree directory structure of operating system is most commonly used in our personal computers. User can create files and
subdirectories too, which was a disadvantage in the previous directory structures.
This directory structure resembles a real tree upside down, where the root directory is at the peak. This root contains all the
directories for each user. The users can create subdirectories and even store files in their directory.
A user do not have access to the root directory data and cannot modify it. And, even in this directory the user do not have access to
other user’s directories. The structure of tree directory is given below which shows how there are files and subdirectories in each
user’s directory.
Advantages
 This directory structure allows subdirectories inside a directory.
 The searching is easier.
 File sorting of important and unimportant becomes easier.
 This directory is more scalable than the other two directory structures explained.
Disadvantages
 As the user isn’t allowed to access other user’s directory, this prevents the file sharing among users.
 As the user has the capability to make subdirectories, if the number of subdirectories increase the searching may become
complicated.
 Users cannot modify the root directory data.
 If files do not fit in one, they might have to be fit into other directories.
 Notes : S37- File Access Mechanisms

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define file access mechanisms and identify Open LMS (https://gulms.galgotiasuniversity.org/)
the basic methods (e.g., sequential, direct). Go to course Operating System(R1UC403B)
2. Explain how different file access methods Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
work (e.g., sequential, direct, indexed). Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

File Access Mechanism

When a file is used then the stored information in the file must be accessed and read into the memory of a computer system.
Various mechanism are provided to access a file from the operating system.
i. Sequential access
ii. Direct Access
iii. Index Access
Sequential Access: It is the simplest access mechanism, in which information stored in a file are accessed in an order such that
one record is processed after the other. For example, editors and compilers usually access files in this manner.

Direct Access: It is an alternative method for accessing a file, which is based on the disk model of a file, since disk allows random
access to any block or record of a file. For this method, a file is viewed as a numbered sequence of blocks or records which are
read/written in an arbitrary manner, i.e. there is no restriction on the order of reading or writing. It is well suited for Database
management System.

Index Access: In this method an index is created which contains a key field and pointers to the various block. To find an entry in
the file for a key value , we first search the index and then use the pointer to directly access a file and find the desired entry.

File Allocation Methods

1. Contiguous Allocation
If the blocks are allocated to the file in such a way that all the logical blocks of the file get the contiguous physical block in the
hard disk then such allocation scheme is known as contiguous allocation.
In the image shown below, there are three files in the directory. The starting block and the length of each file are mentioned in the
table. We can check in the table that the contiguous blocks are assigned to each file as per its need.
Advantages
• It is simple to implement.
• We will get Excellent read performance.
• Supports Random Access into files.
Disadvantages
• The disk will become fragmented.
• It may be difficult to have a file grow.

2. Linked List Allocation

• Linked List allocation solves all problems of contiguous allocation.
• In linked list allocation, each file is considered as the linked list of disk blocks. However, the disks blocks allocated to a
particular file need not to be contiguous on the disk.
• Each disk block allocated to a file contains a pointer which points to the next disk block allocated to the same file.

Advantages
• There is no external fragmentation with linked allocation.
• Any free block can be utilized in order to satisfy the file block requests.
• File can continue to grow as long as the free blocks are available.
• Directory entry will only contain the starting block address.
Disadvantages
• Random Access is not provided.
• Pointers require some space in the disk blocks.
• Any of the pointers in the linked list must not be broken otherwise the file will get corrupted.
• Need to traverse each block.

3. File Allocation Table

• The main disadvantage of linked list allocation is that the Random access to a particular block is not provided. In order to
access a block, we need to access all its previous blocks.
• File Allocation Table overcomes this drawback of linked list allocation. In this scheme, a file allocation table is
maintained, which gathers all the disk block links. The table has one entry for each disk block and is indexed by block
number.
• File allocation table needs to be cached in order to reduce the number of head seeks. Now the head doesn't need to
traverse all the disk blocks in order to access one successive block.
• It simply accesses the file allocation table, read the desired block entry from there and access that block. This is the way
by which the random access is accomplished by using FAT. It is used by MS-DOS and pre-NT Windows versions.

Advantages
• Uses the whole disk block for data.
• A bad disk block doesn't cause all successive blocks lost.
• Random access is provided although its not too fast.
• Only FAT needs to be traversed in each file operation.
Disadvantages
• Each Disk block needs a FAT entry.
• FAT size may be very big depending upon the number of FAT entries.
• Number of FAT entries can be reduced by increasing the block size but it will also increase Internal Fragmentation.
 Notes : S38- File Sharing and Implementation Issues

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]

Learning Outcome: Pre & Post Class Assessment:

By the end of this session, students will be able to: Students are required to :
1. Define file sharing and identify its basic Open LMS (https://gulms.galgotiasuniversity.org/)
purpose in multi-user systems. Go to course Operating System(R1UC403B)
2. Explain how file sharing is implemented and Search Section Titled “Sarvesh Kumar Swarnakar|| Section:34,35”
the mechanisms used to manage shared files. Click on “Session-wise Pre & Post Class Assessments”
 Attempt Assessment quizzes.

File Sharing in OS
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.

Primary Terminology Related to File Sharing

Let's see what are the various ways to achieve this, but there are some important terminologies one should know beforehand. Let's
discuss those primary terminologies first:

 Folder/Directory: It is basically like a container for all of our files on a computer. The folder can contain files and even
other folders maintaining like hierarchical structure for organizing data.
 Networking: It is involved in connecting computers or devices where we need to share the resources. Networks can be
local (LAN) or global (Internet).
 IP Address: It is numerical data given to every connected device on the network
 Protocol: It is given as the set of rules which drives the communication between devices on a network. In the context of
file sharing, protocols define how files are transferred between computers.
 File Transfer Protocol (FTP): FTP is a standard network protocol used to transfer files between a client and a server on a
computer network.

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 system. 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 dataset 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.

FTP File Sharing

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 real-
time 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 real-time 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.

Different Types of File Systems

There are several types of file systems, each designed for specific purposes and compatible with different operating systems. Some
common file system types include:
 FAT32 (File Allocation Table 32): Commonly used in older versions of Windows and compatible with various operating
systems.
 NTFS (New Technology File System): Used in modern Windows operating systems, offering improved performance,
reliability, and security features.
 ext4 (Fourth Extended File System): Used in Linux distributions, providing features such as journaling, large file support,
and extended file attributes.
 HFS+ (Hierarchical File System Plus): Used in macOS systems prior to macOS High Sierra, offering support for
journaling and case-insensitive file names.
 APFS (Apple File System): Introduced in macOS High Sierra and the default file system for macOS and iOS devices,
featuring enhanced performance, security, and snapshot capabilities.
 ZFS (Zettabyte File System): A high-performance file system known for its advanced features, including data integrity,
volume management, and efficient snapshots.
Layers in File System
A file system in an operating system is organized into multiple layers, each responsible for different aspects of file management and
storage. Here are the key layers in a typical file system:

 Application Programs: This is the topmost layer where users interact with files through applications. It provides the user
interface for file operations like creating, deleting, reading, writing, and modifying files. Examples include text editors, file
browsers, and command-line interfaces.
 Logical File system – It manages metadata information about a file i.e includes all details about a file except the actual
contents of the file. It also maintains via file control blocks. File control block (FCB) has information about a file – owner,
size, permissions, and location of file contents.
 File Organization Module – It has information about files, the location of files and their logical and physical blocks.
Physical blocks do not match with logical numbers of logical blocks numbered from 0 to N. It also has a free space that
tracks unallocated blocks.
 Basic File system – It Issues general commands to the device driver to read and write physical blocks on disk. It manages
the memory buffers and caches. A block in the buffer can hold the contents of the disk block and the cache stores frequently
used file system metadata.
 I/O Control level – Device drivers act as an interface between devices and OS, they help to transfer data between disk and
main memory. It takes block number as input and as output, it gives low-level hardware-specific instruction.
 Devices Layer: The bottommost layer, consisting of the actual hardware devices. It performs the actual reading and writing
of data to the physical storage medium. This includes hard drives, SSDs, optical disks, and other storage devices.

Implementation Issues
 Management of Disc pace: 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, check summing, 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.
Overall, file system implementation is a complex and critical component of an operating system. The efficiency and reliability of
the file system have a significant impact on the performance and stability of the entire system.

File protection/sharing of files:-

Any information present in the computer system must be protected from physical damage and improper access.
 Files can be damaged due to h/w problems such as temperature and validation and may be deleted accidently. So, there is need to
protect these files. There are many methods for providing protection to various files.
 File protection is depending on the system -in a single user system we can provide protection by simply removing floppy disks
and storing them at a safe place. -but in multi-user system, there are various mechanism used to provide protection.

They are:-
1-Type of access
2 Access control
3-Other protection approaches (such as password).

Type of access:-
 We can easily provide protection by prohibiting access. Controlled access is provided by protection mechanism. These
mechanisms can accept or reject an access depending on the type of access. The various operations that can be controlled are:-
 Read:- helps to read from the file
 Write:- helps to write or rewrite the file
 Execute:- helps to execute a stored file
 Append:- helps to write new information at the end of file.
 Delete:- helps to delete the file
 List:- helps to list the name and attribute of the file
 Various operations such as renaming, copying, editing of a file can be controlled.

Access control:-
In this approach of protection, access depends on the identity of the user .Every user uses a different type to access a file or directory.
The most common method to make a list with identity of each user and their access control. When a user requests an access for file,
then first it checks the access list related to that file. If that particular user is listed, then the operating system allows to access that
user. If not, then it leads to protection violation and operating system denies the request.

Other protection approaches (password):-

Another protection approach is to use a password for every file. So accessing a file is controlled by password.
Disadvantages:
User has to remember a large no. Of password. If a single password is used for all the files then if it gets discovered, then it makes
all the files accessible.

[Source:https://bcs.wiley.com/he-bcs/Books?action=resource&itemId=0471250600&bcsId=1743&resourceId=2437,
https://www.geeksforgeeks.org/,https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/index.html , Other Online Resources]