CS107

Lec 18 Ice Cream Store Simulation

Biggest Concurrency problem in CS107

Roles

1 Cashier: deal the billing issues
1 Manager: at most one clerks in his office at the same time.
Clerks: 10 - 40, before passing cone to the customer, then has to ask for manager for inspection to get an approval for the cone that he/she made.
10 Customers: each one ask for a random number of cones from 1 to 4.

Manager

Waiting all the time for the clerk’s request
do inspection.
tell the clerk if the cone is qualified.

The manager will wait until all the cones for all the customers to be done.

Clerks

No more than 1 clerk can go to the manager. some kind of lock in manager’s office.
Ask for the manager to inspection the cone.
get the respond from manager that if the cone is qualified.

Customer

comes in, and he want 1 - 4 ice cream cones
fire N clerks, get all cones he wants.
go to the cashier in a line (so there is a kind of sort, first in first out, how to assure that?)

Cashier

Waiting for customers(in a line) to request the service.
handling the customer’s billing

Code

main function

int main(int argc, char** argv)
{
    int totalCones = 0;
    InitThreadPackage();
    SetupSemaphores();
    for (int i = 0; i < 10; i++)
    {
        int numCones = RandomInteger(1,4);
        ThreadNew(_, Customer, 1, numCones);
    	totalCones += numCones;
    }
    
    ThreadNew(_, Cashier, 0);
    ThreadNew(_, Manager, 1, totalCones);
    RunAllThreads();
    FreeSemphores();
    return 0;
}

global variables

// for manager and clerks
struct Inspection
{
    bool passed;	// init as false
    Semaphore requested;	// init as 0, clerk finishes cone and then signals the semaphore to wake up manager.
    Semaphore finished;		// init as 0, manager finishes the inspection and then signals the semaphore to wake up clerk.
	Semaphore lock;			// init as 1, only one customer can get in the office.
} inspection;

struct Line;	// see definitions in Cashier's code part

Manager

void Manager(int totalConesNeeded)
{
    int numApproved = 0;
    int numInspected = 0; 
    
    while(numApproved < totalConesNeeded)
    {
        SW(inspection.requested);
        numInspected++;
        inspection.passed = RandomChance(0, 1);
        if(inspection.passed == true)
        {
            numApproved++;
        }
        SS(inspection.finished);
    }
}

Clerk

void Clerk(Semaphore semToSignal)
{
    // make cones until passing the manager's inspection
    
    bool passed = false;
    while(!passed)
    {
      	MakeCone();
        SW(inspection.lock);		// binary lock.
        SS(inspection.requested);	// signal manager to inspect
        SW(inspection.finished)		// waiting for manager's result.
        passed = inspection.passed;
        SS(inspection.lock);
    }
    // give cone to customer
    SS(semToSignal);
}

If we don’t have the lock, what happens?

struct inspection is shared between all clerks and the manager
if we don’t have that lock, the passed belongs which Clerk?
Imagine one clerk thread was pulled off from the processor before passed = inspection.passed, it is very possible that some other clerk thread could get into the manager’s office, show him his cone, get his passed value. This is the same problem of ticket agents

What if the manager SemaphoreSignal and SemaphoreWait ?

Which means the door of the office would be opened, any other clerk could get in and override the passed value before it close. In another way, we only have one manager thread, the manager will always pass SS, and in the end SW.

Why do we need inspection.requested and inspection.finished?

The manager is waiting on the clerk’s request; the clerk sends a request, and then waits for the manager’s inspection to finish. This is the same synchronization pattern as the Ringbuffer problem.

Customer

void Customer(int numCones)
{
    Browse();
    // get numCones
    Semaphore clerksDone; // 0
    for(int i = 0; i < numCones; i++)
    {
        ThreadNew(_, Clerk, 1, clerksDone);
    }
     
    // wait for numCones done
    for(int i = 0; i < numCones; i++)
    {
    	SemaphoreWait(clerksDone);    
    }
    SemaphoreFree(clerksDone);
    
   	WalkToCashier();
    
    SW(line.lock);	
    int position = line.number++; // get number in sequence
    SS(line.lock);
    SS(line.requested);				// ask Cashier for billing
    SW(line.customers[position]);	// get Cashier's response.
}

Why don’t we just use a single loop?

That would be sequential: we spawn a new thread, then wait for it to finish before we spawn another one.

Why don’t we just use a semaphore and a shared integer?

Back to the problem of test and use. The main reason why we are using semaphores or locks or those basically concurrency constructs is that we need to ensure atomicity: we want to decrement the value or increment its value in one operation or in several operations that are guaranteed to be done atomically. Between operation and test, it could be pulled off from the processor.

Which thread are we waiting for in the second loop?

We do not care which one signaled, as long as we know somebody signaled us.

Cashier

A FIFO queue.

struct Line
{
    int number;	// init as 0, next avaliable position in the line. 
    Semaphore requested; // init as 0;
    Semaphore customers[10];	// init as 0; waiting to be served.
    Semaphore lock;				// init as 1;
} line;

Something missed?

number is a shared resource between Customers, so it need to be protected by lock

void Cashier()
{
    for(int i = 0; i < 10; i++)
    {
        SW(line.requested);
        Checkout(i);	// checkout customer i;
        SS(line.Customers[i]);
    }
}

How to ensure the sequence of first-in, first-out?

This is realized by lock and number of struct Line, the first one gets number 0, while the second gets number 1, and so on.