Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Subject: Re: [RFC PATCH 2/3] docs: scheduler: Add scheduler overview
 documentation
To:     Peter Zijlstra <peterz@infradead.org>,
        John Mathew <john.mathew@unikie.com>
Cc:     linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org,
        corbet@lwn.net, mingo@redhat.com, juri.lelli@redhat.com,
        vincent.guittot@linaro.org, dietmar.eggemann@arm.com,
        rostedt@goodmis.org, bsegall@google.com, mgorman@suse.de,
        tsbogend@alpha.franken.de, lukas.bulwahn@gmail.com, x86@kernel.org,
        linux-mips@vger.kernel.org, tglx@linutronix.de,
        mostafa.chamanara@basemark.com
References: <20200401100029.1445-1-john.mathew@unikie.com>
 <20200401100029.1445-3-john.mathew@unikie.com>
 <20200401103520.GA20713@hirez.programming.kicks-ass.net>
From:   Daniel Bristot de Oliveira <bristot@redhat.com>
Message-ID: <9614b346-a848-3e01-eea7-6237b759dad6@redhat.com>
Date:   Wed, 1 Apr 2020 13:47:04 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
 Thunderbird/68.6.0
MIME-Version: 1.0
In-Reply-To: <20200401103520.GA20713@hirez.programming.kicks-ass.net>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

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