Homework #3

Assigned: February 19th
Due: Sunday, February 29th at 11:59 PM

Please read this information on how to submit homework online. Hard copy of homework will not be accepted.

All work on this homework must be your own.

  1. Consider the following method of eliminating deadlocks: When a process requests a resource, it specifies a time limit. If the process blocks waiting for the resource to be free, it is released after the time limit has been reached. Does this method successfully avoid deadlock? Is it a good idea? Why or why not?
  2. Consider the following snapshot of a system:
    Process Allocation Max
    A B C D A B C D
    P0 1 3 5 4 3 3 6 6
    P1 1 0 0 0 1 7 6 0
    P2 0 6 3 2 0 6 5 2
    P3 0 0 1 2 0 0 2 2
    P4 0 0 1 4 2 6 6 6

    Currently, the available resources are: 1-A, 5-B, 3-C, and 0-D. Answer the following questions, assuming you're using the banker's algorithm to manage resources and avoid deadlock:
    1. How many of each resource are there in the system?
    2. What is the content of the Need matrix?
    3. Is the system currently in a safe state? Explain.
    4. If process P2 requests an additional 2 units of B, can this request be granted immediately? Explain.
  3. Citibank processes millions of transactions per day, each of which transfers money from one account to another account. Accounts are identified by (unique) 10 digit numbers. During a transaction, both debit account D (the one from which the money is coming) and credit account C (the one to which the money is going) must be locked by the process doing the transaction. In order to run faster, Citibank does many transactions in parallel (one transaction per process). If a process needs a lock that is not available, the process waits for the lock to become available. There is a very real possibility for deadlock here because many accounts have hundreds or thousands of transactions per day (businesses), and there's a chance of a cycle in the lock graph. How could Citibank fix things so that deadlock is impossible? It is not acceptable to release a lock on an account without completing a transaction; in other words, solutions that lock one account and release it if the second account is already locked are not allowed.
  4. Problem 3.8 in the textbook (page 186).
Last updated 19 Feb 2004 by Bo Adler