Processes Versus Threads

Multithreading

Processes versus Threads

A running program is called a process. We think of a process as a sequence of events, but the operating system thinks of a process as ordinary data object, like a bank account or an employee.

A process has a context and a state. The context consists of stack, heap, static, and code memory segments, as well as the current contents of the computer's register (e.g. status register, stack pointer, program counter, etc.)

A process can be in the running, ready, or blocked state:

The ready state means the process is waiting in the ready queue for the CPU. The running state means the process controls the CPU and is currently running. The blocked state means the process is not running because it is waiting for an event such as a timer expiration, acquisition of a semaphore, or user input.

When a process enters the blocked state, the operating system takes the CPU away from the process and gives it to the next process in the ready queue. When the event occurs, the blocked process enters the ready state and joins the ready queue. A process may have a priority that determines where it is placed in the ready queue. A preemptive operating system can take the CPU away from a running process when its time slice expires, e.g. 1/100 seconds, and force it back into the ready queue. Otherwise we say the operating system is non preemptive. Win32 is preemptive.

Taking the CPU away from a running process and giving it to the next ready process is called a process switch. This involves changing the state of the old running process and saving its context, then changing the state of the new process and restoring its context.

A process switch can be very time consuming because the saved and restored contexts can be large. This tends to discourage the use of collaborating processes. Also, communication between collaborating processes must use some sort of inter process communication mechanism (IPC) such as pipes or sockets. Shared memory segments are possible, but difficult to set up.

Some operating systems allow a process to divide itself into separate threads of control. Like a process, a thread, also called a lightweight process, has its own state and context, but the context of a thread only consists of a stack segment and register contents. The other segments come from the process that created the thread.

It's easy for threads to collaborate. A thread switch is fast because only the stack segment and registers must be saved and restored, and all threads created by a particular process share the heap and static segments of the parent process, through which they can communicate. Of course sharing memory and other resources introduces synchronization problems that can make multithreaded programs difficult to debug.

Threads are the temporal counterpart of objects. While objects structure memory, threads structure time. Each thread defines a sequence of order-dependent instructions. The operating system decides the execution order of instructions in different threads. This allows the operating system to exploit possible opportunities for concurrency in the hardware.

The Master-Slave Design Pattern

Most multithreaded applications instantiate the Master-Slave Architecture. The master thread creates, manages, and discards slave threads. Slave threads perform some background task, report the result to the master, then disappear. The master may also coordinate communication between the slaves.

For example, the Travelling Salesman Problem can be solved in O(n) time by having the master assign routes to slaves. Each slave computes the length of its route in O(n) steps and reports the result back to the master. The master merely computes the minimum distance reported. (Of course O(n!) slaves will be needed.)

Servers also use the master-slave architecture. The master listens for connection requests from clients. When a request is received, a slave is created to service the request while the master continues to listen for more requests.

Java Threads

Threads as Objects

Java makes multithreading of the underlying host operating system available to programmers. We extend the Java Thread class like any other class, except we usually redefine the inherited run() method:

class Robot extends Thread
{
public void run()
{
while(true)
{
// run around doing stuff forever
}
}
// etc.
}

Threads can be launched using the start() method, which calls the run() method:

public class Factory
{
public static void main(String[] args)
{
for(int i = 0; i < 100; i++)
{
Robot r2d2 = new Robot(...);
r2d2.start();
}
// etc.
}
}

Sometimes it makes more sense to extend another class. Since Java doesn't support multiple inheritance (like C++), we must implement the Runnable interface. This requires defining a run() method as before, as well as creating a thread to run:

class Robot extends Applet implements Runnable
{
private Thread runner;
public void run() {...}
public void start()
{ // the usual place to start threads
if (runner == null)
{
runner = new Thread(this);
runner.start(); // calls run() above
}
}
// etc.
}

Scheduling

Thread States

At any moment a thread can be in any one of the eight states shown in Figure 23. Most of the transitions are thread methods discussed below:

Preemptive vs. Nonpreemptive Scheduling

Java multithreading is implemented using the multithreading system provided by the host platform. On single-processor computers there are two types of multithreading systems: preemptive and nonpreemptive. In a non-preemptive system all runnable threads wait in a ready queue for the currently running thread to release the CPU. This either happens because it terminates, requests I/O, or calls suspend(), wait(), sleep(t), yield(), or stop().

In a preemptive system the CPU is allocated to a thread for a fixed time slice (e.g. one second). If a thread doesn't release the CPU before its time slice expires, it will be interrupted, sent back to the ready queue, and the CPU will be allocated to the "next" thread in the ready queue.

The Java ready queue is a priority queue. This means threads are inserted according to their priority. The maximum priority of a Java thread is 10, the minimum priority is 1, and the normal priority is 5. If a thread has priority n, it will be inserted into the queue behind all threads with priority ≥ n, but ahead of all threads with priority < n. The Thread.getPriority() and Thread.setPriority() methods can be used to learn and modify a thread's priority. When a thread calls yield() or is preempted, it rejoins the ready queue, but if all other threads in the ready queue have lower priority, then the same thread immediately regains control of the CPU.

Cooperative Multitasking using yield() or sleep()

Most multithreading systems are preemptive, but some are not (e.g. Solaris' "green threads"). This means multithreaded Java programs can exhibit platform-dependent behavior. One way to mitigate this problem is to write cooperative threads. A thread is cooperative if it occasionally releases the CPU specifically so other threads can run. There are two ways to do this: by calling the yield() method, or the sleep(t) method where t is an integer. We already mentioned that yield() doesn't guarantee a different thread will be allocated the CPU. The sleep(t) call forces the thread to suspend itself for t milliseconds.

Example: Bouncing Balls

In the bouncing ball applet each ball is animated by its own slave thread. New balls are created by mouse clicks. Keyboard inputs stop, suspend, and resume the balls:

If you have a JDK 1.1 enabled browser, the applet is located at:

Imports

import java.awt.*;
import java.awt.event.*;
import java.util.*;// for Vector
import java.applet.*;

Class Declaration and Member Variables

public class Bounce extends Applet
{
// client area metrics
protected int xUpperLeft, yUpperLeft, xLowerRight, yLowerRight;
private Vector balls;
private int ballDiam;
private Random numberGen;
private boolean paused;

Stopping, Suspending, and Resuming the Balls

private void killAll()
{
showStatus("Killing all balls");
for(int i = 0; i < balls.size(); i++)
{
Ball b = (Ball)balls.elementAt(i);
b.stop();
}
balls.removeAllElements();
repaint();
}
private void resumeAll()
{
if (paused)
{
showStatus("Resuming all balls");
paused = false;
for(int i = 0; i < balls.size(); i++)
{
Ball b = (Ball)balls.elementAt(i);
if (!b.isAlive())
showStatus("This ball is dead!");
b.resume();
}
}
}
private void suspendAll()
{
if (!paused)
{
showStatus("Suspending all balls");
paused = true;
for(int i = 0; i < balls.size(); i++)
{
Ball b = (Ball)balls.elementAt(i);
b.suspend();
}
}
}

start(), stop(), and destroy()

public void start() { updateMetrics(); resumeAll(); }
public void stop() { suspendAll(); }
public void destroy() { killAll(); }

Initializing the Applet

public void init()
{
addMouseListener(new MouseEventHandler());
addKeyListener(new KeyEventHandler());
Object parent = getParent();
balls = new Vector();
ballDiam = 10;
numberGen = new Random();
paused = false;
}

Initializing Client Area Metrics

protected void updateMetrics()
{
Dimension d = getSize();
Insets in = getInsets();
int clientWidth = d.width - in.right - in.left;
int clientHeight = d.height - in.bottom - in.top;
xUpperLeft = in.right;
yUpperLeft = in.top;
xLowerRight = xUpperLeft + clientWidth;
yLowerRight = yUpperLeft + clientHeight;
}

Keyboard Listener

class KeyEventHandler extends KeyAdapter
{
public void keyTyped(KeyEvent e)
{
// int key = e.getKeyCode(); // always 0!
char key = e.getKeyChar();
if (key == 'k') killAll();
else if (key == 'r') resumeAll();
else if (key == 's') suspendAll();
else showStatus("key pressed = " + key);
}
}

Mouse Listener

class MouseEventHandler extends MouseAdapter
{
public void mouseClicked(MouseEvent e)
{
showStatus("New Ball");
Point p = e.getPoint();
Ball b = new Ball(p.x, p.y);
balls.addElement(b);
b.start();
}
public void mouseReleased(MouseEvent e)
{
showStatus("");
}
}

paint()

public void paint(Graphics g)
{
for(int i = 0; i < balls.size(); i++)
{
Ball b = (Ball)balls.elementAt(i);
g.setColor(b.color);
g.fillOval(b.xc, b.yc, ballDiam, ballDiam);
}
}

Balls

// slave thread
class Ball extends Thread
{
public int xc, yc;
private int dx, dy, oldxc, oldyc, red, green, blue;
public Color color;
public Ball(int x, int y)
{
xc = x;
yc = y;
dx = numGen.nextInt() % 7 - 3;
dy = numGen.nextInt() % 7 - 3;
int max = Thread.MAX_PRIORITY + Thread.MIN_PRIORITY + 1;
int pri = (numGen.nextInt() % max) - Thread.MIN_PRIORITY;
red = numberGen.nextInt() % 256;
blue = numberGen.nextInt() % 256;
green = numberGen.nextInt() % 256;
color = new Color(red, green, blue);
}
private void move()
{
oldxc = xc;
oldyc = yc;
xc += dx;
yc += dy;
if (xc <= xUpperLeft || xLowerRight <= xc)
dx = -dx;
if (yc <= yUpperLeft || yLowerRight <= yc)
dy = -dy;
}
public void run()
{
while(true)
{
move();
repaint(oldxc, oldyc, 2 * ballDiam, 2 * ballDiam);
try { Thread.sleep(5); }
catch(InterruptedException e) {}
}
}
}
} // Bounce

HTML

<HTML>
<TITLE> Bouncing Balls </TITLE>
<BODY>
Mouse click creates a ball. Press s to suspend, r to resume, and k to kill.<BR>
<APPLET CODE="Bounce.class" WIDTH=300 HEIGHT=500>
Sorry, your browser can't show applets.
</APPLET>
</BODY>
</HTML>