Rev 53 | Rev 56 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
52 | jermar | 1 | <?xml version="1.0" encoding="UTF-8"?> |
55 | jermar | 2 | <chapter id="time"> |
3 | <?dbhtml filename="time.html"?> |
||
52 | jermar | 4 | |
55 | jermar | 5 | <title>Time management</title> |
52 | jermar | 6 | |
55 | jermar | 7 | <para>Time is one of the dimensions in which kernel, as well as the whole |
8 | system, operates. It is of special importance to many kernel subsytems. |
||
9 | Knowledge of time makes it possible for the scheduler to preemptively plan |
||
10 | threads for execution. Different parts of the kernel can request execution |
||
11 | of their callback function with some specified delay. A good example of such |
||
12 | kernel code is the synchronization subsystem which uses this functionality |
||
13 | to implement timeouting versions of synchronization primitives.</para> |
||
14 | |||
15 | <section> |
||
53 | jermar | 16 | <title>System clock</title> |
17 | |||
55 | jermar | 18 | <para>Every hardware architecture supported by HelenOS must support some |
19 | kind of a device that can be programmed to yield periodic time signals |
||
20 | (i.e. clock interrupts). Some architectures have external clock that is |
||
21 | merely programmed by the kernel to interrupt the processor multiple times |
||
22 | in a second. This is the case of ia32 and amd64 architectures<footnote> |
||
23 | <para>When running in uniprocessor mode.</para> |
||
24 | </footnote>, which use i8254 or a compatible chip to achieve the |
||
25 | goal.</para> |
||
26 | |||
27 | <para>Other architectures' processors typically contain two registers. The |
||
28 | first register is usually called a compare or a match register and can be |
||
29 | set to an arbitrary value by the operating system. The contents of the |
||
30 | compare register then stays unaltered until it is written by the kernel |
||
31 | again. The second register, often called a counter register, can be also |
||
32 | written by the kernel, but the processor automatically increments it after |
||
33 | every executed instruction or in some fixed relation to processor speed. |
||
34 | The point is that a clock interrupt is generated whenever the values of |
||
35 | the counter and the compare registers match. Sometimes, the scheme of two |
||
36 | registers is modified so that only one register is needed. Such a |
||
37 | register, called a decrementer, then counts towards zero and an interrupt |
||
38 | is generated when zero is reached.</para> |
||
39 | |||
40 | <para>In any case, the initial value of the decrementer or the initial |
||
41 | difference between the counter and the compare registers, respectively, |
||
42 | must be set accordingly to a known relation between the real time and the |
||
43 | speed of the decrementer or the counter register, respectively.</para> |
||
44 | |||
45 | <para>The rest of this section will, for the sake of clarity, focus on the |
||
46 | two-register scheme. The decrementer scheme is very similar.</para> |
||
47 | |||
48 | <para>The kernel must reinitialize the counter registers after each clock |
||
49 | interrupt in order to schedule next interrupt. However this step is tricky |
||
50 | and must be done with caution. Imagine that the clock interrupt is masked |
||
51 | either because the kernel is servicing another interrupt or because the |
||
52 | processor locally disabled interrupts for a while. If the clock interrupt |
||
53 | occurs during this period, it will be pending until interrupts are enabled |
||
54 | again. In theory, that could happen arbitrary counter register ticks |
||
55 | later. Which is worse, the ideal time period between two non-delayed clock |
||
56 | interrupts can also elapse arbitrary number of times before the delayed |
||
57 | interrupt gets serviced. The architecture-specific part of the clock |
||
58 | interrupt driver must avoid time drifts caused by this by taking proactive |
||
59 | counter-measures.</para> |
||
60 | |||
61 | <para>Let us assume that the kernel wants each clock interrupt be |
||
62 | generated every <constant>TICKCONST</constant> ticks. This value |
||
63 | represents the ideal number of ticks between two non-delayed clock |
||
64 | interrupts and has some known relation to real time. On each clock |
||
65 | interrupt, the kernel computes and writes down the expected value of the |
||
66 | counter register as it hopes to read it on the next clock interrupt. When |
||
67 | that interrupt comes, the kernel reads the counter register again and |
||
68 | compares it with the written down value. If the difference is smaller than |
||
69 | or equal to <constant>TICKCONST</constant>, then the time drift is none or |
||
70 | small and the next interrupt is scheduled earlier with a penalty of so |
||
71 | many ticks as is the value of the difference. However, if the difference |
||
72 | is bigger, then at least one clock signal was missed. In that case, the |
||
73 | missed clock signal is remembered in the special counter. If there are |
||
74 | more missed signals, each of them is recorded there. The next interrupt is |
||
75 | scheduled with respect to the difference similarily to the former case. |
||
76 | This time, the penalty is taken modulo <constant>TICKCONST</constant>. The |
||
77 | effect of missed clock signals is remedied in the generic clock interrupt |
||
78 | handler.</para> |
||
79 | </section> |
||
80 | |||
81 | <section> |
||
82 | <title>Timeouts</title> |
||
83 | |||
84 | <para>Kernel subsystems can register a callback function to be executed |
||
85 | with a specified delay. Such a registration is represented by a kernel |
||
86 | structure called <classname>timeout</classname>. Timeouts are registered |
||
87 | via <code>timeout_register</code> function. This function takes a pointer |
||
88 | to a timeout structure, a callback function, a parameter of the callback |
||
89 | function and a delay in microseconds as parameters. After the structure is |
||
90 | initialized with all these values, it is sorted into the processor's list |
||
91 | of active timeouts.Timeouts are sorted in this list according to the |
||
92 | number of clock interrupts remaining to their expiration and relative to |
||
93 | each other. </para> |
||
94 | |||
95 | <para>Timeouts can be unregistered via <code>timeout_unregister</code>. |
||
96 | This function can, as opposed to <code>timeout_register</code>, fail when |
||
97 | it is too late to remove the timeout from the list of active |
||
98 | timeouts.</para> |
||
99 | |||
100 | <para>Timeouts are nearing their expiration in the list of active timeouts |
||
101 | which exists on every processor in the system. The expiration counters are |
||
102 | decremented on each clock interrupt by the generic clock interrupt |
||
103 | handler. Due to the relative ordering of timeouts in the list, it is |
||
104 | sufficient to decrement expiration counter only of the first timeout in |
||
105 | the list. Timeouts with expiration counter equal to zero are removed from |
||
106 | the list and their callback function is called with respective |
||
107 | parameter.</para> |
||
108 | </section> |
||
109 | |||
110 | <section> |
||
111 | <title>Generic clock interrupt handler</title> |
||
112 | |||
113 | <para>On each clock interrupt, the architecture specific part of the clock |
||
114 | interrupt handler makes a call to the generic clock interrupt handler |
||
115 | implemented by the <code>clock</code> function. The generic handler takes |
||
116 | care of several mission critical goals:</para> |
||
117 | |||
118 | <itemizedlist> |
||
119 | <listitem> |
||
120 | <para>expiration of timeouts,</para> |
||
121 | </listitem> |
||
122 | |||
123 | <listitem> |
||
124 | <para>updating time of the day counters for userspace and</para> |
||
125 | </listitem> |
||
126 | |||
127 | <listitem> |
||
128 | <para>preemption of threads.</para> |
||
129 | </listitem> |
||
130 | </itemizedlist> |
||
131 | |||
132 | <para>The first two goals are performed exactly one more times than is the |
||
133 | number of missed clock signals (i.e. at least once and possibly more |
||
134 | times, depending on the missed clock signals counter). The remaining |
||
135 | timeslice of the running thread is decremented also with respect to this |
||
136 | counter. By considering its value, the kernel performs actions that would |
||
137 | otherwise be lost due to an occasional excessive time drift described in |
||
138 | previous paragraphs.</para> |
||
139 | </section> |
||
52 | jermar | 140 | </chapter> |