PThread Library

This project was implemented by Amruth Niranjan at Boston University

Tools used: YouTube (Videos explaining semaphore implementation) Linux Man-Pages for semaphore.h (sem_t structure)

Notes:

• I declared some global variables, namely a struct for the TCB block (each thread having a status, an id, a jmp_buf of its context, and a stack pointer for its memory access), SIGALRM timer signal handler, a global thread count, a boolean indicating whether pthread_create was being executed for the first time, and the given macros defining the registers of the jmp_buf. I also declared my own macros RUNNING, READY, EXITED, and NOSTATUS for the possible statuses threads could take. Lastly, a pthread_t type to indicate the ID of the current thread, gCurrent, as well as an arrayof TCBs representing the innards of all 128 (maximum) threads.

• First and easiest, pthread_self() simply returns the current thread, gCurrent.

• I started with pthread_create(). The global flag I used starts as true, so the conditional executes, but then the flag is set to false, so this only executes one time (the first time). Before this, control is transferred to init(), which initializes the TCB table (TCB). Each thread is given a status of NOSTATUS and an id of -1, both of which get modified when the thread is officially created in pthread_create(). Also, here, the signal handler for SIGALRM as well as the timer is set up. The timer generated by ualarm every 50ms triggers a SIGALRM which causes scheduler() to execute, as the sa_handler member of sigaction struct timer_handler is set to the address &scheduler. Once control comes back to pthread_create(), we loop to find the first thread whose status is NOSTATUS (effectively NULL). When this is found, we focus on this thread, setting its id to its index in the TCB array, the argument thread of pthread_create() to this value, and dynamically allocating 32767 bytes of data that its stack pointer is set to. From here, this thread's jmp_buf is altered in numerous ways. First, its program counter is set to the mangled, casted address of start_thunk. Then, we cast and place arg (argument of pthread_create()) in register R13, so that start_routine can execute properly (by placing it in register R12). Then, I move the stack pointer of this thread to the other end of the stack, and then decrement it by 8 bytes, so that the address of pthread_exit can be stored there, such that pthread_exit() will effectively "implicitly" be called following execution of pthread_create(). This is then accomplished by storing the value of the pointer at this location into the stack pointer register RSP. Lastly, all systems go: the status of this thread is set to ready, the global thread count is incremented, and scheduler() is invoked.

• scheduler() was implemented next. The currently running thread is set to READY (if it is not already), and the next thread that is READY is found. When found, the currently running thread's jmp_buf is stored via setjmp, which returns 0 on success. Next, the currently running thread is set to the "found" READY thread, whose status is set to RUNING, and data is loaded from its jmp_buf via longjmp. This does not occur again because the longjmp returns a nonzero value which causes the following save_state (return value of setjmp above) to return the same value, failing the conditional and leaving scheduler().

• Lastly, pthread_exit() was implemented as follows. When invoked, the global thread count is decremented. The currently running thread's status is set to EXITED, and if any threads remain (if globalThreads is not zero), scheduler() is invoked again, which schedules the following thread. If no threads remain, then each dynamically allocated stack pointer for each thread is freed. The program cannot reach below this point because the last thread itself has exited, and thus there is nothing to run the program. In case something has failed through scheduling, though, I implemented a failsafe that auto-exits past this point anyway.

• I implemented lock() and unlock(), which both simply set up a sigprocmask with SIGALRM in their sets to either block or unblock SIGALRM signals. I implemented lock() and unlock() in all of my pthread functions, and called lock() whenever any global variable was being accessed and unlock() after. This is important because global variables are shared between threads so locking and unlocking is important to prevent overwriting following context switches.

• I added a new status: BLOCKED. I also added two new values to the TCB_Table struct, which include the exit return value and the blocked_thread values.

• I changed the pthread_create function address to the address of the newly provided wrapper of pthread_exit, pthread_exit_wrapper. I implemented pthread_join, which checks if the argument thread is not BLOCKED or EXITED itself, in which case the currently running thread's status is set to BLOCKED. Then, the blocked_thread value of the current thread is set to the TID of the argument thread. I then unlock and call scheduler.

• After, I also check to see if the referenced value_ptr is not NULL. If it is not, it is set to the return value of the argument thread.

• In pthread_exit(), I made sure to set the return value of the currently running thread to the value_ptr value that was being passed in. Then, I indexed into the TCB array and found the specific thread whose blocked_thread value matched the current thread's TID. This means that the current thread was the "blocker", so I was trying to find the blocked thread corresponding to this blocker. Once found, its status was set to READY (updated from BLOCKED) and its blocked_thread value was set to -1 (the initialization value), so that it did not implicitly remain blocked. Implementing these corner cases were tough and I had to change around/reverse the logic of the blocker-blocked thread relationship within the blocked_thread value, as it was not working using the reverse logic beforehand. After this, pthread_exit() proceeds as normal, except I free the threads individually instead of altogether.

• I declare a new struct, sema, to represent the values corresponding to each semaphore. These include the unsigned value, the number of threads being blocked, the indices to the queue of threads, an actual queue (simply implemented using a statically allocated array of integers), an initialization flag, and a pointer to the sem_t data type. An array of these semaphores is initialized.

• sem_init() finds the first semaphore with an unraised flag. It sets the referenced semaphore pointer sem's __align value to this index within the semaphores array. It then initializes the indices of the queue to 0, the current_sem pointer of my defined sema data structure to the referenced semaphore sem, and raises the initialization flag. It also sets the value of the semaphore to the referenced value.

• sem_wait() decrements the value if possible (non-zero). If not, it sets the currently running thread's status to BLOCKED, and adds it to the queue. It then increments the corresponding referenced semaphore sem's blocked_count value through the usage of __align.

• sem_post() checks if any threads are being blocked, in which case the value of the currently referenced semaphore sem is incremented. This allows for another thread blocked in a sem_wait() call to be woken up, locking the semaphore.

• Lastly, sem_destroy() sets the blocked_count of an uninitialized semaphore to 0. This is to ensure that the semaphore has only been initialized already by sem_init() and is not one that is uninitialized. This will also ensure that this semaphore is unable to be used again until sem_init() has been called again.

Please let me know if there are any bugs!

Thank you,

Amruth Niranjan