mutilcore.go

//package main
//author: Lubia Yang
//create: 2013-12-6
//refer: www.lubia.me/multicore-scheduler-design

package main

import (
	"fmt"
	"math/rand"
	"os"
	"runtime"
	"strconv"
	"sync"
	"time"
)

const (
	BarSite   = 20
	GrillSite = 8
	BarCost   = 10
	GrillCost = 3 * 60
	BarRand   = 5
)

var (
	BarChan   chan *Custom   //channel to bar
	GrillChan chan *Custom   //channel to grill
	SumChan   chan []*Custom //channel to leave
	StopChan  chan bool      //channel to stop program
)

//Manager handle all customs
type Manager struct {
	bar   Bar
	grill Grill // custom grill food
}

//Init chan,map,multicore cpu
func (m *Manager) Init() {
	BarChan = make(chan *Custom)
	GrillChan = make(chan *Custom)
	SumChan = make(chan []*Custom)
	StopChan = make(chan bool)
	m.bar.finished = make(map[int]int)
	m.bar.customs = make(map[int]*Custom)
	m.bar.order = make(map[int][]int)
	runtime.GOMAXPROCS(runtime.NumCPU()) //multicore cpu
}

//Enter send all customs to bar
func (m *Manager) Enter(count, interval int) {
	m.bar.waitGroup.Add(count)
	m.bar.avgInterval = interval
	m.grill.waitGroup.Add(count)

	for i := 0; i < count; i++ {
		BarChan <- &Custom{0, 0, i, i * interval}
	}
	go m.Summary(count, interval)
}

//Summary wait all customs leave from grill then summary time
func (m *Manager) Summary(count, interval int) {
	customs := <-SumChan
	var barWait, grillWait int
	for _, v := range customs {
		barWait += v.barWaitTime / count
		grillWait += v.grillWaitTime / count
	}
	fmt.Printf("TotalTime(avg):%d seconds\n", barWait+grillWait+BarCost+GrillCost)
	fmt.Printf("BarWaitTime(avg):%d seconds\n", barWait)
	fmt.Printf("GrillWaitTime(avg):%d seconds\n", grillWait)
	StopChan <- true //stop the program
}

//Bar custom get food
type Bar struct {
	waitGroup   sync.WaitGroup  //all customs prepared
	finished    map[int]int     //map[custom.index][finished task]
	customs     map[int]*Custom //map[custom.index][custom]
	order       map[int][]int   //map[column][customs.indexs]
	avgInterval int
}

//Wait customs come and handle
func (b *Bar) Wait() {
	go b.Schedule()
	for {
		custom := <-BarChan
		b.Handle(custom)
		b.waitGroup.Done()
	}
}

//Handle
//1.store customs
//2.distribute site for customs
//3.distribute customs for column
func (b *Bar) Handle(c *Custom) {
	b.customs[c.index] = c
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	for i := 0; i < BarRand; i++ {
		num := r.Intn(BarSite)
		b.finished[c.index] = 0 //finished task init
		b.order[num] = append(b.order[num], c.index)
	}
}

//Schedule parallelism task on multicore cpu
//refer the scheduler design on: www.lubia.me/multicore-scheduler-design
func (b *Bar) Schedule() {
	b.waitGroup.Wait()
	for {
		line := make([]int, 0)
		for i := 0; i < BarSite; i++ {
			if len(b.order[i]) > 0 {
				first := b.order[i][0]
				if b.customs[first].interval <= 0 {
					if len(line) == 0 {
						line = append(line, b.order[i][0])
						b.order[i] = b.order[i][1:]
					} else {
						var suit bool = true
						for k, cus := range b.order[i] {
							if b.customs[cus].interval <= 0 {
								for _, node := range line {
									if node == cus {
										suit = false
									}
								}
								if suit {
									line = append(line, b.order[i][k])
									b.order[i] = append(b.order[i][:k], b.order[i][k+1:]...)
									break
								}
							}
						}
					}
				}
			}
		}
		//fmt.Println(line)
		for index, _ := range b.finished {
			var proper bool
			for _, lv := range line {
				if lv == index {
					b.finished[index] += 1
					if b.finished[index] >= BarRand {
						delete(b.finished, index)
					}
					proper = true
					break
				}
			}
			if !proper && len(b.finished) != 0 {
				if len(line) != 0 && b.customs[index].interval <= 0 {
					b.customs[index].barWaitTime += BarCost
				}
				b.customs[index].interval -= BarCost
			}
		}
		if len(b.finished) == 0 {
			break
		}
	}
	for _, custom := range b.customs {
		custom.interval = custom.index * b.avgInterval
		GrillChan <- custom
	}
}

//Grill customs grill food
type Grill struct {
	waitGroup sync.WaitGroup
	customs   []*Custom //all customs
}

//Wait customs come and handle
func (g *Grill) Wait() {
	go g.Handle()
	for {
		custom := <-GrillChan
		g.customs = append(g.customs, custom)
		g.waitGroup.Done()
	}
}

//Sort customs by arrived time
func (g *Grill) Sort() {
	func(a []*Custom) {
		for i := 1; i < len(a); i++ {
			for j := 0; j < i; j++ {
				if a[i].barWaitTime+a[i].interval < a[j].barWaitTime+a[j].interval {
					a[i], a[j] = a[j], a[i]
				}
			}
		}
	}(g.customs)
}

//Handle
//1.Sort
//2.calculate custom wait time on grill
//3.send customs to summary
func (g *Grill) Handle() {
	g.waitGroup.Wait()
	g.Sort()
	for k := GrillSite; k < len(g.customs); k++ {
		refer := k - GrillSite
		interval := g.customs[k].barWaitTime + g.customs[k].interval -
			g.customs[refer].barWaitTime - g.customs[refer].interval
		if interval < GrillCost {
			g.customs[k].grillWaitTime = GrillCost - interval
		}
	}
	SumChan <- g.customs
}

type Custom struct {
	barWaitTime   int
	grillWaitTime int
	index         int //the order
	interval      int //interval to first custom
}

//GetCommand get customs and interval
func GetCommand() (int, int) {
	if len(os.Args) != 3 {
		fmt.Printf("Usage: %s amount interval\n", os.Args[0])
		os.Exit(1)
	}
	count, err := strconv.Atoi(os.Args[1])
	if err != nil {
		fmt.Printf("amount must be number\n%s\n", err)
		os.Exit(1)
	}
	interval, err := strconv.Atoi(os.Args[2])
	if err != nil {
		fmt.Printf("interval must be number\n%s\n", err)
		os.Exit(1)
	}
	return count, interval
}

func main() {
	c, i := GetCommand()
	m := new(Manager)
	m.Init()
	go m.grill.Wait()
	go m.bar.Wait()
	m.Enter(c, i)
	<-StopChan
}