forked from evergreen-ci/evergreen
-
Notifications
You must be signed in to change notification settings - Fork 0
/
scheduler_stats.go
95 lines (85 loc) · 2.68 KB
/
scheduler_stats.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package model
import (
"time"
"github.com/evergreen-ci/evergreen/model/task"
)
// dependencyPath represents the path of tasks that can
// occur by taking one from each layer of the dependencies
// TotalTime is the sum of all task's time taken to run that are in Tasks.
type dependencyPath struct {
TaskId string
TotalTime time.Duration
Tasks []string
}
// CalculateActualMakespan finds the amount of time it took for the build to complete from
// the first task start to the last task finishing.
func CalculateActualMakespan(tasks []task.Task) time.Duration {
// find the minimum start time and the maximum finish time and take the difference
if len(tasks) == 0 {
return time.Duration(0)
}
minStart := tasks[0].StartTime
maxFinish := tasks[0].FinishTime
for _, t := range tasks {
if t.StartTime.Before(minStart) {
minStart = t.StartTime
}
if t.FinishTime.After(maxFinish) {
maxFinish = t.FinishTime
}
}
return maxFinish.Sub(minStart)
}
// hasTaskId returns true if the dependency list has the task
func hasTaskId(taskId string, dependsOn []task.Dependency) bool {
for _, d := range dependsOn {
if d.TaskId == taskId {
return true
}
}
return false
}
// getMaxDependencyPath recursively traverses a task's dependencies to get the dependency path object with the maximum
// total time.
func getMaxDependencyPath(tasks []task.Task, depPath dependencyPath) dependencyPath {
maxDepPath := depPath
maxTime := time.Duration(0)
// find tasks that depend on the current task in the depPath
for _, t := range tasks {
if hasTaskId(depPath.TaskId, t.DependsOn) {
newDepPath := dependencyPath{
TaskId: t.Id,
Tasks: append(depPath.Tasks, t.Id),
TotalTime: depPath.TotalTime + t.TimeTaken,
}
newDepPath = getMaxDependencyPath(tasks, newDepPath)
if newDepPath.TotalTime > maxTime {
maxTime = newDepPath.TotalTime
maxDepPath = newDepPath
}
}
}
return maxDepPath
}
// FindPredictedMakespan, given a list of tasks that have been completed, finds the optimal makespan of that build.
// While it's possible for tasks to depend on tasks outside its build, this function does not take that
// into account because it is meant to compute the optimal makespan for a single build
func FindPredictedMakespan(tasks []task.Task) dependencyPath {
maxTime := time.Duration(0)
var maxDepPath dependencyPath
for _, t := range tasks {
if len(t.DependsOn) == 0 {
depPath := dependencyPath{
TaskId: t.Id,
Tasks: []string{t.Id},
TotalTime: t.TimeTaken,
}
fullDepPath := getMaxDependencyPath(tasks, depPath)
if fullDepPath.TotalTime > maxTime {
maxTime = fullDepPath.TotalTime
maxDepPath = fullDepPath
}
}
}
return maxDepPath
}