Блог

В настоящее время я создаю программу на C , которая имитирует официантов и клиентов в ресторане с использованием потоков. Программа запускает 40 потоков клиентов и 3 потока официантов с такими функциями:

 void *customer(void * vargp){
    //depending on assigned table, call waiter 1-3 using semaphore
    sem_post(amp;callWaiter);
    //wait for waiter to respond
    sem_wait(amp;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(amp;callWaiter);
        sem_post(amp;waiterResponse);
    }
}
 

Проблема, для которой я пытаюсь найти решение, заключается в том, что официант увидит, что клиент все еще активен (с помощью нескольких различных методов, которые я пробовал), затем заблокирует ожидание семафора, затем клиент завершит работу, и клиентов больше не будет. Есть ли у кого-нибудь идеи о том, как поток официантов может проверять наличие запущенных клиентов без прохождения проверки до завершения последних клиентов?

То, что вы ищете, — это переменные условия. Они находятся в pthreads и теперь являются частью библиотеки потоков C 11. Они специально созданы для решения проблемы, с которой вы столкнулись, потому что проблема, с которой вы столкнулись, не может быть решена в целом с помощью мьютексов и швов.

Однако конкретная версия, которая вам нужна, может быть разрешимой. Я не знаю, в чем заключается ваша конкретная проблема с домашним заданием, но она может быть очень похожа на проблему со спящим парикмахером, у которой есть несколько известных решений, по крайней мере, одно из которых находится по ссылке в Википедии выше.

С семафорами простым способом было бы использовать sem_getvalue() семафор, инициализированный количеством клиентов.

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

Когда клиенты уходят, каждый выполняет sem_wait() работу с этим семафором. Когда sem_getvalue() возвращается 0, это означает, что все клиенты ушли.

Хитрость заключалась бы в том, чтобы последний клиент разбудил своего официанта, чтобы сообщить им, что они ушли.

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

Официанты сначала проверяют, есть ли клиенты, прежде чем обращаться к клиенту.

     while(num_customers(true) > 0){

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

        //work
        sem_post(amp;waiterResponse);
    }
 

Трюк последнего клиента, разбудившего официанта, имеет безвредную гонку, в которой несколько клиентов могут считать, что они последние, и поэтому официант получает несколько сообщений, каждое из которых указывает, что клиентов больше нет. Эти дополнительные сообщения безвредны, поскольку официант все равно выходит. Однако избежать этой гонки можно с помощью другого семафора, инициализированного значением 1, используемого для того, чтобы первый клиент, который не обнаружил больше клиентов, мог разбудить официанта.

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

Для простых состояний можно использовать атомарные переменные:

 //  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
    }
}
 

Где это можно добавить следующим образом:

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

Конфликт блокировок уменьшается, нет никакой двусмысленности в отношении того, что происходит после чего.