Homework #2

CMPS 111, Spring 2007

Assigned: April 18th
Due: TBA

Please read the general homework page for guidelines and submission information. Homework must be submitted online.

All work on this homework must be your own. Please read (and follow!) the academic honesty policy for this class.

  1. Problem 2.3 in the textbook (page 153).
  2. Problem 2.40 in the textbook (page 156).
  3. In class, we discussed the readers/writers synchronization problem. We noted that a writer might "starve" if a continuous stream of readers kept arriving, never releasing the system to the writer. Modify the code for the readers/writers problem so that writers cannot starve. In particular, a writer should go before all readers that arrive after the writer arrives. The system must otherwise work the same way it does currently. You may assume that semaphores keep waiting processes in a FIFO (simple FCFS queue).
  4. On a distant planet, there are three genders. They must share a single bathroom with infinite capacity; unfortunately, only members of a single gender may be in the bathroom at any given time. Thus, the bathroom is in one of the following states:
    • Empty
    • In use by gender 1
    • In use by gender 2
    • In use by gender 3
    A single alien executes the following "code" to use the bathroom: 
    enterBathroom (myGender);
doMyBusiness ();
leaveBathroom (myGender);
    Write the code for enterBathroom (int gender) and leaveBathroom (int gender) so that an alien sleeps when waiting for the bathroom. You may use any semaphores or counters you might need to solve the problem. Does your solution generalize to n genders?
  5. Bank of America processes millions of transactions per day, each of which transfers money from one account to another account. Accounts are identified by (unique) 12 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, BofA 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 BofA fix things so that deadlock is impossible? It is not acceptable to release a lock on an account without completing a transaction (so you can't use two phase locking); in other words, solutions that lock one account and release it if the second account is already locked are not allowed.
  6. Consider the following snapshot of a system:
    Process Allocation Max
    A B C D A B C D
    P0 0 0 1 0 6 7 1 0
    P1 1 0 0 2 2 0 0 2
    P2 3 6 0 2 5 6 0 2
    P3 5 3 1 4 6 3 3 6
    P4 1 0 0 4 6 6 2 6

    Currently, the available resources are: 3-A, 5-B, 1-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.
Last updated 19 Apr 2007 by Ethan L. Miller