CS 7400 Machine Problem 8: Fun with the CK Machine

Out: Monday, November 30, 2009

Due: Tuesday, December 8, 2009

For this problem, you will modify the continuation semantics for the IMPLICIT-REFS machine, interps/implicit-refs-via-cks. For each of the following tasks, you are to modify the reduction rules and other material in rules-cks.txt, and modify the interpreter elsewhere.

Your overall goal is to modify this machine to simulate a multiprocessor executing multiple threads on a shared store. In general, a configuration of the machine will have at least the following components:

< K, e, s, P >

where K and e represent the running thread as before, P is a queue representing the threads that are waiting to run, and s represents the store that is shared by all the threads. Each thread will be represented by a <K,e> pair. You may decide you need other things as well in the configuration or in your representation of threads.

Your machine should use pre-emptive scheduling: that is, the running process should run for at most N steps (for some fixed N). Then the running process should be enqueued on P, and the first element of P should become the running process.

1. (20 points) Implement the basic setup described above, both in rules and in executing code. Your top-level (the equivalent of run) should take a list of expressions to evaluate, and should return the list of their values (in order, of course).

   You will need to figure out a mechanism for each thread to communicate its value to the top-level controller, and to make sure that the values are correctly associated with the threads.

2. (10 points) Add to your language a construct

   parlet x1=e1 x2=e2 in e

   which evaluates e1 and e2 in separate threads and then evaluates e in an environment where x1 and x2 are bound to the values of e1 and e2, respectively.

   As before, you will need to figure out a way for the child processes to communicate their values to the parent process, and to signal the parent process that they are finished.

   Observe that, unlike the situation in the previous problem, e1 and e2 can now communicate via shared variables. Demonstrate e1 and e2 communicating with each other. Demonstrate a race condition in this system. You may do this by showing how the answer can vary depending on the size N of the timeslice. Your demonstration should consist of test cases, or as lines in top.scm, with comments indicated what they demonstrate.

3. (10 points) Add to your language some synchronization construct and use it to resolve the race condition you demonstrated in the preceding problem. For example, you could add semaphores, conditions, or compare-and-swap. You may use any synchronization construct you like, so long as you clearly identify it, with citations so we can see whether you've done it right.

Turn in a single set of files that provides all these extensions, both as rules and as code.

Last modified: Thu Nov 26 09:07:22 Eastern Standard Time 2009