## 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

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

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.