Determining Schedulability of Tasks for a Rate-Monotonic Scheduling System

RMSTask.hs

{-# OPTIONS_GHC -Wall #-} 

module RMSTask 
	(
	RMSTask,
	sufficientSched,
	necessarySched
	)
where

import Data.List

data RMSTask = RMSTask {execution :: Double, period :: Double} deriving (Show)

utilizationFactor :: RMSTask -> Double
utilizationFactor t = (execution t) / (period t)

sufficientSched :: [RMSTask] -> Bool
sufficientSched xs = sum (map (utilizationFactor) xs) <= n * (2.0 ** (1 / n) - 1)
	where
		n = genericLength xs :: Double

--return whether a list of RMSTasks is schedulable
necessarySched :: [RMSTask] -> Bool
necessarySched ts = (maximum (map (minLiSet ts) [1..n])) <= 1
	where
		n = length ts

--compute an Li term = minimum of the L_i set
minLiSet :: [RMSTask] -> Int -> Double
minLiSet ts i = minimum (map (calcSum i ts) (schedPointSet i ts))

--compute an L_i(t) term :)
calcSum :: Int -> [RMSTask] -> Double -> Double
calcSum 0 _ _ = 0.0
calcSum j ts t = (c_j / t) * (fromIntegral (ceiling (t / p_j) :: Int)) + (calcSum (j-1) ts t)
	where
		c_j = execution (ts !! (j-1))
		p_j = period (ts !! (j-1))

--divide two Doubles and take the floor
floorDiv :: Double -> Double -> Int
floorDiv x y = floor $ x / y

--compute the scheduling point set S_i
schedPointSet :: Int -> [RMSTask] -> [Double]
schedPointSet i ts = nub $ sort $ [(fromIntegral k) * p_j | j <- [1..i], p_i <- [period (ts !! (i-1))], p_j <- [period (ts !! (j-1))], k <- [1..(floorDiv p_i p_j)]]