HW #4 Solution

Introduction



The goal of this homework is to practice writing multithreaded code. It will also expose you to the concepts of synchronization using semaphores to access shared data structures. You need to implement three small programs, modify your previous homework to use threads, and build a new program. As usual, we highly recommend spending some time thinking about your code. You may want to design your code rst, think about possible corner cases, and probably even write it down on a piece of paper. It may signi cantly reduce the amount of time that you may spend on writing the code itself.




The homework is structured as follows: Part I consists of readings, Part II is three short programming exercises to practice thread creation and semaphores, Part III is modifying your previous homework, and Part IV is a bigger program-ming exercise with threads.




Part I



For this homework, it is crucial to start early and read the textbook. You should read Chapter 12 from the textbook and corresponding man pages for the functions used in this homework. The web-links below point to the material that may be helpful for this assignment. The second and the third reference, you should be able to access the PDF les for free if you are using the university’s network.




https://en.wikipedia.org/wiki/Quicksort A Parallel Quicksort Algorithm https://dl.acm.org/citation.cfm?doid=366622.366644




We also recommend to go over the readings about locking/synchroniza-tion/threads:




https://www.geeksforgeeks.org/use-posix-semaphores-c/




http://man7.org/linux/man-pages/man3/pthread_spin_lock.3.html




Mutex versus Spinlock




pthreads







1















http://www.mit.edu/people/proven/IAP_2000/index.html




Part II



In this part, you need to implement three small programs that will get you started with writing multithreaded code and give you some practice with using semaphores.




In the rst program, you need to build an application that should print Nth Fibonacci number using separate thread. The program should be called hw4 progfib and N should be obtained from the command line arguments. In this program you need to create a new thread using pthread create() function and nd Nth Fibonacci number using that thread. As before, print only the resulting number to the output. To run a program that prints fourth Fibonacci, one will type the following in the terminal:







$ make progfib




$ ./hw4_progfib 4




In the second program, you need to write an application that will count the number of occurrences of numbers zero, one, and two in some arrays. You will be given three les with following names: \ le1.dat", \ le2.dat", and \ le3.dat". Each le will contain two lines. The rst line contains a number N. The second line contains N space-separated numbers. Your task is to create three threads such that each thread will handle one and only one of the les. Each thread should count the number of occurrences of numbers zero, one, and two on the second line and increment global counters. For storing that information you need to create a global data structure called number counter. Thus, each thread will share the same data structure and should modify that data structure within the thread function body. You need to print only three space-separated numbers to the output that represent the number of occurrences of numbers zero, one, and two respectively. To run that second program, one will type the following in the terminal:







make progcnt



./hw4_progcnt



In the third program, you need to implement Parallel Quicksort algorithm using pthreads. Your program should start with reading the le. The le name is given as the command-line argument. That le contains two lines: the rst line contains number N and the second line contains N space-separated num-bers. Your program should sort numbers from the second line using the parallel quicksort algorithm and print the result as a sorted sequence of space-separated numbers. To run the third program that sorts numbers stored in the le with name \ lename.dat", one will type the following in the terminal:




$ make progqsort




$ ./hw4_progqsort filename.dat







2












Part III



We have discussed what are some reasons to choose a multithread approach versus a multiprocess approach. However, it is also interesting to see the dif-ference from the programming perspective. In this part, you need to modify your previous homework #3. As you may recall, we had fork() to create new processes. In this programming exercise instead of creating new processes, you will need to create new threads to serve the same purposes. Thus, your goal is to re-write part of your homework #3 but instead of using fork() and cre-ating new processes, now you need to use pthread create() and create new threads. You need to re-implement the following commands from the previous homework:







List of commands:




{ help (this stays same) { re TID




{ hire X { reall




{ list { exit




Hint: You may want to read about pthread detach() function.







Part IV



In this part, you need to write a bigger program called museum overseer that will imitate a simple garbage collector that runs in a separate thread. Now let’s phrase that in terms of art!







In the beautiful city of New Stony Brook, there are ve art museums. In this city, there are many people who enjoy going to art museums on a daily basis. Every morning all of the museums open their door to the public and in each of the museums there will be one person who opened it and we consider that person as the rst visitor. Usually, art museums close in the evening, but in the city of New Stony Brook, an art museum cannot close if there is at least one visitor. However, once it is evening and there are no visitors in the art museum, it can close its doors. And now your goal is to make sure that eventually all museums are closed.




Now let’s discuss some internals of this program. First, you need to create some data structure that will represent art museums and will keep a count of the number of visitors in each museum. That data structure should be called museum ds. Then you need to implement several functions:







visitor in(int N). This function imitates that a visitor entered museum number N.




visitor out(int N). This function imitates that a visitor left museum number N.










3















museum info(). This function prints information about the current state of the museums. More information about this function will be provided later.




museum close(int N). This function imitates closing museum number N. museum clean(). This function kicks out all visitors from all museums if




there are any, closes all museums, and frees all the memory.







museum info(). This function should print information about the current state of each museum in the following form:




<MUSEUM NUMBER:<NUMBER OF VISITORS:<STATUS.




For example, if museum number ve has four visitors, then the respective line for that museum will look as \5:4:OPEN". The museum can either be \OPEN" or \CLOSED".




Now, once all those functions are implemented, we nally can proceed to our version of the garbage collector. You need to implement a shell that supports the following commands:




in N X. This command adds X more visitors to the museum N. out N X. This command removes X visitors from the museum N.




info. This command prints information about the current state of the museums in the format described earlier.




start. This command starts the garbage collector. exit. This command exits the program.




The \in N X" command should create X threads where each thread will call visitor in(int N) to modify number of visitors at an art museum number N. You need to use for-loop to create these threads and you should not join your threads within that for-loop.







The \out N X" command should create X threads where each thread will call visitor out(int N) to modify number of visitors at an art museum num-ber N. You need to use for-loop to create these threads and you should not join your threads within that for-loop.







The \info" command should create a thread that will internally call the museum info() function to print the information about the current state of the museums.







Finally, the start command should create a thread that will check ev-ery three seconds if there are open art museums with zero visitors. If there is such an art museum then that thread should close that art museum using museum close(int N) function.




Don’t forget to call museum clean() before exiting your program.
















4












Notes and Requirements



No zombies. No memory leaks. No crashes.




You need to create a Makefile that will allow us to compile your code and put the documentation for your programs into README le. The documen-tation should be written in such way, that a person who will read it should be able to understand how to compile/run your program, what it is about, and high-level details about your implementation.




Your code should be thread-safe. We will use many threads during testing of your code to verify the correctness of your submission.




You need to follow the provided speci cation, especially the required names for executable les and data structures. Failing to do so may result in a severe penalty for the homework grade even if the di erence is just one symbol.




If you are asked for some output then you need to print only what was asked and nothing else. You should create a function called cse320 print(char* msg) that you need to use for any required output. The body of that function may be modi ed during grading.







Submission



Please click on the link below that will set up a repository for you for this homework. In case, it will take more than a few minutes please contact me so I can set up the repository for you manually.




https://classroom.github.com/a/oe5bE6uU




Extra Credit I



For this extra credit, you need to implement the following parallel algorithms using pthreads and report runtime performance gain/loss with varying number of threads:




Parallel Mergesort, Parallel Samplesort, Parallel partitioning,




Parallel matrix multiplication, and Parallel algorithm of your choice.




As before, you need to demonstrate your extra credit work in-person before the last lecture of this semester.



















5












Extra Credit II



For this extra credit, you need to implement three versions of second program in the Part II using di erent types of synchronization mechanisms:




pthread mutex t mutexes,




sem t semaphores, and




pthread spinlock t spinlocks.







You also need to measure running time for your program while varying input size and make a write up to report your ndings.




As before, you need to demonstrate your extra credit work in-person before the last lecture of this semester.

























































































































6