Process

A process is basically a program in execution. The execution of a

process must progress in a sequential fashion.
A process is defined as an entity which represents the basic unit of
work to be implemented in the system.
To put it in simple terms, we write our computer programs in a text
file and when we execute this program, it becomes a process which
performs all the tasks mentioned in the program.
When a program is loaded into the memory and it becomes a process,
it can be divided into four sections ─ stack, heap, text and data. The
following image shows a simplified layout of a process inside main
memory −

S.N. Component & Description

1 Stack
The process Stack contains the temporary data such as
method/function parameters, return address and local variables.
2 Heap
This is dynamically allocated memory to a process during its
run time.

3 Text
This includes the current activity represented by the value of
Program Counter and the contents of the processor's registers.

4 Data
This section contains the global and static variables.

Program

A program is a piece of code which may be a single line or millions

of lines. A computer program is usually written by a computer
programmer in a programming language. For example, here is a
simple program written in C programming language −
#include <stdio.h>

int main() {
printf("Hello, World! \n");
return 0;
}
A computer program is a collection of instructions that performs a
specific task when executed by a computer. When we compare a
program with a process, we can conclude that a process is a dynamic
instance of a computer program.
A part of a computer program that performs a well-defined task is
known as an algorithm. A collection of computer programs, libraries
and related data are referred to as a software.

Process Life Cycle

When a process executes, it passes through different states. These
stages may differ in different operating systems, and the names of
these states are also not standardized.
In general, a process can have one of the following five states at a
time.

S.N. State & Description

1 Start
This is the initial state when a process is first started/created.

2 Ready
The process is waiting to be assigned to a processor. Ready
processes are waiting to have the processor allocated to them by
the operating system so that they can run. Process may come
into this state after Start state or while running it by but
interrupted by the scheduler to assign CPU to some other
process.

3 Running
Once the process has been assigned to a processor by the OS
scheduler, the process state is set to running and the processor
executes its instructions.

4 Waiting
Process moves into the waiting state if it needs to wait for a
resource, such as waiting for user input, or waiting for a file to
become available.

5 Terminated or Exit
Once the process finishes its execution, or it is terminated by the
operating system, it is moved to the terminated state where it
 waits to be removed from main memory.

Process Control Block (PCB)

A Process Control Block is a data structure maintained by the

Operating System for every process. The PCB is identified by an
integer process ID (PID). A PCB keeps all the information needed to
keep track of a process as listed below in the table −

S.N. Information & Description

1 Process State
The current state of the process i.e., whether it is ready, running,
waiting, or whatever.

2 Process privileges
This is required to allow/disallow access to system resources.

3 Process ID
Unique identification for each of the process in the operating
system.

4 Pointer
A pointer to parent process.
5 Program Counter
Program Counter is a pointer to the address of the next
instruction to be executed for this process.

6 CPU registers
Various CPU registers where process need to be stored for
execution for running state.

7 CPU Scheduling Information

Process priority and other scheduling information which is
required to schedule the process.

8 Memory management information

This includes the information of page table, memory limits,
Segment table depending on memory used by the operating
system.

9 Accounting information
This includes the amount of CPU used for process execution,
time limits, execution ID etc.

10 IO status information
This includes a list of I/O devices allocated to the process.

The architecture of a PCB is completely dependent on Operating

System and may contain different information in different operating
systems. Here is a simplified diagram of a PCB −
The PCB is maintained for a process throughout its lifetime, and is
deleted once the process terminates.
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:

o It takes far less time to create a new thread in an existing process

than to create a new process.
o Threads can share the common data, they do not need to use
Inter- Process communication.
o Context switching is faster when working with threads.
o It takes less time to terminate a thread than a process.

Types of Threads

In the operating system, there are two types of threads.

1. Kernel level thread.

2. User-level 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

1. The user threads can be easily implemented than the kernel

thread.
2. User-level threads can be applied to such types of operating
systems that do not support threads at the kernel-level.
3. It is faster and efficient.
4. Context switch time is shorter than the kernel-level threads.
5. It does not require modifications of the operating system.
6. 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.
7. It is simple to create, switch, and synchronize threads without
the intervention of the process.

Disadvantages of User-level threads

1. User-level threads lack coordination between the thread and the

kernel.
2. If a thread causes a page fault, the entire process is blocked.
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. If a kernel
thread performs a blocking operation, the Banky thread execution can
continue. Example: Window Solaris.
Advantages of Kernel-level threads

1. The kernel-level thread is fully aware of all threads.

2. The scheduler may decide to spend more CPU time in the
process of threads being large numerical.
3. The kernel-level thread is good for those applications that block
the frequency.

Disadvantages of Kernel-level threads

1. The kernel thread manages and schedules all threads.

2. The implementation of kernel threads is difficult than the user
thread.
3. The kernel-level thread is slower than user-level threads.

Components of Threads
Any thread has the following components.

1. Program counter
2. Register set
3. Stack space

Benefits of Threads

o 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.
o 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.
o 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.
o 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.
o 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.
o 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.

CPU Scheduling in Operating System

CPU scheduling is a process that allows one process to use the CPU
while the execution of another process is on hold(in waiting state) due
to unavailability of any resource like I/O etc, thereby making full use
of CPU. The aim of CPU scheduling is to make the system efficient,
fast, and fair.

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 from among the processes in memory that are
ready to execute and allocates the CPU to one of them.

CPU Scheduling: 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:

 Switching context
 Switching to user mode
 Jumping to the proper location in the user program to restart that
program from where it left last time.

The dispatcher should be as fast as possible, given that it is invoked

during every process switch. The time taken by the dispatcher to stop
one process and start another process is known as the Dispatch
Latency. Dispatch Latency can be explained using the below figure:
Types of CPU Scheduling

CPU scheduling decisions may take place under the following four
circumstances:

1. When a process switches from the running state to

the waiting state(for I/O request or invocation of wait for the
termination of one of the child processes).
2. When a process switches from the running state to
the ready state (for example, when an interrupt occurs).
3. When a process switches from the waiting state to
the ready state(for example, completion of I/O).
4. When a process terminates.

In circumstances 1 and 4, there is no choice in terms of scheduling. A

new process(if one exists in the ready queue) must be selected for
execution. There is a choice, however in circumstances 2 and 3.
When Scheduling takes place only under circumstances 1 and 4, we
say the scheduling scheme is non-preemptive; otherwise, the
scheduling scheme is preemptive.

Non-Preemptive Scheduling

Under non-preemptive scheduling, once the CPU has been allocated

to a process, the process keeps the CPU until it releases the CPU
either by terminating or by switching to the waiting state.

This scheduling method is used by the Microsoft Windows 3.1 and by

the Apple Macintosh operating systems.

It is the only method that can be used on certain hardware platforms

because It does not require the special hardware(for example a timer)
needed for preemptive scheduling.

In non-preemptive scheduling, it does not interrupt a process running

CPU in the middle of the execution. Instead, it waits till the process
completes its CPU burst time, and then after that it can allocate the
CPU to any other process.

Some Algorithms based on non-preemptive scheduling are: Shortest

Job First (SJF basically non-preemptive) Scheduling and Priority
(non- preemptive version) Scheduling, etc.
Preemptive Scheduling

In this type of Scheduling, the tasks are usually assigned with

priorities. At times it is necessary to run a certain task that has a
higher priority before another task although it is running. Therefore,
the running task is interrupted for some time and resumed later when
the priority task has finished its execution.

Thus this type of scheduling is used mainly when a process switches

either from running state to ready state or from waiting state to ready
state. The resources (that is CPU cycles) are mainly allocated to the
process for a limited amount of time and then are taken away, and
after that, the process is again placed back in the ready queue in the
case if that process still has a CPU burst time remaining. That process
stays in the ready queue until it gets the next chance to execute.

Some Algorithms that are based on preemptive scheduling are Round

Robin Scheduling (RR), Shortest Remaining Time First (SRTF),
Priority (preemptive version) Scheduling, etc.
CPU Scheduling: Scheduling Criteria

There are many different criteria to check when considering

the "best" scheduling algorithm, they are:

CPU Utilization

To make out the best use of the CPU and not to waste any CPU cycle,
the CPU would be working most of the time(Ideally 100% of the
time). Considering a real system, CPU usage should range from 40%
(lightly loaded) to 90% (heavily loaded.)

Throughput

It is the total number of processes completed per unit of time or rather

says the total amount of work done in a unit of time. This may range
from 10/second to 1/hour depending on the specific processes.

Turnaround Time
It is the amount of time taken to execute a particular process, i.e. The
interval from the time of submission of the process to the time of
completion of the process(Wall clock time).

Waiting Time

The sum of the periods spent waiting in the ready queue amount of
time a process has been waiting in the ready queue to acquire get
control on the CPU.

Load Average

It is the average number of processes residing in the ready queue

waiting for their turn to get into the CPU.

Response Time

Amount of time it takes from when a request was submitted until the
first response is produced. Remember, it is the time till the first
response and not the completion of process execution(final response).

In general CPU utilization and Throughput are maximized and other

factors are reduced for proper optimization.

Scheduling Algorithms

To decide which process to execute first and which process to execute

last to achieve maximum CPU utilization, computer scientists have
defined some algorithms, they are:

1. First Come First Serve(FCFS) Scheduling

2. Shortest-Job-First(SJF) Scheduling
3. Priority Scheduling
4. Round Robin(RR) Scheduling
5. Multilevel Queue Scheduling
6. Multilevel Feedback Queue Scheduling
7. Shortest Remaining Time First (SRTF)
What are Real-Time Systems

A real-time system is one whose correctness depends on timing as

well as functionality.

When we discussed more traditional scheduling algorithms, the

metrics we looked at were turn-around time (or throughput), fairness,
and mean response time. But real-time systems have very different
requirements, characterized by different metrics:

 timeliness ... how closely does it meet its timing requirements

(e.g. ms/day of accumulated tardiness)
 predictability ... how much deviation is there in delivered
timeliness

And we introduce a few new concepts:

 feasibility ... whether or not it is possible to meet the

requirements for a particular task set
 hard real-time ... there are strong requirements that specified
tasks be run a specified intervals (or within a specified response
time). Failure to meet this requirement (perhaps by as little as a
fraction of a micro-second) may result in system failure.
 soft real-time ... we may want to provide very good (e.g.
microseconds) response time, the only consequences of missing
a deadline are degraded performance or recoverable failures.

It sounds like real-time scheduling is more critical and difficult than

traditional time-sharing, and in many ways it is. But real-time systems
may have a few characteristics that make scheduling easier:

 We may actually know how long each task will take to run. This
enables much more intelligent scheduling.
 Starvation (of low priority tasks) may be acceptable. The space
shuttle absolutely must sense attitude and acceleration and
adjust spolier positions once per millisecond. But it probably
doesn't matter if we update the navigational display once per
millisecond or once every ten seconds. Telemetry transmission
is probably somewhere in-between. Understanding the relative
 criticality of each task gives us the freedom to intelligently shed
less critical work in times of high demand.
 The work-load may be relatively fixed. Normally high
utilization implies long queuing delays, as bursty traffic creates
long lines. But if the incoming traffic rate is relatively constant,
it is possible to simultaneously achieve high utilization and good
response time.

Real-Time Scheduling Algorithms

In the simplest real-time systems, where the tasks and their execution
times are all known, there might not even be a scheduler. One task
might simply call (or yield to) the next. This model makes a great deal
of sense in a system where the tasks form a producer/consumer
pipeline (e.g. MPEG frame receipt, protocol decoding, image
decompression, display).

In more complex real-time system, with a larger (but still fixed)

number of tasks that do not function in a strictly pipeline fashion, it
may be possible to do static scheduling. Based on the list of tasks to
be run, and the expected completion time for each, we can define (at
design or build time) a fixed schedule that will ensure timely
execution of all tasks.

But for many real-time systems, the work-load changes from moment
to moment, based on external events. These
require dynamic scheduling. For dynamic scheduling algorithms, there
are two key questions:

1. how they choose the next (ready) task to run

o shortest job first
o static priority ... highest priority ready task
o soonest start-time deadline first (ASAP)
o soonest completion-time deadline first (slack time)
2. how they handle overload (infeasible requirements)
o best effort
o periodicity adjustments ... run lower priority tasks less
often.
 o work shedding ... stop running lower priority tasks
entirely.

Preemption may also be a different issue in real-time systems. In

ordinary time-sharing, preemption is a means of improving mean
response time by breaking up the execution of long-running,
compute-intensive tasks. A second advantage of preemptive
scheduling, particularly important in a general purpose timesharing
system, is that it prevents a buggy (infinite loop) program from taking
over the CPU. The trade-off, between improved response time and
increased overhead (for the added context switches), almost always
favors preemptive scheduling. This may not be true for real-time
systems:

 preempting a running task will almost surely cause it to miss its

completion deadline.
 since we so often know what the expected execution time for a
task will be, we can schedule accordingly and should have little
need for preemption.
 embedded and real-time systems run fewer and simpler tasks
than general purpose time systems, and the code is often much
better tested ... so infinite loop bugs are extremely rare.

For the least demanding real time tasks, a sufficiently lightly loaded
system might be reasonably successful in meeting its deadlines.
However, this is achieved simply because the frequency at which the
task is run happens to be high enough to meet its real time
requirements, not because the scheduler is aware of such
requirements. A lightly loaded machine running a traditional
scheduler can often display a video to a user's satisfaction, not
because the scheduler "knows" that a frame must be rendered by a
certain deadline, but simply because the machine has enough cycles
and a low enough work load to render the frame before the deadline
has arrived.