Is it possible to solve this synchronization problem using mutex and conditional variables?

Question

---

I am trying to solve this synchronization problem in C to practice for my lectures of Operating Systems where we use POSIX and Linux. I've been trying for days to find an approach to this problem with no luck, and I can't seem to find similar problems.

To be more specific, I'm failing to see which mechanism would allow me to satisfy this 2 conditions at the same time: respect time of arrival (the first to come, has the greatest priority), and no customer waiting unnecessarily.

Notice the question should be solved without semaphores. So I'm left with mutexes, cond vars and shared variables in memory. This is my attempt so far:

#include <...>

/* there are 2 pumps and infinite customers */

// Mutexes protecting the resources
pthread_mutex_t mPump1;
pthread_mutex_t mPump2;

// Conditional variable to signal the use from different threads
pthread_cond_t Pump1release, Pump1lock;
pthread_cond_t Pump2release, Pump2lock;

// Initial values
bool p1InUse = false;
bool p2InUse = false;

int getUnusedPump()
{

while(true)
{

    while(p1InUse)
    {
        //1. acquire critical section
        pthread_mutex_lock(&mPump1);

        //Release lock & sleep
        pthread_cond_wait(Pump1release, mPump1);
        p1InUse = true;
        return 1;
    }
    
    while(p2InUse)
    {
        //1. acquire critical section
        pthread_mutex_lock(&mPump2);

        //Release lock & sleep
        pthread_cond_wait(Pump2release, mPump2);
        p2InUse = true;
        return 2;
    }

}


}

void releasePump(int pump)
{

if(pump==1) //Release pump1 from our thread
{
    p1InUse = false;
    
    //signal the other threads
    pthread_cond_signal(Pump1release);
    
    //1. release critical section
    pthread_mutex_unlock(&mPump1);
    
}
else
{
    p2InUse = false;
    
    //signal the other threads
    pthread_cond_signal(Pump1release);
    
    //1. release critical section
    pthread_mutex_unlock(&mPump2);

}

}

One of the problems I find is that, given a certain moment when the 2 pumps are busy, If I put one thread to cond_wait() on, say pump 1, but then pump 2 is unlocked, I would be violating requirement 3 because that thread shouldn't be waiting while there's an available pump. Equally concerning, I cannot figure out, given the 2 pumps are available, how should I decide to which of them I send an arriving client(thread)?

Is it possible at all to solve this problem using just the mentioned mechanisms?

Answer 1

Surely you can just implement a queue of waiting customers (per price< I guess, not sure what the price argument is supposed to be fore), earliest arrival first. Then when a pump becomes free, you just wake up the first waiting customer (respecting arrival time). You would also need to maintain a count of the number of free pumps at each price point.

Answer 2

tl;dr Yes, it is possible to solve this problem using

... mutexes, condition variables, and other shared variables

You have attempted to solve it by throwing more mutexes and condition variables at it. It's better to first figure out what shared variables you need first, and then make sure they're correctly synchronized.

You can't solve it just with mutexes and condition variables - you need actual code and shared state to deliberately enforce the fairness constraint.

---

It's sometimes useful to think about real-world systems that behave in a similar way.

The simplest in this case is the system sometimes used by deli counters, where you take a paper ticket on arrival. It relies on the tickets being numbered in strictly ascending order.

So your steps would be

1. take a ticket

   • the ticket here is just an integer value
   • the value is taken from a shared variable, which must be protected by a mutex
   • the shared variable must be incremented every time a ticket is taken

2. wait until your ticket is called

   • the wait step implies a condition variable
   • we might as well use the same mutex for this, there's no obvious benefit to super-fine-grained locking here
   • the wait predicate requires another shared integer variable, which is the number being called

3. do your actual pumping work with the mutex unlocked ...

4. call the next ticket when you're done

   • in releasePump, you'll want to lock the mutex again, increment the "call ticket" variable, and signal the condition variable

Code might look something like:

struct TicketQueue {
    unsigned freeTicket;   // take from here
    unsigned calledTicket; // wait till it appears here
    pthread_mutex_t mutex;
    pthread_cond_t  cv;
};

/* you can put all of steps 1 & 2 in here */
void take_ticket_and_wait(struct TicketQueue*);

/* and step 4 in here */
void call_next_ticket(struct TicketQueue*);

Note that I'm using unsigned ticket values: this is because unsigned overflow is well-defined, so there's no limit on how long the program can run (so long as there are fewer than UINT_MAX concurrent customers).

This is brittle if there's any way of a waiter giving up or being cancelled, since the chain of consecutive tickets is broken. Then you'd need to add some mechanism for handing back a ticket without using it, or replace the numerical tickets with a doubly-linked list.

---

Edit - I omitted the "which pump became free" part and focused on the sleep/wakeup sequencing. You obviously need to also track what pumps are currently busy/free, but the synchronization problem itself is solved. Just protect your shared pump state with the same mutex as the TicketQueue itself.

Answer 3

You should have one main loop and one thread function. The need for mutexes is debatable, if everything is implemented in the same process using threads you should not need any. But the terminology may be platform specific, I am talking as a Windows developer.

The main loop checks the queue for waiting customers. If there is one in queue, it checks the availability of a pump. This could be a simple integer variable. If a pump is available (availablePumps > 0), the waiting customer is taken from the queue, a customer thread is created, the integer is decremented and the thread is started. Sleep for a couple of milliseconds and loop.

The customer thread just calls the function customer(int price) and increments availablePumps.

Incrementing or decrementing an integer may not be an atomic operation so you may need to apply your mutex there, just to prevent concurrent use of the availablePumps variable. In a real world program this would be a lock or a critical section.