Implementation of Monitor

The goal of this problem is to solve an inter-thread communication problem called Sleeping Stylist using semaphores.
There are 40 customers but only 1 stylist in a hair salon. In the salon, there are 5 chairs that customers can sit and
wait for the stylist. Since there is only one stylist, only one customer can get a haircut at a time. If there are no
customers in the salon, the stylist sleeps. When a customer enters the salon, he/she wakes up the stylist and then
waits for the stylist to get ready. The stylist then takes the customer. If the stylist is busy with a customer and more
customers arrive, they sit and wait in the 5 waiting chairs. If a customer enters the salon and it is full (there are
already 5 waiting customers while a customer is getting a haircut), the customer leaves to go shopping and then
comes back later to try to get a haircut again. Every customer must eventually get a haircut (no starvation).
When the stylist nishes with a customer, it takes the next waiting customer. If there are no waiting customers,
the stylist goes back to sleep. The pseudocode is given in Figure 1. Note that the pseudocode only suggests a
guideline. Feel free to add more parameters, variables, and functions as you think necessary.
You will use the pthread package to create 40 customer threads and 1 stylist thread. The program will be
called “sleepingStylistSem.c”. Use a delay loop to slow down each thread (see the pseudocode) by adjusting the
loop bound so that you get a steady stream of customers to compete to get haircuts by the stylist. You want to
ensure that your program can demonstrate its operation when the salon is not full and when the salon is full. Also
make sure that we can see the gradual build up of customers waiting in the chairs. You must complete your
work in csce.unl.edu. Use POSIX semaphore (sem init, sem get, sem post, etc.). Also note that OS-X unlocks
semaphores differently.
3
Sleeping Stylist with Monitor (40 pts)
The goal of this problem is to create your own monitor to provide synchronization support for the sleeping stylist
problem. You will use the pthread package to create 40 customer threads and 1 stylist thread. There are 5 waiting
chairs in the salon. You then need to use a semaphore to create your entry queue.
You also need to create your own Condition Variables (CVs). That is, you CANNOT USE the CV type
provided by the pthread library (e.g., pthread cond init). Condition variables are used to suspend processes or
threads that cannot continue executing due to a specic monitor state (e.g. the stylist is busy). They are also used
to awaken suspended processes or threads when the conditions are satisable. To create your own CVs, follow the
following steps:
1. You will create a new variable type called CV. To do this, you will create a new structure called cond.
The structure consists of an integer variable that indicates the number of threads blocked on a condition
variable and a semaphore used to suspend threads. Your implementation must follow the signal-and-wait
discipline. If your implementation follows a signal-and-continue discipline, you would automatically
lose 20 points. There are three operations that your CV will support. They are:
(a) count(cv)—returns the number of threads blocked on the cv.
(b) wait(cv)— relinquishes exclusive access to the monitor and then suspends the executing threads.
/ ==== s l e e p i n g S t y l i s t S e m . c ====//
# d e f i n e CHAIRS 5
# d e f i n e DELAY 100000 / /
a d j u s t
t h i s
v a l u e
s e m a p h o r e mutex = 1 ,
s t y l i s t = 0 c u s t o m e r s = 0 ;
i n t
w a i t i n g = 0 ;
v o i d main ( v o i d )
{
/ /
c r e a t e 40 c u s t o m e r
t h r e a d s and 1
s t y l i s t
t h r e a d
/ /
don ’ t
f o r g e t
t o
j o i n
t h r e a d s
}
v o i d
s t y l i s t ( v o i d )
{
i n t
j ;
w h i l e ( 1 ) {
down(& c u s t o m e r s ) ;
down(& mutex ) ;
w a i t i n g = w a i t i n g 1 ;
up (& s t y l i s t ) ;
up (& mutex ) ;
f o r ( j = 0 ; j < DELAY ;
j + + ) ;
/ /
c u t
h a i r
}
}
v o i d c u s t o m e r ( v o i d )
{
i n t
j ;
w h i l e ( 1 ) {
down(& mutex ) ;
i f
( w a i t i n g < CHAIRS) {
w a i t i n g = w a i t i n g + 1 ;
up (& c u s t o m e r s ) ;
up (& mutex ) ;
down(& s t y l i s t ) ;
break ;
}
e l s e {
up (& mutex ) ;
f o r ( j = 0 ; j < DELAY ;
j + + ) ;
/ /
go s h o p p i n g
}
}
}
Figure 1: Pseudo-code for the sleeping stylist problem using semaphores
(c) signal(cv)—unblocks one thread suspended at the head of the cv blocking queue. The signaled thread
resumes execution where it was last suspended. The signaler exits the monitor and suspends itself at
the entry queue
.
You should pay special attention to the following questions during your implementation:
(a) How would you guarantee that only one thread is inside the monitor at one time?
(b) How would you make sure that a suspended thread (due to wait) resumes where it left off?
(c) How would you initialize the necessary data structures to support your monitor and make them visible
to all threads?
(d) How would you produce the necessary debugging information that you can use to verify the correctness
of your implementation? For example, what output will you need to show that your implementation
follows the signal-and-wait discipline and not signal-and-continue. How can you show that the num-
ber of waiting threads and the corresponding counter is consistent? How can you show how many
customers have already got their haircuts and how many are still trying? Remember, you’ll need to
convince the grader that your implementation follows our specication precisely.
2. You will create function mon checkCustomer that manages the waiting list and takes a customer to the
styling chair. It rst invokes signal on condition variable stylistAvailable to indicate that the stylist is not
busy. If the salon is empty, it then invokes wait on the condition variable customerAvailable to put the
stylist to sleep.
3. You will create function mon checkStylist that puts a customer on the waiting list if the salon is not
full. If the stylist is sleeping or busy, it rst invokes wait on the condition variable stylistAvailable. It also
invokes signal on condition variable customerAvailable to indicate that a customer is waiting.
4. You will create function customer, stylist, and salonState.
Note that the pseudocode given in Figure 2 provides a guideline on how to program your monitor. However,
this pseudo-code may have incorrect logics. It is part of your responsibility to identify faults and implement a
correctly working monitor.
These functions and your CVs will be implemented in a separate C le. Thus, you should at least have two C
source les, monitor.c and sleepingStylistMon.c. You can compile monitor.c using -c ag (e.g. gcc -c monitor.c).
This will give you the object le (monitor.o) that can be linked to your sleepingStylistMon.c (gcc sleepingStylist-
Mon.c monitor.o). You must complete this part in csce.unl.edu.
4
Submission (10 pts)
Create a zip le that has all your solutions and submit it through canvas. The step to create proper directory
structure is as follows:
1. Create a directory called lastname hw3 (replace lastname with the submitter’s lastname). If you are working
with your partner, only one submission is needed.
2. Create subdirectories: prob1 and prob2 under lastname hw3.
3. Place your solutions in the proper directory. Provide README.txt le for each problem. To earn 10 points,
each README le should:
Provide the name of every member on your team.
Specify the instruction on how to test your solution.
Document the amount of time you spent on each problem.
Quantify the level of challenge from 0 to 5 (5 is most difcult) for each problem.
4. Once all solutions are properly stored, zip the folder lastname hw3 and submit the zip le through canvas.
Note that canvas will only take .zip extension. If you use other means to compress your le, the system will
not accept it. You can use “zip -r” command in csce.unl.edu to zip your folder.
/ / ==== s l e e p i n g S t y l i s t M o n . c ====//
# d e f i n e DELAY 100000 / /
a d j u s t
t h i s
v a l u e
v o i d main ( v o i d )
{
/ /
c r e a t e 40 c u s t o m e r
t h r e a d s and a
s t y l i s t
t h r e a d
/ /
don ’ t
f o r g e t
t o
j o i n
t h r e a d s
}
v o i d s a l o n S t a t e ( v o i d )
/ /
p r i n t how many c u s t o m e r s a r e
w a i t i n g
{
/ /
p r i n t
t h e
s t a t e
o f
t h e
w a i t i n g
c h a i r
u s i n g
t h e
f o l l o w i n g
/ /
f o r m a t :
f i r s t
u s e d
c h a i r :
l a s t
u s e d
c h a i r :
c o u n t
\n .
}
v o i d
s t y l i s t
( v o i d )
{
/ /
add more v a r i a b l e s
a s n e e d e d
i n t
j ;
w h i l e ( 1 ) {
s a l o n S t a t e ( ) ;
m o n c h e c k C u s t o m e r ( ) ;
f o r ( j = 0 ; j < DELAY ;
j + + ) ;
/ /
c u t
h a i r
}
}
v o i d c u s t o m e r ( v o i d )
{
/ /
add more v a r i a b l e s
a s n e e d e d
i n t
j ;
w h i l e ( 1 ) {
s a l o n S t a t e ( ) ;
i f
( m o n c h e c k S t y l i s t ( ) )
break ;
f o r ( j = 0 ; j < DELAY ;
j + + ) ;
/ /
go s h o p p i n g
}
}
/ / ===== m o n i t o r . c ===== / /
# d e f i n e CHAIR 5
c o n d s t y l i s t A v a i l a b l e ,
c u s t o m e r A v a i l a b l e ;
i n t c u s t o m e r = 0 ;
i n t
s t y l i s t = 0 ;
/ /
add more v a r i a b l e s
a s n e c e s s a r y
( e . g . a s e m a p h o r e f o r
e n t r y q u e u e )
v o i d m o n c h e c k C u s t o m e r ( )
{
s t y l i s t = s t y l i s t + 1 ;
s i g n a l ( s t y l i s t A v a i l a b l e ) ;
/ /
s t y l i s t ’ s r e a d y t o
c u t
h a i r
i f
( c u s t o m e r == 0 )
/ /
do n o t u s e w h i l e
h e r e
w a i t ( c u s t o m e r A v a i l a b l e ) ;
c u s t o m e r = c u s t o m e r 1 ;
}
i n t
m o n c h e c k S t y l i s t ( )
/ /
T h i s
f u n c t i o n may h a v e
f a u l t s .
/ /
I f
y o u t h i n k
i t
d o e s ,
y o u ’ l l
n e e d t o
f i x
i t .
{
i n t
s t a t u s = 0 ;
i f
( c u s t o m e r < CHAIRS) {
c u s t o m e r = c u s t o m e r + 1 ;
s i g n a l ( c u s t o m e r A v a i l a b l e ) ;
i f
( s t y l i s t == 0 )
/ /
do n o t u s e w h i l e
h e r e
w a i t ( s t y l i s t A v a i l a b l e ) ;
s t y l i s t = s t y l i s t 1 ;
s t a t u s = 1 ;
}
r e t u r n
s t a t u s

Leave a Reply

Your email address will not be published. Required fields are marked *