CM10135 / Programming II:   Lecture 10


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 last week.
    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.
  6. What are threads for?
    1. This really is basic.  In fact, it's basically covered in the previous lecture.
    2. Every program has at least one thread. 
      1. The main program thread works just like we've been describing.
      2. It can be blocked!
    3. Threads let the rest of your program get useful stuff done while parts of your program are doing slow things, like waiting for users or disk I/O.
    4. Threads also let you attend to other tasks neatly without confusing your code.
      1. E.g. as from last lecture -- updating the clock, autosaving.
      2. If you had to put something in every method of your code to check if it was time to do one of those tasks, that would be very messy.
      3. The scheduler effectively does this for you.

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(checkingTotal);
    savings.setBalance(savingsTotal);

    // 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. Only one thread can call synchornized code on an object at a time.  One way to do this is by declaring synchronized methods:
    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. The synchroinze statement is another way to create synchonized code.
    float checkingTotal;
    synchronize (checking) {
        checkingTotal = checking.balance();
        checkingTotal -= transferAmount;  
        checking.balance(transferAmount);
    }
    System.Out.printline("You have "+ checkingTotal +" in your checking account");
    1. Notice synchronize in this context takes an argument (an object)
      1. Every object has an implicit lock, which is what locks when you call a synchronized method.
      2. If you use that object in the synchronize statement, it will also lock any other access to that object with synchronized code using either way of synchronizing.
      3. You can also create objects just to use their locks if you want to have finer-grained locking.
    2. Notice: you can still get at the object if you use unsynchronized code!
    3. So in other words, this only blocks access from synchonized methods of the object, or of other (or the same!) sychronized program blocks.
    4. Java locks code, not data.
      1. You have to synchronize a lot of things!
      2. Most people wind up using databases to address this (see next year.)
  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.
This is how far we got in class in 2006... but we got through it all in 2007 (from here took 10 minutes.)

III. Liveness & Deadlock

  1. Locking 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.
  5. Note that even if you aren't entirely deadlocked, you can be blockes a lot of the time if everything is synchronized.
    1. Not being blocked too much is called liveness.
    2. If you don't have much liveness then there's not much point in using threads!

IV. Other Threading Notions

  1. These won't be on the exam, but if you seriously care about programming in a concurrent environment (e.g. the Internet) you should probably understand these.
  2. The producer / consumer pattern.
    1. Helps you deal with two things happening at different rates.
    2. Something may produce information / signals & another thing needs to process / `consume' that data, but at a different rate.
    3. Implementing this pattern involves using wait / notify.
    4. Sun recommends doing this using Guarded Blocks.
  3. 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. See article listed below in summary.
  4. 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.
    4. Have a look on the discussions about Liveness on the Sunt Java Tutorial listed below.
  5. More sophisticated locking in Java
    1. Allows you to work with an explicit lock object.
    2. Is both more powerful & more complicated.
    3. The problem with complexity in locks is deadlock, livelock.
    4. The interface Lock documentation is interesting (& may help you understand implicit locks better.)

V. 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, avoiding 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
21 February 2007