Someone has coded a manager-worker idiom with message queues and they both work according to the below pseudo-code.

Make the following assumptions:

• requests and responses are both message queues (each has space for 5 messages)

• one instance of the manager runs and one instance of the worker runs

• create_task() and process_request() are always successful and are useful

• print_response() always succeeds and prints out a nicely formatted response

• send() sends a message to a queue and never fails

• receive() returns a message from a queue and never fails

• send() and receive() are both blocking operations

Worker:

while (1) {

msg = receive(requests);

resp = process_request(msg);

send(responses, resp);

}

Manager:

for (i = 0; i < M; i++) {

msg = create_task(); send(requests, msg);

}

for (i = 0; i < M; i++) {

msg = receive(responses); print_response(msg); }

1. A deadlock happens at which values of M?

2. Draw a resource allocation graph representing the systems state when the deadlock happens.

3. Assume there are two workers running. At what values of M does the deadlock happen?

4. How can we prevent a deadlock (even if M is large and the queue sizes are very small)?