Multithreading & parallel processing

Multithreading is the feature of the programming language that enables the developer to do the parallel processing in the software. You can listen to music while coding! The operating system creates process for each of the task to perform in parallel. The process is scheduled to run on the processor. The process can have one or multiple threads. The execution logic can be divided into multiple threads to perform the concurrent execution. e.g. The Dal thread can fetch the data from the database and UI thread populates them on the UI thereby reducing the wait time of the user to see the results. The programming languages provides lots of API's to operate on the threads and to manage them. In this blog post, lets discuss about the threads and paradigm of parallel programming.

In computer science terminology a thread of execution is the smallest unit of processing that can be scheduled by an operating system. A thread is a lightweight process. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process. (ref Wikipedia)

In terms of programming language, there can be two types of thread - main thread and worker thread. The program is run in the main thread. The worker thread is created from the main thread to share the workload of the main thread. The worker thread is joined to the main thread to consume the result in the main thread. The figure below depicts the scenario of the multithreaded application

The figure shows the main thread spawning the worker threads to execute the code in parallel. The worker thread executes the logic independently of each other and finally joins the main thread to proceed the further execution on the main thread. The main thread is blocked until both the worker threads joins the main thread. The worker threads are allocated separate CPU core to execute the logic at the full core speed. This is the main reason why multithreaded application performs better than single threaded application. The sample C# code for multithreaded application is as shown below:

The main thread creates two threads viz. thread and thread1. These threads have a worker method associated with them. The threads starts execution when Start() method is called on each one. The sequence in which the thread starts and completes the execution is non-deterministic and depends solely on the processor and thread management component of CLR.

.NET framework methods to operate on thread:

1. Start - Start the thread execution
2. Suspend - Suspend the thread execution
3. Resume - Resumes the execution of the suspended thread
4. Abort - Terminates the thread
   
   

Race condition:

The non-deterministic execution behavior of the thread results in the condition which is often referred to as race conditions. In race conditions the final output may vary depending upon the sequence of the execution of the thread. Hence every run of the program may result in different output. The race conditions can be avoided by using synchronization techniques between the producer and consumer threads

Inter-thread and inter-process communication:

As discussed in above sections, the thread is an independent unit of execution. The worker method is expected to have all the data required for it to execute independently and flawlessly. However there are scenarios where one worker thread may depend on the data that is generated by another worker thread. Hence there needs to be a communication channel between worker threads. This mechanism is known as inter-thread or inter-process communication. Wikipedia explains it as - "In computing, Inter-process communication (IPC) is a set of methods for the exchange of data among multiple threads in one or more processes". There are various types of IPC methods: message passing, synchronization, pipes, shared memory, etc.

1. Message passing: The mechanism to enable the thread to exchange the messages between each other. The messages should be generated based on the predefined schema and so that they it can be interpreted by the consumer threads. The typical example of message passing mechanism is MSMQ. The MSMQ stores the messages in the xml format. The format should be well understood by the consumer threads so as to enable consumer thread to read the messages that are generated by producer thread
   
   

2. Synchronization: The mechanism by which the thread synchronizes themselves with the other threads so that all the threads uses the fresh and accurate copy of the data to avoid discrepancies in the final output is known as synchronization
   
   
3. Pipes: This methodology sequences the thread execution and pass the result of one thread as an input to other.
   
   
4. Shared memory: This methodology reserves some amount of the physical memory for all the threads to spool the data which can be shared by other threads. The memory area needs to be protected so as to ensure that one thread enters the shared memory at any point of time. These are often referred to as critical sections.
   
   

Let's discuss synchronization and shared memory concepts in details.

Thread Synchronization: The thread synchronization is the mechanism with which the thread suspends or resumes its processing based on the state of the other thread. This helps the thread to operate on the correct copy of the data generated by the other threads. This is achieved by ensuring that only one thread enters the critical section and operates on the data while other threads waits (blocks) for the previous thread to exit the critical section. The thread signals the other threads when it exits the critical section so that the other threads which are waiting for the previous thread get chance to enter the critical section and operates on the data. There are several methodology to perform thread synchronization viz. mutex, semaphore, monitor

Types of thread synchronization:

The thread synchronization helps to maintain thread safety. The various methods to achieve thread synchronization is as follows:

1. Mutex: The flag used by the threads to stop the other threads from entering the critical section. The thread sets the flag after it has entered the critical section and resets it when it exists the critical section. The other threads wait (busy waiting) on the flag and checks whether the flag has been reseted. They get chance to enter critical section when they see the flag has been reseted by the previous thread. In terms of programming language the mutex is essentially a boolean variable that hold the value of true/false.
   
   
2. Semaphore: It is the special implementation of mutex except that it maintains the available count of the resources. This enables the operating system to avoid the race conditions because it predefines the number of resources that can be allocated. These are known as counting semaphores.
   
   

3. Monitor: In concurrent programming, a monitor is an object or module intended to be used safely by more than one thread. The defining characteristic of a monitor is that its methods are executed with mutual exclusion. That is, at each point in time, at most one thread may be executing any of its methods. This mutual exclusion greatly simplifies reasoning about the implementation of monitors compared to reasoning about parallel code that updates a data structure (ref: Wikipedia)
   
   

.NET framework implementation of the thread synchronization and thread safety

1. Lock: This keyword is used to ensure that only one thread enters the critical section. The lock is internally compiled as the monitor. The lock operates on the object type data structure. The sample code may look like as follows:

2. Events: The events are the messages that are communicated between two threads. The event has two states: Wait and Signal. The wait state causes the thread to wait till the other thread does not signal it. The signal state enables the thread to enter the critical section which means the previous thread has exited the critical section. There are two kinds of synchronization events in .NET:
1. AutoResetEvent: The event is signaled automatically if the thread is waiting on auto reset event and the auto reset event returns to un-signaled state after the thread is allowed to enter the critical section. The thread needs to call Set() to explicitly signals the auto reset event which then allows other threads to enter the critical section

2. ManualResetEvent: The thread resets the event and enters the critical section. After completing the execution the thread calls Set() to allow other waiting threads to acquire the lock to enter critical section.
   
   
   

3. Monitor: The monitor is implemented using Enter() and Exit() methods on the Monitor class in .NET. The critical section is placed between Enter() and Exit() methods so that monitor ensure only thread enters the critical section at any given point of time.

Thread pooling:

The thread pooling is the mechanism with which the thread is allocated from the list of available threads to execute the user work items. The ThreadPool class in .NET enables the framework to spawn and schedule the thread for individual work items of the user. Essentially the thread pool is implemented as a queue (FIFO). The scheduling of the user work items is handled by operating system and there is no guarantee that the thread is scheduled immediately after adding the user work item to the queue. The thread returns back to the thread pool once it completes the current work item for the user so that it can be scheduled once again after sometime.

Writing the thread-safe code:

The thread-safe code is defined as the code that does not allow other threads to modify/update the data used by current thread. The code is thread-safe only if it safely manipulates the data in the shared memory without hampering the execution of the other threads. There are numerous ways to achieve thread safety in the multithreaded application. Let's discuss the obvious approach to write the thread-safe code i.e. reentrant code. For other methodologies to write the thread-safe code please refer to section: .NET framework implementation of the thread synchronization

Reentrant code: The reentrant code is the code which gets the data from the main/parent thread for itself to run independently. The thread maintains its own copy of the data instead of using the global data. This helps the thread to avoid using the data that can be modified by other threads because all the thread has local copy of the data. The reentrant code executes with multiple threads and ensuring the result is consistent across the thread execution. This is achieved by storing the data locally on the thread stack instead of global variables

Deadlock:

The system is said to be in deadlock if each thread is waiting for the other to release the non-preemptive resource and there is a circular wait amongst these threads. It is very critical to detect the deadlock and prevent it from happening because the system can go into endless wait and never comes up again. The detailed discussion of the deadlock is outside the scope of this blog post.

Multithreading on single-core and multi-core machines:

The multithreaded application does not yield good results when run on the single-core machine the code is run on the single core. There is also an overhead involved in managing the thread which is done by CLR e.g. context switching, loading the state from previous run, etc. The thread execution on the single core machine happens on the concept of the time-slice wherein all the thread executes on the processor for a given time span before the next thread is scheduled. The multithreaded application performs better on the multicore machines. The multicore machines has an ability to schedule the threads on the different cores hence achieves the parallel processing in the true sense

Usages of the multithreading concept:

Most of the softwares especially the games and the enterprise products available today makes use of heavy multitasking. These softwares needs a very high quality of the hardware configuration including the multicore processors.

Future of the multithreading:

Nowadays the multithreading has become a basic necessity of any software. There has been a great evolution in the processors as the manufacturers are putting more cores on the processor die. This facilitates the software writers to use multithreading extensively in their products to increase the responsiveness of the product.