#2510 closed enhancement (fixed)

Improve the SMP scheduler with arbitrary processor affinity support

Reported by: Sebastian Huber Owned by: Sebastian Huber
Priority: normal Milestone: Indefinite
Component: score Version:
Severity: normal Keywords: SoC executive
Cc: richidubey@… Blocked By:


The SMP scheduler with arbitrary processor affinity support uses a proof of concept implementation.

A potentially more efficient implementation is available here:

  1. Cerqueira, A. Gujarati, and B. Brandenburg, "Linux’s Processor Affinity API, Refined: Shifting Real-Time Tasks towards Higher Schedulability", Proceedings of the 35th IEEE Real-Time Systems Symposium (RTSS 2014), pp. 249-259, December 2014.


Change History (17)

comment:1 Changed on 01/05/16 at 17:35:28 by Gedare Bloom

Do you intend to implement this?

comment:2 Changed on 01/05/16 at 20:23:56 by Sebastian Huber

I currently do not plan to implement this. I came across this paper by accident. It would be a useful improvement from my point of view.

comment:3 Changed on 02/01/16 at 13:17:56 by Darshit

We would first need to identify the potential functional changes that this would bring into the existing scheduler and the expected performance improvements. Irrespective of expected improvements, it would still be nice to actually provide the option for such a scheduler.

I've been looking into the existing schedulers implemented in RTEMS but am unsure on how exactly to evaluate them with respect to the new scheduler being proposed here.

comment:4 Changed on 02/02/16 at 06:56:58 by Sebastian Huber

You find the basic SMP scheduler implementation here:


We have currently three specialized implementations. All are clustered FP schedulers.

Simple Priority SMP


It uses a sorted list for the ready threads.

Priority SMP


It uses a table based priority queue.

Priority Affinity SMP


This is the one that should be improved. To evaluate its current time complexity, just look at the while and for loops in the code.

comment:5 Changed on 05/02/16 at 10:09:30 by Sebastian Huber <sebastian.huber@…>

In 981eed21761cd0036f0ac61042adea09d8a595a2/rtems:

score: Add dummy Strong APA scheduler

Start with a copy of the Priority SMP scheduler implementation.

Update #2510.

comment:6 Changed on 07/05/16 at 10:28:50 by Darshit

Processor Affinity Set Data Structures

For the scheduler, we need to store the "processor affinity sets" in the nodes. I have reused the code for the Priority Affinity SMP Scheduler to add support for affinity sets. This uses the cpu_set_t data structure to store the affinity set information in Scheduler_strong_APA_Node. For the implementation of the algorithm, certain logical operations on the lists will be useful, especially, set intersection and set union. These operations are already supported by the cpu_set_t data structure, which is why I decided to stick with this structure instead of using Processor_mask or writing something new.

The Algorithm

On arrival of a new task in the system, the _Scheduler_strong_APA_Unblock action will be triggered. The core of the algorithm, the iterative MVM solution will be implemented in this method itself. The output of the algorithm will be a mapping of processors to the thread that they are executing. This mapping will look something like this:

Thread_control *processor_to_task_mapping [ _SMP_Get_processor_count() ];

Where index 0 points to the thread executing on CPU 0, and so on. Initially, the entire array will point to the idle thread.

Then, during the Enqueue_ordered operation, if _get_lowest_scheduled() returns a thread that has a lower priority than the arriving task, the case becomes trivial and we only need to carry out the standard forced migrations during the call to move_from_scheduled_to_ready.

However, if the lowest scheduled task according to the affinity set has a higher priority than the arriving task, then we may need to carry out non-standard task migrations for the most optimal configuration. These migrations will be performed based on the MVM solution set created during the Unblock operation and will be implemented in the _Scheduler_strong_APA_Insert_ready_fifo method.

comment:7 Changed on 08/13/17 at 23:46:52 by Chris Johns

Milestone: 5.0Indefinite
Version: 4.11

comment:8 Changed on 10/10/17 at 06:27:10 by Sebastian Huber

Component: SMPscore

comment:9 Changed on 10/10/17 at 06:29:01 by Sebastian Huber

Component: scorecpukit

comment:10 Changed on 03/15/19 at 15:22:18 by Joel Sherrill

Keywords: SoC added

comment:11 Changed on 03/15/19 at 15:23:34 by Joel Sherrill

Keywords: kernel added

comment:12 Changed on 03/15/19 at 15:24:26 by Joel Sherrill

Keywords: SoC, kernelSoC kernel

comment:13 Changed on 03/15/19 at 20:00:06 by Gedare Bloom

Keywords: SoC kernelSoC,kernel

comment:14 Changed on 03/15/19 at 20:01:21 by Gedare Bloom

Keywords: executive added; kernel removed

comment:15 Changed on 01/14/20 at 21:07:06 by Gedare Bloom

Owner: set to Sebastian Huber
Status: newassigned

comment:16 Changed on 04/08/21 at 07:37:38 by Richi Dubey

I have been working on this ticket since May 2020 (first as part of GSoC 2020 project) , and this ticket is about to be closed very soon :)
I would continue to work on it and provide status.

Link to project: https://summerofcode.withgoogle.com/archive/2020/projects/6529555772211200/

Last edited on 04/08/21 at 07:39:01 by Richi Dubey (previous) (diff)

comment:17 Changed on 01/14/22 at 07:14:57 by Richi Dubey

Cc: richidubey@… added
Resolution: fixed
Status: assignedclosed
Note: See TracTickets for help on using tickets.