Goal

In this assignment, you will implement a parallel version of the Bubble Sort algorithm to sort a bunch of numbers using first multiple processes and then multiple threads. You will learn about working with multiple processes, concurrency, race conditions, and simple inter-process and inter-thread synchronization.

Requirements for parts A and B below.

• Use only the C language and glibc, so that you can understand low-level behavior or your code. No other languages, libraries or packages are necessary/allowed.
• Do not use any pre-existing bubble-sort implementations/libraries other than the ones provided in this assignment.
• Implement only a parallel version of bubble sort, NOT any other sorting algorithm, even though there may be other (possibly better) parallel sorting algorithms, such as parallel merge sort.
• Use the skeleton program named odd_even_sequential_bubble_sort given by me to work on this assignment.

Part A: Parallel Bubble Sort using Processes

Now, implement a parallel version of the even-odd bubble sort using multiple processes.

• Besides N, the parallel bubble sort should take an additional argument P, representing the number of concurrent worker processes. For example, for N=100 and P=5,

$ multi_process_bubble 100 5

• The initial (parent) process creates a shared memory segment in which it stores an array of N random integers.
• Next, the parent process forks P worker processes. After fork, each worker process automatically inherits the attached shared memory segment that was created by the parent. Hence there is no need for child processes to call the shmat() system call.
• Each worker process should execute the parallel bubble sort operation on (about equal sized) overlapping segments of the array, as explained in the slides.
• Each worker should use a barrier (busy looping for now) to coordinate with neighboring workers at the end of each pass.
• You can also store any additional data in the shared memory thats needed for interworker synchronization.
• The parent prints out the fully sorted array once all worker processes have finished.
• Is your parallel version faster or slower than the sequential version? Time it using gettimeofday(). Think about how to make a fair comparison.

Part B: Parallel Bubble Sort using Threads

Now implement the same parallel version of even-odd bubble sort using POSIX threads (instead

of multiple processes, as in Part B). The logic is the same, except the following

• Name your program multi_thread_bubble
• Create multiple threads using pthread_create() instead of multiple processes using fork().
• Theres no need to create shared memory, since the global memory is shared by default among all threads of a process.