Nachos Programming Tips (Phase 1)
=================================

o Pay attention to the static methods in KThread. These methods implicitly takes 
the current thread as argument. The operations they perform are on the current 
thread. These include sleep(), yield() ... You can call KThread.sleep() to put 
the calling thread into sleep. You can call KThread.currentThread() to get the 
current KThread.

o KThread.yield() and KThread.sleep()

Both are static methods that suspend the current thread and may cause another 
thread to run. The difference is, yield() puts the current thread into the 
ready queue (and changes its status to statusReady). sleep(), on the other hand,
does not put the current thread onto any queue (note that current thread is not
in the ready queue). It just changes its status to statusBlocked and runs another
thread. It is the responsibility of whoever calls sleep() to save the current
in some places (typically some other queue).


o How to put a thread t into the ready queue?

	t.ready();

o How to create a queue that conforms to the scheduling policy used by the system?

Look at how KThread creates its readyQueue:

	readyQueue = ThreadedKernel.scheduler.newThreadQueue(false);


o What if I need items in the queue ordered, e.g. by priority, time, etc?

TreeSet is a good data structure to use for this purpose. Look at javadoc for 
how to use it and what methods you need to implement.

o How to Use Condition Variable

A condition variable is a synchronization primitive to guarantee the "condition" 
a thread needs to proceed. It works with a lock, to provide mutex for the shared 
resource (e.g. a buffer), and typically a flag that specifies whether the 
"condition" is true. A thread sleeps on the condition variable if the "condition" 
is not true, waiting for other threads, who can change the "condition" state, to 
wake it up. 

Consider the following example. There are two types of threads, A and B, and a 
boolean condition theCondition. A type threads can proceed if theCondition = true 
and B type threads can proceed if theCondition = false. Assume any number of A 
and B can be running and they all try to access a shared data sd. After the 
access, each thread resets the flag.


Initially:

	SharedData sd;
	boolean theCondition = false;
	Lock theLock = new Lock();
	Condition AcanProceed = new Condition(theLock);
	Condition BcanProceed = new Condition(theLock);

	// Note here the same lock is used for both condition variables -- because 
	// there is only one shared resource to protect.

A's code:

	theLock.acquire();

	while (!theCondition) {
		BcanProceed.wake();
		AcanProceed.sleep();     
		// Releases the lock and go to sleep atomically.
		// And we will have the lock when we are waken up.
	}

	// Do something to sd

	......

	// Reset the flag.
	theCondition = false;

	// Wake up B
	BcanProceed.wake();

	lock.release();
	return;

B's code:

	theLock.acquire();

	while (theCondition) {
		AcanProceed.wake();
		BcanProceed.sleep();     
		// Releases the lock and go to sleep atomically.
		// And we will have the lock when we are waken up.
	}

	// Do something to sd

	......

	// Reset the flag.
	theCondition = true;

	// Wake up A	
	AcanProceed.wake();

	lock.release();
	return;

Note: 

   1. Typically you need one condition variable for each condition in your program logic.
   2. You may not need the flag at all times. Sometimes the simple fact that you are 
      waken up by some thread is enough for you to proceed.

o PriorityScheduler

PriorityQueue (actually any ThreadQueue) implements the scheduling of threads waiting for 
accessing any resource, be it the CPU or a lock. There will be a PriorityQueue for each 
resource. At any time most thread is in exactly one queue (waiting for accessing a 
resource). The only exception is the current thread which is not in any queue*. Each 
resource can be held by at most one thread, which we call the owner of that resource. Since 
each resource is associated with one ThreadQueue, the owner of the resource is also called 
the owner of the ThreadQueue that is waiting for this resource.

A thread in a queue waiting for a resource A can hold another resource B thus be the owner 
of ThreadQueue B. And a thread in queue B can also hold yet another resource C thus be the 
owner of ThreadQueue C. This can go on and get arbitrarily deep. Also a thread can hold 
multiple resources (e.g. it can hold multiple locks) and be the owner of multiple 
ThreadQueues. 

The system needs to associate with each thread additional info necessary for priority 
scheduling. This is what ThreadState class is for. It includes the thread, its prioirity, 
etc. You are free to add more fields. A thread's effective priority can be cached in its 
ThreadState. When the threads in a ThreadQueue change, the effective priority of its owner, 
say thread A, may also change and may need to be updated. Since A may be in another 
ThreadQueue which may also have an owner, thread B, this change may cause B's effective 
priority to change as well. This will go on .... So updating effective priority is a 
propagation of these changes.

A ThreadQueue changes when a thread is added to or removed from the queue or one of its 
members acquires another queue. These happen in places such as waitForAccess,  acquire, 
nextThread (Read ThreadQueue.java to see what really happens in this methods). These are 
the places when effective priorities may change. Note in nextThread when a new thread is 
selected to hold the resource, the previous owner does not own this queue anymore and this 
may change its effective priority, which in turn may cause the propagation described above. 
Think about what information you need in PriorityQueue and ThreadState to perform this 
update and remember a thread can own multiple ThreadQueues.

* Strictly speaking this is not true. The idle thread is not in any queue either.