Assignment 3

A User Level Thread Package with a Sample Test Program

The objective of this assignment is to help you understand and gain some hands on experience on multithreading, and user-level threads in particular.

 User Level Threads Package

Implement a user level threads package with a non-preemptive, priority based, round robin scheduling algorithm. To make things easy, assume that there is only one priority queue of ready to run threads.

 You should define the public interface in the header file eel358threads.h as should be as follows:

Function Signature	Return Values	Description
int eel358init(void);	On success 0, otherwise -1	This function initializes the necessary data structures of the library and starts the internal scheduling mechanism. This function should be called prior to any other functions as a necessary precondition for their success.
int eel358newthread(void (*f)(void), int priority);	On success, the thread's ID (>= 0). Note, you should reuse thread IDs when they become available. On failure, -1 will be returned.	This function creates a new thread, where its entry point is a function with the following signature: void f(void). The newly created thread should be assigned the READY state and appended to the end of the READY list. The priority of the thread is defined by the argument ‘priority’. The function may fail if too many threads were already spawned (The maximal number of threads allowed by the library is specified in  eel358threads.h by MAXTHREADNUM). We set the priority of the thread here only. We cannot change the priority of the thread once the thread has been created. If no priority has been passed as argument, NORM_PRIORITY must be set as the thread priority.
int eel358gettid();		The function returns the thread ID of the calling thread.
int eel358terminate(int tid);	The function returns 0 if the thread was successfully terminated and (-1) otherwise. A thread can terminate itself! In this case the function doesn't return.	This function terminates the thread corresponding to its argument (the thread ID). The function should move the thread to the TERMINATE state and append it to the appropriate list. All the resources taken up by thread apart from its control data structure should be released. A thread may remain in the TERMINATE state an indefinitely long period of time. It is extracted from this state by the eel358thread_wait library call. A thread should explicitly call the eel358terminate function on itself or by other thread in order to notify the library about its termination, otherwise, the thread will forever remain active.
int eel358suspend(int tid);	The function returns the ID of the suspended thread on success and -1 otherwise.	This function suspends a thread until the thread is resumed by eel358resume. The calling thread can suspend itself; in this case, a scheduling decision should be performed. Suspending a thread in the TERMINATE, SLEEP or SUSPEND states has no effect and is not considered an error.
int eel358resume(int tid);	The function returns the thread ID on success and -1 otherwise.	This call resumes a suspended thread. The resumed thread is appended to the end of the READY list.  Resuming a thread in the RUN, READY, TERMINATE, or SLEEP state has no effect and is not considered and error. Obviously, a suspended thread cannot resume itself.
int eel358thread_sleep(long usec);	This function returns 0 in case of success and -1 otherwise.	The calling (in RUN state) thread will sleep for usec micro-seconds, that is, until the virtual time advances to (current_time + usec) (see manpage setitimer(2)). The virtual timer decrements only when a host process runs in the user mode. Therefore in real time the thread that has put itself to sleep may sleep more than usec. Note that you cannot implement thread sleeping using usleep(3).
int eel358thread_wait(int tid, struct eel358thread_status *s);	The function will return the thread's ID on success and -1 otherwise.	This function call fills the eel358thread_status structure with the thread data. If this function is called for a terminated thread, it deletes the thread from the system.

　

 

Make sure you write any error messages on STDERR and not STDOUT.

When a system call fails, you should show the error “system call error\n”. On all other errors encountered, you should show “thread library error\n”

You can have as many internal functions and variables as you like in your library.

A sample eel358threads.h will look like:-

 

#ifndef _EEL358THREADS_H

#define _EEL358THREADS_H

 

#include <stdio.h>

#include <time.h>

#include <setjmp.h>

#include <signal.h>

#include <errno.h>

#include <stdlib.h>

#include <sys/time.h>

#include <unistd.h>

 

#define MAXTHREADNUM 100 /* maximal number of threads */

#define QUANTUM 1000000  /* one second in usecs */

#define STACKSIZE 4096   /* stack size per thread */

#define USECOND 1

#define SECOND USECOND*1000000

 

/* scheduling states */

#define RUN        0x01

#define READY      0x02

#define SLEEP      0x04

#define SUSPEND    0x08

#define TERMINATED 0x10

 

/* thread priority */

#define MIN_PRIORITY        0x01

#define NORM_PRIORITY       0x02

#define MAX_PRIORITY        0x03

 

struct eel358thread_status {

  int  state;     /* the thread's current state */

  int  priority;  /* the thread's current priority */

  long run_time;  /* total virtual time (in microseconds) spent by the thread in RUN state */

  long bursts;    /* number of times the thread has been scheduled to run*/

  long dreams;    /* number of times the thread has been put to sleep */

};

 

/* external interface */

int eel358init(void);

int eel358newthread(void (*f)(void), int priority);

int eel358suspend(int tid);

int eel358resume(int tid);

int eel358terminate(int tid);

int eel358thread_sleep(long usec);

int eel358gettid(void);

int eel358thread_wait(int tid, struct eel358thread_status *ts);

 

/* Note that the function you will write to do the scheduling is an internal function

   and is not visible to the outer world and hence can have any name/ signature. */

 

#endif

You should use the above sample header file and make additions to it as required. Do not modify any of the existing functions/ definitions.

 Non Preemptive Priority Based Round Robin Scheduling Algorithm

The scheduling algorithm we will use is a non-preemptive, priority based, round robin scheduling algorithm. You must implement the scheduling algorithm as described below. There should not be any variations to it (not even minor ones), so make sure you understand it properly.

 

To start with, remember that all scheduling is done in virtual time, i.e., when the process of which the library is a part is running in user mode. Every thread in the host process that is READY to run receives a time slice (QUANTUM*thread_priority) of virtual time (i.e., of the total user-run time of the host process). QUANTUM  is defined in the header file supplied and thread_priority is the priority of the thread being scheduled. The priorities of the thread may be MIN_PRIORITY, NORM _PRIORITY, MAX _PRIORITY. They have also already been defined in the header file.

　

The multiplication of the QUANTUM and the priority of the thread being scheduled gives the time slice for the thread to be scheduled.

 

During the quantum the following four events may occur:

1. The thread finishes and calls eel358terminate.

2. The thread suspends itself through eel358suspend.

3. The thread puts itself to sleep through eel358thread_sleep.

4. The quantum expires.

No other thread can preempt a thread while it is in the RUN state.

 

Each of the above events should trigger the scheduling algorithm that will pick up the next thread to run from the READY list. The RR policy simply means that we pick them one after the other in the order they appear in the list. When a quantum expires, the thread is returned to the end of the list.

 

For the threads that are either suspended or sleep, you should not schedule them until they resume and enter the READY list.

　

POINTS TO NOTE

Ensure that you follow all file names properly. If the file names are not followed properly, we might not be able to evaluate your assignment and a ‘0’ will be awarded.

 

Ensure you do not modify the public interface of the library as defined in the sample header file above. Changing the public interface may cause problems in evaluating your assignments and you may be awarded a ‘0’.

 

We can use the test file of any student and test it against the library of any student. It must work if both are correct. If it doesn’t work, at least one of those students will get a ‘0’.

 

If no test program is given along with the library, it is assumed that the user did not test the library and hence is not working and a ‘0’ will be awarded.

 

Do not output anything from the library except for the errors defined above to the STDERR. Use the test program for such things. An automated test program written by us will evaluate your library and will see any such output as unexpected behavior and heavy penalty will be given.

 

The library must not have any side effects like debug outputs, or exit calls.

 

Use the thread state transition model given at the end. Do not add or remove states to it.

 

The programs must compile with the ‘gcc’ or ‘g++’ compiler.

 

SUGGESTIONS

Do not have any ‘printf’ or similar calls in the library except for displaying the two errors to STDERR as given above.

 

Test your library with the test program written by your class mates and your test program with their library. You do not need their source code to do this. You can do this with the binaries of their library.

 

Refrain from using the CSC machines. Windows users, may download and install Cygwin rather than using the CSC machines. Cygwin supports ‘gcc’, ‘g++’.

 

Look for signal critical sections in your code.

 

Always check the return value of a system call.

 

RESOURCES

You may find it helpful to download and read Chapter 4 and other chapters from the book 'Advanced Linux Programming' by CodeSourcery LLC.  A free copy of this book is available for download at this URL: http://www.advancedlinuxprogramming.com

 

Man pages for:

   1. gettimeofday(2)

   2. setitimer(2)

   3. sigaction(2)

   4. sigprocmask(2)

   5. setjmp (3)

   6. longjmp(3)

   7. signal (3)

   8. sigsetops(3)

 

Sample makefile (This may not work for cygwin. It may need some modifications. You are on your own for that.):-

all : libeel358threads.a

eel358threads.o : eel358threads.c eel358threads.h 

        g++ -c eel358threads.c -Wall

libeel358threads.a : eel358threads.o 

        ar rcu libeel358threads.a eel358threads.o

        ranlib libeel358threads.a

test : libeel358threads.a test.c

        g++ test.c -L. –leel358threads -o eel358test -Wall

 

 THREADS STATE TRANSITIONS:

SUBMISSION

Submit a tar file named <YOUR_ENTRY_NUMBER>_asgn3.tar containing:

1.      README file containing any information that may be useful for the evaluator.

2.      eel358threads.h – The public interface of the library.

3.      eel358threads.c – The source code of the library.

4.      test.c – a sample program to test all the public functions of the library.
We can run any student’s test program on anyone else’s library as the public interface is the same. So ensure you do not mess it up here, or you get ‘0’ marks.

5.      Makefile – Your makefile should generate a static library file named: libeel358threads.a.
This makefile should also generate a executable file named eel358test.out and the static library libeel358threads.a should be linked along with the test program.

The tar file can be uploaded in the assignment # 3 using this link. Please make sure that you upload the assignment only once. In case of multiple submission ONLY first submission will be used for grading.

Deadline

The (extended) submission deadline for the assignment # 3 is 22nd October 2006 [23:59 Hrs].

Questions

If you have any further questions relating to this assignment, you may contact the TA Mr. Jayant Kumar Gandhi [2005EET2906].