BM 110

 Simple programs to work in UNIX

 Simple programs to work in C
 Implementation of stack using arrays and pointers
 Implementation of Queue using arrays and pointers
 Implementation of Circular Queue
 Binary Tree Traversal
 Binary Tree Implementation
 Internal sorting program
 External sorting program
 Travelling salesmen problem
 N- queen problem
 Exercise 1: Unix Fundamentals

1. What is an Operating System ?

A computer system is just a collection of metal, silicon, communications equipment and

magnetic media. The operating system (OS) controls the computers and acts as
intermediate between the user and the computer. OS co-ordinates with inner workings of
the computer.
2. Main features of UNIX

It is a popular multi user time sharing operating system intended for document
preparation and program development tasks. It is written in high-level languages, ‘C’
with careful isolation and confinement of machine dependent features. Some of the
salient features of UNIX:
 Portability: It is available and portable on a wide range of different hardware. It is
written with hardware-dependent code into a few modules only.
 Multi user Operation: It provides more than one users on suitable installations
with proper communication interface and memory management hardware. In
addition to local users, remote users can also get hooked onto the system and
perform file transfer in network configuration.
 Device independence: Files and devices such as disks, tapes are treated in a
uniform manner. I-O redirection is possible at both the command language and
system call levels.
 Hierarchical File system: It’s hierarchical file system helps in organizing / storing
the information effectively. It offers maximum flexibility in grouping information
in way that reflects its natural structure.
 Multitasking Operating system: This means that the system can perform several
tasks – called “processes” at the same time.
3. Unix System Architecture
The Unix System Architecture is shown in the Figure 1. The layers of architecture are
described:
  Kernel is the part of the system which manages the resources of whatever
computer system it stays on, to keep track of printers, disks, tapes, etc.,
 File System is responsible for organizing the data. It not only acts as a
repository for data but provides the means of organizing the layout of the data
storage in complex ways.
 Shell is a command interpreter. It is a utility program. Programs such as shell
and editors shown in the outer layers communicate with the underlying kernel
by invoking a well-defined set of “system calls”.

Figure 1. Unix System Architecture

 Applications programs like the standard C compiler, cc, and exist on the
outermost layer. It invokes a c preprocessor (cpp), assemblers (as), etc.,
 There are two types of users. Super user is known an system administrator. He is
responsible for creating, allowing, modifying, or deleting / disallowing the access
to the UNIX system by other users. Ordinary users can access the files.
 Minimum requirements of Unix System:

8 MB of RAM space

10 MB Hard Disk

16-bit CPU

 Few of the Unix versions are:

AT & T version 7, System V etc.,

 Identify the latest version of UNIX, its features and requirements.

 Identify the UNIX version in your lab and the system configuration.
 Exercise 2 : Getting Started

 Login process

After the boot-up process, the system displays the prompt

Login:

Type the username in lower case, followed by pressing <return> key

If the password feature is enabled, the system responds with

Password:

The password typed by user will not appear on the screen. Finish the entry of

password by pressing <return> key.

 b) Prompt

The standard prompt symbols of the corresponding shell are:

$ Bourne Shell

% C Shell

# for super user

The appearance of prompt on the screen indicates that UNIX has finished execution

of the previous command and it is ready to accept the new command.

 Logging OFF

After finishing the work with the system, sign-off simply by typing Ctrl and D keys

together. This should log out the screen and displays the login: prompt again.
 Exercise 3: Simple Commands in UNIX

 Date command tells the system to print the date and time.

$ date

Output:

 who command tells about all the users who is currently logged-in into the unix
server. The output contains userid, name of the terminal, month date time.

$ who

Output:

 who am I command tells about the user currently logged into that particular
system.

$ who am i

Output:

 Password command is used to change the password of the user. The new
password should be typed twice.

$ password

Output:
 Exercise 4: Files and Directory

Unix files and directories can be organized by the users. The guidelines for naming
are:
 Can be one to fourteen characters long

 Avoid using special characters

 It is case sensitive. Upper-case letters are distinguished from lower-case

letters.

The UNIX hierarchy is given in Figure 2.

root

bin dev etc lib tmp usr

<studentuserid>

Figure 2. The UNIX Hierarchy

The student userid is a home directory for the user and it is login name. UNIX system
always associate each user of the system with a particular directory. When logged-into
the system, the user is automatically placed into a directory called HOME directory.

 A path name enables to uniquely identify a particular file to the UNIX system.

Absolute path name contains complete road may of directory or file from root
directory onwards. Example
/usr/studentuserid

Relative path name are relative to the directory the user is in. Example:

./studentuserid
 To print the current working directory

$ pwd
Output:

 To Create the file “file1” with cat command

$ cat > file1

Hai, it is my first file
<ctrl-d>

 To create the directory in the name of BMI

$ mkdir BMI

 To change the working directory with cd

$ cd BMI

Change the directory again to Home directory

$__________
 ls command is used to list the contents of the directory.

$ ls

Output:

To list all the files including the sub-directories:

$ ls –a

Output:

To list the files with long options:

$ ls – l

Output:

The listing includes file mode, number of links, owner name, group name, file
size in bytes, date and time of last modification, and file name or directory name.

To get the information about the particular directory use –d option:

$ ls –ld BMI

Output:

 To copy the files use cp <old file> <new file>:

$ cp file1 file2
 moving and rename the file file2 as file3

$ mv file2 file3

 remove the file file3

$ rm file3

 to remove the directory

$ rmdir bmi

 ownership and protection

For every file and every directory in the file system, there are 3 classes of users who
may have access. Those ownerships are:

a. User or Owner: The user who initially created the file

b. Group: Several users can be combined into a user group, so there
is a group ownership associated with each file and directory.
c. Others or public or world: Other users of the UNIX system i.e.
anyone who has a user name and can give access to the system.
Permissions describe what kind of things can be done with directory or file. Read
permission to read the file content, write permission to change the file content and
execute permission for a file to execute.

Combining the 3 types of permission with the 3 type of users:

r w x r w x r w x

user group other

Note: r for read, w for write, x for execute

u for user, g for group, o for public, a for all the three,
+ for add permission, - for remove permission
Changing permission with a symbolic way:

$ Chmod go – rx file1
who is Action permission file
affected affected affected

Another example:

$ chmod g-w, o+r file1

Changing permission in a numerical way:

(numerical assignment: r: 4, w:2, x:1
for all: 7, rw:6 rx:5 wx:3)

$ chmod 644 file1

(644 means: 6 indicates rw by owner

4 indicates readable by group and others)
 Exercise 5: Working with vi editor

 The screen editor used in Unix system V is vi. vi stands for “visual”. The vi can
be invoked by using the command:

$ vi filename

 To come out from the vi editor, Press <esc> key and

ZZ Press upper case Z twice to save the content and system takes the user to
command line.

:wq Press the keys :wq in the same sequence, the contents are written onto the
disk and quit operation is executed thereby taking to the system prompt.

:q! Press the keys :q! in the same sequence, the contents are not written to the
disk. The system would then display the prompt

 To type any vi command, press <esc> key when text is finished

 Cursor movements

h moves cursor one character left

j moves cursor one line down
k moves cursor one line up
l moves cursor one character right

H moves cursor to the first character on the first line on the screen
M moves cursor to the first character on the middle line on the screen
L moves cursor to the first character on the last line on the screen

6l moves cursor to 6 characters to the right

^ moves cursor to the beginning of the file

$ moves cursor to the end of the file

 Scrolling

z current line is put at the top of the screen

z. current line is in the middle of the screen
z- current line is at the bottom of the screen
z+ first line of next screen
 <ctrl> E scrolls up one line
<ctrl> Y scrolls down one line

<ctrl> D scrolls down half-window

<ctrl> U scrolls up half-window

<ctrl> F move the window forward through the file

<ctrl>B move the window backward through the file

 The mistakes committed can be changed by undo

Lowercase u will simply undo last change.

Uppercase U command undo the various changes at the same time, but only those
made on the same line.

. dot command is used to do it again

 The x command is used to delete the character on which the cursor is placed. To
gobble 5 characters type x five times or 5x.

 To replace the character, type r followed by the character at that position. It keeps
on replacing until the <esc> key is pressed.

 To append the text, press a

 To insert the text, press i

 To delete the particular line type dd. To delete two lines type 2dd.

 To join lines by type J

 To position the cursor on 10th line, type 10G

 To search the character

Type / followed by the text and press <return> or <esc>

To continue the search

n find next occurrence in same direction

N find next occurrence in reverse direction
// always go forward search
?? always go backward search

 Cut and paste operations

Type dd command to delete the line and press lowercase p command to

puts the line back after its current line. The upper case P puts the lines
before the current line.

 To access Unix system command from vi

Type the key marked with :! followed by system command

To return to vi, press <ctrl> D

 Exercise 6: Utilities in UNIX

 Create the file “file2” to store the details of country and capital

India New Delhi

Malaysia Kula Lumpur
Japan Tokyo
United States New York

 Sorting the text file

To sort the file in the alphabetical order

$ sort file2

output:

To sort the file on the capital of country typed in the file

$ sort+1 file2

output:

To ignore the leading blanks

$ sort-b+1 file2

output

To save the sorted output

$ sort –o filesort +1 file2 (or) $ sort +1 file2 > filesort

 Count things in a file

The wc command counts the number of characters, words, and lines in a file.

$ wc file2

output:

The options are:

-l To count the lines
-w To count the words
-c To count the characters

 Finding the text pattern in a file

To find out the word “New” in file2

$ grep New file2

output:

To omit the searched line in the file

$ grep –v New file2

output:

To count the number of lines that match the pattern

$ grep –c New file2

output:

To show the line numbers of lines that match the string or pattern

$ grep –n New file2

output:
 Exercise 7: Shell Features

 Unix derives its power and flexibility largely out of the user interface that is
built into the system. The user interface within the UNIX is established by a
sophisticated utility program called sh (shell). It is a command interpreter. It
accepts commands from the user, interprets them and calls upon the kernel to
actually perform the operations required. The flavors of shell are Bourne
shell, C shell, Korn shell, and visual shell.

 The shorthand characters and their usage:

* represent any arbitrary group of characters

? represent any single character
[ ] enclose a list of characters,
- hyphen used inside the bracket indicates a range of characters.

$ ls file?
$ ls f*
$ ls file[1-5]

 Input and Output Redirection

Input redirection is used to display the content of the file to the standard
output file e.g. monitor.

$ cat < file1

output:

Output redirection is by storing the output of file into another file:

 $ ls > file4

To append the already existing file by output redirection

$ pwd >> file4

 Connecting commands with pipes

The output of one command can be given as an input to another command,

forming a pipe.

$ who | wc –l
output:

 Filters
A command which accepts its input from the standard input and produces the
output on the standard output, is known as filter.

$ ls –l | tee list of files

output:

 Grouped commands
Simple commands can be grouped by using ;

$ cat xyz; ls

 Standard shell variables

o HOME
This variable is set to the pathname of your HOME directory.
o IFS (Internal Field Separator)
This is set to list of characters that are used to separate words in a
command line. Normally, this would consist of a space, newline and
tab character. Key produced by <tab> and <return>

o MAIL
This variable’s value is name of the directory to which your mail is
sent via the mail command. Shell checks contents of this directory
whenever login. When something is mailed, you are intimated that the
mail has arrived for you.

o PATH
This names the directories which are searched by shell commands.
A colon is used to separate the directory names; there are no spaces.
path=.:/bin:/usr/bin
o PS1 (Prompt string 1) Normally $. It can be redefined./
o PS2
This prompt is used when UNIX thinks you have started a new line
without finishing a command. > You can continue the line by typing
backslash(\) before hitting a return key.
o TERM
This is used to identify the kind of terminal you would usually use.
Example:
$set
HOME=/usr/student1
IFS=
MAIL=/usr/mail/student1
PATH:/bin:/usr/bin
PS1=$
PS2=>
TERM=ansi
$
  Setting shell variables
To create shell variable type name and assign value
Age=25
Fruit=apple
There should not be any blank spaces surrounding the = sign.
When you login a sub-shell gets created for you. Some variables like PS1 and
PATH are given to it. Then shell will look for a .profile file and follows the
instructions it finds in .profile. System administrator would normally, give a
copy of this file in home directory. A typical .profile file contents are
reproduced below:
$ cat.profile
export MAIL PATH TERM
umask 22
TERM=ansi
$

 Some special directories

/bin : consists of user related command files which are most commonly used.
/dev : consists of special files associated with various devices
/etc : this directory consists of files which are essentially required for system
administration purposes.
/lib : library routines required for C program are kept in this directory
/tmp : it is a temporary file used for keeping the buffer files. These files are used in
editing ad sorting.
/usr: It is the directory under which most users keep their login directories, and
other files like their source program, data etc.
 Exercise 8. Shell Programming

 Scripts: it is a sequence of commands that can be stored in a file for

repeated execution
 Parameter passing: Data can be passed to variables within a shell script by
typing the values as arguments on command line
 Conditional Execution: the sequence of executed commands can be varied,
based on some external conditions (if..then..else construct)
 Case Selection: one of alternative command sequences can be selected for
command execution based on some external condition (case construct)
 Repetition: A sequence of commands can be executed repeatedly for a list
of values, each time assigning a new value to a shell variable (for
construct)
 Conditional repetition ( a sequence of commands can be executed
repeatedly until some external condition occurs – while statement)
 Comments: To enhance the readability it is possible to include the
comment lines in shell scripts. Anything which follows the # character in
the script is not processed by the shell.
 Writing the shell scripts
To write the shell script
Create a file and type in the commands/statements to be executed by the shell.
Make this file executable by using chmod command.

The procedure is illustrated below:

Step1 : create file
$ cat > sample
# simple shell script
cat file1 file2
echo “my first shell program”
<ctrl-d>
$
 Step 2:
$ chmod 755 sample
$ sh sample

 Make shell script interactive

echo display a prompt or message on screen or standard output file
read reads the value from the standard input file into shell variable

Example
$ cat > greet
echo “ may I know your name\?\n”
read name
echo “god bless you, $name\n”
$

 Shell script arguments

The arguments are referred by $1 and $2 respectively. $0 is reserved for the name
of the shell script itself.

$* - stands for all the arguments starting from $1

$# - number of arguments in the command line
$? – returns the exit status of previous command. Zero – for successful
$@ - similar to $*, but when enclosed in double quotes refer each word argument
instead of whole line
$- - shell options
$$ - exit status of last executed command
$! - process number of last background command
$@ - name of command beingexecuted.
$ echo * - display all files in current directory
$ echo “*” – display * as it is
 Back quote marks (‘) called grave accents.
Ex.
$DATE=’date’
$echo $DATE
the output is inserted at the precise point
 Shift command to shit over arguments
$ cat > pgshift
echo $1 $2 $3 $4
shift
shift
echo $1 $2 $3 $4
<ctrl-d>

It will throw away already assigned value of $1 and assigns the value of $1 to $2.
Then it sets the value of $2 to old value of $3 and so on.

 test command : perform the task based on conditions

Example:
$ Actor=Amitabh
$ test $Actor=Amitabh
$ echo $?
0

test command can be used to check the file status:

-r filename – whether the file exists and is readable
-w filename – file exists and writable
-f filename – file exists and not directory
-d filename – file exists and directory
-s filename – file exists and has a size greater than zero.
Number1 –eq number2  holds true if integers are equal
-ne, -gt, -lt, -le, -ge, AND, OR, !
 expr: Doing arithmetic within shell
expr 5+4
expr 4\*3
expr 5-3
expr 14/3
expr 14%3

To assign value $ var1=’expr 5+3’

 if condition
then
stmt1
stmtn.
Else
Stmts
fi
Example:
if test !-f $1
then
echo “file $1 not found\n”
exit 1
fi
 for variable in list of values
do
stmts
done

example:
for month in 1 2 3 4 5
do
cal $month 2007
done
 case construct example
case $1 in
0) echo zero::
1) echo one::
*) echo “ I cant understand”
esac
 while loop example
c=1
while test $c –le 10
do
echo $c
c=’expr $c+1’
done

 until loop example

until condition
do
stmts
done
 exit shell command
terminate the script and gives the script an exit status.
 Exercise 9 System Administration

 Use super-user privileges as less as possible,

 Routine work should not be done using these privileges
 Commands like rm,cp, mv should be used with caution as they may
irresponsibility damage the system, if not used properly.
 Unix File System: complete directory structure:
Bootblock, super block, i-nodes, data-block, free-block, free i-nodes

Boot block: first block, contains bootstrap program.

Super-block: contains all file info. (size info, name of file, name of vol, time last
update, time last backup, free block list, free i-node list)

i-nodes: contain more blocks- depends on file systems. – one i-node for every fileand
directory. – description of file, permissions and links

Data blocks: logical device – full of data blocks – direct/indirect blocks

 Make file system

Format using iv (initialize volume), format
Mkfs command for logical data structure
#/etc/mkfs<special-file>[i-nodes] [blocks]

Mounting file :known to kernel

#/etc/mount[devicename] [dirname]

unmount file
#/etc/unmount devicename
 $ ls –l /dev: list Devices special files
The presence of character c indicates character oriented device
B indicates block oriented device

During bootstrap
Kernel invoke init program, getty program display login prompt, login program
validate user. Getty would take place with login prompt.

Shut down system either by <ctrl-d> or shutdown

Check file system by #fsck [-y] [-n] [File System]

Manage the disk space by

du command gives about usage of disk space
df command to find the amount of free space

Backing up / restore file using tar

#tar key [options] [file]
c- create new backup tape
u – update
r- reads from backup
x – extract file names,
t- list name of files
f – forces tar to take place, mandatory
v – provides informational messages,
b – causes tar to use next argument as blocking factor for tape records. Default
blocking factor is 20.

A special shell script to add user: adman, admin, or sysadmsh

Chmod mode 4000: set user-id, mode 2000 : set group-id, mode 1000 – sticky bit
(shareable of executable files).

 Process management
Fork : create child process
Ps to view process id and parent process id
Kill to destroy the process

 Communication

Offline communication: mail and news

Online communication write, wall
Main and write by users, news and wall by system administrators

Messg –n : disallow further message

Uucp: communication between two unix system

Cu: call unix : allow a user connected as one Unix system to login temporarily to
another system, provided he/she has a valid user account in remote unix system
also.