Race conditions & mutual exclusion.html (8265B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.6 (457297)"/><meta name="altitude" content="-1.633376002311707"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-12-03 16:07:23 +0000"/><meta name="latitude" content="52.33331298828125"/><meta name="longitude" content="4.866615317820796"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-12-14 16:34:17 +0000"/><title>Race conditions & mutual exclusion</title></head><body><div>programs can race each other and come to wrong conclusions.</div><div style="-en-paragraph:true;"><span style="-en-paragraph:true;"><br/></span></div><div style="-en-paragraph:true;"><span style="-en-paragraph:true;"><b>Mutual exclusion</b></span></div><div>critical region: a code region with access to shared resources 4 </div><div><br/></div><div>the conditions for mutual exclusion:</div><ol><li><div>no two processes can be simultaneously in their critical regions</div></li><li><div>no assumptions can be made about speed/number of CPUs</div></li><li><div>no process running outside critical region may block others</div></li><li><div>no process should have to wait forever to enter critical region</div></li></ol><div><br/></div><div>non-solutions</div><ul><li><div>disable interrupts (disable reallocation of CPU). if you have multiple processors, shit gets fucked.</div></li><li><div>lock variables (guard critical regions with booleans). so now the race is on the lock variables, great job dude.</div></li><li><div>strict alternation (be nice and take turns). doesn’t allow processes to enter critical regions twice in a row, and a process outside the critical region can block another one.</div></li></ul><div><br/></div><div>Peterson's algorithm<br/></div><ul><li><div>software solution</div></li><li><div>spin lock in the while loop</div></li></ul><div><br/></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, "Courier New", monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902);-en-codeblock:true;"><div>#define N 2</div><div>int turn;</div><div>int interested[N];</div><div><br/></div><div>void enter_region(int process){</div><div> int other = 1 - process;</div><div> interested[process] = TRUE;</div><div> turn = process;</div><div> while(turn==process && interested[other]==TRUE);</div><div>}</div><div><br/></div><div>void leave_region(int process) { </div><div> interested[process] = FALSE;</div><div>}</div></div><div><br/></div><div>TSL instruction 5 </div><ul><li><div>hardware-assisted solution to mutual exclusion problem</div></li><li><div>atomic test and set of a memory value</div></li><li><div>spin until LOCK is acquired</div></li></ul><div><br/></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, "Courier New", monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902);-en-codeblock:true;"><div>enter_region:</div><div><span style="font-size: 12px; font-family: Monaco;">TSL REGISTER, LOCK | copy LOCK to register, set LOCK to 1</span></div><div><span style="font-size: 12px; font-family: Monaco;">CMP REGISTER, #0 | was LOCK zero?</span></div><div><span style="font-size: 12px; font-family: Monaco;">JNE ENTER_REGION | if it was non-zero LOCK was set, so loop</span></div><div><span style="font-size: 12px; font-family: Monaco;">RET | return to caller; critical region entered</span></div><div><br/></div><div><span style="font-size: 12px; font-family: Monaco;">leave_region:</span></div><div><span style="font-size: 12px; font-family: Monaco;">MOVE LOCK, #0 | store a 0 in LOCK</span></div><div><span style="font-size: 12px; font-family: Monaco;">RET | return to caller</span></div></div><div 6 /><div style="-en-paragraph:true;"><span style="-en-paragraph:true;"><span style="font-weight: bold;"><br/></span></span></div><div style="-en-paragraph:true;"><span style="-en-paragraph:true;"><span style="font-weight: bold;">Avoiding busy waiting</span></span></div><div>so far, CPU busy waits until it can enter the critical region (spin lock).</div><div>so, let process waiting return CPU to scheduler voluntarily.</div><div><br/></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, "Courier New", monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902);-en-codeblock:true;"><div>void sleep() {</div><div><span> set own state to BLOCKED;</span><br/></div><div><span><span> give CPU to scheduler;</span><br/></span></div><div><span><span>}</span></span></div><div><span><span><br/></span></span></div><div><span><span>void wakeup(process) {</span></span></div><div><span><span><span> set state of process to READY;</span><br/></span></span></div><div><span><span><span><span> give CPU to scheduler;</span><br/></span></span></span></div><div><span><span><span><span>}</span></span></span></span></div></div><div><br/></div><div>Producer-consumer</div><ul><li><div>producer sleeps when buff is full</div></li><li><div>consumer sleeps when buff is empty</div></li></ul><div style="margin-left: 40px;"><br/></div><div style="margin-left: 40px;"><img src="Race%20conditions%20&%20mutual%20exclusion.resources/screenshot_1.png" height="329" width="681"/></div><div style="margin-left: 40px;"><br/></div><ul><li><div>problem: wake up process may get lost. only wake up producer when count is N-1, but producer sleeps when count is N.</div></li></ul><div><br/></div><div>Semaphores</div><ul><li><div>introduce sema integer type with operations:</div></li><ul><li><div>down: if sema ≤ 0, block calling process. <font face="Courier New">sema--</font> otherwise.</div></li><li><div>up: if there is process blocking on sema, wake it up. sema++ otherwise.</div></li></ul><li><div>OS guarantees that all the operations are atomic (happening instantaneously) by design — disable interrupts on single processors, spin locking on multiprocessors.</div></li><li><div>mutex (mutual exclusion) variable serialises access to shared buffer</div></li></ul><div style="margin-left: 40px;"><br/></div><div style="margin-left: 40px;"><img src="Race%20conditions%20&%20mutual%20exclusion.resources/screenshot_2.png" height="563" width="998"/></div><div><br/></div><div>Monitors 7 </div><ul><li><div>semaphores introduce chaos in programs (gotta set all them bits)</div></li><li><div>monitors: serialise procedure calls on a module, use condition vars to wait/signal processes</div></li><li><div>but this needs dedicated language support</div></li></ul><div><br/></div><div style="margin-left: 40px;"><img src="Race%20conditions%20&%20mutual%20exclusion.resources/screenshot.png" height="521" width="925"/><br/></div><div style="-en-paragraph:true;"><span style="-en-paragraph:true;"><br/></span></div><div style="-en-paragraph:true;"><span style="-en-paragraph:true;"><span style="font-weight: bold;">Message passing: solution to process sync and communication</span></span></div><ul><li><div>processes interact by sending & receiving messages.</div></li><li><div>most common in multiserver OS designs</div></li><li><div>issues — mem copying vs register passing (efficiency), mailboxes vs rendezvous<br/></div></li></ul><div><br/></div></body></html>