ECE344S -- Assignment 4

ECE344 - Operating Systems

Assignment 4: User-level Threads and Context Switching

Due Date: Sunday, March 11, 2001, 11:59:59pm.

Objectives

The objective of this assignment is to fully understand what a context switch really is.

Procedure

You are to implement a user-level threads package called Pumbaa according to the specifications provided below. Some of the low-level code will be made available to you, but you need to make sure you fully understand that code before using it.

Specification

For this assignment, the following structures will be needed:

   typedef int ThreadId;

   struct TD
   {
       struct TD *link;
       ThreadId tid;
       struct Registers regs;
       int priority;
       LL *inlist;
   };

   struct Registers
   {
       unsigned pc;
       unsigned sp;
   };

Also, you will require the following definitions:

   #define OK 0
   #define ERROR -1
   #define PRIORITYERROR -2
   #define STACKERROR -3
   #define NOT_BLOCKED -4

The TD structure should seem familiar -- it is very similar to the PD structure of assignment #1. You should make all the functions for assignment #1 available for this TD structure, i.e. getPid() becomes getTid(), have a CreateList() function, etc. The various fields in TD have the following meanings: link is used to point to the next TD in whatever queue the TD is in, tid is a unique number that can be used to identify a thread once it has been created; regs is a structure used for saving CPU registers when the state of the thread needs to be saved; priority holds the current priority of the thread -- by convention in systems software (particularly for Unix), the higher the number in priority the lower the priority (importance) of the thread; and inlist identifies the queue that the thread is currently in.

You should create two new functions that operate on TDs:

void PrintList(struct LL *list): This function should print the numeric value of its type (i.e. L_PRIORITY would be printed as 1), a space, then call PrintTD() for each member of the list in order, seperated by space. An newline character should be printed at the end.

void PrintTD(struct TD *td): Prints a TD. Use the following code.

   {
       printf("(%d, %u, %u, %d)", td->tid, td->regs->pc, td->regs->sp, 
                                  td->priority);
   }

For example a priority list with 2 elements in it would be printed as

   1 (4, 66666, 777777, 30)(6, 88888, 99999, 20)

You will need three queues for now: ReadyQueue, BlockedQueue and FreeTDs.

You should allocate a fixed size array of TDs, instead of using malloc() to allocate space for the TDs at run time (why will be explained in the next Assignment). For now, make the size of the array equal to 32 elements, meaning that there can be a maximum of 32 threads in existence at one time.

When a new thread is created, it should be assigned a unique integer identifier, stored in the tid field of the TD. Make sure that you do not re-use tids for as long as possible (why is this important, and why not just use numbers from 1 - 32 ? -- think in the context of a real multitasking OS like UNIX).

You will need to provide for the following functions that an application might want to call:

int U_CreateThread( unsigned pc, unsigned stackSize, int priority )

Creates a new Thread that should start executing the procedure pointed to by pc.

Creating a new thread should be done by first allocating a stack (using malloc() with a minimum size of 8K), and then allocating a new thread descriptor, initializing its fields and enqueueing it in the ReadyQueue. If the new thread has higher priority than the invoking thread then the invoking thread should yield the processor to the new thread. U_CreateThread() should return the tid of the new thread, ERROR of there are no thread descriptors available, STACKERROR if stackSize is not at least 8K large, and PRIORITYERROR if priority is not in the range of valid priorities.

int U_DestroyThread( ThreadId tid )

Destroys the thread identified by tid. If tid is 0 or the same as that of the invoking thread, then the invoking thread should be destroyed.

This can be achieved by removing the thread descriptor from whatever queue it is in and adding it to the list of free descriptors. If the Active thread is to be killed, then a new thread should be dispatched. Return ERROR if there is no thread corresponding to tid, or OK otherwise.

int U_Yield()

The invoking thread should yield the processor to the highest priority ready-to-run thread with equal or higher priority.

This is achieved by enqueueing the Active thread onto the ReadyQueue behind all threads of the same, or higher, priority (remember that the higher a thread's priority number, the lower its priority), and dispatching the ready-to-run thread with the highest priority (which happens to be at the head of the ReadyQueue). U_Yield() should return OK.

int U_BlockMyself()

The invoking thread should block until it is woken up again.

This can be achieved by enqueueing the Active thread onto BlockedQueue, and dispatching the ready-to-run thread with the highest priority. U_BlockMyself() should return OK.

int U_WakeupThread( ThreadId tid )

Wakes up the thread identified by tid and makes it ready to run.

If that thread has higher priority than the invoking thread then the invoking thread should yield the processor. U_WakeupThread() should return ERROR if there is no thread with id tid, NOT_BLOCKED if the target thread is not blocked, and OK otherwise.

int U_ChangeThreadPriority( ThreadId tid, int newPriority )

Changes the priority of the target thread identified by tid to newPriority

This can be achieved by setting the priority field of the thread descriptor to newPriority. If the corresponding TD is in the ReadyQueue, then remove and re-insert it, so that the ReadyQueue remains sorted according to priority. If the target thread now has higher priority than the invoking thread then the invoking thread should yield the processor to the target thread. U_ChangeThreadPriority() should return ERROR if there is no thread with Id tid, PRIORITYERROR if newPriority is not valid, and OK otherwise.

The code for U_CreateThread() is given and described below. Although the variable, type and structure names may be different than what you would use, you should be able to understand this code. You will write similar code for the other functions, using the code for CreateThread() as a template. However, it is important that you understand the CreateThread() code before you begin. The code below is presented in a bottom-up fashion:

   #define STACK_ADJUST 200*4    /* needed for Sparc, err on the large size ;-) */

   #define SAVE_REGS() \
      asm( "ta 3" );

   #define RESTORE_REGS() \
      asm( "ld [%sp+0],%l0" ); \
      asm( "ld [%sp+4],%l1" ); \
      asm( "ld [%sp+8],%l2" ); \
      asm( "ld [%sp+12],%l3" ); \
      asm( "ld [%sp+16],%l4" ); \
      asm( "ld [%sp+20],%l5" ); \
      asm( "ld [%sp+24],%l6" ); \
      asm( "ld [%sp+28],%l7" ); \
      asm( "ld [%sp+32],%i0" ); \
      asm( "ld [%sp+36],%i1" ); \
      asm( "ld [%sp+40],%i2" ); \
      asm( "ld [%sp+44],%i3" ); \
      asm( "ld [%sp+48],%i4" ); \
      asm( "ld [%sp+52],%i5" ); \
      asm( "ld [%sp+56],%i6" ); \
      asm( "ld [%sp+60],%i7" );

The macro SAVE_REGS() saves all of the registers on the threads stack, and RESTORE_REGS() restores them back to the registers. Here, "asm" is a special gcc contsruct for generating assembly language; for example, asm("ld [%sp+60],%i7"); generates the assembly statement ld [%sp+60],%i7.

SAVE_CONTEXT() is a macro that saves the program counter and stack pointer of the invoking procedure in the Active thread descriptor. Similarly, the macro RESTORE_CONTEXT() loads the program counter and stack pointer from the Active thread descriptor into the appropriate registers. If you really want to understand the details of this, see the tutorial Context Switches on the Sparc Processor.

   #define SAVE_CONTEXT() \
      asm("st %%fp,%0" : "=m"(Active->regs.sp)); /* save sp */ \
      asm("st %%i7,%0" : "=m"(Active->regs.pc)); /* save pc */

   #define RESTORE_CONTEXT() \
      asm("ld %0,%%fp"::"m"(Active->regs.sp)); /* restore sp */ \
      asm("ld %0,%%i7"::"m"(Active->regs.pc)); /* restore pc */

The CreateThread() function is partitioned into two levels in anticipation of a future assignment and taking into account that the function is partially implemented at the user-level and partly at the kernel-level, called here "low-level". The two parts are U_CreateThread() and L_CreateThread(). The function U_CreateThread() first allocates a stack, then saves all the processor registers on the invoking thread's stack (not the stack just allocated) and calls the low-level function L_CreateThread().

   ThreadId
   U_CreateThread( unsigned pc, unsigned stackSize, int priority )
   {
      void *stack;
      unsigned response;

      /* ensure priority is valid and return error if not */
      /* ensure stackSize is larger than 8K and return error if not */

      /* 1: create a stack */
      stack = (void *) malloc( stackSize );
      stack += stackSize;      /* stack pointer initially at end of stack */
      stack -= STACK_ADJUST;
      /* make sure stack is on a word boundary---how? */

      SAVE_REGS();
      L_CreateThread( pc, stack, priority, &response );
      RESTORE_REGS();

      return (ThreadId) response;
   }

   void
   L_CreateThread( unsigned pc, void * sp, int priority, unsigned *result )
   /* Creates a new thread with ID NextTid.
    * Snags TD from FreeTDs.
    * TD is initialized and then placed on ReadyQueue.
    * Returns NextTid if successful, ERROR if there are no free TDs. */
   {
      TD *td;

      SAVE_CONTEXT();

      /* 2: allocate a TD from the freelist */

      if( ( td = DequeueHead( FreeTDs ) ) == NULL )
      {
         *result = ERROR; 
         return; 
      }

      /* 3: initialize the TD */
      /* NOTE: in code below, use pc-8 as indicated---it has to do
       * with the way the SPARC works */
      InitTD( td, pc-8, sp, priority, NextTid );
      *result = NextTid;
      /* should probably trap the error code returned by the following call */
      (void) PriorityEnqueue( td, ReadyQueue );
         

      /* 4: allocate the tid */
      NextTid++;

      /* 5: check to see whether we need to context switch */
      if( priority < Active->priority )
      {
         (void) PriorityEnqueue( Active, ReadyQueue );
         Active = DequeueHead( ReadyQueue );
         Active->inlist = NULL;
      }

      RESTORE_CONTEXT();
      return;
   }

The first statement in L_CreateThread() should be SAVE_CONTEXT(), which is a macro that saves the program counter and stack pointer of the invoking procedure in the Active thread descriptor. (The saved program counter and stack pointer are re-loaded upon exit from the current sub-routine.) Similarly, the macro RESTORE_CONTEXT() loads the program counter and stack pointer from the Active thread descriptor into the appropriate registers. Note that L_CreateThread() may change Active, so the program counter and stack pointer loaded may differ from those stored earlier in L_CreateThread(). This is what effectively implements the context switch. It is necessary that you fully understand what exactly is going on here.

It is only necessary to save and restore registers and contexts if there is a possibility that a context switch may happen. All of the functions that you will implement, U_CreateThread(), U_DestroyThread(), U_Yield(), U_BlockMyself(), U_WakeupThread(), and U_ChangeThreadPriority() may cause a context switch to occur.

In addition to the above code, you require some support routines. In particular, the code below is used to initialize Pumbaa:

   void Pumbaa_Init()
   {
      void * stack;
      struct TD td;

      printf( "initializing Pumbaa\n" );

      /* Initialize all your data structures here. */
      /* In particular, put all the thread descriptors into FreeTDs. */

      /* Then we have to allocate and initialize a thread descriptor
       * for the thread currently running, namely main().
       */
      td = DequeueHead( FreeTDs );
      InitTD( td, 0, 0, 243, NextTid ); /* note: pc and sp are set later
                                      when main() releases the processor */
      Active = td;                /* this is the currently Active thread */
      Active->inlist = NULL;           /* so we must set Active properly */
      NextTid++;

      /* Finally, create a new thread for an idle process. */
      stack = (void *) malloc( 2048*4 );
      stack += (2048*4);
      stack -= STACK_ADJUST;
      L_CreateThread( (unsigned) idle, stack, MAX_PRIORITY, &response );
   }

The idle process can be defined as follows. You should feel free to modify this in any way you would like. In the following code, idle prints out a list of thread IDs every second. In a real system, idle would do nothing but yield the processor in a tight loop.

 
   void idle()
   {
      int i;
      while( 1 )
      {
         printf( "CPU is idle\n" );
         for( i = 0; i < MAXTHREADS; ++i )
         {
            /* The definition of getQueue() is left as an exercise to
             * the student.
             */
            if( getQueue( &TDArray[i] ) != FreeTDs )
            {
               printf( "tid = %d, ", getTid( &TDArray[i]) );
               printf( "pri = %d, ", getPriority( &TDArray[i] ) );
               if( getQueue( &TDArray[i] ) == NULL )
                  printf( "Active\n");
               else if( getQueue( &TDArray[i] ) == ReadyQueue )
                  printf( "READY\n");
               else if( getQueue( &TDArray[i] ) == BlockedQueue )
                  printf( "BLOCKED\n");
               else
                  printf( "OTHER\n");
            }
         }
         (void) sleep( (unsigned) 1 ); /* just for giggles */
         U_Yield();
      }
   }

And finally, here is some simple code that you can use to test your routines.

 
   void proc2()
   {
      while( 1 )
      {
         /* Pretend doing something for a while */
         printf( "I am the child\n" );
         (void) sleep( (unsigned) 1 ); /* so things go slow */
         U_Yield() ;  /* give a chance to another proc */
      }
   }

   void proc1()
   {
      ThreadId child;

      if ((child = U_CreateThread( (unsigned) proc2, 2048*4, 150)) < 0)
         printf( "proc1: cannot create proc2 - reason %d\n", child);

      while( 1 )
      {
         /* Pretend doing something for a while */
         printf( "I am the father\n" );
        (void) sleep( (unsigned) 1 );

        U_Yield();   /* give a chance to another proc */
      }
   }


   void main(int argc, char *argv[])
   {
      ThreadId tid; /* tid of child */

      Pumbaa_Init() ;
      /* at this point I am now the Active thread */

      tid = U_CreateThread( (unsigned) proc1, 2048*4, 150);
      U_Yield();

      /* should never get here - if it does it is because idle died ! */
      printf( "Oh No! Idle must be dead!\n" );
      exit( 1 );
   }

Play around with the priorities of the two threads and study the behavior of the program.

Submission instructions

In your home directory, create a directory called ece344; create a subdirectory called as4 and then in that directory create files with your code. You should only submit source files. To submit the assignment you should use the submission procedure described in the policies section.

The main function must be in a file by itself called main.c. You must also write a header file called pumbaa.h that exports all the symbols that should be available to the user of your package. To mark this assignment we will be running your code using our own main function (which will #include your pumbaa.h).

The names and organization of the other files are up to you, but you must have a functioning Makefile that produces an executable called pumbaa as the default target. If your code does not compile using your Makefile and our main.c you will lose a substantial part of the assignment mark. The specifications for the functions in the assignment handout must be followed exactly. Do not change the case of any letters, the number or type of arguments, or any of the typedefs, enums or structs defined in the handout.