Subject : Operating System

Instructor : Mr. Ankit Mehta

Detailed Syllabus
Unit 1 : Introduction - Operating system Structure, layered structure, System component,
operating system function, classification of operating systems, batch, interactive, time
sharing, real time system, multi-user system, multi process system, multi processor system,
multi-threaded system, operating system services, renterant kernels, monolithic and micro
kernel systems.
Unit 2 : Concurrent Processes - Process concept, principle of concurrency, producer
consumer problem, mutual exclusion, critical section problem, dekker's solution, Peterson
solution Semaphores, test and set operation, classical problem in concurrency, dining
philosopher problem, sleeping barber problem inter process communication model and
schemes process generation.
Unit 3 : CPU Scheduling - Scheduling concept, performance criteria, process state, process
transition diagram, schedulers, process control block(PCB), process address space, process
identification information, thread and their management, scheduling algorithm multi
processor scheduling, deadlock system model deadlock characterization, prevention,
avoidance and detection recovery from deadlock.
Unit 4 : Memory Management - Basic bare machine, Resident monitor, multi programming with
fixed partition, multi programming with variable partition, protection scheme, paging,
segmentation , paged segmentation, virtual memory concept, demand paging, performance of
demand paging, page replacement algorithm, thrasing, cache memory organization, locality of
reference.
Unit 5 : Management & Disk Scheduling - I/O devices, and I/O subsystem I/O buffering, disk
storage and disc scheduling, RAID, file system, file concept, file organisation and access
mechanism, file directories and file sharing, file system implementation issues file system
protection and security.

Page 1
Page 2
 Unit 1

The term "operating system" was first used in the early 1960s to describe the software
that controls the execution of computer programs and manages hardware resources such
as memory and input/output devices.
The term was coined by John W. Tukey in 1958, in his book "An Introduction to
Mathematical Methods of Statistics," where he used it to describe the software that
manages the operation of a computer system.

"It is better to solve the right problem approximately, than to

solve wrong problem exactly."

John W. Tukey

Page 3
 What is Operating System
Operating system is a system software.
It act as an intermediary between the computer user and computer hardware.
An operating system (OS) is a type of software that manages computer hardware and
software resources.
Provide a platform on which other application program installed.
Ques : Can we access the hardware without operating system?
Ans : YES, but it is not convenient neither efficient.

COMPILER ASSEMBLER MS-OFFICE VLC

SYSTEM & APPLICATION PROGRAMS

OPERATING
SYSTEM

COMPUTER
HARDWARE

Abstract View of Operating System

Goals and Functionalities of operating system

Goals - What to achieve Functionalities - How to achieve

Process Management
Primary Goal (Convince/User Memory Management
friendly)
I/O devices Management
File management
Secondary Goal
(Efficiency) Network Management
Security Management
Interactive operating system
An Interactive Operating System is a type of operating system that allows users to interact
with it using a Graphical User Interface (GUI) or Command Line Interface (CLI). It provides an
interface to the user that allows them to communicate with the computer and perform tasks
such as file management, running applications, configuring settings, etc.
Examples of Interactive Operating Systems include:
Microsoft Windows
macOS
Linux with graphical desktop environments such as GNOME, KDE, or Xfce
Android (for mobile devices)
iOS (for Apple devices)
These operating systems provide users with a visually rich and intuitive interface, making it
easier for them to perform tasks without the need for specialized technical skills. They also
often provide users with access to a wide range of software applications and tools that they
can use to enhance their productivity and creativity. Page 4
 Evolution of Operating System
In starting, mainframe computer were there.
Common input and output device work card reader and tape drive.
User prepare a job which consisted of the program input data and control instructions.
Input job is given in the form of punch card and after processing result also appear in the
form of punch card.
JOBS

CPU Program
I/P data
Input OS Output
Control instruction
User
Program

COMPUTER
Disadvantages
No concept of memory hierarchy.
Very less interactive systems.
Very poor CPU Utilization, speed mismatch between I/O device & CPU.
Every jobs have the different requirement.

Batch Operating System

Batch processing was very popular in the 1970s. Users using batch operating systems do
not interact directly with the computer.
Jobs with the similar needs are batched together and executed through the processor as
a group.
Each user prepares their job using an offline device like a punch card and submitting it to
the computer operator. eg. Fortran Batch, Cobol Batch

User 1 -> Job 1 Batch 1 Batch 2 CPU

User 2 -> Job 2
JOB1 JOB12
Operator
user 3 -> Job 3 input OS Output
. . JOB5 JOB14
. ..
User
. . JOB7 Program
User n -> Job n

Batch Operating System

Advantages Disadvantages
In Batch OS, Jobs are executed after
Limited memory.
one another, saving time from the
interaction of input and output device
activity like loading, linking and
directly with CPU.
compiling.
Very less buffer size, leads to less
During execution no manual intervention
utilization of CPU
is needed, less human interaction.

Page 5
SPOOLING : Simultaneous Peripheral operations online
Spooling refers to putting data of various I/O jobs in a buffer. This buffer is a special area in
memory or hard disk which is accessible to I/O devices.
COMPUTER

CPU

MAIN
MEMEORY
I/P DEVICE O/P DEVICE

DISK
Input and output devices are relatively slow compared to CPU, as CPU is digital device.
In Spooling, data is stored first on to the disc(digital device) and then CPU interact with
disc via main memory.
Spooling is capable of overlapping input and output operation for one job with CPU
operation of other jobs.

Advantages Disadvantages
No interaction of input output devices In starting spooling was uni
with CPU. programming.
CPU utilisation is more as CPU is busy No concept of context switching
most of the time. CPU sit idle for the second event

Multiprogramming operating system

When more than one program is available in the main memory of single processor
computer, this concept is called multi programming.
Multi programming means more than one program process in main memory which are
ready to execute.
Process generally requires CPU time and input/output time so if running process perform
input/output or some other event which do not required CPU then instead of sitting idle
CPU make context switching and pick some other process and this idea will continue.
Do not set idle unless there is a no process ready to execute or at a time of context
switching in main memory.
Page 6
 MM SM

OS
P1 SECONDARY
CPU MEMORY
P2
Pn

Advantages Disadvantages
High CPU utilisation. Difficult scheduling of the process.
Less waiting time & response time. Main memory management required.
Load is very high, hence it is very useful. Memory fragmentation.
Multitasking/Time shearing operating system
Multi-tasking is an extension of multi-programming.
There is only a CPU but the context switching between the process so quickly, they give the
illusion that all are executing at the same time.
It improves a better response time and execution of multiple processes together.
Fixed Time Quantum
One processor but Multiple processes, the processor is so fast that it can complete all the
process alone.
Sometimes it is called multitasking with round robin.

EMAIL

Games OS CPU

Youtube

Multi Processing operating system

If a system have more than one Processor or CPU it is called multi processing system.
Two or more CPU with single computer in a close communication are sharing like system
bus memory and other input and output devices.
Different process runs on different CPU (true parallel execution).

Page 7
 Advantages Disadvantages
Increased throughput(processing per unit More complex as too many processor
time). are available.
Increased reliability. Overhead and coupling reduces
Cost saving(as their is only multiple copies throughput.
of CPU, other devices are same. Large main memory.
True parallel processing

Real Time Operating System

A real-time operating system (RTOS) is an operating system that is used in computing systems
that needs strict completion deadlines for all the tasks that need to be performed on it.
Types
Hard Real-Time Operating System(HRTOS)
The hard real-time operating system is used when we need to complete tasks by a given
deadline. If the task is not completed on time then the system is considered to be failed.
eg. Pacemaker requires require a hard real-time operating system.
Soft Real Time Operating System(SRTOS)
A soft real-time operating system is used where few delays in time duration are acceptable.
That is if the given task is taking a few seconds more than the specified time then also no
critical damage takes place.
eg. telephone switches, the sending or receiving of the call.

Processes and Threads

A process is an instance of a program that is being executed. When we run a program, it does
not execute directly. It takes some time to follow all the steps required to execute the
program, and following these execution steps is known as a process.
A thread is a basic unit of CPU utilization it comprises a thread ID, a program counter, a
register set, and a stack. It shares it's code section, data section and other operating system
resources such as open files and signals with other thread belonging to the same process.
There are two types of threaded process. single threaded process and multi-threaded
process.

Eg. A word processor may have a thread for displaying graphics, another thread for
responding to keystrokes from the user, and a third thread for performing spelling and
grammar checking in the background.
NOTE : Most operating-system kernels are now multi threaded. Several threads operate in the
kernel, and each thread performs a specific task, such as managing devices, managing
memory, or interrupt handling.

Page 8
 Multi-threaded Model
There is a relationship exist between the user threads and Kernel thread. There are three
common ways of establishing the relationship between kernel and user thread.
Many to one model
The many-to-one model maps many user-level User thread
threads to one kernel thread. Thread
management is done by the thread library in
user space, so it is efficient;
Drawback : the entire process will block if a
thread makes a blocking system call. Also,
because only one thread can access the kernel
at a time, multiple threads are unable to run in K Kernel thread
parallel on multiprocessors.

One to one model

The one-to-one model maps each user thread to
User thread
a kernel thread. It provides more concurrency
than the many-to-one model by allowing another
thread to run when a thread makes a blocking
system call; it also allows multiple threads to run
in parallel on multiprocessors.
Drawback : user thread requires creating the K K K K Kernel thread
corresponding kernel thread. Because the
overhead of creating kernel threads can burden
the performance of an application

Many-to-Many Model User thread

Many user thread are associated with many kernel
thread. The number of kernel threads created
depends upon a particular application. The
developer can create as many threads at both
levels but may not be the same. if any thread
makes a blocking system call, the kernel can
schedule another thread for execution. true
concurrency cannot be achieved by this model. Kernel thread
K K K

Operating system services

The operating system provides the number of services, some of them are as follows.
Program execution
To execute a program, several tasks need to be performed. Both the instructions and data
must be loaded into the main memory. In addition, input-output devices and files should be
initialized, and other resources must be prepared. The Operating structures handle these
kinds of tasks.
Control Input/output devices
As there are numerous types of I/O devices within the computer system, and each I/O device
calls for its own precise set of instructions for the operation. The Operating System hides
that info with the aid of presenting a uniform interface.
Page 9
File management
Computers keep data and information on secondary storage devices like magnetic tape,
magnetic disk, optical disk, etc. Each storage media has its capabilities like speed, capacity,
data transfer rate, and data access methods.
Communication
The operating system manages the exchange of data and programs among different
computers connected over a network. This communication is accomplished using message
passing and shared memory.
What is Kernel?
A kernel is an important part of an OS that manages system resources. It also acts as a
bridge between the software and hardware of the computer. It is one of the first program
which is loaded on start-up. The Kernel is also responsible for offering secure access to
the machine’s hardware for various programs. It also decides when and how long a
certain application uses specific hardware.
Monolithic Kernel runs all the basic system services like process management, Memory
management, I/O communication, and interrupt handling, file system, etc in kernel space.
In this type of Kernel approach, the entire operating system runs as a single program in kernel
mode.
APPLICATION

VFS, System Calls

Kernel Space
Scheduler, Virtual Memory

Device Drivers

IPC, File System

Hardware

All OS related component integrate together as a single module in kernel space.

Large in size, and execution is very fast.
Difficult to find error.
If user want to add new service, user have to modify the entire OS.
Security issues will always exist, as there is no isolation among the various services of OS.
eg. DOS, LINUX.
A Microkernel is the most important part for correct implementation of an operating
system. All non essential components are moved from kernel space to user space.

Kernel Space

Page 10
Only essential component such as IPC, memory management and scheduling are
included in kernel space.
If any one of the service fails, rest of the OS will work fine.
Small in size, execution is slow as compared to monolithic kernel.
New services can be added easily, and easy to debug.
eg. Mac, Windoows.

Page 11
 CPU
SCHEDULING

CPU Scheduling - In Multi-programming systems, the Operating system schedules the

processes on the CPU to have the maximum utilization of it and this procedure is called CPU
scheduling.
A process execution consist of CPU execution and I/O execution. Normally every process
begins with the CPU burst that may be followed by I/O burst then another CPU burst,
eventually in the last the process will end up on the CUP burst.
CPU Bound : These are the process which requires most of the time CPU. [Calculation]
I/O Bound : These are the process which requires most of the time I/O devices.[ Printing
pages].
Whenever the CPU become idle, the operating system must select one of the processes from
the ready queue to be executed. The selection process will be carried out by short term
scheduler.
Process states
As a process executes, its changes its state, and the state of the process is defined by the
current activity of that process. The process, from its creation to completion, passes
through various states. The minimum number of states is five.
1. New : A program which is going to be picked up by the OS into the main memory is called a
new process.
2. Ready : Whenever a process is created, it directly enters in the ready state, in which, it
waits for the CPU to be assigned. The OS picks the new processes from the secondary
memory and put all of them in the main memory. The processes which are ready for the
execution and reside in the main memory are called ready state processes. There can be
many processes present in the ready state.
3. Running : One of the processes from the ready state will be chosen by the OS depending
upon the scheduling algorithm. Hence, if we have only one CPU in our system, the number
of running processes for a particular time will always be one. If we have n processors in the
system then we can have n processes running simultaneously.
4. Block or wait : From the Running state, a process can make the transition to the block or
wait state depending upon the scheduling algorithm. When a process waits for a certain
resource to be assigned or for the input from the user then the OS move this process to the
block or wait state and assigns the CPU to the other processes.
5. Completion or termination : When a process finishes its execution, it comes in the
termination state. All the context of the process (Process Control Block) will also be deleted
the process will be terminated by the Operating system.
6. Suspend ready : A process in the ready state, which is moved to secondary memory from
the main memory due to lack of the resources (mainly primary memory) is called in the
suspend ready state. If the main memory is full and a higher priority process comes for the
execution then the OS have to make the space for the process in the main memory by
throwing the lower priority process out into the secondary memory. The suspend ready
processes remain in the secondary memory until the main memory gets available.
Page 12
7. Suspend wait : Instead of removing the process from the ready queue, it's better to
remove the blocked process which is waiting for some resources in the main memory. Since
it is already waiting for some resource to get available hence it is better if it waits in the
secondary memory and make room for the higher priority process. These processes
complete their execution once the main memory gets available and their wait is finished.

STS
LTS

New Ready Time

Running Terminated
Quantum

Priority
Suspend I/O complete I/O request
resume

MTS

Waiting/Block
Suspend/
Ready
resume
Suspend

Suspend/
Process completed I/O, but Wait
still in suspended

Scheduler
It is a special type of software which handles the process scheduling in various ways.
Long term scheduler
It select the process from the secondary memory and put them into the ready queue of
main memory. It also increase the degree of multi-programming.
Short term scheduler
Short term scheduler is also known as CPU scheduler. It selects one of the Jobs from the
ready queue and dispatch to the CPU for the execution.
Mid term scheduler
If the running state processes needs some IO time for the completion then there is a need to
change its state from running to waiting. It also decrease the degree of multi-programming
Process Control Block
Each process is represented in the operating system by a process control block (PCB)—also
called a task control block. It contains many pieces of information associated with a specific
process.

Page 13
Process state : The state may be new, ready, running, waiting, halted, and so on.
Program counter : The counter indicates the address of the next instruction to be executed
for this process.
CPU registers : These are the CPU register which include accumulators, index registers, stack
pointers, and general-purpose registers, plus any condition-code information.
CPU-scheduling information : This information includes a process priority, pointers to
scheduling queues, and any other scheduling parameters.
Memory-management information : This information may include such items as the value of
the base and limit registers and the page tables.

Preemptive and Non-preemptive Scheduling

CPU scheduling is the process of allocating CPU resources to different processes in the
system. There are two main types of CPU scheduling algorithms:
Pre-emptive and non-pre-emptive.
Pre-emptive CPU scheduling is a method where the CPU can be taken away from a process
that is currently running, even if it hasn't completed its execution. This means that a high-
priority process can interrupt a lower-priority process that is currently running, and start
executing immediately. The main advantage of pre-emptive scheduling is that it ensures that
higher-priority processes get the CPU time they need, which can lead to better overall system
performance.
Non-pre-emptive CPU scheduling is a method where the CPU is not taken away from a
process until it has completed its execution or has voluntarily released the CPU. This means
that a higher-priority process must wait for a lower-priority process to complete before it can
start executing. The main advantage of non-pre-emptive scheduling is that it can lead to
more predictable performance, since lower-priority processes are guaranteed to complete
their execution before higher-priority processes are allowed to start.
CPU Scheduling Terminologies
Arrival Time : It is the time at which the process enters in the ready state.
Burst Time/Execution time/Running Time : It is the time required by each process to run on
CPU & complete its execution.
Completion Time/Exit time : It is the time when a process complete its execution and exit
from the system.
Waiting Time [WT = TAT-BT] : When the process is ready for the execution and waiting for the
CPU in ready state.
Turn Around Time [CT-AT]: It is the total time spend by the process in a system.

Non Preemptive Preemptive

When a process complete its execution. If a process enter into ready state either
Process leaves CPU voluntarily to perform from new or waiting state and it is high
some I/O operation or to wait for an event . priority process.
FCFS (first comes first serve) SRTF (shortest remaining time first)
SJF (shortest job first) LRTF (longest remaining time first)
LJF (largest job first) Round Robin
HRRN (highest response ratio next) Priority queue.
Multilevel queue.

Page 14
Types of Scheduling Criteria in an Operating System
CPU utilization. We want to keep the CPU as busy as possible. Conceptually, CPU utilisation
can range from 0 to 100 percent. In a real system, it should range from 40 percent (for a
lightly loaded system) to 90 percent (for a heavily loaded system).
Throughput. If the CPU is busy executing processes, then work is being done. One measure
of work is the number of processes that are completed per time unit, called throughput.
Turnaround time. It determines how long it takes to execute that process. The interval from
the time of submission of a process to the time of completion is the turnaround time.
Waiting time. It affects only the amount of time that a process spends waiting in the ready
queue.
Response time. A process can produce some output fairly early and can continue
computing new results while previous results are being output to the user. It is the time it
take start responding.

Scheduling Algorithms
CPU scheduling deals with the problem of deciding which of the processes in the ready queue
is to be allocated the CPU. There are many different CPU-scheduling
algorithms.

First come first serve(FCFS)

Q1 Process AT BT CT TAT = CT - AT WT = TAT-BT

A 3 4 7 7-3=4 4-4=0

B 5 3 13 13 - 5 = 8 8-3=5

C 0 2 2 2-0=2 2-2=0

D 5 1 14 14 - 5 = 9 9-1=8

E 4 3 10 10 - 4 = 6 6-3=3

AVGwt = (5+8+3)/5
Gantt Chart C A E B D = 16/5 = 3.2

0 2 3 7 10 13 14

Q2
Process AT BT CT TAT = CT - AT WT = TAT-BT

P1 0 2 2 2–0=2 2–2=0

P2 3 1 4 4–3=1 1–1=0

P3 5 6 11 11- 5 = 6 6–6=0

AVGwt = 0

Page 15
 Q3 Process AT BT CT TAT = CT - AT WT = TAT-BT

P1 0 2 2 2–0=2 2–2=0

P2 1 2 4 4–1=3 3–2=1

P3 5 3 8 8- 5 = 3 3–3=0

P4 6 4 12 12 - 6 = 6 6-4=2

Gantt Chart AVGwt = (0+1+0+2)/4

P1 P2 P3 P4 = 3/4 = 0.75

0 2 4 5 8 12

Q4 Process AT BT CT TAT = CT - AT WT = TAT-BT

P0 2 4 9 9–2=7 7–4=3

P1 1 2 5 5–1=4 4–2=2

P2 0 3 3 3 -0=3 3–3=0

P3 4 2 12 12 - 4 = 8 8-2=6

P4 3 1 10 10 - 3 = 7 7-1=6

Gantt Chart AVGwt = (3+2+0+6+6)/5

P2 P1 P0 P4 P4 = 17/5 = 3.4

0 3 5 9 10 12

Q5 Process AT BT CT TAT = CT - AT WT = TAT-BT

P0 0 3 3 3–0=3 3–3=0

P1 2 2 5 5–2=3 3–2=1

P2 6 4 10 10 - 6 = 4 4–4 =0

Gantt Chart P0 P1 P3 AVGwt = (1+0+0)/3

= 1/3 = 0.33
0 3 5 6 10

Q6 Process AT BT CT TAT = CT - AT WT = TAT-BT

P1 0 24 24 24 – 0 = 24 24 – 24 = 0
AVGwt = (0+23+25)/3
P2 1 3 27 27 – 1 = 26 26 – 3 = 23 = 48/3 = 16

P3 2 4 31 31- 2 = 29 29 – 4 = 25

Gantt Chart P1 P2 P3

0 24 27 31
The convoy effect in FCFS scheduling occurs when a long-running CPU-bound process occupies
the CPU for an extended period. As a result, shorter processes that arrive after the long-running
process but are ready to run must wait for the CPU to become available and many shorter
processes are forced to wait for the long-running process to complete. Page 16
Shortest job first(SJF)
In this approach out of all the available processes, CPU is assign to the process which have the
shortest burst time. If their is a tie between the two process, FCFS is used to break it. Shortest
job first can be either preemptive or non-preemptive. Preemption mode of shortest job first is
called shortest remaining time first(SRTF). SRTF is guarantees the minimal waiting time.

Non Preemptive Process AT BT CT TAT = CT - AT WT = TAT-BT

P1 3 1 7 7-3=4 4-1=3

P2 1 4 16 16 - 1 = 15 15 - 4 = 11

P3 4 2 9 9- 4 = 5 5- 2 = 3

P4 0 6 6 6-0=6 6- 6 = 0 AVGwt = (3+11+3+0+7)/5

P5 2 3 12 12 - 2 = 10 10 - 3 = 7 = 24/5 = 4.8

P4 P1 P3 P5 P2

0 6 7 9 12 16

Preemptive Process AT BT CT TAT = CT - AT WT = TAT-BT

P1 3 1 7 4-3=1 1-1=0

P2 1 4 3 2 16 6-1=5 5-4=1 AVGwt = (0+1+2+10+6)/5

= 19/5 = 3.8
P3 4 2 9 8- 4 = 4 4-2=2

P4 0 6 5 6 16 - 0 = 16 16- 6 = 10

P5 2 3 12 11 - 2 = 9 9-3=6

P4 P2 P2 P1 P2 P3 P5 P4

0 1 2 3 4 6 8 11 16

Process Arrival
Burst time CT TAT = CT - AT WT = TAT-BT
Id time

P1 0 7 6 19 19 – 0 = 19 19 – 7 = 12

P2 1 5 4 13 13 – 1 = 12 12 – 5 = 7

P3 2 3 2 6 6–2=4 4–3=1

P4 3 1 4 4–3=1 1–1=0

P5 4 2 9 9–4=5 5–2=3

P6 5 1 7 7–5=2 2–1=1

Average waiting time = (12 + 7 + 1 + 0 + 3 + 1) / 6 = 24 / 6 = 4 unit

Page 17
 PID AT BT CT TAT = CT - AT WT = TAT-BT

P1 0 9 13 13 – 0 = 13 13 – 9 = 4

AvgWT = (4 + 0 + 11) / 3
P2 1 4 5 5–1=4 4–4=0 = 15 / 3 = 5 unit

P3 2 9 22 22- 2 = 20 20 – 9 = 11

Advantages-
SRTF is optimal and guarantees the minimum average waiting time.
It provides a standard for other algorithms since no other algorithm performs better than it.

Disadvantages-
It can not be implemented practically since burst time of the processes can not be known
in advance.
It leads to starvation for processes with larger burst time.
Priorities can not be set for the processes.
Processes with larger burst time have poor response time.

Priority Scheduling
A priority is associated with each process, and the CPU is allocated to the process with the
highest priority. Equal-priority processes are scheduled in FCFS order. An SJF algorithm is
simply a priority algorithm where the priority is, the larger the CPU burst, the lower the
priority, and vice versa. Priority scheduling can be either preemptive or non preemptive.
When a process arrives at the ready queue, its priority is compared with the priority of the
currently running process.
A preemptive priority scheduling algorithm will preempt the CPU if the priority of the
newly arrived process is higher than the priority of the currently running process.
A non preemptive priority scheduling algorithm will simply put the new process at the
head of the ready queue.

Non preemptive Process AT BT Priority CT TAT = CT - AT WT = TAT-BT

P1 0 4 2 4 4–0=4 4–4=0

P2 1 3 3 15 15 – 1 = 14 14 – 3 = 11

P3 2 1 4 12 12 – 2 = 10 10 – 1 = 9

P4 3 5 5 9 9–3=6 6–5=1

P5 4 2 5 11 11 – 4 = 7 7–2=5

Average waiting time = (0 + 11 + 9 + 1 + 5) / 5 = 26 / 5 = 5.2 unit Page 18

Preemptive
Process AT BT Priority CT TAT = CT - AT WT = TAT-BT

P1 0 4 3 2 15 15 – 0 = 15 15 – 4 = 11

P2 1 3 2 3 12 12 – 1 = 11 11 – 3 = 8

P3 2 1 4 3 3–2=1 1–1=0

P4 3 5 5 8 8–3=5 5–5=0

P5 4 2 5 10 10 – 4 = 6 6–2=4

Average waiting time = (11 + 8 + 0 + 0 + 4) / 5 = 23 / 5 = 4.6 unit

Round Robin Scheduling

The round-robin (RR) scheduling algorithm is designed especially for time sharing systems.
It is similar to FCFS scheduling, but pre-emption is added to enable the system to switch
between processes. A small unit of time, called a time quantum or time slice, is defined to
which a process can hold the CPU in one go with in which either process terminates or
process release the CPU and return in the circular queue and wait for the next chance.

Time Quantum = 2 Process AT BT CT TAT = CT - AT WT = TAT-BT

P1 0 5 3 1 13 13 – 0 = 13 13 – 5 = 8

P2 1 3 1 12 12 – 1 = 11 11 – 3 = 8

P3 2 1 5 5–2=3 3–1=2

P4 3 2 9 9–3=6 6–2=4

P5 4 3 1 14 14 – 4 = 10 10 – 3 = 7

Ready/Circular Queue P1, P2, P3, P1, P4, P5, P2,P1, P5

Average waiting time = (8 + 8 + 2 + 4 + 7) / 5 = 29 / 5 = 5.8 unit

CT - AT TAT - BT

Ready queue Average waiting time

= (7 + 6 + 2 + 4 ) / 4
Running queue = 19 / 4 = 4.75 unit
Page 19
Advantages
It doesn’t face the issues of starvation or convoy effect.
All the jobs get a fair allocation of CPU.
It deals with all processes without any priority.
Disadvantages
This method spends more time on context switching.
Process with large burst time, have to wait more.
Multi level queue scheduling
In the computer system, so many types of processes are running, like system process,
interactive process & batch process and every process need different scheduling algorithm
and different queue. Multilevel queue scheduling is one such CPU scheduling algorithm
where the tasks to be performed by the CPU are divided into different groups based on
various properties. Multilevel queue scheduling algorithm partitions the ready queue into
several separate queues. The processes are permanently assigned to one queue, generally
based on some property of the process, such as memory size, process priority, or process
type.
Each queue has its own scheduling algorithm.
Each queue gets a certain portion of the CPU time, which it can then schedule among its
various processes.
No process can change its queue once assigned.
All the queues followed the fixed priority scheduling algorithm.
All the process must be executed as per the priorities.
This algorithm suffers from the problem of starvation.

Multi level feedback queue scheduling

In multilevel queue scheduling algorithm, processes are permanently assigned to a queue
when they enter the system because their are separate queues for foreground and
background processes, processes do not move from one queue to the other, since
processes do not change their foreground or background nature.

Page 20
 Multilevel feedback queue scheduling algorithm, allows a process to move between queues.
The method used to determine when to upgrade a process to a higher priority queue and
when to demote a process to a lower priority queue.
This algorithm help solve the problem of starvation.
NOTE : Starvation is a problem of resource management where in the OS, the process does
not have resources because it is being used by other processes.
It is a problem when the low-priority process wait for a long duration of time because of high-
priority requests being executed.
DEADLOCK
In a multi programming , several processes may compete for a finite number of resources. A
process requests resources; if the resources are not available at that time, the process
enters a waiting state. Sometimes, a waiting process is never again able to change state,
because the resources it has requested are held by other waiting processes. This situation is
called a deadlock.
System model R2
Request : Every process will requested for resources.
Use : If entertained then, process will use the resources. P1 P2
Release : Process must release the resources after use.

Deadlock Characterisation/Necessary Condition for deadlock R1

A deadlock situation can arise if the following four
Resource Allocation
conditions hold simultaneously in a system Graph
Mutual Exclusion. At least one resource must be held in a non-shareable mode, 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.
Hold and wait. A process must be holding at least one resource and waiting to acquire
additional resources that are currently being held by other processes.
No preemption. Resources cannot be preempted; that is, a resource can be released only
voluntarily by the process holding it, after that process has completed its task.
Circular wait. Every process must be waiting for a resources which is being held by another
process, which in turn waiting for the first process to release the resources.
P1 P2 P3

Deadlock handling method

Prevention : Designing a system which violate at least one of four necessary condition of
deadlock and ensure independence from deadlock.
Avoidance : system maintain a set of data using which it takes a decision whether to entertain a
new request or not, for be in safe state.
Detection and recovery : Here we wait until deadlock occur, once we detect it we recover from
it.
Deadlock ignorance (ostrich method): ignore the problem as, problem is not exist.
Why we are ignore deadlock and not to create any algorithm to solve ?
because deadlock occurs very rare then why we write full fledge complex code. It degrade the
performance of operating system as operation system is already doing very complex
operations (memory management & resources management).
Page 21
Deadlock Prevention
Each of the four necessary conditions is required, for the system in a deadlock state, by
ensuring that at least one of these conditions cannot hold, we can prevent the occurrence
of a deadlock.
Mutual Exclusion: At least one of the resources must be in shareable mode. Shareable
resources, in contrast, do not require mutually exclusive access and thus cannot be involved
in a deadlock. We cannot prevent deadlocks by denying the mutual-exclusion condition,
because some resources are non-sharable.
e.g. Read-only files are a good example of a sharable resource. If several processes attempt
to open a read-only file at the same time, they can be granted simultaneous access to the
file.
Hold and Wait:
The process is allowed to start execution if and only if it has acquired all the resources
(less efficient, not implementable, easy, deadlock dependence)
The process will acquire only desired resources but before making any fresh request it
must release all the resource that it currently hold.(efficient, implementable).
A maximum time limit set, up to which a process can wait after that the process must
release all the hold resources.
No Preemption: If a process is holding some resources and requests another resource that
cannot be immediately allocated to it (that is, the process must wait), then all resources the
process is currently holding are preempted.
If a process requests some resources, they are available allocate them. If not check
whether resources are allocated to some other process that is waiting for additional
resources. we preempt the desired resources from the waiting process and allocate them
to the requesting process.
This method may be used high priority process or system process. Process to forcefully
preempt the resources holding by other process.
Circular Wait:
The circular wait can be eliminated by first giving a natural number of every resource.
F:N R, where N is set of natural number.
Each process are only allowed to request the resources either only in increasing/
decreasing order of the resource number.
If these two protocols are used, then the circular-wait condition cannot hold.

P1 P2 P1 P2 R1 R2

R1 R1 R1 R2

R2 R2 R2 R1 P1 P2

If a process request for the in between resources, then it must release all the
resources hold from the resources number in between requested.
NOTE : Prevention is very restrictive approach to handle the deadlock, although it
guarantees that system will never come under dead lock, but it is very expensive.

Page 22
Problem with Prevention
Prevention approach, prevent the deadlock by limiting how requests can be made. The limits
ensure that at least one of the necessary conditions for deadlock cannot occur. Possible side
effects of preventing deadlocks by this method, however, are low device utilization and
reduced system throughput.
Deadlock Avoidance
In Deadlock avoidance, we require additional information about how resources are to be
requested. With this knowledge of the complete sequence of requests and releases for each
process, the system can decide for each request whether or not the process should wait in
order to avoid a possible future deadlock.
In order to avoid the deadlock in runtime, system try to maintain some books like a banker,
whenever someone ask for a loan(resource), it is granted only when the books is allowed.

Total A=10, B=5, C=7

P2
2 0 0
P4
2 1 1

P5
0 0 2

0 1 0 P1

P3
7 2 5 10 5 7

Total A=3, B=14, C=12, D = 12

Process Allocation Max Need Available Remaining Need

P0
Id A B C D A B C D A B C D A B C D

P0 0 0 1 2 0 0 1 2 1 5 2 0 0 0 0 0 P2
0 0 1 2
P1 1 0 0 0 1 7 5 0 1 5 3 2 0 7 5 0
1 3 5 4 P3
P2 1 3 5 4 2 3 5 6 2 8 8 6 1 0 0 2
0 6 3 2
P4
P3 0 6 3 2 0 6 5 2 2 14 11 8 0 0 2 0
0 0 1 4
P4 0 0 1 4 0 6 5 6 2 14 12 12 0 6 4 2 P1
1 0 0 0
2 9 10 12 3 14 12 12

Safe sequence
A state of the system is called safe if the system can allocate all the resources requested by
all the processes without entering into deadlock. If the system cannot fulfill the request of all
processes then the state of the system is called unsafe.
Available. It indicates the number of available resources of each type.
Max. It defines the maximum number of resources demand of each process.
Allocation. It defines the number of resources of each type currently allocated to each
process.
Need. It indicates the remaining resource need of each process to complete its task.
Page 23
Deadlock Detection
Deadlock detection is a technique used in operating systems to identify and resolve situations
where multiple processes are blocked and unable to continue executing because they are
waiting for each other to release resources. A deadlock can occur when two or more processes
are waiting for resources that are being held by each other, resulting in a circular dependency.
Resource-allocation graph
It is one of the simplest way to represent the state of the system like how the resources are
allocated to the process and how process have been assigned the multiple resources. It can be
used to visualise the resources being used by different processes.
Vertex
Vertex

Process Rsource Assigned Request

Vertex Vertex
P P
single multiple
instance instance R R

Single instance Resource-allocation graph

When all the resources available in the system of single instance is called Single instance
resource-allocation graphs.
eg. CPU R1

R1 , R2
Availability = (0 0)
P1 P2
current need (1 1)
Deadlock found

R2

Multi instance Resource-allocation graph

When the resources available in the system of multiple instance is called multiple instance
resource-allocation graphs.
eg. register, stack
R1 Process Allocation Request
Id R1 R2 R1 R2

P1 1 0 0 1
P1 P2
P2 0 1 1 0

P3 P3 0 1 0 0

R2

If every resource have only one resource instance in resource allocation graph, then
detection of graph is necessary and sufficient condition for deadlock detection.
If any resource have the multiple copy of the instance in resource allocation graph then
cycle is necessary but not sufficient condition for deadlock.

Page 24
 MEMORY MANAGEMENT
Memory management is an important aspect of an operating system that is responsible for
managing the primary memory of a computer system. The main goal of memory management is
to allocate and deallocate memory resources to different processes in a way that maximizes
the utilization of available memory while ensuring that each process has enough memory to
execute its tasks.

Main
CPU memory

Note. Functionalities of any computer depend upon both CPU and memory.
There are several key functions involved in memory management in an operating system,
including:
Memory Allocation: The process of assigning a section of memory to a process or program.
The operating system must keep track of which parts of memory are currently in use and
which are available for allocation.
Memory De-allocation: The process of releasing memory that is no longer required by a
process or program. The operating system must ensure that memory is properly deallocated
to prevent memory leaks or fragmentation.
Memory Protection: The process of preventing one process from accessing the memory of
another process. This is important for security and stability reasons.
Virtual Memory Management: The process of managing the allocation of virtual memory,
which is a technique that allows a computer to use more memory than it physically has
available. Virtual memory management involves the use of paging and swapping to move
data between physical memory and disk.
Criteria for the memory
1. Size 2. Access time 3. Per unit cost

These properties are contradict to each other. We cannot have the less access time with large search
space we can’t have the large memory size with low cost.

Hierarchy of memory

MAIN SECONDARY
CPU
MEMEORY MEMEORY

Explanation : When the program executes, it execute sequentially, e.g if instruction number n is
currently executing, then it is the probability that next instruction will be n+1. So, the next instruction
which is about to execute will be fetched and store into main memory. So, when we access the
memory most of the time we get data into the main memory. This will help to meet all the desired
criteria for memory.
How the process comes from secondary memory to primary memory? What are the policies?
How the address translation occur, as CPU generate logical address, and to access main memory we
need physical address?
Page 25
 Memory management technique

contiguous Non contiguous

paging
multilevel paging
Fixed Variable inverted paging
paritioning partioning segmentation
(static) (dynamic) segment paging

Contigous
Contiguous memory allocation is a technique used by operating systems to allocate and
manage memory. When the allocation of the process in main memory in contiguous fashion.

Contiguous memory allocation

Advantages of Contiguous Memory Allocation:

Efficiency: Contiguous memory allocation is a very efficient technique because the CPU can
access memory blocks very quickly, as they are stored in contiguous addresses.
Simplicity: This technique is simple and easy to implement. It is also easy to manage and can
be easily understood by both the developers and the users.
Low overhead: This technique requires a low overhead because it only needs to keep track of
the start and end addresses of the allocated memory block.
Speed: The CPU can access data in contiguous memory blocks very quickly, which results in
faster data access and processing.
10KB

4KB 2KB 4KB

If a new process of size 5KB arrive, it can not be occupied as space is not available in contiguous
fashion, called external fragmentation.
Disadvantages of Contiguous Memory Allocation:
External fragmentation: External fragmentation can occur when the total free memory space
is sufficient to satisfy a memory request, but the available memory is divided into small non-
contiguous blocks that are unusable by the requesting process.
Fixed partitioning (static)
In this technique, the memory is divided into fixed size block, each block may have same
or different size and the process is allocated to the fixed size block.
For every process, the entire memory block will be allocated
10KB

3KB
4KB 2KB 4KB

Suppose the process size 3KB is allocated to fixed size memory block, then 1KB of memory
can not be used again, this is called internal fragmentation Page 26
Variable partitioning (dynamic)
In the variable size partitioning technique, whenever the process is coming into RAM, then only the space
is allocating for the process, it helps to remove internal fragmentation.
10KB

4KB
4KB 6KB
Allocation method in contiguous memory management(variable partitioning)
First fit : Allocate the first hole that is big enough. Searching can start either at the beginning of
the set of holes or at the location where the previous first-fit search ended. We can stop
searching as soon as we find a free hole that is large enough
Best fit: Allocate the smallest hole that is big enough. We must search the entire list, unless
the list is ordered by size. This strategy produces the smallest leftover hole.
Worst fit : Allocate the largest hole. We must search the entire list. This strategy produces the
largest leftover hole, which may be more useful than the smaller leftover hole from a best-fit
approach.

The sequence of requests for blocks of size

Process P1 = 300 units
Process P2 = 25 units
Process P3 = 125 units
Process P4 = 50 units
First fit

Best fit

25

P2 50
125 300
P1
Worst fit P3
P2

As in the variable size partitioning, we can use the leftover space.

In variable size partitioning best fit perform worst and worst fit perform best.
Best fit try to search the space with minimum internal fragmentation, the leftover space is
very less we can not use this again.
Allocation method in contiguous memory management(fixed size)
In the fixed size partitioning, we can not use the leftover space.
Leads to the problem of internal fragmentation
If the size of the process is larger than the total available space, here is no external
fragmentation
External fragmentation is not only depend upon the available space, it also depend upon the
size of the process. It is the size of the process which is unable to allocate.
Page 27
P1 = 357 units
P2 = 210 units 200 400 600 500 300 250
P3 = 468 units
P4 = 491 units
200 400 600 500 300 250
First fit P1 357 43 P2 210 390 P3 468 32

External fragmentation = 491 Internal fragmentation = 465

200 400 600 500 300 250

Best fit P1 357 43 P4 491 109 P3 468 32 P2 210 40

External fragmentation = 0 Internal fragmentation = 224

200 400 600 500 300 250

Worst fit P1 357 243 P2 210 290

External fragmentation = 959 Internal fragmentation = 533

NOTE
External fragmentation occur due to contiguous memory allocation.
Internal fragmentation occur due to fixed size partitioning policy

Address Translation
The process of converting the logical address generated by CPU into physical to access the
main memory, is called address translation. CPU generate logical address and to access the
data available in main memory we need physical address, this translation of address is called
address translation.
SM

i0
i1
i2
i3
i4
i5
.
n.99

The relocation register contains the value of the smallest physical address, or we can say
that it holds the base address of the instruction available in main memory.
The limit register contains the range of logical addresses or we can say that it holds the size of
the process.

Page 28