📄 mutex.htm

📁 A tutorial on RT-Linux
💻 HTM
字号:
<html><head><title>DATA CONSISTENCY TECHNIQUES</title><link rel="stylesheet" type="text/css" href="style.css"></head><body><a href="./ex06_shm.htm">[previous]</a><a href="./tutorial.htm#index">[index]</a><a href="./ex07_sem.htm">[next]</a><h1>Data Consistency Techniques</h1>Any shared data structures that are not operated on as one piece by the CPUneed to be protected by data consistency techniques. Here are the safedata types, from the Intel IA-32 manual <a href="./references.htm#INT3">[INT3]</a>:<ul><p>&#34;The Pentium 4, Intel Xeon, P6family, Pentium, and Intel486 processors guarantee that the followingbasic memory operations will always be carried out atomically: reading or writing a byte, reading or writing a word aligned on a 16-bitboundary, and reading or writing a doubleword aligned on a 32-bitboundary.<p>&#34;The Pentium 4, Intel Xeon, and P6 family, and Pentiumprocessors guarantee that the following additional memory operationswill always be carried out atomically: reading or writing a quadwordaligned on a 64-bit boundary.&#34;</ul>So, if you're writing types char, int, and long int on anything froma 486 to a Pentium, you're OK. On Pentiums (not 486s), long long intsare OK also (e.g., the RTIME time count type in RTAI).<p>Numerous methods exists for ensuring data consistency. To motivate thediscussion, consider this simple (and wrong) algorithm for allocatinga token that signifies permission to modify shared data:<pre>int token = 0;A: if (token == 0) { /* no one has it */B:   token = 1; /* now I have it */     /* modify shared data here */     token = 0; /* now I give it up */   } else {     /* I didn't get it; I'll try again */   }</pre>Why is this wrong?<p>Suppose token is 0 (unclaimed), and Process 1(P1) executes line A and gets to line B. At this point, P1 can beswapped out, and P2 can run.Now, P2 executes its line A, sees thattoken is still 0, and gets to its line B. At this point, P1 and P2will set token to 1, but it's too late: both think they have thetoken. This technique will not work.<p>Brief explanations of some techniques that do work are given below. See <ahref="./references.htm#TAN">[TAN]</a> or <ahref="./references.htm#DEI">[DEI]</a>for a textbook treatment.<h2>Two-Process Mutual Exclusion: Dekker's- and Peterson's Algorithms</h2><ul><li>These algorithms implement two-process mutual exclusion by setting andpolling three sharedboolean flags, a technique known as a "spinlock". No special hardwareinstructions are required.<li>Dekker's algorithm(c. 1965) is widely known and mentioned here for completeness; Peterson's algorithm (c. 1981) is a simpler and more efficientimprovement. <li>Here is Peterson's Algorithm for two processes, p0 andp1:<pre>int favored_process = 0;int p0_wants_to_enter = 0;int p1_wants_to_enter = 0;/* how p0 gets the resource */p0_wants_to_enter = 1;favored_process = 1;while (p1_wants_to_enter && favored_process == 1) /* spinlock */ ;/* operate on shared resource here */p0_wants_to_enter = 0; /* give up the resource *//* how p1 gets the resource */p1_wants_to_enter = 1;favored_process = 0;while (p0_wants_to_enter && favored_process == 0) /* spinlock */ ;/* operate on shared resource here */p1_wants_to_enter = 0; /* give up the resource */</pre><li>Peterson's and Dekker's Algorithms do not suffer from"indefinite postponement," a condition where one of the processes maywait arbitrarily long to acquire the resource if the other repeatedlytakes and gives it.<li>The drawback of these algorithms is their applicability to two-processmutual exclusion only. Algorithms exist for N-process mutual exclusionand no indefinite postponement; see <ahref="./references.htm#DEI">[DEI]</a> for details.</ul><h2>N-Process Mutual Exclusion using Hardware</h2><ul><li>The problem with the first (wrong) technique is that the test ofthe flag for0 and the setting of the flag to 1 can be split. If it wereindivisible ("atomic"), that technique would work.<li>You can make any sequence of instructions atomic by disablingthe tasking interrupt before the sequence, and enabling it againafter. This is generally regarded as bad practice, since it isless efficient than other hardware techniques, such as "test and set".<li>Test and set is implemented on the Intel IA-32 architecture (e.g.,the Pentium) as the XCHG (exchange) instruction <a href="./references.htm#INT2B">[INT2B]</a>, i.e., correspondingto the hypothetical C language interface<pre>value = 1;xchg(&flag, &value);</pre>After the 'xchg()' call, 'value' is what 'flag' was, and 'flag' is 1.If 'value' becomes 0, this means that 'flag' was 0, the caller now hasthe resource, and the flag is set to 1 to block others. If 'value'remains 1, this means that 'flag' was 1, and the caller does not havethe resource (setting a 1 flag to 1 does no harm). <li>Both disabling interrupts and hardware test-and-set suffer frompotential indefinite postponement, since no record of waitingprocesses is maintained. </ul><h2>N-Reader, 1-Writer Mutual Exclusion using Head/Tail Flags</h2><ul><li>Head/tail flags are a pair of flags, typically a byte each,that surround a data structure, e.g.,<pre>struct mystruct {  char head;  int data[1000];  char tail;};</pre><li>This technique only works if the writer can't be interrupted bythe readers, or vice-versa.In RT Linux, this is true if the writer is an RT task andthe readers are Linux processes, vice-versa, or if both are RTtasks. It won't work if they're all Linux processes.<li>The writer increments the head, writes some or all of the data, thensets the tail equal to the head. This can be done directly in theshared memory, or in a local copy that is written out fully whenfinished ("buffering"), depending upon which would occupy the sharedmemory for the least time.<li>The reader compares thehead and tail. If equal, the data in between is consistent. If not,the data is being acted upon and may be inconsistent.<li>If the reader can be interrupted by the writer, the shared memoryshould first be copied to a local data structure. Comparing the headand tail directly from shared memory at one instant does notguarantee that subsequent direct reading of the shared data will beuninterrupted.<li>While head/tail flags do not provide mutual exclusion, they doallow the detection of inconsistent data.<li>This technique can lead to <i>indefinite postponement</i> of thereader if the write frequency is high.In this case, the reader never gets a consistentread. The reader can detect this condition, however.<li>Because there is no blocking, this technique can be appliedbetween Linux processes and RT tasks. We show this in the example.</ul><h2>Other Techniques</h2>There are numerous other techniques for data consistency and mutualexclusion.<ul><li><i>Semaphores</i> are data structures that support give/takesemantics similar to test-and-set (in fact semaphores are oftenimplemented using test-and-set). They support N-process mutualexclusion, and can be used to implement multi-reader, multi-writersystems. Semaphores can be binary or counting, the latter with acumulative 'give' count, allowing as many subsequent takes beforeblocking. Semaphores between real-time processes are discussed in <ahref="./ex07_sem.htm">Example 7, RTL Semaphores</a>.<li><i>Mutexes</i> are like binary semaphores, but add the concept ofownership; that is, only the process who took the mutex can giveit back.<li><i>Monitors</i> and <i>Condition Variables</i> are generalizedmutexes that allow the taking of a mutex, checking of condition, andatomic release-and-wait until the condition is satisfied.<li><i>Reader/Writer Locks</i> block any writer from changing aresource if one or more readers are looking at it, and blocks allreaders from looking at a resource if a writer is changing it.<li>There is a rich literature on mutual exclusion. See <a href="./references.htm#TAN">[TAN]</a>, <ahref="./references.htm#DEI">[DEI]</a>, <ahref="./references.htm#LAM1">[LAM1]</a>, and <ahref="./references.htm#LAM2">[LAM2]</a> for more information.</ul><hr><a href="./ex07_sem.htm">Next: Example 7, RTL Semaphores</a><p><a href="./ex06_shm.htm">Back: Example 6, Shared Memory</a></body></html>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -