Operating System Laboratory Manual 1m6q5h

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

K.L.N. COLLEGE OF ENGINEERING Pottapalayam Post - 630 612. Sivagangai District, Tamil Nadu.

DEPARTMENT OF INFORMATION TECHNOLOGY

IT6412-OPERATING SYSTEM MANUAL

Staff In-Charges and Prepared by Mrs.C.Manjula Devi, AP2/IT

III Year/V Semester (July 2015-November 2015)

1

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in ANNA UNIVERSITY, CHENNAI REGULATION 2013 B.TECH INFORMATION TECHNOLOGY SYLLABUS IT6412

OPERATING SYSTEMS LAB (Common to CSE & IT)

0032

OBJECTIVES: The student should be made to:  Learn shell programming and the use of filters in the UNIX environment.  Be exposed to programming in C using system calls.  Learn to use the file system related system calls.  Be exposed to process creation and inter process communication.  Be familiar with implementation of U Scheduling Algorithms, page replacement algorithms and Deadlock avoidance LIST OF EXPERIMENTS: 1. Basics of UNIX commands. 2. Shell Programming. 3. Implement the following U scheduling algorithms a) Round Robin b) SJF c) FCFS d) Priority 4. Implement all file allocation strategies a) Sequential b) Indexed c) Linked 5. Implement Semaphores 6. Implement all File Organization Techniques a) Single level directory b) Two level c) Hierarchical d) DAG 7. Implement Bankers Algorithm for Dead Lock Avoidance 8. Implement an Algorithm for Dead Lock Detection 9. Implement e all page replacement algorithms a) FIFO b) LRU c) LFU 10. Implement Shared memory and IPC 11. Implement Paging Technique of memory management. 12. Implement Threading & Synchronization Applications TOTAL: 45 PERIODS OUTCOMES: At the end of the course, the student should be able to  Implement deadlock avoidance, and Detection Algorithms  Compare the performance of various U Scheduling Algorithm  Critically analyze the performance of the various page replacement algorithms  Create processes and implement IPC REFERENCE: spoken-tutorial.org

LIST OF EQUIPMENT FOR A BATCH OF 30 STUDENTS:

2

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in Standalone desktops with C / C++ / Java / Equivalent complier 30 Nos. (or) Server with C / C++ / Java / Equivalent complier ing 30 terminals Syllabus ed from www.annauniv.edu

List of Experiments 1.

Basics of UNIX commands

2.

Shell Programming

3. 4. 5.

Implement the following U scheduling algorithms a) Round Robin b) SJF c) FCFS d) Priority Implement all file allocation strategies b) Sequential b) Indexed c) Linked Implement Semaphores

7.

Implement all File Organization Techniques Single level directory b) Two level c) Hierarchical d) DAG Implement Bankers Algorithm for Dead Lock Avoidance

8.

Implement an Algorithm for Dead Lock Detection

6.

10.

Implement e all page replacement algorithms a) FIFO b) LRU c) LFU Implement Shared memory and IPC

11.

Implement Paging Technique of memory management.

12.

Implement Threading & Synchronization Applications

13.

Model Test

9.

Ex.No : 1

UNIX COMMANDS

I. Basic Commands: 1. Echo Command : This command is used to print the arguments on the screen . Syntax : $echo Multi line echo command : To have the output in the same line , the following commands can be used. Syntax : $echo text To have the output in different line, the following command can be used. Syntax : $echo “text >line2 >line3” 2. ’who’ Command : It is used to display who are the s connected to our computer currently.

3

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in Syntax : $who – option‟s Options : H–Display the output with headers. b–Display the last booting date or time or when the system was lastely rebooted. 3. ’who am i’ Command : Display the details of the current working directory. Syntax : $who am i 4. ’tty’ Command : It will display the terminal name. Syntax : $tty 5. ’Binary’ Calculator Command : It will change the „$‟ mode and in the new mode, arithematic operations such as +,,*,/,%,n,sqrt(),length(),=, etc can be performed . This command is used to go to the binary calculus mode. Syntax : $bc operations ^d $ 1 base –inputbase 0 base – outputbase are used for base conversions. Base : Decimal = 1 Binary = 2 Octal = 8 Hexa = 16 II. DIRECTORY RELATED COMMANDS : 1.Present Working Directory Command : To print the complete path of the current working directory. Syntax : $pwd 2.MKDIR Command : To create or make a new directory in a current directory . Syntax : $mkdir 3.CD Command : To change or move the directory to the mentioned directory . Syntax : $cd III. FILE RELATED COMMANDS : 1.CREATE A FILE : To create a new file in the current directory we use CAT command. Syntax : $cat > symbol is redirectory we use cat command. 2.DISPLAY A FILE : To display the content of file mentioned we use CAT command without „>‟ operator. Syntax : $cat
4

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in Syntax : $ cat >> <destination filename> $ cat <source filename> >> <destination filename> it is avoid overwriting. Options : -n content of file with numbers included with blank lines. Syntax : $cat –n 4.SORTING A FILE : To sort the contents in alphabetical order in reverse order. Syntax : $sort Option : $ sort –r 5.COPYING CONTENTS FROM ONE FILE TO ANOTHER : To copy the contents from source to destination file . so that both contents are same. Syntax : $ <source filename> <destination filename> $ <source filename path > <destination filename path> 6.MOVE Command : To completely move the contents from source file to destination file and to remove the source file. Syntax : $ mv <source filename> <destination filename> 7.REMOVE Command : To permanently remove the file we use this command . Syntax : $rm 8. WORD Command : To list the content count of no of lines , words, characters . Syntax : $wc Options : -c – to display no of characters. -l – to display only the lines. -w – to display the no of words. 9. LIST Command : It is used to list all the contents in the current working directory. Syntax : $ ls – options <arguments> If the command does not contain any argument means it is working in the Current directory. Options : a– used to list all the files including the hidden files. c– list all the files columnwise. d- list all the directories. m- list the files separated by commas. p- list files include „/‟ to all the directories. r- list the files in reverse alphabetical order. f- list the files based on the list modification date. x-list in column wise sorted order. VI .Date Command : This command is used to display the current data and time.

5

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in Syntax : $date $date +%ch Options : a = Abbrevated weekday. A = Full weekday. b = Abbrevated month. B = Full month. c = Current day and time. C = Display the century as a decimal number. d = Day of the month. D = Day in „mm/dd/yy‟ format h = Abbrevated month day. H = Display the hour. L = Day of the year. m = Month of the year. M = Minute. P = Display AM or PM S = Seconds T = HH:MM:SS format u = Week of the year. y = Display the year in 2 digit. Y = Display the full year. Z = Time zone . To change the format : Syntax : $date „+%H-%M-%S‟ 2.Calender Command : This command is used to display the calendar of the year or the particular month of calendar year. Syntax : a.$cal b.$cal <month> Here the first syntax gives the entire calendar for given year & the second Syntax gives the calendar of reserved month of that year.

V. FILTERS AND PIPES 1.HEAD : It is used to display the top ten lines of file. Syntax: $head 2.TAIL : This command is used to display the last ten lines of file. Syntax: $tail 3.PAGE : This command shows the page by page a screenfull of information is displayed after which the page command displays a prompt and es for the to strike the enter key to continue scrolling. Syntax: $ls –a\p 4.MORE : It also displays the file page by page .To continue scrolling with more command , press the space bar key. Syntax: $more 6. PIPE : It is a mechanism by which the output of one command can be channeled into the input of another command. Syntax: $who | wc-l

6

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

VI. SEARCHING AND SORTING COMMANDS 1. GREP :This command is used to search and print the specified patterns from the file. Syntax: $grep [option] pattern ‘grep’ command

- grep command searches the given file for lines containing a match to the given strings or words. By default, grep prints the matching lines. Use grep to search for lines of text that match one or many regular expressions, and outputs only the matching lines. The name, "grep", derives from the command used to perform a similar operation, using the Unix/Linux text editor ed: g/re/p Syntax grep 'word' filename grep 'string1 string2' filename cat otherfile | grep 'something' command | grep 'something' 2. SORT : This command is used to sort the datas in some order. Syntax: $sort

V. FILE PERMISSION COMMANDS

SYNTAX: $chmod mode filename DESCRIPTION: This command is used to alter the access permissions for the owner groups and others for a file. MODES: a) ABSOLUTE MODE: SYNTAX: $chmod filename DESCRIPTION: This mode uses number to alter permissions for a file or for all the s. OCTAL MEANING 4 Read permissions 2 Write 1 Execute 0 No permissions Eg: $chmod 644 file.c DESCRIPTION: Read and write to owner and read to groups and others. b) SYMBOLIC MODE: SYNTAX: $chmod filename DESCRIPTION: This mode uses letters to alter permissions for a file and for all s. CHARATER- TYPE OF u- denotes or owner of the file g- denotes group to which the belongs to o- denotes s excluding owner and iroup a- Denotes all s including owner, group and others. CHARATER- ACCESS PERMISSION r- sets read permission w- sets write permission v- sets execute permission CHARATER- ACTION TO BE PERFORMED + assigns permissions for the specified - removes permission from the specified

7

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in = Assign permission for the specified Eg: $chmod u+x file.c DESCRIPTION: Assigns execute permission to only. To check the access permissions, use this command. FOR Eg: ls.l file GENERAL PURPOSE COMMANDS: SYNTAX: $who | wc DESCRIPTION: This command first executes who and the result is transformed to the input of word count command.

vi EDITOR DESCRIPTION : The Vi editor is a visual editor used to create and edit text, files, documents and programs. It displays the content of files on the screen and allows a to add, delete or change part of text . There are three modes available in the Vi editor , they are 1.Command mode 2.Input (or) insert mode. Starting Vi : The Vi editor is invoked by giving the following commands in UNIX prompt. Syntax : $vi (or) $vi This command would open a display screen with 25 lines and with tilt (~) symbol at the start of each line. The first syntax would save the file in the filename mentioned and for the next the filename must be mentioned at the end. Options : 1.vi +n - this would point at the nth line (cursor pos). 2.vi –n - This command is to make the file to read only to change from one mode to another press escape key. INSERTING AND REPLACING COMMANDS : To move editor from command node to edit mode, you have to press the <ESC> key. For inserting and replacing the following commands are used. 1.ESC a Command : This command is used to move the edit mode and start to append after the current character. Syntax : <ESC> a 2.ESC A COMMAND : This command is also used to append the file , but this command append at the end of current line. Syntax : <ESC> A 3.<ESC> j : This command is used to move down a single line or a number of lines. Syntax : <ESC> j – single down movement. <ESC> nj – „n‟ times down movement. 4.<ESC> k : This command is used to move up a single line or a number of lines.

8

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in Syntax : <ESC> k – single line above. <ESC> nk – „n‟ lines above. 5.ENTER (OR) N ENTER : This command will move the cursor to the starting of next lines or a group of lines mentioned. Syntax : <ESC> enter <ESC> n enter. 6.<ESC> + Command : This command is used to move to the beginning of the next line. Syntax : <ESC> + <ESC> n+ 7.<ESC> - Command : This command is used to move to the beginning of the previous line. Syntax : <ESC> - <ESC> n8.<ESC> 0 : This command will bring the cursor to the beginning of the same current line. Syntax : <ESC> 0 9.<ESC> $ : This command will bring the cursor to the end of the current line. Syntax : <ESC> $ 10.<ESC> ^ : This command is used to move to first character of first lines. Syntax : <ESC> ^ 11.<ESC> b Command : This command is used to move back to the previous word (or) a number of words. Syntax : <ESC> b <ESC>nb 12.<ESC> e Command : This command is used to move towards and replace the cursor at last character of the word (or) no of words. Syntax : <ESC> e <ESC>ne 13.<ESC> w Command : This command is used to move forward by a single word or a group of words. Syntax : <ESC> w <ESC> nw DELETING THE TEXT FROM Vi : 1.<ESC> x Command : To delete a character to right of current cursor positions , this command is used. Syntax : <ESC> x <ESC> nx 2.<ESC> X Command : To delete a character to left of current cursor positions , this command is used. Syntax : <ESC> X <ESC> nX 3.<ESC> dw Command :

9

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in This command is to delete a single word or number of words to right of current cursor position. Syntax : <ESC> dw <ESC> ndw 4.db Command : This command is to delete a single word to the left of the current cursor position. Syntax : <ESC> db <ESC> ndb 5.<ESC> dd Command : This command is used to delete the current line (or) a number of line below the current line. Syntax : <ESC> dd <ESC> ndd 6.<ESC> d$ Command : This command is used to delete the text from current cursor position to last character of current line. Syntax : <ESC> d$ SAVING AND QUITING FROM vi :1.<ESC> w Command : To save the given text present in the file. Syntax : <ESC> : w 2.<ESC> q! Command : To quit the given text without saving. Syntax : <ESC> :q! 3.<ESC> wq Command : This command quits the vi editor after saving the text in the mentioned file. Syntax : <ESC> :wq 4.<ESC> x Command : This command is same as „wq‟ command it saves and quit. Syntax : <ESC> :x 5.<ESC> q Command : This command would quit the window but it would ask for again to save the file. Syntax : <ESC> : q Ex.No : 2

SHELL PROGRAMMING

a) COMPARISON OF TWO STRINGS Aim: To write a shell program to compare the two strings. Algorithm: Step1: Enter into the vi editor and go to the insert mode for entering the code Step2: Read the first string. Step3: Read the second string Step4: Compare the two strings using the if loop Step5: If the condition satisfies then print that two strings are equal else print two strings are not equal. Step6: Enter into the escape mode for the execution of the result and the output Program:

10

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in echo “enter the first string” read str1 echo “enter the second string” read str2 if [ $str1 = $str2 ] then echo “strings are equal” else echo “strings are unequal” fi Sample I/P:1 Enter first string: hai Enter second string: hai Sample O/P:1 The two strings are equal Sample I/P:2 Enter first string: hai Enter second string: cse Sample O/P:2 The two strings are not equal Result: Thus the shell program to compare the two strings is executed and output is verified successfully. b) MAXIMUM OF THREE NUMBERS Aim: To write a shell program to find greatest of three numbers. Algorithm: Step1: Declare the three variables. Step2: Check if A is greater than B and C. Step3: If so print A is greater. Step4: Else check if B is greater than C. Step5: If so print B is greater. Step6: Else print C is greater. Program: echo "enter A" read a echo "enter B" read b echo "enter C" read c if [ $a -gt $b -a $a -gt $c ] then echo "A is greater" elif [ $b -gt $a -a $b -gt $c ] then echo "B is greater" else echo "C is greater" fi Sample I/P:

11

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in Enter A:23 Enter B:45 Enter C:67 Sample O/P: C is greater Result: Thus the shell program to find the maximum of three numbers is executed and output is verified successfully. c) FIBONACCI SERIES Aim: To write a shell program to generate fibonacci series. Algorithm : Step 1 : Initialise a to 0 and b to 1. Step 2 : Print the values of 'a' and 'b'. Step 3 : Add the values of 'a' and 'b'. Store the added value in variable 'c'. Step 4 : Print the value of 'c'. Step 5 : Initialise 'a' to 'b' and 'b' to 'c'. Step 6 : Repeat the steps 3,4,5 till the value of 'a' is less than 10. Program : echo enter the number read n a=-1 b=1 i=0 while [ $i –le $n ] do t=`expr $a + $b` echo $t a=$b b=$t i=`expr $i + 1 done Sample I/P : Enter the no: 5 Sample O/P: 0 1 1 2 3 5 Result : Thus the shell program to find the fibonacci series is executed and output is verified successfully. d) ARITHMETIC OPERATIONS USING CASE Aim: To write a shell program to perform the arithmetic operations using case Algorithm : Step 1 : Read the input variables and assign the value Step 2 : Print the various arithmetic operations which we are going to perform Step 3 : Using the case operator assign the various functions for the arithmetic

12

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in operators. Step 4 : Check the values for all the corresponding operations. Step 5 : Print the result and stop the execution. Program : echo 1.Addition echo 2.Subraction echo 3.Multiplication echo 4.Division echo enter your choice read a echo enter the value of b read b echo enter the value of c read c echo b is $b c is $c case $a in 1)d=`expr $b + $c` echo the sum is $d ;; 2)d=`expr $b - $c` echo the difference is $d ;; 3)d=`expr $b \* $c` echo the product is $d ;; 4)d=`expr $b / $c` echo the quotient is $d ;; esac Sample I/P : 1.Addition 2.Subraction 3.Multiplication 4.Division Enter your choice:1 Enter the value of b:3 Enter the value of c:4 b is 3 c is 4 the sum is 7 Sample O/P: b is 3 c is 4 the sum is 7 Result : Thus the shell program to perform arithmetic operations using case is executed and output is verified successfully.

Ex. No:3(a)

ROUND ROBIN SCHEDULING

Aim: Write a C program to implement the various process scheduling mechanisms such as Round Robin Scheduling.

13

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in Algorithm for RR Step 1: Start the process Step 2: Accept the number of processes in the ready Queue and time quantum (or) time slice Step 3: For each process in the ready Q, assign the process id and accept the U burst time Step 4: Calculate the no. of time slices for each process where No. of time slice for process(n) = burst time process(n)/time slice Step 5: If the burst time is less than the time slice then the no. of time slices =1. Step 6: Consider the ready queue is a circular Q, calculate (a) Waiting time for process(n) = waiting time of process(n-1)+ burst time of process(n-1 ) + the time difference in getting the U from process(n-1) (b) Turn around time for process(n) = waiting time of process(n) + burst time of process(n)+ the time difference in getting U from process(n). Step 7: Calculate (a) Average waiting time = Total waiting Time / Number of process (b) Average Turnaround time = Total Turnaround Time / Number of process Step 8: Stop the process /* ROUND ROBIN SCHEDULING ALGORITHM */ #include<stdio.h> #include void main() { int ts,pid[10],need[10],wt[10],tat[10],i,j,n,n1; int bt[10],flag[10],ttat=0,twt=0; float awt,atat; clrscr(); printf("\t\t ROUND ROBIN SCHEDULING \n"); printf("Enter the number of Processors \n"); scanf("%d",&n); n1=n; printf("\n Enter the Timeslice \n"); scanf("%d",&ts); for(i=1;i<=n;i++) { printf("\n Enter the process ID %d",i); scanf("%d",&pid[i]); printf("\n Enter the Burst Time for the process"); scanf("%d",&bt[i]); need[i]=bt[i]; } for(i=1;i<=n;i++) { flag[i]=1; wt[i]=0; } while(n!=0) { for(i=1;i<=n;i++)

14

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in { if(need[i]>=ts) { for(j=1;j<=n;j++) { if((i!=j)&&(flag[i]==1)&&(need[j]!=0)) wt[j]+=ts; } need[i]-=ts; if(need[i]==0) { flag[i]=0; n--; } } else { for(j=1;j<=n;j++) { if((i!=j)&&(flag[i]==1)&&(need[j]!=0)) wt[j]+=need[i]; } need[i]=0; n--; flag[i]=0; } } } for(i=1;i<=n1;i++) { tat[i]=wt[i]+bt[i]; twt=twt+wt[i]; ttat=ttat+tat[i]; } awt=(float)twt/n1; atat=(float)ttat/n1; printf("\n\n ROUND ROBIN SCHEDULING ALGORITHM \n\n"); printf("\n\n Process \t Process ID \t BurstTime \t Waiting Time \t TurnaroundTime \n "); for(i=1;i<=n1;i++) { printf("\n %5d \t %5d \t\t %5d \t\t %5d \t\t %5d \n", i,pid[i],bt[i],wt[i],tat[i]); } printf("\n The average Waiting Time=4.2f",awt); printf("\n The average Turn around Time=4.2f",atat); getch(); } OUTPUT: ROUND ROBIN SCHEDULING

15

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in Enter the number of Processors 4 Enter the Timeslice 5 Enter the process ID 1 5 Enter the Burst Time for the process 10 Enter the process ID 2 6 Enter the Burst Time for the process 15 Enter the process ID 3 7 Enter the Burst Time for the process 20 Enter the process ID 4 8 Enter the Burst Time for the process 25 ROUND ROBIN SCHEDULING ALGORITHM Process

Process ID

BurstTime

Waiting Time

TurnaroundTime

1

5

10

15

25

2

6

15

25

40

3

7

20

25

45

4

8

25

20

45

The average Waiting Time=4.2f The average Turn around Time=4.2f

Ex. No: 3(b) SJF SCHEDULING Aim: Write a C program to implement the various process scheduling mechanisms such as SJF Scheduling . Algorithm for SJF Step 1: Start the process Step 2: Accept the number of processes in the ready Queue Step 3: For each process in the ready Q, assign the process id and accept the U burst time Step 4: Start the Ready Q according the shortest Burst time by sorting according to lowest to

16

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in highest burst time. Step 5: Set the waiting time of the first process as „0‟ and its turnaround time as its burst time. Step 6: For each process in the ready queue, calculate (a) Waiting time for process(n)= waiting time of process (n-1) + Burst time of process(n-1) (b) Turn around time for Process(n)= waiting time of Process(n)+ Burst time for process(n) Step 6: Calculate (c) Average waiting time = Total waiting Time / Number of process (d) Average Turnaround time = Total Turnaround Time / Number of process Step 7: Stop the process /* SJF SCHEDULING ALGORITHM */ #include<stdio.h> void main() { int i,j,k,n,sum,wt[10],tt[10],twt,ttat; int t[10],p[10]; float awt,atat; clrscr(); printf("Enter number of process\n"); scanf("%d",&n); for(i=0;i t[k]) { int temp; temp=t[i]; t[i]=t[k]; t[k]=temp; temp=p[i]; p[i]=p[k]; p[k]=temp; } } printf("\n\n SHORTEST JOB FIRST SCHEDULING ALGORITHM");

17

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in printf("\n PROCESS ID \t BURST TIME \t WAITING TIME \t TURNAROUND TIME \n\n"); wt[0]=0; for(i=0;i
3

0

3

0

4

3

7

2

5

7

12

18

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

AVERAGE WAITING TIME 3.33 AVERAGE TURN AROUND TIME 7.33 Ex. No: 3(c) FCFS SCHEDULING Aim: Write a C program to implement the various process scheduling mechanisms such as FCFS scheduling Algorithm for FCFS scheduling: Step 1: Start the process Step 2: Accept the number of processes in the ready Queue Step 3: For each process in the ready Q, assign the process id and accept the U burst time Step 4: Set the waiting of the first process as „0‟ and its burst time as its turn around time Step 5: for each process in the Ready Q calculate (c) Waiting time for process(n)= waiting time of process (n-1) + Burst time of process(n-1) (d) Turn around time for Process(n)= waiting time of Process(n)+ Burst time for process(n) Step 6: Calculate (e) Average waiting time = Total waiting Time / Number of process (f) Average Turnaround time = Total Turnaround Time / Number of process Step 7: Stop the process /* FCFS SCHEDULING ALGORITHM */ #include<stdio.h> void main() { int i,n,sum,wt,tat,twt,ttat; int t[10]; float awt,atat; clrscr(); printf("Enter number of processors:\n"); scanf("%d",&n); for(i=0;i
19

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in twt=twt+wt; ttat=ttat+tat; printf("\n %d \t\t %d \t\t %d",i+1,wt,tat); printf("\n\n"); } awt=(float)twt/n; atat=(float)ttat/n; printf("\n Average Waiting Time %4.2f",awt); printf("\n Average Turnaround Time %4.2f",atat); getch(); } OUTPUT: Enter number of processors: 3 Enter the Burst Time of the process 1: 2 Enter the Burst Time of the process 2: 5 Enter the Burst Time of the process 3: 4 FIRST COME FIRST SERVE SCHEDULING ALGORITHM Process ID Waiting Time Turn Around Time 1 0 2 2

2

7

3

7

11

Average Waiting Time 3.00 Average Turnaround Time 6.67 Ex. No: 3d PRIORITY SCHEDULING Aim: Write a C program to implement the various process scheduling mechanisms such as Priority Scheduling. Algorithm for Priority Scheduling: Step 1: Start the process Step 2: Accept the number of processes in the ready Queue Step 3: For each process in the ready Q, assign the process id and accept the U burst time Step 4: Sort the ready queue according to the priority number. Step 5: Set the waiting of the first process as „0‟ and its burst time as its turn around time Step 6: For each process in the Ready Q calculate Waiting time for process(n)= waiting time of process (n-1) + Burst time of process(n-1) Turn around time for Process(n)= waiting time of Process(n)+ Burst time for process(n) Calculate Average waiting time = Total waiting Time / Number of process Average Turnaround time = Total Turnaround Time / Number of process Step 7: Stop the process Program: /* PRIORITY SCHEDULING */ #include <stdio.h>

20

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in #include void main() { int i,j,n,tat[10],wt[10],bt[10],pid[10],pr[10],t,twt=0,ttat=0; float awt,atat; clrscr(); printf("\n-----------PRIORITY SCHEDULING--------------\n"); printf("Enter the No of Process: "); scanf("%d", &n); for (i=0;i pr[j] ) { t = pr[i]; pr[i] = pr[j]; pr[j] = t; t = bt[i]; bt[i] = bt[j]; bt[j] = t; t = pid[i]; pid[i] = pid[j]; pid[j] = t; } } // Sorting finished tat[0] = bt[0]; wt[0] = 0; for (i=1;i
21

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in { printf("\n%d\t\t%d\t%d\t\t%d\t\t%d",pid[i],pr[i],bt[i],wt[i],tat[i]); } for(i=0;i
-----------PRIORITY SCHEDULING-------------Enter the No of Process: 4 Enter the Burst time of Pid 0 : 2 Enter the Priority of Pid 0 : 3 Enter the Burst time of Pid 1 : 6 Enter the Priority of Pid 1 : 2 Enter the Burst time of Pid 2 : 4 Enter the Priority of Pid 2 : 1 Enter the Burst time of Pid 3 : 5 Enter the Priority of Pid 3 : 7 ---------------------------------------------------------------------------------------Pid Priority Burst time WaitingTime TurnArroundTime ---------------------------------------------------------------------------------------2 1 0 3

1 2 3 7

4 6 2 5

0 4 10 12

4 10 12 17

Avg.Waiting Time: 6.500000 Avg.Turn Around Time: 10.750000 Result : Thus the program to perform various U Scheduling algorithms are executed and output is verified successfully.

Exp no: 4(a)

SEQUENTIAL FILE ALLOCATION

AIM: Write a C Program to implement Sequential File Allocation method. ALGORITHM: Step 1: Start the program. 22

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

Step 2: Get the number of memory partition and their sizes. Step 3: Get the number of processes and values of block size for each process. Step 4: First fit algorithm searches the entire entire memory block until a hole which is big enough is encountered. It allocates that memory block for the requesting process. Step 5: Best-fit algorithm searches the memory blocks for the smallest hole which can be allocated to requesting process and allocates if. Step 6: Worst fit algorithm searches the memory blocks for the largest hole and allocates it to the process. Step 7: Analyses all the three memory management techniques and display the best algorithm which utilizes the memory resources effectively and efficiently. Step 8: Stop the program.

PROGRAM: #include<stdio.h> #include main() { int n,i,j,b[20],sb[20],t[20],x,c[20][20]; clrscr(); printf("Enter no.of files:"); scanf("%d",&n); for(i=0;i
cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

Enter no. of blocks occupied by file2 10 Enter the starting block of file2 5 Filename Start block length 1 2 4 2 5 10 Enter file name: rajesh File name is:12803 length is:0blocks occupied Exp no: 4(b)

INDEXED FILE ALLOCATION

AIM: Write a C Program to implement Indexed File Allocation method. Algorithm: Step 1: Start. Step 2: Let n be the size of the buffer Step 3: check if there are any producer Step 4: if yes check whether the buffer is full Step 5: If no the producer item is stored in the buffer Step 6: If the buffer is full the producer has to wait Step 7: Check there is any cosumer.If yes check whether the buffer is empty Step 8: If no the consumer consumes them from the buffer Step 9: If the buffer is empty, the consumer has to wait. Step 10: Repeat checking for the producer and consumer till required Step 11: Terminate the process. PROGRAM: #include<stdio.h> #include main() { int n,m[20],i,j,sb[20],s[20],b[20][20],x; clrscr(); printf("Enter no. of files:"); scanf("%d",&n); for(i=0;i
24

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in 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]); getch(); } OUTPUT: Enter no. of files:2 Enter starting block and size of file1: 2 5 Enter blocks occupied by file1:10 enter blocks of file1:3 2 5 4 6 7 2 6 4 7 Enter starting block and size of file2: 3 4 Enter blocks occupied by file2:5 enter blocks of file2: 2 3 4 5 6 File index length 1 2 10 2 3 5

Enter file name: venkat file name is:12803 Index is:0Block occupied are: Exp no:4(c)

LINKED FILE ALLOCATION

AIM: Write a C Program to implement Linked File Allocation method. ALGORITHM: Step 1: Create a queue to hold all pages in memory Step 2: When the page is required replace the page at the head of the queue Step 3: Now the new page is inserted at the tail of the queue Step 4: Create a stack Step 5: When the page fault occurs replace page present at the bottom of the stack Step 6: Stop the allocation. PROGRAM: #include<stdio.h> #include struct file { char fname[10]; int start,size,block[10]; }f[10]; main() { int i,j,n;

25

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

clrscr(); printf("Enter no. of files:"); scanf("%d",&n); for(i=0;i ",f[i].block[j]); printf("%d",f[i].block[j]); printf("\n"); } getch(); } OUTPUT: Enter no. of files:2 Enter file name:venkat Enter starting block:20 Enter no.of blocks:6 Enter block numbers: 4 12 15 45 32 25 Enter file name:rajesh Enter starting block:12 Enter no.of blocks:5 Enter block numbers:6 5

26

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

4 3 2 File start size venkat 20 6 rajesh 12 5

block 4--->12--->15--->45--->32--->25 6--->5--->4--->3--->2

Result: Thus the program for various Memory Allocation Techniques has been implemented successfully.

Ex. No. 5

Semaphores

AIM: To implement producer/consumer problem using semaphore. Algorithm: 1 Declare variable for producer & consumer as pthread-t-tid produce tid consume. 2 Declare a structure to add items, semaphore variable set as struct. 3 Read number of items to be produced and consumed. 4 Declare and define semaphore function for creation and destroy. 5 Define producer function. 6 Define consumer function. 7 Call producer and consumer. 8 Stop the execution. Program #include<stdio.h> #include<semaphore.h> #include #define NBUFF 10 int nitems; struct { int buff[NBUFF]; sem_t mutex,nempty,nstored; }shared; void *produce(void*); void *consume(void*); int main(int argc,char**argv) { pthread_t tid_produce,tid_consume; if(argc!=2) { printf("usage:filename "); return 0; } printf("\n\nproducer_consumer problem using semaphore \n"); printf(".......................................................................................\n"); nitems=atoi(argv[1]); sem_init(&shared.mutex,0,1); sem_init(&shared.nempty,0,NBUFF); sem_init(&shared.nstored,0,0); pthread_setconcurrency(2);

27

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in pthread_create(&tid_produce,NULL,produce,NULL); pthread_create(&tid_consume,NULL,consume,NULL); pthread_(tid_produce,NULL); pthread_(tid_consume,NULL); sem_destroy(&shared.mutex); sem_destroy(&shared.nempty); sem_destroy(&shared.nstored); } void *produce(void *arg) { int i; for(i=0;i
Ex. No.6 (a) FILE ORGANIZATION TECHNIQUE – Single- Level Directory Aim: To implement File Organization Techniques like Single level Directory.

28

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

Algorithm: 1. Initialize values gd =DETECT,gm,count,I,j,mid,cir_x,fname[10][20]; 2..Read number of files in count. 3. Read file name in the loop. 4. calculate the mid value 5. Insert the file in the root directory. 6. Continue the step 5 until count =0 7.Stop the execution.

Program: #include<stdio.h> #include #include<stdlib.h> #include 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
29

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in ROOT

1 .

Enter file 2 name:2.c

ROOT

1 .

2 .

Enter file 3 name:3.c ROOT

3 1 2 . . . Result: Thus the program to implement File Organization Technique - Single level directory was executed and verified successfully

Ex. No.6 (b) FILE ORGANIZATION TECHNIQUE – Two Level Directory Aim: To implement File Organization Technique - Two level directory

Algorithm: 1. Initialize values gd =DETECT,gm,count,I,j,mid,cir_x,fname[10][20]; 2..Read number of files in count. 3. Read file name in the loop. 4. calculate the mid value 5. Insert the file in the root directory. 6. Continue the step 5 until count =0 7.Stop the execution.

Program: #include<stdio.h> main() { int nod,file[30][30],nof[10],i,j; printf("\nEnter the numner of directory under root:\t"); scanf("%d",&nod); for(i=0;i<nod;i++) { printf("Enter directory-%d name:\t",i+1); scanf("%d",&file[i][0]); printf("Enter number of files in the direcotyr:%d",i+1); scanf("%d",&nof[i]); for(j=1;j<nof;j++)

30

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in { printf("Enter the file-%d name:\t",j); scanf("%d",&file[i][j]); } } printf("Two level file organization"); printf("ROOT"); for(i=0;i<nod;i++) printf("\t\t%d\n",file[i][0]); printf("\n"); for(i=0;ii<nod;i++) for(j=1;j<=nof[i];j++) printf("\t%d",file[i][j]); }

Result:

Thus the program to implement File Organization Technique - Two level directory was executed and verified successfully

Ex. No.6 (c) FILE ORGANIZATION TECHNIQUE –Hierarchical Directory Aim: To implement various File Organization Technique – Hierarchical directory

Algorithm: 1. 2. 3. 4. 5. 6.

Read number of files in count. Read file name in the loop. calculate the mid value Insert the file in the root directory. Continue the step 5 until count =0 Stop the execution.

Program: #include<stdio.h> main() { int n,nod,dir[20],nof,file[20],i,m,f; a: printf("If the current directory has subdir, Press !"); scanf("%d",&n); if(n==1) { printf("Enter the number of directory"); scanf("%d",&nod); for(i=0;i<nod;i++) { printf("Enter the directory-%d name:\t",i+1); scanf("%d",&dir[i]); } } printf("If the current directory has subdir, Press 2"); scanf("%d",&f); if(f==2) 31

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in { printf("Enter the number of files:"); scanf("%d",&nof); for(i=0;i<nof;i++) { printf("Enter file-%d name",i+1); scanf("%d",&file[i]); } } for(i=0;i<nod;i++) printf("\t%d",dir[i]); for(i=0;i<nof;i++) printf("\t%d",file[i]); printf("Do you want to enter next level? Y-1/N-2"); scanf("%d",&m); if(m==1) goto a; }

Result: Thus the program to implement File Organization Technique - Hierarchical directory was executed and verified successfully

Ex. No: 7

BANKER’S ALGORITHM

AIM: To implement deadlock avoidance & Prevention by using Banker‟s Algorithm. Deadlock avoidance & Dead Lock Prevention 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 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 allocation; 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 32

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

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  Finish[i] =False  Need<=Work If no such I exists go to step 4. 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 step 2. Otherwise raise an error condition. 2. if Request<=Available go to step 3. 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; 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. ALGORITHM: 1. Start the program. 2. Get the values of resources and processes. 3. Get the avail value. 4. After allocation find the need value. 5. Check whether its possible to allocate. 6. If it is possible then the system is in safe state. 7. Else system is not in safety state. 8. If the new request comes then check that the system is in safety. 9. or not if we allow the request. 10. stop the program.

/* BANKER‟S ALGORITHM */ Program: #include<stdio.h> #include struct da { int max[10],a1[10],need[10],before[10],after[10]; }p[10]; void main() { int i,j,k,l,r,n,tot[10],av[10],cn=0,cz=0,temp=0,c=0; clrscr();

33

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in printf("\n ENTER THE NO. OF PROCESSES:"); scanf("%d",&n); printf("\n ENTER THE NO. OF RESOURCES:"); scanf("%d",&r); for(i=0;i
34

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in for(j=0;j av[j]) cn++; if(p[i].max[j]==0) cz++; } if(cn==0 && cz!=r) { for(j=0;j
35

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

OUTPUT: //TEST CASE 1: ENTER THE NO. OF PROCESSES:4 ENTER THE NO. OF RESOURCES:3 PROCESS 1 MAXIMUM VALUE FOR RESOURCE 1:3 MAXIMUM VALUE FOR RESOURCE 2:2 MAXIMUM VALUE FOR RESOURCE 3:2 ALLOCATED FROM RESOURCE 1:1 ALLOCATED FROM RESOURCE 2:0 ALLOCATED FROM RESOURCE 3:0 PROCESS 2 MAXIMUM VALUE FOR RESOURCE 1:6 MAXIMUM VALUE FOR RESOURCE 2:1 MAXIMUM VALUE FOR RESOURCE 3:3 ALLOCATED FROM RESOURCE 1:5 ALLOCATED FROM RESOURCE 2:1 ALLOCATED FROM RESOURCE 3:1 PROCESS 3 MAXIMUM VALUE FOR RESOURCE 1:3 MAXIMUM VALUE FOR RESOURCE 2:1 MAXIMUM VALUE FOR RESOURCE 3:4 ALLOCATED FROM RESOURCE 1:2 ALLOCATED FROM RESOURCE 2:1 ALLOCATED FROM RESOURCE 3:1 PROCESS 4 MAXIMUM VALUE FOR RESOURCE 1:4 MAXIMUM VALUE FOR RESOURCE 2:2 MAXIMUM VALUE FOR RESOURCE 3:2 ALLOCATED FROM RESOURCE 1:0 ALLOCATED FROM RESOURCE 2:0 ALLOCATED FROM RESOURCE 3:2 ENTER TOTAL VALUE OF RESOURCE 1:9 ENTER TOTAL VALUE OF RESOURCE 2:3 ENTER TOTAL VALUE OF RESOURCE 3:6 RESOURCES ALLOCATED NEEDED P1 322 100 222 P2 613 511 102 P3 314 211 103 P4 422 002 420

P2 P1 P3

TOTAL AVAIL 936 112

AVAIL BEFORE AVAIL AFTER 010 623 401 723 620 934

36

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in P4 514 936 THE ABOVE SEQUENCE IS A SAFE SEQUENCE //TEST CASE:2 ENTER THE NO. OF PROCESSES:4 ENTER THE NO. OF RESOURCES:3 PROCESS 1 MAXIMUM VALUE FOR RESOURCE 1:3 MAXIMUM VALUE FOR RESOURCE 2:2 MAXIMUM VALUE FOR RESOURCE 3:2 ALLOCATED FROM RESOURCE 1:1 ALLOCATED FROM RESOURCE 2:0 ALLOCATED FROM RESOURCE 3:1 PROCESS 2 MAXIMUM VALUE FOR RESOURCE 1:6 MAXIMUM VALUE FOR RESOURCE 2:1 MAXIMUM VALUE FOR RESOURCE 3:3 ALLOCATED FROM RESOURCE 1:5 ALLOCATED FROM RESOURCE 2:1 ALLOCATED FROM RESOURCE 3:1 PROCESS 3 MAXIMUM VALUE FOR RESOURCE 1:3 MAXIMUM VALUE FOR RESOURCE 2:1 MAXIMUM VALUE FOR RESOURCE 3:4 ALLOCATED FROM RESOURCE 1:2 ALLOCATED FROM RESOURCE 2:1 ALLOCATED FROM RESOURCE 3:2 PROCESS 4 MAXIMUM VALUE FOR RESOURCE 1:4 MAXIMUM VALUE FOR RESOURCE 2:2 MAXIMUM VALUE FOR RESOURCE 3:2 ALLOCATED FROM RESOURCE 1:0 ALLOCATED FROM RESOURCE 2:0 ALLOCATED FROM RESOURCE 3:2 ENTER TOTAL VALUE OF RESOURCE 1:9 ENTER TOTAL VALUE OF RESOURCE 2:3 ENTER TOTAL VALUE OF RESOURCE 3:6 RESOURCES ALLOCATED NEEDED TOTAL AVAIL P1 322 101 221 936 110 P2 613 511 102 P3 314 212 102 P4 422 002 420 AVAIL BEFORE AVAIL AFTER DEADLOCK OCCURED

Ex.No.: 8

Dead Lock Detection 37

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

AIM: To Implement DeadLock Detection Algorithm using C ALGORITHM: 1. Start the program. 2. Get the values of resources and processes. 3. Get the avail value. 4. After allocation find the need value. 5. Check whether its possible to allocate. 6. If it is possible then the system is in safe state. 7. Else system is not in safety state. 8. If the new request comes then check that the system is in safety. 9. or not if we allow the request. 10. stop the program.

Program: #include<stdio.h> #include<conio.h> void main() { int found,flag,l,p[4][5],tp,c[4][5],i,j,k=1,m[5],r[5],a[5],temp[5],sum=0; clrscr(); printf("enter total no of processes"); scanf("%d",&tp); printf("enter clain matrix"); for(i=1;i<=4;i++) for(j=1;j<=5;j++) { scanf("%d",&c[i][j]); } printf("enter allocation matrix"); for(i=1;i<=4;i++) for(j=1;j<=5;j++) { scanf("%d",&p[i][j]); } printf("enter resource vector:\n"); for(i=1;i<=5;i++) { scanf("%d",&r[i]); } printf("enter availability vector:\n"); for(i=1;i<=5;i++) { scanf("%d",&a[i]); temp[i]=a[i]; } for(i=1;i<=4;i++) {

38

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in sum=0; for(j=1;j<=5;j++) { sum+=p[i][j]; } if(sum==0) { m[k]=i; k++; } } for(i=1;i<=4;i++) { for(l=1;l<k;l++) if(i!=m[l]) { flag=1; for(j=1;j<=5;j++) if(c[i][j]>temp[j]) { flag=0; break; } } if(flag==1) { m[k]=i; k++; for(j=1;j<=5;j++) temp[j]+=p[i][j]; } } printf("deadlock causing processes are:"); for(j=1;j<=tp;j++) { found=0; for(i=1;i<k;i++) { if(j==m[i]) found=1; } if(found==0) printf("%d\t",j); } getch(); } INPUT: enter total no. of processes : 4 enter claim matrix :

39

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in 01001 00101 00001 10101 enter allocation matrix : 10110 11000 00010 00000 enter resource vector : 21121 enter the availability vector : 00001

OUTPUT : deadlock causing processes are : 1 2

Ex. No: 9 a) FIFO PAGE REPLACEMENT ALGORITHM AIM: To implement page replacement algorithms FIFO (First In First Out) ALGORITHM: Step 1: Create a queue to hold all pages in memory Step 2: When the page is required replace the page at the head of the queue Step 3: Now the new page is inserted at the tail of the queue /* FIFO Page Replacement Algorithm */

Program: #include<stdio.h> #include int i,j,nof,nor,flag=0,ref[50],frm[50],pf=0,victim=-1; void main() { clrscr(); printf("\n \t\t\t FIFI PAGE REPLACEMENT ALGORITHM"); printf("\n Enter no.of frames...."); scanf("%d",&nof); printf("Enter number of reference string..\n"); scanf("%d",&nor); printf("\n Enter the reference string.."); for(i=0;i<nor;i++) scanf("%d",&ref[i]); printf("\nThe given reference string:"); for(i=0;i<nor;i++) printf("%4d",ref[i]); for(i=1;i<=nof;i++) frm[i]=-1; printf("\n");

40

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in for(i=0;i<nor;i++) { flag=0; printf("\n\t Reference np%d->\t",ref[i]); for(j=0;j<nof;j++) { if(frm[j]==ref[i]) { flag=1; break; }} if(flag==0) { pf++; victim++; victim=victim%nof; frm[victim]=ref[i]; for(j=0;j<nof;j++) printf("%4d",frm[j]); } } printf("\n\n\t\t No.of pages faults...%d",pf); getch(); } OUTPUT: FIFO PAGE REPLACEMENT ALGORITHM Enter no.of frames....4 Enter number of reference string.. 6 Enter the reference string.. 564123 The given reference string: ...................................... 5 6 4 1 2 3 Reference np5-> Reference np6-> Reference np4-> Reference np1-> Reference np2-> Reference np3->

5 5 5 5 2 2

-1 6 6 6 6 3

-1 -1 4 4 4 4

-1 -1 -1 1 1 1

No.of pages faults...6

Ex. No:9(b)

LRU PAGE REPLACEMENT ALGORITHM

41

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in AIM: To implement page replacement algorithm LRU (Least Recently Used) LRU (Lease Recently Used) Here we select the page that has not been used for the longest period of time. ALGORITHM: Step 1: Create a queue to hold all pages in memory Step 2: When the page is required replace the page at the head of the queue Step 3: Now the new page is inserted at the tail of the queue Step 4: Create a stack Step 5: When the page fault occurs replace page present at the bottom of the stack /* LRU Page Replacement Algorithm */

Program: #include<stdio.h> #include int i,j,nof,nor,flag=0,ref[50],frm[50],pf=0,victim=-1; int recent[10],lrucal[50],count=0; int lruvictim(); void main() { clrscr(); printf("\n\t\t\t LRU PAGE REPLACEMENT ALGORITHM"); printf("\n Enter no.of Frames...."); scanf("%d",&nof); printf(" Enter no.of reference string.."); scanf("%d",&nor); printf("\n Enter reference string.."); for(i=0;i<nor;i++) scanf("%d",&ref[i]); printf("\n\n\t\t LRU PAGE REPLACEMENT ALGORITHM "); printf("\n\t The given reference string:"); printf("\n……………………………….."); for(i=0;i<nor;i++) printf("%4d",ref[i]); for(i=1;i<=nof;i++) { frm[i]=-1; lrucal[i]=0; } for(i=0;i<10;i++) recent[i]=0; printf("\n"); for(i=0;i<nor;i++) { 42

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in flag=0; printf("\n\t Reference NO %d->\t",ref[i]); for(j=0;j<nof;j++) { if(frm[j]==ref[i]) { flag=1; break; } } if(flag==0) { count++; if(count<=nof) victim++; else victim=lruvictim(); pf++; frm[victim]=ref[i]; for(j=0;j<nof;j++) printf("%4d",frm[j]); } recent[ref[i]]=i; } printf("\n\n\t No.of page faults...%d",pf); getch(); } int lruvictim() { int i,j,temp1,temp2; for(i=0;i<nof;i++) { temp1=frm[i]; lrucal[i]=recent[temp1]; } temp2=lrucal[0]; for(j=1;j<nof;j++) { if(temp2>lrucal[j]) temp2=lrucal[j]; } for(i=0;i<nof;i++) if(ref[temp2]==frm[i]) return i; return 0; } OUTPUT LRU PAGE REPLACEMENT ALGORITHM

43

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in Enter no.of Frames....3 Enter no.of reference string..6 Enter reference string.. 654231 LRU PAGE REPLACEMENT ALGORITHM The given reference string: …………………. 6 5 4 2 3 1 Reference NO 6-> Reference NO 5-> Reference NO 4-> Reference NO 2-> Reference NO 3-> Reference NO 1->

6 6 6 2 2 2

-1 5 5 5 3 3

-1 -1 4 4 4 1

No.of page faults...6 Ex. No: 9(c) OPTIMAL(LFU) PAGE REPLACEMENT ALGORITHM AIM: To implement page replacement algorithms Optimal (The page which is not used for longest time) ALGORITHM: Optimal algorithm Here we select the page that will not be used for the longest period of time. OPTIMAL: Step 1: Create a array Step 2: When the page fault occurs replace page that will not be used for the longest period of time /*OPTIMAL(LFU) page replacement algorithm*/

Program #include<stdio.h> #include int i,j,nof,nor,flag=0,ref[50],frm[50],pf=0,victim=-1; int recent[10],optcal[50],count=0; int optvictim(); void main() { clrscr(); printf("\n OPTIMAL PAGE REPLACEMENT ALGORITHN"); printf("\n................................."); printf("\nEnter the no.of frames"); scanf("%d",&nof); printf("Enter the no.of reference string"); scanf("%d",&nor); printf("Enter the reference string"); for(i=0;i<nor;i++) 44

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in scanf("%d",&ref[i]); clrscr(); printf("\n OPTIMAL PAGE REPLACEMENT ALGORITHM"); printf("\n................................"); printf("\nThe given string"); printf("\n....................\n"); for(i=0;i<nor;i++) printf("%4d",ref[i]); for(i=0;i<nof;i++) { frm[i]=-1; optcal[i]=0; } for(i=0;i<10;i++) recent[i]=0; printf("\n"); for(i=0;i<nor;i++) { flag=0; printf("\n\tref no %d ->\t",ref[i]); for(j=0;j<nof;j++) { if(frm[j]==ref[i]) { flag=1; break; } } if(flag==0) { count++; if(count<=nof) victim++; else victim=optvictim(i); pf++; frm[victim]=ref[i]; for(j=0;j<nof;j++) printf("%4d",frm[j]); } } printf("\n Number of page faults: %d",pf); getch(); } int optvictim(int index) { int i,j,temp,notfound; for(i=0;i<nof;i++) { notfound=1;

45

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in for(j=index;j<nor;j++) if(frm[i]==ref[j]) { notfound=0; optcal[i]=j; break; } if(notfound==1) return i; } temp=optcal[0]; for(i=1;i<nof;i++) if(temp
OUTPUT: OPTIMAL PAGE REPLACEMENT ALGORITHM Enter no.of Frames....3 Enter no.of reference string..6 Enter reference string.. 654231 OPTIMAL PAGE REPLACEMENT ALGORITHM The given reference string: …………………. 6 5 4 2 3 1 Reference NO 6-> Reference NO 5-> Reference NO 4-> Reference NO 2-> Reference NO 3-> Reference NO 1->

6 6 6 2 2 2

-1 5 5 5 3 3

-1 -1 4 4 4 1

No.of page faults...6

Ex. No: 10 DEVELOPING APPLICATION USING INTER PROCESS COMMUNICATION -Pipes and Shared memory Aim: To write a C program to implement inter process communication using pipes and shared memory.

46

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

IPC using Shared Memory Algorithm: 1. 2. 3. 4. 5. 6.

Call the fork () system call. If (!child) then input the shared memory address and create the IPC using shmget (). Then the parent is writing on to the address. Else then input the address using shmget() Assign the shared memory id. Then the child is reading the same content.

IPC - Pipe Conceptually a pipe can be thought of much like a hose-pipe, in that it is a conduit where we pour data in at one end and it flows out at the other. A pipe looks a lot like a file in that it is treated as a sequential data stream. Unlike a file, a pipe has two ends, so when we create a pipe we get two end points back in return. We can write to one end point and read from the other. Also unlike a file, there is no physical storage of data when we close a pipe, anything that was written in one end but not read out from the other end will be lost. We can illustrate the use of pipes as conduits between processes in the following diagram:

Here we see two processes which I've called Parent and Child, for reasons that will become apparent shortly. The Parent can write to Pipe A. and read from Pipe B. The Child can read from Pipe A and write to Pipe B. Algorithm: 1 Start the program. 2 Declare the file pointer fp, f1, f2. 3 Read the choice. 4 In case „1‟ open a file and display the list of files and directories. 5 In case „2‟ open a file and ptr bin\pwd for read mode it displays the personnel working directory. 6 In case „3‟ open a file in write mode. 7 In case „4‟ Exit command is execute. 8 Stop the program.

Program #include<stdio.h> main(int argc,char * argv[]) { int p1[2],p2[2],p3[2],p4[2]; int pid1,pid2,pid3,pid4; 47

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in int wc,cc,sc,lc,j,ch_id,status,count; char c; FILE *fp; wc=sc=cc=lc=0; pipe(p1); pipe(p2); pipe(p3); pipe(p4); pid1=fork(); if(pid1==0) { fp=fopen(argv[1],"r"); while((c=getc(fp))!=EOF) cc++; write(p1[1],&cc,sizeof(int)); fclose(fp); exit(0); } pid2=fork(); f(pid2==0) { fp=fopen(argv[1],"r"); while((c=getc(fp))!=EOF) if(c=='\n') lc++; write(p2[1],&lc,sizeof(int)); fclose(fp); exit(0); } pid3=fork(); if(pid3==0) { fp=fopen(argv[1],"r"); while((c=getc(fp))!=EOF) if(c=='.') sc++; write(p3[1],&sc,sizeof(int)); fclose(fp); exit(0); } pid4=fork(); if(pid4==0) { fp=fopen(argv[1],"r"); while((c=getc(fp))!=EOF) { if(c==' '|c=='\n') wc++;

48

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in } write(p4[1],&wc,sizeof(int)); fclose(fp); exit(0); } j=0; while(j<4) { ch_id=wait(&status); if(ch_id==pid1) { read(p1[0],&count,sizeof(int)); printf("\n\n CHARACTER COUNT:%d",count); } if(ch_id==pid2) { read(p2[0],&count,sizeof(int)); printf("\n\n LINE COUNT:%d",count); } if(ch_id==pid3) { read(p3[0],&count,sizeof(int)); printf("\n\n SENTENCE COUNT:%d",count); } if(ch_id==pid4) { read(p4[0],&count,sizeof(int)); printf("\n\nWORD COUNT:%d",count); } j++; } } Output:

CHARACTER COUNT: 60 LINE COUNT: 6 SENTENCE COUNT: 8 WORD COUNT: 20 Result: Thus the Inter process communication has been implemented successfully using shared memory and pipes.

49

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

Ex. No: 11

PAGING

Aim: To implement the Memory management policy- Paging. Algorithm: Step 1: Read all the necessary input from the keyboard. Step 2: Pages - Logical memory is broken into fixed - sized blocks. Step 3: Frames – Physical memory is broken into fixed – sized blocks. Step 4: Calculate the physical address using the following Physical address = ( Frame number * Frame size ) + offset Step 5: Display the physical address. Step 6: Stop the process.

/* Memory Allocation with Paging Technique */ Program: #include <stdio.h> #include struct pstruct { int fno; int pbit; }ptable[10]; int pmsize,lmsize,psize,frame,page,ftable[20],frameno; void info() { printf("\n\nMEMORY MANAGEMENT USING PAGING\n\n"); printf("\n\nEnter the Size of Physical memory: "); scanf("%d",&pmsize); printf("\n\nEnter the size of Logical memory: "); scanf("%d",&lmsize); printf("\n\nEnter the partition size: "); scanf("%d",&psize); frame = (int) pmsize/psize; page = (int) lmsize/psize; printf("\nThe physical memory is divided into %d no.of frames\n",frame); printf("\nThe Logical memory is divided into %d no.of pages",page); } void assign() { int i; for (i=0;i<page;i++) { ptable[i].fno = -1; ptable[i].pbit= -1; }

50

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in for(i=0; i
OUTPUT: 51

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

MEMORY MANAGEMENT USING PAGING Enter the Size of Physical memory: 16 Enter the size of Logical memory: 8 Enter the partition size: 2 The physical memory is divided into 8 no.of frames The Logical memory is divided into 4 no.of pages Enter the Frame number where page 0 must be placed: 5 Enter the Frame number where page 1 must be placed: 6 Enter the Frame number where page 2 must be placed: 7 Enter the Frame number where page 3 must be placed: 2 PAGE TABLE PageAddress 0 1 2 3 FRAME TABLE FrameAddress

FrameNo. 5 6 7 2

PresenceBit 1 1 1 1

PageNo

0 32555 1 32555 2 3 3 32555 4 32555 5 0 6 1 7 2 Process to create the Physical Address Enter the Base Address: 1000 Enter theLogical Address: 3 The Physical Address where the instruction present: 1013 Result: Thus the program for Paging has been implemented successfully

52

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

Ex.No.12 Implementation of Threading & Synchronization Applications Aim: Program: #include<stdio.h> #include<semaphore.h> #include #define N 5 #define THINKING 0 #define HUNGRY 1 #define EATING 2 #define LEFT (ph_num+4)%N #define RIGHT (ph_num+1)%N sem_t mutex; sem_t S[N]; void * philospher(void *num); void take_fork(int); void put_fork(int); void test(int); int state[N]; int phil_num[N]={0,1,2,3,4}; int main() { int i; pthread_t thread_id[N]; sem_init(&mutex,0,1); for(i=0;i
53

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in put_fork(*i); } } void take_fork(int ph_num) { sem_wait(&mutex); state[ph_num] = HUNGRY; printf("Philosopher %d is Hungry\n",ph_num+1); test(ph_num); sem_post(&mutex); sem_wait(&S[ph_num]); sleep(1); } void test(int ph_num) { if (state[ph_num] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) { state[ph_num] = EATING; sleep(2); printf("Philosopher %d takes fork %d and %d\n",ph_num+1,LEFT+1,ph_num+1); printf("Philosopher %d is Eating\n",ph_num+1); sem_post(&S[ph_num]); } } void put_fork(int ph_num) { sem_wait(&mutex); state[ph_num] = THINKING; printf("Philosopher %d putting fork %d and %d down\n",ph_num+1,LEFT+1,ph_num+1); printf("Philosopher %d is thinking\n",ph_num+1); test(LEFT); test(RIGHT); sem_post(&mutex); }

54

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in

CONTENT BEYOND SYLLABUS IMPLEMENTATION OF MEMORY MANAGEMENT TECHNIQUES-First fit, Best fit and Worst fit. MEMORY MANAGEMENT The purpose of the memory manager is o o o

to allocate primary memory space to processes to map the process address space into the allocated portion of the primary memory to minimize access times using a cost-effective amount of primary memory

Memory Management Algorithms In an environment that s dynamic memory allocation, the memory manager must keep a record of the usage of each allocatable block of memory. This record could be kept by using almost any data structure that implements linked lists. An obvious implementation is to define a free list of block descriptors, with each descriport containing a pointer to the next descriptor, a pointer to the block, and the length of the block. The memory manager keeps a free list pointer and inserts entries into the list in some order conducive to its allocation strategy. A number of strategies are used to allocate space to the processes that are competing for memory. o

Best Fit

The allocator places a process in the smallest block of unallocated memory in which it will fit. Problems:  

It requires an expensive search of the entire free list to find the best hole. More importantly, it leads to the creation of lots of little holes that are not big enough to satisfy any requests. This situation is called fragmentation, and is a problem for all memorymanagement strategies, although it is particularly bad for best-fit. Solution:One way to avoid making little holes is to give the client a bigger block than it asked for. For example, we might round all requests up to the next larger multiple of 64 bytes. That doesn't make the fragmentation go away, it just hides it. 

Unusable space in the form of holes is called external fragmentation



Unusable space in the form of holes is called external fragmentation

o

Worst Fit

55

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in The memory manager places process in the largest block of unallocated memory available. The ides is that this placement will create the largest hole after the allocations, thus increasing the possibility that, compared to best fit, another process can use the hole created as a result of external fragmentation. o

First Fit

Another strategy is first fit, which simply scans the free list until a large enough hole is found. Despite the name, first-fit is generally better than best-fit because it leads to less fragmentation. Aim To write a c program to implement memory management techniques (first fit, bestfit and worst fit). Algorithm 1. Enter the five free memories and five processes. 2. Enter the choice. 3. In first fit, allocate the process to free memory by sequential order if free memory size>=process size. 4. In best fit, allocate the process to free memory, if the memory size is first, equal to free memory then go for greater memory size. 5. In worst fit, allocate the process to free memory, if the memory size is greater then go for equal memory size. Sample Output: [cse98@cselinux ~]$ cc fit.c [cse98@cselinux ~]$ ./a.out Enter five freememory 25 45 65 20 10 Enter five processes 45 20 95 100 60 1.First fit 2.Best fit 3.Worst fit Enter your choice:1 First fit process 20 is allocated for free memory 25 process 45 is allocated for free memory 45 process 60 is allocated for free memory 65 process size 95 is not allocated for any memory process size 100 is not allocated for any memory[cse98@cselinux ~]$ [cse98@cselinux ~]$ cc fit.c [cse98@cselinux ~]$ ./a.out Enter five freememory 25 45 65 20 10 Enter five processes 45 20 95 100 60

56

cseitquestions.blogspot.in | cseitquestions.blogspot.in | cseitquestions.blogspot.in 1.First fit 2.Best fit 3.Worst fit Enter your choice:2 Best fit process 20 is allocated for free memory 20 process 45 is allocated for free memory 45 process 60 is allocated for free memory 65 process size 95 is not allocated for any memory [cse98@cselinux ~]$ cc fit.c [cse98@cselinux ~]$ ./a.out Enter five freememory 25 45 65 20 10 Enter five processes 45 20 95 100 60 1.First fit 2.Best fit 3.Worst fit Enter your choice:3 Worst fit process 45 is allocated for free memory 65 process 20 is allocated for free memory 45 process size 95 is not allocated for any memory process size 100 is not allocated for any memory process size 60 is not allocated for any memory[cse98@cselinux ~]$

Result: Thus the program for memory management technique (first fit, best fit and worst fit) has been implemented successfully.

57