From: Daniel Bristot de Oliveira <bristot@redhat.com>
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
Subject: Re: [RFC PATCH 2/3] docs: scheduler: Add scheduler overview documentation
Date: Wed, 1 Apr 2020 13:47:04 +0200 [thread overview]
Message-ID: <9614b346-a848-3e01-eea7-6237b759dad6@redhat.com> (raw)
In-Reply-To: <20200401103520.GA20713@hirez.programming.kicks-ass.net>
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
next prev parent reply other threads:[~2020-04-01 11:47 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-04-01 10:00 [RFC PATCH 0/3] Add scheduler overview documentation John Mathew
2020-04-01 10:00 ` [RFC PATCH 1/3] docs: scheduler: Restructure scheduler documentation John Mathew
2020-04-01 10:00 ` [RFC PATCH 2/3] docs: scheduler: Add scheduler overview documentation John Mathew
2020-04-01 10:35 ` Peter Zijlstra
2020-04-01 11:47 ` Daniel Bristot de Oliveira [this message]
2020-04-01 12:26 ` Peter Zijlstra
2020-04-01 13:45 ` Valentin Schneider
2020-04-07 19:40 ` Jonathan Corbet
2020-04-08 5:35 ` Daniel Bristot de Oliveira
2020-04-01 11:54 ` Matthew Wilcox
2020-04-01 14:36 ` Jonathan Corbet
2020-04-01 12:20 ` Juri Lelli
2020-04-01 15:03 ` Valentin Schneider
2020-04-01 10:00 ` [RFC PATCH 3/3] docs: scheduler: Add introduction to scheduler context-switch John Mathew
2020-04-01 11:06 ` Peter Zijlstra
2020-04-06 5:07 ` [RFC PATCH 0/3] Add scheduler overview documentation John Mathew
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=9614b346-a848-3e01-eea7-6237b759dad6@redhat.com \
--to=bristot@redhat.com \
--cc=bsegall@google.com \
--cc=corbet@lwn.net \
--cc=dietmar.eggemann@arm.com \
--cc=john.mathew@unikie.com \
--cc=juri.lelli@redhat.com \
--cc=linux-doc@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mips@vger.kernel.org \
--cc=lukas.bulwahn@gmail.com \
--cc=mgorman@suse.de \
--cc=mingo@redhat.com \
--cc=mostafa.chamanara@basemark.com \
--cc=peterz@infradead.org \
--cc=rostedt@goodmis.org \
--cc=tglx@linutronix.de \
--cc=tsbogend@alpha.franken.de \
--cc=vincent.guittot@linaro.org \
--cc=x86@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).