19_Scheduling

1 .Lecture 19 – Scheduling Describe how priorities affect thread execution Describe and give an example of priority inversion Discuss the factors involved in real-time scheduling Given a set of tasks, determine if it is possible to schedule them so that all deadlines are met using a time-line graph Apply the conditions of Liu and Layland to determine analytically if real-time scheduling is possible Describe rate-monotonic sequencing , and use it to schedule a given set of tasks Learning Goals © Paul Davies, C. Antonio Sanchez. Not to be copied, used, or revised without explicit written permission from the copyright owner.

2 .Process Priority All operating systems assign a numerical priority to each thread/process. This indicates the thread’s relative importance . High priority threads are always scheduled to be run in preference to lower priority threads whenever they are not blocked. A high-priority process/thread should be able to pre-empt (i.e. displace) a low priority one. That is, it even if a low priority thread has started, it can be interrupted by the high priority thread. Intro to System Software Engineering 2

3 .Priority Inversion This thread pre-emption can introduce an issue known as priority inversion . Imagine a low priority task that has acquired some non-sharable resource (i.e. has acquired a mutex lock) A high priority task comes along and tries to wait for the resource to become free (it is blocked, and can’t steal the resource from the low-priority task) A medium priority task comes along and pre-empts the low priority task. Intro to System Software Engineering 3 mutex pre-empt wait pre-empt low priority high priority med priority Medium priority task is indirectly blocking execution of higher priority, even though their actions are independent (no shared resources)

4 .Priority Inversion Priority inversion: when a lower-priority indirectly pre-empts a higher-priority task even though they are independent (no shared resources). Usually harmless, only serving to delay higher-priority task. Lead to problems with the Mars Pathfinder Mission in 1997: Higher priority process could never finish on time, triggered a watchdog timer on the lander to reset the system multiple times, jeopardizing the mission. Intro to System Software Engineering 4

5 .Priority Inversion The most common solution to priority inversion is priority inheritance : when a lower-priority task blocks a higher priority task due to a shared resource, the priority of the lower task is temporarily raised by the OS to that of the waiting task. When the resource is released, the priority is returned. Intro to System Software Engineering 5 mutex pre-empt wait low priority high priority med priority unlock raise priority

6 .Real-Time Scheduling Many real-time systems can be broken-down into a set of regularly scheduled tasks, each with either fixed or bounded worst-case compute times . Intro to System Software Engineering 6 c1 c2 c3 A Periodic Task ‘ C ’ being triggered every 50 ms 0 10 20 30 40 50 60 70 80 90 100 110 120 C triggered for the 1 st time C triggered for the 2 nd time C triggered for the 3rd time Time ms e.g. Cruise control: monitors car’s speed every 500 ms and outputs correction to throttle (max time: 10 ms )

7 .Real-Time Scheduling Period: time between successive triggering of the task Deadline: maximum time available to complete execution (i.e. produce a response) Compute time: (maximum) CPU time required to generate the response Intro to System Software Engineering 7 c1 c2 c3 A Periodic Task ‘ C ’ being triggered 3 times, once every 50 ms each with a deadline time of 40ms and compute time of 5ms Time ms 0 10 20 30 40 50 60 70 80 90 100 110 120 Period of ‘C’ = 50ms Period of ‘C’ = 50ms Deadline of ‘C’ = 40ms Deadline of ‘C’ = 40ms Compute time of C = 5ms compute time <= deadline deadline <= period (usually)

8 .Real-Time Scheduling Soft Deadlines: if missing the occasional deadline is acceptable (e.g. a car’s cruise control generates at 600 ms instead of 500 ms once or twice) Hard Deadlines: deadline must be met each and every time or else system fails (e.g. pacemaker, Therac 25) Intro to System Software Engineering 8 Given two processes, A: period = 500ms soft deadline = 500ms compute time = 200ms B: period = 1000ms hard deadline = 1000ms compute time = 200ms Is it possible to schedule them on a single CPU? B A A A A A B B 0 500 1000 1500 2000 2500

9 .Real-Time Scheduling Intro to System Software Engineering 9 A: period = 500ms soft deadline = 500ms compute time = 200ms B: period = 1000ms hard deadline = 600ms compute time = 600ms B A A B A A B A: period = 500ms hard deadline = 500ms compute time = 200ms B: period = 1000ms hard deadline = 600ms compute time = 600ms 100% CPU Usage 0 500 1000 1500 2000 2500

10 .Real-Time Scheduling Is it possible to analyze a given set of N periodic tasks and guarantee with 100% certainty that each can be scheduled to meet it’s deadline each time it is triggered? If so, how do we make it happen ? i.e. force the OS to schedule the tasks so that no deadlines are missed. Intro to System Software Engineering 10 Possible Approach: Prioritize and schedule work based on shortest deadline = highest priority Example: Antonio gives you a lab and says it’s due in two weeks Another prof gives you an assignment and says it’s due Friday Which do you prioritize?

11 .Real-Time Scheduling It is necessary for tasks to be able to pre-empt each other, based on priority. Rate-Monotonic Scheduling (RMS): a static priority is assigned at compile time according to activation period of the job (shorter period  higher priority) Intro to System Software Engineering 11 An assignment that takes 1 day to complete every 5 days. An assignment that takes 1.5 days to complete every 4 days. An assignment that takes 1 day to complete every 3 days. Can you figure out how to prioritize your time, when exactly you will be working and when you would be idle? Note : Assume that you have to decide how to prioritise these tasks at the start of term and cannot change your priorities later. Plot a graph showing when you would be working on each assignment.

12 .Real-Time Scheduling Intro to System Software Engineering 12 B1 A1 0 2 4 6 8 10 A2 B2 B3 C1 C2 C3 . . . A takes 1/5 = 20% your life cycle B takes 3/8 = 37.5% your life cycle C takes 1/3 = 33% your life cycle Total: 90.83% life usage Periods and ”Computation times”: B1 A1 0 2 4 6 8 10 A2 B2 B3 C1 C2 C3 . . . C4 C4

13 .Real-Time Scheduling Two ways to analyze a set of periodic tasks to guarantee with 100% accuracy that they will or will not always meet their individual deadlines: Draw a time line graph to show how you would perform the tasks. Draw the graph until the pattern repeats (lowest-common multiple of periods) Analyze the set of tasks to show mathematically that they always met their deadline Approach 2 is the most desirable since it is quick, but unfortunately does not always give a definitive answer. Approach 1 is time consuming, but always gives an answer. Intro to System Software Engineering 13

14 .Real-Time Scheduling Liu and Layland (1973) show that a set of M tasks will definitely not meet their deadlines if Intro to System Software Engineering 14 If the CPU utilisation is > 100%, tasks will not meet their deadline i.e. they will fail at some time   The above expression does not guarantee they will succeed if <= 1. In that case we have to analyse the task set further to determine if they will meet their deadlines in practice. is the trigger period/deadline is the compute time / is the fraction of CPU time taken by task i  

15 .Real-Time Scheduling Intro to System Software Engineering 15 An assignment that takes 1 day to complete every 5 days. An assignment that takes 1.5 days to complete every 4 days. An assignment that takes 1 day to complete every 3 days. 1/5 + 3/8 + 1/3 = 90.83% Possibility of success Liu and Layland wend further: if the tasks are scheduled on the basis of shorter deadline first , then it IS guaranteed that tasks will meet their deadlines if   If CPU utilization is between the range:   3  must draw graph for 60 days   then we must draw a time-line graph .

16 .Real-Time Scheduling Intro to System Software Engineering 16 Task A with period 100 ms , compute time 20 ms Task B with period 200 ms , compute time 40 ms Task C with period 300 ms , compute time 50 ms   

17 .Real-Time Scheduling Intro to System Software Engineering 17 Task A with compute time 5 ms , period 20 ms Task B with compute time 10 ms , period 30 ms Task C with compute time 10 ms , period 40 ms    Try scheduling tasks as shortest deadline = highest priority and pre-emptive scheduling When task A wants to run, it can pre-empt either task B or C B can pre-empt C but not A. Assume all tasks released at the same time (the worst case scenario), but A, having the highest priority, runs first.

18 .Real-Time Scheduling Intro to System Software Engineering 18 B1 A1 0 20 40 60 80 100 C1 Task A with compute time 5 ms , period 20 ms Task B with compute time 10 ms , period 30 ms Task C with compute time 10 ms , period 40 ms 120 A2 A3 A4 A5 A6 B2 B3 B4 C2 C3 A1 B1 A2 C1 B2 A3 C2 A4 B3 A5 C3 B4 A6 C3 C1 RMS A B C CPU Utilization  

19 .Real-Time Scheduling Intro to System Software Engineering 19 Task A with compute time 6 ms , period 20 ms Task B with compute time 10 ms , period 30 ms Task C with compute time 10 ms , period 40 ms    B1 A1 0 20 40 60 80 100 C1 120 A2 A3 A4 A5 A6 B2 B3 B4 C2 C3 A1 B1 A2 C1 B2 C1 RMS A B C C1 A3 4ms 4ms C1 missed its deadline by 2 ms 

20 .Rate-Monotonic Scheduling Intro to System Software Engineering 20 Rate-Monotonic Scheduling , Liu and Layland (1973), is a real-time operating system scheduling algorithm for pre-emptable periodic processes with static (fixed) priorities. Assumes: Tasks are periodic and have hard deadlines Tasks are independent (i.e. none blocks for any other due to mutex) Each task is deterministic (we can calculate the exact worst-case compute time) Task swapping occurs in zero time Implementation: Sort tasks by increasing deadline, assign decreasing priorities i.e. higher the rate, higher the priority (rate-monotic scheduling)

21 .Process/Thread Priorities (Windows) Intro to System Software Engineering 21 Priorities range from 1 to 31, determined by a Priority Class for the process Priority Level for the thread https://msdn.microsoft.com/en-us/library/windows/desktop/ms685100(v=vs.85).aspx BOOL SetThreadPriority( HANDLE hThread, int nPriority ); BOOL SetPriorityClass( HANDLE hProcess, DWORD dwPriorityClass );

22 .Process/Thread Priorities (POSIX) Intro to System Software Engineering 22 https://developer.apple.com/library/content/documentation/Darwin/Conceptual/KernelProgramming/scheduler/scheduler.html Process/thread priorities work differently depending on a schedule policy: SCHED_FIFO ,  SCHED_RR , or  SCHED_OTHER By default, true priority value depends on a process’s nice value, and a thread’s assigned priority ( SCHED_OTHER ) . SCHED_FIFO and  SCHED_RR ignore the nice value, allow direct setting of thread priorities, typically in range [1, 99] pthread_setschedparam(pthread_t thread, int policy, struct sched_param *param); int setpriority(int  which , id_t   who , int   value ); // modifies the “nice” value   https://linux.die.net/man/3/pthread_setschedparam