Self-Stabilizing Resource Allocation Algorithms by Stéphane Devismes
Explore concurrency in self-stabilizing resource allocation algorithms and critical section code for accessing resources in a finite yet unbounded time. Learn about mutual exclusion safety and liveness in system processes, with examples of various resource allocation problems like dining philosophers and reader-writer scenarios.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Concurrency in (Self-Stabilizing) Resource Allocation Algorithms St phane Devismes
Resource Allocation Problems n processes, x resources with n x 02/09/15 Arcachon'2015
Resource Allocation Problems n processes, x resources with n x Critical Section: - code to access resources - lasts a finite, yet unbounded time 02/09/15 Arcachon'2015
Example: Mutual Exclusion Safety: At most one process executes its critical section at any time Liveness (Fairness): Each requesting process enters its critical section within finite time 02/09/15 Arcachon'2015
Many Other Resource Allocation Problems l-Exclusion k-out-of-l-Exclusion Dining Philosophers Local Mutual Exclusion Local Reader-Writer Drinking Philosophers 02/09/15 Arcachon'2015
Taxonomy Safety Local/Global #Request #Resources #ResourceType l-Exclusion k-out-of-l- Exclusion l 1 Global 1 1-k l Global 1 1 between each pair of neighbors Dining Philosophers 1 Local 1 Local 1 several Local 2 Reader-Writer 1 between each pair of neighbors Drinking Philosophers 1-?(p) Local #edges 02/09/15 Arcachon'2015
With several resources Concurrency: maximize the utilization rate of resources 02/09/15 Arcachon'2015
Example: l-Exclusion [Fischer et al, 79] l l identical copies of a non-shareable reusable resource Critical Section: code to access a resource n.b. the critical section lasts a finite, yet unbounded time Three properties: Safety Liveness Avoiding l l-deadlock (Concurrency) 02/09/15 Arcachon'2015
Example: l-Exclusion [Fischer et al, 79] Safety: At most l processes can execute their critical section concurrently 02/09/15 Arcachon'2015
Example: l-Exclusion [Fischer et al, 79] Safety: At most l processes can execute their critical section concurrently Liveness: Each requesting process enters its critical section within finite time 02/09/15 Arcachon'2015
Example: l-Exclusion [Fischer et al, 79] Safety: At most l processes can execute their critical section concurrently Liveness: Each requesting process enters its critical section within finite time Avoiding l l-deadlock: If fewer than l processes are in their critical section, then it is possible for another (requesting) process to enter its critical section, even though no process leaves its critical section in the meantime 02/09/15 Arcachon'2015
Focus on Avoiding l-Deadlock Assume l=3 02/09/15 Arcachon'2015
Focus on Avoiding l-Deadlock Assume l=3 02/09/15 Arcachon'2015
Focus on Avoiding l-Deadlock Assume l=3 02/09/15 Arcachon'2015
Focus on Avoiding l-Deadlock Assume l=3 02/09/15 Arcachon'2015
Focus on Avoiding l-Deadlock Assume l=3 02/09/15 Arcachon'2015
Focus on Avoiding l-Deadlock The Avoiding l-Deadlock property captures the concurrency in the l-Exclusion 02/09/15 Arcachon'2015
Focus on Avoiding l-Deadlock The Avoiding l-Deadlock property captures the concurrency in the l-Exclusion It is necessary to prevent degenerated solution [Fischer et al, 79] E.g., any Mutex algorithm realizes the safety and liveness of l-Exclusion 02/09/15 Arcachon'2015
Focus on Avoiding l-Deadlock The Avoiding l-Deadlock property captures the concurrency in the l-Exclusion It is necessary to prevent degenerated solution [Fischer et al, 79] E.g., any Mutex algorithm realizes the safety and liveness of l-Exclusion Yet, this property is often missed in correctness proofs of l-Exclusion algorithms! (In particular, self-stabilizing ones!) 02/09/15 Arcachon'2015
Concurrency in l-Exclusion (Avoiding l-Deadlock) Trivial: E.g., make l tokens circulating Example for l l=3 02/09/15 Arcachon'2015
Several Concurrency Properties Avoiding l-Deadlock: l-exclusion problem [Fischer et al, 79] Strict (k , l)-Liveness: k-out-of-l-exclusion problem [Datta et al, 03] Maximal-Concurrency: Committee coordination [Bonakdarpour et al, 11] Drawback: dedicated to a specific problem 02/09/15 Arcachon'2015
Generalization Maximal-Concurrency [Altisen et al, 15] 02/09/15 Arcachon'2015
Generalization Maximal-Concurrency [Altisen et al, 15] Pfree={requesting processes can obtain CS without violating safety} 02/09/15 Arcachon'2015
Generalization Maximal Concurrency [Altisen et al, 15] Pfree={requesting processes can obtain CS without violating safety} If Pfree , then A requesting process should eventually obtain CS even if no process leaves CS meanwhile Equivalently If we block processes in CS, then Pfree is eventually empty 02/09/15 Arcachon'2015
Example: k-out-of-l-Exclusion [Raynal, 91] Safety: At most l resources are used concurrently Each process can access at most k k resources simultaneously Liveness: Each requesting process enters its critical section within finite time 02/09/15 Arcachon'2015
Maximal-Concurrency in k-out-of-l-Exclusion (Strict (k , l)-Liveness) Let X = l-#used Pfree={processes requesting at most X resources} If Pfree then A requesting process should obtain CS even if no process leaves CS meanwhile 02/09/15 Arcachon'2015
Maximal-Concurrency in k-out-of-l- Exclusion impossible! [Datta et al, 03] 3? 3? 2 2? 2 2 Example: 3-out-of-4-Exclusion 3? 3? 2 2 2? 2 02/09/15 Arcachon'2015
Weaker Concurrency: (k-l)-liveness [Datta et al, 03] Let X = l-#used If every requesting process requests for at most X resources, then a requesting process should obtain CS even if no process leaves CS meanwhile 02/09/15 Arcachon'2015
Solution achieving (k-l)-liveness [Datta et al, 11] 3 types of tokens: l Resource tokens 1 pusher: Upon receiving the pusher, a node releases all its resource tokens if its request is not satisfied 1 priority token: A requesting process keeps the Priority Token while its request is unsatisfied The Priority Token cancels the effect of the Pusher Token 02/09/15 Arcachon'2015
Solution achieving (k-l)-liveness [Datta et al, 11] 4-out-of-6-Exclusion 2? 3? 3? 02/09/15 Arcachon'2015
Solution achieving (k-l)-liveness [Datta et al, 11] 4-out-of-6-Exclusion 2? 3? 3? 02/09/15 Arcachon'2015
Solution achieving (k-l)-liveness [Datta et al, 11] 4-out-of-6-Exclusion 2? 3? 3? 02/09/15 Arcachon'2015
Solution achieving (k-l)-liveness [Datta et al, 11] 4-out-of-6-Exclusion 2? 3? 3? 02/09/15 Arcachon'2015
Solution achieving (k-l)-liveness [Datta et al, 11] 4-out-of-6-Exclusion 2? 3? 3? 02/09/15 Arcachon'2015
Solution achieving (k-l)-liveness [Datta et al, 11] 4-out-of-6-Exclusion 2? 3? 3? 02/09/15 Arcachon'2015
Solution achieving (k-l)-liveness [Datta et al, 11] 4-out-of-6-Exclusion 2? 3? 02/09/15 Arcachon'2015
Maximal-Concurrency in Local Resource Allocation Problems LRA [Cantarell et al, 03] Generalization of Many Classical Problems Dining Philosophers Local Mutual Exclusion Drinking Philosophers Local Reader-Writer Local Group Mutual Exclusion ... 02/09/15 Arcachon'2015
LRA Formalism X Y: Resource types X and Y are compatible Two neighboring processes can access them concurrently 02/09/15 Arcachon'2015
LRA Formalism X Y: Resource types X and Y are compatible Two neighboring processes can access them concurrently Safety: If two neighbors and are concurrently executing their CS using X and Y, respectively, then X Y Liveness: Each requesting process enters its critical section within finite time 02/09/15 Arcachon'2015
Examples Local Mutual Exclusion 1 Resource Type: Local Reader-Writer 2 Resource Types: , , , 02/09/15 Arcachon'2015
Maximal-Concurrency in LRA impossible! [Altisen et al, 15] If there is at least one incompatibility Assume X Y 02/09/15 Arcachon'2015
Maximal-Concurrency in LRA impossible! [Altisen et al, 15] If there is at least one incompatibility Assume X Y X? 02/09/15 Arcachon'2015
Maximal-Concurrency in LRA impossible! [Altisen et al, 15] If there is at least one incompatibility Assume X Y X Fairness 02/09/15 Arcachon'2015
Maximal-Concurrency in LRA impossible! [Altisen et al, 15] If there is at least one incompatibility Assume X Y X? X Y? 02/09/15 Arcachon'2015
Maximal-Concurrency in LRA impossible! [Altisen et al, 15] If there is at least one incompatibility Assume X Y X X Y? Maximal-Concurrency 02/09/15 Arcachon'2015
Maximal-Concurrency in LRA impossible! [Altisen et al, 15] If there is at least one incompatibility Assume X Y X Y? 02/09/15 Arcachon'2015
Maximal-Concurrency in LRA impossible! [Altisen et al, 15] If there is at least one incompatibility Assume X Y X? X Y? 02/09/15 Arcachon'2015
Weaker Concurrency Maximal-Concurrency: If we block processes in CS, then Pfree is eventually empty Partial Maximal-Concurrency: If we block processes in CS, then Pfree is eventually a subset of X Strong Partial Maximal-Concurrency: Partial Maximal-Concurrency with X = all neighbors of a unique process except one. 02/09/15 Arcachon'2015
Solution implementing Strong Partial Maximal-Concurrency ID-based priority (greedy approach) Lock state: Token Circulation: 02/09/15 Arcachon'2015
Example: Reader/Writer problem 7 2 9 6 3 5 02/09/15 Arcachon'2015
