Понимание решения проблемы Hilzer's Barbershop - PullRequest
Новая
       59

Понимание решения проблемы Hilzer's Barbershop

0 голосов
/ 12 января 2020

Проблема

Это проблема из "Маленькой книги семафоров".

В нашей парикмахерской есть три стула, три парикмахера и зона ожидания, в которой могут разместиться четыре клиента. на диване и имеет место для дополнительных клиентов. Пожарные коды ограничивают общее количество покупателей в магазине до 20.

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

Решение книги

Ниже приведено решение книги:

Общие переменные 

customers = 0
mutex = Semaphore(1)
mutex2 = Semaphore(1)
sofa = Semaphore(4)
customer1 = Semaphore(0)
customer2 = Semaphore(0)
payment = Semaphore(0)
receipt = Semaphore(0)
queue1 = []
queue2 = []

Нить клиента 

self.sem1 = Semaphore(0)
self.sem2 = Semaphore(0)

mutex.wait()
    if customers == 20:
        mutex.signal()
        balk()
    customers += 1
    queue1.append(self.sem1)
mutex.signal()

# enterShop()
customer1.signal()
self.sem1.wait()

sofa.wait()
    # sitOnSofa()
    self.sem1.signal()
    mutex2.wait()
        queue2.append(self.sem2)
    mutex2.signal()
    customer2.signal()
    self.sem2.wait()
sofa.signal()

# getHairCut()

mutex.wait()
    # pay()
    payment.signal()
    receipt.wait()
    customers -= 1
mutex.signal()

Парикмахерская нить 

customer1.wait()
mutex.wait()
    sem = queue1.pop(0)
    sem.signal()
    sem.wait()
mutex.signal()

customer2.wait()
mutex2.wait()
    sem2 = queue2.pop(0)
    sem2.signal()
mutex2.signal()

# cutHair()
payment.wait()
# acceptPayment()
receipt.signal()

Вопрос

Как я понял, следующие шаги могут произойти, когда приходит первый клиент (Клиент 1), а цирюльник (Парикмахер 1) спит на customer1:

  1. Клиент 1 добавляет свой семафор к queue1, сигнализирует customer1 и ждет на своем собственном семафоре.
  2. Парикмахер 1 просыпается, извлекает семафор Клиента 1 из очереди customer1, сигналы это (разбудив Клиента 1) и ждет его. В этот момент Парикмахер 1 удерживает mutex, поэтому никакой другой свободный парикмахер не может позволить клиенту войти до того, как Парикмахер 1 проснется и выпустит mutex.
  3. Клиент 1 просыпается, проходит через sofa (вычитая это и делая его 3), и сигнализирует свой собственный семафор (пробуждая Парикмахера 1).
  4. Парикмахер 1 просыпается и сигнализирует mutex.

В этот момент, ничто не мешает другому клиенту пройти тот же процесс и в конечном итоге добраться до queue2 до Клиента 1.

Итак, у меня возникают проблемы с пониманием того, как решение книги реализует ограничение, что «если есть любые постоянные клиенты, тот, кто был в магазине дольше всего, садится на диван ".

Для обеспечения выполнения заказа, похоже, что Поток клиентов должен сигнализировать self.sem1 только после добавления себя к queue2, а не до.

Может ли кто-нибудь помочь мне понять это решение?

1 Ответ

0 голосов
/ 12 января 2020

Во-первых, обратите внимание, что парикмахерская нить вытягивает клиентов из головы очереди2, которая представляет диван, поэтому, как только парикмахер тянет клиента, именно этот клиент ждет самое долгое время на диване.

Во-вторых, обратите внимание, что как только клиент выходит из очереди2, сама стрижка не занимает много времени, и клиент переходит к оплате. Таким образом, как написано, клиенты вытащили из очереди и перенесли оплату сразу. Стрижка происходит мгновенно.

Так что, если другой клиент приходит и перемещается по очередям, его можно выбрать только в том случае, если есть другой парикмахер, а второй клиент находится во главе очереди. Но если второй клиент находится во главе очереди, это означает, что другой парикмахер уже выбрал первого клиента. Так что это действительно не может произойти.

По поводу вашего вопроса относительно self.sem1: его цель - разбудить клиента, как только его выберут из очереди. sem1 соответствует очереди для стоящих клиентов, sem2 соответствует дивану. Клиент добавляет семафор в очередь и ждет его, поэтому, когда нить парикмахера его подхватывает, он может разбудить клиента. Таким образом, он не может обеспечить выполнение заказа, он должен разбудить клиента, когда он / она меняет местоположение. Порядок определяется очередью.

...