23-06-2012, 02:43 PM
Synchronization in Distributed Systems
Synchronization in Distributed Systems.ppt (Size: 81 KB / Downloads: 147)
Introduction
Semaphores require processes to access a shared variable. Other synchronization mechanisms may also be based on shared memory (monitors, for example)
In distributed systems, interprocess communication is via messages (or RPC ) so mutual exclusion mechanisms must be based on this approach. Logical clocks are an example.
Message Passing
Processes may use broadcast (transmit to any interested process) or multicast (transmit to all members of a specific group) message passing.
Blocking send/receive protocols are often used, because it can be guaranteed that the sender and receiver are synchronized when the message is exchanged
Sender will not continue until message has reached receiver
Distributed Mutual Exclusion Characterized
Processes communicate only through messages – no shared memory or clock.
Processes must expect unpredictable message delays.
Processes coordinate access to shared resources (printer, file, etc.) that should only be used in a mutually exclusive manner.
Example Use – A Variation of the Readers/Writers Problem
Consider a system where a file server is replicated at several sites in the network.
Users access most readily available version
Multiple readers are okay
For replica consistency, updates should be done at all sites at the same time
One way: enforce mutual exclusion on a write broadcast: no writes anywhere until previous writes complete.
This may not be the best way to solve the problem
Decentralized Mutex Algorithm
More fault-tolerant than the centralized approach.
Based on the Distributed Hash Table (DHT) system structure
Object names are hashed to find the node where they are stored
n replicas of each object are placed on n successive nodes
Hash object name to get addresses
Now every replica has a coordinator that controls access
Distributed Mutual Exclusion
Probabilistic algorithms do not guarantee mutual exclusion is correctly enforced.
Many other algorithms do, including the following.
Originally proposed by Lamport, based on his logical clocks and total ordering relation
Modified by Ricart-Agrawala.