Unit-I

Operating system services and components

1.1 Operating System:

Concept:
 There are three categories of software. System software, Application software and Software
development languages advanced and web tools. Among these software, system software
plays important role in operating machine (computer) as it helps in starting and booting up
the machine.
 System software includes operating system, compiler and interpreter, utilities like disk
compression, disk defragmentation, disk cleanup.
 Following figure shows interaction between hardware, OS, software and users

Basic Structure of operating system: Structure of OS have layered structure.

1. User and Applications(utitlities)
2. Shell/Command interpreter
 3. Kernel
4. Hardware

Bottom most part is hardware. Upper most part is User Interface and between these two layers
kernel layer & Shell layer

1. User: On the basis of the role of users , they can be categorised as Programmers, Operational
Users (responsible for installation of software , software maintenance), End Users.

Programs (application/system) in the user interface part either provide CLI (Command Line
Interface) or GUI (Graphical User interface to the user.

User interacts with the shell or command interpreter to request for the use of resources and services
provided by the system.

2. Shell /Command interpreter: The Shell is a software that provides an interface for users of an
operating system access the services of a kernel. The shell is the layer of programming that
understands and executes the commands that user enters. In some systems shell is called as
command interpreter.

3. Kernel: The kernel is the inner most layer and is the central controlling part of operating system.
Kernel is the core of the operating system and provides basic services like process management,
memory management, file management, device management, I/o management etc. The services of
a kernel are requested by other parts of the operating system or by application program through a
specified set of program interface known as system calls.

4. Hardware: is a physical parts of computer provides basic computing resources like CPU, Memory,
I/O devices, Networking devices and other devices like motherboard, power supply, DVD writer etc.

Functions of Operating System:

An operating system (OS) manages computer resources and provides a user interface to interact
with the hardware. Key functions include managing memory, processors, devices, and files, as well
as handling input/output operations and security. It also facilitates communication between the user
and the computer. Following are the functions of operating system.

1. Memory Management:

The OS allocates and de-allocates memory to different programs and processes, ensuring efficient
use of available RAM.

It keeps track of memory usage and prevents conflicts between programs using the same memory
space.

The OS also handles virtual memory, extending the apparent size of RAM by using disk space.

2. Processor Management:

The OS manages the allocation of the CPU to different processes, ensuring that each process gets a
fair share of processing time.

It handles process scheduling, deciding which process runs next and for how long.
The OS also manages the execution of multiple processes concurrently, a concept called
multitasking.

3. Device Management:

The OS controls all hardware devices connected to the computer, like printers, keyboards, and
storage devices.

It provides a way for programs to interact with these devices through device drivers.

The OS also handles allocation and de-allocation of devices to different processes.

4. File Management:

The OS organizes files and directories on storage devices.

It provides functions for creating, deleting, renaming, and copying files and directories.

The OS also manages access permissions to files, ensuring data security.

5. Input / Output (I/O) Management:

The OS handles all input and output operations, such as reading data from the keyboard or writing
data to the screen.

It acts as an intermediary between programs and input/output devices.

6. User Interface (UI):

The OS provides a way for users to interact with the computer, either through a command-line
interface or a graphical user interface (GUI).

The UI allows users to run programs, manage files, and control hardware.

7. Security:

The OS provides security features to protect the computer system from unauthorized access and
malicious software.

It manages user accounts, access permissions, and other security-related functions.

8. Error Detection and Handling:

The OS detects and handles errors that may occur during program execution or system operation.

It provides mechanisms for error reporting, debugging, and system recovery.

9. Job Accounting:

The OS tracks resource usage by different users and processes, providing information for accounting
and performance analysis.

10. Booting:

The OS is responsible for starting the computer system when it is powered on.

It loads the necessary software components and prepares the system for use.
Functional components of operating system in brief are:

1. Process Management –

a) To provide control access to shared resources like file, memory, I/O and CPU.
b) Control the execution of user applications
c) Creation, execution and deletion of user and system processes.
d) Resume a process execution or cancel it.
e) Scheduling of a process
g) Synchronisation, inter-process communication and deadlock handling for processes.

2. Memory Management –

a) Allocation of memory to the processes

b) Free the memory from process after completion of execution
c) Reallocation of memory to a program after used block becomes free
d) Keep track of memory usage by the process

3. File Management –

a) Creation and deletion of files and directories

b) Provide access to files and allocation of storage space for files
c) Maintain backup of files
d) File security

4. Device Management –

a) To open, close and write device drivers.

b) Communicate, control and monitor the device drivers

5. Secondary storage Management –

a) Managing the free space available on the secondary storage.

b) Allocation of storage space when new files have to be written
c) Scheduling the requests for memory access

6. Protection and security –

a) Assigns the user authentication

b) Assigns file attributes such as read, write, Hide, encryption.
c) Facilitates backup of data

7. User interface or Command interpreter –

a) Provides interface between user and computer hardware. Either through set of
commands (CUI) or Graphically (GUI)

8. Booting the Computer –

a) Provides mechanism for cold booting and hot booting computer.

9. Perform the basic computer tasks –

a) OS manages peripheral devices like mouse, keyboard, monitor, printer etc.

 b) OS facilitates plug and play device and detect and configured without any user
interference.

1.2 Different types of operating system:

Operating systems can be classified into several types based on their functionality and design.
Common types include Batch operating system, Multi-programmed operating system, Time share
Operating system, Multiprocessor operating system, Distributed operating system, Real Time
operating system, Mobile OS (Android OS)

1. Batch operating system:

 Batch processing is a technique in which an OS collects the programs and data together in a
batch before processing.
 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.
 An OS does the following activities related to batch processing
 The OS defines a job which has predefined sequence of commands, programs and data as
single unit.
 Jobs are processed in order of submission i.e. First come first serve.
 When job completes its execution, its memory is released and the output for the job gets
copied into an output spool for later printing or processing.
 Batch monitor program in main memory is used to implement batch processing system.
Batch monitor is also called kernel (Kernel resides in one part of the computer main
memory). Batch monitor program controls the sequence of events.

Batch operating system

Advantages :

1. Move much of the work of the operator to the computer.

2. Increased performance since it was possible for job to start as soon as the as the previous job is
finished, without any manual intervention
Disadvantages :

1. Turnaround time can be large form user standpoint.

2. CPU is often idle, because the speed of the mechanical I/O devices is slower than the CPU.
3. Program debugging is difficult.
4. A job could corrupt the monitor program, thus affecting pending jobs.
5. Due to lack of protection scheme, one batch job can affect pending jobs.
Examples of Batch based Operating System: Payroll System, Bank Statements, report generation
systems. These systems are designed to handle large volumes of data and repetitive tasks efficiently.

2. Multi-programmed operating system:

When two or more programs reside in memory at the same time for sharing processor is referred
as 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
them. Multiprogramming assumes a single shared processor. Multiprogramming increases CPU
utilization by organizing jobs so that the CPU always has one to execute jobs in the memory.

An OS does the following activities related to multiprogramming.

1. The operating system keeps several jobs in memory at a time.

2. This set of jobs is a subset of the jobs kept in the job pool.
3. The operating system picks and begins to execute one of the jobs in the memory.
4. 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.
5. A function of the multi-programming OS is CPU scheduling, Memory management and I/O
management.

Advantages

1. High and efficient CPU utilization.

2. User feels that many programs are allotted CPU almost simultaneously.
Disadvantages

1. CPU scheduling is required.

2. To accommodate many jobs in memory, memory management is required.

2. Multiprocessor Operating system:

A multiprocessing operating system is capable of running many programs simultaneously, and most
modern network operating systems (NOSs) support multiprocessing. These operating
systems include Windows NT, Windows 2000 server, Solaris and Unix. Although Unix is one of the
most widely used multiprocessing systems.

Most computer systems are single processor systems i.e they only have one processor. However,
multiprocessor or parallel systems are increasing in importance nowadays. These systems have
multiple processors working in parallel that share the computer clock, memory, bus, peripheral
devices etc. An image demonstrating the multiprocessor architecture is
Types of Multiprocessors: There are mainly two types of multiprocessors i.e. symmetric and
asymmetric multiprocessors. They are as follows −

1. Symmetric Multiprocessors 2. Asymmetric Multiprocessors

1. Symmetric Processors:

 In symmetric multiprocessing treats all processors are equal rights, an I/O can be
processed on any CPU
 It is easier to implement in Operating system.
 Single OS manages all processor cores simultaneously
 Master-slave concept is not used.
 The processors communicate with each other through shared memory

2. Asymmetric Multiprocessors:

 Asymmetric processing has one master CPU and the remainder CPUs are slaves
 Its architecture is complex.
 Separate OS separate copy of same OS manage each core
 It uses concept of master slave concept.
 Shared memory is not used for communication

Advantages:

1. Throughput: Throughput increased because number of processor is increased

2. Cost: Multiprocessor system is cheaper than the multiple single processor.
3. Reliability: If one processor fails, it has no effect on whole system operation.
4. Response time: Response time is less because of increased number of processors.

Disadvantages:

1. Multiprocessor systems are more complex in both hardware and software.

2. Additional CPU cycles are required to manage the co-operation so per CPU efficiency goes
down.

Difference between multi-programmed and Multiprocessor OS:

Difference between Multi-programming and multi-processing:

Sr. Multi-processor OS Multiprogramming OS

No.
1. Multiprocessing refers to processing of Multiprogramming keeps several programs in
multiple processes at same time by main memory at the same time and execute them
multiple CPUs concurrently utilising single CPU

2. It permits parallel processing Context switching takes place.

3. Less time taken to process the jobs More time taken to process the jobs
4. More expensive system Less expensive system
3. Time shared Operating system:

A time-sharing operating system allows multiple users to access a single computer system
simultaneously, each getting a small slice of the CPU's processing time. This creates the illusion that
each user has exclusive access to the computer, even though the system is rapidly switching
between different users' tasks.

Multiprogramming:

Time-sharing builds upon multiprogramming, where multiple programs reside in memory and the
CPU switches between them to improve resource utilization.

CPU Scheduling:

The operating system uses scheduling algorithms to determine which user’s task gets the CPU for a
specific time slice.

Context Switching:

The process of saving the state of one task and loading the state of another is called context
switching, and it’s a fundamental part of time-sharing.

Time Slice/Quantum:

Each user or process is allocated a small, fixed time interval (time slice or quantum) during which
they can execute.

How it works:

The system allocates a small time slice to each user’s task. The CPU executes the task for that time
slice, and then the operating system switches to another user’s task. This rapid switching creates the
illusion that all users are working concurrently.

Advantages:

1. Efficient Resource Utilization: By sharing the CPU, time-sharing makes better use of the
computer's resources compared to single-user systems.
2. Interactive Response: Users experience a relatively quick response time, as the system
switches between tasks quickly.
3. Reduced CPU Idle Time: The CPU is kept busy most of the time, minimizing idle time.
4. User-Friendly: Time-sharing systems allow multiple users to interact with the system
simultaneously, making it more convenient for collaborative work.
Disadvantages:

1. Complexity: Time-sharing systems are more complex to design and implement than simpler
operating systems.
2. Resource Intensive: They require more resources, including memory and processing power,
to manage multiple users and tasks.
3. Security Concerns: Sharing a system among multiple users can raise security and integrity
concerns, especially if not properly managed.
4. Potential for Issues: Problems with one user's task can potentially affect other users on the
system.

4. Distributed Operating System:

 A Distributed Operating System refers to a model in which applications run on multiple

interconnected computers, offering enhanced communication
 A distributed operating system (DOS) manages a collection of independent computers that
work together as a single system. These computers, or nodes, are connected via a network
and share resources, creating the illusion of a unified computing environment. This allows
for increased scalability, fault tolerance, and resource sharing compared to traditional single-
system operating systems.
 Distributed system or distributed data processing is the system in which processors, data
and other aspects of a data processing system may be dispersed within on organization.

 A distributed system is a collection of autonomous or independent computer that are

connected through a computer network either by LAN or WAN capable of collaborating of a
task.
 A distributed system is a collection of independent computer that appears to its users as a
single coherent system. Each host executes components and operates a distribution
middleware.
 It uses clients and server technologies. It is called loosely coupled because is does not use
shared memory as it uses independent computer which has its own processor and memory.
 Middleware enables the components to coordinates their activities. Users perceive the
system as a single integrated computing facility.
  A distributed system can consists of any number of possible combinations such as
mainframe, personal computers, workstations, mini computers and so on. Distributed OS
provides resource sharing across the boundaries of a single computer system.
 E.g. of distributed operating system are Internet, ATM machine, banking, reservation
system, mobile computing and computer supported cooperative work.

Advantages:

1. Reliability:- It is more reliable than a single system. If one machine from system crashes, the rest
of the computers remain unaffected and the system can survive as a whole.
2. Incremental growth : In distributed computing the computer power can be added in small
increments i.e. new machine can be added incrementally as per requirements on processing power
grow.
3. Sharing resources: Shared data is required to many applications such as banking, reservation
system and computer supported cooperative work. As data or resources are shared in distributed
system, it is essential for various applications.
4. Flexibility: As the system is very flexible, it is very easy to install, implement and debug new
services.
5. Speed: A distributed computing system can have more computing power than a mainframe. Its
speed makes it different than other systems.
6. Performance: - It is yet another advantage of distributed computing system. The collection of
processors in the system can provide higher performance than a centralised computer.

Disadvantages:

1. Troubleshooting – Troubleshooting and diagnosing problems are the most disadvantages of

distributed OS.
2. Software: Less software support is the main disadvantage of DOS because of more software
components that comprise a system there is a chance of error occurring.
3. Networking: Networking cause several problems like transmission error, overloading, loss of
messages etc.
4. Security: - The easy distributed access in distributed computing system which increases the risk of
security. The sharing of data creates the problem of data security. More susceptible to external
attack.

5. Real Time operating System:

 A real-time operating system (RTOS) is an operating system (OS) intended to serve real-time
applications that process data as it comes in, typically without buffer delays. Processing time
requirements (including any OS delay) are measured in tenths of seconds or shorter
increments of time.
 A real-time system is a time-bound system which has well-defined, fixed time constraints.
Processing must be done within the defined constraints or the system will fail. RTOS is an
operating system intended to serve real time application that process data as it comes in,
mostly without buffer delay.
 Most RTOSs use a pre-emptive scheduling algorithm, priority based algorithms. The
processors is normally allocated to the highest priority processors.
  Applications using RTOS range from industrial automation and medical devices to aerospace
and automotive systems, all requiring predictable and timely responses.
 In a Real-Time Operating System (RTOS), the kernel is the core component that manages
tasks, interrupts, and system resources, ensuring that critical operations are executed within
strict timing constraints. It's responsible for scheduling tasks, handling interrupts, and
managing resources to guarantee predictable and timely responses, which is essential for
real-time applications.
 In a real-time operating system (RTOS), a Board Support Package (BSP) acts as a crucial
bridge between the OS and the specific hardware it runs on. It's a collection of hardware-
specific software components that enable the RTOS to function correctly on a particular
board.
 A custom hardware component within a Real-Time Operating System (RTOS) can
significantly enhance performance and determinism by offloading specific tasks or providing
hardware-accelerated functions.

Processing should be done within the defined constraints namely Hard and soft real time system

1. Hard Real Time:

In Hard RTOS, the deadline is handled very strictly which means that given task must start executing
on specified scheduled time, and must be completed within the assigned time duration.
Example: Medical critical care system, Aircraft systems, etc.

2. Soft Real Time:

Soft Real time RTOS, accepts some delays by the Operating system. In this type of RTOS, there is a
deadline assigned for a specific job, but a delay for a small amount of time is acceptable. So,
deadlines are handled softly by this type of RTOS.
Example: Online Transaction system and Livestock price quotation System etc

Advantages:

1. Useful for real time practical industrial applications

2. As user gets higher degree of control the flexibility is setting up the priority of process is greater.
3. Fast response, the system is immediately updated.

Disadvantages: 1. They are very complex and expensive, there by difficult to maintain 2. Needs good
degree of hardware support for responding to external interrupts as fast as possible 3. It is more
difficult to backup these systems when they are in use.

RTOS Examples include: VxWorks, QNX, eCos, and RTLinux. These are used in various applications
such as: automotive systems (engine control, ADAS), aerospace and defense (flight control, radar),
industrial automation (robotics, manufacturing), and medical devices (pacemakers, monitoring
systems).

Mobile OS:

A mobile operating system (OS) is the software that manages a mobile device's hardware and
software, enabling users to interact with their phones, tablets, or other portable devices. It provides
a user interface, manages resources like memory and storage, and allows applications to
run. Popular examples include Android and iOS.

6. Android OS:

Android is a mobile operating system developed by Google, primarily for touchscreen devices like
smartphones and tablets. It's based on a modified Linux kernel and offers a customizable user
interface with support for a wide range of applications. Android is the most popular mobile OS
globally, powering a vast number of devices from various manufacturers.

The Android operating system is structured in a layered software stack, typically comprising five
main layers:

Linux Kernel: This is the foundational layer, providing core system services like process
management, memory management, device drivers (for camera, display, Wi-Fi, etc.), power
management, and security. It acts as an abstraction layer between the device hardware and the
upper layers of the Android stack.

Hardware Abstraction Layer (HAL): The HAL provides a standard interface for hardware vendors to
implement drivers and functionalities without affecting the higher-level Android framework. It
contains modules for various hardware components like audio, Bluetooth, camera, and sensors.

Android Runtime (ART) & Native C/C++ Libraries: Android Runtime (ART): This is the runtime
environment that executes Android applications. It compiles application bytecode (DEX files) into
native machine code during installation, allowing for faster execution and improved performance
compared to the older Dalvik virtual machine.

Native C/C++ Libraries: This layer includes a set of core libraries written in C/C++ that provide
essential functionalities for the Android system and applications. Examples include libraries for
graphics (OpenGL ES, Skia), media playback (Media Framework), database management (SQLite),
and web browsing (WebKit).

Application Framework:

This layer provides the core building blocks and services that Android applications use. It includes
key components like:
Activity Manager: Manages the lifecycle of application activities.
Package Manager: Tracks installed applications and their information.
Window Manager: Manages the display and layout of application windows.
Content Providers: Enable data sharing between applications.
Resource Manager: Manages external application resources like strings, layouts, and images.
Applications: This is the topmost layer, containing both pre-installed system applications (like
Phone, Contacts, Browser) and user-installed third-party applications. All applications, whether
system or user-installed, leverage the functionalities and APIs provided by the Application
Framework.

Features:

Open Source and Customizable: Android is built on open-source principles, allowing manufacturers
to customize it for their specific devices and users to personalize their experience.
Linux Kernel: The core of Android is a modified Linux kernel, providing a robust and secure
foundation for the operating system.
Touchscreen Interface: Android's design centers around intuitive touchscreen interactions, enabling
users to navigate and control devices with finger gestures.
Application Ecosystem: Android boasts a vast library of applications available through the Google
Play Store, offering users a wide array of functionalities and experiences.
Multitasking and Graphics: Android supports multitasking, allowing users to run multiple
applications simultaneously, and offers capabilities for both 2D and 3D graphics.
Security Updates: Android devices receive security updates, including app updates, through Google
Play, ensuring a secure and protected environment.

1.3 Command Line based OS:

Command Line Interface:

In CLI (Command Line Interface) or Character user interface(CUI) , the user interacts with OS by
typing commands or instructions on a command line.

Various commands need to be typed for carrying out various jobs like creating, deleting, editing,
renaming and printing a file.

In CLI, each command represents an executable program which is run when the command is typed
with proper parameters.

MSDOS (developed by Microsoft Corporation) and Unix (developed by AT & T) are the operating
system which provides command line based OS

Advantages:

1. This interface faster as the commands are already known.

2. This interface needs less memory (RAM) [Link] CPU processing time is not utilised

Disadvantages:

1. It is not user-friendly as to remember a lot of commands.

2. Commands should be typed as per syntax

MS-DOS:

Microsoft Disk Operating System is a non-graphical command line OS created for IBM compatible
computers. MSDOS operating system provides CLI called command prompt. This is Single user, single
tasking os.

MS-DOS has predefined command internal and external commands.

Commands are executed by command interpreter ([Link]) by translating them into system
calls. Command interpreter reside outside of kernel so that kernel is not affected by user.

[Link] and [Link] of DOS includes internal commands like dir, cls, cd,md,rd, ren, del copy, move
and external command includes programs as chkdsk, format, fdisk etc.

UNIX :

UNIX shell is command line interface similar to old DOS prompt on the PC platform. Bourne
shell(sh), ksh,bash are the examples of the shell.

It uses a hierarchical file system that allows easy maintenance and efficient implementation.

CPU scheduling in Unix is simple priority algorithm.

The UNIX operating system (OS) consists of a kernel layer, a shell layer , utilities and
applications layer. These three layers create a portable, multiuser, multitasking operating system.
There are multiple versions of the OS, but every version has the exact same structure.

Unix consists of two separate parts kernel and the system programs. Kernel interact shell program
provides the command line interface. It accepts input commands and interprets them and executes
them.
Typically a user access a computer through an application program’s interface and the application
logic communicates with Unix through an application programming interface called POSIX (Portable
Operating System Interface for Unix.

2. Graphical User Interface (GUI)

GUI is an alternative and more user friendly method to interface with the operating system. GUI
provides a rectangular area of screen called Window in which file programs, directories and system
functions are represented as small images or symbols called as icons.

A GUI provides a window and menu based graphical interface that can be operated by using a
pointing device like a mouse.

Advantages:

1. GUI are ease of the use, operate and provides better accessibility
2. User can switch quickly between tasks on GUI interface.
3. GUI allows multiple programs and or instances to be displayed simultaneously.

Disadvantages:

1. It uses more computer memory.

2. GUI becomes more complex if user needs to communicate with the computer directly.
3. Slow speed because of long pointer operations.

Windows :

Windows 7 is an operating system that Microsoft has produced for use on personal computers. The
64-bit version of windows 7 is now commonly installed on large client systems.

Windows architecture follows a layered system approach of modules. The major layers are the HAL
(Hardware Abstraction Layer), Kernel and the executive. All of these layers run in kernel mode and a
group of subsystems and services run in user mode.

1. Hardware Abstraction Layer:- The major goal of windows 7 was to build the operating system
which would be potable across platforms. The HAL is responsible for hiding dissimilarities in
hardware chipset from upper levels of the operating system.

2. Kernel: Scheduling of threads, low level processor synchronisation, interrupt handling, switching
between user mode and kernel mode.

3. Executive: The executive is the upper portion of the operating system. It is written in C and is
architecture independent. It consists of components that work together to accomplish a certain task.
These components are I/O manager, process manager, virtual memory manager, security reference
monitor, cache manager, plug and play manager, power manager, registry and booting, advance
local procedure call facility.

Linux :
Linux is created by Linus Torvalds.

Linux is freely distributed OS. There are no licensing fees. Linux is used by millions of people around
the world. Programmers can even modify the source code and create their own unique versions of
the Linux OS.

Linux is available in various distributions or flavours include Red Hat, Ubuntu, CentOS, Debian, Open
suse etc.

Linux supports several hardware platforms including Intel, Power PC, Dec Alpha, Sun sparc and
Motorola.

Most Linux system provides either the desktop Environment (KDE) or GNOME inter interface both of
which are built on top of x-windows and resemble the windows interface.

GNOME ‘s user interface starts in the activities overview mode which allows you to launch new
applications, switch windows and more them between workspace. GNOME was originally
an acronym for GNU Network Object Model Environment

The KDE is a graphical Desktop environment for Linux providing the linux users with various x-
windows utilities. The KDE desktop contains three main tools to access the applications on the linux
system namely panel icons, desktop icons, and menus.

Mac OS:

MacOS operating system that Apple Inc. developed especially for its Macintosh computer
series. It is the replacement for the classic MacOS. The reliability, security features, ease of
use, and compatibility with other Apple goods and services are all well-known aspects of
macOS

Features of MacOS:

User Friendly Interface: The window and menu that makeup macOS user friendly interface which
make it simple to navigate and find the information you need.

Built in Apps: In macOS so many apps are pre-installed like Mail for email and Photos for picture
management. similarly, safari is used for online browsing is also pre-installed in it.

Integration with Other Apple Devices: macOS connects easily with other Apple devices, such as the
iPad, iPhone, and others. Not only you can reply to messages and take calls, but you may even begin
things on one device and complete them on another.

Privacy and Security: macOS is designed with security and protecting your data from malware and
viruses. By allowing you to choose which apps can access your data.

Updates: By apple, New features like enhancements and security patches are frequently added to
macOS through regular updates. These updates keep your Mac operating properly and are generally
simple to apply.

Accessibility: macOS includes features like VoiceOver for visually disabled users and Dictation for
individuals who have trouble in typing.
 Basic Structure of Mac OS

MacOS has a layered architecture, built upon a Unix core called Darwin, which provides a solid
foundation for its various components. This structure includes the Kernel and Device Drivers, Core
OS, Core Services, Media, and the Application layer. At the top, the user interface layer, known as
Aqua, provides the graphical environment users interact with.

1. Darwin (Unix Core): At the heart of MacOS is Darwin, a POSIX-compliant operating system based
on a hybrid kernel (XNU) that incorporates elements from FreeBSD. This layer handles fundamental
tasks like process management, memory management, networking, and file system operations. It
also provides the standard Unix command-line interface.

2. Core OS: This layer builds upon Darwin, providing essential services like file systems (including the
Unix permissions layer) and other core functionalities. It ensures a stable and reliable base for the
entire system.

3. Core Services: This layer offers a set of APIs and frameworks that developers can use to build
applications. These services handle tasks like networking, data management, and other common
functionalities.

4. Media Layer: This layer is responsible for handling various multimedia tasks, including graphics
rendering and audio/video playback.

5. Application Layer: This layer contains the application frameworks, which are sets of tools and
libraries that developers use to build applications. macOS provides two main APIs for native
application development: Cocoa and Carbon.

Cocoa: A modern, object-oriented framework for developing applications, known for its rich
features and ease of use.

Carbon: A framework that provides backward compatibility with older Mac applications,
allowing developers to update their older applications to work on newer versions of macOS.
6. User Interface (Aqua): The top layer is Aqua, the graphical user interface that users interact
with. It provides the visual elements, windows, icons, and other components that make up the
desktop environment.

7. Graphics Subsystem: This subsystem, which includes Quartz, OpenGL, and QuickTime, is
responsible for rendering graphics on the screen.

Quartz: Provides 2D graphics rendering capabilities, including support for PDF rendering.
OpenGL: Enables 3D graphics rendering for more complex visual effects and gaming experiences.
QuickTime: A framework for handling digital media, including video and audio playback.

8. Window Server: This process manages the display of windows and graphics on the screen,
ensuring smooth animations and user interactions.

9. Core Graphics (Quartz 2D): This is the graphics rendering engine that provides advanced 2D
drawing capabilities for applications.

10. Metal: A low-level graphics API that allows developers to directly utilize the GPU for high-
performance graphics processing.

Difference between CLI and GUI:

S.N. CLI GUI

1. It is a text based used to interact with It is a visual based interface which features
software and operating system by typing the use of graphic images, including
commands into interface and receive a windows, icons and menus.
response in the same way.

2. CLI is faster and difficult to use than GUI GUI is slower and easier to use than CLI

3. CLI consumes low memory GUI consumes large memory

4. In CLI commands have to be typed in the In GUI one can point and click on icons to
command line to execute them execute commands. A mouse is the most
common device to navigate through a GUI
although the keyboard is used sometimes.

5. Not much flexible GUI is more flexible

6. Less user friendly More user friendly

7. Eg. DOS, UNIX Eg. Windows, Linux etc.

1.4 Different Services of operating system:

1. Program Execution:

The OS manages the loading, execution, and termination of programs, ensuring they run without
interference and are allocated necessary resources.
2. Input/Output Operations:

The OS handles communication between the computer and peripheral devices, allowing users to
interact with the system through keyboards, mice, monitors, etc.

3. File Management:

The OS organizes and manages files and directories, providing mechanisms for creating, reading,
writing, and deleting files, as well as controlling access permissions.

4. Resource Allocation:

The OS allocates and manages system resources like CPU time, memory, and storage space to
different programs and users, ensuring efficient utilization and preventing conflicts.

5. Communication:

The OS enables communication between different processes, either on the same machine or over a
network, facilitating data exchange and collaboration.

6. Error Detection and Handling:

The OS detects and handles errors that may occur during program execution or system operation,
preventing crashes and ensuring system stability.

7. Security and Protection:

The OS implements security measures to protect system resources and user data from unauthorized
access and malicious activities.

8. User Interface:

The OS provides a user interface, such as a command-line interface or a graphical user interface, that
allows users to interact with the system and its resources.

9. Accounting:

The OS keeps track of resource usage by different users and processes, enabling system
administrators to monitor and manage resources effectively.

10. Time Management:

The OS manages system time and provides mechanisms for time-based operations, like scheduling
tasks and synchronizing system clocks.

Concept of System Calls:

Definition: A system call is the programmatic way in which a computer program requests a service
from the kernel of the operating system it is executed on.

This may include hardware-related services (for accessing hard disk drive), Creation and execution of
new processes, and communication with integral kernel services such as process scheduling.

System call provides interface between running program and operating system. These calls are
generally available as routines written in C/C++ or assembly language.

Operating system provides a variety of systems calls to control the process.

Almost all modern processors provide instructions that can be used as system calls.

A system call is an instruction that does not execute a specific function in hardware but instead
generates an interrupt that cause the operating system to gain control of the processor.

System call is the call for the operating system to perform some task on behalf of the user’s
program. The interface between user program and Operating system is defined by the set of system
calls that the operating system performs.

User Program

Kernel

Hardware Resources

• Application developers often do not have direct access to the system calls, but can access
them through an application programming interface(API). These functions included in the
API invoke the actual systems calls.

• Three most common APIs are Win32 for windows, Posix for Unix, Linux and Mac OS, Java API
for the Java Virtual Machine(JVM). API provides benefits like portability and ease of use.

Services Provided by System Calls:

• Process creation and management

• Main memory management
• File Access, Directory and File system management
• Device handling(I/O)
• Protection
• Networking, etc.

Types of System Calls:

There are 5 different categories of system calls –

• Process control: end, abort, create, terminate, allocate and free memory.

• File management: create, open, close, delete, read file etc.

• Device management: Request device, release device etc.

• Information maintenance: Get time or date, set time or date etc.

 • Communication: Establish a connection, send, receive message, terminate a
connection.

1. Process and job control: A Running program need to be able to halt its execution either
normally or abnormally (abort). If the program discovers an error in its input and wants to
terminate abnormally

E.g of process and job control system calls are End, Abort, load, execute, create process,
terminate process, ready process, dispatch process, suspend process, resume process, get
process attributes, set process attributes, wait for time, wait event, signal event, change
priority of process.

2. File management:- File management calls are create file, delete file, open file, close file,
read file, write file, get and set file attribute.

After creating a file user can perform various operations on the file. File read, write,
reposition are the operations performed on the file. Every file has file attributes.

3. Device management: Files can be though of as abstract or virtual devices. Thus, many of the
system calls for files are also needed for devices. System calls for device management are
request() devices, get and set device attributes, read, write etc. Process needs for resources
Process request for resources, request is granted if it is free otherwise request is rejected.
Once request is granted, control is transferred to the process.

4. Information maintenance: System calls for this category is set time and date, get time and
date, get system data get and set process, file and device. System calls may return the
amount of free or disk space and so on. Most of the OS provides system calls for set and get
the time and date. This type of the system call is used for transferring information from user
to OS and vice versa.

5. Inter process communication: Pipe, socket, message passing and shared memory are used
for inter process communication. Create and delete connection, send message and received
message, terminate connection at each remote devices are the system calls used in inter
process communication.

a) Shared memory: A process uses memory for communication. One process will create a
memory portion which other process can access. A shared segment can be attached
multiple times by the same process. Shared memory is the faster IPC because data does
not need to be copied between processes.

b) Message passing: Two processes communicate with each other by passing messages.
Message passing is direct or indirect communication. Indirect communication uses
mailbox for sending receiving message from each other process.

Communication related system calls are establish a connection, send and receive
message and terminate message
Operating System Components:

1. Process Management:

2. Main Memory Management

3. File Management

4. I/O Management

5. Secondary Storage Management

Operating is complex and is many smaller parts. Each part is well defined with inputs, outputs and
function. Following are the parts of Operating system

1, Process Management :

A process is a program in execution. For e.g. A word processing program when being run is
called process. Sending printout to printers is also called process.

• A process needs certain resources like CPU time, memory, I/O devices, and file to accomplish
its task. These resources are provided when process is created or allocated while it is
running.
• Program is passive entity as the contents of file is stored in on disk whereas a process is an
active entity with program counter it specifies the next instruction to execute.
• The execution of a process must be sequential. The CPU executes instructions one after
another until the process completes.
• A process is the unit of work in system. Such a system consists of collection of processes,
some of our operating system processes and rest are user processes. All these process are
concurrently executed.
The operating system is responsible for the following activities w.r.t. process management

1. Creating and deleting both user and system processes

2. Suspending and resuming process
3. Providing mechanism for process communication and process synchronisation
4. Providing mechanism for deadlock handling.

2. Main Memory management :

• The main memory is central to the operation of modern computer systems. Main memory
acts as interface between CPU and I/O devices and access data easily.

• CPU process data from the disk, those data first transferred to main memory by CPU
generated I/O calls. Instructions must be in memory for the CPU to execute them.

• When a program is executed, it must be mapped to absolute addresses and loaded in

memory. As the program executes, it accesses program instructions and data from memory
by generating these absolute addresses.

• When program is executed, these memory space is reused for the next program.

• To improve CPU utilisation and speed of computer, we must keep several program into
memory.
 • The operating system is responsible for the following activities w.r.t. main memory
management

1. keeping track of which parts of memory are currently being used and by whom.
2. Deciding which processes are to be loaded into memory when memory space becomes
free.
3. Allocation memory space as needed
4. de-allocating memory space as needed

3. File Management - File management deals with the management and organisation of various
files in the system. File is a collection of related information by some name. Commonly, file
represents program or data. Files and directories must be well organised and managed so to use
easily.

The operating system is responsible for the following activities w.r.t. File management.

1. Creating and deleting files

2. Creating and deleting directories.
3. Supporting primitives for manipulating files and directories
4. Mapping files on a secondary storage
5. Backing up files on storage media.

4. I/O device Management:

The purpose of operating system to hide the particular hardware devices from the user. Each I/O
device has device driver to operate. Only the device drivers knows the peculiarities of the specific
device to which it is assigned. The operating system is responsible for the following activities w.r.t.
I/O device management.

1. Keep tracks of all devices. Program responsible for this task is known as the I/O controller
2. Decides which process gets the device when and for how much time.
3. Allocates the device in the efficient way.
4. De-allocates devices

5. Secondary storage management:

Main memory is too small to accommodate all data and programs and its data are lost when power
is lost, so that the computer system must provide secondary storage to backup.
Secondary storage consists of tapes, disks and other media designed to hold data and program. This
data and program can be accessed in primary storage when required.
The operating system is responsible for the following activities w.r.t. secondary storage
management.

a) Managing the free space available on the secondary storage.

b) Allocation of storage space when new files have to be written
c) Scheduling the requests for memory access

6. Protection and security:

Operating systems employ security and protection measures to prevent a user from illegally using
resources in a computer system.
Security measures deals with threats to resources that come from outside a computer system, while
protection measures deals strictly restricted to manage the internal resources. Protection refers to
the mechanism for controlling the access of the resources while security maintains the integrity of
the system and corresponding data. The operating system is responsible for the following activities
w.r.t. Protection and
a) Assigns the user authentication
b) Assigns file attributes such as read, write, Hide, encryption.
c) Facilitates backup of data

7. Booting the Computer:

Programs required for booting the computer are stored in ROMBIOS and executed one by one when
you switch on computer system. Operating is loaded into memory by using loader program for ROM-
BIOS. Warm booting is the process of using the operating system to restart the computer.

8. Performs basic tasks and error detection:

The different peripheral devices such as the mouse, keyboard and printers are managed by
operating system. Now a days most operating systems are plus and play which means any device will
automatically be detected and configured without any user interface.
Errors can occur anytime and anywhere. An error may occur in CPU, in I/O devices or in the memory
hardware. Following are the major activities of an operating system with respect to error handling −
a) The OS constantly checks for possible errors.
b) The OS takes an appropriate action to ensure correct and consistent computing.

9. User interface: The role of operating system is to work as interface between the user and
hardware of the computer. This interface is provided by operating system through set of commands
or it is a graphical user interface (GUI)

Difference between Program and Process

S.N. Program Process

1. Program contains a set of instructions Process is an instance of an executing program.

designed to complete a specific task.

2. Program is a passive entity as it Process is a active entity as it is created during

resides in the secondary memory. execution and loaded into the main memory

3. Program is a static entity. Process is a dynamic entity.

4. Program does not have any resource Process has a high resource requirement, it
requirement, it only requires memory needs resources like CPU, memory address, I/O
space for storing the instructions. during its lifetime.

5. Program does not have any control Process has its own control block called Process
block. Control Block.

6. It is stored in secondary storage Process is stored in memory

7. Program is static entity as it is made Process is dynamic entity

up of programme statements
 8. Program occupy fixed space in storage Process changes its state during execution.
or main memory

Unit –II

Process Management
Introduction:

Process management is the fundamental task of any modern operating system. The OS must
allocates resources to processes, enable processes to share and exchange information, protect the
resources of each processes from other processes and enable synchronisation among processes.

Process Management includes creating, running, terminating and assigning different processes to
different device. Even process scheduling is a part of process management where the sequence and
priorities of the process are defined.

To meet these requirements, the OS must maintain a data structure for each process which
describes the state and resources ownership of that process.

2.1 Processes:

A process is defined as an entity which represents the basic unit of work to be implemented in the
system.

A process is defined as a program under execution which competes for the CPU time and other
resources like e/o devices, files, storage devices etc.

The execution of a process must progress in a sequential fashion. That is at any time at most one
instruction is executed on behalf of the process.

A process is an instance of executing program including the current values of the program counter,
registers and variables.

Process in Memory:
 Process in memory

Logically each process has its separate virtual CPU. In actual, the real CPU switches from one process
to another. A process is an activity and it has a program, input, output and a state.

Each process has following sections

1. Text Section: that contains the program code

2. Data section that contains global and static variables
3. Heap is used for dynamic memory allocation and is managed via calls to new, delete, malloc,
free etc.
4. Stack is used for local variables. A process stack which contains the temporary data such as
subroutine parameters, return addresses and temporary variables. Space on the stack is
reserved. For local variables when they are declared and freed up when the variables go out
of scope. Stack and text can be increased and decreased in size while executing process.
5. Program Counter: that contains the contents of processor’s registers.

Process State:

In a multiprogramming system many processes are executed by operating system. But at any instant
of time only one process executes on the CPU. Other processes wait for their turn.

The current activity of a process is known as its state. As a process executes, it changes its state.
The process state is an indicator of the nature of the current activity in a process. Following figure
shows process state diagram. A state diagram represents the different states in which a process can
be at different times, along with the transitions form one state to another that possible in the
operating system.

Process States and Process Transition

Each process may be in one of the following states:

New State (Create) – In this step, the process is about to be created but not yet created, it is the
program which is present in secondary memory that will be picked up by OS to create the process.

Ready state– New -> Ready to run. After the creation of a process, the process enters the ready
state i.e. the process is loaded into the main memory in a queue called ready queue. The process
here is ready to run and is waiting to get the CPU time for its execution. Processes that are ready for
execution by the CPU are maintained in a queue for ready processes.

Running state – The process is chosen by CPU for execution and the instructions within the process
are executed by any one of the available CPU cores.

Waiting state – Whenever the process requests access to I/O or needs input from the user, it enters
into waiting state. The process continues to wait in the main memory and does not require CPU.
Once the I/O operation is completed the process again goes to the ready state.

Terminated state– After completion of the process the process will be automatically terminated by
the CPU. Process is killed as well as PCB is deleted.

Dispatcher: Dispatcher is program which allocate the process to the CPU for execution after
selecting the process from ready queue by scheduler program.

Functions of dispatcher:

1. To load or allocate process to CPU after selecting the process by scheduler program
2. Provides context switching
3. Switching to user mode.
4. Jump to proper location of process i.e. moving to the correct location in the newly loaded
program.
Dispatch latency: It is the time taken by dispatcher program to load the process to CPU. Or
Dispatch latency is the amount of time needed by the CPU scheduler to stop one process and start
another.

Process Control:

For managing process and resources operating system must have information about the current
status of each process and resource. Four different types of tables maintained by operating system.

1. Memory tables: are used to keep track of both main and secondary memory.
2. I/I tables are used by the operating system to manage the I/O devices and channels of the
computer system.
3. File tables provide information about the existence of files, their location on secondary
memory, their current status of its attributes.
4. Process tables are used to manage processes. Process must include a program or set of
programs to be executed.

Process Control Block:

Each process is represented in the operating system by a Process Control Block(PCB) also called Task
Control Block(TCB).The operating system groups all information that needs about a particular
process into a data structure called a PCB or process descriptor.
• When process is created operating system creates a corresponding PCB and released
whenever the process terminates.
• A PCB stores descriptive information pertaining to a process such as its state, program
counter, memory management information, information about its scheduling, allocated
resources, accounting information etc. that is required to control and manage the particular
process.
Process Control block includes following:

1. Process number: Each process is identified by its process called Process Identification
Number (PID). Every process has a unique process ID. The process ID is provided by the
operating system. The process ID of two process could not be same because process ID is
always unique.

2. Priority: each process is assigned a certain level of priority. Priority is the preference of the
one process over other process for execution. Priority may be given by user/system manager
or it may be given internally by OS.

3. Process state: This is about the current state of the process. The state may be new, ready,
running and waiting, halted/blocked and so on.

4. Program counter: The counter indicates the address of the next instruction to be executed
for this process.

5. CPU registers: The registers vary in number and type, depending upon the computer
architecture. They include accumulators, index registers, stack pointers and general purpose
resisters, plus any condition code information.

6. CPU scheduling information: This information includes a process priority, pointers to

scheduling queues and any other scheduling parameters.

7. Memory management information: This information may include such information as the
value of the base and limit registers, the page tables, or the segment tables, depending upon
the memory system used by operating system.

8. Accounting information : This information includes the amount of CPU and real time used,
time limits, account numbers, job or process number and so on.

9. I/O status information: This information includes the list of I/O devices allocated to the
process, a list of open files and so on.

10. File management: includes information about all open files, access rights etc.

11. Pointer: Pointer points to another process control block. Pointer is used for maintaining the
scheduling list.
2.2 Process scheduling :
• In multiprogramming environment, multiple programs are running all the programs
concurrently or simultaneously, then we use the scheduling.
• Processes are the small programs those are executed by the user according to their request.
CPU executes all the process according to some rules or some schedule.
• Scheduling is that in which each process have some amount of time of CPU. Scheduling
provides time of CPU to each process.
• When two or more processes compete for the CPU at the same time then choice has been
made which process to allocate the CPU next.
• Determining the next process to be executed on the CPU is called process scheduling and
module of the operating system that makes this decision called the scheduler.
• The allocation strategy for a job/process to a processor is called process scheduling.

The process of scheduling is well explained with the help of diagram

Processing scheduling Objectives:

• Maximize the number of interactive users within acceptable response times.

• Achieve a balance between response and utilization.
• Avoid indefinite postponement and enforce priorities.
• It also should give reference to the processes holding the key resources.
Scheduling Queues:

Scheduling Queues

Three types of operating system queues are:

• Job queue – It helps you to store all the processes in the secondary memory of the system.
• Ready queue – This type of queue helps you to set every process residing in the main
memory, which is ready and waiting to execute.
• Device queues – It is the queue in a device where processes are waiting for I/O operation i.e.
in blocked condition.
• For a uni-processor system, there will be never be more than one running process. If there
are more than one processes, the rest will have to wait until the CPU is free and can be
rescheduled.
• The processes which are ready and waiting to execute are kept on a list called the ready
queue. The list is generally a linked list. A ready queue header will contain pointers to the
first and last PCB’s in the list. Each PCB has a pointer field which points to the next process
in the ready queue.
• There are also other queues in the system. When a process is allocated to the CPU, it
executes for a while and eventually quits and waits for the occurrence of a particular event
such as the completion of an I/O request.
• The process therefore may have to wait for the I/O operation. The list of processes waiting
for a particular I/O device is called device queue. Each device has its own device queue.
• A process enters the system from the outside world and is put in the ready queue. It waits
in the ready queue until it is selected for the CPU. After running on the CPU, it waits for an
operation by moving to an I/O queue.
• Eventually, it is served by the I/O device and returns to the ready queue. A process
continues this CPU burst and I/O burst cycle until it finishes and then it exits from the
system.
Schedulers:

Schedulers are special system software which handles process scheduling in various ways. The main
task is to select the jobs to be submitted into the system and to decide which process to run. It is
also called software routine or module.

Schedulers are of three types

1. Long Term Scheduler 2. Short term Scheduler 3. Medium Term scheduler.

1. Long Term Scheduler:

• The Long term scheduler is that which in which job from the pool and loads into main
memory for execution is called long term scheduler. It is also called as job scheduler.

• The long term scheduler determines which jobs are admitted to the system for processing
from Job Queue in secondary memory.

• In batch system there are more jobs to be submitted that can be executed immediately.
These jobs are spooled to mass storage device where they are kept for later execution(ready
queue)

• The long term scheduler selects jobs from the job pool and load into main memory for
execution. Therefore, it is also called job scheduler.

• Time sharing operating system have no long term scheduler. When the process changes its
state from new to ready, then there is use of long term scheduler.

• In long term scheduler frequency of execution is low.(in few minutes) Speed is less than
short terms scheduler. It deals with main memory for loading process. It controls the
degree of multiprogramming. (number of processes executed per unit time is called
multiprogramming)
2. Medium Term Scheduler:

The medium term scheduler is that it removes the process from main memory and again reloads
afterwards when required.

The medium term scheduler temporarily removes processes from main memory and places
them on secondary memory. This is commonly referred to as “swapping out” or “Swapping in”

It is a process swapping scheduler. Its execution frequency is medium. Medium scheduler is

called whenever it is required. It reduces the degree of multiprogramming. Time sharing
operating system use medium term scheduler.

3. Short Term Scheduler:

Short term scheduler is that in which it selects the jobs or processes which are ready to execute
from the ready queue and allocate the CPU to one of them.

It is also called CPU scheduler. In most cases short term scheduler is written in assembly
language because it is a critical part of the operating system.

It provides frequency of execution very high (in miliseconds). The speed is very fast and deals
with CPU. It provides lesser control over degree of multiprogramming.

On some systems, the long term scheduler may be absent or minimal. For example time sharing
systems such as Unix and Microsoft windows systems often have no long term scheduler by
simply put every new process in memory for the short term scheduler.
 Difference between short scheduler, Medium scheduler and Long term scheduler

Short-Term
Basis Scheduler Medium-term Scheduler Long-Term Scheduler

1. Alternate It is also called a CPU It is also called a process It is also called a

Name scheduler. swapping scheduler. job scheduler.

It provides lesser
It reduces the control It controls the
2. Degree in control over the
over the degree degree of
programming degree of
of multiprogramming. multiprogramming.
multiprogramming.

The speed of a
The speed of the Speed of medium
long-term term
short-term scheduler scheduler between the
3. Speed scheduler is more
is very fast. short-term and long-term
than medium-term
scheduler
scheduler.

4. Usage in
It is almost absent
time- sharing It is minimal in the It is a part of the time-
or minimal in a
system sharing time-sharing system. sharing system.
sharing system.
system

It can reintroduce the

It selects the from among the process It selects processes
processes from into memory that from the pool and
5. Purpose among the process executes and its loads them into
that is ready to execution can be memory for
execute. continued. execution.

6. Process Process state is ready Process state is not Process state is

state to running present new to ready.
 Short-Term
Basis Scheduler Medium-term Scheduler Long-Term Scheduler

Select that process,

Select a good
Select a new which is currently not
7. Selection process , mix of I/O
process for a CPU need to load fully on
of process bound and CPU
quite frequently. RAM, so it swap it
bound.
into swap partition.

Context Switch:

• Switching the CPU to another process requires saving the state of the old process and
loading the saved state for the new process. This task is known as context switch.

• CPU switching from one process to another process is called a context switch.

• This enables multiple processes to share a single CPU. The context switch is an essential
feature of multitasking OS.

• The context of a process is represented in PCB of the process, it includes the value of the
CPU registers, the process state, Process ID and memory information.

• Context switch times are highly dependent on hardware support. Its speed depends on a
memory speed, the no. of registers that must be copied and existence of special instructions.
Speed is normally in microseconds.

• When the process is switched, the following information is stored

1. Program counter 2. Scheduling information 3. Base and limit registers value 4. Currently used
registers 5. Changed state 6. I/O state 7. Accounting information

Context Switch between two processes

 2.3 Inter Process Communication :
• Process is a series of actions.
• Process executing concurrently in the operating system might be either independent process
or co-operating process.
• Independent process are those processes which do not affect other process which is
executing and does not affect itself by other process.
• Cooperating process are those processes which will affect other process. These share
information.
• OS provides cooperating processes to communicate with each other via an inter process
communication facility.
• An exchange of information among processes is called an inter process communication. The
processes can be running on the same computer or on different computers connected
through network.

The purpose of IPC is to transfer data, sharing data, event notification, resource sharing and
synchronisation and process control.

Two fundamental models are used in IPC

1. Shared memory model

2. Message passing model

1. Shared memory model :

• Two processes exchange data or information through main memory sharing region. They
can read and write data from and to this region. One process will reside in shared region and
other process will read that information.
• Processes can exchange information by reading and writing data to the shared region.
2. Message passing model :

In message passing model the data or information is exchanged in the form of messages.

Message passing provides a mechanism to allow processes to communicate and synchoronise their
actions without sharing the same address space (sharing region). It particularly useful in distributed
environment where the communication processes may reside on different computers connected by
a network.

E.g. is a chat program used in World Wide Web could be designed so that chat participants
communicate with one another by exchanging information.

An IPC provides two operations or primitives.

1. Send (message) 2. Receive (message)

• If process A and B want to communicate, they must send messages to and receive messages
from each other; communication link must exist either between them. This link is
implemented not only physically but also logically.
• Communication can be direct or indirect.
1. Direct message passing: With direct communication, each process that wants to
communicate must explicitly name the recipient or sender of the communication
i) Send(B, message) : Send a message to a process A
ii) Receive(A, message) : Receive a message from process B
2. Indirect message passing: With indirect communication, the message is sent to and
receive from mailboxes or ports. Mailbox where messages can be placed by processes and
from which messages can be removed. The send and receive primitives are defined as
follows :
i) Send(B, message) : Send a message to mailbox A
ii) receive(A, message) : Receive a message from mailbox A.
2.4 Threads :

• A thread is called light weight process and is a basic unit of CPU utilisation; it comprises a
thread ID, a program counter, a register set and stack.
• A thread is defined as unit of concurrency within a process and had access to the entire
code, data parts and other operating system resources such as open files and signals of the
process. Thus, thread of the same process can share their code and data with one another.
• If a process belongs one thread performing single task at a time is called single threading. If a
process belongs to more than one thread performing multiple tasks at a time is called
multithreading.
• For example : in ms-word have a thread for display graphics, another thread for reading
keystrokes , and third thread can be spell and grammar check, others are saving file,
indentation etc.

Benefit:

1. Threads improve performance of system

 2. Concurrent operations can be achieved using threads within a process.
3. Threads minimises context switching. (saving state of ole process and loading the state of
new process.)
4. Threads can share common data, code and file of the same process. They do not need to
use IPC.
5. Context switching are fast when working with threads.

Difference between process and Thread:

S.N. Process Thread

1. Program in execution(Heavy weight Part of a process or basic unit of CPU utilisation.

process) (Light Weight process)

2. Takes more time for creation and Takes less time for creation and dependent
independent

3. More time for context switch Less time for context switch

4. Consumes more resources Consumes less resources

5. Memory is not shared Memory is shared of the process

6. Process communication is complex. Easy and efficient communication

User and kernel threads:

Practically threads can be implemented at two different levels

1. User level Threads - User managed threads.

2. Kernel level Threads – Operating system managed threads acting on kernel

A library which provides the programmers with an Application Programming Interface(API)

for thread creation and management is referred to as a thread library.

The thread library maps the user threads to the kernel threads. A thread library can be
implemented either in user space or in the kernel space.

1. User Level Threads :

• Threads implemented at the user level are called user threads.

• In user level, thread creation, scheduling and management is done by the application and
kernel is not aware of existence of threads.

• User threads are supported above the kernel and implemented by a thread library at the
user level. The library provides support for thread creation, scheduling, and management
with no support from the kernel. All code and data structures for the library exist in user
space.

• User level thread are generally fast to create and manage as there is no intervention of
kernel. User thread libraries include POSIX Pthreads, Mach C-threads, and Solaris 2 UI
threads.
Advantages:

1. User level thread can run on any operating system

2. User Level threads are fast to create and manage
3. User thread library easy to portable.
4. Thread switching does not require kernel model privilege.
5. Low cost thread operations is possible.

Disadvantages:

1. Multithreaded applications cannot take advantage of multiprocessing

2. At most one user level thread can be in operation at one time, which limits the degree of
parallelism.
3. If a user thread is block in the kernel, the entire process (all threads of that process) are blocked.

2. Kernel level threads:

The threads implemented at kernel level are known as kernel threads. Kernel threads are directly
supported by the operating system.

The kernel performs thread creation, scheduling and management in the kernel space. Because
thread management is done by operating system.

Kernel thread are generally slower to create and manage than are user threads.

If a thread performs a blocking system call, the kernel can schedule another thread.

Most operating systems including Windows NT, windows 2000, Solaris 2, support kernel thread.
Advantages:

1. Kernel can simultaneously schedule multiple threads from the same process or multiple
processes.
2. If one thread in a process is blocked, the kernel can schedule another thread of the same
process.
3. Kernel routines themselves can multithreaded.

Disadvantages:

1. The kernel level threads are slow and inefficient.

2. Transfer of control from one thread to another within same process requires a mode switch
to the kernel.

Difference between User Level Thread and Kernel Level Thread:

S.N. User Level Thread Kernel Level Thread

1. User level threads are faster to create Kernel level threads are slower to create and
and manage manage.

2. Implemented by a thread library at the Operating system support directly to kernel

user level. threads.

3. User level thread can run on any Kernel level threads are specific to operating
operating system system

4. Multithread application cannot take Kernel routines themselves can be

 advantage of multiprocessing. multithreaded.

Multithreading Models:

• Multithreading allows the execution of the multiple parts of a program (threads) at the same
time. These parts are known as threads. And are lightweight processes available within the
process. Therefore, multithreading leads to maximum utilisation of the CPU by
multitasking.

• Operating system that support multithreading process can consists of many threads. These
threads run in parallel improving the application performance.

• Each thread share the address space of the process and the environment.

• Considering the advantages of user and kernel level threads, a hybrid threading model uses
both user threads and kernel threads.

• Solaris operating system supports the hybrid model.

Following are the three multithreading models:

1. One to one multi-threading model

2. Many to one multithreading model

3. Many to many multithreading model

1. One to one model:

• In this model relationship between user level thread and kernel level thread is one to one. It
means that there is mapping of a single user level thread to a single kernel level thread.

• Because of such type of relationship multiple threads executes in parallel leading to more
concurrency.

• However, since it is needed to create kernel thread for every new creation of user threads.
So application performance will be degraded.

• Windows NT, Windows 2000, and OS/2 implement the one to one model.
2. Many to one model :

• In this model relationship between user level thread and kernel thread is many to one. It
means that there is mapping of many user level threads to a single level threads.

• In this model management is done in user space. When one thread make a system call for
blocking, the entire process gets blocked.

• One thread can access the kernel at a time, so many other threads cannot execute in
parallel on multiple processors.

• Therefore, concurrent execution of threads cannot be achieved. This type of relationship

facilitates an effective context switching environment, easily implemented even on simple
kernels with no thread support.

Solaris Green Thread, GNU portable uses this model

3. Many to Many Model:

Many to Many association exist between user level thread and kernel thread in this model.

It means that more number of user level threads are allied to equal or smaller number of kernel level
threads.

The necessity of altering code in both kernel and user space leads to the level of complexity.

This model allows developer to create as many threads. Concurrency is not gained because the
kernel can schedule only one thread at a time.

Solaris -2, IRIX, Unix support this model.

Difference between one to one and many to many

Parameter One to One threading Model Many to Many threading model

Mapping Each user thread maps to one kernel Multiple user threads map to a pool of
thread i.e. the OS schedules kernel kernel threads i.e. The OS schedules
thread, and each user thread is kernel; threads and multiple user threads
bound to a specific kernel thread are mapped to a pool of kernel threads.

Overhead Creating a new kernel thread for Efficient use of resources i.e. Kernel
each user thread can be expensive in threads are reused, reducing the overhead
terms of system resources. of creating new threads.

Parallelism True parallelism i.e. Multiple kernel Limited Parallelism i.e. The number of
threads can run concurrently kernel threads in the pool limits the
allowing for true Parallelism degree of Parallelism

Example Windows NT, Windows 2000, and Solaris 2, IRIX, HP-UX and Tru64 Unix
OS/2 implement the one to one support many to many model.
model.

Execute process commands: (top, ps, kill, wait, sleep, exit, nice)

1. top command:

The top command in Linux provides a dynamic, real-time view of a running system, displaying a
summary of system statistics and a list of processes or threads currently managed by the Linux
kernel.

Syntax:

top [options]

Example:
 $top -p 1234

This command monitors the process with PID 1234.

2. ps command:

When a program runs on the system, it is referred to as a process. Linux is a multitasking operating
system, which means that more than one process can be active at once.

To know the status of process ps command is used. The ps command is used to display the
characteristics of a process.

Syntax : ps [option]

Example: By default the ps command shows only the processes that belong to the current user and
that are running on the current terminal.

$ps

PID TTY Time cmd

30 01 0:03 sh

56 01 0.00 ps

$_

Each line has shown the PID(Process ID number), the terminal with which the process is
associated, the cumulative processor time that has been removed since the process has been
started and the process name.

Ps command options:

S.N. Parameter Description

1. -a Display all processes except session headers and processes without terminal.

2. -c Display additional scheduler information about the process

3. -e Display all processes

4. -j Display job information

3. Wait command:

Wait is a built-in shell command which waits for a given process to complete and returns its exit
status. Wait command waits for the process identified by process ID and reports its termination.

If an ID is not given waits for all currently active child processes and the return status is zero.

Syntax : wait pid

Example: wait 2112

Waits for process 2112 to terminate and return exit status.

4. sleep command:
The sleep command is used to delay for a specified amount of time. The sleep command pauses for
an amount of time defined by NUMBER. SUFFIX may be “s” for seconds(by default) “m” for minutes,
“h” for hours or “d” for days.

Syntax: $sleep 10s (Delay for 10 seconds.)

$sleep 10m

5. Exit command:

The exit command terminates a script just as in a C program.

It can also return a value which is available to the script’s parent process. Issuing the exit command
at the shell prompt will cause the shell to exit.

Syntax:

$ exit

6. nice command:

The nice command in Linux is used to launch a command or program with a specified "niceness"
value, which influences its scheduling priority. A higher niceness value indicates a lower priority for
the process, meaning it is more "nice" to other processes by yielding CPU time. Conversely, a lower
(or negative) niceness value indicates a higher priority.

Syntax:

nice [OPTION]... COMMAND [ARG]...

Example:

Running a command with a lower priority (default niceness of 10):

nice my_script.sh

Running a command with a specific lower priority:

nice -n 15 long running process

Running a command with a higher priority (requires root privileges):

sudo nice -n -5 important_task

 UNIT –II

CPU Scheduling

3.1 Basic Concept of scheduling:

CPU scheduling is the process of selecting a process and allocating the processor to the selected
process for execution.

The scheduler is the kernel component responsible for deciding which program should be executed
on the CPU. A scheduler selects a job/task which is to be submitted next for execution.

• Figure shows a schematic for CPU scheduling. Several processes await allocation of the CPU.

CPU scheduling which allows one process to select the CPU while the execution of another process
is on hold(in waiting state) due to unavailability of any resource like I/O etc, thereby making full use
of CPU. The selection process is carried out by the short-term scheduler (or CPU scheduler).

The scheduler program only selects one of these processes for execution on the CPU. Dispatcher
program will load the program into main memory, allocate CPU for the process, switching OS to the
user mode and moving process to proper location.

Dispatcher: Dispatcher is program which allocate the process to the CPU for execution after
selecting the process from ready queue by scheduler program.

Functions of dispatcher:

1. To load or allocate process to CPU after selecting the process by scheduler program
2. Provides context switching
3. Switching to user mode.
4. Jump to proper location of process i.e. moving to the correct location in the newly loaded
program.
Dispatch latency: It is the time taken by dispatcher program to load the process to CPU. Or
Dispatch latency is the amount of time needed by the CPU scheduler to stop one process and start
another.

Scheduling objectives:

The main objectives of scheduling is to increase system performance in accordance with the chosen
set of criteria. Depending on the system, the user and designer might expect the scheduler to
following objectives for scheduling:

1. Fairness: All jobs should get fair chance to get the use of CPU.
2. Maximise resource utilisation: The scheduling techniques should keep the resources of the
system busy.
3. Maximise throughput: If the CPU is busy executing processes, then work is being done.
Throughput is defined as the total number of processes that a system can executes per unit
of time.
4. Policy enforcement: The scheduler has to make sure that system’s policy is enforced.
5. Avoid indefinite postponement: A process should not experience an unbounded wait time
before or while receiving service.
6. Response time: A scheduler should minimise the response time for interactive user.
7. Minimse overhead: Overhead often results in wasted resources. Less overhead can greatly
improve overall system performance.
8. Turnaround time: Turnaround time is the sum periods spent waiting to get into memory,
waiting in a ready queue and executing on the CPU and doing I/O .

CPU and I/O burst cycle:

• CPU scheduling is greatly affected by how a process behaves during its execution. Almost all
the processes continue to switch between CPU(for processing) and I/O devices (for
performing I/O) during their execution.

• Process execution is a cycle of the CPU execution state and I/O wait state.

• Processes alternate back and forth between these two states. Process execution begins with
a CPU burst. It is followed by an I/O burst which is followed by another CPU burst. Then
another I/O burst.

• Eventually, the last CPU burst will end with a system request to terminate execution, rather
than another I/O burst.

• To realise a system scheduling objectives, the scheduler should consider process behavoiur.

1. CPU Bound process: The process which spends more time in computations or with CPU
and very rarely with the I/O devices is called as CPU bound process.

2. I/O Bound process: The process which spends more time in I/O operation than
computation is I/O bound process.
1. Pre-emptive scheduling:

• A pre-emptive scheduling allows a higher priority process to replace a currently running

process even if its time slot is not completed or it has not requested for any I/O.

• If a higher priority process enters the system, the currently running process is stopped and
the CPU transfers the control to the higher priority process.

• The current running process may be interrupted and moved to the ready state by the
operating system. Windows 95 introduces preemptive scheduling and all version of windows
operating system have used pre-emptive scheduling.

• The Mac OS operating system for the Macintosh also uses preemptive scheduling.

• The pre-emptive scheduling algorithms is based on priority where a scheduler may preempt
a low priority running process anytime when a high priority process enters into a ready
state.

• The advantage of preemptive scheduling algorithms is they allow real multiprogramming

• The disadvantage of preemptive scheduling algorithms are they are complex and they lead
the system to race condition.

• Examples : Round robin, priority algorithms, SRTF (shortest remaining time first),
SRTN(shortest remaining time next)

2. Non pre-emptive scheduling:

• In non-preemptive scheduling once the CPU is assigned to a process, the processor do not
release until the completion of the process. It means that a running process has the control
of the CPU and other allocated resources until the normal termination of that process.
 • If a higher priority process enters the system, the running process cannot be forced to
release the control.

• Non-pre-emptive algorithms are designed so that once process enters the running state, it
cannot be pre-empted until its completion at allotted time.

• The advantage of the non-preemptive scheduling are they are simple and they cannot lead
the system to race condition.

• The disadvantage of non-preemptive scheduling algorithms is they do not allow real

multiprogramming.

• Example of non-preemptive scheduling algorithms are FCFC, SJF, Multilevel scheduling etc.

Difference between Preemptive and Non-preemptive scheduling:

S.N. Preemptive Scheduling Non-preemptive scheduling

1. If CPU is allocated to one process, CPU Once, the CPU has been allocated to a process,
can be preempted to other process the process keeps the CPU until completion of
having higher priority or or some execution or either by terminating.
other fulfilling criteria

2. Throughput is less Throughput is more

3. It is suitable for real time system It is not suitable for real time system

4. Algorithm design is complex Algorithm design is simple

5. Only the processes having higher Processes having any priority can get scheduled
priority are scheduled

6. It does not treat all processes as equal It treats all process equal

7. The system resources are used The system resources are not used efficiently
efficiently

8. Example: Round Robin, Priority Example: FCFS, SJF, Multi queue algorithm.
algorithm

Scheduling criteria:

Scheduling criteria:

The scheduler may consider some performance measures and optimisation criteria. Following are
the some criteria's considered while scheduling.

1. CPU utilisation : CPU utilisation defined as the percentage of the time of the CPU is busy in
executing process. For higher utilisation CPU must kept busy as possible. It may range from
0-100 In real time system it should range from 40-100.

2. Throughput: Throughput is defined as the total number of process that a system can
execute per unit time. Throughput may be 10 processes per second.
 3. Turnaround time: Turnaround time (TAT) is the time interval from the time of submission of
a process to the time of the completion of the process. It can also be considered as the sum
of the time periods spent waiting to get into memory or ready queue, execution on CPU and
executing input/output.

4. Waiting time: Waiting time is defined as the time spent by a process while waiting in the
ready queue.

5. Balance utlisation: Balanced utlisation keeps system resources busy. It is defined as a

balance mixture of CPU bound processes and I/O bound processes.

6. Response time: Response time is the total amount of time it takes to respond to a request
to service. That service can be anything from memory fetch to and from a disk, to a a
complex database query

Scheduling algorithms:

The algorithms used by the scheduler to carry out the selection of a process for execution is known
as scheduling algorithm.

CPU scheduler schedules different processes to be assigned to the CPU based on scheduling
algorithms. Scheduler algorithms are either non-preemptive or preemptive.

Types of CPU scheduling algorithms are First Come First Serve,(FCFS), Shortest Job First(SJF),
Shortest Remaining Time Next (SRTN), Round Robin(RR), Priority scheduling, Multilevel Queue
scheduling.

1) First Come First Serve :

• It is the simplest type of algorithm in which the process that requests to allocate the CPU
first. A real-life example of the FCFS method is buying a movie ticket on the ticket counter.

• In FCFS scheduling algorithm processes are scheduled in as they are received in ready queue.
The FCFS algorithm is easily implemented by using a queue.

• The FCFS scheduling algorithm is non-preemptive. i.e. once the CPU has been allocated to a
process that process keeps the CPU until it wants to release the CPU either by termination or
by requesting I/O.

• In time sharing system, it is not useful because process will hold the CPU, it keeps it till the
completion of execution.

• Performance of FCFS is often very poor because a process with a long burst will hold up
other processes. Moreover, it can affect overall throughput. Average waiting time for FCFS
algorithm is not minimal and it also varies substantially if the process CPU burst time vary
greatly.

Advantages:

1. It is the simplest form of a CPU scheduling algorithm.

2. FCFS is best suited for batch systems where the longer time periods for each process are
often acceptable.
3. First come first served
Disadvantages:

1. It is a Non-Pre-emptive CPU scheduling algorithm, so after the process has been allocated to the
CPU, it will never release the CPU until it finishes executing.
2. The Average Waiting Time is high.
3. Short processes that are at the back of the queue have to wait for the long process at the front to
finish.
4. Not an ideal technique for time-sharing systems.
5. Because of its simplicity, FCFS is not very efficient.

Example 1:

Consider the four jobs are scheduled for execution (all jobs arrived at the same time. Find the
average waiting time and average turnaround time.

Process CPU burst time/Execution time

P1 8

P2 4

P3 9

P4 5

Soln.

Gantt chart shows the execution flow of process

P1 P2 P3 P4

0 (8) 8 12 21
26

Formulas to remind:

1. Waiting time(WT) = TAT- BT

2. Turnaround Time (TAT)= CT – AT
3. TAT =WT+BT
4. In non-preemptive algorithm WT=RT (Response Time)
5. In preemptive algorithm RT=time CPU First Time Serve - AT

Process Arrival CPU Burst Completion Response Waiting Turnaround

Time (AT) Time(BT) time Time(RT) Time Time (TAT)
(WT)
(CT-AT)
(TAT-BT)

P1 0 8 8 0 0 8

P2 0 4 12 8 8 12
 P3 0 9 21 12 12 21

P4 0 5 26 21 21 26

Average waiting Time: Average turnaround time :

Example 2 : Consider the four jobs are scheduled for execution (all jobs arrived at different time.
Find the average waiting time and average turnaround time using FCFS algorithm.

Process Arrival Time CPU burst time/Execution time

P1 0 2

P2 1 2

P3 5 3

P4 6 4

2. Shortest Job First(SJF) :

SJF algorithm schedules the processes according to the length of the CPU burst time. In SJF algorithm
the process with the shortest processing time is assigned first to CPU.

Jobs or processes are executed in the ascending order of their CPU burst time. Every time the job/or
process with smallest CPU burst time is selected from the ready queue.

If the two processes having same CPU burst time then, they will be scheduled according to FCFS
algorithm. Performance of this algorithm is very good in SJF.

The SJF algorithm is optimal it gives minimal average waiting time for a given set of processes. By
moving short process before a long one causes to decrease the average waiting time.

SJF can be evaluated in two different manners:

1. Non-preemptive SJF: In this method, if the CPU is executing one process, it is not stopped in
between before completion.

2. Pre-emptive SJF: In this method, while CPU is executing one process, if a new process arrives
in ready queue with smaller burst time/execution time, then current process is pre-empted
(sent back to ready queue) and the new process is executed. It is also called Shortest
Remaining Time First (SRTF). It is necessary to check the processes which are arrived at every
one unit time to find out completion time, Average waiting time, Average turnaround Time.

Advantages:

1. Overall performance is significantly improve in terms of response time.

2. Waiting time is reduced to minimal.
Disadvantages:
 1. There is a risk of starvation of longer process.
2. It is very difficult to know the length of next CPU burst time.

Consider example:

1. Non-preemptive SJF:

Example 1: Consider following table find average waiting time and turnaround time using SJF (Non-
preemptive

Process Arrival Time CPU burst time/Execution time

P1 0 4
P2 1
1
P3 2
2
P4 1
3
Soln.:

Gantt Chart:

P1 P2 P4 P3

0 (4) 4 (1) 5 (1) 6 (2)

8

Process Arrival CPU Burst Completion Response Waiting Turnaround

Time (AT) Time(BT) time Time(RT) Time Time (TAT)
(WT)
(CT-AT)
(TAT-BT)

P1 0 4 4 0 0 4

P2 1 5 3 3 4
1
P3 2 8 2 2 4
2
P4 1 6 4 4 5
3
Average waiting Time: 2.25 Average turnaround time: 4.25
SJF with pre-preemptive (SRTN): (shortest remaining time first)

Consider following table. Find Response Time, Average Waiting time and Average Turnaround Time
using SRTN.

Process Arrival Time (AT) CPU burst time/Execution time (BT)

P1 0 7
P2 1 5
P3 3 2
P4 4 3

Gantt Chart:

P1 P2 P2 P3 P3 P3 P2 P2 P4 P4 P4 P1

0 1 2 3 4 5 6 7 8 9 10 11 17

At 0 unit time : P1 At 1 unit time : p1,p2 At 2 unit time : p1,p2

At 3 unit time : p1,p2,p3 At 4 unit time : p1,p2,p3,p4 RT = CPU first time meet – AT

2. Example :
Consider following table. Find Average Waiting Time and Average Turnaround Time using
SRTN
Process Arrival Time (AT) CPU burst time/Execution time (BT)

P1 2 1
P2 1 5
 P3 4 1
P4 0 6
P5 2 3

Advantages of SRTN:
1. Many processes execute in less amount of time so, throughput is increased.
2. Processes which have short burst time run fast
Disadvantages of SRTN:
1. Practically it is not possible to predict the burst time.
2. Processes which have long burst time will have to wait for long time for execution

3. Priority Scheduling:

• In priority scheduling, each process has a priority which is a integer value assigned to it.
Priority scheduling can be evaluated with non-preemption or with preemption.

• Smallest Integer is considered as highest priority and largest integer is considered as lowest
priority. Always Highest priority process gets the CPU.

• In this algorithm, low priority processes may never execute. This is starvation. Solution to
this starvation problem is aging. In aging as the time progresses, increase the priority of the
process so that lowest priority processes gets converted to highest priority gradually.

Example 1 : Consider the following example for priority scheduling. Find AVG. WT,AVG TAT with
non-preemption. (use Lesser the number higher the priority)

Process Burst Time (BT) Priority

P1 12 4
P2 10 5
P3 5 2
P4 4 1
P5 3 3

Soln.:

Gantt Chart:

P4 P3 P5 P1 P2
0 (4) 4 (5) 9 (3) 12 (12) 24 (10) 34
Example 2: Consider following table. Find Average waiting time and average turnaround time using
priority scheduling with non-preemption (use Lesser the number higher the priority)

Process Burst Time (BT) Priority

P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2
Exercise:

Advantages:

1. It is simple in use
2. Important processes are never made to wit because of the execution of the less important
processes.
3. Suitable for applications with varying time and resource requirements.

Disadvantages:

1. It suffers from the problem of starvation of lower priority process, since the continuous
arrival of higher priority will prevent lower priority processes indefinitely from acquiring the
CPU.
2. A priority scheduling can leave some low priority waiting processes indefinitely for CPU.

4. Round Robin (RR) Scheduling algorithm:

• The round robin(RR) scheduling algorithm is designed especially for time sharing systems.
RR is the pre-emptive process scheduling algorithm.

• Round Robin scheduling is pre-emptive version of first come first serve scheduling.
Processes are dispatched in a first in first out(FIFO) sequence but each process is allowed to
run for only a limited amount of time.

• It is similar to FCFS scheduling but pre-emption is added to switch between processes. A

small unit of time called a time quantum or time slice is defined.

• A time quantum is generally from 10 to 100 milliseconds. The ready queue is treated as a
circular queue. The CPU scheduler goes around the ready queue, allocating CPU to each
process for a time interval of up to 1 time quantum.
 • If a process does not complete before its quantum expires, the system preempts it and gives
the processor to the next waiting process. The system then places the preempted process at
the back of the ready queue.

Figure shows process P1 is dispatched to a processor, where it executes either until completion, in
which case it exits the system or until its time slice expires at which point is pre-empted and placed
at the tail of the ready queue. The scheduler then dispatches the process P2.

The average waiting time under this algorithm is often long.

Example 1: Consider the following table with CPU burst time given in milliseconds. (time
quantum=4msec.) Find avg. waiting & turnaround time using RR.

Process Burst Time (BT)

P1 24
P2 3
P3 3

Solution:

P1 P2 P3 P1

0 (4) 4 (3) 7 (3) 10 ( 20)

30

Avg. waiting time : 5.66 Avg. Turn Around Time : 15.66

Example 2:

Consider the following table with CPU burst time given in milliseconds. (time quantum=3msec.) Find
avg. waiting & turnaround time using RR.

Process Arrival Time (AT) Burst Time (BT)

P1 0 5
P2 1 3
P3 2 8
P4 3 6
Solution:

Gantt Chart:

P1 P2 P3 P4 P1 P3 P4 P3
0 3 (3) 6 (3) 9 (3) 12 (2) 14 (3) 17 (3) 20 (2) 22

Avg. waiting time : 8.5 Avg. turnaround time : 14

Advantages: 1. RR is effective in timesharing OS. 2. CPU time is divided among the competing
processes. 3. RR increases the fairness among the processes 4. RR overhead is low on processor .

Disadvantages: 1. In RR the processes may take long time to execute. This decreases system
throughput. 2. It requires hardware support 3. In RR care must be taken in choosing quantum
value. 4. Throughput in RR is low if time quantum is too small.

5. Multi Level priority Queue(MLQ) scheduling algorithm :

• Multilevel Queue is based on response time requirements. Some processes required a quick
response by the processor; some can wait.

• A multilevel queue scheduling algorithm partitions the ready queue into separate queues.
Each queue follows a separate scheduling algorithm.

• In multilevel queue scheduling algorithm, the processes are classified into different groups
such as system processes, Interactive processes (Applications), Batch processes, student
processes or user processes.

• The interactive processes are known as foreground processes and the batch processes are
known as background processes. These two types of processes require different response
time. So they may need different scheduling algorithm.

• In this algorithm highest priority is given to system processes and lowest priority is given to
student process or user processes.

• Here, each queue gets a certain portion of the CPU time, which it can then schedule among
the various processes.
Multilevel Feedback Queue MLFQ) scheduling algorithm:

• It is improved version of MLQ.

• In MLFQ processes are not permanently assigned to a queue on entry to the system.

• Instead, they are allowed to move between queues. If a process uses too much CPU time, it
will be moved to lower priority queue.

• Similarly, a process that waits too long in a low priority queue will be moved to a higher
priority queue. i.e. the process is promoted to higher priority. This process is called as
aging. Aging prevents starvation of process.
Advantages:

1. MLFQ speeds up the flow of task execution

2. It prevents starvation by moving a lower priority process to a higher priority queue if it has
been waiting for long time.
3. It improves the overall performance of the system
4. It is fair to I/O bound processes.

Disadvantages:

1. TAT for long processes may increase significantly

2. It is the most complex scheduling algorithm
3. Context switch over head is increased.

3.4 Dead Lock:

 In multiprogramming environment, processes may require physical or logical resources.
Physical resources could be different devices and logical resources could be files present the
computer system. A process requests resources. If they are not available at that time, a
process enters into wait state.

 It may happen that waiting process will never change the state again because resources
requested by the process are occupied by some other process. This is known as dead lock
and leads to blocking of process execution.(no progress)

 Deadlock affects the progress by causing indefinite delays in resources allocation.

Processing is blocked and is waiting for events those cannot happen.

 Such delays have serious consequences for the response time of process and performance of
the system.

 Therefore, an operating system shall make use of resource allocation policies that ensures
no deadlock in the system.

 When every process in the set of or collection of processes are waiting for some event that
will happen by the other processes in the set, this kind of condition is called deadlock.

 Deadlock is a situation when two or more processes get locked and cannot be processed
further because of interdependently.
 • In above diagram, Deadlock is situation where set of processes are blocked because each
process is holding a resource and waiting for another resource acquired by some other
process.

• Deadlock may include the same resource shared by the processes, or may be different
resources shared. In the normal case, a process utilises the resources in the sequence of
Request, Use and Release.

• Request: The process first requests the resource. If the request cannot be granted
immediately satisfied, it has to wait until the requested resource is available.

• Use: The process can operate on the resource.(e.g. If the resource is printer, the process can
print on printer resource)

• Release: The process releases the resource.

• The request and release of resources are system calls provided by operating system. E.g.
system calls are request() and release() device, open() and close() files, allocate() and free()
memory.

• Request and Release system call can be accomplished through wait() and signal() operations
on semaphores. Semaphores are special variables that allow controlling the access to the
common resources in multi-programming environment.

• Semaphore is an integer variable that solves the critical section problem(deadlock). After
initialization, it can only be accessed by two atomic operations named wait() and signal().
There are two types of semaphores a) Binary semaphore b) Counting semaphore.

Deadlock System Models:

Overview:
A deadlock occurs when a set of processes is stalled because each process is holding a resource and
waiting for another process to acquire another resource. In the diagram below, for example, Process
1 is holding Resource 1 while Process 2 acquires Resource 2, and Process 2 is waiting for Resource 1.
System Model:

• For the purposes of deadlock discussion, a system can be modeled as a collection of limited
resources that can be divided into different categories and allocated to a variety of
processes, each with different requirements.

• Memory, printers, CPUs, open files, tape drives, CD-ROMs, and other resources are
examples of resource categories.

• By definition, all resources within a category are equivalent, and any of the resources within
that category can equally satisfy a request from that category. If this is not the case (i.e. if
there is some difference between the resources within a category), then that category must
be subdivided further. For example, the term “printers” may need to be subdivided into
“laser printers” and “color inkjet printers.”

• Some categories may only have one resource.

• The kernel keeps track of which resources are free and which are allocated, to which process
they are allocated, and a queue of processes waiting for this resource to become available
for all kernel-managed resources. Mutexes or wait() and signal() calls can be used to control
application-managed resources (i.e. binary or counting semaphores. )

• When every process in a set is waiting for a resource that is currently assigned to another
process in the set, the set is said to be deadlocked.

Operations:
In normal operation, a process must request a resource before using it and release it when finished,
as shown below.

• Request -
If the request cannot be granted immediately, the process must wait until the resource(s)
required to become available. The system, for example, uses the functions open(), malloc(),
new(), and request ().
 • Use -
The process makes use of the resource, such as printing to a printer or reading from a file.

• Release -
The process relinquishes the resource, allowing it to be used by other processes.

Necessary Conditions leading to deadlock:

Following four conditions that must hold for there to be deadlock. i.e. There are 4 conditions
necessary for the occurrence of a deadlock.
1. Mutual Exclusion: At least one resource is held in a non-sharable mode that is only one
process at a time can use the resource. If another process requests that resource, the
requesting process must be delayed until the resource has been released.

2. Hold and Wait: There must be at least one resource that is holding at least one resource
waiting for getting other resources that are currently held by other processes.

3. No preemption: Resources granted to requesting process cannot be taken away by

compelling it. These resources should be released by the process itself that is holding it.

4. Circular wait: There should be a collection or a set of processes like (P0,P1.P2…Pn). In this
set of process P0 is waiting for resource that is being utlised by P1. Also P1 is waiting for the
resource that is being used by P2 and so on. Thus, there must be a circular chain of two or
more processes, each of which is waiting for a resource held by the next member of the
chain.

Deadlock Handling:

We know that deadlock is situation in resource allocation system in which two or more
processes are in simultaneous wait state, each one is waiting for one of the others to release a
resource before it can proceed.

A deadlock in operating system can be handles in following four different ways:

1. Adopt methods for avoiding the deadlock.

2. Prevent the deadlock from occurring (use protocol)
3. Ignore the deadlock
4. Allow the deadlock to occur, detect it and recover from it.
5. To ensure that deadlocks never occur, the system can use either deadlock prevention or
deadlock avoidance.

If any of these two techniques (deadlock prevention or deadlock avoidance) is not used, a deadlock
may occur. In this case, an algorithm can be provided for detecting the deadlock and then using the
algorithm to recover the system from the deadlock.

If in a system, deadlock occurs less frequently (say in two years) then it is better to ignore deadlocks
instead of adopting expensive techniques for deadlock prevention, deadlock avoidance or deadlock
detection and recovery.

Deadlock prevention:

Deadlock occurs when all of the four conditions are satisfied at any point of time. Deadlock
prevention provides a set of methods for ensuring that at least one of the necessary conditions
cannot hold.
Following are the methods of preventing the deadlock

1. Eliminating Mutual Exclusion condition 2. Eliminating Hold and wait condition 3. Eliminating
No pre-emption condition 4. Eliminating Circular wait condition.

1. Eliminating Mutual Exclusion condition :

The mutual exclusion condition must hold for non-sharable type of resources. E.g. several
processes cannot simultaneously share a printer.

Sharable resources do not require mutually exclusive access. Read only files are good example
of a sharable resource. If several processes attempt to open read only file at the same time,
they can be granted simultaneous access to the file.

Process never needs to wait for sharable resources. It is not possible to prevent deadlock by
denying the mutual exclusion condition.

2. Eliminating Hold and wait condition:

Hold and wait condition can be eliminated by not allowing any process to request for a
resource until it releases the resources held by it which is impractical as process may require the
resources simultaneously.

3. Eliminating No preemption :

The elimination of no preemption means a process can release the resource held by it. Only
those resources are preempted whose current state is saved and can be reused. E.g resources
like disk drive, printer cannot be preempted.

4. Eliminating Circular wait condition :

The circular wait condition can be eliminated by assigning a priority number to each available
resource and a process can request resources only in increasing order.

Whenever, a process requests for a resource, the priority number of the required resource is
compared with the priority numbers of the resources already held by it.

Deadlock Avoidance:

A deadlock can be prevented by eliminating any one of the four necessary conditions of the
deadlock which results in the inefficient use of resources. Deadlock avoidance approaches
ensure that deadlocks cannot arise/occur in the system, but not allowing the conditions for
deadlock to hold simultaneously.

Deadlock avoidance requires that the operating system can be given information in advance
regarding the resources requirement for processes and will request and use. This information
is used by the operating system to schedule the allocation of resources so that no process will
wait for resource.

Safe state:

A state is safe if the system can allocate all resources requested by all processes without
entering a deadlock state.

A state is safe if there exists a safe sequence of processes(p0,p1,p2….pn) such that all of the
resources get the processes.
If a safe sequence does not exist, the system is in an unsafe state which will lead to deadlock.

Deadlock avoidance algorithm Bankers’s Algorithm (developed by Dijkshra) is used to avoid

deadlock.

Banker’s algorithm in the operating system is such that it can know in advance before a resource
is allocated to a process, whether it can lead to deadlock (unsafe state) or to avoid it (safe
state)

Several data structures must be maintained in advance to implement the banker’s algorithm,
where n is the number of processes in the system and m is the number of resource types. The
system should know in advance the total number of processes, resources required for each
process, current available resources, maximum need of resources, Allocated resources to
processes.

From this information, algorithm decide allocation strategy.

1. Available : A vector of length (Available[m]) m indicates the number of available resources of

each type
2. Max. : The matrix n x m defines the maximum demand of each process.
3. Allocation: An n x m matrix defines the number of resources of each type currently allocated
to each process.
4. Need: An n x m matrix indicates the remaining resource need of each process. Need[i][j] =
Max[i][j] - Allocation[i][j]

Safety algorithm:

This algorithm is used to find out whether a system is in safe sate or not. Following are the steps
to be in safe state.

1. Let work and finish the vector of length m and n respectively.

Initialise work=Available and Finish[i]=false for i=0,1,…. N-1.
2. Find an index i such that both
i) Finish[i]==false
Ii) Need I <=work
If no such I exits, go to step4
3. Work=Work +Allocation;
Finish[i]=true
Go to step 2
4. If Finish [i]==true for all I, then system is in safe state.

Example:

Consider the following allocation chart. Check whether the system is safe or unsafe. Write Safe
sequence.

Process Allocation Max. Available

R1 R2 R1 R2 R1 R2

P1 1 2 4 2 1 1
 P2 0 1 1 2

P3 1 0 1 3

P4 2 0 3 2

Solution:

Need = Max. – Allocation

Process Allocation

R1 R2

P1 3 0

P2 1 1

P3 0 3

P4 1 2

System is in safe state with safe sequence P2,P4,P1,P3. System will complete its operation in
this sequence.

UNIT-IV

Memory Management
4.1 Basic Memory Management:

Introduction:

 There are many types of memories in computer system. Registers memory, cache memory,
main memory (RAM), and secondary memory (disk). Secondary memory has lowest access
speed. Registers have highest access speed. Hierarchy maintained in computer system.
 The main memory is central to the operation of modern computer system. Main memory is
a large array of bytes. Main memory is act as an interface between CPU and I/O devices and
access data easily.

 When a program is executed, it must be mapped to absolute addresses and loaded in

memory. As the program executes, it accesses program instructions and data from memory
by generating these absolute addresses.

 When a program is executed, these memory space is reuse for the next program.

 To improve the CPU utlisation and speed of computers, we must keep several programs into
memory(degree of multiprogramming). Memory Management schemes available to handle
different situations.

 Memory management is the technique which is responsible for allocating memory to

processes and for protecting the memory allocated to each process from undesired access
by other process (keeping track of memory usage).

 Memory management is very important because it affects the execution time of process.
Therefore, an operating system must perform the memory management in such a manner
that the essential data is always present in main memory.

Processing of user program:

Memory management is the functionality of an operating system which handles or manages

primary memory and moves processes back and forth between main memory and disk during
execution.

Secondary storage device stores program in binary executable format. Before executing the
program, it is loaded first into main memory.

Most of operating system allow user process to store in any section of main memory. Source
program uses symbolic addresses.

Figure shows processing of user program.

Binding of instructions and data to main memory

Addresses in following ways:

1. Compile Time

2. Load Time

3. Execution Time
1. Compile time: Source program is translated at compile time to produce relocatable object
module. At compile time, the translator generates code to allocate storage for the variable.
This storage address is used for code reference.

2. Load Time: Compiler generates relocatable code if memory location is not known at compile
time.

3. Execution time: Memory address of the program is changed at execution time, then
execution time binding is used. Binding is delayed until the run time of the program.
Normally, all operating system use execution time binding. Special hardware is used for
execution time binding.

Main memory can be contiguous or non-contiguous. Contiguous memory allocates

processes in order as they arrive. In non-contiguous memory, the processes are stored in
random way.

Contiguous memory can be partitioned in two ways to allocate processes : 1. Fixed (Static )
partitioning 2. Dynamic(variable) partitioning
 Non-contiguous partitioning used paging, segmentation to allocate processes

Functions of memory Management:

1. Process Isolation: Process isolation means controlling of one process interacts with the data and
memory of other process.

2. Tracking of memory location: Memory management keeps track of each and every memory
location regardless either it is allocated to some process or free.

3. Automatic allocation and management: Memory (processes) should be allocated dynamically

based on the priorities of the process.

4. Protection and access control: should apply to the important applications only

Memory Partitioning:

Memory partitioning is the system by which the memory of a computer system is divided into two
sections resident monitor(OS) and user area. These memory divisions are known as partitions. . User
area is used to allocate processes in different size of partitions.

Resident monitor place in low memory and user program is executing in high memory.

We need to protect the monitor code and data from changes by the user program. This protection
must be provided by the hardware and can be implemented in several ways.
 32K

The general approach is every address (instructions and data) generated by the user program is
compared with a fence address.

If the generated address is greater than or equal to the fence, then it is a legitimate reference to
user memory and is sent to the memory unit as usual.

If the generated address is less than the fence address, the address is illegal reference to monitor.
The reference is intercepted and trap to operating system is generated.

There are different ways in which memory can be partitioned: fixed and dynamic partitioning
(variable)

1. Static(fixed sized) memory partitioning:

Job scheduling in fixed sized memory partitions:

Suppose that we had FCFS job scheduler and regions of 2k,6k and 12K. We would first assign process
1(5K) to the 6k regions and process2(2k) to the 2k regions. Since our next process3 requires 3k, we
need the 6k region.

Since 6k region is used by process1, we must wait until process terminates, then process 4(12k) is
then allocated to 12k regions and so on.

Advantages:
1. Implementation of fixed partitioning is simple
2. In fixed partitioning the overhead of processing is also low.
3. Fixed partitioning makes efficient utlisation of processor and I/O devices
4. No complicated algorithms are required

Disadvantages:

1. The main drawback of fixed partition is memory wastage. (due to internal fragmentation)
2. Poor utilisation of CPU.
3. Requires contiguous loading of a program.
4. Memory is not fully utilised.

Internal fragmentation:

If a partition is being used by a process requiring some memory smaller than the partition
size, then is called an internal fragmentation.

External fragmentation:

The unused spaces formed between non-contiguous memory fragments are too small to
serve a new process, is called External fragmentation.

2. Dynamic(variable) memory partitioning:

 In variable memory partitioning the partitions can vary in number and size. In variable
memory the amount of memory allocated is exactly the amount of memory of process
requires.

 The operating system keeps a table indicating which parts of memory are available and
which are occupied. Initially, all memory is available for user programs and is considered as
one large block of available memory called as hole.

 When a job or process arrives and needs memory, we search for a hole large enough for this
process. If we find one, we allocate only as much s as needed, keeping the rest available to
satisfy future requests.

Advantages:

1. Partitions are made as per the process length

2. Memory wastage is very less
3. Maximum part of memory is utilised.
Disadvantages:

1. The main drawback is entered fragmentation i.e. some small partitions remains unutilised.
To overcome this problem of external fragmentation is compaction.
2. This is all free memory space compacted. To form a new block.
For example, assume 256K memory is available and resident monitor of 40K. This situation
leaves 216 for user programs.

 Given the job queue in table and FCFS scheduling, we can immediately allocate memory to
job1, job2,job3 creating the memory map of fig. a. Unallocated segment is called as hole.

 We have 26k of external fragmentation. Job2 will terminate at time 5 unit, releasing its
memory allocation shown fig b
  We then return to our job queue and schedule the next job, job 4 to produce the memory
map of fig. c. Job1 will terminate at time 10 unit to produce fig. d

 Job5 is then scheduled produced fig. e

Another example is

Difference between fixed (static) partitioning and Dynamic (Variable) Partitioning

S.N Fixed Partitioning (Static Partitioning) Dynamic Partitioning (Variable Partitioning

1. In this partitioning, memory is divided In this partitioning, region or partition size is not
into several partitions of fixed size fixed and can vary dynamically.
that never changes.

2. Process size can not grow at run time Process can grow or shrink at run time

3. Degree of multiprogramming is fixed Degree of multiprogramming is dynamic.

(i.e. no. of partitions)

4. Memory utilisation is poor in this Memory utilisation is good in this partitioning.

partitioning.

5. Memory utilisation is difficult in this Memory utilisation is easy in this partitioning.

partitioning.

6. Fixed partitioning is suffered from Dynamic partitioning is suffered from external

internal fragmentation fragmentation

Storage allocation strategy:

The set of holes(free space) is searched to determine which hole(free space) is best to allocate. The
most common strategies used to select a free hole from the set of available holes are First fit, Best fit
and Worst fit.

1. First Fit: Allocate the first hole(or free block) that is big enough for the new process.
Searching can start either at the beginning of the set of holes or where the previous first fit
 search ended. We can stop searching as soon as we find a large enough free hole. First fit is
generally faster.

2. Best fit: Allocate the smallest hole that is big enough. We search the entire list, unless the
list is kept ordered by size. This strategy produce the smallest left over hole.

3. Worst fit: Allocate the largest hole. Again we must search the entire list, unless it is sorted
by size.
Free Space Management Technique:

 Files are created and deleted frequently during the operation of computer system. Since
there is only a limited amount of disk space, it is necessary to reuse the space from deleted
files for new files.

 To keep track of free disk space, the file system maintains a free space list. The free space
list records all disk blocks which are free.

 To create a file, we search the free space list for the required amount of space and allocate
it to the new fie. This space is removed from the free space list. When a files is deleted, its
disk space is added to the free space list.

 The process of looking after and managing the free block of the disk is called free space
management. The methods are used in free management techniques are Bit Vector or bit
map, Linked List, Grouping and Counting.

1. Bit Vector or bit map :

Bit map is a series or collection of bits where each bit corresponds to disk block.

Each block in bit map is represented by one bit. If the block is free, the block is set to ‘1’, and
if the block is allocated block is set to ‘0’
For example consider a disk where blocks 2,3,4,5,8,9,10,11 are free, the free space bit map would
be 00111100111100

0 = Allocated block

1= Free block

The main benefit of bitmap is that it is relatively simple and efficient to find the first free blocks or n
consecutives free blocks on the disk.

Unfortunately, bit vectors are inefficient unless the entire vector is kept in memory for most
accesses. Keeping it main memory is possible for smaller disks as on microcomputers, but not large
ones.

Advantages: 1. It is simple and efficient method to find the first free blocks or n consecutive free
blocks on the disk. 2. A bit map requires lesser space as it uses 1 bit per block.

Disadvantages: 1. Extra space required to store bit map. 2. It may require a special hardware
support to do bit operation i.e find out which bit is 1 and which bit is 0.

2. Linked List:

Linked list is another technique for free space management in which, the free disk blocks are linked
together i.e. a free block contains a pointer to the next free block.

In linked list technique, link all the free disk blocks together, keeping a pointer to the first free block.
This block contains a pointer to the next free block and so on.

In our example we would keep a pointer of the block 2 in first free block, Block 2 would contain a
pointer of Block 3 and so on.

Advantages: 1. If a file to be allocate free block, the OS can simply allocate the first block in the free
space list and move the head pointer to the next free block in the list. 2. No disk fragmentation as
every block is utilised.

Disadvantages: 1. It is not very efficient scheme as to traverse the list; we must read each block
requiring substantial time. 2. Pointers use here will also consume disk space. Additional memory is
therefore required.
 4.2 Swapping :

Swapping in an operating system is a memory management technique where processes are

temporarily moved from the main memory (RAM) to secondary storage (like a hard drive) to
free up RAM for other processes, and then moved back into RAM for execution when
needed. This process, known as swap-out and swap-in, is performed by the OS to increase
the degree of multiprogramming, efficiently use available memory, and allow the system to
run larger or more processes than physical RAM would normally allow.

Purpose and Benefits

1. Efficient Memory Utilization:
Swapping ensures that the limited physical RAM is used for the most active processes, improving
overall performance.
2. Increased Multiprogramming:
It allows the operating system to handle more processes concurrently, even when the total memory
required by these processes exceeds the available RAM.
3. Running Larger Applications:
Swapping enables the execution of larger programs or applications that would otherwise not fit into
the system's physical memory.

Compaction:
Compaction refers to combining of all the empty spaces together and processes. Compaction helps
to solve the problem of fragmentation, but it requires a lot of CPU time. It moves all the occupied
areas of storage to one end and leaves one large free space for incoming jobs, instead of numerous
small ones.

Limitations of Compaction
1. CPU Overhead:
Compaction requires a substantial amount of CPU time to move memory blocks and update
relocation information, which can slow down overall system performance.
2. Dynamic Relocation:
Compaction can only be performed if the system uses dynamic relocation, where memory addresses
can be changed during execution. Static relocation, where addresses are fixed at load time, prevents
compaction.

Fragmentation:

Fragmentation in an operating system is the inefficient use of memory or disk space, where allocated
blocks of memory or storage are broken into small, non-contiguous pieces, leading to unused
capacity that cannot be effectively utilized. There are two main types: external
fragmentation, where small, scattered blocks of free memory are too small to be allocated to new
processes; and internal fragmentation, where a larger, fixed-size block of memory is allocated to a
process that requires less space, leaving unused space within the allocated block.

Types of Fragmentation
1. External Fragmentation:
Occurs when free memory is split into small, non-contiguous fragments. Although the total free
space might be sufficient for a new process, it's not available in a single, large enough block, so the
memory cannot be allocated.
Example: A large process needs 10MB of contiguous space, but only smaller, non-connected blocks
of free memory are available.
2. Internal Fragmentation:
Occurs when an operating system allocates a fixed-size block of memory to a process that needs less
than the allocated block's total size. The extra, unused space within the allocated block is wasted.
Example: A process requires 2MB of memory but is allocated a fixed 3MB block, leaving 1MB of
internal, wasted space.
Causes of Fragmentation
1. Dynamic Memory Allocation: The continuous allocation and deallocation of memory for various
processes.
2. Fixed-Size Memory Blocks: The use of fixed-size blocks for processes, which can lead to internal
fragmentation when a process doesn't use the entire block.
3. Non-Contiguous Allocation: Memory allocation schemes that break processes into non-
contiguous chunks, leading to external fragmentation.
 Partitioning algorithms: Partitioning algorithms in operating systems manage how memory or disk
space is divided and allocated to processes or files, improving resource utilization and
efficiency. Common methods include fixed partitioning, which uses pre-defined memory divisions,
and dynamic partitioning, which creates partitions as needed. Algorithms within dynamic
partitioning, such as First Fit, Best Fit, and Worst Fit, determine which available partition to use for a
process, with Next Fit being a variation of First Fit.

Types of Partitioning:

1. Fixed Partitioning (Static Partitioning)

Description: The system's main memory is divided into a fixed number of non-overlapping partitions
at system startup.

Characteristics: Each process is assigned a designated memory space within a partition.

Advantages: Simple to implement and suitable for small systems or embedded applications.

Disadvantages: Can lead to internal fragmentation, where a process uses less memory than its
assigned partition, wasting the unused space.

2. Dynamic Partitioning (Variable Partitioning)

Description: Partitions are not pre-defined but are created dynamically to match the exact size or
requirements of a process when it is loaded.
Characteristics: The OS initially creates one large partition and then divides the remaining space as
processes are loaded.
Advantages: Reduces internal fragmentation.
Disadvantages: Can lead to external fragmentation, where there are many small, scattered free
memory blocks that are too small to be allocated to new processes, even though the total free
memory is sufficient.
These algorithms decide which free block of memory to allocate to a new process.
1. First Fit: Allocates the first available free partition that is large enough to hold the process.
2. Best Fit: Allocates the smallest available free partition that is sufficient for the process, minimizing
wasted space within that specific partition.
3. Worst Fit: Allocates the largest available free partition, aiming to leave a large contiguous block of
memory for future processes.
4. Next Fit: Similar to First Fit but starts the search for a suitable partition from the last allocation
point rather than from the beginning of memory.
 Each of these placement algorithms has trade-offs between the speed of allocation and the
likelihood of fragmentation.

Non-contiguous Memory Management Techniques:

Non-contiguous memory management techniques in an OS allow processes to be stored in non-

adjacent memory locations, using paging and segmentation to break down processes and map them
to available physical memory frames or segments. These techniques reduce memory wastage from
fragmentation but increase the overhead of address translation, which involves using tables
like page tables to map logical addresses to physical ones.
Paging:

Introduction of Paging:

 Paging is a memory management scheme that permits the physical address space of a
process to be non-contiguous.

 When a process is to be loaded in main memory, paging scheme loads only those required
pages from the process instead of whole process. With this, paging reduces loading time and
amount of physical memory required to load the process. Paging avoids the problem of
fitting the varying sized memory chunks onto the backing store. Paging is also called
demand paging because only demanded pages are transferred to physical memory.

 When some code fragments or data residing in main memory need to be swapped out,
space must be available on the backing store.

 In paging, physical memory is divided into fixed sized blocks called as frames and logical
memory is divided into blocks of the same size called as pages.

 When a process is to be executed, its pages are loaded into any available memory frames
from the backing store. The backing store is divided into fixed sized blocks that are of the
same size as the memory frames. Address(Logical ) generated by the CPU is divided into two
parts: a page number (p) and a page offset (d). Page number is used as an index into a page
table. The page table contains the base address of each page in physical memory. This base
address is combined with the page offset to define the physical memory address that is sent
to the memory unit. This is called address translation. Page table is automatically updated
when
 Paging hardware:

 page is loaded into physical memory

 Example: Using a page size of 4 byte and physical memory of 32 byte(8 pages) we show how
the user’s view of memory can be mapped into physical memory. Logical address 0 is page 0
offset 0. We find that page 0 is in frame 5.

Thus, logical address 0 maps to physical address 20 =(5x4+0).

Example:

Consider, an e-mail program, a web browser and a word processor is loaded into RAM
simultaneously; the 64 MB space is not enough to store all these programs. Without a virtual
memory, a message “You cannot load any more applications. Please close an application to load a
new one.” would be displayed. By using a virtual memory, a computer can look for empty areas of
RAM which is not being used currently and copies them on to the hard disk device. Thus RAM is
freed to load new applications. Actually it is done automatically, the user do not even know that it is
happening, and the user feels like RAM has unlimited space even though the RAM capacity is 32 MB .
It is a process of increasing computer’s RAM by using a section of the hard disk storage as an
extension of RAM.

Advantages of paging:

1. Allows jobs to be allocated in non-contiguous memory locations

2. Paging eliminates fragmentation
3. Memory used efficiently
4. Paging increases memory and processor utilisation.
5. Support higher degree of multiprogramming

Disadvantages:

1. Page address mapping hardware usually increase the cost of computer.

2. Requires the entire job to be stored in memory location.
3. Memory must be used to store the various tables like page table, memory map etc.
Segmentation:

 Segmentation is a memory management technique where an operating system divides a

process into smaller, logical units called segments of variable sizes, such as code, data, or
functions, and places them in non-contiguous memory locations. Each process has a
segment table containing the base address and length (limit) for each of its segments,
allowing for efficient memory allocation, sharing, and protection, unlike fixed-size paging
which doesn't reflect a program's logical structure.
 Like paging segmentation is also a memory management scheme that implements the user’s
view of a program
 In segmentation, the entire logical address space is considered as collection of segments
with each segment having a number and a length.
 The length of a segment may range from 0 to some maximum value as specified by the
hardware and may also change during the execution. The user specifies each logical address
consisting of a segment number(s) and offset(d).
 A segment is a logical unit such as main program, procedure, function, method, object, local
variables, common block, stack, symbol table, arrays etc. as shown in fig.
 Each segment has name and length. Address specify both the segment name and the offset
within the segment.
 Logical address consists of two parts a segment number ‘s’ and an offset into the segment
‘d’. The segment number is used as an index into segment table. Each entry of segment
table has a segment base and segment limit
Example consider the situation sown in fig.. We have segments numbered from 0 through 4. The
segments are actually stored in physical memory.

The segment table has a separate entry for each segment, giving the beginning of the
segment in the physical memory (the base) and the length of that segment(limit) for example
segment 2 is 400 byte long, the beginning of location is 4300. Thus, reference to byte 53 of segment
2 is mapped on to location 4300+53=4353

Advantages:

1. Eliminate fragmentation
2. Provide virtual memory
 3. Facilitates shared segment
4. It provides a convenient way of organising programs and data to the programmer.
Disadvantages:

1. It suffers from external fragmentation.

2. Address translation i.e. conversion of logical address to physical address is not simple as
compared to paging.
3. Increased complexity in the operating system
4. Increased hardware cost for mapping.

Parameter Paging Segmentation

Memory Paging is managed by hardware Segmentation is managed by software through a segm
Management through a page table.
Memory Paging results in less internal Segmentation results in more internal fragmentation b
Utilization fragmentation, but more external
fragmentation.
Page Size Page size is fixed and determined by Segment size is variable and determined by the proce
the system.
Overhead Paging has lower overhead due to a Segmentation has higher overhead due to a more com
simpler memory management scheme.
Address Address translation in paging is Address translation in segmentation is more complex
Translation straightforward as it involves a single
table lookup.
Flexibility Paging is less flexible due to the fixed Segmentation is more flexible due to the variable seg
page size.
Performance Paging has better performance due to Segmentation has lower performance due to the softw
the hardware-based management and translation.
simpler address translation.

4.4 Virtual memory:

Basics of virtual memory:

Def. 1 : Virtual memory is a technique which allows the execution of processes that may not be
completely in memory.

Def. 2 : Virtual memory is a memory management technique that provides an idealised abstraction
of the secondary memory that are actually available on a given machine which creates the illusion
to users of a very large main memory.

Virtual memory is a memory which appears to be present but it is actually it is not .

Virtual memory is the separation of user logical memory from physical memory. This separation
allows an extremely large virtual to be provided for programmers when only a smaller physical
memory is available.

Virtual memory makes the task of programming much easier because the programmer no longer
needs to worry about the amount of the physical memory available.
Virtual memory is commonly implemented by demand paging and demand segmentation.

It is not easy to implement and may decrease the performance, if it is used carelessly. Following
figure shows the concept of virtual memory.

Page Replacement:

When the CPU needs to execute a page and if that page is not available in main memory then this
situation is called page fault.

For bringing in the required page into main memory, if the space is not available in memory then we
need to remove the page from the main memory for allocating the space to the new page which
needs to be executed.

When page fault occurs, the operating system has to choose a page from secondary memory and
transferred to frame of main memory which is already filled. One of that page is replaced by new
page that cpu demanded page of secondary memory. This is known as page replacement.

Following are the steps required for page replacement

1. Find the location of the desired page on the disk

2. Find a free frame:
i) if there is free frame, use it
ii) if there is no free frame, use page replacement algorithm to select a victim frame.
iii) writes the victim frame to the disk, change the page and frame tables
3. Read the desired page into the newly freed frame, change the page and frame tables.
4. Restart user process.
Operating system provides tool the replacement algorithm in which page is swapped out, writes to
secondary memory(disk) and new page is swapped in a frame of main memory. Page table and
frame table is automatically updated during page replacement.

Page replacement algorithm works on string of memory reference is called reference string. It is a
string of pages demanded by cpu in future or used in past.

A page replacement algorithm is evaluated by running the particular algorithm on a string of

memory references and the page faults. Referenced string is a sequence of pages being referenced.

The Different page replacement algorithms are used are FIFO(First in First Out), algorithm, LRU(least
Recently Used) algorithm and Optimal page replacement algorithm.

1. FIFO (First in First Out) :

In this algorithm, a page must be replaced when frames in main memory is full. When a page is
replaced, the oldest page is chosen i.e first arrived page in main memory. FIFO queue is created to
hold all pages in memory. We replace, the page at the head of the queue.

When a page is brought into main memory frame, we insert it at the tail of the queue. This algorithm
is simple to understand and performance is not always good. If number of frames are increased,
number of page faults also increased.

Example 1 : Consider the reference string 1,2,3,4,1,2,5,1,2,3,4,5. Calculate page fault for three and
four frames and ratio of page fault and page hit using FIFO algorithm.
 1. Page fault for three frames:

No. of Page faults (F) = 9 No. of page hits(H) = 3

Page Miss ratio = 9/12*100 = 75 Page Hit Ratio = 3/12*100= 25

Example 2: Consider 3,2,1,3,4,1,6,2,4,3,4,2,1,4,5,2,1,3,4 . Calculate page fault for three and ratio of
page fault and page hit using FIFO algorithm.

No. of Page faults (F) = 13 No. of page hits(H) = 6

Page Miss ratio = 13/19*100= Page Hit Ratio =6/19*100

Example 3 : : Consider the reference string 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 Calculate page

fault for three and ratio of page fault(Miss) and page hit.

Page faults(F) = 15 Page Hit = 5 Page Miss Ratio= 15/20 Page Hit ratio= 5/20

Advantages:

1. It is simple to implement.
2. It is easiest algorithm
3. Easy to understand and execute

Disadvantages:

1. It is not very effective

2. System needs to track of each frame
3. Its performance is not always good
4. It suffers from Belady’s anomally.
5. Bad replacement choice increases the page fault rate and slow process execution

2. Optimal Page replacement algorithm :

An optical page replacement algorithm has the lowest page fault rate of all algorithms and never
suffer from Belady’s anomally [Beladys anomaly is the name given to the phenomenon where
increasing the number of page frames results in an increase in the number of page faults for a given
memory access pattern]. This phenomenon is commonly experienced in First in first out (FIFO)

Optimal replacement algorithm states replace that page which will not be used for the longest
period of time in future.

Advantages:

1. It is the best possible optimal algorithm

2. It gives the smallest number of page faults.
3. It never suffers from Belady’s anomally.
4. Twice as good as FIFO page replacement algorithm

Disadvantages:

1. This algorithm is difficult to implement

2. It requires future knowledge of reference string.
Example 1 : Consider the reference string 1,2,3,4,1,2,5,1,2,3,4,5. Calculate page fault for three
frames and ratio of page fault and page hit using Optimal Page replacement algorithm.

Note : Replace the page which will not be used for the longest period of time in future.

No. of page fault : 7 Page fault /miss ratio : 7/12*100

No. of Hits : 5 Hit ratio: 5/12*100

Example 2 : Consider the reference string 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 Calculate page fault

for three frames and ratio of page fault and page hit using Optimal Page replacement algorithm.

Note : Replace the page which will not be used for the longest period of time in future.

No. of page fault : 9 Page fault /miss ratio :

No. of Hits : 11 Hit ratio:

3. LRU(Least Recently Used) Page replacement Algorithm :

In LRU replacement algorithm, page is replaced which has not been used for the longest period of
time.

We can think of this strategy as the optimal page replacement algorithm looking backward in time,
rather than forward.

Example 1 : Consider the reference string 1,2,3,4,1,2,5,1,2,3,4,5. Calculate page fault for three
frames and ratio of page fault and page hit using Least recently Used Page replacement algorithm.

Solution :

Note : Replace the page which is has not been used for the longest period of time.

No. of page fault : 10 Page fault /miss ratio :

No. of Hits : 02 Hit ratio:

Example 2 : Consider the reference string 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1. Calculate page fault

for three frames and ratio of page fault and page hit using Least Recently used replacement
algorithm.

Solution :

No. of page fault : 12 Page fault /miss ratio :

No. of Hits : 08 Hit ratio:

Example 3 : Consider the reference string 9,7,6,1,7,6,1,2,2,7,2. Calculate page fault for three
frames and ratio of page fault and page hit using FIFO, Optimal and Least Recently used
replacement algorithm.

Solution :
No. of page fault : Page fault /miss ratio :

No. of Hits : Hit ratio:

Advantages:
1. LRU is actually quite a good algorithm
2. It never suffers from Belady’s anomally
3. LRU algorithm is very feasible to implement
Disadvantages:
1. LRU algorithm is that it requires additional data structure and hardware support.
2. Its implementation is not very easy.
Difference between FIFO and LRU:

S.N. FIFO LRU

1. Number of page fault is more than Number of page fault is more than optimal and
LRU and optimal less than FIFO

2. Suffer from Belady’s anomaly Does not suffer from belady’s anomaly

3. Future predictions not required Future prediction is required.

4. Simple to implement. Difficult to implement

Differences
LRU FIFO

Replaces the least recently used

Principle Replaces the oldest page in memory
page

Requires additional data structure No additional data structure

Data Structure
for tracking page usage order required

Performs better in reducing page May not always provide optimal

Performance
faults performance

Access Pattern Sensitive to the access pattern of

Not sensitive to the access pattern
Sensitivity pages

Implementation Relatively more complex to

Simple to implement
Complexity implement
 UNIT-V

File Management
5.1 File Concept:
File management is the important function of operating system. It facilitates
storage, access and retrieval of both data and programs or all the operating
system and of the user.
 File management is the process of manipulating files in computer system. File
management includes the process of creating, modifying and deleting the
files.
 A file is a collection of specific information stored in the memory of the
computer system. The operating system defines a logical storage unit known
as a file, with all data being stored in the form of files.
 File management system is that set of system software that provides services
to users and applications in the use of files.
 File system is that an operating system or program uses to organise, manage
and keep track of files known as file system. NTFS is include in Windows xp,
Windows 7, Windows 12 etc., MS-DOS uses FAT-16, FAT-32, Unix os uses Unix
file system, Linux uses extended filed system (EXT3). These files systems
provides information about files, files types, file attributes, directory
structure etc.
Functions of File Management in Operating system:
1. File management helps in creating new files and placing them at a specific
location.
2. It provides a uniform logical view of data to the users rather than physical
view. i.e. internal structure by giving user friendly interface. E.g .doc in word.
3. It provides security measures for confidential data such as electronic funds or
criminal records. Read only, Hide etc.
4. It makes the process of sharing the files among different users easy.
5. It controls transferring of data blocks between the secondary memory storage
and main memory as when required between different files.
6. It helps to store the files in separate folders known as directories in Unix or
Linux that ensures better organisation of data.
7. Memory space management is an important function of file management. It
allocates and manages space for the files
 8. File management helps in modifying the content as well as the name of the
files as per the user’s requirement.
File Concept: A file is a collection of related information that is recorded on
secondary storage such as magnetic disks, magnetic tapes and optical disks.
Commonly files represent programs(source and object forms) and data. Data files
may be alphabetic, alphanumeric or binary.
Many different types of files may stored in a file : source program, object program,
executable program, Numeric data, text data, payroll records, graphic images, sound
recording and so on.
A file has a certain defined structure according to its types.
Text file: is sequence of characters organised into lines
Source file: is sequence of sub routines and functions, each of which is further
organised as declarations followed by executable statement.
Object file: is sequence of bytes organised into blocks understable by the system’s
linker.
Executable file: is a series of code sections that the loader can bring into memory
and execute. Files are mapped by the operating system on to the physical devices
File attributes:
A files have certain attributes which vary from one operating system to another.
Attributes are nothing but the properties of files which store the file related data.
Attributes are useful to get information about a particular file or directory. File
system keeps the track of information.
Following is the list of some common file attributes:
1. Name: The symbolic file name is the only information kept in human readable
form.
2. Type: This information is needed for those systems that support different
types.
3. Location: This information is a pointer to a device and to the location of the
file on that device.
4. Size: The current size of the file(in bytes, words or blocks) and possibly the
maximum allowed size are included in this attribute.
 5. Protection: Access control information controls that who can do reading,
writing, executing and so on.
6. Time, date and user identification: This information may be kept for creation.,
Last modification and last use
7. Identifier: File system gives a unique tag or number that identifies file within
file system and which is used to refer files internally.
8. Creator or owner: A creator is a user or a person who has created that file and
owner is a person who owns that file currently.
The Information about all files is stored in the directory structure, which is
present on secondary storage. By using the name of the file and its unique
identifier, we can search the directory for the entry of a file.
File operations:
To define file properly, we need to consider the operations to be performed on files.
The Operating system provides system calls to create, write, read, reposition, delete
and truncate files.
Different systems provide different operations to allow storage and retrieval.
Common file operations are:
1. Creating a file:Two steps are necessary to create a file. First to create space in the
file system must be found for the file. Second an entry for a new file must be made in
the directory. The directory entry record the name of the file and location in the file
system.
2. Writing a file: To write a file, we make a system call specifying both the name of
the file and the information to be written to the file. Given the name of the file, the
system searches the directory to find the location of the file then write pointer must
be updated whenever a write occurs.
3. Reading a file: To read from a file, we must use a system call that specifies the
name of the file and where(in memory) the next block of the file should be put..
System needs to keep a read pointer to the location in the file system where the next
read is to take place. Once the read has taken place, the read pointer is updated.
4. Repositioning within the a file : The directory is searched for the appropriate
entry and the current file position is set to a given value. Repositioning within the
file does not need to involve any actual I/O. This file operation is also known as a file
seeks.
5. Deleting a file: To delete a file, we search the directory for the named file. Having
found the associated directory entry, we release all the file space and erase the
directory entry.
6. Truncating a file: Instead of deleting a file and then recreate it, this function allows
all attributes to remain unchanged but for the file to be reset to length zero. User
wants to erase the file contents of the file.
Other common operations include appending new information to the end of an
existing file and renaming an existing file.
File types:
• To operate on the file in a reasonable way an operating system recognises the
type of a file.
• The filename is split into two parts a name of file and extension. E.g
[Link] created in ms-excel.
• The system uses the extension to indicate to indicate the type of the file and
the type of operations that can be done on that file. Only a file
with .com, .exe, .bat extensions can be executed. All .exe. and .com are two
forms of binary executables files, whereas a .bat file is containing in the ASCII
format, commands to the operating system.
• The following table shows the common file types
File structure:
Files can be structured in any of several ways.
1. Stream of bytes:
• OS considers a file to be unstructured.
• Simplifies file management for the OS. Application can impose their own
structure.
• Used by UNIX, Windows, most modern operating system.
2. Records :
• A file is sequence of fixed length record, each with some internal structure
• Collection of bytes treated as a unit. Example employee record.
• Operations at the level of record ( read_rec,write_rec)
• File is a collection of similar records. OS can optimise operations on records.
3. Tree of records :
• A file consists of a tree of records, not necessarily all the same length
• Records are of variable length
• Each has an associated key. Record retrieval based on key.
File system structure:
• User create and store data in computer system for later retrieval and
manipulation. The computer system normally stores data in storage devices
such as disks so that the data can retain permanently.
• An operating system implements a software layer for users to access data,
retrieve data and manipulate data from storage devices with relative ease.
Entities within file system and directories are maintained separately. When
the operating system is installed for the first time, it is loaded into directory
structure. Following are the layers included in file system.
Each layer has its own functionality.
• A file system is a section of hard disk that has been allocated to contain files.
This section of hard disk is accessed by mounting the file system over a
directory. After the file system is mounted, it looks just like any other
directory to the end user.
• When the operating system is installed for the first time, it is loaded into a
directory structure. Following are the software layers included in file system.
1. Application layer –This is a top most layer. This layer provides application program
interface(API) for file operation like open, close, read, write etc.
2. Logical file system layer - This layer maintains directory structure as well as meta
data of a file like file name, attributes etc. This layer provides protection and security
to the file and provides information to next layer.
3. File organisation layer - Using upper information the file organisation module
map logical block address into corresponding physical block address. It performs free
space management.
4. Base file System layer – By knowing physical block address, it generates generic
commands to underlying layer.
5. I/O control layer – It consists of device drivers and interrupt handler. It translates
commands of upper layer that can understand by devices.
6. Devices layer – devices are physical devices which performs the function as per
instructions.
 General File System Structure
5.2 File Accessing methods:
Methods those provides reading from or writing to a file are known as access
method. There are several ways that the information in the file can be accessed.
An access method describes the manner and mechanisms by which a process
accesses the data/information in a file.
Following are the access methods are 1. Sequential File Access 2. . Random or Direct
File Access 3. Indexed Sequential File Access
1. Sequential File Access:
• The simplest access method is sequential access. Information in the file is
processed in order, one record after the other.
• The bulk of the operations on a file are reads and writes. The read and write
operations on the sequential file are done in sequential order.
• A read operation reads the next portion of the file and automatically advances
a file pointer, which tracks the I/O location. Similarly a write appends to the
end of the file and advances to the end of the newly written material.
• Such a file can be reset to the beginning and on some systems a program may
be able to skip forward or backward ‘n’ records for some integer ‘n’
• In this type of file, a fixed format is used for records. All records are of the
same length consists of the same number of fixed length fields in a particular
order.
 • One particular field usually the first field in each record is referred to as the
key field. The key field uniquely identifies the record.
Roll No. Name Marks

Advantages: 1. Easy to access the next record. 2. Data organisation is very simple. 3.
Absence of data structures 4. They are easily stored on tapes as well as disks.
Disadvantages: 1. Wastage of memory space because of master file and transaction
file. 2. It is more time consuming since reading, writing and searching always start
from beginning of the file. 3. Sequential file provides poor performance.
Beginning Current position End

Rewind Read r Write

2. Direct Access method or random access method:

It is a technique for finding data on a disk by deriving its storage address from an
identifying key in the record such as account number.
A file is made up of fixed length of logical records that allow programs to read and
write records rapidly in no particular order.
In direct file access, records are accessed directly by physical addresses of the
location at which the records are stored in the disk.
A direct access file allows arbitrary blocks to be read or written. Thus, we may read
block 14, then read block 50 and then write block 7. There are no restrictions on the
order of reading and writing for a direct access file.
Direct file access is used in those applications, where speed is the main constraint for
accessing. Hashing technique is usually used for accessing the records in direct
access file.
Advantages :
1. Using this method we can access any records randomly
2. It gives fastest retrieval of records.
Disadvantages:
1. Wastage of storage space, if hashing algorithm is not chosen properly
2. This method is complex and expensive.
3. Indexed sequential file access:
An indexed sequential file is a sequential file in which the records are indexed. It is
improvement in sequential files access method.
Index is maintained just like index in book.
Entries in indexed files are made of two fields like Key field and pointer
To find a specific field in file, the index is searched first and then pointer start
searching the record at location it indicates.
Advantages:
1. Variable length records are allowed
2. Indexed sequential file may be updated in sequential or random mode. Very
fast operation
Disadvantages:
1. As the file grows, a performance deteriorates rapidly hence reorganisation is
required.
2. When a new record is added to file, all of the index files must be updated.
3. Consumes large memory space for maintaining index files.

5.3 File Allocation Methods:

File allocation methods determine how disk blocks are assigned to files, with the
three main types being Contiguous, Linked, and Indexed allocation. Contiguous
allocation assigns a single, unbroken set of blocks to a file, offering fast sequential
access but leading to external fragmentation. Linked allocation stores file blocks non-
contiguously, forming a linked list of blocks across the disk, which avoids external
fragmentation and supports file growth but requires slower traversal for random
access. Indexed allocation uses a special "index block" to store pointers to all the
file's actual blocks, supporting direct access and eliminating external fragmentation,
though it introduces its own wasted space for the index. Following are the types of
file allocation methods:
1. Contiguous Allocation
2. Linked Allocation
3. Indexed Allocation
1. Contiguous allocation:
A file occupies a single, consecutive range of disk blocks. The operating system keeps
track of the file's starting block and its length.
In this scheme, each file occupies a contiguous set of blocks on the disk. For example,
if a file requires n blocks and is given a block b as the starting location, then the
blocks assigned to the file will be: b, b+1, b+2,......b+n-1. This means that given the
starting block address and the length of the file (in terms of blocks required), we can
determine the blocks occupied by the file. The directory entry for a file with
contiguous allocation contains
Address of starting block
Length of the allocated portion.
The file 'mail' in the following figure starts from the block 19 with length = 6 blocks.
Therefore, it occupies 19, 20, 21, 22, 23, 24 blocks.

Advantages:
1. Both the Sequential and Direct Accesses are supported by this. For direct access,
the address of the kth block of the file which starts at block b can easily be obtained
as (b+k).
2. This is extremely fast since the number of seeks are minimal because of
contiguous allocation of file blocks.
Disadvantages:
1. This method suffers from both internal and external fragmentation. This makes it
inefficient in terms of memory utilization.
2. Increasing file size is difficult because it depends on the availability of contiguous
memory at a particular instance.

2. Linked List Allocation In this scheme, each file is a linked list of disk blocks
which need not be contiguous. The disk blocks can be scattered anywhere on the
disk. The directory entry contains a pointer to the starting and the ending file block.
Each block contains a pointer to the next block occupied by the file. The file 'jeep' in
following image shows how the blocks are randomly distributed. The last block (25)
contains -1 indicating a null pointer and does not point to any other block.

Advantages:
1. This is very flexible in terms of file size. File size can be increased easily since the
system does not have to look for a contiguous chunk of memory.
2. This method does not suffer from external fragmentation. This makes it relatively
better in terms of memory utilization.
Disadvantages:
1. Because the file blocks are distributed randomly on the disk, a large number of
seeks are needed to access every block individually. This makes linked allocation
slower.
2. It does not support random or direct access. We can not directly access the blocks
of a file. A block k of a file can be accessed by traversing k blocks sequentially
(sequential access ) from the starting block of the file via block pointers.
3. Pointers required in the linked allocation incur some extra overhead.

3. Indexed Allocation In this scheme, a special block known as the Index

block contains the pointers to all the blocks occupied by a file. Each file has its own
index block. The ith entry in the index block contains the disk address of the ith file
block. The directory entry contains the address of the index block as shown in the
image:

Advantages:
1. This supports direct access to the blocks occupied by the file and therefore provides
fast access to the file blocks.
2. It overcomes the problem of external fragmentation.
Disadvantages:
1. The pointer overhead for indexed allocation is greater than linked allocation.
2. For very small files, say files that expand only 2-3 blocks, the indexed allocation
would keep one entire block (index block) for the pointers which is inefficient in terms
of memory utilization. However, in linked allocation we lose the space of only 1
pointer per block.
5.4 Directory Structure:
A directory is a container that is used to contain folders and files. It organises files
and folders in a hierarchical manner. In other words, directories are like folders that
help organise 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.
The operating system uses directories to track where files are stored, just like using
folders to organise papers.
Different directory structures can be used to suit various organisational needs.
Understanding directory structures helps in organising and accessing files more
easily.
By using these structures, it becomes simpler to manage and navigate files on your
computer.

Different Types of Directories in OS

In an operating system, there are different types of directory structures that help
organise and manage files efficiently.
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.

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.
Advantages
1. 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.
2. 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.
3. 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.
4. 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.
5. 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
1. There may chance of name collision because two files can have the same name.
2. Searching will become time taking if the directory is large.
3. This can not 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 lists only the files of a single user.
System’s master file directory (MFD) is searched whenever a new user id is created.

Advantages
1. The main advantage is there can be more than two files with same name, and
would be very helpful if there are multiple users.
2. 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
1. As there is advantage of security, there is also disadvantage that the user cannot
share the file with the other users.
2. Unlike the advantage users can create their own files, users don't have the ability
to create subdirectories.
3. 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
1. This directory structure allows subdirectories inside a directory.
2. The searching is easier.
3. File sorting of important and unimportant becomes easier.
4. This directory is more scalable than the other two directory structures explained.
Disadvantages
1. As the user isn't allowed to access other user's directory, this prevents the file
sharing among users.
2. As the user has the capability to make subdirectories, if the number of
subdirectories increase the searching may become complicated.
3. Users cannot modify the root directory data.
4. If files do not fit in one, they might have to be fit into other directories.