8/6/02
Amir Kamil

Topic: Threading, Synchronization

Announcement:


Threads:
- Allow multiple pieces of code within a program to execute at the same 
  time.
- Say we want to create a Hacker class that hacks into a server. Many 
  encryption schemes use a very large product of two primes as a
  key. The product is publicized and can be used to encrypt data, but
  you can only decrypt data if you know what the two primes are. So
  let's have our Hacker try factoring the key in order to break the
  encryption.

  class Hacker {
    int factorKey(int key) {
      for (int i = 2; i < key; i++) {
        if (num % i == 0) {
          return i;
        }
      }
      return 0;
    }
  }

  What's the problem with this code? Well, factoring is hard,
  exponentially so (O(2^n) in the number of bits in the key; keys of
  hundreds or thousands of bits are typical). So the Hacker will sit
  there forever trying to break the key, while we want it to try other
  hacking techniques as well. We can use threading in order to allow
  it to do both at the same time.

- To have a class represent a thread, it must either extend Thread or
  implement Runnable. It must then define a run() method, which is the
  code that is executed when the new thread is created (just like the
  main() method gets executed when a program is started; however, 
  run() takes no arguments).
- To start a thread, if the class extends Thread, you instantiate the 
  class and call the start() method. This creates a new thread and
  executes the run() method of the class.

  So let's fix our Hacker:

  class Factor extends Thread {
    int number, factor;
    boolean running = false;
    Factor (int number) {
      this.number = number;
    }
    public void run() {
      running = true;
      factor = findFactor(number);
      running = false;
    }
    int findFactor(int num) {
      for (int i = 2; i < num; i++) {
        if (num % i == 0) {
          return i;
        }
      }
      return 0;
    }
  }
 
  class Hacker {
    Factor f;
    void hack(Server s) {
      f = new Factor(s.getKey());
      f.start(); // creates a new thread, calls f.run()
      while (f.running) {
        trySomethingElse(s);
      }
      // now we know the key, so we can crash the server
      crashServer(s, f.factor);
    }
    void trySomethingElse(Server s) {
      sendVirus(s);
      ...
    }
    ...
  }

- To start a Runnable object, we must first create a generic Thread with 
  the object as the argument (e.g. Thread t = new Thread(new
  RunnableObject())). Then we call the start method of the Thread.


Synchronization:
- Now that we can have multiple threads running at once, what if we have 
  code that we only want one to access at a time? For example, we
  might have methods that read and write a particular file, and we
  don't want multiple thread writing the same file at the same time or
  simultaneously reading and writing it, since the results would be
  undefined.
- Using the Java keyword "synchronized", we can prohibit more than one 
  thread from executing a block of code at the same time. Any block
  can be synchronized, including entire methods, in which case the
  method can be declared synchronized.

  Ex:
  public synchronized void writeFile(String toWrite) {...}

  public String readFile() {
    synchronized {...}
  }

  Now only one thread at a time can be in either the writeFile()
  method or the synchronized block in the readFile() method. We say
  that the thread has acquired a "lock" on the block. However, one
  thread can be in one method while another thread is in the other,
  which isn't what we want. How do we fix this?

  boolean locked;
  public synchronized void getLock() {
    while (locked) {}
    locked = true;
  }
  public void releaseLock() {
    locked = false;
  }

  We add the above code, and now when a thread wants to read/write a
  file, it calls the getLock() method first. Then it waits until no
  other thread has the lock, in which case it claims it. A thread that
  is done reading/writing calls releaseLock() in order to release the
  lock.Now the above code is inefficient, since the continuous loop
  uses cpu time, as do other threads that are locked out of the
  getLock() method. Java provides a way of for threads to sleep until
  they are awakened by the thread currently with the lock, after which
  they can try acquiring it. Calling the wait() method in any object
  will cause the current thread to sleep, until it is awakened by a
  notify() or notifyAll() call on that object.

  boolean locked;
  public synchronized void getLock() {
    if (locked) {
      wait();
    }
    locked = true;
  }
  public void releaseLock() {
    locked = false;
    notifyAll();
  }

  Now when a thread calls getLock() and finds that another thread has
  the lock on the file, it can sleep until it is notified by that
  thread to wake up and try to get the lock. When a thread sleeps, it
  releases all synchronization claims on the object in which it called
  wait(). So in this case for example, other threads can execute the
  getLock() method while threads are sleeping. notify() tells a single
  arbitrary thread to wake up, while notifyAll() tells all threads
  that are sleeping on that object to wake up.

  Why do we have to declare getLock() to be synchronized? Well, what
  if the file was unlocked and two different threads called getLock()
  at the same time. Both would think they got the lock, and both would
  read/write the file at the same time, which would be erroneous.

  Synchronization issues are important in operating systems. While it
  may be unlikely that two threads execute the same code at the exact
  same time, we don't want our computers to crash when it does
  happen. It's errors like these that are the most difficult to fix,
  since they are difficult to reproduce. If you are running a Windows
  machine and want to see an example of synchronization, try opening a
  file in Microsoft Word and then in WordPad at the same time. You'll
  see that the OS won't let you.