Tribhuvan University

Institute of Engineering
Pulchowk Campus
Department of Electronics and Computer Engineering

Operating System
Chapter Two
Process Management

Santosh Giri
Asst. Professor, IOE, Pulchowk Campus.
 Chapter Two: Process Management

Course Outline: 7 hours

1. Introduction to Process
Process description
Process states
Process control
2. Scheduling Algorithms
First Come First Serve(FCFS)
Shortest Job First(SJF)
Shortest Remaining Time(SRT)
Round Robin(RR)
Highest Response Ratio Next (HRNN)
Completely Fair Scheduler (CFS) used in Linux.
3. Threads
Process Basics
 Introduction to Process
 Program
 A program is a piece of code which may be a single line or
millions of lines which when executed performs a specific task.

 Process
 A process is an instance of a program in execution.
 Each process has its own address space and Process Control Block
(PCB).

4
 Process States
Processes may be in one of 5 states, as shown in the Figure below

Some systems may have other states besides the ones listed here

7
 Process States…
New:
The process is in the stage of being created.
Ready:
The process has all the resources available that it needs to run, but the CPU is not
currently working on this process's instructions.
Running:
The CPU is working on this process's instructions.
Waiting:
The process cannot run at the moment, because it is waiting for some resource to
become available or for some event to occur. For example, the process may be
waiting for keyboard input, disk access request, inter-process messages, a timer to
go off, or a child process to finish.
Terminated - The process has been completed.

8
 Process Control Block
For each process, there is a Process Control Block, PCB, which stores the following (
types of ) process-specific information, as illustrated in the figure below
(details may vary from system to system. )

9
 Process Control Block
 Process ID: Unique Identification for each process.
 Process State: Running, waiting, etc., as discussed earlier.
 Program counter: Address of next instruction to be executed for this process.
 Pointer: A pointer to the parent process.
 Priority: priority numbers of each process.
 CPU Registers: Various CPU registers where processes need to be stored for
execution for running state.
 I/O Status Information: list of I/O devices allocated to the process.
 Accounting Information: CPU time consumed, account numbers, limits, etc.
 CPU Scheduling Information: Process priority and other scheduling information
which is required to schedule the process.
 Memory Management Information: Information of page table, memory limits,
and segments table depending on the memory used by the OS.
10
Thread
 Thread

 A thread is the smallest unit of execution in a program.

 A program becomes a process when it runs.
 A process can have one or more threads.
 All threads in a process share the same:
• Code, Data (memory), etc.
 Real-World Examples
• Web Browser: Each tab is a thread.
• Video Player: One thread plays video, another handles audio.
• MS Word: Typing is one thread, spell-checking is another.

17
 Thread

Common Issues
 Race Conditions:
Two threads changing the same data at the same time.
 Need Synchronization:
Use locks, semaphores to prevent errors.

Summary (Key Points)

 Threads = mini-programs inside a process.
 Multiple threads → faster and smoother programs.
 Threads share memory → good for performance, but needs
careful management.
Assignment
Implement a multithreaded program in C using the pthread header file.

18
CPU Scheduling:

 It is the basis of multi-programmed operating systems.

 By switching the CPU among processes, It can make the

computer more productive

 A CPU scheduler is responsible for

Removal of running process from the CPU
Selection of the next running process (based on a particular strategy)
Goal for a scheduler

 Maximize
 CPU utilization: keep the CPU as busy as possible
 Throughput: the number of processes completed per unit time

 Minimize
 Response time: the time of submission to the time the first response
is produced
 Wait time: total time spent waiting in the ready queue
 Turnaround time: the time of submission to the time of completion
Scheduling Terminologies
o Burst Time/Execution Time(BT):It is the time required by the process to
complete execution. It is also called running time.
o Arrival Time(AT): when a process enters a ready state.
o Complete Time(CT): when process complete and exit from a system
o Turn Around Time(TAT): The time interval from the time of submission of a
process to the time of the completion of the process.
i.e. TAT = CT – AT
o Waiting time(WT): The total time waiting in a queue. i.e. WT = TAT – BT
o Response Time(RT): Amount of time from when a request was submitted
until the first response is produced.
o CPU/IO burst cycle: Characterizes process execution, which alternates
between CPU and I/O activity. CPU times are usually shorter than the time of
I/O.
o Quantum size: specific time interval used to prevent any one process from
monopolizing the system i.e. can be run exclusively.

22
Scheduling: Priority
Types of Priority Scheduling
1. Preemptive Scheduling:
In Preemptive Scheduling, the tasks are mostly assigned with their priorities.
 Sometimes it is important to run a task with a higher priority before another
lower-priority task, even if the lower-priority task is still running.
The lower priority task holds for some time and resumes when the higher
priority task finishes its execution.

2. Non-Preemptive Scheduling:
• In this type of scheduling method, the CPU has been allocated to a specific
process.
• The process that keeps the CPU busy, will release the CPU either by switching
context or terminating.
34
Scheduling: Priority
When scheduling is Preemptive or Non-Preemptive?

To determine if scheduling is preemptive or non-preemptive,

consider these four parameters:
1. A process switches from the running to the waiting state.
2. Specific process switches from the running state to the ready
state.
3. Specific process switches from the waiting state to the ready
state.
4. The process finished its execution and terminated.
• Only conditions 1 and 4 apply, the scheduling is called non-preemptive.
• All other scheduling is preemptive.
35
Scheduling Terminologies
o Burst Time/Execution Time(BT):It is the time required by the
process to complete execution. It is also called running time.
o Arrival Time(AT): when a process enters a ready state.
o Complete Time(CT): when process is complete and exit from a
system
o Turn Around Time(TAT): The time interval from the time of
submission of a process to the time of the completion of the
process.
i.e. TAT = CT – AT
o Waiting time(WT): The total time waiting in a queue.
i.e. WT = TAT – BT
o Quantum size: specific time interval used to prevent any one
process from monopolizing the system i.e. can be run exclusively.
38
Categories of Scheduling Algorithms
[Link] Come First Served (FCFS)
[Link]-Job-First (SJF) Scheduling
[Link] Remaining Time
[Link] Robin Scheduling
[Link](Highest Response Ratio Next) Scheduling
[Link] Scheduling

Carry a Calculator for next class

39
[Link] Come First Serve (FCFS):
o The process which requests the CPU gets the CPU allocation first. This
scheduling method can be managed with a FIFO queue.
o It offers a non-preemptive scheduling algorithm.

Advantages:
o It is pretty simple and easy to implement.
o Eventually, every process will get a chance to run, so starvation doesn’t
occur.
Disadvantages:
o This method is poor in performance, and the general wait time is quite
high.
o As there is no option for preemption of a process, if a process is started,
then CPU executes the process until it ends.
40
[Link] Come First Serve Examples:

41
[Link] Come First Serve Examples:

42
[Link] Come First Serve Examples:

43
2. Shortest Job First (SJF)/Shortest Process Next:
o It is a non-preemptive Scheduling Algorithm.
o It is a scheduling policy that selects the waiting process with the
smallest execution time to execute first.
Advantages:
o The throughput is increased because more processes can be executed in
less amount of time.
o Having minimum average waiting time among all scheduling
algorithms.
Disadvantages:
o It is practically infeasible as OS may not know burst time and therefore
may not sort them.
o Longer processes will have more waiting time, eventually, they will
suffer starvation.
44
2. Shortest Job First (SJF) Examples:

45
2. Shortest Job First (SJF) Examples:

46
2. Shortest Job First (SJF) Examples:

47
3. Shortest Remaining Time Scheduling:
o Also called Preemptive Shortest Job First/Shortest Remaining
Time Next, or Shortest Remaining Time First.
o Process with the smallest amount of time remaining until
completion is selected to execute.
Advantages:
oShort processes are handled very quickly.
oThe system also requires very little overhead since it only makes a
decision when a process completes or a new process is added.

Disadvantages:
oLike shortest job first, it has the potential for process starvation.
oLong processes may be held off indefinitely if short processes are
continually added.

48
 3. Shortest Remaining Time Scheduling Example:

Classwork 1 Classwork 2

49
4. Round Robin Scheduling:
o CPU is assigned to the process for a fixed amount of time called quantum
or time slice.
o After the time quantum expires, the running process is preempted a queue.
o Then, the CPU is assigned to the next arrived process.
o It is always preemptive scheduling algorithm.

Advantages:
o It gives the best performance in terms of average response time.
o It is best suited for time sharing system, client server architecture.

Disadvantages:
o It lead to starvation for processes with larger burst time as they have to repeat the
cycle many times.
o Its performance heavily depends on time quantum.
o Priorities can not be set for the processes.
50
4. Round Robin Scheduling: Examples

51
4. Round Robin Scheduling: Examples
Draw the Gantt chart of the above processes and find the average TAT and average
WT using round robin with quantum 3 and 2.

52
5. HRRN (Highest Response Ratio Next):
o Most optimal, Non-preemptive algorithm in which the scheduling is done on the
basis of an extra parameter called Response Ratio.
o Response Ratio is calculated as
Response Ratio = (WT+BT)/BT
Where,
WT = Waiting Time
BT = Service Time or Burst Time
o Job with the highest response ratio is given priority over the others.
Advantages:
o It performs better than SJF Scheduling.
o It not only favors the shortest jobs but also limits the waiting time for longer jobs.
Disadvantages:
o Practically, implementations is nearly impossible if burst time of the processes cannot
be known in advance.

53
 6. HRRN Example:

• At t = 0, only process A is available in the ready queue. So, process A executes till its
completion.
• At t = 3, only process B is available in the ready queue. So, process B executes till its
completion.
• At t = 9, C, D, and E processes are available in the ready queue.
 Response Ratio for process C = [(9-4) + 4] / 4 = 9 / 4 = 2.25
 Response Ratio for process D = [(9-6) + 5] / 5 = 8 / 5 = 1.6
54
 Response Ratio for process E = [(9-8) + 2] / 2 = 3 / 2 = 1.5

• Since process C has the highest response ratio, so process C executes till completion i.e. till
t=13.
 6. HRRN Example:

• At t = 13, the processes D and E are available in the ready queue. So, the response ratio is
calculated as-

 Response Ratio for process D = [(13-6) + 5] / 5 = 12 / 5 = 2.4

 Response Ratio for process E = [(13-8) + 2] / 2 = 7 / 2 = 3.5
• Since process E has the highest response ratio, so process E executes till completion i.e. till
t=15.
55
• At t = 15, only the process D is available in the ready queue. So, process D executes till its
completion.
6. HRRN Example:

56
 Assignment 2

1. Implement a multithreaded program in C using the pthread header file.

2. Completely Fair Scheduler (CFS) used in Linux.

3. Calculate Average TAT, Average WT, Throughput, and CPU Utilization for
the following problems:
• First Come First Serve Examples ( Question 1 and Question 2)
• Shortest Remaining Time Scheduling Example ( Example 1)
• Round Robin ( Example 1: Quantum Time=4, 3, and 2)
• Priority Scheduling: Non-Preemptive Example (Question 2)
• Priority Scheduling: Preemptive Example (Example 2)

57