Real-time Systems and Rate-Monotonic Scheduling

EMERALDS Landon Cox Landon Cox March 30, 2016 March 30, 2016

Real-time systems Typical hardware constraints Typical hardware constraints Slow, low-power processors Small memories Little to no persistent storage Typical workload Typical workload Periodic sensing and actuation Task periodicity deadlines

EMERALDS OS for embedded systems OS for embedded systems Due to hardware constraints Due to hardware constraints Want to minimize overhead everywhere Use resources on real work, not management Focus on three system services Focus on three system services Task scheduling Synchronization Communication

Rate-monotonic scheduling Each task has Each task has A periodicity (e.g., must run every 10 ms) A worst-case execution time (e.g., 5 ms) A static priority (i.e., does not change over time) Basic idea Basic idea Assign task priorities based on periodicity Tasks with smaller period get higher priority Can use pre-emption to interrupt a task

Rate-monotonic scheduling T1 (Period 100ms, execution time 50ms) T1 (Period 100ms, execution time 50ms) T2 (Period 200ms, execution time 80ms) T2 (Period 200ms, execution time 80ms) Pre Pre- -empt and schedule every 50ms empt and schedule every 50ms 150 150 0 0 50 50 100 100 180 180 200 200 T2 T1 T1 T2 What to run next? What to run next? Did we meet all of our deadlines? What to run next? What was our utilization?

Rate-monotonic scheduling Rate Rate- -monotonic is optimal for fixed monotonic is optimal for fixed- -priority Maximizes task-set schedulability Ensures that max number of tasks meet their deadlines priority Scheduability Scheduability test for RM (Liu and test for RM (Liu and Layland Layland) ) Completion time m tasks Task period

Rate-monotonic scheduling Rate Rate- -monotonic is optimal for fixed monotonic is optimal for fixed- -priority Maximizes task-set schedulability Ensures that max number of tasks meet their deadlines priority Scheduability Scheduability test for RM (Liu and test for RM (Liu and Layland Layland) ) If utilization is below this number, a feasible schedule exists

Rate-monotonic scheduling Rate Rate- -monotonic is optimal for fixed monotonic is optimal for fixed- -priority Maximizes task-set schedulability Ensures that max number of tasks meet their deadlines priority Scheduability Scheduability test for RM (Liu and test for RM (Liu and Layland Layland) ) for m = 2, utilization < .83

Rate-monotonic scheduling Rate Rate- -monotonic is optimal for fixed monotonic is optimal for fixed- -priority Maximizes task-set schedulability Ensures that max number of tasks meet their deadlines priority Scheduability Scheduability test for RM (Liu and test for RM (Liu and Layland Layland) ) As long as utilization is below 0.69, RM will meet all deadlines for m , utilization < ln(2) 0.69

Rate-monotonic scheduling Rate Rate- -monotonic is optimal for fixed monotonic is optimal for fixed- -priority Maximizes task-set schedulability Ensures that max number of tasks meet their deadlines priority Scheduability Scheduability test for RM (Liu and test for RM (Liu and Layland Layland) ) Leaves roughly 31% CPU for scheduler and other stalls for m , utilization < ln(2) 0.69

Rate-monotonic scheduling T1 (Period 100ms, execution time 50ms) T1 (Period 100ms, execution time 50ms) T2 (Period 200ms, execution time 80ms) T2 (Period 200ms, execution time 80ms) Pre Pre- -empt and schedule every 50ms empt and schedule every 50ms 150 150 0 0 50 50 100 100 180 180 200 200 T2 T1 T1 T2 How is RM different than earliest-deadline first (EDF)? RM priorities are static, EDF prioritizes task closest to deadline

Scheduling overheads Runtime overhead Runtime overhead Time to decide what to run next Want fast access to TCB queues Schedulability Schedulability overhead For a given a task set Can all tasks in set be processed in time? overhead

Runtime overhead EDF EDF Tasks are kept in an unsorted list Walk the whole list to find one with earliest deadline O(1) to block/unblock a task O(n) to schedule next task RM RM Tasks are kept in a sorted list Keep pointer to highest priority ready task O(n) to block O(1) to unblock O(1) to schedule next task

Scheduability overhead EDF EDF Can schedule all workloads where 1 Zero scheduability overhead RM RM Observed utilizations of 0.88 on average for RM

Rate-monotonic scheduling ii 1 1 4 4 1.0 1.0 2 2 5 5 1.0 1.0 3 3 6 6 1.0 1.0 4 4 7 7 1.0 1.0 5 5 8 8 0.5 0.5 6 6 20 20 0.5 0.5 7 7 30 30 0.5 0.5 8 8 50 50 0.5 0.5 9 9 100 100 0.5 0.5 10 10 130 130 0.5 0.5 Pi Pi ci ci 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 T1 T2 T3 T4 T1 T2 T3 T4 What s wrong? What to run next? What to run next? What to run next? What to run next? What to run next? What to run next? What to run next? What to run next? When would T5 run under EDF?

Combined static/dynamic (CSD) Hybrid approach Hybrid approach Very useful for solving many kinds of problems Use one approach when it does well Use another approach when it does well Main idea: two queues Main idea: two queues Dynamic queue (sorted, used by EDF) Fixed queue (unsorted, used by RM) Key is figuring out which queue to put tasks on

CSD scheduling ii 1 1 4 4 1.0 1.0 2 2 5 5 1.0 1.0 3 3 6 6 1.0 1.0 4 4 7 7 1.0 1.0 5 5 8 8 0.5 0.5 6 6 20 20 0.5 0.5 7 7 30 30 0.5 0.5 8 8 50 50 0.5 0.5 9 9 100 100 0.5 0.5 10 10 130 130 0.5 0.5 Pi Pi ci ci Need to identify longest-period task that fails under RM DPQ T1 T2 T3 T4 T5 Which tasks have higher priority? FPQ T6 T7 T8 T9 T10

CSD scheduling ii 1 1 4 4 1.0 1.0 2 2 5 5 1.0 1.0 3 3 6 6 1.0 1.0 4 4 7 7 1.0 1.0 5 5 8 8 0.5 0.5 6 6 20 20 0.5 0.5 7 7 30 30 0.5 0.5 8 8 50 50 0.5 0.5 9 9 100 100 0.5 0.5 10 10 130 130 0.5 0.5 Pi Pi ci ci Need to identify longest-period task that fails under RM DPQ T1 T2 T3 T4 T5 When do FPQ tasks run? FPQ T6 T7 T8 T9 T10

CSD scheduling ii 1 1 4 4 1.0 1.0 2 2 5 5 1.0 1.0 3 3 6 6 1.0 1.0 4 4 7 7 1.0 1.0 5 5 8 8 0.5 0.5 6 6 20 20 0.5 0.5 7 7 30 30 0.5 0.5 8 8 50 50 0.5 0.5 9 9 100 100 0.5 0.5 10 10 130 130 0.5 0.5 Pi Pi ci ci 5.5 5.5 0 0 1 1 2 2 3 3 4 4 4.5 4.5 6.5 6.5 7.5 7.5 T1 T2 T3 T4 T5 T1 T2 T3 DPQ T1 T1 T2 T2 T3 T3 T4 T4 T5 T5 When would FPQ tasks run? FPQ T6 T7 T8 T9 T10 Need a DPQ task to block

CSD scheduling ii 1 1 4 4 1.0 1.0 2 2 5 5 1.0 1.0 3 3 6 6 1.0 1.0 4 4 7 7 1.0 1.0 5 5 8 8 0.5 0.5 6 6 20 20 0.5 0.5 7 7 30 30 0.5 0.5 8 8 50 50 0.5 0.5 9 9 100 100 0.5 0.5 10 10 130 130 0.5 0.5 Pi Pi ci ci 5.5 5.5 0 0 1 1 2 2 3 3 4 4 4.5 4.5 6.5 6.5 7.5 7.5 T1 T2 T3 T4 T5 T1 T2 T3 DPQ T1 T1 T2 T2 T3 T3 T4 T5 T5 What if we have a lot of tasks? FPQ T6 T7 T8 T9 T10 Time to walk DPQ could grow

CSD scheduling ii 1 1 4 4 1.0 1.0 2 2 5 5 1.0 1.0 3 3 6 6 1.0 1.0 4 4 7 7 1.0 1.0 5 5 8 8 0.5 0.5 6 6 20 20 0.5 0.5 7 7 30 30 0.5 0.5 8 8 50 50 0.5 0.5 9 9 100 100 0.5 0.5 10 10 130 130 0.5 0.5 Pi Pi ci ci 5.5 5.5 0 0 1 1 2 2 3 3 4 4 4.5 4.5 6.5 6.5 7.5 7.5 T1 T2 T3 T4 T5 T1 T2 T3 DPQ T1 T1 T2 T2 T3 T3 T4 T5 T5 Why might this be a problem? FPQ T6 T7 T8 T9 T10 May start missing deadlines

CSD scheduling ii 1 1 4 4 1.0 1.0 2 2 5 5 1.0 1.0 3 3 6 6 1.0 1.0 4 4 7 7 1.0 1.0 5 5 8 8 0.5 0.5 6 6 20 20 0.5 0.5 7 7 30 30 0.5 0.5 8 8 50 50 0.5 0.5 9 9 100 100 0.5 0.5 10 10 130 130 0.5 0.5 Pi Pi ci ci 5.5 5.5 0 0 1 1 2 2 3 3 4 4 4.5 4.5 6.5 6.5 7.5 7.5 T1 T2 T3 T4 T5 T1 T2 T3 DPQ T1 T1 T2 T2 T3 T3 T4 T5 T5 What s the solution? FPQ T6 T7 T8 T9 T10 Split DPQ into two Qs

CSD3 scheduling ii 1 1 4 4 1.0 1.0 2 2 5 5 1.0 1.0 3 3 6 6 1.0 1.0 4 4 7 7 1.0 1.0 5 5 8 8 0.5 0.5 6 6 20 20 0.5 0.5 7 7 30 30 0.5 0.5 8 8 50 50 0.5 0.5 9 9 100 100 0.5 0.5 10 10 130 130 0.5 0.5 Pi Pi ci ci DPQ 1 Which tasks go on which queue? T1 T2 T3 More frequent tasks in DPQ1 DPQ 2 T4 T5 FPQ T6 T7 T8 T9 T10

CSD3 scheduling ii 1 1 4 4 1.0 1.0 2 2 5 5 1.0 1.0 3 3 6 6 1.0 1.0 4 4 7 7 1.0 1.0 5 5 8 8 0.5 0.5 6 6 20 20 0.5 0.5 7 7 30 30 0.5 0.5 8 8 50 50 0.5 0.5 9 9 100 100 0.5 0.5 10 10 130 130 0.5 0.5 Pi Pi ci ci DPQ 1 Why is DPQ1 helpful? T1 T2 T3 Lower search time for frequent tasks. Longer searches occur less frequently. DPQ 2 T4 T5 FPQ T6 T7 T8 T9 T10

CSD3 scheduling ii 1 1 4 4 1.0 1.0 2 2 5 5 1.0 1.0 3 3 6 6 1.0 1.0 4 4 7 7 1.0 1.0 5 5 8 8 0.5 0.5 6 6 20 20 0.5 0.5 7 7 30 30 0.5 0.5 8 8 50 50 0.5 0.5 9 9 100 100 0.5 0.5 10 10 130 130 0.5 0.5 Pi Pi ci ci DPQ 1 T1 T2 T3 When do DPQ2 tasks run? DPQ 2 T4 T5 When DPQ1 is empty FPQ T6 T7 T8 T9 T10

CSD3 scheduling ii 1 1 4 4 1.0 1.0 2 2 5 5 1.0 1.0 3 3 6 6 1.0 1.0 4 4 7 7 1.0 1.0 5 5 8 8 0.5 0.5 6 6 20 20 0.5 0.5 7 7 30 30 0.5 0.5 8 8 50 50 0.5 0.5 9 9 100 100 0.5 0.5 10 10 130 130 0.5 0.5 Pi Pi ci ci DPQ 1 T1 T2 T3 DPQ 2 When do FPQ tasks run? T4 T5 When DPQ1, DPQ2 are empty FPQ T6 T7 T8 T9 T10

CSD3 scheduling ii 1 1 4 4 1.0 1.0 2 2 5 5 1.0 1.0 3 3 6 6 1.0 1.0 4 4 7 7 1.0 1.0 5 5 8 8 0.5 0.5 6 6 20 20 0.5 0.5 7 7 30 30 0.5 0.5 8 8 50 50 0.5 0.5 9 9 100 100 0.5 0.5 10 10 130 130 0.5 0.5 Pi Pi ci ci DPQ 1 T1 T2 T3 What is the downside of DPQ2? DPQ 2 T4 T5 Schedualibility suffers FPQ T6 T7 T8 T9 T10

CSD3 scheduling ii 1 1 4 4 1.0 1.0 2 2 5 5 1.0 1.0 3 3 6 6 1.0 1.0 4 4 7 7 1.0 1.0 5 5 8 8 0.5 0.5 6 6 20 20 0.5 0.5 7 7 30 30 0.5 0.5 8 8 50 50 0.5 0.5 9 9 100 100 0.5 0.5 10 10 130 130 0.5 0.5 Pi Pi ci ci DPQ 1 T1 T2 T3 T4 What if DPQ2 only has T5? DPQ 2 T5 We re back to missing its deadline FPQ T6 T7 T8 T9 T10

CSD3 scheduling ii 1 1 4 4 1.0 1.0 2 2 5 5 1.0 1.0 3 3 6 6 1.0 1.0 4 4 7 7 1.0 1.0 5 5 8 8 0.5 0.5 6 6 20 20 0.5 0.5 7 7 30 30 0.5 0.5 8 8 50 50 0.5 0.5 9 9 100 100 0.5 0.5 10 10 130 130 0.5 0.5 Pi Pi ci ci DPQ 1 T1 T2 T3 T4 What s the solution? DPQ 2 T5 Exhaustive offline search! FPQ T6 T7 T8 T9 T10

Synchronization General approach General approach Integrate synchronization with scheduling Same approach as 310 thread library Main primitive: semaphores Main primitive: semaphores Initialize w/ value one to use as a lock Initizlize w/ value zero to use for ordering (e.g., CV)

Synchronization Semaphores Semaphores w w/ priority inheritance for locking / priority inheritance for locking if (sem locked) { do priority inheritance; add calling thread to wait queue; block; } lock sem;

Synchronization Tx Tx How do we get rid of this context switch? Schedule T1 before T2 unlock unlock T1 T1 (lock holder) (lock holder) lock lock T2 T2

Synchronization Tx Tx What extra info must be passed to blocking call? ID of semaphore to be acquired unlock unlock T1 T1 (lock holder) (lock holder) lock lock T2 T2

Synchronization Tx Tx Checks if semaphore is held. If so, transfers T2 priority to T1. Blocks T2 on semaphore wait list. What does the scheduler do before it tries to run T2? unlock unlock T1 T1 (lock holder) (lock holder) lock lock T2 T2

Synchronization Tx Tx When T1 releases the lock. This transfers T2 priority back to T2. When is T2 unblocked? unlock unlock T1 T1 (lock holder) (lock holder) lock lock T2 T2

Synchronization Tx Tx unlock unlock T1 T1 (lock holder) (lock holder) lock lock T2 T2

Communication Typical access pattern Typical access pattern One task reading a sensor Many tasks processing sensor values Single writer, multiple readers Could use producer Could use producer- -consumer queue Writer acquires lock on shared queue Readers block acquiring lock to read queue Writer adds new value to queue Readers take turns acquiring lock, reading value Too slow for an embedded system Too slow for an embedded system consumer queue

Communication Note this is for a uni-processor. System is concurrent, but not parallel. R0 Reader R1 R2 R3 Writer R4 R5 Index = 0 Index = 0 Reader State Message State Message

Communication What is the difference between concurrency and parallelism? R0 Reader R1 R2 Parallelism is when threads run R3 Writer at the same time. Concurrency is when threads execution overlaps in time. R4 R5 Index = 0 Index = 0 Reader State Message State Message

Communication R0 What operations are atomic? Reader R1 R2 R3 Loads and stores to access B bytes. Writer R4 R5 Index = 0 Index = 0 Reader State Message State Message

Communication Do I need this circular buffer if my data is B bytes? R0 Reader R1 R2 No, can just update with load or store. Value R3 Writer won t be partially written. Need buffers when data is > B bytes. R4 R5 Index = 0 Index = 0 Reader State Message State Message

Communication R0 To update SM: To update SM: (1) (1) Read new sensor value Read new sensor value (2) (2) Read index into Read index into ii (3) (3) Write value to (i+1)%6 Write value to (i+1)%6 (4) (4) Update index to (i+1)%6 Update index to (i+1)%6 Reader R1 To read SM: To read SM: (1) (1) Read index into Read index into ii (2) (2) Read value at Read value at buffer[i R2 buffer[i] ] R3 What happens if reader runs Writer between 1 and 2? R4 R5 Index = 0 Index = 0 Sees old value Reader State Message State Message

Communication R0 To update SM: To update SM: (1) (1) Read new sensor value Read new sensor value (2) (2) Read index into Read index into ii (3) (3) Write value to (i+1)%6 Write value to (i+1)%6 (4) (4) Update index to (i+1)%6 Update index to (i+1)%6 Reader R1 To read SM: To read SM: (1) (1) Read index into Read index into ii (2) (2) Read value at Read value at buffer[i R2 buffer[i] ] R3 What happens if reader runs Writer between 3 and 4? R4 R5 Index = 0 Index = 0 Sees old value Reader State Message State Message

Communication R0 To update SM: To update SM: (1) (1) Read new sensor value Read new sensor value (2) (2) Read index into Read index into ii (3) (3) Write value to (i+1)%6 Write value to (i+1)%6 (4) (4) Update index to (i+1)%6 Update index to (i+1)%6 Reader R1 To read SM: To read SM: (1) (1) Read index into Read index into ii (2) (2) Read value at Read value at buffer[i R2 buffer[i] ] R3 Writer R4 What happens if writer runs between 1 and 2? R5 Index = 0 Index = 0 Reader State Message State Message Sees old value

Communication R0 To update SM: To update SM: (1) (1) Read new sensor value Read new sensor value (2) (2) Read index into Read index into ii (3) (3) Write value to (i+1)%6 Write value to (i+1)%6 (4) (4) Update index to (i+1)%6 Update index to (i+1)%6 Reader R1 To read SM: To read SM: (1) (1) Read index into Read index into ii (2) (2) Read value at Read value at buffer[i R2 buffer[i] ] R3 Writer R4 What happens if writer runs 6 times between start of 2 and end of 2? R5 Index = 0 Index = 0 Reader will see garbled value Reader State Message State Message

Communication R0 To update SM: To update SM: (1) (1) Read new sensor value Read new sensor value (2) (2) Read index into Read index into ii (3) (3) Write value to (i+1)%6 Write value to (i+1)%6 (4) (4) Update index to (i+1)%6 Update index to (i+1)%6 Reader R1 To read SM: To read SM: (1) (1) Read index into Read index into ii (2) (2) Read value at Read value at buffer[i R2 buffer[i] ] R3 Writer R4 What happens if writer runs 6 times between start of 2 and end of 2? R5 Index = 0 Index = 0 Reader will see garbled value Reader State Message State Message

Communication Could make the buffer longer Could make the buffer longer Making the buffer too long will waste memory Idea Idea We know how long read and write tasks take Set buffer length based on longest a read could take d is reader s period (deadline) c is reader s compute time cr is time to read value maxReadTime maxReadTime = = d d ( (c c cr cr) )

Communication Could make the buffer longer Could make the buffer longer Making the buffer too long will waste memory Idea Idea We know how long read and write tasks take Set buffer length based on longest a read could take xmax is max writes that could garble values Pw is writer s period dw is writer s deadline maxReadTime maxReadTime = = d d ( (c c cr cr) ) xmax xmax > > FLOOR((maxReadTime FLOOR((maxReadTime (Pw (Pw dw dw))/Pw) ))/Pw)

Communication Could make the buffer longer Could make the buffer longer Making the buffer too long will waste memory Idea Idea We know how long read and write tasks take Set buffer length based on longest a read could take maxReadTime maxReadTime W W W W W W W W W W pw pw dw dw maxReadTime maxReadTime = = d d ( (c c cr cr) ) xmax xmax > > FLOOR((maxReadTime FLOOR((maxReadTime (Pw (Pw dw dw))/Pw) ))/Pw)

Course administration Research projects Research projects Study use of native code in Android apps Build a FUSE file system for Linux