【正文】 ased ? A Centralized Algorithm ? A Decentralized Algorithm ? A Distributed Algorithm ? Token based ? A Token Ring Algorithm Centralized algorithm ? Mimic single processor system ? One process elected as coordinator 1. Request resource 2. Wait for response 3. Receive grant 4. access resource 5. Release resource P C request(R) grant(R) release(R) Centralized algorithm ? If another process claimed resource: ? Coordinator does not reply until release ? Maintain queue ? Service requests in FIFO order Queue P1 P2 P0 C request(R) grant(R) release(R) P1 P2 request(R) request(R) grant(R) Centralized Algorithm Step 1: Process 1 asks the coordinator for permission to access a hared resource. Permission is granted. Step 2: Process 2 then asks permission to access the same resource. The coordinator does not reply. Step 3: When process 1 releases the resource, it tells the coordinator, which then replies to 2. Centralized algorithm Benefits ? Fair ? All requests processed in order ? Easy to implement, understand, verify Problems ? Process cannot distinguish being blocked from a dead coordinator ? Centralized server can be a bottleneck Decentralized Algorithm ? Distributed Hash Table ? Nodes and names have keys, which are large integers. ? You get the key from the name by hashing. Nodes get keys (called IDs) by some way, usually just random. ? Given a name, hash it to the key. ? Now find the node that is responsible for that key. It is the node that has an ID = key. A Decentralized Algorithm ? Use a distributed hash table (DHT). ? Hashes to a node. ? Each resource has n coordinators (called replicas in the book). A limit m ( n/2) is predefined. ? A client acquires the lock by sending a request to each coordinator. ? If it gets m permissions, then it gets it. ? If a resource is already locked, then it will be rejected (as opposed to just blocking.) 1. Send lock requests 2. Receive responses. Blue succeeds. 3. Release if failed. n = 5 m = 3 Coordinator Failure ? If a coordinator fails, replace it. ? But what about the lock state? ? This amounts to a resetting of the coordinator state, which could result in violating mutual exclusion. ? How many would have to fail? ? 2m n ? What is the probability of violation? Probability of Violation ? Let p be the probability of failure during some time ?t. The probability that k out of n coordinators reset is: ? ? knk ppknkP ??????????? )1(???nnmkkP2][? To violate mutual exclusion, you need at least 2mn failures. ? With node participation for 3 hours, ?t of 10 seconds, and n = 32 and m = , the probability of violation is less than 1040. A Distributed Algorithm 1. When a process wants a resource, it creates a message with the name of the resource, its process number, and the current (logical) time. 2. It then reliably sends the message to all processes and waits for an OK from everyone. 3. When a process receives a message: A. If the receiver is not accessing the resource and is not currently trying to access it, it sends back an OK message to the sender. ? “Yes, you can have it. I don’t want it, so what do I care?” B. If the receiver already has access to the resource, it simply does not reply. Instead, it queues the request. ? “Sorry, I am using it. I will save your request, and give you an OK when I am done with it.” C. If the receiver wants to access the resource as well but has not yet done so, it pares the timestamp of the ining message with the one contained in the message that it has sent everyone. The lowest one wins. 1. If the ining message has a lower timestamp, the receiver sends back an OK. – “I want it also, but you were first.” 2. If it’s own message has a lower timestamp, it queues it up. – “Sorry, I want it also, and I was first.” 4. When done using a resource, send an OK on its queue and delete them all from the queue. Two processes (0 and 2) want to access a shared resource at the same moment. Process 0 has the lowest timestamp, so it wins. When process 0 is done, it sends an OK also, so 2 can now go ahead. Step 2 Accesses resource Step 3 Accesses resource Step 1 Timestamp Ricart amp。 Agrawala algorithm Ricart amp。 Agrawala algorithm ? N points of failure ? A lot of messaging traffic ? Demonstrates that a fully distributed algorithm is possible Evaluation ? How many messages are required? More or less than centralized? ? One request and OK from everyone else, so 2(n1). ? More scalable? ? How much work per node, per lock? ? Is it better than centralized? How many points of failure? ? We have replaced a poor one with a worse one. ? Can we figure out how to handle failure? Lamport’s Mutual Exclusion ?Each process maintains request queue ? Contains mutual exclusion requests ?Requesting critical section: ? Process Pi sends request(i, Ti) to all nodes ? Places request on its own queue ? When a process Pj receives a request, it returns a timestamped ack Lamport time Lamport’s Mutual Exclusion ?Entering critical section (accessing resource): ? Pi received a message (ack or release) from every other process with a timestamp larger than Ti ? Pi’s request has the earliest timestamp in its queue ?Difference from RicartAgrawala: ? Everyone responds … always no holdback ? Process decides to go based on whether its request is the earliest in its queue Lamport’s Mutual Exclusion ?Releasing critical section: ? Remove request from its own queue ? Send a timestamped release message ? When a process receives a release message ? Removes request for that process from its queue ? This may cause its own entry have the earliest timestamp in the queue, e