Приоритетная очередь в GoLang с использованием каналов

Вопрос

На изображении выше показан вопрос, на который мне нужно найти решение. вот решение, которое я придумал (должно быть закодировано в Go). Я получаю ошибку взаимоблокировки:

fatal error: all goroutines are asleep - deadlock!

goroutine 1 [chan send]:
main.main()
    /home/kypriank/Assignment 5/priorityqueue.go:42 +0x1a3

goroutine 17 [chan send]:
main.priorityQueue(0xc420080060, 0xc4200800c0)
    /home/kypriank/Assignment 5/priorityqueue.go:22 +0x1a2
created by main.main
    /home/kypriank/Assignment 5/priorityqueue.go:40 +0xe5
exit status 2

Мне было интересно, может ли кто-нибудь помочь мне выяснить, где мой код испортился (у основной функции есть код для проверки моего решения):

package main

var numOrder [20] int
var mesOrder [] PriorityMessage
var pri int
var a int

type PriorityMessage struct {
    Priority int // between 0 and 9
    Message string
}

func priorityQueue(west chan PriorityMessage, east chan string) {
    incomming := <-west
    if numOrder[incomming.Priority] == 10 {
        numOrder[incomming.Priority] = incomming.Priority
    }else {numOrder[incomming.Priority+1] = incomming.Priority}
    mesOrder = append(mesOrder, incomming)
    for i := 0; i < len(numOrder); i++ {if numOrder[i] != 10 {pri = 
numOrder[i]; a = i; break}}
    for i := 0; i < len(mesOrder); i++ {
        if pri == mesOrder[i].Priority {
            east <- (mesOrder[i]).Message
            numOrder[a] = 10
            mesOrder = append(mesOrder[:i], mesOrder[i+1:]...) 
        }
    }
}

var west chan PriorityMessage
var east chan string

func printToScreen() {
    for {println(<- east)}
}

func main() {
    for i := 0; i < len(numOrder); i++ {numOrder[i] = 10}
    west = make(chan PriorityMessage)
    east = make(chan string)
    go priorityQueue(west, east)
    west <- PriorityMessage{1, "one"}
    west <- PriorityMessage{0, "zero"}
    west <- PriorityMessage{2, "two"}
    west <- PriorityMessage{1, "another one"}
    west <- PriorityMessage{0, "another zero"}
    go printToScreen()
    select {} // to allow all messages to be printed
}

go channels deadlock priority-queue
person Kypper    schedule 18.11.2018    source источник
comment
Priority Queue является стандартным типом данных в CS и не требует параллелизма для реализации — en.wikipedia.org/ wiki/Priority_queue#Обычная_реализация   -  person Dmitry Harnitski    schedule 19.11.2018
comment
к сожалению, задание требует, чтобы я реализовал это с использованием параллелизма. Но спасибо за вклад, Дмитрий :) большая часть кода предоставлена. Единственная часть кода, которую я должен реализовать сам, — это функция PriorityQueue.   -  person Kypper    schedule 19.11.2018

Ответы (1)


arrow_upward
0
arrow_downward

На самом деле я не смотрел на поведение очереди с приоритетом, а вместо этого сосредоточился на взаимоблокировке.

Итак, у вас есть несколько проблем, которые приведут вас в тупик:

  1. Вы читаете из west только один раз, однако записываете в него несколько раз. Это означает, что он будет заблокирован, когда вы напишете zero. Может быть, добавить цикл for.
  2. go printToScreen() после всех записей в west. Это означает, что когда ваша процедура чтения из west, а затем запись в east доходит до записывающей части, она блокируется, потому что ничего не читается из east.
  3. Пустой выбор (select{}). Хотя это заблокирует основную процедуру go, она будет делать это бесконечно. Это вызовет панику взаимоблокировки, как только все другие подпрограммы go закроются.

Я изменил ваш код на это:

package main

import "time"

var numOrder [20]int
var mesOrder []PriorityMessage
var pri int
var a int

type PriorityMessage struct {
    Priority int // between 0 and 9
    Message  string
}

func priorityQueue(west chan PriorityMessage, east chan string) {
    for {
        incomming := <-west
        if numOrder[incomming.Priority] == 10 {
            numOrder[incomming.Priority] = incomming.Priority
        } else {
            numOrder[incomming.Priority+1] = incomming.Priority
        }
        mesOrder = append(mesOrder, incomming)
        for i := 0; i < len(numOrder); i++ {
            if numOrder[i] != 10 {
                pri =
                    numOrder[i]
                a = i
                break
            }
        }
        for i := 0; i < len(mesOrder); i++ {
            if pri == mesOrder[i].Priority {
                east <- (mesOrder[i]).Message
                numOrder[a] = 10
                mesOrder = append(mesOrder[:i], mesOrder[i+1:]...)
            }
        }
    }
}

var west chan PriorityMessage
var east chan string

func printToScreen() {
    for {
        println(<-east)
    }
}

func main() {
    for i := 0; i < len(numOrder); i++ {
        numOrder[i] = 10
    }
    go printToScreen()
    west = make(chan PriorityMessage)
    east = make(chan string)
    go priorityQueue(west, east)
    west <- PriorityMessage{1, "one"}
    west <- PriorityMessage{0, "zero"}
    west <- PriorityMessage{2, "two"}
    west <- PriorityMessage{1, "another one"}
    west <- PriorityMessage{0, "another zero"}

    time.Sleep(time.Hour)
}

И идут следующие результаты:

one
zero
two
another one
another zero
person poy    schedule 18.11.2018
comment
Большое спасибо за подробное объяснение и решение, которое вы предоставили! как я упоминал ранее, к сожалению, мне не разрешено изменять какой-либо код, кроме кода в функции priorityQueue. Я создал переменные numOrder, mesOrder, pri и a. поэтому, кроме этих 4, и что-либо в функции priorityQueue не может быть изменено. - person Kypper; 19.11.2018
comment
Достаточно справедливо, но это означает, что вы должны постоянно потреблять с запада и не быть заблокированным с востока. Итак, вставьте цикл for в функцию, а затем при записи на восток сделайте это в новой процедуре go. - person poy; 19.11.2018