|
CS361 Concurrent Programming Fall 2001
Exercise 15A
Working in groups of one, two or three, pick one of the following things to do. Submit your work into the group area under webCT, making sure that commentary in the files as well as the directory names clearly indicate who worked on a particular submission. 1. Do an implementation of a simulation of the Halloween problem you started last time, in the Hartley style. (3 points = working, tested implementation free of major defects, 2 points = working implementation not passing all tests but with all essential ingredients for correct solution present, 1 point = fully detailed layout of simulation behavior, but not yet compiling nor correctly executing). We reproduce the description of the problem below. The Halloween problem. Trick or treaters visit a home on Halloween. Some of the children want candy, others are collecting money for a charity. Sadly, many more are interested in getting candy than collecting for charity. Some of them want to do both, of course. There are two parents at the house who can hand out treats. There are two bowls of candy and and one jar of coins that they can use. The children arrive at the house in groups, with a random numbers in the group wanting candy, others wanting money. Thus, it’s possible for the two parents to give out candy to two children at once, or one to give money and one to give candy (or only one, or none) to serve. Because it takes time to switch between the bowl of candy and the jar of coins, a parent would like to serve as many before switching, but of course not to the point of causing a starvation condition for the coin seekers. Using semaphores, develop a solution to this problem that is correct, works well with concurrent action. You need not guarantee optimal service for the children, but avoid long waiting times. 2. The four little pigs. Four pigs graduated from college and now need to make their way in the world. They say goodbye to their mother, and strike off to a new life. They hitchhike a ride with a few truckers (Hatfields and Oscar Meyers truckers seemed to be particularly fond of stopping for them). Eventually they arrive in Kansas and find a spot to settle. The first order of business is to build their homes. Each pig builds their own home. One pig decides to build a house out of mud (adobe). A second pig decided to build a house out of mud, and straw. The third decided to build a house out of mud, straw, and bricks. The fourth will build a house out of bricks and concrete. They plan to build their houses next to each other, so they get a communal (and essentially infinite) supply of mud, straw, bricks, and concrete (although only the last pig is going to use the concrete). However, since they were all philosophy majors in college, they have rigged things so that each of the mud, straw, and bricks can be accessed by only one pig at a time. A pig must access all of their supplies simultaneously in order to do some building. For example, the second pig’s building loop would be (want to build more – get a lock on mud and on straw – build some – release locks – take a break – repeat cycle). Design a simulation to the construction activity,
using semaphores. You need not
produce working Java code, but for full credit you should give the full
pseudocode describing the use of data structures, classes, and semaphores. Explain why your code allows good concurrency,
is correct, and avoids deadlock. Also
explain whether or why your code prevents starvation with or without convention. CS361 Concurrent Programming Spring 2002 Exercise #4A 1. As a
group, determine the answer to the following question:
On queen, a machine with 4 processors, 4 threads are programmed
to do “N=N+1;” concurrently.
If N is initialized to 47 before the threads are started up, what
are all the possible values for the result after the 4 threads
do their operation? Develop a few Powerpoint slides or Word document
that describe a scenario for each of the possible outcomes in a fashion
similar to the lecture slides. Appoint one person from the group as a
scribe. Connect their laptop to
a projector so that you can show the work as it is being developed and/or
integrated to everyone in your group. 2. Break up your group into two teams, corresponding
to who’s sitting on a particular side of the table. One team should work on problem A below, the
other on problem B. One problem
is probably a bit easier than the other so you may assign the work according
to the relative strengths of the two teams. Using Visual Café or a combination of emacs and command-line invocation of java/javac , write a version of the program that subclasses Thread on the laptop (do not use Unix for this).Use the version of threads where you use an object that implements Runnable as one of the parameters to the Thread constructor. Now create programs that do the following variations: a program that outputs ping pong ping pong ping pong , and a program that outputs pong ping pong ping pong ping.
b) Write a Java program that starts up a program that starts up three threads. The first prints “A” the next prints “B” and the third prints “C”. The program halts after all three threads have finished. Using Visual Café or a combination of emacs and command-line invocation of java/javac , write a version of the program that subclasses Thread on the laptop (do not use Unix for this). Use the version of threads where you use an object that implements Runnable as one of the parameters to the Thread constructor. Can you use the basic thread operations to have the threads do the following output: A B B C C C? What about ping A B C C B A? Show your output of the various programs to the instructor. Deposit the files into the Exercise4 subdirectory of your group. Be sure to put the names of the participants in the comments for the program. When your group has finished parts a) and b), call over the instructor, who will award you 3 points for a solid working program, 2 points if the program has noticable and significant weaknesses, 1 point if you were unable to finish the program but are within 20 minutes of doing so. When you are done, upload your answers into the webCT shared area for your group. |