I am currently making a program in C that simulates Waiters and Customers in a restaurant using threads. The program runs 40 Customers threads and 3 Waiters threads, with functions like this:

void *customer(void * vargp){
    //depending on assigned table, call waiter 1-3 using semaphore
    sem_post(&callWaiter);
    //wait for waiter to respond
    sem_wait(&waiterResponse);
    //leave table and finish thread
}

void *waiter(void *vargp){
    //this is what I'm trying to fix
    while(there are still customers){ //this check has been a number of different attempts
        sem_wait(&callWaiter);
        sem_post(&waiterResponse);
    }
}

The issue I am trying to find a solution for is that a waiter will see that a customer is still active (through a few different techniques I tried), then block waiting for the semaphore, then the customer will finish and there will be no more customers. Does anyone have ideas for how a waiter thread can check for running customers without the check going through before the last customers finish?

CodePudding user response：

What you are looking for is condition variables. They are in pthreads, and are now part of the C 11 threading library. They are specifically constructed to solve the problem you are having, because the problem you are having cannot be solved in general with mutexes and seamphores.

However, the specific version you need may be solvable. I don't know what your particular homework problem is, but it may be very akin to the sleeping barber problem, which has several known solutions, at least one of which is found on the Wikipedia link above.

CodePudding user response：

With semaphores, a straightforward way would be to use sem_getvalue() on a semaphore initialized to the number of customers.

int num_customers(bool = false){
    int v;
    sem_getvalue(&customers, &v);
    return v;
}

As customers leave, each performs sem_wait() on that semaphore. When sem_getvalue() returns 0, it means all the customers have left.

A trick would be for the last customer to wake up their waiter to let them know they have left.

    //leave table and finish thread
    sem_wait(&customers);
    if (num_customers() == 0) sem_post(&callWaiter);

The waiters would check to see if there are any customers first before handling a customer.

    while(num_customers(true) > 0){

        //wait for work
        sem_wait(&callWaiter);
        if (num_customers(true) == 0) break;

        //work
        sem_post(&waiterResponse);
    }

The trick of the last customer waking up the waiter has a harmless race, where multiple customers may each of them believe they are the last, and so the waiter gets multiple posts each indicating there are no more customers. Those extra posts are harmless, since the waiter is exiting anyway. However, avoiding that race can be achieved with another semaphore initialized to 1 used to let the first customer that detected no more customers be the one to wake up the waiter.

int num_customers(bool is_waiter = false){
    int v;
    sem_getvalue(&customers, &v);
    if (is_waiter) return v;
    if (v == 0) {
        if (sem_trywait(&last_customer) == -1) {
            assert(errno == EAGAIN);
            return 1;
        }
    }
    return v;
}

CodePudding user response：

For simple states, atomic variables can be used:

//  waiter
myId= waiter id
while(work)
{
    work=false;
    for(int n=0;n<40;n  )
    while (customerWaiterMatrix[n][myId].load()>0) // one of 120 atomic variables
    {
           work=true;
           std::lock_guard<std::mutex>(mutexOfThatCustomerThisWaiter);
           // thread safe customer logic
    }
}

Where it can be added like this:

// customer 
myId = customer id
customerWaiterMatrix[myId][selectedWaiterId].fetch_add(1);
same lock of current customer & waiter with lock guard
Do safe logic
customerWaiterMatrix[myId][selectedWaiterId].fetch_add(-1);

Locking contention is reduced, there is no ambiguity about what happens after what.