UNIT – II

Linux: Introduction to shell, Types of shell's , example shell programs.

Process and CPU Scheduling - Process concepts and scheduling, Operations on
processes, CooperatingProcesses, Threads, Scheduling Criteria, Scheduling
Algorithms, Multiple -Processor Scheduling.

Shell Programming
The shell has similarities to the DOS command processor Command.com
(actually Dos was design as a poor copy of UNIX shell), it's actually much
more powerful, really a programming language in its own right.

A shell is always available on even the most basic UNIX installation. You have
to go through the shell to get other programs to run. You can write programs
using the shell. You use the shell to administrate your UNIX system. For
example:

ls -al | more
is a short shell program to get a long listing of the present directory and route
the output through the more command.
What is a Shell?

A shell is a program that acts as the interface between you and the UNIX
system, allowing you to enter commands for the operating system to execute.

Here are some common shells.

Introduction- Working with Bourne Shell

• The Bourne shell, or sh, was the default Unix shell of Unix Version 7. It was developed by
Stephen Bourne, of AT&T Bell Laboratories.
• A Unix shell, also called "the command line", provides the traditional user interface forthe Unix
operating system and for Unix-like systems. Users direct the operation of the computer by entering
command input as text for a shell to execute.
• There are many different shells in use. Theyare
– Bourne shell (sh)
– C shell (csh)
– Korn shell (ksh)Bourne Again shell (bash)

• When we issue a command the shell is the first agency to acquire the information. Itaccepts and
interprets user requests. The shell examines &rebuilds the commands &leaves the execution work to
kernel. The kernel handles the h/w on behalf ofthesecommands &all processes in the system.
• The shell is generally sleeping. It wakes up when an input is keyed in at the prompt. Thisinput is
actually input to the program that represents the shell.

Shell responsibilities
1. Program Execution
2. Variable and Filename Substitution
3. I/O Redirection
4. Pipeline Hookup
5. Environment Control
6. Interpreted Programming Language1.Program Execution:
• The shell is responsible for the execution of all programs that you request fromyourterminal.
• Each time you type in a line to the shell, the shell analyzes the line and thendetermineswhat to
do.

26
• The line that is typed to the shell is known more formallyas the command line. The shellscans
this command line and determines the name of the program to be executed and what arguments to pass to
the program.
2. Variable and Filename Substitution:
• Like any other programming language, the shell lets you assign values to variables. Whenever
you specify one of these variables on the command line, preceded by adollarsign, the shell substitutes the
value assigned to the variable at that point.
3. I/O Redirection:
• It is the shell's responsibility to take care of input and output redirection on the commandline.
It scans the command line for the occurrence of the special redirection characters <,
>, or >>.
4. Pipeline Hookup:
• Just as the shell scans the command line looking for redirection characters, it also looks for
the pipe character |. For each such character that it finds, it connects the standard output from the
command preceding the | to the standard input of the one following the|.It then initiates execution of both
programs.
5. Environment Control:

• The shell provides certain commands that let you customize your environment. Your
environment includes home directory, the characters that the shell displays to prompt you
to type in a command, and a list of the directories to be searched whenever you requestthat a program be
executed.
6. Interpreted Programming Language:

• The shell has its own built-in programming language. This language is interpreted, meaning
that the shell analyzes each statement in the language one line at a time and thenexecutes it. This differs
from programming languages such as C and FORTRAN, in which the programming statements are
typically compiled into a machine-executable form before they are executed.
• Programs developed in interpreted programming languages are typically easier to debug and
modify than compiled ones. However, they usually take much longer to execute than their compiled
equivalents.

Pipes connect processes together. The input and output of UNIX programs can be redirected.

Redirecting Output

The > operator is used to redirect output of a program. For example:ls -l > lsoutput.txt
redirects the output of the list command from the screen to the file lsoutput.txt.

To 0append to a file, use the >> operator.

Pipes and Redirection

ps >> lsoutput.txt

Redirecting Input
27
You redirect input by using the < operator. For example:more < killout.txt

Pipes

We can connect processes together using the pipe operator ( | ). For example, the followingprogram means
run the ps program, sort its output, and save it in the file pssort.out

ps | sort > pssort.out

The sort command will sort the list of words in a textfile into alphbetical order according to the ASCII
code set character order.

Here Documents
A here document is a special way of passing input to a command from a shell script. Thedocument starts
and ends with the same leader after <<. For example:

#!/bin/sh

cat < this is a heredocument

!FUNKY!

How It Works

It executes the here document as if it were input commands.

Running a Shell Script

You can type in a sequence of commands and allow the shell to execute them interactively, oryouu can sotre
these commands in a file which you can invoke as a program.

Interactive Programs

A quick way of trying out small code fragments is to just type in the shell script on the commandline. Here
is a shell program to compile only files that contain the string POSIX.

The hell as a Programming LanguageCreating a Script

To create a shell script first use a text editor to create a file containing the commands. Forexample, type
the following commands and save them as first.sh

28
Note: commands start with a #.

The line

#!/bin/sh
is special and tells the system to use the /bin/sh program to execute this program.

The command
exit 0
Causes the script program to exit and return a value of 0, which means there were not errors.
Making a Script Executable
There are two ways to execute the script. 1) invoke the shell with the name of the script file as aparameter,
thus:/bin/sh first.sh
Or 2) change the mode of the script to executable and then after execute it by just typing itsname.
chmod +x first.shfirst.sh
Actually, you may need to type:
./first.sh to make the file execute unles the path variable has your directory in it.

Shell Syntax
The modern UNIX shell can be used to write quite large, structured programs.
Shell metacharacters

The shell consists of large no. of metacharacters. These characters plays vital role in Unixprogramming.

Types of metacharacters:

29
1.File substitution

2.I/O redirection

3.Process execution

4. Quoting metacharacters

5. Positionalparameters

6.Special characters

7.Command substitution

Filename substitution:

These metacharacters are used to match the filenames in a directory.

Metacharacter significance

* matches any no. of characters

? matches a single character

[ijk] matches a single character either i,j,k

[!ijk] matches a single character that is not an I,j,k

Shell Variables

Variables are generally created when you first use them. By default, all variables are consideredand stored
as strings. Variable names are case sensitive.

U can define & use variables both in the command line and shell scripts. These variablesare called shell
variables.
No type declaration is necessary before u can use a shellvariable.

30
 Variables provide the ability to store and manipulate the information with in the shell program. The
variables are completely under the control ofuser.

Variables in Unix are of two types.

1) User-defined variables:

Generalized form:

variable=value.Eg: $x=10

$echo $x10

To remove a variable use unset.

$unset x

All shell variables are initialized to null strings by default. To explicitly set null valuesuse

x= or x=‗‘ or x=―‖

To assign multiword strings to a variable use

$msg=‗u have a mail‘

2) Environment Variables

 They are initialized when the shell script starts and normallycapitalized to distinguish them from user-
defined variables in scripts
 To display all variables in the local shell and their values, type the set command
 The unset command removes the variable from the current shell and subshell

Environment Description
Variables
$HOME Home directory
$PATH List of directories to search for
commands
$PS1 Command prompt
$PS2 Secondary prompt
$SHELL Current login shell
$0 Name of the shell script

$# No . of parameters passed
$$ Process ID of the shell script

31
 Command substitution and Shell commands:

read:

 The read statement is a tool for taking input from the user i.e. making scripts interactive It is used
with one or more variables. Input supplied through the standard input is read into these variables.

$read name
What ever u entered is stored in the variablename. printf:

Printf is used to print formattedo/p. printf "format" arg1 arg2 ...Eg:

$ printf "This is a number: %d\n" 10This is a number: 10

$
Printf supports conversion specification characters like %d, %s ,%x

,%o…. Exit status of a command:

o Every command returns a value after execution .This value is called the exitstatus or return
value of a command.
o This value is said to be true if the command executes successfully and false if it fails.
o There is special parameter used by the shell it is the $?. It stores the exit status of a
command.

exit:

o The exit statement is used to prematurely terminate a program. When this statement is
encountered in a script, execution is halted and control is returned to the calling program- in most cases the
shell.
o U don‘t need to place exit at the end of every shell script because the shell knows when
script execution is complete.
o Set :

Set is used to produce the list of currently defined variables.

$set

32
 Set is used to assign values to the positional parameters.

$set welcome to Unix

The do-nothing( : )Command

It is a null command.
In some older shell scripts, colon was used at the start of a line to introduce acomment,
but modern scripts uses # now.
expr:
The expr command evaluates its arguments as an expression:
$ expr 8 + 6
$ x=`expr 12 / 4 `
$ echo $x3

export:
There is a way to make the value of a variable known to a sub shell, and that'sby exporting it
with the export command. The format of this command is

export variables

where variables is the list of variable names that you want exported. For any sub shells that get executed
from that point on, the value of the exported variables will bepassed down to the sub shell.

eval:

eval scans the command line twice before executing it. General form for evalis eval command-line

Eg:

$ cat last

eval echo \$$#

$ last one two three fourfour

${n}

If u supply more than nine arguments to a program, u cannot access the tenth and greater arguments with
$10, $11, and so on.

${n} must be used. So to directly access argument 10, you must write

33
${10}

Shift command:

The shift command allows u to effectively left shift your positional parameters. If u executethe command

Shift

whatever was previously stored inside $2 will be assigned to $1, whatever was previouslystored in $3 will
be assigned to $2, and so on. The old value of $1 will be irretrievably lost.

The Environment-Environment Variables

It creates the variable salutation, displays its value, and some parameter variables.

• When a shell starts, some variables are initialized from values in the environment. Here is a
sample of some ofthem.

Parameter Variables
• If your script is invoked with parameters, some additional variables are created.

Quoting

Normally, parameters are separated by white space, such as a space. Single quot marks can be used to
enclose values containing space(s). Type the following into a file called quot.sh

34
make sure to make it executable by typing the command:

< chmod a+xquot.sh The results of executing

the file is:

How It Works

The variable myvar is created and assigned the string Hi there. The content of the variable is displyed using
the echo $. Double quotes don't effect echoing the value. Single quotes and backslash do.

The test, or []Command

Here is how to check for the existance of the file fred.c using the test and using the []command.

You can even place the then on the same line as the if, if youu add a semicolon before theword then.

Here are the conditon types that can be used with the test command. There are stringcomparison.

35
There are arithmetic comparison.

There are file conditions.

Control Structures

The shell has a set of control structures.

if

The if statement is vary similar other programming languages except it ends with a fi.if condition
then
statementsstatements
else fi

36
elif

the elif is better known as "else if". It replaces the else part of an if statement with another ifstatement.
You can try it out by using the following script.
#!/bin/sh

echo "Is it morning? Please answer yes or no"read timeofday

if [ $ti0meofday = "yes" ]then

echo "Good morning"elif [ $timeofday = "no" ]; thenecho "Good afternoon"
else
echo "Sorry, $timeofday not recognized. Enter yesor no" exit 1 fi

exit 0

How It Works

The above does a second test on the variable timeofday if it isn't equal to yes.

A Problem with Variables

If a variable is set to null, the statement

if [ $timeofday = "yes" ]if [ = "yes" ]
which is illegal. This problem can be fixed by using double quotes around the variable name. if [
"$timeofday" = "yes" ]
.
for

The for construct is used for looping through a range of values, which can be any set of strings.The syntax
is:

for variable in valuesdo

statements
done
Try out the following script:
#!/bin/sh

for foo in bar fud 43do

echo $foo
done exit 0
When executed, the output should be:
bar fud043
How It Works
The above example creates the variable foo and assigns it a different value each time around thefor loop.
How It Works
Here is another script which uses the $(command) syntax to expand a list to chap3.txt, chap4.txt, and
chap5.txt and print the files.

#!/bin/sh

37
for file in $(ls chap[345].txt); dolpr $file
done0
while

While loops will loop as long as some condition exist. OF course something in the body statements of the
loop should eventually change the condition and cause the loop to exit. Here is the while loop syntax.

while condition do
statements
done
Here is a whil loop that loops 20 times.#!/bin/sh

foo=1

while [ "$foo" -le 20 ]do

done exit 0

How It Works
echo "Here we go again" foo=$(($foo+1))

The above script uses the [ ] command to test foo for <= the value 20. The linefoo=$(($fo0o+1))
increments the value of foo each time the loop executes..

until

The until statement loops until a condition becomes true! Its syntax is:

until conditiondo
statements
done
Here is a script using until.
#!/bin/sh

until who | grep "$1" > /dev/nulldo

Sl0eep 60
done

# now ring the bell and announce the expected user.

echo -e \\a
echo "**** $1 has just loogged in ****"exit 0

case

The case statement allows the testing of a variable for more then one value. The case statementends with
the word esac. Its syntax is:

case variable in
pattern [ | pattern] ...) statements;;pattern [ | pattern] ...) statements;;

38
...
esac
Here is a sample script using a case statement:
#!/bin/sh

echo "Is it morning? Please answer yes or no"read timeofday

case "$timeofday" in
"yes") echo "Good Morning";; "no" ) echo "Good Afternoon";; 0"y" ) echo "Good Morning";; "n" ) echo
"Good Afternoon";;
* ) echo "Soory, answer not recognized";;
esac exit 0

The value in the varaible timeofday is compared to various strings. When a match is made, theassociated
echo command is executed.

Here is a case where multiple strings are tested at a time, to do the some action.case "$timeofday" in
"yes" | "y" | "yes" | "YES" ) echo "good Morning";;"n"* | "N"* ) <echo "Good Afternoon";;
* ) < echo "Sorry, answer not recognized";;
0esac

How It Works

The above has sever strings tested for each possible statement.

Here is a case statement that executes multiple statements for each case.case "$timeofday" in
"yes" | "y" | "Yes" | "YES" )echo "Good Morning"
echo "Up bright and early this morning"
;;
[nN
]*) echo "Good Afternoon"
;;

*) echo "Sorry, answer not recognized" echo "Please answer yes or

noo" exit 1
;;
esac

How It Works

39
When a match is found to the variable value of timeofday, all the statements up to the ;; areexecuted.
Parameter Expansion

Using { } around a variable to protect it against expansion.#!/bin/sh

for i in 1 2do
my_secret_process ${i}_tmp
done
Here are some of the parameter expansion

How It Works

The try it out exercise uses parameter expansion to demonstrate how parameter expansion works.

Shell Script ExamplesExample

#!/bin/sh

echo "Is it morning? (Answer yes or no)"read timeofday

if [ $timeofday = "yes" ]; then

echo "Good Morning"

else

echo "Good afternoon"

fi exit 0

elif - Doing further Checks

#!/bin/sh

echo "Is it morning? Please answer yes or no"read timeofday

if [ $timeofday = "yes" ]; thenecho "Good Morning"

40
elif [ $timeofday = "no" ]; thenecho "Good afternoon"

else echo "Wrong answer! Enter yes or no"exit 1

fi exit 0

Process
A process is a program at the time of execution.
Differences between Process and Program

Process Program
Process is a dynamic object Program is a static object

Process is sequence of instruction Program is a sequence of instructions

execution
Process loaded in to main memory Program loaded into secondarystorage
devices
Time span of process is limited Time span of program is unlimited
Process is a active entity Program is a passive entity

Process States

When a process executed, it changes the state, generally the state of process is
determined by the current activity of the process. Each process may be in one of the
following states:
1. New : The process is being created.
2. Running : The process is being executed.
3. Waiting : The process is waiting for some event to occur.
4. Ready : The process is waiting to be assigned to a processor.
5. Terminated : The Process has finished execution.
Only one process can be running in any processor at any time, But many process may be
inready and waiting states. The ready processes are loaded into a “ready queue”.
Diagram of process state

41
a) New ->Ready : OS creates process and prepares the process to be executed, then OS
moved the process into ready queue.
b) Ready->Running : OS selects one of the Jobs from ready Queue and move themfrom ready
to Running.

c) Running->Terminated : When the Execution of a process has Completed, OS terminates that process
from running state. Sometimes OS terminates the process for some other reasons including Time exceeded,
memory unavailable, access violation, protection Error, I/O failure and soon.
d) Running->Ready : When the time slot of the processor expired (or) If the processor received any
interrupt signal, the OS shifted Running -> Ready State.

e) Running -> Waiting : A process is put into the waiting state, if the process need anevent occur (or) an
I/O Device require.
f) Waiting->Ready : A process in the waiting state is moved to readystate when the event for which it
has been Completed.
Process Control Block:

Each process is represented in the operating System by a Process Control Block.

It is also called Task Control Block. It contains many pieces of information associated with a specific
Process.

Process State

Program Counter

CPU Registers

CPU Scheduling Information

Memory – Management Information

Accounting Information

I/O Status Information

Process Control Block

1. Process State : The State may be new, ready, running, and waiting, Terminated…
2. Program Counter : indicates the Address of the next Instruction to be executed.
3. CPUregisters : registers include accumulators, stack pointers,
General purpose Registers….

42
4. CPU-Scheduling Info : includes a process pointer, pointers to
scheduling Queues, other scheduling parameters etc.
5. Memory management Info: includes page tables, segmentation tables, value ofbase and limit
registers.
6. Accounting Information: includes amount of CPU used, time limits, Jobs(or)Process numbers.
7. I/O Status Information: Includes the list of I/O Devices Allocated to the processes, list ofopen
files.

Threads:

A process is divide into number of light weight process, each light weight process is said to be a Thread.
The Thread has a program counter (Keeps track of which instruction to execute next), registers (holds its
current working variables), stack (execution History).
Thread States:

1. born State : A thread is just created.

2. ready state : The thread is waiting for CPU.
3. running : System assigns the processor to the thread.
4. sleep : A sleeping thread becomes ready after the designated sleep time expires.
5. dead : The Execution of the thread finished.

Egg: Word processor.

Typing, Formatting, Spell check, saving are threads.
Differences between Process and Thread

Process Thread
Process takes more time to create. Thread takes less time to create.
it takes more time to complete execution & Less time to terminate.
terminate.
Execution is very slow. Execution is very fast.
It takes more time to switch b/w two It takes less time to switch b/w two
processes. threads.
Communication b/w two processes is difficult . Communication b/w two threads is
easy.
Process can’t share the same memory area. Threads can share same memory area.
System calls are requested to communicate System calls are not required.
each other.
Process is loosely coupled. Threads are tightly coupled.
It requires more resources to execute. Requires few resources to execute.

43
 Multithreading
A process is divided into number of smaller tasks each task is called a Thread. Number ofThreads with in a
Process execute at a time is called Multithreading.
If a program, is multithreaded, even when some portion of it is blocked, the whole program is not blocked.
The rest of the program continues working If multiple CPU’s are available.
Multithreading gives best performance. If we have only a single thread, number of CPU’s available, No
performance benefits achieved.
 Process creation is heavy-weight while thread creation is light-weight Can simplify code, increase
efficiency

Kernels are generally multithreaded

CODE- Contains instruction
DATA- holds global variable
FILES-opening and closing files
REGISTER- contain information about CPU state
STACK-parameters, local variables, functions

PROCESS SCHEDULING:

CPU is always busy in Multiprogramming. Because CPU switches from one job to another job. But in
simple computers CPU sit idle until the I/O request granted.
scheduling is a important OS function. All resources are scheduled before use.(cpu, memory, devices…..)
Process scheduling is an essential part of a Multiprogramming operating systems. Such operating systems
allow more than one process to be loaded into the executable memory ata time and the loaded process shares
the CPU using time multiplexing
. Scheduling Objectives
Maximize throughput.
Maximize number of users receiving acceptable response times.Be predictable.
Balance resource use.
44
Avoid indefinite postponement.
Enforce Priorities.
Give preference to processes holding key resources

SCHEDULING QUEUES: people live in rooms. Process are present in rooms knows as queues. There are
3types
1. job queue: when processes enter the system, they are put into a job queue, which consists all
processes in the system. Processes in the job queue reside on mass storage and await the allocation of main
memory.
2. ready queue: if a process is present in main memory and is ready to be allocated tocpu for execution,
is kept in ready queue.
3. device queue: if a process is present in waiting state (or) waiting for an i/o event tocomplete is said to
bein device queue.(or)
The processes waiting for a particular I/O device is called device queue.

Schedulers : There are 3 schedulers

1. Long term scheduler.

2. Medium termscheduler
3. Short term scheduler.

Scheduler duties:

 Maintains the queue.

 Select the process from queues assign to CPU.
Types of schedulers

1. Long term scheduler:

select the jobs from the job pool and loaded these jobs into main memory (ready queue).Long term scheduler
is also called job scheduler.
2. Short term scheduler:
select the process from ready queue, and allocates it to the cpu.
If a process requires an I/O device, which is not present available then process enters devicequeue.
short term scheduler maintains ready queue, device queue. Also called as cpu scheduler.
3. Medium term scheduler: if process request an I/O device in the middle of the execution, then
the process removed from the main memory and loaded into the waiting queue. When the I/O operation
completed, then the job moved from waiting queue to ready queue. These two operations performed by
medium term scheduler.

45
Context Switch: Assume, main memory contains more than one process. If cpu is executing a process, if
time expires or if a high priority process enters into main memory, then the scheduler saves information
about current process in the PCB and switches to execute the another process. The concept of moving CPU
by scheduler from one process to other process is known as context switch.
Non-Preemptive Scheduling: CPU is assigned to one process, CPU do not release until the competition of
that process. The CPU will assigned to some other process only after the previous process has finished.
Preemptive scheduling: here CPU can release the processes even in the middle of the execution. CPU
received a signal from process p2. OS compares the priorities of p1 ,p2. If p1>p2, CPU continues the
execution of p1. If p1<p2 CPU preempt p1 and assigned to p2.
Dispatcher: The main job of dispatcher is switching the cpu from one process to another process. Dispatcher
connects the cpu to the process selected by the short term scheduler.
Dispatcher latency: The time it takes by the dispatcher to stop one process and start another process is
known as dispatcher latency. If the dispatcher latency is increasing, then the degree of multiprogramming
decreases.
SCHEDULING CRITERIA:

1. Throughput: how many jobs are completed by the cpu with in a timeperiod.
2. Turn around time : The time interval between the submission of the process and time of the
completion is turn around time.
TAT = Waiting time in ready queue + executing time + waiting time in waiting queue forI/O.
3. Waiting time: The time spent by the process to wait for cpu to beallocated.
4. Response time: Time duration between the submission and firstresponse.
5. Cpu Utilization: CPU is costly device, it must be kept as busy aspossible. Eg: CPU efficiency is
90% means it is busy for 90 units, 10 units idle.
CPU SCHEDULINGALGORITHMS:

1. First come First served scheduling: (FCFS): The process that request the CPU
first is holds the cpu first. If a process request the cpu then it is loaded into the ready queue,
connect CPU to that process.
Consider the following set of processes that arrive at time 0, the length of the cpu burst time
given in milli seconds.
burst time is the time, required the cpu to execute that job, it is in milli seconds.

Process Burst time(milliseconds)

P1 5
P2 24
P3 16
P4 10
P5 3

46
 Average turn around time:

Turn around time= waiting time + burst time

Turn around time for p1= 0+5=5.

Turn around time for
p2=5+24=29 Turn around time
for p3=29+16=45 Turn around
time for p4=45+10=55 Turn
around time for p5= 55+3=58
Average turn around time= (5+29++45+55+58/5) = 187/5 =37.5 millisecounds

Average waiting time:

waiting time= starting time- arrival time

Waiting time for p1=0

Waiting time for p2=5-0=5
Waiting time for p3=29-0=29
Waiting time for p4=45-0=45
Waiting time for p5=55-0=55
Average waiting time= 0+5+29+45+55/5 = 125/5 = 25 ms.

Average Response Time :

Formula : First Response - Arrival

Time Response Time for P1 =0
Response Time for P2 => 5-0 = 5
Response Time for P3 => 29-0 = 29
Response Time for P4 => 45-0 = 45
Response Time for P5 => 55-0 = 55
Average Response Time => (0+5+29+45+55)/5 =>25ms

1) First Come FirstServe:

It is Non Primitive Scheduling Algorithm.

47
 PROCESS BURST ARRIVAL
TIME TIME
P1 3 0

P2 6 2

P3 4 4

P4 5 6

P5 2 8

Process arrived in the order P1, P2, P3, P4, P5.

P1 arrived at 0 ms.
P2 arrived at 2 ms.
P3 arrived at 4 ms.
P4 arrived at 6 ms.
P5 arrived at 8 ms.

Average Turn Around Time

Formula : Turn around Time =: waiting time + burst time
Turn Around Time for P1 => 0+3= 3
Turn Around Time for P2 => 1+6 = 7
Turn Around Time for P3 => 5+4 = 9
Turn Around Time for P4 => 7+ 5= 12
Turn Around Time for P5 => 2+ 10=12
Average Turn Around Time => ( 3+7+9+12+12 )/5 =>43/5 = 8.50 ms.
Average Response Time :
Formula : Response Time = First Response - Arrival Time
Response Time of P1 = 0
Response Time of P2 => 3-2 = 1
Response Time of P3 => 9-4 = 5
Response Time of P4 => 13-6 = 7
Response Time of P5 => 18-8 =10
Average Response Time => ( 0+1+5+7+10 )/5 => 23/5 = 4.6 ms
Advantages: Easy to Implement, Simple.

48
Disadvantage: Average waiting time is very high.
2) Shortest Job First Scheduling ( SJF ):

Which process having the smallest CPU burst time, CPU is assigned to that process . If
two process having the same CPU burst time, FCFS is used.

PROCESS CPU BURST TIME

P1 5

P2 24

P3 16

P4 10

P5 3

P5 having the least CPU burst time ( 3ms ). CPU assigned to that ( P5 ). After completion of
P5 short term scheduler search for nest ( P1 ).......
Average Waiting Time :

Formula = Staring Time - Arrival Time

waiting Time for P1 => 3-0 = 3
waiting Time for P2 => 34-0 = 34
waiting Time for P3 => 18-0 = 18
waiting Time for P4 =>8-0=8
waiting time for P5=0
Average waiting time => ( 3+34+18+8+0 )/5 => 63/5 =12.6 ms

Average Turn Around Time :

Formula = waiting Time + burst Time

Turn Around Time for P1 => 3+5 =8

Turn Around for P2 => 34+24 =58
49
Turn Around for P3 => 18+16 = 34
Turn Around Time for P4 => 8+10 =18
Turn Around Time for P5 => 0+3 = 3
Average Turn around time => ( 8+58+34+18+3 )/5 => 121/5 = 24.2 ms
Average Response Time :

Formula : First Response - Arrival Time

First Response time for P1 =>3-0 = 3

First Response time for P2 => 34-0 = 34
First Response time for P3 => 18-0 = 18
First Response time for P4 => 8-0 = 8
First Response time for P5 = 0
Average Response Time => ( 3+34+18+8+0 )/5 => 63/5 = 12.6 ms
SJF is Non primitive scheduling algorithm
Advantages : Least average waiting time
Least average turn around time Least
average response time
Average waiting time ( FCFS ) = 25 ms
Average waiting time ( SJF ) = 12.6 ms 50% time saved in SJF.
Disadvantages:
 Knowing the length of the next CPU burst time is difficult.
 Aging ( Big Jobs are waiting for long time for CPU)

3) Shortest Remaining Time First ( SRTF );

This is primitive scheduling algorithm.

Short term scheduler always chooses the process that has term shortest remaining time. When a
new process joins the ready queue , short term scheduler compare the remaining time of
executing process and new process. If the new process has the least CPU burst time, The
scheduler selects that job and connect to CPU. Otherwise continue the old process.

PROCESS BURST TIME ARRIVAL TIME

P1 3 0
P2 6 2
P3 4 4
P4 5 6
P5 2 8

50
P1 arrives at time 0, P1 executing First , P2 arrives at time 2. Compare P1 remaining time and P2 ( 3-2 =
1) and 6. So, continue P1 after P1, executing P2, at time 4, P3 arrives, compare P2 remaining time (6-1=5
) and 4 ( 4<5 ) .So, executing P3 at time 6, P4 arrives. Compare P3 remaining time and P4 ( 4-
2=2 ) and 5 (2<5 ). So, continue P3 , after P3, ready queue consisting P5 is the least out of
three. So execute P5, next P2, P4.
FORMULA : Finish time - Arrival
Time Finish Time for P1 => 3-0 = 3
Finish Time for P2 => 15-2 = 13
Finish Time for P3 => 8-4 =4
Finish Time for P4 => 20-6 = 14
Finish Time for P5 => 10-8 = 2

Average Turn around time => 36/5 = 7.2 ms.

4 )ROUND ROBIN SCHEDULING ALGORITHM :

It is designed especially for time sharing systems. Here CPU switches between the processes.
When the time quantum expired, the CPU switched to another job. A small unit of time, called
a time quantum or time slice. A time quantum is generally from 10 to 100 ms. The time
quantum is generally depending on OS. Here ready queue is a circular queue. CPU scheduler
picks the first process from ready queue, sets timer to interrupt after one time quantum and
dispatches the process.

PROCESS BURST TIME

P1 30

P2 6

P3 8

51
AVERAGE WAITING TIME :

Waiting time for P1 => 0+(15-5)+(24-20) => 0+10+4 = 14

Waiting time for P2 => 5+(20-10) => 5+10 = 15
Waiting time for P3 => 10+(21-15) => 10+6 = 16
Average waiting time => (14+15+16)/3 = 15 ms.

AVERAGE TURN AROUND TIME :

FORMULA : Turn around time = waiting time + burst Time
Turn around time for P1 => 14+30 =44
Turn around time for P2 => 15+6 = 21
Turn around time for P3 => 16+8 = 24
Average turn around time => ( 44+21+24 )/3 = 29.66 ms

5) PRIORITY SCHEDULING :

PROCESS BURST PRIORITY

TIME
P1 6 2

P2 12 4

P3 1 5

P4 3 1

P5 4 3

P4 has the highest priority. Allocate the CPU to process P4 first next P1, P5, P2, P3.

AVERAGE WAITING TIME :

Waiting time for P1 => 3-0 =3

Waiting time for P2 => 13-0 = 13
Waiting time for P3 => 25-0 = 25
Waiting time for P4 => 0
Waiting time for P5 => 9-0 =9

52
Average waiting time => ( 3+13+25+0+9 )/5 = 10 ms

AVERAGE TURN AROUND TIME :

Turn around time for P1 =>3+6 = 9

Turn around time for P2 => 13+12= 25
Turn around time for P3 => 25+1 = 26
Turn around time for P4 => 0+3= 3
Turn around time for P5 => 9+4 = 13

Average Turn around time => ( 9+25+26+3+13 )/5 = 15.2 ms

Disadvantage: Starvation

Starvation means only high priority process are executing, but low priorityprocess are waiting for the
CPU for the longest period of the time.

Multiple – processor scheduling:

When multiple processes are available, then the scheduling gets more complicated, because there is more
than one CPU which must be kept busy and in effective use at all times.
Load sharing resolves around balancing the load between multiple processors. Multi processor systems
may be heterogeneous (It contains different kinds of CPU’s) ( or ) Homogeneous(all the same kind of
CPU).
1) Approaches to multiple-processor schedulinga)Asymmetric multiprocessing
One processor is the master, controlling all activities and running all kernel code, while the other runs
only user code.
b)Symmetric multiprocessing:
Each processor schedules its own job. Each processor may have its own private queue of readyprocesses.

2) Processor Affinity
Successive memory accesses by the process are often satisfied in cache memory. what happens if the
process migrates to another processor. the contents of cache memory must be invalidated for the first
processor, cache for the second processor must be repopulated. Most Symmetric multi processor systems
try to avoid migration of processes from one processor to another processor, keep a process running on
the same processor. This is called processor affinity.
a) Soft affinity:
Soft affinity occurs when the system attempts to keep processes on the same processor but makes no
guarantees.

53
b) Hard affinity:
Process specifies that it is not to be moved between processors.
3) Load balancing:
One processor wont be sitting idle while another is overloaded. Balancing can be
achived through push migration or pull migration.

Push migration:
Push migration involves a separate process that runs periodically(e.g every 200 ms)
and moves processes from heavily loaded processors onto less loaded processors.
Pull migration:
Pull migration involves idle processors taking processes from the ready queues of
the otherprocessors.

54