18.6 JAVA S wait-notify MECHANISM FOR DEALING WITH DEADLOCK

18.6 JAVA'S wait-notify MECHANISM FOR DEALING WITH DEADLOCK

Let's consider again the situation of different threads modifying a common data object. But now let's assume that the different threads produce different types of modifications that could potentially cause the threads to deadlock.

Consider, for example, the case of a bank account that is shared by multiple customers. Some customers may deposit money into the account while others may withdraw money from the account. If a customer finds that the balance in the account is less than the amount he/she wanted to withdraw, the customer would wait until one or more depositors added to the account. If we represent each customer by a thread, then a thread wanting to withdraw money should wait until the threads depositing funds into the account had produced a sufficient balance. In multithreaded programming with Java, this effect can be achieved by using the wait-notify mechanism. When a thread wishing to make a certain modification to a data object finds out that the state of the data object does not meet a condition that must be satisfied before the modification can be carried out, the thread executes the wait method. And when threads capable of establishing that condition do their job, they execute the notifiyAll method, which enables the waiting thread to try to seek a lock on the object again so that it can proceed with data modification.^[12]

The reader will recall that every object with at least one synchronized method has a monitor that maintains a list of all the threads wanting to execute any of the synchronized methods in that object. The threads are let into the object one at a time and the thread currently executing a synchronized method becomes the owner of the monitor for the object. When a thread sees wait while it is executing a synchronized method, the thread releases its ownership of the monitor and gets placed in the wait list for the object. On the other hand, when a thread executes notifyAll, that notification is sent to all the threads in the wait list that were sent there by the wait method. The important thing to remember is that if a thread landed in a wait list because it executed wait, the only way it can come off the list is if it receives a notification sent by notifyAll in some other thread. Instead of notifyAll, it is also possible to use notify, which sends the notification to a randomly selected thread in the wait list.

The following example illustrates the use of the wait-notify mechanism. We have a bank account shared by 10 customers, five of whom only deposit money into the account while the other five only like to withdraw money from the account. The shared account is an instance of the class Account defined in line (A) with two synchronized methods, deposit and withdraw in lines (D) and (G), respectively.

Notice how in line (H) the withdraw method first makes sure that the amount to be withdrawn is not larger than the current balance in the account. If this condition is not satisfied, the wait method is invoked in line (I). The method wait throws InterruptedException, which must be caught. Execution of this method causes the thread to release its lock on the Account object and to be put back in the list of waiting threads maintained by the monitor for the Account object. We used the no-arg version of wait in line (I). This is one of the following three possible ways to invoke wait:

     void wait() throws InterruptedException;     void wait(long milliseconds) throws InterruptedException;     void wait(long milliseconds, int nanoseconds)                                 throws InterruptedException; 

While the first version causes the thread executing the wait method to wait indefinitely, the other two versions make for a time-bounded wait in terms of the specified number of milliseconds and nanoseconds.

The only notifyAll call in our example that will cause a waiting thread to come off the monitor's list is in line (F) of the deposit method of line (D). So each time a deposit is made by any of the threads capable of doing so, a notification is broadcast to all the threads in the monitor list that got put there by the wait command.

If a thread is again given a lock on the object upon receiving a notification from notifyAll, the flow of control in the thread moves to just beyond the wait statement whose execution put the thread in the wait state in the first place. If the wait statement is placed inside a while loop, as we do in line (H), this will automatically cause the condition of the loop to be tested again. If this condition is not satisfied again, the thread loses once again its lock on the object and gets put back in the monitor's wait list. It is for this reason that the while loop in line (H) cannot be replaced by a statement such as

     if (balance < draw) {                                    // WRONG         try {         wait();         } catch(InterruptedException e) {} 

Getting back to our example, money will be deposited in the common account by customers of type Depositor as defined in line (K). Note that each deposit, whose amount is generated by the Java random number generator in line (P), consists of a number between 0 and 10. Also, each depositor keeps on adding to the amount indefinitely. As dictated by line (Q), each depositor thread will print out the account balance once every 1000 deposits.

Monies are withdrawn by customers of type Withdrawer defined in line (T). As with the depositors, each thread of type Withdrawer will withdraw monies from the common account indefinitely and will print out the account balance after very 1000 withdrawals. The source code for this example follows:

 
 //MultiCustomerAccount.java /////////////////////////// class Account /////////////////////////// class Account {                                                          //(A)     int balance;                                                         //(B)     Account() {balance = 0;}                                             //(C)     synchronized void deposit(int dep){                                  //(D)         balance += dep;                                                  //(E)         notifyAll();                                                     //(F)     }     synchronized void withdraw(int draw) {                               //(G)         while (balance < draw) {                                         //(H)             try {                 wait();                                                  //(I)             } catch(InterruptedException e) {}         }         balance -= draw;                                                 //(J)     } } ////////////////////////// class Depositor ////////////////////////// class Depositor extends Thread {                                          //(K)     private Account acct;                                                 //(L)     Depositor(Account act){ acct = act; }                                 //(M)     public void run() {                                                   //(N)         int i = 0;         while (true) {                                                    //(O)             int x = (int) (10 * Math.random() );                          //(P)             acct.deposit(x);                                              //(Q)             if (i++ % 1000 == 0)                                          //(R)                 System.out.printIn(                     "balance after deposits: "                     + acct.balance);                                      //(S)                        try { sleep(5); } catch(InterruptedException e) {}         }     } } ////////////////////////// class Withdrawer ///////////////////////// class Withdrawer extends Thread {                                         //(T)     private Account acct;     Withdrawer(Account act) { acct = act; }     public void run() {         int i = 0;         while (true) {             int x = (int) (10 * Math.random() );             acct.withdraw(x);             if (i++ % 1000 == 0)                 System.out.printIn("balance after withdrawals: "                                     + acct.balance);             try { sleep(5); } catch(InterruptedException e) {}         }     } } //////////////////// class MultiCustomerAccount ///////////////////// class MultiCustomerAccount {                                            //(U)          public static void main(String[] args) {         Account account = new Account();         Depositor[] depositors = new Depositor[ 5 ];         Withdrawer[] withdrawers = new Withdrawer[ 5 ];         for (int i=0; i < 5; i++) {             depositors[ i ] = new Depositor(account);             withdrawers[ i ] = new Withdrawer(account);             depositors[ i ].start();             withdrawers[ i ].start();         }     } } 
 

A typical output of this program is

     balance after deposits: 5     balance after withdrawals: 4     balance after deposits: 10     balance after withdrawals: 14     balance after deposits: 14     balance after withdrawals: 28     balance after deposits: 31     balance after withdrawals: 10     balance after deposits: 20     balance after withdrawals: 29     balance after deposits: 205     balance after deposits: 214     balance after deposits: 234     .....     .....     ..... 

Since the threads run indefinitely, the program can only be terminated by killing the process.

The wait-notify mechanism is an important tool to resolving potential deadlock between threads. However, just because a program uses this mechanism does not mean that deadlock will not occur—one still has to design with care the logic of a program so that irresolvable deadlock situations do not occur. An irresolvable deadlock occurs when each one of the waiting threads waits indefinitely for the others to proceed.

Evidently, the threads in our MultiCustomerAccount will not deadlock because no conditions need be satisfied for making deposits. So the Depositor threads will continue to make deposits no matter what. Therefore, if a Withdrawer thread blocks for lack of sufficient funds, it will eventually be able to get back into the running.

But now consider the following variation on the MultiCustomerAccount class. Instead of having a single account that could be accessed by multiple customers, let's now consider a single customer with access to multiple accounts. Let's also assume that all that the customer is allowed to do is to shift monies between the accounts. So if the customer is depositing funds in some account, it is because the customer has withdrawn these funds from some other account. If we associate a separate thread with each account, the run method of the thread could then transfer money from its account to one of the other randomly selected accounts. Suppose we have only two accounts A and B. If account A, with a balance of $1000, wants to transfer $2000 to account B, and account B, with a balance of $2000, wants to transfer $3000 to account A, the threads will deadlock. This can also happen with more than two accounts. Say, account A with a balance of $1000 wants to transfer $2000 to account B, account B with a balance of $2000 wants to transfer $3000 to account C, and account C with a balance of $500 wants to transfer $1000 to account A. The three threads corresponding to the three accounts would evidently deadlock.

^[12]The methods wait, notify, and notifyAll are defined for the class Object.