| 翻訳と辞書 |
Mutual exclusion
In computer science, mutual exclusion refers to the requirement of ensuring that no two concurrent processes are in their critical section at the same time; it is a basic requirement in concurrency control, to prevent race conditions. Here, a critical section refers to a period when the process accesses a shared resource, such as shared memory. The requirement of mutual exclusion was first identified and solved by Edsger W. Dijkstra in his seminal 1965 paper titled ''Solution of a problem in concurrent programming control'',〔Taubenfeld, (The Black-White Bakery Algorithm ). In Proc. Distributed Computing, 18th international conference, DISC 2004. Vol 18, 56-70, 2004〕 and is credited as the first topic in the study of concurrent algorithms.
A simple example of why mutual exclusion is important in practice can be visualized using a singly linked list (See Figure 1). In such a linked list, the removal of a node is done by changing the "next" pointer of the preceding node to point to the subsequent node (e.g., if node ''i'' is being removed then the "next" pointer of node ''i'' − 1 will be changed to point to node ''i'' + 1). In an execution where such a linked list is being shared between multiple processes, two processes may attempt to remove two different nodes simultaneously, resulting in the following problem: let nodes ''i'' and ''i'' + 1 be the nodes to be removed; furthermore, let neither of them be the head nor the tail; the next pointer of node ''i'' − 1 will be changed to point to node ''i'' + 1 and the next pointer of node ''i'' will be changed to point to node ''i'' + 2. Although both removal operations complete successfully, node ''i'' + 1 remains in the list since ''i'' − 1 was made to point to ''i'' + 1, skipping node ''i'' (which was the node that reflected the removal of ''i'' + 1 by having its next pointer set to ''i'' + 2). This can be seen in Figure 1. This problem (normally called a race condition) can be avoided by using the requirement of mutual exclusion to ensure that simultaneous updates to the same part of the list cannot occur.
==Enforcing mutual exclusion==
There are both software and hardware solutions for enforcing mutual exclusion. Some different solutions are discussed below.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Mutual exclusion」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|