Processes, threads, and Java

CSA-Prep, Fall 2004

Some terms

• A process is an execution of a program.

  For example, if you start up a Scheme interpreter within emacs, there are two programs executing. These are separate processes---two programs being executed at the same time (via "timesharing:" the processes take turns using the CPU).

  Also, if two users are executing emacs at the same time, then there are two processes---this time two executions of the same program. Note that these two executions occur independently of each other in general: they represent two execution paths through the same program code.

• Modern computing systems allow a single process to include multiple execution paths, called threads. The threads share the same program, and also share computing resources such as memory with each other; furthermore, it's more efficient to switch (take turns) between two threads in the same process than between two different processes.

• Threads within a process are sometimes called lightweight processes; these are started up within a program. separate executions of programs are then called heavyweight processes; these are typically started up using shell actions or application icons.

• Blocking occurs when a process or thread must wait for a computing resource.

  For example, suppose that a process or thread A needs to access a file on disk, but that another process or thread B is currently using that disk. Then A's execution is temporarily stopped, until B is finished with the disk the file data has been retrieved and made available. We say that A is blocked waiting for the disk.

• The term mutual exclusion ("mutex") describes a situation where a process possesses sole access to a computing resource. For example, in the blocking example above involving the disk access, we assume A must wait because B has mutually exclusive access to the disk. Without that mutual exclusion, A would be able to access the disk at the same time as B, and no blocking would be necessary.

• Deadlock occurs when a set of processes (or threads) is blocked, each waiting for an event that can only be provided by other processes in that set.

  For example, consider a client-server application with a database.
  
  In this diagram, an arrow indicates mutually exclusive access to some computing resource:

  • the client has set a lock on a particular record within the database, providing a mutually exclusive right to that record;
  • the client has requested a web page from the server, and the server has mutually exclusive access to providing that page; and
  • the server is trying to access the database record that the client happens to have locked, and the database management system (DBMS) (which has mutually exclusive access to all database records) will not satisfy the server's request until the client relinqishes its right to that record.
  Thus, the set of two processes consisting of the client and the server are each blocked, awaiting an event that can only be caused by the other; i.e., the client and server are deadlocked. (Note that the DBMS is not itself in the deadlock set; it can continue to serve other processes.)

• A critical section of code is a portion of a program where a thread (or process) accesses shared resources, e.g., shared memory variables. Programmers must construct critical sections with care so that situations such as deadlock do not occur among the threads (or processes).

• A race condition occurs when the correct behavior of a program or system depends on timing.

  Race conditions can be extremely difficult to detect in a program, since the problem occurs only intermittently.

• The topic of programming multi-process/multi-threaded applications correctly is called interprocess communication (IPC). The processes (threads) involved must somehow (often indirectly) communicate with each other in order to prevent errors, race conditions, deadlocks, etc.

Race condition example

Consider the following producer/consumer problem.

• One process produces things that another process uses. Examples: print jobs, shell pipeline, values from a sensor.

  Produced items are stored in an array of length MAX that is shared by the two processes. The number of items in that array is stored in a shared variable count.

• Algorithm 1. Producer algorithm:

  repeat forever
     produce an item
     if (count == MAX)
        sleep()  /* to be awakened by consumer when space is available */
     insert an item
     count = count + 1
     if (count == 1)
        wakeup(consumer)
  

  Consumer algorithm:

  repeat forever
     if (count == 0)
        sleep()  /* to be awakened by producer when an item is available */
     remove an item
     count = count - 1
     if (count == MAX-1)
        wakeup(producer)
     consume that item
  

  Issues: Race conditions

  Additional races if multiple producers and/or multiple consumers

Details of a race condition in producer/consumer example

producer                    consumer
                               +>
                               |  repeat forever
                               |     ...
                               |     // ASSUME count=0 NOW
                               |     if (count == 0)
			      <+
   produce an item	       |
   if (count == MAX)	       |
      sleep()  		       |
   insert an item	       |
   count = count + 1	       |
   if (count == 1)	       |
      wakeup(consumer)	       |
   produce an item	       |
   ...             	       |
                               +>
                               |        sleep()  // BLOCK!
			      <+
   ...             	       |
   // ASSUME count=MAX NOW     |
   produce an item	       |
   if (count == MAX)	       |
      sleep() // BLOCK!	       |

Threads in Java

• Java provides a class Thread which represents a separate execution path within a Java program. In order to program with threads, one typically constructs a subclass of Thread with a customized run() method; that method contains the code to be used in that thread's execution path. Other methods of Thread allow the execution of that thread's run() method to be started up, paused, terminated, etc.

• For example, in graphics with animation, we might create a subclass of Thread that serves a timer function: such a thread could periodically update the image on the screen. We could use separate threads to animate different images on the screen so they can move around independently, potentially at different update rates.

• _____

IPC in Java

• synchronized_____

• wait()_____

• notify()_____

• Example: Bounce.java

rab@stolaf.edu, October 27, 2004