about the L4Linux scheduler

Adam Lackorzynski adam at os.inf.tu-dresden.de
Mon Oct 1 22:50:30 CEST 2007


On Sun Sep 30, 2007 at 12:29:27 +0900, Lin wrote:
> I have some questions about the scheduler system on DROPS L4Linux.
> I would like your help or some hints.
> The version of my source is ...
>   DROPS SVN revision   : 205
>   L4Linux SVN revision : 61
>   Fiasco version       : 1.2
>   L4Linux version      : 2.6.22
> In L4Linux system (on L4Env), there are two schedulers (in Fiasco
> and in Linux server), you know.

Yes, multiple schedulers may exist on the system.
> Some papers say any Linux user process consists of L4 task and the L4
> shceduler schedules all L4 thread.
> It is ok, but I can't understand the work of the Linux scheduler.
> In fact, a new thread is created in L4 when a process (has one thread)
> is created in Linux, and the active thread is changed when the context
> switch occurs in Linux server (made sure by using Fiasco JDB).
> I want to make this relation clear.
> In other words, what does the Linux scheduler do at these time.

In genernal, the Linux scheduler doesn't do anything special, it just
lives in its Linux world and schedules Linux processes. The Linux
scheduler doesn't know about L4.
> 1. Task creating
> ~~~~~~~~~~~~~~~~
> When "fork()" (or such functions) is called, the function:
>   l4x_setup_next_exec (in "arch/l4/kernel/arch-i386/dispatch.c")
> may be called.
> This function seems push the argument function "ret_from_fork" to the
> stack of the new "task_struct" instance to execute it first when the
> task is scheduled.


> Then, when "fork()" ends (when "do_fork()" returns), the new
> "task_struct" instance is created in Linux system.

do_fork and its helpers are allocating this new process, so when fork
returns the new process is already there.

> At this time, is the L4 thread (task ?) corresponds to that
> "task_struct" is not created yet ?
> (I assume it is created after the "task_struct" is scheduled.)

The corresponding L4 task is created when necessary, i.e. when this
task was actually scheduled and should run some user code.

> 2. Linux server's scheduling
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> In L4Linux task, there are 7 threads and IRQ threads:
>   (1)l4lx.rm       (2)l4lx.sem      (3)l4lx.main     (4)l4lx.tamer
>   (5)l4lx.cpu0     (6)l4lx.timer.i0 (7)l4lx.idler    ...
> "l4lx.main" creates "l4lx.cpu0" (Linux server) and waits this end.

> "l4lx.cpu0" does many initialization in the function "start_kernel()",
> and then it reaches at the function:
>   l4x_idle (in "arch/l4/kernel/dispatch.c").
> In this function, the Linux server creates the thread "l4lx.idler"
> and then enters the scheduling and IPC waiting loop.
> What does this function do ??
> (My expectation about it is written in 4.)

It's the idle thread. It is running when no other activity is in the
L4Linux system. It just sits there are waits for things to happen.

> And more, What is the thread "l4lx.idler" used for ??

It wakes up the idle thread when work is to be done.
> 3. Scheduled new Linux task
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~
> The function "switch_to()" (depends on L4 arch) in Linux kernel only
> saves and restores the registers ESI, ..., ESP, and EIP.
> So, when all new created "task_struct"s are scheduled by the Linux
> server, they runs from "ret_from_fork" as the Linux server thread.
> (Is it right ?)   ^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^

ret_from_fork is the first function a newly created process is

> "ret_from_fork" reaches at the function:
>   l4x_user_dispatcher (in "arch/l4/kernel/dispatch.c").
> It calls "l4x_spawn_cpu_thread()" before its loop.
> I assume it creates the new L4 thread corresponds to the now scheduled
> "task_struct" in Linux server.


> And, the loop in "l4x_user_dispatcher" seems to reply or wait page
> fault, exception and system call IPCs from any L4 thread runs as a
> Linux user task.
> What does this loop do in fact ??

It handles request from a user process, i.e. system calls, page faults,
exceptions etc. It receives the requests, handles them and replies

> When the context switch occurs in Linux server for some reasons,
> the active L4 thread is also switched almost at the same time.
> (I see it by using "ps" on Linux and the thread list of JDB on L4.)
> I want to know the mechanism of this synchronization.
Only one user process is running at a time, i.e. when the user
dispatcher is waiting for an incoming message, a user process is
running. If the user dispatcher is not waiting, no user process is
> 4. Summary
> ~~~~~~~~~~
> My main quiestions is ...
>   (1) What is "l4lx.idler" created for ? (in 2)
>   (2) What does the function "l4x_idle" do ? (in 2)

Hopefully answered.

>   (3) Do all Linux user tasks ("task_struct" instance) only execute
>       "l4x_user_dispatcher" (from "ret_from_fork") as the Linux
>       server ? (in 1 and 3)

Yes, all user processes run in the user-dispatcher loop.

>   (4) What does the function "l4x_user_dispatcher" do ?
>       How to switch contexts in Linux and in L4 almost at the same
>       time ? (in 3)

Context switching in L4 is done by the kernel (Fiasco). Also note that
the L4Linux server itself runs in an L4 thread and thus Fiasco is doing
context switches when switching from a user process (L4 thread) to the
L4Linux server (another L4 thread). This basically happens when the IPCs
are sent. The context switch in the other direction happens when the
L4Linux server replies the user process.
The context switches in the Linux server happen inside the schedule()
call, the L4 side is not affected by this, as it basically only means
that the Linux server switches to another stack.

> My expectation about Linux scheduling system is the following:
>   - When there is no need to reschedule Linux user processes, Linux
>     server is in IPC sleep and waiting the wakeup IPC in "l4x_idle".


>   - If Linux server gets IPC for some reasons, it wakes up and check
>     the IPC sender. Then, if the sender is a thread corresponds to
>     certain Linux task, Linux server wakes up this Linux task and
>     reschedules by calling "schedule()".

I don't quite understand what you want to say. If the Linux server gets
an IPC it has to handle this request (Pagefault, syscall...). If the
Linux system wants to reschedule, schedule() is called so that another
context may be selected.

>   - The waked up task will be active as Linux server. This context
>     may execute only "l4x_user_dispatcher" which replies and wait IPCs
>     and handles page faults and exceptions based on information of the
>     received IPC.

Basically yes, but the kernel-side context of the user process will be

>   - When the L4 thread of the Linux task exits, that Linux task in
>     Linux (task_struct instance) also is freed. If there is no
>     schedulable task in Linux at that time, the original context
>     (executes "l4x_idle") is re-scheduled.

There's always one process active in Linux (init). Idle is actually
process 0 so this would be 'running' then.

Adam                 adam at os.inf.tu-dresden.de
  Lackorzynski         http://os.inf.tu-dresden.de/~adam/

More information about the l4-hackers mailing list