Applying C - Deadline Scheduling
Written by Harry Fairhead   
Monday, 12 August 2019
Article Index
Applying C - Deadline Scheduling

Scheduling is complicated and generally it is assumed that Linux can't do realtime scheduling but now there is deadline scheduling which solves many problems. This extract is from my  book on using C in an IoT context.

Now available as a paperback or ebook from Amazon.

Applying C For The IoT With Linux

  2. Kernel Mode, User Mode & Syscall
  3. Execution, Permissions & Systemd
    Extract Running Programs With Systemd
  4. Signals & Exceptions
    Extract  Signals
  5. Integer Arithmetic
    Extract: Basic Arithmetic As Bit Operations
    Extract: BCD Arithmetic  ***NEW
  6. Fixed Point
    Extract: Simple Fixed Point Arithmetic
  7. Floating Point 
  8. File Descriptors
    Extract: Simple File Descriptors 
    Extract: Pipes 
  9. The Pseudo-File System
    Extract: The Pseudo File System
    Extract: Memory Mapped Files 
  10. Graphics
    Extract: framebuffer
  11. Sockets
    Extract: Sockets The Client
    Extract: Socket Server
  12. Threading
    Extract:  Pthreads
    Extract:  Condition Variables
    Extract:  Deadline Scheduling
  13. Cores Atomics & Memory Management
    Extract: Applying C - Cores 
  14. Interupts & Polling
    Extract: Interrupts & Polling 
  15. Assembler
    Extract: Assembler

Also see the companion book: Fundamental C




Earlier in the chapter but not in this extract:

  • Why Multi-task?
  • To Thread or Fork
  • Pthreads
  • The Thread Attributes Object
  • Joinable And Detached Threads
  • Threads and Scope - Thread Local
  • Atomic Operations and Locks
  • Mutex
  • Condition Variables
  • First Thread to Finish
  • Scheduling

Deadline Scheduling

For real time tasks FIFO scheduling is appropriate. However, if you are using a modern version of Linux there’s a better choice. Earliest Deadline Scheduling (EDS) is new recently introduced (Kernel 3.14) Linux scheduling policy. Due to its recent introduction and because it isn’t a POSIX scheduling method, it isn't widely used, but it does have many good properties for realtime tasks.

A SCHED_DEADLINE thread is associated with three parameters – runtime, period and deadline. The thread will receive runtime nanoseconds of execution every period nanoseconds and deadline specifies in nanoseconds how delayed into the period the allocation can be. If a thread takes longer than its runtime period the operating system suspends it and restarts it at its next activation period.

It is also useful to know that in this case sched_yield suspends the thread until its next time period starts. This means you can give time back to the system if you have overestimated how long a task should take.

Notice that times are specified in nano seconds (ns) but micro seconds (us) are more reasonable for describing how long a real world task is likely to take.

For example, if runtime is 10 us, period 100 us and deadline 20 us you can be sure that the thread will get 10 us every 100us and the maximum delay from the start of the 100 us period is 20 us. If the thread is, say, setting a hardware line high at the start of the 10us and low at the end, the pulses will be 10us wide and repeat every 100us, but with a jitter of 20 us from the start of the 100us period, i.e. a pulse could be up to 20us late. This only works if the system isn’t overloaded and there are enough CPUs to satisfy all of the demands. As long as the system isn’t overloaded then the scheduling algorithm is proven to meet the specifications of period and deadline.

You may be wondering how Linux can manage to operate with threads that have different scheduler policies?

The answer is that Linux has a modular scheduler which can be expanded by the addition of new classes. At the moment there are four scheduler classes - idle, cfs, rt and dl in order of priority. Any Deadline tasks are scheduled first, then FIFO, then Round Robin and finally Normal. What this means is that if there are any runnable Deadline threads these take precedence of any other type of thread. However, to keep the system running, Linux only allows Deadline tasks to add up to 95% of the available computing time. This leaves no less than 5% for the other schedulers.

To set deadline scheduling you have to use the Linux-specific calls and these are not available as easy-to-call functions in the GNU libraries. Fortunately it is very easy to use a direct Linux syscall:

int sched_setattr(pid, struct sched_attr *attr, flags);

where pid is the Linux process id and not the thread id returned by Pthreads. If this is 0 then the current thread is used. The second parameter is a pointer to a new struct which sets the properties of the scheduling policy. flags is an integer which is currently unused and should be set to 0.

To make use of this function we need a definition of the new struct. While there is a definition in one of the Linux-specific headers, it is simpler to include it in your program:

struct sched_attr {
    uint32_t size;
    uint32_t sched_policy;
    uint64_t sched_flags;
    int32_t sched_nice;
    uint32_t sched_priority;
    uint64_t sched_runtime;
    uint64_t sched_deadline;
    uint64_t sched_period;

with size as the size of the struct and policy specifying the policy using the same constants as used earlier plus the new SCHED_DEADLINE. The flags field is only used for one obscure thing and can mostly be set to zero and ignored. The next two fields control what happens under SCHED_OTHER/BATCH and SCHED_FIFO/RR respectively. The final three fields control SCHED_DEADLINE. To use these constants you need to add:

#include <linux/sched.h>

The function call has to be implemented as a Linux syscall so you also need to add:

#include <sys/syscall.h>
int sched_setattr(pid_t pid, 
const struct sched_attr *attr,
unsigned int flags) { return syscall(__NR_sched_setattr, pid, attr, flags); }

There is also a related getattr call:

int sched_getattr(pid_t pid,struct sched_attr *attr, 
unsigned int size,unsigned int flags){ return syscall(__NR_sched_getattr, pid, attr,
size, flags); }

The whole idea of EDS is that any task that has to be done on a regular basis can be given a guarantee that it will not miss its appointments. For example, suppose you need to check that a sensor is within range every few seconds. The actual reading takes little time, but in a priority based scheduler it could be that a high priority task blocks access to the CPU for so long that multiple readings are missed. You can be sure that the deadlines will be met because the scheduler computes the feasibility of the requested schedule and setattr will return with an EBUSY error when you add a thread that makes it impossible.

Last Updated ( Monday, 12 August 2019 )