Threading and Mutex

Question

I'm working on a program that simulates a gas station. Each car at the station is it's own thread. Each car must loop through a single bitmask to check if a pump is open, and if it is, update the bitmask, fill up, and notify other cars that the pump is now open. My current code works but there are some issues with load balancing. Ideally all the pumps are used the same amount and all cars get equal fill-ups.

EDIT: My program basically takes a number of cars, pumps, and a length of time to run the test for. During that time, cars will check for an open pump by constantly calling this function.

int Station::fillUp()
{

// loop through the pumps using the bitmask to check if they are available
for (int i = 0; i < pumpsInStation; i++)
{

    //Check bitmask to see if pump is open
    stationMutex->lock();
    if ((freeMask & (1 << i)) == 0 )
    {

        //Turning the bit on
        freeMask |= (1 << i);
        stationMutex->unlock();

        // Sleeps thread for 30ms and increments counts
        pumps[i].fillTankUp();

        // Turning the bit back off
        stationMutex->lock();
        freeMask &= ~(1 << i);
        stationCondition->notify_one();
        stationMutex->unlock();

        // Sleep long enough for all cars to have a chance to fill up first.
        this_thread::sleep_for(std::chrono::milliseconds((((carsInStation-1) * 30) / pumpsInStation)-30));


        return 1;
    }
    stationMutex->unlock();
}

// If not pumps are available, wait until one becomes available.
stationCondition->wait(std::unique_lock<std::mutex>(*stationMutex));

return -1;
}

I feel the issue has something to do with locking the bitmask when I read it. Do I need to have some sort of mutex or lock around the if check?

Answer 1

Normally I wouldn't suggest refactoring as it's kind of rude and doesn't go straight to the answer, but here I think it would help you a bit to break your logic into three parts, like so, to better show where the contention lies:

int Station::acquirePump()
{
    // loop through the pumps using the bitmask to check if they are available
    ScopedLocker locker(&stationMutex);
    for (int i = 0; i < pumpsInStation; i++)
    {
        // Check bitmask to see if pump is open
        if ((freeMask & (1 << i)) == 0 )
        {
            //Turning the bit on
            freeMask |= (1 << i);
            return i;
        }
    }
    return -1;
}

void Station::releasePump(int n)
{
    ScopedLocker locker(&stationMutex);
    freeMask &= ~(1 << n);
    stationCondition->notify_one();
}

bool Station::fillUp()
{
    // If a pump is available:
    int i = acquirePump();
    if (i != -1)
    {
        // Sleeps thread for 30ms and increments counts
        pumps[i].fillTankUp();
        releasePump(i)

        // Sleep long enough for all cars to have a chance to fill up first.
        this_thread::sleep_for(std::chrono::milliseconds((((carsInStation-1) * 30) / pumpsInStation)-30));
        return true;
    }
    // If no pumps are available, wait until one becomes available.
    stationCondition->wait(std::unique_lock<std::mutex>(*stationMutex));
    return false;
}

Now when you have the code in this form, there is a load balancing issue which is important to fix if you don't want to "exhaust" one pump or if it too might have a lock inside. The issue lies in acquirePump where you are checking the availability of free pumps in the same order for each car. A simple tweak you can make to balance it better is like so:

int Station::acquirePump()
{
    // loop through the pumps using the bitmask to check if they are available
    ScopedLocker locker(&stationMutex);
    for (int n = 0, i = startIndex; n < pumpsInStation; ++n, i = (i+1) % pumpsInStation)
    {
        // Check bitmask to see if pump is open
        if ((freeMask & (1 << i)) == 0 )
        {
            // Change the starting index used to search for a free pump for
            // the next car.
            startIndex = (startIndex+1) % pumpsInStation;

            // Turning the bit on
            freeMask |= (1 << i);
            return i;
        }
    }
    return -1;
}

Another thing I have to ask is if it's really necessary (ex: for memory efficiency) to use bit flags to indicate whether a pump is used. If you can use an array of bool instead, you'll be able to avoid locking completely and simply use atomic operations to acquire and release pumps, and that'll avoid creating a traffic jam of locked threads.

Answer 2

Imagine that the mutex has a queue associated with it, containing the waiting threads. Now, one of your threads manages to get the mutex that protects the bitmask of occupied stations, checks if one specific place is free. If it isn't, it releases the mutex again and loops, only to go back to the end of the queue of threads waiting for the mutex. Firstly, this is unfair, because the first one to wait is not guaranteed to get the next free slot, only if that slot happens to be the one on its loop counter. Secondly, it causes an extreme amount of context switches, which is bad for performance. Note that your approach should still produce correct results in that no two cars collide while accessing a single filling station, but the behaviour is suboptimal.

What you should do instead is this:

1. lock the mutex to get exclusive access to the possible filling stations
2. locate the next free filling station
3. if none of the stations are free, wait for the condition variable and restart at point 2
4. mark the slot as occupied and release the mutex
5. fill up the car (this is where the sleep in the simulation actually makes sense, the other one doesn't)
6. lock the mutex
7. mark the slot as free and signal the condition variable to wake up others
8. release the mutex again

Just in case that part isn't clear to you, waiting on a condition variable implicitly releases the mutex while waiting and reacquires it afterwards!

Answer 3

It looks like every car checks the availability of pump #0 first, and if that pump is busy it then checks pump #1, and so on. Given that, it seems expected to me that pump #0 would service the most cars, followed by pump #1 serving the second-most cars, all the way down to pump #(pumpsInStation-1) which only ever gets used in the (relatively rare) situation where all of the pumps are in use simultaneously at the time a new car pulls in.

If you'd like to get better load-balancing, you should probably have each car choose a different random ordering to iterate over the pumps, rather than having them all check the pumps' availability in the same order.