El reloj lógico de Lamport fue creado por Leslie Lamport. Es un procedimiento para determinar el orden de los eventos que ocurren. Proporciona una base para el algoritmo de reloj vectorial más avanzado . Debido a la ausencia de un reloj global en un sistema operativo distribuido, se necesita un reloj lógico Lamport .
Algoritmo:
- Ocurrió antes de la relación (->): a -> b, significa que ‘a’ sucedió antes que ‘b’.
- Reloj Lógico: Los criterios para los relojes lógicos son:
- [C1]: C i (a) < C i (b), [ C i -> Reloj lógico, si ‘a’ sucedió antes que ‘b’, entonces el tiempo de ‘a’ será menor que ‘b’ en un determinado proceso. ]
- [C2]: C i (a) < C j (b), [El valor del reloj de C i (a) es menor que C j (b)]
Referencia:
- Proceso : Pi
- Evento: E ij , donde i es el proceso en número y j : j ésimo evento en el i ésimo proceso .
- t m : lapso de tiempo del vector para el mensaje m.
- Reloj vectorial Ci asociado con el proceso P i , el elemento j ésimo es Ci[j] y contiene el valor más reciente de Pi para el tiempo actual en el proceso P j .
- d: tiempo de deriva, generalmente d es 1.
Reglas de implementación [IR]:
- [IR1]: Si a -> b [‘a’ sucedió antes que ‘b’ dentro del mismo proceso] entonces, C i (b) =C i (a) + d
- [IR2]: C j = max(C j , t m + d) [Si hay más cantidad de procesos, entonces t m = valor de C i (a), C j = valor máximo entre C j y t m + d ]
Por ejemplo:
- Tome el valor inicial como 1, ya que es el primer evento y no hay ningún valor entrante en el punto inicial:
- e11 = 1
- e21 = 1
- El valor del siguiente punto irá aumentando en d (d = 1), si no hay valor entrante, es decir, para seguir [IR1].
- e12 = e11 + d = 1 + 1 = 2
- e13 = e12 + d = 2 + 1 = 3
- e14 = e13 + d = 3 + 1 = 4
- e15 = e14 + d = 4 + 1 = 5
- e16 = e15 + d = 5 + 1 = 6
- e22 = e21 + d = 1 + 1 = 2
- e24 = e23 + d = 3 + 1 = 4
- e26 = e25 + d = 6 + 1 = 7
- Cuando haya un valor entrante, siga [IR2] , es decir, tome el valor máximo entre C j y T m + d .
- e17 = max(7, 5) = 7, [e16 + d = 6 + 1 = 7, e24 + d = 4 + 1 = 5, el máximo entre 7 y 5 es 7]
- e23 = max(3, 3) = 3, [e22 + d = 2 + 1 = 3, e12 + d = 2 + 1 = 3, máximo entre 3 y 3 es 3]
- e25 = max(5, 6) = 6, [e24 + 1 = 4 + 1 = 5, e15 + d = 5 + 1 = 6, máximo entre 5 y 6 es 6]
Limitación :
- En el caso de [IR1], si a -> b, entonces C(a) < C(b) -> verdadero.
- En el caso de [IR2], si a -> b, entonces C(a) < C(b) -> Puede ser cierto o no serlo.
A continuación se muestra el programa C para implementar el reloj lógico de Lamport:
C++
// C++ program to illustrate the Lamport's
// Logical Clock
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum timestamp
// between 2 events
int max1(int a, int b)
{
// Return the greatest of th two
if (a > b)
return a;
else
return b;
}
// Function to display the logical timestamp
void display(int e1, int e2,
int p1[5], int p2[3])
{
int i;
cout << "\nThe time stamps of "
"events in P1:\n";
for (i = 0; i < e1; i++) {
cout << p1[i] << " ";
}
cout << "\nThe time stamps of "
"events in P2:\n";
// Print the array p2[]
for (i = 0; i < e2; i++)
cout << p2[i] << " ";
}
// Function to find the timestamp of events
void lamportLogicalClock(int e1, int e2,
int m[5][3])
{
int i, j, k, p1[e1], p2[e2];
// Initialize p1[] and p2[]
for (i = 0; i < e1; i++)
p1[i] = i + 1;
for (i = 0; i < e2; i++)
p2[i] = i + 1;
cout << "\t";
for (i = 0; i < e2; i++)
cout << "\te2" << i + 1;
for (i = 0; i < e1; i++) {
cout << "\n e1" << i + 1 << "\t";
for (j = 0; j < e2; j++)
cout << m[i][j] << "\t";
}
for (i = 0; i < e1; i++) {
for (j = 0; j < e2; j++) {
// Change the timestamp if the
// message is sent
if (m[i][j] == 1) {
p2[j] = max1(p2[j], p1[i] + 1);
for (k = j + 1; k < e2; k++)
p2[k] = p2[k - 1] + 1;
}
// Change the timestamp if the
// message is received
if (m[i][j] == -1) {
p1[i] = max1(p1[i], p2[j] + 1);
for (k = i + 1; k < e1; k++)
p1[k] = p1[k - 1] + 1;
}
}
}
// Function Call
display(e1, e2, p1, p2);
}
// Driver Code
int main()
{
int e1 = 5, e2 = 3, m[5][3];
// message is sent and received
// between two process
/*dep[i][j] = 1, if message is sent
from ei to ej
dep[i][j] = -1, if message is received
by ei from ej
dep[i][j] = 0, otherwise*/
m[0][0] = 0;
m[0][1] = 0;
m[0][2] = 0;
m[1][0] = 0;
m[1][1] = 0;
m[1][2] = 1;
m[2][0] = 0;
m[2][1] = 0;
m[2][2] = 0;
m[3][0] = 0;
m[3][1] = 0;
m[3][2] = 0;
m[4][0] = 0;
m[4][1] = -1;
m[4][2] = 0;
// Function Call
lamportLogicalClock(e1, e2, m);
return 0;
}
C
// C program to illustrate the Lamport's
// Logical Clock
#include <stdio.h>
// Function to find the maximum timestamp
// between 2 events
int max1(int a, int b)
{
// Return the greatest of th two
if (a > b)
return a;
else
return b;
}
// Function to display the logical timestamp
void display(int e1, int e2,
int p1[5], int p2[3])
{
int i;
printf("\nThe time stamps of "
"events in P1:\n");
for (i = 0; i < e1; i++) {
printf("%d ", p1[i]);
}
printf("\nThe time stamps of "
"events in P2:\n");
// Print the array p2[]
for (i = 0; i < e2; i++)
printf("%d ", p2[i]);
}
// Function to find the timestamp of events
void lamportLogicalClock(int e1, int e2,
int m[5][3])
{
int i, j, k, p1[e1], p2[e2];
// Initialize p1[] and p2[]
for (i = 0; i < e1; i++)
p1[i] = i + 1;
for (i = 0; i < e2; i++)
p2[i] = i + 1;
for (i = 0; i < e2; i++)
printf("\te2%d", i + 1);
for (i = 0; i < e1; i++) {
printf("\n e1%d \t", i + 1);
for (j = 0; j < e2; j++)
printf("%d\t", m[i][j]);
}
for (i = 0; i < e1; i++) {
for (j = 0; j < e2; j++) {
// Change the timestamp if the
// message is sent
if (m[i][j] == 1) {
p2[j] = max1(p2[j], p1[i] + 1);
for (k = j + 1; k < e2; k++)
p2[k] = p2[k - 1] + 1;
}
// Change the timestamp if the
// message is received
if (m[i][j] == -1) {
p1[i] = max1(p1[i], p2[j] + 1);
for (k = i + 1; k < e1; k++)
p1[k] = p1[k - 1] + 1;
}
}
}
// Function Call
display(e1, e2, p1, p2);
}
// Driver Code
int main()
{
int e1 = 5, e2 = 3, m[5][3];
// message is sent and received
// between two process
/*dep[i][j] = 1, if message is sent
from ei to ej
dep[i][j] = -1, if message is received
by ei from ej
dep[i][j] = 0, otherwise*/
m[0][0] = 0;
m[0][1] = 0;
m[0][2] = 0;
m[1][0] = 0;
m[1][1] = 0;
m[1][2] = 1;
m[2][0] = 0;
m[2][1] = 0;
m[2][2] = 0;
m[3][0] = 0;
m[3][1] = 0;
m[3][2] = 0;
m[4][0] = 0;
m[4][1] = -1;
m[4][2] = 0;
// Function Call
lamportLogicalClock(e1, e2, m);
return 0;
}
Python3
# Python program to illustrate the Lamport's
# Logical Clock
# Function to find the maximum timestamp
# between 2 events
def max1(a, b) :
# Return the greatest of th two
if a > b :
return a
else :
return b
# Function to display the logical timestamp
def display(e1, e2, p1, p2) :
print()
print("The time stamps of events in P1:")
for i in range(0, e1) :
print(p1[i], end = " ")
print()
print("The time stamps of events in P2:")
# Print the array p2[]
for i in range(0, e2) :
print(p2[i], end = " ")
# Function to find the timestamp of events
def lamportLogicalClock(e1, e2, m) :
p1 = [0]*e1
p2 = [0]*e2
# Initialize p1[] and p2[]
for i in range (0, e1) :
p1[i] = i + 1
for i in range(0, e2) :
p2[i] = i + 1
for i in range(0, e2) :
print(end = '\t')
print("e2", end = "")
print(i + 1, end = "")
for i in range(0, e1) :
print()
print("e1", end = "")
print(i + 1, end = "\t")
for j in range(0, e2) :
print(m[i][j], end = "\t")
for i in range(0, e1) :
for j in range(0, e2) :
# Change the timestamp if the
# message is sent
if(m[i][j] == 1) :
p2[j] = max1(p2[j], p1[i] + 1)
for i in range(j + 1, e2) :
p2[k] = p2[k - 1] + 1
# Change the timestamp if the
# message is received
if(m[i][j] == -1) :
p1[i] = max1(p1[i], p2[j] + 1)
for k in range(i + 1, e1) :
p1[k] = p1[k - 1] + 1
# Function Call
display(e1, e2, p1, p2)
# Driver Code
if __name__ == "__main__" :
e1 = 5
e2 = 3
m = [[0]*3 for i in range(0,5)]
# dep[i][j] = 1, if message is sent
# from ei to ej
# dep[i][j] = -1, if message is received
# by ei from ej
# dep[i][j] = 0, otherwise
m[0][0] = 0
m[0][1] = 0
m[0][2] = 0
m[1][0] = 0
m[1][1] = 0
m[1][2] = 1
m[2][0] = 0
m[2][1] = 0
m[2][2] = 0
m[3][0] = 0
m[3][1] = 0
m[3][2] = 0
m[4][0] = 0
m[4][1] = -1
m[4][2] = 0
# Function Call
lamportLogicalClock(e1, e2, m)
# This code is contributed by rakeshsahni
Javascript
<script>
// JavaScript program to illustrate the Lamport's
// Logical Clock
// Function to find the maximum timestamp
// between 2 events
const max1 = (a, b) => {
// Return the greatest of th two
if (a > b)
return a;
else
return b;
}
// Function to display the logical timestamp
const display = (e1, e2, p1, p2) => {
let i;
document.write(`<br/>The time stamps of events in P1:<br/>`);
for (i = 0; i < e1; i++) {
document.write(`${p1[i]} `);
}
document.write(`<br/>The time stamps of events in P2:<br/>`);
// Print the array p2[]
for (i = 0; i < e2; i++)
document.write(`${p2[i]} `);
}
// Function to find the timestamp of events
const lamportLogicalClock = (e1, e2, m) => {
let i, j, k, p1 = [], p2 = [];
// Initialize p1[] and p2[]
for (i = 0; i < e1; i++)
p1[i] = i + 1;
for (i = 0; i < e2; i++)
p2[i] = i + 1;
for (i = 0; i < e2; i++)
document.write(`\te2${i + 1}`)
for (i = 0; i < e1; i++) {
document.write(`<br/>e1${i + 1} `)
for (j = 0; j < e2; j++)
document.write(`${m[i][j]}\t`);
}
for (i = 0; i < e1; i++) {
for (j = 0; j < e2; j++) {
// Change the timestamp if the
// message is sent
if (m[i][j] == 1) {
p2[j] = max1(p2[j], p1[i] + 1);
for (k = j + 1; k < e2; k++)
p2[k] = p2[k - 1] + 1;
}
// Change the timestamp if the
// message is received
if (m[i][j] == -1) {
p1[i] = max1(p1[i], p2[j] + 1);
for (k = i + 1; k < e1; k++)
p1[k] = p1[k - 1] + 1;
}
}
}
// Function Call
display(e1, e2, p1, p2);
}
// Driver Code
let e1 = 5, e2 = 3;
// message is sent and received
// between two process
/*dep[i][j] = 1, if message is sent
from ei to ej
dep[i][j] = -1, if message is received
by ei from ej
dep[i][j] = 0, otherwise*/
const m = [
[0, 0, 0],
[0, 0, 1],
[0, 0, 0],
[0, 0, 0],
[0, -1, 0]
]
// Function Call
lamportLogicalClock(e1, e2, m);
// This code is contributed by rakeshsahni
</script>
Producción
e21 e22 e23 e11 0 0 0 e12 0 0 1 e13 0 0 0 e14 0 0 0 e15 0 -1 0 The time stamps of events in P1: 1 2 3 4 5 The time stamps of events in P2: 1 2 3
Complejidad de Tiempo: O(e1 * e2 * (e1 + e2))
Espacio Auxiliar: O(e1 + e2)