Department of

Computer Science and Engineering

OCB0212–OPERTATING SYSTEMS

Faculty Name :[Link]

• Threads ‐ Overview ‐ Multithreading Models ‐ CPU
Scheduling ‐ Basic Concepts ‐ Scheduling Criteria ‐
Scheduling Algorithms ‐ Thread Scheduling ‐
Multiple‐Processor Scheduling ‐ The Critical‐Section
Problem ‐ Peterson's Solution ‐ Synchronization
Hardware ‐ Semaphores

3
 Thread
• In an operating system, a thread is the
smallest unit of execution that can be
scheduled by the CPU. Think of it as a
"lightweight process." A single process can
contain multiple threads, which allows a
program to perform multiple tasks at the same
time, a concept known as multithreading.

4
 States in the Thread Life
Cycle
• New: The initial state when a thread is created but not yet started.
• Runnable: The thread is ready to run, waiting for the operating
system to allocate CPU time.
• Running: The thread is actively executing its instructions on the
CPU.
• Blocked/Waiting: The thread pauses its execution, typically to
acquire a lock held by another thread or to wait for a specific
event.
• Timed Waiting: The thread is waiting for a specified amount of
time to pass before resuming execution.
• Terminated (Dead): The thread's execution has completed, and it
no longer exists as an active entity.

5
6
• A thread's life cycle describes its states from
creation to termination, encompassing New,
Runnable, Running, Blocked/Waiting, Timed
Waiting, and finally Terminated (or Dead).
Threads transition between these states
through various actions like start(), run(),
sleep(), wait(), and notify() methods, or due to
external events like the completion of a task
or the acquisition of a resource.
7
• A process is essentially a program in execution, which includes
the code, data, and resources (like memory and open files). A
thread exists within a process and has its own program
counter, stack, and register set, but shares the process's
resources. This sharing makes threads "lightweight," as they
are more efficient to create and switch between than
separate processes.
• Multithreading: This is the ability of a system to run multiple
threads. On a single-core processor, the OS rapidly switches
between threads to give the illusion of parallel execution. On
a multi-core processor, threads can truly run simultaneously
on different cores, which significantly boosts performance.
8
Feature Thread Process

Shares memory, code, and

Has its own independent
Resource Sharing files with other threads in
memory, code, and files.
the same process.

Slower and higher

Creation Fast and low-overhead.
overhead.

Slower and more complex

Easy and fast (shared
Communication (inter-process
memory).
communication).

Fast, as less state Slower, as more state

Context Switching information needs to be information needs to be
saved. saved.

9
 Types of Threads
• User-Level Threads: Managed by a library in
user space, with the kernel unaware of them.
They are fast but if one thread blocks, the
entire process also blocks.
• Kernel-Level Threads: Managed directly by the
OS kernel. This allows for true multitasking, as
the kernel can schedule other threads from
the same process if one blocks.

10
 Use Threads
• Responsiveness: A program can remain responsive to
user input while performing background tasks. For
example, in a word processor, one thread can save
the document while another keeps the interface
active for the user.
• Resource Sharing: Threads within the same process
can easily share data, making collaboration and
communication between them straightforward.
• Scalability: Multithreading allows programs to fully
utilize the power of modern multi-core processors.
11
 Multithreading
• Multithreading is the ability of an operating
system to run multiple threads of a single
process concurrently. A thread is the smallest
unit of execution that can be scheduled by the
CPU.

12
•Process vs. Thread: A process is a program in execution with its own
dedicated memory space and resources.
•A thread is a lightweight component within a process. All threads in a single
process share that process's memory and resources, but each thread has its own
unique program counter, stack, and registers. This shared memory is what makes
threads so efficient.
•Concurrency: On a single-core CPU, the OS rapidly switches between different
threads,giving the illusion of parallel execution. This is known as concurrency.
•Parallelism: On a multi-core CPU, different threads can truly run at the same
time on different cores. This is known as parallelism, and it significantly boosts
performance for applications designed to take advantage of it.

13
 Advantages
• Responsiveness: An application can remain responsive to user input even
if one part of it is performing a time-consuming task. For example, a web
browser can use one thread to load a webpage while another handles
user input, preventing the entire application from freezing.
• Resource Sharing: Threads within the same process can easily share data,
which simplifies communication and is more efficient than the complex
inter-process communication (IPC) mechanisms needed for separate
processes.
• Economy: It's much faster and requires less memory to create and
manage threads than to create and manage new processes.
• Scalability: Multithreading allows a program to fully utilize the processing
power of modern multi-core CPUs.

14
 Multithreading Models

• The way threads are managed depends on the operating system's

multithreading model:
• Many-to-One: Many user-level threads are mapped to a single
kernel-level thread. This is fast but doesn't allow for true parallelism
on a multi-core system, and if one thread blocks, the entire process
blocks.
• One-to-One: Each user-level thread is mapped to a unique kernel-
level thread. This allows for true parallelism and prevents blocking
issues, but it has more overhead.
• Many-to-Many: This is a hybrid approach where multiple user-level
threads are multiplexed to a smaller or equal number of kernel-level
threads. It provides a good balance between the other two models.

15
 CPU Scheduling

• CPU scheduling is the process of deciding which process or

thread will use the CPU at a given time. It's a fundamental
part of a multitasking operating system, as it allows the CPU
to be shared among multiple processes, giving the illusion
that they are all running simultaneously.
• The primary goal of a CPU scheduler is to maximize system
performance by balancing various objectives, such as
maximizing CPU utilization and throughput, while minimizing
waiting time and response time for processes.

16
•CPU Utilization: The percentage of time the CPU is busy.
•The goal is to keep it as high as possible.
•Throughput: The number of processes that complete their execution per unit
of time.
•Turnaround Time: The total time from when a process is submitted until it
completes.
•Waiting Time: The amount of time a process spends waiting in the ready
queue.
•Response Time: The time it takes for a process to produce its first response,
not the time it takes to complete.

17
 TWO TYPES OF
SCHEDULING

NON PRE-EMPTIVE PRE – EMPTIVE

SCHEDULING SCHEDULING

18
 1. Non-Preemptive
Scheduling
• In this type of scheduling, once a process is given control of
the CPU, it continues to execute until it either completes its
task or voluntarily releases the CPU. The scheduler cannot
interrupt it.
• First-Come, First-Served (FCFS): The simplest algorithm.
Processes are executed in the order they arrive in the ready
queue. It's easy to implement but can lead to long waiting
times if a long-running process arrives first.
• Shortest-Job-First (SJF): This algorithm selects the process
with the shortest next CPU burst time. It's optimal in terms of
minimizing the average waiting time, but it's difficult to
predict the exact burst time of a process.
19
 2. Preemptive
Scheduling
• In this type of scheduling, the CPU can be taken away from a process before
it finishes. This is typically done to give higher-priority processes a chance to
run or to ensure no single process dominates the CPU for too long.
• Round Robin (RR): This is a preemptive version of FCFS. Each process is
given a small, fixed unit of time (a "time slice" or "quantum"). If the process
doesn't finish within that time, it's preempted and moved to the back of the
ready queue. This is common in time-sharing systems.
• Priority-Based Scheduling: Each process is assigned a priority, and the
scheduler always chooses the highest-priority process to run. Preemption
occurs if a new, higher-priority process arrives.
• Shortest-Remaining-Time-First (SRTF): This is the preemptive version of SJF.
The scheduler always runs the process with the shortest remaining
execution time. If a new process arrives with a shorter remaining time than
the currently running process, the current process is preempted.

20
 CPU scheduling
• CPU scheduling decisions under 4 circumstances:
1. Process -> Switches from running to waiting state(I/O request)
2. Process -> Switches from running to ready state(Interrupt)
[Link] -> Switches from waiting to ready(I/O completes)
[Link] -> Terminates
• Scheduling under 1 and 4 is non preemptive
• 2 and 3 scheduling is preemptive
–Consider access to shared data
–Consider preemption while in kernel mode
–Consider interrupts occurring during crucial OS activities

21
 Dispatcher

• Also called as short term scheduler.

• It is the module that gives control of the CPU to the process selected by the
short term scheduler.

Functions:
• Switching Context

• Switching to mode user.

• Jumping to the proper location in the user program to restart that program.

22
 Dispatch Latency

• The time its takes for the dispatcher to stop

one process & start another running.

23
 Scheduling Criteria

CPU utilization
– keep the CPU as busy as possible.

– Ideal – 0 – 100%

– Real – 40 – 90%

Throughput
•Measure of work.

•# of processes that complete their execution per time unit

Turn around time = No of Processes/Time

24
Turnaround time
• Sum of various time period Spent waiting to get into memory + waiting in
the ready queue + executing on the CPU + I/O time.
TA time = Time of Completion of job – Time of Submission of Job

Waiting time
•Sum of time period process has been waiting in the ready queue.
•For a good algorithm waiting time should be lower.

Response time
•Amount of time the process Starts executing or
•Processor starts responding to a process.

25
26
27
First- Come, First-Served (FCFS)
Scheduling
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:
P1 P2 P3
0 24 27 30

Waiting time for P1 = 0; P2 = 24; P3 = 27

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

28
Suppose that the processes arrive in the order:
P2 , P3 , P1
• The Gantt chart for the schedule is:
P2 P3 P1
0 3 6 30

• Waiting time for P1 = 6; P2 = 0; P3 = 3

• Average waiting time: (6 + 0 + 3)/3 = 3
• Much better than previous case
• Convoy effect - short process behind long process
– Consider one CPU-bound and many I/O-bound processes

29
 Shortest-Job-First (SJF)
Scheduling
• Associate with each process the length of its next CPU burst

– Use these lengths to schedule the process with the shortest time

• SJF is optimal – gives minimum average waiting time for a given set of
processes
– The difficulty is knowing the length of the next CPU request

– Could ask the user

30
Arriva l T Processime Burst Time
P1 0.0 6
P2 2.0 8
P3 4.0 7
P4 5.0 3
• SJF scheduling chart

P4 P1 P3 P2
0 3 9 16 24

• Average waiting time = (3 + 16 + 9 + 0) / 4 = 7

31
• Now we add the concepts of varying arrival times and preemption to the
analysis
ProcessAarri Arrival TimeT Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
• Preemptive SJF Gantt Chart
P1 P2 P4 P1 P3
0 1 5 10 17 26

• Average waiting time = [(10-1)+(1-1)+(17-2)+5-3)]/4 = 26/4 = 6.5 msec

32
 Priority Scheduling

• A priority number (integer) is associated with each process

• The CPU is allocated to the process with the highest priority
(smallest integer  highest priority)
• Preemptive
• Non preemptive
• SJF is priority scheduling where priority is the inverse of
predicted next CPU burst time
• Problem  Starvation – low priority processes may never
execute
• Solution  Aging – as time progresses increase the priority of
the process
33
• ProcessA arri Burst TimeT Priority
• P1 10 3
• P2 1 1
• P3 2 4
• P4 1 5
• P5 5 2
• Priority scheduling Gantt Chart

P1 P2 P1 P3 P4
0 1 6 16 18 19

• Average waiting time = 8.2 msec

34
 Round Robin (RR)

• Each process gets a small unit of CPU time (time quantum q), usually 10-100
milliseconds. After this time has elapsed, the process is preempted and added to the end
of the ready queue.

• If there are n processes in the ready queue and the time quantum is q, then each process
gets 1/n of the CPU time in chunks of at most q time units at once. No process waits
more than (n-1)q time units.

• Timer interrupts every quantum to schedule next process

• Performance

– q large  FIFO

– q small  q must be large with respect to context switch, otherwise overhead is too
high

35
 Example of RR with Time Quantum = 4

• Process Burst Time

• P1 24
• P2 3
• P3 3
• The Gantt chart is:
P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

• Typically, higher average turnaround than SJF, but better

response
• q should be large compared to context switch time
• q usually 10ms to 100ms, context switch < 10 usec
36
 Multilevel Queue

• Ready queue is partitioned into separate queues, eg:

– foreground (interactive)
– background (batch)
• Process permanently in a given queue
• Each queue has its own scheduling algorithm:
– foreground – RR
– background – FCFS
• Scheduling must be done between the queues:
– Fixed priority scheduling; (i.e., serve all from foreground then from
background). Possibility of starvation.
– Time slice – each queue gets a certain amount of CPU time which it
can schedule amongst its processes; i.e., 80% to foreground in RR
– 20% to background in FCFS
37
Multilevel Queue Scheduling

38
 Multilevel Feedback Queue

• A process can move between the various queues; aging can

be implemented this way
• Multilevel-feedback-queue scheduler defined by the following
parameters:
• number of queues
• scheduling algorithms for each queue
• method used to determine when to upgrade a process
• method used to determine when to demote a process
• method used to determine which queue a process will enter
when that process needs service

39
 Example of Multilevel
Feedback Queue
• Three queues:
• Q0 – RR with time quantum 8 milliseconds
• Q1 – RR time quantum 16 milliseconds
• Q2 – FCFS
• Scheduling
• A new job enters queue Q0 which is served FCFS
• When it gains CPU, job receives 8 milliseconds
• If it does not finish in 8 milliseconds, job is moved to queue Q1
• At Q1 job is again served FCFS and receives 16 additional milliseconds
• If it still does not complete, it is preempted and moved to queue Q2

40
 Thread Scheduling
• Thread scheduling is the process by which the
operating system (OS) decides which thread
will run on the CPU at a given [Link] there
can be multiple threads (lightweight
processes) in a program, and limited CPU
cores, the OS must schedule them [Link]
is part of CPU scheduling in a multithreaded
environment.

41
 Types of Thread
Scheduling
• Preemptive Scheduling
– The OS can interrupt a running thread and give the CPU to
another thread.
– Ensures better responsiveness.
– Example: Round Robin scheduling.
• Non-Preemptive Scheduling
– Once a thread starts executing, it cannot be stopped until
it finishes or voluntarily gives up the CPU.
– Simpler but less responsive.
– Example: First Come, First Serve (FCFS).

42
 Levels of Thread
Scheduling
• Process-Contention Scope (PCS)
– Scheduling among threads within the same
process.
– Usually handled by the thread library.
• System-Contention Scope (SCS)
– Scheduling among all threads in the system (from
all processes).
– Usually handled by the OS kernel.

43
 Peterson’s Solution
•Peterson’s Solution is a classical software algorithm used to achieve
•mutual exclusion in a critical section problem for two processes.
•It ensures that only one process enters its critical section at a time,
preventing race conditions.

Conditions of Critical Section Problem (what it must satisfy)Mutual Exclusion –

Only one process can be in the critical section at a time.
Progress – If no process is in the critical section, one of the waiting processes
must be allowed to [Link] Waiting – A process should not wait
indefinitely to enter its critical section.

Variables Usedflag[2] → Boolean array, where each process sets its flag to true
when it wants to enter the critical [Link] → Integer variable that decides
whose turn it is to enter the critical section.

44
• How It Works
• If both processes want to enter at the same
time:
• The turn variable decides which process gets
[Link] other process waits until turn
changes.
• This prevents both from being inside the
critical section at once.

45
• Advantages
• Simple, software-only solution.
• Works for two processes.
• Satisfies mutual exclusion, progress, and
bounded waiting.

46
Limitations
•Works only for two processes (not scalable).
•Assumes atomic read/write of variables (idealized hardware).
•In modern multiprocessor systems, hardware instructions (like Test-
and-Set, Compare-and-Swap) are preferred.

47
• Why Synchronization Hardware?
• In multiprogramming, multiple processes/threads may access
shared resources (e.g., memory, files).This can lead to race
conditions if two processes modify data [Link]
prevent this, the OS uses critical section handling.
• Software-only solutions (like Peterson’s Solution) work but are
inefficient and [Link] support makes
synchronization faster and more reliable.

48
1. Test-and-Set (TS) Instruction
•Checks a memory location and sets it in one atomic step.
•Used to implement locks.

2. Compare-and-Swap (CAS)
•Compares a memory location with an expected value and, if they
match, swaps it with a new value.

3. Exchange Instruction (XCHG / Swap)

•Atomically swaps contents of two variables.
•Used in low-level synchronization.

49
• Advantages of Hardware-Based Synchronization
• Faster than software-only solutions.
• Simple to implement mutual exclusion.
• Works directly at CPU instruction level.
• Disadvantages
• Usually leads to busy waiting (CPU cycles wasted while
waiting).
• Doesn’t automatically provide bounded waiting.
• More suitable for low-level locks; high-level abstractions like
mutexes, semaphores, monitors are built on top of these.

50
 Semaphore
• A synchronization tool used to control access to a shared resource in a
concurrent system (multi-processing/multi-threading).Proposed by
Edsger Dijkstra in the [Link] to solve critical section problems,
producer–consumer problems, etc.
• Types of Semaphores
• Counting Semaphore
• Value can range over an unrestricted domain.
• Used when multiple instances of a resource exist.
• Example: managing a pool of printers.
• Binary Semaphore (Mutex)
• Value is either 0 or 1.
• Works like a lock → ensures only one process enters the critical section at
a time.

51
 Operations on Semaphores

Two atomic operations are used:

•wait() (also called P or down)

wait(S) { while (S <= 0); // busy wait S--; }
•signal() (also called V or up)
signal(S) { S++; }

52
• Advantages
• Simple and powerful synchronization tool.
• Can handle multiple processes and multiple
resources.
• Limitations
• Risk of deadlock (if processes wait forever).
• Risk of starvation (if some processes never get the
resource).
• Complex to debug in large systems.
53
 Thank You

Department of Computer Science and Engineering 54