📄 http:^^www.cs.wisc.edu^~cs537-1^dphil-correction.html
字号:
Date: Tue, 05 Nov 1996 20:57:28 GMTServer: NCSA/1.5Content-type: text/htmlLast-modified: Thu, 31 Oct 1996 21:38:54 GMTContent-length: 7757<html><head><title>CS 537 - Fix for Project 2</title></head><body bgcolor="#ffffff"><h1>Fix for Project 2</h1>As I mentioned in class, the<!WA0><a href="http://www.cs.wisc.edu/~cs537-1/project2.html#details">suggested algorithm</a>for Project 2 algorithm 2has a very small change of deadlocking if preemptive scheduling isin effect.A couple of teams have actually experienced this problem, showing thatMurphy's law is valid: If something can go wrong, it eventually will.Deadlocks due to the bug have been reported under the Windows Javaimplementation, which has built-in preemptive scheduling. I do no know ifanybody has observed them under Solaris, even with the ThreadScheduler.<p>Disclaimers:<ul><li>This problem applies <em>only</em> to the second (``hygienic'') algorithm.If your algorithm 1 deadlocks, you have some other bug in your program.<li>You are <em>not</em> required to fix this bug to get full credit for theassignment. I'm only telling your about it in case you'rehaving problems tracking down the cause of a deadlock andsuspect it might be due to this problem.<li>It is very likely that the deadlock you're seeing is <em>not</em>due to this problem, but to some more ``ordinary'' bug in your program.If your program deadlocks under Solaris without the ThreadSchedulerit is <em>certainly</em> because of some other bug.(To turn off the ThreadScheduler, simply comment out the line<samp><font color="0f0fff">sched.start()</font></samp>.)If it deadlocks only under Windows, it is more likely (but not certain)that the bug is caused by this problem.</ul>The problem arises because synchronized methods contain calls to othersynchronized methods <em>and</em> it is possible to set up a circularpattern of calls between distinct objects.For example, if A and B are neighboring Philosopher objects,A.takeForks() calls B.requestFork(), and B.putForks() calls A.giveFork().Suppose thread t1 is preempted while active (not waiting) in A.takeForks(),and thread t2 is allowed to enter B.putForks(). At this point,t1 is locking A and t2 is locking B. When t2 calls A.giveFork() itwill block waiting for A's mutex, and when t1 is subsequently resumedand calls B.requestFork() it will block on B's mutex. At that pointt1 and t2 are deadlocked.<p>In today's class (Oct 9), Joni Baker pointed out that this particularscenario cannot occur if the code is carefully written to preventduplicate requests, as in the sample code I wrote on the blackboard.B.putForks() only calls A.giveFork() if B has previously requestedthe fork from B, butA.takeForks() only calls B.requestFork() if A has <em>not</em> previouslyrequested it.In class, I said that a more complicated scenario could be devised toshow that deadlock is still possible, but couldn't think of one on the spot.It seems to require at least three philosophers.<p>Consider a circular pattern of philosophers, A, B, and C, each pair sharingone fork (i.e., a three-philosopher version of the original dining philosophers problem).Assume B is eating, so he has the forks he shares with A and C,and A has the fork she shares with C.Let t<sub>A</sub>, t<sub>B</sub>, and t<sub>C</sub> represents the threads for philosophers A, B, and C.Suppose C gets hungry just before B finishes eating, and A gets hungry justafter.The following sequence of events is possible.<ul><li>C gets hungry, so thread t<sub>A</sub> enters C.takeForks() and calls B.requestFork(),which returns <samp><font color="0f0fff">false</font></samp> because B is eating.<li>Thread t<sub>C</sub> is preempted.<li>B finishes eating, so t<sub>B</sub> enters putForks(), and seeing that there is arequest from C, tries to call C.giveFork().Thread t<sub>B</sub> is blocked because t<sub>C</sub> is still active in C.takeForks().<li>A gets hungry, so t<sub>A</sub> enters A.getForks(). She already has the forkshe shares with C, so t<sub>A</sub> tries to call B.requestFork(), butis blocked because t<sub>B</sub> is still active in B.putForks().<li>Thread t<sub>C</sub> is resumed and tries to call A.getFork().</ul>At that point the three threads are deadlocked.<p>Here is the example I couldn't show this morning because there wasno projector. This is the original version of takeForks() fromthe TA's solution to the project.<pre><font color="0f0fff">private synchronized void takeForks() { state = HUNGRY; int forksHave = 0; // Number of forks currently owned while (forksHave < forks.length) { for (int i = 0; i < forks.length; i++) { if (forks[i].have) forksHave++; else if (!forks[i].haveRequested) { if (phil[forks[i].neighborId].requestFork(forks[i].forkId)){ forks[i].clean = true; forks[i].have = true; forksHave++; } else forks[i].haveRequested = true; } } } if (forksHave < forks.length) { forksHave = 0; try { wait(); } catch (InterruptedException e) {} } } state = EATING;}</font></pre>The trick is to split takeForks into two pieces.The first, called forksNeeded(), is a <samp><font color="0f0fff">synchronized</font></samp> procedure thatdoes all the necessary manipulation of shared variables. The remainingcode does not touch any shared variables that ever change,so it does not have to be <samp><font color="0f0fff">synchronized</font></samp>.<pre><font color="0f0fff">/* This procedure finds a fork that this philosopher doesn't have and needsto request and returns its index.If no such fork exists because all forks are here it returns -1 and setsthe local state to EATING.If no such fork exists because all absent forks have already been requested,it waits and tries again. */private synchronized int neededFork() { state = HUNGRY; for (;;) { int forksHave = 0; // Number of forks currently owned for (int i = 0; i < forks.length; i++) { if (forks[i].have) forksHave++; else if (!forks[i].haveRequested) { forks[i].haveRequested = true; return i; } } if (forksHave == forks.length) { state = EATING; return -1; } try { wait(); } catch (InterruptedException e) {} }}private void takeForks() { for (;;) { int i = neededFork(); if (i == -1) return; if (phil[forks[i].neighborId].requestFork(forks[i].forkId)) giveFork(forks[i].forkId); // give myself the fork }}</font></pre>At the end of class, Patrick Gaffney pointed out that there's stilla danger of a race condition.What happens if thread t<sub>A</sub> is preempted in A.takeForks() after its callto B.requestFork() has returned <samp><font color="0f0fff">true</font></samp> but before it gets a chance to callA.giveFork()? At this point neither A nor B thinks it has the fork.The call B.requestFork() has updated B's data structure to indicate that Bdoes not have it, but A.giveFork() has not had a chance to update A's variablesto show that A has it.This is not necessarily a problem, but the code has to be carefully writtenso that it can cope with this unusual situation.For example, if t<sub>B</sub> is allowed to run next, it may become hungry, and seeingthat it no longer has the fork, it may call A.requestFork(), which willfind that A doesn't have the fork that is being requested.At this point, neither philosopher thinks he has the fork.<hr><br>Copyright © 1996 by Marvin Solomon. All rights reserved.</body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -