Mutithreaded Programing

                                       & its application in Graphics

 

_____________________________________________________________________

Abstract: This article is forcus on structures, advantages and limitation of concurrency implemented by multithreaded progamming, and take multi-threaded  Graphics in Java  as one of their application examples. 

_________________________________________________

Part I < Concurrency Background> Advantages & Limitation

*Advantages

Concurrency opens up design possibilities that are impractical in sequential programs. Threads liberate you from the limitations of code that invokes a method and then blocks, doing nothing while waiting for a reply. Using threads, you can additionally trigger new independent activities that run concurrently, with or without waiting out their completion. Reasons to exploit threads include:

Reactive programming

Some programs are required to do more than one thing at a time, performing each activity as a reactive response to some input. For example, a World Wide Web browser may be simultaneously performing an http GET request to get a Web page, playing an audio clip, displaying the number of bytes received of some image, and engaging in an advisory dialog with the user. While it is possible to program such systems in a single-threaded manner by manually interleaving the different activities, this is complicated, fragile, and error-prone. Reactive programs are easier to design and implement using threads. In fact, the vast majority of design principles and patterns described in this book are geared for use in reactive programs.

Availability

Concurrency allows you to maintain high availability of services. For example, among the more common concurrent design patterns (seen in most internet services and even in many applets) is to have one object serve as a gateway interface to a service, handling each request by constructing a new thread to asynchronously perform the associated actions. The gateway is able to accept another request quickly. This helps avoid bottlenecks by draining the communications network of pending messages. It can also improve the fairness of access: new, quickly-serviceable requests do not have to wait for old time-consuming requests to complete.

Controllability

Activities within threads can be suspended, resumed, and stopped by other objects. This provides simplicity and flexibility not found in sequential programming, where the desire to stop an activity (for a while, or forever) and do something else is often difficult to implement.

Active objects

Software objects often model real objects. Most real objects display independent, autonomous behavior. At least in some cases, the easiest way to program this is to fire up a new thread whenever you create such an object.

Asynchronous messages

When one object sends a message to another, the first object does not always care when the resulting action is performed. Threads allow the first object to continue with its own activity without having to wait for unrelated actions to complete.

Parallelism

On machines with multiple CPUs, concurrent programming can be used to exploit available computing power to improve performance. Even without multiple CPUs, interleaving activities in threads avoids delays associated with time-consuming processing that need not complete before other activities are started.

Required concurrency

Even if you do not explicitly intend to write concurrent programs, many predefined Java support classes and run-time features operate in a concurrent manner. These include the java.applet and java.awt classes for playing audio clips and displaying images, and the mechanisms that cause every Java Applet to run in its own thread.
 

* Limitations

If concurrency is great, then you should use it everywhere. But you shouldn't. The benefits of concurrency must be weighed against its costs in resource consumption, efficiency, and program complexity:

Safety

When multiple threads are not completely independent, each can entail objects sending messages to other objects that may also be involved in other threads. All of these objects must utilize synchronization mechanisms or structural exclusion techniques to ensure that they maintain consistent state. Attempts to use multiple threads involving objects that were designed to work only in sequential settings can lead to random-looking, hard-to-debug inconsistencies. On the other hand, synchronization mechanics can add complexity to programs.

Liveness

Activities within concurrent programs may fail to be live. That is, one or more activities can simply stop, for any of a number of reasons; for example because other activities are consuming all CPU cycles, or because two different activities are deadlocked, both endlessly waiting for each other to continue.

Nondeterminism

Multithreaded activities can be arbitrarily interleaved. No two executions of the same program need be identical. Activities requiring a lot of computation may finish before those requiring practically no computation. This can make multithreaded programs harder to predict, understand, and debug.

Threads versus method calls

Threads are not very useful for request/reply-style programming. When one object must logically wait for a reply from another in order to continue, the same thread should be used to implement the entire request-execute-reply sequence. Constructing a new thread achieves no benefit when there is no room for concurrency. Conversely, an activity running as a thread cannot use the standard sequential invocation style in which a client sends arguments, waits for them to be processed, and then receives results in a reply. These effects can be obtained in threads, but require special coding.

Objects versus activities

In essentially all object-oriented systems, there are many fewer asynchronously executing concurrent activities than there are objects. Even from an active object approach, it makes sense to create a new thread only when an invocation actually generates a new asynchronous activity, not automatically whenever constructing a new object that may or may not ever engage in asynchronous activities.

Thread construction overhead

Constructing a thread and setting it in motion is typically slower and more memory-intensive than constructing a normal object or invoking a method on it. If an activity is only a matter of a few primitive statements, then it is much faster just to invoke it via a method call than to use threads.

Context-switching overhead

When there are more active threads than there are CPUs, the Java run-time system occasionally switches from running one activity to running another, which also entails scheduling -- figuring out which thread to run next.

Synchronization overhead

Java methods employing synchronization can be slower than those that do not provide proper concurrency protection. And methods that must postpone and resume actions depending on the current states of objects can be yet more expensive. Between thread and synchronization overhead, concurrent programs can run more slowly than sequential ones unless you have multiple CPUs, and sometimes even if you do.

Threads versus processes

Activities that are intrinsically self-contained and sufficiently heavy may be simpler to encapsulate into standalone programs. Standalone programs can be accessed via system-level (concurrent) execution facilities or remote invocation mechanisms rather than as multithreaded components of a single process. (Although the borderlines can be slippery, a process is usually defined as an active entity that maintains its own set of resources, while a thread uses the resources of its enclosing process.)

Part II  Threads Architecture and Benefit implementation

________________________________________________________________________________________________
What is a thread? Just as multitasking operating systems can do more than one thing concurrently by running more than a single process, a process can do the same by running more than a single thread. Each thread is a different stream of control that can execute its instructions independently, allowing a multithreaded process to perform numerous tasks concurrently. One thread can run the GUI, while a second thread does some I/O, while a third one performs calculations.

A thread is an abstract concept that comprises everything a computer does in executing a traditional program. It is the program state that gets scheduled on a CPU, it is the "thing" that does the work. If a process comprises data, code, kernel state, and a set of CPU registers, then a thread is embodied in the contents of those registers -- the program counter, the general registers, the stack pointer, etc., and the stack. A thread, viewed at an instant of time, is the state of the computation.

A thread and a process are conceptually related. But a process is a kernel-level entity and includes such things as a virtual memory map, file descriptors, user ID, etc., and each process has its own collection of these. The only way for your program to access data in the process structure, to query or change its state, is via a system call.
 
 

All parts of the process structure are in kernel space (Figure 1). A user program cannot touch any of that data directly. By contrast, all of the user code (functions, procedures, etc.) along with the data is in user space, and can be accessed directly.

Figure 1
Figure 1 -- Relationship between a process and threads

A thread is a user-level entity. The thread structure is in user space and can be accessed directly with the thread library calls, which are just normal user-level functions. Note that the registers (stack pointer, program counter, etc.) are all part of a thread, and each thread has its own stack, but the code it is executing is not part of the thread. The actual code (functions, routines, signal handlers, etc.) is global and can be executed on any thread. In Figure 1, we show three threads (T1, T2, T3), along with their stacks, stack pointers (SP), and programs counters (PC). T1 and T3 are executing the same function. This is a normal situation, just as two different people can read the same road sign at the same time.

All threads in a process share the state of that process (see Figure 2). They reside in the exact same memory space, see the same functions, see the same data. When one thread alters a process variable (say, the working directory), all the others will see the change when they next access it. If one thread opens a file to read it, all the other threads can also read from it.



Figure 2 -- The process structure and the thread structures



When you write a multithreaded program, 99% of your programming is identical to what it was before -- you spend you efforts in getting the program to do its real work. The other 1% is spent in creating threads, arranging for different threads to coordinate their activities, dealing with thread-specific data, and signal masks. Perhaps 0.1% of your code consists of calls to thread functions.

So here's the essential point about threads: They are user-level entities. Virtually everything you do to a thread happens at user level with no system calls involved. Because no system calls are involved, it's fast. There are no kernel structures affected by the existence of threads in a program, so no kernel resources are consumed -- threads are cheap. The kernel doesn't even know that threads exist. (This is important. We're going to repeat it about ten times.)

The value of using threads
There is really only one reason for writing MT programs -- you get better programs, more quickly. If you're an ISV, you sell more software. If you're developing software for your own in-house use, you simply have better programs to use. The reason that you can write better programs is because MT gives your programs and your programmers a number of significant advantages over nonthreaded programs and programming paradigms.

A point to keep in mind here is that you are not replacing simple, nonthreaded programs with fancy, complex, threaded ones. You are using threads only when you need them to replace complex or slow nonthreaded programs. Threads are really just one more way you have to make your programming tasks easier.

The main benefits of writing multithreaded programs are:

The following sections elaborate further on these benefits.

Parallelism
Computers with more than one processor provide multiple simultaneous points of execution (Figure 3). Multiple threads are an efficient way for application developers to exploit the parallelism of the hardware. Different threads can run on different processors simultaneously with no special input from the user and no effort on the part of the programmer.

A good example of this is a process that does matrix multiplication. A thread can be created for each available processor, allowing the program to use the entire machine. The threads can then compute distinct elements of the result matrix by doing the appropriate vector multiplication.

Figure 3
Figure 3 -- Different threads running on different processors

Throughput
When a traditional, single-threaded program requests a service from the operating system, it must wait for that service to complete, often leaving the CPU idle. Even on a uniprocessor, multithreading allows a process to overlap computation with one or more blocking system calls (Figure 4). Threads provide this overlap even though each request is coded in the usual synchronous style. The thread making the request must wait, but another thread in the process can continue. Thus, a process can have numerous blocking requests outstanding, giving you the beneficial effects of doing asynchronous I/O, while still writing code in the simpler synchronous fashion.

Figure 4
Figure 4 -- Two threads making overlapping system calls

Responsiveness
Blocking one part of a process need not block the whole process. Single-threaded applications that do something lengthy when a button is pressed typically display a "please wait" cursor and freeze while the operation is in progress. If such applications were multithreaded, long operations could be done by independent threads, allowing the application to remain active and making the application more responsive to the user.

Communications
An application that uses multiple processes to accomplish its tasks can be replaced by an application that uses multiple threads to accomplish those same tasks. Where the old program communicated among its processes through traditional IPC (interprocess communications) facilities (e.g., pipes or sockets), the threaded application can use the inherently shared memory of the process. The threads in the MT process can maintain separate IPC connections while sharing data in the same address space. A classic example is a server program, which can maintain one thread for each client connection (Figure 5). This provides excellent performance, simpler programming, and effortless scalability.

Figure 5
Figure 5 -- Different client machines being handled by different threads in a server program

System resources
Programs that use two or more processes to access common data through shared memory are effectively applying more than one thread of control. However, each such process must maintain a complete process structure, including a full virtual memory space and kernel state. The cost of creating and maintaining this large amount of state makes each process much more expensive, in both time and space, than a thread. In addition, the inherent separation between processes may require a major effort by the programmer to communicate among the different processes or to synchronize their actions. By using threads for this communication instead of processes, the program will be easier to debug and can run much faster.

An application can create hundreds or even thousands of threads, one for each synchronous task, with only minor impact on system resources. Threads use a fraction of the system resources used by processes.

Distributed objects
With the first releases of standardized distributed objects and object request brokers (coming in 1995), your ability to make use of these will become increasingly important. Distributed objects are inherently multithreaded. Each time you request an object to perform some action, it executes that action in a separate thread (Figure 6). Object servers are an absolutely fundamental element in distributed object paradigm, and those servers (as discussed above) are inherently multithreaded.

Although you can make a great deal of use of distributed objects without doing any MT programming, knowing what they are doing and being able to create objects that are threaded will increase the usefulness of the objects you do write.

Figure 6
Figure 6 -- Distributed objects running on distinct threads

Same binary for uniprocessors and multiprocessors
In most older parallel processing schemes, it was necessary to tailor a program for the individual hardware configuration. With threads, this customization isn't required because the MT paradigm works well irrespective of the number of CPUs. A program can be compiled once, and it will run acceptably on a uniprocessor, whereas on a multiprocessor it will just run faster.

Program structure
Many programs are more efficiently structured with threads because they are inherently concurrent. A traditional program that tries to do many different tasks is crowded with lots of complicated code to coordinate these tasks. A threaded program can do the same tasks with much less, far simpler code. Multithreaded programs can be more adaptive to variations in user demands than single- threaded programs (see Figure 7).

Figure 7
Figure 7 -- Simplified flow of control in complex applications


 

Part III  Java Threads  and their Application in Graphics

_________________________________________________________________

Java threads allow a programmer to build multitasking into their programs with great ease. Many languages support multitasking through add-on libraries, yet Java includes threading as part of the base language. Beginning to use threads (i.e., methods and objects from the Thread class) can be a fairly complex process because they require the programmer to think about a lot more things in their program at once. However, knowing how to utilize threads is a prerequisite for other important areas of Java programming such as animation and network programming.

Important Thread methods

Like Applet, Thread has a number of important methods which are used and/or re-implemented in almost every program that intends to use threading. Some of these methods even have the same name as their equivalents in Applet, so be sure you know which methods you're calling when you come to write your first threaded Applets.
run
This method should contain the code that executes whilst the Thread is running. This method is almost always overridden by Thread subclasses and often contains a loop which performs some part of the object's duties during each iteration (e.g., display one frame of an animation, etc)
start
Invoke this method on the Thread object to start the object running
stop
Stops this Thread object executing
sleep
This method suspends the current Thread execution for a specified number of milliseconds. Calls to this method are often found in run methods to allow other threads or processes to execute for a period of time

Thread Applet Demonstration

Here is one applet demo for showing responsive multi-threaded programming.


Here is a screen shot of the BasicThreadTest applet

Thread state

The diagram below shows the various states a Thread object can take, and which of the methods we've seen cause a change from one state to another (other methods also cause state change, but this diagram has been limited to the methods we've seen so far).
There is a lot more to be said about threads and their operation. This brief discussion is merely to provide sufficient background knowledge of threads prior to looking at animation and threaded servers.

Animation

Like most aspects of multimedia in Java, animation can be accomplished quite simply, but various degrees of optimization are needed to really use animation efficiently in conjunction with other parts of Java programs. Using animation properly involves the knowledge and use of threads to concurrently perform other tasks whilst the animation is running. The Applet running below is a fairly simple animation that could use some customization to improve its performance and user-friendliness. 

sourceCode 1 *2