COMP450 Concurrent Programming Assignment

 

Designs due Friday, January 31, 2003

Implementation due by Friday, February 7, 2003

 

Solve any four of the following concurrent programming problems.  You may use C, C++, C# or Java.  You may use semaphores, monitors or synchronized methods.  Your solutions do not have to compile, just give an outline of the program.  Do not worry about showing data manipulation in detail (i.e. you can write “put on queue” instead of detailing how this is done).  Show how you handle concurrency.

One of the problems must be implemented.  This one problem has to compile and run.  Email the source code of your solution to your instructor.  Only a limited number of students may implement each problem.  You must register the program you will implement by sending email to williams@ncat.edu

Sock matching – There are several threads that make socks.  Each sock is one of four colors.  The socks are then passed to a matching thread.  The matching thread finds two socks that are the same color.  It then passes the pair of socks to the washer thread.  The washer thread destroys the socks.

Game show program – This program asks the user a series of questions.  If they answer each question correctly in 10 seconds, they score a point.  If they answer the question incorrectly or if they do not answer the question within 10 seconds, the correct answer is displayed and they do not score any points.  After getting an answer or running out of time, the next question is displayed.

Sensors - Consider a real time shared memory system with ten threads that continually read sensors.  After any combination of 100 sensor readings, an analysis thread must run to check the results.  The analysis takes a relatively long time, so a separate thread must do it.  The two types of threads are show below.  Write the code for the save_result and the get_stuff functions.

sensor threads                    analysis thread

loop forever{                  loop forever {

     x = sensor value;              get_stuff( *results );

     save_result(x);                analyze results;

     }                              }

 

Ying/Yang - To keep cyberspace in harmony, there must be a balance of ying and yang.  In a concurrent shared memory system of many threads, some threads will call the ying function and some will call the yang function.  When a thread calls the ying function, it can not return unless another thread calls the yang function.  Similarly a thread calling the yang function will be suspended until the ying function is called. There will always be an equal number of threads returning from ying and yang.  If one function is called more than the other, the extra threads must be suspended until a balancing number of calls are made to the other function.  Think of these functions as gate keepers that only let threads through in pairs.

                                          ying

                                                                                               

                              yang


Simple Leader Election – Assume a system with N threads.  Each thread has an identifying name.  At a given time, the threads need to select one of the threads as a leader.  All of the threads will call a function elect(myname)  which should return the name of the leader.  You can use any algorithm that selects one and only one thread as the leader.

Ordered Leader Election – Assume a system with N threads. Each threads has an identifying name and an integer rank value.  Threads do not previously know the rank value of other threads.  All of the threads will call a function oelect(myname, myrank) which should return the identifier of the leader.  The thread with the largest rank value is to be selected as the leader.  You can use any algorithm that selects one and only one thread as the leader.

Smoker’s (2-out-of-3) problem - Three chain smokers are together in a room with a vendor of cigarette supplies.  To make and use a cigarette, each smoker needs three ingredients: tobacco, paper, and matches, all of which the vendor has ample supply.  One smoker has his own tobacco, a second has his own paper, and the third has her own matches.  The action begins when the vendor puts two of the ingredients on a table.  (Note: the vendor does NOT know which smoker wants which items.)  When the appropriate smoker is done, he or she wakes up the vendor, who the puts down two more ingredients (randomly), unblocking another smoker.  Write this program with at least four threads, one for each smoker and another for the vendor.

Job shop - Four people are sharing the use of tools - a hammer and 2 mallets - to manufacture small components.  Each object is made by driving a peg into a block.  A pair, consisting of a peg and a block, is referred to as a job.  The jobs arrive sequentially on a conveyer belt and completed jobs depart on a conveyer belt.  The job shop could involve any number of workers called jobbers, sharing more or fewer tools.  The jobs that arrive at the conveyer have varying degrees of difficulty: easy, moderate, hard.  An easy job requires no tool (manual), a moderate job can use either a hammer or mallet, but a hard job requires a hammer.  Jobbers may therefore compete for the use of the hammer and mallet, as well as who takes the next job.  Implement this problem with at least four jobber threads.

Matrix Multiplication – Write a method matmult(float A, float B, float C, int m, int n, int p) that multiplies the m x n matrix A by the n x p matrix B to give the m x p matrix C.  To make the program execute faster in a multiprocessor environment, use four processes to speed up the execution.

Networked philosophers - This is an extension of the dining philosophers problem.  Consider an arbitrary connected graph.  Each node shares a resource with its neighboring nodes.  After a random amount of time, a node in the system wants to acquire all of the resources it shares with all of its neighboring nodes.  It holds the resources for a while and then releases all of them.  Write a program to simulate the actions of the nodes.  Assume that each node is a thread.  All of the nodes know who their neighbor's are.

 

Challenge problem

Solve another problem.  Make sure you identify which problem you are doing as a challenge problems.