CM10135 / Programming II:   Lecture 11


More on Threading 
most especially
When Threading Goes Wrong


I. More Threading Basics

  1. Threads are managed by a scheduler.
  2. The scheduler picks a runnable thread to allow to run for a short slice of time.
  3. A thread is runnable when it is in the ready state.
    1. Remember from this morning.
    2. Basically 
      1. has been started
      2. hasn't died
      3. isn't blocked, asleep or waiting.
  4. There's no guarantee about the order in which threads are taken --- they're just taken from a queue.
  5. The death of threads:
    1. Threads will die when they just finish --- when their run function ends / returns.
    2. They can also be terminated when they get notified that they should interrupt.
      1. This is done by calling the thread's interrupt function, e.g. thread.interrupt();
        1. This won't kill the thread directly, rather it issues a polite request to the thread to die!
        2. See the examples below for how the thread should watch for interruptions.
      2. Note on language: this isn't like an interruption in a conversation, where you might go back to what you are doing, this is (at least intended to be) death.
        1. Language is inherited from unix -- Java was written by Sun.
        2. Interrupt in unix/linux can be generated from the keyboard with ^C,  "control c".
        3. Originally Java allowed you to send suspend (^Z) and resume messages, but these have been deprecated as unnecessarily complicated.
        4. If you want your thread to be able to be suspended, write a method so that it can put itself to sleep!
      3. A thread's run method should check occassionally to see if it has been interrupted:
        1. Interrupts are easy to catch when you're sleeping:
          // a silly run function that's just looking to be interrupted!
          public void run() {
          try {
          Thread.sleep(5000);
          System.out.println("FAIL: No Interrupt! Returned from sleep.");
          } catch (InterruptedException e) {
          if (isInterrupted()) {
          System.out.println("I've been interrupted;"+
          " If I'd been doing anything now I'd clean it up.");
          return(); // return after finish cleaning up!
          }
          }
          }
        2. But if you're busy doing something, you need to explicitly give the system a chance to check messages!
          // a tight loop would ignore interrupts, so we added a short sleep
          public int run() {
          int mySum = 0;
          for (int iii = 10000000; iii > 0; iii--) {
          mySum += iii;
          if (iii mod 10000 == 0) {
          try {
          Thread.sleep(20); // twenty milliseconds!
          } catch (InterruptedException e) {
          if (isInterrupted()) {
          System.out.println("I've been interrupted;"+
          " I only got to " + iii);
          return(-1); // return after finish cleaning up!
          } // if interrupted
          } // catch interrupt
          } // once in 10,000 steps check
          } // for a long time run a tight loop
          return(mySum);
          } // method run

          1. A tight loop is one with no sleeps, waits or calls to other classes' methods.  It's not always easy to guess, but basically it's things the compiler will try to wrap very tightly and get over with quickly.
          2. When a program hangs (stops doing anything), it's generally either stuck in a tight loop that isn't terminating for some reason.  If it were blocked waiting for some I/O, an interrupt should stop it (depends on the OS!)
      4. isInterrupted() checks the status of the interrupt flag without changing it.
        1. if you use interrupted() instead, you will not only find out if you were interrupted, but clear the flag as well.
        2. This means you really could just continue on & wait until you're interrupted again.
        3. So really, interrupt can mean different things in different applications (you'll see this occassionally).
        4. But normally, people expect things to die if they are interrupted.

II. Corruption, Locking & Synchronization

  1. As we talked about in the last lecture, threads can share state. 
    1. e.g. if every instance of a class has a thread, then they share access to the class variables.
  2. This can be a problem!
  3. The classic example:  An ATM (automatic teller machine).
    1. Suppose I and my partner are standing at two ATMs right next to each other.
    2. I want to transfer money from our checking accout to my savings account.
    3. My partner wants to take money out of my checking account.
  4. Suppose that these are the threads that get run:
    //My Thread
    transferAmount = ATM.getTypedNumber();
    float checkingTotal = checking.getBalance();
    float savingsTotal = savings.getBalance();
    // would really have to catch if this makes the checkingTotal < 0!
    checkingTotal -= transferAmount;
    savingsTotal += transferAmount;
    checking.setBalance(transferAmount);
    savings.setBalance(transferAmount);

    // My Partner's Thread
    withdrawalAmount = ATM.getTypedNumber();
    float checkingTotal = checking.getBalance();
    // would really have to catch if this makes the checkingTotal < 0!
    checkingTotal -= withdrawalAmount;
    ATM.squirtMoneyOut(withdrawelAmount);
    checking.setBalance(checkingTotal);
     
  5. What makes ATM examples interesting is the squirtMoneyOut command.
    1. Once the customer has the money, nothing the program can do will get it back!!
  6. Now suppose that both of our threads read the original checking balance from before either of us has changed it.
    1. We get free money! 
    2. The final checking balance will only reflect either the withdrawal or the transfer, not both!
    3. But we have more money in savings and my partner has cash too.
  7. This may sound cool, but actually it's not.
    1. If we'd been depositing money, we could have lost money in the same way.
    2. No nation / economy can do very well if their banks don't work better than this!
  8. The solution is called locking
    1. If a thread is going to do multiple things to some memory / state / a variable (esp. read it then change it!) then it locks that variable.
    2. A lock prevents other threads from accessing the value.
    3. If they try to, they block - basically they wait until they can get access to it.
  9. Locking in Java is done via synchronization.
  10. There are two ways to use synchrony:
    1. synchronized methods, and
    2. synchronized statements.
  11. If you declare a method as synchronized, then only one thread can call it at a time:
    public synchronized float debitAccount (Account a, float amount) {
    if (a.getBalance - amount < 0) {
    throw new BalanceLTZeroException ("some clever message");
    }
    a.setBalance(a.getBalance() - amount);
    return (a.getBalance());
    }
  12. Notice that I haven't only solved the problem by creating a synchronized method.  
  13. I also had to create essentially a new way of accessing the account balance.  All other accessors should either be synchronized, made private or got rid of!
    1. This is because we haven't really locked the attribute, we've locked a method.
    2. If you want to lock just individual elements of data rather than code, you need to use a database (more on this next year!)
  14. If your method is long you may not want to declare the whole thing synchronized.
    1. Don't want to cut down on parallelism.
    2. Want to let other threads have a go.
  15. If you use a synchronize statement, no other thread can accesss its object with synchronized statements or methods:
    float checkingTotal;
    synchronize (checking) {
    checkingTotal = checking.balance();
    checkingTotal -= transferAmount;
    checking.balance(transferAmount);
    }
    System.Out.printline("You have "+ checkingTotal +" in your checking account");
    1. Unfortunately, there's still a caveat here: you can still get at the object if you use unsynchronized code. 
    2. So in other words, this only blocks access from synchonized methods of the object, or of other (or the same!) sychronized program blocks.
    3. Java really makes you synchronize a lot of little things!
  16. Again, you don't want to do this very often or for very long bits of code, because that will reduce the benefit of having threads in the first place.
    1. This is why Java forces you to synchronize in little pieces.
    2. Still, it's an unusually annoying language for making these things work right.

III. Deadlock

  1. Sounds great, right?  But what if my partner and I are running threads like this?
    //My Thread
    synchronize (checking) {
    synchronize(savings) {
    // do stuff to our accounts...
    }
    }

    // My Partner's Thread
    synchronize (savings) {
    synchronize(checking) {
    // do stuff to our accounts...
    }
    }
  2. If we are very unlucky, my thread will get just enough time on its first slice to lock checking, while my partner's will have just enough time to lock savings.
    1. From then on, whenever our threads get a slice, they will still be blocked!
    2. This is called deadlock.
    3. Important fact about luck and computers: computers do things fast enough and often enough that however unlikely something may be, if it's possible at all it will happen eventually.  Probably it will happen often!
  3. There are a lot to avoid deadlock, but none of them are perfect!
    1. You can make an ordering of how locks should be acquired.  Then the above could never happen... if no mistake was ever made!
    2. You can have some process (e.g. the scheduler) notice when a process hasn't done anything for a very long time & interrupt it. 
      1. This lets the other process go.
      2. But it means you have to plan for the possibility that you may not finish your thread (should always think about that anyway.)
    3. You could make all the resources you need attributes of a larger object, then lock / synchronize that.
  4. Although it's important to allow for interrupts, the main way to avoid deadlock is with careful engineering and good design patterns.

IV. Other Threading Notions

  1. The producer / consumer pattern.
    1. One thread is in charge of generating content.
    2. Another thread is in charge of doing something with that content.
    3. Implementing this pattern involves using wait / notify.
    4. This will be on coursework 2.
    5. Here's an  example from the Sun Java Tutorial
      1. In general, the sun java tutorial has excellent notes on threads!!
  2. Thread groups & security:
    1. Unless you say otherwise, thread is grouped with its parent (the thread that called it.)
    2. Threads groups are used to determine security --- if you are running on the internet, you might not want just any thread to be able to manipulate you!
  3. Livelock:
    1. Sort of like deadlock, but the difference is that the threads keep waking up, but can't really do anything and go back to sleep.
    2. Harder to detect by the scheduler than deadlock because it looks like they are doing something, they aren't just blocked.
    3. Has to be dealt with through engineering.

VI. Summary

  1. Threads are a huge topic we are barely touching.  If you are curious here's some more links:
    1. article about threads, thread groups & thread management.
    2. developers discussing stopping a thread in a tight loop.
    3. Most useful resource: the Sun Java Tutorial on Threads.
  2. The most important things in this lecture have been:
    1. How to deal with interrupts, avoid overly tight loops.
    2. The notion of locking and the mechanics of using synchronize
      1. on methods
      2. on objects.
    3. The notion of deadlock - how does it happen?  What does it mean?  What helps avoid it?

page author: Joanna Bryson
4 March 2004
, updated 8 March with some clarifications / comments