//OPTIMAL PAGE REPLACEMENT ALGORITHM
#include <stdio.h>
#include <conio.h>
int main()
{
int n, rss, fa[20], rsa[50], ta[20]; //n-No_of_Frames
//rss->Reference_String_Size::fa->Frame_Array
//rsa->Reference_String_Array::ta->Temporary_Array
int i,j,k, d,pfc=0,npf, cp,ff=0;
//d-distance[How soon a page will be used again?]
//cp->Current_Position :: ff->Frames_Filled ::pfc->Page_Fault_Count
//npf:NO_Page_Faults [0-False, 1-True]
printf("Enter number of frames: ");
scanf("%d", &n);
printf("Enter number of pages in reference string: ");
scanf("%d", &rss);
printf("Enter Reference string:\n");
for(i=0; i<rss; i++)
scanf("%d",&rsa[i]);
for(i=0;i<n;i++)
{
fa[i]=-1;
ta[i]=999;
}
printf("\nCURRENT_PAGE\t\tPAGES_IN_FRAME\t\tPAGE_FAULT_OCCURED?\n");
for(i=0; i<rss; i++)
{
printf("\n\t%d\t\t",rsa[i]);
npf=0;
for(j=0;j<n;j++) //Checking for the page in FRAME ARRAY
{
if(fa[j]==rsa[i])
{
npf = 1;
printf("\t\t\t\tNO");
break;
}
}
if(npf==0) // if page fault occurs
{
pfc++;
if(ff<n)
{
fa[ff]=rsa[i];
ff++;
}
else
{
for(k=0;k<n;k++)
ta[k]=999;
for(k=0; k<n; k++) //finding how near a page is
{
d = 0; // d-> distance
for(j=i+1;j<rss;j++)
{
if(fa[k]==rsa[j])
{
ta[k]=d;
break;
}
else
d++;
}
}
cp=0;
for(j=1;j<n;j++)
{
if(ta[cp]<ta[j])
cp=j; //cp->current position
}
fa[cp] = rsa[i];
}
for(j=0;j<n;j++)
printf("%d\t",fa[j]);
printf("\tYES");
}
}
printf("\nTotal no of pagefaults: %d",pfc);
return 0;
} 
You can emulate US for a passion for acquiring new knowledge, and disseminate it to as many as you can. You have great potential. Work with dedication and get ready for the challenges of your career!!! Dedicated to- Our students, who are bringing glory to us and our Faculty.
Showing posts with label OS. Show all posts
Showing posts with label OS. Show all posts
Thursday, 7 April 2016
Optimal Page Replacement Algorithm
LRU Page Replacement Algorithm
//LRU PAGE REPLACEMENT ALGORITHM
#include <stdio.h>
#include <conio.h>
int main()
{
int n, rss, fa[20], rsa[50], ta[20]; //n-No_of_Frames
//rss->Reference_String_Size::fa->Frame_Array
//rsa->Reference_String_Array::ta->Temporary_Array
int i,j,k,pfc=0,npf, cp;
//cp->Current_Position ::pfc->Page_Fault_Count
//npf:NO_Page_Faults [0-False, 1-True]
printf("Enter number of frames: ");
scanf("%d", &n);
printf("Enter number of pages in reference string: ");
scanf("%d", &rss);
printf("Enter Reference string:\n");
for(i=0; i<rss; i++)
scanf("%d",&rsa[i]);
for(i=0;i<n;i++)
fa[i]=-1;
for(i=0;i<n;i++)
ta[i]=n-(i+1);
printf("\nCURRENT_PAGE\t\tPAGES_IN_FRAME\t\tPAGE_FAULT_OCCURED?\n");
for(i=0; i<rss; i++)
{
printf("\n\t%d\t\t",rsa[i]);
npf=0;
for(j=0;j<n;j++) //Checking for the page in FRAME ARRAY
{
if(fa[j]==rsa[i])
{
npf = 1;
for(k=0;k<n;k++)
ta[k]++;
ta[j]=0;
printf("\t\t\t\tNO");
break;
}
}
if(npf==0) // if page fault occurs
{
pfc++;
cp=0;
for(j=1;j<n;j++)
if(ta[cp]<ta[j])
cp=j; //cp->current position
fa[cp] = rsa[i];
for(k=0;k<n;k++)
ta[k]++;
ta[cp]=0;
for(j=0;j<n;j++)
printf("%d\t",fa[j]);
printf("\tYES");
}
}
printf("\nTotal no of pagefaults: %d",pfc);
return 0;
} FIFO Page Replacement Algorithm
//FIFO PAGE REPLACEMENT ALGORITHM
#include <stdio.h>
#include <conio.h>
int main()
{
int n, rss, fa[20], rsa[50]; //n-No_of_Frames
//rss->Reference_String_Size::fa->Frame_Array
//rsa->Reference_String_Array::ta->Temporary_Array
int i,j,k,pfc=0,npf, cp=0;
//cp->Current_Position :: ff->Frames_Filled ::pfc->Page_Fault_Count
//npf:NO_Page_Faults [0-False, 1-True]
printf("Enter number of frames: ");
scanf("%d", &n);
printf("Enter number of pages in reference string: ");
scanf("%d", &rss);
printf("Enter Reference string:\n");
for(i=0; i<rss; i++)
scanf("%d",&rsa[i]);
for(i=0;i<n;i++)
fa[i]=-1;
printf("\nCURRENT_PAGE\t\tPAGES_IN_FRAME\t\tPAGE_FAULT_OCCURED?\n");
for(i=0; i<rss; i++)
{
printf("\n\t%d\t\t",rsa[i]);
npf=0;
for(j=0;j<n;j++) //Checking for the page in FRAME ARRAY
{
if(fa[j]==rsa[i])
{
npf = 1;
printf("\t\t\t\tNO");
break;
}
}
if(npf==0) // if page fault occurs
{
pfc++;
fa[cp] = rsa[i];
cp=(cp+1)%n;
for(j=0;j<n;j++)
printf("%d\t",fa[j]);
printf("\tYES");
}
}
printf("\nTotal no of pagefaults: %d",pfc);
return 0;
} Priority Scheduling
//PROGRAM FOR PRIORITY CPU SCHEDULING ALGORITHM" WITH NO-PRE_EMPTION & ARRIVAL TIMES
#include<stdio.h>
#include<string.h>
int main(void)
{
//VARIABLE DECLARATION
char pn[20][20], c[20][20]; //PN-PROGRAM NAMES C-A TEMPORARY ARRAY
int n,i,j,at[20], bt[20], pt[20], wt[20],ct[20],tat[20];
//bt-BURST TIME ;pt-PRIORITY;wt-WAITING TIME; tat-TURN AROUND TIME
int temp1, temp2, temp3, count=0,twt=0;//,tat=0;
printf("Enter number of processes:");
scanf("%d", &n);
printf("Enter <ProcessName> <ArrivalTime> <BurstTime> <Priority> :\n");
//TAKING INPUT VALUES i.e., PROCESS-NAMES, ARRIVAL-TIMES AND BURST-TIMES
for(i=0; i<n; i++)
scanf("%s%d%d%d",&pn[i],&at[i],&bt[i],&pt[i]);
//SCHEDULING THE PROCESSES ACCORDING TO SJF
for(i=0 ; i<n; i++)
{
for(j=i+1; j<n; j++)
if (
//IF THERE IS NO PROCESS IN MAIN MEMORY,
//SORT PROCESSES ACCORDING TO ARRIVAL TIMES &
//IF WE GOT PROCESSES WITH SAME ARRIVAL TIME SORT THEM BY PRIORITY
( (i==0||count<1)&&(at[i]>at[j]||(at[i]==at[j]&&pt[i]>pt[j])) )
//IF WE GOT ONLY ONE PROCESS IN MAIN MEMORY AFTER COMPLETION OF THE CURRENT PROCESS
|| (count == 1 && ct[i-1]>=at[j])
//IF WE GOT MORE THAN ONE PROCESS IN MAIN MEMORY, SORT THEM BY PRIORITY
|| ((ct[i-1]>=at[j]&&pt[i]>pt[j]))// || (ct[i-1]<at[i]&&ct[i-1]>=at[j]))
)
//SWAPPING PROCESSES
{
temp1 = bt[i];
bt[i] = bt[j];
bt[j] = temp1;
temp2 = at[i];
at[i] = at[j];
at[j] = temp2;
temp3 = pt[i];
pt[i] = pt[j];
pt[j] = temp3;
strcpy(c[i],pn[i]);
strcpy(pn[i],pn[j]);
strcpy(pn[j],c[i]);
}
if(i==0 || count<1)
ct[i] = at[i] + bt[i];
else
ct[i] = ct[i-1] + bt[i];
wt[i] = ct[i] - (at[i] + bt[i]);
tat[i] = ct[i] - at[i];
count = 0 ;
for(j=i+1; j<n; j++)
if(ct[i]>=at[j])
count++;
}
//PRINTING THE VALUES AFTER ALL PREOCESSES COMPLETED
printf("S.N.\tPN\tAT\tBT\tPri\tCT\tWT\tTAT\n");
for(i=0; i<n; i++)
printf("%d\t%s\t%d\t%d\t%d\t%d\t%d\t%d\n",(i+1),pn[i],at[i],bt[i],pt[i],ct[i],wt[i],tat[i]);
} //END OF MAIN
/* EXAMPLE OUTPUT
Enter number of processes:4
Enter <ProcessName> <ArrivalTime> <BurstTime> <Priority> :
p1 3 2 4
p2 2 1 6
p3 10 2 3
p4 2 3 2
S.N. PN AT BT Pri CT WT TAT
1 p4 2 3 2 5 0 3
2 p1 3 2 4 7 2 4
3 p2 2 1 6 8 5 6
4 p3 10 2 3 12 0 2
*/ Round Robin CPU Scheduling Algorithm
//PROGRAM FOR ROUND ROBIN "CPU SCHEDULING ALGORITHM" WITH ARRIVAL TIMES
#include<stdio.h>
#include<string.h>
int main(void)
{
//VARIABLE DECLARATION
char pn[20][20], c[20][20]; //PN-PROGRAM NAMES
int n,i,j,k,l, tq, at[20], bt[20], rbt[20], wt[20],tt[20],ct[20]; //bt-BURST TIME ; wt-WAITING TIME; tat-TURN AROUND TIME
int temp1, temp2, temp3, count=0,twt=0, tn;//,tat=0;
printf("Enter <Number_of_Processes & Time_Quantum:\n");
scanf("%d%d", &n, &tq);
printf("Enter PN, AT, BT:\n");
//TAKING INPUT VALUES i.e., PROCESS-NAMES, ARRIVAL-TIMES, BURST-TIMES
for(i=0; i<n; i++)
scanf("%s%d%d",&pn[i],&at[i],&bt[i]);
for(i=0; i<n; i++)
rbt[i]=bt[i];
//SCHEDULING THE PROCESSES ACCORDING TO SJF
for(i=0;i<n;i++)
{
for(j=i+1; j<n;j++)
{
//SORTING BASED ON ARRIVAL TIMES
if(at[i]>at[j])
{
temp1 = bt[i];
bt[i] = bt[j];
bt[j] = temp1;
temp2 = at[i];
at[i] = at[j];
at[j] = temp2;
temp3 = rbt[i];
rbt[i] = rbt[j];
rbt[j] = temp3;
strcpy(c[i],pn[i]);
strcpy(pn[i],pn[j]);
strcpy(pn[j],c[i]);
}
} //END OF J FOR-LOOP
}//END OF I FOR-LOOP
tn = at[0];
label:
for(i=0; i<n; i++)
{
if(at[i]>tn) i--;
if(rbt[i]>0)
{
if(rbt[i]>tq)
{
tn += tq;
rbt[i] -= tq;
}
else
{
tn += rbt[i];
rbt[i] = 0;
ct[i] = tn;
count++;
}
}
}
if(count<n) goto label;
//CALCULATING WAITING TIME & TAT
for(i=0;i<n;i++)
{
wt[i] = ct[i]-at[i]-bt[i];
twt += wt[i];
}
//PRINTING THE VALUES AFTER ALL PREOCESSES COMPLETED
printf("S.N.\tPN\tAT\tBT\tCT\tWT\n");
for(i=0; i<n; i++)
printf("%d\t%s\t%d\t%d\t%d\t%d\n",(i+1),pn[i],at[i],bt[i],ct[i],wt[i]);
printf("Total waiting time:%d", twt);
} //END OF MAIN SJF CPU Scheduling Algorithm (Preemptive)
//PROGRAM FOR SHORTEST-JOB-FIRST(SJF) "CPU SCHEDULING ALGORITHM" WITH PRE_EMPTION
#include<stdio.h>
#include<conio.h>
int main()
{
int n,at[10], bt[10], ct[10], wt[10], tn =0, c, ta[10],tat[10];
//at-ArritvalTime::br-BurstTime::ct-CompletionTime::ta-TemporaryArray
//wt-WaitingTime::tat-TurnAroundTime::tn-CurrentTime(TimeNow)
// int i, j, k, tot, pc=0, pointer = 0, lp=-1;//lp-Last-executedProcess
int i, k, tot, pc=0, pointer = 0, lp=-1;//lp-Last-executedProcess
char pn[10][10];
printf("Enter the number of processes: ");
scanf("%d",&n);
printf("Enter <ProcessName> <ArrivalTime> <BurstTime>\n");
for(i=0;i<n;i++)
scanf("%s%d%d",&pn[i],&at[i],&bt[i]);
for(i=0; i<n; i++)
{
ct[i] = -1;
ta[i] = bt[i];
}
while(pc!=n)
{
k=0;
c = 0;
for(i=0; i<n; i++)
{
if(ct[i]<0 && at[i]<=tn)
c++;
}
if(c==0)
tn++;
else
{
pointer = 0;
while(at[pointer]>tn || ct[pointer]>0)
pointer++;
for(k=pointer+1; k<n; k++)
if( (at[k]<=tn && ct[k]<0) &&
( (bt[pointer]==bt[k] && k==lp) || bt[pointer]>bt[k] ) )
pointer = k;
if(ct[pointer]<0)
{
bt[pointer]--;
tn++;
if(bt[pointer]==0)
{
ct[pointer] = tn;
wt[pointer] = ct[pointer] - ( at[pointer]+ ta[pointer] );
tat[pointer] = ct[pointer] - at[pointer];
pc++;
}
}
lp = pointer;
}
}
printf("\nPN\tAT\tBT\tCT\tWT\tTAT\n");
for(i=0;i<n;i++)
printf("%s\t%d\t%d\t%d\t%d\t%d\n",pn[i],at[i],ta[i],ct[i],wt[i],tat[i]);
return 0;
}
/* SAMPLE OUTPUT
Enter the number of processes: 6
Enter <ProcessName> <ArrivalTime> <BurstTime>
p1 3 1
p2 1 4
p3 10 6
p4 25 10
p5 1 3
p6 12 3
PN AT BT CT WT TAT
p1 3 1 5 1 2
p2 1 4 9 4 8
p3 10 6 19 3 9
p4 25 10 35 0 10
p5 1 3 4 0 3
p6 12 3 15 0 3
*/ SJF CPU Scheduling Algorithm (Non-Preemptive)
//PROGRAM FOR SHORTEST-JOB-FIRST(SJF) "CPU SCHEDULING ALGORITHM" WITHOUT PRE_EMPTION
#include<stdio.h>
#include<conio.h>
int main()
{
int at[10], bt[10], ct[10], wt[10], ta[10], tat[10];
//at-ArritvalTime::br-BurstTime::ct-CompletionTime::ta-TemporaryArray
//wt-WaitingTime::tat-TurnAroundTime::tn-CurrentTime(TimeNow)
int n, i, k, pc=0, pointer = 0, tn =0, c;//pc-ProcessesCompleted
char pn[10][10]; //pn-ProcessName
printf("Enter the number of processes: ");
scanf("%d",&n);
printf("Enter <ProcessName> <ArrivalTime> <BurstTime>\n");
for(i=0;i<n;i++)
scanf("%s%d%d",&pn[i],&at[i],&bt[i]);
for(i=0; i<n; i++)
{
ct[i] = -1;
ta[i] = bt[i];
}
while(pc!=n)
{
c = 0;
for(i=0; i<n; i++)
if(ct[i]<0 && at[i]<=tn)
c++;
if(c==0)
tn++;
else
{
pointer = 0;
while(at[pointer]>tn || ct[pointer]>0)
pointer++;
for(k=pointer+1; k<n; k++)
if(at[k]<=tn && ct[k]<0 && bt[pointer]>bt[k])
pointer = k;
if(ct[pointer]<0)
{
tn=tn+bt[pointer];
bt[pointer] = 0;
ct[pointer] = tn;
wt[pointer] = ct[pointer] - ( at[pointer]+ ta[pointer] );
tat[pointer] = ct[pointer] - at[pointer];
pc++;
}
}
}
printf("\nPN\tAT\tBT\tCT\tWT\tTAT\n");
for(i=0;i<n;i++)
printf("%s\t%d\t%d\t%d\t%d\t%d\n",pn[i],at[i],ta[i],ct[i],wt[i],tat[i]);
return 0;
}
/* EXAMPLE OUTPUT
Enter the number of processes: 6
Enter <ProcessName> <ArrivalTime> <BurstTime>
p1 3 2
p2 6 5
p3 1 1
p4 6 2
p5 15 3
p6 20 10
PN AT BT CT WT TAT
p1 3 2 5 0 2
p2 6 5 13 2 7
p3 1 1 2 0 1
p4 6 2 8 0 2
p5 15 3 18 0 3
p6 20 10 30 0 10
*/
//ANOTHER PROGRAM for the same problem
//PROGRAM FOR SHORTEST-JOB-FIRST(SJF) "CPU SCHEDULING ALGORITHM" WITH NO-PRE_EMPTION & ARRIVAL TIMES
#include<stdio.h>
#include<string.h>
int main(void)
{
//VARIABLE DECLARATION
char pn[20][20], c[20][20]; //PN-PROGRAM NAMES C-A TEMPORARY ARRAY
int n,i,j,at[20], bt[20], wt[20],ct[20],tat[20]; //bt-BURST TIME ; wt-WAITING TIME; tat-TURN AROUND TIME
int temp1, temp2, count=0,twt=0;//,tat=0;
printf("Enter number of processes:");
scanf("%d", &n);
printf("Enter PN, AT, BT:\n");
//TAKING INPUT VALUES i.e., PROCESS-NAMES, ARRIVAL-TIMES AND BURST-TIMES
for(i=0; i<n; i++)
scanf("%s%d%d",&pn[i],&at[i],&bt[i]);
//SCHEDULING THE PROCESSES ACCORDING TO SJF
for(i=0 ; i<n; i++)
{
for(j=i+1; j<n; j++)
if (
//IF THERE IS NO PROCESS IN MAIN MEMORY,
//SORT PROCESSES ACCORDING TO ARRIVAL TIMES &
//IF WE GOT PROCESSES WITH SAME ARRIVAL TIME SORT THEM BY BURST TIMES
( (i==0||count<1)&&(at[i]>at[j]||(at[i]==at[j]&&bt[i]>bt[j])) )
//IF WE GOT ONLY ONE PROCESS IN MAIN MEMORY AFTER COMPLETION OF THE CURRENT PROCESS
|| (count == 1 && ct[i-1]>=at[j])
//IF WE GOT MORE THAN ONE PROCESS IN MAIN MEMORY, SORT THEM BY BURST TIMES
|| ((ct[i-1]>=at[j]&&bt[i]>bt[j]))// || (ct[i-1]<at[i]&&ct[i-1]>=at[j]))
)
//SWAPPING PROCESSES
{
temp1 = bt[i];
temp2 = at[i];
bt[i] = bt[j];
at[i] = at[j];
bt[j] = temp1;
at[j] = temp2;
strcpy(c[i],pn[i]);
strcpy(pn[i],pn[j]);
strcpy(pn[j],c[i]);
}
if(i==0 || count<1)
ct[i] = at[i] + bt[i];
else
ct[i] = ct[i-1] + bt[i];
wt[i] = ct[i] - (at[i] + bt[i]);
tat[i] = ct[i] - at[i];
count = 0 ;
for(j=i+1; j<n; j++)
if(ct[i]>=at[j])
count++;
}
//PRINTING THE VALUES AFTER ALL PREOCESSES COMPLETED
printf("S.N.\tProcess-Name\tArrival-Time\tBurst-Time\tCT\tWT\tTAT\n");
for(i=0; i<n; i++)
printf("%d\t\t%s\t\t%d\t\t%d\t%d\t%d\t%d\n",(i+1),pn[i],at[i],bt[i],ct[i],wt[i],tat[i]);
} //END OF MAIN
/* EXAMPLE OUTPUT
Enter number of processes:6
Enter PN, AT, BT:
p1 3 2
p2 6 5
p3 1 1
p4 6 2
p5 15 3
p6 20 10
S.N. Process-Name Arrival-Time Burst-Time CT WT TAT
1 p3 1 1 2 0 1
2 p1 3 2 5 0 2
3 p4 6 2 8 0 2
4 p2 6 5 13 2 7
5 p5 15 3 18 0 3
6 p6 20 10 30 0 10
*/
FCFS
FCFS CPU Scheduling Algorithm
//PROGRAM FOR FIRST-COME-FIRST-SERVE "CPU SCHEDULING ALGORITHM"
#include<stdio.h>
#include<string.h>
int main(void)
{
//VARIABLE DECLARATION
char pn[20][20], c[20][20]; //PN-PROGRAM NAMES
int n,i,j,at[20], bt[20], wt[20],tat[20], ct[20]; //bt-BURST TIME ; wt-WAITING TIME; tat-TURN AROUND TIME
int twt=0, ttat=0, temp1, temp2;
printf("Enter number of processes:");
scanf("%d", &n);
//TAKING INPUT VALUES i.e., PROCESS-NAMES, ARRIVAL-TIMES AND BURST-TIMES
printf("Enter <Process-name> <Arrival-time> <Burst-time> for processes:\n", (i+1));
for(i=0; i<n; i++)
scanf("%s%d%d",&pn[i],&at[i],&bt[i]);
//SORT THE PROCESSES ACCORDING TO ARRIVAL TIMES
for(i=0;i<n;i++)
{
for(j=i+1; j<n;j++)
{
if(at[i]>at[j])
{
temp1 = bt[i];
temp2 = at[i];
bt[i] = bt[j];
at[i] = at[j];
bt[j] = temp1;
at[j] = temp2;
strcpy(c[i],pn[i]);
strcpy(pn[i],pn[j]);
strcpy(pn[j],c[i]);
}
}
if(i==0) ct[0]=at[0]+bt[0];
if(i>0)
{
if(at[i]>ct[i-1])
ct[i]=at[i]+bt[i];
else
ct[i]=ct[i-1]+bt[i];
}
}
//CALCULATING WAITING TIME & TAT
wt[0]=0;
tat[0]=ct[0]-at[0];
for(i=1;i<n;i++)
{
tat[i] = ct[i]-at[i];
wt[i] = tat[i]-bt[i];
twt += wt[i];
ttat += tat[i];
}
//PRINTING THE VALUES AFTER ALL PREOCESSES COMPLETED
printf("S.N.\tPN\tAT\tBT\tCT\tWT\tTAT\n");
for(i=0; i<n; i++)
printf("%d\t%s\t%d\t%d\t%d\t%d\t%d\n",(i+1),pn[i],at[i],bt[i],ct[i],wt[i],tat[i]);
printf("Total waiting time:%d\n", twt);
printf("Total Turn Around Time:%d", ttat);
}
Thursday, 20 August 2015
race around
Binary Semaphores can assume only the value 0 or the value 1 counting
semaphores also called general semaphores can assume only nonnegative
values.
The P (or wait or sleep or down) operation on semaphores S, written as P(S) or wait (S), operates as follows:
P(S): IF S > 0
THEN S := S - 1
ELSE (wait on S)
The V (or signal or wakeup or up) operation on semaphore S, written as V(S) or signal (S), operates as follows:
V(S): IF (one or more process are waiting on S)
THEN (let one of these processes proceed)
ELSE S := S +1
Operations P and V are done as single, indivisible,
atomic action. It is guaranteed that once a semaphore operations has
stared, no other process can access the semaphore until operation has
completed. Mutual exclusion on the semaphore, S, is enforced within P(S) and V(S).
If several processes attempt a P(S) simultaneously, only process will be
allowed to proceed. The other processes will be kept waiting, but the
implementation of P and V guarantees that processes will not suffer
indefinite postponement.
Semaphores solve the lost-wakeup problem.
Producer-Consumer Problem Using Semaphores
The Solution to producer-consumer problem uses three semaphores, namely, full, empty and mutex.
The semaphore 'full' is used for counting the number of slots in the buffer that are full. The 'empty' for counting the number of slots that are empty
and semaphore 'mutex' to make sure that the producer and consumer do
not access modifiable shared section of the buffer simultaneously.
Initialization
Set full buffer slots to 0.
i.e., semaphore Full = 0.
Set empty buffer slots to N.
i.e., semaphore empty = N.
For control access to critical section set mutex to 1.
i.e., semaphore mutex = 1.
Producer ( )
WHILE (true)
produce-Item ( );
P (empty);
P (mutex);
enter-Item ( )
V (mutex)
V (full);
Consumer ( )
WHILE (true)
P (full)
P (mutex);
remove-Item ( );
V (mutex);
V (empty);
consume-Item (Item)
An Example:-
#include<sys/types.h>
#include<stdio.h>
#include<sys/ipc.h>
#include<unistd.h>
#include<sys/sem.h>
struct msgbuf {
long mtype; /* message type, must be > 0 */
char mtext[10]; /* message data */
};
union semun {
int val; /* Value for SETVAL */
struct semid_ds *buf; /* Buffer for IPC_STAT, IPC_SET */
unsigned short *array; /* Array for GETALL, SETALL */
struct seminfo *__buf; /* Buffer for IPC_INFO
(Linux-specific) */
};
struct buffer
{
unsigned short sem_num; /* semaphore number */
short sem_op; /* semaphore operation */
short sem_flg; /* operation flags */
};
int main(int argc, char* argv[])
{
struct msgbuf buf;
struct buffer buf1;
union semun sem;
int msg_id=msgget((key_t)2341,IPC_CREAT|IPC_EXCL);
if(msg_id<0)
{
printf("Already exists\n");
msg_id=msgget((key_t)2341,0666);
if(msg_id<0)
{
printf("handle error\n");
return 0;
}
}
////////////////////
int sem_id=semget((key_t)6001,1,IPC_CREAT|IPC_EXCL);
if(sem_id<0)
{
printf("already used semaphore\n");
sem_id=semget((key_t)6001,1,0666);
if(sem_id<0)
{
printf("error in getting semaphore\n");
return 0;
}
}
//sem.val=1;
//semctl(sem_id,0,SETVAL,sem);
sem.val=0;
semctl(sem_id,0,SETVAL,sem);
///////////////////////////
buf.mtype=atoi(argv[1]);
strcpy(buf.mtext,"test it");
int ret=msgsnd(msg_id,&buf,sizeof(buf.mtext),0);
if(ret<=0)
printf("msg sndng error%d\n",ret);
return 0;
}
Creating Reader 1
#include<sys/types.h>
#include<stdio.h>
#include<sys/ipc.h>
#include<unistd.h>
#include<sys/sem.h>
struct msgbuf {
long mtype; /* message type, must be > 0 */
char mtext[10]; /* message data */
};
union semun {
int val; /* Value for SETVAL */
struct semid_ds *buf; /* Buffer for IPC_STAT, IPC_SET */
unsigned short *array; /* Array for GETALL, SETALL */
struct seminfo *__buf; /* Buffer for IPC_INFO
(Linux-specific) */
};
struct buffer
{
unsigned short sem_num; /* semaphore number */
short sem_op; /* semaphore operation */
short sem_flg; /* operation flags */
};
int main()
{
struct buffer buf1;
union semun sem;
struct msgbuf buf;
int msg_id=msgget((key_t)2341,IPC_CREAT|IPC_EXCL);
if(msg_id<0)
{
printf("Already exists\n");
msg_id=msgget((key_t)2341,0666);
if(msg_id<0)
{
printf("handle error\n");
return 0;
}
}
int ret=msgrcv(msg_id,&buf,sizeof(buf.mtext),10,0);
if(ret<=0)
printf("msg sndng error\n");
else
printf("%s\n",buf.mtext);
int sem_id=semget((key_t)6001,1,IPC_CREAT|IPC_EXCL);
if(sem_id<0)
{
printf("already used semaphore\n");
sem_id=semget((key_t)6001,1,0666);
if(sem_id<0)
{
printf("error in getting semaphore\n");
return 0;
}
}
//sem.val=1;
//semctl(sem_id,0,SETVAL,sem);
buf1.sem_num=0;
buf1.sem_flg=SEM_UNDO;
buf1.sem_op=1;
semop(sem_id,&buf1,1);
return 0;
}
Creating Reader 2
#include<sys/types.h>
#include<stdio.h>
#include<sys/sem.h>
#include<sys/ipc.h>
#include<unistd.h>
struct msgbuf {
long mtype; /* message type, must be > 0 */
char mtext[10]; /* message data */
};
union semun {
int val; /* Value for SETVAL */
struct semid_ds *buf; /* Buffer for IPC_STAT, IPC_SET */
unsigned short *array; /* Array for GETALL, SETALL */
struct seminfo *__buf; /* Buffer for IPC_INFO
(Linux-specific) */
};
struct buffer
{
unsigned short sem_num; /* semaphore number */
short sem_op; /* semaphore operation */
short sem_flg; /* operation flags */
};
int main()
{
struct msgbuf buf; //buffer for message queue
struct buffer buf1; //buffer for semaphore
union semun sem; //union for semaphore
int msg_id=msgget((key_t)2341,IPC_CREAT|IPC_EXCL); //taking the message queue
int sem_id=semget((key_t)6001,1,IPC_CREAT|IPC_EXCL); //taking the semaphore
if(sem_id<0)
{
printf("already used semaphore\n");
sem_id=semget((key_t)6001,1,0666);
if(sem_id<0)
{
printf("error in getting semaphore\n");
return 0;
}
}
//sem.val=0; //initialize the semaphore
//semctl(sem_id,0,SETVAL,sem);
buf1.sem_num=0;
buf1.sem_flg=SEM_UNDO;
buf1.sem_op=-1; //wait operation
semop(sem_id,&buf1,1); //wait
if(msg_id<0)
{
printf("Already exists\n");
msg_id=msgget((key_t)2341,0666);
if(msg_id<0)
{
printf("handle error\n");
return 0;
}
}
int ret=msgrcv(msg_id,&buf,sizeof(buf.mtext),30,0); //reading the MQ
if(ret<=0)
{
printf("msg sndng error\n");
}
else
{
printf("%s\n",buf.mtext);
msgctl(msg_id,IPC_RMID,NULL); //removing the MQ
semctl(sem_id,0,IPC_RMID); //removing the semaphore
}
return 0;
}
#include<stdio.h>
#include<pthread.h>
#include<semaphore.h>
#include<unistd.h>
#include<stdlib.h>
sem_t sem1;
int i=5,res=0;
void * fun1(void* p)
{
sem_wait(&sem1); printf("thread 1 is running:\n"); i=0;
}
void * fun2(void* p)
{ printf("thread 2 is running:\n"); res=200/i; sem_post(&sem1);
}
int main()
{ sem_init(&sem1,0,0); int ret; void *status; pthread_t p_id,t_id; pthread_create(&p_id,NULL,fun1,NULL); pthread_create(&t_id,NULL,fun2,NULL); //printf("%d",i); pthread_join(p_id,&status);
// printf("thread1:%s\n",(char*)status); pthread_join(t_id,&status);
// printf("thread1:%s",(char*)status);
return 0;
}
Wednesday, 8 July 2015
Operating Systems
A CPU generates 32-bit virtual addresses. The page size is 4 KB. The processor has a translation look-aside buffer (TLB) which can hold a total of 128 page table entries and is 4-way set associative. The minimum size of the TLB tag is:
(A) 11 bits
(B) 13 bits
(C) 15 bits
(D) 20 bits
Answer: (C)
Explanation: Size of a page = 4KB = 2^12
Total number of bits needed to address a page frame = 32 – 12 = 20
If there are ‘n’ cache lines in a set, the cache placement is called n-way set associative. Since TLB is 4 way set associative and can hold total 128 (2^7) page table entries, number of sets in cache = 2^7/4 = 2^5. So 5 bits are needed to address a set, and 15 (20 – 5) bits are needed for tag.
(A) 11 bits
(B) 13 bits
(C) 15 bits
(D) 20 bits
Answer: (C)
Explanation: Size of a page = 4KB = 2^12
Total number of bits needed to address a page frame = 32 – 12 = 20
If there are ‘n’ cache lines in a set, the cache placement is called n-way set associative. Since TLB is 4 way set associative and can hold total 128 (2^7) page table entries, number of sets in cache = 2^7/4 = 2^5. So 5 bits are needed to address a set, and 15 (20 – 5) bits are needed for tag.
Consider data given in the above question. What is the minimum number of page colours needed to guarantee that no two synonyms map to different sets in the processor cache of this computer? (GATE CS 2013)
(A) 2
(B) 4
(C) 8
(D) 16
Answer: (C)
Explanation:
(A) 2
(B) 4
(C) 8
(D) 16
Answer: (C)
Explanation:
1 MB 16-way set associative virtually indexed physically tagged cache(VIPT).
The cache block size is 64 bytes.
No of blocks is 2^20/2^6 = 2^14.
No of sets is 2^14/2^4 = 2^10.
VA(46)
+-------------------------------+
tag(30) , Set(10) , block offset(6)
+-------------------------------+
In VIPT if the no. of bits of page offset =
(Set+block offset) then only one page color is sufficient.
but we need 8 colors because the number bits where the cache set index and
physical page number over lap is 3 so 2^3 page colors is required.(option
c is ans).
Virtual memory is (A) Large secondary memory (B) Large main memory (C) Illusion of large main memory (D) None of the above Answer: (C) Explanation: Virtual memory is illusion of large main memory.
Subscribe to:
Posts (Atom)