Last active
December 30, 2015 13:49
-
-
Save btfak/7838077 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment