Ewerwrkkkz # m “” That was written by my son who is 1 year and 7 months old

Centralized synchronization extends to distributed environments; And how do distributed systems handle deadlocks?

In a distributed system, there is no common memory or common clock, so it is sometimes impossible to determine the order of two events. It is necessary to propose a distributed algorithm for consistent global ordering of events.

If there is no causal relationship between two events, the two events are said to be executed concurrently. Since they do not affect each other, it does not matter which comes first; what matters is that processes that care about the order of the two concurrent events agree in some order.

In order to determine whether event A occurred before event B, A common clock, or A fully synchronized clock set, is required. But none of this is practical in distributed systems, and you must define a prior relationship without using a physical clock.

What to do? The time stamp.

Define one logical clock per process. When process B receives a message with a timestamp t greater than its logical clock LC(B), it increments its logical clock LC(B)=t+1.

In order to achieve a full sort, according to the timestamp sort method, just follow the following rule: if two events have the same timestamp, they are concurrent.

Implement mutual exclusion in distributed environment.

1. A process in the centralized algorithm system is selected as the coordinator of the critical section entry. Each process that wants to call a mutex must send a request to the coordinator to enter the critical section, and only after receiving a response can it enter the critical section, otherwise it will queue up. A release message is also sent to the coordinator after exiting the critical section. This algorithm guarantees mutual exclusion.

When a process wants to enter a critical section, it generates a new timestamp and sends a request message to all other processes in the system. When these processes receive a request message, they send a reply message either immediately or later. When this process receives a reply message from all the other processes in the system, it can enter the critical section and queue incoming requests and delay them. After exiting the critical section, the process sends a reply message to all requests it has deferred.

Whether a process immediately responds to a request message depends on three factors: 1) if it is in its critical region, was postponed reply ‘2) if it doesn’t want to enter its critical section, immediate answer 3) if it wants to enter did not enter, or your request from the timestamp and the timestamp request message process, if you request a timestamp is greater than the latter, reply immediately, because each other first requests; Otherwise, the reply is delayed.

3. Token passing algorithm The system circulates a token between processes. Only the token holder has access to a critical section. Because there is only one token, only one process can enter the critical section at a time.

Atomicity The role of transaction coordinator in distributed system is to ensure atomicity of transaction execution in distributed system.

Each site has its own local transaction coordinator, who coordinates all transactions that start at the site, including: 1) starting the execution of the transaction, 2) splitting the transaction into subtransactions and distributing them to the appropriate sites for execution, and 3) coordinating the completion of the transaction

To maintain atomicity, all sites involved in executing transactions must agree on the final result of executing transactions: either commit at all sites or terminate at all sites. To ensure this feature, the transaction coordinator must implement a commit protocol. The simplest and most widely used protocol is the two-phase Commit (2PC) protocol. When all sites executing a transaction notify the transaction coordinator that the transaction has completed, the coordinator initiates the 2PC protocol. In the first phase, the coordinator sends a prepare message to all sites executing the transaction. The site can respond abort or ready phase 2, and the coordinator receives all responses to the PREPARE message or, after a period of time, can decide whether to commit or terminate the transaction. If all are ready, the transaction can be committed, otherwise it must be terminated. A site executing a transaction can terminate unconditionally at any time before sending a ready reply message.

Error handling in 2PC 1) An error at a participating site After the site recovers from the error, the log must be examined to determine the fate of the transaction being executed

2) Coordinator error Coordinator error, the fate of the transaction needs to be determined by the participating site. Sometimes, you have to wait for the coordinator to recover.

3) If all sites are on the same network segment, transaction submission will not be affected; Otherwise refer to error handling above.

The transaction manager of a distributed database system manages transactions (or sub-transactions) that access data stored at a local site and are part of a local or global transaction (that is, transactions performed at several sites). Each transaction manager is responsible for maintaining a log for recovery and participating in the concurrency control scheme.

1) Non-replication method Each site maintains a lock manager who manages locking and unlocking requests for data stored in the site. When a transaction wishes to lock data items at a site, it sends a message to the lock manager at that site. Suitable for situations where no data is replicated. Easy to implement.

2) The single coordinator method maintains only one lock manager on one site, and all lock and unlock requests are made on this site. Easy to implement, easy to deal with deadlock; But prone to bottlenecks, fragile.

3) Most protocols maintain a lock manager per site that manages the locking of data stored in the site or its copies. When a transaction wants to lock a data item, it must send a lock request to more than half of the sites.

4) Bias protocol is more convenient to handle shared locks than exclusive locks. A shared lock only needs to be handled by the site of any copy; Exclusive locks require site processing that contains all copies.

5) Primary copy Select the site where a copy resides as the primary site, and the lock on the copy is handled by the primary site.

2. Time stamps

In a distributed environment, there must be a scheme that produces a unique timestamp.

1) Generation of unique timestamp

Two methods:

Centralized: Select a site to dispatch the timestamp

Distributed: each site generates a unique local timestamp, which is combined with the site identifier to generate a globally unique identifier (GUID?).



For a distributed approach, there needs to be a mechanism to ensure that timestamps are generated fairly in the system. To ensure that different logical clocks are synchronized, when there is a timestamp