【正文】 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, en。 Partial Ordering ?Causality ? If a?b then event a can affect event b ?Concurrency ? If neither a ? b nor b ? a then one event cannot affect the other ?Partial Ordering ? Causal events are sequenced ?Total Ordering ? All events are sequenced Outline ?Clock Synchronization ?Mutual Exclusion ?Election Algorithms Mutual Exclusion ? Overview ? A Centralized Algorithm ? A Decentralized Algorithm ? A Distributed Algorithm ? A Token Ring Algorithm ? A Comparison of the Four Algorithm Terminology ? In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. ? Mutual exclusion (ME, often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of a mon resource, such as a global variable, by pieces of puter code called critical sections. Applications use ME ? Replicated databases ? Protocols that control access to replicated data and ensure data consistency in case of work partitioning are called replica control protocols. ? A transaction (an access request to data) is the basic unit of user putation in a database. ? All replica control protocols require that mutual exclusion must be guaranteed between two write operations and a read and write operation. ? Distributed shared memory (DSM) is an abstraction used for sharing data between puters that do not share physical memory. Performance Metrics of DME Algorithm ? Message Complexity (MC) ? The number of messages exchanged by a process per CS entry. ? Synchronization Delay (SD) ? the average time delay in granting CS, which is the period of time between the instant a site invokes mutual exclusion and the instant when it enters CS. ? A good DME algorithm must be ? safe (it shall ensure mutual exclusion), live (the system should make progress towards the execution of CS and a deadlock situation shall not occur) and fair (it shall not be biased against or in favor of a node and each request shall eventually be satisfied). ? It should have low MC and SD. ? High fault tolerance and availability add to the qualities of a good DME algorithm. Mutual Exclusion ? Prevent simultaneous access to a resource ? Two basic kinds: ? Permission based ? 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 response