Description
Problem 1 We have a program prob_1.c, it can be compiled fine with: gcc prob_1.c -o prob_1 -g -lpthread What outputs are possible for this program? Put your answers in problems.txt (ASCII file). Problem 2 Give the following pseudo code: // Transfer from account acc_from to account acc_to, // where each account has a mutex field and an amount field bool Transfer (amount, acc_from, acc_to) { pthread_mutex_lock(&acc_from.mutex); pthread_mutex_lock(&acc_to.mutex); if (acc_from.balance < amount) return ERROR; acc_from.balance -= amount; acc_to.balance += amount; pthread_mutex_unlock(&acc_from.mutex); pthread_mutex_unlock(&acc_to.mutex); return SUCCESS; } Client1() { Transfer (amount1, account1, account2); } Client2() { Transfer (amount2, account2, account1); } int main(){ // Some code to initialize two global accounts: account1 and account2 … // The two threads pthread_create(&tid1, NULL, Client1, NULL); pthread_create(&tid2, NULL, Client2, NULL); } 1. Find and describe a potential deadlock in the pseudo code. 2. Now you are given a function Order(pthread_mutex_t *m1, pthread_mutex_t *m2), which returns 0 if m1 and m2 are the same and returns 1 or -1 if m1 and m2 are different. This Order() function has the following properties: if Order(&mutexA, &mutexB) returns value X (where X is not equal to 0), then Order(&mutexB, &mutexA) returns value -X; if Order(&mutexA, &mutexB) and Order(&mutexB, &mutexC) return the same value X, then Order(&mutexA, &mutexC) also return value X. With such a function, how would you fix the potential deadlock. Please describe.
Put your answers in problems.txt (ASCII file). Problem 3 Our goal here is to write a multithreaded program that can calculate the maximum difference for a list of numbers stored in a file, where a number takes one line in the file and the file name is passed in through a command line option. For a file containing the following numbers: 1 2 3 4 5 your program should print out 4. We will use a single manager thread and multiple worker threads to collaborate on solving the problem. We will first start worker threads and then use the main thread as the manager thread. The manager uses a task queue to post tasks if a slot is available in the task queue. The workers fetch tasks from the task queue when they are idle if there are tasks posted in the queue. The manager thread can read in all numbers before starting worker threads, but a new task can be put into the queue only if there is an empty slot. If all task slots have already been occupied, the manager will have to wait for worker threads to complete more tasks before posting more work. If all tasks have already been assigned, workers will have to wait for the main thread to put in more tasks, until the manager informs the worker threads that that all numbers have already been processed. Once all numbers have been worked on, a single reduction task needs to be put in the task queue, and one of the worker threads will take the reduction task and calculate a global maximum. Essentially, this is a producer/consumer problem, where the queue is a task queue. A skeleton, prob_3.c, will help you get started, and the program takes two parameters: ./proc_3 input_long In the given skeleton, the maximum number of worker threads and the task queue size have been defined as 8 and 16, respectively. Basically, there are two type of tasks: many to find the local maximum difference for each worker and one to find the global maximum difference among workers. The total number of tasks is equal to 1+N, where N is the number of numbers in the input file, but we will be using 1+ instead. You need to compute the difference of all pairs of numbers, so be careful when your manager is assigning tasks. The difference computation between the newly read number and all the older ones is a good granularity level for task assignment. Each of your worker can store its local maximum difference to a global structure, based on which the final reduction to find the overall maximum difference can be conducted. One possible design of data structure is using an array to store the local maximum difference for number i to numbers 0…i-1. One way to orgnize tasks: for a file containing 1 CSC 246 Spring 2019 Homework 3 3/10/19, 6)02 AM https://people.engr.ncsu.edu/gjin2/Classes/246/Spring2019/hw/hw3/index.html Page 4 of 5 2 3 4 5 The first task for “1” does not compute anything; the second task for “2” compares “2” with “1”, getting “1” as the local max; the third task for “3” compares “3” with “2” and “1”, getting “2” as the local max; (omitting the fourth task); the fifth task for “5” compares “5” with “1”, “2”, “3”, and “4”, geeting “4” as the local max; the last task compute the global max from local maximums “NA”, “1”, “2”, “3”, “4”. You need to make sure the global reduction task is only worked on after the local ones have been completed, i.e., you somehow need to synchronize between these phase. In the example above, you need to make sure the last task starts after “4” is calculated by the fifth task. Since they are multithreaded programs, you need to be careful while testing and debugging. Make sure you reason about all possible interleavings and use necessary synchronization operations in your code. As always, if your code catch certain error conditions, print meaningful error messages in your own format. After you finish, turn in your source files prob_3.c, Makefile, and README. Homework 3.1 Since we have not covered much on memory management yet and this producer-consumer queue programming assignment can use some extra time, you can use another week to reengineer the program. Each of you can submit a new version of your program and help others on their programs. Below, we describe the policy, and we assume 100 as the maximum points for the programming assignment. If you choose to submit a new version, your final grade for this programming assignment will be adjusted. If your original grade is X with a penalty of Y, which is 0 or 25%, and your new grade is Z, (Z-X) will be scaled and added to X*(1-Y). (Z-X) will be scaled only if it is larger than 20, and points in between 20+10i will be halved for i times, e.g., 26 will be scaled to 23, 34 will be scaled to 26, and 48 will be scaled to 28.5. You need to minimize your code changes. As a result, (Z-X) after scaling with further be divided by your code change factor: number_of_all_lines_in_new_file/number_of_reused_lines. Please still change lines as usual and do not put all code into one line. When you are working on your new version, you can ask for your fellow classmates for help. Suppose you ask two classmates for help, (Z-X)*scalefactor/changefactor will be given to them as credits, and you three need to decide how to distribute the credit. Note that you will still get (Z-X)*scalefactor/changefactor for yourself. You can decide according your own situation by specifying a percentage for each and the two percentage numbers should be less than 1 when they add up. You can decide whom you want to ask for help, and you do not necessarily need to ask for two classmates for help. If you prefer, you can also work in groups. Everyone can provide and offer help. The maximum number of points that can be added to X*(1-Y) will be 25, and the maximum final points is 115. After you finish, turn in your new source files prob_3.c, Makefile, and README. There will be a new submission folder, but please use the original discussion forum. In your README, please CLEARLY DESCRIBE what changes have been made and why they are made. If you do not, your credits will be further scaled. If you provide CSC 246 Spring 2019 Homework 3 https://people.engr.ncsu.edu/gjin2/Classes/246/Spring2019/hw/hw3/index.html Page 5 of 5 or receive help, please briefly describe such activities and specify how the credits should be distributed. Lastly, if you find holes in the policy above, please let the instructor know. Thanks in advance for helping each other master the producer-consumer queue.