Lab 6 Solutions

Ice Cream Parlor was a lecture example created by Jerry Cain.

Before the end of lab, be sure to fill out the lab checkoff sheet here!

Before starting, get the starter code by cloning the lab6 folder:

$ git clone /usr/class/cs110/repos/lab6/shared lab6
$ cd lab6
$ make

Problem 1: Ice Cream Parlor

In this lab problem, we will implement a simulation of customers ordering ice cream in an ice cream parlor. The example is a bit contrived, but it allows us to work through a complex synchronization setup without actually having a very complicated program. You’ll see some applications of mutexes, semaphores, and condition variables that will be extremely helpful in Assignment 5.

The goal of this lab is to help you practice:

• When should you use each synchronization primitive? You’ll need to use mutexes, semaphores, and condition variables in different situations for this simulation.
• When you’re working on a big, complicated problem, how do you break it down into small pieces that you can implement and test incrementally? It’s crucial to avoid writing large amounts of code without testing, because if you have a bug, it will be like trying to find a needle in a haystack.

Simulation overview

This ice cream parlor comes from a somewhat odd universe:

• There are kNumCustomers customers. Each decide to order 1-4 ice cream cones. However, instead of ordering them at a counter like they normally would, they hire clerks on demand to make their cones. (Imagine using an app like Fiverr or Instacart where you could hire someone on the spot.) If a customer comes in wanting 3 ice cream cones, he hires 3 clerks on the spot to make each cone for him.
• A single manager sits in an office. When clerks make the ice cream cones, she inspects them one-by-one and decides whether to approve or reject them.
• Each clerk that is hired rushes to the parlor and makes a cone, before presenting it to a manager for approval. If the manager approves the cone, the clerk hands it to the customer and leaves; otherwise, the clerk re-makes the cone.
• A single cashier rings up each customer’s order.
• Some number of electricians arrive at the ice cream parlor needing to make repairs. They wait until all customers leave the shop, then perform the repairs.

Here are slides that walk through the various parts of the simulation: [keynote], [pdf]

Implementing the simulation

You can find the ice-cream-parlor.cc starter code in the lab6 directory (instructions for cloning are above). Alternatively, you can work through this cplayground.

Our final implementation is available here.

Customer/Clerk interactions

• How can a customer summon clerks on demand?

  We can spawn the necessary number of clerk threads within the customer:

  vector<thread> clerks;
  for (size_t i = 0; i < coneCount; i++) {
      clerks.push_back(thread([=]{
          clerk(id, i);
      }));
  }
  

• How should a customer wait until his clerks have finished making his cones?

  We simply join the clerk threads:

  for (size_t i = 0; i < coneCount; i++) {
      clerks[i].join();
  }
  

Clerk/Manager interactions

There are several things (mutexes, semaphores, etc) that we need to add here, related to synchronization in the manager’s office. To help organize these variables, our solution declares a ManagerOffice struct, although your solution does not need to do so. (You could just declare all these variables as direct members of IceCreamParlor.)

struct ManagerOffice {
    // manager-specific things here...
}

class IceCreamParlor {
  private:
    ManagerOffice managerOffice;
    // more stuff follows...
}

• How can we ensure that only one clerk is in the manager’s office at a time?

  We can use a mutex, acquired by clerks, such that only one clerk can hold the mutex at a time:

    struct ManagerOffice {
        mutex vacant;   // A clerk must acquire this lock to enter the office
    }
  
    class IceCreamParlor {
      private:
        ManagerOffice managerOffice;
        // more stuff follows...
    }
  
    void IceCreamParlor::clerk(size_t customerId, size_t coneId) {
        makeCone(coneId, customerId);
  
        lock_guard<mutex> lg(managerOffice.vacant);
        // ...
    }
    
  

• How can we make the manager sleep until a clerk needs an inspection?

  We can use a semaphore to coordinate handoff from the clerk threads to the manager thread. The manager waits for a ball to be added to the bucket, and a clerk adds a ball to the bucket when it wants an inspection.

    struct ManagerOffice {
        mutex vacant;   // A clerk must acquire this lock to enter the office
        semaphore inspectionRequested;  // wake up the manager
    }
  
    void IceCreamParlor::clerk(size_t customerId, size_t coneId) {
        makeCone(coneId, customerId);
  
        lock_guard<mutex> lg(managerOffice.vacant);
        managerOffice.inspectionRequested.signal();
        // ...
    }
  
    void IceCreamParlor::manager(size_t numNeeded) {
        // ...
        while (numApproved < numNeeded) {
            // wait for a clerk to show up in the office
            managerOffice.inspectionRequested.wait();
        }
        // ...
    }
    
  

• How can we make the clerk sleep until the inspection is complete?

  We use a semaphore to coordinate handoff from the manager thead to the waiting clerk thread.

    struct ManagerOffice {
        mutex vacant;   // A clerk must acquire this lock to enter the office
        semaphore inspectionRequested;  // wake up the manager
        semaphore inspectionFinished;   // wake up the clerk after the inspection
    }
  
    void IceCreamParlor::clerk(size_t customerId, size_t coneId) {
        makeCone(coneId, customerId);
  
        lock_guard<mutex> lg(managerOffice.vacant);
        managerOffice.inspectionRequested.signal();
  
        // wait for inspection results
        managerOffice.inspectionFinished.wait();
        // ...
    }
  
    void IceCreamParlor::manager(size_t numNeeded) {
        // ...
        while (numApproved < numNeeded) {
            // wait for a clerk to show up in the office
            managerOffice.inspectionRequested.wait();
            // tell the clerk the inspection is done
            managerOffice.inspectionFinished.signal();
        }
        // ...
    }
    
  

• How can we communicate the results of the inspection (passed/failed) from the manager to the clerk?

  We can store the result in the manager’s office, so that when the clerk wakes up, it can see the result. The manager needs to place the result before signaling the clerk to wake up. As long as the clerk reads the result before exiting the office, no other clerk can enter the office and start a new inspection.

    struct ManagerOffice {
        mutex vacant;   // A clerk must acquire this lock to enter the office
        semaphore inspectionRequested;  // wake up the manager
        semaphore inspectionFinished;   // wake up the clerk after the inspection
        bool passedInspection;
    }
  
    void IceCreamParlor::clerk(size_t customerId, size_t coneId) {
        bool passedInspection = false;
        while (!passedInspection) {
            makeCone(coneId, customerId);
      
            lock_guard<mutex> lg(managerOffice.vacant);
            managerOffice.inspectionRequested.signal();
      
            // wait for inspection results
            managerOffice.inspectionFinished.wait();
            passedInspection = managerOffice.passedInspection;
        }
    }
  
    void IceCreamParlor::manager(size_t numNeeded) {
        // ...
        while (numApproved < numNeeded) {
            // wait for a clerk to show up in the office
            managerOffice.inspectionRequested.wait();
            managerOffice.passedInspection = inspectCone();
            // tell the clerk the inspection is done
            managerOffice.inspectionFinished.signal();
        }
        // ...
    }
    
  

Customer/Cashier interactions

Similar to the manager’s office, our solution declares a struct containing variables that are specific to the checkout line. You do not have to do this.

struct CashierLine {
    // Cashier-specific fields here
};

class IceCreamParlor {
  private:
    ManagerOffice managerOffice;
    CashierLine cashierLine;
    // ... more stuff...
};

• How should the customers order themselves in line? (How does the cashier know who to help first, second, third? If two threads arrive at the same time, how do we make sure one thread goes first, followed by the next thread?)

  We can have each customer assign itself an index in line:

    struct CashierLine {
        size_t nextIndex = 0;   // when the next customer joins the line, they'll be
                                // in this position in line
        mutex nextIndexLock;
    };
  
    void IceCreamParlor::customer(size_t id, size_t coneCount) {
        // ... get the cones ...
    
        // Get in line to see the cashier
        size_t place = [&]{
            lock_guard<mutex> lg(cashierLine.nextIndexLock);
            return cashierLine.nextIndex++;
        }();
        cout << oslock << "Customer " << id << " is in position #" << place
            << " at the checkout counter." << endl << osunlock;
    }
    
  

• How should the cashier wait until a customer has joined the line?

  Similar to making the manager wait until a clerk needs attention, we can use a semaphore:

    struct CashierLine {
        size_t nextIndex = 0;   // when the next customer joins the line, they'll be
                                // in this position in line
        mutex nextIndexLock;
        semaphore customersWaiting;   // wake up the cashier when someone joins the line
    };
  
    void IceCreamParlor::customer(size_t id, size_t coneCount) {
        // ... get the cones ...
    
        // Get in line to see the cashier
        size_t place = [&]{
            lock_guard<mutex> lg(cashierLine.nextIndexLock);
            return cashierLine.nextIndex++;
        }();
        cout << oslock << "Customer " << id << " is in position #" << place
            << " at the checkout counter." << endl << osunlock;
  
        // Wake up the cashier
        cashierLine.customersWaiting.signal();
    }
  
    void IceCreamParlor::cashier() {
        for (size_t i = 0; i < kNumCustomers; i++) {
            // wait for a customer to show up in line
            cashierLine.customersWaiting.wait();
    
            cout << oslock << "Cashier rings up customer " << i << "."
                << endl << osunlock;
            sleep_for(1000);
            cout << oslock << "Cashier rang up customer " << i << "."
                << endl << osunlock;
        }
    }
    
  

• How should the cashier notify a specific customer that they are finished?

  We can have a semaphore for each individual customer, which is signaled when the cashier finishes ringing up that customer. Note that having a single semaphore (for all customers to wait on) would not work, because when the cashier puts a ball in the bucket, any customer (possibly one at the very end of the line) might get the ball and think that it is done being rung up.

    struct CashierLine {
        size_t nextIndex = 0;   // when the next customer joins the line, they'll be
                                // in this position in line
        mutex nextIndexLock;
        semaphore customersWaiting;   // wake up the cashier when someone joins the line
        semaphore done[kNumCustomers];     // wake up a customer in line when they are ringed up
    };
  
    void IceCreamParlor::customer(size_t id, size_t coneCount) {
        // ... get the cones ...
    
        // Get in line to see the cashier
        size_t place = [&]{
            lock_guard<mutex> lg(cashierLine.nextIndexLock);
            return cashierLine.nextIndex++;
        }();
        cout << oslock << "Customer " << id << " is in position #" << place
            << " at the checkout counter." << endl << osunlock;
  
        // Wake up the cashier
        cashierLine.customersWaiting.signal();
  
        // Wait for the cashier to finish ringing us up
        cashierLine.done[place].wait();
    }
  
    void IceCreamParlor::cashier() {
        for (size_t i = 0; i < kNumCustomers; i++) {
            // wait for a customer to show up in line
            cashierLine.customersWaiting.wait();
    
            cout << oslock << "Cashier rings up customer " << i << "."
                << endl << osunlock;
            sleep_for(1000);
            cout << oslock << "Cashier rang up customer " << i << "."
                << endl << osunlock;
  
            // wake up the customer to go home
            cashierLine.done[i].signal();
        }
    }
    
  

Electrician/Customer interactions

• How should the electricians wait until all customers have left the store?

  We can keep a count of the number of customers in the store, and each electrician can wait for this count to become 0 by using a condition variable.

    class IceCreamParlor {
      private:
        ManagerOffice managerOffice;
        CashierLine cashierLine;
        int numCustomersInStore = 0;
        mutex numCustomersLock;
        condition_variable_any storeEmpty;
        // ...
    }
  
    void IceCreamParlor::customer(size_t id, size_t coneCount) {
        // ... get ice cream cones ...
  
        // ... check out and leave store ...
        cout << oslock << "Customer " << id << " exits the ice cream store."
            << endl << osunlock;
    
        lock_guard<mutex> lg(numCustomersLock);
        numCustomersInStore--;
        if (numCustomersInStore == 0) {
            storeEmpty.notify_all();
        }
    }
  
    void IceCreamParlor::run() {
        // Make an array of customer threads, and add up how many cones they order
        int totalConesOrdered = 0;
        vector<thread> customers;
        for (size_t i = 0; i < kNumCustomers; i++) {
            {
                lock_guard<mutex> lg(numCustomersLock);
                numCustomersInStore++;
            }
            int numConesWanted = getNumCones();
            customers.emplace_back(thread([=]{
                customer(i, numConesWanted);
            }));
            totalConesOrdered += numConesWanted;
        }
  
        // ... spawn other threads ...
    }
  
    void IceCreamParlor::electrician(size_t id) {
        cout << oslock << "Electrician " << id
            << " waiting for all customers to exit..." << endl << osunlock;
    
        // wait for all customers to exit
        lock_guard<mutex> lg(numCustomersLock);
        while (numCustomersInStore > 0) {
            storeEmpty.wait(numCustomersLock);
        }
    
        cout << oslock << "Electrician " << id
            << " sees all customers have exited, doing electrical work!"
            << endl << osunlock;
    }
    
  

  Note that numCustomersInStore must be incremented in the main thread, before the electrician threads are spawned. Otherwise, if the electrician threads start running before that count has been properly set, they may see numCustomersInStore == 0 and begin electrical work too early. Another valid approach would have been to initialize numCustomersInStore = kNumCustomers in the IceCreamParlor definition, which works here because the number of customers is constant, but would not work if this were a situation where customers were coming/leaving at arbitrary times.