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
172
|
Process Management Optimizations
================================
Problems
--------
Early versions of the SMP support for the runtime system completely
relied on locking in order to protect data accesses from multiple
threads. In some cases this isn't that problematic, but in some cases
it really is. It complicates the code, ensuring all locks needed are
actually held, and ensuring that all locks are acquired in such an
order that no deadlock occur. Acquiring locks in the right order often
also involve releasing locks held, forcing threads to reread data
already read. A good recipe for creation of bugs. Trying to use more
fine-grained locking in order to increase possible parallelism in the
system makes the complexity situation even worse. Having to acquire a
bunch of locks when doing operations also often cause heavy lock
contention which cause poor scalability.
Management of processes internally in the runtime system suffered from
these problems. When changing state on a process, for example from
`waiting` to `runnable`, a lock on the process needed to be
locked. When inserting a process into a run queue also a lock
protecting the run queue had to be locked. When migrating a process
from one run queue to another run queue, locks on both run queues and
on the process had to be locked.
This last example is a quite common case in during normal
operation. For example, when a scheduler thread runs out of work it
tries to steal work from another scheduler threads run queue. When
searching for a victim to steal from there was a lot of juggling of
run queue locks involved, and during the actual theft finalized by
having to lock both run queues and the process. When one scheduler
runs out of work, often others also do, causing lots of lock
contention.
Solution
--------
### Process ###
In order to avoid these situations we wanted to be able to do most of
the fundamental operations on a process without having to acquire a
lock on the process. Some examples of such fundamental operations are,
moving a process between run queues, detecting if we need to insert it
into a run queue or not, detecting if it is alive or not.
All of this information in the process structure that was needed by
these operations was protected by the process `status` lock, but the
information was spread across a number of fields. The fields used was
typically state fields that could contain a small number of different
states. By reordering this information a bit we could *easily* fit
this information into a 32-bit wide field of bit flags (only 12-flags
were needed). By moving this information we could remove five 32-bit
wide fields and one pointer field from the process structure! The move
also enabled us to easily read and change the state using atomic
memory operations.
### Run Queue ###
As with processes we wanted to be able to do the most fundamental
operations without having to acquire a lock on it. The most important
being able to determine if we should enqueue a process in a specific
run queue or not. This involves being able to read actual load, and
load balancing information.
The load balancing functionality is triggered at repeated fixed
intervals. The load balancing more or less strives to even out run
queue lengths over the system. When balancing is triggered,
information about every run queue is gathered, migrations paths and
run queue length limits are set up. Migration paths and limits are
fixed until the next balancing has been done. The most important
information about each run queue is the maximum run queue length since
last balancing. All of this information were previously stored in the
run queues themselves.
When a process has become runnable, for example due to reception of a
message, we need to determine which run queue to enqueue it
in. Previously this at least involved locking the run queue that the
process currently was assigned to while holding the status lock on the
process. Depending on load we sometimes also had to acquire a lock on
another run queue in order to be able to determine if it should be
migrated to that run queue or not.
In order to be able to decide which run queue to use without having to
lock any run queues, we moved all fixed balancing information out of
the run queues into a global memory block. That is, migration paths
and run queue limits. Information that need to be frequently updated,
like for example maximum run queue length, were kept in the run queue,
but instead of operating on this information under locks we now use
atomic memory operations when accessing this information. This made it
possible to first determine which run queue to use, without locking
any run queues, and when decided, lock the chosen run queue and insert
the process.
#### Fixed Balancing Information ####
When determining which run queue to choose we need to read the fixed
balancing information that we moved out of the run queues. This
information is global, read only between load balancing operations,
but will be changed during a load balancing. We do not want to
introduce a global lock that needs to be acquired when accessing this
information. A reader optimized rwlock could avoid some of the
overhead since the data is most frequently read, but it would
unavoidably cause disruption during load balancing, since this
information is very frequently read. The likelihood of a large
disruption due to this also increase as number of schedulers grows.
Instead of using a global lock protecting modifications of this
information, we write a completely new version of it at each load
balancing. The new version is written in another memory block than the
previous one, and published by issuing a write memory barrier and then
storing a pointer to the new memory block in a global variable using
an atomic write operation.
When schedulers need to read this information, they read the pointer
to currently used information using an atomic read operation, and then
issue a data dependency read barrier, which on most architectures is a
no-op. That is, it is very little overhead getting access to this
information.
Instead of allocating and deallocating memory blocks for the different
versions of the balancing information we keep old memory blocks and
reuse them when it is safe to do so. In order to be able to determine
when it is safe to reuse a block we use the thread progress
functionality, ensuring that no threads have any references to the
memory block when we reuse it.
#### Be Less Aggressive ####
We implemented a test version using lock free run queues. This
implementation did however not perform as good as the version using
one lock per run queue. The reason for this was not investigated
enough to say why this was. Since the locked version performed better
we kept it, at least for now. The lock free version, however, forced
us to use other solutions, some of them we kept.
Previously when a process that was in a run queue got suspended, we
removed it from the queue straight away. This involved locking the
process, locking the run queue, and then unlinking it from the double
linked list implementing the queue. Removing a process from a lock
free queue gets really complicated. Instead, of removing it from the
queue, we just leave it in the queue and mark it as suspended. When
later selected for execution we check if the process is suspended, if
so just dropped it. During its time in the queue, it might also get
resumed again, if so execute it when it get selected for execution.
By keeping this part when reverting back to a locked implementation,
we could remove a pointer field in each process structure, and avoid
unnecessary operations on the process and the queue which might cause
contention.
### Combined Modifications ###
By combining the modifications of the process state management and the
run queue management, we can do large parts of the work involved when
managing processes with regards to scheduling and migration without
having any locks locked at all. In these situations we previously had
to have multiple locks locked. This of course caused a lot of rewrites
across large parts of the runtime system, but the rewrite both
simplified code and eliminated locking at a number of places. The
major benefit is, of course, reduced contention.
### A Benchmark Result ###
When running the chameneosredux benchmark, schedulers frequently run
out of work trying to steal work from each other. That is, either
succeeding in migrating, or trying to migrate processes which is a
scenario which we wanted to optimize. By the introduction of these
improvements, we got a speedup of 25-35% when running this benchmark
on a relatively new machine with an Intel i7 quad core processor with
hyper-threading using 8 schedulers.
|
