Determine if task set schedulable under Rate Monotonic scheduling (WIP)

main.go

package main

import (
	"errors"
	"fmt"
	"io/ioutil"
	"log"
	"math"
	"os"
	"sort"
)

func init() {
	if os.Getenv("QUIET") != "" {
		log.SetOutput(ioutil.Discard)
	}
}

// A Task represents a process to be executed.
type Task struct {
	id       string
	phase    int
	p        int // period
	e        int // execution_time
	deadline int
}

func (t Task) String() string { return t.id }

func round(x float64, n float64) float64 {
	y := math.Pow(10, n)

	return math.Floor(x*y) / y
}

// NewTask creates a task under the 0-phase, implicit deadline model.
func NewTask(id string, p, e int) Task {
	return Task{id, 0, p, e, e}
}

func (t Task) utilization() float64 {
	return float64(t.e) / float64(t.p)
}

// TaskSet represents the list of entites that will be under consideration
// when creating the RM schedule.
type TaskSet []Task

// Satisfy the sort interface ordered by periods (i.e. priority)
func (ts TaskSet) Len() int           { return len(ts) }
func (ts TaskSet) Swap(i, j int)      { ts[i], ts[j] = ts[j], ts[i] }
func (ts TaskSet) Less(i, j int) bool { return ts[i].p < ts[i].p }

// NewTaskSet constructs a task set ordered by priority.
func NewTaskSet(ts []Task) (TaskSet, error) {
	if len(ts) < 2 {
		return nil, errors.New("There must be atleast 2 tasks in the set.")
	}
	tset := TaskSet(ts)
	sort.Sort(tset)

	return tset, nil
}

func gcd(a, b int) int {
	for b != 0 {
		t := b
		b = a % b
		a = t
	}
	return a
}

func lcm(a, b int, integers ...int) int {
	result := a * b / gcd(a, b)

	for i := 0; i < len(integers); i++ {
		result = lcm(result, integers[i])
	}

	return result
}

func (ts TaskSet) utilization() float64 {
	sum := 0.0

	for _, t := range ts {
		sum += t.utilization()
	}

	return sum
}

func (ts TaskSet) isUtilizationBounded() (float64, bool) {
	u := ts.utilization()

	return u, u <= 1.0
}

func (ts TaskSet) hyperperiod() int {
	a := ts[0]
	b := ts[1]
	rest := ts[1:]
	restp := make([]int, len(rest))
	for k, v := range rest {
		restp[k] = v.p
	}

	return lcm(a.p, b.p, restp...)
}

func (ts TaskSet) responseTimes() []float64 {
	responseTimes := make([]float64, len(ts))
	hyperperiod := ts.hyperperiod()

	log.Println("Hyperperiod: ", hyperperiod)

	for index, t := range ts {
		// set of tasks with higher prio than t.
		hp := ts[0:index]
		log.Println("HP set for ", t, " => ", hp)

		if len(hp) == 0 {
			log.Printf("Setting RT for %s to %f\n", t, float64(t.e))

			responseTimes[index] = float64(t.e)
			continue
		}

		iter := 1
		rprev := float64(t.e)
	loop:
		for iter <= hyperperiod {
			r := float64(t.e)
			for _, ht := range hp {
				r += rprev * ht.utilization()
			}

			log.Printf("[%s] Iteration %d, response time = %f\n", t, iter, r)

			if round(rprev, 2) == round(r, 2) {
				// converged!
				responseTimes[index] = round(r, 2)
				break loop
			}

			rprev = r

			iter++
		}
	}

	return responseTimes
}

// sufficient condition for schedulability
func (ts TaskSet) sufficiencyCheck() bool {
	n := float64(len(ts))

	lhs := ts.utilization()
	rhs := n * (math.Pow(2, 1/n) - 1)

	return lhs <= rhs
}

func (ts TaskSet) Schedulable() bool {
	if ts.sufficiencyCheck() {
		return true
	}

	// bad luck; check the necessary condition for schedulability
	rt := ts.responseTimes()

	for i, t := range ts {
		r := rt[i]
		log.Printf("Response time for task: %d = %f\n", i, r)
		period := round(float64(t.p), 2)
		if r > period {
			return false
		}
	}

	return true
}

func main() {
	tasks := []Task{
		NewTask("Task 1", 6, 2),
		NewTask("Task 2", 8, 3),
		NewTask("Task 3", 12, 3),
	}

	ts, err := NewTaskSet(tasks)
	if err != nil {
		fmt.Fprintln(os.Stderr, err)
		return
	}

	fmt.Println("Schedulable =>", ts.Schedulable())
}