All goroutines deadlock

Question

Encountered problem where all goroutines are asleep - deadlock. I have a Data structure with cars array with limited amount of cars in it. Worker threads starts and tries to remove cars from data structure if there are no cars in the array and the main thread hasn't finished writing data to Data stricture then worker thread sleeps till main thread adds more cars to data struct cars array. Then worker thread wakes up, removes car object from data structure, does calculations and moves it to result structure. At some point sometimes it goes in to deadlock. Noticed that even if program finishes without exception some data(sometimes more, sometimes less) is still missing. Code:

    package main

    import (
    "crypto/sha256"
    "encoding/json"
    "fmt"
    "io/ioutil"
    "log"
    "os"
    "strconv"
    "sync"
    )

    type Car struct {
    Make         string  `json:"Make"`
    Year         int     `json:"Year"`
    Displacement float64 `json:"Displacement"`
    Hash         string
    }
    type Cars struct {
    Auto   []Car
    count  int
    MaxLen int
    mutex  *sync.Mutex
    cond   *sync.Cond
    end    bool
    }

    func (a *Cars) Insert(aut Car) {
      a.mutex.Lock() // lock method so other thread couldin't use Data structure
      for a.count == a.MaxLen {
        a.cond.Wait()//wait if current count of cars is equal to maximum amount that are allowed to store in cars array in Data structure
    }

      a.Auto[a.count] = aut
      a.count++
      a.mutex.Unlock()
      a.cond.Broadcast()
    }

    func (a *Cars) Remove(group *sync.WaitGroup) Car {
      a.mutex.Lock()
      for a.count == 0 {
        a.cond.Wait()//if there is no cars to remove from Data struct car array then sleep
      }
      result := a.Auto[a.count-1]//get the last car from cars structure car array
      var tmp Car
      a.Auto[a.count-1] = tmp//remove the last car from structure car array
      a.count--
    
      a.mutex.Unlock() // unlock this method and let others thread use i
      a.cond.Broadcast() //tell all threads that removing has been finishedt
      return result
    }
    func (a *Cars) InsertSort(aut Car) {
      a.mutex.Lock()
      for a.count == a.MaxLen {
        a.cond.Wait()
      }
      j := 0
      for i := 0; i < a.count; i++ {
        if a.Auto[i].Displacement < aut.Displacement {
            j = i //Finds where to insert new item in sorted list
        }
      }
      if j != 0 {
        for i := a.count; i >= j; i-- {
            a.Auto[i+1] = a.Auto[i]//moves objects from j to the right
        }
      }
      a.Auto[j] = aut
      a.count++
      a.mutex.Unlock()
      a.cond.Broadcast()
      }

    var Auto []Car

    func main() {
      CurrentWD, err := os.Getwd()
      if err != nil {
        log.Println(err)
      }
      path := CurrentWD + "\\Auto.json"

      jsonFile, err := os.Open(path)

      byteValue, _ := ioutil.ReadAll(jsonFile)
      json.Unmarshal(byteValue, &Auto)

      var mutex = sync.Mutex{} 
      var cond = sync.NewCond(&mutex) //syncing cond with mutex
      MaxLength := 5 // max lenght of data array
      var A = make([]Car, 5)
      Auto1 := Cars{count: 0, MaxLen: MaxLength, cond: cond, mutex: &mutex, Auto: A}//data structs

      var B = make([]Car, 40)
      Auto2 := Cars{count: 0, MaxLen: 40, cond: cond, mutex: &mutex, Auto: B}//results struct

      var waitGroup = sync.WaitGroup{}

      ThreadsAmt := 8

      waitGroup.Add(ThreadsAmt)
      for i := 0; i < ThreadsAmt; i++ {
        go execute(&Auto1, &waitGroup, &Auto2)
      }
      for _, s := range Auto {
        Auto1.Insert(s)
      }

      Auto1.end = true//finished writing to data struct
      waitGroup.Wait()

      var RLoc = CurrentWD + "\\Results.txt"
      f, err := os.Create(RLoc)
      defer f.Close()
      f.WriteString(fmt.Sprintf("%15s|%4s|%12s|%50s \n", "Make", "Year", "Displacement", "Hash"))
      for i := 0; i < Auto2.count-1; i++ {
        f.WriteString(fmt.Sprintf("%3d %15s|%4d|%12.2f|%50s  \n", i, Auto2.Auto[i].Make, 
      Auto2.Auto[i].Year, Auto2.Auto[i].Displacement, Auto2.Auto[i].Hash))
      }

      fmt.Println("Program finished execution")
      }
      func execute(Data *Cars, group *sync.WaitGroup, res *Cars) {
      hash := sha256.New()
      for Data.end == false && Data.count != 0 {
        carTemp := Data.Remove(group)//removes and returns car object from data struct
        if carTemp.Displacement > 0 {//checks if returned car object displacement is bigger than *
            var ss string
            ss = carTemp.Make + strconv.Itoa(carTemp.Year) + fmt.Sprint(carTemp.Displacement) //making string calculating hash
            sum := hash.Sum([]byte(ss))
            for i := 0; i < len(sum); i++ {
                ss += string(sum[i])//joining hash byte array in to string
            }
            carTemp.Hash = ss
            res.InsertSort(carTemp) // inserts car
        }
    }
    defer group.Done()
    }

Data: Auto.json

[{
  "Make": "Chrysler",
  "Year": 1997,
  "Displacement": 3.6
}, {
  "Make": "Honda",
  "Year": 2016,
  "Displacement": 1.4
}, {
  "Make": "Aston Martin",
  "Year": 2009,
  "Displacement": 4.1
}, {
  "Make": "Geo",
  "Year": 2011,
  "Displacement": 4.9
}, {
  "Make": "Buick",
  "Year": 2001,
  "Displacement": 6.3
}, {
  "Make": "Chevrolet",
  "Year": 2001,
  "Displacement": 2.7
}, {
  "Make": "Suzuki",
  "Year": 2004,
  "Displacement": 4.5
}, {
  "Make": "Studebaker",
  "Year": 2001,
  "Displacement": 7.5
}, {
  "Make": "Chevrolet",
  "Year": 2020,
  "Displacement": 1.1
}, {
  "Make": "Volkswagen",
  "Year": 1996,
  "Displacement": 6.2
}, {
  "Make": "Mercedes-Benz",
  "Year": 2009,
  "Displacement": 2.9
}, {
  "Make": "Nissan",
  "Year": 2019,
  "Displacement": 7.2
}, {
  "Make": "Subaru",
  "Year": 2010,
  "Displacement": 2.6
}, {
  "Make": "Hummer",
  "Year": 1991,
  "Displacement": 8.8
}, {
  "Make": "Subaru",
  "Year": 2017,
  "Displacement": 8.0
}, {
  "Make": "Mitsubishi",
  "Year": 2010,
  "Displacement": 6.6
}, {
  "Make": "Mercedes-Benz",
  "Year": 1996,
  "Displacement": 2.0
}, {
  "Make": "Lincoln",
  "Year": 1991,
  "Displacement": 9.9
}, {
  "Make": "Chevrolet",
  "Year": 1998,
  "Displacement": 3.4
}, {
  "Make": "Dodge",
  "Year": 2010,
  "Displacement": 5.8
}, {
  "Make": "GMC",
  "Year": 2016,
  "Displacement": 6.8
}, {
  "Make": "Chevrolet",
  "Year": 2013,
  "Displacement": 3.4
}, {
  "Make": "Ford",
  "Year": 2010,
  "Displacement": 5.1
}, {
  "Make": "Toyota",
  "Year": 2017,
  "Displacement": 9.6
}, {
  "Make": "Hyundai",
  "Year": 2015,
  "Displacement": 3.8
}, {
  "Make": "Mercedes-Benz",
  "Year": 2016,
  "Displacement": 4.3
}, {
  "Make": "Chevrolet",
  "Year": 2019,
  "Displacement": 2.2
}, {
  "Make": "Dodge",
  "Year": 2009,
  "Displacement": 1.8
}, {
  "Make": "Pontiac",
  "Year": 2006,
  "Displacement": 4.6
}, {
  "Make": "Chevrolet",
  "Year": 2008,
  "Displacement": 9.2
}]

Error: Fatal error: all goroutines are asleep - deadlock!

goroutine 1 [sync.Cond.Wait]:
runtime.goparkunlock(...)
E:/Program Files (x86)/Go projects/go1.15.2/src/runtime/proc.go:312
sync.runtime_notifyListWait(0xc00003c050, 0x3)
E:/Program Files (x86)/Go projects/go1.15.2/src/runtime/sema.go:513 +0x117
sync.(*Cond).Wait(0xc00003c040)
E:/Program Files (x86)/Go projects/go1.15.2/src/sync/cond.go:56 +0xa5
main.(*Cars).Insert(0xc00003c080, 0xc000014343, 0x3, 0x7e0, 0x401b333333333333, 0x0, 0x0)
c:/Users/Justas/OneDrive - Kaunas University of Technology/5 
Semestras/Lygiagretusis programavimas/Lab1/main.go:32 +0x57
main.main()
c:/Users/Justas/OneDrive - Kaunas University of Technology/5 
Semestras/Lygiagretusis programavimas/Lab1/main.go:109 +0x53c
exit status 2
Process exiting with code: 1 signal: false

Your program text doesn't compile, try a little harder please. — mevets
@mevets The program compiles on the playground play.golang.org/p/3WxBSlIDghS. Here it is with the data file: play.golang.org/p/JSgQyMdXB_N — thwd
sorry, must have been a c+p fault on my side. weird. I changed the dos file sep (\) to a normal one (/), and it worked on macos + go 1.14 — mevets
It looks like you're using a slice as a queue shared across multiple goroutines, which means you're creating a lot of work and opportunity for errors just to recreate exactly the functionality that channels provide natively. — Adrian

colm.anseo colm.anseo · Accepted Answer · 2020-10-07T16:29:13

Welcome to StackOverflow & Go development! Go currency is powerful - but also very hard to master. Don't get discouraged!

Issues:

while the other functions employ sync locking - the execute() function does not - leading to the bulk of the data-race conditions
- to compile a data-race version go build --race and standard error will show where concurrent reads/writes occur. Read more here.
the InsertSort function is broken in a lot of edge cases
use of the hasher is incorrect:
- Create hash, write bytes, then compute hash via h.Sum(nil)
- hashes are binary - so when printing them with fmt hex-formatting is recommended. (%x)

Design:

As @Adrian mentioned - using a channel is much easer to coordinate - when feeding work items in. A slice is tedious to control concurrent access here
Your output requires a sorted-slice - so in that cases a results channel does not make sense.
Go slices already have a count you can retrieve with the native len() function - so no need to track length with your own count field
slices entries do not need to be zero-out when reducing the length of a slice
- to remove the last element of a slice: s = s[:len(s)-1]
there is too much quirky slice manipulation to determine the cause of the deadlock
go standard library has sort.Slice to do heavy lifting for you

I applied all the above suggestions and roll them into a channel-based solution - with a mutex on the output slice, to sort the results at runtime:

https://play.golang.org/p/ewR3zHxirL8

This can be improved by having worker write results to an output channel - and have a results goroutine reads that channel and thus sort only once at the end. This removes the need for any sync.Mutexs - and any custom structs:

https://play.golang.org/p/0T1fFaP0iml

All goroutines deadlock

2 Answers