In the book The Little Book of Semaphores, the author considers a task called the Exclusive queue: you need to write a multi-threaded program without active waiting, using semaphores that emulate the behavior of dancers. There are two types of dancers - the master and the slave, who must dance as a pair, that is, the master must wait until the slave appears and vice versa. Each dancer corresponds to a flow, a dance corresponds to a call to the dance() function. Author's decision:

 leaders = followers = 0 mutex = Semaphore(1) leaderQueue = Semaphore(0) followerQueue = Semaphore(0) rendezvous = Semaphore(0) def leader_thread(): mutex.wait() if followers > 0: followers-- followerQueue.signal() else: leaders++ mutex.signal() leaderQueue.wait() dance() rendezvous.wait() mutex.signal() def follower_thread(): mutex.wait() if leaders > 0: leaders-- leaderQueue.signal() else: followers++ mutex.signal() followerQueue.wait() dance() rendezvous.signal()

The wait and signal operations in other implementations may be called P and V , acquire and release .

In my opinion, there is a much simpler solution:

 leader_mutex=Semaphore(1) follower_mutex=Semaphore(1) leader_rendezvous=Semaphore(0) follower_rendezvous=Semaphore(0) def leader_thread(): leader_mutex.wait() leader_rendezvous.signal() follower_rendezvous.wait() dance() leader_mutex.signal() def follower_thread(): follower_mutex.wait() follower_rendezvous.signal() leader_rendezvous.wait() dance() follower_mutex.signal()

Since the solution is rather obvious, it seems to me that its simplicity is compensated for by any shortcomings, for example, errors or low productivity. Are there any flaws and if so, which ones?

I even wrote a working program in Python 3, however, it does not produce errors.

 import threading import time import random import sys error=False counter=0 counter_mutex=threading.Semaphore(1) lead_mutex=threading.Semaphore(1) foll_mutex=threading.Semaphore(1) lead_rv=threading.Semaphore(0) foll_rv=threading.Semaphore(0) def leader(index): print("Leader started %d" % (index)) lead_mutex.acquire() time.sleep(random.uniform(0, 0.1)) lead_rv.release() time.sleep(random.uniform(0, 0.1)) foll_rv.acquire() counter_mutex.acquire() global counter, error counter+=1 print("Dancing leader %d %d" % (index, counter)) if(counter>1 or counter<-1): print("ERROR!"); error=True exit(1) counter_mutex.release() time.sleep(random.uniform(0, 0.1)) lead_mutex.release() print("Leader ended %d" % (index)) def follower(index): print("Follower started %d" % (index)) foll_mutex.acquire() time.sleep(random.uniform(0, 0.1)) foll_rv.release() time.sleep(random.uniform(0, 0.1)) lead_rv.acquire() counter_mutex.acquire() global counter, error counter-=1 print("Dancing follower %d %d" % (index, counter)) if(counter>1 or counter<-1): print("ERROR!"); error=True exit(1) counter_mutex.release() time.sleep(random.uniform(0, 0.1)) foll_mutex.release() print("Follower ended %d" % (index)) random.seed() for i in range(0,50000): if(error): break rand_val=random.randint(0, 4) if(rand_val == 0): t=threading.Thread(target=leader, args=(i,)) t.daemon=True t.start() elif(rand_val == 1 or rand_val == 3): t=threading.Thread(target=follower, args=(i,)) t.daemon=True t.start() time.sleep(random.uniform(0,0.2)) print("End: %d" % (error) )
  • I think the lack of a solution is its excessive complexity . Higher-level primitives are usually easier to use and (most importantly!) Understand. - VladD 5:59 pm
  • @VladD well, so my decision, in my opinion, is simpler than the author. And in this problem, be sure to use semaphores, as I wrote. In general, I have already responded to another forum, as there will be time, I will write the answer. Only it needs a little refinement. Or maybe you will do it? - Im ieee
  • I have a couple of days off the phone, it's hard for me: - \ - VladD
  • Write the answer to this post, additionally select it as accepted. You also give achivku. And the answer is interesting - FeroxTL

1 answer 1

You can come up with a proof that my decision is also correct. Since the functions are symmetrical, statements can only be considered for leading dancers, then they will be true for slaves.

  1. When one lead captured leader_mutex , another obviously cannot. It follows that the two hosts cannot dance at the same time.
  2. If one couple is dancing, then no one else can dance until this couple is finished. From the first statement it follows that one dancer must still finish dancing. Let the presenter finish the dance first. Then the next presenter will wait for follower_rendezvous . Someone must follower_rendezvous.signal() , but until the slave finishes dancing, another slave cannot do this (statement 1).
  3. It is also necessary to exclude consecutive calls to dance() leading at the very beginning or after the couple danced. Given the first statement, this is only possible if one master has already completed. Let the presenter wait for follower_rendezvous in the situation of the second statement. It is possible that the slave will execute follower_rendezvous.signal() , the master will perform dance() and end. Let the next leader come, then he will wait on the same semaphore. The only possible change in this situation is the execution of dance() by the slave. Further, it can be noted that the conditions of the second statement have again been fulfilled.