Princeton University Computer Science Dept.

Computer Science 510 Programming Languages Andrew W. Appel

Fall 2000

Announcements

More Final Exam Clarifications (Jan 11th)

Problem 2. Yesterday's "clarification" was not very useful. Let me just say that you are to implement mutex locks (without condition variables), and that if thread A attempts a withLock on a lock that is held by thread B, then thread A blocks (without busy waiting) and allows other threads to run until some later time when the lock is released.

Problem 3. Ignore yesterday's "clarification" and use the following specification instead.

After each interface operation (mkVar,mkExp,combine, or output), allow all f function evaluations to complete before accepting the next interface operation. You may assume that the f functions do not call the interface operations (which, of course, would lead to deadlock).

After each interface operation, each f function will execute at most once, because at most one variable has been assigned a new value.

It's all right if you have a central bottleneck. Here we are assuming that the slow thing is the evaluation of each individual f function (so they should be done in different threads), and we are not worrying about the time taken to synchronize between threads (within reason, of course).

Also, in the exam I wrote, "The function f passed to combine and update may be time-consuming to execute..." What I meant was, "The function f passed to combine and output may be time-consuming to execute..."

Final Exam Clarifications

1. Problem 1. In parts a-i, show only the rules for the new operators.

2. Problem 2. I have asked you to implement locks without condition variables. This is a weak (and rather stupid) model of concurrency; for example, if a thread yields while holding a lock, another thread might deadlock on that lock. This is not a bug, it just reflects the weakness of the concurrency model.

3. Problem 3. This information is incorrect and obsolete. Ignore it, and use the January 11th clarification, above. Suppose a thread performs,

      assign(v, 2);
      assign(v, 5);
      output(mkExp(v), fn n=>print(Int.toString n))
   

   In a purely sequential implementation, such as the structure Pem given in the example, only the number 5 will be printed. In your concurrent implementation, it is all right if 2 is printed first, and eventually 5 will be printed. But 5 must the last number printed (by this particular instance of fn n=>print(Int.toString n)). To say this in another way, any particular output routine must eventually converge on the right answer.

4. Problem 3. I wrote, "The function f passed to combine and update may be time-consuming to execute..." But what about the f passed to output? I didn't specify this, so you can make any reasonable decision. For example, you could explicitly assume that any "output f" will be fast, or you could treat the "output f" the same way as for combine and update.

Final Exam now available. I will answer questions in person and by e-mail until 2 p.m. on January 12. After that I will be away from my mail until after the due date of the exam.

Old Announcements