Concurrent Programming Homework Solutions

Below are my solutions to the homework questions. I believe that they are correct although that has not been verified. Challenge point credit will be given to the first individual who finds an error.

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.

semaphore q1m = 1, q1size = 0, q2m = 1, q2size = 0;

 

sock_maker {

      do forever {

            make a sock;

            p(q1m);                 // lock the first queue

            put the sock on the first queue;

            v(q1m);                 // unlock the first queue

            v(q1size);              // let matcher run

      }

}

 

matcher {

      do forever {

            p(q1size);              // wait for a sock to be available

            p(q1m);                 // lock the input queue

            get a sock from the first queue;

            v(q1m);                 // unlock the input queue

            if (we already have this color) {

                  p(q2m);

                  put the matched pair on the 2nd queue;

                  v(q2m);

                  v(q2size);

            } else {

                  save this sock for later;

            }

      }

}

 

washer {

      do forever {

            p(q2size);              // wait for socks to be available

            p(q2m);                 // lock the 2nd queue

            get a pair of socks from the queue;

            v(q2m);                 // unlock the 2nd queue

            lose 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.

 

semaphore s = 0;              // synchronize print and read threads

int   currentQuestion = 0;    // number of last question printed

int   done = 0;               // true if all done

int   response;               // answer from user or TIMEOUT

 

printQuestion thread {

      start reader_thread;

      for (i = 0; i < 10; i++) {

            print question[i];

            currentQuestion = i;

            start timer_thread(i);        // start timer thread

            p(s);                         // wait for answer or timeout

            answer = response;            // save response from user

            print “correct”, “wrong” or “timeout”

      }

      done = 1;

}

 

reader_thread {

      for (i = 0; i < 10; i++) {

            if (done) thread_exit();      // check for end of program

            read answer;

            response = answer;            // move answer to global variable

            v(s);                         // release printer thread

      }

}

 

timer_thread(int qnum) {

      sleep(10);                          // wait 10 seconds

      if (qnum == currentQuestion) {      // still waiting for this question?

            response = TIMEOUT;           // put TIMEOUT value as response

            v(s);                         // release printer thread

      }

}

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

semaphore mutex = 1, workonit = 0;
int num_data = 0; /* number of readings collected */

save_result(x) {
    p(mutex);
    save x;
    num_data++;
    if (num_data == 100) v(workonit); /* start analysis */
    v(mutex);
    }

get_stuff( *results ) {
    p(workonit); /* wait for 100 readings */
    p(mutex);
    copy all the data;
    num_data = 0;
    v(mutex);
    }

 

Ying/Yang - To keep cyberspace in harmony, there must be a balance of ying and yang. In a concurrent shared memory system of many processes, some processes will call the ying function and some will call the yang function. When a process calls the ying function, it can not return unless another process calls the yang function. Similarly a process calling the yang function will be suspended until the ying function is called. There will always be an equal number of processes returning from ying and yang. If one function is called more than the other, the extra processes 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 processes through in pairs.

semaphore black = 0, white = 0;

void ying( ) {
    v(black);
    p(white);
    }

void yang( ) {
    v(white);
    p(black);
    }

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. When the appropriate smoker is done, he or she wakes up the vendor, who the puts down two more ingredients (randomly), unblocking another smoker.

semaphore avail = 0, donesmoking = 0;

vendor {
    put two items on the table;
    v(avail); /* activate 1 smoker */
    p(donesmoking); /* wait until the smoker is done */
    }

smoker { /* there will be three of these tasks */
    p(avail);
    if (this smoker needs both items) {
        smoke;
        v(donesmoking);
        }
    else {
        v(avail); /* wake up another smoker */
        }
    }

Java solution

public class Smokers {
        private Object avail = new Object();
        private Object donesmoking = new Object();
        private table;
 
public synchronized void vendor() {
        put two random items on the table
        avail.signal();                // wake up a smoker
        donesmoking.wait()             // wait for smoker to finish smoking
}
 
public synchronized void smoking() {  // three of these are started
        avail.wait();                  // wait for something on the table
        if (table contains all that I need) {
               smoke();
               donesmoking.signal();  // tell vendor to do it again
        } else {
               avail.signal();        // wake another smoker
        }
}
}

Jobshop - 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 jobshop 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.

semaphore hammer = 1, mallet = 2;
semaphore jobstodo = 0; /* number of jobs available */
semaphore mutex = 1;

do forever {
    p(jobstodo);
    p(mutex);
    get next job from conveyer;
    v(mutex);
    switch (job.difficulty) { /* get necessary tool */
        easy: break;
        moderate: p(mallet);
            break;
        hard: p(hammer);
            break;
        }
    assemble the job;
    switch (job.difficulty) { /* release tool */
        easy: break;
        moderate: v(mallet);
            break;
        hard: v(hammer);
            break;
        }
    }

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

name winner; /* name of the new leader */
boolean elected = FALSE;
semaphore mutex = 1;

elect(myname) {
    if (elected == TRUE) /* atomic access to shared variable */
        return winner;
    p(mutex);
    if (elected == FALSE) {
        winner = myname;
        elected = TRUE;
        }
    v(mutex);
    return winner;
    }

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

name winner; /* name of the new leader */
int best = -
¥ ;
int num_votes = 0;
semaphore mutex = 1, wait = 0;

oelect(myname, myrank) {
    p(mutex);
    if (myrank > best) {
        best = myrank;
        winner = myname;
        }
    num_votes++;
    if (num_votes < N) {
        v(mutex);
        p(wait); /* wait for all to vote */
        }
    else {
        v(mutex);
        for (i = 0; i < N-1; i++)
            v(wait); /* release all waiting */
        }
    return winner;
    }

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.

 

matmult(float A, float B, float C, int m, int n, int p){

      for (i = 0; i < 4; i++) {

            start thread partialmatmult(A,B,C,m,n,p, i*m/4, m/4);

      }

      for (i = 0; i < 4; i++) {

            join thread i;

      }

}

 

partialmatmult(float A, float B, float C, int m, int n, int p,

int firstrow, int numrow) {

      // Compute numrows of the matrix C starting with row firstrow

}

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 task. All of the nodes know who their neighbor's are.

Each node has a list (size N) of its neighboring nodes with which it shares resources. This list must be sorted in alphabetical order. When a node wants to use the resources, it must acquire them in order. This avoids possible deadlocks that could occur if they randomly lock resources.

semaphore neighbor[N] = 1;

do forever {
    think;
    for (i = 0; i < N; i++)
        p(neighbor[I]);
    eat;
    for (i = 0; i < N; i++)
        v(neighbor[I]);
    }