Алгоритм Спящего Парикмахера (с несколькими парикмахерами)
Спящая парикмахерская проблема это классическая проблема синхронизации, с которой многие из вас могут быть знакомы или, по крайней мере, о ней слышали.
Это основано на предпосылке, что парикмахер(нить) спит, когда нет клиентов(каждый клиент - это тема) в комнате ожидания(это семафор), Если кто-то есть, он подстригается (символизирует некоторую обработку), и клиент уходит. Если в зале ожидания никого нет, парикмахер ложится спать. Когда приходит другой клиент, он должен разбудить парикмахера.
Я сделал реализацию этого, используя следующую основную идею
(хотя фактический код находится вC
Я написал следующеепсевдокод без особой заботы о синтаксисе ради понимания проблемы, только используяsem_wait
а такжеsem_post
1 для более плавного чтения)
Semaphore Customers = 0;
Semaphore Barber = 0;
Mutex accessSeats = 1;
int NumberOfFreeSeats = N;
Barber {
while(1) {
sem_wait(Customers); // waits for a customer (sleeps)
sem_wait(accessSeats); // mutex to protect the number of available seats
NumberOfFreeSeats++; // a chair gets free
sem_post(Barber); // bring customer for haircut
sem_post(accessSeats); // release the mutex on the chair
// barber is cutting hair
}
}
Customer {
while(1) {
sem_wait(accessSeats); // protects seats so only 1 thread tries to sit in a chair if that's the case
if(NumberOfFreeSeats > 0) {
NumberOfFreeSeats--; // sitting down
sem_post(Customers); // notify the barber
sem_post(accessSeats); // release the lock
sem_wait(Barber); // wait in the waiting room if barber is busy
// customer is having hair cut
} else {
sem_post(accessSeats); // release the lock
// customer leaves
}
}
}
Однако теперь, когда я решу эту проблему с несколькими парикмахерами, моя голова застряла. Я пошел в Википедию, чтобы посмотреть, смогу ли я найти что-нибудь об этом, но единственное, что я там нашел, это
Проблема нескольких спящих парикмахеров имеет дополнительную сложность координации нескольких парикмахеров среди ожидающих клиентов.
и я не мог понять это сам2.
Какие изменения я должен сделать в своем коде? Где мне нужен дополнительный семафор?
1sem_wait()
блокирует семафор.sem_post()
разблокирует это
2Отказ от ответственности: хотя я спросил это вprogrammers.stackexchange Я так и не нашел желаемого ответа, и мой вопрос все еще сохраняется.