Objectives:- Write an algorithm to simulate the functioning of Lamport’s clocks.
Algorithm:
Lamport's logical clocks
v the "time" concept in distributed
systems -- used to order events in a distributed system.
v Assumption:
§ the execution of a process is characterized by a
sequence of events. An event can be the execution of one
instruction or of one procedure.
§ sending a message is one event, receiving a
message is one event.
v The events in a distributed system are not total chaos.
Under some conditions, it is possible to ascertain the order of
the events. Lamport's logical clocks try to catch this.
Lamport's ``happened before'' relation
The ``happened before'' relation (®) is defined as follows:
v
A®B if A and B are within the same
process (same sequential thread of control) and A occurred before B.
v *************************
v if A®B and B®C then A®C
Event A causally affects event B iff A®B.
Distinct events A and B are concurrent (A| | B) if we do not have A®B or B®A.
Lamport Logical Clocks
Are local to each process (processor?)
v do not measure real time
v only measure ``events''
v are consistent with the happened-before relation
v are useful for totally ordering transactions, by
using logical clock values as timestamps.
Logical Clock Conditions
Ci is the local clock
for process Pi
v if a and b are two successive
events in Pi, then Ci(b) = Ci(a) + d1, where d1> 0
v if a is the sending of
message m by Pi, then mis assigned timestamp tm= Ci(a)
v if b is the receipt of m by Pj, then Cj(b) = max { Cj (b), tm+ d2}, where d2> 0 The value of d could be 1, or it
could be an approximation to the elapsed real time. For example, we could take d1to be the elapsed local
time, and d2to be the estimated
message transmission time. The latter solves the problem of
waiting forever for a virtual time instant to pass.
Program Code:
#include<stdio.h>
#include<conio.h>
int max(int,int);
int max(int a, int b)
{
if(a>b)
*************
else
return b;
}
int main()
{
int n1, n2, p1[20], p2[20], x[20][20], i, z, j, a,
k;
printf ("ENTER NO OF EVENTS ON P1 : ");
scanf (*********);
printf ("\n ENTER NO OF EVENTS ON P2:");
scanf ("%d",&n2);
*******************
*******************
*******************
if(z==1)
{
Printf("\nEnterDependencyMatrix\n");
for(i=0;i<n2;i++)
{
printf("\tP2E%d",i+1);
}
for(i=0;i<n1;i++)
{
***********************
}
for(i=0;i<n1;i++)
{
for(j=0;j<n2;j++)
if (x[i][j]==1)
{
a=max(p2[j], p1[j]+1);
p2[j]=a;
for(k=j;k<n2;k++)
{
p2[k+1]=p2[k]+1;
}
}
for(j=0;j<n2;j++)
if ((-1)==x[i][j])
{
*************************
for(k=j;k<n1;k++)
{
p1[k+1]=p1[k]+1;
}
}
}
printf("Lamport clock for P1 -> ");
for(i=0;i<n1;i++)
{
printf("%d ",p1[i]);
}
printf("\nLamport clock for P2 -> ");
for(i=0;i<n2;i++)
{
printf("%d ",p2[i]);
}
Else
{
printf("Lamport clock for P1 -> ");
for(i=0;i<n1;i++)
{
printf("%d ",p1[i]);
}
printf("\nLamport clock for P2 -> ");
for(i=0;i<n2;i++)
{
printf("%d ",p2[i]);
}
}
getch();
}
}
