Livelock – Concurrency: Part I
Livelock
Two threads may result in a livelock, if the response by a thread to another thread’s action is always to undo or revert the consequences of the action. The threads are responding to each other, but are blocked in making any progress. The combined actions of the threads make it impossible for them to complete their tasks, making it impossible for the threads to terminate. This situation is different from a deadlock, where the threads are blocked, waiting for locked shared resources to become available.
An example of a livelock is when two guests (i.e., two threads) are trying to enter through a door, but there is only one door key and only one guest at a time can use it. Each guest is too polite, and insists on giving the key to the other if the other wants to enter. In other words, if one guest hands the key to the other, the other hands it right back. This situation will continue indefinitely, with neither guest thereby entering through the door. We have a livelock because of handing the key back and forth.
Example 22.10 provides another example of a livelock. Two threads are created at (11) and (12). In the first one, a customer makes a payment to a seller, and in the second one, the seller ships an item to the customer.
The Customer class at (1) has a flag (paymentMade) to mark that payment has been made. In the makePaymentTo() method, the customer continuously checks whether the seller has sent the shipment. If the seller has not, the customer waits before checking again. Once the seller has shipped the item, the customer marks at (4) that the payment has now been made.
On the other hand, the Seller class at (6) has a flag (itemShipped) to record that shipment has been sent. In the shipTo() method, the seller continuously checks whether the customer has paid. If the customer has not, the seller waits before checking again. Once the customer has paid, the seller marks at (5) that the shipment has been sent.
Output from running the program shows that the customer is waiting for shipment from the seller, and the seller is waiting for payment from the customer. Neither thread is able to make progress because the seller cannot send the shipment before the customer has paid, and the customer cannot pay before the shipment has been sent. Each is expecting a confirmation from the other, which never arrives. They need to renegotiate their contract, and one of them will have to trust the other.
Example 22.10 Livelock
public class Customer { // (1)
private boolean paymentMade = false; // (2)
public void makePaymentTo(Seller seller) { // (3)
while (!seller.hasShipped()) {
System.out.println(“Customer: waiting for shipment from seller”);
try {
Thread.sleep(1000);
} catch (InterruptedException ex) {
ex.printStackTrace();
}
}
System.out.println(“Customer: payment made”);
this.paymentMade = true; // (4)
}
public boolean hasPaid() {
return this.paymentMade;
}
}
public class Seller { // (5)
private boolean itemShipped = false; // (6)
public void shipTo(Customer customer) { // (7)
while (!customer.hasPaid()) {
System.out.println(“Seller: waiting for payment from customer”);
try {
Thread.sleep(500);
} catch (InterruptedException ex) {
ex.printStackTrace();
}
}
System.out.println(“Seller: item shipped”);
this.itemShipped = true; // (8)
}
public boolean hasShipped() {
return this.itemShipped;
}
}
public class LivelockShipment {
public static void main(String[] args) {
Customer customer = new Customer();
Seller seller = new Seller();
new Thread(() -> customer.makePaymentTo(seller)).start(); // (9)
new Thread(() -> seller.shipTo(customer)).start(); // (10)
}
}
Output from the program:
…
Seller: waiting for payment from customer
Customer: waiting for shipment from seller
Seller: waiting for payment from customer
Seller: waiting for payment from customer
Customer: waiting for shipment from seller
Seller: waiting for payment from customer
…
