CIT 595 Spring 2011

Homework #2

Due Mon Feb 7 1:30pm


Introduction

In this assignment, you will develop a multi-threaded program that simulates the flow of patients through a hospital emergency room. Each patient is represented using a single thread, and goes through a sequence of steps (check in, assess, treat, reassess, check out) as he or she is treated in the ER. Each step requires one or more "resources" (doctors, nurses, beds, desk clerks), which are limited, such that some patients have to wait while others are being taken care of.

In addition to developing this simulation, you will measure the effect of varying the number of resouces, to see how they impact patient waiting time and cost.

In some parts of this assignment, you will need to write C code; in others, you will need to provide written solutions. All submissions should be electronic for this assignment, as described below.


Before You Begin

The program hospital.c provides the skeleton code that you need to modify in order to complete this assignment. You should not change the signatures (name, return type, parameter list) for any of the functions that are provided. However, you may add other functions if necessary (though, honestly, you probably shouldn't need to).

If you compile and run this code, you will see that a single patient "arrives" at the ER, goes through the five steps, and then departs.


Part I (5 points)

Modify the skeleton code so that the "main" function creates 10 threads, each of which starts at the "arrive" function and passes a unique integer ID (preferably starting at 0 and increasing in order) to that function. The number of threads should, of course, be easily configurable, e.g. through a global variable. These 10 threads will represent the 10 patients, each of which goes through the steps of the ER simulation separately.

When you run your simulation, you should see each thread print out its ID as it reaches each step, and ultimately see the "good bye" message for each patient. If you don't see the "good bye" message for all 10 patients, it's likely that your "main" thread terminated too early.

 

Part II (10 points)

Modify the code from Part I to represent the different resources in the simulation by using semaphores. In this part of the assignment, you only need to set up the different semaphores you will use, you do not need to actually use the wait and post functions (yet). There are four resources: Nurses, Doctors, Desk Clerks, and Beds. For now, configure your code so that there are 6 Nurses, 2 Doctors, 1 Desk Clerk, and 6 Beds. These should also be easily configurable, e.g. by using a global variable.

 

Part III (15 points)

Now the tricky part. Further modify the code such that each step in the simulation checks to see if the required resources are available, and waits for one to be freed up if need be. You should also simulate the amount of time it takes for each step to be completed once the resources are available (hint: use the "sleep" function), according to the following table:

Step Resource(s) Completion time
Check In Clerk 4
Assess Nurse, Bed 6
Treat Doctor, Bed 10
Reassess Nurse, Bed 5
Check Out Clerk 2

For instance, when a thread gets to the Check In step, it should only proceed if one of the Clerk resources is available. If one is available, then the thread should pause for four seconds in order to simulate four minutes of time spent checking in (we can pretend that one second in our program represents one minute in real time), and then it should proceed. If no Clerk is available, though, the thread must wait for one to be freed up. For the Assess, Treat, and Reassess steps, the thread should only proceed if both resources are available.

Now when you run your code, you should see some delays as the patients go through each step, depending on the different resources and waiting time. Check the output of your program to ensure that all 10 patients go through all of the steps.

Note that this part of the assignment is probably the trickiest, and requires changes throughout the code. Ask one of the members of the instruction staff if you need help!

 

Part IV (5 points)

Using the configuration (number of resources) from Part II, and the code from Part III, run 10 simulations to estimate how long it will take for all 10 patients to go through the ER (yes, I realize that this is kind of unrealistic because all 10 patients "arrive" at about the same time, and then no one else arrives... maybe we'll fix that later!).

As in homework #1, use the Unix "time" command. Use the "real" time that it returns, since the time the threads spend "sleeping" are not included in the "user" and "sys" values.

For this part of the assignment, submit an electronic version of a table that looks like this, with the running time of each test run filled in:

Test: 1 2 3 4 5 6 7 8 9 10 Average
Time:                                                                  

 

Part V (5 points)

Considering your answer for Part IV, what is the approximate average utilization rate for each clerk, nurse, and doctor? The utilization rate is defined as the time a resource spends doing actual work, divided by the total time of the simulation. Use the settings from Part II (number of each type of resource... remember, there are 6 Nurses and 2 Doctors!) and the table from Part III (resources and completion time) to help you answer this question. Hint: if you get a utilization rate of over 100%... that's probably wrong. Be sure to show your work.

 

Part VI (5 points)

Hospitals may use simulations like this to determine the cost impact of varying the different resources, for instance by having more nurses or fewer doctors. Assume that the cost per minute for a single instance of each resource is as follows:

Resource Cost/min
Bed $0.01
Clerk $0.50
Nurse $0.75
Doctor $2.00

Given the average running time of the simulation from Part IV, what is the total cost incurred, assuming that each resource gets paid for the entire duration of the simulation, regardless of whether he or she is actually doing any work? Be sure to show your work.

 

Part VII (5 points)

Realizing that nurses and clerks appear to be the bottleneck, the hospital is considering increasing the number of nurse resources to 8, and the number of clerks to 2. Repeat the simulations from Part IV, and use the table in Part VI to help them determine whether this will cost them or save them money (and how much).

 

Extra Credit! (5 points)

Try to find a resource allocation so that the total cost will be lower than the results of Parts VI and VII. This will involve a bit of tinkering, but think about where the bottlenecks are and the tradeoff between time and cost. Keep the number of patients fixed at 10, though!


Academic Honesty

You must work on this assignment individually. Collaboration is explicitly not allowed. That includes (but is not limited to) working together on the assignment, providing solutions to or receiving solutions from another student, or receiving assistance from an outside source. Whereas it is okay to discuss the intent of the assignment or address other clarification issues with other students, you must not discuss approaches, algorithms, or code.

If you need help with this assignment, please visit a member of the teaching staff during office hours, or contact one of us to set up an appointment.


Submission

Your submission should include one C program (hospital.c), and an electronic version of your writeup, which should be a single .doc, .txt, or .pdf document.

Homeworks are to be submitted via Blackboard, as described on the course overview page. Please tar and/or zip your two files (the .c file and the writeup) into a single submission file.