GO: Scheduling Precedence Graphs

Disclaimer

Introduction to Precedence Graphs

  • A Precedence Graph specifies the timing relationships between multiple goroutines.
  • An arrow (or sequence of arrows) A → B indicates that B cannot start execution before A is finished.
  • In the diagram epsilon cannot be executed until beta, gamma and delta have completed.
  • STOP cannot execute until both alpha and epsilon have completed.
  • There are no arrows between beta, gamma and delta so they can execute in an arbitrary order.
  • The following schedules are legal under this precedence graph:
    • START, alpha, beta, gamma, delta, epsilon, STOP
    • START, beta, alpha, delta, gamma, epsilon, STOP
    • START, delta, gamma, beta, epsilon, alpha, STOP
  • The following schedules are illegal:
    • START, epsilon, beta, gamma, delta, alpha, STOP, (epsilon cannot execute before beta or gamma or delta.)
    • START, beta, delta, epsilon, gamma, alpha, STOP, (epsilon cannot execute until all of beta, gamma, delta have completed.)
    • START, delta, gamma, beta, epsilon, STOP, alpha, (alpha and epsilon must complete before STOP.)

Scheduling with workGroups

  • goroutine4.go implements the goroutines alpha…epsilon. These sleep a random number of milliseconds and each prints out its name.
  • The seed for the random number generator is taken from the command line.
  • Two waitgroups wg1, wg2 are used for synchronization.
  • START and STOP are executed as functions.
  • Repeatedly running the code yields legal sequences of execution, despite the random sleep intervals and the inherent non-determinism of goroutine execution order.
  • This is because the waitGroup synchronization imposes the correct sequence of execution.
/* goroutine4.go
   synchronizing an arbitrary graph */
   
package main
import ("fmt"; "sync"; "math/rand"; "os"; "strconv"; "time")

func START() {
   fmt.Printf("\nSTART")
}
func STOP() {
   fmt.Printf("\nSTOP")
}
func alpha(wg *sync.WaitGroup) {
   time.Sleep(time.Duration(rand.Intn(100))*
      time.Millisecond)
   fmt.Printf("\nalpha")
   wg.Done()
}
func beta(wg *sync.WaitGroup) {
   time.Sleep(time.Duration(rand.Intn(100))*
      time.Millisecond)
   fmt.Printf("\nbeta")
   wg.Done()
}
func gamma(wg *sync.WaitGroup) {
   time.Sleep(time.Duration(rand.Intn(100))*
      time.Millisecond)
   fmt.Printf("\ngamma")
   wg.Done()
}
func delta(wg *sync.WaitGroup) {
   time.Sleep(time.Duration(rand.Intn(100))*
      time.Millisecond)
   fmt.Printf("\ndelta")
   wg.Done()
}
func epsilon(wg *sync.WaitGroup) {
   time.Sleep(time.Duration(rand.Intn(100))*
      time.Millisecond)
   fmt.Printf("\nepsilon")
   wg.Done()
}

func main() {
   if len(os.Args) < 2 {
      fmt.Printf("usage <filename> seed\n")
      return
   }
   seed, _  := strconv.Atoi(os.Args[1])
   rand.Seed(int64(seed))

   var  wg1,  wg2 sync.WaitGroup
   START()
   wg1.Add(2)
   go alpha(&wg1) 
   wg2.Add(3)
   go beta(&wg2) 
   go gamma(&wg2) 
   go delta(&wg2) 
   wg2.Wait()
   go epsilon(&wg1)
   wg1.Wait()
   STOP()
}

Review

  • Complex networks of goroutines can be synchronized using multiple waitGroups.
  • Some thought is required to correctly execute the goroutines under the precedence relationships implied by the networks.
  • The following exercises give you a chance to further explore these ideas.
    • Write GO programs to implement the precedence graphs shown, as was done in goroutine4.go. You must verify that the schedules produced are legal by running the codes with different seeds.
GO home
Next