Laboratory Manual: Department of Information Technology
Laboratory Manual: Department of Information Technology
Laboratory Manual: Department of Information Technology
COLLEGE OF ENGINEERING
S. No. 18, Plot No. 5/3, Karvenagar, PUNE – 411 052
Tel: 020-25473160 Fax: 020-25470909
Website: www.mmcoe.edu.in
LABORATORY MANUAL
SOFTWARE LABORATORY II
2015 course
Prepared By
Ms. Shital Kakad
Marathwada Mitra Mandal’s
COLLEGE OF ENGINEERING
S. No.18, Plot No.5/3, Karvenagar, PUNE - 411 052
---------------------------------------------------------------------------------------------------------------------
DEPARTMENT OF INFORMATION TECHNOLOGY
List of Assignments
Subject: Software Laboratory II Class: TE (IT)
Teaching Scheme: Examination Scheme:
Practical: 4 Hours/Week Practical: 50 Marks
Term Work: 25 Marks
Experiment No. Name of Assignment
Shell programming
Write a program to implement an address book with options given below: a) Create
1
address book. b) View address book. c) Insert a record. d) Delete a record. e) Modify a
record. f) Exit.
Process control system calls: The demonstration of FORK, EXECVE and WAIT system
calls along with zombie and orphan states.a. Implement the C program in which main
program accepts the integers to be sorted. Main program uses the FORK system call to
create a new process called a child process. Parent process sorts the integers using sorting
algorithm and waits for child process using WAIT system call to sort the integers using
any sorting algorithm. Also demonstrate zombie and orphan states.b. Implement the C
2
program in which main program accepts an integer array. Main program uses the FORK
system call to create a new process called a child process. Parent process sorts an integer
array and passes the sorted array to child process through the command line arguments of
EXECVE system call. The child process uses EXECVE system call to load new program
that uses this sorted array for performing the binary search to search the particular item in
the array.
3 Implement multithreading for Matrix Multiplication using pthreads.
Implement an assignment using File Handling System Calls (Low level system calls like
9
open, read, write, etc).
Implement a new system call in the kernel space, add this new system call in the Linux
kernel by the compilation of this kernel (any kernel source, any architecture and any Linux
10
kernel distribution) and demonstrate the use of this embedded system call using C
program in user space.
COURSE OUTCOMES:
CO1 X X X X X X X X
CO2 X X X X X X X X
OOPL
CO3 X X X X X X X X
CO4 X X X
CO5 X X X
CO6 X X X
Assignment No. 1 X
Assignment No. 2 X X X
Assignment No. 3 X X X
Assignment No. 4 X X
Assignment No. 5 X X
Assignment No. 6 X X
Assignment No. 7 X X X
Assignment No. 8 X X
Assignment No. 9 X
Assignment No. 10 X X X
Assignment No. 11 X X
Assignment No. 12 X X
Experiment No. 1
Title of Experiment: Basics of Shell programming
Write a program to implement an address book with options given below:
a) Create address book.
b) View address book.
c) Insert a record.
d) Delete a record.
e) Modify a record.
f) Exit.
Course Objectives:
To learn shell programming concepts and applications.
Theory:
Shell:
Computer understand the language of 0's and 1's called binary language. In early days of
computing, instruction are provided using binary language, which is difficult for all of us, to
read and write. So in Os there is special program called Shell. Shell accepts your instruction or
commands in English (mostly) and if its a valid command, it is pass to kernel. Shell is a user
program or it's environment provided for user interaction. Shell is an command language
interpreter that executes commands read from the standard input device (keyboard) or from a
file. Shell is not part of system kernel, but uses the system kernel to execute programs, create
files etc.
[4] ksh
David Korn developed the Korn shell, or ksh, about the time tcsh was introduced. Ksh is
compatible with sh and bash. Ksh improves on the Bourne shell by adding floating-point
arithmetic, job control, command aliasing and command completion. AT&T held proprietary
rights to ksh until 2000, when it became open source.
echo $SHELL
[2.8] cp – copy
copy files and directories
Usage: cp [OPTION] SOURCE FILE] [DESTINATION FILE]
eg. cp sample.txt sample_copy.txt After execution of command, the both source and destination
files are available.
[3.2] cat - used to display the contents of a small file on terminal usage:
cat [file name]
[3.6] wc - command is used to count lines, words and characters, depending on the option
used.
Usage: wc [options] [file name]
You can just print number of lines, number of words or number of charcters by using
following
options:
l : Number of lines
w : Number of words
c : Number of characters
TE IT (Course 2015) Software Laboratory II
Eg. wc file.txt
count number of lines, words and character (including whitespaces , newline etc) in a file.
Read 4 r--
Write 2 -w-
Execute 1 --x
Symbol Meaning
u User
g Group
o Other
+ Add Permission
- Remove a permission
r Read Permission
w Write permission
x Execute permission
expr1 <= expr2 If both expr1 and expr2 are numeric, expr
expr1 < expr2
compares them as numbers; otherwise it
expr1 = expr2
compares them as strings. If the
expr1!= expr2
comparison is true, the expression results
expr1 >= expr2 in 1; otherwise it results in 0.
expr1 > expr2
Implementation Details:
Input:
1. Inserting Record
Inserting the sample data for e.g Name and Contact Number 2.
4. Modify a record
Algorithm
3. perform the operations as per the Input (1. Insert / 2. Search / 3. Delete a record / 4. Modify
a Record/ 5. Display file).
3.1 Insertion
i. Ask user to Enter required data (In this case, “Name” and “Contact Number”)
Searching
ii. Compare that word with each record in the target file. (Use grep command)
Delete a Record
ii. Delete a record there on the line no in the target file. (use sed command)
Modify a Record
iii. Search and replace the actual record with new record. (Use sed Command).
Output:
Completion or error messages shall be displayed for respective operations mentioned above.
Conclusion:
In this experinment we have done basic shell scripts programs using different shell commands.
With same we implemented address book operation with options of Create address book, View
address book, Insert a record,Delete a record, Modify a record & Exit. For these operations cat,
grep and other basic commands were used.
FAQ’s
Q1. Explain Chmod, Grep, Cat & Sort Command with example.
Q2. Explain sed command with example.
Q3. Write shell script for sorting a given list of numbers.
Title of Experiment:
Process control system calls: The demonstration of fork, execve and wait system calls
along with zombie and orphan states.
Part A: Implement the C program in which main program accepts the integers to be sorted.
Main program uses the fork system call to create a new process called a child process. Parent
process sorts the integers using merge sort and waits for child process using wait system call to
sort the integers using quick sort. Also demonstrate zombie and orphan states.
Part B: Implement the C program in which main program accepts an integer array. Main
program uses the fork system call to create a new process called a child process. Parent process
sorts an integer array and passes the sorted array to child process through the command line
arguments of execve system call. The child process uses execve system call to load new program
that uses this sorted array for performing the binary search to search the particular item in the
array.
Course Objectives:
1. To demonstrate the process, memory, file and directory management issues under the
UNIX/LINUX operating system
2. To introduce LINUX basic commands
3. To make students how to make simple programs in LINUX and administrative task of
LINUX
Theory:
Processes carry out tasks within the operating system. A program is a set of machine code
instructions and data stored in an executable image on disk and is, as such, a passive entity; a
process can be thought of as a computer program in action. It is a dynamic entity, constantly
changing as the machine code instructions are executed by the processor. As well as the
program's instructions and data, the process also includes the program counter and all of the
CPU's registers as well as the process stacks
TE IT (Course 2015) Software Laboratory II
containing temporary data such as routine parameters, return addresses and saved variables. The
current executing program, or process, includes all of the current activity in the microprocessor.
Linux is a multiprocessing operating system. Processes are separate tasks each with their own rights
and responsibilities. If one process crashes it will not cause another process in the system to crash.
Each individual process runs in its own virtual address space and is not capable of interacting with
another process except through secure, kernel managed mechanisms. During the lifetime of a process
it will use many system resources. It will use the CPUs in the system to run its instructions and the
system's physical memory to hold it and its data. Linux must keep track of the process itself and of
the system resources that it has so that it can manage it and the other processes in the system fairly. It
would not be fair to the other processes in the system if one process monopolized most of the
system's physical memory or its CPUs. Linux is a multiprocessing operating system, its objective is
to have a process running on each CPU in the system at all times, to maximize CPU utilization. If
there are more processes than CPUs (and there usually are), the rest of the processes must wait
before a CPU becomes free until they can be run. Multiprocessing is a simple idea; a process is
executed until it must wait, usually for some system resource; when it has this resource, it may run
again. In a uniprocessing system, for example DOS, the CPU would simply sit idle and the waiting
time would be wasted. In a multiprocessing system many processes are kept in memory at the same
time. Whenever a process has to wait the operating system takes the CPU away from that process
and gives it to another, more deserving process. It is the scheduler which chooses which is the most
appropriate process to run next and Linux uses a number of scheduling strategies to ensure fairness.
Each process in a Linux system is identified by its unique process ID, sometimes referred to as
pid. Process IDs are 16-bit numbers that are assigned sequentially by Linux as new processes are
created. Every process also has a parent process. Thus, you can think of the processes on a Linux
system as arranged in a tree, with the init process at its root. The parent process ID, or ppid, is
simply the process ID of the process’s parent. When referring to process IDs in a C or C++
program, always use the pid_t typedef, which is defined in <sys/types.h>. A program can obtain
the process ID of the process it’s running in with the getpid() system call, and it can obtain the
process ID of its parent process with the getppid() system call.
The ps command displays the processes that are running on your system. The GNU/Linux
version of ps has lots of options because it tries to be compatible with versions of ps on several
other UNIX variants.These options control which processes are listed and what information
about each is shown. By default, invoking ps displays the processes controlled by the terminal or
terminal window in which ps is invoked. You can kill a running process with the kill command.
Simply specify on the command line the process ID of the process to be killed. The kill
command works by sending the process a SIGTERM, or termination, signal. This causes the
process to terminate, unless the executing program explicitly handles or masks the SIGTERM
signal.
Calling fork
When a program calls fork, a duplicate process, called the child process, is created. The parent
process continues executing the program from the point that fork was called. The child process, too,
executes the same program from the same place. So how do the two processes differ? First, the child
process is a new process and therefore has a new process ID, distinct from its parent’s process ID.
One way for a program to distinguish whether it’s in the parent process or the child process is to call
getpid. However, the fork function provides different return values to the parent and child processes
— one
process ―goes in‖ to the fork call, and two processes ―come out,‖ with different return
values. The return value in the parent process is the process ID of the child. The return value in
the child process is zero. Because no process ever has a process ID of zero, this makes it easy for
the program whether it is now running as the parent or the child process.
Process States
As a process executes, it changes state. The state of a process is defined as the current activity of
the process.
Process can have one of the following five states at a time.
1 New
The process is being created.
Ready
2 The process is waiting to be assigned to a processor. Ready processes are waiting to
have theprocessor allocated to them by the operating system so that they can run.
Running
3 Process instructions are being executed (i.e. The process that is currently being
executed).
Waiting
4
5 The process is waiting for some event to occur (such as the completion of an I/O
operation).
Terminated
5
The process has finished execution.
Zombie Process:
If a child process terminates while its parent is calling a wait function, the child process vanishes
and its termination status is passed to its parent via the wait call. But what happens when a child
process terminates and the parent is not calling wait? Does it simply vanish? No, because then
information about its termination—such as whether it exited normally and, if so, what its exit
status is—would be lost. Instead, when a child process terminates, is becomes a zombie
process.A zombie process is a process that has terminated but has not been cleaned up yet. It is
the responsibility of the parent process to clean up its zombie children. The wait functions do
this,too, so it’s not necessary to track whether your child process is still executing before waiting
for it. Suppose, for instance, that a program forks a child process, performs some other
computations, and then calls wait. If the child process has not terminated at that point, the parent
process will block in the wait call until the child process finishes. If the child process finishes
before the parent process calls wait, the child process becomes a zombie. When the parent
process calls wait, the zombie child’s termination status is extracted, the child process is deleted,
and the wait call returns immediately. What happens if the parent does not clean up its children?
They stay around in the system, as zombie processes.
Orphan Process:
An orphan process is a computer process whose parent process has finished or terminated,
though it remains running itself. In a Unix-like operating system any orphaned process will be
immediately adopted by the special init system process. This operation is called re- parenting
and occurs automatically. Even though technically the process has the "init" process as its
parent, it is still called an orphan process since the
Implementation Details:
PART A:
Algorithm:
1: START
2: Accept array of integers from the user
3: Call Merge_sort() to sort the array of integers
4: Call fork() to create child
5: Using wait system call, wait for child to finish execution
6: if (pid == 0) i.e. if child process, then call quick_sort() to sort array using quick sort.
7: END
Input:
1: Array of Integers
Steps to execute:
Input:
1: Array of Integers
2: Number to find
Steps to execute:
Conclusion:
Using the fork() and wait () system calls we created new processes and by manipulating the
sleep time for both the processes, we demonstrated the zombie and orphan states for the
processes that we created. For orphan state we kept the child process in sleep and allowed the
parent to terminate, whereas for the zombie state we did not allow the parent process to wait
until the child finished its execution and let the child finish before parent, which made the child
zombie.Using execve function call we executed the second program from the child process and
passedthe sorted array to the second program which further performed binary search over it.
FAQ’s
Q1. What is a system call? Explain briefly execve system call.
Q2. List and explain different states of a process.
Q3. What is a process? Explain how Process is represented internally.
Course Objectives:
1. To familiarize the students with the Operating System.
2. To demonstrate the process, memory, file and directory management issues under the
UNIX/LINUX operating system
3. To make students how to make simple programs in LINUX and administrative task of
LINUX
Theory:
What is a Thread? Technically, a thread is defined as an independent stream of instructions that
can be scheduled to run as such by the operating system. But what does this mean? To the
software developer, the concept of a "procedure" that runs independently from its main program
may best describe a thread. To go one step further, imagine a main program (a.out) that contains a
number of procedures. Then imagine all of these procedures being able to be scheduled to run
simultaneously and/or independently by the operating system. That would describe a "multi-
threaded" program.
Thread Basics:
Thread operations include thread creation, termination, synchronization (joins,
blocking),scheduling, data management and process interaction. A thread does not maintain a list
of created threads, nor does it know the thread that created it. All threads within a process share
the same address space. Threads in the same process share:
◆ Process instructions
◆ Most data
◆ open files (descriptors)
◆ signals and signal handlers
◆ current working directory
◆ User and group id
Arguments:
◆ thread_return - If thread_return is not NULL, the return value of th is stored in the location
pointed to by thread_return.
Implementation Details:
Algorithm:
1: START
2: Accept 2 matrices from user
3: If number of columns in matrix1 equals number of rows in matrix2, goto step 5
4: Else goto step 15
5: Initialize result matrix to all 0’s.
6: Loop for each row in matrix1.
7: Loop for each columns in matrix2 and initialize output matrix to 0. This loop will run for each
rows of matrix1.
8: Loop for each columns in matrix1.
9: Create a new thread using pthread_create() function, call the multiply function with created
thread and pass the mat1[i,k] & mat2[k,j] for multiplication
10: Return the multiplication value from the function using pthread_exit() function
11: Using pthread_join() function, receive the multiplication of two numbers
12: Add this value to result matrix[i,j];
13: End all the loops.
14: Print the resultant matrix
15: END
Input:
1: Accept 2-matrices from user
Steps to execute:
Step 1: Compile file using gcc program_name.c –o program_name.out -lpthread
Step 2: Execute the program using ./program_name.out
FAQ’s
1. Write the use of -pthread flag with gcc.
2. What is difference between -pthread and -lpthread gcc flags?
3. What is difference between mutex and semaphores in Linux multithreading?
1. To demonstrate the process, memory, file and directory management issues under the
UNIX/LINUX operating system
2. To make students how to make simple programs in LINUX and administrative task of
LINUX
1. Use C / C++ and Unix commands, and develop various system programs under
Linux to make use of OS concepts related to process synchronization, shared memory, file
systems,etc.
2. Recognize CPU Scheduling, synchronization, and deadlock.
Theory:
Thread Synchronization:
Running several threads in most cases requires synchronization. There is a number of ways to
synchronize threads:
● Mutual exclusions – mutexes (Mutex – MUTual EXclusion);
● Conditional variables;
● Semaphores.
Using conditional variables and semaphores in multiple-threaded applications is similar to using
these synchronization tools in multiple-process applications. Using a mutex is a general method of
synchronizing threads. A mutex can be defined as a synchronization object, which is set in a special
signalling state, when it is not engaged by any thread. At any given time a mutex can only belong to
a single thread. Using a mutex guarantees that only one thread at a given moment completes the
critical section of code. A mutex can be also used in a single-thread code. The following operations
with mutexes are available: initialization, deletion, capture or opening, attempt to capture.
Synchronization objects are variables in process memory and have liveness of process objects.
Threads in different processes can communicate via synchronization objects,
3. When a process can display a file and there is a thread in this process, which
gets unique access to records. Just as locking is set, any other thread in any process,
displaying a file, which is trying to lock, is blocked until writing in a file is completed.
Mutex:
To synchronize threads via a mutex the following basic functions are used:
● pthread_mutex_init – initializes mutex;
● pthread_mutex_destroy – deletes mutex;
● pthread_mutex_lock – sets locking. In case locking has been set by another thread, the current thread is interrupted until a
Mutex scope can be either a certain process, or the entire system. In case of the former a mutex
can only be operated by threads, created by a process, within which a mutex is generated. In case
of the latter a mutex exists in shared memory and can be divided among threads of several
processes. By default a mutex is created within process scope and has process liveness.
int pthread_mutex_init(pthread_mutex_t *mp, const pthread_mutexattr_t *mattr)
A mutex, which is indicated by the first argument mp, is initiated with a default value, in case the
second argument mattr is equal to NULL, or with certain attributes, which have already been set
via pthread_mutexattr_init. The function pthread_mutex_init returns 0 upon successful
completion or another value, in case of error. When a mutex is initialized, it is in the on-state
(unlocked). Statically certain mutexes can be directly initialized with default values via the
constant PTHREAD_MUTEX_INITIALIZER
int pthread_mutex_lock(pthread_mutex_t *mutex);
To unlock (disengage) a mutex the function pthread_mutex_unlock is used. In this case a mutex
has to be closed, and a calling thread has to be its owner, i.e. a mutex has to be closed by this
thread. While any other threads are waiting to access a mutex, its owner, situated at the
beginning of the queue, is not locked. The function pthread_mutex_unlock returns 0 upon
successful completion or another value, in case of error.
int pthread_mutex_trylock(pthread_mutex_t *mutex);
There is another way of capturing a mutex without locking a thread. The function
pthread_mutex_trylock is trying to lock a mutex. It is a non-locking version of
pthread_mutex_lock. In case a mutex is already locked, calling returns an error, however, the
thread, calling this function, is not blocked. Otherwise, a mutex is closed, and a calling process
becomes its owner. The function pthread_mutex_trylock returns 0 upon successful completion
or another value, in case of error.
Producer-Consumer problem:
The producer–consumer problem (also known as the bounded-buffer problem) is a classic
example of a multi-process synchronization problem. The problem describes two processes, the
producer and the consumer, who share a common, fixed-size buffer used as a queue. The
producer's job is to generate a piece of data, put it into the buffer and start again. At the same
time, the consumer is consuming the data (i.e., removing it from the buffer) one piece at a time.
The problem is to make sure that the producer won't try to add data into the buffer if it's full and
that the consumer won't try to remove data from an empty buffer.
The solution for the producer is to either go to sleep or discard data if the buffer is full. The next
time the consumer removes an item from the buffer, it notifies the producer, who starts to fill the
buffer again. In the same way, the consumer can go to sleep if it finds the buffer to be empty.
The next time the producer puts data into the buffer, it wakes up the sleeping consumer. The
solution can be reached by means of inter-process communication, typically using semaphores.
An inadequate solution could
TE IT (Course 2015) Software Laboratory II
result in a deadlock where both processes are waiting to be awakened. The problem can also be
generalized to have multiple producers and consumers.
Implementation Details:
Algorithm for Producer Consumer problem using Mutex:
1: START
2: Declare a buffer structure containing the character buffer array along with mutex &
condition variables.
3: Initialize the condition variables using pthread_cond_init() and create 2 threads, one for
producer and another for consumer using pthread_create().
4: END
The Producer:
1: START
2: Start Loop
3: The producer thread acquires a lock on mutex using pthread_mutex_lock().
4: Check if the buffer is full
If yes wait for the consumer to consume 1 item from buffer using pthread_cond_wait()
function. After consumer signals, goto step 5.
5: Copy contents into buffer.
6: Signal to consumer that an item has been produced using pthread_cond_signal()
7: Unlock mutex variable using pthread_mutex_unlock().
8: End Loop
9: END
The Consumer:
1: START
2: Start Loop
3: The consumer thread acquires a lock on mutex using pthread_mutex_lock().
4: Check if the buffer is empty
If yes wait for the producer to produce 1 item into buffer using pthread_cond_wait() function.
After producer signals goto step 5.
5: Copy contents from buffer and display on screen.
6: Signal to producer that an item has been consumed using pthread_cond_signal()
7: Unlock mutex variable using pthread_mutex_unlock().
8. End Loop
9: END
The Consumer:
1: START
2: Start Loop
3: The consumer decreases the semaphore value and waits till it becomes positive using
sem_wait()
4: Copy contents from buffer and print.
5: Using sem_post() increase the value of semaphore.
6: End Loop
7: END
Input: NA
Steps to execute:
Step 1: Compile file using gcc program_name.c –o program_name.out -lpthread
Step 2: Execute the program using ./program_name.out
Conclusion:
We studied and implemented the producer-consumer problem using both mutex and semaphores.
Using mutex gives us locking control over the buffer which is shared by the two threads where
only one of the threads either producer or consumer can access buffer. A signalling mechanism is
available to signal the waiting thread about the status of the buffer. Using semaphores the
producer- consumer problem was handled with semaphore wait & post signals to the semaphore
variables.
FAQ’s
Course Objectives:
1. To demonstrate the functioning of OS basic building blocks like processes, threads under
the LINUX.
2. To demonstrate the functioning of OS concepts in user space like concurrency control (process
1. To implement basic building blocks like processes, threads under the Linux.
2. To develop various system programs for the functioning of OS concepts in user space like
concurrency control and file handling in Linux.
Theory:
1. Give readers priority: when there is at least one reader currently accessing the
resource, allow new readers to access it as well. This can cause starvation if there are writers
waiting to modify the resource and new readers arrive all the time, as the writers will never be
granted access as long as there is at least one active reader.
2. Give writers priority: here, readers may starve.
3. Give neither priority: all readers and writers will be granted access to the resource in
their order of arrival. If a writer arrives while readers are accessing the resource, it will wait
until those readers free the resource, and then modify it. New readers arriving in the meantime
will have to wait.
Thus, readers are processes that are not required to exclude one another and writers are processes
that are required to exclude all other processes, readers and writers alike.
Mutex:
To synchronize threads via a mutex the following basic functions are used:
● pthread_mutex_init – initializes mutex;
● pthread_mutex_destroy – deletes mutex;
● pthread_mutex_lock – sets locking. In case locking has been set by another thread, the current thread is interrupted until a
A mutex, which is indicated by the first argument mp, is initiated with a default value, in case the
second argument mattr is equal to NULL, or with certain attributes, which have already been set
via pthread_mutexattr_init. The function pthread_mutex_init returns 0 upon successful
completion or another value, in case of error. When a mutex is initialized, it is in the on-state
(unlocked). Statically certain mutexes can be directly initialized with default values via the
constant PTHREAD_MUTEX_INITIALIZER
int pthread_mutex_lock(pthread_mutex_t *mutex);
To unlock (disengage) a mutex the function pthread_mutex_unlock is used. In this case a mutex
has to be closed, and a calling thread has to be its owner, i.e. a mutex has to be closed by this
thread. While any other threads are waiting to access a mutex, its owner, situated at the
beginning of the queue, is not locked. The function pthread_mutex_unlock returns 0 upon
successful completion or another value, in case of error.
int pthread_mutex_trylock(pthread_mutex_t *mutex);
There is another way of capturing a mutex without locking a thread. The function
pthread_mutex_trylock is trying to lock a mutex. It is a non-locking version of
pthread_mutex_lock. In case a mutex is already locked, calling returns an error, however, the
thread, calling this function, is not blocked. Otherwise, a mutex is closed, and a calling process
becomes its owner. The function pthread_mutex_trylock returns 0 upon successful completion
or another value, in case of error.
Implementation Details:
Algorithm for Reader-Writer problem using Mutex
1. Define number of reading processes & writing processes who are accessing the data
9. Decrement reader_count
10. If there are no more processes reading from the shared resource, allow writing process to
access the data
11. Writer gains access to the shared resource
Input: NA
Conclusion:
The readers-writers problem is a classical one in computer science. In this experiment we have
demonstrated this problem with two types of process that is Reader process and Writer process.
These process are synchronized with help of Mutex.
FAQ’s
Title of Experiment:
Implement the deadlock-free solution to Dining Philosophers problem to illustrate the problem of
deadlock and/or starvation that can occur when many synchronized threads are competing for
limited resources.
Course Objectives:
To demonstrate the process, memory, file and directory management issues under the
UNIX/LINUX operating system
To make students how to make simple programs in LINUX and administrative task of LINUX.
Use C / C++ and Unix commands, and develop various system programs under Linux to make use
of OS concepts related to process synchronization, shared memory, file systems, etc.
Theory:
Deadlock:
Starvation:
Starvation is a situation where, a process that needs several popular resources may have to wait
indefinitely, because at least one of the resources that it needs is always allocated to some other
process.
One simple solution is to represent each chopstick with a semaphore. A philosopher tries to grab a
chopstick by executing a wait () operation on that semaphore; she releases her chopsticks by
executing the signal() operation on the appropriate semaphores. Although this solution guarantees
that no two neighbors are eating simultaneously, it nevertheless must be rejected because it could
create a deadlock. Suppose that all five philosophers become hungry simultaneously and each
grabs her left chopstick. All the elements of chopstick will now be equal to 0. When each
philosopher tries to grab her right chopstick, she will be delayed forever. A satisfactory solution to
the dining-philosophers problem must guard against the possibility that one of the philosophers
will starve to death. A deadlock-free solution does not necessarily eliminate the possibility of
starvation.
A semaphore is an object that consists of a counter, a waiting list of processes and two methods
(e.g., functions): signal and wait.
Semaphores methods:
sem_wait() decrements (locks) the semaphore pointed to by sem. If the semaphore's value is
greater than zero, then the decrement proceeds, and the function returns, immediately. If the
semaphore currently has the value zero, then the call blocks until either it becomes possible to
perform the decrement (i.e., the semaphore value rises above zero), or a signal handler interrupts
the call.
sem_post() increments (unlocks) the semaphore pointed to by sem. If the semaphore's value
consequently becomes greater than zero, then another process or thread blocked in a sem_wait()
call will be woken up and proceed to lock the semaphore.
Implementation Details:
When a philosopher is hungry See if chopsticks on both sides are free acquire chopsticks eat
restore the chopsticks
void put_forks(int i)
{
wait(mutex);
state[i] = THINKING;
test(LEFT);
test(RIGHT);
signal(mutex);
}
Steps to execute:
Using semaphores we demonstrated the deadlock and starvation solution of Dining Philosophers
Problem. We also studied the concept of thread synchronization using semaphores.
FAQ’s
Pipes : Full duplex communication between parent and child processes. Parent process writes a
pathname of a file (the contents of the file are desired) on one pipe to be read by child process and
child process writes the contents of the file on second pipe to be read by parent process and
displays on standard output.
FIFOs: Full duplex communication between two independent processes. First process accepts
sentences and writes on one pipe to be read by second process and second process counts number
of characters, number of words and number of lines in accepted sentences, writes this output in a
text file and writes the contents of the file on second pipe to be read by first process and displays
on standard output.
Course Objectives:
1. To demonstrate the process, memory, file and directory management issues under the
UNIX/LINUX operating system
3. To make students how to make simple programs in LINUX and administrative task of
LINUX
1. Use C / C++ and Unix commands, and develop various system programs under Linux
to make use of OS concepts related to process synchronization, shared memory, file systems,
etc.
2. Recognize CPU Scheduling, synchronization, and deadlock
Theory:
PIPES:
A pipe is a communication device that permits unidirectional communication. Data written to the
―write end‖ of the pipe is read back from the ―read end. ‖ Pipes are serial devices;
the data is always read from the pipe in the same order it was written. Typically, a pipe is used to
communicate between two threads in a single process or between parent and child processes. A
pipe’s data capacity is limited. If the writer process writes faster than the reader process consumes
the data, and if the pipe cannot store more data, the writer process blocks until more capacity
becomes available. If the reader tries to read but no
There are two types of pipes for two-way communication: anonymous pipes and named pipes.
Anonymous pipes enable related processes to transfer information to each other. Typically, an
anonymous pipe is used for redirecting the standard input or output of a child process so that it can
exchange data with its parent process. To exchange data in both directions (duplex operation), you
must create two anonymous pipes. The parent process writes data to one pipe using its write
handle, while the child process reads the data from that pipe using its read handle. Similarly, the
child process writes data to the other pipe and the parent process reads from it. Anonymous pipes
cannot be used over a network, nor can they be used between unrelated processes.
Properties of Pipe:
Pipes do not have a name. For this reason, the processes must share a parent process. This is the
main drawback to pipes. However, pipes are treated as file descriptors, so the pipes remain open
even after fork and exec.
Pipes do not distinguish between messages; they just read a fixed number of bytes. Newline (\n)
can be used to separate messages. A structure with a length field can be used for message
containing binary data.
Pipes can also be used to get the output of a command or to provide input to a command.
Creating Pipes:
To create a pipe, invoke the pipe command. Supply an integer array of size 2.The call to pipe
stores the reading file descriptor in array position 0 and the writing file descriptor in position 1.
Data written to the file descriptor write_fd can be read back from read_fd.
If the parent wants to receive data from the child, it should close write_fd, and the child should
close read_fd. If the parent wants to send data to the child, it should close read_fd, and the child
should close write_fd. Since descriptors are shared between the parent and child, we should
always be sure to close the end of pipe we aren't concerned with. On a technical note, the EOF will
never be returned if the unnecessary ends of the pipe are not explicitly closed.
The mkfifo function takes the path of the file and the mode (permissions) with which the file
should be created. It creates the new named pipe file as specified by the path.
● Write (using write function call) to a named pipe is guaranteed to be atomic. It is atomic even
if the named pipe is opened in non-blocking mode.
● Named pipes have permissions (read and write) associated with them, unlike anonymous
pipes. These permissions can be used to enforce secure communication.
● Named pipes can only be used for communication among processes on the same host
machine.
● Named pipes can be created only in the local file system of the host, that is, you cannot create
a named pipe on the NFS file system.
● Due to their basic blocking nature of pipes, careful programming is required for the client and
server, in order to avoid deadlocks.
Server
1: START
2: Create two fifos i.e named pipes using mkfifo() function.
3: Open the pipe1 in read only mode.
4: Read and store the pipe1 contents in a buffer.
5: Calculate the number of lines, characters & words in the contents of pipe1.
6: Open pipe2 file in write only mode using the open() function.
7: Write the number of characters, lines & words into the opened pipe2.
8: END
Steps to execute:
Steps for executing Pipe & Signal:
Step 1: Compile file using ―gcc program_name.c –o program_name.out Step 2: Execute the
program using ―./program_name.out
Conclusion:
Thus we have implemented inter process communication in Linux using Pipes for Full duplex
communication between parent and child processes, FIFOs for Full duplex communication
between two independent processes, Signals for Detecting the termination of multiple child
processes with the help of SIGCHLD signal
FAQ’s
1. Explain the use of | operator with the example of multiple commands. (At least three
examples with practical demonstration is expected).
2. What is difference between pipe and shared memory implementation in Linux IPC?
3. What is difference between pipe and FIFO? Explain at least three points.
5. Explain the situation where FIFO is appropriate structure used over pipe.
Course Objectives:
1. To demonstrate the functioning of OS concepts in user space like concurrency control (process
1. To develop various system programs for the functioning of OS concepts in user space like
concurrency control and file handling in Linux.
Theory:
Shared Memory :
Shared memory is one of the three interprocess communication (IPC) mechanisms available under
Linux and other Unix-like systems. The other two IPC mechanisms are the message queues and
semaphores. In case of shared memory, a shared memory segment is created by the kernel and
mapped to the data segment of the address space of a requesting process. A process can use the
shared memory just like any other global variable in its address space.
Like message queues and semaphores, shared memory also comes in two flavors, the traditional
System V shared memory and the newer POSIX shared memory. In this post, we will look at the
System V shared memory calls. Example programs for a server and client processes
communicating via the System V shared memory are given near the end of the post.
The pathname is an existing file in the filesystem. The last eight bits of proj_id are used; these
must not be zero. A System V IPC key is returned.
As the name suggests, shmget gets you a shared memory segment associated with the given key.
The key is obtained earlier using the ftok function. If there is no existing shared memory segment
corresponding to the given key and IPC_CREAT flag is specified in shmflg, a new shared memory
segment is created. Also, the key value could be IPC_PRIVATE, in which case a new shared
memory segment is created. size specifies the size of the shared memory segment to be created; it
is rounded up to a multiple of PAGE_SIZE. If shmflg has IPC_CREAT | IPC_EXCL specified and
a shared memory segment for the given key exists, shmget fails and returns -1, with errno set to
EEXIST. The last nine bits of shmflg specify the permissions granted to owner, group and others.
The execute permissions are not used. If shmget succeeds, a shared memory identifier is returned.
On error, -1 is returned and errno is set to the relevant error.
With shmat, the calling process can attach the shared memory segment identified by shmid. The
process can specify the address at which the shared memory segment should be attached with shmaddr.
However, in most cases, we do not care at what address system attaches the shared memory segment
and shmaddr can conveniently be specified as NULL. shmflg specifies the flags for attaching the
shared memory segment. If shmaddr is not null and SHM_RND is specified in shmflg, the shared
memory segment is attached at address rounded down to the nearest multiple of SHMLBA, where
SHMLBA stands for Segment low boundary address. The idea is to attach at an address which is a
multiple of SHMLBA. On most Linux systems, SHMLBA is the same as PAGE_SIZE. Another flag is
SHM_RDONLY, which means the shared memory segment should be attached with read only access.
On success, shmat returns pointer to the attached shared memory segment. On error, (void *) -1 is
returned, with errno set to the cause of the error.
3 shmdt
#include <sys/types.h>
#include <sys/shm.h>
int shmdt (const void *shmaddr);
shmdt detaches a shared memory segment from the address space of the calling process. shmaddr
is the address at which the shared memory segment was attached, being the value returned by an
earlier shmat call. On success, shmdtreturns 0. On error, shmdt returns -1 and errno is set to
indicate the reason of error.
4 shmctl
#include <sys/ipc.h>
#include <sys/shm.h>
int shmctl (int shmid, int cmd, struct shmid_ds *buf);
The shmctl call is for control operations of a System V shared memory segment identified by the
shmid identifier, returned by an earlier shmget call. The data structure for shared memory
segments in the kernel is,
struct shmid_ds
{
struct ipc_perm shm_perm; /* Ownership and permissions */ size_t shm_segsz; /*
Size of segment (bytes) */
time_t shm_atime; /* Last attach time */ time_t shm_dtime; /*
Last detach time */ time_t shm_ctime; /* Last change time */
pid_t shm_cpid; /* PID of creator */
pid_t shm_lpid; /* PID of last shmat(2)/shmdt(2) */ shmatt_t shm_nattch; /* No. of
/* Sequence number */ };
The cmd parameter in shmctl specifies the command. The important commands are IPC_STAT,
IPC_SET and IPC_RMID. The IPC_STAT command copies the data in the kernel data structure
shmid_ds for the shared memory into the location pointed by the parameter buf. With the
IPC_SET command, we can set some of the fields in the shmid_dsstructure in the kernel for the
shared memory segment. The fields that can be modified are shm_perm.uid, shm_perm.gid and
the least significant 9 bits of shm_perm.mode. The command, IPC_RMID, marks a shared
memory segment for removal from the system. The shared memory segment is actually removed
after the last process detaches it from its address space.
The example has a server process which prints strings received from clients. The Server is a kind
of consumer process which consumes strings. The server creates a shared memory segment and
attaches it to its address space. The client processes attach the shared memory segment and write
strings in it. The client processes are producers; they produce strings. The server takes strings from
the shared memory segment and writes the strings on the terminal. The spooler prints strings in the
order they are written in the shared memory segment by the clients. So, effectively, there are n
concurrent processes producing strings at random times and the server prints them nicely in the
chronological order.
Implementation Details
2: Attach the shared memory segment to the address space of the client process
4: Client reads the content of the shared memory and write on to the standard output
Shared memory allows one or more processes to communicate via memory that appears in all of
their virtual address spaces. The pages of the virtual memory is referenced by page table entries in
each of the sharing processes' page tables. It does not have to be at the same address in all of the
processes' virtual memory. As with all System V IPC objects, access to shared memory areas is
controlled via keys and access rights checking. Once the memory is being shared, there are no
checks on how the processes are using it. They must rely on other mechanisms, for example
System V semaphores, to synchronize access to the memory.
FAQ.
Course Objectives:
1. To develop various system programs for the functioning of OS concepts in user space like
file handling in Linux.
Theory:
The file is the most basic and fundamental abstraction in Linux. Linux follows the everything-is-
a-file philosophy. Consequently, much interaction transpires via filesystem system calls such as
reading of and writing to files, even when the object in question is not what you would consider
your everyday file.
In order to be accessed, a file must first be opened. Files can be opened for reading, writing, or
both. An open file is referenced via a unique descriptor, a mapping from the metadata associated
with the open file back to the specific file itself. Inside the Linux kernel, this descriptor is
handled by an integer (of the C type int) called the file descriptor, abbreviated fd. File
descriptors are shared with user space, and are used directly by user programs to access files. A
large part of Linux system programming consists of opening, manipulating, closing, and
otherwise using file descriptors.
File descriptors:
The operating system assigns internally to each opened file a descriptor or an identifier (usually
this is a positive integer). When opening or creating a new file the system returns a file
descriptor to the process that executed the call. Each application has its own file descriptors.
Byconvention, the first three file descriptors are opened at the beginning of each process. The 0
file descriptor identifies the standard input, 1 identifies the standard output and 2 the standard
output for errors. The rest of the descriptors are used by the processes when opening an ordinary,
pipe or special file, or directories. There are five system calls that generate file descriptors:
create, open, fcntl, dup and pipe. The following section presents the way to use the most
common system calls in order to make input-output operations on files, as well as operations to
handle files and directories in the Linux operating system.
This function returns the file descriptor or in case of an error -1. The number of arguments that
this function can have is two or three. The third argument is used only when creating a new file.
When we want to open an existing file only two arguments are used. The function returns the
smallest available file descriptor. This can be used in the following system calls: read, write,
lseek and close. The effective UID or the effective GID of the process that executes the call has
to have read/write rights, based on the value of the argument flags. The file pointer is places on
the first byte in the file. The argument flags is formed by a bitwise OR operation made on the
constants defined in the fcntl.h header.
O_RDONLY Opens the file for reading.
O_WRONLY Opens the file for writing.
O_RDWR The file is opened for reading and writing.O_APPEND It writes successively to the end of the file.
O_CREAT The file is created in case it didn't already exist.
O_EXCL
O_NONBLOCK If the file exists and O_CREAT is positioned, calling open will fail.
In the case of pipes and special files, this causes the open system call
O_TRUNC If the file exists all of its content will be deleted.
O_SYNC It forces to write on the disk with function write.
Though it slows down all the system, it can be useful in critical situations. and any other future
I/O operations to never block. The third argument, mod, is a bit-wise OR made between a
combination of two from the following list:
S_IRUSR, S_IWUSR, S_IXUSR
Owner: read, write, execute.
S_IRGRP, S_IWGRP, S_IXGRP
Group: read, write, execute.
S_IROTH, S_IWOTH, S_IXOTH
Others: read, write, execute.
The above define the access rights for a file and they are defined in the sys/stat.h header.
The function returns the number of bytes read, 0 for end of file (EOF) and -1 in case an error
occurred. It reads noct bytes from the open file referred by the fd descriptor and it puts it into a
buffer buf. The pointer (current position) is incremented automatically after a reading that certain
amount of bytes. The process that executes a read operation waits until the system puts the data
from the disk into the buffer.
The function returns the number of bytes written and the value -1 in case of an error. It writes
noct bytes from the buffer buf into the file that has as its descriptor fd. It is interesting to note
that the actual writing onto the disk is delayed. This is done at the initiative of the root, without
informing the user when it is done. If the process that did the call or an other process reads the
data that haven't been written on the disk yet, the system reads all this data out from the cache
buffers. The delayed writing is faster, but it has three disadvantages:
● a disk error or a system error may cause loosing all the data
● a process that had the initiative of a write operation cannot be informed in case a writing error
occurred
● the physical order of the write operations cannot be controlled.
The function returns 0 in case of success and -1 in case of an error. At the termination of a
process an open file is closed anyway.
1. opendir()
Syntax : DIR * opendir (const char * dirname );
opendir () takes dirname as the path name and returns a pointer to a DIR structure. On error
returns NULL.
2. readdir()
Syntax: struct dirent * readdir ( DIR *dp) ;
A directory maintains the inode number and filename for every file in its fold. This function
returns a pointer to a dirent structure consisting of inode number and filename.'dirent' structure is
defined in <dirent.h> to provide at least two members – inode number and directory name.
struct dirent
{
ino_t d_ino ; // directory inode number
char d_name[]; // directory name
}
3. closedir()
Syntax: int closedir ( DIR * dp);
Input:
Enter information to be written to the file
HELLO
Output:
Information read from the file
HELLO
Conclusion:
The file is the most basic and fundamental abstraction in Linux. Linux follows the everything-is-
a-file philosophy. Consequently, much interaction transpires via filesystem system calls such as
reading of and writing to files, even when the object in question is not what you would consider
your everyday file. In order to be accessed, a file must first be opened. Files can be opened for
reading, writing, or both.
FAQ:
1. Write a program to implement “cat” Unix command using system calls.
2. Program to get the attribute of a file or directory on linux using system calls.
3. Write a program that will list all files in a current directory and all files in subsequent sub
directories.
Title of Experiment:
Implement a new system call, add this new system call in the Linux kernel (any kernel source,
any architecture and any Linux kernel distribution) and demonstrate the use of same.
Course Objectives:
2. To demonstrate the process, memory, file and directory management issues under the
UNIX/LINUX operating system
4. To make students how to make simple programs in LINUX and administrative task of
LINUX
Theory:
System Call:
In computing, a system call is how a program requests a service from an operating system's
kernel. This may include hardware-related services (for example, accessing a hard disk drive),
creation and execution of new processes, and communication with integral kernel services such
as process scheduling. System calls provide an essential interface between a process and the
operating system. In most systems, system calls are possible to be made only from user space
processes, while in some systems, OS/360 and successors for example, privileged system code
also issues system calls.
System calls are generally not invoked directly, but rather via wrapper functions in glibc (or
perhaps some other library). Often, but not always, the name of the wrapper function is the same
as the name of the system call that it invokes. For example, glibc contains a function truncate()
which invokes the underlying "truncate" system call.
On Unix, Unix-like and other POSIX-compliant operating systems, popular system calls are
open, read, write, close,wait, exec, fork, exit, and kill. Many modern operating systems have
hundreds of system calls. For example, Linux and OpenBSD each have over 300 different calls,
NetBSD has close to 500, FreeBSD has over 500, while Plan 9 has 51.
TE IT (Course 2015) Software Laboratory II
Tools such as strace and truss allow a process to execute from start and report all system calls the
process invokes, or can attach to an already running process and intercept any system call made
by said process if the operation does not violate the permissions of the user. This special ability
of the program is usually also implemented with a system call, e.g. strace is implemented with
ptrace or system calls on files in procfs.
Implementing system calls requires a control transfer which involves some sort of architecture-
specific feature. A typical way to implement this is to use a software interrupt or trap. Interrupts
transfer control to the operating system kernel so software simply needs to set up some register
with the system call number needed, and execute the software interrupt.
● Process Control
A running program needs to be able to stop execution either normally or abnormally. When
execution is stopped abnormally, often a dump of memory is taken and can be examined with a
debugger.
● load
● execute
● terminate process
● File management
Some common system calls are create, delete, read, write, reposition, or close. Also, there is a
need to determine the file attributes – get and set file attribute. Many times the OS provides an
API to make these system calls.
■ create file, delete file
■ open, close
● Device Management
Process usually require several resources to execute, if these resources are available, they will be
granted and control returned to the user process. These resources are also thought of as devices.
Some are physical, such as a video card, and others are abstract, such as a file. User programs
request the device, and when finished they release the device. Similar to files, we can read, write,
and reposition the device.
● request device, release device
● Information Maintenance
Some system calls exist purely for transferring information between the user program and the
operating system. An example of this is time, or date. The OS also keeps information about all its
processes and provides system calls to report this information.
■ get/set time or date
● Communication
5. since a number is associated with each system call, system call interface
invokes/dispatch intended system call in OS kernel and return status of the system call and
any return value
6. increment stack pointer
Syscall() function
syscall() is a small library function that invokes the system call whose assembly language
interface has the specified number with the specified arguments. Employing syscall() is useful,
for example, when invoking a system call that has no wrapper function in the C library. syscall()
saves CPU registers before making the system call, restores the registers upon return from the
system call, and stores any error code returned by the system call in errno if an error occurs.
Symbolic constants for system call numbers can be found in the header file <sys/syscall.h>. The
return value is defined by the system call being invoked. In general, a 0 return value indicates
success. A -1 return value indicates an error, and an error code is stored in errno.
1: START
2: Go to directory usr/src/linux-3.18.3
3: Create a new directory named ―addnum and create ―addnum.c file for the system call
4: Add the code for adding 2 numbers
asmlinkage long sys_addnum(int i, int j)
{
printk(KERN_INFO "Addnum is working! Now adding %d and %d", i, j); return i+j;
}
9: Open the file /usr/src/linux-3.18.3/include/linux/syscalls.h and just before the last #endif
statement add the following line
asmlinkage long sys_addnum(int i, int j);
11: Write a C code and using syscall function and the line number at which we have added
the syscall in step 8
Thus we have implemented and added a new system call in Linux Kernel to add 2 numbers using
the steps defined above and have used the system call to implement addition of 2 numbers.
FAQ’s
Q1. Explain the importance of make file in Linux