Parts of this assignment have been given before, and so there is increased temptation for you to hand-in someone else's work. Still, I have decided to give it to you because it is (in my opinion) an excellent hands-on learning experience WRT process synchronization. Please do your own work - otherwise you gain nothing from this assignment (which will be reflected on your final exam) and you risk being caught. I think it's a fun assignment., I hope you enjoy it.
This assignment is meant to make you think a little more about process synchronization and the interaction of the operating system with code containing race conditions. This assignment will also get you used to using pthreads. You can find the source to pthreads in ~cs315/pub/pthreads. Please look there and read the documentation. The documentation can be found on the web pages under the Student Functions icon - then under pthreads documentation Take a look. In the pthreads directory you will find many source files. Most are the O/S source files. You are welcome to take your own copy of all the files in this directory. This way you can modify them if you wish (though you will not do so for this assignment). There is also a file called app.c. This is the application that the O/S runs. The makefile is set up to compile the O/S source files, archive them into pthreads.a, compile the application file, and then link the application with the archive. If you want to distribute your application over several source files you will have to modify the makefile. You can ask lots of questions about pthreads in class and in tutorials.
This assignment contains three parts, and asks you some questions that I'd like you to answer along the way (and to submit your answers with your solution to the assignment). But before you begin the first part, please look at the pthreads directory, read the pthreads documentation, look over and compile the application, and generally play around with pthreads until you get used to it.
For this part, I want you to imagine that you are planning to host a small party. You've invited several people who may or may not like each other. In order to predict the social interaction, you are going to create a simulation that determines each person's ideal position at the party. For example, Alex may have a crush on Judy and want to spend the evening within 1 meter of her. This may not suit Judy, who finds Alex a little annoying, but would rather catch up on old news with Amanda. Write a pthreads program that will simulate people's movements at the party by having a process for each guest.
Now you may find this example a little contrived, but it shows the concept of parallel execution, and synchronous access to shared data. Besides which, it does computer scientists good to think about social interaction for a change.
Assume the room is a rectangle and each location can be identified in terms of an x-y coordinate.
Each guest has an ideal distance from each other guest and the refreshment table. You could keep this information in an array, which is read in from a file at the beginning of the program.
Each guest also has a initial location (specified by an x-y coordinate description), which may be specified or randomly selected.
At random time periods, each guest makes a decision about whether to move one square or stay in the same place. The decision of where to move is determined by their unhappiness level. The unhappiness level is the sum of the differences between the ideal distance and the current distance from each guest.
(i.e. unhappy = (x(i) - x(j))2 + (y(i) -y(j))2)
There are 9 possible moves on a rectangular grid. Choose the move that minimizes the sum of the unhappiness factor (in effect maximizes happiness). Each guest contributes to the unhappiness of the current guess, so you must add each of these to get a total unhappiness factor for each new possible move. Note, the refreshment table does not move.
In your own words, answer the following question:
Do not worry about having a nice Graphical Output for this program. If I have time, I may write some a function that allows you to draw the party floor plan at some point in time. This is an operating systsems course, so the synchronization problem is what I want you to focus on.
NEW INFORMATION: In order to have a consistent interface for the marker, it is necessary to determine the standard method of getting the detailed information to the program. This will be via command line arguments and an input file. The way to invoke your party program is the following:
% party rows columns datafile
The format of the datafile is as follows:
numguests tabletop, tableleft, tablebottom, tableright "guestname", initial-x, initial-y, d0, d1, d2, ..., d(n-1), d(table)
e.g. 4 13, 15, 17, 16 "Fred", 12, 3, 6, 2, 1, 1 "Barney", 36, 4, 5, 4, 4, 5 "Wilma", 19, 27, 8, 8, 6, 3 "Betty", 19, 19, 10, 2, 1, 7
Use semaphores to ensure mutual exclusion for the critical sections created in part 1 above. Test your code to be sure that you have fixed the race condition. Please answer the following question:
Extra Credit: Implement a solution that gives some processes a higher priority than others by having a different amounts of time pass between move decisions are made (i.e. someone gets hungry and must move to the food table quickly).
For this part, you are going to create a Monitor service. Once this service is implemented you are going to use it to solve the following critical section problem. You are to write four routines (plus an initialization routine if you desire) that can be called by applications wanting to use the monitor service. Clearly these need some way of stopping and starting processes. For this, you are going to use the IPC system calls Send(), Receive() and Reply(). The first two routines are obvious:
These implement wait and notify. MonWait is as described in class and the notes. Notify is exactly the same as Signal, except in the case of Notify the process being resumed (that previously did the MonWait) does not re-enter the monitor until the notify-ing process is done and leaves the monitor (by doing a MonWait or MonLeave). In the case of Signal, the signalling-ing process left the monitor as a result of doing the Signal, and the resumed process was let in right away. Both routines require a single parameter indicating the condition variable. We will use the integers in the range 0 to (NumbConds - 1) to represent condition variables. NumbConds is a compile-time constant. Both routines return 0 in the normal case and -1 if some error has been detected. Remember the logic of wait and notify: a process executing *wait* leaves the monitor and is suspended. A process executing *notify* resumes one waiting process, or does nothing if there are no waiting processes. If there is a process to be resumed, then it is resumed once the notify-ing process leaves the monitor by calling MonLeave or MonWait. If a process calls MonNotify more than once, then that many waiting processes are resumed (if there are that many) one at a time.
The other two routines are as follows:
Because we don't want to be modifying the C language, monitor subroutines all must begin with a call to MonEnter(), and end with a call to MonLeave(). The application programmer must ensure that each monitor routine has exactly one call to each (MonEnter() being the first statement executed by each monitor routine, and MonLeave() being the last statement executed by each monitor routine). Both routines return 0 on success, and -1 if some error was encountered. These routines indicate the entry and exit of a process from the monitor.
Finally, you may (if you find it necessary) write a routine to perform initialization of the monitor service. If you do so, call this routine MonInit, and pass it NumbConds as a parameter as follows:
The monitor routines for this solution should be the bodies of the incrementing and decrementing processes. Thus the processes, once started, should each make one call to their respective monitor routines. In order to ensure that one process does not hog the monitor, synchronize the processes (using MonNotify and MonWait) so that the value of count never goes any higher than 10, nor any lower than -10.
Now, for the problem to solve. Here it is again, the Producer-Consumer in a slightly simplified form.
Each process will execute a loop N times. N should be an integer command-line argument to your executable. These two processes share an integer variable, count, which is initialized to 0. Your program should proceed as follows:
The body of the producer's loop contains the following code:
{
int temp;
int x = 5000;
temp = count; /* count is shared, temp is local to the producer */
while(x--); /* small delay */
temp++;
count = temp;
}
The body of the consumer's loop contains the following code:
{
int temp;
int x = 5000;
temp = count; /* count is shared, temp is local to the consumer */
while(x--); /* small delay */
temp--;
count = temp;
}
Essentially, the producer is producing integers, and the consumer is consuming them. Note that there is no synchronization between the producer and consumer. This is an unprotected critical section.
The monitor routines for this solution should be the bodies of the incrementing and decrementing processes. Thus the processes, once started, should each make one call to their respective monitor routines. In order to ensure that one process does not hog the monitor, synchronize the processes (using MonNotify and MonWait) so that the value of count never goes any higher than 10, nor any lower than -10.
cd ~ -- changes to your home directory
handin cs315 a2handin -- gives a copy of the files in ~/cs315/a2handin to
the TA
As above.
Much of this assignment should be fun - I hope you find it so. At the very least, I know you will find it to be an excellent learning experience.
Have fun! - Dwight