Process Scheduling in OS

The PPT describes following contents
What is process?
Scheduling Criteria
Types of schedulers
Process Scheduling algorithms along with examples.
Threads
Multithreading
User thread
kernel thread

1. Process And Process Scheduling
By Ms. Rashmi Bhat

2. MODULE OBJECTIVES
To introduce the notion of a process
To describe the various features of processes
To describe various scheduling algorithms
To understand the concept of threads
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 2

3. "PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 3
Recipe (Program)
Recipe being made
(Program in execution)
(Process)

4. What Is A Process?
Process is a program in execution
Process contains
Program code
Program counter and registers
Stack
Data section
Heap
Program is a passiveentity while process is an activeentity.
Two or more processes of same program might run at the same time but
each of them is a separate process.
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 4
Text
Data
Heap
Stack
Fig. Process in memory
Program
Main Memory
Program Process

5. Process States
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 5
New Ready Running
Waiting
Terminated
Admitted
Interrupt
Scheduler dispatch
I/O or
Event wait
I/O or Event
completion
Exit
Fig. Process states (Process Life Cycle)

6. Process Description: Process Control Block (PCB)
Each is represented by a Process Control Block (PCB)
Also known as task control block
PCB contains
Process state
Program counter
CPU registers
CPU Scheduling information
Memory management information
Accounting information
I/O status information
PCB is a repository for any information that vary from process to
process
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 6
Process State
Process Number
Program Counter
Registers
Memory Limits
List of Open Files
. . . .
Fig. Process Control Block

7. Scheduling Queues
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 7
•Contains all
processes
Job Queue
•Ready to
execute
•Waiting for CPU
Ready Queue
•Waiting for a
particular
device I/O
device
Device Queue
Fig. Different Scheduling Queues

8. How A Process Is Scheduled?
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 8
ready queue CPU
I/O I/O queue I/O request
Time slice
expired
fork a child
Wait for an
interrupt
Child
executes
Interrupt
occurs
Newly
admitted
process
Dispatched
Fig. Queueing diagram of process scheduling

9. Who Schedules The Process?
Scheduler
Selects processes from different queues for scheduling purpose
Types of schedulers
Long-term Scheduler (Job Scheduler)
Selects processes from job pool (job queue) and loads them into main memory for execution
Less frequently executed
Controls the degree of multiprogramming(no. of processes in main memory)
Short-term Scheduler (CPU Scheduler)
Selects processes from ready queue and allocates CPU to one of them.
Most frequently executed
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 9

10. Context Switch
When interrupt occurs, the system saves the current context of a process running on
the CPU
The contextis represented in the PCB
We perform
State save of the current state of the process
State restore to resume operations
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
Context-switch time is pure overhead
Highly dependent on hardware support
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 10

11. Context Switch
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 11
Fig. CPU Switching from Process to Process

12. Process Scheduling
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 12

13. Basic Concept of Scheduling
Multiprogramming concept
Properties of a process/program
CPU-bound program
I/O-bound program
CPU Scheduler selects process to execute
Scheduling
Non-preemptive or cooperative
Preemptive
Incurs a cost associated with access to shared data
Affects the design of the operating-system kernel
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 13
When CPU Scheduling is to be done?
When a process moves from
1.Running state waiting state
2.Running state ready state
3.Waiting state ready state
4.Terminates

14. Basic Concept of Scheduling
Dispatcher
Gives control of the CPU to the process selected by short-term scheduler
Involves
Switching context
Switching to user mode
Jumping to the proper location in the user program to restart that program
Dispatch latency
The time it takes for the dispatcher to stop one process and start another running
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 14

15. Scheduling Criteria
CPU Utilization
To keep the CPU as busy as possible
Throughput
The number of processes that are completed per unit time
Turnaround time
The interval from the time of submission of a process to the time of completion
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 15
Waiting
to get in
memory
Waiting
to ready
queue
Executing
on the
CPU
Doing
I/O
Turnaround
Time

16. Scheduling Criteria
Waiting time
The sum of the periods spent waiting in the ready queue
Response time
The time from the submission of a request until the first response is produced
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 16

17. Scheduling Algorithms
First-Come First-Served Scheduling (FCFS)
Shortest Job First Scheduling (SJF)
Priority Scheduling
Round Robin Scheduling (RR)
Multilevel Queue Scheduling
Multilevel Feedback Queue Scheduling
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 17

18. Scenario 1
How movie tickets are issued?
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 18
First-Come First-Served Scheduling (FCFS)

19. First-Come First-Served Scheduling (FCFS)
Managed with FIFO queue
Working of an algorithm
When a process enters in ready queue, its PCB is linked to the tail of the queue
When CPU is free, it is allocated to the process at the head of the queue
Average waiting time is quite long
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 19
??????
�. . . . . . . . . . . . . . .??????
�??????
�??????
�
BusyFree
Tail

20. First-Come First-Served Scheduling (FCFS)
Average Waiting time:
�������??????�??????���??????����������������
��.�����������
Total Turnaround time:
����������������??????���??????��+��??????�??????���??????������??????�������������
Average Turnaround time:
�����������??????��
��.�����������
Schedules in order of arrival of processes
Algorithm is non-preemptive
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 20

21. Remember …
Process Times
Burst Time (BT)
Arrival Time (AT)
Completion Time (CT)
Turnaround Time (TT)
Avg. Turnaround Time (ATT)
Waiting Time (WT)
Avg. Waiting Time (AWT)
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 21
????????????=�??????−�??????
�????????????=
σ
??????=�
�
????????????
??????
��.�����������
????????????=????????????−�??????
�????????????=
σ
??????=�
�
????????????
??????
��.�����������

22. Example 1
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 22
P1 P2 P3 P4
0 7 17 40 44
Suppose following set of processes arrived in system at time 0 in given order.
Process BT WT TT
P1
P2
P3
P4
Average
Process BT
P1 7
P2 10
P3 23
P4 4
Process BT WT TT
P1 7 0 7
P2 10 7 17
P3 23 17 40
P4 4 40 44
Average 16 27
Gantt Chart

23. Example 2
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 23
Suppose following set of five processes arriving at different times.
ProcessBT AT
P1 4 0
P2 5 1
P3 3 2
P4 5 3
P5 6 4
CTTTWT
P1P2P3P4P5
Ready
queue

24. Example 2
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 24
Suppose following set of five processes arriving at different times.
ProcessBT AT
P1 4 0
P2 5 1
P3 3 2
P4 5 3
P5 6 4
CTTTWTCTTTWT
4 4 0
9 8 3
1210 7
1714 9
231913
P1P2P3P4P5
Ready
queue
ATT = 11
AWT = 6.4
P1 P2 P3 P4 P5
0 4 9 12 17 23

25. Example 3
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 26
Suppose following set of five processes arriving at different times, Find avg. waiting time using FCFS
scheduling
ProcessBT AT CT TT WT
A 4 4
B 3 6
C 2 0
D 1 9
E 3 5

26. First-Come First-Served Scheduling (FCFS)
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 27
•Suppose, we have one CPU-bound process and many I/O-bound processes. What will be the situation??
•When all I/O-bound processes wait in ready queue, I/O devices are idle
•When all processes wait in I/O queue, CPU sits idle.
•Convoy Effect
•All the other processes wait for one big process to release the CPU

27. Scenario 2
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 28
I just want
to book a
flight ticketI want to
place an
order for
grocery
I want to play
Counter Strike.
My friends are
waiting
I want to
see cartoon

28. Shortest Job First (SJF)
Each process is associated with the length of the process's next CPU burst
Shortest-next-CPU-burst algorithm
CPU is assigned to process that has the smallest next CPU burst.
If two processes have same CPU burst, FCFSis used.
Algorithm can be either preemptive ornon-preemptive
The choice arises when a new process arrives at the ready queue while a previous process
is still running
Preemptive algorithm : Shortest-Remaining-Time-First (SRTF)
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 29

29. Example 4
Suppose process are arrived in system at different times, Find average turnaround time and average
waiting time using SJF scheduling (Non-preemptive).
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 30
ProcessAT BT
A 0 8
B 2 5
C 1 9
D 3 2

30. Example 4
Suppose process are arrived in system at different times, Find average turnaround time and average
waiting time using SJF scheduling (Non-preemptive). (SRTN)
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 31
ProcessAT BT
A 0 8
B 2 5
C 1 9
D 3 2
A D B C
0 8 10 15 24
CT TT WTCT TT WT
8 8 0
15 13 8
24 23 14
10 7 5
���.????????????=
��
�
=��.��
���.????????????=
��
�
=�.��

31. Example 4
Suppose process are arrived in system at different times, Find average turnaround time and average
waiting time using SJF scheduling (preemptive). (SRTF)
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 32
ProcessAT BT
A 0 8
B 2 5
C 1 9
D 3 2
0 9 15 24
CT TT WTCT TT WT
15 15 7
9 7 2
24 23 14
5 2 0
���.????????????=
��
�
=��.��
���.????????????=
��
�
=�.��
A B D B A C
23 5

32. Example 5
An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling
of processes. Consider the following set of processes with their arrival times and CPU burst times (in
milliseconds):
Find the average waiting time of processes.
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 33
ProcessAT BT
P1 0 12
P2 2 4
P3 3 8
P4 8 4

33. Example 5
An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling
of processes. Consider the following set of processes with their arrival times and CPU burst times (in
milliseconds):
Find the average waiting time of processes.
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 34
ProcessAT BT
P1 0 12
P2 2 4
P3 3 8
P4 8 4
P1 P2 P3 P4 P3 P1
0 2 6 8 12 18 28
CT TT WT
���.????????????=�.��
CT TT WT
28 28 16
6 4 0
18 15 7
12 4 0

34. Scenario 3
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 35
How to share the bicycle among all four friends?

35. Round Robin Scheduling
Designed especially for time sharing systems.
FCFS + Preemption
Time quantum or time slice
The ready queue is treated as a circular queue
The ready queue is treated as a FIFO queue of processes
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 36
P1
P2
P3. . .
Pn
P1 P2 … Pn
Ready Queue
Circular Ready Queue

36. Round Robin Scheduling
Working of the Algorithm
The scheduler picks the first process from the ready queue
Sets a timer to interrupt after 1 time quantum
Dispatches the process
If &#3627408463;&#3627408482;&#3627408479;&#3627408480;&#3627408481;_&#3627408481;??????&#3627408474;??????< 1 &#3627408481;??????&#3627408474;??????&#3627408478;&#3627408482;&#3627408462;&#3627408475;&#3627408481;&#3627408482;&#3627408474;
Currently running process releases the CPU voluntarily
Scheduler selects the next process in the ready queue.
If &#3627408463;&#3627408482;&#3627408479;&#3627408480;&#3627408481;_&#3627408481;??????&#3627408474;??????> 1 &#3627408481;??????&#3627408474;??????&#3627408478;&#3627408482;&#3627408462;&#3627408475;&#3627408481;&#3627408482;&#3627408474;
Timer goes off and causes interrupt to OS and preempts the currently running process
On interrupt, context switch will be executed
The process will be put at the tail of the ready queue
Selects the next process in the ready queue.
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 37

37. Round Robin Scheduling
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 38
P3=4
P2=1
P1=8
P4=10
CPU
Process Burst Time
P1 13
P2 6
P3 4
P4 10
Time quantum = 5 ms
P4=10
P2=1P1=8
CPU
P4=5
P1=3
CPU
P2=1
P1=3P4=5
CPU
P2=6
P1=8
P4=10
P3=4
CPU
P1=8
P4=5P2=1
CPU
P1=13
P4=10
P3=4
P2=6
CPU
P1=3
CPU

38. Example
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 39
Process Burst Time
P1 18
P2 3
P3 5
Time quantum = 3 ms
P1 P2 P3 P1 P3 P1 P1 P1 P1
0 3 6 9 1214 17 20 23 26
Avg. waiting time: (0+6+2)+(3)+(6+3) = 20/3 = 6.67
Total turnaround time: (8+18)+(3+3)+(9+5)= 46
Avg. turnaround time: 46 / 3 = 15.33

39. Round Robin Scheduling
Average waiting time under the RR policy is often long
Algorithm is preemptive
The performance depends heavily on the size of the time quantum
Approach is called processor sharing
The effect of context switching on the performance of RR scheduling
The time quantum has to be large with respect to the context switch time, but it should
not be too large
If the time quantum is too large, RR scheduling degenerates to FCFS policy.
Turnaround time also depends on the size of the time quantum.
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 40

40. Example
Suppose 6 processes are sharing the CPU in FCFS fashion. If the context switch requires 1 unit time,
calculate the average turn waiting time. (All times are in milliseconds)
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 41
Process
Name
Arrival TimeBurst Time
A 0 3
B 1 2
C 2 1
D 3 4
E 4 5
F 5 2

41. Scenario 3
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 42
What will Andy do first??

42. Priority Scheduling
A priorityis associated with each process
Priority is a number assigned to the process
CPU is allocated to the process with the highest priority
Equal-priorityprocesses are scheduled in FCFSmanner
What number is to consider as higher priority?
Convention: Low numbers represent high priority order
Can be either preemptiveor non-preemptive
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 43

43. Priority Scheduling
When a newly arrived process has higher priority than the priority of the currently
running process then
Put the newly arrived process at the head of the ready queue and let the current process
continue. (Non-Preemptive)
OR
Preempt the CPU from currently process, allocate it to the newly arrived process.
(Preemptive)
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 44

44. Example 6
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 45
P2 P5 P1 P3 P4
0 3 4 12 17 19
ProcessBT Priority
P1 8 3
P2 3 1
P3 5 4
P4 2 5
P5 1 2
Assume following set of processes are arrived in system. What will be the average
waiting time when priority scheduling is applied?
CT WT
12 4
3 0
17 12
19 17
4 3
Avg.WaitingTime=
4+0+12+17+3
5
=
36
5
=7.2

45. Example 6
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 46
0
ProcessBTATPriority
P1 8 0 3
P2 3 1 1
P3 5 2 4
P4 2 3 5
P5 1 4 2
Assume following set of processes are arrived in system. What will be the average
waiting time when priority scheduling (preemptive approach) is applied?
CT WT
12 4
4 0
17 10
19 14
5 0
Avg.WaitingTime=
4+0+10+14+0
5
=
28
5
=5.6
P1 P2 P5 P1 P3 P4
1 45 12 17 19

46. Priority Scheduling
Indefinite blocking or starvation
Keeps a low priority processes waiting indefinitely
Solution : aging
Gradually increasing the priority of processes that wait in the system for a long time
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 47

47. Threads
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 48

48. Threads
What is thread?
A threadis a basic unit of CPU
utilization, consisting of a
program counter, a stack, and a
set of registers, ( and a thread
ID.)
Processes (heavyweight) have a
single thread of control.
Also called as lightweight
process.
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 49
Process
Threads

49. Threads
Multithreadingis an ability of an OS to support multiple, concurrent paths of
execution within a single process.
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 50
One Process
One Thread
Multiple Processes
One Thread per process
One Process
Multiple Threads
Multiple Processes
Multiple Thread per process
Fig. Single Threaded Approach Fig. Multithreaded Approaches

50. Threads
In single threaded processmodel, a process includes
Its PCB,
User address space,
User and kernel stack
To manage call/return behavior of the execution of the process
While the process is running, it controls the processor
registers.
The contents of these registers are saved when the process
is not running
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 51
Fig. Single Threaded Process Model

51. Threads
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 52
In multithreaded process model, there is
A single PCB
User Address space
Separate stack for each thread
Separate control block of each thread
All threads share the state and resources of
that process
All threads reside in same address space and
have access to all data
Process
Fig. Multithreaded Process Model

52. Threads
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 53
Benefits of threads:
Takes less time to create a new thread in an existing process than to create a brand new
process.
Takes less time to terminate than the process.
Takes less time to switch between two threads within the same process than to switch
between two processes.
Enhance efficient in communication between different executing programs.

53. Types of Threads
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 54
User Level Threads
All of the work of thread management is carried out by the
application and the kernel is not aware about the existence
of the threads.
Any application can be programmed to be multithreaded
by using thread libraries.
By default an application starts with single thread.
While application is running, at any time, the application
may spawn a new thread to run within the same process.
Threads
User Level
Threads
Kernel Level
Threads
Types of Threads
Fig. Pure UserLevel Thread

54. Types of Threads
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 55
User Level Threads
Advantages
Thread switching does not require kernel mode privileges.
Scheduling can be application specific.
User level threads can run on any operating system.
Disadvantages
When a user level thread executes a system call, not only is that thread blocked, but also all of
the threads within the process are blocked.
In pure user level thread strategy, a multithreaded application cannot take advantage of
multiprocessing OS.

55. Types of Threads
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 56
Kernel Level Threads
All of the work of thread management is done by the kernel.
There is no thread management code in the application level.
Kernel saves context information for process as a whole and for
individual threads within the process.
Scheduling is done by kernel on thread basis.
Kernel can schedule multiple threads on multiple processors
If one thread is blocked, kernel schedules another thread within the
same process.
Transferring control from one thread to another thread in same
process requires a mode switch to the kernel.
Fig. Pure KernelLevel Thread

56. Types of Threads
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 57
Combined Approach
Thread creation is done completely in user space.
Multiple user level threads are mapped onto some (smaller or
equal) number of kernel level threads
Multiple threads within the same application can run in parallel on
multiple processors
Blocking system calls need not block the entire process.
Fig. Combined Approach

57. Multi-Threading Models
"PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 58
One-to-One Model Many-to-One Model Many-to-Many Model

58. "PROCESS AND PROCESS SCHEDULING" BY MS. RASHMI BHAT 59
Thank You…