CS414 Prelim 1.  10:15 to 11:25. 

Three problems, 25 points each.  Closed book.

 

Your name: ___________________Your ID : _______________________

 

 

  1. You, your mom, and your dad, are programmers.  As a vacation activity, you’ve each coded a different crossword-puzzle solving algorithm.  Now you want to integrate the three procedures into one concurrent program.

Assume that each of method is a single thread and that the puzzle is a shared object these three threads access concurrently.  Each thread looks at the list of questions, finds one it can answer (reading the puzzle if needed), and then writes down the answer.  Sometimes, a guess turns out to be wrong.  When a thread realizes that an existing word is incorrect, it can also erase that word, by “writing” blanks as necessary.  In the example below, if 1-across used to contain “dog”, perhaps the thread that wanted to put “apple” into 1-down first erased “dog”, so that the “a” would make sense. 

For simplicity, we’re not going to think about how the threads figure out who will work on which clue.  Instead, we’ll focus only on the way that threads access the puzzle.  Our challenge is to maintain a high degree of concurrency, but to avoid “conflicts” where two threads try to update the same cells in different ways at the same time.  Other aspects of solving the problem, such as recognizing that an initial guess was wrong, marking a clue as “apparently solved,” or putting a clue back on the list of unsolved clues are not part of the problem today.

Below are several options for synchronization.  In each case, comment very briefly on whether it would work, how well it would work, and why. 

A sample crossword puzzle: 

Across:

1.      Witch’s pet

2.      Apricot _________

            Down:

1.      Newton’s inspiration

 

 

 

a)      Associate a separate mutex semaphore with each square – one semaphore for each letter.  Obtain mutual exclusion prior to reading, writing or erasing that letter.  Release it immediately after doing so, before obtaining mutex for the next letter. 

 

 

 

 

 

 

 

b)      Like (a) in that we have an array of mutex semaphores, one per cell on the puzzle.  But this time, obtain mutual exclusion prior to reading, writing or erasing each word, by waiting on the single semaphore associated with the first letter of that word.  Release the mutex after reading or writing the whole word.  To write “apple”, number 1 down, you wait on the semaphore for the cell containing the “a”, numbered 1-down.

 

 

 

 

 

 

c)      Same as (c) but before writing or erasing a word, obtain mutual exclusion for every word your word will overlap.  For example, if 9-down crosses 3-across and 6-across, first obtain mutual exclusion using the semaphores associated with all three words.  Obtain these in alphabetic order: 3-across, 6-across, 9-down, etc.

 

 

 

 

 

d)      Same as (c) but using a reader’s and writers solution, with separate semaphores for each word.  If you are reading 9-down and it crosses 3-across, you’ll do a start-read for both words.  If you are writing 9-down you’ll do a start-write for both words before writing any letters.

 

 

 

 

 

 

 

 

 

e)      Does it matter that in (c) and (d) the semaphores are obtained in alphabetical order?  Suppose we had said you can do it in a random order.  Would that make the solution incorrect?  Explain briefly.  If the solution would still work, would it be better?


2.   Below is the Bakery algorithm, using the same code and notation we employed in class.  Recall that (a,x)<(b,y) means “(a < b) or (a=b and x<y)”.   Assume that N=5.

 

#define      true                 1

#define      false                0

int number[N], choosing[N];  /* Initially number[i] = 0, choosing[i] = false */

     

Process Pi:

      while (1) {

                      do something else

choosing[i] = true;

ticket[i] = max(number[0]…number[N-1])+1;

choosing[i] = false;

for(k = 0; k < N; ++k) {

while(choosing[k] ) loop;

while((number[k],k) < (number[i],i)) loop;

}

 

Critical Section for Process i

number[i] := 0;

 

}

 

 

Suppose that process 0 is in the “do something else” code when process 2 enters the critical section, and that process 2 has number value 5.   Now suppose that process 0 finishes the “do something else code” while process 2 is still in the critical section.  The next line that process 0 will execute is “choosing[0] = true;”  Which of the following are possibilities?  Explain, by reference to the code, why each can or cannot occur, explaining the conditions that can cause the scenario to arise, or explaining why no possible execution sequence can cause this to happen.   Don’t worry about numbers overflowing, but do consider possible actions by other processes.

 

 

 

 

 

 

 

 

 

 

 

 

a)      Process 2 has not yet left the critical section, yet process 0 doesn’t wait when it executes the while loop “while((number[2],2) < (number[0],0)) loop”

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

b)      Process 2 is able to leave and re-enter the critical section three times before Process 0 is able to enter it even once.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

c)      Process 1 enters the critical section three times before process 0 enters it even once.

 

 

 

 

 

 

 

 

 

 

 

d)      When process 0 enters the critical section, it prints number[0].  The value is 1.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

e)      Process 0 never enters the critical section, although other processes continue to do so.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.   Suppose that an operating system uses read and write locks to control file access.  You can assume that each process accesses many files, and that the order in which this happens can’t be controlled or predicted.   These locks work like the readers and writers mechanism we discussed in class – you obtain a read lock by calling “BeginRead” and release it with “EndRead”, etc.

 

 

a)  Give a very simple execution example, with as few processes and files as possible, in which a deadlock arises.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

b) Suppose that the operating system maintains a process-wait graph, so that if process i holds a lock and process j is trying to obtain that lock, there will be a node for i, a node for j, and an arrow from i to j.  Now, suppose that before allowing a process to obtain a requested lock, the operating system adds the associated wait edge to the graph, and runs a reducibility test.  It grants the lock request only if the graph is reducible.  Otherwise, the lock request fails with the error code “EMIGHTDEADLOCK”.   Would this avoid the risk of deadlocks?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

c) Same scenario as part (b).  Now suppose that when an application gets the error code EMGHTDEADLOCK it waits for a random amount of time between 0 and 1 second, then requests the lock again, and loops in this manner.  Would this result in a correct system?  Explain.