LIST OF EXPERIMENTS

1. Installation of windows operating system

2. Illustrate UNIX commands and Shell Programming
3. Process Management using System Calls : Fork, Exit, Getpid, Wait, Close
4. Write C programs to implement the various CPU Scheduling Algorithms
5. Illustrate the inter process communication strategy
6. Implement mutual exclusion by Semaphore
7. Write C programs to avoid Deadlock using Banker's Algorithm
8. Write a C program to Implement Deadlock Detection Algorithm
9. Write C program to implement Threading
10. Implement the paging Technique using C program
11. Write C programs to implement the following Memory Allocation
Methods a. First Fit b. Worst Fit c. Best Fit
12. Write C programs to implement the various Page Replacement
Algorithms 13. Write C programs to Implement the various File Organization
Techniques 14. Implement the following File Allocation Strategies using C
programs
a. Sequential b. Indexed c. Linked
15. Write C programs for the implementation of various disk scheduling
algorithms 16. Install any guest operating system like Linux using VMware.
TOTAL: 45 PERIODS
1
Ex. No: 2a ILLUSTRATION OF UNIX COMMANDS
AIM
To study and execute basic UNIX commands,
COMMANDS IN UNIX

UNIX has a large number of commands. A UNIX command is a program written to perform
certain specific action. All UNIX commands are written in lower case letters. Almost all the commands
are cryptic. They can have zero, one or more number of arguments associated with them. UNIX
commands also have format specifiers represented by + character and options represented by hyphen (-).
There are two types of commands

∙ Internal or built-in commands – A command that does not have an independent existence is called
an internal command. The routines for an internal command will be a part of another program or
routine. Example echo, mkdir, cd.

∙ External commands –A command with independent existence in the form of a separate file is called
an external command. For example programs for the commands cat and ls, exist independently in a
directory called /bin directory.

1. GENERAL PURPOSE COMMANDS

1. Command :Who
Purpose :It is used to get the information about all the users currently working in the
system.
Syntax:who
Example :$ who
2. Command :Date
Purpose :It is used to display the system date and time.
Syntax:date
Example :$ date
3. Command :Cal
Purpose :It prints the calendar for the specified year and month.
Syntax: cal <month><year>
Example :$ cal 05 2003
4. Command : Clear
Purpose : It is used to clear the screen.
Syntax:clear
Example :$ clear

2
5. Command : uname
Purpose :It is used to display the details about the OS in which we are working.
Syntax:uname [options]
Example :$ uname –n
6. Command :pwd
Purpose :It is used to display the absolute pathname of current working directory.
Syntax:pwd
Example :$ pwd
7. Command :bc
Purpose :It is used to perform simple mathematical calculations.
Syntax:bc <operation>
Example :$ bc 3+5 8 ^d
8. Command :ls
Purpose :It is used to display the files in the current working directory.
Syntax:ls [options] <arguments>
Example :$ ls –p
9. Command :echo
Purpose :It echoes the argument on the standard output device.
Syntax:echo [options] <string>
Example :$ echo „BOOM‟
10. Command . man
Purpose . It gives details about the unix commands.
Syntax: man < command name >
Example :$ man echo

2. FILE MANIPULATION COMMANDS

1. Command :cat
Purpose :It is used to display the contents of the file as well as used to create a new file.
Syntax:cat <file name >
Example : $ cat devi
2. Command :more
Purpose :It is used to display the contents of the file on the screen at a time.
Syntax:more <file name >
Example : $ more devi

3
3. Command :cp
Purpose :It is used to copy one or more files.
Syntax:cat <source file name ><destination file name>
Example : $ cp devi latha
4. Command :mv
Purpose :It is used to move a file within a directory with different names and also used to
move a file to different directory with its original name.
Syntax:mv <source file name ><destination file name>
Example : $ mv devi jeya
5. Command :rm
Purpose :It is used to remove a file from the disk.
Syntax :rm <file name >
Example : $ rm devi

3. DIRECTORY COMMANDS
1. Command :mkdir
Purpose :It is used to create new directory or more than one directory.
Syntax:mkdir <directory name >
Example : $ mkdir riya
2. Command :rmdir
Purpose :It is used to remove the directory if it is empty.
Syntax:rmdir <directory name >
Example :$ rmdir riya
3. Command :cd
Purpose :It is used to change the control from one working directory to another specified
directory.
Syntax:cd <directory name >
Example : $ cd riya
4. Command :cd ..
Purpose :It is used to quit from current directory and move to the previous
directory.
Syntax : cd ..
Example : $ cd ..

4
4. COMMAND GROUPING & FILTER COMMANDS
1. Command :Head
Purpose :It is used to display the top portion of the file.
Syntax: head [options] <file name>
Example : $ head -5 devi
2. Command :Tail
Purpose :It is used to display the bottom portion of the file.
Syntax: tail [options] <file name >
Example : $ tail –5 devi
3. Command :Pr
Purpose :It is used to display the contents of the file by separating them into pages and each page
begins with the header information.
Syntax: pr [options] <file name >
Example : $ pr devi
4. Command :Cut
Purpose :It is used to extract selected fields or columns from each line of one or more files and
display them on the standard output device.
Syntax: cut [options] <file name >
Example : $ cut –c5 devi
5. Command :Paste
Purpose :It concatenates the line from each input file column by column with tab characters in
between them.
Syntax: paste [options] <file name >
Example : $ paste f1 f2
6. Command :Join
Purpose :It is used to extracts common lines from two sorted files and there should be the
common field in both file.
Syntax: join [options] <file name1 > <file name 2>
Example : $ join –a1 f1 f2
7. Command :Uniq
Purpose :It compares adjacent lines in the file and displays the output by
eliminating duplicate adjacent lines in it.
Syntax: uniq [options] <file name >
Example : $ uniq -c devi

5
8. Command :Sort
Purpose :It sorts one or more files based on ASCII sequence and also to merge the file.
Syntax: sort [options] <file name >
Example : $ sort -r devi
9. Command :Nl
Purpose :It is used to add the line numbers to the file.
Syntax: nl [options] [filename]
Example : $ nl devi
10. Command :Tr
Purpose :It is used to translate or delete a character or a string from the standard input to produce
the required output.
Syntax: tr [options] <string1> <string2>
Example : $ tr –t „a‟ „b‟ < devi>
11. Command :Tee
Purpose :It is used to read the contents from standard input or from output of another command
and reproduces the output to both in standard output and direct into output to one or more files.
Syntax: tee [options] <file name >
Example : $ tee date dat.txt
12. Command :grep
Purpose :It is used to search the specified pattern from one or more files.
Syntax: grep [options] <pattern> <file name >
Example : $ grep “anand” devi

RESULT

Thus the Basic Unix commands are executed and verified.

SAMPLE VIVA-VOCE QUESTIONS

1. What is Shell?
2. Difference between multiuser and multitask.
3. How the process can be identified?
4. Enumerate some of the most commonly used network commands in UNIX
5. Differentiate cat command from more command.

6
Ex. No: 2b SHELL PROGRAMMING
Ex. No: 2b (i) SWAPPING VALUES OF TWO VARIABLES AIM
To write and execute a simple shell program for swapping two numbers.

ALGORITHM
Step1. Start
Step2. Read the values of a and b
Step3. Interchange the values of a and b using another variable t as
follows. t = a
a=b
b=t
Step4. Print a and b
Step5. Stop
PROGRAM
clear
echo -n "Enter value for A : "
read a
echo -n "Enter value for B : "
read b
t=$a
a=$b
b=$t
echo "Values after Swapping"
echo "A Value is $a"
echo "B Value is $b"
RESULT
Thus the program for swapping two values is written and output is verified successfully.

Ex .No. 2(b)(ii) AREA & CIRCUMFERENCE OF CIRCLE

AIM
To write and execute a simple shell program to calculate area and circumference of a circle.
ALGORITHM
Step1. Start
Step2. Define constant pi = 3.14
Step3. Read the value of radius
Step4 . Calculate area using formulae. pi × radius2

7
Step5 . Calculate circumference using formulae. 2 × pi × radius
Step6 . Print area and circumference
Step7 . Stop
PROGRAM
clear
pi=`expr "scale=2; 22 / 7" | bc`
readonly pi # pi value cannot be altered
echo -n "Enter value for radius : "
read radius
area=`expr "scale=2; $pi * $radius * $radius" | bc`
circum=`expr "scale=2; 2 * $pi * $radius" | bc`
echo "Area : $area"
echo "Circumference : $circum"

RESULT
Thus the program for finding the area and circumference of a circle is executed and verified
successfully.

Ex. No: 2(b)(iii) CHECK A NUMBER ODD OR EVEN

AIM
To write shell program for finding whether the given number is odd or even using decision-making
constructs.
ALGORITHM
Step1 . Start
Step2 . Read number
Step3 . If number divisible by 2 then
Print "Number is Even", otherwise
Print "Number is Odd"
Step4 . Stop
PROGRAM
clear
echo -n "Enter a non-zero number : "
read num
rem=`expr $num % 2`
if [ $rem -eq 0 ]
then

8
echo "$num is Even"
else
echo "$num is Odd"
fi
RESULT
Thus the program to find whether the given number is odd or even is executed and output is
verified successfully.

Ex. No: 2(b)(iv) BIGGEST OF 3 NUMBERS

AIM
To write shell program to find the biggest of three numbers using decision-making constructs.
ALGORITHM
Step1 . Start
Step 2 . Read values of a, b and c
Step 3 . If a > b and a > c then
Print "A is the biggest"
Step 4.Otherwise , if b >c then
Print "B is the biggest "
Step 5.Otherwise,Print "C is the biggest"
Step 6. Stop
PROGRAM
clear
echo -n "Give value for A B and C: "
read a b c
if [ $a -gt $b -a $a -gt $c ]
then
echo "A is the Biggest number"
elif [ $b -gt $c ]
then
echo "B is the Biggest number"
else
echo "C is the Biggest number"
fi
RESULT

9
Thus the program to find the biggest of three numbers using decision-making constructs is
executed and output is verified successfully.

Ex. No: 2(b) (v) VOWEL OR CONSONANT

AIM
To write shell program to find whether the given alphabet is vowel or consonant using decision
making constructs.
Algorithm

Step1 : Start
Step2 : Read char
Step3 : If char is either 'a', 'e', 'i', 'o' or 'u' then Print "It's a vowel"
Step3.1 : else Print "It's a consonant"
Step4 : Stop
PROGRAM
clear
echo -n "Key in a lower case character : "
read choice
case $choice in
a|e|i|o|u) echo "It's a Vowel";;
*) echo "It's a Consonant"
Esac

[iicse01@LINUXSVR2 ~]$ sh vowel.sh

Key in a lower case character : c
It's a Consonant

RESULT

Thus the shell program to find whether the given alphabet is vowel or consonant using decision
making constructs is executed and the output is verified successfully.

Ex .No. 2(b)(vi) MULTIPLICATION TABLE

10
AIM
To write a shell program to generate multiplication table using for loop.
ALGORITHM
Step1 . Start
Step2 . Read the value of n
Step3 . Initialize 1 to i
Step4 . Print n, i, n×i
Step5 . Increment i by 1
Step6 . Repeat Steps 4 and 5 until i <10
Step7 . Stop
PROGRAM
clear
echo -n "Which multiplication table? : "
read n
for x in 1 2 3 4 5 6 7 8 9 10
do
p=`expr $x \* $n`
echo "$n X $x = $p"
sleep 1
done

RESULT

Thus the shell program for generating multiplication table using for loop is executed and the output
is verified successfully.

Ex .No. 2(b)(vii) NUMBER REVERSE

AIM
To write a shell program that displays the reverse of a given number using while loop.
ALGORITHM
Step1. Start
Step2. Read number
Step3. Initialize 0 to reverse
Step4. Extract last digit by computing number modulo 10
Step5. Compute reverse = reverse10 + last digit
11
Step6. Divide number by 10
Step7. Repeat Steps 4–6 until number > 0
Step8. Print reverse
Step9. Stop
PROGRAM
clear
echo -n "Enter a number : "
read n
rd=0
while [ $n -gt 0 ]
do
rem=`expr $n % 10`
rd=`expr $rd \* 10 + $rem`
n=`expr $n / 10`
done
echo "Reversed number is $rd"
RESULT

Thus a shell program to reverse the given number using while loop is written executed successfully.

Ex .No. 2(b)(viii) FACTORIAL VALUE

AIM
To write shell programs to find the factorial of the given number.
ALGORITHM
Step1 . Start
Step2 . Read number
Step3 . Initialize 1 to fact and number to i
Step4 . fact = fact * i
Step5 . Decrement i by 1
Step6. Repeat Steps 4–6 until i > 0
Step7 . Print fact
Step8 . Stop
PROGRAM
clear
echo -n "Enter a positive number : "
read n
12
f=1
until [ $n -lt 1 ]
do
f=`expr $f \* $n`
n=`expr $n - 1`
done
echo "Factorial value : $f"

RESULT
Thus the program for factorial is executed and verified successfully.

13
Ex.No.3(a) PROCESS MANAGEMENT USING SYSTEM CALLS: FORK(), EXIT(), GETPID()
AIM
To write a simple script for process creation using fork, exit, getpid, wait, and close commands

ALGORITHM
Step 1. Start
Step 2. Print the process id using getpid () system call.
Step 3. Call the fork () system call to create processes and it takes no arguments and returns a process
ID.
Step 4. If the process is equal to zero then goto Step5 else Step6
Step 5. Print the child process id and its parent process.
Step 6. Print the parent process id and its fork process.
PROGRAM(vi fork.c)
#include<stdio.h>
#include<unistd.h>
int main()
{
int pid,pid1,pid2;
pid=fork();
if(pid==-1)
{
printf(“ERROR IN PROCESS CREATION \n”);
exit(1);
}
if(pid!=0)
{
pid1=getpid();
printf(“\n the parent process ID is %d\n”, pid1);
}
else
{
pid2=getpid();
printf(“\n the child process ID is %d\n”, pid2);
}
}

14
RESULT
Thus the program for process creation using fork, exec commands is created and executed
successfully.
Ex.No.3 (b) PROCESS MANAGEMENT USING SYSTEM CALLS: WAIT() AIM
To perform wait () system call using c program.
DESCRIPTION
The wait() causes the parent to wait for any child process to complete its execution.
ALGORITHM
Step1: Start the execution
Step2: Create process using fork and assign it to a variable
Step3: Check for the condition pid is equal to 0
Step4: If it is true print the value of i and terminate the child process
Step5: If it is not a parent process has to wait until the child terminate
Step6: Stop the execution
PROGRAM
#include<stdio.h>
int main()
{
int i=10;
int pid=fork();
if(pid==0)
{
printf("initial value of i %d \n ",i);
i+=10;
printf("value of i %d \n ",i);
printf("child terminated \n");
exit(0);
}
else
{
wait(0);
printf("value of i in parent process %d",i);
15
}
}

RESULT
Thus the program was executed and verified successfully.

SAMPLE VIVA-VOCE QUESTIONS

1. Which system call does not return control to the calling point, on termination?
2. Which system call transforms executable binary file into a process?
3. Which of the following system call is used for opening or creating a file?
4. Which mode is used for opening a file in both reading and writing?
5. How open system call returns the file descriptor?
6.
Ex.No.3(c) PROCESS MANAGEMENT USING SYSTEM CALLS: CLOSE() AIM
To write a C program using system call - close.
DESCRIPTION
close () system call is used to close the opened file, it tells the operating system that you are done with the
file and close the file. int fclose(FILE *stream) closes the stream. All buffers are flushed. Stream is the
pointer to a FILE object that specifies the stream to be closed. Returns zero if the stream is successfully
closed. On failure, EOF is returned.
ALGORITHM
Step1: Start
Step2: Declare the file stream fp
Step3: Open a file using fopen() and specify the mode as write w
Step4: write input data to file using fprintf ()
Step5: close the file using fclose()
Step6: Stop.
PROGRAM
#include <stdio.h>
int main () {
FILE *fp;
fp = fopen("filenew", "w");
fprintf(fp, "%s", "OS LAB");
fclose(fp);
16
return(0);
}
RESULT
Thus the program using close system call has been successfully executed.
Ex. No. 4(a) IMPLEMENTATION OF FCFS (FIRST-COME, FIRST-SERVED) CPU
SCHEDULING ALGORITHM
AIM
To write a C Program that implements FCFS scheduling algorithm and computes average waiting
time and turnaround time.
DESCRIPTION
The simplest CPU-scheduling algorithm is the first-come, first-served (FCFS) scheduling
algorithm. The process that requests the CPU first is allocated the CPU first. The implementation of the
FCFS policy is easily managed with a FIFO queue. When a process enters the ready queue, its PCB is
linked onto the tail of the queue. When the CPU is free, it is allocated to the process at the head of the
queue. The running process is then removed from the queue.
On the negative side, the average waiting time under the FCFS policy is often quite long. There is
a convoy effect as all the other processes wait for the one big process to get off the CPU. This effect
results in lower CPU and device utilization than might be possible if the shorter processes were allowed to
go first.
ALGORITHM
Step 1. Start
Step 2. Get the number of processes to be inserted
Step 3. Get the value for burst time of each process from the user
Step 4. Having allocated the burst time for individual processes , Start with the first process from its
initial position let other process to be in queue
Step 5. Calculate the waiting time(wt) ,average waiting time (awt) and turnaround time(tat) and
average turnaround time
Step 6. Display the values
Step 7. Stop
PROGRAM
#include<stdio.h>
int main()
{
int bt[10],at[10],wait_Time_Sum=0,turn_Time_Sum=0;
17
int time=0,n,i,smallest,count=0;
clrscr();
printf("Enter no of processes : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter arrival time for process P%d : ",i+1);
scanf("%d",&at[i]);
printf("Enter burst time for process P%d : ",i+1);
scanf("%d",&bt[i]);
}
printf("\n\nProcess\t|Turnaround Time| Waiting Time\n\n");
at[9]=9999;
while(count!=n) //End the loop when n process finish
{
smallest=9; // Checking For index of Process with smallest Arrival Time
for(i=0;i<n;i++)
{
if(at[i]<at[smallest] && bt[i]>0)
{
smallest=i;
}
}
//Index of Smallest Arrival Time stored in `smallest`
time+=bt[smallest]; //Incrementing Current Time
wait_Time_Sum+=time-at[smallest]-bt[smallest];
turn_Time_Sum+=time-at[smallest];
printf("P[%d]\t|\t%d\t|\t%d\n",smallest+1,time-at[smallest],time-at[smallest]-bt[smallest]);
bt[smallest]=0; //Making burst time of current Process 0 so that it won't run again count++;
}
printf("\n average waiting time = %f",wait_Time_Sum*1.0/n);
printf("\n average turnaround time = %f\n",turn_Time_Sum*1.0/n);
getch();
return 0;
18
}
RESULT
Thus a C Program that implements FCFS scheduling algorithm and computes average waiting time
and turnaround time is executed and verified.
SAMPLE VIVA-VOCE QUESTIONS
1. Define convoy effect.
2. Define Burst time.
3. Define Waiting time.
4. What is response time?
5. What is Gantt chart?
Ex. No. 4(b) IMPLEMENTATION OF SJF (SHORTEST-JOB-FIRST) CPU SCHEDULING
ALGORITHM
AIM
To write a C Program that implements SJF scheduling algorithm and computes average waiting
time and turnaround time.
DESCRIPTION
A different approach to CPU scheduling is the shortest-job-first (SJF) scheduling algorithm. This
algorithm associates with each process the length of the process‟s next CPU burst. When the CPU is
available, it is assigned to the process that has the smallest next CPU burst. If the next CPU bursts of two
processes are the same, FCFS scheduling is used to break the tie.
Note that a more appropriate term for this scheduling method would be the shortest-next- CPU
burst algorithm, because scheduling depends on the length of the next CPU burst of a process, rather than
its total length. The SJF scheduling algorithm is provably optimal, in that it gives the minimum average
waiting time for a given set of processes.
ALGORITHM
Step1: Start the process
Step2: Declare the array size
Step3: Get the number of elements to be inserted
Step4: Select the process which have shortest burst will execute first
Step5: If two processes have same burst length then FCFS scheduling algorithm
used Step6: Make the average waiting the length of next process
Step7: Start with the first process from it‟s selection as above and let other process to be in queue
Step8: Calculate the total number of burst time
19
Step9: Display the values
Step10: Stop the process
PROGRAM
#include<stdio.h>
int main()
{
int time,bt[10],at[10],sum_bt=0,smallest,n,i;
int sum_turnaround=0,sum_wait=0;
printf("Enter no of processes : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter arrival time for process P%d : ",i+1);
scanf("%d",&at[i]);
printf("Enter burst time for process P%d : ",i+1);
scanf("%d",&bt[i]);
sum_bt+=bt[i];
}
bt[9]=9999;
printf("\n\nProcess\t|Turnaround Time| Waiting Time\n\n");
for(time=0;time<sum_bt;)
{
smallest=9;
for(i=0;i<n;i++)
{
if(at[i]<=time && bt[i]>0 && bt[i]<bt[smallest])
smallest=i;
}
if(smallest==9)
{
time++;
continue;
}
printf("P[%d]\t|\t%d\t|\t%d\n",smallest+1,time+bt[smallest]-at[smallest],time-at[smallest]);
sum_turnaround+=time+bt[smallest]-at[smallest];
20
sum_wait+=time-at[smallest];
time+=bt[smallest];
bt[smallest]=0;
}
printf("\n\n average waiting time = %f",sum_wait*1.0/n);
printf("\n\n average turnaround time = %f",sum_turnaround*1.0/n);
return 0;
}

RESULT
Thus a C Program that implements SJF scheduling algorithm and computes average waiting time
and turnaround time is executed and the output is verified.

SAMPLE VIVA-VOCE QUESTIONS

1. Define average waiting time
2. What is preemptive SJF algorithm?
3. Define turnaround time.
4. What is throughput?
5. What is shortest remaining first scheduling algorithm?

Ex. No. 4(c) IMPLEMENTATION OF ROUND ROBIN CPU SCHEDULING ALGORITHM

AIM
To write a C Program that implements round robin scheduling algorithm and computes average
waiting time and turnaround time.
DESCRIPTION
The round-robin (RR) scheduling algorithm is designed especially for timesharing systems. It is
similar to FCFS scheduling, but preemption is added to enable the system to switch between processes. A
small unit of time, called a time quantum or time slice, is defined. A time quantum is generally from 10
to 100 milliseconds in length. The ready queue is treated as a circular queue. The CPU scheduler goes
around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum. To
implement RR scheduling, we again treat the ready queue as a FIFO queue of 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 dispatches the process. The average waiting time under
the RR policy is often long.
21
ALGORITHM
Step 1. Start
Step 2. Get the number of elements to be inserted
Step 3. Get the value for burst time for individual processes
Step 4. Get the value for time quantum .
Step 5. Make the CPU scheduler go around the ready queue allocating CPU to each process for the
time interval specified
Step 6. Make the CPU scheduler pick the first process and set time to interrupt after quantum. And
after it's expiry dispatch the process
Step 7. If the process has burst time less than the time quantum then the process is released by the
CPU
Step 8. If the process has burst time greater than time quantum then it is interrupted by the OS and
the process is put to the tail of ready queue and the schedule selects next process from head
of the queue
Step 9. Calculate the total and average waiting time and turnaround time
Step10. Display the results
Step11. Stop
PROGRAM
#include<stdio.h>
int main()
{
int i,j,n,time,remain,flag=0,ts;
int sum_wait=0,sum_turnaround=0,at[10],bt[10],rt[10];
printf("Enter no of Processes : ");
scanf("%d",&n);
remain=n;
for(i=0;i<n;i++)
{
printf("Enter arrival time and burst time for Process P%d :",i+1);
scanf("%d",&at[i]);
scanf("%d",&bt[i]);
rt[i]=bt[i];
}
printf("Enter quantum time");
scanf("%d",&ts);
printf("\n\nProcess\t|Turnaround time|waiting time\n\n");
for(time=0,i=0;remain!=0;)
{
if(rt[i]<=ts && rt[i]>0)

22
{
time+=rt[i];
rt[i]=0;
flag=1;
}
else if(rt[i]>0)
{
rt[i]-=ts;
time+=ts;
}
if(rt[i]==0 && flag==1)
{
remain--;
printf("P[%d]\t|\t%d\t|\t%d\n",i+1,time-at[i],time-at[i]-bt[i]);
sum_wait+=time-at[i]-bt[i];
sum_turnaround+=time-at[i];
flag=0;
}
if(i==n-1)
i=0;
else if(at[i+1]<=time)
i++;
else
i=0;
}
printf("\nAvg sum_wait = %f\n",sum_wait*1.0/n);
printf("Avg sum_turnaround = %f",sum_turnaround*1.0/n);
return 0;
}

RESULT
Thus a C Program that implements round robin scheduling algorithm and computes average
waiting time and turnaround time is executed and the output is verified.

SAMPLE VIVA-VOCE QUESTIONS

1. Why is round robin algorithm considered better than first come first served algorithm? 2. What
happens if the time allocated in a Round Robin Scheduling is very large? And what happens if the
time allocated is very low?
3. Define Quantum time.
4. Which of the following statements are true?

23
i) Preemptive scheduling may cause starvation
ii) Round robin is better than FCFS in terms of response time

Ex. NO. 4(d) IMPLEMENTATION OF PRIORITY CPU SCHEDULING ALGORITHM

AIM
To write a C Program that implements priority scheduling algorithm and computes average waiting
time and turnaround time.
DESCRIPTION
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 algorithm 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. Priority scheduling can be either preemptive or non-preemptive.
Priorities can be defined either internally or externally. Internally defined priorities use some measurable
quantity or quantities to compute the priority of a process.
ALGORITHM
Step 1. Start
Step 2. Get the number of processes to be inserted
Step 3. Get the corresponding priority of processes
Step 4. Sort the processes according to the priority and allocate the one with highest priority to
execute first
Step 5. If two process have same priority then FCFS scheduling algorithm is used
Step 6. Calculate the total and average waiting time and turnaround time
Step 7. Display the values
Step 8. Stop
PROGRAM
#include<stdio.h>
int main()
{
int i,j,n,time,sum_wait=0,sum_turnaround=0;
int smallest,at[10],bt[10],priority[10],remain;
printf("Enter no of Processes : ");
scanf("%d",&n);
remain=n;
for(i=0;i<n;i++)
{
printf("Enter arrival time, burst time and priority for process p%d :",i+1);
scanf("%d",&at[i]);
scanf("%d",&bt[i]);
24
scanf("%d",&priority[i]);
}
priority[9]=11;
printf("\n\nProcess\t|Turnaround time|waiting time\n");
for(time=0;remain!=0;)
{
smallest=9;
for(i=0;i<n;i++)
{
if(at[i]<=time && priority[i]<priority[smallest] && bt[i]>0)
{
smallest=i;
}
}
time+=bt[smallest];
remain--;
printf("P[%d]\t|\t%d\t|\t%d\n",smallest+1,time-at[smallest],time-at[smallest]-bt[smallest]);
sum_wait+=time-at[smallest]-bt[smallest];
sum_turnaround+=time-at[smallest];
bt[smallest]=0;
}
printf("\nAvg waiting time = %f\n",sum_wait*1.0/n);
printf("Avg turnaround time = %f",sum_turnaround*1.0/n);
return 0;
}
RESULT
Thus a C Program that implements priority scheduling algorithm and computes average waiting
time and turnaround time is executed and verified.
SAMPLE VIVA-VOCE QUESTIONS

1. Why CPU scheduling is needed?

2. What is Starvation?
3. Define aging.
4. Differentiate preemptive and non preemptive priority scheduling.
5. On what basis a process is given high priority?

25
Ex. No: 5 ILLUSTRATION OF THE INTER PROCESS COMMUNICATION STRATEGY
AIM
To write a C program to develop application for Inter Process Communication using shared
memory.
DESCRIPTION
Shared Memory is an efficient means of passing data between programs. One program will create a
memory portion which other processes (if permitted) can access. Interprocess communication (IPC) is a
set of programming interfaces that allow a programmer to coordinate activities among different program
processes that can run concurrently in an operating system. This allows a program to handle many user
requests at the same time.
∙ shmid A shared memory segment is described by a control structure with a unique ID that points to
an area of physical memory.
∙ shmget() is used to obtain access to a shared memory segment
∙ shmctl() is used to alter the permissions and other characteristics of a shared memory segment ∙
shmat(),shmdt() - are used to attach and detach shared memory segments
∙ The structure definition for the shared memory segment control structures and prototypes can be
found in <sys/shm.h>.
ALGORITHM
Step 1. Start the program.
Step 2. Include all the header files.
Step 3. Define the size of shared memory.
Step 4. Name can be given to the shared memory.
Step 5. We have to create a server program and a client program in different
location. Step 6. In server program we are creating the segment.
Step 7. In client program change the first character of the segment to „*‟ into indicate that we have to read
the segment.
Step 8. Stop the program
PROGRAM
SENDER:
#include<unistd.h>
#include<fcntl.h>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<sys/stat.h>
#include<sys/shm.h>
#define size 32
int main()

26
{
int shmid;
char *s[100],*str;
printf("\nipc message passing using shared memory sender");
shmid=shmget(60,size,IPC_CREAT|0666);
str=shmat(shmid,0,0);
printf("\nenter the message to be sent");
gets(s);
strcpy(str,s);
printf("\nyour message has been sent");
return 0;
}
RECEIVER:
#include<unistd.h>
#include<fcntl.h>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<sys/stat.h>
#include<sys/shm.h>
#define size 32
int main()
{
printf("\n ipc message passing using shared memory receiver");
int shmid;
char *str;
shmid=shmget(60,size,IPC_CREAT|0666);
str=shmat(shmid,0,0);
printf("\nReceived message is.... ");
puts(str);
return 0;
}

RESULT
Thus the C program to develop application for Inter Process Communication using shared memory
is executed and verified.

SAMPLE VIVA-VOCE QUESTIONS

1. Define Interprocess Communication.
2. What is shmid?
3. What is SHM_LOCK?
4. What is Memory Management Unit (MMU)?
5. What are RPC and RMI?

27
Ex.No. 6 IMPLEMENT MUTUAL EXCLUSION BY SEMAPHORE

AIM
To write a C program to implement producer consumer problem using semaphore.
DESCRIPTION
A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard
atomic operations: wait and signal. These operations were originally termed P (for wait; from the Dutch
proberen, to test) and V (for signal; from verhogen, to increment).
wait(S): S--;
wait(S){ }
while(S<=0) Signal(S): Signal(S){ S++;
;//busy wait }

Modifications to the integer value of the semaphore in the wait and signal operations must be executed
indivisibly. When one process modifies the semaphore value, no other process can simultaneously modify
that same semaphore value.
ALGORITHM
Step 1. Create two process using fork () for producer and consumer.
Step 2. Set buffer size for both producer and consumer.
Step 3. Producer process
do
{
/*produce an item in next_produced*/
wait(empty);
wait(mutex);
/*add next_produced to buffer*/
signal (mutex);
signal(full);
}
while (true);

Step 4. Consumer process

do
{
28
wait(full);
wait(mutex);
/*remove an item from buffer to next_consumed*/
signal (mutex);
signal(full);
/*consume the item in next_consumed */
}
while(true);
PROGRAM
#include<stdio.h>
#define BUF_SIZ 4
int in=0,out=-1;
int count=0;
typedef struct
{
int stat,pid;
}Item;
Item item[BUF_SIZ];
void producer()
{
if(in==out&&in==0)
{
printf("Buffer overflow\n");
printf("In:%d \tout:%d\n",in,out);
}
else
{
if(item[in%BUF_SIZ].stat==0)
{
Item temp;
temp.stat=1;
temp.pid=rand()%1000;
item[(in%BUF_SIZ)]=temp;
in=(in%BUF_SIZ)+1;
printf("Process added with id:%d\n",temp.pid);
printf("In:%d\t out:%d\n",in,out);
if(count>=BUF_SIZ)
count=(count%BUF_SIZ)+1;
else
count++;
}
else
{
29
printf("Error: Buffer overflow\n");
printf("In:%d\t Out:%d\n",in,out);
}}}
void view()
{
int i;
printf("\n processes\n");
for(i=0;i<BUF_SIZ;i++)
{
if(item[i].stat==0)
printf("Buffer position empty\n");
else
printf("process %d in buffer position %d\n",item[i].pid,i+1);
}}
void consume()
{
if(in==0&&out==-1)
{
printf("No process to consume\n");
}
else
{
if(item[(out+1)%BUF_SIZ].stat==0)
printf("Error cannot consume process\n");
else
{
out=(out+1)%BUF_SIZ;
item[out].stat=0;
printf("In:%d\t out:%d\n",in,out);
printf("Item consumed\n");
}}}
int main(void)
{
int ch=0;
system("clear");
do{
printf("\n1.produce new process to buffer\n");
printf("\n2.consume process\n");
printf("\n3.view buffer\n");
printf("\n4.Exit program\n");
printf("Enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
30
producer();
view();
break;
case 2:
consume();
view();
break;
case 3:
view();
break;
}}
while(ch!=4);
return 0;
}

RESULT
Thus the C program to implement producer consumer problem using semaphore is executed and
verified.
SAMPLE VIVA-VOCE QUESTIONS
1. What is semaphore?
2. What is mutual exclusion?
3. What is spinlock?
4. What difference between counting semaphore and binary semaphore ?

31
Ex. No: 7 C PROGRAM TO AVOID DEADLOCK USING BANKER'S ALGORITHM AIM
To write a C program to implement Banker‟s algorithm for dead lock avoidance.
DESCRIPTION
A set of processes is deadlocked if each process in the set is waiting for an event that only another process
in the set can cause (including itself).
Banker’s Algorithm:
When a new process enters a system, it must declare the maximum number of instances of each resource
type it needed. This number may exceed the total number of resources in the system. When the user
request a set of resources, the system must determine whether the allocation of each resources will leave
the system in safe state. If it will the resources are allocated; otherwise the process must wait until some
other process release the resources.
Data structures
∙ n-Number of process, m-number of resource types.
∙ Available: Available[j]=k, k – instance of resource type Rj is available.
∙ Max: If max[i, j]=k, Pi may request at most k instances resource Rj.
∙ Allocation: If Allocation [i, j]=k, Pi allocated to k instances of resource Rj
∙ Need: If Need[I, j]=k, Pi may need k more instances of resource type Rj,
∙ Need[I, j]=Max[I, j]-Allocation[I, j];
Safety Algorithm
1. Work and Finish be the vector of length m and n respectively, Work=Available and Finish[i] =False.
2. Find an i such that both
i. Finish[i] =False
ii. Need<=Work
If no such I exists go to Step4.
3. work=work+Allocation, Finish[i] =True;
4. if Finish[1]=True for all I, then the system is in safe state.
Resource request algorithm
Let Request i be request vector for the process Pi, If request i=[j]=k, then process Pi wants k instances of
resource type Rj.
1. if Request<=Need I go to Step2. Otherwise raise an error condition.
2. if Request<=Available go to Step3. Otherwise Pi must since the resources are available. 3. Have the
system pretend to have allocated the requested resources to process Pi by modifying the state as
follows;
32
Available=Available-Request I;
Allocation I =Allocation+Request I;
Need i=Need i-Request I;
If the resulting resource allocation state is safe, the transaction is completed and process Pi is
allocated its resources. However if the state is unsafe, the Pi must wait for Request i and the old
resource-allocation state is restored.
PROGRAM
#include<stdio.h>
#include<conio.h>
struct da
{
int max[10],a1[10],need[10],before[10],after[10];
}p[10];
Int main()
{
int i,j,k,l,r,n,tot[10],av[10],cn=0,cz=0,temp=0,c=0;
printf("\n ENTER THE NO. OF PROCESSES:");
scanf("%d",&n);
printf("\n ENTER THE NO. OF RESOURCES:");
scanf("%d",&r);
for(i=0;i<n;i++)
{
printf("PROCESS %d \n",i+1);
for(j=0;j<r;j++)
{
printf("MAXIMUM VALUE FOR RESOURCE %d:",j+1);
scanf("%d",&p[i].max[j]);
}
for(j=0;j<r;j++)
{
printf("ALLOCATED FROM RESOURCE %d:",j+1);
scanf("%d",&p[i].a1[j]);
p[i].need[j]=p[i].max[j]-p[i].a1[j];
}}
for(i=0;i<r;i++)
33
{
printf("ENTER TOTAL VALUE OF RESOURCE %d:",i+1);
scanf("%d",&tot[i]);
}
for(i=0;i<r;i++)
{
for(j=0;j<n;j++)
temp=temp+p[j].a1[i];
av[i]=tot[i]-temp;
temp=0;
}
printf("\n\t RESOURCES ALLOCATED NEEDED TOTAL AVAIL");
for(i=0;i<n;i++)
{
printf("\n P%d \t",i+1);
for(j=0;j<r;j++)
printf("%d",p[i].max[j]);
printf("\t");
for(j=0;j<r;j++)
printf("%d",p[i].a1[j]);
printf("\t");
for(j=0;j<r;j++)
printf("%d",p[i].need[j]);
printf("\t");
for(j=0;j<r;j++)
{
if(i==0)
printf("%d",tot[j]);
}
printf(" ");
for(j=0;j<r;j++)
{
if(i==0)
printf("%d",av[j]);
}}
34
printf("\n\n\t AVAIL BEFORE\T AVAIL AFTER ");
for(l=0;l<n;l++)
{
for(i=0;i<n;i++)
{
for(j=0;j<r;j++)
{
if(p[i].need[j] >av[j])
cn++;
if(p[i].max[j]==0)
cz++;
}
if(cn==0 && cz!=r)
{
for(j=0;j<r;j++)
{
p[i].before[j]=av[j]-p[i].need[j];
p[i].after[j]=p[i].before[j]+p[i].max[j];
av[j]=p[i].after[j];
p[i].max[j]=0;
}
printf("\n P %d \t",i+1);
for(j=0;j<r;j++)
printf("%d",p[i].before[j]);
printf("\t");
for(j=0;j<r;j++)
printf("%d",p[i].after[j]);
cn=0;
cz=0;
c++;
break;
}
else
{
cn=0;cz=0;
35
}}}
if(c==n)
printf("\n THE ABOVE SEQUENCE IS A SAFE SEQUENCE");
else
printf("\n DEADLOCK OCCURED");
}
RESULT
Thus the program using Bankers Algorithm for Dead Lock Avoidance is executed and the output is
verified.
SAMPLE VIVA-VOCE QUESTIONS
1. List the necessary conditions of deadlock.
2. Define safe state.
3. What is the use of resource allocation graph?
4. State the sequence in which the process may utilize a resource.
36
Ex. No: 8 C PROGRAM TO IMPLEMENT DEADLOCK DETECTION ALGORITHM AIM
To write a C program for implementation of Dead Lock Detection algorithm.
DESCRIPTION
If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm, then
a deadlock situation may occur. In this situation the system may provide:
∙ An algorithm that examines the state of the system to determine whether a deadlock has occurred •
An algorithm to recover from the deadlock
ALGORITHM
1. LetWork and Finish be vectors of length m and n, respectively. Initialize Work = Available. For i = 0,
1, ..., n–1, if Allocationi _= 0, then Finish[i] =false. Otherwise, Finish[i] = true. 2. Find an index i such
that both
a. Finish[i] == false
b. Requesti ≤Work
If no such i exists, go to Step4.
3. Work =Work + Allocationi
Finish[i] = true
Go to Step2.
4. If Finish[i] ==false for some i, 0≤i<n, then the system is in a deadlocked state. Moreover, if Finish[i]
== false, then process Pi is deadlocked.
PROGRAM
#include<stdio.h>
#include<conio.h>
int max[100][100];
int alloc[100][100];
int need[100][100];
int avail[100];
int n,r;
void input();
void show();
void cal();
int main()
{
int i,j;
printf("********** Deadlock Detection Algo ************\n");
input();
show();
cal();
getch();
return 0;
}
void input()
37
{
int i,j;
printf("Enter the no of Processes\t");
scanf("%d",&n);
printf("Enter the no of resource instances\t");
scanf("%d",&r);
printf("Enter the Max Matrix\n");
for(i=0;i<n;i++)
{
for(j=0;j<r;j++)
{
scanf("%d",&max[i][j]); }
}
printf("Enter the Allocation Matrix\n");
for(i=0;i<n;i++)
{
for(j=0;j<r;j++)
{
scanf("%d",&alloc[i][j]); }
}
printf("Enter the available Resources\n");
for(j=0;j<r;j++)
{
scanf("%d",&avail[j]);
}}
void show()
{
int i,j;
printf("Process\t Allocation\t Max\t Available\t");
for(i=0;i<n;i++)
{
printf("\nP%d\t ",i+1);
for(j=0;j<r;j++)
{
printf("%d ",alloc[i][j]); }
printf("\t");
for(j=0;j<r;j++)
{
printf("%d ",max[i][j]); }
printf("\t");
if(i==0)
{
for(j=0;j<r;j++)
printf("%d ",avail[j]); } } }
void cal()
{
int finish[100],temp,need[100][100],flag=1,k,c1=0;
38
int dead[100];
int safe[100];
int i,j;
for(i=0;i<n;i++)
{
finish[i]=0;
}
//find need matrix
for(i=0;i<n;i++)
{
for(j=0;j<r;j++)
{
need[i][j]=max[i][j]-alloc[i][j];
}}
while(flag)
{
flag=0;
for(i=0;i<n;i++)
{
int c=0;
for(j=0;j<r;j++)
{
if((finish[i]==0)&&(need[i][j]<=avail[j])) {
c++;
if(c==r)
{
for(k=0;k<r;k++) {
avail[k]+=alloc[i][j]; finish[i]=1; flag=1; }
//printf("\nP%d",i); if(finish[i]==1) {
i=n; } } } } } }
j=0;
flag=0;
for(i=0;i<n;i++)
{
if(finish[i]==0)
{
dead[j]=i;
j++;
flag=1;
}}
if(flag==1)
{
printf("\n\nSystem is in Deadlock and the Deadlock process are\n"); for(i=0;i<n;i++)
39
{
printf("P%d\t",dead[i]);
}}
else
{
printf("\nNo Deadlock Occur");
}
}

RESULT
Thus the program for Deadlock Detection is implemented and the output is verified.
SAMPLE VIVA-VOCE QUESTIONS

1. When is a system in safe state?

2. When to invoke a deadlock detection algorithm?
3. What is process termination?
4. What is resource preemption?
5. How to calculate the request?
40
Ex.No. 9 C PROGRAM TO IMPLEMENT THREADING

AIM
To a C program to implement threading applications in UNIX.
DESCRIPTION
A Thread is defined as the fundamental unit of CPU utilization. Multiple threads of the same process
share with each other the code section, data section and other resources, such as open files and signals.
The traditional processes are termed heavy weight while a thread is referred to as light weight process
(LWP).Each thread has its own ID, stack, set of registers and program counter.
ALGORITHM.
Step1. Include the header files
Step2. Initialize the pthread
Step3. Start the thread process and increment the counter
Step4. Check the mutex with init process
Step5. Print the thread status with stdout
Step6. Stop the program
PROGRAM
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
void *functionC();
pthread_mutex_t mutex1=PTHREAD_MUTEX_INITIALIZER;

int counter=0;
main()
{
int rcl,rc2;
pthread_t thread1, thread2;

/*Create independent threads each of which will execute functionC */

if((rc1=pthread_create(& thread1, NULL, &function C, NULL)))

{
printf("Thread creation failed: %d\n", rc1);
}
if((rc2=pthread_create( &thread2, NULL, &function C, NULL)))
41
{
printf("Thread creation failed: %d\n", rc2);
}
/* Wait till threads are complete before main continues. Unless we */
/* wait we run the risk of executing an exit which will terminate */
/* the process and all threads before the threads have completed. */
pthread_join(thread1,NULL);
pthread_join(thread2, NULL);
exit(EXIT_SUCCESS);
}
void functionC()
{
pthread_mutex_lock( &mutex1);
counter++;
printf("Counter value: %d",counter);
pthread_mutex_unlock(&mutex1);
}
RESULT
Thus the C program to implement threading application is executed and output is verified.
SAMPLE VIVA-VOCE QUESTIONS
1. What is a thread?
2. What are the benefits of multithreaded programming?
3. What is user threads and kernel threads?
4. Define thread cancellation & target thread?

42
Ex. No: 10 IMPLEMENT THE PAGING TECHNIQUE USING C PROGRAM AIM
To write a C program to implement Paging Technique of memory management.
DESCRIPTION
Paging is a memory-management scheme that permits the physical-address space of a process to
be noncontiguous. Paging avoids the considerable problem of fitting the varying-sized memory chunks
onto the backing store. Support for paging has been handled by hardware. Physical memory is broken into
fixed-sized blocks called frames. Logical memory is also broken into blocks of the same size called pages.
Every address generated by the CPU is divided into two parts: A page number (p) and a page offset (d).
The page number is used as an index into a page table. The page table contains the base address of each
page in physical memory. This base address is combined with the page offset to define the physical
memory address that is sent to the memory unit.
ALGORITHM
Step 1. Start
Step 2. Declare the structure P_table with variables for page numbers and frame
number Step 3. Display the status of physical memory
Step 4. Get the number of pages needed for a process
Step 5. Get the contents of the pages
Step 6. Display the contents of logical memory
Step 7. If the physical memory is available then allot the pages of the process
Step 8. Update the physical memory status
Step 9. Update the page table status
Step 10. Display the page table after allocation
Step 11. Display the physical memory after allocation
Step 12. Stop
PROGRAM
#include<stdio.h>
#include<conio.h>
#include<math.h>
void main()
{
int size,m,n,pgno,pagetable[3]={5,6,7},i,j,frameno;
double m1;
int ra=0,ofs;
clrscr();
printf("Enter process size (in KB of max 12KB):");/*reading memeory size*/
scanf("%d",&size);
m1=size/4;

43
n=ceil(m1);
printf("Total No. of pages: %d",n);
printf("\nEnter relative address (in hexadecimal notation eg.0XRA) \n");
//printf("The length of relative Address is : 16 bits \n\n The size of offset is :12 bits\n");
scanf("%d",&ra);
pgno=ra/1000; /*calculating physical address*/
ofs=ra%1000;
printf("page no=%d\n",pgno);
printf("page table");
for(i=0;i<n;i++)
printf("\n %d [%d]",i,pagetable[i]);
frameno=pagetable[pgno];
printf("\n Equivalent physical address : %d%d",frameno,ofs);
getch();
}

RESULT
Thus the C program for implementation of Paging Technique of memory management was written
and executed.
SAMPLE VIVA-VOCE QUESTIONS
1. Define Demand Paging
2. What is fragmentation? Different types of fragmentation?
3. What are Dynamic Loading, Dynamic Linking and Overlays?
4. Define Page fault?
5. Define interrupt, and Thrashing?

44
Ex. No: 11(a) IMPLEMENTATION OF MEMORY ALLOCATION METHODS FOR FIXED
PARTITION-FIRST FIT
AIM
To write a C program for implementation of first fit memory allocation method for fixed partition .
DESCRIPTION
In Partition Allocation, when there are more than one partition freely available to accommodate a
process‟s request, a partition must be selected. To choose a particular partition, a partition allocation
method is needed. A partition allocation method is considered better if it avoids internal fragmentation.
In first fit, the partition is allocated to the first sufficient from the top of Main Memory. Its
advantage is that it is the fastest search as it searches only the first block i.e. enough to assign a process.
ALGORITHM
Step1. Start the process
Step2. Declare the size
Step3. Get the number of processes to be inserted
Step4. Allocate the best hole that is small enough searching
Step5. Start at the best of the set of holes
Step6. If not start at the hole that is sharing the previous best fit search end
Step7. Compare the hole
Step8. If small enough then stop searching in the procedure
Step9. Display the values
Step10. Stop the process
PROGRAM
#include<stdio.h>
int main()
{
int a[20],p[20],i,j,n,m;
printf("Enter no of Blocks.\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter the %dst Block size:",i);
scanf("%d",&a[i]);
}
printf("Enter no of Process.\n");
scanf("%d",&m);

45
for(i=0;i<m;i++)
{
printf("Enter the size of %dst Process:",i);
scanf("%d",&p[i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(p[j]<=a[i])
{
printf("The Process %d allocated to %d\n",j,a[i]);
p[j]=10000;
break;
}
}
}
for(j=0;j<m;j++)
{
if(p[j]!=10000)
{
printf("The Process %d is not allocated\n",j);
}
}

RESULT
Thus the program for implementation of first fit memory allocation method for fixed partition is
executed and output is verified.
SAMPLE VIVA-VOCE QUESTIONS
1. Which of the following type of partition has the problem of internal fragmentation?
2. Who performs the garbage collection?
3. After an allocation of space using the first-fit policy the number of holes in memory

46
Ex. No: 11(b) IMPLEMENTATION OF MEMORY ALLOCATION METHODS FOR FIXED
PARTITION - WORST FIT
AIM
To write a C program for implementation of worst fit memory allocation method for fixed partition.
DESCRIPTION
In Partition Allocation, when there are more than one partition freely available to accommodate a
process‟s request, a partition must be selected. To choose a particular partition, a partition allocation
method is needed. A partition allocation method is considered better if it avoids internal fragmentation.
Worst Fit allocates the process to the partition which is largest sufficient among the freely
available partitions available in the main memory.
ALGORITHM
Step1: Get the number of Processes.
Step2: Get each process memory size.
Step3: Get the memory size of each partition. Enter -99 to indicate the last memory
partition. Step4: Compare the process size with the memory partitions.
Step5: If process size is less than or equal to a memory partition, select the largest matching partition and
allocate it to the process.
Step6: Reduce the memory partition from the process size and make it a new memory
partition. Step7: Do the same for all the processes
Step8: Display the output.
PROGRAM
#include<stdio.h>
#define max 25
int main()
{
int frag[max],b[max],f[max],i,j,nb,nf,temp,highest=0;
static int bf[max],ff[max];
printf("\n\tMemory Management Scheme - Worst Fit");
printf("\nEnter the number of blocks:");
scanf("%d",&nb);
printf("Enter the number of files:");
scanf("%d",&nf);
printf("\nEnter the size of the blocks:-\n");
for(i=1;i<=nb;i++)
{

47
printf("Block %d:",i);
scanf("%d",&b[i]);
}
printf("Enter the size of the files :-\n");
for(i=1;i<=nf;i++)
{
printf("File %d:",i);
scanf("%d",&f[i]);}

for(i=1;i<=nf;i++)
{
for(j=1;j<=nb;j++)
{
if(bf[j]!=1) //if bf[j] is not allocated
{
temp=b[j]-f[i];
if(temp>=0)
if(highest<temp)
{
ff[i]=j;
highest=temp;
}
}
}
frag[i]=highest;
bf[ff[i]]=1;
highest=0;
}
printf("\nFile_no:\tFile_size :\tBlock_no:\tBlock_size:\tFragement");
for(i=1;i<=nf;i++)
printf("\n%d\t\t%d\t\t%d\t\t%d\t\t%d",i,f[i],ff[i],b[ff[i]],frag[i]);
}
RESULT
Thus the program for implementation of worst fit memory allocation method for fixed partition is
executed and output is verified.
48
SAMPLE VIVA-VOCE QUESTIONS
1. In internal fragmentation, memory is internal to a partition and?
2. A solution to the problem of external fragmentation is?
3. When the memory allocated to a process is slightly larger than the process, then?
Ex. No: 11(c) IMPLEMENTATION OF MEMORY ALLOCATION METHODS FOR FIXED
PARTITION -BEST FIT

AIM
To write a C program for implementation of best fit memory allocation method for fixed partition.
DESCRIPTION
In Partition Allocation, when there are more than one partition freely available to accommodate a
process‟s request, a partition must be selected. To choose a particular partition, a partition allocation
method is needed. A partition allocation method is considered better if it avoids internal fragmentation.
Best Fit allocates the process to the partition which is first smallest sufficient partition among the
free available partition.

ALGORITHM
Step1: Start the process
Step2: Declare the size
Step3: Get the number of processes to be inserted
Step4: Allocate the first hole that is big enough searching
Step5: Start at the beginning of the set of holes
Step6: If not start at the hole that is sharing the pervious first fit search end
Step7: Compare the hole
Step8: If large enough then stop searching in the procedure
Step9: Display the values
Step10: Stop the process
PROGRAM
#include<stdio.h>
void main()
{
int a[20],p[20],i,j,n,m,temp,b[20],temp1,temp2,c[20];
printf("Enter no of Blocks.\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter the %dst Block size:",i);
scanf("%d",&a[i]);
49
b[i]=i;
}
printf("Enter no of Process.\n");
scanf("%d",&m);
for(i=0;i<m;i++)
{
printf("Enter the size of %dst Process:",i);
scanf("%d",&p[i]);
c[i]=i;
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(a[i]<a[j])
{
temp=a[i];
temp1=b[i];
a[i]=a[j];
b[i]=b[j];
a[j]=temp;
b[j]=temp1;
}
if(p[i]<p[j])
{
temp=p[i];
temp2=c[i];
p[i]=p[j];
c[i]=c[j];
p[j]=temp;
c[j]=temp2;
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(p[j]<=a[i])
{
printf("The Process %d allocated to Block %d\n",c[j],b[i]); p[j]=10000;
break;
}
}}
for(j=0;j<m;j++)
{
if(p[j]!=10000)
{
printf("The Process %d is not allocated\n",j); }
}
50
}

RESULT
Thus the program for implementation of best fit memory allocation method for fixed partition is
executed and output is verified.
SAMPLE VIVA-VOCE QUESTIONS
1. Fixed and dynamic partitioning suffers from which of the following fragmentation?
2. Which memory allocation policy fastest?
3. Which dynamic storage-allocation algorithms results in the largest leftover hole in memory?

51
Ex. No: 12(a) IMPLEMENTATION OF FIFO PAGE REPLACEMENT ALGORITHM

AIM
To write a C program to implement FIFO (First In First Out)page replacement algorithm.
DESCRIPTION
The simplest page-replacement algorithm is a first-in, first-out (FIFO) algorithm. A FIFO
replacement algorithm associates with each page the time when that page was brought into memory. When
a page must be replaced, the oldest page is chosen. Notice that it is not strictly necessary to record the time
when a page is brought in. A FIFO queue can be created to hold all pages in memory. The page wil be
replaced at the head of the queue. When a page is brought into memory, it is inserted at the tail of the
queue.
ALGORITHM
Step 1. Start the process
Step 2. Declare the size with respect to page length
Step 3. Check the need of replacement from the page to memory
Step 4. Check the need of replacement from old page to new page in memory
Step 5. Forma queue to hold all pages
Step 6. Insert the page require memory into the queue
Step 7. Check for bad replacement and page fault
Step 8. Get the number of processes to be inserted
Step 9. Display the values
Step 10. Stop the process
PROGRAM
#include<stdio.h>
int main()
{
int i,j,n,a[50],frame[10],no,k,avail,count=0;
printf("\n ENTER THE NUMBER OF PAGES:\n");
scanf("%d",&n);
printf("\n ENTER THE PAGE NUMBER :\n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("\n ENTER THE NUMBER OF FRAMES :");
scanf("%d",&no);
for(i=0;i<no;i++)
frame[i]= -1;
j=0;
printf("\tref string\t page frames\n");
for(i=1;i<=n;i++)
{
52
printf("%d\t\t",a[i]);
avail=0;
for(k=0;k<no;k++)
if(frame[k]==a[i])
avail=1;
if (avail==0)
{
frame[j]=a[i];
j=(j+1)%no;
count++;
for(k=0;k<no;k++)
printf("%d\t",frame[k]);
}
printf("\n");
}
printf("Page Fault Is %d",count);
return 0;
}

RESULT
Thus the program to implement FIFO (First In First Out)page replacement algorithm is executed
and the output is verified.
SAMPLE VIVA-VOCE QUESTIONS
1. Why page replacement is needed?
2. What is victim frame?
3. What is belady‟s anomally?
4. What is meant byreference string?
5.

53
Ex.No:12(b) IMPLEMENTATION OF LRU PAGE REPLACEMENT ALGORITHM
AIM
To implement page replacement algorithm LRU (Lease Recently Used) algorithm.
LRU PAGE REPLACEMENT
The page that has not been used for the longest period of time. This approach is the least recently
used (LRU) algorithm. When a page must be replaced, LRU chooses the page that has not been used for
the longest period of time.
ALGORITHM
Step1. Create a queue to hold all pages in memory
Step2. When the page is required replace the page at the head of the queue
Step3. Now the new page is inserted at the tail of the queue
Step4. Create a stack
Step5. When the page fault occurs replace page present at the bottom of the stack
PROGRAM
#include<stdio.h>
int main()
{
int q[20],p[50],c=0,c1,d,f,i,j,k=0,n,r,t,b[20],c2[20];
printf("Enter no of pages:");
scanf("%d",&n);
printf("Enter the reference string:");
for(i=0;i<n;i++)
scanf("%d",&p[i]);
printf("Enter no of frames:");
scanf("%d",&f);
q[k]=p[k];
printf("\n\t%d\n",q[k]);
c++;
k++;
for(i=1;i<n;i++){
c1=0;
for(j=0;j<f;j++){
if(p[i]!=q[j])
c1++;
}
if(c1==f)
{
c++;
if(k<f)
{
q[k]=p[i];
k++;
for(j=0;j<k;j++)
printf("\t%d",q[j]);
54
printf("\n");
}
else
{
for(r=0;r<f;r++)
{
c2[r]=0;
for(j=i-1;j<n;j--)
{
if(q[r]!=p[j])
c2[r]++;
else
break;
}
}
for(r=0;r<f;r++)
b[r]=c2[r];
for(r=0;r<f;r++) {
for(j=r;j<f;j++) {
if(b[r]<b[j])
{
t=b[r];
b[r]=b[j];
b[j]=t;
}}}
for(r=0;r<f;r++) {
if(c2[r]==b[0])
q[r]=p[i];
printf("\t%d",q[r]);
}
printf("\n");
} }}
printf("\nThe no of page faults is %d",c);
}

RESULT
Thus the program to implement page replacement algorithm LRU (Least Recently Used) algorithm
is executed and the output is verified.

SAMPLE VIVA-VOCE QUESTIONS

1. Is there a possibilty of belady‟s anomaly in LRU?
2. What is reference bit?
3. What is a frame?
4. Define counters.
55
Ex. No: 12(c) IMPLEMENTATION OF OPTIMAL (LFU) PAGE REPLACEMENT ALGORITHM

AIM
To write a C program to implement an optimal page replacement algorithm.
DESCRIPTION
An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms, and will never
suffer from Belady's anomaly. It is also called OPT or MIN. It is simply 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.
ALGORITHM
Step 1. Start the process
Step 2. Declare the size
Step 3. Get the number of pages to be inserted
Step 4. Get the value
Step 5. Declare counter and stack
Step 6. Select the least frequently used page by counter value
Step 7. Stack them according the selection.
Step 8. .Display the values
Step 9. Stop the process
PROGRAM
#include<stdio.h>
int main()
{
int no_of_frames, no_of_pages, frames[10], pages[30], temp[10], flag1, flag2, flag3, i, j, k, pos, max,
faults = 0;
printf("Enter number of frames: ");
scanf("%d", &no_of_frames);

printf("Enter number of pages: ");

scanf("%d", &no_of_pages);

printf("Enter page reference string: ");

for(i = 0; i < no_of_pages; ++i){

scanf("%d", &pages[i]);
}

for(i = 0; i < no_of_frames; ++i){

frames[i] = -1;
}

for(i = 0; i < no_of_pages; ++i){

56
flag1 = flag2 = 0;

for(j = 0; j < no_of_frames; ++j){

if(frames[j] == pages[i]){
flag1 = flag2 = 1;
break;
}}

if(flag1 == 0){
for(j = 0; j < no_of_frames; ++j){
if(frames[j] == -1){
faults++;
frames[j] = pages[i];
flag2 = 1;
break;
}}}

if(flag2 == 0){
flag3 =0;

for(j = 0; j < no_of_frames; ++j){

temp[j] = -1;

for(k = i + 1; k < no_of_pages; ++k){

if(frames[j] == pages[k]){ temp[j] = k;
break;
}}}

for(j = 0; j < no_of_frames; ++j){

if(temp[j] == -1){
pos = j;
flag3 = 1;
break;
}}
if(flag3 ==0){
max = temp[0];
pos = 0;

for(j = 1; j < no_of_frames; ++j){

if(temp[j] > max){
max = temp[j];
pos = j;
} } } frames[pos] = pages[i];
faults++;
}
printf("\n");

for(j = 0; j < no_of_frames; ++j){

printf("%d\t", frames[j]);
57
}}
printf("\n\nTotal Page Faults = %d", faults);
return 0;
}

RESULT
Thus the program a C program to implement an optimal page replacement algorithm is executed
and the output is verified.

SAMPLE VIVA-VOCE QUESTIONS

1. What is the full form of LRU?
2. Explain when page replacement occurs?
3. Which is the best page replacement algorithm? why?
4. What do you mean by page fault?
58
Ex. No: 13(a) IMPLEMENTATION OF SINGLE LEVEL DIRECTORY FILE ORGANIZATION
TECHNIQUE

AIM
To write a C program to implement the Single Level Directory file organization technique.
DESCRIPTION
The structure of the directories and the relationship among them are the main areas where file systems
tend to differ, and it is also the area that has the most significant effect on the user interface provided by
the file system. The most common directory structures used by multi-user systems are: ∙ single-level
directory
∙ two-level directory
∙ tree-structured directory
∙ acyclic directory
Single level directory
In a single-level directory system, all the files are placed in one directory. This is very common on
single-user OS's. A single-level directory has significant limitations, however, when the number of files
increases or when there is more than one user. Since all files are in the same directory, they must have
unique names. If there are two users who call their data file "test", then the unique-name rule is violated.
Although file names are generally selected to reflect the content of the file, they are often quite limited in
length. Even with a single-user, as the number of files increases, it becomes difficult to remember the
names of all the files in order to create only files with unique names.

ALGORITHM
Step 1. Start
Step 2. Get the number of files
Step 3. Implement the necessary graphical function
Step 4. Get the file name
Step 5. mid=value/count value
Step 6. Print single level directory
Step 7. Stop
PROGRAM
#include<stdio.h>

59
#include<conio.h>
#include<stdlib.h>
#include<graphics.h>
void main()
{
int gd=DETECT,gm,count,i,j,mid,cir_x;
char fname[10][20];
clrscr();
initgraph(&gd,&gm,"c:\\tc\\bgi");
cleardevice();
setbkcolor(GREEN);
puts("Enter no of files do u have?");
scanf("%d",&count);
for(i=0;i<count;i++)
{
cleardevice();
setbkcolor(GREEN);
printf("Enter file %d name",i+1);
scanf("%s",fname[i]);
setfillstyle(1,MAGENTA);
mid=640/count;
cir_x=mid/3;
bar3d(270,100,370,150,0,0);
settextstyle(2,0,4);
settextjustify(1,1);
outtextxy(320,125,"Root Directory");
setcolor(BLUE);
for(j=0;j<=i;j++,cir_x+=mid)
{
line(320,150,cir_x,250);
fillellipse(cir_x,250,30,30);
outtextxy(cir_x,250,fname[j]);
}
getch();
}
}

RESULT
Thus the C program to implement the Single Level Directory file organization technique is
executed and verified.
SAMPLE VIVA-VOCE QUESTIONS
1. What is meant by file system?
2. What are the types of directory structure?
3. What are the operations of directory?
4. What is Single level directory?
5. Define device directory.

60
Ex. No: 13(b) IMPLEMENTATION OF TWO LEVEL FILE ORGANIZATION TECHNIQUE

AIM
To write a C program to implement the Two Level Directory file organization technique.
DESCRIPTION
In the two-level directory system, the system maintains a master block that has one entry for each user.
This master block contains the addresses of the directory of the users .There are still problems with two
level directory structure. This structure effectively isolates one user from another. This is an advantage
when the users are completely independent, but a disadvantage when the users want to cooperate on some
task and access files of other users. Some systems simply do not allow local files to be accessed by other
users.
ALGORITHM
Step 1. Start
Step 2. Create tree element
Step 3. Create root directory and implement the necessary graphical function
Step 4. Get the number of director/file
Step 5. Print two level directory
Step 6. Stop.
PROGRAM
#include<stdio.h>
#include<graphics.h>
struct tree_element
{
char name[20];
int x,y,ftype,lx,rx,nc,level;
struct tree_element *link[5];
};
typedef struct tree_element node;
void main()
{
int gd=DETECT,gm;
node *root;
root=NULL;
clrscr();
61
create(&root,0,"null",0,639,320);
clrscr();
initgraph(&gd,&gm,"c:\\tc\\bgi");
display(root);
getch();
closegraph();
}
create(node **root,int lev,char *dname,int lx,int rx,int x)
{
int i,gap;
if(*root==NULL)
{
(*root)=(node*)malloc(sizeof(node));
printf("enter name of dir/file(under %s):",dname);
fflush(stdin);
gets((*root)->name);
if(lev==0||lev==1)
(*root)->ftype=1;
else
(*root)->ftype=2;
(*root)->level=lev;
(*root)->y=50+lev*50;
(*root)->x=x;
(*root)->lx=lx;
(*root)->rx=rx;
for(i=0;i<5;i++)
(*root)->link[i]=NULL;
if((*root)->ftype==1)
{
if(lev==0||lev==1)
{
if((*root)->level==0)
printf("How many users");
else
printf("how many files");
printf("(for%s):",(*root)->name);
scanf("%d",&(*root)->nc);
}
else
(*root)->nc=0;
if((*root)->nc==0)
gap=rx-lx;
else
gap=(rx-lx)/(*root)->nc;
for(i=0;i<(*root)->nc;i++)
create(&((*root)->link[i]),lev+1,(*root)-
>name,lx+gap*i,lx+gap*i+gap,lx+gap*i+gap/2)
;}
else
(*root)->nc=0;
}
}
62
display(node *root)
{
int i;
settextstyle(2,0,4);
settextjustify(1,1);
setfillstyle(1,BLUE);
setcolor(14);
if(root!=NULL)
{
for(i=0;i<root->nc;i++)
{
line(root->x,root->y,root->link[i]->x,root->link[i]->y);
}
if(root->ftype==1)
bar3d(root->x-20,root->y-10,root->x+20,root->y+10,0,0);
else
fillellipse(root->x,root->y,20,20);
outtextxy(root->x,root->y,root->name);
for(i=0;i<root->nc;i++)
{
display(root->link[i]);
}
}}

RESULT
Thus the C program to implement the Two Level Directory file organization technique is executed
and verified.
SAMPLE VIVA-VOCE QUESTIONS
1. What is Two-Level Directory?
2. What is UFD?
3. What is MFD?
4. What is search path?

63
Ex. No: 13(c) IMPLEMENTATION OF HIERARCHICAL FILE ORGANIZATION
TECHNIQUES

AIM
To write a C program to implement the Hierarchical directory file organization technique.
DESCRIPTION
The two level directories eliminate name conflicts among users but it is not satisfactory for users but it is
not satisfactory for users with a large no of files. To avoid this, create the subdirectory and load the same
type of the files into the subdirectory. So, in this method each can have as many directories are needed.
This directory structure looks like tree, that‟s why it is also said to be tree-level directory structure

ALGORITHM
Step 1. Start
Step 2. Create tree element
Step 3. Create root directory and implement the necessary graphical function
Step 4. Get the number of director/file
Step 5. Get the number of sub-directory and files
Step 6. Print Hierarchical directory
Step 7. Stop.
PROGRAM
#include<stdio.h>
#include<graphics.h>
struct tree_element
{
char name[20];
int x,y,ftype,lx,rx,nc,level;
struct tree_element *link[5];
};
typedef struct tree_element node;
void main()
{
64
int gd=DETECT,gm;
node *root;
root=NULL;
clrscr();
create(&root,0,"root",0,639,320);
clrscr();
initgraph(&gd,&gm,"c:\\tc\\BGI");
display(root);
getch();
closegraph();
}
create(node **root,int lev,char *dname,int lx,int rx,int x)
{
int i,gap;
if(*root==NULL)
{
(*root)=(node *)malloc(sizeof(node));
printf("Enter name of dir/file(under %s) : ",dname);
fflush(stdin);
gets((*root)->name);
printf("enter 1 for Dir/2 for file :");
scanf("%d",&(*root)->ftype);
(*root)->level=lev;
(*root)->y=50+lev*50;
(*root)->x=x;
(*root)->lx=lx;
(*root)->rx=rx;
for(i=0;i<5;i++)
(*root)->link[i]=NULL;
if((*root)->ftype==1)
{
printf("No of sub directories/files(for %s):",(*root)->name);
scanf("%d",&(*root)->nc);
if((*root)->nc==0)
gap=rx-lx;
else
gap=(rx-lx)/(*root)->nc;
for(i=0;i<(*root)->nc;i++)
create(&((*root)->link[i]),lev+1,(*root)-
>name,lx+gap*i,lx+gap*i+gap,lx+gap*i+gap/2);
}
else
(*root)->nc=0;
}
}
display(node *root)
{
int i;
settextstyle(2,0,4);
settextjustify(1,1);
setfillstyle(1,BLUE);
setcolor(14);
65
if(root !=NULL)
{
for(i=0;i<root->nc;i++)
{
line(root->x,root->y,root->link[i]->x,root->link[i]->y);
}
if(root->ftype==1)
bar3d(root->x-20,root->y-10,root->x+20,root->y+10,0,0);
else
fillellipse(root->x,root->y,20,20);
outtextxy(root->x,root->y,root->name);
for(i=0;i<root->nc;i++)
{
display(root->link[i]);
}
}
}

RESULT
Thus the C program to implement the Hierarchical Directory file organization technique is
executed and verified.
SAMPLE VIVA-VOCE QUESTIONS
1. What is Hierarchical File?
2. What is root directory?
3. What is an absolute path name?

66
Ex. No: 13(d) IMPLEMENTATION OF DAG (DIRECTED ACYCLIC GRAPH) FILE
ORGANIZATION

AIM
To write a C program to implement the DAG file organization technique.
DESCRIPTION
An acyclic directory structure is an extension of the tree-structured directory structure. In the tree
structured directory, files and directories starting from some fixed directory are owned by one particular
user. In the acyclic structure, this prohibition is taken out and thus a directory or file under directory can
be owned by several users. An acyclic graph that is a graph with no cycles allows directories to share
subdirectories and files. the same file or subdirectory may be in two different directories. When we add
links to an existing tree structured directory, the tree structure is destroyed, resulting in a simple graph
structure. This structure is used to traversing is easy and file sharing also possible.

ALGORITHM
Step 1. Start
Step 2. Create tree element
Step 3. Create root directory and implement the necessary graphical function
Step 4. Get the number of director/file
Step 5. Get the number of sub-directory and files
Step 6. Get the value of an edge (i,j) whenever i < j
Step 7. Calculate N-choose-2 = n (n-1)/2 edges, but no cycles.
Step 8. Print Hierarchical directory
Step 9. Stop.
PROGRAM
#include<stdio.h>
67
#include<conio.h>
#include<graphics.h>
#include<string.h>
struct tree_element
{
char name[20];
int x,y,ftype,lx,rx,nc,level;
struct tree_element *link[5];
};
typedef struct tree_element node;
typedef struct
{
char from[20];
char to[20];
}link;
link L[10];
int nofl;
node * root;
void main()
{
int gd=DETECT,gm;
root=NULL;
clrscr();
create(&root,0,"root",0,639,320);
read_links();
clrscr();
initgraph(&gd,&gm,"c:\\tc\\BGI");
draw_link_lines();
display(root);
getch();
closegraph();
}
read_links()
{
int i;
printf("how many links");
scanf("%d",&nofl);
for(i=0;i<nofl;i++)
{
printf("File/dir:");
fflush(stdin);
gets(L[i].from);
printf("user name:");
fflush(stdin);
gets(L[i].to);
}
}
draw_link_lines()
{
int i,x1,y1,x2,y2;
for(i=0;i<nofl;i++)
{
68
search(root,L[i].from,&x1,&y1);
search(root,L[i].to,&x2,&y2);
setcolor(LIGHTGREEN);
setlinestyle(3,0,1);
line(x1,y1,x2,y2);
setcolor(YELLOW);
setlinestyle(0,0,1);
}
}
search(node *root,char *s,int *x,int *y)
{
int i;
if(root!=NULL)
{
if(strcmpi(root->name,s)==0)
{
*x=root->x;
*y=root->y;
return;
}
else
{
for(i=0;i<root->nc;i++)
search(root->link[i],s,x,y);
}}}
create(node **root,int lev,char *dname,int lx,int rx,int x)
{
int i,gap;
if(*root==NULL)
{
(*root)=(node *)malloc(sizeof(node));
printf("enter name of dir/file(under %s):",dname);
fflush(stdin);
gets((*root)->name);
printf("enter 1 for dir/ 2 for file:");
scanf("%d",&(*root)->ftype);
(*root)->level=lev;
(*root)->y=50+lev*50;
(*root)->x=x;
(*root)->lx=lx;
(*root)->rx=rx;
for(i=0;i<5;i++)
(*root)->link[i]=NULL;
if((*root)->ftype==1)
{
printf("no of sub directories /files (for %s):",(*root)->name);
scanf("%d",&(*root)->nc);
if((*root)->nc==0)
gap=rx-lx;
else
gap=(rx-lx)/(*root)->nc;
for(i=0;i<(*root)->nc;i++)
69
create( & ( (*root)->link[i] ) , lev+1 , (*root)-
>name,lx+gap*i,lx+gap*i+gap,lx+gap*i+gap/2);
}
else
(*root)->nc=0;
}}
/* displays the constructed tree in graphics mode */
display(node *root)
{
int i;
settextstyle(2,0,4);
settextjustify(1,1);
setfillstyle(1,BLUE);
setcolor(14);
if(root !=NULL)
{
for(i=0;i<root->nc;i++)
{
line(root->x,root->y,root->link[i]->x,root->link[i]->y);

}
if(root->ftype==1)
bar3d(root->x-20,root->y-10,root->x+20,root->y+10,0,0);
else
fillellipse(root->x,root->y,20,20);
outtextxy(root->x,root->y,root->name);
for(i=0;i<root->nc;i++)
{
display(root->link[i]);
}}}

RESULT
Thus the C program to implement the DAG Directory file organization technique is executed and
verified.
SAMPLE VIVA-VOCE QUESTIONS
1. What is acyclic graph?
2. What is the use of shared file?
3. What is link?
70
Ex. No: 14(a) IMPLEMENTATION OF SEQUENTIAL FILE ALLOCATION STRATEGY

AIM
To write a C Program to implement Sequential File Allocation method.
DESCRIPTION
Contiguous allocation requires that each file occupy a set of contiguous blocks on the disk. Disk
addresses define a linear ordering on the disk. With this ordering, assuming that only one job is accessing
the disk, accessing block b + 1 after block b normally requires no head movement. When head movement
is needed (from the last sector of one cylinder to the first sector of the next cylinder), the head need only
move from one track to the next. Thus, the number of disk seeks required for accessing contiguously
allocated files is minimal, as is seek time when a seek is finally needed.

ALGORITHM
Step 1. Start
Step 2. Get the Starting block number and length of the file from the user.
Step 3. Allocate files sequentially until end of the file.
Step 4. Display the fragments of the file.
Step 5. Stop
PROGRAM
#include<stdio.h>
main()
{
int n,i,j,b[20],sb[20],t[20],x,c[20][20];
printf("Enter no.of files:");
scanf("%d",&n);
for(i=0;i<n;i++)
{

71
printf("Enter no. of blocks occupied by file%d",i+1);
scanf("%d",&b[i]);
printf("Enter the starting block of file%d",i+1);
scanf("%d",&sb[i]);
t[i]=sb[i];
for(j=0;j<b[i];j++)
c[i][j]=sb[i]++;
}
printf("Filename\tStart block\tlength\n");
for(i=0;i<n;i++)
printf("%d\t %d \t%d\n",i+1,t[i],b[i]);
printf("Enter file name:");
scanf("%d",&x);
printf("File name is:%d",x);
printf("length is:%d",b[x-1]);
printf("blocks occupied:");
for(i=0;i<b[x-1];i++)
printf("%4d",c[x-1][i]);
}

RESULT
Thus the program to sequential file allocation method is executed and the output is verified.
SAMPLE VIVA-VOCE QUESTIONS
1. Define Sequential File allocation
2. What is external fragmentation?
3. Why we use file allocation strategies?
4. What are the advantages and disadvantages of Sequential File allocation?
72
Ex. No: 14(b) IMPLEMENTATION OF INDEXED FILE ALLOCATION STRATEGY

AIM
To write a C Program to implement Indexed File Allocation method.
DESCRIPTION
Linked allocation solves the external-fragmentation and size-declaration problems of contiguous
allocation. However, in the absence of a FAT, linked allocation cannot support efficient direct access, since
the pointers to the blocks are scattered with the blocks themselves all over the disk and must be retrieved
in order. Indexed allocation solves this problem by bringing all the pointers together into one location: the
index block. Each file has its own index block, which is an array of disk-block addresses. The ith entry in
the index block points to the ith block of the file. The directory contains the address of the index block.

ALGORITHM
Step 1. Start
Step 2. Get the index block no. and total no.of files in a block from the user.
Step 3. Allocate files based on the index block no.
Step 4. Arrange the files based on indexes which are created for each fragment of the file such that
each and every similar indexed file is maintained by the primary index to provide the flow to file
fragments.
Step 5. Stop
PROGRAM
#include<stdio.h>
main()
{
int n,m[20],i,j,sb[20],s[20],b[20][20],x;
printf("Enter no. of files:");
scanf("%d",&n);
for(i=0;i<n;i++)
{ printf("\nEnter starting block and size of file%d:",i+1);
73
scanf("%d%d",&sb[i],&s[i]);
printf("\nEnter blocks occupied by file%d:",i+1);
scanf("%d",&m[i]);
printf("\n enter blocks of file%d:",i+1);
for(j=0;j<m[i];j++)
scanf("%d",&b[i][j]);
} printf("\nFile\t index\tlength\n");
for(i=0;i<n;i++)
{
printf("%d\t%d\t%d\n",i+1,sb[i],m[i]);
}printf("\nEnter file name:");
scanf("%d",&x);
printf("file name is:%d\n",x);
i=x-1;
printf("Index is:%d",sb[i]);
printf("Block occupied are:");
for(j=0;j<m[i];j++)
printf("%3d",b[i][j]);
}

RESULT
Thus the program to Indexed file allocation method is executed and the output is verified.
SAMPLE VIVA-VOCE QUESTIONS
1. What file allocation strategy is most appropriate for random access files?
2. Define File and Directory?
3. What is FCB?
4. What are the advantages and disadvantages Indexed Allocation?
5. What is index block?

74
Ex. No: 14(c) IMPLEMENTATION OF LINKED FILE ALLOCATION STRATEGY
AIM
To write a C Program to implement Linked File Allocation method.
DESCRIPTION
Linked allocation solves all problems of contiguous allocation. In linked allocation, each file is a linked
list of disk blocks. The directory contains a pointer to the first and (optionally the last) block of the file.
Each block contains a pointer to the next block and the last block contains a NIL pointer. The value -1
may be used for NIL to differentiate it from block 0.With linked allocation, each directory entry has a
pointer to the first disk block of the file. This pointer is initialized to nil (the end-of-list pointer value) to
signify an empty file. There is no external fragmentation with linked allocation. Any free block can be
used to satisfy a request. A file can continue to grow as long as there are free blocks.

ALGORITHM
Step 1. Start
Step 2. Read File allocation request which consist of File name, No of blocks , contents
Step 3. Traverse the AVAIL linked list from the starting node
Step 4. Retrieve the required no of blocks from AVAIL List
Step 5. Assign the contents of file to the retrieved blocks
Step 6. Update the FAT by making an entry in FAT
Step 7. Update the AVAIL LIST
Step 8. Display the AVAIL List and FAT table
Step 9. Stop
PROGRAM
#include<stdio.h>
struct file
{
char fname[10];
int start,size,block[10];
}f[10];
main()
75
{
int i,j,n;
printf("Enter no. of files:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter file name:");
scanf("%s",&f[i].fname);
printf("Enter starting block:");
scanf("%d",&f[i].start);
f[i].block[0]=f[i].start;
printf("Enter no.of blocks:");
scanf("%d",&f[i].size);
printf("Enter block numbers:");
for(j=1;j<=f[i].size;j++)
{
scanf("%d",&f[i].block[j]);
}
}
printf("File\tstart\tsize\tblock\n");
for(i=0;i<n;i++)
{
printf("%s\t%d\t%d\t",f[i].fname,f[i].start,f[i].size);
for(j=1;j<=f[i].size-1;j++)
printf("%d--->",f[i].block[j]);
printf("%d",f[i].block[j]);
printf("\n");
}
}
RESULT
Thus the program to linked file allocation method is executed and the output is verified.
SAMPLE VIVA-VOCE QUESTIONS
1. What is FAT?
2. What is chunk?
3. Define linked scheme.
76
Ex No.15(a) IMPLEMENTATION OF FCFS DISK SCHEDULING ALGORITHM
AIM
To write a C program to implement the FCFS disk Scheduling Algorithm.
DESCRIPTION
Serve I/O requests in the order that they are received. This algorithm is fair, but poor
performance. ALGORITHM
Step1: Start the program
Step2: Let Request array represents an array storing indexes of tracks
that have been requested in ascending order of their time of arrival „head‟ is the position of disk
head.
Step3: Let us one by one take the tracks in default order.
Step4: And calculate the absolute distance of the track from the head.
Step5: Increment the total seek count with this distance.
Step6: Currently serviced track position now becomes the new head position.
Step7: Go to Step2 until all tracks in request array have not been serviced.
STEP8: Stop
PROGRAM
#include<stdio.h>
#include<stdlib.h>
int main()
{
int RQ[100],i,n,TotalHeadMoment=0,initial;
printf("Enter the number of Requests\n");
scanf("%d",&n);
printf("Enter the Requests sequence\n");
for(i=0;i<n;i++)
scanf("%d",&RQ[i]);
printf("Enter initial head position\n");
scanf("%d",&initial);
// logic for FCFS disk scheduling
for(i=0;i<n;i++)
{
TotalHeadMoment=TotalHeadMoment+abs(RQ[i]-initial);
initial=RQ[i];
}
printf("Total head moment is %d",TotalHeadMoment);
return 0;
}

RESULT
Thus the C program to implement the FCFS disk Scheduling Algorithm is executed and verified.
77
Ex No.15(a) IMPLEMENTATION OF SSTF DISK SCHEDULING ALGORITHM AIM
To write a C program to implement the SSTF disk Scheduling Algorithm.
DESCRIPTION
Selects the request with the minimum seek time from the current head position. May cause
starvation of some requests if requests keep coming in close to current location while a request is waiting
on the far side of the disk
ALGORITHM
Step 1: start
Step 2: Let Request array represents an array storing indexes of tracks that have been requested. „head‟ is
the position of disk head.
Step 3: Find the positive distance of all tracks in the request array from head.
Step 4: Find a track from requested array which has not been accessed/serviced yet and has minimum
distance from head.
Step 5. Increment the total seek count with this distance.
Step 6: Currently serviced track position now becomes the new head position.
Step 7: Go to Step2 until all tracks in request array have not been serviced.
Step 8: stop the program
PROGRAM
#include<stdio.h>
#include<stdlib.h>
int main()
{
int RQ[100],i,n,TotalHeadMoment=0,initial,count=0;
printf("Enter the number of Requests\n");
scanf("%d",&n);
printf("Enter the Requests sequence\n");
for(i=0;i<n;i++)
scanf("%d",&RQ[i]);
printf("Enter initial head position\n");
scanf("%d",&initial);

// logic for sstf disk scheduling

/* loop will execute until all process is completed*/

while(count!=n)
{
int min=1000,d,index;
for(i=0;i<n;i++)
{
d=abs(RQ[i]-initial);
if(min>d)
{
min=d;

78
index=i;
}

}
TotalHeadMoment=TotalHeadMoment+min;
initial=RQ[index];
// 1000 is for max
// you can use any number
RQ[index]=1000;
count++;
}

printf("Total head movement is %d",TotalHeadMoment);

return 0;
}

RESULT
Thus the C program to implement the SSTF disk Scheduling Algorithm is executed and verified.
79
Ex. No.15(c) IMPLEMENTATION OF SCAN DISK SCHEDULING ALGORITHM AIM
To write a C program to implement the SCAN disk Scheduling Algorithm.
FCFS DISK SCHEDULING
Disk head moves from one end of the disk to the other, servicing requests as it goes. When it
reaches the other end, it immediately returns to the beginning of the disk, without servicing any requests
on the return trip. Provides a more uniform wait time than SCAN.
The C-SCAN scheduling algorithm essentially treats the cylinders as a circular list that wraps
around from the final cylinder to the first one.
ALGORITHM
Step 1: Start the process.
Step 2: Arrange all the I/O requests in ascending order.
Step 3: The head starts servicing the requests in the one direction based on user interest of selection. Step
4: As soon as a request is encountered, head movement is calculated as the current request - the previous
request.
Step 5: This process is repeated until the head reaches the end of the disc and the head movements are
added.
Step 6: Once the end of the disk is reached, the head direction is reversed, and it services all the requests
in the opposite direction.
Step 7: Scheduling completes as soon as all the requests are serviced and the total head movements can be
calculated.
Step 8: Stop
PROGRAM
#include<stdio.h>
#include<stdlib.h>
int main()
{
int RQ[100],i,j,n,TotalHeadMoment=0,initial,size,move;
printf("Enter the number of Requests\n");
scanf("%d",&n);
printf("Enter the Requests sequence\n");
for(i=0;i<n;i++)
scanf("%d",&RQ[i]);
printf("Enter initial head position\n");
scanf("%d",&initial);
printf("Enter total disk size\n");
scanf("%d",&size);
printf("Enter the head movement direction for high 1 and for low 0\n");
80