Principles of Operating System (CS303) Unit 2 Dr.

Anum Kamal

THREAD IN OPERATING SYSTEM

A thread is a single sequence stream within a process. Threads are also called lightweight processes as they possess
some of the properties of processes. Each thread belongs to exactly one process.
 In an operating system that supports multithreading, the process can consist of many threads. But threads
can be effective only if the CPU is more than 1 otherwise two threads have to context switch for that single
CPU.
 All threads belonging to the same process share - code section, data section, and OS resources (e.g. open
files and signals)
 But each thread has its own (thread control block) - thread ID, program counter, register set, and a stack
 Any operating system process can execute a thread. we can say that single process can have multiple
threads.

Why Do We Need Thread?

 Threads run in concurrent manner that improves the application performance. Each such thread has its own
CPU state and stack, but they share the address space of the process and the environment. For example,
when we work on Microsoft Word or Google Docs, we notice that while we are typing, multiple things
happen together (formatting is applied, page is changed and auto save happens).
 Threads can share common data so they do not need to use inter-process communication. Like the
processes, threads also have states like ready, executing, blocked, etc.
 Priority can be assigned to the threads just like the process, and the highest priority thread is scheduled
first.
 Each thread has its own Thread Control Block (TCB). Like the process, a context switch occurs for the
thread, and register contents are saved in (TCB). As threads share the same address space and resources,
synchronization is also required for the various activities of the thread.

Components of Threads
These are the basic components of the Operating System.
 Stack Space: Stores local variables, function calls, and return addresses specific to the thread.
 Register Set: Hold temporary data and intermediate results for the thread's execution.
 Program Counter: Tracks the current instruction being executed by the thread.

Similarity Between Threads and Process

 Only one thread or process is active at a time in an operating system.
 Within the process, both execute in a sequential manner.
 Both can create children.
 Both can be scheduled by the operating system: Both threads and processes can be scheduled by the
operating system to execute on the CPU. The operating system is responsible for assigning CPU time to the
threads and processes based on various scheduling algorithms.
 Both have their own execution context: Each thread and process has its own execution context, which
includes its own register set, program counter, and stack. This allows each thread or process to execute
independently and make progress without interfering with other threads or processes.
 Both can communicate with each other: Threads and processes can communicate with each other using
various inter-process communication (IPC) mechanisms such as shared memory, message queues, and
pipes. This allows threads and processes to share data and coordinate their activities.
 Both can be preempted: Threads and processes can be preempted by the operating system, which means
that their execution can be interrupted at any time. This allows the operating system to switch to another
thread or process that needs to execute.

7
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

 Both can be terminated: Threads and processes can be terminated by the operating system or by other
threads or processes. When a thread or process is terminated, all of its resources, including its execution
context, are freed up and made available to other threads or processes.
Differences Between Threads and Process
 Resources: Processes have their own address space and resources, such as memory and file handles,
whereas threads share memory and resources with the program that created them.
 Scheduling: Processes are scheduled to use the processor by the operating system, whereas threads are
scheduled to use the processor by the operating system or the program itself.
 Creation: The operating system creates and manages processes, whereas the program or the operating
system creates and manages threads.
 Communication: Because processes are isolated from one another and must rely on inter-process
communication mechanisms, they generally have more difficulty communicating with one another than
threads do. Threads, on the other hand, can interact with other threads within the same program directly.
Threads, in general, are lighter than processes and are better suited for concurrent execution within a single program.
Processes are commonly used to run separate program or to isolate resources between program.

Types of Thread in Operating System

Threads are of two types. These are described below.
 User Level Thread
 Kernel Level Thread

Threads

8
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

1. User Level Thread

User Level Thread is a type of thread that is not created using system calls. The kernel has no work in the
management of user-level threads. User-level threads can be easily implemented by the user. In case when user-level
threads are single-handed processes, kernel-level thread manages them. Let's look at the advantages and
disadvantages of User-Level Thread.
Advantages of User-Level Threads
 Implementation of the User-Level Thread is easier than Kernel Level Thread.
 Context Switch Time is less in User Level Thread.
 User-Level Thread is more efficient than Kernel-Level Thread.
 Because of the presence of only Program Counter, Register Set, and Stack Space, it has a simple
representation.
Disadvantages of User-Level Threads
 The operating system is unaware of user-level threads, so kernel-level optimizations, like load balancing
across CPUs, are not utilized.
 If a user-level thread makes a blocking system call, the entire process (and all its threads) is blocked,
reducing efficiency.
 User-level thread scheduling is managed by the application, which can become complex and may not be as
optimized as kernel-level scheduling.

2. Kernel Level Threads

A kernel Level Thread is a type of thread that can recognize the Operating system easily. Kernel Level Threads has
its own thread table where it keeps track of the system. The operating System Kernel helps in managing threads.
Kernel Threads have somehow longer context switching time. Kernel helps in the management of threads.
Advantages of Kernel-Level Threads
 Kernel-level threads can run on multiple processors or cores simultaneously, enabling better utilization of
multicore systems.
 The kernel is aware of all threads, allowing it to manage and schedule them effectively across available
resources.
 Applications that block frequency are to be handled by the Kernel-Level Threads.
 The kernel can distribute threads across CPUs, ensuring optimal load balancing and system performance.
Disadvantages of Kernel-Level threads
 Context switching between kernel-level threads is slower compared to user-level threads because it requires
mode switching between user and kernel space.
 Managing kernel-level threads involves frequent system calls and kernel interactions, leading to increased
CPU overhead.
 A large number of threads may overload the kernel scheduler, leading to potential performance degradation
in systems with many threads.
 Implementation of this type of thread is a little more complex than a user-level thread.
For more, refer to the Difference Between User-Level Thread and Kernel-Level Thread.

Threading Issues
 The fork() and exec() System Calls : The semantics of the fork() and exec() system calls change in a
multithreaded program. If one thread in a program calls fork(), does the new process duplicate all threads,
or is the new process single-threaded? Some UNIX systems have chosen to have two versions of fork(),
one that duplicates all threads and another that duplicates only the thread that invoked the fork() system
call. The exec() system , That is, if a thread invokes the exec() system call , the program specified in the
parameter to exec() will replace the entire process—including all threads.

9
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

 Signal Handling : A signal is used in UNIX systems to notify a process that a particular event has
occurred. A signal may be received either synchronously or asynchronously depending on the source of and
the reason for the event being signaled. All signals, whether synchronous or asynchronous, follow the same
pattern:1. A signal is generated by the occurrence of a particular event.2. The signal is delivered to a
process.3. Once delivered, the signal must be handled. A signal may be handled by one of two possible
handlers: 1. A default signal handler .2. A user-defined signal handler. Every signal has a default signal
handler that the kernel runs when handling that signal. This default action can be overridden by a user-
defined signal handler that is called to handle the signal.
 Thread Cancellation : Thread cancellation involves terminating a thread before it has completed. For
example, if multiple threads are concurrently searching through a database and one thread returns the result,
the remaining threads might be canceled. Another situation might occur when a user presses a button on a
web browser that stops a web page from loading any further. Often, a web page loads using several
threads—each image is loaded in a separate thread. When a user presses the stop button on the browser, all
threads loading the page are canceled. A thread that is to be canceled is often referred to as the target thread.
Cancellation of a target thread may occur in two different scenarios:1. Asynchronous cancellation. One
thread immediately terminates the target thread.2. Deferred cancellation. The target thread periodically
checks whether it should terminate, allowing it an opportunity to terminate itself in an orderly fashion.
 Thread-Local Storage : Threads belonging to a process share the data of the process. Indeed, this data
sharing provides one of the benefits of multithreaded programming. However, in some circumstances, each
thread might need its own copy of certain data. We will call such data thread-local storage (or TLS.) For
example, in a transaction-processing system, we might service each transaction in a separate thread.
Furthermore, each transaction might be assigned a unique identifier. To associate each thread with its
unique identifier, we could use thread-local storage.
 Scheduler Activations : One scheme for communication between the user-thread library and the kernel is
known as scheduler activation. It works as follows: The kernel provides an application with a set of virtual
processors (LWPs), and the application can schedule user threads onto an available virtual processor.

What is Multi-Threading?
A thread is also known as a lightweight process. The idea is to achieve parallelism by dividing a process into
multiple threads. For example, in a browser, multiple tabs can be different threads. MS Word uses multiple threads:
one thread to format the text, another thread to process inputs, etc. More advantages of multithreading are discussed
below.
Multithreading is a feature in operating systems that allows a program to do several tasks at the same time. Think of
it like having multiple hands working together to complete different parts of a job faster. Each "hand" is called a
thread, and they help make programs run more efficiently.
Multithreading is a technique used in operating systems to improve the performance and responsiveness of computer
systems. Multithreading allows multiple threads (i.e., lightweight processes) to share the same resources of a single
process, such as the CPU, memory, and I/O devices.

10
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Single Threaded vs Multi-threaded Process

Multithreading can be done without OS support, as seen in Java's multithreading model. In Java, threads are
implemented using the Java Virtual Machine (JVM), which provides its own thread management. These threads,
also called user-level threads, are managed independently of the underlying operating system.
Application itself manages the creation, scheduling, and execution of threads without relying on the operating
system's kernel. The application contains a threading library that handles thread creation, scheduling, and context
switching. The operating system is unaware of User-Level threads and treats the entire process as a single-threaded
entity.

Benefits of Thread in Operating System

 Responsiveness: If the process is divided into multiple threads, if one thread completes its execution, then
its output can be immediately returned.
 Faster context switch: Context switch time between threads is lower compared to the process context
switch. Process context switching requires more overhead from the CPU.
 Effective utilization of multiprocessor system: If we have multiple threads in a single process, then we
can schedule multiple threads on multiple processors. This will make process execution faster.
 Resource sharing: Resources like code, data, and files can be shared among all threads within a process.
Note: Stacks and registers can't be shared among the threads. Each thread has its own stack and registers.
 Communication: Communication between multiple threads is easier, as the threads share a common
address space. while in the process we have to follow some specific communication techniques for
communication between the two processes.
 Enhanced throughput of the system: If a process is divided into multiple threads, and each thread
function is considered as one job, then the number of jobs completed per unit of time is increased, thus
increasing the throughput of the system.

11
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

CPU SCHEDULING IN OPERATING SYSTEMS

CPU scheduling is a process used by the operating system to decide which task or process gets to use the CPU at a
particular time. This is important because a CPU can only handle one task at a time, but there are usually many tasks
that need to be processed. The following are different purposes of a CPU scheduling time.
 Maximize the CPU utilization
 Minimize the response and waiting time of the process.

What is the Need for a CPU Scheduling Algorithm?

CPU scheduling is the process of deciding which process will own the CPU to use while another process is
suspended. The main function of CPU scheduling is to ensure that whenever the CPU remains idle, the OS has at
least selected one of the processes available in the ready-to-use line.
In Multiprogramming, if the long-term scheduler selects multiple I/O binding processes then most of the time, the
CPU remains idle. The function of an effective program is to improve resource utilization.

Basic Concepts
1. CPU-I/O Burst Cycle
The success of CPU scheduling depends on an observed property of processes. The Process execution consists
of a cycle of the CPU execution and I/O wait. Processes alternate between these two states. Process execution
begins with a CPU Burst. That is followed an I/O Burst, which is followed by another CPU burst, then another
I/O burst, and so on.
A process typically spends a period of time executing instructions on the CPU (a "CPU burst"), then transitions
to an I/O operation (an "I/O burst"), and then back to the CPU, and so on. This cycle continues until the process
completes its task.

2. CPU scheduler
Whenever the CPU becomes idle, the operating system must select one of the processes in the ready queue to be
executed. The selection process is carried out by the short-term scheduler (or CPU scheduler). The scheduler
selects a process from the processes in memory that are ready to execute and allocates the CPU to that process.

12
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

3. Dispatcher
Another component involved in the CPU-scheduling function is the dispatcher. The dispatcher is the module
that gives control of the CPU to the process selected by the short-term scheduler.
This function involves the following:
 Switching Context
 Switching to user mode
 Jumping to the proper location in the user program to restart that program.
The dispatcher should be as fast as possible, since it is invoked during every process switch. The time it takes
for the dispatcher to stop one process and start another is known as the dispatch latency.

Terminologies Used in CPU Scheduling

 Arrival Time: The time at which the process arrives in the ready queue.
 Completion Time: The time at which the process completes its execution.
 Burst Time: Time required by a process for CPU execution.
 Turn Around Time: Time Difference between completion time and arrival time.
Turn Around Time = Completion Time – Arrival Time
 Waiting Time(W.T): Time Difference between turn around time and burst time.
Waiting Time = Turn Around Time – Burst Time

Things to Take Care While Designing a CPU Scheduling Algorithm

Different CPU Scheduling algorithms have different structures and the choice of a particular algorithm depends on
a variety of factors.
 CPU Utilization: The main purpose of any CPU algorithm is to keep the CPU as busy as possible.
Theoretically, CPU usage can range from 0 to 100 but in a real-time system, it varies from 40 to 90 percent
depending on the system load.
 Throughput: The average CPU performance is the number of processes performed and completed during
each unit. This is called throughput. The output may vary depending on the length or duration of the
processes.
 Turn Round Time: For a particular process, the important conditions are how long it takes to perform that
process. The time elapsed from the time of process delivery to the time of completion is known as the
conversion time. Conversion time is the amount of time spent waiting for memory access, waiting in line,
using CPU and waiting for I/O.
 Waiting Time: The Scheduling algorithm does not affect the time required to complete the process once it
has started performing. It only affects the waiting time of the process i.e. the time spent in the waiting
process in the ready queue.
 Response Time: In a collaborative system, turn around time is not the best option. The process may
produce something early and continue to computing the new results while the previous results are released
to the user. Therefore another method is the time taken in the submission of the application process until the
first response is issued. This measure is called response time.

Different Types of CPU Scheduling Algorithms

There are mainly two types of scheduling methods:
 Preemptive Scheduling: Preemptive scheduling is used when a process switches from running state to
ready state or from the waiting state to the ready state.
 Non-Preemptive Scheduling: Non-Preemptive scheduling is used when a process terminates , or when a
process switches from running state to waiting state.

13
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

CPU Scheduling
CPU SCHEDULING ALGORITHMS

FCFS - First Come First Serve CPU Scheduling

First Come, First Serve (FCFS) is one of the simplest types of CPU scheduling algorithms. It is exactly what it
sounds like: processes are attended to in the order in which they arrive in the ready queue, much like customers
lining up at a grocery store.
FCFS Scheduling is a non-preemptive algorithm, meaning once a process starts running, it cannot be stopped until it
voluntarily relinquishes the CPU, typically when it terminates or performs I/O. This method schedules processes in
the order they arrive, without considering priority or other factors.

How Does FCFS Work?

The mechanics of FCFS are straightforward:
1. Arrival: Processes enter the system and are placed in a queue in the order they arrive.
2. Execution: The CPU takes the first process from the front of the queue, executes it until it is complete, and
then removes it from the queue.
3. Repeat: The CPU takes the next process in the queue and repeats the execution process.
This continues until there are no more processes left in the queue.

Example of FCFS CPU Scheduling:

To understand the First Come, First Served (FCFS) scheduling algorithm effectively, we'll use two examples -
 one where all processes arrive at the same time,
 another where processes arrive at different times.
We'll create Gantt charts for both scenarios and calculate the turnaround time and waiting time for each process.

Scenario 1: Processes with Same Arrival Time

Consider the following table of arrival time and burst time for three processes P1, P2 and P3
Process Arrival Time Burst Time
p1 0 5
p2 0 3
p3 0 8

Step-by-Step Execution:
1. P1 will start first and run for 5 units of time (from 0 to 5).

14
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

2. P2 will start next and run for 3 units of time (from 5 to 8).
3. P3 will run last, executing for 8 units (from 8 to 16).

Gant Chart:

15
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Now, let's calculate average waiting time and turn around time:
Turnaround Time = Completion Time - Arrival Time
Waiting Time = Turnaround Time - Burst Time
AT : Arrival Time
BT : Burst Time or CPU Time
TAT : Turn Around Time
WT : Waiting Time
Processes AT BT CT TAT WT
P1 0 5 5 5-0 = 5 5-5 = 0
P2 0 3 8 8-0 = 8 8-3 = 5
P3 0 8 16 16-0 = 16 16-8 = 8
 Average Turn around time = 9.67
 Average waiting time = 4.33

Scenario 2: Processes with Different Arrival Times

Consider the following table of arrival time and burst time for three processes P1, P2 and P3
Process Burst Time (BT) Arrival Time (AT)
P1 5 ms 2 ms
P2 3 ms 0 ms
P3 4 ms 4 ms
Step-by-Step Execution:
 P2 arrives at time 0 and runs for 3 units, so its completion time is:
Completion Time of P2=0+3=3
 P1 arrives at time 2 but has to wait for P2 to finish. P1 starts at time 3 and runs for 5 units. Its completion
time is:
Completion Time of P1=3+5=8
 P3 arrives at time 4 but has to wait for P1 to finish. P3 starts at time 8 and runs for 4 units. Its completion
time is:
Completion Time of P3=8+4=12

16
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Gantt Chart:

17
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Now, lets calculate average waiting time and turn around time:

Process Completion Time (CT) Turnaround Time (TAT = CT - AT) Waiting Time (WT = TAT - BT)

P2 3 ms 3 ms 0 ms

P1 8 ms 6 ms 1 ms

P3 12 ms 8 ms 4 ms

 Average Turnaround time = 5.67

 Average waiting time = 1.67

Advantages of FCFS
 The simplest and basic form of CPU Scheduling algorithm
 Every process gets a chance to execute in the order of its arrival. This ensures that no process is arbitrarily
prioritized over another.
 Easy to implement, it doesn't require complex data structures.
 Since processes are executed in the order they arrive, there’s no risk of starvation
 It is well suited for batch systems where the longer time periods for each process are often acceptable.
Disadvantages of FCFS
 As it is a Non-preemptive CPU Scheduling Algorithm, FCFS can result in long waiting times, especially if
a long process arrives before a shorter one. This is known as the convoy effect, where shorter processes are
forced to wait behind longer processes, leading to inefficient execution.
 The average waiting time in the FCFS is much higher than in the others
 Since FCFS processes tasks in the order they arrive, short jobs may have to wait a long time if they arrive
after longer tasks, which leads to poor performance in systems with a mix of long and short tasks.
 Processes that are at the end of the queue, have to wait longer to finish.
 It is not suitable for time-sharing operating systems where each process should get the same amount of
CPU time.

18
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Shortest Job First or SJF CPU Scheduling

Shortest Job First (SJF) or Shortest Job Next (SJN) is a scheduling process that selects the waiting process with
the smallest execution time to execute next. This scheduling method may or may not be preemptive. Significantly
reduces the average waiting time for other processes waiting to be executed.

Implementation of SJF Scheduling

 Sort all the processes according to the arrival time.
 Then select that process that has minimum arrival time and minimum Burst time.
 After completion of the process make a pool of processes (a ready queue) that arrives afterward till the
completion of the previous process and select that process in that queue which is having minimum Burst
time.

Estimation Formula Concept in SJF Scheduling

The Shortest Job First (SJF) Scheduling algorithm selects the process with the smallest burst time for execution. But
in some cases, the exact burst time of a process may not be known in advance. In such scenarios, an estimation
formula is used to predict the next burst time based on the previous burst times.

Estimation Formula
Tn+1=α⋅tn+(1−α)⋅TnTn+1=α⋅tn+(1−α)⋅Tn
Where:
 Tn+1: Predicted burst time for the next process.
 Tn: Previously predicted burst time.
 tn: Actual burst time of the previous process.
 α: Smoothing factor (0 ≤ α ≤ 1).

20
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Characteristics of SJF Scheduling

 Shortest Job first has the advantage of having a minimum average waiting time among all operating system
scheduling algorithms.
 It is associated with each task as a unit of time to complete.
 It may cause starvation if shorter processes keep coming. This problem can be solved using the concept
of ageing.

Example of Non Pre-emptive Shortest Job First CPU Scheduling Algorithm

Example: Consider the following table of arrival time and burst time for three processes P1, P2 and P3.
Process Burst Time Arrival Time
P1 6 ms 0 ms
P2 8 ms 2 ms
P3 3 ms 4 ms
Step-by-Step Execution:
1. Time 0-6 (P1): P1 runs for 6 ms (total time left: 0 ms)
2. Time 6-9 (P3): P3 runs for 3 ms (total time left: 0 ms)
3. Time 9-17 (P2): P2 runs for 8 ms (total time left: 0 ms)
Gantt chart :

21
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

As we know,
 Turn Around time = Completion time - arrival time
 Waiting Time = Turn around time - burst time

Now, lets calculate average waiting time and turn around time:
Process Arrival Burst Completion Turn Around Waiting Time
Time Time Time (CT) Time (TAT) (WT)
(AT) (BT)
P1 0 6 6 6-0 = 6 6-6 = 0
P2 2 8 17 17-2 = 15 15-8 = 7
P3 4 3 9 9-4 = 5 5-3 = 2
 Average Turn around time = (6 + 15 + 5)/3 = 8.6 ms
 Average waiting time = ( 2 + 0 + 7 )/3 = 9/3 = 3 ms

22
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Advantages of SJF Scheduling

 SJF is better than the First come first serve(FCFS) algorithm as it reduces the average waiting time.
 SJF is generally used for long term scheduling.
 It is suitable for the jobs running in batches, where run times are already known.
 SJF is probably optimal in terms of average Turn Around Time (TAT).
Disadvantages of SJF Scheduling
 SJF may cause very long turn-around times or starvation.
 In SJF job completion time must be known earlier.
 Many times it becomes complicated to predict the length of the upcoming CPU request.

26
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Priority Scheduling in Operating System

Priority scheduling is one of the most common scheduling algorithms used by the operating system to schedule
processes based on their priority. Each process is assigned a priority value based on criteria such as memory
requirements, time requirements, other resource needs, or the ratio of average I/O to average CPU burst time.
The process with the highest priority is selected for execution first. If there are multiple processes sharing the same
priority, they are scheduled in the order they arrived, following a First-Come, First-Served approach. The chosen
process is then executed, either until completion or until it is preempted, depending on whether the scheduling is
preemptive or non-preemptive.
Priority Scheduling can be implemented in two ways:
 Non-Preemptive Priority Scheduling
 Preemptive Priority Scheduling

Non-Preemptive Priority Scheduling

In Non-Preemptive Priority Scheduling, the CPU is not taken away from the running process. Even if a higher-
priority process arrives, the currently running process will complete first.
Ex: A high-priority process must wait until the currently running process finishes.

Example of Non-Preemptive Priority Scheduling:

Consider the following table of arrival time and burst time for three processes P1, P2 and P3:
Note: Lower number represents higher priority.
Process Arrival Time Burst Time Priority
P1 0 4 2
P2 1 2 1
P3 2 6 3

Step-by-Step Execution:
 At Time 0: Only P1 has arrived. P1 starts execution as it is the only available process, and it will continue
executing till t = 4 because it is a non-preemptive approach.
 At Time 4: P1 finishes execution. Both P2 and P3 have arrived. Since P2 has the highest priority (Priority
1), it is selected next.
 At Time 6: P2 finishes execution. The only remaining process is P3, so it starts execution.
 At Time 12: P3 finishes execution.
Gantt Chart:

31
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

32
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Now, lets calculate average waiting time and turn around time:
Arrival Burst Completion Turnaround Time (CT - Waiting Time (TAT -
Process
Time Time Time AT) BT)
P1 0 4 4 4 0
P2 1 2 6 5 3
P3 2 6 12 10 4
 Average Turnaround Time = 6.33
 Average Waiting Time = 2.33

Preemptive Priority Scheduling

In Preemptive Priority Scheduling, the CPU can be taken away from the currently running process if a new
process with a higher priority arrives.
Ex: A low-priority process is running, and a high-priority process arrives; the CPU immediately switches to the
high-priority process.
Example of Preemptive Priority Scheduling (Same Arrival Time)
Consider the following table of arrival time and burst time for three processes P1, P2 and P3:
Note: Higher number represents higher priority.
Process Arrival Time Burst Time Priority
P1 0 7 2
P2 0 4 1
P3 0 6 3

Step-by-Step Execution:
 At Time 0: All processes arrive at the same time. P3 has the highest priority (Priority 3), so it starts
execution.
 At Time 6: P3 completes execution. Among the remaining processes, P1 (Priority 2) has a higher priority
than P2, so P1 starts execution.
 At Time 13: P1 completes execution. The only remaining process is P2 (Priority 1), so it starts execution.
 At Time 17: P2 completes execution. All processes are now finished.
Gant Chart:

33
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

34
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Now, lets calculate average waiting time and turn around time:
Arrival Burst Completion Turnaround Time (CT - Waiting Time (TAT -
Process
Time Time Time AT) BT)
P1 0 7 13 13 6
P2 0 4 17 17 13
P3 0 6 6 6 0
 Average Turnaround Time = 12
 Average Waiting Time = 6.33

Example of Preemptive Priority Scheduling (Different Arrival Time)

Consider the following table of arrival time and burst time for three processes P1, P2 and P3:
Process Arrival Time Burst Time Priority
P1 0 6 2
P2 1 4 3
P3 2 5 1

Step-by-Step Execution:
 At Time 0: Only P1 has arrived, so it starts execution.
 At Time 1: P2 arrives with a higher priority (Priority 3) than P1. P1 is preempted, and P2 starts execution.
 At Time 5: P2 completes execution. Both P1 and P3 are available. P1 has the higher priority (Priority 2), so
it starts execution.
 At Time 10: P1 completes execution. P3 resumes execution to finish its remaining burst time.
 At Time 15: P3 completes execution. All processes are now finished.

Gant Chart:

35
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

36
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Now, lets calculate average waiting time and turn around time:
Arrival Burst Completion Turnaround Time (CT - Waiting Time (TAT -
Process
Time Time Time AT) BT)
P1 0 6 10 10 4
P2 1 4 5 4 0
P3 2 5 15 13 8
 Average Turnaround Time = 9
 Average Waiting Time = 4

37
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Round Robin Scheduling in Operating System

Round Robin Scheduling is a method used by operating systems to manage the execution time of multiple
processes that are competing for CPU attention. It is called "round robin" because the system rotates through all the
processes, allocating each of them a fixed time slice or "quantum", regardless of their priority.
The primary goal of this scheduling method is to ensure that all processes are given an equal opportunity to execute,
promoting fairness among tasks.

Here's a simple breakdown:

 Process Arrival: Processes enter the system and are placed in a queue.
 Time Allocation: Each process is given a certain amount of CPU time, called a quantum.
 Execution: The process uses the CPU for the allocated time.
 Rotation: If the process completes within the time, it leaves the system. If not, it goes back to the end of
the queue.
 Repeat: The CPU continues to cycle through the queue until all processes are completed.

Round Robin Flow Chart

How Does It Work? - Imagine you're at a busy restaurant with a group of friends, and there's only one waiter. The
waiter could spend a long time at one table, but instead, he choose to spend exactly one minute at each table before
moving to the next. Similarly, in Round Robin Scheduling, the CPU spends a predetermined slice of time on each
process. If a process hasn't finished its task by the time its slice is up, it's moved to the back of the queue, and the
CPU moves on to the next process.

Advantages of Round Robin Scheduling

 Fairness: Each process gets an equal share of the CPU.
 Simplicity: The algorithm is straightforward and easy to implement.
 Responsiveness: Round Robin can handle multiple processes without significant delays, making it ideal
for time-sharing systems.
Disadvantages of Round Robin Scheduling:
 Overhead: Switching between processes can lead to high overhead, especially if the quantum is too small.
 Underutilization: If the quantum is too large, it can cause the CPU to feel unresponsive as it waits for a
process to finish its time.

42
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Example of Round Robin Scheduling Algorithm:

To understand the Round Robin Scheduling algorithm, let’s consider the following two scenarios:
Scenario 1: Processes with Same Arrival Time
Consider the following table of arrival time and burst time for three processes P1, P2 and P3 and given Time
Quantum = 2 ms
Process Burst Time Arrival Time
P1 4 ms 0 ms
P2 5 ms 0 ms
P3 3 ms 0 ms

Step-by-Step Execution:
1. Time 0-2 (P1): P1 runs for 2 ms (total time left: 2 ms).
2. Time 2-4 (P2): P2 runs for 2 ms (total time left: 3 ms).
3. Time 4-6 (P3): P3 runs for 2 ms (total time left: 1 ms).
4. Time 6-8 (P1): P1 finishes its last 2 ms.
5. Time 8-10 (P2): P2 runs for another 2 ms (total time left: 1 ms).
6. Time 10-11 (P3): P3 finishes its last 1 ms.
7. Time 11-12 (P2): P2 finishes its last 1 ms.

Gantt Chart:

43
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

44
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

45
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Now, lets calculate average waiting time and turn around time:
 Turnaround Time = Completion Time - Arrival Time
 Waiting Time = Turnaround Time - Burst Time

Processes AT BT CT TAT WT
P1 0 4 8 8-0 = 8 8-4 = 4
P2 0 5 12 12-0 = 12 12-5 = 7
P3 0 3 11 11-0 = 11 11-3 = 8
 Average Turn around time = (8 + 12 + 11)/3 = 31/3 = 10.33 ms
 Average waiting time = (4 + 7 + 8)/3 = 19/3 = 6.33 ms

Scenario 2: Processes with Different Arrival Times

Consider the following table of arrival time and burst time for three processes P1, P2 and P3 and given Time
Quantum = 2
Process Burst Time (BT) Arrival Time (AT)
P1 5 ms 0 ms
P2 2 ms 4 ms
P3 4 ms 5 ms

Step-by-Step Execution:
 Time 0-2 (P1 Executes):
o P1 starts execution as it arrives at 0 ms.
o Runs for 2 ms; remaining burst time = 5 - 2 = 3 ms.
o Ready Queue: [P1].
 Time 2-4 (P1 Executes Again):
o P1 continues execution since no other process has arrived yet.
o Runs for 2 ms; remaining burst time = 3 - 2 = 1 ms.
o P2 arrive at 4 ms.
o Ready Queue: [P2, P1].
 Time 4-6 (P2 Executes):
o P2 starts execution as it arrives at 4 ms.
o Runs for 2 ms; remaining burst time = 2 - 2 = 0 ms.
o P3 arrive at 5ms
o Ready Queue: [P1, P3].
 Time 6-7 (P1 Executes):
o P1 starts execution.
o Runs for 1 ms; remaining burst time = 1 - 1 = 0 ms.
o Ready Queue: [P3].
 Time 7-9 (P3 Executes):
o P3 starts execution.
o Remaining burst time = 4 - 2 = 2 ms.
o Ready Queue: [P3].
 Time 9-11 (P3 Executes Again):
o P3 resumes execution and runs for 2 ms and complete its execution
o Remaining burst time = 2 - 2 = 0 ms.
o Ready Queue: [].

46
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Gantt Chart:

47
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

48
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Now, lets calculate average waiting time and turn around time:
Process Completion Time (CT) Turnaround Time (TAT = CT - AT) Waiting Time (WT = TAT - BT)
P1 7 ms 7 ms 2 ms
P2 6 ms 2 ms 0 ms
P3 11 ms 6 ms 2 ms
 Average Turn around time =7+2+6/3=15/3=5ms
 Average waiting time = 2+0+2/3=1.33ms

49
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

What is Multilevel Queue Scheduling?

Multilevel Queue Scheduling is a CPU scheduling mechanism where the process is divided into several hierarchy
queues and each queue possesses a different priority, and process type. The scheduling algorithm can be different for
each Queue and these processes are mapped in a permanent manner to a particular Queue following some criteria,
for example in relation to priority or resources.

Priorities in Multilevel Queue Scheduling

Here, all queues have their own scheduling algorithm, and process is chosen with highest priority. Then it is
executed preemptive or non-preemptively. No process in lower priority queue can get executed until higher process
queue are all empty.

For example, if batch process queue is running and interactive process comes in ready state batch process is
preempted and interactive process is allowed to execute.

Features of Multilevel Queue (MLQ) CPU Scheduling

 Multiple Queues: In MLQ scheduling, processes are divided into multiple queues based on their priority,
with each queue having a different priority level. Higher-priority processes are placed in queues with higher
priority levels, while lower-priority processes are placed in queues with lower priority levels.
 Priorities Assigned: Priorities are assigned to processes based on their type, characteristics, and
importance. For example, interactive processes like user input/output may have a higher priority than batch
processes like file backups.
 Preemption: Preemption is allowed in MLQ scheduling, which means a higher priority process can
preempt a lower priority process, and the CPU is allocated to the higher priority process. This helps ensure
that high-priority processes are executed in a timely manner.
 Scheduling Algorithm: Different scheduling algorithms can be used for each queue, depending on the
requirements of the processes in that queue. For example, Round Robin scheduling may be used for
interactive processes, while First Come First Serve scheduling may be used for batch processes.
 Feedback Mechanism: A feedback mechanism can be implemented to adjust the priority of a process
based on its behavior over time. For example, if an interactive process has been waiting in a lower-priority
queue for a long time, its priority may be increased to ensure it is executed in a timely manner.
 Efficient Allocation of CPU Time: MLQ scheduling ensures that processes with higher priority levels are
executed in a timely manner, while still allowing lower priority processes to execute when the CPU is idle.

50
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

 Fairness: MLQ scheduling provides a fair allocation of CPU time to different types of processes, based on
their priority and requirements.
 Customizable: MLQ scheduling can be customized to meet the specific requirements of different types of
processes.

Advantages of Multilevel Queue CPU Scheduling

 Low Scheduling Overhead: Since processes are permanently assigned to their respective queues, the
overhead of scheduling is low, as the scheduler only needs to select the appropriate queue for execution.
 Efficient Allocation of CPU Time: The scheduling algorithm ensures that processes with higher priority
levels are executed in a timely manner, while still allowing lower priority processes to execute when the
CPU is idle. This ensures optimal utilization of CPU time.
 Fairness: The scheduling algorithm provides a fair allocation of CPU time to different types of processes,
based on their priority and requirements.
 Customizable: The scheduling algorithm can be customized to meet the specific requirements of different
types of processes. Different scheduling algorithms can be used for each queue, depending on the
requirements of the processes in that queue.
 Prioritization: Priorities are assigned to processes based on their type, characteristics, and importance,
which ensures that important processes are executed in a timely manner.
 Preemption: Preemption is allowed in Multilevel Queue Scheduling, which means that higher-priority
processes can preempt lower-priority processes, and the CPU is allocated to the higher-priority process.
This helps ensure that high-priority processes are executed in a timely manner.

Disadvantages of Multilevel Queue CPU Scheduling

 Some processes may starve for CPU if some higher priority queues are never becoming empty.
 It is inflexible in nature.
 There may be added complexity in implementing and maintaining multiple queues and scheduling
algorithms.

Ready Queue is divided into separate queues for each class of processes. For example, let us take three different
types of processes System processes, Interactive processes, and Batch Processes. All three processes have their own
queue. Now, look at the below figure.

The Description of the processes in the above diagram is as follows:

 System Processes: The CPU itself has its own process to run which is generally termed a System Process.
 Interactive Processes: An Interactive Process is a type of process in which there should be the same type
of interaction.

51
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

 Batch Processes: Batch processing is generally a technique in the Operating system that collects the
programs and data together in the form of a batch before the processing starts.
All three different type of processes have their own queue. Each queue has its own Scheduling algorithm. For
example, queue 1 and queue 2 use Round Robin while queue 3 can use FCFS to schedule their processes.

Scheduling among the queues: What will happen if all the queues have some processes? Which process should get
the CPU? To determine this Scheduling among the queues is necessary. There are two ways to do so -
1. Fixed priority preemptive scheduling method: Each queue has absolute priority over the lower priority
queue. Let us consider the following priority order queue 1 > queue 2 > queue 3. According to this
algorithm, no process in the batch queue(queue 3) can run unless queues 1 and 2 are empty. If any batch
process (queue 3) is running and any system (queue 1) or Interactive process(queue 2) entered the ready
queue the batch process is preempted.
2. Time slicing: In this method, each queue gets a certain portion of CPU time and can use it to schedule its
own processes. For instance, queue 1 takes 50 percent of CPU time queue 2 takes 30 percent and queue 3
gets 20 percent of CPU time.

Example Problem:
Consider the below table of four processes under Multilevel queue scheduling. Queue number denotes the queue of
the process.

Priority of queue 1 is greater than queue 2. queue 1 uses Round Robin (Time Quantum = 2) and queue 2 uses FCFS.

Below is the Gantt chart of the problem:

Gantt Chart
Working
 At starting, both queues have process so process in queue 1 (P1, P2) runs first (because of higher priority)
in the round-robin fashion and completes after 7 units
 Then process in queue 2 (P3) starts running (as there is no process in queue 1) but while it is running P4
comes in queue 1 and interrupts P3 and start running for 5 seconds and
 After its completion P3 takes the CPU and completes its execution.

52
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling

Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling is like Multilevel Queue(MLQ) Scheduling but
in this process can move between the queues. And thus, much more efficient than multilevel queue scheduling.
Characteristics of Multilevel Feedback Queue Scheduling:
 In a multilevel queue-scheduling algorithm, processes are permanently assigned to a queue on entry to the
system, and processes are allowed to move between queues.
 As the processes are permanently assigned to the queue, this setup has the advantage of low scheduling
overhead,

Features of Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling:

Multiple queues: Similar to MLQ scheduling, MLFQ scheduling divides processes into multiple queues based on
their priority levels. However, unlike MLQ scheduling, processes can move between queues based on their behavior
and needs.
Priorities adjusted dynamically: The priority of a process can be adjusted dynamically based on its behavior, such
as how much CPU time it has used or how often it has been blocked. Higher-priority processes are given more CPU
time and lower-priority processes are given less.
Time-slicing: Each queue is assigned a time quantum or time slice, which determines how much CPU time a
process in that queue is allowed to use before it is preempted and moved to a lower priority queue.
Feedback mechanism: MLFQ scheduling uses a feedback mechanism to adjust the priority of a process based on
its behavior over time. For example, if a process in a lower-priority queue uses up its time slice, it may be moved to
a higher-priority queue to ensure it gets more CPU time.
Preemption: Preemption is allowed in MLFQ scheduling, meaning that a higher-priority process can preempt a
lower-priority process to ensure it gets the CPU time it needs.
Multilevel Feedback Queue Scheduling (MLFQ) dynamically adjusts the priority of processes based on their
behavior. Understanding how MLFQ works and how to implement it effectively is essential for operating system
studies. This complex scheduling mechanism is often examined in competitive exams.

Advantages of Multilevel Feedback Queue Scheduling:

 It is more flexible.
 It allows different processes to move between different queues.
 It prevents starvation by moving a process that waits too long for the lower priority queue to the higher
priority queue.
Disadvantages of Multilevel Feedback Queue Scheduling:
 The selection of the best scheduler, it requires some other means to select the values.
 It produces more CPU overheads.
 It is the most complex algorithm.

Multilevel feedback queue scheduling, however, allows a process to move between queues. Multilevel Feedback
QueueScheduling (MLFQ) keeps analyzing the behavior (time of execution) of processes and according to which it
changes its priority.
Now, look at the diagram and explanation below to understand it properly.

53
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

Now let us suppose that queues 1 and 2 follow round robin with time quantum 4 and 8 respectively and queue 3
follow FCFS.

Implementation of MFQS is given below -

 When a process starts executing the operating system can insert it into any of the above three queues
depending upon its priority . For example, if it is some background process, then the operating system
would not like it to be given to higher priority queues such as queues 1 and 2. It will directly assign it to a
lower priority queue i.e. queue 3. Let's say our current process for consideration is of significant priority so
it will be given queue 1 .
 In queue 1 process executes for 4 units and if it completes in these 4 units or it gives CPU for I/O operation
in these 4 units then the priority of this process does not change and if it again comes in the ready queue
then it again starts its execution in Queue 1.
 If a process in queue 1 does not complete in 4 units then its priority gets reduced and it is shifted to queue
2.
 Above points 2 and 3 are also true for queue 2 processes but the time quantum is 8 units. In a general case
if a process does not complete in a time quantum then it is shifted to the lower priority queue.
 In the last queue, processes are scheduled in an FCFS manner.
 A process in a lower priority queue can only execute only when higher priority queues are empty.
 A process running in the lower priority queue is interrupted by a process arriving in the higher priority
queue.
Well, the above implementation may differ for example the last queue can also follow Round-robin Scheduling.

Problems in the above implementation: A process in the lower priority queue can suffer from starvation due to
some short processes taking all the CPU time.
Solution: A simple solution can be to boost the priority of all the processes after regular intervals and place them all
in the highest priority queue.

What is the need for such complex Scheduling?

 Firstly, it is more flexible than multilevel queue scheduling.
 To optimize turnaround time algorithms like SJF are needed which require the running time of processes to
schedule them. But the running time of the process is not known in advance. MFQS runs a process for a
time quantum and then it can change its priority(if it is a long process). Thus it learns from past behavior of

54
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

the process and then predicts its future behavior. This way it tries to run a shorter process first thus
optimizing turnaround time.
 MFQS also reduces the response time.

Example 1: Now, let us consider multilevel feedback queue with three queues.

 A Round Robin queue with time quantum of 8 milliseconds, say Q1.

 A Round Robin queue with time quantum of 16 milliseconds, say Q2.
 A First Come First Serve queue, say Q3.
Now, when the process enters Q1 it is allowed to execute and if it does not complete in 8 milliseconds it is shifted to
Q2 and receives 16 milliseconds. Again it is preempted to Q3 if it does not complete in 16 seconds. In this manner,
scheduling is carried on in this scheme.

Example 2: Consider a system that has a CPU-bound process, which requires a burst time of 40 seconds. The
multilevel Feed Back Queue scheduling algorithm is used and the queue time quantum '2' seconds and in each level
it is incremented by '5' seconds. Then how many times the process will be interrupted and in which queue the
process will terminate the execution?
Solution:
 Process P needs 40 Seconds for total execution.
 At Queue 1 it is executed for 2 seconds and then interrupted and shifted to queue 2.
 At Queue 2 it is executed for 7 seconds and then interrupted and shifted to queue 3.
 At Queue 3 it is executed for 12 seconds and then interrupted and shifted to queue 4.
 At Queue 4 it is executed for 17 seconds and then interrupted and shifted to queue 5.
 At Queue 5 it executes for 2 seconds and then it completes.
 Hence the process is interrupted 4 times and completed on queue 5.

55
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

UNIPROCESSOR SCHEDULING
Uniprocessor scheduling in operating systems refers to the management of processes on a single CPU. It involves
deciding which process gets to use the CPU next, aiming to optimize system performance based on various criteria
like response time, throughput, and resource utilization. Different scheduling algorithms are employed, each with its
own strengths and weaknesses, to achieve these goals.
Here's a breakdown of the key aspects:

1. Types of Scheduling:
 Long-term scheduling: Determines which processes are admitted to the system for execution.
 Medium-term scheduling: Manages the swapping of processes in and out of main memory to optimize
resource usage.
 Short-term scheduling (CPU scheduling or dispatcher): The most frequent type, deciding which process
gets to use the CPU next.
 I/O scheduling: Handles requests for input/output operations.

2. Scheduling Algorithms:
 First-Come, First-Served (FCFS):
Processes are executed in the order they arrive. Simple but can lead to longer wait times for shorter processes if a
long process arrives first.
 Round Robin (RR):
Each process gets a fixed time slice (quantum) of CPU time. If a process doesn't finish within its time slice, it's
moved to the back of the queue. Good for time-sharing but can have high overhead if the time slice is too short.
 Shortest Process Next (SPN):
The process with the shortest estimated execution time is selected next. Efficient in terms of minimizing average
waiting time but requires accurate estimation of execution time and can lead to starvation of longer processes.
 Shortest Remaining Time (SRT):
A preemptive version of SPN, where the process with the shortest remaining execution time is selected. Can preempt
a running process if a new process with a shorter remaining time arrives.
 Highest Response Ratio Next (HRRN):
Calculates a ratio based on waiting time and estimated execution time to favor processes that have been waiting
longer or have shorter execution times.
 Priority Scheduling:
Processes are assigned priorities, and the highest priority process is selected for execution.
 Feedback Queues:
Processes can move between different priority queues based on their behavior, allowing for dynamic priority
adjustments.

3. Key Scheduling Concepts:

 Preemptive vs. Non-Preemptive: Preemptive scheduling allows a running process to be interrupted and
switched out for a higher priority process, while non-preemptive scheduling requires a process to finish its
current CPU burst before another process can run.
 Response Time: The time it takes from when a request is submitted until the first output is received.
 Throughput: The number of processes completed per unit of time.
 CPU Utilization: The percentage of time the CPU is actively processing.
 Starvation: A situation where a process is indefinitely delayed because it's constantly preempted by higher
priority processes.

56
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

4. Goals of Scheduling:
 Maximize CPU utilization: Keep the CPU busy as much as possible.
 Maximize throughput: Process as many jobs as possible in a given time.
 Minimize response time: Provide quick responses to user requests.
 Minimize waiting time: Reduce the amount of time processes spend waiting for the CPU.
 Fairness: Ensure that all processes get a reasonable share of the CPU time.
Uniprocessor scheduling is a fundamental aspect of operating systems, and the choice of scheduling algorithm
significantly impacts system performance and user experience.

MULTIPLE-PROCESSOR SCHEDULING
In systems containing more than one processor, multiple-processor scheduling addresses task allocations to multiple
CPUs. This will involve higher throughputs since several tasks can be processed concurrently in separate processors.
It would also involve the determination of which CPU handles a particular task and balancing loads between
available processors.

Approaches to Multiple-Processor Scheduling

One approach is when all the scheduling decisions and I/O processing are handled by a single processor which is
called the Master Server and the other processors executes only the user code. This is simple and reduces the need
of data sharing. This entire scenario is called Asymmetric Multiprocessing. A second approach uses Symmetric
Multiprocessing where each processor is self scheduling. All processes may be in a common ready queue or each
processor may have its own private queue for ready processes. The scheduling proceeds further by having the
scheduler for each processor examine the ready queue and select a process to execute.

1. Processor Affinity
Processor Affinity means a processes has an affinity for the processor on which it is currently running. When a
process runs on a specific processor there are certain effects on the cache memory. The data most recently accessed
by the process populate the cache for the processor and as a result successive memory access by the process are
often satisfied in the cache memory. Now if the process migrates to another processor, the contents of the cache

57
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

memory must be invalidated for the first processor and the cache for the second processor must be repopulated.
Because of the high cost of invalidating and repopulating caches, most of the SMP(symmetric multiprocessing)
systems try to avoid migration of processes from one processor to another and try to keep a process running on the
same processor. This is known as PROCESSOR AFFINITY. There are two types of processor affinity:
 Soft Affinity: When an operating system has a policy of attempting to keep a process running on the same
processor but not guaranteeing it will do so, this situation is called soft affinity.
 Hard Affinity: Hard Affinity allows a process to specify a subset of processors on which it may run. Some
systems such as Linux implements soft affinity but also provide some system calls
like sched_setaffinity() that supports hard affinity.

2. Load Balancing
Load Balancing is the phenomena which keeps the workload evenly distributed across all processors in
an SMP system. Load balancing is necessary only on systems where each processor has its own private queue of
process which are eligible to execute. Load balancing is unnecessary because once a processor becomes idle it
immediately extracts a runnable process from the common run queue. On SMP(symmetric multiprocessing), it is
important to keep the workload balanced among all processors to fully utilize the benefits of having more than one
processor else one or more processor will sit idle while other processors have high workloads along with lists of
processors awaiting the CPU. There are two general approaches to load balancing :
 Push Migration: In push migration a task routinely checks the load on each processor and if it finds an
imbalance then it evenly distributes load on each processors by moving the processes from overloaded to
idle or less busy processors.
 Pull Migration: Pull Migration occurs when an idle processor pulls a waiting task from a busy processor
for its execution.

3. Multicore Processors
In multicore processors multiple processor cores are places on the same physical chip. Each core has a register set
to maintain its architectural state and thus appears to the operating system as a separate physical processor. SMP
systems that use multicore processors are faster and consume less power than systems in which each processor has
its own physical chip. However multicore processors may complicate the scheduling problems. When processor
accesses memory then it spends a significant amount of time waiting for the data to become available. This situation
is called MEMORY STALL. It occurs for various reasons such as cache miss, which is accessing the data that is
not in the cache memory. In such cases the processor can spend upto fifty percent of its time waiting for data to
become available from the memory. To solve this problem recent hardware designs have implemented multithreaded
processor cores in which two or more hardware threads are assigned to each core. Therefore if one thread stalls
while waiting for the memory, core can switch to another thread. There are two ways to multithread a processor :
 Coarse-Grained Multithreading: In coarse grained multithreading a thread executes on a processor until
a long latency event such as a memory stall occurs, because of the delay caused by the long latency event,
the processor must switch to another thread to begin execution. The cost of switching between threads is
high as the instruction pipeline must be terminated before the other thread can begin execution on the
processor core. Once this new thread begins execution it begins filling the pipeline with its instructions.
 Fine-Grained Multithreading: This multithreading switches between threads at a much finer level mainly
at the boundary of an instruction cycle. The architectural design of fine grained systems include logic for
thread switching and as a result the cost of switching between threads is small.

4. Virtualization and Threading

In this type of multiple-processor scheduling even a single CPU system acts like a multiple-processor system. In a
system with Virtualization, the virtualization presents one or more virtual CPU to each of virtual machines running
on the system and then schedules the use of physical CPU among the virtual machines. Most virtualized

58
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

environments have one host operating system and many guest operating systems. The host operating system creates
and manages the virtual machines. Each virtual machine has a guest operating system installed and applications run
within that guest. Each guest operating system may be assigned for specific use cases,applications or users including
time sharing or even real-time operation. Any guest operating-system scheduling algorithm that assumes a certain
amount of progress in a given amount of time will be negatively impacted by the virtualization. A time sharing
operating system tries to allot 100 milliseconds to each time slice to give users a reasonable response time. A given
100 millisecond time slice may take much more than 100 milliseconds of virtual CPU time. Depending on how busy
the system is, the time slice may take a second or more which results in a very poor response time for users logged
into that virtual machine. The net effect of such scheduling layering is that individual virtualized operating systems
receive only a portion of the available CPU cycles, even though they believe they are receiving all cycles and that
they are scheduling all of those [Link], the time-of-day clocks in virtual machines are incorrect because
timers take no longer to trigger than they would on dedicated CPU's. Virtualizations can thus undo the good
scheduling-algorithm efforts of the operating systems within virtual machines.

Use Cases of Multiple Processors Scheduling in Operating System

Now, we will discuss a few of the use cases of Multiple Processor Scheduling in Operating Systems?
 High-Performance Computing ? Multiple processor scheduling is crucial in high-performance computing
(HPC) environments where large-scale scientific simulations, data analysis, or complex computations are
performed. Efficient scheduling of processes across multiple processors enables parallel execution, leading
to faster computation times and increased overall system performance.
 Server Virtualization ? In virtualized environments, where multiple virtual machines (VMs) run on a
single physical server with multiple processors, effective scheduling ensures fair allocation of resources to
VMs. It enables optimal utilization of processing power while maintaining performance isolation and
ensuring that each VM receives its allocated share of CPU time.
 Real-Time Systems ? Real-time systems, such as those used in aerospace, defense, and industrial
automation, have strict timing requirements. Multiple processor scheduling algorithms like Earliest
Deadline First (EDF) ensure that critical tasks with imminent deadlines are executed promptly,
guaranteeing timely response and meeting stringent timing constraints.
 Multimedia Processing ? Multimedia applications, such as video rendering or audio processing, often
require significant computational power. Scheduling processes across multiple processors allows for
parallel execution of multimedia tasks, enabling faster processing and smooth real-time performance.
 Distributed Computing ? In distributed computing systems, tasks are distributed across multiple
processors or nodes for collaborative processing. Efficient scheduling algorithms ensure load balancing,
fault tolerance, and effective resource utilization across the distributed infrastructure, improving overall
system efficiency and scalability.
 Cloud Computing ? Cloud service providers employ multiple processors to serve numerous client requests
simultaneously. Scheduling algorithms optimize the allocation of virtual machines and containers across the
available processors, ensuring fairness, scalability, and efficient resource utilization in cloud computing
environments.
 Big Data Processing ? Big data analytics involves processing and analyzing massive volumes of data.
Multiple processor scheduling enables parallel execution of data processing tasks, such as data ingestion,
transformation, and analysis, significantly reducing the time required for data processing and enabling real-
time or near-real-time insights.
 Scientific Simulations and Modeling ? Numerical simulations and scientific modeling often require
extensive computational resources. Multiple processor scheduling allows for the parallel execution of
simulation tasks, accelerating the time it takes to obtain results and enabling researchers to explore complex
phenomena and perform more accurate simulations.

59
Principles of Operating System (CS303) Unit 2 Dr. Anum Kamal

 Gaming ? In modern gaming systems, multiple processors are utilized to handle complex graphics
rendering, physics simulations, and AI computations. Effective scheduling ensures smooth gameplay,
minimizes lag, and maximizes the utilization of available processing power to deliver an immersive gaming
experience.
 Embedded Systems ? Embedded systems with multiple processors, such as automotive systems, IoT
devices, or robotics, require efficient scheduling to ensure a timely response, real-time control, and
coordination of various tasks running on different processors. Scheduling algorithms prioritize critical tasks
and manage resource allocation to meet system requirements.

Extra
he major differences between single processor and multi-processor are as follows −

Parameter Single Processor Systems Multiprocessor Systems

The name itself is saying that the single For this also the name itself indicates that the
Description processor system contains only one multiprocessor system contains two or more
processor for processing. processors for processing.

Multiprocessor uses two types of approaches −

There is a use of a coprocessor in single
In Symmetric Multiprocessing every processor
processors because it uses multiple
Is there any use performs all the tasks within the operating
Controllers which are designed to handle
of Co- system.
special tasks and that can execute limited
Processors? In Asymmetric Multiprocessing one Processor
instruction sets. For example − DMA
will acts as a Master and Second Processor act
Controller.
as Slave.

The Throughput of Multiprocessor systems is

greater when compared to single processor
The Throughput of single processor systems.
Throughput of systems is less when compared to Suppose if a system contains N processors then
the system multiprocessor systems because every task its throughput will be less than N because
is performed by the same processor. synchronization must be maintained between
two processors and they also share resources
which increases a certain amount of overhead.

Multiprocessor systems cost less than

Single processor systems cost is more
Cost of the equivalent multiple single processor systems
because here every processor requires
processor because they use the same resources on a
separate resources.
sharing basis.

It is difficult to design Multi Processor Systems

What is the because Synchronization must be maintained
It is Easy to design Single Processor
Design Process between processors otherwise it may result in
Systems.
of the processor? overloading of one processor and another
processor may remain idle at the same time.

Single processor system is less reliable Multiprocessor system is more reliable because
Reliability of the
because failure in one processor will result failure of one processor does not halt the entire
system
in failure of the entire system. system but only speed will be slowed down.

Examples Most Modern PCs. Blade Servers.

60