Os Lab Manual
Os Lab Manual
Os Lab Manual
TECHNOLOGY
Manipal – 576 104
EVALUATION PLAN ii
6 PROCESS SCHEDULING 50
8 BANKERS ALGORITHM 59
DYNAMIC STORAGE ALLOCATION STRATEGY FOR
9 63
FIRST FIT AND BEST FIT
10 PAGE REPLACEMENT ALGORITHMS 65
REFERENCES 74
i
Course Objectives
Course Outcomes
Evaluation plan
ii
INSTRUCTIONS TO THE STUDENTS
• Students should carry the Lab Manual Book and the required stationery to every
lab session.
• Be in time and follow the institution dress code.
• Must Sign in the log register provided.
• Make sure to occupy the allotted seat and answer the attendance.
• Adhere to the rules and maintain the decorum.
iii
• Plagiarism (copying from others) is strictly prohibited and would invite severe
penalty in evaluation.
• The exercises for each week are divided under three sets:
✓ Solved exercise
✓ Lab exercises - to be completed during lab hours
✓ Additional Exercises - to be completed outside the lab or in the lab to en-
hance the skill
• If a student misses a lab class then he/ she must ensure that the experiment is
completed during the repetition class in case of genuine reason (medical certifi-
cate approved by HOD) with the permission of the faculty concerned
• Questions for lab tests and examination are not necessarily limited to the questions
in the manual, but may involve some variations and / or combinations of the ques-
tions.
• A sample note preparation is given as a model for observation.
iv
LAB NO: 1
Objective:
1. To recall the UNIX special characters and commands.
2. To describe basic commands.
A shell is an environment in which we can run our commands, programs, and scripts.
There are different flavors of shells, just as there are different flavors of operating
systems. Each flavor of shell has its own set of recognized commands and functions.
Shell Prompt:
The prompt, $, which is called command prompt, is issued by the shell. While the
prompt is displayed, you can type a command. The command is a binary executable.
Once the Enter key is pressed, the shell reads the command line arguments and per-
forms accordingly. It determines the command to be executed by looking for input
executable name placed in standard location (ex: /usr/bin). Multiple arguments can
be provided to the command (executable) separated by spaces.
Following is a simple example of date command which displays current date and time:
$date
Thu Jun 25 08:30:19 MST 2009
Shell Types:
In UNIX there are two major types of shells:
1. The Bourne shell. If you are using a Bourne-type shell, the default prompt is the
$ character.
2. The C shell. If you are using a C-type shell, the default prompt is the % character.
There are again various subcategories for Bourne Shell which are listed as follows:
• Bourne shell (sh)
• Korn shell (ksh)
• Bourne again shell (bash)
• POSIX shell (sh)
1
LAB NO: 1
The original UNIX shell was written in the mid-1970s by Stephen R. Bourne while
he was at AT&T Bell Labs in New Jersey. The Bourne shell was the first shell to
appear on UNIX systems, thus it is referred to as "the shell". The Bourne shell is
usually installed as /bin/sh on most versions of UNIX. For this reason, it is the shell
of choice for writing scripts to use on several different versions of UNIX.
Special Characters:
Before we continue to learn about UNIX shell commands, it is important to know that
there are many symbols and characters that the shell interprets in special ways. This
means that certain type of characters: a) cannot be used in certain situations, b) may
be used to perform special operations, or, c) must be “escaped” if you want to use
them in a normal way.
2
LAB NO: 1
Character Description
\ Escape character. If you want to refer a special character, you must “escape”
it with a backslash first. Example: touch /tamp/filename\*
. Current directory. Can also “hide” files when it is the first character in a file-
name.
.. Parent directory
[] Can be used to represent a range of values, e.g. [0-9], [A-Z], etc. Example:
hello[0-2].txt represents the names hello0.txt, hello1.txt, and hello2.txt
| “Pipe”. Redirect the output of one command into another command. Exam-
ple: ls | more
> Redirect the output of a command into a new file. If the file already exists,
over-write it. Example: ls > myfiles.txt
>> Redirect the output of a command onto the end of an existing file. Example:
echo “Mary 555-1234” >> phonenumbers.txt
<< Reads from a stream literal (an inline file, passed to the standard input) Ex-
ample: tr a-z A-Z << END_TEXT
This is OS lab manual
For IT students
END_TEXT
3
LAB NO: 1
&& Command separator as above, but only runs the second command if the first
one finished without errors. Example: cd /var/logs && less messages
& Execute a command in the background, and immediately get your shell back.
Example: find / -name core > /tmp/corefiles.txt &
[Before executing the program, the program file has to be granted with execution
permission. For granting execute permission the command chmod +x has to be
executed.]
Command Syntax
When interacting with the UNIX operating system, one of the first things you need to
know is that, unlike other computer systems you may be accustomed to, everything in
UNIX is case-sensitive. Be careful when you're typing in commands - whether a character
is upper or lower case does make a difference. For instance, if you want to list your files
with the ls command, if you enter LS you will be told “command not found”. Commands
4
LAB NO: 1
can be run by themselves, or you can pass in additional arguments to make them do dif-
ferent things. Each argument to the command should be separated by space. Typical com-
mand syntax can look something like this:
command [-argument] [-argument] [--argument] [file]
Examples: ls #List files in current directory
ls -l #Lists files in “long” format
ls -l --color #As above, with colorized output
cat filename #Show contents of a file
cat -n filename #Show contents of a file, with line numbers
Getting Help
When you're stuck and need help with a UNIX command, help is usually only a few
keystrokes away! Help on most UNIX commands is typically built right into the com-
mands themselves, available through online help programs (“man pages” and “info
pages”), and of course online.
Many commands have simple “help” screens that can be invoked with special command
flags. These flags usually look like -h or --help. Example: grep –help. “Man Pages” are
the best source of information for most commands can be found in the online manual
pages. To display a command's manual page, type man <commandName>.
Examples: man ls Get help on the “ls” command.
man man A manual about how to use the manual!
To search for a particular word within a man page, type /<word>. To quit from a man
page, just type the “Q” (or q) key.
Sometimes, you might not remember the name of UNIX command and you need to search
for it. For example, if you want to know how to change a file's permissions, you can
search the man page descriptions for the word “permission” like this: man -k permission.
All matched manual page names and short descriptions will be displayed that includes
the keyword “permission” as regular expression.
the words enclosed in angular brackets (<>) represents user defined arguments and
should be replaced with actual arguments. Example: ls <dirName> should be replaced
with actual existing directory name such as ls ABC.
a. pwd (“Print Working Directory”): Shows the current location in the directory
tree.
b. cd (“Change Directory”): When typed all by itself, it returns you to your home
directory. Few of the arguments to cd are:
i. cd <dirName>: changes current path to the specified directory name. Ex-
ample: cd /usr/src/unix
ii. cd ~ : “~” is an alias for your home directory. It can be used as a shortcut to your
“home”, or other directories relative to your home
iii. cd ..: Move up one directory. For example, if you are in /home/vic and
you type cd .., you will end up in /home. Note: there should be space be-
tween cd and .. .
iv. cd -: Return to previous directory. An easy way to get back to your previ-
ous location!
c. ls: List all files in the current directory, in column format. Few of the arguments
for ls command are as follows:
i. ls <dirName>: List the files in the specified directory. Example: ls /var/log
ii. ls -l: List files in “long” format, one file per line. This also shows you addi-
tional info about the file, such as ownership, permissions, date, and size.
iii. ls –a: List all files, including “hidden” files. Hidden files are those files that
begin with a “.”,
iv. ls –ld < dirName >: A “long” list of “directory”, but instead of showing the
directory contents, show the directory's detailed information. For example,
compare the output of the following two commands: ls -l /usr/bin ls -ld
/usr/bin
v. ls /usr/bin/d*: List all files whose names begin with the letter “d” in the
/usr/bin directory.
6
LAB NO: 1
7
LAB NO: 1
The remaining wildcard is the set construct. A set is a list of characters (e.g., abc), an
inclusive range (e.g., a-z), or some combination of the two. If you want the dash character
to be part of a list, just list it first or last.
In the original wildcard example, program.[co] and program.[a-z] both match program.c
and program.o, but not program.log. An exclamation point after the left bracket lets you
"negate" a set. For example, [!.;] matches any character except period and semicolon; [!a-
zA-Z] matches any character that isn't a letter. To match “!” itself, place it after the first
character in the set, or precede it with a backslash, as in [\!].
The range notation is handy, but you shouldn't make too many assumptions about what
characters are included in a range. It's safe to use a range for uppercase letters, lowercase
letters, digits, or any subranges thereof (e.g., [f-q], [2-6]). Don't use ranges on punctuation
characters or mixed-case letters: e.g., [a-Z] and [A-z] should not be trusted to include all
of the letters and nothing more.
However, it's important to be aware that the commands that you run only see the results
of wildcard expansion. That is, they just see a list of arguments, and they have no
8
LAB NO: 1
knowledge of how those arguments came into being. For example, if you type ls fr* and
your files are as on the previous page, then the shell expands the command line to ls fred
frank and invokes the command ls with arguments fred and frank. If you type ls g*, then
(because there is no match) ls will be given the literal string g* and will complain with
the error message, g*: No such file or directory. This is different from the C shell's wild-
card mechanism, which prints an error message and doesn't execute the command at all.
The wildcard examples that we have seen so far are actually part of a more general con-
cept called pathname expansion. Just as it is possible to use wildcards in the current di-
rectory, they can also be used as part of a pathname. For example, if you wanted to list
all of the files in the directories /usr and /usr2, you could type ls /usr*. If you were only
interested in the files beginning with the letters b and e in these directories, you could
type ls /usr*/[be]* to list them.
a. touch: changes the file timestamps, if the file does not exists then this command
creates an empty file. Example: touch abc xyz mno creates three empty files in the
current directory
b. file: Find out what kind of file it is. For example, file /bin/ls tells us that it is a
UNIX executable file.
c. cat: Display the contents of a text file on the screen. For example: cat file.txt
would displays the file content.
d. head: Display the first few lines of a text file. Example: head /etc/services
e. tail: Display the last few lines of a text file. Example: tail /etc/services. tail -f
displays the last few lines of a text file.
f. cp: Copies a file from one location to another. Example: cp mp3files.txt /tmp (cop-
ies the mp3files.txt file to the /tmp directory)
g. mv: Moves a file to a new location, or renames it. For example: mv mp3files.txt
/tmp (copy the file to /tmp, and delete it from the original location)
h. rm: Delete a file. Example: rm /tmp/mp3files.txt
9
LAB NO: 1
10
LAB NO: 1
7. Shortcuts
a. ctrl+c Halts the current command
b. ctrl+z Stops the current command,
c. ctrl+d Logout the current session, similar to exit
d. ctrl+w Erases one word in the current line
e. ctrl+u Erases the whole line
f. !! Repeats the last command
g. exit Logout the current session
Lab Exercises
1. Execute and write output of all the commands explained so far in this manual.
2. Explore the following commands along with their various options. (Some of the op-
tions are specified in the bracket)
a. cat (variation used to create a new file and append to existing file)
b. head and tail (-n, -c )
c. cp (-n, -i, -f)
d. mv (-f, -i) [try (i) mv dir1 dir2 (ii) mv file1 file2 file3 ... directory]
e. rm (-r, -i, -f)
f. rmdir (-r, -f)
g. find (-name, -type)
11
LAB NO: 1
12
LAB NO: 2
Objectives:
1. To know the UNIX shell, special characters and commands.
2. To describe Unix commands.
Usage
Grep <word> <filename>
grep <word> file1 file2 file3
grep < word1> <word2> filename
cat <otherfile> | grep <word>
command | grep <something>
grep --color < word> <filename>
grep text * # * stands for all files in current directory
Examples:
$ cat fruitlist.txt
apple
13
LAB NO: 2
apples
pineapple
fruit-apple
banana
pear
peach
orange
$ grep ^p fruitlist.txt
pineapple
pear
peach
$ grep -v apple fruitlist.txt #print unmatched lines
banana
pear
peach
orange
b. sort
sort is a program that prints the lines of its input or concatenation of all files listed in
its argument list in sorted order. Sorting is done based on one or more sort keys ex-
tracted from each line of input. By default, the entire input is taken as sort key. Blank
space is the default field separator. Note: Sort doesn’t modify the input file content.
sort <any number of filenames> #sort the content of file(s)
sort <fileName> #sort alphabetically
sort -o <file> <outputFile> #write result to a file
14
LAB NO: 2
c. wc (word count)
This shell command can be used to print the number of lines words in the input file/s.
$wc <fileName> #Number of lines, number of words, byte size of <fileName>.
Other arguments includes: -l (lines), -w (words), -c (byte size), -m
$ wc * : counts for all files in the current directory.
d. cut
cut is a data filter: it extracts columns from tabular data. If you supply the numbers of
columns you want to extract from the input, cut prints only those columns on the
standard output. Columns can be character positions or—relevant in this example—
fields that are separated by TAB characters (default delimiter) or other delimiters.
Examples
ls –l | cut –d “-“ -f 2 #-d specifies the delimiter and default delimiter is tab. The
permission for the group for the files can be obtained using this statement
cut –c 1-3 record.txt # -c specifies characters to be extracted
cut -c1,4,7 record.txt #characters 1, 4, and 7
cut -c1-3,8 record.txt #characters 1 thru 3, and 8
cut -c3- record.txt #characters 3 thru last
cut –f 1,4,7 record.txt #tab-separated fields 1, 4, and 7 #-f specifies fields to be
extracted.
15
LAB NO: 2
the '-f sed.in' option. This latter option is most used if the sed commands are complex
and involve lots of regexps!
For instance: sed -e 's/input/output/' my_file
will echo every line from my_file to standard output, changing the first occurrence of
'input' on each line into 'output'. sed is line-oriented, so if you wish to change every
occurrence on each line, then you need to make it a 'greedy' search & replace like so:
sed -e 's/input/output/g' my_file # g stands for global
By default the output is written to stdout. You may redirect this to a new file, or if you
want to edit the existing file in place you should use the -i flag:
sed -e 's/input/output/' my_file > new_file
sed -i -e 's/input/output/' my_file
sed and regexps
What if one of the characters you wish to use in the search command is a special sym-
bol, like / (e.g. in a filename) or * etc? Then you must escape the symbol just as for
grep (and awk). Say you want to edit a shell scripts to refer to /usr/local/bin and not
/bin any more, then you could do this
sed -e 's/\/bin/\/usr\/local\/bin/' my_script > new_script
What if you want to use a wildcard as part of your search – how do you write the output
string? You need to use the special symbol '&' which corresponds to the pattern found.
So say you want to take every line that starts with a number in your file and surround
that number by parentheses:
sed -e 's/[0-9]*/(&)/' my_file
where [0-9] is a regexp range for all single digit numbers, and the '*' is a repeat
count, means any number of digits.
Other sed commands
The general form is sed -e '/pattern/ command' my_file, where 'pattern' is a regexp
and 'command' can be one of 's' = search & replace, or 'p' = print, or 'd' =delete, or
'i'=insert, or 'a'=append, etc. Note that the default action is to print all lines that do
not match anyway, so if you want to suppress this you need to invoke sed with the '-
n' flag and then you can use the 'p' command to control what is printed. So if you
want to do a listing of all the subdirectories you could use below statement, as ls –l
includes “d” at the start while listing the subdirectories.
ls -l | sed -n -e '/^d/ p'
Below statement, deletes all lines that start with the comment symbol '#' in my_file.
sed -e '/^#/ d' my_file
16
LAB NO: 2
To insert a new line after a matching pattern is found the option “a” is used
sed –i ‘/word/a “xyz”’ filename
You can also use the range form
sed -e '1,100 command' my_file
to execute 'command' on lines 1,100. You can also use the special line number '$' to
mean 'end of file'. For example below statement deletes all but the first 10 lines of a
file.
sed -e '11,$ d' my_file
f. tr (translate)
The tr filter is used to translate one set of characters from the standard inputs to an-
other.
Examples:
$tr “[a-z]” “[A-Z]” < filename #maps all lowercase characters in filename to up-
percase. Content of the file is not changed.
tr 'abcd' 'jkmn' #maps all characters a to j, b to k, c to m, and d to n.
The character set may be abbreviated by using character ranges. The previous ex-
ample could be written: tr 'a-d' 'jkmn'
The s flag (suppress) causes tr to compress sequences of identical adjacent charac-
ters in its output to a single token. For example,
tr -s '\n' #replaces sequences of one or more newline characters with a single
newline.
The d flag causes tr to delete all tokens of the specified set of characters from its
input. The tr -d '\r' statement removes carriage return characters.
The c flag indicates the complement of the first set of characters. The invocation
tr -cd '[:alnum:]' therefore removes all non-alphanumeric characters.
b. kill
kill is a command that is used in several popular operating systems to send signals to
running processes in order to request the termination of the process. The signals in
which users are generally most interested are SIGTERM and SIGKILL. The SIG-
TERM signal is sent to a process to request its termination. Unlike the SIGKILL sig-
nal, it can be caught and interpreted or ignored by the process. This allows the process
to perform nice termination releasing resources and saving state if appropriate. The
SIGKILL signal is sent to a process to cause it to terminate immediately (kill). This
signal cannot be caught or ignored, and the receiving process cannot perform any
clean-up upon receiving this signal.
Examples:
A process can be sent a SIGTERM signal in four ways (the process ID is '1234' in this
case):
kill 1234
kill -s TERM 1234
kill -TERM 1234
kill -15 1234
The process can be sent a SIGKILL signal in three ways:
kill -s KILL 1234
kill -KILL 1234
kill -9 1234
The chmod command also accepts a finer-grained symbolic notation, which allows
modifying specific modes while leaving other modes untouched. The symbolic mode
is composed of three components, which are combined to form a single string of text:
$ chmod [references][operator][modes] file ...
The references (or classes) are used to distinguish the users to whom the permissions
apply. If no references are specified it defaults to “all” but modifies only the permis-
sions allowed by the umask. The references are represented by one or more of the
following letters:
The chmod program uses an operator to specify how the modes of a file should be
adjusted. The following operators are accepted:
Operator Description
+ adds the specified modes to the specified classes
- removes the specified modes from the specified classes
= the modes specified are to be made the exact modes for the specified clas-
ses
The modes indicate which permissions are to be granted or removed from the spec-
ified classes. There are three basic modes which correspond to the basic permis-
sions:
19
LAB NO: 2
Command Explanation
chmod a+r Comments.txt read is added for all classes (i.e. User, Group
and Others)
chmod a+rx viewer.sh add read and execute for all classes.
chmod u=rw,g=r,o= Plan.txt user(i.e. owner) can read and write, group
can read, others cannot access.
chmod ug=rw groupAgreements.txt user and group members can read and write
(update the file).
chmod 664 global.txt sets read and write and no execution access
for the user and group, and read, no write,
no execute for all others.
20
LAB NO: 2
21
LAB NO: 2
This command would open a display screen with 25 lines and with tilt (~) symbol at the
start of each line. The first syntax would save the file in the filename mentioned and for
the next the filename must be mentioned at the end.
Options :
1.vi +n <filename> - this would point at the nth line (cursor pos).
2.vi –n <filename> - This command is to make the file to read only to change from one
mode to another press escape key.
Saving and Quitting from vi
To move editor from command node to edit mode, you have to press the <ESC> key.
<ESC> w Command To save the given text present in the file.
<ESC> q! Command To quit the given text without saving.
<ESC> wq Command This command quits the vi editor after saving the text in the
mentioned file.
<ESC> x Command This command is same as “wq” command it saves and quit.
<ESC> q Command This command would quit the window but it would ask for
again to save the file.
Lab Exercises
1. Execute all the commands explained in this section and write the output.
2. Write grep commands to do the following activities:
• To select the lines from a file that have exactly two characters.
• To select the lines from a file that start with the upper case letter.
• To select the lines from a file that end with a period.
• To select the lines in a file that has one or more blank spaces.
• To select the lines in a file and direct them to another file which has digits as
one of the characters in that line.
3. Create file studentInformation.txt using vi editor which contains details in the follow-
ing format.
RegistrationNo:Name:Department:Branch:Section:Sub1:Sub2:Sub3
1234:XYZ:ICT:CCE:A:80:60:70 … (add atleast 10 rows)
i) Display the number students( only count) belonging to ICT department.
ii) Replace all occurrences of IT branch with “Information Technology” and save
the output to ITStudents.txt
iii) Display the average marks of student with the given registration number
“1234” (or any specific existing number).
22
LAB NO: 2
iv) Display the title row in uppercase. The remaining lines should be unchanged.
Example:
REGISTRATIONNO:NAME:DEPARTMENT:BRANCH:SECTION:…
1234:XYZ:ICT:CCE:A:10:30:50 … ( Hint: use ; for running multiple commands)
3. List all the files containing “MIT” in the current folder. Also display the lines con-
taining MIT being replaced with Manipal Institute of Technology. (Hint: use grep,
cut & sed)
4. Write a shell command to display the number of lines, characters, words of files con-
taining a digit in its name.
5. Run wc command in the background many times using wc &. Kill all the processes
named wc.
Additional Exercises
1. Write a sed command that deletes the character before the last character in each line
in a file.
2. Write a shell command to count the number lines containing digits present in a file.
23
LAB NO: 3
Objectives:
EXAMPLE #!/bin/sh
Comments Comments are descriptive material preceded by a # sign. They are in ef-
fect until the end of a line and can be started anywhere on the line.
Wildcards There are some characters that are evaluated by the shell in a special way.
They are called shell meta characters or "wildcards". These characters are neither
numbers nor letters. For example, the *, ?, and [ ] are used for filename expansion.
24
LAB NO: 3
The <, >, 2>, >>, and | symbols are used for standard I/O redirection and pipes. To
prevent these characters from being interpreted by the shell they must be quoted.
EXAMPLE
Filename expansion:
Shell keywords :
Some of the shell keywords are echo, read, if fi, else, case, esac, for, while, do, done,
until, set, unset, readonly, shift, export, break, continue, exit, return, trap , wait, eval
,exec, ulimit , umask.
Local variables are in scope for the current shell. When a script ends, they are no longer
available; i.e., they go out of scope. Local variables are set and assigned values.
EXAMPLE
variable_name=value
name="John Doe"
x=5
25
LAB NO: 3
Global variables are called environment variables. They are set for the currently running
shell and any process spawned from that shell. They go out of scope when the script ends.
EXAMPLE
VARIABLE_NAME=value
export VARIABLE_NAME
PATH=/bin:/usr/bin:.
export PATH
Extracting values from variables: To extract the value from variables, a dollar sign is
used.
EXAMPLE [here, echo command is used display the variable value]
echo $variable_name
echo $name
echo $PATH
Input:
To get the input from the user read is used.
Syntax : read x y #no need of commas between variables
The read command takes a line of input from the user and assigns it to a variable(s) on
the right-hand side. The read command can accept multiple variable names. Each variable
will be assigned a word. No need to declare the variables to be read from user
Output :
echo can be used to display the results. Wildcards must be escaped with either a
backslash or matching quotes.
Syntax :
echo “Enter the value of b” (or) echo Value of b is $b(for variable).
26
LAB NO: 3
a=$(expr $a + 1)
a=`expr $a + 1`
space should not be present be-
tween = and expr. Space should
expr expression
expr be present between operator and
operators: + , - , /, %,=,==,!=
operands. To access values $ has
to be used for operands. Performs
only integer arithmetic opera-
tions.
[ condition/expression ]
Note one space should be present
after [ and before ]. Also operand
echo “Enter Two Values”
and operator must be separated
read a b
by a space.
result=$[ a == b ]
operators:
echo "Check for Equality $re-
Integers: -eq, -ne, -gt,-lt,-ge, -le,
sult”
test [ ] ==, !=
O/P: Enter Two Values
Boolean: !, -o(or), -a(and)
44
String: =, !=,-z(zero length), -
Check for Equality 1
n(non-zero length), [ $str ] (true if
test works in combination with
$str is not empty)
control structures refer section 6.
File: -f (ordinary file), -d
(directory), -r (readable), -w, -x, -
s (size is zero), -e (exists)
27
LAB NO: 3
6. Control statements
The shell control structure is similar to C syntax, but instead of brackets {} statements
like then- fi or do-done are used. The then, do has to be used in next line, otherwise ; has
to be used to mark the next line.
28
LAB NO: 3
Control
Syntax Example
Structure
if condition ; then
command(s) read character
fi if [ "$character" = "2" ]; then
OR echo " You entered two."
if
if condition fi
then O/P: 2
command(s) You entered two
fi
read fileName
if [ -e $fileName ]; then
if condition ; then
echo “ File $fileName exists"
command(s)
else
if else else
echo “ File $fileName does not exist"
command(s)
fi
fi
O/P: LAB3.sh
File LAB3.sh exists
read a b
if [ $a == $b ]; then
echo "$a is equal to $b"
if condition ; then elif [ $a -gt $b ]; then
command(s) echo "$a is greater than $b"
else if elif condition ; then elif (( a<b)) ; then
ladder command(s) echo "$a is less than $b"
fi else
echo "None of the condition met"
fi
O/P: 4 5
4 is less than 5
29
LAB NO: 3
read n
for (( i=1; i<=n; i++));do
for (( initialization;
echo -n $i
condition; expo)); do
for done
command(s)
O/P:
done
5
12345
30
LAB NO: 3
read n
i=1;
while (( i <= n)); do
while condition
echo -n $i " "
do
((i++))
while command(s) to be executed
done
while the condition is true
echo “"
done
O/P:
5
12345
read n
i=1
until condition until (( i > n )); do
do echo -n $i " "
until command(s) to be executed ((i++))
until condition is true i.e done
while the condition is false. O/P:
Done 5
12345
31
LAB NO: 3
echohi
echo "last error status $?"
exit num command may be
exit $? #exit the script with las error sta-
used to deliver an num exit
tus
exit status to the shell (num
echo "HI" # never printed
must be an integer in the 0 -
O/P:
255 range).
echohi: command not found
last error status 127
Lab Exercises
1. Write a shell script to find whether a given file is the directory or regular file.
2. Write a shell script to list all files (only file names) containing the input pattern
(string) in the folder entered by the user.
3. Write a shell script to replace all files with .txt extension with .text in the current di-
rectory. This has to be done recursively i.e if the current folder contains a folder
“OS” with abc.txt then it has to be changed to abc.text ( Hint: use find, mv )
4. Write a shell script to calculate the gross salary. GS=Basics + TA + 10% of Basics.
Floating point calculations has to be performed.
5. Write a program to copy all the files (having file extension input by the user) in the
current folder to the new folder input by the user. ex: user enter .text TEXT then all
files with .text should be moved to TEXT folder. This should be done only at single
level. i.e if the current folder contains a folder name ABC which has .txt files then
these files should not be copied to TEXT.
6. Write a shell script to modify all occurrences of “ex:” with “Example:” in all the files
present in current folder only if “ex:” occurs at the start of the line or after a period
32
LAB NO: 3
(.). Example: if a file contains a line: “ex: this is first occurrence so should be re-
placed” and “second ex: should not be replaced as it occurs in the middle of the sen-
tence.”
7. Write a shell script which deletes all the even numbered lines in a text file.
Additional Exercises
1. Write a shell script to check whether the user entered number is prime or not.
2. Write a shell script to find the factorial of number.
3. Write a shell script that, given a file name as the argument will write the even
numbered line to a file with name evenfile and odd numbered lines to a file called
oddfile.
33
LAB NO: 4
Objectives:
ables.
34
LAB NO: 4
$1 to $9 Arguments 1 through 9
EXAMPLE:
At the command line:
$scriptname arg1 arg2 arg3 ...
Inside script:
echo $1 $2 $3 ${10} #Positional parameters
echo $* #All the positional parameters
echo $# #The number of positional parameters
shift
2. System variables
When you log in on UNIX, your current shell (login shell) sets a unique working envi-
ronment for you which is maintained until you log out. You can see system variables by
giving command like $ set, few of the important system variables are
35
LAB NO: 4
NOTE that some of the above settings can be different in your PC. You can print any of
the above variables contain as follows
$ echo $USER
$ echo $HOME
[Caution: Do not modify System variable this can some time create problems.]
If you are using bash shell the here is the syntax of array initialization:
array_name=(value1 ... valuen) or
declare -a array_name
Accessing Array values
After you have set any array variable, you access it as follows:
${array_name[index]}
Here array_name is the name of the array, and index is the index of the value to be
accessed.
Example:
read -a inputArrayOfNumbers # input separated by spaces and not by carriage re-
turn
echo -n "Entered input is…"
for i in ${inputArrayOfNumbers[@]} ; do
echo -n $i " "
done
O/P:
5 4 45 3
Entered input is…5 4 45 3
Example 2:
declare –a arrayOfNumber
j=0
for i in $@
do
arrayOfNumber[j]=$i
((j++))
done
echo “${arrayOfNumber[@]}”
3.2 Functions:
Functions enable you to break down the overall functionality of a script into smaller,
logical subsections, which can then be called upon to perform their individual task
when it is needed. Using functions to perform repetitive tasks is an excellent way to
create code reuse.
37
LAB NO: 4
Function Definition
To define a function, simply use the following syntax:
function_name () { # can also use function function_name
list of command(s)
# to use parameters passed to the function use $1, $2…
}
Calling a Function
To call the function in the script use the following syntax:
function_name Arg1 arg2… # without spaces
Example :
function_add() {
a=$1
b=$2
c=`echo $a+$b | bc`
echo $c
}
function_add 3 5
38
LAB NO: 4
Lab Exercises
1. Write a shell script to make a duplicate copy of a specified file through command line.
2. Write a shell script to remove all files that are passed as command line arguments
interactively.
3. Write a program to sort the strings that are passed as a command line arguments. (ex:
./script.sh “OS Lab” “Quoted strings” “Command Line” “Sort It”. The output
should be “Command Line” “OS Lab” “Quoted strings” “Sort It”. ( make use of
usrdefined sort function)
4. Implement wordcount script that takes -linecount, -wordcount, -charcount options
and performs accordingly, on the input file that is passed as command line argument
(use case statement)
5. Write a menu driven shell script to read list of patterns as command line arguments
and perform following operations.
a. Search the patterns in the given input file. Display all lines containing the pat-
ten in the given input file.
39
LAB NO: 4
Additional Exercises
1. Write a shell script to input a file and display permissions of the owner group and
others.
2. Write a shell script to display all files that are created between the input years
range.(ex with 2014-2015)
3. Write a shell script that accepts a file name starting and ending line numbers as argu-
ments and displays all the lines between the given line numbers.
40
LAB NO: 5
41
LAB NO: 5
fork():
#include <sys/types.h>
#include <unistd.h>
pid_t fork(void);
The fork system call does not take any argument. The process that invokes
the fork() is known as the parent and the new process is called the child. If
the fork system call fails, it will return a -1. If the fork system call is successful, the
process ID of the child process is returned in the parent process and a 0 is returned in
the child process. When a fork() system call is made, the operating system generates
a copy of the parent process which becomes the child process. Both parent and child
resume execution of the instruction after the fork statement. vfork() is a variant of
fork. It creates the child process and blocks the parent, also both parent and child
share the same address space. Refer the manual pages for fork and vfork.
The operating system will pass to the child process most of the parent's process infor-
mation. However, some information is unique to the child process:
42
LAB NO: 5
43
LAB NO: 5
44
LAB NO: 5
wait():
#include <sys/types.h>
#include <sys/wait.h>
int *status;
pid_t pidOfLastTerminatedChild= wait(&status);
A parent process usually needs to synchronize its actions by waiting until the child
process which has either stopped or terminated its actions. The wait() system call al-
lows the parent process to suspend its activities until one of these actions has occurred.
The wait() system call accepts a single argument, which is a pointer to an integer and
returns a value defined as type pid_t. If the calling process does not have any child
associated with it, wait will return immediately with a value of -1. If any child pro-
cesses are still active, the calling process will suspend its activity until a child process
terminates.
Example of wait():
int status;
pid_t fork_return;
fork_return = fork();
if (fork_return == 0) /* child process */ {
printf("\n I'm the child!");
exit(0); }
else { /* parent process */
wait(&status);
printf("\n I'm the parent!");
if (WIFEXITED(status)) // #include<sys/wait.h>
printf("\n Child returned: %d\n", WEXITSTATUS(status)); //#include<sys/wait.h>
}
A few notes on this program:
45
LAB NO: 5
wait(&status) causes the parent to suspend until the child process finishes execu-
tion
details of how the child stopped are returned via the status variable to the parent.
Several macros are available to interpret the information. Two useful ones are:
➢ WIFEXITED evaluates as true, or 0, if the process ended normally with an exit
or return call.
➢ WEXITSTATUS if a process ended normally you can get the value that was
returned with this macro.
exec*():
#include <unistd.h>
extern char **environ;
int execl(const char *path, const char *arg, ...);
int execlp(const char *file, const char *arg, ...);
int execle(const char *path, const char *arg , ..., char * const envp[]);
int execv(const char *path, char *const argv[]);
int execvp(const char *file, char *const argv[]);
"The exec family of functions replaces the current process image with a new process
image." (man pages)
Commonly a process generates a child process because it would like to transform the
child process by changing the program code the child process is executing. The text,
data and stack segment of the process are replaced and only the u (user) area of the
process remains the same. If successful, the exec system calls do not return to the
invoking program as the calling image is lost.
It is possible for a user at the command line to issue an exec system call, but it takes
over the current shell and terminates the shell.
% exec command [arguments]
46
LAB NO: 5
NOTE:
In the four system calls where the PATH string is not used (execl, execv, execle,
and execve) the path to the program to be executed must be fully specified.
Pass Cur-
rent Search
Library Argument
Environ- PATH auto-
Call Name Type
ment matic?
Variables
execle list no no
execve array no no
47
LAB NO: 5
execlp
this system call is used when the number of arguments to be passed to the program
to be executed is known in advance
execvp
this system call is used when the numbers of arguments for the program to be
executed is dynamic
execlp("date","date", NULL); //uses the PATH to find date, try: %echo $PATH
48
LAB NO: 5
getpid():
#include <sys/types.h>
#include <unistd.h>
pid_t getpid(void);
pid_t getppid(void);
getpid() returns the process id of the current process. The process ID is a unique pos-
itive integer identification number given to the process when it begins executing.
getppid() returns the process id of the parent of the current process. The parent process
forked the current child process.
getpgrp():
#include <unistd.h>
pid_t getpgrp(void);
Every process belongs to a process group that is identified by an integer process group
ID value. When a process generates a child process, the operating system will auto-
matically create a process group.
The initial parent process is known as the process leader. getpgrp() will obtain the
process group id.
Lab Exercises
1. Write a C program to create a child process. Display different messages in parent
process and child process. Display PID and PPID of both parent and child process.
2. Write a C program to accept a set of strings as command line arguments. Sort the
strings and display them in a child process. Parent process should display the un-
sorted strings only after the child displays the sorted list.
3. Write a C program to read N strings. Create two child processes, each of this
should perform sorting using two different methods (bubble, selection, quicksort
etc). The parent should wait until one of the child process terminates.
Additional Exercises
1. Write a C program to simulate the unix commands: ls -l, cp and wc commands.
[NOTE: DON’T DIRECTLY USE THE BUILT-IN COMMANDS]
49
LAB NO: 6
PROCESS SCHEDULING
Objectives:
1. Basic Concepts :
CPU scheduling is the basis of multi programmed operating systems. By switching the
CPU among processes, the operating system can make the computer more productive. In
a single-processor system, only one process can run at a time; others(if any) must wait
until the CPU is free and can be rescheduled. The objective of multiprogramming is to
have some process running at all times, to maximize CPU utilization.
The idea is relatively simple. A process is executed until it must wait, typically for the
completion of some I/O request. In a simple computer system, the CPU then just sits idle.
All this waiting time is wasted; no useful work is accomplished. With multiprogramming,
we try to use this time productively. Several processes are kept in memory at one time.
When one process has to wait, the operating system takes the CPU away from that process
and gives the CPU to another process. This pattern continues. Every time one process has
to wait, another process can take over use of the CPU.
CPU Scheduler:
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 CPU sched-
uler. The scheduler selects a process from the processes in memory that are ready to ex-
ecute and allocates the CPU to that process.
50
LAB NO: 6
To implement RR scheduling, we keep the ready queue as a FIFO queue o£ processes.
New processes are added to the tail of the ready queue. The CPU scheduler picks the first
process from the ready queue, sets a timer to interrupt after 1 time quantum, and dis-
patches the process.
One of two things will then happen. The process may have a CPU burst of less than 1
time quantum. In this case, the process itself will release the CPU voluntarily. The sched-
uler will then proceed to the next process in the ready queue. Otherwise, if the CPU burst
of the currently running process is longer than 1 time quantum, the timer will go off and
will cause an interrupt to the operating system. A context switch will be executed, and
the process will be put at the tail of the ready queue. The CPU scheduler will then select
the next process in the ready queue.
P1 0 8
P2 5 4
P3 3 9
P4 7 16
P1 P3 P1 P2 P3 P4 P1 P2 P3 P4
0 3 6 9 12 15 18 20 21 24 37
51
LAB NO: 6
Example:Non-Preemptive
A 0 15
B 5 3
C 8 5
D 10 7
SJF Waiting time A= 0, B=10, C=10, D=13. TT A=15, B=13, C=15, D=20.
0 15 18 23 30
A B C D
A priority is associated with each process, and the CPU is allocated to the process with
the highest priority. Equal-priority processes are scheduled in FCFS order. An SJF algo-
rithm is simply a priority algorithm where the priority (p) is the inverse of the (predicted)
next CPU burst. The larger the CPU burst, the lower the priority, and vice versa.
52
LAB NO: 6
Example: Non-Preemptive
Process Arrival Time Execution Time Priority
J1 0 8 1
J2 2 4 2
J3 9 9 2
J4 4 15 3
J1 J2 J3 J4
0 8 12 21 36
Lab Exercise
1. Develop a menu driven C program to implement the following process scheduling
algorithms: preemptive-SJF, RR and non-preemptive priority scheduling algo-
rithms.
Additional Exercises
1. Write C program to implement FCFS. (Assuming all the processes arrive at the
same time)
2. Write a C program to implement non-preemptive SJF, where the arrival time is
different for the processes.
53
LAB NO: 7
Objectives:
1. To solve synchronization problems using threads.
1. Semaphores
A semaphore is a synchronization tool to solve critical section problem. A semaphore S
is an integer variable that, apart from initialization, is accessed only through two stand-
ard atomic operations: wait () and signal ().
The definition of wait () is as follows:
Wait(S) {
while S <= 0
; // no-op
S--;
}
The definition of signal() is as follows:
signal(S) { S++; }
2. Classical Problems :
54
LAB NO: 7
example, a Web server produces (that is, provides) HTML files and images, which are
consumed (that is, read) by the client Web browser requesting the resource.
One solution to the producer-consumer problem uses shared memory. To allow producer
and consumer processes to run concurrently, we must have available a buffer of items
that can be filled by the producer and emptied by the consumer. This buffer will reside in
a region of memory that is shared by the producer and consumer processes. A producer
can produce one item while the consumer is consuming another item. The producer and
consumer must be synchronized, so that the consumer does not try to consume an item
that has not yet been produced.
3. Algorithm
}end { producers_consumers}
process producer;
do
{
//Produce the data to be put into buffer in anyway
wait(empty);
wait(pmutex);
buffer[in] = producedItem;
in = (in mod capacity) + 1;
signal(pmutex);
signal(full);
other_X_processing
}while (TRUE);
end; {producer}
process consumer;
do
{ wait(full);
wait(cmutex);
citem = buffer[out];
out = (out mod capacity) + 1;
signal(cmutex);
signal(empty);
// Use the consumed data
} while(TRUE);
end; {consumer}
program readers_writers;
var
readercount : integer;
mutex, write : semaphore; {binary}
56
LAB NO: 7
process readerX;
begin
while true do
begin
{obtain permission to enter}
wait(mutex);
readercount := readercount +1;
if readercount = 1 then wait(write);
signal(mutex);
…
{reads}
…
wait(mutex);
readercount = readercount – 1;
if readercount = 0 then signal(write);
signal(mutex);
other_X_processing
end {while}
end; {reader}
process writerZ;
begin
while true do
begin
wait(write);
…
signal(write);
Other_Z_processing
end {while}
end; {writerZ}
{parent process}
begin {readers_writers}
readercount : = 0;
signal(mutex);
signal (write);
57
LAB NO: 7
Lab Exercise
1. Write a C program to solve producer consumer problem with bounded buffer using
semaphores.
2. Write a C program to solve the readers and writers Problem.
Additional Exercise
1. Write a C program to solve the Dining-Philosophers problem.
58
LAB NO: 8
BANKERS ALGORITHM
Objectives:
1. Deadlocks
In a multiprogramming environment, several processes may compete for a finite number
of resources. A process requests resources; if the resources are not available at that time,
the process enters a waiting state. Sometimes, a waiting process is never again able to
change state, because the resources it has requested are held by other waiting processes.
This situation is called a deadlock. Under the normal mode of operation, a process may
utilize a resource in only the following sequence:
Request: The process requests the resource. If the request cannot be granted immediately
(for example, if the resource is being used by another process), then the requesting pro-
cess must wait until it can acquire the resource.
Use: The process can operate on the resource (for example, if the resource is a printer,
the process can print on the printer).
A deadlock situation can arise if the following four conditions hold simultaneously in a
system:
Mutual exclusion: At least one resource must be held in a non-sharable mode; that is,
only one process at a time can use the resource. If another process requests that resource,
the requesting process must be delayed until the resource has been released.
Hold and wait: A process must be holding at least one resource and waiting to acquire
additional resources that are currently being held by other processes.
No preemption: Resources cannot be preempted; that is, a resource can be released only
voluntarily by the process holding it, after that process has completed its task.
59
LAB NO: 8
Circular wait: A set { P0 , Pl, ... , P11 } of waiting processes must exist such that Po is
waiting for a resource held by P1, P1 is waiting for a resource held by P2, ... , Pn-1 is
waiting for a resource held by Pn and Pn is waiting for a resource held by Po.
2. Deadlock Avoidance
In deadlock avoidance, simplest and most useful model requires that each process declare
the maximum number of resources of each type that it may need. The deadlock-avoidance
algorithm dynamically examines the resource-allocation state to ensure that there can
never be a circular-wait condition. Resource-allocation state is defined by the number of
available and allocated resources, and the maximum demands of the processes
Safe Sate
When a process requests an available resource, system must decide if immediate alloca-
tion leaves the system in a safe state. System is in safe state if there exists a sequence
<P1, P2, …, Pn> of ALL the processes in the systems such that for each Pi, the resources
that Pi can still request can be satisfied by currently available resources plus resources
held by all the Pj, with j < i. That is:
• If Pi resource needs are not immediately available, then Pi can wait until all Pj
have finished
• When Pj is finished, Pi can obtain needed resources, execute, return allocated re-
sources, and terminate
• When Pi terminates, Pi +1 can obtain its needed resources, and so on
If a system is in safe state then no deadlocks. If a system is in unsafe state then there is a
possibility of deadlock
60
LAB NO: 8
3. Bankers Algorithm
It is a deadlock avoidance algorithm. The name was chosen because the bank never allo-
cates more than the available cash.
Available: A vector of length m indicates the number of available resources of each type.
If Available[j] equals k, then k instances of resource type Ri are available.
Max: An n x m matrix defines the maximum demand of each process. If Max[i] [j] equals
k, then process P; may request at most k instances of resource type Ri.
Allocation: An n x m matrix defines the number of resources of each type currently allo-
cated to each process. If Allocation[i][j] equals lc, then process Pi is currently allocated
lc instances of resource type Rj.
• Let Work and Finish be vectors of length m and n, respectively. Initialize Work=
Available and Finish[i] =false for i = 0, 1, ... , n - 1.
• Find an index i such that both
61
LAB NO: 8
a. Finish[i] ==false
b. Needi <= Work
If no such i exists, go to step 4.
• Work = Work + Allocation;
Finish[i] = true
Go to step 2.
• If Finish[i] ==true for all i, then the system is in a safe state.
Let Requesti; be the request vector for process Pi. If Requesti [j] == k, then process Pi
wants k instances of resource type Rj. When a request for resources is made by process
Pi, the following actions are taken:
1. If Requesti <= Needi, go to step 2. Otherwise, raise an error condition, since the pro-
cess has exceeded its maximum claim.
2. If Requesti <= Available, go to step 3. Otherwise, Pi must wait, since the resources
are not available.
3. Have the system pretend to have allocated the requested resources to process Pi by
modifying the state as follows:
Available= Available – Requesti;
Allocationi =Allocationi +Requesti;
Needi =Needi - Requesti;
If the resulting resource-allocation state is safe, the transaction is completed, and process
Pi is allocated its resources. However, if the new state is unsafe, then Pi must wait for
Requesti, and the old resource-allocation state is restored.
Lab Exercise
1. Develop a program to simulate banker’s algorithm. (Consider safety and resource-
request algorithms)
Additional exercises
1. Write a C program to implement the deadlock detection algorithm.
62
LAB NO: 9
Objectives:
2. To write C program which allocates memory requirement for processes using first
fit and best fit strategies.
1. Description
One of the simplest methods for memory allocation is to divide memory into several
fixed-sized partitions. Each partition may contain exactly one process. In this multiple-
partition method, when a partition is free, a process is selected from the input queue and
is loaded into the free partition. When the process terminates, the partition becomes avail-
able for another process. The operating system keeps a table indicating which parts of
memory are available and which are occupied. Finally, when a process arrives and needs
memory, a memory section large enough for this process is provided. When it is time to
load or swap a process into main memory, and if there is more than one free block of
memory of sufficient size, then the operating system must decide which free block to
allocate.
The first fit and best fit strategies are used to select a free hole (available block of
memory) from the set of available holes.
First fit: Allocate the first hole that is big enough. Searching can start either at the begin-
ning of the set of holes or at the location where the previous first-fit search ended. We
can stop searching as soon as we find a free hole that is large enough.
Best fit: Allocate the smallest hole that is big enough. We must search the entire list,
unless the list is ordered by size. This strategy produces the smallest leftover hole.
2. Algorithm
First Fit Allocation
1. Declare structures hole and process to hold information about set of holes and
processes respectively.
2. Get number of holes, say nh.
3. Get the size of each hole
4. Get number of processes, say np.
63
LAB NO: 9
64
LAB NO: 10
Objectives:
1.Introduction :
Page replacement is basic to demand paging. It completes the separation between logical memory
and physical memory. With this mechanism, an enormous virtual memory can be provided for
programmers on a smaller physical memory. There are many different page-replacement algo-
rithms. Every operating system probably has its own replacement scheme.
FIFO algorithm:
The simpler page replacement algorithm is a FIFO algorithm. A FIFO replacement algorithm
associates with each page the time when that page was brought into memory. When a page must
be replace, the oldest page is chosen. We can create a FIFO queue to hold all pages in memory.
We replace the page at the head of the queue when a page is brought into memory; we insert it at
the tail of the queue.
Optimal page replacement algorithm has the lowest page-fault rate of all algorithms and will never
suffer from Belady's anomaly. The basic idea is to replace the page that will not be used for the
longest period of time. Use of this page-replacement algorithm guarantees the lowest possible
page fault rate for a fixed number of frames. Unfortunately, the optimal page-replacement algo-
rithm is difficult to implement, because it requires future knowledge of the reference string.
65
LAB NO: 10
2.Algorithms :
FIFO :
1. Start
2. Read the number of frames
3. Read the number of pages
4. Read the page numbers
5. Initialize the values in frames to -1
6. Allocate the pages in to frames in first in first out order.
7. Display the number of page faults.
8. stop
Lab exercise :
1. Write a C program to simulate page replacement algorithms: FIFO and optimal. Frame allo-
cation has to be done as per user input and use dynamic allocation for all data structures.
2. Write a C program to simulate LRU Page Replacement. Frame allocation has to be done as
per user input and dynamic allocation for all data structures.
66
LAB NO: 11
Objectives:
2. To write a menu driven C program to simulate the following disk scheduling al-
gorithm : SSTF, SCAN, C-SCAN, C-LOOK.
1. Introduction
In operating systems, seek time is very important. Since all device requests are linked in
queues, the seek time is increased causing the system to slow down. Disk Scheduling
Algorithms are used to reduce the total seek time of any request.
By using these algorithms we can keep the Head Movements (# tracks) to the least
amount as possible. The less the head has to move the faster the seek time will be.
Problem :
Given the following queue -- 95, 180, 34, 119, 11, 123, 62, 64 with the Read-write head
initially at the track 50 and the tail track being at 199 let us now discuss the different
algorithms.
67
LAB NO: 11
SCAN :
This approach works like an elevator does. It scans down towards the nearest end and
then when it hits the bottom it scans up servicing the requests that it didn't get going down.
If a request comes in after it has been scanned it will not be serviced until the process
comes back down or moves back up. This process moved a total of 230 tracks. Once again
this is more optimal than the previous algorithm, but it is not the best.
68
LAB NO: 11
Circular scanning works just like the elevator to some extent. It begins its scan toward
the nearest end and works it way all the way to the end of the system. Once it hits the
bottom or top it jumps to the other end and moves in the same direction. Keep in mind
that the huge jump doesn't count as a head movement. The total head movement for this
algorithm is only 187 track, but still this isn't the most sufficient.
C-LOOK :
This is just an enhanced version of C-SCAN. In this the scanning doesn't go past the last
request in the direction that it is moving. It too jumps to the other end but not all the way
to the end. Just to the furthest request. C-SCAN had a total movement of 187 but this scan
(C-LOOK) reduced it down to 157 tracks.
From this you were able to see a scan change from 644 total head movements to just 157.
You should now have an understanding as to why your operating system truly relies on
the type of algorithm it needs when it is dealing with multiple processes.
69
LAB NO: 11
Lab Exercise :
1. Develop a menu driven program to simulate the following disk scheduling algo-
rithms: SSTF, SCAN, C-SCAN, C-LOOK.
Additional Exercise :
1. Develop a menu driven program to simulate the following disk scheduling algo-
rithms: FCFS, LOOK.
70
LAB NO: 12
Objectives:
Types of RTSs
Real-time computing is of two types: hard and soft. A hard real-time system has the most
stringent requirements, guaranteeing that critical realtime tasks be completed within their
deadlines. Safety-critical systems are typically hard real-time systems. A soft real-time
system is less restrictive, simply providing that a critical real-time task will receive pri-
ority over other tasks and that it will retain that priority until it completes. Many com-
mercial operating systems-as well as Linux-provide soft real-time support.
Process Characteristics
Certain characteristics of the processes are as follows: First, the processes are considered
periodic. That is, they require the CPU at constant intervals (periods). Each periodic pro-
cess has a fixed processing timet once it acquires the CPU, a deadline d by which time it
must be serviced by the CPU, and a period p. The relationship of the processing time, the
deadline, and the period can be expressed as 0 <= t <= d <= p. The rate of a periodic task
71
LAB NO: 12
is 1 / p. The Figure below illustrates the execution of a periodic process over time. Sched-
ulers can take advantage of this relationship and assign priorities according to the deadline
or rate requirements of a periodic process.
2. Rate-Monotonic Scheduling
The rate-monotonic scheduling algorithm schedules periodic tasks using a static priority
policy with preemption. If a lower-priority process is running and a higher-priority pro-
cess becomes available to run, it will preempt the lower-priority process. Upon entering
the system, each periodic task is assigned a priority inversely based on its period. The
shorter the period, the higher the priority; the longer the period, the lower the priority.
The rationale behind this policy is to assign a higher priority to tasks that require the CPU
more often.
Furthermore, rate-monotonic scheduling assumes that the processing time of a periodic
process is the same for each CPU burst. That is, every time a process acquires the CPU,
the duration of its CPU burst is the same.
Let's consider an example. We have two processes P1 and P2. The periods for P1 and P2
are 50 and 100, respectively-that is, Pl =50 and P2 = 100. The processil1.g times are t1 =
20 for P1 and t2 = 35 for P2 . The deadline for each process requires that it complete its
CPU burst by the start of its next period. We must first ask ourselves whether it is possible
to schedule these tasks so that each meets its deadlines. If we measure the CPU utilization
of a process Pi as the ratio of its burst to its period -ti I Pi -the CPU utilization of P1 is
20/50 = 0.40 and that of P2 is 35/100 = 0.35, for a total CPU utilization of 75 percent.
Therefore, it seems we can schedule these tasks in such a way that both meet their dead-
lines and still leave the CPU with available cycles.
Example:
Suppose we use rate-monotonic scheduling, in which we assign P1 a higher priority than
P2, since the period of P1 is shorter than that of P2.
72
LAB NO: 12
P1 starts first and completes its CPU burst at time 20, thereby meeting its first deadline.
P2 starts running at this point and runs until time 50. At this time, it is preempted by P1,
although it still has 5 milliseconds remaining in its CPU burst. P1 completes its CPU burst
at time 70, at which point the scheduler resumes P2. P2 completes its CPU burst at time
75, also meeting its first deadline. The system is idle until time 100, when P1 is scheduled
again. Rate-monotonic scheduling is considered optimal in that if a set of processes can-
not be scheduled by this algorithm, it cannot be scheduled by any other algorithm that
assigns static priorities.
3. Earliest-Deadline-First Scheduling
Earliest-deadline-first (EDF) scheduling dynamically assigns priorities according to
deadline. The earlier the deadline, the higher the priority; the later the deadline, the lower
the priority. Under the EDF policy, when a process becomes runnable, it must announce
its deadline requirements to the system. Priorities may have to be adjusted to reflect the
deadline of the newly rmmable process. Note how this differs from rate-monotonic sched-
uling, where priorities are fixed.
Example:
P1 has values of p1 = 50 and t1 = 25 and that P2 has values of p2 = 80 and t2 = 35. The
EDF scheduling of these processes is shown in Figure below.
Process P1 has the earliest deadline, so its initial priority is higher than that of process P2
• Process P2 begins rmming at the end of the CPU burst for P1. However, whereas rate-
monotonic scheduling allows P1 to preempt P2 at the beginning of its next period at time
50, EDF scheduling allows process P2 to continue running. P2 now has a higher priority
than P1 because its next deadline (at time 80) is earlier than that of P1 (at time 100). Thus,
both P1 and P2 meet their first deadlines. Process P1 again begins running at time 60 and
completes its second CPU burst at time 85, also meeting its second deadline at time 100.
73
LAB NO: 12
P2 begins rum1ing at this point only to be preempted by P1 at the start of its next period
at time 100. P2 is preempted because P1 has an earlier deadline (time 150) than P2 (time
160). At time 125, P1 completes its CPU burst and P2 resumes execution, finishing at
time 145 and meeting its deadline as well. The system is idle until time 150, when P1 is
scheduled to run once again.
Unlike the rate-monotonic algorithm, EDF scheduling does not require that processes be
periodic, nor must a process require a constant amount of CPU time per burst. The only
requirement is that a process a1mom1ce its deadline to the scheduler when it becomes
runnable. The appeal of EDF scheduling is that it is theoretically optimal-theoretically, it
can schedule processes so that each process can meet its deadline requirements and CPU
utilization will be 100 percent. In practice, however, it is impossible to achieve this level
of CPU utilization due to the cost of context switching between processes and interrupt
handling.
Lab exercises
1. Write a C program to simulate Rate-Monotonic and Earliest-Deadline-First sched-
uling for real time systems.
REFERENCES
4. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 2nd
Edition, Prentice-Hall India, 2001.
5. Sartaj Sahni, Data Structures, Algorithms and Applications in C++, 2nd Edition,
McGraw-Hill, 2000.
6. Mark Allen Weiss, “Data Structures and Algorithm Analysis in C”, Pearson Educa-
tion, 2nd Edition, 2007.
74