SFWRENG 3SH3: Operating Systems Lab 3: POSIX Threads Dr. Borzoo Bonarkdarpour

SFWRENG 3SH3: Operating Systems Lab 3: POSIX Threads Dr. Borzoo Bonarkdarpour

SFWRENG 3SH3: Operating Systems Lab 3: POSIX Threads Dr. Borzoo Bonarkdarpour SFWRENG 3SH3: Operating SystemsLab 3: POSIX ThreadsDr. Borzoo Bonarkdarpour1Overall ObjectiveYou are to write a C or C++ concurrent Shearsort program using POSIX PTHREADSlibrary and semaphore operations. You are NOT to use fork() calls, pipes, or messagequeues in this exercise.The Shearsort is a simple mesh-sorting algorithm that consists of nothing more thanalternately sorting rows and columns of the mesh. In particular, it sorts all the rows in√√Phases 1, 3, . . . , log2 N + 1, and all the columns in Phases 2, 4, . . . , log2 N , where Nis the total number of elements. √ columns are sorted so that smaller numbers moveTheupward. The odd rows (1, 3, .√. , N −1) are sorted so that smaller numbers move leftward,.and the even rows (2, 4, . . . , N ) are sorted in reverse order (i.e., so that smaller numbers√move rightward). The numbers will appear in a snakelike order after 2 log2 N + 1 =log2 N + 1 phases. An example is given in Figure 1. (A proof that the Shearsort algorithmworks can be found in Introduction to Parallel Algorithms and Architectures: Arrays, Trees,Hypercubes by F. Thomson Leighton. However, the information about Shearsort in thishandout should be sufficient for you to complete the exercise.)2AssignmentIn this lab assignment you will use shared memory to store ONE copy of the whole 2dimensional array. Also, you will be required to create a limited number of threads for thesort. For a square array of n×n elements, ONLY n THREADS are to be created. Each threadis to alternate between row (odd) and column (even) phases. To synchronize the phasesproperly, you will need to use semaphores. You are to use at most ONE SEMAPHOREPER THREAD.Your program should implement the Shearsort algorithm to handle 16 integers as follows.1. Read the integers into a 2-dimensional n × n array in global memory from the file”input.txt”. This can be done by the main program.2. Print the integers in the order entered to stdout.1Figure 1: Alternately sorting the rows and columns in Shearsort. The numbers to be sortedappear in a snakelike order after log2 N + 1 phases. Notice that even rows are always sortedin reverse order. The arrow direction indicates the sorting order (from small to large).3. Create and initialize the semaphores necessary for the algorithm.4. Create the n threads to sort the array using Shearsort.5. Wait for the threads to finish.6. Print the array of sorted integers to stdout.Each thread would do the following in each phase of the algorithm.1. By performing the appropriate number of wait operations, block until the prior phase(if any) is finished.2. Sort the row/column in the appropriate order using Bubblesort.23. Perform appropriate signal operations to signal the other threads to begin the nextphase.WARNING: You are NOT to use the sleep() call or any code (such as a loop countingfrom 1 to 10000) to introduce any delay in your program. If any such delaying code is foundin your program, YOU WILL LOSE %30 OF TOTAL POINTS.3POSIX pthreadsPOSIX Threads, usually referred to as Pthreads, is an execution model that exists independently from a language, as well as a parallel execution model. It allows a program tocontrol multiple different flows of work that overlap in time. Each flow of work is referredto as a thread, and creation and control over these flows is achieved by making calls tothe POSIX Threads API. You can find plenty of online resources to learns about the API.Essentially you need to know how to (1) create threads, (2) terminate threads, and (3) usemutex variables. Here’s one resource: https://computing.llnl.gov/tutorials/pthreads/4GuidelinesYou will• work on this assignment individually• implement this assignment using C or C++ (you are free to separate your programinto multiple source files as you see fit)• present your implementation and output to your lab TA.You may present your program in a different section in the same week only once throughout the term.3

  • Continue to make an order HERE