Unit No: 2

Process & Threads

Prepared by: OSD Group,
Dept of Computer, VIIT

1. To understand process & thread concepts & their

working in Linux environment

2. To know significance of context of process
3. To understand deadlock and to simulate it with

real time examples

4. To understand working of init process on Android
device

OSD, TE Computer, VIIT

After the completion of the unit, students

should be able
1. To design the process scheduler for UNIX
like environment
2. To manage IPC using IPC constructs
3. To create single and multi-threaded process
4. To
implement Ostrich and Banker's
algorithm for deadlock avoidance
5. To demonstrate working of init process on
Android device
OSD, TE Computer, VIIT

Process and its management

Shell script
Thread management
Deadlock
Init process in Android

OSD, TE Computer, VIIT

Structure of process
Process states and transition
Context of process
Data structures of process
Components of context of process
Process creation, termination
Signals

OSD, TE Computer, VIIT

A program in execution

An instance of a program running on a

computer
The entity that can be assigned to and
executed on a processor
A unit of activity characterized by the
execution of a sequence of instructions, a
current state, and an associated set of system
instructions

OSD, TE Computer, VIIT

A process is comprised of:

Program code (possibly shared)

A set of data
A number of attributes describing the state of the
process

OSD, TE Computer, VIIT

While the process is running it has a number

of elements including

Identifier
State
Priority
Program counter
Memory pointers
Context data
I/O status information
Accounting information

OSD, TE Computer, VIIT

Contains
the
process
elements
Created and manage by
the operating system
Allows
support
for
multiple processes

OSD, TE Computer, VIIT

Process may be in one of two states

Running
Not-running

OSD, TE Computer, VIIT

10

Etc processes moved by the dispatcher of the OS to the CPU then

back to the queue until the task is competed

OSD, TE Computer, VIIT

11

Creation
New batch job
Interactive Login
Created by OS to
provide a service
Spawned by
existing process

Termination
Normal Completion
Memory
unavailable
Protection error
Operator or OS
Intervention
OSD, TE Computer, VIIT

12

The OS builds a data structure to manage the

process
Traditionally, the OS created all processes
But it can be useful to let a running process create
another

This action is called process spawning

Parent Process is the original, creating, process

Child Process is the new process

OSD, TE Computer, VIIT

13

There must be some way that a process can

indicate completion.
This indication may be:
A HALT instruction generating an interrupt alert to
the OS.
A user action (e.g. log off, quitting an application)
A fault or error
Parent process terminating

OSD, TE Computer, VIIT

14

OSD, TE Computer, VIIT

15

User Running

interrupt,
interrupt return

4
Asleep
in
Memory

sleep

swap
out

Sleep, Swapped

reschedule
process
Ready to
Run in Memory

enough mem
Created
swap
out

wakeup

Preempted

Kernel
Running
preempt

wakeup

return
to user

return

Zombie

system call,
interrupt

swap
in

fork

not enough mem

(swapping system only)

Ready to Run, Swapped

OSD, TE Computer, VIIT

16

Executing in user mode

Executing in kernel mode
Not executing but is ready to run as soon as kernel
schedules it
Process is sleeping and resides in main memory
Process is ready to run but swapper must swap it in
main memory before kernel schedules it for
execution
Process is sleeping and swapped in to secondary
mem.
Process is returning from kernel mode to user mode
, but kernel preempts it
Process is newly created and is in a transition state
Process executed exit system call and is in zombie
state.

OSD, TE Computer, VIIT

17

Kernel Process
Table

Kernel Region
Table

A Process

Per Process Region Table

Text
File Descriptor Table

Data
Stack

U Area
OSD, TE Computer, VIIT

18

Kernel Process table

describes state of every active process
Contains general fields of processes that must
be always be accessible to the kernel

U area
contains additional information that controls
operation of a process
further characteristics of the process only need
to be accessible to the running process itself

OSD, TE Computer, VIIT

19

per process
region table

Kernel region table

u area

Kernel
process table

main memory

OSD, TE Computer, VIIT

20

State field: user running, kernel running

etc
Fields that allow the kernel to locate the
process and u area. Requires while context
switch
Process size : kernel know how much
space to allocate for the process
User ID
Process ID : specify relationship between
processes
OSD, TE Computer, VIIT

21

Event descriptor
Used when the process is in the "sleep" state.

Scheduling parameters
Allow the kernel to determine the order in
which processes move to the states "kernel
running" and "user running

A signal field
keeps the signals sent to a process but not
yet handled

Various

timers:

process
resource utilization etc

execution

OSD, TE Computer, VIIT

time,

22

A pointer to the process table entry

User IDs
various Timer:
Execution time in user mode
Execution Time in kernel mode

An error field: keeps error during system

call
Return value field: result of system call

OSD, TE Computer, VIIT

23

I/O parameters

Amount of data transfer

Address of source and target etc.

The current directory and current root

User file descriptor table : records the files the
process has open
Limit fields
Restrict process size
Restrict size of the file it can write

The control terminal field:

login terminal associated with the process, if one exists

An array indicates how the process wishes to

react to signal
OSD, TE Computer, VIIT

24

System has 3 logical sections : text, data

and stack
A region is contiguous area of virtual
address space of process that can be
treated as shared or protected
Kernel region table contains the pointer to
the page table which keeps the physical
memory address

OSD, TE Computer, VIIT

25

Each process contains private per process

region table
Can be found in process table/u area
Each pregion entry points to the kernel
region table
Starting virtual (absolute) address of the
region
Permission filed:
read-only, read-write, read-execute

OSD, TE Computer, VIIT

26

Region

Per Proc Region Tables

(Virtual Addresses)
Process
A

Text

8K

Data 16K

Stack32K

a
Text

4K

Process
Data 8K
B
Stack

32K

<Processes and Regions>

OSD, TE Computer, VIIT

27

Every mem location = (page no., byte

offset in page)
32 bit addr : 22 bit page no + 10 bit offset

Logical Page Number

0
1
2
3

Physical Page Number

177
54
209
17

OSD, TE Computer, VIIT

28

Per Proc Region Table

Page Tables(Physical Addresses)
Text

8K

empty

Data 32K

137K

Stack 64K

852K
87K

764K

541K

552K

433K

783K

727K

333K

986K

941K

897K

1096K

Virtual Addresses

.
.
.
.
.
.
.
.

2001K

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

<Mapping Virtual Addresses to Physical Address>

OSD, TE Computer, VIIT

29

Size of page is 1K bytes, process wants to

access 68432.
It accesses page 2, and offset 986K

OSD, TE Computer, VIIT

30

Virtual mem. Mapping for kernel is

independent.
The code and data of kernel resides in
system permanently
The kernel page tables are similar to
process PT
Kernel addr. Space 0 to 4M-1
User addr. Space = 4M up
Two sets of mem mgmt triplets : kernel
(kenel mode) and user (user mode)
OSD, TE Computer, VIIT

31

OSD, TE Computer, VIIT

32

Every process has private u area but still

kernel has access to it
The virtual address to u area is assigned at
OS compilation time
Concern module knows the addr.

OSD, TE Computer, VIIT

33

OSD, TE Computer, VIIT

34

Consists of contents of user level,reg. level

and system level
Reg. level context

PC
PSW
SP
General purpose reg.

OSD, TE Computer, VIIT

35

System level :
Static part
State of the process from PT

Dynamic part

OSD, TE Computer, VIIT

36

OSD, TE Computer, VIIT

37

Interrupts and exceptions

If CPU is at lower level than int. level it accepts it
It saves the current reg. context and creates new
layer
Determines source of int. , gets int. no.
Refers IVT
Kernel invokes int. handler
IRET , restores previous context layer
Refer dia.

OSD, TE Computer, VIIT

38

User level context is static part

Region table entry contains
a ptr to inode of the file whose contents loaded
into region
Region type
Location of region in physical mem.
Status of region : locked, in demand, in the
process
Valid
Ref. count

OSD, TE Computer, VIIT

39

Kernel allocates a new region during

fork,exec,shmget sys calls
Kernel has a region table whose entry will
be either on free list or active list
Upload dia.

OSD, TE Computer, VIIT

40

Kernel attaches a newly allocated or

existing shared region
Process should not exceed the system limit
of highest VA.

OSD, TE Computer, VIIT

41

No longer attached region is returned to

list of free region.
If region is associated with inode kernel
releases the inode.
Kernel releases the physical resources e.g
page table, pages

OSD, TE Computer, VIIT

42

Fork call execution

Allocates a slot in the process table

Assigns a unique ID no
It makes a logical copy of context of parent
Increments file and inode table counters
Returns ID to parent and 0 to child

OSD, TE Computer, VIIT

43

Occurrence of asynchronous events.

19 signals in system V
Can be classified as

Termination of process
Signals for process induced exceptions
Unrecoverable conditions during sys call
execution
Signals caused by unexpected error conditions
e.g writing a pipe that has no reader , illegal
ref. in lseek etc
Signals originated from process in UM e.g.
alarm
Related to terminal interaction
Tracing execution of process
OSD, TE Computer, VIIT

44

Shell basics
Shell types
First shell script
Logic : if
Logic : for
Logic : while

OSD, TE Computer, VIIT

45

INPUT

shell

OUTPUT

ERROR
OSD, TE Computer, VIIT

46

Any Program

But there are a few popular shells

OSD, TE Computer, VIIT

47

/bin/sh
/bin/bash
Bourne-Again Shell

OSD, TE Computer, VIIT

48

C Shell (/bin/csh)
Turbo C Shell (/bin/tcsh)
Korn Shell (/bin/ksh)

OSD, TE Computer, VIIT

49

C Shell (/bin/csh)
Turbo C Shell (/bin/tcsh)
Korn Shell (/bin/ksh)

OSD, TE Computer, VIIT

50

/bin, /usr/bin, /usr/local/bin

/sbin, /usr/sbin, /usr/local/sbin
/tmp
/dev
/home/borwicjh

OSD, TE Computer, VIIT

51

A Text File
With Instructions
Executable

OSD, TE Computer, VIIT

52

% cat > hello.sh

#!/bin/sh
echo Hello, world
% chmod +x hello.sh
% ./hello.sh
Hello, world

OSD, TE Computer, VIIT

53

% ./hello.sh
echo vs. /usr/bin/echo
% echo $PATH
/bin:/usr/bin:/usr/local/bin:
/home/borwicjh/bin
% which echo
/usr/bin/echo

OSD, TE Computer, VIIT

54

% hello.sh
bash: hello.sh: Command not found
% PATH=$PATH:.
% hello.sh
Hello, world

OSD, TE Computer, VIIT

55

% echo $USER
$USER
% echo $USER
borwicjh
% echo \

% echo deacnet\\sct
deacnet\sct
% echo \
\

OSD, TE Computer, VIIT

56

OSD, TE Computer, VIIT

57

% echo This \
Is \
A \
Very \
Long \
Command Line
This Is A Very Long Command Line
%

OSD, TE Computer, VIIT

58

$?
0 is True

% ls /does/not/exist
% echo $?
1
% echo $?
0

OSD, TE Computer, VIIT

59

% cat > test.sh

exit 3
% chmod +x test.sh
% ./test.sh
% echo $?
3

OSD, TE Computer, VIIT

60

%
%
0
%
%
1

test 1 -lt 10
echo $?
test 1 == 10
echo $?

OSD, TE Computer, VIIT

61

% echo $(( 1 + 2 ))
3
% echo $(( 2 * 3 ))
6
% echo $(( 1 / 3 ))
0

OSD, TE Computer, VIIT

62

if [ $USER eq borwicjh ]
then
:
# elif a contraction of else if:
elif ls /etc/oratab
then
:
else
then
:
fi

OSD, TE Computer, VIIT

63

# see if a file exists

if [ /etc/passwd ]
then
echo /etc/passwd exists
else
echo /etc/passwd not found!
fi

OSD, TE Computer, VIIT

64

for i in 1 2 3
do
echo $i
done

OSD, TE Computer, VIIT

65

for i in /*
do
echo Listing $i:
ls -l $i
read
done

OSD, TE Computer, VIIT

66

a=0; LIMIT=10
while [ "$a" -lt "$LIMIT" ]
do
echo -n "$a
a=$(( a + 1 ))
done

OSD, TE Computer, VIIT

67

#!/bin/bash
echo "enter maximum number
read n
# taking input from user
echo "enter Numbers in array:
for (( i = 0; i < $n; i++ ))
do
read nos[$i]
done
#printing the number before sorting
echo "Numbers in an array are:
for (( i = 0; i < $n; i++ ))
do
echo ${nos[$i]}
done

OSD, TE Computer, VIIT

68

# Now do the Sorting of numbers

for (( i = 0; i < $n ; i++ ))
do
for (( j = $i; j < $n; j++ ))
do
if [ ${nos[$i]} -gt ${nos[$j]} ]; then
t=${nos[$i]}
nos[$i]=${nos[$j]}
nos[$j]=$t
fi
done
done

OSD, TE Computer, VIIT

69

# Printing the sorted number

echo -e "\nSorted Numbers
for (( i=0; i < $n; i++ ))
do
echo ${nos[$i]}
done

OUTPUT:

pavan@pavan-desktop:~$bash BubbleSort.sh
enter maximum number
4
enter numbers in array:
4
1
0
3

OSD, TE Computer, VIIT

70

Numbers in an array are:

4
1
0
3
Sorted Numbers in Ascending Order:
0
1
3
4
pavan@pavan-desktop:~$

OSD, TE Computer, VIIT

71

Concepts
Various threading models
Fork() & exec() system call
Thread library
Thread cancellation
Thread specific data

OSD, TE Computer, VIIT

72

A basic unit of CPU utilization. It comprises a thread ID, a program counter, a

register set, and a stack. It is a single sequential flow of control within a
program

It shares with other threads belonging to the same process its code section,
data section, and other OS resources, such as open files and signals
A traditional (or heavyweight) process has a single thread of control
If a process has multiple threads of control, it can perform more than one
task at a time. Threads are a way for a program to split itself into two or
more simultaneously running tasks. That is the real excitement surrounding
threads
OSD, TE Computer, VIIT

73

OSD, TE Computer, VIIT

74

 A word processor may have a threads for

displaying graphics
responding to keystrokes from the user
performing spelling and grammar checking in the
background

OSD, TE Computer, VIIT

75

OSD, TE Computer, VIIT

76

Imagine the following C program

main() {
ComputePI(pi.txt);
PrintClassList(clist.text);
}

What is the behaviour here?

OSD, TE Computer, VIIT

77

Version of program with Threads

main() {
CreateThread(ComputePI(pi.txt));
CreateThread(PrintClassList(clist.text));
}

What does CreateThread do?

Start independent thread running given procedure

What is the behavior here?

This should behave as if there are two separate CPUs

CPU1

CPU2

CPU1

CPU2

CPU1

CPU2

Time
OSD, TE Computer, VIIT

78

If we stopped this program and examined it

with a debugger, we would see

Two sets of CPU registers

Stack 1

Two sets of Stacks

Heap

Address Space

Stack 2

Global Data
Code
OSD, TE Computer, VIIT

79

Each Thread has a Thread Control Block (TCB)

Execution State: CPU registers, program counter, pointer to
stack
Scheduling info: State (more later), priority, CPU time
Accounting Info

Various Pointers (for implementing scheduling queues)

Pointer to enclosing process (PCB)
Etc

OSD, TE Computer, VIIT

80

Responsiveness

Resource Sharing

Economy

Utilization of MP Architectures

OSD, TE Computer, VIIT

81

Support for threads may be provided either at the

user level, for user threads (supported above the
kernel and managed without kernel support), or by
the kernel, for kernel threads (supported and
managed directly by the OS)

Three common ways of establishing relationship

between user and kernel threads
Many-to-One
One-to-One
Many-to-Many

OSD, TE Computer, VIIT

82

Thread management done by user-level threads

library

Three primary thread libraries

POSIX Pthreads
Win32 threads
Java threads

OSD, TE Computer, VIIT

83

Supported by the Kernel

Examples

Windows XP/2000
Solaris
Linux
Tru64 UNIX
Mac OS X

OSD, TE Computer, VIIT

84

Many user-level threads mapped to single kernel

thread

OSD, TE Computer, VIIT

85

Basically, the kernel is not aware of the existence

of threads.
Thread switching does not require kernel mode
privileges and scheduling is application specific.
Thread management is done by the thread library
in user space, so it is efficient
Just as a uniprocessor provides the illusion of
parallelism by multiplexing multiple processes on a
single CPU, user-level threads packages provide
the illusion of parallelism by multiplexing multiple
user threads on a single kernel thread
OSD, TE Computer, VIIT

86

Since there is only one kernel thread, if a user

thread executes a blocking system call, the entire

process blocks, since no other user thread can
execute until the kernel thread (which is blocked in
the system call) becomes available

Multithreaded programs will run no faster on

multiprocessors than they run on uniprocessors.

The single kernel thread acts as a bottleneck,

preventing optimal use of the multiprocessor
OSD, TE Computer, VIIT

87

Advantages
Thread switching does not involve kernel no mode switching
Scheduling
algorithm

can

be

application

specific

choose

best

ULTs can run on any OS only needs a thread library

Disadvantages
Most system calls are blocking and the kernel blocks processes
all threads within the process will be blocked
Kernel can only assign processes to processors threads
within same process cannot run simultaneously on processors

OSD, TE Computer, VIIT

88

Each user-level thread maps to kernel thread

OSD, TE Computer, VIIT

89

Because each kernel thread is actually a different kernelschedulable entity, multiple threads can run concurrently on
different processors
Can achieve significant speedups
uniprocessors to multiprocessors

when

migrated

from

Unlike the many-to-one model, threads blocking in the

kernel do not impede process progress under the one-to-one
model.
The only drawback is that creating a user thread requires
creating the corresponding kernel thread
Overhead of creating kernel threads can burden the performance
of the application

OSD, TE Computer, VIIT

90

Allows many user-level threads to be mapped to many

kernel threads

Idea is to combine the best of both approaches

OSD, TE Computer, VIIT

91

A thread library provides the programmer with an

API for creating and managing threads
Two primary ways of implementing a thread library
Provide the library entirely in user space with no kernel
support.
Implement kernel-level library supported directly by the OS.
Three main thread libraries in use today: (1) POSIX
Pthreads, (2) Win32, and (3) Java

OSD, TE Computer, VIIT

92

Example: Design a multithreaded program

that performs the following summation in a

separate thread

sum =

i=0

OSD, TE Computer, VIIT

93

#include <pthread.h>
#include <stdio.h>
int sum; //this data is shared by the thread(s)

void *runner(void *param); // the thread

main(int argc, char* argv[])
{
pthread_t tid; // the thread identifier
pthread_create(&tid,NULL,runner,argv[1]); // create thread
pthread_join(tid,NULL); // now wait for the thread to exit
printf("sum = %d\n",sum);
}

OSD, TE Computer, VIIT

94

void *runner(void *param) {

int upper = atoi(param);

int i;
sum = 0;
if (upper > 0) {
for (i = 1; i <= upper; i++)
sum += i;
}
pthread_exit(0);
}

OSD, TE Computer, VIIT

95

Semantics of fork() and exec() system calls

Thread cancellation of target thread

Asynchronous or deferred

Signal handling
Thread pools
Thread-specific data
Scheduler activations

OSD, TE Computer, VIIT

96

Terminating a thread before it has finished

Two general approaches:
Asynchronous cancellation terminates the target
thread immediately
Deferred cancellation allows the target thread to
periodically check if it should be cancelled

OSD, TE Computer, VIIT

97

If one thread in a program calls fork(), does the

new process duplicate only the calling thread or all

threads?
Some UNIX systems provide two versions of fork()
One duplicates all threads
The other duplicates only the thread that invoked fork()

If a thread invokes exec(), the program specified

in the parameter to exec() will replace the entire

process including all threads

OSD, TE Computer, VIIT

98

Signals are used in UNIX systems to notify a

process that a particular event has occurred
A signal handler is used to process signals
1. Signal is generated by particular event
2. Signal is delivered to a process
3. Signal is handled

Options:
Deliver the signal to the thread to which the signal
applies
Deliver the signal to every thread in the process
Deliver the signal to certain threads in the process
Assign a specific thread to receive all signals for the
process

OSD, TE Computer, VIIT

99

Create a number of threads in a pool where

they await work
Advantages:
Usually slightly faster to service a request with an
existing thread than create a new thread
Allows the number of threads in the application(s) to
be bound to the size of the pool

OSD, TE Computer, VIIT

10
0

Allows each thread to have its own copy of

data
Useful when you do not have control over
the thread creation process (i.e., when
using a thread pool)

OSD, TE Computer, VIIT

10
1

OSD, TE Computer, VIIT

10
2

Linux refers to them as tasks rather than

threads

Thread creation is done through clone()

system call

clone() allows a child task to share the

address space of the parent task (process)

OSD, TE Computer, VIIT

10
3

Concepts
Principles of deadlock
Deadlock strategies

Prevention
Avoidance
Detection
Recovery

Ostrich algorithm
Bankers algorithm

OSD, TE Computer, VIIT

10
4

A set of processes is deadlocked when each

process in the set is blocked awaiting an
event that can only be triggered by another
blocked process in the set
Typically involves processes competing for the
same set of resources

No efficient solution

OSD, TE Computer, VIIT

10
5

I need
quad C
and B

I need
quad B
and C

I need
quad A
and B

I need
quad D
and A
OSD, TE Computer, VIIT

10
6

HALT until
D is free

HALT until
C is free

HALT until
B is free

HALT until
A is free

OSD, TE Computer, VIIT

10
7

OSD, TE Computer, VIIT

10
8

Lets look at this with

two processes P and Q
Each needing exclusive
access to a resource A
and B for a period of
time

OSD, TE Computer, VIIT

10
9

Consider a pair of processes, in which each

process attempts to receive a message from
the other process and then send a message
to the other process

OSD, TE Computer, VIIT

11
0

OSD, TE Computer, VIIT

11
1

Devise a ritual (algorithm) that will allow the

philosophers to eat.
No two philosophers can use the same fork at the
same time (mutual exclusion)
No philosopher must starve to death (avoid
deadlock and starvation literally!)

OSD, TE Computer, VIIT

11
2

OSD, TE Computer, VIIT

11
3

OSD, TE Computer, VIIT

11
4

Directed graph that depicts a state of the

system of resources and processes

OSD, TE Computer, VIIT

11
5

Mutual exclusion (non-sharable resources)

Only one process may use a resource at a time

Hold-and-wait
A process may hold allocated resources while
awaiting assignment of others

No pre-emption
No resource can be forcibly removed from a
process holding it

OSD, TE Computer, VIIT

11
6

All previous 3 conditions plus:

Circular wait
A closed chain of processes exists, such that each
process holds at least one resource needed by the
next process in the chain

OSD, TE Computer, VIIT

11
7

OSD, TE Computer, VIIT

11
8

OSD, TE Computer, VIIT

11
9

Three general approaches exist for dealing

with deadlock.
Prevent deadlock
Avoid deadlock
Detect Deadlock

OSD, TE Computer, VIIT

12
0

Design a system in such a way that the

possibility of deadlock is excluded.
Two main methods
Indirect prevent one of the three necessary
conditions from occurring
Direct prevent circular waits

OSD, TE Computer, VIIT

12
1

Mutual Exclusion

Hold and Wait

No Preemption

Circular Wait

Must be supported by the OS

Require a process request all of its required
resources at one time
Process must release resource and request again
OS may preempt a process to require it releases
its resources

Define a linear ordering of resource types

OSD, TE Computer, VIIT

12
2

It is a strategy of ignoring potential problems on

the basis that they may be exceedingly rare
It is named for the ostrich effect, i.e. to stick
ones head in the sand and pretend there is no
problem
This assumes that it is more cost effective to
allow problem to occur than to attempt its
prevention
UNIX and Windows takes this approach.
It is trade-off between convenience &
correctness
OSD, TE Computer, VIIT

12
3

A decision is made dynamically whether the

current resource allocation request will, if
granted, potentially lead to a deadlock
Requires knowledge of future process
requests

OSD, TE Computer, VIIT

12
4

Process Initiation Denial

Do not start a process if its demands might lead to
deadlock

Resource Allocation Denial

Do not grant an incremental resource request to a
process if this allocation might lead to deadlock

OSD, TE Computer, VIIT

12
5

A process is only started if the maximum

claim of all current processes plus those of
the new process can be met.
Not optimal,
Assumes the worst: that all processes will make
their maximum claims together.

OSD, TE Computer, VIIT

12
6

Referred to as the bankers algorithm

A strategy of resource allocation denial

Consider a system with fixed number of

resources
State of the system is the current allocation of
resources to process
Safe state is where there is at least one sequence
that does not result in deadlock
Unsafe state is a state that is not safe

OSD, TE Computer, VIIT

12
7

When a process makes a request for a set of

resources,
assume that the request is granted,
Update the system state accordingly,
Then, determine if the result is a safe state.
If so, grant the request
if not, block the process until it is safe to grant the
request.

OSD, TE Computer, VIIT

12
8

OSD, TE Computer, VIIT

12
9

OSD, TE Computer, VIIT

13
0

OSD, TE Computer, VIIT

13
1

OSD, TE Computer, VIIT

13
2

Maximum resource requirement must be

stated in advance
Processes under consideration must be
independent and with no synchronization
requirements
There must be a fixed number of resources to
allocate
No process may exit while holding resources

OSD, TE Computer, VIIT

13
3

Deadlock prevention
conservative;

strategies

are

very

limit access to resources and impose restrictions on

processes.

Deadlock detection strategies do the opposite

Resource requests are granted whenever possible.
Regularly check for deadlock

OSD, TE Computer, VIIT

13
4

Abort all deadlocked processes

Back up each deadlocked process to some
previously defined checkpoint, and restart all
process
Risk or deadlock recurring

Successively abort deadlocked processes until

deadlock no longer exists
Successively
preempt
resources
until
deadlock no longer exists

OSD, TE Computer, VIIT

13
5

OSD, TE Computer, VIIT

13
6

About Android
Android boot process / sequence

OSD, TE Computer, VIIT

137

It is Linux-based open source operating

system
All android devices runs on ARM (Advanced
RISC Machine) process, except Intels Xolo
device
Android boot sequence has minor difference
compare to desktop version
Next slide explain boot sequence of Android
device

OSD, TE Computer, VIIT

13
8

OSD, TE Computer, VIIT

13
9

Step 1 : power on and system start up

When power start Boot ROM code start execution
from pre defined location which is hardwired on
ROM
It load Bootloader into RAM and start execution

Step 2 : bootloader
Bootloader is small program which runs before
Android operating system running
Popular bootloader - redboot, uboot, qi bootloader
Android bootloader can be found at - <Android
Source>\bootable\bootloader\legacy\usbloader

OSD, TE Computer, VIIT

14
0

Step 3 : kernel

Android kernel start similar as desktop Linux kernel

starts
When kernel finish system setup, it first look for
init in file system

Step 4 : init process

It is very first process.

Treated as ancestor of all processes
It
is
can
be
found
at
source>/system/core/init
And
init.rc
at
source>/system/core/rootdir/init.rc

OSD, TE Computer, VIIT

<android
<android

14
1

Step 5 : Zygote and Dalvik

Zygote enable shared code across Dalvik VM, lower
memory footprint and minimal startup time
Zygote is a VM process that starts at system boot
Zygote preloads and initialize core library classes

Step 6 : system service

After completion of above steps, system servers are
started
System servers are considered as process, which is
written in native and Java both

OSD, TE Computer, VIIT

14
2

1.

Explain five state process model with diagram

2.

Explain with examples, process scheduling algorithms:

FSFC, Priority, SJF, RR

3.

Compare above process scheduling algorithms

4.

Explain with diagram saving context of process

5.

Is operating system itself a process? Justify your answer.

6.

Compare and contrast process with thread.

7.

Explain with suitable diagram multi-threading models.

OSD, TE Computer, VIIT

14
3

8. Write short notes on popular thread library (For eg, POSIX, Java, Win32)
9. What do you understand by deadlock? How deadlock can be prevented?
10. What do you understand by deadlock? How deadlock can be avoided?
11. What do you understand by deadlock? How deadlock can be detected?
12. Is deadlock prevention is better than deadlock avoidance ? Justify your

answer
13. Explain with example Banker algorithm
14. Write notes on ostrich algorithm
15. Explain in details six steps of Android boot process

OSD, TE Computer, VIIT

14
4

[1] William Stalling, Operating Systems: Internals and Design

Principles, 6/E, Prentice Hall
[2] Maurice J. Bach, The Design of UNIX Operating System, PHI,
ISBN 978-81-203-0516-8
[3]

www.wfu.edu/~borwicjh/presentations/UNIX

Shell-Scripting

Basics.ppt
[4] cse.stfx.ca/~mlin/cs375/lectures/thread.ppt
[5]

http://www.kpbird.com/2012/11/in-depth-android-boot-sequence-

process.html

OSD, TE Computer, VIIT

14
5

Thank You
OSD, TE Computer, VIIT

14
6