CS 3331 Final QUESTIONS
Jun. 20, 2025
DO NOT WRITE YOUR SOLUTIONS ON THIS QUESTION SHEET!
1. (5 points) Answer the true-or-false questions on the solution sheet.
2. (10 points) Answer the short response questions on the solution sheet.
3. (7 points) Consider the following C code:
1charb = ’ b ’ ;
2
3voidf ( ){
4static int∗p = m a l l o c (sizeof(int) ) ;
5intx = 6 ;
6∗p = x ;
7int∗∗q = &p ;
8}
On the solution sheet, indicate which area of process memory each variable may be stored in.
4. (6 points) Consider the following C code:
1intmain ( ){
2intr , s ;
3for(inti = 0 ; i<3 ; i ++){
4r = f o r k ( ) ;
5i f( r == 0 )
6break;
7}
8s = f o r k ( ) ;
9i f( r == 0 && s != 0 )
10f o r k ( ) ;
11}
On the solution sheet draw the process tree that results from this programs execution. Label each vertex
of the tree with the line number of thefork()that spawned it. Label the main process (root vertex)
with “M”.
5. (15 points) Below is a proposed solution to the critical section problem. There are two threadsT
0
and
T
1
run thef()function below. Theivariable refers to this process and thejvariable refers to the other
process. That is, forT
0
,i= 0 andj= 1; forT
1
,i= 1 andj= 0).
1b o o l i n t e r e s t [ 2 ] ={FALSE , FALSE};
2
3voidf ( ){
4while( 1 ){
5i n t e r e s t [ i ] = TRUE;
6while( i n t e r e s t [ j ] == TRUE){
7i n t e r e s t [ i ] = FALSE ;
8while( i n t e r e s t [ j ] == TRUE) ;
9i n t e r e s t [ i ] = TRUE;
10}
11// CRITICAL SECTION HERE
12i n t e r e s t [ i ] = FALSE ;
13// remainder
14}
15}
Answer the questions on the solution sheet.
(a) (8 points) Does this solution provide mutual exclusion? If so, give a formal proof by contradiction
that it does. If it does not, give a proof by counter-example using an execution table.
(b) (7 points) Show this solution does not provide bounded waiting by giving an execution sequence
where a thread is able to enter the CS twice while another thread is not able to enter once despite
waiting to enter. Show the sequence is repeatable by indicating where the program enters a repeated
state.
6. (13 points) The system below has exactly twoT Athreads and twoT Bthreads running at the same
time.
The intended behavior is that the program will always print the string “AABBAABBAABB. . .”.
1 semaphore mutex = 1 , g o
a = 2 , g ob = 0 ;
2
3voidTA( ){
4while( t r u e ){
5w a i t ( mutex ) ;
6w a i t ( g o
a ) ;
7p r i n t ( ”A” ) ;
8s i g n a l ( g ob ) ;
9s i g n a l ( mutex ) ;
10}
11}
12voidTB( ){
13while( t r u e ){
14w a i t ( mutex ) ;
15w a i t ( g o
b ) ;
16p r i n t ( ”B” ) ;
17s i g n a l ( g oa ) ;
18s i g n a l ( mutex ) ;
19}
20}
Page 2 of 5
(a) (3 points) This solution is incorrect. Give an execution sequence to illustrate this. Have the
program execute in such a way that the output produced begins with “AB...”.
(b) (3 points) This solution has a possible deadlock. Give an execution sequence where the system
deadlocks.
(c) (2 points) Draw the resource allocation graph (RAG) for the system in a deadlocked state.
(d) (5 points) Correct the solution to prevent both incorrect output and deadlocks. You may add new
semaphores or helper variables as you see fit, but be sure to indicate their initial state.You may
not add newprintstatements. A thread may only executeprintonce in an iteration
of the while loops on lines 4/13.
7. (13 points) In a system there are 3 worker threads{T
1
, T
2
, T
3
}, each of which must perform some phase
computation in a synchronized manner. That is, before any threadT
i
can execute phasej, all threads
must have completed executing phasej−1.
Each of the worker threads execute the following thread function:
1voidphase
comp ( ){
2inti = 0 ;
3while( t r u e ){
4/∗BEGIN PHASE COMPUTATION∗/
5p r i n t ( ”T” + i d + ” e x e c u t e s p h a s e ” + i + ”\n” ) ;
6/∗END PHASE COMPUTATION∗/
7p h a s es y n c ( ) ;// Monitor Method
8i ++;
9}
10}
In order to properly synchronize the system, your classmate has written the followingHoare-type
monitor:
1 m o n i t o r phase
mon{
2c o n d i t i o n w a i t
f o ra l l ;
3intdone = 0 ;
4p r o c p h a s e
s y n c ( ) ;
5}
6
7 p r o c p h a s e
s y n c ( ){
8done++;
9i f( done<3 ){
10w a i t ( w a i t
f o ra l l ) ;
11}else{
12for(inti = 0 ; i<2 ; i ++)
13s i g n a l ( w a i t
f o ra l l ) ;
14done = 0 ;
15}
16}
Your classmate’s monitor is incorrect.
(a) (5 points) To show the solution is incorrect, give an execution sequence where some thread is able
to complete some execution phasejbefore some other thread is able to complete execution phase
j−1.
(b) (5 points) Correct your classmate’s monitor code in the space provided. You may add/remove
monitor variables as you see fit, but be sure to indicate their initial state.You may NOT change
the threads’phasecomp()function.
Page 3 of 5
(c) (3 points) Does your classmate’s original solution work if the monitor were aMesa-typemonitor?
Why or why not?
8. (10 points) A system has 4 processes{P
0
, P
1
, P
2
, P
3
}, and three shared resources{A, B, C}with 4, 3,
and 4 instances of each resource respectively.
AllocationMaxStill NeedsAvailable
ABCABCABCABC
P
0
201213
.
P
1
101102
P
2
000303
P
3
021122
(a) (5 points) Is the system in a safe state? Run the safety algorithm to determine if it is or not.
Explain your results.
(b) (5 points) Say processP
0
makes a request for (0,1,1). Use the Banker’s algorithm to determine
whether or not this request can be safely granted. Give an explanation of your results.
9. (5 points) A system has two adder threads and one waiter thread,T A
1
, T A
2
andT W, running the
associated code below.
1intc o u n t = 0 ;
2voidTA( ){
3c o u n t ++;
4}
5voidTW( ){
6while( c o u n t<2 ) ;
7p r i n t ( ”Done w a i t i n g ! ” ) ;
8}
Give an execution sequence where both adder threads completely execute the TA function, but the
waiter thread gets stuck waiting indefinitely.
10. (8 points) A restaurant has three cooks,C
1
, C
2
, C
3
and one dishwasherD. The kitchen has three
different utensils, a knife, a spatula, and a pan, each of which needs to be washed after use. Each cook
is an expert in cooking some dish, each of which require a different subset of utensils, enumerated in the
table below.
KnifeSpatulaPan
C
1
12
C
2
12
C
3
12
Cooks will always grab their utensils individually, and will never give up a utensil until they have
completed their dish (where they then go into the set of dirty dishes). The cooks grab them in the order
presented in the table above (e.g.,C
3
will try to grab the knife first, and then the pan), they won’t
attempt to grab the second utensil until they have the first. The dishwasher washes one utensil at a
Page 4 of 5
time (chosen at random from the dirty dishes), and waits for one of the chefs to collect it before going
back to wash and bring out another utensil. Assume all utensils start off in the dirty dishes set.
Does this system have a deadlock? If it does, give an execution sequence where it deadlocks. If it does
not, explain which requirement for a deadlock is broken in this system.
11. (8 points) Below is code for a partial solution to the readers-writers problem using aMESA-style
monitor.
1 m o n i t o r rw
mon{
2c o n d i t i o n r e a d e r sg o , w r i t e rg o ;
3b o o l w r i t i n g = FALSE ;
4intr e a d e r s = 0 ;
5intw
r e a d e r s = 0 , ww r i t e r s = 0 ;
6p r o c r e a d e re n t e r ( ) ;
7p r o c r e a d e r
e x i t ( ) ;
8p r o c w r i t e re n t e r ( ) ;
9p r o c w r i t e re x i t ( ) ;
10}
11
12 p r o c w r i t e r
e n t e r ( ){
13while( w r i t i n g||r e a d e r s>0 ){
14ww r i t e r s ++;
15w a i t ( w r i t e r
g o ) ;
16ww r i t e r s−−;
17}
18w r i t i n g = TRUE;
19}
20
21 p r o c w r i t e r
e x i t ( ){
22i f( wr e a d e r s>0 ){
23s i g n a l ( r e a d e r sg o ) ;
24}else i f( ww r i t e r s>0 ){
25s i g n a l ( w r i t e r sg o ) ;
26}
27w r i t i n g = FALSE ;
28}
The threads will execute the following code:
voidw r i t e r
t h r e a d ( ){
while( 1 ){
w r i t e r
e n t e r ( ) ;
// write to document
w r i t e re x i t ( ) ;
// do something e l s e
}
}
voidr e a d e r
t h r e a d ( ){
while( 1 ){
r e a d e r
e n t e r ( ) ;
// write to document
r e a d e re x i t ( ) ;
// do something e l s e
}
}
On the solution sheet, implement code for thereader
enterandreaderexitmonitor procedures. You
may add condition variables/helper variables as you deem necessary, but be sure to give their initial
state.
Page 5 of 5
