|
In concurrent computing, liveness refers to a set of properties of concurrent systems, that require a system to make progress despite the fact that its concurrently executing components ("processes") may have to "take turns" in critical sections, parts of the program that cannot be simultaneously run by multiple processes. Liveness guarantees are important properties in operating systems and distributed systems. A liveness property cannot be violated in a finite execution of a distributed system because the "good" event might only theoretically occur at some time after execution ends. Eventual consistency is an example of a liveness property. All properties can be expressed as the intersection of safety and liveness properties and most non-trivial properties are a mix of the two. ==Forms of liveness== Several forms of liveness are recognized. The following ones are defined in terms of a multi-process system that has a critical section, protected by some mutual exclusion (mutex) device. All processes are assumed to correctly use the mutex; progress is defined as finishing execution of the critical section. * Freedom from deadlock is a form of liveness, although a weak one. Consider a system with multiple processes and a single critical section, protected by some mutual exclusion device. Such a system is said to be deadlock-free if, when a group of processes is competing for access to the critical section at some point in time, then ''some'' process eventually makes progress at a later point in time. That process need not belong to the aforementioned group; it might have gained access at an earlier or even later moment. * Freedom from starvation (or "finite bypass") is a stronger liveness guarantee than deadlock-freedom. It states that ''all'' processes vying for access to the critical region eventually make progress. Any starvation-free system is also deadlock-free. * Stronger still is the requirement of bounded bypass. This means that, if processes are competing for access to the critical region, then each process makes progress after being bypassed at most times by other processes for some function . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「liveness」の詳細全文を読む スポンサード リンク
|