/Operating-System-Project

A researched based project that includes a comparative study between Multithreading, Multiprocessing, and Normal Execution.

Primary LanguageC

Operating-System-Project

Sorting Algorithm Performance Comparison with Processes and Threads

Objectives

The objective of this experiment is to test whether multithreading is faster than multiprocessing and a normal sorting algorithm.

Introduction

In our semester project, we aimed to compare the performance of different sorting algorithms with multiprocessing and multithreading. We implemented the algorithms using the pthread.h library for threads and time.h to calculate the time taken to sort an array. We ran each test with six different arrays and recorded the results.

Hypothesis

We predict that programs run with multithreading will produce the smallest elapsed time (ET). We predict that the programs running without any multithreading or multiprocessing will produce the largest ET.

Algorithms

We used 5 algorithms to test our hypothesis:

  • Mergesort
  • Quicksort
  • Selection sort
  • Rank sort
  • Radix sort

Methodology

We first created an array of 8 elements and then ran the program using that array to minimize the variability in the generation of random numbers. We added the numbers to our spreadsheet and created a graph to compare each of the programs. We also did our best to write a program that produces the same number of threads as the number of fork calls to decrease variability. Our focus is on testing only the speed and not any other factors.

Findings

Mergesort

The normal (single-threaded) program consistently outperformed both the multithreaded and multiprocessing programs. Elapsed time for each sorting algorithm using normal, threading, and processing methods:

Algorithm Normal Threading Processing
Mergesort 0.000003 4.00E-06 0.000683
... ... ... ...
merge sort

Quick sort

The findings indicate that the Quick sort algorithm has the smallest elapsed time when run in the normal program, followed by multithreading and multiprocessing.

Algorithm Normal Threading Processing
Quicksort 0.000002 0.000174 0.000531
... ... ... ...
Quick sort

Radix Sort

Based on the data, Radix sort with threading had the largest elapsed time, while Radix sort with multiprocessing had the smallest elapsed time.

Algorithm Normal Threading Processing
Radix sort 0.000033 0.008366 0.000331
... ... ... ...
Radix sort

Selection sort

The normal program consistently outperformed the multithreaded and multiprocessed programs for Selection Sort.

Algorithm Normal Threading Processing
Selection Sort 0.000002 0.00155 0.000949
... ... ... ...
Selection sort

Rank sort

The performance of the rank sort algorithm with multiprocessing and multithreading is worse than the normal program.

Algorithm Normal Threading Processing
Rank Sort 0.000002 0.001739 0.000246
... ... ... ...
Rank Sort

Conclusion

Contrary to our hypothesis, all the tests showed that the normal program runs faster than the multiprocess or multithreaded programs. It's important to note that the performance of multiprocessing and multithreading can vary depending on various factors such as the size of the data, the number of cores/threads available, the implementation of the algorithm, and the overhead of managing threads/processes. In our case, it's possible that the overhead of managing threads/processes outweighed the benefits of parallelization, leading to longer elapsed times.

In conclusion, our experiment showed that the normal program outperformed the programs with multiprocessing and multithreading. Future work could explore different implementations and configurations of the algorithms and experiment with larger datasets to further investigate the performance of multiprocessing and multithreading. It's important to interpret the findings in the context of the experimental setup and consider possible limitations and sources of error.

Reference List