More Scheduling

These are lecture notes from my Computer Science course. For learning about real-time systems, I recommend Real-Time Systems and Programming Languages.

Extensions on Task Model

  • Release Jitter:
  • Arbitrary Deadlines: Where the deadline is greater than the period.
  • Cooperative Scheduling: True preemptive behaviour is not always acceptable for safety-critical systems. But pure non-preemptive reduces schedulability. Cooperative scheduling is a compromise. Blocks of code specify when they are prepared to be pre-empted.
  • Fault Tolerance: Coping with a certain level of faults during execution and still meet deadline.

As an aside, it’s good to be able to do response time analysis from a table of tasks with intervals etc.

Checking all possible orderings of task is a factorial operation; it can’t be done. But there’s a nifty algorithm called ‘Audsley’s Algorithm’ which turns it into an n^2 problem. You do this by picking the lowest priority task and putting it at the bottom, then work your way up, not touching that one that has fitted at the bottom. Apparently this works.

Methods of scheduling

Cyclic Executive

In a system where you know what’s going to happen to a bunch of tasks, you can generate a fixed major cycle (composed of different minor cycles) to ensure all tasks run and meet their deadlines. This has really big problems though:

  • You can’t handle sporadic tasks very well.
  • Tasks with long periods are difficult to handle – you end up with big major cycles.
  • It’s an NP-hard problem to actually make a cyclic executive (bin packing).
  • A big task will need to be split across fixed size procedures; this might be error prone.

Task-based scheduling

When discussing task-based scheduling, random annoying variables are just ignored. For example the application just has a fixed set of tasks running on one CPU where no tasks have internal delays based on I/O and you know the worst-case execution time for all tasks, and context switching is instant. And so on.

There are 3 main scheduling approaches for task-based scheduling. We will mostly consider Fixed-Priority Scheduling.

  • Fixed-Priority Scheduling is the most widely used. Each task has a fixed static priority which is computed pre-run time. The priority is based on the task’s temporal requirements, not its importance in the system.
  • Earliest Deadline First is where runnable tasks are executed based on which one has the nearest deadline.
  • Value-Based Scheduling is adaptive; assign a value to each task and employ an online value-based scheduling algorithm to decide which task to run next.

Sufficient and Necessary

You can test schedules to see if they will allow tasks to meet their deadlines. Tests can be sufficient and/or necessary (if a test is both, it is exact, though this is often difficult to work out).

  • A test is sufficient if a positive outcome guarantees all deadlines are always met. However a negative outcome doesn’t necessarily mean the task set is going to fail.
  • A test is necessary if a negative outcome guarantees a deadline miss at some point during execution.

Generally a sufficient test that isn’t too pessimistic will do.

Fixed-Priority Scheduling

Really simple: Priorities (1 is lowest) are assigned to tasks based on their period. The longer the period, the lower the priority.

Testing it

There are a few different tests for FPS. You can test based on utilization; so long as utilization isn’t over a certain value then it’ll be OK. There are different levels of pessimism with these tests. Details are on the slides or in the book (p371-374).

You can also test using Response Time Analysis. This is based on the theory that the worst-case response time (R) for a task is based on the interference from higher-priority tasks. The equations for this are discussed in detail in the slides or in the book (p375-378).

This entry was posted in lecture, rts. Bookmark the permalink.