In this project, you will add synchronization implementation to SThreads, a simple user$-$space threading library. In the synchronization implementation, you are expected to implement the lock utilities, including read$\_$lock and write$\_$lock. Given your implementation, an application programmer can use your synchronization primitive to develop a multithreading application that accesses and updates shared data. In particular, an application programmer will use your $($read$/$write$)$ lock mechanism to achieve the synchronization goal.

Get the source program folder sthread.tgz $($to extract: $ tar zxvf sthread.tgz$).$ The files provide the source, header, and Makefile for the SThreads library. The publicly available functions and datatypes are in the file sthread.h$.$ The library is used as follows:

Threads are manipulated using variables of type sthread$\_$t$.$

sthread$\_$init$()$ must be called exactly once, as the first thing in main$().$ It returns $0$ normally, and $-1$ on error.

A new thread is created using the function:

int sthread$\_$create$($sthread$\_$t $*$t$,$ sthread$\_$main$\_$t main, void $*$arg$)$

The first argument is where the sthread$\_$t object is returned. The second is the function the new thread should run. The third argument is passed to this function. sthread$\_$create$()$ returns $0$ normally and $-1$ on error.

sthread$\_$self$()$ returns the sthread$\_$t associated with the currently running thread. sthread$\_$suspend$()$ puts the currently running thread to sleep, and sthread$\_$wake$($sthread$\_$t t$)$ wakes up a thread specified.

An example program:

#define $\_$REENTRANT

#include

#include

#include

#include

#include "sthread.h$"$

int

threadmain$($void $*$arg$)$

$\{$

int threadno $=($int$)$arg;

for $($;;$)\{$

printf$("$thread $\%$d: I$\text{'}$m going to sleep

$",$ threadno$)$;

sthread$\_$suspend$()$;

printf$("$thread $\%$d: I woke up$!$

$",$ threadno$)$;

$\}$

return $0$;

$\}$

int

main$($int argc, char $*$argv$[])$

$\{$

sthread$\_$t thr$1,$ thr$2$;

if $($sthread$\_$init$()==-1)$

fprintf$($stderr$,"\%$s: sthread$\_$init: $\%$s

$",$ argv$[0],$ strerror$($errno$))$;

if $($sthread$\_$create$($&thr$1,$ threadmain, $($void $*)1)==-1)$

fprintf$($stderr$,"\%$s: sthread$\_$create: $\%$s

$",$ argv$[0],$ strerror$($errno$))$;

if $($sthread$\_$create$($&thr$2,$ threadmain, $($void $*)2)==-1)$

fprintf$($stderr$,"\%$s: sthread$\_$create: $\%$s

$",$ argv$[0],$ strerror$($errno$))$;

sleep$(1)$;

sthread$\_$wake$($thr$1)$;

sleep$(1)$;

sthread$\_$wake$($thr$2)$;

sleep$(1)$;

sthread$\_$wake$($thr$1)$;

sthread$\_$wake$($thr$2)$;

sleep$(1)$;

return $0$;

$\}$

#define $\_$REENTRANT: This is necessary in any multithreaded program, as it tells subsequent include files to use reentrant versions of library functions and thread$-$safe variables. For example, the errno variable, since it is a global variable, is normally not thread$-$safe. A function in thread A can set it on error, and thread B can set it to something else before the caller in thread A ever gets to read the value. This is an example of a race condition. If you #define $\_$REENTRANT, though, errno is redefined to $(*\_\_$errno$\_$location$()),$ which references a different address for each thread. An implementation of this function is provided in sthread.c$.$

sleep$()$: you are not allowed to use sleep$()$ or any other timer functions in your implementation for sync functions $($except the user applications, which is for demonstration purpose$).$

test$\_$and$\_$set$\_$bit$()$: is used to immplement spinlocks, in which you repeatedly call test$\_$and$\_$set$\_$bit$()$ and a no$-$op in a tight loop, waiting for the test result to be $0.$ sched$\_$yield$()$ is a good no$-$op function to use $($within your spinlocks, you need to #include $).$ Note that you can use spinlocks to synchronize the access on your readers$-$writers locks' shared data structures, but not to implement the readers$-$writers locks' themselves. In other words, if a thread calls sthread$\_$write$\_$lock$()$ on an unavailable read$-$write lock, it should suspend rather than spin until the lock is available.

Support muliple readers: your rwlock implementation should allow multiple readers to acquire the lock in read $($shared$)$ mode and concurrently execute. For example, if the lock is held by reader thread A$,$ another reader thread B can immediately acquire and share the lock with A if there is no other waiting thread $($write$).$ If the lock is held in write mode, no other threads can acquire the lock in read or write mode.

Bonus $(10\%)$: Favor writer threads over readers: if there are threads waiting to acquire the lock in write mode, you should let one of these threads acquire the lock immediately when the lock becomes abailable. For example, the lock is held by a writer thread and a thread A is waiting to acquire the lock in read mode. Another thread B comes, trying to acquire the lock in write mode. In an implementation that favors writers over readers, thread B can acquire the lock in write mode and proceed if the previous write lock is released.