<div class="xblock xblock-public_view xblock-public_view-vertical" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Reading_8_Objectives" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Reading 8 Objectives</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_f5ca859f83b8">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_f5ca859f83b8" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="html" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h4>Software in 6.005</h4>
<table class="table table-striped no-markdown">
<tbody>
<tr>
<th width="33%">Safe from bugs</th>
<th>Easy to understand</th>
<th>Ready for change</th>
</tr>
<tr>
<td>
Correct today and correct in the unknown future.
</td>
<td>
Communicating clearly with future programmers, including future you.
</td>
<td>
Designed to accommodate change without rewriting.
</td>
</tr>
</tbody>
</table>
<h4>Objectives</h4>
<p>After reading the notes and examining the code for this class, you should be able to use message passing (with synchronous queues) instead of shared memory for communication between threads.</p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Two_models_for_concurrency" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Two models for concurrency</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_0315c1d14c3a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_0315c1d14c3a" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="html" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="two_models_for_concurrency">Two models for concurrency</h2>
<div data-outline="two_models_for_concurrency">
<p>In our introduction to concurrency, we saw <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-two-models">two models for concurrent programming</a>: <em>shared memory</em> and <em>message passing</em>.</p>
<ul>
<li>
<div class="panel panel-figure pull-right pull-margin" style="margin-top:-1em"><img src="/assets/courseware/v1/ad443ebc4c017f384effbc6d73b4a1d5/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/08-multiprocessor.png" alt="multiprocessor shared memory" width="200"></div>
<p>In the <strong>shared memory</strong> model, concurrent modules interact by reading and writing shared mutable objects in memory. Creating multiple threads inside a single Java process is our primary example of shared-memory concurrency.</p>
</li>
<li>
<p>In the <strong>message passing</strong> model, concurrent modules interact by sending immutable messages to one another over a communication channel. We've had one example of message passing so far: the <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-client-server">client/server pattern</a>, in which clients and servers are concurrent processes, often on different machines, and the communication channel is a <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-client-server#network_sockets">network socket</a>.</p>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/04342e5183dd4c0c3428016bde120c17/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/08-network.png" alt="network message passing" width="200"></div>
</li>
</ul>
<p>The message passing model has several advantages over the shared memory model, which boil down to greater safety from bugs. In message-passing, concurrent modules interact <em>explicitly</em>, by passing messages through the communication channel, rather than <em>implicitly</em> through mutation of shared data. The implicit interaction of shared memory can too easily lead to <em>inadvertent</em> interaction, sharing and manipulating data in parts of the program that don't know they're concurrent and aren't cooperating properly in the thread safety strategy. Message passing also shares only immutable objects (the messages) between modules, whereas shared memory <em>requires</em> sharing mutable objects, which we have already seen can be <a href="//courses.edx.org/courses/course-v1:MITx+6.005.1x+3T2016/jump_to_id/vertical-risks-of-mutation">a source of bugs</a>.</p>
<p>We'll discuss in this reading how to implement message passing within a single process, as opposed to between processes over the network. We'll use <strong>blocking queues</strong> (an existing threadsafe type) to implement message passing between threads within a process.</p>
</div>
<h2 id="message_passing_with_threads">Message passing with threads</h2>
<div data-outline="message_passing_with_threads">
<p>We've previously talked about message passing between processes: <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-client-server#network_sockets">clients and servers communicating over network sockets</a>. We can also use message passing between threads within the same process, and this design is often preferable to a shared memory design with locks, which we'll talk about in the next reading.</p>
<p>Use a synchronized queue for message passing between threads. The queue serves the same function as the buffered network communication channel in client/server message passing. Java provides the <a href="http://docs.oracle.com/javase/8/docs/api/?java/util/concurrent/BlockingQueue.html"><code>BlockingQueue</code></a> interface for queues with blocking operations:</p>
<p>In an ordinary <a href="http://docs.oracle.com/javase/8/docs/api/?java/util/Queue.html"><code>Queue</code></a>:</p>
<ul>
<li><code>add(e)</code> adds element <code>e</code> to the end of the queue.</li>
<li><code>remove()</code> removes and returns the element at the head of the queue, or throws an exception if the queue is empty.</li>
</ul>
<p>A <a href="http://docs.oracle.com/javase/8/docs/api/?java/util/concurrent/BlockingQueue.html"><code>BlockingQueue</code></a> extends this interface:</p>
<blockquote>
<p>additionally supports operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an element.</p>
</blockquote>
<ul>
<li><strong><code>put(e)</code></strong> <em>blocks</em> until it can add element <code>e</code> to the end of the queue (if the queue does not have a size bound, <code>put</code> will not block).</li>
<li><strong><code>take()</code></strong> <em>blocks</em> until it can remove and return the element at the head of the queue, waiting until the queue is non-empty.</li>
</ul>
<p>When you are using a <code>BlockingQueue</code> for message passing between threads, make sure to use the <code>put()</code> and <code>take()</code> operations, not <strike class="no-markdown"><code>add()</code> and <code>remove()</code></strike>.</p>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/33285ef1e095cb38b8490e574b05fad9/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/08-producer-consumer.png" alt="producer-consumer message passing" width="240"></div>
<p>Analogous to the client/server pattern for message passing over a network is the <strong>producer-consumer design pattern</strong> for message passing between threads. Producer threads and consumer threads share a synchronized queue. Producers put data or requests onto the queue, and consumers remove and process them. One or more producers and one or more consumers might all be adding and removing items from the same queue. This queue must be safe for concurrency.</p>
<p>Java provides two implementations of <code>BlockingQueue</code>:</p>
<ul>
<li><a href="http://docs.oracle.com/javase/8/docs/api/?java/util/concurrent/ArrayBlockingQueue.html"><code>ArrayBlockingQueue</code></a> is a fixed-size queue that uses an array representation.
<code>put</code>ting a new item on the queue will block if the queue is full.</li>
<li><a href="http://docs.oracle.com/javase/8/docs/api/?java/util/concurrent/LinkedBlockingQueue.html"><code>LinkedBlockingQueue</code></a> is a growable queue using a linked-list representation. If no maximum capacity is specified, the queue will never fill up, so <code>put</code> will never block.</li>
</ul>
<p>Unlike the streams of bytes sent and received by sockets, these synchronized queues (like normal collections classes in Java) can hold objects of an arbitrary type. Instead of designing a wire protocol, we must choose or design a type for messages in the queue.
<strong>It must be an immutable type.</strong> And just as we did with operations on a threadsafe ADT or messages in a wire protocol, we must design our messages here to prevent race conditions and enable clients to perform the atomic operations they need.</p>
<h3 id="bank_account_example">Bank account example</h3>
<div data-outline="bank_account_example">
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/bfc078652f4528b04976dca395432f94/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/08-message-passing-bank-account.png" alt="message passing model for bank accounts" width="500"></div>
<p>Our first example of message passing was the <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-message-passing">bank account example</a>.</p>
<p>Each cash machine and each account is its own module, and modules interact by sending messages to one another. Incoming messages arrive on a queue.</p>
<p>We designed messages for <code>get-balance</code> and <code>withdraw</code>, and said that each cash machine checks the account balance before withdrawing to prevent overdrafts:</p><pre><code class="hljs cpp">get-balance
<span class="hljs-keyword">if</span> balance >= <span class="hljs-number">1</span> then withdraw <span class="hljs-number">1</span></code></pre>
<p>But it is still possible to interleave messages from two cash machines so they are both fooled into thinking they can safely withdraw the last dollar from an account with only $1 in it.</p>
<p>We need to choose a better atomic operation: <code>withdraw-if-sufficient-funds</code> would be a better operation than just <code>withdraw</code>.</p>
</div>
</div>
<h2 id="implementing_message_passing_with_queues">Implementing message passing with queues</h2>
<div data-outline="implementing_message_passing_with_queues">
<p>Here's a message passing module for squaring integers:</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/** Squares integers. */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Squarer</span> </span>{
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> BlockingQueue<Integer> in;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> BlockingQueue<SquareResult> out;
<span class="hljs-comment">// Rep invariant: in, out != null</span>
<span class="hljs-comment handout-javadoc-comment">/** Make a new squarer.
* <span class="hljs-doctag">@param</span> requests queue to receive requests from
* <span class="hljs-doctag">@param</span> replies queue to send replies to */</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Squarer</span><span class="hljs-params">(BlockingQueue<Integer> requests,
BlockingQueue<SquareResult> replies)</span> </span>{
<span class="hljs-keyword">this</span>.in = requests;
<span class="hljs-keyword">this</span>.out = replies;
}
<span class="hljs-comment handout-javadoc-comment">/** Start handling squaring requests. */</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">start</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">new</span> Thread(<span class="hljs-keyword">new</span> Runnable() {
<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-keyword">while</span> (<span class="hljs-keyword">true</span>) {
<span class="hljs-comment">// <span class="hljs-doctag">TODO:</span> we may want a way to stop the thread</span>
<span class="hljs-keyword">try</span> {
<span class="hljs-comment">// block until a request arrives</span>
<span class="hljs-keyword">int</span> x = in.take();
<span class="hljs-comment">// compute the answer and send it back</span>
<span class="hljs-keyword">int</span> y = x * x;
out.put(<span class="hljs-keyword">new</span> SquareResult(x, y));
} <span class="hljs-keyword">catch</span> (InterruptedException ie) {
ie.printStackTrace();
}
}
}
}).start();
}
}</code></pre>
<p>Incoming messages to the <code>Squarer</code> are integers; the squarer knows that its job is to square those numbers, so no further details are required.</p>
<p>Outgoing messages are instances of <code>SquareResult</code>:</p><pre><code class="language-java hljs"><span class="hljs-comment handout-javadoc-comment">/** An immutable squaring result message. */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">SquareResult</span> </span>{
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> input;
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> output;
<span class="hljs-comment handout-javadoc-comment">/** Make a new result message.
* <span class="hljs-doctag">@param</span> input input number
* <span class="hljs-doctag">@param</span> output square of input */</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">SquareResult</span><span class="hljs-params">(<span class="hljs-keyword">int</span> input, <span class="hljs-keyword">int</span> output)</span> </span>{
<span class="hljs-keyword">this</span>.input = input;
<span class="hljs-keyword">this</span>.output = output;
}
<span class="hljs-annotation">@Override</span> <span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">toString</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">return</span> input + <span class="hljs-string">"^2 = "</span> + output;
}
}</code></pre>
<p>We would probably add additional observers to <code>SquareResult</code> so clients can retrieve the input number and output result.</p>
<p>Finally, here's a main method that uses the squarer:</p><pre><code class="language-java hljs"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>{
BlockingQueue<Integer> requests = <span class="hljs-keyword">new</span> LinkedBlockingQueue<>();
BlockingQueue<SquareResult> replies = <span class="hljs-keyword">new</span> LinkedBlockingQueue<>();
Squarer squarer = <span class="hljs-keyword">new</span> Squarer(requests, replies);
squarer.start();
<span class="hljs-keyword">try</span> {
<span class="hljs-comment">// make a request</span>
requests.put(<span class="hljs-number">42</span>);
<span class="hljs-comment">// ... maybe do something concurrently ...</span>
<span class="hljs-comment">// read the reply</span>
System.out.println(replies.take());
} <span class="hljs-keyword">catch</span> (InterruptedException ie) {
ie.printStackTrace();
}
}</code></pre>
<p>It should not surprise us that this code has a very similar flavor to the code for implementing message passing with sockets.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_64b269c5630e" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_fff67ba8819a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_fff67ba8819a" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="html" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-rep-invariant">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-rep-invariant" data-graded="True" data-has-score="True" data-runtime-version="1" data-block-type="problem" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_08-rep-invariant" class="problems-wrapper" role="group"
aria-labelledby="08-rep-invariant-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-rep-invariant" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-rep-invariant/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="08-rep-invariant-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-rep-invariant-problem-progress" tabindex="-1">
Rep invariant
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-rep-invariant-problem-progress"></div>
<div class="problem">
<div>
<pre>
/** An immutable squaring result message. */
public class SquareResult {
private final int input;
private final int output;
/** Make a new result message.
* @param input input number
* @param output square of input */
public SquareResult(int input, int output) {
this.input = input;
this.output = output;
}
@Override public String toString() {
return input + "^2 = " + output;
}
private void checkRep() {
assert /*REP_INVARIANT*/;
}
}
</pre>
<p>Write the rep invariant of SquareResult, as an expression that could be used in the assert statement in checkRep(). Use the minimum number of characters you can without any method calls in your answer.</p>
<p>/*REP_INVARIANT*/</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_08-rep-invariant_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<input type="text" name="input_08-rep-invariant_2_1" id="input_08-rep-invariant_2_1" aria-describedby="status_08-rep-invariant_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_08-rep-invariant_2_1"/>
<span class="status unanswered" id="status_08-rep-invariant_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_08-rep-invariant_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_08-rep-invariant_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Rep invariant" />
<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_08-rep-invariant" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_08-rep-invariant">
<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="08-rep-invariant-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="08-rep-invariant-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="08-rep-invariant-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@08-code-review">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-code-review" data-graded="True" data-has-score="True" data-runtime-version="1" data-block-type="problem" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_08-code-review" class="problems-wrapper" role="group"
aria-labelledby="08-code-review-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-code-review" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-code-review/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="08-code-review-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-code-review-problem-progress" tabindex="-1">
Code review
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-code-review-problem-progress"></div>
<div class="problem">
<div>
<pre>
/** Squares integers. */
public class Squarer {
private final BlockingQueue&lt;Integer&gt; in;
private final BlockingQueue&lt;SquareResult&gt; out;
// Rep invariant: in, out != null
/** Make a new squarer.
* @param requests queue to receive requests from
* @param replies queue to send replies to */
public Squarer(BlockingQueue&lt;Integer&gt; requests,
BlockingQueue&lt;SquareResult&gt; replies) {
this.in = requests;
this.out = replies;
}
/** Start handling squaring requests. */
public void start() {
new Thread(new Runnable() {
public void run() {
while (true) {
// TODO: we may want a way to stop the thread
try {
// block until a request arrives
int x = in.take();
// compute the answer and send it back
int y = x * x;
out.put(new SquareResult(x, y));
} catch (InterruptedException ie) {
ie.printStackTrace();
}
}
}
}).start();
}
}
</pre>
<p>The code above undergoes a code review and produces the following comments. Evaluate the comments.</p>
<p>"The Squarer constructor shouldn&#8217;t be putting references to the two queues directly into its rep; it should make defensive copies."</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_08-code-review_2_1">
<fieldset aria-describedby="status_08-code-review_2_1">
<div class="field">
<input type="radio" name="input_08-code-review_2_1" id="input_08-code-review_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="08-code-review_2_1-choice_0-label" for="input_08-code-review_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_08-code-review_2_1"> True
</label>
</div>
<div class="field">
<input type="radio" name="input_08-code-review_2_1" id="input_08-code-review_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="08-code-review_2_1-choice_1-label" for="input_08-code-review_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_08-code-review_2_1"> False
</label>
</div>
<span id="answer_08-code-review_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_08-code-review_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_08-code-review_solution_1"/>
</div><p>"Squarer.start() has an infinite loop in it, so the thread will never stop until the whole process is stopped."</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_08-code-review_3_1">
<fieldset aria-describedby="status_08-code-review_3_1">
<div class="field">
<input type="radio" name="input_08-code-review_3_1" id="input_08-code-review_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="08-code-review_3_1-choice_0-label" for="input_08-code-review_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_08-code-review_3_1"> True
</label>
</div>
<div class="field">
<input type="radio" name="input_08-code-review_3_1" id="input_08-code-review_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="08-code-review_3_1-choice_1-label" for="input_08-code-review_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_08-code-review_3_1"> False
</label>
</div>
<span id="answer_08-code-review_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_08-code-review_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_08-code-review_solution_2"/>
</div><p>"Squarer" can have only one client using it, because if multiple clients put requests in its input queue, their results will get mixed up in the result queue.</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_08-code-review_4_1">
<fieldset aria-describedby="status_08-code-review_4_1">
<div class="field">
<input type="radio" name="input_08-code-review_4_1" id="input_08-code-review_4_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="08-code-review_4_1-choice_0-label" for="input_08-code-review_4_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_08-code-review_4_1"> True
</label>
</div>
<div class="field">
<input type="radio" name="input_08-code-review_4_1" id="input_08-code-review_4_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="08-code-review_4_1-choice_1-label" for="input_08-code-review_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_08-code-review_4_1"> False
</label>
</div>
<span id="answer_08-code-review_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_08-code-review_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_08-code-review_solution_3"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Code review" />
<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_08-code-review" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_08-code-review">
<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="08-code-review-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="08-code-review-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="08-code-review-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Stopping" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Stopping</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_c9742d591a5a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_c9742d591a5a" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="html" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="stopping">Stopping</h2>
<div data-outline="stopping">
<p>What if we want to shut down the <code>Squarer</code> so it is no longer waiting for new inputs? In the client/server model, if we want the client or server to stop listening for our messages, we close the socket. And if we want the client or server to stop altogether, we can quit that process. But here, the squarer is just another thread in the <em>same</em> process, and we can't “close” a queue.</p>
<p>One strategy is a <em>poison pill</em>: a special message on the queue that signals the consumer of that message to end its work. To shut down the squarer, since its input messages are merely integers, we would have to choose a magic poison integer (everyone knows the square of 0 is 0 right? no one will need to ask for the square of 0…) or use null (don't use null). Instead, we might change the type of elements on the requests queue to an ADT:</p><pre><code class="hljs ini"><span class="hljs-setting">SquareRequest = <span class="hljs-value">IntegerRequest + StopRequest</span></span>
</code></pre>
<p>with operations:</p><pre><code class="hljs java">input : SquareRequest → <span class="hljs-keyword">int</span>
shouldStop : SquareRequest → <span class="hljs-keyword">boolean</span>
</code></pre>
<p>and when we want to stop the squarer, we enqueue a <code>StopRequest</code> where <code>shouldStop</code> returns <code>true</code>.</p>
<p>For example, in <code>Squarer.start()</code>:</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">run</span><span class="hljs-params">()</span> </span>{
<span class="hljs-keyword">while</span> (<span class="hljs-keyword">true</span>) {
<span class="hljs-keyword">try</span> {
<span class="hljs-comment">// block until a request arrives</span>
SquareRequest req = in.take();
<span class="hljs-comment">// see if we should stop</span>
<span class="hljs-keyword">if</span> (req.shouldStop()) { <span class="hljs-keyword">break</span>; }
<span class="hljs-comment">// compute the answer and send it back</span>
<span class="hljs-keyword">int</span> x = req.input();
<span class="hljs-keyword">int</span> y = x * x;
out.put(<span class="hljs-keyword">new</span> SquareResult(x, y));
} <span class="hljs-keyword">catch</span> (InterruptedException ie) {
ie.printStackTrace();
}
}
}</code></pre>
<p>It is also possible to <em>interrupt</em> a thread by calling its <code>interrupt()</code> method. If the thread is blocked waiting, the method it's blocked in will throw an <code>InterruptedException</code> (that's why we have to try-catch that exception almost any time we call a blocking method). If the thread was not blocked, an <em>interrupted</em> flag will be set. The thread must check for this flag to see whether it should stop working. For example:</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">run</span><span class="hljs-params">()</span> </span>{
<span class="hljs-comment">// handle requests until we are interrupted</span>
<span class="hljs-keyword">while</span> ( ! Thread.interrupted()) {
<span class="hljs-keyword">try</span> {
<span class="hljs-comment">// block until a request arrives</span>
<span class="hljs-keyword">int</span> x = in.take();
<span class="hljs-comment">// compute the answer and send it back</span>
<span class="hljs-keyword">int</span> y = x * x;
out.put(<span class="hljs-keyword">new</span> SquareResult(x, y));
} <span class="hljs-keyword">catch</span> (InterruptedException ie) {
<span class="hljs-comment">// stop</span>
<span class="hljs-keyword">break</span>;
}
}
}</code></pre>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_77f1e86d5091" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_fff67ba8819a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_fff67ba8819a" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="html" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-implementing-poison-pills">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-implementing-poison-pills" data-graded="True" data-has-score="True" data-runtime-version="1" data-block-type="problem" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_08-implementing-poison-pills" class="problems-wrapper" role="group"
aria-labelledby="08-implementing-poison-pills-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-implementing-poison-pills" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-implementing-poison-pills/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="08-implementing-poison-pills-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-implementing-poison-pills-problem-progress" tabindex="-1">
Implementing poison pills
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-implementing-poison-pills-problem-progress"></div>
<div class="problem">
<div><p>Using the data type definition above:</p><pre>
SquareRequest = IntegerRequest + StopRequest
</pre>
For each option below: is the snippet of code a correct outline for how you would implement this in Java that takes maximum advantage of static checking?
For each option below: is the snippet of code a correct outline for how you would implement this in Java that takes maximum advantage of static checking?
<pre>
interface SquareRequest { ... }
class IntegerRequest implements SquareRequest { ... }
class StopRequest implements SquareRequest { ... }
</pre>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_08-implementing-poison-pills_2_1">
<fieldset aria-describedby="status_08-implementing-poison-pills_2_1">
<div class="field">
<input type="radio" name="input_08-implementing-poison-pills_2_1" id="input_08-implementing-poison-pills_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="08-implementing-poison-pills_2_1-choice_0-label" for="input_08-implementing-poison-pills_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_08-implementing-poison-pills_2_1"> Yes
</label>
</div>
<div class="field">
<input type="radio" name="input_08-implementing-poison-pills_2_1" id="input_08-implementing-poison-pills_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="08-implementing-poison-pills_2_1-choice_1-label" for="input_08-implementing-poison-pills_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_08-implementing-poison-pills_2_1"> No
</label>
</div>
<span id="answer_08-implementing-poison-pills_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_08-implementing-poison-pills_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_08-implementing-poison-pills_solution_1"/>
</div><pre>
class SquareRequest { ... }
class IntegerRequest { ... }
class StopRequest { ... }
</pre>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_08-implementing-poison-pills_3_1">
<fieldset aria-describedby="status_08-implementing-poison-pills_3_1">
<div class="field">
<input type="radio" name="input_08-implementing-poison-pills_3_1" id="input_08-implementing-poison-pills_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="08-implementing-poison-pills_3_1-choice_0-label" for="input_08-implementing-poison-pills_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_08-implementing-poison-pills_3_1"> Yes
</label>
</div>
<div class="field">
<input type="radio" name="input_08-implementing-poison-pills_3_1" id="input_08-implementing-poison-pills_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="08-implementing-poison-pills_3_1-choice_1-label" for="input_08-implementing-poison-pills_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_08-implementing-poison-pills_3_1"> No
</label>
</div>
<span id="answer_08-implementing-poison-pills_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_08-implementing-poison-pills_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_08-implementing-poison-pills_solution_2"/>
</div><pre>
class SquareRequest {
private final String requestType;
public static final String INTEGER_REQUEST = "integer";
public static final String STOP_REQUEST = "stop";
...
}
</pre>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_08-implementing-poison-pills_4_1">
<fieldset aria-describedby="status_08-implementing-poison-pills_4_1">
<div class="field">
<input type="radio" name="input_08-implementing-poison-pills_4_1" id="input_08-implementing-poison-pills_4_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="08-implementing-poison-pills_4_1-choice_0-label" for="input_08-implementing-poison-pills_4_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_08-implementing-poison-pills_4_1"> Yes
</label>
</div>
<div class="field">
<input type="radio" name="input_08-implementing-poison-pills_4_1" id="input_08-implementing-poison-pills_4_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="08-implementing-poison-pills_4_1-choice_1-label" for="input_08-implementing-poison-pills_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_08-implementing-poison-pills_4_1"> No
</label>
</div>
<span id="answer_08-implementing-poison-pills_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_08-implementing-poison-pills_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_08-implementing-poison-pills_solution_3"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Implementing poison pills" />
<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_08-implementing-poison-pills" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_08-implementing-poison-pills">
<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="08-implementing-poison-pills-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="08-implementing-poison-pills-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="08-implementing-poison-pills-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Thread_safety_arguments_with_message_passing" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Thread safety arguments with message passing</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_8352a9b95119">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_8352a9b95119" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="html" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="thread_safety_arguments_with_message_passing">Thread safety arguments with message passing</h2>
<div data-outline="thread_safety_arguments_with_message_passing">
<p>A thread safety argument with message passing might rely on:</p>
<ul>
<li>
<p><strong>Existing threadsafe data types</strong> for the synchronized queue. This queue is definitely shared and definitely mutable, so we must ensure it is safe for concurrency.</p>
</li>
<li>
<p><strong>Immutability</strong> of messages or data that might be accessible to multiple threads at the same time.</p>
</li>
<li>
<p><strong>Confinement</strong> of data to individual producer/consumer threads. Local variables used by one producer or consumer are not visible to other threads, which only communicate with one another using messages in the queue. </p>
</li>
<li>
<p><strong>Confinement</strong> of mutable messages or data that are sent over the queue but will only be accessible to one thread at a time. This argument must be carefully articulated and implemented. But if one module drops all references to some mutable data like a hot potato as soon as it puts them onto a queue to be delivered to another thread, only one thread will have access to those data at a time, precluding concurrent access.</p>
</li>
</ul>
<p>In comparison to synchronization, message passing can make it easier for each module in a concurrent system to maintain its own thread safety invariants. We don't have to reason about multiple threads accessing shared data if the data are instead transferred between modules using a threadsafe communication channel.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_0f147cc390f8" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_fff67ba8819a">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_fff67ba8819a" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="html" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-message-passing">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-message-passing" data-graded="True" data-has-score="True" data-runtime-version="1" data-block-type="problem" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_08-message-passing" class="problems-wrapper" role="group"
aria-labelledby="08-message-passing-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-message-passing" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-message-passing/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="08-message-passing-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-message-passing-problem-progress" tabindex="-1">
Message passing
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-message-passing-problem-progress"></div>
<div class="problem">
<div>
<p>Leif Noad just started a new job working for a stock trading company:</p>
<pre>
public interface Trade {
public int numShares();
public String stockName();
}
public class TradeWorker implements Runnable {
private final Queue&lt;Trade&gt; tradesQueue;
public TradeWorker(Queue&lt;Trade&gt; tradesQueue) {
this.tradesQueue = tradesQueue;
}
public void run() {
while (true) {
Trade trade = tradesQueue.poll();
TradeProcessor.handleTrade(trade.numShares(), trade.stockName());
}
}
}
public class TradeProcessor {
public static void handleTrade(int numShares, String stockName) {
/* ... process the trade ... takes a while ... */
}
}
</pre>
<p>What are <code>TradeWorker</code>s?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_08-message-passing_2_1">
<fieldset aria-describedby="status_08-message-passing_2_1">
<div class="field">
<input type="checkbox" name="input_08-message-passing_2_1[]" id="input_08-message-passing_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="08-message-passing_2_1-choice_0-label" for="input_08-message-passing_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_08-message-passing_2_1"> separate threads
</label>
</div>
<div class="field">
<input type="checkbox" name="input_08-message-passing_2_1[]" id="input_08-message-passing_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="08-message-passing_2_1-choice_1-label" for="input_08-message-passing_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_08-message-passing_2_1"> objects that can be passed to the thread constructor
</label>
</div>
<div class="field">
<input type="checkbox" name="input_08-message-passing_2_1[]" id="input_08-message-passing_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="08-message-passing_2_1-choice_2-label" for="input_08-message-passing_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_08-message-passing_2_1"> producers in the producer/consumer pattern
</label>
</div>
<div class="field">
<input type="checkbox" name="input_08-message-passing_2_1[]" id="input_08-message-passing_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="08-message-passing_2_1-choice_3-label" for="input_08-message-passing_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_08-message-passing_2_1"> consumers in the producer/consumer pattern
</label>
</div>
<span id="answer_08-message-passing_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_08-message-passing_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_08-message-passing_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Message passing" />
<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_08-message-passing" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_08-message-passing">
<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="08-message-passing-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="08-message-passing-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="08-message-passing-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@08-mistakes-were-made">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-mistakes-were-made" data-graded="True" data-has-score="True" data-runtime-version="1" data-block-type="problem" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_08-mistakes-were-made" class="problems-wrapper" role="group"
aria-labelledby="08-mistakes-were-made-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-mistakes-were-made" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-mistakes-were-made/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="08-mistakes-were-made-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-mistakes-were-made-problem-progress" tabindex="-1">
Mistakes were made
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@08-mistakes-were-made-problem-progress"></div>
<div class="problem">
<div>
<p>Suppose we have several <code>TradeWorker</code>s processing trades off the same shared queue.</p>
<p>Notice that we are <em>not using <code>BlockingQueue</code>!</em> Workers call <code>poll</code> to retrieve items from the queue.</p>
<p>Which of the following can happen?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_08-mistakes-were-made_2_1">
<fieldset aria-describedby="status_08-mistakes-were-made_2_1">
<div class="field">
<input type="checkbox" name="input_08-mistakes-were-made_2_1[]" id="input_08-mistakes-were-made_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="08-mistakes-were-made_2_1-choice_0-label" for="input_08-mistakes-were-made_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_08-mistakes-were-made_2_1"> trades are not processed by the <code>TradeProcessor</code> in the same order they were in on the queue
</label>
</div>
<div class="field">
<input type="checkbox" name="input_08-mistakes-were-made_2_1[]" id="input_08-mistakes-were-made_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="08-mistakes-were-made_2_1-choice_1-label" for="input_08-mistakes-were-made_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_08-mistakes-were-made_2_1"> a single trade can be processed multiple times
</label>
</div>
<div class="field">
<input type="checkbox" name="input_08-mistakes-were-made_2_1[]" id="input_08-mistakes-were-made_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="08-mistakes-were-made_2_1-choice_2-label" for="input_08-mistakes-were-made_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_08-mistakes-were-made_2_1"> we can crash with a <code>NullPointerException</code>
</label>
</div>
<span id="answer_08-mistakes-were-made_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_08-mistakes-were-made_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_08-mistakes-were-made_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Mistakes were made" />
<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_08-mistakes-were-made" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_08-mistakes-were-made">
<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="08-mistakes-were-made-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="08-mistakes-were-made-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="08-mistakes-were-made-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Reading_8_Summary" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="vertical" data-init="VerticalStudentView" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<h2 class="hd hd-2 unit-title">Reading 8 Summary</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_835a6fc23626">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-request-token="0544f54ee99711efb7c40e0e3c45b88f" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_835a6fc23626" data-graded="True" data-has-score="False" data-runtime-version="1" data-block-type="html" data-init="XBlockToXModuleShim" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-runtime-class="LmsRuntime">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="summary">Summary</h2>
<div data-outline="summary">
<ul>
<li>
<p>Rather than synchronize with locks, message passing systems synchronize on a shared communication channel, e.g. a stream or a queue.</p>
</li>
<li>
<p>Threads communicating with blocking queues is a useful pattern for message passing within a single process.</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>