Operating System

Process and Threads

Contents
1. Program and process, C Program Execution

2. Process Related Details

○ Process Structure
○ Layout of a process in memory.
○ Memory Layout of a C program
○ Process States Diagram
○ PCB
○ Process scheduling Queues
○ Process- Context Switching
○ Schedulers

2
Process & Program
Process is a program in execution
Process execution must progress in sequential fashion
Program is a passive entity stored on disk (executable file), process is
active entity
Program becomes process when executable file loaded into memory
Executable program can be loaded into memory
1. By mouse click
2. By command line
One program can have several processes.
3
Process

Processor RAM HDD

● A program is written using programming languages like Java, Python etc.

● The program is also referred to as source code
● After compilation of source code a byte code (executable) is created
● Bytecode is initially placed on disk like HDD/SSD

4
Process

Processor RAM HDD

● When user run executable file using mouse or command line interface,
executable and data related to program brought into RAM
● Memory gets allocated to code and data in RAM

5
Process

Processor RAM HDD

● Processor reads the data and instructions from memory and perform
computations.
● Read/write happens on main memory.

6
Process

Processor RAM HDD

● After program execution source code and data related to code is

removed from memory
● The executable remains on HDD/SSD

7
A C program execution
Here it is a Here it is a
Program i.e Process i.e Processor
passive entity active entity

C program Compile Executabl Data

e

HDD RAM 8
Process related details
● Process Structure
● Layout of a process in memory.
● Memory Layout of a C program
● Process States Diagram
● PCB
● Process scheduling Queues
● Process- Context Switching
● Schedulers

9
Process structure
1. Int a,b,c,Result
2. Int call_func(int a, int b)
3. { A process is program under execution.
4. Int x = a*b A process is more than program code.
5. Int y = a-b
6. Return (y+x) It also includes
7. } ● Process ID
8. Int main() ● program counter
9. { ● registers
10. Read a,b,c ● state
11. Result = Call_func(a,b,c) ● open files pointers
12. print(Results) ● Current directory, etc.
13. Return main
14. }
10
Layout of a process in memory.
1. Int a,b,c,Result Max Stack Process stack
2. Int call_func(int a, int b) contains
Heap is the memory
3. { Temporary data
which
Data is dynamically
4. Int x = a*b such assection
function which
allocated
A programduring
contains globalcode is
5. Int y = a-b parameters, return
process
storedruntime
variables in a text
address, and local
6. Return (y+x) section
variables
7. }
8. Int main() Heap
9. {
Data A program counter
10. Read a,b,c,Result register keep track
11. Result = Call_func(a,b) current instruction being
0 Text
12. print(Results) executed and processor
13. Return main registers holds the
14. } variable values
Heap and stack 11
grow or shrink
Memory layout of a C program
#include<stdio.h>
#include<stdlib.h>
Argc, argv
int x;
Stack int y = 15;
int main(int argc, int *argv[])
{
int *value;
int i;
values = (int *)malloc(sizeof(int) * 5);
Heap for(int i = 0; i < 5; i++)
uninitialized data {
values[i] = i;
Initialized data }
return 0;
Text
}
12
Process states

New The Process is being created

Ready The process is waiting to be assigned to processor

Running Instructions are being executed

Waiting The process is waiting for some event to occur

Terminate
The process completes its execution
d
13
Process state diagram
New Admitted Interrupt Terminated

Ready Running
Exit

Scheduler dispatch
IO event
IO or event wait
completion
Waiting

It is important to realize that only one process can be running on any processor core at
any instant.
14
Process state diagram
New

● When user clicks or run executable, data and source code of the
program copied from disk into main memory after memory gets
allocated.
● A process is just created and not assigned with any CPU resources

15
Process state diagram
New Admitted

Ready

● After allocation of memory process is ready to execute

● Process is placed into ready queue by a long term scheduler
● A process will get chance to CPU resource based on short term
scheduler
● Process may not get CPU for execution immediately as other process
running on CPU 16
Process state diagram
New Admitted

Ready Running

Scheduler dispatch

● When scheduler (short term) decides to execute the process, process

moves to running state
● In running state process got the CPU and its executing
17
Process state diagram
New Admitted

Ready Running

Scheduler dispatch
IO or event wait
Waiting

● During process execution process may expect IO operation such as

read input from the user from keyboard
● Users are much slower as compared to processor
● Process should be kept in waiting state so that other processes get
18
chance for CPU
Process state diagram
New Admitted

Ready Running

Scheduler dispatch
IO event
IO or event wait
completion
Waiting

● On completion of IO, process will again kept in ready state

● Short term scheduler takes decision to keep process into running
state again.
19
Process state diagram
New Admitted Interrupt

Ready Running

Scheduler dispatch
IO event
IO or event wait
completion
Waiting

● Sometimes process is given with time quanta to execute on CPU

● After completion oftime quanta process gets interrupte and removed
from running state to waiting state
20
Process state diagram
New Admitted Interrupt Terminated

Ready Running
Exit

Scheduler dispatch
IO event
IO or event wait
completion
Waiting

● After completion of process execution it moves to terminated state

21
Process Control Block (PCB)
● Every process has Process Control Block (PCB) and Information associated with
a process is stored in PCB
1. Process state - Ready, running, terminated, etc.
2. Process ID - Unique identification number assigned when process gets created.
3. Program counter - Location of the next instruction to be executed
4. CPU registers - Contents of all process centric registers.
5. CPU scheduling information - Priorities, scheduling queue pointers, etc.
6. Memory management information - Memory allocation to process in code,
data, stack and heap segment and their limits.
7. Accounting information - CPU used, clock time elapsed since start, time limits.
8. I/O status information - I/O devices allocated to process, list of open files, etc.

22
Process representation in Linux
● Represented by C structure task_struct
long state; /*denote state of the process */

struct sched entity se; /*denote scheduling information */

struct task struct *parent; /*denotes this process’s parent */

struct list head children; /*denotes this process’s children */

struct files struct *files; /* denotes list of open files */

struct mm struct *mm; /* denotes address space of this process */

struct task struct *p_opptr,*p_pptr,*p_cptr,*p_ysptr,*p_osptr

/*denotes, op = original parent, p = parent, c = youngest child, ys = youngest sibling,

os = older sibling */

23
Process representation in Linux

Process Table
PID PCB

3 PID PID PCB

4 PC PC

Status Status
PCB

24
Process Scheduling
● At any point of time number of processes are ready for the
execution
● Operating system has to decide which process to be executed
next
● The main objective of process scheduling is to maximize CPU
utilization.
● Process “gives” up the CPU under two conditions, IO request and
after N units of time have elapsed
● Once process “gives” up the CPU it is added to the ready queue
● Process scheduler selects among available processes in the
ready queue for the next execution on CPU.

25
Process Scheduling Queues
● OS maintains scheduling queues of process

1. Job queue - Set of all processes in the system

2. Ready queue - set of processes residing in the main memory,
ready and waiting to execute.
3. Device queue - Set of processes waiting for an IO device

Processes migrate among various queues

26
Process Scheduling Queues
Queuing Diagram
Ready Queue CPU

I/O I/O Queue I/O request

Time slice expired

Child
Fork a child
executes

Interrupt Wait for an

occurs interrupt
27
Process - Context switching
● When CPU switches to another process, the system must save the
state of the old process and load the saved state of new process
via a context switch
● Context of the process is represented by PCB
● Context switch time is pure overhead, the system does no useful
work while switching
● More complex OS and PCB implies more overheads of switch
● Time depends on hardware support - some hardware provides
multiple set of registers so that multiple process contexts
loaded/stored

28
Process - Context switching
Process P0 Operating Process P1
System
Executing Interrupt or system call

Save state into PCB0 Idle

Reload state from PCB1

Idle
Interrupt or system call Executing

Save state into PCB1

Idle
Reload state from PCB0
Executing
29
CPU bound vs IO bound process
● A CPU-bound process requires more ● An IO bound process requires less
CPU time CPU time
● Spends more time in the running ● An I/O-bound process spends more
state. time in the waiting state.
● CPU bound means the program is ● I/O bound means the program is
bottlenecked by the CPU bottlenecked by the IO operations
● Spends more time doing ● Spends more time on IO
computations ● I/O bound operations are
● In a CPU-bound environment, most characterized by many and fewer
times, the processor is the only CPU bursts during execution
component being used for execution.
Long IO operation
Short IO burst Short CPU burst

Time -> Time -> 30

Schedulers
1. Selects which process to be executed next
and allocates CPU
2. Sometimes only scheduler
3. Short term scheduler is invoked
frequently (in milliseconds), must be
Short term invoked very fast
4. The choices of the short term scheduler
Scheduler
are very important. If it selects a process
with a long burst time, then all the
processes after that will have to wait for a
long time in the ready queue.
5. This is known as starvation and it may
happen if a wrong decision is made by the
short-term scheduler.

31
Schedulers
1. Selects the processes from the storage
pool in the secondary memory and
loading them into the ready queue in
the main memory for execution.
2. The long-term scheduler controls the
Long term degree of multiprogramming.
Scheduler 3. It must select a careful mixture of I/O
bound and CPU bound processes to
yield optimum system throughput.
4. If it selects too many CPU bound
processes then the I/O devices are idle
and if it selects too many I/O bound
processes then the processor has
nothing to do.

32
Schedulers

1. Medium-term scheduling involves

swapping out a process from main
memory.
Medium term
2. The process can be swapped in later
Scheduler
from the point it stopped executing.
3. This can also be called as
suspending and resuming the
process and is done by the medium-
term scheduler.

33
Operation of Processes
● Process Creation

● Process Termination

34
Process Creation
● A process may create other processes
● Parent process creates children processes, which in turn create other
processes, forming a tree of processes
● Generally a process is identified and managed via process identifier (PID)
Init
Pid = 1

login sshd
Pid = 1234 Pid = 3451

bash Sshd
Pid = 1434 Pid = 8976

A tree of processes in Unix

35
Process Creation
● Fork system call is used for creating a new process, which is called child
process, which runs concurrently with the process that makes the fork()
call (parent process).
● After a new child process is created, both processes will execute the next
instruction following the fork() system call.
● A child process uses the same pc(program counter), same CPU registers,
same open files which use in the parent process.
● It takes no parameters and returns an integer value. Below are different
values returned by fork().
Negative Value: creation of a child process was unsuccessful.
Zero: Returned to the newly created child process.
Positive value: Returned to parent or caller. The value contains process ID
36
of newly created child process.
Process Creation - fork()

fork()
P0 P1

Stack
Stack
Both processes P0 and P1
share the address space
and P1 also executes same
program.
Heap
Heap
Data
Data
COPY Text
Text

Parent process Child process

address space address space
37
Process Creation - fork() program
1. #include <stdio.h> 1. #include <stdio.h>
2. #include <sys/types.h> 2. #include <sys/types.h>
3. #include <unistd.h> 3. int main()
4. int main() 4. {
5. { 5. fork();
6. // make two process which run same
6. fork();
7. // program after this instruction
7. fork();
8. fork();
9. printf("Hello world!\n"); 8. printf("hello\n");
10. return 0; 9. return 0;
11. } 10. }
Output: - Output?
Hello world!
Hello world!

38
Process Creation - fork() and exec()
● fork() system call is used to create a new process
● exec() system call is used after a fork() replaces the process’s memory
space with a new program
● Using fork() a child is duplicate of the parents address space
● Using fork()A child loads program into address space

Wait

Fork

Exec() Exit()
39
Process Creation - fork() and exec()
fork() then exec()
P0 P1

Stack
Stack
Both processes P0 and P1
have separate address
space and P1 now executes
completely different
Heap
Heap program. P1 overwrite
address space copied from Data
Data
P0. Text
Text

Parent process Child process

address space address space
40
Process Creation - Exec() program
1. //EXEC.c 1. #include<stdio.h>
2. #include<stdio.h> 2. #include<stdlib.h>
3. #include<unistd.h> 3. #include<unistd.h>
4. int main() 4. int main()
5. { 5. {
6. int i; 6. //A null terminated array of character
7. printf("I am EXEC.c called by
7. //pointers
execvp() ");
8. char *args[]={"./EXEC",NULL};
8. printf("\n");
9. return 0;
9. execvp(args[0],args);
10.} [Link]("Ending-----");
11. return 0;
12.}
COMPILE AND CREATE EXECUTABLE Compile and Run this program
gcc EXEC.c -o EXEC gcc execDemo.c -o execDemo

41
Process Termination
● A process terminates when it executes its final statement and ask
OS to delete it by using exit() system call
● All the resources allocated to process gets deallocated by the
operating system
● A parent may terminate the execution of child process using
abort system call, some reasons to do so are
1. Child has exceeded allocated resources
2. Task assigned to child is no longer required
3. The parent is exiting and OS does not allow a child to continue if
the parent terminates.

42
Process Termination
1. A parent process may wait till child process terminates using
wait() system call. The call returns status and pid of terminated
process.

pid = wait(&status);

1. A process that has finished the execution but still has an entry in
the process table called as Zombie process
2. An orphan process is a computer process whose parent process
has finished or terminated, though it (child process) remains
running itself.

43
44
45
46
48
55
Threads

56
Threads
● The process model so far considered that a process is a program that performs a
single thread of execution.
● For example, if a process is running a word-processor program, a single thread of
instructions is being executed.
● This single thread of control allows the process to perform only one task at a time.
● For example, user could not simultaneously type in characters and run spell
checker within the same process.
● Many modern OS have extended process concept to allow a process to have
multiple threads of execution thus user will be perform more than one task at a
time.
● Thread is a lightweight process, is a basic unit of CPU utilization. (tid, PC, register
set, stack)

57
Web server example

● If we handle one user at a time it

may lead to starvation to others
● If for each user a separate
process is created:-
● Each process contains
data,text,stack and heap region
● If multiple processes gets created
it becomes very heavy to operate;
takes more time.

58
Web server
Motivation for threads

Let's say there are multiple tasks with a

computer application
1. Displaying graphics,
2. Reading keystrokes from the user
3. Spell check and Grammar

4. Fetch data from web

5. Answer to a network request

59
Motivation for threads

P1 P2

Fetch data Spell Checking

● Two separate processes created for each

operation
● Process creation is heavy weight - code, data,
stack segments, hence switching is also slow.
● If parent child relation between processes
then shared memory needs to be created
which is limited 60
Single vs multi threaded process

Code Data Files Code Data Files

Registers Stack Registers Registers Registers

Stack Stack Stack

Single threaded Multi-threaded process 61

process
Multi-threaded server architecture

Create new thread to service Thread for client 1

request
SERVER

Thread for client 2

Thread for client 3

Client 1 Client 2 Client 3 62

Benefits of multi-threading

Responsiveness - May allow continued execution if part of process is

1 blocked, especially important for user interfaces

Resource sharing - Thread share resources of process easier than

2 shared memory.

Economy - Cheaper than process creation, thread switching

3 overheads are lesser than context switch process overhead

Scalability – process with multiple threads can take advantage of

4 multiprocessor architecture. A single thread process can run on
only one processor, regardless how many are available

63
User threads and kernel threads

Support for threads also provided at two levels

● User threads - Supported above the kernel and are managed
without support of the kernel.
Generally handled by a programmer or by a threads library
● Kernel threads - Supported and managed directly by OS

64
Relationship between user and kernel threads

● Many-to-one
● One-to-one
● Many-to-many

65
Relationship between user and kernel threads

● Many-to-one
● One-to-one User threads
● Many-to-many User space

● Many user level

threads mapped to
one kernel thread
● One thread blocking
cause all to block; Kernel space
entire process will be
blocked.
● Multiple threads may
not run in parallel
because only one Kernel threads
may be in kernel at a
time
66
Relationship between user and kernel threads

● Many-to-one
● One-to-one User threads
● Many-to-many User space

● Whenever a new
thread is created in
user space, a new
thread is created in
kernel space Kernel space
● Each user thread,
kernel thread
handles system calls
● Less blocking at OS
level Kernel threads

67
Relationship between user and kernel threads

● Many-to-one
● One-to-one User threads
● Many-to-many User space

● Allows many user

threads mapped to
many kernel threads
● Allows OS to create
sufficient number of Kernel space
kernel threads

Kernel threads

68
Thread Libraries

● Thread libraries provide programmer with API

creating and managing threads

● Two primary ways of implementing

1. Library entirely in user space
2. Kernel library supported by OS

● Three primary thread libraries

1. POSIX Pthreads
2. Windows threads
3. Java threads
69
Multi-CPU vs Multi-core

Core 0 Core 1

Local Local
Memory Memory
Shared Memory

Storage

● Multiple CPUs placed in a computer ● Multiple cores placed on a single

● Each processor is having its own processor chip
local memory Each core appears as separate CPU
for OS
70
Serial vs concurrency vs parallelism

Serial

● Host is talking with one guest at a time

● While host talking with one guest other
guests wait till his/her chance
● Host communicates with a guest till it
finishes, it doesn’t switch to another
guest in between
Host

71
Serial vs concurrency vs parallelism

Concurrent

● Host is talking with one guest at a time

for one minute
● While host talking with one guest other
guests wait till his/her chance
● Host switch to another guest after one
minute
Host ● Each guest will get time to communicate
with host for some time

72
Serial vs concurrency vs parallelism

Parallel

● Multiple host copies are available

● Each guest is communicating with host
without any intervention

Host

73
Serial vs concurrency vs parallelism

Concurrency +
Parallelism

● Multiple host copies (ghost :-) ) are

available
● Each guest is communicating with two
host concurrently

Host

74