$3.$ This problem studies the interaction between real$-$time scheduling and mutual exclusion.

Consider the following excerpt of code:

$1$ pthread$\_$mutex$\_$t X; $//$ Resource X: Radio communication

$2$ pthread$\_$mutex$\_$t Y; $//$ Resource Y: LCD Screen

$3$ pthread$\_$mutex$\_$t Z; $//$ Resource Z: External Memory $($slow$)$

$4$

$5$ void ISR$\_$A$()\{//$ Safety sensor Interrupt Service Routine

$6$ pthread$\_$mutex$\_$lock$($&Y$)$;

$7$ pthread$\_$mutex$\_$lock$($&X$)$;

$8$ display$\_$alert$()$; $//$ Uses resource Y

$9$ send$\_$radio$\_$alert$()$; $//$ Uses resource X

$10$ pthread$\_$mutex$\_$unlock$($&X$)$;

$11$ pthread$\_$mutex$\_$unlock$($&Y$)$;

$12\}$

$13$

$14$ void taskB$()\{//$ Status recorder task

$15$ while $(1)\{$

$16$ static time$\_$t starttime $=$ time$()$;

$17$ pthread$\_$mutex$\_$lock$($&X$)$;

$18$ pthread$\_$mutex$\_$lock$($&Z$)$;

$19$ stats$\_$t stat $=$ get$\_$stats$()$;

$20$ radio$\_$report$($ stat $)$; $//$ uses resource X

$21$ record$\_$report$($ stat $)$; $//$ uses resource Z

$22$ pthread$\_$mutex$\_$unlock$($&Z$)$;

$23$ pthread$\_$mutex$\_$unlock$($&X$)$;

$24$ sleep$(100-($time$()-$starttime$))$; $//$ schedule next excecution

$25\}$

$26\}$

$27$

$28$ void taskC$()\{//$ UI Updater task

$29$ while$(1)\{$

$30$ pthread$\_$mutex$\_$lock$($&Z$)$;

$31$ pthread$\_$mutex$\_$lock$($&Y$)$;

$32$ read$\_$log$\_$and$\_$display$()$; $//$ uses resources Y and Z

$33$ pthread$\_$mutex$\_$unlock$($&Y$)$;

$34$ pthread$\_$mutex$\_$unlock$($&Z$)$;

$35\}$

$36\}$

You may assume that the comments fully disclose the resource usage of the procedures. That

is$,$ if a comment says $$uses resource X$,$ then the relevant procedure uses only resource X$.$ The

scheduler running aboard the system is a priority$-$based preemptive scheduler, where taskB is

higher priority than taskC. In this problem, ISR A can be thought of as an asynchronous task

with the highest priority.

The intended behavior is for the system to send out a radio report every $100$ms and for the

UI to update constantly. Additionally, if there is a safety interrupt, a radio report is sent

immediately and the UI alerts the user.

$($a$)$ Every so often, when there is a safety interrupt, the system completely stops working.

In a scheduling diagram $($like Figure $12\mathrm{.}11$ in Lee&Seshia$),$ using the tasks fA$,$B$,$Cg$,$ and

resources fX$,$Y$,$Zg$,$ explain the cause of this behavior. Execution times do not have to

be to scale in your diagram. Label your diagram clearly. You will be graded in part on

the clarity of your answer, not just on its correctness.

$($b$)$ Using the priority ceiling protocol, show the scheduling diagram for the same sequence

of events that you gave in part $($a$).$ Be sure to show all resource locks and unlocks until

all tasks are finished or reached the end of an iteration. Does execution stop as before?

$($c$)$ Without changing the scheduler, how could the code in taskB be reordered to fix the

issue? Using an exhaustive search of all task$/$resource locking scenarios, prove that

this system will not encounter deadlock. $($Hint: Your proof should enumerate $6$ cases

because the $3$ tasks each have $2$ possible resources they could block on$.)$