22XX403 – OPERATING SYSTEM

UNIT II & LP 1 – PROCESSES AND THREADS - PROCESS

SCHEDULING & CPU SCHEDULING ALGORITHMS
PROCESSES AND THREADS
PROCESS:
An active program which running now on the Operating System is known as the process. The Process
is the base of all computing things. Although process is relatively similar to the computer code but, the method
is not the same as computer code. A process is a "active" entity, in contrast to the program, which is sometimes
thought of as some sort of "passive" entity. The properties that the process holds include the state of the
hardware, the RAM, the CPU, and other attributes.

PROCESS IN AN OPERATING SYSTEM

A process is actively running software or a computer code. Any procedure must be carried out in a
precise order. An entity that helps in describing the fundamental work unit that must be implemented in any
system is referred to as a [Link] other words, we create computer programs as text files that, when executed,
create processes that carry out all of the tasks listed in the program.
When a program is loaded into memory, it may be divided into the four components stack, heap, text, and data
to form a process. The process life cycle in the main memory is shown in the diagram below.

Process Lifecycle
 Stack : The process stack stores temporary information such as method or function arguments, the return
address, and local variables.

Heap: This is the memory where a process is dynamically allotted while it is running.

Text : This consists of the information stored in the processor's registers as well as the most recent activity
indicated by the program counter's value.

Data : In this section, both global and static variables are discussed.

Program : Program is a set of instructions which are executed when the certain task is allowed to complete
that certain task. The programs are usually written in a Programming Language like C, C ++, Python, Java,
R, C # (C sharp), etc. A computer program is a set of instructions that, when carried out by a computer,
accomplish a certain task
Threads in Operating System
A thread is a single sequential flow of execution of tasks of a process so it is also known as thread of
execution or thread of control. There is a way of thread execution inside the process of any operating system.
Apart from this, there can be more than one thread inside a process. Each thread of the same process makes
use of a separate program counter and a stack of activation records and control blocks. Thread is often
referred to as a lightweight process.

The process can be split down into so many threads. For example, in a browser, many tabs can be viewed as
threads. MS Word uses many threads - formatting text from one thread, processing input from another thread,
etc.
Need of Thread:
It takes far less time to create a new thread in an existing process than to create a new process. Threads
can share the common data, they do not need to use Inter- Process communication. Context switching is
faster when working with threads. It takes less time to terminate a thread than a process.
Types of Threads
In the operating system, there are two types of threads.
 Kernel level thread.
 User-level thread.
Kernel level thread
The kernel thread recognizes the operating system. There is a thread control block and process control
block in the system for each thread and process in the kernel-level thread. The kernel-level thread is
implemented by the operating system. The kernel knows about all the threads and manages them. The kernel-
level thread offers a system call to create and manage the threads from user-space. The implementation of
kernel threads is more difficult than the user thread. Context switch time is longer in the kernel thread.

User-level thread
The operating system does not recognize the user-level thread. User threads can be easily implemented
and it is implemented by the user. If a user performs a user-level thread blocking operation, the whole process
is blocked. The kernel level thread does not know nothing about the user level thread. The kernel-level thread
manages user-level threads as if they are single-threaded processes? Examples: Java thread, POSIX threads,
etc.

Advantages of User-level threads

  The user threads can be easily implemented than the kernel thread.
 User-level threads can be applied to such types of operating systems that do not support threads at the
kernel-level.
 It is faster and efficient.
 Context switch time is shorter than the kernel-level threads.
 It does not require modifications of the operating system.
 User-level threads representation is very simple. The register, PC, stack, and mini thread control blocks
are stored in the address space of the user-level process.
 It is simple to create, switch, and synchronize threads without the intervention of the process.
Disadvantages of User-level threads

 User-level threads lack coordination between the thread and the kernel.
 If a thread causes a page fault, the entire process is blocked.

Advantages of Kernel-level threads

 The kernel-level thread is fully aware of all threads.
 The scheduler may decide to spend more CPU time in the process of threads being large numerical.
 The kernel-level thread is good for those applications that block the frequency.
Disadvantages of Kernel-level threads
 The kernel thread manages and schedules all threads.
 The implementation of kernel threads is difficult than the user thread.
 The kernel-level thread is slower than user-level threads.

Components of Threads
 1. Program counter
2. Register set
3. Stack space
Benefits of Threads

 Enhanced throughput of the system: When the process is split into many threads, and each thread
is treated as a job, the number of jobs done in the unit time increases. That is why the throughput of
the system also increases.
 Effective Utilization of Multiprocessor system: When you have more than one thread in one
process, you can schedule more than one thread in more than one processor.
 Faster context switch: The context switching period between threads is less than the process context
switching. The process context switch means more overhead for the CPU.
 Responsiveness: When the process is split into several threads, and when a thread completes its
execution, that process can be responded to as soon as possible.
 Communication: Multiple-thread communication is simple because the threads share the same
address space, while in process, we adopt just a few exclusive communication strategies for
communication between two processes.
 Resource sharing: Resources can be shared between all threads within a process, such as code, data,
and files. Note: The stack and register cannot be shared between threads. There is a stack and register
for each thread.

PROCESS SCHEDULING
Operating system uses various schedulers for the process scheduling described below.

1. Long term scheduler

o Long term scheduler is also known as job scheduler. It chooses the processes from the pool
(secondary memory) and keeps them in the ready queue maintained in the primary memory.

o Long Term scheduler mainly controls the degree of Multiprogramming. The purpose of long
term scheduler is to choose a perfect mix of IO bound and CPU bound processes among the
jobs present in the pool.

o The job scheduler chooses more IO bound processes then all of the jobs may reside in the
blocked state all the time and the CPU will remain idle most of the time. This will reduce the
degree of Multiprogramming. Therefore, the Job of long term scheduler is very critical and
may affect the system for a very long time.
 2. Short term scheduler
o Short term scheduler is also known as CPU scheduler. It selects one of the Jobs from the ready
queue and dispatch to the CPU for the execution.

o A scheduling algorithm is used to select which job is going to be dispatched for the execution.
The Job of the short term scheduler can be very critical in the sense that if it selects job whose
CPU burst time is very high then all the jobs after that, will have to wait in the ready queue for
a very long time.

o This problem is called starvation which may arise if the short term scheduler makes some
mistakes while selecting the job.

3. Medium term scheduler

o Medium term scheduler takes care of the swapped out processes. If the running state processes
needs some IO time for the completion, then there is a need to change its state from running to
waiting.

o Medium term scheduler is used for this purpose. It removes the process from the running state
to make room for the other processes. Such processes are the swapped out processes and this
procedure is called swapping. The medium term scheduler is responsible for suspending and
resuming the processes.

o It reduces the degree of multiprogramming. The swapping is necessary to have a perfect mix
of processes in the ready queue.
Process Queues

The Operating system manages various types of queues for each of the process states. The PCB related to
the process is also stored in the queue of the same state. If the Process is moved from one state to another state
then its PCB is also unlinked from the corresponding queue and added to the other state queue in which the
transition is made.
There are the following queues maintained by the Operating system.

1. Job Queue
In starting, all the processes get stored in the job queue. It is maintained in the secondary memory. The
long term scheduler (Job scheduler) picks some of the jobs and put them in the primary memory.

2. Ready Queue
Ready queue is maintained in primary memory. The short term scheduler picks the job from the ready
queue and dispatch to the CPU for the execution.

3. Waiting Queue
When the process needs some IO operation in order to complete its execution, OS changes the state of
the process from running to waiting. The context (PCB) associated with the process gets stored on the
waiting queue which will be used by the Processor when the process finishes the IO.

Various Times related to the Process

• Arrival Time
The time at which the process enters into the ready queue is called the arrival time.

• Burst Time
The total amount of time required by the CPU to execute the whole process is called the Burst
Time. This does not include the waiting time. It is confusing to calculate the execution time for a
process even before executing it hence the scheduling problems based on the burst time cannot
be implemented in reality.

• Completion Time
 The Time at which the process enters into the completion state or the time at which the process
completes its execution, is called completion time.

• Turnaround time
The total amount of time spent by the process from its arrival to its completion, is called
Turnaround time.

• Waiting Time
The Total amount of time for which the process waits for the CPU to be assigned is called waiting
time.

• Response Time
The difference between the arrival time and the time at which the process first gets the CPU is
called Response Time.

CPU SCHEDULING ALGORITHMS

CPU Scheduling
In the uniprogramming systems like MS DOS, when a process waits for any I/O operation to
be done, the CPU remains idol. This is an overhead since it wastes the time and causes the problem of
starvation. However, In Multiprogramming systems, the CPU doesn't remain idle during the waiting time
of the Process and it starts executing other processes. Operating System has to define which process the
CPU will be given.

In Multiprogramming systems, the Operating system schedules the processes on the CPU to
have the maximum utilization of it and this procedure is called CPU scheduling. The Operating System
uses various scheduling algorithm to schedule the processes.

This is a task of the short term scheduler to schedule the CPU for the number of processes present
in the Job Pool. Whenever the running process requests some IO operation then the short term scheduler
saves the current context of the process (also called PCB) and changes its state from running to waiting.
During the time, process is in waiting state; the Short term scheduler picks another process from the
ready queue and assigns the CPU to this process. This procedure is called context switching.

Process Control Block

 The Operating system maintains a process control block during the lifetime of the process. The
Process control block is deleted when the process is terminated or killed. There is the following
information which is saved in the process control block and is changing with the state of the process.

Why do we need Scheduling?

In Multiprogramming, if the long term scheduler picks more I/O bound processes then most of the time,
the CPU remains idol. The task of Operating system is to optimize the utilization of resources. If most
of the running processes change their state from running to waiting then there may always be a possibility
of deadlock in the system. Hence to reduce this overhead, the OS needs to schedule the jobs to get the
optimal utilization of CPU and to avoid the possibility to deadlock.

Process Control Block

An Operating System helps in process creation, scheduling, and termination with the help of Process
Control Block. The Process Control Block (PCB), which is part of the Operating System, aids in managing
how processes operate. Every OS process has a Process Control Block related to it. By keeping data on
different things including their state, I/O status, and CPU Scheduling, a PCB maintains track of processes.

A Process Control Block consists of :

1. Process ID 2. Process State
 3. Program Counter 6. Accounting and Business Information
4. CPU Registers 7. Memory Management Information
5. CPU Scheduling Information 8. Input Output Status Information
1) Process ID
It is a Identification mark which is present for the Process. This is very useful for finding the process.
It is also very useful for identifying the process also.

2) Process States

State Diagram

The process, from its creation to completion, passes through various states. The minimum number of states
is [Link] names of the states are not standardized although the process may be in one of the following states
during execution.

i) New State
A Program which is going to be taken up by the Operating System directly into the Main Memory is
known as a New Process State
ii) Ready State
The ready state, when a process waits for the CPU to be assigned, is the first state it enters after being
formed. The operating system pulls new processes from secondary memory and places them all in main
memory. The term "ready state processes" refers to processes that are in the main memory and are prepared
for execution. Numerous processes could be active at the moment.
iii) Running State
The Operating System will select one of the processes from the ready state based on the scheduling
mechanism. As a result, if our system only has one CPU, there will only ever be one process operating at any
given moment. We can execute n processes concurrently in the system if there are n processors.
iv) Waiting or Blocking State
Depending on the scheduling mechanism or the inherent behavior of the process, a process can go
from the Running state to the Block or Wait states.
The OS switches a process to the block or wait state and allots the CPU to the other processes while it
waits for a specific resource to be allocated or for user input.
v) Terminated State
A process enters the termination state once it has completed its execution. The operating system will
end the process and erase the whole context of the process (Process Control Block).

Operations on the Process

 Creation
Once the process is created, it will be ready and come into the ready queue (main memory) and will
be ready for the execution.
 Scheduling
Out of the many processes present in the ready queue, the Operating system chooses one process and
start executing it. Selecting the process which is to be executed next, is known as scheduling.
 Execution
Once the process is scheduled for the execution, the processor starts executing it. Process may come
to the blocked or wait state during the execution then in that case the processor starts executing the
other processes.
 Deletion/killing
Once the purpose of the process gets over then the OS will kill the process. The Context of the process
(PCB) will be deleted and the process gets terminated by the Operating system.

3) Program Counter
The address of the following instruction to be executed from memory is stored in a CPU register called
a program counter (PC) in the computer processor. It is a digital counter required for both task execution
speed and for monitoring the present stage of execution.
An instruction counter, instruction pointer, instruction addresses register, or sequence control register are
other names for a program counter.
4) CPU Registers
When the process is in a running state, here is where the contents of the processor registers are
 kept. Accumulators, index and general-purpose registers, instruction registers, and condition code
registers are the many categories of CPU registers.
5) CPU Scheduling Information
It is necessary to arrange a procedure for execution. This schedule determines when it transitions from
ready to running. Process priority, scheduling queue pointers (to indicate the order of execution), and several
other scheduling parameters are all included in CPU scheduling information.
6) Accounting and Business Information
The State of Business Addressing and Information includes information such as CPU use, the amount
of time a process uses in real time, the number of jobs or processes, etc.
7) Memory Management Information
The Memory Management Information section contains information on the page, segment tables, and
the value of the base and limit registers. It relies on the operating system's memory system.
8) Input Output Status Information
This Input Output Status Information section consists of Input and Output related information which
includes about the process statuses, etc.

Scheduling Algorithms in OS (Operating System)

There are various algorithms which are used by the Operating System to schedule the processes on the
processor in an efficient way.

The Purpose of a Scheduling algorithm

1. Maximum CPU utilization 4. Minimum turnaround time
2. Fare allocation of CPU 5. Minimum waiting time
3. Maximum throughput 6. Minimum response time

There are the following algorithms which can be used to schedule the jobs.

1. First Come First Serve

It is the simplest algorithm to implement. The process with the minimal arrival time will get the
CPU first. The lesser the arrival time, the sooner will the process gets the CPU. It is the non-preemptive
type of scheduling.

2. Round Robin

In the Round Robin scheduling algorithm, the OS defines a time quantum (slice). All the
processes will get executed in the cyclic way. Each of the process will get the CPU for a small amount
of time (called time quantum) and then get back to the ready queue to wait for its next turn. It is a
preemptive type of scheduling.

3. Shortest Job First

 The job with the shortest burst time will get the CPU first. The lesser the burst time, the sooner
will the process get the CPU. It is the non-preemptive type of scheduling.

4. Shortest remaining time first

It is the preemptive form of SJF. In this algorithm, the OS schedules the Job according to the
remaining time of the execution.

5. Priority based scheduling

In this algorithm, the priority will be assigned to each of the processes. The higher the priority,
the sooner will the process get the CPU. If the priority of the two processes is same then they will be
scheduled according to their arrival time.

6. Highest Response Ratio Next

In this scheduling Algorithm, the process with highest response ratio will be scheduled next. This
reduces the starvation in the system.

First Come First Serve CPU Process Scheduling in Operating Systems

The important concept name is First Come First Serve. This is the basic algorithm which every
student must learn to understand all the basics of CPU Process Scheduling Algorithms.

First Come First Serve paves the way for understanding of other algorithms. This algorithm may have
many disadvantages. But these disadvantages created very new and efficient algorithms. So, it is our
responsibility to learn about First Come First Serve CPU Process Scheduling Algorithms.

Important Abbreviations
1. CPU - - - > Central Processing Unit 5. WT - - - > Waiting Time
2. FCFS - - - > First Come First Serve 6. TAT - - - > Turn Around Time
3. AT - - - > Arrival Time 7. CT - - - > Completion Time
4. BT - - - > Burst Time 8. FIFO - - - > First In First Out