Analyzing the Run Time of Threaded vs non-Threaded Programs

Which should run faster, a threaded program or a non-threaded program?  This depends on a couple of things.  One is whether the problem to be solved can be divided efficienly into separate pieces that can be solved by individual threads running concurrently. A second is whether there are multiple cores and/or processors on the computer on which the program is being run.  If there are, the threads can truly run at the same time; if not, the OS must schedule the threads to share the same processor and/or or core for a slice of time.

Threaded Quicksort vs non-Threaded Quicksort

Various students presented their graphs of the running times of the threaded quicksort program compared with the non-threaded version.  A trend quickly emerged, namely that for small data sets the threaded version was slower than the non-threaded version.  Then, for some students, the threaded version always slower, or similar in speed, to the non-threaded version, whereas for other students, the threaded version began to run quicker than the non-threaded version for larger lists.

It was determined that the students in the first case had older computers with single-core processors, whereas students in the second case had more modern computers with mult-core processors. In the latter case, threads were apparently being executed in parallel on the separate cores, thus causing the overall execution time to be quicker.  In the former case, the two threads had to share execution on a single processor.  The overhead of starting, stopping, and restarting the two threads as they shared the single-core processor made the threaded program run slower.

Differences Between Processes and Threads

Recall that a process has an image consisting of its executable code, as well as space for static variables, a stack, and a heap.  It also has an associated process control block that is essentially set to be an image of the processor state whenever a process is rescheduled by the OS. Thus a process can be started again later with the processor state loaded from the PCB for that process, ensuring that the process will start right where it left off.

Threads, on the other hand, exist inside processes.  Thus, a process can have multiple threads.  There is still only one process image with executable code, static variables space.  The threads share the same executable code, and have access to shared values in static memory and on the heap.  Each thread must, however, have its own Task Control Block (TCB) similar to, but with less info than the PCB for the containiing process. Each thread must also have its own stack, as each thread will be able to call methods independently.

Finally, threads are intended for application programmers to use within the context of a single program they are writing, whereas processes, in general, represent completely independent programs that do not share any data.  However, there are situations in which separate processe are designed to communicate with each other.  This is usually a cumbersome process in which messages are passed between the two via OS calls, for example.