Programming Assignment 6

User-Level Thread Library

Objective

In this project, you will design and implement a user-level thread library which supports thread creation, thread scheduling, thread synchronization, and inter-thread communication (message passing and mailbox) functions.

Assignment

You will design and implement, in 4 phases, a user-level thread library.

Phase 1

Thread library initialization and shutdown, and thread creation and termination:

void t_init(); /* Initialize the thread library by setting up the "running" and the "ready" queues, creating TCB of the "main" thread (with thread_priority 1 and thread_id 0), and inserting it into the running queue. */
void t_shutdown(); /* Shut down the thread library by freeing all the dynamically allocated memory. */
void t_create(void (*func)(int), int thr_id, int pri); /* Create a thread with priority pri, start function func with argument thr_id as the thread id. Function func should be of type void func(int). TCB of the newly created thread is added to the end of the "ready" queue; the parent thread calling t_create() continues its execution upon returning from t_create(). */
void t_terminate(); /* Terminate the calling thread by removing (and freeing) its TCB from the "running" queue, and resuming execution of the thread in the head of the "ready" queue via setcontext(). Every thread must end (semantically) with a call to t_terminate(). */

An initial thread control block (TCB) may look like the following.

       struct tcb {
	  int         thread_id;
          int         thread_priority;
	  ucontext_t *thread_context;
	  struct tcb *next;
       };

       typedef struct tcb tcb;

Yield the CPU:

void t_yield(); /* The calling thread volunarily relinquishes the CPU, and is placed at the end of the ready queue. The first thread (if there is one) in the ready queue resumes execution. */

Test cases: T1, T1x, and Contributed Test Runs from Students below
Notes on header files: ud_thread.h is the header file to be included by YOUR applications (such as test00.c). It is equivalent to header file pthread.h included in any Pthread application. Therefore, ud_thread.h should ONLY contain the following API prototypes (in Phase 1), and nothing else.
```
void t_create(void(*function)(int), int thread_id, int priority);
void t_yield(void);
void t_init(void);
void t_shutdown(void);
void t_terminate(void);
```
t_lib.h is the header file for the implementation of the UD Thread library (t_lib.c). t_lib.h includes ucontext.h, stdlib.h, etc. and declares the type tcb as the node type for a linked list of TCBs. As these data structures (e.g., tcb) are internal to the implementation of the UD Thread library, they should not be "visible" to any application.
"Errors" in valgrind: When you run valgrind to check for memory leaks in your code, there could be "errors" reported. These errors (which are different from the reported memory leaks) are caused by the "stacks" allocated for the threads. You may either ignore the "errors," or consult this code to see how your could use VALGRIND_STACK_REGISTER(start, end) (Registers a new stack. Informs Valgrind that the memory range between start and end is a unique stack. Returns a stack identifier that can be used with other VALGRIND_STACK_* calls.) and VALGRIND_STACK_DEREGISTER(id) (Deregisters a previously registered stack. Informs Valgrind that previously registered memory range with stack identifier id is no longer a stack.) to get rid of those "errors." (Credits: Will Cantera)

Extra Credits: Challenging test cases...

Phase 2

CPU scheduling and time slicing:

2-Level Queue (2LQ) with level 0 (high priority) and 1 (low priority). By default, the main thread is with level 1 (low priority). Threads in the low priority queue will be executed only when there is no high priority thread.
Round-Robin (RR) scheduler within each level with time quantum of, say, 10,000 microseconds. Use ualarm() to "simulate" timer interrupts so that when a SIGALRM is caught by the signal handler (i.e., the arrival of a timer interrupt), context switching is performed. Notice that right before context switching to a new thread, another SIGALRM needs to be scheduled (via ualarm) as the next timer interrupt. Also, when a thread yields before its time quantum expires, the scheduled SIGALRM should be canceled via ualarm(0,0). The thread library functions of t_init(), t_terminate(), t_shutdown(), and t_yield() should be made atomic by distabling (timer) interrupts via sighold() and sigrelse().

Test cases: T1a (2LQ), T2 (RR), T4 (RR), and T7 (2LQ)

Phase 3

Thread synchronization with Semaphore:

int sem_init(sem_t **sp, int sem_count); /* Create a new semaphore pointed to by sp with a count value of sem_count. */
void sem_wait(sem_t *sp); /* Current thread does a wait (P) on the specified semaphore. */
void sem_signal(sem_t *sp); /* Current thread does a signal (V) on the specified semaphore. Follow the Mesa semantics (p. 9 of OSTEP Chapter 30 Condition Variables) where the thread that signals continues, and the first waiting (blocked) thread (if there is any) becomes ready. */
void sem_destroy(sem_t **sp); /* Free any memory related to the specified semaphore. If there are queued TCBs, move them to the ready queue, and this may imply that the semantics of the application might be incorrect. */

Semaphore type sem_t is defined in t_lib.h as follows.

       typedef struct {
         int count;
         tcb *q;
       } sem_t;

Since application programs of the UD Thread Library need to define variables of type semaphore pointer, Semaphore type sem_t is defined in ud_thread.h as follows.
```
       typedef void sem_t;
```

Atomic execution of sem_wait() and sem_signal() must be enforced. This can be achieved by disabling and enabling SIGALRM "interrupts" via sighold(3) and sigrelse(3), respectively.
sample thread library where applications include ud_thread.h
Test cases: T3, T10, Shone-Hoffman (output), and Dining Philosophers [outputs of 3 sample runs] (Note that this implementation used pseudo-random number generator rand() to shuffle the thread creation order of philosophers, where the current time is used as the seed (into srand()) for a new sequence of pseudo-random integers to be returned by rand().

Notes on header files: Now, ud_thread.h should be extended with the semaphore type and semaphore API prototypes.

typedef void sem_t;

int sem_init(sem_t **sp, unsigned int count);
void sem_wait(sem_t *sp);
void sem_signal(sem_t *sp);
void sem_destroy(sem_t **sp);

Requirement: You need to implement the Semaphore homework problems of Rendezvous (Question 2 of OSTEP Chapter 31) (as rendezvous.c) and Partial Order (as partialorder.c) with your UD Thread Library and submit the code (and the updated Makefile) with your library implementation in the same zip file.

Phase 4

Inter-thread communications:

mailbox:

int mbox_create(mbox **mb); /* Create a mailbox pointed to by mb. */
void mbox_destroy(mbox **mb); /* Destroy any state related to the mailbox pointed to by mb. */
void mbox_deposit(mbox *mb, char *msg, int len); /* Deposit message msg of length len into the mailbox pointed to by mb. */
void mbox_withdraw(mbox *mb, char *msg, int *len); /* Withdraw the first message from the mailbox pointed to by mb into msg and set the message's length in len accordingly. The caller of mbox_withdraw() is responsible for allocating the space in which the received message is stored. If there is no message in the mailbox, len is set to 0. Notice that mbox_withdraw() is not blocking, i.e., mbox_withdraw() returns immediately if there is no message available in the specified mailbox. Even if more than one message awaits the caller, only one message is returned per call to mbox_withdraw(). Messages are withdrew in the order in which they were deposited. */

An initial mailbox may look like the following.

       struct messageNode {
         char *message;     // copy of the message 
         int  len;          // length of the message 
         int  sender;       // TID of sender thread 
         int  receiver;     // TID of receiver thread 
         struct messageNode *next; // pointer to next node 
       };
	 
       typedef struct {
	  struct messageNode  *msg;       // message queue
	  sem_t               *mbox_sem;  // used as lock
       } mbox;

Test cases: T6

message passing:

void send(int tid, char *msg, int len); /* Send a message to the thread whose tid is tid. msg is the pointer to the start of the message, and len specifies the length of the message in bytes. In your implementation, all messages are character strings. */
void receive(int *tid, char *msg, int *len); /* Wait for and receive a message from another thread. The caller has to specify the sender's tid in tid, or sets tid to 0 if it intends to receive a message sent by any thread. If there is no "matching" message to receive, the calling thread waits (i.e., blocks itself). [Later, a sending thread is responsible for waking up a waiting (or blocked) receiving thread.] Upon returning, the message is stored starting at msg. The tid of the thread that sent the message is stored in tid, and the length of the message is stored in len. The caller of receive() is responsible for allocating the space in which the message is stored. Even if more than one message awaits the caller, only one message is returned per call to receive(). Messages are received in the order in which they were sent. The caller will not resume execution until it has received a message (blocking receive). */
Note: send() and receive() together are termed asynchronous communication.
Test cases: T5 and T8
Notes on asynchronous "message passing" implementation: You may implement asynchronous message passing through the following two intermediate steps,
- Non-blocking receive()
  When a thread executes a non-blocking receive(), the receive() function goes through the thread's message queue and looks for the first "matching" message. If there exists such a matching message, copies it to the space allocated, deletes the message from the message queue, and returns. If no such message, simply returns. Of course, you have to use a binary semaphore [from Phase 3] as a lock to protect the examining and dequeuing process.
  The send() function simply enqueues the sent message to the receiving thread's message queue. Of course, you will need to lock such an enqueue operation.
  Since there is no blocking involved, you don't need to use any semaphore to block any thread.
- Non-discriminatory, blocking receive()
  In this version of receive(), receive() ignores the sender's tid and simply returns the first message (if there is one) in the message queue. However, when receive() is executed but there is no message in the message queue, the invoking thread (executing inside the receive() function) is blocked. To implement such blocking, you use a counting semaphore [from Phase 3] defined in struct tcb.
  Now, the send() function, when invoked by a sending thread, not only enqueues the message, but also "signals" the receiving thread's counting semaphore to wake it up (if the receiving thread is currently blocked). Notice that threads could send messages to a receiving thread at any time so that multiple messages may have been enqueued in a receiving thread's message buffer before the receiving thread even executes a receive(). For instance, send() may have been invoked 3 times (from the same or different threads) so that the receiving thread's semaphore has been signaled 3 times to raise the value of the semaphore to 3! Now when the receiving thread executes receive(), it does sem_wait() and dequeue the first message. Since the semaphore value is not negative, the receiving thread continues and returns from receive() [without blocking]. Given that there are 3 messages in the queue originally, the receiving thread could execute receive() 3 times without being blocked. However, when the 4th receive() is executed, the receiving thread blocks waiting for the next (4th) message to wake it up.
Extra Credits [rendezvous -- synchronous communication] (Refer to Question #2, Chapter 31 Semaphores)
void block_send(int tid, char *msg, int length); /* Send a message and wait for reception. The same as send(), except that the caller does not return until the destination thread has received the message. */
void block_receive(int *tid, char *msg, int *length); /* Wait for and receive a message; the same as receive(), except that the caller (a receiver) also needs to specify the sender. */
Test cases: T9 and T11

How to get started

Start the project from the sample thread library (a zip file).

Understand user context, and the saving (via getcontext()) and restoration (via setcontext()) of the user context (of a thread) by reviewing and executing the program loop.c.
Create a new thread via the makecontext() function call.
Unserstand the context switching between threads with the getcontext()/setcontext()/swapcontext() function calls by reviewing and executing the following programs.
- code (first version): swapcontext.c and its execution trace
- code (with yield()): swapcontext-yield.c
- code (using TCB): swapcontext_tcb.c
Round-robin scheduling: Use ualarm(3)and a signal handler that catches SIGALRM and schedules the next thread in accordance with the scheduling policy. Use sighold(3)/sigrelse(3) to make thread library APIs atomic. (sample alarm code) (example critical section code by Sean Krail)

Test Runs

The TA will use the test programs T1, T1x, T1a, T2, T2a, T3, T4, T5, T6, T7, T8, T9, T10, and T11, to test your code against outputs 1, 1x, 1a, 2, 2a, 3, 4, 5, 6, 7, 8, 9 or 9.alt, 10, and 11 or 11.alt, and may use other test programs as well.
Blocking send/receive: [9 with active V], [9 with passive V], [11 with active V], [11 with passive V]

Contributed Test Runs from Students

Phase 1:

Shone-Hoffman (output)
Sullivan (multithreaded Fibonacci generator) (makefile) (output)
Baron-Sankar (output)

Phase 2:

Phase 3:

Senzer-Spicer (output and README)

Phase 4:

Senzer-Spicer (output and README)

Grading

50% correctly working thread library initialization, thread creation/termination, 2LQ/RR and voluntary scheduling.
15% correctly working thread synchronization via semaphore.
25% correctly working inter-thread communication.
10% documentation and code structure.