The explanation refers to the following excerpts of labelled code:
ThreadId ThreadCreate( unsigned pc, unsigned stack_size, int priority ) {
...
if( /* context switch appropriate */ ) {
L1: SAVE_REGS();
L2: ContextSwitch();
L3: RESTORE_REGS();
}
...
}
void ContextSwitch () {
L4: SAVE_CONTEXT();
/*
* At this point, it is safe to perform a context switch
* (change the Active thread) as all pertinent state information
* for this thread has been saved on the stack (SAVE_REGS) and
* the thread descriptor (SAVE_CONTEXT).
*/
QueueInsert(Active, ReadyQueue);
L5: Active = QueueDelete( ReadyQueue ) ;
Active->inqueue = NULL ;
/*
* The subroutine return address has now been set to the newly
* selected active thread and the FP (which will become the SP
* on return) has been set to that of the selected thread.
*/
L6: RESTORE_CONTEXT();
/*
* If the active thread has been changed, we will now return
* to a different thread.
*/
L7: return;
}
In ThreadCreate(), the statement at L1 causes all of
the current register windows to be saved onto the stack. This must be
done by the operating system, since the user process does not have
access to the register sets other than the currently active ones.
At L2, the subroutine ContextSwitch() is called. In doing so, the parameters are placed into the out registers of the current register window, and control is passed to ContextSwitch(). The old PC, still pointing to L2 is stored into %o7.
ContextSwitch() first executes a save instruction (not visible in the code, but generated by the compiler), which first shifts the register window and then decrements the stack pointer, effectively allocating more space on the stack. Note that the old stack pointer is now the frame pointer, and that %o7 becomes %i7. ContextSwitch() at L4 then stores the values of the frame pointer in the SP field of the active thread descriptor and the call return address (in %i7) into the PC field of the thread descriptor.
At L5, Active may now be set to point to a new thread. Then, in L6, the frame pointer (%i6) is set to the SP value last stored in the thread descriptor, and %i7 is set to the PC value of the descriptor, before returning. The return at L7 causes a restore instruction to be executed, which shifts the register window back by one set, so all the in registers become out registers again. In particular, this sets the stack pointer to the value of the frame pointer.
The processor then continues executing at the instruction pointed to by %i7+8 (taken before the restore), which happens to be L3. At that point, all the in and local registers of the current register window are loaded back from the stack (see the macro for RESTORE_REGS()). Note, that no out registers are loaded, so any return values are still valid. When ThreadCreate() returns, the register window will move back one set, and the appropriate registers for the calling function will be restored.
A very brief introduction to libraries
A library is a set of compiled functions that can be linked together
with a user's program to provide the desired services. For example,
the math library, libm.a, contains the functions that implement
sin(), exp(), log(), etc. The library does
not contain a main() function, as that is the responsibility of
the user program to provide.
Libraries may be created as either static or dynamic
(also known as shared). For this assignment, we will only
consider static libraries. To create such a library on the SPARC
machines, consisting of the code in files file.c and file2.c, you would
use:
Note that while the generated library file will thus be called
libthreads.a, by UNIX naming conventions, we refer to this
library simply as threads. In the following, when the linker
sees the parameter -lthreads, it knows to search for a library
named libthreads.a. Thus, to link the code from
myprog.c (containing the main() function as well as any
code that is not part of the threads library), with the library, you
would use the following:
Testing
To test your threads library, write a main() function that
calls ThreadsInit(), then creates a thread and yields the
processor to it. This thread should run in an infinite loop,
printing out a message every second to indicate that it is still alive,
and yielding the processor every iteration of the loop in case other
threads are ready. In order to ensure that the thread continues running,
you must prevent main() from terminating. One way to accomplish
this is to sleep for a very long time (see sleep(3)). However,
you can also take advantage of thread priorities to make sure that
main() doesn't get control of the processor unless no other
threads are on the ReadyQueue.
At this point, you should add additional threads to your test program.
Try creating children threads within threads, and also figure out a way to
create multiple threads from the main() function.
Once you have done so, create a special idle thread
that will always be available to run (at a low priority).
Sample code for this thread is given below:
Scheduler
Once you have written and tested the threads library, implement a
simple priority scheduler that uses internal priority computation (see
the text, pp. 172-174) to prevent starvation. Your scheduler should
give all of the ready threads a chance to run, but pays more attention
to threads with a higher external (user assigned) priority. To
take advantage of the scheduler, the user program must call a threads
library function, ThreadsUseScheduler() after the call
to ThreadsInit(). From that point on, any call to
ThreadYield() will select the next ready thread according to
the scheduler policy. You may wish to add additional fields to the
thread descriptor data structure in order to maintain timing
information (see gettimeofday(2)) and internal priority. Note
that your scheduler will still be non-preemptive, so every thread must
call ThreadYield() at some point to relinquish the processor.
Test your scheduler with various combinations of threads requiring
light and heavy processor usage. Use the sleep(3)
call to simulate extended thread execution. Does your scheduler
adequately penalize CPU hogs? How long does it take to reach a steady
state given a static pool of threads with a fixed distribution of
processor requirements? Illustrate this by reproducing the
CPU utilization of each thread in a graphical format.
Submitting your assignment
You must submit a hardcopy consisting of the following:
In addition to the hardcopy submission, you must provide an electronic
version of your assignment in UNIX tar(8) format, encoded with
uuencode(1). The electronic submission will be compiled and
tested automatically on the Sparc systems in the ECE undergraduate lab.
The electronic submission must contain:
Your message must be sent by October 29, 16:00. Assignments will
not be considered complete if they have not been submitted both in
hardcopy and electronically or if the two versions of the source code
differ. Incomplete submissions will not be marked. The hardcopy and
electronic versions may be submitted at different times within the
assigned deadline.
In order to allow for automatic processing, your submission message
must be formatted as specified in the following paragraphs. An
unproperly formatted message will be automatically bounced back to the
sender and the submission will not be considered complete. You may
then correct the errors and resubmit. However, you may
not resubmit after a properly formatted message has
been accepted: please make sure that your files contain exactly what
you wish to submit.
The "Subject:" field of your email message must have the following format:
427-A2-YOUR_STUDENT_ID, with the digits of your student ID number in
place of YOUR_STUDENT_ID; do not write anything else in the subject; do
not write anything in the message other than the tar file.
The tar file must create, when opened, a directory named with your
student ID, containing all the source files (there may be
subdirectories, if needed) and the Makefile as described above. An
optional file named README may be included, containing instructions for
the correct compilation and use of the library. Do not include any
non-text files (e.g. compiled executables, relocatable objects), since
they may be handled improperly by the email software, causing
corruption of the entire tar file. Make sure that all files are in
UNIX text format (lines terminated by a line-feed character, ASCII 10):
use a converter if you edit them on a PC under MS-DOS/Windows.
An example sequence of UNIX shell commands that creates and sends a tar
file as specified follows [comments in square brackets]:
If the submission is correct, you will receive an automatic acknowledgement
in reply. Otherwise, the message will be refused, and an explanatory
error message will be sent to you.
gcc -c file1.c file2.c
ar -rcv libname.a file1.o file2.o
where name is the name of your library, in this case, threads.
gcc -c myprog.c
gcc myprog.o -L. -lthreads -o myprog
The -L. tells the linker to look in the current directory for
any libraries you specify, in this case, libthreads.a.
/*
* A sample (and simple) idle thread. The code loops forever,
* printing information about the list of allocated threads.
* In a real system, Idle would look more like:
* void Idle() { while (1) ThreadYield(); }
*/
void Idle() {
Queue *queue;
int i;
while( 1 ) {
printf( "CPU is idle\n" );
for( i = 0; i < MAX_THREAD; ++i ) {
queue = TDArray[i].inqueue;
if( queue != FreeTDs ) {
printf( "id = %d, ", TDArray[i].id );
printf( "pri = %d, ", TDArray[i].priority );
if( queue == NULL ) printf( "ACTIVE\n");
else if (queue == ReadyQueue) printf("READY\n");
else printf( "BLOCKED\n");
}
}
(void) sleep( (unsigned) 1 );
ThreadYield() ;
}
}
Style note:
Since Idle() examines the thread queues and details
of the thread descriptor, you may prefer to include this function in
the library code. That way, you do not have to expose the
implementation details of the thread data structure to the user
program.
The report should keep to a maximum of six pages, excluding test
results and graphs; anything beyond the six-page limit will
not be read.
Avoid discussion of the helper code that was provided to you.
Flowcharts of any sort are absolutely verboten.
by sending an email message to the instructor.
[Create the source directory for student with id 952334.]
% mkdir ./952334
[Copy all the sources in it.]
% cp foo.c bar.c baz.c flop.c README ./952334
[Create the tar file with the directory content.]
% tar cvf 427-A2-952334.tar ./952334
[Uuencode the tar file]
% uuencode 427-A2-952334.tar 427-A2-952334.tar > 427-A2-952334.tar.uu
[Send it with the proper subject field.]
% mail -s "427-A2-952334"
< 427-A2-952334.tar.uu