Unit – II Operating Systems

1. THE PROCESS CONCEPT

A. The Process:
A process is a program in execution. A process is more than the program code, which is
sometimes known as the text section. It also includes the current activity, as represented by the
value of the program counter and the contents of the processor's registers. A process generally
also includes the process stack, which contains temporary data (such as function parameters, return
addresses, and local variables), and a data section, which contains global variables. A process may
also include a heap, which is memory that is dynamically allocated during process run time. The
structure of a process in memory is shown in Figure.

Figure: A process in memory

B. Process State:
As a process executes, it changes state. The state of a process is defined in part by the
current activity of that process. Each process may be in one of the following states:
• New: The process is being created.
• Running: Instructions are being executed.
• Waiting: The process is waiting for some event to occur.
• Ready: The process is waiting to be assigned to a processor.
• Terminated: The process has finished execution.

Figure: Process States

1|P ag e
Unit – II Operating Systems

C. Process Control Block:

Each process is represented in the operating system by a process control block (PCB)—
also called a task control block. A PCB is shown in Figure.

It contains many pieces of information associated with a specific process, including these:
Process state: The state may be new, ready, running, waiting, halting, and so on.
Program counter: The counter indicates the address of the next instruction to be executed for
this process.
CPU registers: The registers vary in number and type, depending on the computer architecture.
They include accumulators, index registers, stack pointers, and general-purpose registers, plus
any condition-code information. Along with the program counter, this state information must be
saved when an interrupt occurs, to allow the process to be continued correctly afterward
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 information as the
value of the base and limit registers, the page tables, or the segment tables, depending on the
memory system used by the operating system.
Accounting information: This information includes the amount of CPU and real time used,
time limits, account numbers, job or process numbers, and so on.
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.

2|P ag e
Unit – II Operating Systems

2. PROCESS SCHEDULING
A. Scheduling Queues:
A new process is initially put in the ready queue. It waits there until it is selected for
execution, or is dispatched. Once the process is allocated the CPU and is executing, one of several
events could occur:
• The process could issue an I/O request and then be placed in an I/O queue.
• The process could create a new sub process and wait for the sub process's termination.
• The process could be removed forcibly from the CPU, as a result of an interrupt, and be
put back in the ready queue.
the first two cases, the process eventually switches from the waiting state to the ready state
and is then put back in the ready queue. A process continues this cycle until it terminates, at which
time it is removed from all queues and has its PCB and resources de allocated.

Figure: Queing-diagram representation of process scheduling.

B. Schedulers:
Schedulers are special system software’s which handles process scheduling in various ways.
Their main task is to select the jobs to be submitted into the system and to decide which process to
run. Schedulers are of three types
 Long Term Scheduler
 Short Term Scheduler
 Medium Term Scheduler

Figure: Process state transition diagram with schedulers.

3|P ag e
 Unit – II Operating Systems

i. Long Term Scheduler: It is also called job scheduler. Long term scheduler determines which
programs are admitted to the system for processing. Job scheduler selects processes from the queue
and loads them into memory for execution. Process loads into the memory for CPU scheduling. The
primary objective of the job scheduler is to provide a balanced mix of jobs, such as I/O bound and
processor bound. It also controls the degree of multiprogramming. If the degree of
multiprogramming is stable, then the average rate of process creation must be equal to the average
departure rate of processes leaving the system On some systems, the long term scheduler may not
be available or minimal. Time-sharing operating systems have no long term scheduler. When
process changes the state from new to ready, then there is use of long term scheduler.
ii. Short Term Scheduler: It is also called CPU scheduler. Main objective is increasing system
performance in accordance with the chosen set of criteria. It is the change of ready state to running
state of the process. CPU scheduler selects process among the processes that are ready to execute
and allocates C
iii. PU to one of them.
Short term scheduler also known as dispatcher, execute most frequently and makes the fine
grained decision of which process to execute next. Short term scheduler is faster than long term
scheduler.
iv. Medium Term Scheduler: Medium term scheduling is part of the swapping. It removes the
processes from the memory. It reduces the degree of multiprogramming. The medium term
scheduler is in-charge of handling the swapped out-processes.

Figure: Medium term sceduler in queing diagram.

Running process may become suspended if it makes an I/O request. Suspended processes
cannot make any progress towards completion. In this condition, to remove the process from
memory and make space for other process, the suspended process is moved to the secondary
storage. This process is called swapping, and the process is said to be swapped out or rolled out.
Swapping may be necessary to improve the process mix.
Comparison between Scheduler
S.N. Long Term Scheduler Short Term Scheduler Medium Term Scheduler
It is a process swapping
1 It is a job scheduler It is a CPU scheduler
scheduler.
Speed is lesser than short term Speed is fastest among Speed is in between both short
2
scheduler other two and long term scheduler.
It provides lesser control
It controls the degree of It reduces the degree of
3 over degree of
multiprogramming multiprogramming.
multiprogramming
It is almost absent or minimal It is also minimal in time It is a part of Time sharing
4
in time sharing system sharing system systems.
It selects processes from pool It selects those processes It can re-introduce the process
5 and loads them into memory which are ready to into memory and execution
for execution execute can be continued.

4|P ag e
Unit – II Operating Systems

C. Context Switch:
Switching the CPU to another process requires performing a state save of the current
process and a state restore of a different process. This task is known as a context switch.
The context is represented in the PCB of the process. It includes the value of the CPU
registers, the process state and memory-management information. Generically, we perform a state
save of the current state of the CPU, be it in kernel or user mode, and then a state restore to resume
operations.
Context-switch time is pure overhead, because the system does no useful work while
switching. Switching speed varies from machine to machine, depending on the memory speed, the
number of registers that must be copied, and the existence of special instructions (such as a single
instruction to load or store all registers).
Context-switch times are highly dependent on hardware support.
Dispatcher: Another component involved in the CPU-Scheduling function is Dispatcher. The
dispatcher is the module that gives control of the CPU to the process selected by short-term
scheduler. This function involves the following:
1. Switching context
2. Switching to user mode
3. Jumping to the proper location in the user program to restart that program.
Dispatch latency – time it takes for the dispatcher to stop one process and start another running.
3. OPERATIONS ON PROCESSES
A. Process Creation:
A process may create several new processes, via a create-process system call, during the
course of execution. The creating process is called a parent process, and the new processes are
called the children of that process. Each of these new processes may in turn create other processes,
forming a tree of processes.
Most operating systems identify processes according to a unique process identifier (or Pid),
which is typically an integer number.
Figure illustrates a typical process tree for the Linux operating system, showing the name of
each process and its pid. (We use the term process rather loosely, as Linux prefers the term task
instead.) The init process (which always has a pid of 1) serves as the root parent process for all user
processes. Once the system has booted, the init process can also create various user processes, such
as a web or print server, an ssh server, and the like. In Figure 3.8, we see two children of init—
kthreadd and sshd. The kthreadd process is responsible for creating additional processes that
perform tasks on behalf of the kernel (in this situation, khelper and pdflush). The sshd process is
responsible for managing clients that connect to the system by using ssh (which is short for secure
shell). The login process is responsible for managing clients that directly log onto the system. In
this example, a client has logged on and is using the bash shell, which has been assigned pid 8416.
Using the bash command

Figure: A Tree of processes on a typical Linux system

5|P ag e
Unit – II Operating Systems

When a process creates a new process, two possibilities exist in terms of execution:
1. The parent continues to execute concurrently with its children.
2. The parent waits until some or all of its children have terminated.
There are also two possibilities in terms of the address space of the new process:
1. The child process is a duplicate of the parent process (it has the same program and data as
the parent).
2. The child process has a new program loaded into it.
To illustrate these differences, let's first consider the UNIX operating system. In UNIX, as
we've seen, each process is identified by its process identifier, which is a unique integer. A new
process is created by the fork ( ) system call. The new process consists of a copy of the address
space of the original process. This mechanism allows the parent process to communicate easily
with its child process. Both processes (the parent and the child) continue execution at the
instruction after the fork(), with one difference: The return code for the for() is zero for the new
(child) process, whereas the (nonzero) process identifier of the child is returned to the parent.
#include <sys/types.h>
#include <stdio.h>
#include <unistd.h>
int main()
{
pid-t pid;
/* fork a child process */
pid = fork();
if (pid < 0) {/* error occurred */
fprintf(stderr, "Fork Failed");
exit (-1) ;
}
else if (pid == 0} {/* child process */
execlpf"/bin/Is","Is",NULL);
}
else {/* parent process */
/* parent will wait for the child to complete */
wait(NULL);
printf("Child Complete");
exit (0) ;
}}
Program: Creating a separate process using the UNIX fork() system call.

Figure: Process creation using the fork() system call.

B. Process Termination:
A process terminates when it finishes executing its final statement and asks the operating
system to delete it by using the exit () system call. A parent may terminate the execution of one of
its children for a variety of reasons, such as these:

6|P ag e
Unit – II Operating Systems

1. The child has exceeded its usage of some of the resources that it has been allocated. (To
determine whether this has occurred, the parent must have a mechanism to inspect the
state of its children.)
2. The task assigned to the child is no longer required.
3. The parent is exiting, and the operating system does not allow a child to continue if its
parent terminates.
In such systems, if a process terminates (either normally or abnormally), then all its children
must also be terminated. This phenomenon, referred to as cascading termination, is normally
initiated by the operating system.

4. INTER PROCESS COMMUNICATION

An independent process is one that cannot affect or be affected by the execution of another
process
A cooperating process can affect or be affected by the execution of another process in the
system
Advantages of process cooperation:
1. Information sharing (of the same piece of data)
2. Computation speed-up (break a task into smaller subtasks)
3. Modularity (dividing up the system functions)
4. Convenience (to do multiple tasks simultaneously)
Two fundamental models of Interprocess communication
1. Shared memory (a region of memory is shared)
2. Message passing (exchange of messages between processes)

Figure Communication models: (a) Message Passing. (b) Shared Memory

A. Shared Memory Systems:
Interprocess communication using shared memory requires communicating processes to
establish a region of shared memory. Typically, a shared-memory region resides in the address
space of the process creating the shared-memory segment.
A producer process produces information that is consumed by a consumer process.
One solution to the producer–consumer problem uses shared memory.
Two types of buffers can be used. The unbounded buffer places no practical limit on the size of the
buffer. The consumer may have to wait for new items, but the producer can always produce new
items. The bounded buffer assumes a fixed buffer size. In this case, the consumer must wait if the
buffer is empty, and the producer must wait if the buffer is full.

7|P ag e
Unit – II Operating Systems

#define BUFFER SIZE 10

typedef struct {
...
}item;
item buffer[BUFFER SIZE];
int in = 0;
int out = 0;
Producer Process:
while (true) {
/* produce an item in next produced */
while (((in + 1) % BUFFER SIZE) == out)
; /* do nothing */
buffer[in] = next produced;
in = (in + 1) % BUFFER SIZE;
}
Consumer Process:
item next consumed;
while (true) {
while (in == out)
; /* do nothing */
next consumed = buffer[out];
out = (out + 1) % BUFFER SIZE;
/* consume the item in next consumed */
}
B. Message Passing Systems:
 Mechanism to allow processes to communicate and to synchronize their actions
 No address space needs to be shared; this is particularly useful in a distributed processing
environment (e.g., a chat program)
 Message-passing facility provides two operations:
o send(message) – message size can be fixed or variable
o receive(message)
 If P and Q wish to communicate, they need to:
o establish a communication link between them
o exchange messages via send/receive
 Logical implementation of communication link
o Direct or indirect communication
o Synchronous or asynchronous communication
o Automatic or explicit buffering
1) Direct Communication:
Processes must name each other explicitly:
send (P, message) – send a message to process P
receive(Q, message) – receive a message from process Q
Properties of communication link:
 Links are established automatically between every pair of processes that want to
communicate
 A link is associated with exactly one pair of communicating processes
 Between each pair there exists exactly one link
 The link may be unidirectional, but is usually bi-directional
Disadvantages
 Limited modularity of the resulting process definitions
 Hard-coding of identifiers are less desirable than indirection techniques

8|P ag e
Unit – II Operating Systems

2. Indirect Communication:
Messages are directed and received from mailboxes (also referred to as ports)
 Each mailbox has a unique id
 Processes can communicate only if they share a mailbox
o send(A, message) – send message to mailbox A
o receive(A, message) – receive message from mailbox A
Properties of communication link
 Link is established between a pair of processes only if both have a shared mailbox
 A link may be associated with more than two processes
 Between each pair of processes, there may be many different links, with each link
corresponding to one mailbox
For a shared mailbox, messages are received based on the following methods:
 Allow a link to be associated with at most two processes
 Allow at most one process at a time to execute a receive() operation
 Allow the system to select arbitrarily which process will receive the message (e.g., a round
robin approach)
Mechanisms provided by the operating system
 Create a new mailbox
 Send and receive messages through the mailbox
 Destroy a mailbox
Synchronization:
 Message passing may be either blocking or non-blocking
 Blocking is considered synchronous
 Blocking send has the sender block until the message is received
 Blocking receive has the receiver block until a message is available
 Non-blocking is considered asynchronous
 Non-blocking send has the sender send the message and continue
 Non-blocking receive has the receiver receive a valid message or null
 When both send() and receive() are blocking, we have a rendezvous between the sender and
the receiver
Buffering:
Whether communication is direct or indirect, messages exchanged by communicating processes
reside in a temporary queue
These queues can be implemented in three ways:
1. Zero capacity – the queue has a maximum length of zero - Sender must block until the
recipient receives the message
2. Bounded capacity – the queue has a finite length of n - Sender must wait if queue is full
3. Unbounded capacity – the queue length is unlimited Sender never blocks

5. THREADS
A thread is a light weight process. It comprises a thread ID, a program counter, a register
set, and a stack. It shares with other threads belonging to the same process its code section, and
other operating-system resources such as open files and signals. For e.g, Windows-XP and Solaris
kernels are multithreaded.
A. Benefits:
 Resource Sharing: Threads share memory and resources of the process to which they
belong.
 Economy: Allocating memory and resources for process creation is costly. Solaris, for
example, creating a process is about thirty times slower than is creating thread, and context
switching is five times slower.

9|P ag e
Unit – II Operating Systems

 Utilization of multiprocessor architecture: Multiple threads can run on multiple

processors parallel. A single threaded process can run only on one CPU.
 Responsive time: Multithreading an interactive application may allow a program to
continue running even if part of it is blocked, thereby increasing responsiveness.
B. Multithreading Models
Threads may be provided either at the user level, for user threads, or by the kernel, for kernel
threads. User threads are supported above the kernel and are managed by without kernel support.
Kernel threads are supported and managed directly by the operating system. All contemporary
operating systems like Solaris, windows-XP, Linux and MAC OS x support kernel threads.
Many-to-One model:
The many-to-one model maps many user-level threads to one kernel thread. Thread
management is done by thread library in user space, so it is efficient; but the entire process will
block if a thread makes a blocking system call. Since, kernel is unaware of user threads, multiple
threads can’t be scheduled on multiple processors. GNU portable threads on UNIX Java threads,
WIN32 threads and Green threads on Solaris are user thread libraries.

One-to-One Model:

Fig: One-to-One Model

The one-to-one Model maps each user thread to 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 allows multiple threads to run in parallel on multiprocessors. The only drawback is creating
a kernel thread correspond to user thread. Creating a kernel thread is an overhead to the application.
Solaris 9, Linux, Windows 95,98, NT, 200 and xp implement one-to-one model.

10 | P a g e
Unit – II Operating Systems

Many-to-Many Model:

Fig: Many-to-Many Model

The many-to-many model multiplexes many user-level threads to small or equal number of
kernel threads. Many-to-one model allows the developer to create as many user threads as she
wishes, true concurrency is not gained because kernel can schedule only one user thread at a time.
The one-to-one model allows for greater concurrency, but a developer has to be careful not to create
too many threads within application. The man-to-many model does not suffers from neither of these
shortcomings: Developers can create as many user threads as necessary, and corresponding kernel
threads can run in parallel on a multi-processor. Also, when a thread performs a blocking system
call, the kernel can schedule another thread for execution. Solaris prior to version 9, windows
NT/2000 with thread fiber package supports many-to-many model.
Two-level-model:
It is a variation of many-to-many model. Two-level model still multiplexes many userlevel
threads to a smaller or equal number of kernel threads but also allows a user-level thread to be
bound to kernel thread. Two-level model is supported by Solaris 8 and earlier.

Fig: Two-level-Model

6. PROCESS SCHEDULING CRITERIA AND ALGORITHMS

Pre-emptive Scheduling:
CPU scheduling decisions may take place when a process:
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates
For situations 1 and 4, a new process must be selected for execution.

11 | P a g e
Unit – II Operating Systems

Non pre-emptive or cooperative scheduling (situation 1 and 4), Once a process is in the
running state, it will continue until it terminates or blocks itself for I/O. This scheduling method
was used by windows 3.x.
Pre-emptive:
 Currently running process may be interrupted and moved to ready state by the OS
 Pre-emption may occur when new process arrives, on an interrupt, or periodically.
 This scheduling method was used by Windows 95, 98, xp and MAC OS x.
Scheduling Criteria:
Scheduling criteria is used to compare different scheduling algorithms.
 CPU Utilization: We want keep the CPU as busy as possible. In real systems, CPU
utilization range from 40 to 90 percent. Every scheduling algorithm tries to maximize the
CPU utilization.
 Throughput: No of processes that are completed their execution per time unit, called
throughput. Throughput depends upon scheduling policy and average length of process.
Every scheduling algorithm tries to maximize the Throughput.
 Turnaround time: This interval from time of submission of a process to the time of
completion is the turnaround time. Scheduling algorithm tries to minimize the turnaround
time.
Turnaround time = waiting time to get into memory + waiting time in ready queue + I/O
time + CPU execution time.
 Waiting time: Waiting time is the sum of the periods spent waiting in the ready queue.
Scheduling algorithm tries to minimize the waiting time.
 Response time: It is the time from the submission of a request until the first response
produced. It is the important criteria for interactive jobs. Scheduling algorithm tries to
minimize the waiting time.
Scheduling Algorithms:
CPU scheduling algorithm decides which of the processes in ready queue is to be allocated
the CPU. There are many CPU scheduling algorithms.
A) First-Come, First-Served Scheduling (FCFS):
In FCFS, the process that requests the CPU first is allocated the CPU first. Each process
joins the ready queue. When the CPU is free, it is allocated to the process at the head of the queue.
The running process is removed from the queue. A short process may have to wait a very long time
before it can execute. In FCFS average waiting time is long. FCFS scheduling algorithm is a no
pre-emptive. It is not suitable for interactive jobs and time sharing systems.
Assume that the following set of processes that arrive at time 0, with length of CPU burst
given in milliseconds:
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt chart for the schedule is:

Process Burst Time Waiting Time Turn Around Time Response Time
P1 24 0 24 0
P2 03 24 27 24
P3 03 27 30 27
Waiting time for P1 = 0; P2 = 24; P3 = 27

12 | P a g e
Unit – II Operating Systems

Average waiting time: (0 + 24 + 27)/3 = 17

Average turn Around Time : (24+27+30) / 3 = 27
Average Response Time : ( 0 + 24 + 27)/3 = 17.
Process Burst Time
P2 3
P3 3
P1 24

Process Burst Time Waiting Time Turn Around Time Response Time
P2 03 0 3 0
P3 03 3 6 3
P1 24 6 30 6

Average waiting time: (0 + 3 + 6)/3 = 3

Average turn Around Time : (3+6+30) / 3 = 13
Average Response Time : ( 0 + 3 + 6)/3 = 3
Convoy effect:
Assume we have one CPU-bound process and many I/O bound processes. The CPU-bound
processes will get and hold the CPU. During this time, all the other processes will finish their I/O
and will move into the ready queue, waiting for the CPU. While the processes wait in ready queue,
the I/O devices are idle. Eventually, the CPU bound process finishes its CPU burst and moves to an
I/O device. All the I/O bound processes, which have short CPU bursts, execute quickly and move
back to I/O queues. At this point, CPU is IDLE. The CPU-bound process will then move back to
ready queue and be allocated the CPU. Again, all the I/O bound processes will end up waiting in
ready queue until the CPU-bound processes is done. This is a CONVOY effect as all the other
processes wait for one big process to get off the CPU.

B) Shortest-job-First Scheduling (SJF):

When CPU is available, it is assigned to the process that has the smallest next CPU burst. If
the next CPU bursts of two processes are same, FCFS scheduling is used to break the tie. The more
appropriate name for this algorithm is Shortest-next-CPU-burst algorithm. It is not suitable for
time-sharing systems and interactive jobs. The longer process may get starvation.
Process Burst Time
P1 6
P2 8
P3 7
P4 3
Process Burst Time Waiting Time Turn Around Time Response Time
P1 6 3 9 3
P2 8 16 24 16
P3 7 9 16 9
P4 3 0 3 0
Average waiting time: (0 + 3 + 9+16)/4 = 7
Average turn Around Time : (9+24+16+3) / 4 = 13
Average Response Time : ( 3+16+9 + 0)/4 = 7

13 | P a g e
Unit – II Operating Systems

The average waiting time is very low. The real difficult with the SJF algorithm is knowing
the length of the next CPU burst. SJF algorithm is frequently used in long term scheduling and it
cannot be implemented at the level of short-term scheduling
The SJF algorithm can be either pre-emptive or non-pre-emptive. The choice arises when a
new process arrives at the ready queue while previous process is still executing. The next CPU
burst of the newly arrived process may be shorter than what is left of the currently executing
process. A pre-emptive SJF algorithm will pre-empt the currently executing process, whereas a
non-pre-emptive SJF algorithm will allow the currently running process to finish its CPU burst.
Process Burst Time(Mille Seconds) Arrival Time
P1 8 0
P2 4 1
P3 9 2
P4 5 3
Burst Waiting Turn Around Response
Process Arrival Time
Time Time Time Time
P1 8 0 9 17 0
P2 4 1 0 4 0
P3 9 2 15 24 15
P4 5 3 2 7 2

Average waiting time: (9+ 0 + 15+2)/4 = 6.5

Average turn Around Time: (9+24+16+3) / 4 = 13
Average Response Time : (3+16+9 + 0)/4 = 7
C. Priority Scheduling:
A priority is associated with each process. And the CPU is allocated to the process with
highest priority. Equal priority processes are scheduled in FCFS order. (An SJF is special case of
priority scheduling. The largest the CPU burst, the lower the priority, and vice versa. In this topic,
we assume that low numbers represent high priority.
Process Burst Time(Milli Seconds) Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2

Burst Waiting Turn Around Response

Process Priori
Time Time Time Time
P1 10 3 6 16 6
P2 1 1 0 1 0
P3 2 4 16 18 16
P4 1 5 18 19 18
P5 5 2 1 6 1

Priorities can be defined internal or externally. Internal priorities are defined based on time
limit, memory requirement, number of opened files. Priority scheduling can be either preemptive or
nonpreemtive. When a process arrives at the ready queue, its priority is compared with priority of
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
nonpreemptive priority scheduling algorithm will simply put the new process at the head of the
ready queue.

14 | P a g e
Unit – II Operating Systems

A major problem with priority scheduling algorithm is INDEFINITE BLOCKING or

STARVATION. A priority scheduling algorithm can leave some low priority processes waiting
indefinitely. A steady stream of high higher-priority processes can prevent low-priority processes
waiting indefinitely. Then the low priority processes get starvation.
A solution to the problem of STARVATION of low priority processes is AGING. Aging is
a technique of gradually increasing the priority of processes that wait in the system for a long time.
For example, increase the priority of a low priority job by 1 for every 15 minutes.

D) Round-Robin Scheduling Algorithm (RR):

The Round-Robin (RR) Scheduling Algorithm is designed especially for time sharing
systems. Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds.
After this time has elapsed, the process is preempted and added to the end of the ready queue.
To implement RR scheduling, we keep the ready queue as FIFO queue of processes. New processes
are added to the tail of the ready queue. The CPU scheduler picks the first process from ready
queue, sets timer to interrupt after 1 time quantum, and dispatches the process.
The process may have a CPU burst of less than 1 time quantum. In this case, the process
itself will release the CPU voluntarily. The scheduler will then proceed to the next process in the
ready queue.
If CPU burst is longer than 1 time quantum, the timer will go off and will cause an interrupt
to OS. A context switch will be executed, and the running process will be put at the tail of the ready
queue. The Round-Robin scheduler selects the next process in the ready queue.
The average waiting time under RR policy is often long. If time quantum increases turnaround time
decreases and response time increases. In general time quantum always should be greater than
context switching time. If time quantum is too long it will become FCFS scheduling algorithm.

Problem 1:
Process Burst Time
P1 24
P2 3
P3 3

Process Burst Time Waiting Time Turn Around Response Time

Time
P1 24 6 30 0
P2 3 4 7 4
P3 3 7 10 7
Assume that all jobs are submitted at the same time and time quantum is 4msec.
The average waiting time is 17/3 = 5.66 milliseconds.
Problem 2:
Process Burst Time
P1 24
P2 3
P3 3
Assume that all jobs are submitted at the same time and time quantum is 2msec.

Process Burst Time Waiting Time Turn Around Response Time

Time
P1 24 6 30 0
P2 3 6 9 2
P3 3 7 10 4
If time slice decreases, the average turnaround time increases and average response time decreases.

15 | P a g e
Unit – II Operating Systems

Problem 3:
Process Burst Time
P1 24
P2 7
P3 7

Process Burst Time Waiting Time Turn Around Response Time

Time
P1 24 13 41 0
P2 7 12 19 4
P3 10 19 29 8
Assume that all jobs are submitted at the same time and time quantum is 4msec.

16 | P a g e