Subversion Repositories HelenOS-doc

Rev

Rev 57 | Rev 59 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 57 Rev 58
1 
<?xml version="1.0" encoding="UTF-8"?>
 1 
<?xml version="1.0" encoding="UTF-8"?>
2 
<chapter id="scheduling">
 2 
<chapter id="scheduling">
3 
  <?dbhtml filename="scheduling.html"?>
 3 
  <?dbhtml filename="scheduling.html"?>
4 
 
 4 
 
5 
  <title>Scheduling</title>
 5 
  <title>Scheduling</title>
6 
 
 6 
 
7 
  <para>One of the key aims of the operating system is to create and support
 7 
  <para>One of the key aims of the operating system is to create and support
8 
  the impression that several activities are executing contemporarily. This is
 8 
  the impression that several activities are executing contemporarily. This is
9 
  true for both uniprocessor as well as multiprocessor systems. In the case of
 9 
  true for both uniprocessor as well as multiprocessor systems. In the case of
10 
  multiprocessor systems, the activities are trully happening in parallel. The
 10 
  multiprocessor systems, the activities are trully happening in parallel. The
11 
  scheduler helps to materialize this impression by planning threads on as
 11 
  scheduler helps to materialize this impression by planning threads on as
12 
  many processors as possible and, where this means reaches its limits, by
 12 
  many processors as possible and, where this means reaches its limits, by
13 
  quickly switching among threads executing on a single processor.</para>
 13 
  quickly switching among threads executing on a single processor.</para>
14 
 
 14 
 
15 
  <section>
 15 
  <section>
16 
    <title>Contexts</title>
 16 
    <title>Contexts</title>
17 
 
 17 
 
18 
    <para>The term context refers to the set of processor resources that
 18 
    <para>The term context refers to the set of processor resources that
19 
    define the current state of the computation or the environment and the
 19 
    define the current state of the computation or the environment and the
20 
    kernel understands it in several more or less narrow sences:</para>
 20 
    kernel understands it in several more or less narrow sences:</para>
21 
 
 21 
 
22 
    <itemizedlist>
 22 
    <itemizedlist>
23 
      <listitem>
 23 
      <listitem>
24 
        <para>synchronous register context,</para>
 24 
        <para>synchronous register context,</para>
25 
      </listitem>
 25 
      </listitem>
26 
 
 26 
 
27 
      <listitem>
 27 
      <listitem>
28 
        <para>asynchronous register context,</para>
 28 
        <para>asynchronous register context,</para>
29 
      </listitem>
 29 
      </listitem>
30 
 
 30 
 
31 
      <listitem>
 31 
      <listitem>
32 
        <para>FPU context and</para>
 32 
        <para>FPU context and</para>
33 
      </listitem>
 33 
      </listitem>
34 
 
 34 
 
35 
      <listitem>
 35 
      <listitem>
36 
        <para>memory management context.</para>
 36 
        <para>memory management context.</para>
37 
      </listitem>
 37 
      </listitem>
38 
    </itemizedlist>
 38 
    </itemizedlist>
39 
 
 39 
 
40 
    <para>The most narrow sence refers to the the synchronous register
 40 
    <para>The most narrow sence refers to the the synchronous register
41 
    context. It includes all the preserved registers as defined by the
 41 
    context. It includes all the preserved registers as defined by the
42 
    architecture. To highlight some, the program counter and stack pointer
 42 
    architecture. To highlight some, the program counter and stack pointer
43 
    take part in the synchronous register context. These are the registers
 43 
    take part in the synchronous register context. These are the registers
44 
    that must be preserved across a procedure call and during synchronous
 44 
    that must be preserved across a procedure call and during synchronous
45 
    context switches. </para>
 45 
    context switches.</para>
46 
 
 46 
 
47 
    <para>The next type of the context understood by the kernel is the
 47 
    <para>The next type of the context understood by the kernel is the
48 
    asynchronous register context. On an interrupt, the interrupted execution
 48 
    asynchronous register context. On an interrupt, the interrupted execution
49 
    flow's state must be guaranteed to be eventually completely restored.
 49 
    flow's state must be guaranteed to be eventually completely restored.
50 
    Therefore the interrupt context includes, among other things, the scratch
 50 
    Therefore the interrupt context includes, among other things, the scratch
51 
    registers as defined by the architecture. As a special optimization and if
 51 
    registers as defined by the architecture. As a special optimization and if
52 
    certain conditions are met, it need not include the architecture's
 52 
    certain conditions are met, it need not include the architecture's
53 
    preserved registers. The condition mentioned in the previous sentence is
 53 
    preserved registers. The condition mentioned in the previous sentence is
54 
    that the low-level assembly language interrupt routines don't modify the
 54 
    that the low-level assembly language interrupt routines don't modify the
55 
    preserved registers. The handlers usually call a higher-level C routine.
 55 
    preserved registers. The handlers usually call a higher-level C routine.
56 
    The preserved registers are then saved on the stack by the compiler
 56 
    The preserved registers are then saved on the stack by the compiler
57 
    generated code of the higher-level function. In HelenOS, several
 57 
    generated code of the higher-level function. In HelenOS, several
58 
    architectures can be compiled with this optimization.</para>
 58 
    architectures can be compiled with this optimization.</para>
59 
 
 59 
 
60 
    <para>Although the kernel does not do any floating point
 60 
    <para>Although the kernel does not do any floating point
61 
    arithmetics<footnote>
 61 
    arithmetics<footnote>
62 
        <para>Some architectures (e.g. ia64) inevitably use a fixed set of
 62 
        <para>Some architectures (e.g. ia64) inevitably use a fixed set of
63 
        floating point registers to carry out its normal operations.</para>
 63 
        floating point registers to carry out its normal operations.</para>
64 
      </footnote>, it must protect FPU context of userspace threads against
 64 
      </footnote>, it must protect FPU context of userspace threads against
65 
    destruction by other threads. Moreover, only a fraction of userspace
 65 
    destruction by other threads. Moreover, only a fraction of userspace
66 
    programs use the floating point unit. HelenOS contains a generic framework
 66 
    programs use the floating point unit. HelenOS contains a generic framework
67 
    for switching FPU context only when the switch is forced.</para>
 67 
    for switching FPU context only when the switch is forced.</para>
68 
 
 68 
 
69 
    <para>The last member of the context family is the memory management
 69 
    <para>The last member of the context family is the memory management
70 
    context. It includes memory management registers that identify address
 70 
    context. It includes memory management registers that identify address
71 
    spaces on hardware level (i.e. ASIDs and page tables pointers).</para>
 71 
    spaces on hardware level (i.e. ASIDs and page tables pointers).</para>
72 
 
 72 
 
73 
    <section>
 73 
    <section>
74 
      <title>Synchronous context switches</title>
 74 
      <title>Synchronous context switches</title>
75 
 
 75 
 
76 
      <para>The scheduler, but also other pieces of the kernel, make heavy use
 76 
      <para>The scheduler, but also other pieces of the kernel, make heavy use
77 
      of synchronous context switches, because it is a natural vehicle not
 77 
      of synchronous context switches, because it is a natural vehicle not
78 
      only for changes in control flow, but also for switching between two
 78 
      only for changes in control flow, but also for switching between two
79 
      kernel stacks. Two functions figure in a synchronous context switch
 79 
      kernel stacks. Two functions figure in a synchronous context switch
80 
      implementation: <code>context_save</code> and
 80 
      implementation: <code>context_save</code> and
81 
      <code>context_restore</code>. Note that these two functions break the
 81 
      <code>context_restore</code>. Note that these two functions break the
82 
      natural perception of the linear C code execution flow starting at
 82 
      natural perception of the linear C code execution flow starting at
83 
      function's entry point and ending on one of the function's exit
 83 
      function's entry point and ending on one of the function's exit
84 
      points.</para>
 84 
      points.</para>
85 
 
 85 
 
86 
      <para>When the <code>context_save</code> function is called, the
 86 
      <para>When the <code>context_save</code> function is called, the
87 
      synchronous context is saved in a memory structure passed to it. After
 87 
      synchronous context is saved in a memory structure passed to it. After
88 
      executing <code>context_save</code>, the caller is returned 1 as a
 88 
      executing <code>context_save</code>, the caller is returned 1 as a
89 
      return value. The execution of instructions continues as normally until
 89 
      return value. The execution of instructions continues as normally until
90 
      <code>context_restore</code> is called. For the caller, it seems like
 90 
      <code>context_restore</code> is called. For the caller, it seems like
91 
      the call never returns<footnote>
 91 
      the call never returns<footnote>
92 
          <para>Which might be a source of problems with variable liveliness
 92 
          <para>Which might be a source of problems with variable liveliness
93 
          after <code>context_restore</code>.</para>
 93 
          after <code>context_restore</code>.</para>
94 
        </footnote>. Nevertheless, a synchronous register context, which is
 94 
        </footnote>. Nevertheless, a synchronous register context, which is
95 
      saved in a memory structure passed to <code>context_restore,</code> is
 95 
      saved in a memory structure passed to <code>context_restore,</code> is
96 
      restored, thus transfering the control flow to the place of occurrence
 96 
      restored, thus transfering the control flow to the place of occurrence
97 
      of the corresponding call to <code>context_save</code>. From the
 97 
      of the corresponding call to <code>context_save</code>. From the
98 
      perspective of the caller of the corresponding
 98 
      perspective of the caller of the corresponding
99 
      <code>context_save</code>, it looks as though a return from
 99 
      <code>context_save</code>, it looks as though a return from
100 
      <code>context_save</code>. However, this time a return value of 0 is
 100 
      <code>context_save</code>. However, this time a return value of 0 is
101 
      returned.</para>
 101 
      returned.</para>
102 
    </section>
 102 
    </section>
103 
  </section>
 103 
  </section>
104 
 
 104 
 
105 
  <section>
 105 
  <section>
106 
    <title>Scheduler</title>
 106 
    <title>Threads</title>
107 
 
 107 
 
- 
 
 108 
    <para>A thread is the basic executable entity with some code and stack.
- 
 
 109 
    While the code, implemented by a C language function, can be shared by
- 
 
 110 
    several threads, the stack is always private to each instance of the
- 
 
 111 
    thread. Each thread belongs to exactly one task through which it shares
- 
 
 112 
    address space with its sibling threads. Threads that execute purely in the
- 
 
 113 
    kernel don't have any userspace memory allocated. However, when a thread
- 
 
 114 
    has ambitions to run in userspace, it must be allocated a userspace stack.
- 
 
 115 
    The distinction between the purely kernel threads and threads running also
- 
 
 116 
    in userspace is made by refering to the former group as to kernel threads
- 
 
 117 
    and to the latter group as to userspace threads. Both kernel and userspace
- 
 
 118 
    threads are visible to the scheduler and can become a subject of kernel
- 
 
 119 
    preemption and thread migration during times when preemption is
- 
 
 120 
    possible.</para>
- 
 
 121 
 
- 
 
 122 
    <para>HelenOS userspace layer knows even smaller units of execution. Each
- 
 
 123 
    userspace thread can make use of an arbitrary number of pseudo threads.
- 
 
 124 
    These pseudo threads have their own synchronous register context,
- 
 
 125 
    userspace code and stack. They live their own life within the userspace
108 
    <para>How scheduler designed and how it works.</para>
 126 
    thread and the scheduler does not have any idea about them because they
- 
 
 127 
    are completely implemented by the userspace library. This implies several
- 
 
 128 
    things:</para>
- 
 
 129 
 
- 
 
 130 
    <itemizedlist>
- 
 
 131 
      <listitem>
- 
 
 132 
        <para>pseudothreads schedule themselves cooperatively within the time
- 
 
 133 
        slice given to their userspace thread,</para>
- 
 
 134 
      </listitem>
- 
 
 135 
 
- 
 
 136 
      <listitem>
- 
 
 137 
        <para>pseudothreads share FPU context of their containing thread
- 
 
 138 
        and</para>
- 
 
 139 
      </listitem>
- 
 
 140 
 
- 
 
 141 
      <listitem>
- 
 
 142 
        <para>all pseudothreads of one userspace thread block when one of them
- 
 
 143 
        goes to sleep.</para>
- 
 
 144 
      </listitem>
- 
 
 145 
    </itemizedlist>
- 
 
 146 
 
- 
 
 147 
    <para></para>
109 
  </section>
 148 
  </section>
110 
</chapter>
 149 
</chapter>