Exercise 5: Extending our User Level Thread Library

Subject: Extending User-Level Threads.

Due Date: 16/02/03

This exercise is not very difficult, but you will do yourself a favor if you start early.

This exercise is optional. You are not required to do it, if you feel that your grade will be sufficiently high even without it.

In this exercise you will extend the basic user thread library developed in Exercise 2. The extension is in the following two dimensions.

• Support for the basic syncronization primitives: you implement counting semaphores.
• Support for preemptive scheduling: you implement a Linux-like scheduling algorithm.

As usual, the package is delivered in form of a static library. The public interface of your library is given by uthreads.h. Needless to say, that you are required to study it thoroughly, and that you are not allowed to make any changes to it.

There may be a number of internal functions, and data structures that you might find necessary to implement. These functions are not visible outside the library, and, therefore, you are not restricted in their number, signatures, and content. The same goes for the private data structures of the library.

Please, note the following. When you write a library, you cannot assume that the user will always use the library correctly. The order in which the functions are called matters. You can infer the correct order from carefully reading the comments inside uthreads.h. If you allow, for instance, to use some function from the library before you initialized the library, and your library does not fail, and, moreover, operates correctly - that is a problem. The problem is that you do not follow the required behavior. However, this is a mild problem. If the program fails with SIGSEGV as a result of an unchecked NULL pointer reference, this is a big problem, and you will lost much more points.

The goals of this exercise include:

1. Understand the issues involved with implementation of synchronization primitives;
2. Understand preemptive scheduling algorithms;
3. Understand the implementation issues involved with preemptive scheduling;
4. Understand the race condidions due to asynchronous signal processing.

1. Carefully read the man pages on setsigmask/getsigmask/kill/sleep/signal system calls.
2. Read in the book / notes / slides the sections that deal with: CPU Scheduling, threads, Linux schedulingetc.
3. Carefully read the attached Demo code with rudimentary preemptive scheduling.
4. Chapter 10 in the "Advanced Programming in the Unix Environment", by R. Stevens that discusses signalling.

Synchronization Primitives

• int uthreads_semcreate(int value) : creates a semaphore structure that is internal to your library implementation, and initializes the sempahore count of the newly created semaphore to be the value of the argument. The correctness of the argument is the responsibility of the library user. This function returns -1 in case of any failure. Otherwise, this function returns a non-negative semaphore id that serves as an argument to the subsequent semaphore-related functions. The semantics of the counter value is as usual.
  • If grater than zero, than this is the number of threads that can perform the wait() operation without blocking.
  • As long as it is either zero, or less, all threads that attempt wait() operation block. The absolute value of the semaphore counter when it is negative, is the number of threads being blocked in their wait() operation.
• int uthreads_semwait(int semid) : wait() operation of the semaphore. This function receives the semaphore id as an argument. A valid semaphore id can only be obtained through a previous call to uthreads_semcreate(). If a user specifies an invalid semid, the function should return -1. Otherwise, if the operation can be completed without blocking, the function returns immediately with 0.
• int uthreads_semsignal(int semid) : signal() operation of the semaphore. This operation never blocks. In case of invalid semid, this function returns -1. Otherwise it return 0.

If a thread cannot complete its semwait() operation, and the operation blocks, the thread should not be among the READY threads. In other words, it should not be a part of scheduling now, because it cannot continue running anyway. The thread will get back to the READY state queue only when this operation can be completed without blocking. When a thread blocks on a semaphore, it enters the BLOCKED state.

You are required to implement the FIFO order of the threads waiting on the same semaphore. This means that when there is a possibility to complete the semwait() operation, the thread that waits the most time on the semaphore will complete semwait(). Thus, the semaphore implementation would be fair.

Needless to say that you should assign the errno variable in your library accordingly, so that uthreads_perror() can be used as before in ex2

Interface Extensions

• int uthreads_suspend(int tid) : suspends the execution of the thread with the thread id specified as an argument. In case of any failure (e.g., invalid tid, tid of a thread that was not started yet etc), this function returns -1. Otherwise this function returns the tid of the thread that is being suspended. The suspended thread enters the special SUSPENDED state. It is not part of scheduling until the complimentary function is invoked. This operation can be invoked only for threads that have been started(), and not yet suspended. In all other cases, the function should fail, and return -1.
• int uthreads_resume(int tid) : this function can only be invoked on the previously suspended thread. In all other cases, the function should fail, and return -1 as failure indication.
• int uthreads_ps(char* buf, int size) : this function fills the buffer of the specified size pointed to by buf with the status information about the threads in the library. If the buffer is not large enough, or the library has not been initialized yet, then this function fails, and returns with -1. Otherwise it fills the buffer with the lines in the following format:
  TID SchedulingState TotalTime RunTime Bursts V-TICKS
  The list should be sorted by the TID number. The last character in the buffer should be '\0'. Please, note this, and don't forget to add terminate the buffer properly.
  Example buffer: (shows information for three threads: 1, 10, 12)
  
  1 RUN 500 111 10 7\n10 BLOCKED 137 12 4 5\n12 READY 256 40 6 3\n\0

The first two operations can be called by any thread on any other thread.

The last operation can be called at any point in time after the library has been initialized. If there are no threads the buffer should contain only '\0'

Scheduling Extensions

for (;;) {
kill (pid, SIGUSR1); //simulate clock tick
sleep(10);
}

That's about it. Should not be difficult to implement :)

Now, to the scheduling algorithm itself. The virtual time in our system is divided into epochs. At the beginning of each epoch each thread gets the virtual quantum which is the number of the simulated clock ticks. This is maximal virtual time that a thread can use in this epoch. The quantums of different threads may differ as explained later.

Each time there is a clock tick, the library deducts 1 from the remaining quantum of the currently running thread. The currently active thread runs in the given epoch until one of the following occurs:

• thread blocks on the uthreads_semwait() operation;
• thread is suspended by some other thread that called uthreads_suspend() on this thread.
• thread yields the CPU by calling uthreads_yield().
• virtual time quantum of the thread becomes 0;

• READY state if the thread is signalled on the semaphore by some other thread;
• SUSPENDED state if this thread is suspended by some other thread while it is being BLOCKED. In this case the thread should not prevent other threads from completing their wait() operation.

In the second case, when the thread is resumed, it returns to the BLOCKED state to complete its wait() operation. It can move to the READY state only if it completes its last wait() operation. Suspending the already suspended thread has no effect on the internal state of the thread, and the thread remains in the SUSPENDED state. If suspend is called on the already suspended thread, it should return with -1 as specified in the uthreads.h file.

In case of yielding the CPU, the thread remains in the READY state. It will run when scheduler gets to it. If its quantum is greater than zero, this will happen in the current epoch.

If the quantum of a thread became 0, the thread is in the READY state, but the scheduler cannot schedule it. It cannot run until its quantum is refilled. This may happen only when a new epoch starts.

When does an epoch start? When does it end? The first epoch starts when uthreads_start() is called for the first time for the given thread set. At the beginning of epoch i, each thread is given its virtual quantum according to the formula: VQ(i)= V_QUANTUM + VQ(i-1)/2 where V_QUANTUM is the base quantum defined in uthreads.h, and VQ(i-1) is the quantum value that remains from the previous epoch, i-1. For the first epoch the second term is, of course, 0.
An epoch terminates when no READY thread with non-zero quantum exists. Then the new epoch is started, and the virtual quantums are allocated to all threads according to the formula above.

What is the role of the virtual time quantum? It serves as the priority of the thread. The rule is as follows. Every time the scheduler needs to choose which thread to run, it chooses the READY process with the highest virtual quantom.

• number of times this thread gained CPU;
• total time in microseconds that elapsed since this thread's creation to its termination;
• total time in microseconds that this thread run;
• total number of virtual ticks for this thread.

1. Design data structure(s) for managing threads.
2. Implement the library interface as defined in uthreads.h. Note the new things in this file. The library functions are well documented, please, pay attention.
3. Return Values:
   • All functions that have return value (except uthreads_wait(...), and uthreads_spawn(...)), should return 0 in case of success, unless otherwise specified and -1 in case of any failure. Examples of such failures are calling to functions in a wrong order, passing wrong arguments, etc.
   • You are required to extend the implementation of auxiliary function void uthreads_perror (char *msg) to reflect new functions that you add to the library. The output should be directed into the standard error stream, as before. See exercise 2 definition.
     

     Important Hint

     In order successfully to complete this exercise, you should understand where you have the critical sections. For example, handling external asynchronous singlals (SIGUSR1) of the virtual clock) while making updates to all internal data structures (such as semaphores, process queues, etc) would be unwise, to say the least. One simple way to handle this problem is to block signals from delivery while doing the critical operations inside your library. Be careful though to restore the signals appropriately when you finish with the critical operations.

   
   

    

   Submission

   Submit tar file named ex5.tar containing:

   1. README file containing your logins as usual.
   2. Source code.
   3. Makefile - your makefile should generate a library file named: libuthreads.a

   Make sure that the tar file can be extracted and that the extracted files do compile.

   Guidelines:

   1. Run everything on local machine (workstation you are using)
      
   2. Avoid collisions: do not use public machines (i.e. inferno, bagel...)
   3. Design your program carefully before you start writing.
   4. Always check the return value of a system call wherever applicable.
   5. Test you code thoroughly - write test programs - cross test program with other groups.
   6. Use asserts and debug printouts, but make sure to remove all asserts and any debug output from the library before submission. A library function should not have side-effects such as debug output or exit calls.
   7. CONVENTIONAL DEBUGERS ARE NOT SUITABLE FOR THREADS DEBUGGING !
      

    

   ---

   Ex5 errorcodes

   ---

   GOOD LUCK !!
   To the course home page