CooperatingDeadlock.java
import java.util.*;
import java.util.concurrent.*;
/**
* CooperatingDeadlock
* <p/>
* Lock-ordering deadlock between cooperating objects
*
*/
public class CooperatingDeadlock {
private static final int NUM_THREADS = 10;
private static final int NUM_ACCOUNTS = 5;
private static final int NUM_EVENTS = 100;
private static final int NUM_SCREEN_UPDATS = 100;
private static final int MAP_SIZE = 10;
private static final int[][] DIRS = {{0,1},{0,-1},{1,0},{-1,0}};
public static void main(String[] args) {
final Random rnd = new Random();
final Taxi[] accounts = new Taxi[NUM_ACCOUNTS];
final CooperatingDeadlock cdl = new CooperatingDeadlock();
final Dispatcher dispatcher = cdl.new Dispatcher();
final BlockingDeque<String> gpsEvents = new LinkedBlockingDeque<>();
//final BlockingDeque<String> taxiBookedEvents = new LinkedBlockingDeque<>();
for (int i = 0; i < accounts.length; i++) {
accounts[i] = cdl.new Taxi(dispatcher);
accounts[i].setLocation(cdl.new Point(i, i));
accounts[i].setDestination(cdl.new Point(i, i+1));
dispatcher.addTaxi(accounts[i]);
}
//simulate gps location time sequences
int[] xp = new int[NUM_ACCOUNTS];
int[] yp = new int[NUM_ACCOUNTS];
for (int i = 0; i < NUM_ACCOUNTS; i++) {
xp[i] = accounts[i].getLocation().x;
yp[i] = accounts[i].getLocation().y;
}
for (int i = 0; i < NUM_EVENTS; i++) {
int index = rnd.nextInt(NUM_ACCOUNTS);
Taxi taxi = accounts[index];
Point p = cdl.new Point(xp[index], yp[index]);
int[] v = DIRS[rnd.nextInt(4)]; //random move
if(p.equals(taxi.getDestination())) {
// System.out.println("create reaching event for " + index);
gpsEvents.offer(index + "," + p.x + "," + p.y);
} else {
Point np = cdl.new Point((p.x + v[0]) % MAP_SIZE, p.y+v[1] % MAP_SIZE);
gpsEvents.offer(index + "," + np.x + "," + np.y);
xp[index] = np.x;
yp[index] = np.y;
}
}
System.out.println("Done simulate gps update events");
class TaxiMoveThread extends Thread {
public void run() {
while(!gpsEvents.isEmpty()) { //in uber case, never exit, keep checking
try {
String[] info = gpsEvents.takeFirst().split(",");
int id = Integer.parseInt(info[0]);
int x = Integer.parseInt(info[1]);
int y = Integer.parseInt(info[2]);
Taxi t = accounts[id];
t.setLocation(cdl.new Point(x, y));
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
//event queue workers
for (int i = 0; i < NUM_THREADS; i++)
new TaxiMoveThread().start();
//gui updater
new Thread(()->{
for (int i = 0; i < NUM_SCREEN_UPDATS; i++)
dispatcher.getImage();
}).start();
System.out.println("Done.");
}
private static int uid = 0;
// Warning: deadlock-prone!
class Taxi {
private Point location, destination;
private final Dispatcher dispatcher;
public final int id;
public Taxi(Dispatcher dispatcher) {
this.dispatcher = dispatcher;
this.id = uid;
uid += 1;
}
public synchronized Point getLocation() {
return location;
}
public synchronized void setLocation(Point location) {
this.location = location;
if (location.equals(destination))
dispatcher.notifyAvailable(this);
}
public synchronized Point getDestination() {
return destination;
}
public synchronized void setDestination(Point destination) {
this.destination = destination;
}
}
class Dispatcher {
private final Set<Taxi> taxis;
private final Set<Taxi> availableTaxis;
public Dispatcher() {
taxis = new HashSet<Taxi>();
availableTaxis = new HashSet<Taxi>();
}
public synchronized void addTaxi(Taxi taxi) {
this.taxis.add(taxi);
}
public synchronized void notifyAvailable(Taxi taxi) {
System.out.println(taxi.id + " is available.");
availableTaxis.add(taxi);
}
public synchronized Image getImage() {
Image image = new Image();
for (Taxi t : taxis) {
System.out.print("draw taxi " + t.id + " ");
image.drawMarker(t.getLocation());
}
return image;
}
}
class Image {
public void drawMarker(Point p) {
System.out.println("at location " + p.x + ", " + p.y);
}
}
class Point {
public final int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Point))
return false;
Point p = (Point)o;
return this.x == p.x && this.y == p.y;
}
@Override
public int hashCode() {
int result = 17;
result = 31 * result + x;
result = 31 * result + y;
return result;
}
}
}
This program simulates a taxi dispatch system where multiple threads update taxi locations and a GUI thread periodically renders all taxi positions. Each Taxi object cooperates with a central Dispatcher by notifying it when it reaches its destination, and the Dispatcher in turn queries each Taxi for its location during rendering. Both Taxi and Dispatcher methods are synchronized, and since Taxi.setLocation calls a synchronized Dispatcher method while holding its own lock, and Dispatcher.getImage calls a synchronized Taxi method while holding the dispatcher lock, this creates a circular lock dependency. As a result, if one thread holds a Taxi lock and tries to enter the Dispatcher, while another holds the Dispatcher lock and tries to access the same Taxi, a lock-ordering deadlock can occur.
No comments:
Post a Comment