Project 4

Project files

All files: p4.zip

• Code skeleton: p4.ml

• Files for command line submission (see "Submission" for usage)
  • .submit
  • submit.jar

• Public tests: p4_public_tests.zip

Project description

In class, we developed an interpreter for a simple, multithreaded programming language. That language includes thread creation, (non-reentrant) locks, and wait/notify. In this project, you will extend that interpreter to include a number of other useful multithreading primitives. Note that while you will add these features by modifying the interpreter, in practice many of these features can be added by instead encoding them in terms of other available features; e.g., reader/writer locks can be encoded using regular locks.

When you finish this project, all of the different pieces you develop should work together. Thus, if for a later part of the project you need to modify some of the data structures for the project (e.g., what a configuration is), you might need to then revisit an earlier part of the project so that it works with the new data structure. However, if you are careful about your program design, you should be able to minimize any repeated work.

Important: To grade your project, we will create various configurations and run your step function on them under certain schedules. To make sure we can do this programmatically there are some requirements and restrictions concerning how you carry out your implementation; see the end of the project description, below.

Part 1. A new scheduler

In class, we developed two schedulers: one that runs each thread to completion, and another that runs each thread one step and then switches to the next available thread.

For this part of the project, write a function make_rr_sched_n n : int -> scheduler that is similar to make_rr_sched (supplied in the project code), but creates a scheduler that runs each thread for n ticks (rather than 1 tick) before switching to the next available thread. It should be the case that make_rr_sched_n 1 returns a scheduler that behaves identically to make_rr_sched ().

For purposes of this project, your scheduler should increment its tick count for a thread id each time it returns that thread id, even if that thread id is blocked from running. Again, this is sub-optimal for scheduling in practice, but sufficient for purposes of this project.

Part 2. Better locking

In this part of the project, you will add three extensions to locks:

1. Modify p4.ml so that the step function throws an exception if some thread executes the command Release "lock", Wait "lock", or NotifyAll "lock" but it does not hold "lock". Hint: You will need to keep track of the owning thread id for each lock held.
2. Implement the TryAcquire(lock,lab) command, which tries to acquire lock and, if successful, jumps to lab; if not successful (i.e., the lock is already held by some other thread), it falls through to the next statement, rather than blocking. Your TryAcquire implementation should be made compatible with reentrant locks, discussed next.
3. In the implementation in p4.ml, locks are not reentrant: if the same thread tries to acquire a lock it already holds, that thread will deadlock. For this part of the project, you should change the behavior of Acquire and Release so that locks are reentrant, meaning (a) each lock may still only be held by at most one thread; (b) a lock may be reacquired by the same thread more than once; (c) a lock is released only when the thread that holds it releases the lock the same number of times it acquired it. For example, here is a sequence of Acquire and Release commands along with a description of when the lock is held:
   • Thread 1 - Acquire x - lock acquired by thread 1
   • Thread 1 - Acquire x - lock still held by thread 1
   • Thread 1 - Release x - lock still held by thread 1
   • Thread 1 - Acquire x - lock still held by thread 1
   • Thread 1 - Release x - lock still held by thread 1
   • Thread 1 - Release x - lock released by thread 1
4. Add support for reader/writer locks, as follows. RdAcquire x acquires a lock x for reading. Any number of threads can hold a read lock at once. WrAcquire x acquires a lock x for writing. Only one thread can hold a write lock at a time, and no other thread can hold a read lock when a write lock is held. Thus, RdAcquire x should block if a write lock on x is already held, and WrAcquire x should block if either a read or a write lock on x is already held. RdWrRelease x releases either a reader or writer lock, and your interpreter should raise an exception if a thread attempts to release a reader/writer lock it does not hold. For this part of the project, you can assume that reader/writer locks are disjoint from regular locks, i.e., there will never be a case when both Acquire x and Rd/WrAcquire x is called. Your reader/writer locks should not be reentrant---the interpreter should raise an exception if a thread tries to reacquire (as either read or write) a reader/writer lock it already holds.

Part 3. More synchronization primitives

There are several other useful synchronization primitives aside from locks. For this part of the project, you must implement the following:

1. Barriers. Threads can use a barrier to ensure that all threads conceptually reach some common point. Specifically, each thread should block at a use of the command Barrier until all threads are at a Barrier command; at that point, the program counters of all threads should advance by one. For example, suppose threads 1, 2, and 3 are running, and consider the following sequence of commands:
   • Thread 1 - Barrier - Thread 1 blocks
   • Thread 2 - Assign("x", ENum 3) - Thread 1 still blocked
   • Thread 3 - Barrier - Threads 1 and 3 blocked
   • Thread 2 - Barrier - Threads 1-3 unblocked, advance to next command
   • Thread 2 - Barrier - Thread 2 blocked
   • Thread 1 - Assign("x", ENum 4) - Thread 2 still blocked
   • Thread 3 - Assign("y", Enum 5) - Thread 2 still blocked
   • Thread 1 - Barrier - Threads 1 and 2 blocked
   • Thread 3 - Barrier - Threads 1-3 unblocked, advance to next command
   You should only include threads that have not ended when deciding if all threads have arrived at a barrier. Thus, if a thread ends when other threads are waiting at a barrier, it might allow those threads to proceed (assuming there are no other live threads not waiting at a barrier).
2. Count down latches. A count down latch lets several threads wait until some condition is achieved. A latch is created in some thread with CreateLatch(s,e), where s is the name of the latch and e evaluates to an integer that is the initial count of the latch. (You may assume a latch is only ever created once in a program, and is never created with a negative count.) There are two possible operations on latches: CountDown s decrements the count of the latch by one if the count is positive (i.e., it will not decrement below zero), and WaitLatch s causes the current thread to block until the latch's count is zero. Note that, unlike wait and notifyAll, there is no association between latches and locks---there is no need to hold any particular lock to wait at or decrement a latch. For example, here is a sequence of commands illustrating count down latches:
   • Thread 1 - CreateLatch("latch", ENum 3)
   • Thread 1 - WaitLatch("latch") - Thread 1 blocked, count is 3
   • Thread 2 - CountDown("latch") - Thread 1 still blocked, count is 2
   • Thread 3 - CountDown("latch") - Thread 1 still blocked, count is 1
   • Thread 2 - CountDown("latch") - Thread 1 unblocked
   • Thread 3 - CountDown("latch") - equivalent to Skip
   The interpreter should raise an exception if CountDown or WaitLatch are used on a latch that hasn't been created. You need not handle the case when a latch with the same name is created more than once (i.e., we will not test code such as CreateLatch("latch"); CreateLatch("latch")).
3. Semaphore. A sempahore conceptually represents a set of permits to proceed. Initially, each semaphore contains zero permits. RelSem s increments semaphore s's permit count by one. AcqSem s decreases semaphore s's permit count by one, blocking until a permit is available, i.e., until the semaphore's associated count is greater than zero. For example, here is a sequence of commands illustrating semaphores:
   • Thread 1 - RelSem("sem") - sem count is 1
   • Thread 2 - RelSem("sem") - sem count is 2
   • Thread 1 - AcqSem("sem") - sem count is 1
   • Thread 1 - Assign("x", ENum 3) - sem count is 1
   • Thread 1 - AcqSem("sem") - sem count is 0
   • Thread 1 - AcqSem("sem") - Thread 1 blocks
   • Thread 2 - Assign("y", ENum 4) - Thread 1 still blocked
   • Thread 2 - RelSem("sem") - sem count is 1, thread 1 unblocks, when it proceeds sem count is 0
   Note that semaphores are not explicitly created---implicitly, all possible semaphores exist with zero permits when the program starts.

Part 4. Deadlock detection (Optional!)

This part of the project is optional, for extra credit on this project.

Deadlock occurs when one or more threads are blocked and will never be able to take another step. For example, consider the following sequence of commands in two threads:

• Thread 1 - Acquire "A"
• Thread 2 - Acquire "B"
• Thread 1 - Acquire "B"
• Thread 2 - Acquire "A"

We can characterize this kind of deadlock more precisely as follows. Imagine a graph whose nodes consist of the program's thread ids and locks held under a partcular configuration c. For our example above, the graph nodes are 1, 2, A, and B. Draw an edge from a lock to a tid if that tid holds that lock. For our example, this yields edges A->1 and B->2. Draw an edge from a tid to a lock if that thread is trying to acquire that lock. For our example, this yields edges 1->B and 2->A. Then c has a deadlock if the graph so constructed has a cycle in it. For our example, the cycle is A->1->B->2->A.

For this part of the project, you must implement a function deadlocked : program -> config -> bool that returns true if a configuration is deadlocked according to the above definition, and false otherwise. Note that you need only look for deadlock for mutual exclusion locks with Acquire/Release; you don't need to check for deadlock with Reader/Writer locks, wait/notify, etc.

Requirements on your implementation

• You may only change the type config. (You are free to add additional types if you like.) Thus, you must leave the types expr, mem, cmd, pc, program, tid, lock, waiter, and scheduler as is. Because you can't change the type scheduler, schedulers might be sub-optimal in that they might try running threads that can't make progress because they're waiting for a reader/writer lock or some other feature added to the project. That's ok. If your step function is asked to step a thread that can't make progress, it should return the same configuration it was given as input.
• You must implement a function to_initial_config m pcs that takes a memory and an array of program counter options, and creates an appropriate initial configuration with that memory, program counter, and no locks held, no threads waiting, no barriers activated, etc. We will call this function to create the initial configurations under which we test your step function.
• You must implement functions mem_of c and pcs_of c, which return the memory and program counter option array from a configuration. We will call these functions to verify that your step function behaved correctly when asked to take a step.

Submission

You may either submit over the web or under command line interface.

Submitting over the web

Submit your archive directly to the submit server by clicking on the submit link in the column "web submission".

Next, use the submit dialog to submit your p4.ml file directly.

Select your file using the "Browse" button, then press the "Submit project!" button.

Submitting in command line interface

The first time you submit this way you will be asked to enter your directory ID and password. All files in the directory (and its subdirectories) will then be put in a jar file and submitted to the submit server. If your submission is successful you will see the message:

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.