P536 Discussion Week 3

Ying Feng, Sep. 14, 2000

Note: Please bring a hardcopy of Nachos source code to every discussion session.

Nachos Threads

• In Nachos (and many systems) a process consists of:
• An address space. The address space includes all the memory the process is allowed to reference:
• Executable code (e.g., the program's instructions)
• Stack space for local variables
• Heap space for global variables and dynamically allocated memory
• A single thread of control - the main thread of the process. In multi-threaded process, you will need a list to keep the threads belonging to that process.
• Other objects, such as open file descriptors.

• Nachos provides threads.
• Threads within the same nachos process share the same address space: they execute and share the same code (the Nachos source code, although each thread can execute its own code segment as well) and share the same global variables; but each thread has its own private stack (don't confuse this with the process's stack).
• Nachos starts as a single Unix process ->  single Nachos thread (the main thread for Nachos) -> fork more Nachos (kernal) threads or create user process -> main terminates after all threads finishes.
• Ready List: The Nachos scheduler maintains a data structure called  ready list, which keeps track of the threads that are ready to execute.

• Thread state - describing what the thread is currently doing:
• READY: The thread is eligible to use the CPU (e.g, it's on the ready list), but another thread happens to be running.
• RUNNING: The thread is currently running. Only one thread can be in the RUNNING state at a time; the global variable currentThread always points to the currently running thread.
• BLOCKED: The thread is blocked waiting for some external event; it cannot execute until that event takes place (e.g. a thread puts itself to sleep via Thread::Sleep()). A blocked thread does not reside on the ready list.
• JUST_CREATED: The thread exists, but has no stack yet. This state is a temporary state used during thread creation. The Thread constructor creates a thread, whereas Thread::Fork() actually turns the thread into one that the CPU can execute (by placing it on the ready list).

• Thread objects in Nachos:
• Thread's context block - information associated with thread, is maintained as private data of a Thread object instance.
• Status (READY, BLOCKED etc)
• Machine states (PC, register values)
• Stack pointer (points to its private stack)
• Where do we put a thread's context block? Where do we put a thread's stack? Hint: think about the heap in the process's address space.

Thread Operations

• Thread *Thread(char *threadName): Thread constructor, does only minimal initialization.
• The thread's status is set to JUST_CREATED.
• Its stack is initialized to NULL.
• It's given the name threadName.
• Its address space is set to NULL.

• Fork(VoidFunctionPtr func, int arg): Thread creation, turning a thread into one that the CPU can schedule and execute.
• Argument func is the address of a procedure where execution is to begin when the thread starts executing.
• Argument arg is an argument that should be passed to the new thread.
• Fork allocates stack space for the new thread, initializes the registers by saving the initial value's in the thread's context block, etc.

• void StackAllocate(VoidFunctionPtr func, int arg): Allocating the stack and creating an initial activation record that causes execution to appear to begin in func.
• Allocate memory for the stack.
• Place a sentinel value at the top of the allocated stack. Whenever it switches to a new thread, the scheduler verifies that the sentinel value of the thread being switched out has not changed, as might happen if a thread overflows its stack during execution.
• Initialize the program counter PC to point to the routine ThreadRoot (in switch.s), where execution at the user-supplied routine, execution actually begins in routine ThreadRoot:
• Calls an initialization routine that simply enables interrupts.
• Calls the user-supplied function, passing it the supplied argument.
• Calls thread::Finish(), to terminate the thread.
• Why do we need ThreadRoot? Hint: think about how we can return after executing func.

• void Yield():
• Suspend the calling thread and select a new one for execution (by calling Scheduler::FindNextToRun()).
• If no other threads are ready to execute, continue running the current thread.

• void Sleep(): Called when the current thread needs to be blocked until some future event takes place.
• Suspend the current thread, change its state to BLOCKED, and remove it from the ready list.
• If the ready list is empty, invoke interrupt->Idle() to wait for the next interrupt.

• void Finish():
• Terminate the currently running thread. In particular, return such data structures as the stack to the system, etc.
• How can we free the stack while the thread is still using it? (Hint: set it to threadToBeDestroyed and let another thread to terminate it.)

Exercise

Show the contents of memory when execution reaches the point labeled L1. More precisely, draw a memory map showing the contents of the process stack and heap.  Your memory map should look something like the memory maps drawn in lecture.  As in lecture, write the values of global variables off to the side of your memory map.  You should show the value of currentThread and the contents of the ready list; you do not need to show values of other global variables.  Assume the Nachos implementation of threads and scheduling is being used.  Don't forget to indicate the return address stored in each stack frame.  Don't forget to include stack frames for Yield, Run, etc., if appropriate.

The heap will contain the stacks of forked threads and objects allocated with "new".  Note that Thread::StackAllocate allocates those stacks by calling AllocBoundedArray.  As in lecture, you can ignore the details of AllocBoundedArray; just assume AllocBoundedArray returns a chunk of memory on the heap that is used as a stack. When showing the contents of a Thread object, it suffices to indicate the stored values of the program counter, stack pointer, and frame pointer.

For convenience, you do not need to show any of the values in the stack frame for the main function (defined in threads/main.cc), which calls ThreadTest.  Also, you do not need to indicate a specific value for the return address in the stack frame for the new ThreadTest function (just write "somewhere in main").

   void f(int j)
   {
     (*(int *)j) += 2;
     currentThread->Yield();
     (*(int *)j) += 4;
   }

   int ThreadTest()
   {
     int i = 0;
 
     Thread t1 = new Thread("one");
     // casting pointers to integers is gross, but unfortunately, that's
     // how Nachos is set up.
     t1->Fork(f1, (int)&i);
     currentThread->Yield();
     i += 8;
     // L1
     currentThread->Yield();
   }

Comments on ThreadRoot:

To prevent your getting bogged down in details of StackAllocate (in thread.cc) and ThreadRoot (in switch.s), I recommend that you simply trust the relevant comments in thread.cc, namely:
  // Thread::StackAllocate
  //    Allocate and initialize an execution stack.  The stack is
  //    initialized with an initial stack frame for ThreadRoot, which:
  //            enables interrupts
  //            calls (*func)(arg)
  //            calls Thread::Finish
  //
  //    "func" is the procedure to be forked
  //    "arg" is the parameter to be passed to the procedure
This suggests that each newly-allocated stack contains a stack frame containing the values of "func" and "arg" (and the return address).

Nitty-Gritty Details for the Curious: If you look at the code for StackAllocate (specifically, the SPARC version) in thread.cc, you can see that the newly-allocated stack really contains an *empty* stack frame, and that the values of "func" and "arg" are stored in registers in machineState.  This just reflects an optimization used for all procedure calls on the SPARC (and many other RISC processors): arguments to functions (and the return address) are passed in registers whenever possible, since that's more efficient than storing the arguments on the stack. Thus, the stack frame for any procedure call (not just ThreadRoot) contains only the arguments that didn't fit in registers. We have just seen that in the case of ThreadRoot, all of the arguments fit in registers, so the stack frame is empty.  In general, though, I don't expect anyone to figure out which arguments fit in registers and which don't.  So, I suggest that for all procedure calls (including calls to ThreadRoot), you pretend that all arguments are passed on the stack.

Comments on SWITCH:

You can pretend that calls to SWITCH do not cause a new frame to be allocated on the stack.  I say "you can pretend..." because, in the SPARC implementation of Nachos, calls to SWITCH do allocate a stack frame.  However, this is not essential; SWITCH could be implemented in a way that is safe to inline, and inlined function calls don't create stack frames.

The purpose of this pretense is to prevent you from getting bogged down in the assembler code in switch.s, which contains the details of how the stack frame for SWITCH is allocated and de-allocated.  In particular, it is not obvious (without reading that code, or perhaps even after reading it!) whether the stack frame for SWITCH is de-allocated before the context-switch, or when the yielding thread resumes.