Re: [RFC PATCH 2/3] docs: scheduler: Add scheduler overview documentation

[Daniel Bristot de Oliveira]

On 4/1/20 12:35 PM, Peter Zijlstra wrote:
>> +Scheduler State Transition
>> +==========================
>> +
>> +A very high level scheduler state transition flow with a few states can be
>> +depicted as follows.
>> +
>> +.. kernel-render:: DOT
>> +   :alt: DOT digraph of Scheduler state transition
>> +   :caption: Scheduler state transition
>> +
>> +   digraph sched_transition {
>> +      node [shape = point,  label="exisiting task\n calls fork()"]; fork
>> +      node [shape = box, label="TASK_NEW\n(Ready to run)"] tsk_new;
>> +      node [shape = box, label="TASK_RUNNING\n(Ready to run)"] tsk_ready_run;
>> +      node [shape = box, label="TASK_RUNNING\n(Running)"] tsk_running;
>> +      node [shape = box, label="TASK_DEAD\nEXIT_ZOMBIE"] exit_zombie;
>> +      node [shape = box, label="TASK_INTERRUPTIBLE\nTASK_UNINTERRUPTIBLE\nTASK_WAKEKILL"] tsk_int;
>> +      fork -> tsk_new [ label = "task\nforks" ];
>> +      tsk_new -> tsk_ready_run;
>> +      tsk_ready_run -> tsk_running [ label = "schedule() calls context_switch()" ];
>> +      tsk_running -> tsk_ready_run [ label = "task is pre-empted" ];
>> +      subgraph int {
>> +         tsk_running -> tsk_int [ label = "task needs to wait for event" ];
>> +         tsk_int ->  tsk_ready_run [ label = "event occurred" ];
>> +      }
>> +      tsk_int ->  exit_zombie [ label = "task exits via do_exit()" ];
>> +   }
> And that is a prime example of why I hates RST, it pretty much mandates
> you view this with something other than a text editor.

The good thing about the dot format is that we can convert it to many other
formats, including text:

[bristot@x1 ~]$ cat sched_transition.dot | graph-easy 

                       *

                       |
                       | task
                       | forks
                       v
                     +------------------------------------+
                     |              TASK_NEW              |
                     |           (Ready to run)           |
                     +------------------------------------+
                       |
                       |
                       v
+ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -+
'                                     int                                            '
'                                                                                    '
'                    +------------------------------------+                          '
'                    |            TASK_RUNNING            |                          '
'   +--------------> |           (Ready to run)           | <--+                     '
'   |                +------------------------------------+    |                     '
'   |                  |                                       |                     '
'   |                  | schedule() calls context_switch()     | task is pre-empted  '
'   |                  v                                       |                     '
'   |                +------------------------------------+    |                     '
'   |                |            TASK_RUNNING            |    |                     '
'   |                |             (Running)              | ---+                     '
'   | event occurred +------------------------------------+                          '
'   |                  |                                                             '
'   |                  |                                      - - - - - - - - - - - -+
'   |                  |                                    '
'   |                  | task needs to wait for event       '
'   |                  v                                    '
'   |                +------------------------------------+ '
'   |                |         TASK_INTERRUPTIBLE         | '
'   |                |        TASK_UNINTERRUPTIBLE        | '
'   +--------------- |           TASK_WAKEKILL            | '
'                    +------------------------------------+ '
'                                                           '
+ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +
                       |
                       | task exits via do_exit()
                       v
                     +------------------------------------+
                     |             TASK_DEAD              |
                     |            EXIT_ZOMBIE             |
                     +------------------------------------+


Is there a way to also add this representation, while hiding it
when using a graphical reader?

PS: I know nothing about rst, only about rts - real-time systems...
yeah, it is a bad joke haha.

> Also, Daniel, you modeled all this, is the above anywhere close?

hum... let's say that we modeled things we a different goal. Here the
idea is to explain, document... not to create an explicit model.

For instance, there is the context switch _in_, but not the _out_ in the
above example.

But, well, if the goal is to document, it is nice to have graphical
representations.

>> +Scheduler provides trace points tracing all major events of the scheduler.
>> +The tracepoints are defined in ::
>> +
>> +  include/trace/events/sched.h
>> +
>> +Using these treacepoints it is possible to model the scheduler state transition
>> +in an automata model. The following conference paper discusses such modeling.

this is a workshop paper.

>> +
>> +https://www.researchgate.net/publication/332440267_Modeling_the_Behavior_of_Threads_in_the_PREEMPT_RT_Linux_Kernel_Using_Automata
> Ah, you've found Daniel ;-)

:-)

This is a better reference (a journal paper).

Daniel B. de Oliveira, RÃmulo S. de Oliveira, Tommaso Cucinotta, **A thread
synchronization model for the PREEMPT_RT Linux kernel**, *Journal of Systems
Architecture*, Volume 107, 2020, 101729, ISSN 1383-7621,
https://doi.org/10.1016/j.sysarc.2020.101729.

-- Daniel