<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical-thread-safety">
<h2 class="hd hd-2 unit-title">Reading 6 Objectives</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_a3d89824ceeb">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_a3d89824ceeb">
<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>
<p>Recall race conditions: multiple threads sharing the same mutable variable without coordinating what they're doing. This is unsafe, because the correctness of the program may depend on accidents of timing of their low-level operations.</p>
<p>There are basically four ways to make variable access safe in shared-memory concurrency:</p>
<ul>
<li><strong>Confinement.</strong> Don't share the variable between threads. This idea is called confinement, and we'll explore it today.</li>
<li><strong>Immutability.</strong> Make the shared data immutable. We've talked a lot about immutability already, but there are some additional constraints for concurrent programming that we'll talk about in this reading.</li>
<li><strong>Threadsafe data type.</strong> Encapsulate the shared data in an existing threadsafe data type that does the coordination for you. We'll talk about that today.</li>
<li><strong>Synchronization.</strong> Use synchronization to keep the threads from accessing the variable at the same time. Synchronization is what you need to build your own threadsafe data type.</li>
</ul>
<p>We'll talk about the first three ways in this reading, along with how to make an argument that your code is threadsafe using those three ideas. We'll talk about the fourth approach, synchronization, in a later reading.</p>
<p>The material in this reading is inspired by an excellent book: Brian Goetz et al., <em><a href="http://jcip.net/">Java Concurrency in Practice</a></em>, Addison-Wesley, 2006.</p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical-confinement">
<h2 class="hd hd-2 unit-title">Strategy 1: Confinement</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_1207c8177380">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_1207c8177380">
<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="https://ajax.googleapis.com/ajax/libs/jquery/3.1.1/jquery.min.js"></script>
<script>
$(function() {
// create a hover interaction
// will either update an attribute of a target element inside this element,
// or show only targets matching an indexed selector, as the user hovers over
// elements matching a selector
function createHoverInteraction() {
var elt = $(this);
var selector = elt.data('selector');
var target = $(elt.data('target'), elt);
var pick = elt.data('pick');
if (pick) {
var updateTarget = function() {
var filter = pick.replace(/INDEX/g, $(this).index()+1);
target.hide().filter(filter).show();
}
} else {
var attr = elt.data('attr');
var template = elt.data('template');
var updateTarget = function() {
var value = template.replace(/INDEX/g, $(this).index());
target.attr(attr, value);
}
}
var update = function() {
$(this).addClass('highlighted').siblings().removeClass('highlighted');
updateTarget.apply(this);
}
$(selector).addClass('hover-figure-select').on('click mouseenter', update);
update.apply($(selector).first());
}
// wire up interactive elements
$('.hover-figure').each(createHoverInteraction);
});
</script>
<style>
.hover-figure-select {
cursor: default;
}
.highlighted {
background: #fcf8e3;
box-shadow: 0 0 0 4px #fcf8e3;
}
</style>
-->
<h2 id="what_threadsafe_means">What Threadsafe Means</h2>
<div data-outline="what_threadsafe_means">
<p>A data type or static method is <em>threadsafe</em> if it behaves correctly when used from multiple threads, regardless of how those threads are executed, and without demanding additional coordination from the calling code.</p>
<ul>
<li>“behaves correctly” means satisfying its specification and preserving its rep invariant;</li>
<li>“regardless of how threads are executed” means threads might be on multiple processors or timesliced on the same processor;</li>
<li>“without additional coordination” means that the data type can't put preconditions on its caller related to timing, like “you can't call <code>get()</code> while <code>set()</code> is in progress.”</li>
</ul>
<p>Remember <a href="http://docs.oracle.com/javase/8/docs/api/?java/util/Iterator.html"><code>Iterator</code></a>? It's not threadsafe. <code>Iterator</code>'s specification says that you can't modify a collection at the same time as you're iterating over it. That's a timing-related precondition put on the caller, and <code>Iterator</code> makes no guarantee to behave correctly if you violate it.</p>
</div>
<h2 id="strategy_1_confinement">Strategy 1: Confinement</h2>
<div data-outline="strategy_1_confinement">
<p>Our first way of achieving thread safety is <em>confinement</em>. Thread confinement is a simple idea: you avoid races on mutable data by keeping that data confined to a single thread. Don't give any other threads the ability to read or write the data directly.</p>
<p>Since shared mutable data is the root cause of a race condition, confinement solves it by <em>not sharing</em> the mutable data.</p>
<p>Local variables are always thread confined. A local variable is stored in the stack, and each thread has its own stack. There may be multiple invocations of a method running at a time (in different threads or even at different levels of a single thread's stack, if the method is recursive), but each of those invocations has its own private copy of the variable, so the variable itself is confined.</p>
<p>But be careful — the variable is thread confined, but if it's an object reference, you also need to check the object it points to. If the object is mutable, then we want to check that the object is confined as well — there can't be references to it that are reachable from any other thread.</p>
<p>Confinement is what makes the accesses to <code>n</code>, <code>i</code>, and <code>result</code> safe in code like this:</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">Factorial</span> </span>{
<span class="hljs-comment handout-javadoc-comment">/**
* Computes n! and prints it on standard output.
* <span class="hljs-doctag">@param</span> n must be >= 0
*/</span>
<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">computeFact</span><span class="hljs-params">(<span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> n)</span> </span>{
BigInteger result = <span class="hljs-keyword">new</span> BigInteger(<span class="hljs-string">"1"</span>);
<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i <= n; ++i) {
System.out.println(<span class="hljs-string">"working on fact "</span> + n);
result = result.multiply(<span class="hljs-keyword">new</span> BigInteger(String.valueOf(i)));
}
System.out.println(<span class="hljs-string">"fact("</span> + n + <span class="hljs-string">") = "</span> + result);
}
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>{
<span class="hljs-keyword">new</span> Thread(<span class="hljs-keyword">new</span> Runnable() { <span class="hljs-comment">// create a thread using an</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">run</span><span class="hljs-params">()</span> </span>{ <span class="hljs-comment">// anonymous Runnable</span>
computeFact(<span class="hljs-number">99</span>);
}
}).start();
computeFact(<span class="hljs-number">100</span>);
}
}</code></pre>
<p>This code starts the thread for <code>computeFact(99)</code> with an <a href="https://docs.oracle.com/javase/tutorial/java/javaOO/anonymousclasses.html">anonymous</a> <code>Runnable</code>, a common idiom <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-anonymous-class">discussed in the previous reading</a>.</p>
<style>
table.figure-right td {
vertical-align: top;
}
table.figure-right td:first-child {
border-right: 1px solid #333;
padding-right: 1em;
}
table.figure-right td:last-child {
padding-left: 1em;
}
</style>
<!--
<p>Let's look at snapshot diagrams for this code. Hover or tap on each step to update the diagram:</p>
<table id="confinement-example" class="figure-right pull-margin">
<tbody>
<tr>
<td>
<ol>
<li class="highlighted">
<p>When we start the program, we start with one thread running <code>main</code>.</p>
</li>
<li>
<p><code>main</code> creates a second thread using the anonymous <code>Runnable</code> idiom, and starts that thread.</p>
</li>
<li>
<p>At this point, we have two concurrent threads of execution. Their interleaving is unknown! But one <em>possibility</em> for the next thing that happens is that thread 1 enters <code>computeFact</code>.</p>
</li>
<li>
<p>Then, the next thing that <em>might</em> happen is that thread 2 also enters <code>computeFact</code>.</p>
<p>At this point, we see how <strong>confinement</strong> helps with thread safety: each execution of <code>computeFact</code> has its own <code>n</code>, <code>i</code>, and <code>result</code> variables. None of the objects they point to are mutable; if they were mutable, we would need to check that the objects are not aliased from other threads.</p>
</li>
<li>
<p>The <code>computeFact</code> computations proceed independently, updating their respective variables.</p>
</li>
</ol>
</td>
<td>
<div class="hover-figure no-markdown" data-selector="#confinement-example li" data-target="img" data-attr="src" data-template="/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/06-confinement-INDEX.png"><img style="max-width:425px" src="/assets/courseware/v1/94c713f1d8eec893767e52dad8e938cb/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/06-confinement-0.png"></div>
</td>
</tr>
</tbody>
</table>
-->
<h3 id="avoid_global_variables">Avoid Global Variables</h3>
<div data-outline="avoid_global_variables">
<p>Unlike local variables, static variables are not automatically thread confined.</p>
<p>If you have static variables in your program, then you have to make an argument that only one thread will ever use them, and you have to document that fact clearly. Better, you should eliminate the static variables entirely.</p>
<p>Here's an example:</p><pre><code class="language-java hljs"><span class="hljs-comment">// This class has a race condition in it.</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">PinballSimulator</span> </span>{
<span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> PinballSimulator simulator = <span class="hljs-keyword">null</span>;
<span class="hljs-comment">// invariant: there should never be more than one PinballSimulator</span>
<span class="hljs-comment">// object created</span>
<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-title">PinballSimulator</span><span class="hljs-params">()</span> </span>{
System.out.println(<span class="hljs-string">"created a PinballSimulator object"</span>);
}
<span class="hljs-comment">// factory method that returns the sole PinballSimulator object,</span>
<span class="hljs-comment">// creating it if it doesn't exist</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> PinballSimulator <span class="hljs-title">getInstance</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">if</span> (simulator == <span class="hljs-keyword">null</span>) {
simulator = <span class="hljs-keyword">new</span> PinballSimulator();
}
<span class="hljs-keyword">return</span> simulator;
}
}</code></pre>
<p>This class has a race in the <code>getInstance()</code> method — two threads could call it at the same time and end up creating two copies of the <code>PinballSimulator</code> object, which we don't want.</p>
<p>To fix this race using the thread confinement approach, you would specify that only a certain thread (maybe the “pinball simulation thread”) is allowed to call <code>PinballSimulator.getInstance()</code>. The risk here is that Java won't help you guarantee this.</p>
<p>In general, static variables are very risky for concurrency. They might be hiding behind an innocuous function that seems to have no side-effects or mutations. Consider this example:</p><pre><code class="language-java hljs"><span class="hljs-comment">// is this method threadsafe?</span>
<span class="hljs-comment handout-javadoc-comment">/**
* <span class="hljs-doctag">@param</span> x integer to test for primeness; requires x > 1
* <span class="hljs-doctag">@return</span> true if and only if x is prime with high probability
*/</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">isPrime</span><span class="hljs-params">(<span class="hljs-keyword">int</span> x)</span> </span>{
<span class="hljs-keyword">if</span> (cache.containsKey(x)) <span class="hljs-keyword">return</span> cache.get(x);
<span class="hljs-keyword">boolean</span> answer = BigInteger.valueOf(x).isProbablePrime(<span class="hljs-number">100</span>);
cache.put(x, answer);
<span class="hljs-keyword">return</span> answer;
}
<span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> Map<Integer,Boolean> cache = <span class="hljs-keyword">new</span> HashMap<>();</code></pre>
<p>This function stores the answers from previous calls in case they're requested again. This technique is called <a href="http://en.wikipedia.org/wiki/Memoization">memoization</a>, and it's a sensible optimization for slow functions like exact primality testing. But now the <code>isPrime</code> method is not safe to call from multiple threads, and its clients may not even realize it. The reason is that the <code>HashMap</code> referenced by the static variable <code>cache</code> is shared by all calls to <code>isPrime()</code>, and <code>HashMap</code> is not threadsafe. If multiple threads mutate the map at the same time, by calling <code>cache.put()</code>, then the map can become corrupted in the same way that <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-shared-memory">the bank account became corrupted in the last reading</a>. If you're lucky, the corruption may cause an exception deep in the hash map, like a <code>NullPointerException</code> or <code>IndexOutOfBoundsException</code>. But it also may just quietly give wrong answers, as we saw in the <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-shared-memory">bank account example</a>.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_1bf1c58e4901">
<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@Confinement">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Confinement">
<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@06-factorial">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-factorial">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_06-factorial" class="problems-wrapper" role="group"
aria-labelledby="06-factorial-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-factorial" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-factorial/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="06-factorial-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-factorial-problem-progress" tabindex="-1">
Factorial
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-factorial-problem-progress"></div>
<div class="problem">
<div>
<p>Suppose <code>main</code> looks like this:</p>
<pre>
public static void main(String[] args) {
new Thread(new Runnable() { // create a thread using an
public void run() { // anonymous Runnable
computeFact(99);
}
}).start();
computeFact(100);
}
</pre>
<p>Which of the following are possible interleavings?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_06-factorial_2_1">
<fieldset aria-describedby="status_06-factorial_2_1">
<div class="field">
<input type="checkbox" name="input_06-factorial_2_1[]" id="input_06-factorial_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="06-factorial_2_1-choice_0-label" for="input_06-factorial_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_06-factorial_2_1"> The call to computeFact(100) starts before the call to computeFact(99) starts
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-factorial_2_1[]" id="input_06-factorial_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="06-factorial_2_1-choice_1-label" for="input_06-factorial_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_06-factorial_2_1"> The call to computeFact(99) starts before the call to computeFact(100) starts
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-factorial_2_1[]" id="input_06-factorial_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="06-factorial_2_1-choice_2-label" for="input_06-factorial_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_06-factorial_2_1"> The call to computeFact(100) finishes before the call to computeFact(99) starts
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-factorial_2_1[]" id="input_06-factorial_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="06-factorial_2_1-choice_3-label" for="input_06-factorial_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_06-factorial_2_1"> The call to computeFact(99) finishes before the call to computeFact(100) starts
</label>
</div>
<span id="answer_06-factorial_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_06-factorial_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_06-factorial_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Factorial" />
<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_06-factorial" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_06-factorial">
<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="06-factorial-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="06-factorial-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="06-factorial-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@06-pinball">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-pinball">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_06-pinball" class="problems-wrapper" role="group"
aria-labelledby="06-pinball-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-pinball" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-pinball/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="3"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="06-pinball-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-pinball-problem-progress" tabindex="-1">
PinballSimulator
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-pinball-problem-progress"></div>
<div class="problem">
<div>
<p>Here&#8217;s part of the pinball simulator example from the previous section:</p>
<pre>
public class PinballSimulator {
private static PinballSimulator simulator = null;
// ...
public static PinballSimulator getInstance() {
/* 1 */ if (simulator == null) {
/* 2 */ simulator = new PinballSimulator();
}
/* 3 */ return simulator;
}
}
</pre>
<p>The code has a race condition that invalidates the invariant that only one simulator object is created.</p>
<p>Suppose two threads are running <code>getInstance()</code>. One thread is about to execute one of the numbered lines above; the other thread is about to execute the other. For each pair of possible line numbers, is it possible the invariant will be violated?</p>
<p>About to execute lines 1 and 3</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_06-pinball_2_1">
<fieldset aria-describedby="status_06-pinball_2_1">
<div class="field">
<input type="radio" name="input_06-pinball_2_1" id="input_06-pinball_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="06-pinball_2_1-choice_0-label" for="input_06-pinball_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_06-pinball_2_1"> Yes, it could be violated
</label>
</div>
<div class="field">
<input type="radio" name="input_06-pinball_2_1" id="input_06-pinball_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="06-pinball_2_1-choice_1-label" for="input_06-pinball_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_06-pinball_2_1"> No, we're safe
</label>
</div>
<span id="answer_06-pinball_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_06-pinball_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_06-pinball_solution_1"/>
</div><p>About to execute lines 1 and 2</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_06-pinball_3_1">
<fieldset aria-describedby="status_06-pinball_3_1">
<div class="field">
<input type="radio" name="input_06-pinball_3_1" id="input_06-pinball_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="06-pinball_3_1-choice_0-label" for="input_06-pinball_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_06-pinball_3_1"> Yes, it could be violated
</label>
</div>
<div class="field">
<input type="radio" name="input_06-pinball_3_1" id="input_06-pinball_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="06-pinball_3_1-choice_1-label" for="input_06-pinball_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_06-pinball_3_1"> No, we're safe
</label>
</div>
<span id="answer_06-pinball_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_06-pinball_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_06-pinball_solution_2"/>
</div><p>About to execute lines 1 and 1</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_06-pinball_4_1">
<fieldset aria-describedby="status_06-pinball_4_1">
<div class="field">
<input type="radio" name="input_06-pinball_4_1" id="input_06-pinball_4_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="06-pinball_4_1-choice_0-label" for="input_06-pinball_4_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_06-pinball_4_1"> Yes, it could be violated
</label>
</div>
<div class="field">
<input type="radio" name="input_06-pinball_4_1" id="input_06-pinball_4_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="06-pinball_4_1-choice_1-label" for="input_06-pinball_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_06-pinball_4_1"> No, we're safe
</label>
</div>
<span id="answer_06-pinball_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_06-pinball_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_06-pinball_solution_3"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="PinballSimulator" />
<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_06-pinball" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_06-pinball">
<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="06-pinball-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="06-pinball-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="06-pinball-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@06-confinement-60">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-confinement-60">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_06-confinement-60" class="problems-wrapper" role="group"
aria-labelledby="06-confinement-60-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-confinement-60" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-confinement-60/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="06-confinement-60-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-confinement-60-problem-progress" tabindex="-1">
Confinement
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-confinement-60-problem-progress"></div>
<div class="problem">
<div>
<p>In the following code, which variables are confined to a single thread?</p>
<pre>
public class C {
public static void main(String[] args) {
new Thread(new Runnable() {
public void run() {
threadA();
}
}).start();
new Thread(new Runnable() {
public void run() {
threadB();
}
}).start();
}
private static String name = "Napoleon Dynamite";
private static int cashLeft = 150;
private static void threadA() {
int amountA = 20;
cashLeft = spend(amountA);
}
private static void threadB() {
int amountB = 30;
cashLeft = spend(amountB);
}
private static int spend(int amountToSpend) {
return cashLeft - amountToSpend;
}
}
</pre>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_06-confinement-60_2_1">
<fieldset aria-describedby="status_06-confinement-60_2_1">
<div class="field">
<input type="checkbox" name="input_06-confinement-60_2_1[]" id="input_06-confinement-60_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="06-confinement-60_2_1-choice_0-label" for="input_06-confinement-60_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_06-confinement-60_2_1"> amountA
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-confinement-60_2_1[]" id="input_06-confinement-60_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="06-confinement-60_2_1-choice_1-label" for="input_06-confinement-60_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_06-confinement-60_2_1"> amountB
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-confinement-60_2_1[]" id="input_06-confinement-60_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="06-confinement-60_2_1-choice_2-label" for="input_06-confinement-60_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_06-confinement-60_2_1"> amountToSpend
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-confinement-60_2_1[]" id="input_06-confinement-60_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="06-confinement-60_2_1-choice_3-label" for="input_06-confinement-60_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_06-confinement-60_2_1"> cashLeft
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-confinement-60_2_1[]" id="input_06-confinement-60_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="06-confinement-60_2_1-choice_4-label" for="input_06-confinement-60_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_06-confinement-60_2_1"> name
</label>
</div>
<span id="answer_06-confinement-60_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_06-confinement-60_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_06-confinement-60_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Confinement" />
<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_06-confinement-60" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_06-confinement-60">
<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="06-confinement-60-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="06-confinement-60-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="06-confinement-60-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-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical-immutability">
<h2 class="hd hd-2 unit-title">Strategy 2: Immutability</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_3a496c8130de">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_3a496c8130de">
<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="strategy_2_immutability">Strategy 2: Immutability</h2>
<div data-outline="strategy_2_immutability">
<p>Our second way of achieving thread safety is by using immutable references and data types. Immutability tackles the shared-mutable-data cause of a race condition and solves it simply by making the shared data <em>not mutable</em>.</p>
<p>Final variables are immutable references, so a variable declared final is safe to access from multiple threads. You can only read the variable, not write it. Be careful, because this safety applies only to the variable itself, and we still have to argue that the object the variable points to is immutable.</p>
<p>Immutable objects are usually also threadsafe. We say “usually” here because our current definition of immutability is too loose for concurrent programming. We've said that a type is immutable if an object of the type always represents the same abstract value for its entire lifetime. But that actually allows the type the freedom to mutate its rep, as long as those mutations are invisible to clients. We saw an example of this notion, called benevolent or beneficent mutation, when we looked at <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-tuning-the-rep">an immutable list that cached its length in a mutable field</a> the first time the length was requested by a client. Caching is a typical kind of beneficent mutation.</p>
<p>For concurrency, though, this kind of hidden mutation is not safe. An immutable data type that uses beneficent mutation will have to make itself threadsafe using locks (the same technique required of mutable data types), which we'll talk about in a future reading.</p>
</div>
<h3 id="stronger_definition_of_immutability">Stronger definition of immutability</h3>
<div data-outline="stronger_definition_of_immutability">
<p>So in order to be confident that an immutable data type is threadsafe without locks, we need a stronger definition of immutability:</p>
<ul>
<li>no mutator methods</li>
<li>all fields are private and final</li>
<li>no <a href="//courses.edx.org/courses/course-v1:MITx+6.005.1x+3T2016/jump_to_id/vertical-invariants">representation exposure</a></li>
<li>no mutation whatsoever of mutable objects in the rep — not even <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-tuning-the-rep">beneficent mutation</a></li>
</ul>
<p>If you follow these rules, then you can be confident that your immutable type will also be threadsafe.</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/imstrat.html" class="alert-link">A Strategy for Defining Immutable Objects</a> (1 page)</li>
</ul>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_ccad511a2f18">
<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@Immutability">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Immutability">
<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@06-immutability-61">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-immutability-61">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_06-immutability-61" class="problems-wrapper" role="group"
aria-labelledby="06-immutability-61-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-immutability-61" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-immutability-61/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="06-immutability-61-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-immutability-61-problem-progress" tabindex="-1">
Immutability
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-immutability-61-problem-progress"></div>
<div class="problem">
<div>
<p>Suppose you're reviewing an abstract data type which is specified to be immutable, to decide whether its implementation actually is immutable and threadsafe. Which of the following elements would you have to look at?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_06-immutability-61_2_1">
<fieldset aria-describedby="status_06-immutability-61_2_1">
<div class="field">
<input type="checkbox" name="input_06-immutability-61_2_1[]" id="input_06-immutability-61_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="06-immutability-61_2_1-choice_0-label" for="input_06-immutability-61_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_06-immutability-61_2_1"> fields
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-immutability-61_2_1[]" id="input_06-immutability-61_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="06-immutability-61_2_1-choice_1-label" for="input_06-immutability-61_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_06-immutability-61_2_1"> creator implementations
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-immutability-61_2_1[]" id="input_06-immutability-61_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="06-immutability-61_2_1-choice_2-label" for="input_06-immutability-61_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_06-immutability-61_2_1"> client calls to creators
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-immutability-61_2_1[]" id="input_06-immutability-61_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="06-immutability-61_2_1-choice_3-label" for="input_06-immutability-61_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_06-immutability-61_2_1"> producer implementations
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-immutability-61_2_1[]" id="input_06-immutability-61_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="06-immutability-61_2_1-choice_4-label" for="input_06-immutability-61_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_06-immutability-61_2_1"> client calls to producers
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-immutability-61_2_1[]" id="input_06-immutability-61_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="06-immutability-61_2_1-choice_5-label" for="input_06-immutability-61_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_06-immutability-61_2_1"> observer implementations
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-immutability-61_2_1[]" id="input_06-immutability-61_2_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="06-immutability-61_2_1-choice_6-label" for="input_06-immutability-61_2_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_06-immutability-61_2_1"> client calls to observers
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-immutability-61_2_1[]" id="input_06-immutability-61_2_1_choice_7" class="field-input input-checkbox" value="choice_7"/><label id="06-immutability-61_2_1-choice_7-label" for="input_06-immutability-61_2_1_choice_7" class="response-label field-label label-inline" aria-describedby="status_06-immutability-61_2_1"> mutator implementations
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-immutability-61_2_1[]" id="input_06-immutability-61_2_1_choice_8" class="field-input input-checkbox" value="choice_8"/><label id="06-immutability-61_2_1-choice_8-label" for="input_06-immutability-61_2_1_choice_8" class="response-label field-label label-inline" aria-describedby="status_06-immutability-61_2_1"> client calls to mutators
</label>
</div>
<span id="answer_06-immutability-61_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_06-immutability-61_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_06-immutability-61_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Immutability" />
<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_06-immutability-61" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_06-immutability-61">
<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="06-immutability-61-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="06-immutability-61-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="06-immutability-61-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-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical-using-threadsafe-datatypes">
<h2 class="hd hd-2 unit-title">Strategy 3: Using Threadsafe Data Types</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_3809471b2fe0">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_3809471b2fe0">
<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="strategy_3_using_threadsafe_data_types">Strategy 3: Using Threadsafe Data Types</h2>
<div data-outline="strategy_3_using_threadsafe_data_types">
<p>Our third major strategy for achieving thread safety is to store shared mutable data in existing threadsafe data types.</p>
<p>When a data type in the Java library is threadsafe, its documentation will explicitly state that fact. For example, here's what <a href="http://docs.oracle.com/javase/8/docs/api/?java/lang/StringBuffer.html">StringBuffer</a> says:</p>
<blockquote>
<p>[StringBuffer is] A threadsafe, mutable sequence of characters. A string buffer is like a String, but can be modified. At any point in time it contains some particular sequence of characters, but the length and content of the sequence can be changed through certain method calls.</p>
<p>String buffers are safe for use by multiple threads. The methods are synchronized where necessary so that all the operations on any particular instance behave as if they occur in some serial order that is consistent with the order of the method calls made by each of the individual threads involved.</p>
</blockquote>
<p>This is in contrast to <a href="http://docs.oracle.com/javase/8/docs/api/?java/lang/StringBuilder.html">StringBuilder</a>:</p>
<blockquote>
<p>[StringBuilder is] A mutable sequence of characters. This class provides an API compatible with StringBuffer, but with no guarantee of synchronization. This class is designed for use as a drop-in replacement for StringBuffer in places where the string buffer was being used by a single thread (as is generally the case). Where possible, it is recommended that this class be used in preference to StringBuffer as it will be faster under most implementations.</p>
</blockquote>
<p>It's become common in the Java API to find two mutable data types that do the same thing, one threadsafe and the other not. The reason is what this quote indicates: threadsafe data types usually incur a performance penalty compared to an unsafe type.</p>
<p>It's deeply unfortunate that <code>StringBuffer</code> and <code>StringBuilder</code> are named so similarly, without any indication in the name that thread safety is the crucial difference between them. It's also unfortunate that they don't share a common interface, so you can't simply swap in one implementation for the other for the times when you need thread safety. The Java collection interfaces do much better in this respect, as we'll see next.</p>
</div>
<h3 id="threadsafe_collections">Threadsafe Collections</h3>
<div data-outline="threadsafe_collections">
<p>The collection interfaces in Java — <code>List</code>, <code>Set</code>, <code>Map</code> — have basic implementations that are not threadsafe. The implementations of these that you've been used to using, namely <code>ArrayList</code>, <code>HashMap</code>, and <code>HashSet</code>, cannot be used safely from more than one thread.</p>
<p>Fortunately, just like the Collections API provides wrapper methods that make collections immutable, it provides another set of wrapper methods to make collections threadsafe, while still mutable.</p>
<p>These wrappers effectively make each method of the collection atomic with respect to the other methods. An <strong>atomic action</strong> effectively happens all at once — it doesn't interleave its internal operations with those of other actions, and none of the effects of the action are visible to other threads until the entire action is complete, so it never looks partially done.</p>
<p>Now we see a way to fix the <code>isPrime()</code> method we had <a href="#avoid_global_variables">earlier in the reading</a>:</p><pre><code class="language-java hljs"><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> Map<Integer,Boolean> cache =
Collections.synchronizedMap(<span class="hljs-keyword">new</span> HashMap<>());</code></pre>
<p>A few points here.</p>
<p><strong>Don't circumvent the wrapper.</strong> Make sure to throw away references to the underlying non-threadsafe collection, and access it only through the synchronized wrapper. That happens automatically in the line of code above, since the new <code>HashMap</code> is passed only to <code>synchronizedMap()</code> and never stored anywhere else. (We saw this same warning with the unmodifiable wrappers: the underlying collection is still mutable, and code with a reference to it can circumvent immutability.)</p>
<p><strong>Iterators are still not threadsafe.</strong> Even though method calls on the collection itself (<code>get()</code>, <code>put()</code>, <code>add()</code>, etc.) are now threadsafe, iterators created from the collection are still not threadsafe. So you can't use <code>iterator()</code>, or the for loop syntax:</p><pre><code class="language-java hljs"><span class="hljs-keyword">for</span> (String s: lst) { ... } <span class="hljs-comment">// not threadsafe, even if lst is a synchronized list wrapper</span></code></pre>
<p>The solution to this iteration problem will be to acquire the collection's lock when you need to iterate over it, which we'll talk about in a future reading.</p>
<p>Finally, <strong>atomic operations aren't enough to prevent races:</strong> the way that you use the synchronized collection can still have a race condition. Consider this code, which checks whether a list has at least one element and then gets that element:</p><pre><code class="language-java hljs"><span class="hljs-keyword">if</span> ( ! lst.isEmpty()) { String s = lst.get(<span class="hljs-number">0</span>); ... }</code></pre>
<p>Even if you make <code>lst</code> into a synchronized list, this code still may have a race condition, because another thread may remove the element between the <code>isEmpty()</code> call and the <code>get()</code> call.</p>
<p>Even the <code>isPrime()</code> method still has potential races:</p><pre><code class="language-java hljs"><span class="hljs-keyword">if</span> (cache.containsKey(x)) <span class="hljs-keyword">return</span> cache.get(x);
<span class="hljs-keyword">boolean</span> answer = BigInteger.valueOf(x).isProbablePrime(<span class="hljs-number">100</span>);
cache.put(x, answer);</code></pre>
<p>The synchronized map ensures that <code>containsKey()</code>, <code>get()</code>, and <code>put()</code> are now atomic, so using them from multiple threads won't damage the rep invariant of the map. But those three operations can now interleave in arbitrary ways with each other, which might break the invariant that <code>isPrime</code> needs from the cache: if the cache maps an integer x to a value f, then x is prime if and only if f is true. If the cache ever fails this invariant, then we might return the wrong result.</p>
<p>So we have to argue that the races between <code>containsKey()</code>, <code>get()</code>, and <code>put()</code> don't threaten this invariant.</p>
<ol>
<li>The race between <code>containsKey()</code> and <code>get()</code> is not harmful because we never remove items from the cache — once it contains a result for x, it will continue to do so.</li>
<li>There's a race between <code>containsKey()</code> and <code>put()</code>. As a result, it may end up that two threads will both test the primeness of the same x at the same time, and both will race to call <code>put()</code> with the answer. But both of them should call <code>put()</code> with the same answer, so it doesn't matter which one wins the race — the result will be the same.</li>
</ol>
<p>The need to make these kinds of careful arguments about safety — even when you're using threadsafe data types — is the main reason that concurrency is hard.</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/collections/implementations/wrapper.html" class="alert-link">Wrapper Collections</a> (1 page)</li>
<li><a href="http://docs.oracle.com/javase/tutorial/essential/concurrency/collections.html" class="alert-link">Concurrent Collections</a> (1 page)</li>
</ul>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_d95a479d46ce">
<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@Threadsafe_Data_Types">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Threadsafe_Data_Types">
<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@06-threadsafe-data-types-63">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-threadsafe-data-types-63">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_06-threadsafe-data-types-63" class="problems-wrapper" role="group"
aria-labelledby="06-threadsafe-data-types-63-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-threadsafe-data-types-63" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-threadsafe-data-types-63/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="3"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="06-threadsafe-data-types-63-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-threadsafe-data-types-63-problem-progress" tabindex="-1">
problem
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-threadsafe-data-types-63-problem-progress"></div>
<div class="problem">
<div>
<p>Consider this class's rep:</p>
<pre>
public class Building {
private final String buildingName;
private int numberOfFloors;
private final int[] occupancyPerFloor;
private final List&lt;String&gt; companyNames = Collections.synchronizedList(new ArrayList&lt;&gt;());
...
}
</pre>
<p>Which of these variables use a threadsafe data type?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_06-threadsafe-data-types-63_2_1">
<fieldset aria-describedby="status_06-threadsafe-data-types-63_2_1">
<div class="field">
<input type="checkbox" name="input_06-threadsafe-data-types-63_2_1[]" id="input_06-threadsafe-data-types-63_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="06-threadsafe-data-types-63_2_1-choice_0-label" for="input_06-threadsafe-data-types-63_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_06-threadsafe-data-types-63_2_1"> buildingName
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-threadsafe-data-types-63_2_1[]" id="input_06-threadsafe-data-types-63_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="06-threadsafe-data-types-63_2_1-choice_1-label" for="input_06-threadsafe-data-types-63_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_06-threadsafe-data-types-63_2_1"> numberOfFloors
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-threadsafe-data-types-63_2_1[]" id="input_06-threadsafe-data-types-63_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="06-threadsafe-data-types-63_2_1-choice_2-label" for="input_06-threadsafe-data-types-63_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_06-threadsafe-data-types-63_2_1"> occupancyPerFloor
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-threadsafe-data-types-63_2_1[]" id="input_06-threadsafe-data-types-63_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="06-threadsafe-data-types-63_2_1-choice_3-label" for="input_06-threadsafe-data-types-63_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_06-threadsafe-data-types-63_2_1"> companyNames
</label>
</div>
<span id="answer_06-threadsafe-data-types-63_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_06-threadsafe-data-types-63_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_06-threadsafe-data-types-63_solution_1"/>
</div><p>Which of these variables are safe for use by multiple threads?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_06-threadsafe-data-types-63_3_1">
<fieldset aria-describedby="status_06-threadsafe-data-types-63_3_1">
<div class="field">
<input type="checkbox" name="input_06-threadsafe-data-types-63_3_1[]" id="input_06-threadsafe-data-types-63_3_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="06-threadsafe-data-types-63_3_1-choice_0-label" for="input_06-threadsafe-data-types-63_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_06-threadsafe-data-types-63_3_1"> buildingName
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-threadsafe-data-types-63_3_1[]" id="input_06-threadsafe-data-types-63_3_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="06-threadsafe-data-types-63_3_1-choice_1-label" for="input_06-threadsafe-data-types-63_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_06-threadsafe-data-types-63_3_1"> numberOfFloors
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-threadsafe-data-types-63_3_1[]" id="input_06-threadsafe-data-types-63_3_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="06-threadsafe-data-types-63_3_1-choice_2-label" for="input_06-threadsafe-data-types-63_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_06-threadsafe-data-types-63_3_1"> occupancyPerFloor
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-threadsafe-data-types-63_3_1[]" id="input_06-threadsafe-data-types-63_3_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="06-threadsafe-data-types-63_3_1-choice_3-label" for="input_06-threadsafe-data-types-63_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_06-threadsafe-data-types-63_3_1"> companyNames
</label>
</div>
<span id="answer_06-threadsafe-data-types-63_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_06-threadsafe-data-types-63_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_06-threadsafe-data-types-63_solution_2"/>
</div><p>Which of these variables cannot be involved in any race condition?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_06-threadsafe-data-types-63_4_1">
<fieldset aria-describedby="status_06-threadsafe-data-types-63_4_1">
<div class="field">
<input type="checkbox" name="input_06-threadsafe-data-types-63_4_1[]" id="input_06-threadsafe-data-types-63_4_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="06-threadsafe-data-types-63_4_1-choice_0-label" for="input_06-threadsafe-data-types-63_4_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_06-threadsafe-data-types-63_4_1"> buildingName
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-threadsafe-data-types-63_4_1[]" id="input_06-threadsafe-data-types-63_4_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="06-threadsafe-data-types-63_4_1-choice_1-label" for="input_06-threadsafe-data-types-63_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_06-threadsafe-data-types-63_4_1"> numberOfFloors
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-threadsafe-data-types-63_4_1[]" id="input_06-threadsafe-data-types-63_4_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="06-threadsafe-data-types-63_4_1-choice_2-label" for="input_06-threadsafe-data-types-63_4_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_06-threadsafe-data-types-63_4_1"> occupancyPerFloor
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-threadsafe-data-types-63_4_1[]" id="input_06-threadsafe-data-types-63_4_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="06-threadsafe-data-types-63_4_1-choice_3-label" for="input_06-threadsafe-data-types-63_4_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_06-threadsafe-data-types-63_4_1"> companyNames
</label>
</div>
<span id="answer_06-threadsafe-data-types-63_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_06-threadsafe-data-types-63_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_06-threadsafe-data-types-63_solution_3"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="problem" />
<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_06-threadsafe-data-types-63" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_06-threadsafe-data-types-63">
<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="06-threadsafe-data-types-63-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="06-threadsafe-data-types-63-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="06-threadsafe-data-types-63-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-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical-how-to-make-a-safety-argument">
<h2 class="hd hd-2 unit-title">How to Make a Safety Argument</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_301e357ab310">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_301e357ab310">
<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="how_to_make_a_safety_argument">How to Make a Safety Argument</h2>
<div data-outline="how_to_make_a_safety_argument">
<p>We've seen that concurrency is hard to test and debug. So if you want to convince yourself and others that your concurrent program is correct, the best approach is to make an explicit argument that it's free from races, and write it down.</p>
<p>A safety argument needs to catalog all the threads that exist in your module or program, and the data that that they use, and argue which of the four techniques you are using to protect against races for each data object or variable: confinement, immutability, threadsafe data types, or synchronization. When you use the last two, you also need to argue that all accesses to the data are appropriately atomic — that is, that the invariants you depend on are not threatened by interleaving. We gave one of those arguments for <code>isPrime</code> above.</p>
<h3 id="thread_safety_arguments_for_data_types">Thread Safety Arguments for Data Types</h3>
<div data-outline="thread_safety_arguments_for_data_types">
<p>Let's see some examples of how to make thread safety arguments for a data type. Remember our four approaches to thread safety: confinement, immutability, threadsafe data types, and synchronization. Since we haven't talked about synchronization in this reading, we'll just focus on the first three approaches.</p>
<p>Confinement is not usually an option when we're making an argument just about a data type, because you have to know what threads exist in the system and what objects they've been given access to. If the data type creates its own set of threads, then you can talk about confinement with respect to those threads. Otherwise, the threads are coming in from the outside, carrying client calls, and the data type may have no guarantees about which threads have references to what. So confinement isn't a useful argument in that case. Usually we use confinement at a higher level, talking about the system as a whole and arguing why we don't need thread safety for some of our modules or data types, because they won't be shared across threads by design.</p>
<p>Immutability is often a useful argument:</p>
<div class="pull-margin"><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/** MyString is an immutable data type representing a string of characters. */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">MyString</span> </span>{
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">char</span>[] a;
<span class="hljs-comment">// Thread safety argument:</span>
<span class="hljs-comment">// This class is threadsafe because it's immutable:</span>
<span class="hljs-comment">// - a is final</span>
<span class="hljs-comment">// - a points to a mutable char array, but that array is encapsulated</span>
<span class="hljs-comment">// in this object, not shared with any other object or exposed to a</span>
<span class="hljs-comment">// client</span></code></pre>
<p>Here's another rep for MyString that requires a little more care in the argument:</p>
<pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/** MyString is an immutable data type representing a string of characters. */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">MyString</span> </span>{
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">char</span>[] a;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> start;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> len;
<span class="hljs-comment">// Rep invariant:</span>
<span class="hljs-comment">// 0 <= start <= a.length</span>
<span class="hljs-comment">// 0 <= len <= a.length-start</span>
<span class="hljs-comment">// Abstraction function:</span>
<span class="hljs-comment">// represents the string of characters a[start],...,a[start+length-1]</span>
<span class="hljs-comment">// Thread safety argument:</span>
<span class="hljs-comment">// This class is threadsafe because it's immutable:</span>
<span class="hljs-comment">// - a, start, and len are final</span>
<span class="hljs-comment">// - a points to a mutable char array, which may be shared with other</span>
<span class="hljs-comment">// String objects, but they never mutate it</span>
<span class="hljs-comment">// - the array is never exposed to a client</span></code></pre></div>
<p>Note that since this <code>MyString</code> rep was designed for sharing the array between multiple <code>MyString</code> objects, we have to ensure that the sharing doesn't threaten its thread safety. As long as it doesn't threaten the <code>MyString</code>'s immutability, however, we can be confident that it won't threaten the thread safety.</p>
<p>We also have to avoid rep exposure. Rep exposure is bad for any data type, since it threatens the data type's rep invariant. It's also fatal to thread safety.</p>
</div>
<h3 id="bad_safety_arguments">Bad Safety Arguments</h3>
<div data-outline="bad_safety_arguments">
<p>Here are some <em>incorrect</em> arguments for thread safety:</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/** <code>MyStringBuffer</code> is a threadsafe mutable string of characters. */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">MyStringBuffer</span> </span>{
<span class="hljs-keyword">private</span> String text;
<span class="hljs-comment">// Rep invariant:</span>
<span class="hljs-comment">// none</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">// text is an immutable (and hence threadsafe) String,</span>
<span class="hljs-comment">// so this object is also threadsafe</span></code></pre>
<p>Why doesn't this argument work? String is indeed immutable and threadsafe; but the rep pointing to that string, specifically the <code>text</code> variable, is not immutable. <code>text</code> is not a final variable, and in fact it <em>can't</em> be final in this data type, because we need the data type to support insertion and deletion operations. So reads and writes of the <code>text</code> variable itself are not threadsafe. This argument is false.</p>
<p>Here's another broken argument:</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">Graph</span> </span>{
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> Set<Node> nodes =
Collections.synchronizedSet(<span class="hljs-keyword">new</span> HashSet<>());
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> Map<Node,Set<Node>> edges =
Collections.synchronizedMap(<span class="hljs-keyword">new</span> HashMap<>());
<span class="hljs-comment">// Rep invariant:</span>
<span class="hljs-comment">// for all x, y such that y is a member of edges.get(x),</span>
<span class="hljs-comment">// x, y are both members of nodes</span>
<span class="hljs-comment">// Abstraction function:</span>
<span class="hljs-comment">// represents a directed graph whose nodes are the set of nodes</span>
<span class="hljs-comment">// and whose edges are the set (x,y) such that</span>
<span class="hljs-comment">// y is a member of edges.get(x)</span>
<span class="hljs-comment">// Thread safety argument:</span>
<span class="hljs-comment">// - nodes and edges are final, so those variables are immutable</span>
<span class="hljs-comment">// and threadsafe</span>
<span class="hljs-comment">// - nodes and edges point to threadsafe set and map data types</span></code></pre>
<p>This is a graph data type, which stores its nodes in a set and its edges in a map. (Quick quiz: is <code>Graph</code> a mutable or immutable data type? What do the final keywords have to do with its mutability?) Graph relies on other threadsafe data types to help it implement its rep — specifically the <a href="#threadsafe_collections">threadsafe <code>Set</code> and <code>Map</code> wrappers</a> that we talked about above. That prevents some race conditions, but not all, because the graph's rep invariant includes a relationship <em>between</em> the node set and the edge map. All nodes that appear in the edge map also have to appear in the node set. So there may be code like this:</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">addEdge</span><span class="hljs-params">(Node from, Node to)</span> </span>{
<span class="hljs-keyword">if</span> ( ! edges.containsKey(from)) {
edges.put(from, Collections.synchronizedSet(<span class="hljs-keyword">new</span> HashSet<>()));
}
edges.get(from).add(to);
nodes.add(from);
nodes.add(to);
}</code></pre>
<p>This code has a race condition in it. There is a crucial moment when the rep invariant is violated, right after the <code>edges</code> map is mutated, but just before the <code>nodes</code> set is mutated. Another operation on the graph might interleave at that moment, discover the rep invariant broken, and return wrong results. Even though the threadsafe set and map data types guarantee that their own <code>add()</code> and <code>put()</code> methods are atomic and noninterfering, they can't extend that guarantee to <em>interactions</em> between the two data structures. So the rep invariant of <code>Graph</code> is not safe from race conditions. Just using immutable and threadsafe-mutable data types is not sufficient when the rep invariant depends on relationships <em>between</em> objects in the rep.</p>
<p>We'll have to fix this with synchronization, and we'll see how in a future reading.</p>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_017844f560c5">
<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@Safety_Arguments">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Safety_Arguments">
<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@06-safety-arguments-62">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-safety-arguments-62">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_06-safety-arguments-62" class="problems-wrapper" role="group"
aria-labelledby="06-safety-arguments-62-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-safety-arguments-62" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-safety-arguments-62/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="06-safety-arguments-62-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-safety-arguments-62-problem-progress" tabindex="-1">
Safety arguments
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-safety-arguments-62-problem-progress"></div>
<div class="problem">
<div>
<p>Consider the following ADT with a <b>bad</b> safety argument, which appeared in the reading:</p>
<pre>
/** MyStringBuffer is a threadsafe mutable string of characters. */
public class MyStringBuffer {
private String text;
// Rep invariant:
// none
// Abstraction function:
// represents the sequence text[0],...,text[text.length()-1]
// Thread safety argument:
// text is an immutable (and hence threadsafe) String,
// so this object is also threadsafe
/** @return the string represented by this buffer, with all letters converted to uppercase */
public String toUpperCase() {
return text.toUpperCase();
}
/** @param pos position to insert text into the buffer. Requires 0 &lt;= pos &lt;= text.length().
@param s text to insert
Mutates this buffer to insert s as a substring at position pos. */
public void insert(int pos, String s) {
text = text.substring(0, pos) + s + text.substring(pos);
}
/** @return the string represented by this buffer */
public String toString() {
return text;
}
/** Resets this buffer to the empty string */
public void clear() {
text = "";
}
/** @return the first character of this buffer, or "" if this buffer is empty
public String first() {
if (text.length() &gt; 0) {
return String.valueOf(text.charAt(0));
} else {
return "";
}
}
</pre>
<p>Which of these methods are counterexamples to this buggy safety argument, because they have a race condition? In particular, you should mark some method A as a counterexample if it's possible for one thread running method A at the same time as another thread is running some other method, some particular interleaving would violate A's postcondition?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_06-safety-arguments-62_2_1">
<fieldset aria-describedby="status_06-safety-arguments-62_2_1">
<div class="field">
<input type="checkbox" name="input_06-safety-arguments-62_2_1[]" id="input_06-safety-arguments-62_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="06-safety-arguments-62_2_1-choice_0-label" for="input_06-safety-arguments-62_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_06-safety-arguments-62_2_1"> toUpperCase
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-safety-arguments-62_2_1[]" id="input_06-safety-arguments-62_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="06-safety-arguments-62_2_1-choice_1-label" for="input_06-safety-arguments-62_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_06-safety-arguments-62_2_1"> insert
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-safety-arguments-62_2_1[]" id="input_06-safety-arguments-62_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="06-safety-arguments-62_2_1-choice_2-label" for="input_06-safety-arguments-62_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_06-safety-arguments-62_2_1"> toString
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-safety-arguments-62_2_1[]" id="input_06-safety-arguments-62_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="06-safety-arguments-62_2_1-choice_3-label" for="input_06-safety-arguments-62_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_06-safety-arguments-62_2_1"> clear
</label>
</div>
<div class="field">
<input type="checkbox" name="input_06-safety-arguments-62_2_1[]" id="input_06-safety-arguments-62_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="06-safety-arguments-62_2_1-choice_4-label" for="input_06-safety-arguments-62_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_06-safety-arguments-62_2_1"> first
</label>
</div>
<span id="answer_06-safety-arguments-62_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_06-safety-arguments-62_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_06-safety-arguments-62_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Safety arguments" />
<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_06-safety-arguments-62" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_06-safety-arguments-62">
<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="06-safety-arguments-62-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="06-safety-arguments-62-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="06-safety-arguments-62-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-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical-serializability">
<h2 class="hd hd-2 unit-title">Serializability</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_3c615bdc551f">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_3c615bdc551f">
<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>
/* style timeline tables */
window.onHandoutDidRender = function() {
$('.timeline table').addClass('table-condensed');
$('.timeline table').css('width', 'inherit');
$('.timeline table thead:not(:has(th:not(:empty)))').remove();
}
</script>
<h3 id="serializability">Serializability</h3>
<div data-outline="serializability">
<p>Look again at the code for the exercise above. We might also be concerned that <code>clear</code> and <code>insert</code> could interleave such that a client sees <code>clear</code> violate its postcondition.</p>
<div class="timeline panel panel-figure pull-right">
<table class="table table-condensed" style="width: inherit;">
<thead>
<tr>
<th>A</th>
<th>B</th>
</tr>
</thead>
<tbody>
<tr>
<td>call <code>sb.clear()</code></td>
<td></td>
</tr>
<tr>
<td></td>
<td>call <code>sb.insert(0, "a")</code></td>
</tr>
<tr>
<td>— in <code>clear</code>: <code>text = ""</code></td>
<td></td>
</tr>
<tr>
<td></td>
<td>— in <code>insert</code>: <code>text = "" + "a" + "z"</code></td>
</tr>
<tr>
<td>— <code>clear</code> returns</td>
<td></td>
</tr>
<tr>
<td></td>
<td>— <code>insert</code> returns</td>
</tr>
<tr>
<td><code>assert sb.toString()</code>
<br><code> .equals("")</code></td>
<td></td>
</tr>
</tbody>
</table>
</div>
<p>Suppose two threads are sharing <code>MyStringBuffer sb</code> representing <code>"z"</code>. They run <code>clear</code> and <code>insert</code> concurrently as shown on the right.</p>
<p>Thread A's assertion will fail, but not because <code>clear</code> violated its postcondition. Indeed, when all the code in <code>clear</code> has finished running, the postcondition is satisfied.</p>
<div class="clearfix"></div>
<p>The real problem is that thread A has not anticipated possible interleaving between <code>clear()</code> and the <code>assert</code>. With any threadsafe mutable type where atomic mutators are called concurrently, <em>some</em> mutation has to “win” by being the last one applied. The result that thread A observed is identical to the execution below, where the mutators don't interleave at all:</p>
<div class="timeline">
<table class="table table-condensed" style="width: inherit;">
<thead>
<tr>
<th>A</th>
<th>B</th>
</tr>
</thead>
<tbody>
<tr>
<td>call <code>sb.clear()</code></td>
<td></td>
</tr>
<tr>
<td>— in <code>clear</code>: <code>text = ""</code></td>
<td></td>
</tr>
<tr>
<td>— <code>clear</code> returns</td>
<td></td>
</tr>
<tr>
<td></td>
<td>call <code>sb.insert(0, "a")</code></td>
</tr>
<tr>
<td></td>
<td>— in <code>insert</code>: <code>text = "" + "a" + "z"</code></td>
</tr>
<tr>
<td></td>
<td>— <code>insert</code> returns</td>
</tr>
<tr>
<td><code>assert sb.toString()</code>
<br><code> .equals("")</code></td>
<td></td>
</tr>
</tbody>
</table>
</div>
<p>What we demand from a threadsafe data type is that when clients call its atomic operations concurrently, the results are consistent with <em>some</em> sequential ordering of the calls. In this case, clearing and inserting, that means either <code>clear</code>-followed-by-<code>insert</code>, or <code>insert</code>-followed-by-<code>clear</code>. This property is called <a href="https://en.wikipedia.org/wiki/Serializability"><strong>serializability</strong></a>: for any set of operations executed concurrently, the result (the values and state observable by clients) must be a result given by <em>some</em> sequential ordering of those operations.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_681f8d9215c5">
<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@Safety_Arguments">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Safety_Arguments">
<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@06-serializability">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-serializability">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_06-serializability" class="problems-wrapper" role="group"
aria-labelledby="06-serializability-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-serializability" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-serializability/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="5"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="06-serializability-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-serializability-problem-progress" tabindex="-1">
Serializability
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@06-serializability-problem-progress"></div>
<div class="problem">
<div>
<p>Suppose two threads are sharing a <code>MyStringBuffer</code> representing "z".</p>
<p>For each pair of concurrent calls and their result, does that outcome violate serializability (and therefore demonstrate that <code>MyStringBuffer</code> is not threadsafe)?</p>
<p><code>clear()</code> and <code>insert(0, "a")</code> &#8594; <code>insert</code> throws an <code>IndexOutOfBoundsException</code></p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_06-serializability_2_1">
<fieldset aria-describedby="status_06-serializability_2_1">
<div class="field">
<input type="radio" name="input_06-serializability_2_1" id="input_06-serializability_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="06-serializability_2_1-choice_0-label" for="input_06-serializability_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_06-serializability_2_1"> Violates serializability
</label>
</div>
<div class="field">
<input type="radio" name="input_06-serializability_2_1" id="input_06-serializability_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="06-serializability_2_1-choice_1-label" for="input_06-serializability_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_06-serializability_2_1"> Consistent with serializability
</label>
</div>
<span id="answer_06-serializability_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_06-serializability_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_06-serializability_solution_1"/>
</div><p><code>clear()</code> and <code>insert(1, "a")</code> &#8594; <code>insert</code> throws an <code>IndexOutOfBoundsException</code></p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_06-serializability_3_1">
<fieldset aria-describedby="status_06-serializability_3_1">
<div class="field">
<input type="radio" name="input_06-serializability_3_1" id="input_06-serializability_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="06-serializability_3_1-choice_0-label" for="input_06-serializability_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_06-serializability_3_1"> Violates serializability
</label>
</div>
<div class="field">
<input type="radio" name="input_06-serializability_3_1" id="input_06-serializability_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="06-serializability_3_1-choice_1-label" for="input_06-serializability_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_06-serializability_3_1"> Consistent with serializability
</label>
</div>
<span id="answer_06-serializability_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_06-serializability_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_06-serializability_solution_2"/>
</div><p><code>first()</code> and <code>insert(0, "a")</code> &#8594; <code>first</code> returns "a"</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_06-serializability_4_1">
<fieldset aria-describedby="status_06-serializability_4_1">
<div class="field">
<input type="radio" name="input_06-serializability_4_1" id="input_06-serializability_4_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="06-serializability_4_1-choice_0-label" for="input_06-serializability_4_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_06-serializability_4_1"> Violates serializability
</label>
</div>
<div class="field">
<input type="radio" name="input_06-serializability_4_1" id="input_06-serializability_4_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="06-serializability_4_1-choice_1-label" for="input_06-serializability_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_06-serializability_4_1"> Consistent with serializability
</label>
</div>
<span id="answer_06-serializability_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_06-serializability_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_06-serializability_solution_3"/>
</div><p><code>first()</code> and <code>clear()</code> &#8594; <code>first</code> returns "z"</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><div class="choicegroup capa_inputtype" id="inputtype_06-serializability_5_1">
<fieldset aria-describedby="status_06-serializability_5_1">
<div class="field">
<input type="radio" name="input_06-serializability_5_1" id="input_06-serializability_5_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="06-serializability_5_1-choice_0-label" for="input_06-serializability_5_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_06-serializability_5_1"> Violates serializability
</label>
</div>
<div class="field">
<input type="radio" name="input_06-serializability_5_1" id="input_06-serializability_5_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="06-serializability_5_1-choice_1-label" for="input_06-serializability_5_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_06-serializability_5_1"> Consistent with serializability
</label>
</div>
<span id="answer_06-serializability_5_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_06-serializability_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_06-serializability_solution_4"/>
</div><p><code>first()</code> and <code>clear()</code> &#8594; <code>first</code> throws an <code>IndexOutOfBoundsException</code></p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 5" role="group"><div class="choicegroup capa_inputtype" id="inputtype_06-serializability_6_1">
<fieldset aria-describedby="status_06-serializability_6_1">
<div class="field">
<input type="radio" name="input_06-serializability_6_1" id="input_06-serializability_6_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="06-serializability_6_1-choice_0-label" for="input_06-serializability_6_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_06-serializability_6_1"> Violates serializability
</label>
</div>
<div class="field">
<input type="radio" name="input_06-serializability_6_1" id="input_06-serializability_6_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="06-serializability_6_1-choice_1-label" for="input_06-serializability_6_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_06-serializability_6_1"> Consistent with serializability
</label>
</div>
<span id="answer_06-serializability_6_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_06-serializability_6_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_06-serializability_solution_5"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Serializability" />
<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_06-serializability" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_06-serializability">
<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="06-serializability-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="06-serializability-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="06-serializability-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-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Reading_6_Summary">
<h2 class="hd hd-2 unit-title">Reading 6 Summary</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_be9736d00d08">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="13782690e9a111efbd7312d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_be9736d00d08">
<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>This reading talked about three major ways to achieve safety from race conditions on shared mutable data:</p>
<ul>
<li>Confinement: not sharing the data.</li>
<li>Immutability: sharing, but keeping the data immutable.</li>
<li>Threadsafe data types: storing the shared mutable data in a single threadsafe datatype.</li>
</ul>
<p>These ideas connect to our three key properties of good software as follows:</p>
<ul>
<li>
<p><strong>Safe from bugs.</strong> We're trying to eliminate a major class of concurrency bugs, race conditions, and eliminate them by design, not just by accident of timing.</p>
</li>
<li>
<p><strong>Easy to understand.</strong> Applying these general, simple design patterns is far more understandable than a complex argument about which thread interleavings are possible and which are not.</p>
</li>
<li>
<p><strong>Ready for change.</strong> We're writing down these justifications explicitly in a thread safety argument, so that maintenance programmers know what the code depends on for its thread safety.</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>