3
$\begingroup$

We have two processes. One process produces F and the other process consumes F

Initialization:

Consuming = false
Produced = false
F = EMPTY

The first thread (we can think of it as some kind of producer):

P1:
loop_for_ever:
    Produce(F)
    Consuming = true
    Produced = true
    while(Consuming) {Busy Wait)

And here is P2:

P2:
loop_for_ever:
    while(NOT Produced) {Busy Wait}
    Consume(F)
    Produced = false
    Consuming = false

One problem with this solution is after P1 has produced F, there is no way for P2 to consume F until P1 unlocks the Produced variable. Any other problems with this solution with regards to mutual exclusion? Is there a scenario in which P1 and P2 try to produce and consume F at the same time?

EDIT:

After reading fade2black's answer, I think I first need to address another more basic question. So let's add these extra conditions.

Extra conditions:

1- No mutex or semaphore based solution (only busy wait).

2- The threads have no remainder section (in that case this approach would obviously not work). Basically, what I am trying to do is to take a sequential algorithm (such as the one @fade2black has given) and distribute it among two threads. I could have blindly used an algorithm such as Dekker's (with turn given to P1 at the beginning). So I think first I need to find an answer for this question : "Is there any point to try and use a concurrent algorithm for this problem"? (when there is only one consumer and one producer and there is only one shared space between the two).

$\endgroup$
0
$\begingroup$

A simpler solution to the original problem

Using Python style notation, here is the simplified and more correct solution.

Initialization:

consuming = False
init(F) //if needed

Code for P1:

while True:
    while consuming:
        pass
    produce(F)  //updates F
    consuming= True

Code for P2:

while True:
        while not consuming:
            pass
        consume(F)
        consuming= False

This is an improvement over the code posted in question. It only uses one variable and the busy wait is located before the body of the code for each thread (the code in the question could lead to trouble if P2 thread has other sections and they somehow manipulate the variables).

A note about fade2black's answer:

This original code is in fact concurrent. But it is not parallel.

As this source (p. 166) states:

A system is parallel if it can perform more than one task simultaneously. In contrast, a concurrent system supports more than one task by allowing all the tasks to make progress. Thus, it is possible to have concurrency without parallelism.

$\endgroup$
2
$\begingroup$

Your approach works fine providing assignment operations are atomic. But I cannot see any concurrency in your approach. $P_2$ always waits until $P_1$ produces and reaches the upper limit, for example until it completely fills the buffer. Then it triggers $P_2$ to consume and waits until $P_2$ consumes all items, for example empties the buffer. So the algorithm can be rewritten as

doStuff()
  loop-forever 
    produce(F) # N items
    consume(F) # N items
  end
end

In fact the consumer(s) consumes as soon as the producer(s) produces items. In this case you would have to use synchronizations techniques such as mutexes.

Also (from here)

The producer–consumer problem, particularly in the case of a single producer and single consumer, strongly relates to implementing a FIFO or a channel.

So there is no point to try and use a concurrent algorithm for this problem. But if your model is multi producer/consumer model then your approach may lead to the race condition.

$\endgroup$
  • $\begingroup$ You are right. I have another question though. Leaving methods using mutexes and semaphores aside, how can this be compared to algorithms such as Dekker's (or Peterson's)? Are they as insufficient for this type of problem as my approach? $\endgroup$ – jrook Jul 27 '17 at 3:45
  • $\begingroup$ Both Dekker's and Peterson's algorithms solve mutual exclusion problem, that is, the problem of access a common resource. In your example you have, say buffer, $F$ used by both threads which means you have a mutual exclusion problem. This page explains Petersons's approach for two processes. You should put Produce(F) and Consumes(F) in the critical sections. $\endgroup$ – fade2black Jul 27 '17 at 3:55
  • $\begingroup$ I know about those algorithms. What I am confused about is if the problem statement makes the use of those algorithms futile in this case and allows a naive approach such as mine to work. The critical section for each thread is either Produce or Consume. I cannot see how Dekker's algorithm is better than mine in this case. Of course it is better if we want to avoid a race condition (both trying to modify F at the same time). But here F is not really modified, it is just produced and consumed. It seems to me the flow of a Dekker-algorithm-based program would be similar to mine. $\endgroup$ – jrook Jul 27 '17 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.