Project 6

Updates

• Dec 10. Notes on the project
  • Do not use busy waiting for any part of this project.
  • You can use a while loop in your code if it's useful (e.g., to wait while a condition is true).
  • Be sure to look at this post and this post on the web forum.

Introduction

In this project, you will build some simple functions to show the relationship betewen locking and message passing, and you will reimplement part 2 from project 5 using Concurrent ML-style message passing concurrency (the Event module) in OCaml instead of shared memory concurrency in Ruby.

For this project, you will probably want to look at the Thread library documentation from the OCaml manual. To make a version of the OCaml top level in which these functions are available, run the following command:

ocamlmktop -thread unix.cma threads.cma -o mytop

This creates a program mytop, which is the OCaml top level, except threads are enabled. To use it, run

./mytop -I +threads

To save everyone from having to build mytop themselves, you can run

which is already in your path if 330submit is in your path.

Part 1: Encodings

As we mentioned in class, message passing and locking are both representable using the other. In this part of the project, you will demonstrate this very concretely by developing two encodings.

First, in the file channel.ml, fill in the implementation of the Channel module, which has the following signature:

type 'a t
val new_channel : unit -> 'a t
val send : 'a t -> 'a -> unit
val receive : 'a t -> 'a

Here new_channel makes a new channel; send sends a value over a channel, blocking until a receiver tries to receive it; and receive receives a value from a channel, blocking until a sender sends something over the channel.

In your implementation of this module, you must use OCaml's Mutex and Condition modules, and you must not use OCaml's Event module. In this way, you will show that you can build channels using locks. Hint: You can probably just port the producer consumer example code from lecture, except you will need to make sends block until a receiver is ready.

Second, in the file lock.ml, implement the Lock module, which has the following signature:

type t
val create : unit -> t
val acquire : t -> unit
val release : t -> unit

Here create makes a new lock, which can be acquired and released by calling the appropriate functions. In your implementation of this module, you must use OCaml's Event module, and you must not use OCaml's Mutex or Condition modules. Your locks do not have to be reentrant, i.e., it is OK to block if the same thread tries to acquire a lock more than once. Your code can also behave arbitrarily if a thread tries to unlock a lock it doesn't hold.

Part 2: The Simulation

Finally, implement exactly the same simulation as project 5, with the same output. Specifically, write a function

simulate : string list list -> unit

Notes:

• As in project 5, you should have a thread per person and a thread per train, at a minimum. You may also wind up creating other threads, depending on exactly how you design your simulation.
• You must use the Event module to perform all communication between threads. This means, with one exception (just below), you must not use either the Mutex or Condition modules. (You will also definitely use the Thread module to create threads.)
• The one exception to the above rule is that you can and should use Mutex to ensure that lines printed from different threads are not interleaved. To make this easier, in metro.ml we've defined a function printf you can call to do all your printing. It first acquires a lock, then prints, then flushes, then releases the lock. For example, you could write

    printf "Foo %d: %s\n" 3 "bar"
  

  to print Foo 3: bar\n to standard output.

• Do not use the code you wrote for part 1. You should just use sends and receives directly.
• Be sure to call flush stdout after printing an output message, so that you don't get any weird interleavings in your output.
• You can call Thread.delay 1.0 to sleep for 1 second.
• You can use the verifier you wrote for project 5 to test your output.

Starting Code

You can get a (very minimal) skeleton for this project at

Academic Integrity

The Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this assignment." Consequently your program is requested to contain this pledge in a comment near the top.

Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.