This problem is about critical sections. $($Note: If any part of your answer comes

from an AI system, you must cite the system you use and tell what prompt$($s$)$ you gave.$)$ Consider

an implementation of a LIFO list, implemented by the following code:

typedef struct element $\{$

void $*$value;

struct element $*$next;

$\}$ elem$\_$t;

$0$ void insert$($elem$\_$t $**$l$,$ void $*$val$)\{$

$1$ elem$\_$t $*$e $=$ malloc$($sizeof$($elem$\_$t$))$; assert$($e$)$;

$2$ e$->$value $=$ val;

$3$ e$->$next $=*$l;

$4*$l $=$ e;

$5\}$

$6$

$7$ void $*$get$($elem$\_$t $**$l$)\{$

$8$ void $*$rv $=$ NULL;

$9$ elem$\_$t $*$e $=*$l;

$10$ if $($e$)\{$

$11*$l $=$ e$->$next;

$12$ rv $=$ e$->$value;

$13$ free$($e$)$;

$14\}$

$15$ return rv;

$16\}$

A certain program will use threads that share an instance of the above implementation and update

it via the insert and get functions. $($Note that an instance can be created simply by declaring a

variable of type elem$\_$t $*$ and initializing it to NULL.$)$

a$.$ Identify any critical sections in the two functions above, by giving the range of line numbers

that could give incorrect results if interleaved in the execution of two threads.

b$.$ What statements need to be added to the insert and get functions to implement mutual

exclusion using a pthreads mutex?

c$.$ What additional function will need to be implemented in order for the modified code to work?

d$.$ The code, as written, returns NULL if the list is empty. This is not very useful if the list is used

to$,$ say, store pointers to jobs, because a thread must waste cycles repeatedly calling get$()$ to

obtain useful work to do$.$ A more useful semantic is for the thread calling get$()$ to block if

the list is empty, and for a thread that calls insert$()$ on an empty list to awaken a thread

blocked in get. Rewrite the $($synchronized$)$ get$()$ and insert$()$ functions to implement this

blocking semantics; also add any additional code needed to make it work correctly. $($It is OK

for threads calling get$()$ to block forever if nothing is ever inserted.$)$

Note: this is a subtle problem. You will need to use a condition variable $($pthread$\_$cond$\_$t$)$

to implement this correctly. See the man page for pthread$\_$cond$\_$wait$()$ and the slides from

lecture that show how to use condition variables. The man pages are long, but the first

half$-$dozen paragraphs of pthread$\_$cond$\_$wait tell you most of what you need to know. The

paragraph $$Condition Wait Semantics$$ is also important. $($You will need to initialize the

condition variable.