Note for Project 1

Phase 1: Build a thread system

Index

TASK I: (5%, 5 lines) Join

Implement KThread.join().

(5%, 5 lines) Implement KThread.join(). Note that another thread does not have to call join(), but if it is called, it must be called only once. The result of calling join() a second time on the same thread is undefined, even if the second caller is a different thread than the first caller. A thread must finish executing normally whether or not it is joined.

Correctness constraints

No busy waiting
Return immediately.
this method must only be called once; the second call is not guaranteed to return.

New variables

private variable in class KThread: joinQueue, wait queue for joined on me thread

Interface

KThread.join: waits for this thread to finish. if this thread is already finished.

Pseudocode

join() {
  Disable interrupts;
  if (joinQueue not be initiated) {
      create a new thread queue (joinQueue) with transfer priority flag opened
      joinQueue acquires this thread as holder
  }
  If (CurrentThread != self) and (status is not Finished) {
      add current thread to join queue
      sleep current thread 
  }

  Re-enable interrupts;
}

KThread.finish: finish the current thread and schedule it to be destroyed when it is safe to do so.

Note: KThread.finish has already implemented, just need to add several lines of code in it.

Pseudocode

finish() {
 // Interrupts have been disabled.
 ...(existing code)...
 get join queue thru current thread in static interface KThread.finish
 Ready the thread on the joinedOnMe queue
  ...(existing code)...
}

Test Strategy

Test ThreadGrader3.a: Tries a join on thread x before x actually runs
Test ThreadGrader3.b: Tries a join on thread x after x has completed

Test Case

Var1: fork a child thread, join the child thread
Var2: fork a child thread, then main thread yields, then join the child thread

============================================================================

TASK II: (5%, 20 lines) condition variable

Implement condition variables directly

(5%, 20 lines) Implement condition variables directly, by using interrupt enable and disable to provide atomicity. We have provided a sample implementation that uses semaphores; your job is to provide an equivalent implementation without directly using semaphores (you may of course still use locks, even though they indirectly use semaphores). Once you are done, you will have two alternative implementations that provide the exact same functionality. Your second implementation of condition variables must reside in class nachos.threads.Condition2

Correctness constraints

Condition Variable: a queue of threads waiting for something inside a critical sections. Allow sleeping inside critical section by atomically releasing lock at time we go to sleep.

Basic structure of the solution

sleep(): atomically release the lock and relinkquish the CPU until woken; then reacquire the lock.

       release condition lock
       diable interrupt
       add current thread to wait queue
       make current thread sleep
       restore interrupt 
       acquire condition lock

wake(): wake up a single thread sleeping in this condition variable, if possible.

      if wait queue is not empty 
          disable interrupt
          remove the first element from wait queue 
          put the first element into ready queue
          restore interrupt

wakeAll(): wake up all threads sleeping inn this condition variable.

       while wait queue is not empty
          invoke wake()

Test strategy

Tests condition variables using a few threads
Tests condition variables using many threads

Test case

       Create a lock variable and a condition variable
       Spawn multiple threads, each thread invoke sleep() inside the lock
       in main thread, invoke wake() to wake up the first thread in the wait queue.
       in main thread, invoke wakeAll() to wake up left sleeping threads.

============================================================================================

TASK III: (10%, 40 lines) Alarm class

Complete the implementation of the Alarm class

(10%, 40 lines) Complete the implementation of the Alarm class, by implementing the waitUntil(long x) method. A thread calls waitUntil to suspend its own execution until time has advanced to at least now + x. This is useful for threads that operate in real-time, for example, for blinking the cursor once per second. There is no requirement that threads start running immediately after waking up; just put them on the ready queue in the timer interrupt handler after they have waited for at least the right amount of time. Do not fork any additional threads to implement waitUntil(); you need only modify waitUntil() and the timer interrupt handler. waitUntil is not limited to one thread; any number of threads may call it and be suspended at any one time.

Correctness constraints

Note: Nachos will not function correctly with more than one alarm.

A thread calls waitUntil to suspend its own execution until time has advanced to at least now + x.
Do not fork any additional threads to implement waitUntil().
waitUntil is not limited to one thread; any number of threads may call it and be suspended at any one time.
No busy-waiting.

Basic structure of the solution

Alarm(): allocate a new Alarm, set the machine's timer interrupt handler to this alarm's callback.

      create a Runnable object to wrapt run(), run() just to invoke this.timerInterrupt 
      invoke Machine.timer().setInterruptHandler, specify Runnable object as the only argument

timerInterrupt(): callback function, will be invoked by Nacho machine's timer approximately every 500 clock ticks.
```
      check if threads in waiting queue are due
      put due threads into ready queue
```
waitUntil(long x): put the current thread to sleep for at least x ticks. The thread must be woken up during the first timer interrupt where
(current time) >= (WaitUntil called time) + (x)
```
       current time plus wait time, get the due time.    
       put current thread and due time into waiting queue
       current thread sleeps 
```

Test strategy

tests waitUntil to ensure it waits at least minimum amount of time
tests whether waitUntil actually wakes up at correct time

Test case

fork several threads, invoke waitUntil with different time amount.
verify if all the threads waits at least minimum amount of time and wakes up at correct time.

=====================================================================================================

TASK IV: (20%, 40 lines) Communicator

Implement the Communicator class with operations

Implement synchronous send and receive of one word messages (also known as Ada-style rendezvous), using condition variables (don't use semaphores!). Implement the Communicator class with operations, void speak(int word) and int listen().

speak() atomically waits until listen() is called on the same Communicator object, and then transfers the word over to listen(). Once the transfer is made, both can return. Similarly, listen() waits until speak() is called, at which point the transfer is made, and both can return (listen() returns the word).

Your solution should work even if there are multiple speakers and listeners for the same Communicator (note: this is equivalent to a zero-length bounded buffer; since the buffer has no room, the producer and consumer must interact directly, requiring that they wait for one another). Each communicator should only use exactly one lock. If you're using more than one lock, you're making things too complicated.

Ada's Rendez-Vous refer to the paper as below

Title: Resurrecting Ada's Rendez-Vous in Java* Author: Luis Mateu, Jose M. Piquer and Juan Leon Casilla 2777,Santiago,Chile lmateu@dcc.uchile.cl

http://en.wikibooks.org/wiki/Ada_Programming/Tasking#Rendezvous Rendezvous The only entities that a task may export are entries. An entry looks much like a procedure. It has an identifier and may have in, out or in out parameters. Ada supports communication from task to task by means of the entry call. Information passes between tasks through the actual parameters of the entry call. We can encapsulate data structures within tasks and operate on them by means of entry calls, in a way analogous to the use of packages for encapsulating variables. The main difference is that an entry is executed by the called task, not the calling task, which is suspended until the call completes. If the called task is not ready to service a call on an entry, the calling task waits in a (FIFO) queue associated with the entry.

This interaction between calling task and called task is known as a rendezvous. * The calling task requests rendezvous with a specific named task by calling one of its entries. A task accepts rendezvous with any caller of a specific entry by executing an accept statement for the entry. If no caller is waiting, it is held up. Thus entry call and accept statement behave symmetrically. (To be honest, optimized object code may reduce the number of context switches below the number implied by this naive description.)

Correctness constraints

A communicator allows threads to synchronously exchange 32-bit messages.
Multiple threads can be waiting to speak, and multiple threads can be waiting to listen .
But there should never be a time when both a speaker and a listener are waiting, because the two threads can be paired off at this point.

Basic structure of the solution

Data Structure

Two conditions: Condition for speakers and Condition for listeners, they share the same lock
A variable 'listener' to record count of listeners
A variable 'speaker' to record count of speakers
A variable 'wordReady' to record if speaker has spoken a word

Functions

Communicator(): Allocate a new communicator, and initialize class members.

void speak(int word): Wait for a thread to listen through this communicator, and then transfer word to the listener. Note Exactly one listener should receive word .

           speaker acquires the lock
           increase the number of speakers by one

           while no available listener or word is ready(but listener hasn't fetched it)
                   speaker goes to sleep

           speaker says a word
           set flag to show that word is ready.
           wake up all the listener
          
           decrease the number of speaker by one
           speaker releases the lock

int listen(): Wait for a thread to speak through this communicator, and then return the word that thread passed to speak.

           listener acquires the lock
           increase the number of listener by one
          
           while word is not ready
                      Wake up all the speaker (although it's not efficient, it can keep code simple enough)
                      listener goes to sleep
                     

           (By now listener is waken up and require the lock again)

           listener receives the word
           reset flag to show that word is unavailable 

           decrease the number of listener by one
           listener releases the lock

Test strategy

Test ThreadGrader2.a: Tests your communicator
Test ThreadGrader2.b: Tests your communicator, with more speakers/listeners
Test ThreadGrader2.c: Tests your communicator, with more speakers/listneers, and transmits more messages

Test case

Test ThreadGrader2.a: Tests your communicator
- VAR1: Test for one speaker, one listener, speaker waits for listener
- VAR2: Test for one speaker, one listener, listener waits for speaker
Test ThreadGrader2.b: Tests your communicator, with more speakers/listeners
- VAR3: Test for one speaker, more listeners, listener waits for speaker
- VAR4: Test for one speaker, more listeners, speaker waits for listener
- VAR5: Test for one speaker, more listeners, listeners waits for speaker, and then create more listeners
- VAR6: Test for more speakers, one listener, listener waits for speaker
- VAR7: Test for more speakers, one listener, speaker waits for listener
- VAR8: Test for one listener, more speakers, speakers wait for listener, and then create more speakers
Test ThreadGrader2.c: Tests your communicator, with more speakers/listneers, and transmits more messages
- VAR9: Test for more speakers, more listeners, listeners waits for speaker
- VAR10: Test for more speakers, more listeners, listeners waits for speaker
- VAR11: Test for more speakers, more listeners, speakers and listeners have the same number but created with random order.
- VAR12: Run above test cases in batch for more than two hours, make sure no exception occurs.

=====================================================================================================

TASK V (35%, 125 lines) priority schedulin

###Implement priority scheduling in Nachos by completing the PriorityScheduler class.

(35%, 125 lines) Implement priority scheduling in Nachos by completing the PriorityScheduler class. Priority scheduling is a key building block in real-time systems. Note that in order to use your priority scheduler, you will need to change a line in nachos.conf that specifies the scheduler class to use. The ThreadedKernel.scheduler key is initially equal to nachos.threads.RoundRobinScheduler. You need to change this to nachos.threads.PriorityScheduler when you're ready to run Nachos with priority scheduling. Note that all scheduler classes extend the abstract class nachos.threads.Scheduler. You must implement the methods getPriority(), getEffectivePriority(), and setPriority(). You may optionally also implement increasePriority() and decreasePriority() (these are not required). In choosing which thread to dequeue, the scheduler should always choose a thread of the highest effective priority. If multiple threads with the same highest priority are waiting, the scheduler should choose the one that has been waiting in the queue the longest.

An issue with priority scheduling is Priority Inversion. If a high priority thread needs to wait for a low priority thread (for instance, for a lock held by a low priority thread), and another high priority thread is on the ready list, then the high priority thread will never get the CPU because the low priority thread will not get any CPU time. A partial fix for this problem is to have the waiting thread donate its priority to the low priority thread while it is holding the lock.

Implement the priority scheduler so that it donates priority, where possible. Be sure to implement Scheduler.getEffectivePriority(), which returns the priority of a thread after taking into account all the donations it is receiving.

Note that while solving the priority donation problem, you will find a point where you can easily calculate the effective priority for a thread, but this calculation takes a long time. To receive full credit for the design aspect of this project, you need to speed this up by caching the effective priority and only recalculating a thread's effective priority when it is possible for it to change.

It is important that you do not break the abstraction barriers while doing this part -- the Lock class does not need to be modified. Priority donation should be accomplished by creating a subclass of ThreadQueue that will accomplish priority donation when used with the existing Lock class, and still work correctly when used with the existing Semaphore and Condition classes.

Terminology

Priority inheritance(Priority donation)

Under the policy of priority inheritance, whenever a high priority task has to wait for some resource shared with an executing low priority task, the low priority task is temporarily assigned the priority of the highest waiting priority task for the duration of its own use of the shared resource, thus keeping medium priority tasks from pre-empting the (originally) low priority task, and thereby affecting the waiting high priority task as well. Once the resource is released, the low priority task continues at its original priority level.
Effective priority

The effective priority of a thread is the priority of a thread after taking into account priority donations.

Correctness constraints

A priority scheduler associates a priority with each thread. The next thread to be dequeued is always a thread with priority no less than any other waiting thread's priority.
A priority scheduler must partially solve the priority inversion problem; in particular, priority must be donated through locks, and through joins.

New state variables [5]

PriorityQueue.holder - this ThreadState corresponds to the holder of the resource signified by the
PriorityQueue.waitQueue - an ArrayList of ThreadStates waiting on this resource. Unsorted.
PriorityQueue.dirty - set to true when a new thread is added to the queue, or any of the queues in the waitQueue flag themselves as dirty.
PriorityQueue.effective - the cached highest of the effective priorities in the waitQueue. This value is 　invalidated while dirty is true.
ThreadState.myResources - collection of PriorityQueues that signify the Locks or other resources that this thread currently holds.
ThreadState.waitingOn - PriorityQueues corresponding to resources that this thread has attempted to acquire but could not. Note a thread must not simutaneously wait for access to multiple resources, so only one queue needed at here.
ThreadState.effective - the cached effective priority of this thread. this value is invalidated when dirty is true
ThreadState.dirty - set to true when this thread's priority is changed, or when one of the queues in myResources flags itself as dirty.

Basic structure of the solution

PriorityQueue

PriorityQueue.getEffectivePriority (NO need to implement): Get the effective priority of the specified thread.

Note, must be called with interrupts disabled.

For a priority scheduler, this is the maximum of the thread's priority and the priorities of all other threads waiting for the thread through a lock or a join.

      if do not transfer priority, return priority directly
      if (dirty)
        effective = minimum priority;
        for each ThreadState t in waitQueue
          effective = MAX(effective, t.getEffectivePriority())
        dirty = false;
      return effective;

PriorityQueue.setPriority: NO need to implement set actual priority of the specified thread. Then set this queue's dirty flag, and calls setDirty on the current holder of this thread.

Must be called with interrupts disabled.
```
  public void setDirty()
    if do not transfer priority
            there is no need to recurse, return
    dirty = true;
    if have a holder
           Invoke holder.setDirty()
```
PriorityQueue.acquire: Implemented Sets the holder of this queue to the specified thread, bypassing the queue. Resets previous holder and sets dirty flags as in nextThread().
```
if I have a holder and I transfer priority
    remove myself from the holder's resource list
thread.acquire(this)
waitQueue.holder = state;
```

PriorityQueue.nextThread: [Implemented 10/27/2013] Remove a thread from the beginning of the priority queue

  if I have a holder and I transfer priority, remove myself from the holder's resource list
  if waitQueue is empty, return null
     ThreadState firstThread = pickNextThread();
     remove firstThread from waitQueue
     firstThread.acquire(this);
  return firstThread

PriorityQueue.pickNextThread: [Implemented 10/27/2013] Return the next thread that nextThread() would return, without modifying the state of this queue.

If this queue is dirty, returns the maximum of each of the ThreadStates.getEffectivePriority() in this queue.
```
ThreadState ret = null
for each ThreadState ts in waitQueue
   if ret is null OR ts has higher priority/time ranking than ret
      set ret to ts
return ret;
```
PriorityQueue.waitForAccess: [No need to implement] Called when waitForAccess(thread) (where thread is the associated thread) is invoked on the specified priority queue. The associated thread is therefore waiting for access to the resource guarded by waitQueue. This method is only called if the associated thread cannot immediately obtain access.

ThreadState

ThreadState.setPriority : [Implemented 10/27/2013] Set the priority of the associated thread to the specified value.

set non-donated priority to the argument setDirty()
ThreadState.setDirty [Implemented 10/27/2013] Set the dirty flag, then call setdirty() on each thread of priority queue that the thread is waiting for. ThreadState.setDirty and PriorityQueue.setDirty would invoke each other, they are mutually recursive.

public void setDirty() if already dirty return dirty = true; for each of the PriorityQueues that the thread is waiting on, pq.setDirty
ThreadState.waitForAccess [Implemented 10/27/2013] This method is only called if the associated thread cannot immediately obtain access.

add the waitQueue to my waitingOn list if the waitQueue was previously in myResources, remove it and set its holder to null. if waitQueue has a holder, set the queue to dirty to signify possible change in the queue's effective priority
ThreadState.acquire [Implemented 10/27/2013] Called when the associated thread has acquired access to whatever is guarded by waitQueue

add waitQueue to myResources list if waitQueue was in my waitingOn list, remove it

setDirty();
getEffectivePriority [Implemented 10/27/2013] Return the effective priority of the associated thread.

public int getEffectivePriority() if (dirty) { effective = non-donated priority for each PriorityQueue pq that I am currently holding effective = MAX(effective, pq.getEffectivePriority) } return effective;

Test strategy

Phase I:

Test ThreadGrader5.a: Tests priority scheduler without donation
Test ThreadGrader5.c: Tests priority scheduler without donation, altering priorities of threads after they've started running

Phase II:

Test ThreadGrader6a.a: Tests priority donation
Test ThreadGrader6a.b: Tests priority donation with more locks and more complicated resource allocation

Test case

Test ThreadGrader5.a: Tests priority scheduler without donation
- VAR1: MyTester.PriopritySchedulerVAR1. Create several(>2) threads, verify these threads can be run successfully.
- VAR2: MyTester.PriopritySchedulerVAR2. Create lots of threads with more locks and more complicated resource allocation
Test ThreadGrader5.c: Tests priority scheduler without donation, altering priorities of threads after they've started running
- VAR3: MyTester.PriopritySchedulerVAR3. Create several(>2) threads, decrease or increase the priorities of these threads, verify these threads can be run successfully.
- VAR4: MyTester.PriopritySchedulerVAR4. Create a scenario to hit the priority inverse problem. Verify the highest thread is blocked by lower priority thread.
Test ThreadGrader6a.a: Tests priority donation
- VAR: Tested by VAR4

Test ThreadGrader6a.b: Tests priority donation with more locks and more complicated resource allocation

VAR: Tested by Other cases.

     KThread.selfTest();
     Communicator.selfTest();
     Condition2.selfTest();
     Alarm.selfTest();
     Semaphore.selfTest();

**On 12/7/2013, at last I've completed coding and testing of TASK V. several months passed.

===========================================================================================================

Task VI: (25%, 150 lines) Boat Grader

Now that you have all of these synchronization devices, use them to solve this problem. You will find condition variables to be the most useful synchronization method for this problem. A number of Hawaiian adults and children are trying to get from Oahu to Molokai. Unfortunately, they have only one boat which can carry maximally two children or one adult (but not one child and one adult). The boat can be rowed back to Oahu, but it requires a pilot to do so.

Arrange a solution to transfer everyone from Oahu to Molokai. You may assume that there are at least two children.

The method Boat.begin() should fork off a thread for each child or adult. Your mechanism cannot rely on knowing how many children or adults are present beforehand, although you are free to attempt to determine this among the threads (i.e. you can't pass the values to your threads, but you are free to have each thread increment a shared variable, if you wish).

To show that the trip is properly synchronized, make calls to the appropriate BoatGrader methods every time someone crosses the channel. When a child pilots the boat from Oahu to Molokai, call ChildRowToMolokai. When a child rides as a passenger from Oahu to Molokai, call ChildRideToMolokai. Make sure that when a boat with two people on it crosses, the pilot calls the ...RowTo... method before the passenger calls the ...RideTo... method.

Your solution must have no busy waiting, and it must eventually end. Note that it is not necessary to terminate all the threads -- you can leave them blocked waiting for a condition variable. The threads representing the adults and children cannot have access to the numbers of threads that were created, but you will probably need to use these number in begin() in order to determine when all the adults and children are across and you can return.

The idea behind this task is to use independent threads to solve a problem. You are to program the logic that a child or an adult would follow if that person were in this situation. For example, it is reasonable to allow a person to see how many children or adults are on the same island they are on. A person could see whether the boat is at their island. A person can know which island they are on. All of this information may be stored with each individual thread or in shared variables. So a counter that holds the number of children on Oahu would be allowed, so long as only threads that represent people on Oahu could access it.

What is not allowed is a thread which executes a "top-down" strategy for the simulation. For example, you may not create threads for children and adults, then have a controller thread simply send commands to them through communicators. The threads must act as if they were individuals.

Information which is not possible in the real world is also not allowed. For example, a child on Molokai cannot magically see all of the people on Oahu. That child may remember the number of people that he or she has seen leaving, but the child may not view people on Oahu as if it were there. (Assume that the people do not have any technology other than a boat!)

You will reach a point in your simulation where the adult and child threads believe that everyone is across on Molokai. At this point, you are allowed to do one-way communication from the threads to begin() in order to inform it that the simulation may be over. It may be possible, however, that your adult and child threads are incorrect. Your simulation must handle this case without requiring explicit or implicit communication from begin() to the threads.

Implementation overview

If there are more than one child on Oahu, two children from Oahu will pilot to Molokai, and one will return to Oahu. This process continues until just one child left on Oahu. If there is only one child on Oahu, an adult will pilot to Molokai and a child will bring the boat back to Oahu. This process which is carried to completion eventually in all of the adults and children on Molokai.

Each thread will attempt to acquire the lock (which essentially represents control over the boat). If the thread can perform one of the tasks fitting for the current state of the world, it executes it. Otherwise, it will go to sleep on the condition variable corresponding to its current role and location.

New Variables

Define two variables Oahu and Molokai to represent the two locations.
bostLocation: where is the boat? Oahu or Molokai.
location: each thread has a local variable to keep track of which island the person is currently on. location will be passed as argument of ChildItinerary and AdultItinerary.
cntPassengers: number of passengers, note a adult occupies two seats in my code.
boatLock: a lock to protect actions related to the boat.
waitingOnOahu: condition variable based boatlock, synchronize for people waiting on Oahu
waitingOnMolokai: condition variable based boatlock, synchronize for people waiting on Molokai
waitingOnBoatFull: condition variable based boatlock, synchronize for two children to get on the boat
OahuChildren: number of children on Oahu
OahuAdults: number of adults on Oahu
MolokaiChildren: number of children on Molokai
MolokaiAdults: number of children on Molokai
Communicator: send message between child/adult thread and main thread. When child or adult arrives on Molokai, report main thread the number of persons on Molokai.

Interface

Boat.begin()： should fork off a thread for each child or adult.

Note Your mechanism cannot rely on knowing how many children or adults are present beforehand, although you are free to attempt to determine this among the threads (i.e. you can't pass the values to your threads, but you are free to have each thread increment a shared variable, if you wish).

define thread function(fun) for child and adult threads which invoke ChildItinerary and AdultItinerary. fork child and adult threads listen to threads, receive number of children and adults until the number is equal to total number of people.
Boat.ChildItinerary(location):

acquire boat

if child is on Oahu if boat isn't on Oahu or boat is full or just one child on Oahu waitingOnOahu goes to sleep wake up all the persons on Oahu if only one child left in Oahu, this guy will pilot to Molokai directly if more than one child on Oahu this child gets on boat. if there are two children on boat notify the first guy to row to Molokai via waitingOboatFull.wake() this guy will pilot to Molokai two children arrives on Molokai, set location and boat's place accordingly speak number of people on Molokai to main thread via communicator wake all the people on Molokai this guy will go to sleep via waitingOnMolokai else only one child on boat, wait for next child coming via waitingOnBoatFull else
the child is on Molokai now
wake one child to bring boat back to Oahu the child arrives on Oahu wake up all people on Oahu the child goes to sleep via waitingOnOahu

release the boat lock
Boat.AdultItinerary(location):

acuire boat lock

if this adult is on Oahu if boat is full or more than one child on Oahu or boat is not on Oahu go to sleep via waitingOnOahu
```
  this adult row to Molokai
  speak number of people on Molokai to main thread via communicator
  wake all the people on Molokai
  go to sleep via waitingOnMolokai
```
else if this adult is on Molokai go to sleep via waitingOnMolokai

release boat lock

comment: the code is not beautiful but works anyway.

Test strategy

Tests BoatGrader2.a-BoatGrader2.f: Test boat simulation with various numbers of threads.
Test stresstest: Tests boat simulation with a ton of threads.

Test case

Tests Var1 ~ Var9: Test boat simulation with various numbers of threads.
Var1: just one child
- expected result: OK
- begin(0, 1, b);
Var2: two child
- expected result: OK
- begin(0, 2, b);
Var3: three child
- expected result: OK
- begin(0, 3, b);
Var4: one adult
- expected result: Failed
- begin(1, 0, b);
Var5: one adult, one child
- expected result: Failed
- begin(1, 1, b);
Var6: one adult, two child
- expected result: OK
- begin(1, 2, b);
Var7: one adult, three child
- expected result: OK
- begin(1, 3, b);
Var8: two adult, two child
- expected result: OK
- begin(2, 2, b);
Var9: three adult, two child
- expected result: OK
- begin(3, 2, b);
Test stresstest: Tests boat simulation with a ton of threads.
Var10: lots of adult, two child
- expected result: OK
- begin(10, 2, b);
Var11: lots of adult, lots of child
- expected result: OK
- begin(10, 20, b);
Var12: stress testing
- expected result: OK
- begin(100, 50, b);

===================================================================================================================

Design questions

Question: Why is it fortunate that we did not ask you to implement priority donation for semaphores?

Answer: Currently, each time a thread acquires a lock or calls join(), we know who is currently holding the resource. This allows us to donate priority to this single resource if a higher-priority thread begins waiting on it. With semaphores, this is not possible for initial values greater than 1, because the last thread to successfully "acquire" the semaphore will not necessarily be the one with the lowest priority. The implementation would need to change to keep track of all threads that are actually using the semaphore currently and thus be able to determine which of those has the lowest priority and needs to "receive" a donation.

Question: A student proposes to solve the boats problem by use of a counter, AdultsOnOahu. Since this number isn't known initially, it will be started at zero, and incremented by each adult thread before they do anything else. Is this solution likely to work? Why or why not?

Answer: No, because there is no way of enforcing the fact that everyone will increment it before they do anything else.

===================================================================================================================

Reference

9. CS 162 Nachos Tutorial

www-inst.eecs.berkeley.edu/~cs162/sp12/Nachos/nachos.ppt

10. Another design document for CS162 - Project1

http://cs162-sp09.googlecode.com/svn-history/r182/trunk/proj1/project1.odt

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Note for Project 1

Phase 1: Build a thread system

Index

TASK I: (5%, 5 lines) Join

Implement KThread.join().

TASK II: (5%, 20 lines) condition variable

Implement condition variables directly

TASK III: (10%, 40 lines) Alarm class

Complete the implementation of the Alarm class

TASK IV: (20%, 40 lines) Communicator

Implement the Communicator class with operations

TASK V (35%, 125 lines) priority schedulin

Task VI: (25%, 150 lines) Boat Grader

Design questions

Reference

1. Phase 1: Build a thread system

2. National Taiwan University Of Science And Technology

3. My code

4. Project example

5. Note for Project 1 from Paul Borokhov(lensovet)

6. CS162 - FAQ

7. baugarten's project on Github

8. xzhsh's project on Github

9. CS 162 Nachos Tutorial

10. Another design document for CS162 - Project1

Clone this wiki locally