dsaf32131
dsaf32131
2015-04-11 01:52
浏览 51
已采纳

Housie程序中的死锁。 生产者-消费者模式

I am trying to implement a housie game where a goroutine produces numbers, 3 other goroutines check if these are in their tokens and inform the producer if all their numbers were produced. I have implemented it in golang in the following way. This results in a deadlock. Any idea why this is happening? This is a "homework problem", I am just implementing it in go to learn go better.

package main

import (
    "fmt"
    "math/rand"
)

type PersonID int

func contains(s []int, e int) bool {
    for _, a := range s {
        if a == e {
            return true
        }
    }
    return false
}

func Person(called_number chan int, claim_prize chan PersonID, received chan bool, coupon []int, person_id PersonID) {
    numFound := 0
    for i := 0; i < len(coupon); i++ {
        current_number := <-called_number
        found := contains(coupon, current_number)
        if found {
            numFound++
        }
        if numFound == len(coupon) {
            claim_prize <- person_id
        } else {
            received <- true
        }
    }
}

func main() {
    var called_number chan int
    var claim_prize chan PersonID
    var received chan bool

    tokens := make([][]int, 3)
    for i := 0; i < 3; i++ {
        tokens[i] = make([]int, 12)
        for j := 0; j < 12; j++ {
            num := rand.Intn(100) + 1
            found := contains(tokens[i], num)
            for found {
                num = rand.Intn(100) + 1
                found = contains(tokens[i], num)
            }
            tokens[i][j] = num
        }
    }

    go Person(called_number, claim_prize, received, tokens[0], 0)
    go Person(called_number, claim_prize, received, tokens[1], 1)
    go Person(called_number, claim_prize, received, tokens[2], 2)

    claimants := make([]PersonID, 0)
    prev_called := make(map[int]bool)
    for i := 0; i < 100; i++ {
        if len(claimants) == 3 {
            break
        }
        num := rand.Intn(100) + 1
        _, ok := prev_called[num]
        for ok {
            num = rand.Intn(100) + 1
            _, ok = prev_called[num]
        }
        prev_called[num] = true
        called_number <- num
        for j := 0; j < 3; j++ {
            select {
            case _ = <-received:
                continue
            case pid := <-claim_prize:
                claimants = append(claimants, pid)
            }
        }
    }

    fmt.Println(claimants)
}

EDIT: The exact problem is that that the producer needs to send the number to each of the consumers. When a consumer receives all the numbers in it's token, it can claim the prize. Based on what @OneOfOne said, I have made some changes to the program. The changes are that now there is a separate channels for each of the consumers and I am closing it after it claims a prize. Below is the new program, it still deadlocks.

package main

import (
    "fmt"
    "math/rand"
)

func contains(s []int, e int) bool {
    for _, a := range s {
        if a == e {
            return true
        }
    }
    return false
}

func Person(called_number chan int, claim_prize chan int, received chan bool, coupon []int, person_id int) {
    numFound := 0
    for current_number := range called_number {
        if contains(coupon, current_number) {
            numFound++
        }
        if numFound == len(coupon) {
            fmt.Println(person_id)
            claim_prize <- person_id
        } else {
            received <- true
        }
    }
}

func main() {
    var (
        called_number1 = make(chan int, 1)
        called_number2 = make(chan int, 1)
        called_number3 = make(chan int, 1)
        claim_prize    = make(chan int, 1)
        received       = make(chan bool, 1)
    )

    tokens := make([][]int, 3)
    for i := 0; i < 3; i++ {
        tokens[i] = make([]int, 12)
        for j := 0; j < 12; j++ {
            num := rand.Intn(100) + 1
            found := contains(tokens[i], num)
            for found {
                num = rand.Intn(100) + 1
                found = contains(tokens[i], num)
            }
            tokens[i][j] = num
        }
    }

    go Person(called_number1, claim_prize, received, tokens[0], 0)
    go Person(called_number2, claim_prize, received, tokens[1], 1)
    go Person(called_number3, claim_prize, received, tokens[2], 2)

    claimants := make([]int, 0)
    prev_called := make(map[int]bool)
    for i := 0; i < 100; i++ {
        if len(claimants) == 3 {
            break
        }
        num := rand.Intn(100) + 1
        _, ok := prev_called[num]
        for ok {
            num = rand.Intn(100) + 1
            _, ok = prev_called[num]
        }
        prev_called[num] = true
        if !contains(claimants, 0) {
            called_number1 <- num
        }
        if !contains(claimants, 1) {
            called_number2 <- num
        }
        if !contains(claimants, 2) {
            called_number3 <- num
        }
        for j := 0; j < 3; j++ {
            select {
            case _ = <-received:
                continue
            case pid := <-claim_prize:
                if pid == 0 { close(called_number1) }
                if pid == 1 { close(called_number2) }
                if pid == 2 { close(called_number3) }
                claimants = append(claimants, pid)
            }
        }
    }
    fmt.Println(claimants)
}

EDIT2: This still deadlocked because I was not reducing the number of channels to wait for even after the goroutines were completed. Did that and everything works.

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • doris20141022
    doris20141022 2015-04-11 02:52
    已采纳

    Few problems:

    1. You're using a nil channel, so it just blocks forever, for some reason it's not panicing.

    2. Also, your second inner loop will block indefinitely because it's waiting to read but nothing is being sent.

    3. After your Person's loop ends, called_number <- num will block forever.

    //edit Kinda-working-code : http://play.golang.org/p/3At5nuJTuk

    But the logic is flawed, you will have to rethink it.

    点赞 评论

相关推荐