Algoritmo di Berkeley: differenze tra le versioni

Versione delle 18:22, 30 mag 2019

Versione attuale delle 15:59, 31 ago 2025

(14 versioni intermedie di 10 utenti non mostrate)

Riga 1:

{{F|teorie dell'informatica|marzo 2021}}

L'algoritmo di Berkeley è un metodo di sincronizzazione del clock negli algoritmi distribuiti in cui si assume che le macchine non abbiano una fonte accurata da cui ricevere il tempo. L'algoritmo è stato realizzato da Gusella e Zatti presso la University of California, Berkeley nel 1989.

{{W|informatica|marzo 2021}}

L''''algoritmo di Berkeley''' è un metodo di sincronizzazione del [[clock]] negli algoritmi distribuiti in cui si assume che le macchine non abbiano una fonte accurata da cui ricevere il tempo. L'algoritmo è stato realizzato da Gusella e Zatti presso lal'[[Università University of California,di Berkeley]] nel 1989.

=== L'algoritmo ===

---------------------

Al contrario dell'algoritmo di [[Algoritmo di Cristian|Cristian]], in questo processo è presente un master che periodicamente fa delle richieste agli slave.

Il processo segue i seguenti passi:

=== L'algoritmo ===

1. un master viene eletto tramite un algoritmo di elezione come quello di Chang e Roberts

Al contrario dell'algoritmo di [[Algoritmoalgoritmo di Cristian|Cristian]], in questo processo è presente un master che periodicamente fa delle richieste agliad altri nodi della rete che si comportano da [[Architettura master-slave|slave]].

Il processo segue i seguenti passi:

2. il master chiede agli slave di inviargli i propri timestamp similarmente a come avviene nell'[[algoritmo di Cristian]]

1.# un master viene eletto tramite un algoritmo di elezione come quello di Chang e RobertsRobert

3. il master quindi, tenendo conto dell'RTT, calcola la differenza (positiva o negativa) che intercorre tra il proprio tempo e quello dei vari slave che hanno risposto

2.# il master chiede agli slave di inviargli i propri timestamp similarmente a come avviene nell'[[algoritmo di Cristian]]

3.# il master quindi, tenendo conto dell'RTT, calcola la differenza (positiva o negativa) che intercorre tra il proprio tempo e quello dei vari slave che hanno risposto

4.# il master quindi esegue una media delle differenze calcolate

5.# ad ogni slave, il master, invia la differenza tra il tempo ricevuto dello slave e la media appena calcolata. In questo modo ogni slave sa di quanto tempo (positivo o negativo) deve aggiustare il proprio timer

L'utilizzo di questo sistema di calcolo della media evita ai vari slave di utilizzare tempi che nel tempo possono divergere tra loro.

Si noti che contrariamente al funzionamento di questo algoritmo, i computer, normalmente, si rifiuterebbero di aggiornare il proprio timer con un tempo negativo a quello già passato.

L'utilizzo di questo algoritmo potrebbe creare problemi a processi presenti sul sistema che invece assumono che, per definizione, il tempo sia continuo e strettamente monotono crescente (ad esempio il comando [[Make|make]])

Una prima e semplice soluzione a tale problema potrebbe essere quella di fermare temporaneamente il clock che tuttavia, porterebbe ad altri problemi.

Per correzioni minori, molti sistemi rallentano il clock (aka "clock slew").

Spesso il master ignora quei tempi che gli vengono inviati dagli slave se sono troppo distanti dalla media generata: in questo modo si previene un drastico cambiamento dei timer nella rete dovuto ad errori presenti in alcuni degli slave.

== Altri progetti ==

{{interprogetto}}

{{Portale|informatica}}

[[Categoria:Algoritmi]]