Multithreading

What is a thread?

Operating systems can run several programs in parallel. This is called multitasking or multi-processing. If the computer has several processors, then each program might run on a different processor. This is true parallel processing. Otherwise, the programs take turns running on whatever processors are available. This is simulated parallel processing. The operating system facilitates the turn-taking by quickly switching from one program to the next.

Operating systems also allow programs to execute several functions in parallel. This is called multithreading. Again, each function might be running on a separate processor—true parallelism—or they might take turns running on whatever processors are available—simulated parallelism. Here too the operating system facilitates the turn-taking by quickly switching from one function to the next.

Think of a thread as a virtual processor with its own stack, registers, and instruction pointer. If a program has 10 threads, then 10 functions can be executing in "parallel".

Thread states

Generally speaking, a thread can be in one of four states:

·       In its ready state a thread is in the ready queue of some processor, waiting for its turn to run.

·       In its running state a thread is using a processor to execute instructions. When a thread completes its task it enters the stopped state.

·       A thread can be suspended for a number of reasons. It might be waiting for input, waiting to access memory shared with other threads, or waiting for a specified amount of time to elapse.

Applications of threads

Application 1: User interface thread

A program might have a function that runs forever or at least for a long time. The user would like to be able to suspend, resume, or stop the execution of this function. But how? If the program is sucking up all of the processor time, then how will the user tell the program to stop? Simple. The user interface runs in a different thread from the function. While the function is busy burning processor cycles in its thread, the user interface thread is listening for user inputs.

Application 2: Server threads

A server perpetually listens for incoming requests from clients. For example, a web server perpetually listens for HTTP requests from web browsers. Servers are often bombarded with requests coming from all over the world. In the time it would take for a server to service a single request many more requests may have come in and been ignored, causing frustration for users. Instead, the server creates a thread and runs the request handler function in it, then goes back to listening for more requests.

Application 3: Multi-Agent Programs

An agent is an autonomous, goal-driven object:

class Agent {
  State state, goal;
  void run() {
     while(state != goal) {
        state = update(state);
     }
  }
  State update(State state) { ... }
}

Agents are useful for modeling populations of animals, machines, companies, characters in a game, etc. But each agent's run loop may run forever or for a very long time, blocking other agents from running their run loops. To overcome this, each agent's run loop can run in a separate thread.

Active Objects

In object-oriented programming an active object is an object that owns a thread. Any method called by the object is executed in its thread (even if the method belongs to a different object).

In UML notation a class of active objects (called an active class) has double borders on its sides:

The Master-Slave Design Pattern

Many multithreaded applications instantiate the Master-Slave Design Pattern:

Notes

·       The master manages a collection of active slave objects.

·       The master has the ability to start, stop, suspend or resume some or all of the slaves.

·       The master also provides services to the slaves. For this reason each slave has a pointer to the master.

·       One type of service is message passing—providing a mechanism for slaves to pass messages to each other.

·       The master might allow slaves to broadcast messages to all of the slaves.

·       Another type of service is discovery. A slave can ask the master to pair it with another slave.

·       The master might also provide a shared environment consisting of resources to be shared by the slaves.

·       In the example above the manager plays the role of master and the agents play the role of slaves.