Month: October 2014

DEFINITION

A thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler (typically as part of an operating system). The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is a component of a process. Multiple threads can exist within the same process and share resources such as memory, while different processes do not share these resources. In particular, the threads of a process share the latter’s instructions (its code) and its context (the values that its variables reference at any given moment).

On a single processor, multithreading is generally implemented by time-division multiplexing (as in multitasking): the processor (CPU) switches between different hardware threads. This context switching generally happens frequently enough that the user perceives the threads or tasks as running at the same time. On a multiprocessor or multi-core system, threads can be truly concurrent, with every processor or core executing a separate thread simultaneously. The operating system uses hardware threads to implement multi processing. Hardware threads are different from the software threads mentioned earlier. Software threads are a pure software construct. The CPU has no notion of software threads, and is unaware of their existence.

Many modern operating systems directly support both time-sliced and multiprocessor threading with a process scheduler. The kernel of an operating system allows programmers to manipulate threads via the system call interface. Some implementations are called a kernel thread, whereas a lightweight process (LWP) is a specific type of kernel thread that shares the same state and information.

Programs can have user-space threads when threading with timers, signals, or other methods to interrupt their own execution, performing a sort of ad hoc time-slicing.

DIFFERENCES BETWEEN THREAD AND PROCESS

Threads differ from traditional multitasking operating system processes in that:

• processes are typically independent, while threads exist as subsets of a process

• processes carry considerably more state information than threads, whereas multiple threads within a process share process state as well as memory and other resources

• processes have separate address spaces, whereas threads share their address space

• processes interact only through system-provided inter-process communication mechanisms

• context switching between threads in the same process is typically faster than context switching between processes.

Systems such as Windows NT and OS/2 are said to have “cheap” threads and “expensive” processes; in other operating systems there is not so great a difference except the cost of address space switch which implies a TLB flush.

MULTITHREADING

Multithreading is mainly found in multitasking operating systems. Multithreading is a widespread programming and execution model that allows multiple threads to exist within the context of a single process. These threads share the process’s resources, but are able to execute independently. The threaded programming model provides developers with a useful abstraction of concurrent execution. Multithreading can also be applied to a single process to enable parallel execution on a multiprocessing system.

Multi-threaded applications have the following advantages:

• Responsiveness: Multi-threading has the ability for an application to remain responsive to input. In a single-threaded program, if the main execution thread blocks on a long-running task, the entire application can appear to freeze. By moving such long-running tasks to a worker thread that runs concurrently with the main execution thread, it is possible for the application to remain responsive to user input while executing tasks in the background. On the other hand, in most cases multithreading is not the only way to keep a program responsive, with non-blocking I/O and/or Unix signals being available for gaining similar results.

• Faster Execution: This advantage of a multithreaded program allows it to operate faster on computer systems that have multiple or multi-core CPUs, or across a cluster of machines, because the threads of the program naturally lend themselves to truly concurrent execution.

• Less Resource Intensive: Using threads, an application can serve multiple clients concurrently using less resource than it would need when using multiple process copies of itself. For example, the Apache HTTP server, which uses a pool of listener and server threads for listening to incoming requests and processing these requests.

• Better System Utilization: Multi-threaded applications can also utilize the system better. For example, a file-system using multiple threads can achieve higher throughput and lower latency since data in faster mediums like the cache can be delivered earlier while waiting for a slower medium to retrieve the data.

• Simplified Sharing and Communication: Unlike processes, which require message passing or shared memory to perform inter-process communication, communication between threads is very simple. Threads automatically share the data, code and files and so, communication is vastly simplified.

• Parallelization: Applications looking to utilize multi-core and multi-CPU systems can use multi-threading to split data and tasks into parallel sub-tasks and let the underlying architecture manage how the threads run, either concurrently on a single core or in parallel on multiple cores. GPU computing environments like CUDA and OpenCL use the multi-threading model where dozens to hundreds of threads run in parallel on a large number of cores.

Multi-threading has the following drawbacks:

• Synchronization: Since threads share the same address space, the programmer must be careful to avoid race conditions and other non-intuitive behaviors. In order for data to be correctly manipulated, threads will often need to rendezvous in time in order to process the data in the correct order. Threads may also require mutually exclusive operations (often implemented using semaphores) in order to prevent common data from being simultaneously modified or read while in the process of being modified. Careless use of such primitives can lead to deadlocks.

• Thread crashes Process: An illegal operation performed by a thread crashes the entire process and so, one misbehaving thread can disrupt the processing of all the other threads in the application.

Issues with multithreading

There are few known issues with multithreading

1. when a thread execute a fork system call to create a new proccess, does the child process duplicate all thread from the parent or just the thread ?

2. how does a multithread process handle its signal ? is a signal delivered to a process receive by any thread, a few particular thread or all of thr thread ?

3. how thread are scheduled ? at what level they scheduled, the user level or the kernel level ?

Operating systems schedule threads in one of two ways:

1. Preemptive multitasking is generally considered the superior approach, as it allows the operating system to determine when a context switch should occur. The disadvantage of preemptive multithreading is that the system may make a context switch at an inappropriate time, causing lock convoy, priority inversion or other negative effects, which may be avoided by cooperative multithreading.

2. Cooperative multithreading, on the other hand, relies on the threads themselves to relinquish control once they are at a stopping point. This can create problems if a thread is waiting for a resource to become available.

Threads, called tasks, made an early appearance in OS/360 Multiprogramming with a Variable Number of Tasks (MVT) in 1967.

Until the late 1990s, CPUs in desktop computers did not have much support for multithreading, although threads were still used on such computers because switching between threads was generally still quicker than full-process context switches. Processors in embedded systems, which have higher requirements for real-time behaviors, might support multithreading by decreasing the thread-switch time, perhaps by allocating a dedicated register file for each thread instead of saving/restoring a common register file. In the late 1990s, the idea of executing instructions from multiple threads simultaneously, known as simultaneous multithreading, had reached desktops with Intel’s Pentium 4 processor, under the name hyper-threading. It has been dropped from Intel Core and Core 2 architectures, but later was re-instated in the Core i7 architectures and some Core i3 and Core i5 CPUs.

THREAD MODELS

1:1 (Kernel-level threading)

Threads created by the user are in 1-1 correspondence with schedulable entities in the kernel. This is the simplest possible threading implementation. Win32 used this approach from the start. On Linux, the usual C library implements this approach (via the NPTL or older LinuxThreads). The same approach is used by Solaris, NetBSD and FreeBSD.

N:1 (User-level threading)

An N:1 model implies that all application-level threads map to a single kernel-level scheduled entity; the kernel has no knowledge of the application threads. With this approach, context switching can be done very quickly and, in addition, it can be implemented even on simple kernels which do not support threading. One of the major drawbacks however is that it cannot benefit from the hardware acceleration on multi-threaded processors or multi-processor computers: there is never more than one thread being scheduled at the same time. For example: If one of the threads needs to execute an I/O request, the whole process is blocked and the threading advantage cannot be utilized. The GNU Portable Threads uses User-level threading, as does State Threads.

M:N (Hybrid threading)

M:N maps some M number of application threads onto some N number of kernel entities, or “virtual processors.” This is a compromise between kernel-level (“1:1”) and user-level (“N:1”) threading. In general, “M:N” threading systems are more complex to implement than either kernel or user threads, because changes to both kernel and user-space code are required. In the M:N implementation, the threading library is responsible for scheduling user threads on the available schedulable entities; this makes context switching of threads very fast, as it avoids system calls. However, this increases complexity and the likelihood of priority inversion, as well as suboptimal scheduling without extensive (and expensive) coordination between the userland scheduler and the kernel scheduler.

Hybrid implementation examples

• Scheduler activations used by the NetBSD native POSIX threads library implementation (an M:N model as opposed to a 1:1 kernel or userspace implementation model)

• Marcel from the PM2 project.

• The OS for the Tera/Cray MTA

• Microsoft Windows 7

• The Haskell compiler GHC uses lightweight threads which are scheduled on operating system threads.

Fiber implementation examples

Fibers can be implemented without operating system support, although some operating systems or libraries provide explicit support for them.

• Win32 supplies a fiber API (Windows NT 3.51 SP3 and later)

• Ruby as Green threads

• Netscape Portable Runtime (includes a user-space fibers implementation)

• ribs2

References

1. Pat Villani: Advanced WIN32 Programming: Files, Threads, and Process Synchronization, Harpercollins Publishers

2. Bill Lewis: Threads Primer: A Guide to Multithreaded Programming, Prentice Hall

3. http://www.dmoz.org//Computers/Programming/Threads/

4. http://www.futurechips.org/tips-for-power-coders/parallel-programming.html

5. Sibsankar Haldar, Alex Alagarsamy Aravind: Operating System