理发师问题
一个理发师，一把理发椅，n把等候理发的顾客椅子，如果没有顾客则理发师便在理发椅上睡觉 ，当有一个顾客到达时，首先看理发师在干什么，如果理发师在睡觉，则唤醒理发师理发，如果理发师正在理发，则查看是否有空的顾客椅子可坐， 如果有，坐下等待，如果没有，则离开。
简化成如下步骤：
- 理发师等待顾客
- 顾客尝试进入等待区（人满则离开）
- (step0) 理发师招待顾客
- (step1) 顾客响应
- (step2) 理发师理发到完成
- (step3) 顾客离开
- (step4) 理发师结束，继续step0 招待新顾客
- 要求:
- 每个顾客一个线程，每个理发师一个线程
- 每个步骤都打印
- 确保2-7是顺序执行的
- 1个理发师，多个顾客
思考下该怎么实现呢？
单理发师多线程版
为了保证 2-7的顺序执行，我们只需要让3-7每个步骤一个信号量，前一个步骤结束时释放下一个步骤的信号量。
kotlin 例子如下：
abstract class SleepingBarberSimulator(val seats: Int){
companion object {
const val BARBER_PREP_SEC = 3
const val BARBER_WORK_SEC = 8
const val BARBER_REST_SEC = 3
const val BARBER_WORK_VAR = 2
}
private val rand = Random()
abstract fun newBarber()
abstract fun newCustomer()
abstract fun joinAllCustomers()
protected fun logBarber(msg: String) = println("=".repeat(100)+"Barber "+msg)
protected fun barberWorkSpeed() = BARBER_WORK_SEC - BARBER_WORK_VAR + rand.nextInt(BARBER_WORK_VAR*2)
}
class MultiThreadSleepingBarberSimulator(seats: Int): SleepingBarberSimulator(seats){
private val bid = AtomInt()
private val cid = AtomInt()
private val steps = (0 until 10).map{ Semaph(0) }
private val freeSeats = AtomInt(seats)
private val repliedCustomers = ConcurrentDeque<Int>()
// val repliedCustomers = ConcurrentLinkedDeque<Int>()
private val barberCustomerSemas = Hashtable<Int, Pair<Semaph, Semaph>>()
val customerThreads = LinkedList<Thread>()
override fun newBarber(){
val id = bid.inc()
val workSpeed = barberWorkSpeed()
Thread{
logBarber("$id comes and make some prepare")
sleep(BARBER_PREP_SEC)
while(true){
steps[0].acquire()
logBarber("$id asking for a customer")
steps[1].release()
steps[2].acquire()
val customer = repliedCustomers.poll()
logBarber("$id working on customer $customer")
sleep(workSpeed)
logBarber("$id done on customer $customer")
steps[3].release()
steps[4].acquire()
logBarber("$id has a rest")
sleep(BARBER_REST_SEC)
barberCustomerSemas.remove(customer)
}
}.apply{ start() }
}
override fun newCustomer() {
val id = cid.inc()
customerThreads.add(Thread{
println("---Customer $id comes")
if(freeSeats.dec() < 0){
println("!!!!!!!!!!!!Customer $id has no seat and leaves")
freeSeats.inc()
return@Thread
}
println("---Customer $id sits and waits")
steps[0].release()
steps[1].acquire()
println("---Customer $id responds, stands up and is served")
freeSeats.inc()
repliedCustomers.add(id)
barberCustomerSemas[id] = Semaph(0) to Semaph(0)
steps[2].release()
steps[3].release()
println("---Customer $id done and leaves")
steps[4].release()
}.apply{ start() })
}
override fun joinAllCustomers() = customerThreads.forEach{ it.join() }
private fun sleep(nSecond: Int) = Thread.sleep(nSecond * 1000L)
}
多个理发师
区别在于我们此时需要对理发师和顾客进行配对，也意味着是从step2开始不能再完全共享信号量，而是按照配对情况来共享。
private val barberCustomerSemas = Hashtable<Int, Pair<Semaph, Semaph>>()
override fun newBarber(){
val id = bid.inc()
val workSpeed = barberWorkSpeed()
Thread{
logBarber("$id comes and make some prepare")
sleep(BARBER_PREP_SEC)
while(true){
steps[0].acquire()
logBarber("$id asking for a customer")
steps[1].release()
steps[2].acquire()
val customer = repliedCustomers.poll()
logBarber("$id working on customer $customer")
sleep(workSpeed)
logBarber("$id done on customer $customer")
val (cs, bs) = barberCustomerSemas[customer]!!
cs.release()
bs.acquire()
logBarber("$id has a rest")
sleep(BARBER_REST_SEC)
barberCustomerSemas.remove(customer)
}
}.apply{ start() }
}
override fun newCustomer() {
val id = cid.inc()
customerThreads.add(Thread{
println("---Customer $id comes")
if(freeSeats.dec() < 0){
println("!!!!!!!!!!!!Customer $id has no seat and leaves")
freeSeats.inc()
return@Thread
}
println("---Customer $id sits and waits")
steps[0].release()
steps[1].acquire()
println("---Customer $id responds, stands up and is served")
freeSeats.inc()
repliedCustomers.add(id)
barberCustomerSemas[id] = Semaph(0) to Semaph(0)
steps[2].release()
val (cs, bs) = barberCustomerSemas[id]!!
cs.acquire()
println("---Customer $id done and leaves")
bs.release()
}.apply{ start() })
}
单线程coroutine版
(单线程)coroutine让实现变得更简单，因为在单线程下共享状态，不需要担心CPU缓存不一致，不需要加锁来保证原子性。
每个customer/barber一个coroutine，coroutine间的同步我们可以用channel来完成。
这里只需要每个customer/barber一个ReceiveChannel（相当于一个actor，可以用unbuffered(bufferSize=1) Channel 来使得send和receive都等待），
同步时往配对的channel里send/receive。
class CoroutineSleepingBarberSimulator(seats: Int): SleepingBarberSimulator(seats){ // by single thread coroutine
var bid = 0
var cid = 0
val scope = CoroutineScope(newSingleThreadContext("sleep barbers"))
val customerJobs = LinkedList<Job>()
val seatedCustomers = Chan<Int>()
val customerChans = mutableMapOf<Int, Chan<Int>>()
val barberChans = mutableMapOf<Int, Chan<Int>>()
override fun newBarber(){
val id = ++bid
val workSpeed = barberWorkSpeed()
scope.launch {
logBarber("$id comes and make some prepare")
sleep(BARBER_PREP_SEC)
while(true){
val customer = seatedCustomers.receive()
val customerChan = customerChans[customer]!!
val chan = Chan<Int>(1)
barberChans[id] = chan
logBarber("$id asking for a customer")
customerChan.send(id)
chan.receive()
logBarber("$id working on customer $customer")
sleep(workSpeed)
logBarber("$id done on customer $customer")
customerChan.send(0)
chan.receive()
logBarber("$id has a rest")
sleep(BARBER_REST_SEC)
barberChans.remove(id)
}
}
}
override fun newCustomer(){
val id = ++cid
customerJobs.add(scope.launch {
println("---Customer $id comes")
if(seatedCustomers.size() >= seats){
println("!!!!!!!!!!!!Customer $id has no seat and leaves")
return@launch
}
println("---Customer $id sits and waits")
val chan = Chan<Int>(1)
customerChans[id] = chan
seatedCustomers.send(id)
val barber = chan.receive()
val barberChan = barberChans[barber]!!
println("---Customer $id responds, stands up and is served by barber $barber")
barberChan.send(0)
chan.receive()
println("---Customer $id done and leaves")
customerChans.remove(id)
barberChan.send(0)
})
}
override fun joinAllCustomers() = runBlocking { customerJobs.forEach { it.join() } }
private suspend fun sleep(nSecond: Int) = delay(nSecond * 1000L)
}
附加问题: 打印sleep/awake
对于step0: 要让理发师在没有顾客时打印"sleep", 并且如果sleep那么唤醒时需要额外打印"awake"。
那么该如何实现?
References
https://en.wikipedia.org/wiki/Sleeping_barber_problem
完整代码参见: https://github.com/davidhuangdw/kotlin.concurrent/blob/master/src/main/kotlin/examples/sleeping_barbers.kt
