HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What is the problem with this Busy Wait solution for two threads?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thisproblemthewhatwaitwiththreadsbusytwofor

Problem

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).

Solution

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.

Code Snippets

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

Context

StackExchange Computer Science Q#79387, answer score: 2

Revisions (0)

No revisions yet.