使用 POSIX Semaphore
解决多线程间的通讯问题，具体需要解决Sleeping Stylist问题。
Sleeping Stylist with Semaphores
The goal of this problem is to solve an inter-thread communication problem
called Sleeping Stylist using semaphores. There are 120 customers but only 1
stylist in a hair salon. In the salon, there are 7 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, the customer 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 7 waiting chairs. If a customer enters the
salon and it is full (there are already 7 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 finishes with a customer, she takes
the next waiting customer. If there are no waiting customers, the stylist goes
back to sleep. The pseudo-code is given in Figure 1. Note that the pseudo-code
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 120 customer threads and 1 stylist
thread. The program will be called “sleepingStylistSem.c”. Use a delay loop to
slow down each thread (see the pseudo-code) 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 empty, 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 should think about the necessary debugging information that you can use to
verify the correctness of your implementation. For example, what output will
show that the number 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 specification precisely.
You must complete your work. Use POSIX semaphore (sem init, sem get, sem post,
etc.). Also note that OS-X unlocks semaphores differently.
Sleeping Stylist with Monitor
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 120 customer threads and 1 stylist thread. There are
7 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). If you use pthread CV, you will get 0 for this part. Condition
variables are used to suspend processes or threads that cannot continue
executing due to a specific monitor state (e.g. the stylist is busy). They are
also used to awaken suspended processes or threads when the conditions are
satisfiable. To create your own CVs, follow the following steps:
Step 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.
//==== sleepingStylistSem.c ====//
#define CHAIRS 7
#define DELAY 1000000 // adjust this value
semaphore mutex = 1, stylist = 0, customers = 0;
int waiting = 0;
void main(void)
{
// create a specified number of customer threads
// and a stylist thread. Don’t forget to join threads
}
void stylist(void)
{
int j;
while (1)
{
down(&customers);
down(&mutex);
waiting = waiting - 1;
up(&stylist);
up(&mutex);
for (j = 0; j < DELAY; j++); // cuthair
}
}
void customer(void)
{
int j;
while (1)
{
down(&mutex);
if (waiting < CHAIRS)
{
waiting = waiting + 1;
up(&customers);
up(&mutex);
down(&stylist);
break;
}
else
{
up(&mutex);
for (j = 0; j < DELAY; j++); // go shopping
}
}
}
—|—
If your implementation follows the signal-and-continue discipline, you would
automatically lose 30 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.
- (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 leftoff?
- (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, in addition to the required information in mon_debugPrint, that you can use to verify the correctness of your implementation? For example, what kind of output will show that your implementation follows the signal-and-wait discipline and not signal-and-continue? How can you show that the number of waiting threads and the corresponding counter is consistent?
Step 2
You will create function mon_checkCustomer that manages the waiting list and
takes a customer to the styling chair. It first 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.
Step 3
You will create function mon_checkStylist that puts a customer on the 7
waiting chairs if the salon is not full. If the stylist is sleeping or busy,
it first invokes wait on the condition variable stylistAvailable. It also
invokes signal on condition variable customerAvailable to indicate that a
customer is waiting.
Step 4
You will create function mon_debugPrint to expose internal states of the
monitor to help with debugging. The specific format of this function is
provided in the pseudo-code.
Step 5
You will create function customer and stylist.
Step 6
Make sure that your program produces an output that clearly shows that it
follows the signal-and-wait discipline. As an example, this can be done via a
simple output statement that shows where each blocked thread resumes its
execution to after it is awaken from the a queue.
Note that the pseudo-code given provides a guideline on how to program your
monitor. However, this pseudo-code may have incorrect logic. 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 file. Thus,
you should at least have two C source files, monitor.c and
sleepingStylistMon.c. You can compile monitor.c using -c flag (e.g. gcc -c monitor.c ). This will give you the object file (monitor.o) that can be
linked to your sleepingStylistMon.c ( gcc sleepingStylist- Mon.c monitor.o
). You must also complete this part. You must also create a Makefile so that
we can automatically compile your code and remove the binaries using make and
make clean commands, respectively.
//==== sleepingStylistMon.c ====//
#define DELAY 1000000 // adjust this value
void main(void)
{
// create a specified number of customer threads
// and a stylist thread. Don’t forget to join threads
}
void stylist(void)
{
// add more variables as needed
int j;
while (1)
{
mon_debugPrint();
mon_checkCustomer();
for (j = 0; j < DELAY; j++); // cuthair
}
}
void customer(void)
{
// add more variables as needed
int j;
while (1)
{
mon_debugPrint();
if (mon_checkStylist())
break;
for (j = 0; j < DELAY; j++); // go shopping
}
}
—|—
Submission
Create a zip file that has all your solutions and submit it through canvas.
The step to create proper directory structure is as follows:
- Create a directory called lastname pa2 (replace lastname with the submitter’s lastname). If you are working with partner(s), only one submission is needed.
- Create sub-directories: prob1 and prob2 under lastname pa2.
- Place your solutions in the proper directory. Provide a README file and a Makefile for each problem. To earn 10 points, each README file should:
* Provide the name of every member on your team.
* Specify the instruction on how to run your solution and what to observe to ensure that it is following the signal-and-wait discipline.
* Document the amount of time you spent on each problem.
* Quantify the level of challenge from 0 to 5 (5 is most difficult) for each problem. - Once all solutions are properly stored, zip the folder lastname pa2 and submit the zip file through canvas.
Note that canvas will only take .zip extension. If you use other means to
compress your file, the system will not accept it. You can use “zip -r”
command to zip your folder.
