<div class="xblock xblock-public_view xblock-public_view-vertical" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Reading_9_Objectives" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Reading 9 Objectives</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_88be711a0a2a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_88be711a0a2a" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="html" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h4>Software in 6.005</h4>
<table class="table table-striped no-markdown">
<tbody>
<tr>
<th width="33%">Safe from bugs</th>
<th>Easy to understand</th>
<th>Ready for change</th>
</tr>
<tr>
<td>
Correct today and correct in the unknown future.
</td>
<td>
Communicating clearly with future programmers, including future you.
</td>
<td>
Designed to accommodate change without rewriting.
</td>
</tr>
</tbody>
</table>
<h4>Objectives</h4>
<ul>
<li>Understand how a lock is used to protect shared mutable data</li>
<li>Be able to recognize deadlock and know strategies to prevent it</li>
<li>Know the monitor pattern and be able to apply it to a data type</li>
</ul>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Synchronization" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Synchronization</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_bd047a2efbcc">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_bd047a2efbcc" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="html" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="introduction">Introduction</h2>
<div data-outline="introduction">
<p>Earlier, we <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-confinement">defined thread safety</a> for a data type or a function as <em>behaving correctly when used from multiple threads, regardless of how those threads are executed, without additional coordination</em>.</p>
<p>Here's the general principle: <strong>the correctness of a concurrent program should not depend on accidents of timing</strong>.</p>
<p>To achieve that correctness, we enumerated <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-confinement">four strategies for making code safe for concurrency</a>:</p>
<ol>
<li><a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-confinement"><strong>Confinement</strong></a>: don't share data between threads.</li>
<li><a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-immutability"><strong>Immutability</strong></a>: make the shared data immutable.</li>
<li><a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-using-threadsafe-datatypes"><strong>Use existing threadsafe data types</strong></a>: use a data type that does the coordination for you.</li>
<li><strong>Synchronization</strong>: prevent threads from accessing the shared data at the same time. This is what we use to implement a threadsafe type, but we didn't discuss it at the time.</li>
</ol>
<p>We talked about strategies 1-3 earlier. In this reading, we'll finish talking about strategy 4, using <strong>synchronization</strong> to implement your own data type that is <strong>safe for shared-memory concurrency</strong>.</p>
</div>
<h2 id="synchronization">Synchronization</h2>
<div data-outline="synchronization">
<p><strong>The correctness of a concurrent program should not depend on accidents of timing.</strong></p>
<p>Since race conditions caused by concurrent manipulation of shared mutable data are disastrous bugs — hard to discover, hard to reproduce, hard to debug — we need a way for concurrent modules that share memory to <strong>synchronize</strong> with each other.</p>
<p><strong>Locks</strong> are one synchronization technique. A lock is an abstraction that allows at most one thread to <em>own</em> it at a time.
<em>Holding a lock</em> is how one thread tells other threads: “I'm working with this thing, don't touch it right now.”</p>
<p>Locks have two operations:</p>
<ul>
<li>
<p><strong><code>acquire</code></strong> allows a thread to take ownership of a lock. If a thread tries to acquire a lock currently owned by another thread, it <em>blocks</em> until the other thread releases the lock. At that point, it will contend with any other threads that are trying to acquire the lock. At most one thread can own the lock at a time.</p>
</li>
<li>
<p><strong><code>release</code></strong> relinquishes ownership of the lock, allowing another thread to take ownership of it.</p>
</li>
</ul>
<p>Using a lock also tells the compiler and processor that you're using shared memory concurrently, so that registers and caches will be flushed out to shared storage. This avoids the problem of <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-shared-memory#reordering">reordering</a>, ensuring that the owner of a lock is always looking at up-to-date data.</p>
<h3 id="bank_account_example">Bank account example</h3>
<div data-outline="bank_account_example">
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/4bdb2a1931a66d89626697757f86cae0/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/09-shared-memory-bank-account.png" alt="shared memory model for bank accounts" width="500"></div>
<p>Our first example of shared memory concurrency was a <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-shared-memory">bank with cash machines</a>. The diagram from that example is on the right.</p>
<p>The bank has several cash machines, all of which can read and write the same account objects in memory.</p>
<p>Of course, without any coordination between concurrent reads and writes to the account balances, <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-shared-memory#interleaving">things went horribly wrong</a>.</p><span class="clearfix"></span>
<p>To solve this problem with locks, we can add a lock that protects each bank account. Now, before they can access or update an account balance, cash machines must first acquire the lock on that account.</p>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/17948c051fe5b7f47e23b865c3196f3f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/09-locks-bank-account.png" alt="synchronizing bank accounts with locks" width="500"></div>
<p>In the diagram to the right, both A and B are trying to access account 1. Suppose B acquires the lock first. Then A must wait to read and write the balance until B finishes and releases the lock. This ensures that A and B are synchronized, but another cash machine C is able to run independently on a different account (because that account is protected by a different lock).</p><span class="clearfix"></span></div>
</div>
<h2 id="deadlock">Deadlock</h2>
<div data-outline="deadlock">
<p>When used properly and carefully, locks can prevent race conditions. But then another problem rears its ugly head. Because the use of locks requires threads to wait (<code>acquire</code> blocks when another thread is holding the lock), it's possible to get into a a situation where two threads are waiting <em>for each other</em> — and hence neither can make progress.</p>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/7308e875713487bee9b5c02aaebaa948/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/09-deadlock.png" alt="bank account deadlock" width="250"></div>
<p>In the figure to the right, suppose A and B are making simultaneous transfers between two accounts in our bank.</p>
<p>A transfer between accounts needs to lock both accounts, so that money can't disappear from the system. A and B each acquire the lock on their respective “from” account: A acquires the lock on account 1, and B acquires the lock on account 2. Now, each must acquire the lock on their “to” account: so A is waiting for B to release the account 2 lock, and B is waiting for A to release the account 1 lock. Stalemate! A and B are frozen in a “deadly embrace,” and accounts are locked up.</p>
<p><strong>Deadlock</strong> occurs when concurrent modules are stuck waiting for each other to do something. A deadlock may involve more than two modules: the signal feature of deadlock is a <strong>cycle of dependencies</strong>, e.g. A is waiting for B which is waiting for C which is waiting for A. None of them can make progress.</p>
<p>You can also have deadlock without using any locks. For example, a message-passing system can experience deadlock when message buffers fill up. If a client fills up the server's buffer with requests, and then <em>blocks</em> waiting to add another request, the server may then fill up the client's buffer with results and then block itself. So the client is waiting for the server, and the server waiting for the client, and neither can make progress until the other one does. Again, deadlock ensues.</p>
<div class="handout-solo alert alert-warning">
<p>In the Java Tutorials, read:</p>
<ul>
<li><a href="http://docs.oracle.com/javase/tutorial/essential/concurrency/deadlock.html" class="alert-link">Deadlock</a> (1 page)</li>
</ul>
</div>
</div>
<h2 id="developing_a_threadsafe_abstract_data_type">Developing a threadsafe abstract data type</h2>
<div data-outline="developing_a_threadsafe_abstract_data_type">
<p>Let's see how to use synchronization to implement a threadsafe ADT.</p>
<p>Suppose we're building a multi-user editor, like Google Docs, that allows multiple people to connect to it and edit it at the same time. We'll need a mutable datatype to represent the text in the document. Here's the interface; basically it represents a string with insert and delete operations:</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/** An EditBuffer represents a threadsafe mutable string of characters
* in a text editor. */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">interface</span> <span class="hljs-title">EditBuffer</span> </span>{
<span class="hljs-comment handout-javadoc-comment">/**
* Modifies this by inserting a string.
* <span class="hljs-doctag">@param</span> pos position to insert at
(requires 0 <= pos <= current buffer length)
* <span class="hljs-doctag">@param</span> ins string to insert
*/</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">insert</span><span class="hljs-params">(<span class="hljs-keyword">int</span> pos, String ins)</span></span>;
<span class="hljs-comment handout-javadoc-comment">/**
* Modifies this by deleting a substring
* <span class="hljs-doctag">@param</span> pos starting position of substring to delete
* (requires 0 <= pos <= current buffer length)
* <span class="hljs-doctag">@param</span> len length of substring to delete
* (requires 0 <= len <= current buffer length - pos)
*/</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">delete</span><span class="hljs-params">(<span class="hljs-keyword">int</span> pos, <span class="hljs-keyword">int</span> len)</span></span>;
<span class="hljs-comment handout-javadoc-comment">/**
* <span class="hljs-doctag">@return</span> length of text sequence in this edit buffer
*/</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">length</span><span class="hljs-params">()</span></span>;
<span class="hljs-comment handout-javadoc-comment">/**
* <span class="hljs-doctag">@return</span> content of this edit buffer
*/</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">toString</span><span class="hljs-params">()</span></span>;
}</code></pre>
<p>A very simple rep for this datatype would just be a string:</p><pre><code class="language-java hljs"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">SimpleBuffer</span> <span class="hljs-keyword">implements</span> <span class="hljs-title">EditBuffer</span> </span>{
<span class="hljs-keyword">private</span> String text;
<span class="hljs-comment">// Rep invariant: </span>
<span class="hljs-comment">// text != null</span>
<span class="hljs-comment">// Abstraction function: </span>
<span class="hljs-comment">// represents the sequence text[0],...,text[text.length()-1]</span></code></pre>
<p>The downside of this rep is that every time we do an insert or delete, we have to copy the entire string into a new string. That gets expensive. Another rep we could use would be a character array, with space at the end. That's fine if the user is just typing new text at the end of the document (we don't have to copy anything), but if the user is typing at the beginning of the document, then we're copying the entire document with every keystroke.</p>
<p>A more interesting rep, which is used by many text editors in practice, is called a <em>gap buffer</em>. It's basically a character array with extra space in it, but instead of having all the extra space at the end, the extra space is a <em>gap</em> that can appear anywhere in the buffer. Whenever an insert or delete operation needs to be done, the datatype first moves the gap to the location of the operation, and then does the insert or delete. If the gap is already there, then nothing needs to be copied — an insert just consumes part of the gap, and a delete just enlarges the gap! Gap buffers are particularly well-suited to representing a string that is being edited by a user with a cursor, since inserts and deletes tend to be focused around the cursor, so the gap rarely moves.</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/** GapBuffer is a non-threadsafe EditBuffer that is optimized for
* editing with a cursor, which tends to make a sequence of inserts
* and deletes at the same place in the buffer. */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">GapBuffer</span> <span class="hljs-keyword">implements</span> <span class="hljs-title">EditBuffer</span> </span>{
<span class="hljs-keyword">private</span> <span class="hljs-keyword">char</span>[] a;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> gapStart;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> gapLength;
<span class="hljs-comment">// Rep invariant: </span>
<span class="hljs-comment">// a != null</span>
<span class="hljs-comment">// 0 <= gapStart <= a.length</span>
<span class="hljs-comment">// 0 <= gapLength <= a.length - gapStart</span>
<span class="hljs-comment">// Abstraction function: </span>
<span class="hljs-comment">// represents the sequence a[0],...,a[gapStart-1],</span>
<span class="hljs-comment">// a[gapStart+gapLength],...,a[length-1]</span></code></pre>
<p>In a multiuser scenario, we'd want multiple gaps, one for each user's cursor, but we'll use a single gap for now.</p>
<h3 id="steps_to_develop_the_datatype">Steps to develop the datatype</h3>
<div data-outline="steps_to_develop_the_datatype">
<p>Recall our recipe for designing and implementing an ADT:</p>
<div class="list-style-sub-lower-alpha">
<ol>
<li>
<p><strong>Specify.</strong> Define the operations (method signatures and specs). We did that in the <code>EditBuffer</code> interface.</p>
</li>
<li>
<p><strong>Test.</strong> Develop test cases for the operations. See <code>EditBufferTest</code> in the provided code. The test suite includes a testing strategy based on partitioning the parameter space of the operations.</p>
</li>
<li>
<p><strong>Rep.</strong> Choose a rep. We chose two of them for <code>EditBuffer</code>, and this is often a good idea:</p>
<ol>
<li>
<p><strong>Implement a simple, brute-force rep first.</strong> It's easier to write, you're more likely to get it right, and it will validate your test cases and your specification so you can fix problems in them before you move on to the harder implementation. This is why we implemented <code>SimpleBuffer</code> before moving on to <code>GapBuffer</code>. Don't throw away your simple version, either — keep it around so that you have something to test and compare against in case things go wrong with the more complex one.</p>
</li>
<li>
<p><strong>Write down the rep invariant and abstraction function, and implement <code>checkRep()</code>.</strong>
<code>checkRep()</code> asserts the rep invariant at the end of every constructor, producer, and mutator method. (It's typically not necessary to call it at the end of an observer, since the rep hasn't changed.) In fact, assertions can be very useful for testing complex implementations, so it's not a bad idea to also assert the postcondition at the end of a complex method. You'll see an example of this in <code>GapBuffer.moveGap()</code> in the code with this reading.</p>
</li>
</ol>
</li>
</ol>
</div>
<p>In all these steps, we're working entirely single-threaded at first. Multithreaded clients should be in the back of our minds at all times while we're writing specs and choosing reps (we'll see later that careful choice of operations may be necessary to avoid race conditions in the clients of your datatype). But get it working, and thoroughly tested, in a sequential, single-threaded environment first.</p>
<p>Now we're ready for the next step:</p>
<ol start="4">
<li>
<p><strong>Synchronize.</strong> Make an argument that your rep is threadsafe. Write it down explicitly as a comment in your class, right by the rep invariant, so that a maintainer knows how you designed thread safety into the class.</p>
</li>
</ol>
<p>This part of the reading is about how to do step 4. We already saw <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-how-to-make-a-safety-argument">how to make a thread safety argument</a>, but this time, we'll rely on synchronization in that argument.</p>
<p>And then the extra step we hinted at above:</p>
<ol start="5">
<li>
<p><strong>Iterate</strong>. You may find that your choice of operations makes it hard to write a threadsafe type with the guarantees clients require. You might discover this in step 1, or in step 2 when you write tests, or in steps 3 or 4 when you implement. If that's the case, go back and refine the set of operations your ADT provides.</p>
</li>
</ol>
</div>
</div>
<h2 id="locking">Locking</h2>
<div data-outline="locking">
<p>Locks are so commonly-used that Java provides them as a built-in language feature.</p>
<p>In Java, every object has a lock implicitly associated with it — a <code>String</code>, an array, an <code>ArrayList</code>, and every class you create, all of their object instances have a lock. Even a humble <code>Object</code> has a lock, so bare <code>Object</code>s are often used for explicit locking:</p><pre><code class="language-java hljs">Object lock = <span class="hljs-keyword">new</span> Object();</code></pre>
<p>You can't call <code>acquire</code> and <code>release</code> on Java's intrinsic locks, however. Instead you use the <strong><code>synchronized</code></strong> statement to acquire the lock for the duration of a statement block:</p><pre><code class="language-java hljs"><span class="hljs-keyword">synchronized</span> (lock) { <span class="hljs-comment">// thread blocks here until lock is free</span>
<span class="hljs-comment">// now this thread has the lock</span>
balance = balance + <span class="hljs-number">1</span>;
<span class="hljs-comment">// exiting the block releases the lock</span>
}</code></pre>
<p>Synchronized regions like this provide <strong>mutual exclusion</strong>: only one thread at a time can be in a synchronized region guarded by a given object's lock. In other words, you are back in sequential programming world, with only one thread running at a time, at least with respect to other synchronized regions that refer to the same object.</p>
<h3 id="locks_guard_access_to_data">Locks guard access to data</h3>
<div data-outline="locks_guard_access_to_data">
<p>Locks are used to <strong>guard</strong> a shared data variable, like the account balance shown here. If all accesses to a data variable are guarded (surrounded by a synchronized block) by the same lock object, then those accesses will be guaranteed to be atomic — uninterrupted by other threads.</p>
<p>Because every object in Java has a lock implicitly associated with it, you might think that simply owning an object's lock would prevent other threads from accessing that object.
<strong>That is not the case.</strong> Acquiring the lock associated with object <code>obj</code> using</p><pre><code class="language-java hljs"><span class="hljs-keyword">synchronized</span> (obj) { ... }</code></pre>
<p>in thread <em>t</em> does one thing and one thing only: prevents other threads from entering a <code>synchronized(obj)</code> block, until thread <em>t</em> finishes its synchronized block. That's it.</p>
<p>Locks only provide mutual exclusion with other threads that acquire the same lock. All accesses to a data variable must be guarded by the same lock. You might guard an entire collection of variables behind a single lock, but all modules must agree on which lock they will all acquire and release.</p>
</div>
</div>
<h2 id="monitor_pattern">Monitor pattern</h2>
<div data-outline="monitor_pattern">
<p>When you are writing methods of a class, the most convenient lock is the object instance itself, i.e. <code>this</code>. As a simple approach, we can guard the entire rep of a class by wrapping all accesses to the rep inside <code>synchronized (this)</code>.</p><pre class="no-markdown"><code class="java hljs">
<span class="hljs-comment">/** SimpleBuffer is a threadsafe EditBuffer with a simple rep. */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">SimpleBuffer</span> <span class="hljs-keyword">implements</span> <span class="hljs-title">EditBuffer</span> </span>{
<span class="hljs-keyword">private</span> String text;
...
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">SimpleBuffer</span><span class="hljs-params">()</span> </span>{
<b><span class="hljs-keyword">synchronized</span> (<span class="hljs-keyword">this</span>) {</b>
text = <span class="hljs-string">""</span>;
checkRep();
<b>}</b>
}
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">insert</span><span class="hljs-params">(<span class="hljs-keyword">int</span> pos, String ins)</span> </span>{
<b><span class="hljs-keyword">synchronized</span> (<span class="hljs-keyword">this</span>) {</b>
text = text.substring(<span class="hljs-number">0</span>, pos) + ins + text.substring(pos);
checkRep();
<b>}</b>
}
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">delete</span><span class="hljs-params">(<span class="hljs-keyword">int</span> pos, <span class="hljs-keyword">int</span> len)</span> </span>{
<b><span class="hljs-keyword">synchronized</span> (<span class="hljs-keyword">this</span>) {</b>
text = text.substring(<span class="hljs-number">0</span>, pos) + text.substring(pos+len);
checkRep();
<b>}</b>
}
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">length</span><span class="hljs-params">()</span> </span>{
<b><span class="hljs-keyword">synchronized</span> (<span class="hljs-keyword">this</span>) {</b>
<span class="hljs-keyword">return</span> text.length();
<b>}</b>
}
<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">toString</span><span class="hljs-params">()</span> </span>{
<b><span class="hljs-keyword">synchronized</span> (<span class="hljs-keyword">this</span>) {</b>
<span class="hljs-keyword">return</span> text;
<b>}</b>
}
}
</code></pre>
<p>Note the very careful discipline here.
<em>Every</em> method that touches the rep must be guarded with the lock — even apparently small and trivial ones like <code>length()</code> and <code>toString()</code>. This is because reads must be guarded as well as writes — if reads are left unguarded, then they may be able to see the rep in a partially-modified state.</p>
<p>This approach is called the <strong>monitor pattern</strong>. A monitor is a class whose methods are mutually exclusive, so that only one thread can be inside an instance of the class at a time.</p>
<p>Java provides some syntactic sugar for the monitor pattern. If you add the keyword <code>synchronized</code> to a method signature, then Java will act as if you wrote <code>synchronized (this)</code> around the method body. So the code below is an equivalent way to implement the synchronized <code>SimpleBuffer</code>:</p><pre class="no-markdown"><code class="java hljs">
<span class="hljs-comment">/** SimpleBuffer is a threadsafe EditBuffer with a simple rep. */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">SimpleBuffer</span> <span class="hljs-keyword">implements</span> <span class="hljs-title">EditBuffer</span> </span>{
<span class="hljs-keyword">private</span> String text;
...
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">SimpleBuffer</span><span class="hljs-params">()</span> </span>{
text = <span class="hljs-string">""</span>;
checkRep();
}
<span class="hljs-function"><span class="hljs-keyword">public</span> </span><b><span class="hljs-function"><span class="hljs-keyword">synchronized</span></span></b><span class="hljs-function"> <span class="hljs-keyword">void</span> <span class="hljs-title">insert</span><span class="hljs-params">(<span class="hljs-keyword">int</span> pos, String ins)</span> </span>{
text = text.substring(<span class="hljs-number">0</span>, pos) + ins + text.substring(pos);
checkRep();
}
<span class="hljs-function"><span class="hljs-keyword">public</span> </span><b><span class="hljs-function"><span class="hljs-keyword">synchronized</span></span></b><span class="hljs-function"> <span class="hljs-keyword">void</span> <span class="hljs-title">delete</span><span class="hljs-params">(<span class="hljs-keyword">int</span> pos, <span class="hljs-keyword">int</span> len)</span> </span>{
text = text.substring(<span class="hljs-number">0</span>, pos) + text.substring(pos+len);
checkRep();
}
<span class="hljs-function"><span class="hljs-keyword">public</span> </span><b><span class="hljs-function"><span class="hljs-keyword">synchronized</span></span></b><span class="hljs-function"> <span class="hljs-keyword">int</span> <span class="hljs-title">length</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">return</span> text.length();
}
<span class="hljs-function"><span class="hljs-keyword">public</span> </span><b><span class="hljs-function"><span class="hljs-keyword">synchronized</span></span></b><span class="hljs-function"> String <span class="hljs-title">toString</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">return</span> text;
}
}
</code></pre>
<p>Notice that the <code>SimpleBuffer</code> constructor doesn't have a <code>synchronized</code> keyword. Java actually forbids it, syntactically, because an object under construction is expected to be confined to a single thread until it has returned from its constructor. So synchronizing constructors should be unnecessary.</p>
<div class="handout-solo alert alert-warning">
<p>In the Java Tutorials, read:</p>
<ul>
<li><a href="http://docs.oracle.com/javase/tutorial/essential/concurrency/syncmeth.html" class="alert-link">Synchronized Methods</a> (1 page)</li>
<li><a href="http://docs.oracle.com/javase/tutorial/essential/concurrency/locksync.html" class="alert-link">Intrinsic Locks and Synchronization</a> (1 page)</li>
</ul>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_5371691af093" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_fff67ba8819a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_fff67ba8819a" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="html" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-synchronizing-with-locks">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-synchronizing-with-locks" data-graded="True" data-has-score="True" data-runtime-version="1" data-block-type="problem" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_09-synchronizing-with-locks" class="problems-wrapper" role="group"
aria-labelledby="09-synchronizing-with-locks-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-synchronizing-with-locks" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-synchronizing-with-locks/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="09-synchronizing-with-locks-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-synchronizing-with-locks-problem-progress" tabindex="-1">
Synchronizing with locks
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-synchronizing-with-locks-problem-progress"></div>
<div class="problem">
<div>
<p>If thread B tries to acquire a lock currently held by thread A:</p>
<p>What happens to thread A?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_09-synchronizing-with-locks_2_1">
<fieldset aria-describedby="status_09-synchronizing-with-locks_2_1">
<div class="field">
<input type="radio" name="input_09-synchronizing-with-locks_2_1" id="input_09-synchronizing-with-locks_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="09-synchronizing-with-locks_2_1-choice_0-label" for="input_09-synchronizing-with-locks_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_09-synchronizing-with-locks_2_1"> blocks until B acquires the lock
</label>
</div>
<div class="field">
<input type="radio" name="input_09-synchronizing-with-locks_2_1" id="input_09-synchronizing-with-locks_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="09-synchronizing-with-locks_2_1-choice_1-label" for="input_09-synchronizing-with-locks_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_09-synchronizing-with-locks_2_1"> blocks until B releases the lock
</label>
</div>
<div class="field">
<input type="radio" name="input_09-synchronizing-with-locks_2_1" id="input_09-synchronizing-with-locks_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="09-synchronizing-with-locks_2_1-choice_2-label" for="input_09-synchronizing-with-locks_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_09-synchronizing-with-locks_2_1"> nothing
</label>
</div>
<span id="answer_09-synchronizing-with-locks_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_09-synchronizing-with-locks_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<p>What happens to thread B?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_09-synchronizing-with-locks_3_1">
<fieldset aria-describedby="status_09-synchronizing-with-locks_3_1">
<div class="field">
<input type="radio" name="input_09-synchronizing-with-locks_3_1" id="input_09-synchronizing-with-locks_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="09-synchronizing-with-locks_3_1-choice_0-label" for="input_09-synchronizing-with-locks_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_09-synchronizing-with-locks_3_1"> blocks until A acquires the lock
</label>
</div>
<div class="field">
<input type="radio" name="input_09-synchronizing-with-locks_3_1" id="input_09-synchronizing-with-locks_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="09-synchronizing-with-locks_3_1-choice_1-label" for="input_09-synchronizing-with-locks_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_09-synchronizing-with-locks_3_1"> blocks until A releases the lock
</label>
</div>
<div class="field">
<input type="radio" name="input_09-synchronizing-with-locks_3_1" id="input_09-synchronizing-with-locks_3_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="09-synchronizing-with-locks_3_1-choice_2-label" for="input_09-synchronizing-with-locks_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_09-synchronizing-with-locks_3_1"> nothing
</label>
</div>
<span id="answer_09-synchronizing-with-locks_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_09-synchronizing-with-locks_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_09-synchronizing-with-locks_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Synchronizing with locks" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_09-synchronizing-with-locks" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_09-synchronizing-with-locks">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="09-synchronizing-with-locks-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="09-synchronizing-with-locks-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="09-synchronizing-with-locks-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-this-list-is-mine-all-mine">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-this-list-is-mine-all-mine" data-graded="True" data-has-score="True" data-runtime-version="1" data-block-type="problem" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_09-this-list-is-mine-all-mine" class="problems-wrapper" role="group"
aria-labelledby="09-this-list-is-mine-all-mine-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-this-list-is-mine-all-mine" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-this-list-is-mine-all-mine/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="09-this-list-is-mine-all-mine-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-this-list-is-mine-all-mine-problem-progress" tabindex="-1">
This list is mine, all mine
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-this-list-is-mine-all-mine-problem-progress"></div>
<div class="problem">
<div>
<p>Suppose <code>list</code> is an instance of <code>ArrayList&lt;String&gt;</code>.</p>
<p>What is true while A is in a <code>synchronized (list) { ... }</code> block?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_09-this-list-is-mine-all-mine_2_1">
<fieldset aria-describedby="status_09-this-list-is-mine-all-mine_2_1">
<div class="field">
<input type="checkbox" name="input_09-this-list-is-mine-all-mine_2_1[]" id="input_09-this-list-is-mine-all-mine_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="09-this-list-is-mine-all-mine_2_1-choice_0-label" for="input_09-this-list-is-mine-all-mine_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_09-this-list-is-mine-all-mine_2_1"> it owns the lock on <code>list</code>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_09-this-list-is-mine-all-mine_2_1[]" id="input_09-this-list-is-mine-all-mine_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="09-this-list-is-mine-all-mine_2_1-choice_1-label" for="input_09-this-list-is-mine-all-mine_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_09-this-list-is-mine-all-mine_2_1"> it does not own the lock on <code>list</code>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_09-this-list-is-mine-all-mine_2_1[]" id="input_09-this-list-is-mine-all-mine_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="09-this-list-is-mine-all-mine_2_1-choice_2-label" for="input_09-this-list-is-mine-all-mine_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_09-this-list-is-mine-all-mine_2_1"> no other thread can use observers of <code>list</code>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_09-this-list-is-mine-all-mine_2_1[]" id="input_09-this-list-is-mine-all-mine_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="09-this-list-is-mine-all-mine_2_1-choice_3-label" for="input_09-this-list-is-mine-all-mine_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_09-this-list-is-mine-all-mine_2_1"> no other thread can use mutators of <code>list</code>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_09-this-list-is-mine-all-mine_2_1[]" id="input_09-this-list-is-mine-all-mine_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="09-this-list-is-mine-all-mine_2_1-choice_4-label" for="input_09-this-list-is-mine-all-mine_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_09-this-list-is-mine-all-mine_2_1"> no other thread can acquire the lock on <code>list</code>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_09-this-list-is-mine-all-mine_2_1[]" id="input_09-this-list-is-mine-all-mine_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="09-this-list-is-mine-all-mine_2_1-choice_5-label" for="input_09-this-list-is-mine-all-mine_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_09-this-list-is-mine-all-mine_2_1"> no other thread can acquire locks on elements in <code>list</code>
</label>
</div>
<span id="answer_09-this-list-is-mine-all-mine_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_09-this-list-is-mine-all-mine_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_09-this-list-is-mine-all-mine_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="This list is mine, all mine" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_09-this-list-is-mine-all-mine" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_09-this-list-is-mine-all-mine">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="09-this-list-is-mine-all-mine-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="09-this-list-is-mine-all-mine-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="09-this-list-is-mine-all-mine-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-ok-fine-but-this-synchronized-list-is-totally-mine">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-ok-fine-but-this-synchronized-list-is-totally-mine" data-graded="True" data-has-score="True" data-runtime-version="1" data-block-type="problem" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_09-ok-fine-but-this-synchronized-list-is-totally-mine" class="problems-wrapper" role="group"
aria-labelledby="09-ok-fine-but-this-synchronized-list-is-totally-mine-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-ok-fine-but-this-synchronized-list-is-totally-mine" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-ok-fine-but-this-synchronized-list-is-totally-mine/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="09-ok-fine-but-this-synchronized-list-is-totally-mine-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-ok-fine-but-this-synchronized-list-is-totally-mine-problem-progress" tabindex="-1">
OK fine but this synchronized List is totally mine
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-ok-fine-but-this-synchronized-list-is-totally-mine-problem-progress"></div>
<div class="problem">
<div>
<p>Suppose <code>sharedList</code> is a <code>List</code> returned by <a href="http://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#synchronizedList-java.util.List-"><code>Collections.synchronizedList</code></a>.</p>
<p>It is now safe to use <code>sharedList</code> from multiple threads without acquiring any locks... except! Which of the following would require a <code>synchronized(sharedList) { ... }</code> block?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1">
<fieldset aria-describedby="status_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1">
<div class="field">
<input type="checkbox" name="input_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1[]" id="input_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1-choice_0-label" for="input_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1"> call <code>isEmpty</code>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1[]" id="input_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1-choice_1-label" for="input_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1"> call <code>add</code>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1[]" id="input_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1-choice_2-label" for="input_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1"> iterate over the list
</label>
</div>
<div class="field">
<input type="checkbox" name="input_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1[]" id="input_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1-choice_3-label" for="input_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1"> call <code>isEmpty</code>, if it returns false, call <code>remove(0)</code>
</label>
</div>
<span id="answer_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_09-ok-fine-but-this-synchronized-list-is-totally-mine_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_09-ok-fine-but-this-synchronized-list-is-totally-mine_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="OK fine but this synchronized List is totally mine" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_09-ok-fine-but-this-synchronized-list-is-totally-mine" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_09-ok-fine-but-this-synchronized-list-is-totally-mine">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="09-ok-fine-but-this-synchronized-list-is-totally-mine-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="09-ok-fine-but-this-synchronized-list-is-totally-mine-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="09-ok-fine-but-this-synchronized-list-is-totally-mine-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Thread_safety_argument_with_synchronization" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Thread safety argument with synchronization</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_5f06754dd3d1">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_5f06754dd3d1" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="html" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="thread_safety_argument_with_synchronization">Thread safety argument with synchronization</h2>
<div data-outline="thread_safety_argument_with_synchronization">
<p>Now that we're protecting <code>SimpleBuffer</code>'s rep with a lock, we can write a better thread safety argument:</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/** SimpleBuffer is a threadsafe EditBuffer with a simple rep. */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">SimpleBuffer</span> <span class="hljs-keyword">implements</span> <span class="hljs-title">EditBuffer</span> </span>{
<span class="hljs-keyword">private</span> String text;
<span class="hljs-comment">// Rep invariant: </span>
<span class="hljs-comment">// text != null</span>
<span class="hljs-comment">// Abstraction function: </span>
<span class="hljs-comment">// represents the sequence text[0],...,text[text.length()-1]</span>
<span class="hljs-comment">// Thread safety argument:</span>
<span class="hljs-comment">// all accesses to text happen within SimpleBuffer methods,</span>
<span class="hljs-comment">// which are all guarded by SimpleBuffer's lock</span></code></pre>
<p>The same argument works for <code>GapBuffer</code>, if we use the monitor pattern to synchronize all its methods.</p>
<p>Note that the encapsulation of the class, the absence of rep exposure, is very important for making this argument. If text were public:</p><pre><code class="language-java hljs"> <span class="hljs-keyword">public</span> String text;</code></pre>
<p>then clients outside <code>SimpleBuffer</code> would be able to read and write it without knowing that they should first acquire the lock, and <code>SimpleBuffer</code> would no longer be threadsafe.</p>
<h3 id="locking_discipline">Locking discipline</h3>
<div data-outline="locking_discipline">
<p>A locking discipline is a strategy for ensuring that synchronized code is threadsafe. We must satisfy two conditions:</p>
<ol>
<li>
<p>Every shared mutable variable must be guarded by some lock. The data may not be read or written except inside a synchronized block that acquires that lock.</p>
</li>
<li>
<p>If an invariant involves multiple shared mutable variables (which might even be in different objects), then all the variables involved must be guarded by the <em>same</em> lock. Once a thread acquires the lock, the invariant must be reestablished before releasing the lock.</p>
</li>
</ol>
<p>The monitor pattern as used here satisfies both rules. All the shared mutable data in the rep — which the rep invariant depends on — are guarded by the same lock.</p>
</div>
</div>
<h2 id="atomic_operations">Atomic operations</h2>
<div data-outline="atomic_operations">
<p>Consider a find-and-replace operation on the <code>EditBuffer</code> datatype:</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/** Modifies buf by replacing the first occurrence of s with t.
* If s not found in buf, then has no effect.
* <span class="hljs-doctag">@returns</span> true if and only if a replacement was made
*/</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">findReplace</span><span class="hljs-params">(EditBuffer buf, String s, String t)</span> </span>{
<span class="hljs-keyword">int</span> i = buf.toString().indexOf(s);
<span class="hljs-keyword">if</span> (i == -<span class="hljs-number">1</span>) {
<span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
}
buf.delete(i, s.length());
buf.insert(i, t);
<span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
}</code></pre>
<p>This method makes three different calls to <code>buf</code> — to convert it to a string in order to search for <code>s</code>, to delete the old text, and then to insert <code>t</code> in its place. Even though each of these calls individually is atomic, the <code>findReplace</code> method as a whole is not threadsafe, because other threads might mutate the buffer while <code>findReplace</code> is working, causing it to delete the wrong region or put the replacement back in the wrong place.</p>
<p>To prevent this, <code>findReplace</code> needs to synchronize with all other clients of <code>buf</code>.</p>
<h3 id="giving_clients_access_to_a_lock">Giving clients access to a lock</h3>
<div data-outline="giving_clients_access_to_a_lock">
<p>It's sometimes useful to make your datatype's lock available to clients, so that they can use it to implement higher-level atomic operations using your datatype.</p>
<p>So one approach to the problem with <code>findReplace</code> is to document that clients can use the <code>EditBuffer</code>'s lock to synchronize with each other:</p><pre class="no-markdown"><code class="java hljs">
<span class="hljs-comment">/** An EditBuffer represents a threadsafe mutable string of characters
* in a text editor. </span><b><span class="hljs-comment">Clients may synchronize with each other using the
* EditBuffer object itself.</span></b><span class="hljs-comment"> */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">interface</span> <span class="hljs-title">EditBuffer</span> </span>{
...
}
</code></pre>
<p>And then <code>findReplace</code> can synchronize on <code>buf</code>:</p><pre class="no-markdown"><code class="java hljs">
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">findReplace</span><span class="hljs-params">(EditBuffer buf, String s, String t)</span> </span>{
<b><span class="hljs-keyword">synchronized</span> (buf) {</b>
<span class="hljs-keyword">int</span> i = buf.toString().indexOf(s);
<span class="hljs-keyword">if</span> (i == -<span class="hljs-number">1</span>) {
<span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
}
buf.delete(i, s.length());
buf.insert(i, t);
<span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
<b>}</b>
}
</code></pre>
<p>The effect of this is to enlarge the synchronization region that the monitor pattern already put around the individual <code>toString</code>, <code>delete</code>, and <code>insert</code> methods, into a single atomic region that ensures that all three methods are executed without interference from other threads.</p>
</div>
<h3 id="sprinkling_synchronized_everywhere">Sprinkling <code>synchronized</code> everywhere?</h3>
<div data-outline="sprinkling_synchronized_everywhere">
<p>So is thread safety simply a matter of putting the <code>synchronized</code> keyword on every method in your program? Unfortunately not.</p>
<p>First, you actually don't want to synchronize methods willy-nilly. Synchronization imposes a large cost on your program. Making a synchronized method call may take significantly longer, because of the need to acquire a lock (and flush caches and communicate with other processors). Java leaves many of its mutable datatypes unsynchronized by default exactly for these performance reasons. When you don't need synchronization, don't use it.</p>
<p>Another argument for using <code>synchronized</code> in a more deliberate way is that it minimizes the scope of access to your lock. Adding <code>synchronized</code> to every method means that your lock is the object itself, and every client with a reference to your object automatically has a reference to your lock, that it can acquire and release at will. Your thread safety mechanism is therefore public and can be interfered with by clients. Contrast that with using a lock that is an object internal to your rep, and acquired appropriately and sparingly using <code>synchronized()</code> blocks.</p>
<p>Finally, it's not actually sufficient to sprinkle <code>synchronized</code> everywhere. Dropping <code>synchronized</code> onto a method without thinking means that you're acquiring a lock without thinking about which lock it is, or about whether it's the right lock for guarding the shared data access you're about to do. Suppose we had tried to solve <code>findReplace</code>'s synchronization problem simply by dropping <code>synchronized</code> onto its declaration:</p><pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">synchronized</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">findReplace</span><span class="hljs-params">(EditBuffer buf, ...)</span> </span>{</code></pre>
<p>This wouldn't do what we want. It would indeed acquire a lock — because <code>findReplace</code> is a static method, it would acquire a static lock for the whole class that <code>findReplace</code> happens to be in, rather than an instance object lock. As a result, only one thread could call <code>findReplace</code> at a time — even if other threads want to operate on <em>different</em> buffers, which should be safe, they'd still be blocked until the single lock was free. So we'd suffer a significant loss in performance, because only one user of our massive multiuser editor would be allowed to do a find-and-replace at a time, even if they're all editing different documents.</p>
<p>Worse, however, it wouldn't provide useful protection, because other code that touches the document probably wouldn't be acquiring the same lock. It wouldn't actually eliminate our race conditions.</p>
<p>The <code>synchronized</code> keyword is not a panacea. Thread safety requires a discipline — using confinement, immutability, or locks to protect shared data. And that discipline needs to be written down, or maintainers won't know what it is.</p>
</div>
</div>
<h2 id="designing_a_datatype_for_concurrency">Designing a datatype for concurrency</h2>
<div data-outline="designing_a_datatype_for_concurrency">
<p><code>findReplace</code>'s problem can be interpreted another way: that the <code>EditBuffer</code> interface really isn't that friendly to multiple simultaneous clients. It relies on integer indexes to specify insert and delete locations, which are extremely brittle to other mutations. If somebody else inserts or deletes before the index position, then the index becomes invalid.</p>
<p>So if we're designing a datatype specifically for use in a concurrent system, we need to think about providing operations that have better-defined semantics when they are interleaved. For example, it might be better to pair <code>EditBuffer</code> with a <code>Position</code> datatype representing a cursor position in the buffer, or even a <code>Selection</code> datatype representing a selected range. Once obtained, a <code>Position</code> could hold its location in the text against the wash of insertions and deletions around it, until the client was ready to use that <code>Position</code>. If some other thread deleted all the text around the <code>Position</code>, then the <code>Position</code> would be able to inform a subsequent client about what had happened (perhaps with an exception), and allow the client to decide what to do. These kinds of considerations come into play when designing a datatype for concurrency.</p>
<p>As another example, consider the <a href="http://docs.oracle.com/javase/8/docs/api/?java/util/concurrent/ConcurrentMap.html"><code>ConcurrentMap</code></a> interface in Java. This interface extends the existing <code>Map</code> interface, adding a few key methods that are commonly needed as atomic operations on a shared mutable map, e.g.:</p>
<ul>
<li><code>map.putIfAbsent(key,value)</code> is an atomic version of
<br>
<code>if ( ! map.containsKey(key)) map.put(key, value);</code></li>
<li><code>map.replace(key, value)</code> is an atomic version of
<br>
<code>if (map.containsKey(key)) map.put(key, value);</code></li>
</ul>
</div>
<h2 id="deadlock_rears_its_ugly_head">Deadlock rears its ugly head</h2>
<div data-outline="deadlock_rears_its_ugly_head">
<p>The locking approach to thread safety is powerful, but (unlike confinement and immutability) it introduces blocking into the program. Threads must sometimes wait for other threads to get out of synchronized regions before they can proceed. And blocking raises the possibility of deadlock — a very real risk, and frankly <em>far</em> more common in this setting than in message passing with blocking I/O (where we first mentioned it).</p>
<p>With locking, deadlock happens when threads acquire multiple locks at the same time, and two threads end up blocked while holding locks that they are each waiting for the other to release. The monitor pattern unfortunately makes this fairly easy to do. Here's an example.</p>
<p>Suppose we're modeling the social network of a series of books:</p><pre><code class="language-java hljs"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Wizard</span> </span>{
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> String name;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> Set<Wizard> friends;
<span class="hljs-comment">// Rep invariant:</span>
<span class="hljs-comment">// name, friends != null</span>
<span class="hljs-comment">// friend links are bidirectional: </span>
<span class="hljs-comment">// for all f in friends, f.friends contains this</span>
<span class="hljs-comment">// Concurrency argument:</span>
<span class="hljs-comment">// threadsafe by monitor pattern: all accesses to rep </span>
<span class="hljs-comment">// are guarded by this object's lock</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Wizard</span><span class="hljs-params">(String name)</span> </span>{
<span class="hljs-keyword">this</span>.name = name;
<span class="hljs-keyword">this</span>.friends = <span class="hljs-keyword">new</span> HashSet<Wizard>();
}
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">synchronized</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isFriendsWith</span><span class="hljs-params">(Wizard that)</span> </span>{
<span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.friends.contains(that);
}
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">synchronized</span> <span class="hljs-keyword">void</span> <span class="hljs-title">friend</span><span class="hljs-params">(Wizard that)</span> </span>{
<span class="hljs-keyword">if</span> (friends.add(that)) {
that.friend(<span class="hljs-keyword">this</span>);
}
}
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">synchronized</span> <span class="hljs-keyword">void</span> <span class="hljs-title">defriend</span><span class="hljs-params">(Wizard that)</span> </span>{
<span class="hljs-keyword">if</span> (friends.remove(that)) {
that.defriend(<span class="hljs-keyword">this</span>);
}
}
}</code></pre>
<p>Like Facebook, this social network is bidirectional: if <em>x</em> is friends with <em>y</em>, then <em>y</em> is friends with <em>x</em>. The <code>friend()</code> and <code>defriend()</code> methods enforce that invariant by modifying the reps of both objects, which because they use the monitor pattern means acquiring the locks to both objects as well.</p>
<p>Let's create a couple of wizards:</p><pre><code class="language-java hljs"> Wizard harry = <span class="hljs-keyword">new</span> Wizard(<span class="hljs-string">"Harry Potter"</span>);
Wizard snape = <span class="hljs-keyword">new</span> Wizard(<span class="hljs-string">"Severus Snape"</span>);</code></pre>
<p>And then think about what happens when two independent threads are repeatedly running:</p><pre><code class="language-java hljs"> <span class="hljs-comment">// thread A // thread B</span>
harry.friend(snape); snape.friend(harry);
harry.defriend(snape); snape.defriend(harry);</code></pre>
<p>We will deadlock very rapidly. Here's why. Suppose thread A is about to execute <code>harry.friend(snape)</code>, and thread B is about to execute <code>snape.friend(harry)</code>.</p>
<ul>
<li>Thread A acquires the lock on <code>harry</code> (because the friend method is synchronized).</li>
<li>Then thread B acquires the lock on <code>snape</code> (for the same reason).</li>
<li>They both update their individual reps independently, and then try to call <code>friend()</code> on the other object — which requires them to acquire the lock on the other object.</li>
</ul>
<p>So A is holding Harry and waiting for Snape, and B is holding Snape and waiting for Harry. Both threads are stuck in <code>friend()</code>, so neither one will ever manage to exit the synchronized region and release the lock to the other. This is a classic deadly embrace. The program simply stops.</p>
<p>The essence of the problem is acquiring multiple locks, and holding some of the locks while waiting for another lock to become free.</p>
<p>Notice that it is possible for thread A and thread B to interleave such that deadlock does not occur: perhaps thread A acquires and releases both locks before thread B has enough time to acquire the first one. If the locks involved in a deadlock are also involved in a race condition — and very often they are — then the deadlock will be just as difficult to reproduce or debug.</p>
<h3 id="deadlock_solution_1_lock_ordering">Deadlock solution 1: lock ordering</h3>
<div data-outline="deadlock_solution_1_lock_ordering">
<p>One way to prevent deadlock is to put an ordering on the locks that need to be acquired simultaneously, and ensuring that all code acquires the locks in that order.</p>
<p>In our social network example, we might always acquire the locks on the <code>Wizard</code> objects in alphabetical order by the wizard's name. Since thread A and thread B are both going to need the locks for Harry and Snape, they would both acquire them in that order: Harry's lock first, then Snape's. If thread A gets Harry's lock before B does, it will also get Snape's lock before B does, because B can't proceed until A releases Harry's lock again. The ordering on the locks forces an ordering on the threads acquiring them, so there's no way to produce a cycle in the waiting-for graph.</p>
<p>Here's what the code might look like:</p><pre><code class="language-java hljs"> <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">friend</span><span class="hljs-params">(Wizard that)</span> </span>{
Wizard first, second;
<span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.name.compareTo(that.name) < <span class="hljs-number">0</span>) {
first = <span class="hljs-keyword">this</span>; second = that;
} <span class="hljs-keyword">else</span> {
first = that; second = <span class="hljs-keyword">this</span>;
}
<span class="hljs-keyword">synchronized</span> (first) {
<span class="hljs-keyword">synchronized</span> (second) {
<span class="hljs-keyword">if</span> (friends.add(that)) {
that.friend(<span class="hljs-keyword">this</span>);
}
}
}
}</code></pre>
<p>(Note that the decision to order the locks alphabetically by the person's name would work fine for this book, but it wouldn't work in a real life social network. Why not? What would be better to use for lock ordering than the name?)</p>
<p>Although lock ordering is useful (particularly in code like operating system kernels), it has a number of drawbacks in practice.</p>
<ul>
<li>First, it's not modular — the code has to know about all the locks in the system, or at least in its subsystem.</li>
<li>Second, it may be difficult or impossible for the code to know exactly which of those locks it will need before it even acquires the first one. It may need to do some computation to figure it out. Think about doing a depth-first search on the social network graph, for example — how would you know which nodes need to be locked, before you've even started looking for them?</li>
</ul>
</div>
<h3 id="deadlock_solution_2_coarse-grained_locking">Deadlock solution 2: coarse-grained locking</h3>
<div data-outline="deadlock_solution_2_coarse-grained_locking">
<p>A more common approach than lock ordering, particularly for application programming (as opposed to operating system or device driver programming), is to use coarser locking — use a single lock to guard many object instances, or even a whole subsystem of a program.</p>
<p>For example, we might have a single lock for an entire social network, and have all the operations on any of its constituent parts synchronize on that lock. In the code below, all <code>Wizard</code>s belong to a <code>Castle</code>, and we just use that <code>Castle</code> object's lock to synchronize:</p><pre><code class="language-java hljs"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Wizard</span> </span>{
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> Castle castle;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> String name;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> Set<Wizard> friends;
...
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">friend</span><span class="hljs-params">(Wizard that)</span> </span>{
<span class="hljs-keyword">synchronized</span> (castle) {
<span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.friends.add(that)) {
that.friend(<span class="hljs-keyword">this</span>);
}
}
}
}</code></pre>
<p>Coarse-grained locks can have a significant performance penalty. If you guard a large pile of mutable data with a single lock, then you're giving up the ability to access any of that data concurrently. In the worst case, having a single lock protecting everything, your program might be essentially sequential — only one thread is allowed to make progress at a time.</p>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_442352a90a9b" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_fff67ba8819a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_fff67ba8819a" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="html" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-deadlock">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-deadlock" data-graded="True" data-has-score="True" data-runtime-version="1" data-block-type="problem" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_09-deadlock" class="problems-wrapper" role="group"
aria-labelledby="09-deadlock-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-deadlock" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-deadlock/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="4"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="09-deadlock-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-deadlock-problem-progress" tabindex="-1">
Deadlock
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-deadlock-problem-progress"></div>
<div class="problem">
<div>
<p>In the code below three threads 1, 2, and 3 are trying to acquire locks on objects <code>alpha</code>, <code>beta</code>, and <code>gamma</code>.</p>
<table>
<tr>
<td>Thread 1</td>
<td>Thread 2</td>
<td>Thread 3</td>
</tr>
<tr>
<td style="vertical-align: top;">
<pre>
synchronized (alpha) {
// using &#945;
// ...
}
synchronized (gamma) {
synchronized (beta) {
// using &#946; &amp; &#947;
// ...
}
}
// finished
</pre>
</td>
<td style="vertical-align: top;">
<pre>
synchronized (gamma) {
synchronized (alpha) {
synchronized (beta) {
// using &#945;, &#946; &amp; &#947;
// ...
}
}
}
// finished
</pre>
</td>
<td style="vertical-align: top;">
<pre>
synchronized (gamma) {
synchronized (alpha) {
// using &#945; &amp; &#947;
// ...
}
}
synchronized (beta) {
synchronized (gamma) {
// using &#946; &amp; &#947;
// ...
}
}
// finished
</pre>
</td>
</tr>
</table>
<p>This system is susceptible to deadlock.</p>
<p>For each of the scenarios below, determine whether the system is in deadlock if the threads are currently on the indicated lines of code.</p>
<p>
<b>Scenario A</b>
</p>
<p>Thread 1 inside <code>using alpha</code><br/>Thread 2 blocked on <code>synchronized (alpha)</code><br/>Thread 3 finished</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_09-deadlock_2_1">
<fieldset aria-describedby="status_09-deadlock_2_1">
<div class="field">
<input type="radio" name="input_09-deadlock_2_1" id="input_09-deadlock_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="09-deadlock_2_1-choice_0-label" for="input_09-deadlock_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_09-deadlock_2_1"> deadlock
</label>
</div>
<div class="field">
<input type="radio" name="input_09-deadlock_2_1" id="input_09-deadlock_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="09-deadlock_2_1-choice_1-label" for="input_09-deadlock_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_09-deadlock_2_1"> not deadlock
</label>
</div>
<span id="answer_09-deadlock_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_09-deadlock_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_09-deadlock_solution_1"/>
</div><p>
<b>Scenario B</b>
</p>
<p>Thread 1 finished<br/>Thread 2 blocked on <code>synchronized (beta)</code><br/>Thread 3 blocked on 2nd <code>synchronized (gamma)</code></p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_09-deadlock_3_1">
<fieldset aria-describedby="status_09-deadlock_3_1">
<div class="field">
<input type="radio" name="input_09-deadlock_3_1" id="input_09-deadlock_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="09-deadlock_3_1-choice_0-label" for="input_09-deadlock_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_09-deadlock_3_1"> deadlock
</label>
</div>
<div class="field">
<input type="radio" name="input_09-deadlock_3_1" id="input_09-deadlock_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="09-deadlock_3_1-choice_1-label" for="input_09-deadlock_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_09-deadlock_3_1"> not deadlock
</label>
</div>
<span id="answer_09-deadlock_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_09-deadlock_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_09-deadlock_solution_2"/>
</div><p>
<b>Scenario C</b>
</p>
<p>Thread 1 running <code>synchronized (beta)</code><br/>Thread 2 blocked on <code>synchronized (gamma)</code><br/>Thread 3 blocked on 1st <code>synchronized (gamma)</code></p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_09-deadlock_4_1">
<fieldset aria-describedby="status_09-deadlock_4_1">
<div class="field">
<input type="radio" name="input_09-deadlock_4_1" id="input_09-deadlock_4_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="09-deadlock_4_1-choice_0-label" for="input_09-deadlock_4_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_09-deadlock_4_1"> deadlock
</label>
</div>
<div class="field">
<input type="radio" name="input_09-deadlock_4_1" id="input_09-deadlock_4_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="09-deadlock_4_1-choice_1-label" for="input_09-deadlock_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_09-deadlock_4_1"> not deadlock
</label>
</div>
<span id="answer_09-deadlock_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_09-deadlock_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_09-deadlock_solution_3"/>
</div><p>
<b>Scenario D</b>
</p>
<p>Thread 1 blocked on <code>synchronized (beta)</code><br/>Thread 2 finished<br/>Thread 3 blocked on 2nd <code>synchronized (gamma)</code></p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><div class="choicegroup capa_inputtype" id="inputtype_09-deadlock_5_1">
<fieldset aria-describedby="status_09-deadlock_5_1">
<div class="field">
<input type="radio" name="input_09-deadlock_5_1" id="input_09-deadlock_5_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="09-deadlock_5_1-choice_0-label" for="input_09-deadlock_5_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_09-deadlock_5_1"> deadlock
</label>
</div>
<div class="field">
<input type="radio" name="input_09-deadlock_5_1" id="input_09-deadlock_5_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="09-deadlock_5_1-choice_1-label" for="input_09-deadlock_5_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_09-deadlock_5_1"> not deadlock
</label>
</div>
<span id="answer_09-deadlock_5_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_09-deadlock_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_09-deadlock_solution_4"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Deadlock" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_09-deadlock" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_09-deadlock">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="09-deadlock-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="09-deadlock-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="09-deadlock-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-locked-out">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-locked-out" data-graded="True" data-has-score="True" data-runtime-version="1" data-block-type="problem" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_09-locked-out" class="problems-wrapper" role="group"
aria-labelledby="09-locked-out-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-locked-out" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-locked-out/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="09-locked-out-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-locked-out-problem-progress" tabindex="-1">
Locked out
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@09-locked-out-problem-progress"></div>
<div class="problem">
<div>
<p>Examine the code again.</p>
<p>In the previous problem, we saw deadlocks involving <code>beta</code> and <code>gamma</code>.</p>
<p>What about <code>alpha</code>?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_09-locked-out_2_1">
<fieldset aria-describedby="status_09-locked-out_2_1">
<div class="field">
<input type="checkbox" name="input_09-locked-out_2_1[]" id="input_09-locked-out_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="09-locked-out_2_1-choice_0-label" for="input_09-locked-out_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_09-locked-out_2_1"> there is a possible deadlock where thread 1 owns the lock on <code>alpha</code>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_09-locked-out_2_1[]" id="input_09-locked-out_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="09-locked-out_2_1-choice_1-label" for="input_09-locked-out_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_09-locked-out_2_1"> there is a possible deadlock where thread 2 owns the lock on <code>alpha</code>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_09-locked-out_2_1[]" id="input_09-locked-out_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="09-locked-out_2_1-choice_2-label" for="input_09-locked-out_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_09-locked-out_2_1"> there is a possible deadlock where thread 3 owns the lock on <code>alpha</code>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_09-locked-out_2_1[]" id="input_09-locked-out_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="09-locked-out_2_1-choice_3-label" for="input_09-locked-out_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_09-locked-out_2_1"> there are no deadlocks involving <code>alpha</code>
</label>
</div>
<span id="answer_09-locked-out_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_09-locked-out_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_09-locked-out_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Locked out" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_09-locked-out" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_09-locked-out">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="09-locked-out-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="09-locked-out-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="09-locked-out-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Goals_of_concurrent_program_design" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Goals of concurrent program design</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_e0c4977ab816">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_e0c4977ab816" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="html" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="goals_of_concurrent_program_design">Goals of concurrent program design</h2>
<div data-outline="goals_of_concurrent_program_design">
<p>Now is a good time to pop up a level and look at what we're doing. Recall that our primary goals are to create software that is <strong>safe from bugs</strong>, <strong>easy to understand</strong>, and <strong>ready for change</strong>.</p>
<p>Building concurrent software is clearly a challenge for all three of these goals. We can break the issues into two general classes. When we ask whether a concurrent program is <em>safe from bugs</em>, we care about two properties:</p>
<ul>
<li>
<p><strong>Safety.</strong> Does the concurrent program satisfy its invariants and its specifications? Races in accessing mutable data threaten safety. Safety asks the question: can you prove that <strong>some bad thing never happens</strong>?</p>
</li>
<li>
<p><strong>Liveness.</strong> Does the program keep running and eventually do what you want, or does it get stuck somewhere waiting forever for events that will never happen? Can you prove that <strong>some good thing eventually happens</strong>?</p>
</li>
</ul>
<p>Deadlocks threaten liveness. Liveness may also require <em>fairness</em>, which means that concurrent modules are given processing capacity to make progress on their computations. Fairness is mostly a matter for the operating system's thread scheduler, but you can influence it (for good or for ill) by setting thread priorities.</p>
</div>
<h2 id="concurrency_in_practice">Concurrency in practice</h2>
<div data-outline="concurrency_in_practice">
<p>What strategies are typically followed in real programs?</p>
<ul>
<li>
<p><strong>Library data structures</strong> either use no synchronization (to offer high performance to single-threaded clients, while leaving it to multithreaded clients to add locking on top) or the monitor pattern.</p>
</li>
<li>
<p><strong>Mutable data structures with many parts</strong> typically use either coarse-grained locking or thread confinement. Most graphical user interface toolkits follow one of these approaches, because a graphical user interface is basically a big mutable tree of mutable objects. Java Swing, the graphical user interface toolkit, uses thread confinement. Only a single dedicated thread is allowed to access Swing's tree. Other threads have to pass messages to that dedicated thread in order to access the tree.</p>
</li>
<li>
<p><strong>Search</strong> often uses immutable datatypes. Our <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-boolean-formulas">Boolean formula satisfiability search</a> would be easy to make multithreaded, because all the datatypes involved were immutable. There would be no risk of either races or deadlocks.</p>
</li>
<li>
<p><strong>Operating systems</strong> often use fine-grained locks in order to get high performance, and use lock ordering to deal with deadlock problems.</p>
</li>
</ul>
<p>We've omitted one important approach to mutable shared data because it's outside the scope of this course, but it's worth mentioning: <strong>a database</strong>. Database systems are widely used for distributed client/server systems like web applications. Databases avoid race conditions using <em>transactions</em>, which are similar to synchronized regions in that their effects are atomic, but they don't have to acquire locks, though a transaction may fail and be rolled back if it turns out that a race occurred. Databases can also manage locks, and handle locking order automatically.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Reading_9_Summary" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Reading 9 Summary</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_ef0618bbff20">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-request-token="a38501d0e99811efb7c60e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_ef0618bbff20" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="html" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="summary">Summary</h2>
<div data-outline="summary">
<p>Producing a concurrent program that is safe from bugs, easy to understand, and ready for change requires careful thinking. Heisenbugs will skitter away as soon as you try to pin them down, so debugging simply isn't an effective way to achieve correct threadsafe code. And threads can interleave their operations in so many different ways that you will never be able to test even a small fraction of all possible executions.</p>
<ul>
<li>
<p>Make thread safety arguments about your datatypes, and document them in the code.</p>
</li>
<li>
<p>Acquiring a lock allows a thread to have exclusive access to the data guarded by that lock, forcing other threads to block — as long as those threads are also trying to acquire that same lock.</p>
</li>
<li>
<p>The <em>monitor pattern</em> guards the rep of a datatype with a single lock that is acquired by every method.</p>
</li>
<li>
<p>Blocking caused by acquiring multiple locks creates the possibility of deadlock.</p>
</li>
</ul>
</div>
<div class="license">This reading was collaboratively authored with contributions from: Saman Amarasinghe, Adam Chlipala, Srini Devadas, Michael Ernst, Max Goldman, John Guttag, Daniel Jackson, Rob Miller, Martin Rinard, and Armando Solar-Lezama. This work is licensed under <a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/">CC BY-SA 4.0</a>.</div>
</div>
</div>
</div>
</div>