Ogg-Vorbis format, 52Mbytes

WAV format, 290Mbytes

Distributed systems and concurrent systems

• Distributed and concurrent systems both deal with "multiple things happening together"
• Distributed systems deal with multiple execution threads on more than one computer
• Concurrent systems deal with multiple execution threads on a single computer
• They share some common aspects
  • need to communicate
  • sharing of state
• They differ in the amount of shared information and in communication bandwidth
• These produce different programming concerns
• A common way of dealing with some of the problems caused by distributed systems on a local basis is to use concurrency techniques

Concurrency

• A concurrent program can be described as one that does more than one thing at a time
• Concurrency first appeared in hardware with e.g. dedicated I/O processors which offload processing from the main CPU
• Concurrency was mainly used in operating systems, with prime examples being Unix processes

Unix processes

• The O/S schedules and runs a number of processes
• Some sort of time-sharing or process switching mechanism is used to allocate time to each process
• One process can create another, with a parent-child relationship
• There is limited sharing of information between parent-child processes:
  • Open files
  • Shared memory
  • Named pipes and streams
  • Sockets
• Processes each have their own stack and private data areas

Scheduling policies

• A process scheduler may be pre-emptive or co-operative
• Pre-emptive: the scheduler is in charge of how long a process runs for. If a process exceeds its timeslice, it is stopped by the scheduler
• Co-operative: each process is in charge of how long it runs for. When a process feels like co-operating, it will surrender execution
• Pre-emptive is good, co-operative is usually bad
• Most O/S now support pre-emptive scheduling, but not all (Windows 3.1 is a major co-operative scheduler). NT has both models, to support "traditional" 16-bit Windows applications as well as newer 32-bit ones

Threads

• Threads are "lightweight processes". They share more information than heavyweight processes
• Typically threads share
  • the same system stack
  • the same heap memory
• Threads usually have their own procedure call/local variable stacks

Shared memory problems

• If two processes/threads share memory, then both can read and write to it
• An assignment such as i = i + 1 or i++ involves both a read and a write
• The scheduler does not treat such an operation as "atomic" and may interrupt it half way through to perform a context switch to another process.
• So if process/thread A reads a value, control switches to B which writes a value, then back to A which also writes a value, then B's change is lost
• Many techniques exist to avoid these problems, such as locks, semaphores, monitors, etc

Threads

• Java includes threads as part of the language model
• No extra libraries are required
• An application consists of at least one "user" thread which runs the main() method
• The main thread may create and run other threads as well
• A JVM may run several "kernel" and "user" threads as well
• An application terminates when all user threads terminate

Thread scheduling

• Many aspects of threads are looked after by the JVM
• Thread scheduling may use scheduling models supplied by the O/S
• Java threads may behave differently depending on whether the O/S supports pre-emptive or co-operative threads

Thread creation

• Subclass from Thread:

        class MyThread extends Thread {
            public void run() {
                // code for my thread
            }
        }

  Start this thread by

        MyThread thr = new MyThread();
        thr.start();

• Implement Runnable:

        class MyRun implements Runnable {
            public void run() {
                // code for my thread
            }
        }

  Start this thread by

        MyRun run = new MyRunnable();
        new Thread(run).start();

Example

Sequential server

while (msg = getMessage())
    handle msg

Concurrent server

while (msg = getMessage())
    create new thread to handle msg

Thread life-cycle

Thread alive states

Example broken shared memory

• The following program (based on one from Core Java) shares a number of "bank accounts".
• Amounts are transferred from one to another on a random basis: the sum should remain constant
• Every now and then the sum is printed
• Each thread "yields" halfway through a transfer. A pre-emptive O/S could interrupt the method when it felt like, including at this point. Yielding at this point allows most opportunity for errors
• On a test run under Linux it was producing wrong results after 30 transactions. Without the yield() it was still running "correctly" after 100,000 transactions (but would probably break sometime)

Mutual exclusion

• Mutual exclusion can be accomplished in Java using the synchronized keyword
• This can be applied to methods

        synchronized void writeLogEntry() {...}

  or to blocks of code

        ...
        synchronized(anObject) {
            ...
        }
        ...

• A synchronized method/block can be viewed as a "critical section" that excludes access the object by any other synchronized methods during its execution

Use of synchronized

• The use of this word is pretty straightforward: whenever a resource needs to be accessed in an atomic manner, then make the access synchronized

Fixing bank account

• The unsynch bank account allowed "simultaneous" access to the elements of the bank account array
• Removing the yield() does not fix the problem
• Synchronizing the transfer() and test() methods does

  
        public synchronized void test() {...}
        public synchronized void transfer(int from, int to, int amount) {...}

• Strictly, synchronising test() is redundant since it is only called from transfer(), but it does no harm
• This corrects the problem, but does not allow the maximum concurrency: in order to transfer between two accounts, all transfers but one are blocked, including those that do not involve these accounts (see "Deadlock" later)

More synchronization

• Synchronization occurs on an object i.e. multiple threads executing code associated with a single object
• Synchronizing a method is equivalent to synchronizing all of the method code on the object this
• In the SynchBankTest, the synchronizing object is the Bank object b created by main()
• The method transfer() could have been written

  public void transfer(int from, int to, int amount)
   {    synchronized(this) {
            if (accounts[from] < amount) return;
            accounts[from] -= amount;
            accounts[to] += amount;
            ntransacts++;
            if (ntransacts % NTEST == 0) test();
        }
   }
  

Synchronization on a shared object

• The above example uses a single Bank object to synchronize on
• If threads use different objects, they can only synchronize on a shared object
• The following (artificial) example creates two separate Adder objects and then uses a third shared object synchObject to avoid contention

Fine control of threads

There are a number of ways in which threads can control execution

• Thread.sleep(milliseconds)
• Thread.yield() allows the scheduler to select another runnable thread
• wait() block until woken up by a call to notify
• notify() and notifyAll() wakeup threads waiting to regain control of the monitor's lock

Wait/notify

• wait()/notifyAll() occur in pairs, associated with a synchronizing object
• One thread in a synchronized block waits.
• This gives up control of the synchronizing object to another thread
• When a thread wants to wakeup any waiting thread, it notifies the thread
• The method notifyAll() is preferred to notify()
• Note that wait() and notifyAll() can usually only be called within a synchronized block or method

  synchronized(obj) {
        ...
        obj.wait();
        ...
   }

Reader/Writer example

Deadlock

Example:

Two processes wish to communicate with each other, in a 2-way manner. Two pipes can be used for this:

Example:

When the "give way to the right" rule was in force, this was a common situation:

Deadlock detection

A resource allocation graph is a graph showing processes, resources and the connections between them. Processes are modelled by circles, resources by squares. If a process controls a resource then there is an arrow from resource to process. If a process requests a resource an arrow is shown the other way.

For example, P1 is using R1 and has requested R2, while P2 is using R2.

Deadlock can now occur if P2 requests R1 - setting up a cycle.

The total set of conditions for deadlock to occur are:

1. Mutual exclusion. Each resource is either currently assigned to one process or is available.
2. Hold and wait. Processes holding resources can request new ones.
3. No preemption. Resources granted cannot be taken away, but must be released by the process holding them.
4. Circular wait. There must be a cycle in the resource allocation graph.

Deadlock and the bank account

• Making the transfer() method synchronized locks all accounts for a transfer between two of them
• This reduces concurrency
• Why not just lock the two accounts?
• This introduces a potential deadlock

  
        public void transfer(int from, int to, int amount) {
            if (accounts[from] < amount) return;
            synchronized(accounts[from]) {
                synchronized(accounts[to]) {
                    accounts[from] -= amount;
                    accounts[to] += amount;
                    ntransacts++;
                    if (ntransacts % NTEST == 0) test();
                }
            }
        }

• A simultaneous transfer from e.g. one to two, two to three and three to one will introduce a cycle

Deadlock prevention

To prevent deadlocks from occurring, one of the four conditions must be disallowed.

1. Mutual exclusion. Make some resources unsharable, such as printers, tape drives.
2. Hold and wait. Process must request all needed resources at one time. This results in wasted resources.

   Process must release all current resources before requesting more. This is not feasible.

3. No Preemption. Make it possible for the O/S to make a process give up a resource. This may result in lost data.
4. Circular wait. Make it impossible for cycles to occur in the graph by restricting the types of graphs that can be made. For example, give each resource a priority number. If a resource is held with a priority, then a new resource can only be requested of lower priority.

Bank account avoiding circular wait

• Prioritise the accounts by using their numeric order
• Always grab the higher order before the lower one

  
        public void transfer(int from, int to, int amount) {
            if (accounts[from] < amount) return;
            int high, low;
            if (from > to) {
                high = from;
                low = to;
            } else {
                high = to;
                low = from;
            }
            synchronized(accounts[high]) {
                synchronized(accounts[low]) {
                    accounts[from] -= amount;
                    accounts[to] += amount;
                    ntransacts++;
                    if (ntransacts % NTEST == 0) test();
                }
            }
        }

Deadlock avoidance

Deadlock prevention is to ensure that deadlocks never occur. Deadlock avoidance is attempting to ensure that resources are never allocated in a way that might cause deadlock.

There are situations that may give rise to cycles, but in practise will not lead to deadlock. For example, P1 and P2 both want R1 and R2, but in this manner:

• P1 needs R1 first, then R2, but with a slight overlap.
• P2 needs R2 first, then R1 but with no overlap.

P1 can be given R1 and P2 can be given R2. P1 will require R2 before it can give up R1, but that is ok - P2 will give up R2 before it needs R1.

The Banker's algorithm can be used to ensure this, but it is too complicated for general use.

Listing a directory (and subdirectories)

Listing all the files in a directory is a recursive operation:

• write the name of the current directory
• find all the files in the current directory
• for each file, if it is an ordinary file then write its name, else call the list files function with the new directory

Recursive single-thread solution

Multi-threaded solution

Each directory could be handled by a separate thread. When a list of files is found for each directory, it's name is printed if it is an ordinary file, but if it is a directory then a new thread is created to handle it.

Summing the size of files in directories

Listing files can be made more complex by finding their size and summing them.

Recursive sum

Multi-threaded sum

This one is a lot more complicated!

• The sum variable must be shared between all threads, so it needs to be static
• Access to sum must be synchronised
• The synchronisation must be on a common shared object, say the first SumFilesThread object created
• How do you know when the summation is complete?
  Wait until all threads have completed
• How do you know when all threads have completed?
  • Use Thread.activeCount(). But this is an estimate only, so is not reliable
  • Keep a count of all threads that are alive
• How do you keep count of all threads?
  • Have a shared static variable threadCount
  • Make all changes to this synchronized
  • When a new thread is created, increment the count (you can't wait until run() is called, because there may be a gap between creation and running)
  • When run() finishes, decrement the count

Conclusion

• Java makes it relatively easy to do thread level programming
• It supplies a set of simple methods in the Thread class
• Thread programming is not always simple: It is easy to make obscure and hard to trace errors using threads