Skip to content

Instantly share code, notes, and snippets.

@kevincon

kevincon/RMSTask.hs

Created June 26, 2012 20:33
Show Gist options
  • Save kevincon/2998745 to your computer and use it in GitHub Desktop.
Save kevincon/2998745 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Kevin Conley created this gist Jun 26, 2012.
    47 changes: 47 additions & 0 deletions RMSTask.hs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,47 @@
    {-# 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)]]