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
