3

В книге The Little Book of Semaphores автор рассматривает задачу, которая называется Exclusive queue: нужно написать многопоточную программу без активного ожидания, использующую семафоры, которая эмулирует поведение танцоров. Есть два вида танцоров — ведущие и ведомые, которые должны танцевать в паре, то есть ведущий должен дождаться, пока появится ведомый и наоборот. Каждый танцор соответствует потоку, танец соответствует вызову функции dance(). Решение автора:

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

Операции wait и signal в других реализациях могут называться P и V, acquire и release.

На мой взгляд, существует гораздо более простое решение:

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

Поскольку решение довольно очевидное, мне кажется, что его простота компенсируется какими-либо недостатками, например, ошибками или малой производительностью. Есть ли недостатки на самом деле и если да, то какие?

Я даже написал работающую программу на Python 3, правда, ошибок она не выдаёт.

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) ) 
4
  • Думаю, недостаток решения — его излишняя сложность. Более высокоуровневые примитивы обычно легче в использовании и (главное!) понимании.
    – VladD
    Commented 26 мар. 2016 в 17:59
  • @VladD ну так моё решение, на мой взгляд, проще, чем авторское. И в этой задаче обязательно использовать семафоры, как я и написал. Вообще мне уже ответили на другом форуме, как будет время, я напишу ответ. Только его нужно немного доработать. Или может быть, вы это сделаете?
    – Im ieee
    Commented 27 мар. 2016 в 15:02
  • Я с телефона ещё пару дней, мне сложно :-\
    – VladD
    Commented 27 мар. 2016 в 18:02
  • Напишите ответ к этому посту, дополнительно выберите его как принятый. Вам ещё и ачивку дадут. А ответ интересен
    – FeroxTL
    Commented 24 июн. 2016 в 12:01

1 ответ 1

1

Можно придумать доказательство того, что моё решение также верное. Поскольку функции симметричные, можно рассматривать утверждения только для ведущих танцоров, тогда они будут верны и для ведомых.

  1. Когда один ведущий захватил leader_mutex, другой, очевидно, сделать это не может. Из этого следует то, что двое ведущих не могут танцевать одновременно.
  2. Если одна пара танцует, то никто другой не сможет танцевать, пока эта пара не закончит. Из первого утверждения следует, что один танцор всё-таки должен закончить танцевать. Пусть ведущий закончил танцевать первым. Тогда следующий ведущий будет ждать на follower_rendezvous. Кто-то должен выполнить follower_rendezvous.signal(), но пока ведомый не закончит танцевать, другой ведомый это выполнить не может (утверждение 1).
  3. Нужно также исключить последовательные вызовы dance() ведущими в самом начале или после того как пара станцевала. С учётом первого утверждения это возможно только если один ведущий уже завершился. Пусть в ситуации второго утверждения ведущий ждёт на follower_rendezvous. Возможно, что ведомый выполнит follower_rendezvous.signal(), ведущий выполнит dance() и завершится. Пусть подошёл следующий ведущий, тогда он будет ждать на этом же семафоре. Единственное возможное изменение в этой ситуации -- это выполнение dance() ведомым. Далее, можно заметить, что опять выполнились условия второго утверждения.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.