Computer Science/162/proj1 - Revision history

Lensovet: Lensovet moved page CS/162/proj1 to Computer Science/162/proj1

2023-02-20T03:51:34Z

Lensovet moved page CS/162/proj1 to Computer Science/162/proj1

Lensovet: /* Design questions */ no. 1

2008-10-05T06:49:54Z

‎Design questions: no. 1

Lensovet: /* Pseudocode */ minor fix

2008-10-05T06:47:22Z

‎Pseudocode: minor fix

Lensovet: /* Implementation */

2008-10-05T06:45:29Z

‎Implementation

Lensovet: /* Priority Scheduler */ formatting

2008-10-05T06:44:48Z

‎Priority Scheduler: formatting

Show changes

Lensovet: /* Pseudocode */ rm cr

2008-10-05T06:29:01Z

‎Pseudocode: rm cr

Lensovet: /* WaitUntil() */ formatting

2008-10-05T06:28:37Z

‎WaitUntil(): formatting

24.130.25.237: /* Implementation */

2008-10-05T06:14:09Z

‎Implementation

75.62.110.89: /* Implementation */

2008-10-05T05:20:12Z

‎Implementation

75.62.110.89: /* Testing */

2008-10-05T05:14:36Z

‎Testing

@@ Line 376: / Line 376: @@
 ==Design questions==
 ;Why is it fortunate that we did not ask you to implement priority donation for semaphores?
-:Be damned if I know. Anyone?
+:Currently, each time a thread acquires a lock or calls {{c|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.
 ;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?
 :No, because there is no way of enforcing the fact that everyone will increment it before they do anything else.

@@ Line 159: / Line 159: @@
                  Wake a waiting listener;
+             }
-             Sleep as an active speaker;
+             Sleep as waiting to return;
              AS--;
              AL--;
@@ Line 188: / Line 188: @@
                  Wake a waiting speaker;
+             }
-             Sleep as an active listener;
+             Sleep as waiting to return;
              AL--;
              AS--;

@@ Line 338: / Line 338: @@
 In addition, each thread has a local variable to keep track of which island the person is currently on.
-;Basic idea
+;Implementation overview
 If there are no children on Molokai or if there are no adults left on Oahu, two children from Oahu will pilot over and one will return to Molokai. If there is a child on Molokai, an adult will pilot over to Molokai and the child will bring the boat back to Oahu. This process, carried to completion eventually results 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.
-;Algorithm details
+;Implementation details
 Each child will begin running on Oahu and try to acquire the lock.

@@ Line 100: / Line 100: @@
      Re-enable interrupts;
 }</pre>}}
 {{c|<pre>timerInterrupt(){

@@ Line 79: / Line 79: @@
 }</pre>}}
-==WaitUntil()==
+=={{c|waitUntil()}}==
 ===Implementation===
 ;New state variables
-Alarm has a new instance variable, waitingThreads, which is a Java PriorityQueue of waiting threads with the target wake time as their priority. It also contains a new inner class named waitingThread, which contains a reference to a KThread and its associated wakeTime. The PriorityQueue waitingThreads will be populated with instances of this inner class.
+Alarm has a new instance variable, {{c|waitingThreads}}, which is a Java {{c|PriorityQueue}} of waiting threads with the target wake time as their priority. It also contains a new inner class named {{c|WaitingThread}}, which contains a reference to a {{c|KThread}} and its associated {{c|wakeTime}}. The {{c|PriorityQueue waitingThreads}} will be populated with instances of this inner class.
 ;Implementation details
-* waitUntil() creates a new instance of waitingThread, which will associate the currentThread with the give time argument. It will then add this waitingThread instance to the PriorityQueue and put the current thread to sleep.  This method is atomic.
+* {{c|waitUntil()}} creates a new instance of {{c|waitingThread}}, which will associate the current thread with the given time argument. It will then add this {{c|waitingThread}} instance to the {{c|PriorityQueue}} and put the current thread to sleep.  This method is atomic.
-* timerInterrupt() peek at the first WaitingThread in the waitQueue and check if its associated wake time is less than or equal to the current time.  If it is, this method will pop the WaitingThread off the waitQueue and wake the associated thread.  This process is repeated until the wake time of the first WaitingThread is greater than the current time.
+* {{c|timerInterrupt()}} peeks at the first {{c|WaitingThread}} in the {{c|waitQueue}} and checks if its associated wake time is less than or equal to the current time.  If it is, this method will pop the {{c|WaitingThread}} off the {{c|waitQueue}} and wake the associated thread.  This process is repeated until the wake time of the first {{c|WaitingThread}} is greater than the current time.
 ===Testing===
-* Have the timer interrupt print a debug statement, and have timed threads print the times they go to sleep and when they have woken up. Verify that they wake up relatively close to their expected exit time.
+* Have the timer interrupt print a debug statement, and have timed threads print the times they go to sleep and when they have woken up. Verify that they wake up relatively close to their expected wake time.
 * Make sure threads called with illegal times return immediately. Test threads that go to sleep chronologically in order (1, 500, 1050) as well as threads that go to sleep with the same times (50, 50) and threads that go to sleep in reverse order (500, 250). Verify they all wake up when they are supposed to.

← Older revision	Revision as of 03:51, 20 February 2023
(No difference)

@@ Line 204: / Line 204: @@
 ==Priority Scheduler==
 ===Implementation===
 ;New state variables
 *'''PriorityQueue''' – {{c|ThreadState holder, ArrayList<ThreadState> waitQueue, int effective, boolean dirty}}<br />

@@ Line 240: / Line 240: @@
 * Instantiate new threads and set their priorities in decreasing order. Have the threads state their priorities as they execute and verify that they were run in decreasing order according to their priorities.
 * Verify donation works by creating a high priority thread and joining it to a low priority thread with a high priority thread already queued.
 ===Pseudocode===