367 lines
18 KiB
HTML
Executable file
367 lines
18 KiB
HTML
Executable file
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
|
||
<html>
|
||
<head>
|
||
<title>Homework 3 solutions</title>
|
||
</head>
|
||
|
||
<body>
|
||
<h1>Homework 3 solutions</h1>
|
||
|
||
<ol start=1 type=1>
|
||
<li class=MsoNormal style='mso-list:l1 level1 lfo3;tab-stops:list .5in'><b>7.1.
|
||
Busy Waiting<br>
|
||
<br>
|
||
</b><span style='font-weight:normal'><i>Busy waiting</i></span> is
|
||
continuously executing (using the CPU) while waiting for something to
|
||
happen. This is typically implemented by spinning; e.g. testing a variable
|
||
in a tight loop until it changes. <br>
|
||
<br>
|
||
The alternative to busy waiting is <i>blocking</i><span style='font-style:
|
||
normal'>, where the waiting process is suspended an other processes can
|
||
execute while the process is waiting.<br style='mso-special-character:
|
||
line-break'>
|
||
<![if !supportLineBreakNewLine]><br style='mso-special-character:line-break'>
|
||
<![endif]></span></li>
|
||
<li class=MsoNormal style='mso-list:l1 level1 lfo3;tab-stops:list .5in'><b>7.2.
|
||
Spinlocks<br>
|
||
<br>
|
||
</b><span style='font-weight:normal'>Spinlocks are not appropriate for
|
||
uniprocessor systems because by definition only one process is executing
|
||
at a time. As a result, no other process can ever change release the lock
|
||
– the scheduler has to intervene and switch out the spinning process
|
||
first. As a result, the spinning process might as well suspend itself
|
||
instead of spinning. Or, locking should disable interrupts to prevent the scheduler
|
||
from running, so that the process is guaranteed that it can execute the
|
||
entire critical section.<br>
|
||
<br>
|
||
On a 2 CPU multiprocessor, for example, a process scheduled on processor 1
|
||
can release the lock while a process on processor 2 is spinning on it. No
|
||
interrupt is needed. Thus, spinlocks are not necessarily wasteful on a
|
||
multiprocessor.</span></li>
|
||
</ol>
|
||
|
||
|
||
<p class=MsoNormal>Synchronization Problems</p>
|
||
|
||
<p class=MsoNormal>Notes:</p>
|
||
|
||
<p class=MsoNormal style='margin-left:.5in;text-indent:-.25in;mso-list:l2 level1 lfo7;
|
||
tab-stops:list .5in'><![if !supportLists]><span style='font-family:"Times New Roman"'>-<span
|
||
style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]>Please use real binary semaphores, counting semaphores,
|
||
or monitors. If you invent your own synchronization method, there is a 99% chance
|
||
you will get it wrong. Plus it makes it very hard to grade - we look very
|
||
closely and are more likely to find problems. If you must do this, provide an
|
||
implementation of your construct, because otherwise we don't know if:</p>
|
||
|
||
<p class=MsoNormal style='margin-left:1.0in;text-indent:-.25in;mso-list:l2 level2 lfo7;
|
||
tab-stops:list 1.0in'><![if !supportLists]><span style='font-family:"Courier New"'>o<span
|
||
style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]>It is possible to implement</p>
|
||
|
||
<p class=MsoNormal style='margin-left:1.0in;text-indent:-.25in;mso-list:l2 level2 lfo7;
|
||
tab-stops:list 1.0in'><![if !supportLists]><span style='font-family:"Courier New"'>o<span
|
||
style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]>How it works</p>
|
||
|
||
<p class=MsoNormal style='margin-left:.5in;text-indent:-.25in;mso-list:l2 level1 lfo7;
|
||
tab-stops:list .5in'><![if !supportLists]><span style='font-family:"Times New Roman"'>-<span
|
||
style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]>If you use semaphores, you must specify initial values
|
||
for your semaphores (mandatory).</p>
|
||
|
||
<p class=MsoNormal style='margin-left:.5in;text-indent:-.25in;mso-list:l2 level1 lfo7;
|
||
tab-stops:list .5in'><![if !supportLists]><span style='font-family:"Times New Roman"'>-<span
|
||
style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]>If you have a shared state, you should say what mutex
|
||
protects the shared state (not mandatory)</p>
|
||
|
||
<p class=MsoNormal style='margin-left:.5in;text-indent:-.25in;mso-list:l2 level1 lfo7;
|
||
tab-stops:list .5in'><![if !supportLists]><span style='font-family:"Times New Roman"'>-<span
|
||
style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]>With semaphores, if you wake up on one semaphore and then
|
||
call signal() to wake up the next waiter you might wake yourself up -
|
||
semaphores have history, so your next wait might be the one that awakes,
|
||
because the other waiters might have been context switchted out before they
|
||
call wait().</p>
|
||
|
||
<p class=MsoNormal style='margin-left:.5in;text-indent:-.25in;mso-list:l2 level1 lfo7;
|
||
tab-stops:list .5in'><![if !supportLists]><span style='font-family:"Times New Roman"'>-<span
|
||
style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]>With semaphores, you shouldn't wait while holding a
|
||
mutex, unless the routine signaling you does not need the mutex to wake you up.</p>
|
||
|
||
<p class=MsoNormal style='margin-left:.5in;text-indent:-.25in;mso-list:l2 level1 lfo7;
|
||
tab-stops:list .5in'><![if !supportLists]><span style='font-family:"Times New Roman"'>-<span
|
||
style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]>With monitors, you don't need to grab a mutex (or,
|
||
shudder, a condition variable) to access shared state. The monitor, by
|
||
definition, ensures mutual exclusion.</p>
|
||
|
||
<p class=MsoNormal style='margin-left:.5in;text-indent:-.25in;mso-list:l2 level1 lfo7;
|
||
tab-stops:list .5in'><![if !supportLists]><span style='font-family:"Times New Roman"'>-<span
|
||
style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]>With monitors, wait() doesn't take any parameters - it
|
||
just waits until somebody then calls signal().</p>
|
||
|
||
<p class=MsoNormal style='margin-left:.5in;text-indent:-.25in;mso-list:l2 level1 lfo7;
|
||
tab-stops:list .5in'><![if !supportLists]><span style='font-family:"Times New Roman"'>-<span
|
||
style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]>When writing synchronization code, you should try to
|
||
minimize the number of context switches and the number of times a process is
|
||
awoken when it doesn't need to be. Ideally, in a while() loop, a process should
|
||
only be woken once.<br style='mso-special-character:line-break'>
|
||
<![if !supportLineBreakNewLine]><br style='mso-special-character:line-break'>
|
||
<![endif]></p>
|
||
|
||
<ol start=3 type=1>
|
||
<li class=MsoNormal style='mso-list:l1 level1 lfo3;tab-stops:list .5in'><b>7.8.
|
||
Sleeping-barber problem.</b><span style='font-weight:normal'> </span></li>
|
||
</ol>
|
||
|
||
<h2 style='margin-left:.5in;mso-list:l0 level1 lfo10'><![if !supportLists]><span
|
||
style='font-size:12.0pt'><span style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]><span style='font-size:12.0pt'>Barbershop Requirements:<o:p></o:p></span></h2>
|
||
|
||
<h3 style='margin-left:.5in;mso-list:l0 level1 lfo11'><![if !supportLists]><span
|
||
style='font-size:10.0pt'>-<span style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]><span style='font-size:10.0pt'>Barber sleeps if no
|
||
customers waiting<o:p></o:p></span></h3>
|
||
|
||
<h3 style='margin-left:.5in;mso-list:l0 level1 lfo11'><![if !supportLists]><span
|
||
style='font-size:10.0pt'>-<span style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]><span style='font-size:10.0pt'>Customers leave if no
|
||
chairs for waiting<o:p></o:p></span></h3>
|
||
|
||
<h3 style='margin-left:.5in;mso-list:l0 level1 lfo11'><![if !supportLists]><span
|
||
style='font-size:10.0pt'>-<span style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]><span style='font-size:10.0pt'>Waiting customers can't
|
||
leave until haircut done.<o:p></o:p></span></h3>
|
||
|
||
<h2 style='margin-left:.5in;mso-list:l0 level1 lfo10'><![if !supportLists]><span
|
||
style='font-size:12.0pt'><span style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]><span style='font-size:12.0pt'>Solution: we use
|
||
semaphores<o:p></o:p></span></h2>
|
||
|
||
<h3 style='margin-left:.5in;mso-list:l0 level1 lfo11'><![if !supportLists]><span
|
||
style='font-size:10.0pt'>-<span style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]><span style='font-size:10.0pt'>Mutex = 1<o:p></o:p></span></h3>
|
||
|
||
<h3 style='margin-left:.5in;mso-list:l0 level1 lfo11'><![if !supportLists]><span
|
||
style='font-size:10.0pt'>-<span style='font:7.0pt "Times New Roman"'>
|
||
</span></span><![endif]><span style='font-size:10.0pt'>counting:
|
||
barber_sleeping, customer_queue, cut_done<o:p></o:p></span></h3>
|
||
|
||
|
||
<b>Barber Code</b><br>
|
||
<br>
|
||
|
||
<pre>
|
||
wait(mutex)
|
||
if (customers_waiting == 0) {
|
||
signal(mutex);
|
||
wait(barber_sleeping);
|
||
wait(mutex);
|
||
}
|
||
customers_waiting--;
|
||
signal(mutex);
|
||
signal(customer_queue);
|
||
do_cut_hair();
|
||
signal(cut_done);
|
||
</pre>
|
||
|
||
<b>Customer Code</b><br>
|
||
|
||
<pre>
|
||
wait(mutex);
|
||
if (customers_waiting == n) {
|
||
signal(mutex);
|
||
return;
|
||
}
|
||
customers_waiting++;
|
||
if (customers_waiting == 1) {
|
||
signal(barber_sleeping);
|
||
}
|
||
signal(mutex);
|
||
wait(customer_queue);
|
||
get_hair_cut();
|
||
wait(cut_done);
|
||
</pre>
|
||
|
||
<b>As a monitor</b>
|
||
|
||
<pre>
|
||
monitor barbershop {
|
||
int num_waiting;
|
||
condition get_cut;
|
||
condition barber_asleep;
|
||
condition in_chair;
|
||
condition cut_done;
|
||
|
||
Barber routine
|
||
barber() {
|
||
while (1);
|
||
while (num_waiting == 0) {
|
||
barber_asleep.wait();
|
||
}
|
||
customer_waiting.signal();
|
||
in_chair.wait();
|
||
give_hait_cut();
|
||
cut_done.signal();
|
||
}
|
||
Customer routine
|
||
customer () {
|
||
if (num_waiting == n) {
|
||
return;
|
||
}
|
||
if (num_waiting == 0) {
|
||
barber_asleep.signal();
|
||
}
|
||
customer_waiting.wait();
|
||
in_char.signal();
|
||
get_hair_cut();
|
||
cut_done.wait();
|
||
}
|
||
</pre>
|
||
|
||
<p style='margin-left:.5in;tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><![if !supportEmptyParas]> <![endif]><o:p></o:p></p>
|
||
|
||
<p style='margin-left:.5in;text-indent:-.25in;mso-list:l1 level1 lfo3;
|
||
tab-stops:list .5in'><![if !supportLists]>7.<span style='font:7.0pt "Times New Roman"'>
|
||
</span><![endif]><b>7.9. The Cigarette-Smokers Problem.</b><span
|
||
style='font-weight:normal'> </span></p>
|
||
|
||
<p style='margin-left:.5in;tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'>Semaphores
|
||
are a convenient mechanism for implementing this, because they remember what
|
||
elements are on the table.</p>
|
||
|
||
<p style='margin-left:.5in;tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><span
|
||
style='font-family:"Courier New"'>Sempahore TobaccoAndPaper = 0;<br>
|
||
Sempahore PaperAndMatches = 0;<br>
|
||
Semaphore MatchesAndTobacco = 0;<br>
|
||
Sempaphore DoneSmoking = 1;<o:p></o:p></span></p>
|
||
|
||
<p class=MsoNormal style='margin-left:.5in;tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><span
|
||
style='font-family:"Courier New"'>void agent() <br>
|
||
{<br>
|
||
wait(DoneSmoking);<br>
|
||
int r = rand() % 3;<o:p></o:p></span></p>
|
||
|
||
<p class=MsoNormal style='margin-left:.5in;tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><span
|
||
style='font-family:"Courier New"'><br>
|
||
//<br>
|
||
// Signal which ever combination was<br>
|
||
// chosen.<br>
|
||
//<br style='mso-special-character:line-break'>
|
||
<![if !supportLineBreakNewLine]><br style='mso-special-character:line-break'>
|
||
<![endif]><o:p></o:p></span></p>
|
||
|
||
<p class=MsoNormal style='margin-left:.5in;tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><span
|
||
style='font-family:"Courier New"'><br>
|
||
switch( r ) {<br>
|
||
case 0:
|
||
signal(TobaccoAndPaper);<br>
|
||
break;<br>
|
||
case 1:
|
||
signal(PaperAndMatches);<br>
|
||
break;<br>
|
||
case 2:
|
||
signal(MatchesAndTobacco);<br>
|
||
break;<br>
|
||
}<br>
|
||
}<br>
|
||
<br>
|
||
void Smoker_A()<br>
|
||
{<br>
|
||
while(true) {<br>
|
||
<br>
|
||
//<br>
|
||
// Wait for our
|
||
two ingredients<br>
|
||
//<br>
|
||
<br>
|
||
|
||
wait(TobaccoAndPaper);<br>
|
||
smoke();<br>
|
||
<br>
|
||
//<br>
|
||
// Signal that
|
||
we're done smoking<br>
|
||
// so the next
|
||
agent can put down<br>
|
||
// ingredients.<br>
|
||
//<br>
|
||
<br>
|
||
|
||
signal(DoneSmoking);<br>
|
||
}<br>
|
||
}<br style='mso-special-character:line-break'>
|
||
<![if !supportLineBreakNewLine]><br style='mso-special-character:line-break'>
|
||
<![endif]></span></p>
|
||
|
||
<p class=MsoNormal style='margin-left:.5in;tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'>Smoker
|
||
b and c are similar.<span style='font-family:"Courier New"'><o:p></o:p></span></p>
|
||
|
||
<p style='margin-left:.5in;tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'><span
|
||
style="mso-spacerun: yes"> </span></p>
|
||
|
||
<pre style='margin-left:.5in'><span style="mso-spacerun: yes"> </span></pre>
|
||
|
||
<p style='margin-left:.5in;text-indent:-.25in;mso-list:l1 level1 lfo3;
|
||
tab-stops:list .5in'><![if !supportLists]>8.<span style='font:7.0pt "Times New Roman"'>
|
||
</span><![endif]><b>7.15. File-synchronization</b><span style='font-weight:
|
||
normal'> </span></p>
|
||
|
||
<p style='margin-left:.5in;tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'>
|
||
From the book you should know how to use a <i>conditional-wait</i><span
|
||
style='font-style:normal'> construct (priority-based signaling), so we'll use it here. We'll assume for simplicity that no
|
||
process has an id greater than or equal to n (or we'd just print an error
|
||
message). </span></p>
|
||
|
||
<pre style='margin-left:.5in'><![if !supportEmptyParas]> <![endif]><o:p></o:p></pre><pre
|
||
style='margin-left:.5in'> type file = monitor</pre><pre style='margin-left:
|
||
.5in'><span style="mso-spacerun: yes"> </span>var space_available: binary condition</pre><pre
|
||
style='margin-left:.5in'><span style="mso-spacerun: yes"> </span>total: integer</pre><pre
|
||
style='margin-left:.5in'> </pre><pre style='margin-left:.5in'><span style="mso-spacerun: yes"> </span>procedure entry file_open(id)</pre><pre
|
||
style='margin-left:.5in'><span style="mso-spacerun: yes"> </span>begin</pre><pre
|
||
style='margin-left:.5in'><span style="mso-spacerun: yes"> </span>while (total + id >= n)</pre><pre
|
||
style='margin-left:.5in'><span style="mso-spacerun: yes"> </span>space_available.wait(id)</pre><pre
|
||
style='margin-left:.5in'><span style="mso-spacerun: yes"> </span>total = total + id;</pre><pre
|
||
style='margin-left:.5in'><span style="mso-spacerun: yes"> </span>if (total < n - 1)</pre><pre
|
||
style='margin-left:.5in'><span style="mso-spacerun: yes"> </span>space_available.signal();</pre><pre
|
||
style='margin-left:.5in'><span style="mso-spacerun: yes"> </span>end</pre><pre
|
||
style='margin-left:.5in'><![if !supportEmptyParas]> <![endif]><o:p></o:p></pre><pre
|
||
style='margin-left:.5in'><span style="mso-spacerun: yes"> </span>procedure entry file_close(id)</pre><pre
|
||
style='margin-left:.5in'><span style="mso-spacerun: yes"> </span>begin</pre><pre
|
||
style='margin-left:.5in'><span style="mso-spacerun: yes"> </span>total = total - id;</pre><pre
|
||
style='margin-left:.5in'><span style="mso-spacerun: yes"> </span>space_available.signal();</pre><pre
|
||
style='margin-left:.5in'><span style="mso-spacerun: yes"> </span>end</pre>
|
||
|
||
<p class=MsoNormal style='margin-left:.5in;tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt'>What
|
||
happens here? As long as the incoming processes find adequate space available
|
||
(i.e. sums less than n), they will claim that space and open the file. Note
|
||
that since we're using a binary condition, we can signal() at will even if
|
||
nothing is waiting. If a process finds inadequate space, it will block. When a
|
||
process is done, it wakes up the process with the smallest id (the most likely
|
||
to fit in the available space). This process, upon waking, then signals the
|
||
next process if space is still available, but only after successfully claiming
|
||
its own space. At some point (quite possibly with the first process), the space
|
||
made available may not be enough for the waking process, and so a process will
|
||
be woken up prematurely. This is what the loop is for; it will immediately
|
||
block again. </p>
|
||
|
||
|
||
|
||
<ol start=6 type=1>
|
||
<li class=MsoNormal style='mso-list:l1 level1 lfo3;tab-stops:list .5in'><b>8.4
|
||
b<br>
|
||
</b>install traffic lights :)
|
||
<br>
|
||
<li class=MsoNormal style='mso-list:l1 level1 lfo3;tab-stops:list .5in'><b>8.8
|
||
<br>
|
||
</b>The system can always make progress in all possible
|
||
allocation scenarios (use pigeonhole principle to show this).
|
||
</ol>
|
||
<hr>
|
||
</body>
|
||
</html>
|