1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
Scheduler monitors
==================
- Name: sched
- Type: container for multiple monitors
- Author: Gabriele Monaco <gmonaco@redhat.com>, Daniel Bristot de Oliveira <bristot@kernel.org>
Description
-----------
Monitors describing complex systems, such as the scheduler, can easily grow to
the point where they are just hard to understand because of the many possible
state transitions.
Often it is possible to break such descriptions into smaller monitors,
sharing some or all events. Enabling those smaller monitors concurrently is,
in fact, testing the system as if we had one single larger monitor.
Splitting models into multiple specification is not only easier to
understand, but gives some more clues when we see errors.
The sched monitor is a set of specifications to describe the scheduler behaviour.
It includes several per-cpu and per-task monitors that work independently to verify
different specifications the scheduler should follow.
To make this system as straightforward as possible, sched specifications are *nested*
monitors, whereas sched itself is a *container*.
From the interface perspective, sched includes other monitors as sub-directories,
enabling/disabling or setting reactors to sched, propagates the change to all monitors,
however single monitors can be used independently as well.
It is important that future modules are built after their container (sched, in
this case), otherwise the linker would not respect the order and the nesting
wouldn't work as expected.
To do so, simply add them after sched in the Makefile.
Specifications
--------------
The specifications included in sched are currently a work in progress, adapting the ones
defined in by Daniel Bristot in [1].
Currently we included the following:
Monitor tss
~~~~~~~~~~~
The task switch while scheduling (tss) monitor ensures a task switch happens
only in scheduling context, that is inside a call to `__schedule`::
|
|
v
+-----------------+
| thread | <+
+-----------------+ |
| |
| schedule_entry | schedule_exit
v |
sched_switch |
+--------------- |
| sched |
+--------------> -+
Monitor sco
~~~~~~~~~~~
The scheduling context operations (sco) monitor ensures changes in a task state
happen only in thread context::
|
|
v
sched_set_state +------------------+
+------------------ | |
| | thread_context |
+-----------------> | | <+
+------------------+ |
| |
| schedule_entry | schedule_exit
v |
|
scheduling_context -+
Monitor snroc
~~~~~~~~~~~~~
The set non runnable on its own context (snroc) monitor ensures changes in a
task state happens only in the respective task's context. This is a per-task
monitor::
|
|
v
+------------------+
| other_context | <+
+------------------+ |
| |
| sched_switch_in | sched_switch_out
v |
sched_set_state |
+------------------ |
| own_context |
+-----------------> -+
Monitor scpd
~~~~~~~~~~~~
The schedule called with preemption disabled (scpd) monitor ensures schedule is
called with preemption disabled::
|
|
v
+------------------+
| cant_sched | <+
+------------------+ |
| |
| preempt_disable | preempt_enable
v |
schedule_entry |
schedule_exit |
+----------------- can_sched |
| |
+----------------> -+
Monitor snep
~~~~~~~~~~~~
The schedule does not enable preempt (snep) monitor ensures a schedule call
does not enable preemption::
|
|
v
preempt_disable +------------------------+
preempt_enable | |
+------------------ | non_scheduling_context |
| | |
+-----------------> | | <+
+------------------------+ |
| |
| schedule_entry | schedule_exit
v |
|
scheduling_contex -+
Monitor sncid
~~~~~~~~~~~~~
The schedule not called with interrupt disabled (sncid) monitor ensures
schedule is not called with interrupt disabled::
|
|
v
schedule_entry +--------------+
schedule_exit | |
+----------------- | can_sched |
| | |
+----------------> | | <+
+--------------+ |
| |
| irq_disable | irq_enable
v |
|
cant_sched -+
References
----------
[1] - https://bristot.me/linux-task-model
|
