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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
|
/*
* Implementation Overview
*
* This class and its nested classes provide the main
* functionality and control for a set of worker threads:
* Submissions from non-FJ threads enter into submission queues.
* Workers take these tasks and typically split them into subtasks
* that may be stolen by other workers. Preference rules give
* first priority to processing tasks from their own queues (LIFO
* or FIFO, depending on mode), then to randomized FIFO steals of
* tasks in other queues. This framework began as vehicle for
* supporting tree-structured parallelism using work-stealing.
* Over time, its scalability advantages led to extensions and
* changes to better support more diverse usage contexts. Because
* most internal methods and nested classes are interrelated,
* their main rationale and descriptions are presented here;
* individual methods and nested classes contain only brief
* comments about details.
* 该类及其嵌套类为一组工作线程提供主要功能和控制：来自non-FJ线程的提交进入提交队列。工人们承担这些任务，
* 通常将他们分解成可能被其他工人窃取的子任务。优先规则优先处理来自其自己的队列（LIFO或FIFO，取决于模式）的任务，
* 然后是其他队列中任务的随机FIFO窃取。这个框架开始作为支持使用工作窃取的树形结构并行的工具。
* 随着时间的推移，其可扩展性的优势导致扩展和变化，以更好地支持更多不同的使用情况。因为大多数内部方法和嵌套类是相互关联的，
* 所以它们的主要基本原理和描述在这里给出;个别方法和嵌套类只包含关于细节的简短评论。
*
* WorkQueues 工作队列
* ==========
*
* Most operations occur within work-stealing queues (in nested
* class WorkQueue). These are special forms of Deques that
* support only three of the four possible end-operations -- push,
* pop, and poll (aka steal), under the further constraints that
* push and pop are called only from the owning thread (or, as
* extended here, under a lock), while poll may be called from
* other threads. (If you are unfamiliar with them, you probably
* want to read Herlihy and Shavit's book "The Art of
* Multiprocessor programming", chapter 16 describing these in
* more detail before proceeding.) The main work-stealing queue
* design is roughly similar to those in the papers "Dynamic
* Circular Work-Stealing Deque" by Chase and Lev, SPAA 2005
* (http://research.sun.com/scalable/pubs/index.html) and
* "Idempotent work stealing" by Michael, Saraswat, and Vechev,
* PPoPP 2009 (http://portal.acm.org/citation.cfm?id=1504186).
* The main differences ultimately stem from GC requirements that
* we null out taken slots as soon as we can, to maintain as small
* a footprint as possible even in programs generating huge
* numbers of tasks. To accomplish this, we shift the CAS
* arbitrating pop vs poll (steal) from being on the indices
* ("base" and "top") to the slots themselves.
*
* 大多数操作发生在工作窃取队列中（在嵌套的类WorkQueue中）。
* 这些是Deques的特殊形式，它只支持四种可能的最终操作中的三种 - push，pop和poll（又名steal），
* 在进一步的约束条件下push和pop只能从拥有的线程中调用（或者像扩展这里，在一个锁）下，而轮询可能会从其他线程调用。
* （如果你不熟悉它们，你可能要阅读Herlihy和Shavit的书"多处理器编程的艺术"，第16章在进行更详细的描述之前）。
* 主要的工作队列设计大致类似于Chase和Lev撰写的"Dynamic Circular Work-Stealing Deque"，SPAA 2005（http://research.sun.com/scalable/pubs/index.html）
* 和Michael，Saraswat和Vechev的"幂等工作窃取"PPoPP 2009（http://portal.acm.org/citation.cfm?id=1504186）。
* 主要的差异最终来自GC的要求，我们尽可能地将其空缺，尽可能保持尽可能小的占用空间，即使在产生大量任务的程序中也是如此。
* 为了实现这一点，我们将CAS仲裁pop与poll（steal）从指标（"base"和"top"）转移到角色本身。
*
* Adding tasks then takes the form of a classic array push(task): 然后添加任务，然后采取经典数组push(task)的形式:
* q.array[q.top] = task; ++q.top;
*
* (The actual code needs to null-check and size-check the array,
* properly fence the accesses, and possibly signal waiting
* workers to start scanning -- see below.) Both a successful pop
* and poll mainly entail a CAS of a slot from non-null to null.
* （实际的代码需要对数组进行空值检查和大小检查，对访问进行适当的隔离，并可能发出信号等待工作人员开始扫描 - 见下文）。
* 成功的pop和poll主要是由 non-null 到null的槽的CAS.
*
* The pop operation (always performed by owner) is:
* if ((base != top) and
* (the task at top slot is not null) and
* (CAS slot to null))
* decrement top and return task;
*
* And the poll operation (usually by a stealer) is
* if ((base != top) and
* (the task at base slot is not null) and
* (base has not changed) and
* (CAS slot to null))
* increment base and return task;
*
* Because we rely on CASes of references, we do not need tag bits
* on base or top. They are simple ints as used in any circular
* array-based queue (see for example ArrayDeque). Updates to the
* indices guarantee that top == base means the queue is empty,
* but otherwise may err on the side of possibly making the queue
* appear nonempty when a push, pop, or poll have not fully
* committed. (Method isEmpty() checks the case of a partially
* completed removal of the last element.) Because of this, the
* poll operation, considered individually, is not wait-free. One
* thief cannot successfully continue until another in-progress
* one (or, if previously empty, a push) completes. However, in
* the aggregate, we ensure at least probabilistic
* non-blockingness. If an attempted steal fails, a thief always
* chooses a different random victim target to try next. So, in
* order for one thief to progress, it suffices for any
* in-progress poll or new push on any empty queue to
* complete. (This is why we normally use method pollAt and its
* variants that try once at the apparent base index, else
* consider alternative actions, rather than method poll, which
* retries.)
*
* 因为我们依赖引用的CASes，所以我们不需要在底部或顶部标记位。它们是用于任何基于循环数组的队列中的简单整数（参见例如ArrayDeque）。
* 对索引的更新保证top == base意味着队列是空的，但是否则可能会在push，pop或poll未完全提交时可能使队列显示为非空。
* （方法isEmpty（）检查部分完成删除最后一个元素的情况。）因此，单独考虑的poll操作不是等待的。
* 一个小偷不能成功地继续下去，直到另一个小偷（或者，如果先前是空的，推）完成。但总的来说，我们至少保证概率性的非阻塞性。
* 如果一次偷窃失败，一个小偷总是选择一个不同的随机受害者目标来尝试下一个。
* 所以，为了让一个小偷进步，只要有任何进行中的poll或者任何空队列的新push就足够了。
* （这就是为什么我们通常使用方法pollAt及其在变量基础上尝试一次的方法，否则考虑替代操作，而不是方法poll，重试。)
*
* This approach also enables support of a user mode in which
* local task processing is in FIFO, not LIFO order, simply by
* using poll rather than pop. This can be useful in
* message-passing frameworks in which tasks are never joined.
* However neither mode considers affinities, loads, cache
* localities, etc, so rarely provide the best possible
* performance on a given machine, but portably provide good
* throughput by averaging over these factors. Further, even if
* we did try to use such information, we do not usually have a
* basis for exploiting it. For example, some sets of tasks
* profit from cache affinities, but others are harmed by cache
* pollution effects. Additionally, even though it requires
* scanning, long-term throughput is often best using random
* selection rather than directed selection policies, so cheap
* randomization of sufficient quality is used whenever
* applicable. Various Marsaglia XorShifts (some with different
* shift constants) are inlined at use points.
* 这种方法还支持用本地任务处理在FIFO中而不是LIFO顺序的用户模式，只需使用poll而不是pop。
* 这在消息传递框架中是非常有用的，在这个框架中任务永远不会被加入。
* 然而，这两种模式都不考虑亲和性，负载，缓存区域等，因此很少在给定的机器上提供最好的性能，
* 但是通过对这些因素进行平均，可移植性提供了良好的吞吐量。
* 此外，即使我们试图使用这些信息，我们通常也没有发现它的依据。
* 例如，一些任务集合从缓存关系中获益，而另外一些则受到缓存污染影响的伤害。
* 另外，即使需要扫描，长期吞吐量通常也是使用随机选择而不是定向选择策略的最佳选择，
* 所以在适用的情况下使用足够质量的廉价随机化。各种Marsaglia XorShifts（一些具有不同的移位常数）在使用点内联。
*
* WorkQueues are also used in a similar way for tasks submitted
* to the pool. We cannot mix these tasks in the same queues used
* by workers. Instead, we randomly associate submission queues
* with submitting threads, using a form of hashing. The
* ThreadLocalRandom probe value serves as a hash code for
* choosing existing queues, and may be randomly repositioned upon
* contention with other submitters. In essence, submitters act
* like workers except that they are restricted to executing local
* tasks that they submitted (or in the case of CountedCompleters,
* others with the same root task). Insertion of tasks in shared
* mode requires a lock (mainly to protect in the case of
* resizing) but we use only a simple spinlock (using field
* qlock), because submitters encountering a busy queue move on to
* try or create other queues -- they block only when creating and
* registering new queues. Additionally, "qlock" saturates to an
* unlockable value (-1) at shutdown. Unlocking still can be and
* is performed by cheaper ordered writes of "qlock" in successful
* cases, but uses CAS in unsuccessful cases.
*
* WorkQueues也以类似的方式用于提交给池的任务。我们不能把这些任务混合在工人使用的同一个队列中。
* 相反，我们使用散列形式将提交队列与提交线程随机关联。
* ThreadLocalRandom探测值用作选择现有队列的哈希代码，并且可以在与其他提交者竞争时随机地重新定位。
* 实质上，提交者的行为与工作者相似，只是他们被限制为执行他们提交的本地任务（或者在CountedCompleters的情况下，其他人则具有相同的根任务）。
* 在共享模式下插入任务需要一个锁（主要是为了保护在调整大小的情况下），
* 但是我们只使用一个简单的自旋锁（使用字段qlock），因为提交者遇到一个忙碌的队列后继续尝试或创建其他队列 - 只有在创建和注册新的队列时
* 。此外，"qlock"在关机时饱和到一个不可解锁的值（-1）。解锁仍然可以和成功的情况下执行更便宜的有序的"qlock"写入，但使用CAS不成功的情况下。
*
* Management 管理
* ==========
*
* The main throughput advantages of work-stealing stem from
* decentralized control -- workers mostly take tasks from
* themselves or each other, at rates that can exceed a billion
* per second. The pool itself creates, activates (enables
* scanning for and running tasks), deactivates, blocks, and
* terminates threads, all with minimal central information.
* There are only a few properties that we can globally track or
* maintain, so we pack them into a small number of variables,
* often maintaining atomicity without blocking or locking.
* Nearly all essentially atomic control state is held in two
* volatile variables that are by far most often read (not
* written) as status and consistency checks. (Also, field
* "config" holds unchanging configuration state.)
*
* 偷窃工作的主要优势在于分散控制 - 工人们大多是从自己或彼此的任务中，以每秒超过10亿的速度进行工作。
* 池本身创建，激活（启用扫描和运行任务），停用，阻塞和终止线程，所有这些都以最少的中央信息。
* 我们可以全局跟踪或维护的属性只有少数，所以我们将它们打包成少量的变量，通常保持原子性而不会阻塞或锁定。
* 几乎所有本质上的原子控制状态都被保存在两个非常常被读取（不被写入）的易失变量中作为状态和一致性检查。 （另外，"config"字段保持不变的配置状态。）
*
*
* Field "ctl" contains 64 bits holding information needed to
* atomically decide to add, inactivate, enqueue (on an event
* queue), dequeue, and/or re-activate workers. To enable this
* packing, we restrict maximum parallelism to (1<<15)-1 (which is
* far in excess of normal operating range) to allow ids, counts,
* and their negations (used for thresholding) to fit into 16bit
* subfields.
*
* 字段"ctl"包含64位，用于存储原子级决定添加，禁用，入队（在事件队列上），出队和/或重新激活工作人员所需的信息。
* 为了实现这种打包，我们限制最大平行度为（1 << 15）-1（远远超过正常工作范围），以允许ID，计数和它们的否定（用于阈值处理）适合16位子域。
*
* Field "runState" holds lockable state bits (STARTED, STOP, etc)
* also protecting updates to the workQueues array. When used as
* a lock, it is normally held only for a few instructions (the
* only exceptions are one-time array initialization and uncommon
* resizing), so is nearly always available after at most a brief
* spin. But to be extra-cautious, after spinning, method
* awaitRunStateLock (called only if an initial CAS fails), uses a
* wait/notify mechanics on a builtin monitor to block when
* (rarely) needed. This would be a terrible idea for a highly
* contended lock, but most pools run without the lock ever
* contending after the spin limit, so this works fine as a more
* conservative alternative. Because we don't otherwise have an
* internal Object to use as a monitor, the "stealCounter" (an
* AtomicLong) is used when available (it too must be lazily
* initialized; see externalSubmit).
*
* 字段"runState"保存可锁定状态位（STARTED，STOP等），同时保护对workQueues数组的更新。
* 当作为锁使用时，通常只保留几条指令（唯一的例外是一次性数组初始化和不常见的调整大小），
* 所以在最多短暂旋转后几乎总是可用的。但要谨慎，在旋转之后，方法awaitRunStateLock（仅在初始CAS失败时调用）
* 在内置监视器上使用等待/通知机制来阻止何时（很少）需要。这对于高度锁定来说是一个可怕的想法，
* 但是大多数游戏池在没有锁定的情况下仍然在旋转限制之后竞争，所以这可以作为更保守的选择。
* 因为我们没有其他内部对象用作监视器，所以在可用时使用"stealCounter"（AtomicLong）（它也必须被懒惰地初始化;参见externalSubmit）
*
* Usages of "runState" vs "ctl" interact in only one case:
* deciding to add a worker thread (see tryAddWorker), in which
* case the ctl CAS is performed while the lock is held.
* “runState”vs“ctl”的用法仅在一个例子中进行交互:决定添加一个工作线程(请参阅“添加工作人员”)，在这种情况下，在锁定锁的情况下执行ctl cas。
*
* Recording WorkQueues. WorkQueues are recorded in the
* "workQueues" array. The array is created upon first use (see
* externalSubmit) and expanded if necessary. Updates to the
* array while recording new workers and unrecording terminated
* ones are protected from each other by the runState lock, but
* the array is otherwise concurrently readable, and accessed
* directly. We also ensure that reads of the array reference
* itself never become too stale. To simplify index-based
* operations, the array size is always a power of two, and all
* readers must tolerate null slots. Worker queues are at odd
* indices. Shared (submission) queues are at even indices, up to
* a maximum of 64 slots, to limit growth even if array needs to
* expand to add more workers. Grouping them together in this way
* simplifies and speeds up task scanning.
*
* 录制工作流程WorkQueues被记录在"workQueues"数组中。该数组在首次使用时创建（请参阅externalSubmit）并在必要时展开。
* 录制新工作人员和不录制已终止人员时对阵列的更新通过runState锁相互隔离，但数组可以同时读取并直接访问。我们还确保读取数组引用本身不会变得过时。
* 为了简化基于索引的操作，数组大小始终是2的乘方，所有读者都必须容忍空位。工人队列在奇数指数。共享（提交）队列处于偶数索引，最多可达64个时隙，
* 即使数组需要扩展以添加更多工作人员，也会限制增长。以这种方式将它们分组在一起简化和加快了任务扫描。
*
* All worker thread creation is on-demand, triggered by task
* submissions, replacement of terminated workers, and/or
* compensation for blocked workers. However, all other support
* code is set up to work with other policies. To ensure that we
* do not hold on to worker references that would prevent GC, All
* accesses to workQueues are via indices into the workQueues
* array (which is one source of some of the messy code
* constructions here). In essence, the workQueues array serves as
* a weak reference mechanism. Thus for example the stack top
* subfield of ctl stores indices, not references.
*
* 所有工作线程的创建都是按需提供的，由任务提交，更换终止的工作人员和/或对被阻止的工作人员进行补偿。
* 但是，所有其他支持代码都已设置为与其他策略配合使用。为了确保我们不要拘泥于可能阻止GC的工作者引用，
* 所有对workQueues的访问都是通过指向workQueues数组（这是这里一些混乱的代码构造的一个来源）的索引。
* 本质上，workQueues数组是一个弱引用机制。因此，例如，ctl的堆栈顶部子字段存储索引，而不是引用。
*
* Queuing Idle Workers. Unlike HPC work-stealing frameworks, we
* cannot let workers spin indefinitely scanning for tasks when
* none can be found immediately, and we cannot start/resume
* workers unless there appear to be tasks available. On the
* other hand, we must quickly prod them into action when new
* tasks are submitted or generated. In many usages, ramp-up time
* to activate workers is the main limiting factor in overall
* performance, which is compounded at program start-up by JIT
* compilation and allocation. So we streamline this as much as
* possible.
*
* 排队空闲的工人。不像高性能计算机窃取工作的框架，我们不能让工作人员无限期地扫描任务，
* 而不能立即找到任何工作，除非看起来有任务可用，否则我们不能启动/恢复工人。
* 另一方面，当新任务提交或产生时，我们必须迅速采取行动。在许多用法中，启动员工的加速时间是整体绩效的主要限制因素，
* 在程序启动时通过JIT汇编和分配加剧。所以我们尽可能简化它。
*
* The "ctl" field atomically maintains active and total worker
* counts as well as a queue to place waiting threads so they can
* be located for signalling. Active counts also play the role of
* quiescence indicators, so are decremented when workers believe
* that there are no more tasks to execute. The "queue" is
* actually a form of Treiber stack. A stack is ideal for
* activating threads in most-recently used order. This improves
* performance and locality, outweighing the disadvantages of
* being prone to contention and inability to release a worker
* unless it is topmost on stack. We park/unpark workers after
* pushing on the idle worker stack (represented by the lower
* 32bit subfield of ctl) when they cannot find work. The top
* stack state holds the value of the "scanState" field of the
* worker: its index and status, plus a version counter that, in
* addition to the count subfields (also serving as version
* stamps) provide protection against Treiber stack ABA effects.
*
* "ctl"字段自动维护活动和总工人数以及放置等待线程的队列，以便它们可以定位用于信令。
* 积极的计数也起到静止指标的作用，所以当工人认为没有更多的任务要执行时，积分计数就会减少。
* "队列"实际上是一个Treiber栈的形式。堆栈非常适合以最近使用的顺序激活线程。
* 这提高了性能和局部性，超过了容易发生争用和无法释放工人的缺点，除非它是最上面的堆栈。
* 我们在闲置的工作人员堆栈（由ctl的低32位子域表示）找不到工作时，将工人停放/停放。
* 顶层堆栈状态保存worker的"scanState"字段的值：索引和状态，以及版本计数器，除了计数子字段（也用作版本标记）之外，
* 还提供针对Treiber堆栈ABA效果的保护。
*
* Field scanState is used by both workers and the pool to manage
* and track whether a worker is INACTIVE (possibly blocked
* waiting for a signal), or SCANNING for tasks (when neither hold
* it is busy running tasks). When a worker is inactivated, its
* scanState field is set, and is prevented from executing tasks,
* even though it must scan once for them to avoid queuing
* races. Note that scanState updates lag queue CAS releases so
* usage requires care. When queued, the lower 16 bits of
* scanState must hold its pool index. So we place the index there
* upon initialization (see registerWorker) and otherwise keep it
* there or restore it when necessary.
*
* 现场scanState由worker和pool用来管理和跟踪worker是否处于INACTIVE状态（可能被阻塞在等待信号），
* 或者SCANNING用于任务（当两个任务都没有忙于运行任务时）。当工作人员被禁用时，它的scanState字段被设置，
* 并且被阻止执行任务，即使它必须扫描一次以避免排队竞争。请注意，scanState更新滞后队列CAS版本，因此使用需要谨慎。
* 排队时，scanState的低16位必须保存其索引。所以我们在初始化时将索引放在那里（请参阅registerWorker），否则将它保留在那里或在必要时恢复。
*
* Memory ordering. See "Correct and Efficient Work-Stealing for
* Weak Memory Models" by Le, Pop, Cohen, and Nardelli, PPoPP 2013
* (http://www.di.ens.fr/~zappa/readings/ppopp13.pdf) for an
* analysis of memory ordering requirements in work-stealing
* algorithms similar to the one used here. We usually need
* stronger than minimal ordering because we must sometimes signal
* workers, requiring Dekker-like full-fences to avoid lost
* signals. Arranging for enough ordering without expensive
* over-fencing requires tradeoffs among the supported means of
* expressing access constraints. The most central operations,
* taking from queues and updating ctl state, require full-fence
* CAS. Array slots are read using the emulation of volatiles
* provided by Unsafe. Access from other threads to WorkQueue
* base, top, and array requires a volatile load of the first of
* any of these read. We use the convention of declaring the
* "base" index volatile, and always read it before other fields.
* The owner thread must ensure ordered updates, so writes use
* ordered intrinsics unless they can piggyback on those for other
* writes. Similar conventions and rationales hold for other
* WorkQueue fields (such as "currentSteal") that are only written
* by owners but observed by others.
*
* 内存排序。
* Le，Pop，Cohen和Nardelli在PPoPP 2013（http://www.di.ens.fr/~zappa/readings/ppopp13.pdf）上的
* "正确和高效的偷窃工作"的工作窃取算法中的内存排序要求类似于这里使用的。我们通常需要比最低限度的排序更有力，
* 因为我们有时必须向工人发出信号，要求像德克一样的全面防护，以避免丢失信号。在没有昂贵的过度围栏的情况下进行足够的
* 排序需要在表达访问约束的支持手段之间权衡。最重要的操作是从队列中取出并更新ctl状态，这需要全面的CAS。使用不安全提
* 供的挥发物模拟来读取阵列插槽。从其他线程访问WorkQueue base，top和array需要对这些读取中的第一个进行非易失性加载。
* 我们使用声明"base"索引的惯例volatile，并且总是在其他字段之前读取它。所有者线程必须确保有序更新，因此写入使用有序
* 的内在函数，除非它们可以搭载在其他写入的那些函数上。其他WorkQueue字段（如"currentSteal"）的其他WorkQueue字段也有
* 类似的约定和理由，这些字段只能由所有者书写，但是由其他人观察。
*
* Creating workers. To create a worker, we pre-increment total
* count (serving as a reservation), and attempt to construct a
* ForkJoinWorkerThread via its factory. Upon construction, the
* new thread invokes registerWorker, where it constructs a
* WorkQueue and is assigned an index in the workQueues array
* (expanding the array if necessary). The thread is then
* started. Upon any exception across these steps, or null return
* from factory, deregisterWorker adjusts counts and records
* accordingly. If a null return, the pool continues running with
* fewer than the target number workers. If exceptional, the
* exception is propagated, generally to some external caller.
* Worker index assignment avoids the bias in scanning that would
* occur if entries were sequentially packed starting at the front
* of the workQueues array. We treat the array as a simple
* power-of-two hash table, expanding as needed. The seedIndex
* increment ensures no collisions until a resize is needed or a
* worker is deregistered and replaced, and thereafter keeps
* probability of collision low. We cannot use
* ThreadLocalRandom.getProbe() for similar purposes here because
* the thread has not started yet, but do so for creating
* submission queues for existing external threads.
*
* 创建工作。为了创建一个工人，我们预先增加总数（作为保留），并尝试通过其工厂构建一个ForkJoinWorkerThread。在构建时，新的线程调用registerWorker，
* 在那里构造一个WorkQueue，并在workQueues数组中分配一个索引（如果需要，扩展数组）。线程然后启动。如果在这些步骤中发生任何异常，
* 或者从工厂返回null，则deregisterWorker会相应地调整计数和记录。如果返回空值，那么池将继续运行，而目标编号的工人数少于此值。如果例外，
* 则将异常传播给一些外部呼叫者。工作者索引分配避免了在从workQueues数组开始的顺序打包条目时发生的扫描偏差。我们把这个数组视为一个简单的二元哈希表，
* 根据需要进行扩展。 seedIndex增量确保不会发生冲突，直到需要调整大小或者取消注册和替换工作人员，并且此后保持低冲突概率。
* 我们不能在这里使用ThreadLocalRandom.getProbe（）来达到类似的目的，因为线程还没有启动，但是为了创建现有外部线程的提交队列。
*
* Deactivation and waiting. Queuing encounters several intrinsic
* races; most notably that a task-producing thread can miss
* seeing (and signalling) another thread that gave up looking for
* work but has not yet entered the wait queue. When a worker
* cannot find a task to steal, it deactivates and enqueues. Very
* often, the lack of tasks is transient due to GC or OS
* scheduling. To reduce false-alarm deactivation, scanners
* compute checksums of queue states during sweeps. (The
* stability checks used here and elsewhere are probabilistic
* variants of snapshot techniques -- see Herlihy & Shavit.)
* Workers give up and try to deactivate only after the sum is
* stable across scans. Further, to avoid missed signals, they
* repeat this scanning process after successful enqueuing until
* again stable. In this state, the worker cannot take/run a task
* it sees until it is released from the queue, so the worker
* itself eventually tries to release itself or any successor (see
* tryRelease). Otherwise, upon an empty scan, a deactivated
* worker uses an adaptive local spin construction (see awaitWork)
* before blocking (via park). Note the unusual conventions about
* Thread.interrupts surrounding parking and other blocking:
* Because interrupts are used solely to alert threads to check
* termination, which is checked anyway upon blocking, we clear
* status (using Thread.interrupted) before any call to park, so
* that park does not immediately return due to status being set
* via some other unrelated call to interrupt in user code.
*
* 取消激活并等待。排队遇到几个固有的种族;最值得注意的是，一个任务生成线程可能会错过看到（和发信号）另一个线程，
* 放弃寻找工作，但还没有进入等待队列。当一个工作人员找不到任务要偷取时，就会停用并排队。很多时候，由于GC或OS调度，
* 缺乏任务是短暂的。为了减少错误警报停用，扫描器在扫描期间计算队列状态的校验和。
* （在这里和其他地方使用的稳定性检查是快照技术的概率变体 - 参见Herlihy＆Shavit。）工人放弃并且在整个扫描期间总和
* 稳定后才尝试去激活。此外，为了避免错过信号，他们在成功排队之后重复这个扫描过程直到再次稳定。在这种状态下，工作者
* 不能接受/运行它所看到的任务，直到它从队列中释放出来，所以工作者本身最终试图释放自己或任何后继者（参见tryRelease）。
* 否则，在空的扫描中，停用的工人在阻塞（通过停车）之前使用自适应本地旋转构造（参见awaitWork）。注意关于围绕停车和其
* 他阻塞的Thread.interrupts的不寻常约定：因为中断仅用于提醒线程检查终止，无论如何，在阻塞之后检查终止，所以我们在任何
* 呼叫停放之前清除状态（使用Thread.interrupted）由于通过其他不相关的呼叫来设置状态，用户代码中断将不会立即返回。
*
* Signalling and activation. Workers are created or activated
* only when there appears to be at least one task they might be
* able to find and execute. Upon push (either by a worker or an
* external submission) to a previously (possibly) empty queue,
* workers are signalled if idle, or created if fewer exist than
* the given parallelism level. These primary signals are
* buttressed by others whenever other threads remove a task from
* a queue and notice that there are other tasks there as well.
* On most platforms, signalling (unpark) overhead time is
* noticeably long, and the time between signalling a thread and
* it actually making progress can be very noticeably long, so it
* is worth offloading these delays from critical paths as much as
* possible. Also, because inactive workers are often rescanning
* or spinning rather than blocking, we set and clear the "parker"
* field of WorkQueues to reduce unnecessary calls to unpark.
* (This requires a secondary recheck to avoid missed signals.)
*
* 信令和激活。只有在看起来至少有一项他们可能能够找到并执行的任务时，才会创建或激活工人。
* 一旦（通过工作人员或外部提交）推送（先前（可能）空队列），工作人员在空闲时发信号通知，
* 或者如果存在比给定的并行性级别更少的信号，则发出信号。当其他线程从队列中删除一个任务时，
* 这些主要信号由其他线程支持，并注意到这里还有其他的任务。在大多数平台上，信令（unpark）的开销时间明显较长，
* 从一个线程到实际进展的时间可能会非常长，所以尽可能地将这些延迟从关键路径上卸载。另外，
* 由于不活跃的工作人员经常重新扫描或旋转，而不是阻止，我们设置并清除WorkQueues的"parker"字段，以减少不必要的停靠站点。
* （这需要二次重新检查以避免错过信号。）
*
* Trimming workers. To release resources after periods of lack of
* use, a worker starting to wait when the pool is quiescent will
* time out and terminate (see awaitWork) if the pool has remained
* quiescent for period IDLE_TIMEOUT, increasing the period as the
* number of threads decreases, eventually removing all workers.
* Also, when more than two spare threads exist, excess threads
* are immediately terminated at the next quiescent point.
* (Padding by two avoids hysteresis.)
*
* 整理工人。为了在不使用期间释放资源，当池静止时开始等待的工作者将超时并终止（参见awaitWork）如果池保持静止持续期间IDLE_TIMEOUT，
* 则最终随着线程数量的减少而增加删除所有的工人。另外，当存在两个以上的备用线程时，多余的线程立即在下一个静止点终止。 （填充两个避免迟滞。）
*
* Shutdown and Termination. A call to shutdownNow invokes
* tryTerminate to atomically set a runState bit. The calling
* thread, as well as every other worker thereafter terminating,
* helps terminate others by setting their (qlock) status,
* cancelling their unprocessed tasks, and waking them up, doing
* so repeatedly until stable (but with a loop bounded by the
* number of workers). Calls to non-abrupt shutdown() preface
* this by checking whether termination should commence. This
* relies primarily on the active count bits of "ctl" maintaining
* consensus -- tryTerminate is called from awaitWork whenever
* quiescent. However, external submitters do not take part in
* this consensus. So, tryTerminate sweeps through queues (until
* stable) to ensure lack of in-flight submissions and workers
* about to process them before triggering the "STOP" phase of
* termination. (Note: there is an intrinsic conflict if
* helpQuiescePool is called when shutdown is enabled. Both wait
* for quiescence, but tryTerminate is biased to not trigger until
* helpQuiescePool completes.)
*
* 关机和终止。对shutdownNow的调用调用tryTerminate来自动设置一个runState位。调用线程以及之后的其他每个工作者终止，
* 通过设置（qlock）状态，取消未处理的任务并唤醒它们来帮助终止其他人，重复这样做直到稳定（但是由工人数量限制的循环）。
* 调用非突发关机（）通过检查终止是否应该开始。这主要依赖于保持一致的"ctl"的活动计数位 - 每当静止时，tryTerminate就从await工作中调用。
* 但是，外部提交者不参与这个共识。因此，尝试终止扫描队列（直到稳定），以确保在触发终止的"停止"阶段之前缺少空中提交和工作人员处理它们。
* （注意：如果在启用shutdown的情况下调用helpQuiescePool，则存在内部冲突，两者都等待静止，但tryTerminate有偏见，直到helpQuiescePool完成时才触发。
*
*
* Joining Tasks 加入任务
* =============
*
* Any of several actions may be taken when one worker is waiting
* to join a task stolen (or always held) by another. Because we
* are multiplexing many tasks on to a pool of workers, we can't
* just let them block (as in Thread.join). We also cannot just
* reassign the joiner's run-time stack with another and replace
* it later, which would be a form of "continuation", that even if
* possible is not necessarily a good idea since we may need both
* an unblocked task and its continuation to progress. Instead we
* combine two tactics:
* 当一名工作人员正在等待加入被他人盗取（或总是被盗）的任务时，可能会采取任何一种行动。
* 因为我们将许多任务复用到工作池中，所以我们不能让它们阻塞（如在Thread.join中）。我们也不能仅仅把joiner的运行时间栈重新分配给另一个栈，
* 并且稍后将其替换，这将是一种"延续"形式，即使可能也不一定是一个好主意，因为我们可能需要一个畅通无阻的任务，进展。相反，
* 我们结合了两种策略：
*
* Helping: Arranging for the joiner to execute some task that it
* would be running if the steal had not occurred. 帮助:安排joiner执行一些任务，如果没有发生，它将运行。
*
* Compensating: Unless there are already enough live threads,
* method tryCompensate() may create or re-activate a spare
* thread to compensate for blocked joiners until they unblock.
* 补偿:除非已经有足够的活线程，方法尝试补偿()可以创建或重新激活一个备用线程来补偿阻塞的连接，直到它们解除阻塞为止。
*
* A third form (implemented in tryRemoveAndExec) amounts to
* helping a hypothetical compensator: If we can readily tell that
* a possible action of a compensator is to steal and execute the
* task being joined, the joining thread can do so directly,
* without the need for a compensation thread (although at the
* expense of larger run-time stacks, but the tradeoff is
* typically worthwhile).
*
* 第三种形式（在tryRemoveAndExec中实现）相当于帮助一个假设的补偿器：如果我们可以很容易地告诉补偿器的一个可能的动作是窃取和执行被加入的任务，
* 那么加入的线程可以直接完成，而不需要补偿线程（尽管以较大的运行时间堆栈为代价，但折衷通常是值得的）。
*
* The ManagedBlocker extension API can't use helping so relies
* only on compensation in method awaitBlocker.
* 管理的拦截器扩展API不能使用帮助，因此只依赖于方法中的补偿等待拦截器。
*
* The algorithm in helpStealer entails a form of "linear
* helping". Each worker records (in field currentSteal) the most
* recent task it stole from some other worker (or a submission).
* It also records (in field currentJoin) the task it is currently
* actively joining. Method helpStealer uses these markers to try
* to find a worker to help (i.e., steal back a task from and
* execute it) that could hasten completion of the actively joined
* task. Thus, the joiner executes a task that would be on its
* own local deque had the to-be-joined task not been stolen. This
* is a conservative variant of the approach described in Wagner &
* Calder "Leapfrogging: a portable technique for implementing
* efficient futures" SIGPLAN Notices, 1993
* (http://portal.acm.org/citation.cfm?id=155354). It differs in
* that: (1) We only maintain dependency links across workers upon
* steals, rather than use per-task bookkeeping. This sometimes
* requires a linear scan of workQueues array to locate stealers,
* but often doesn't because stealers leave hints (that may become
* stale/wrong) of where to locate them. It is only a hint
* because a worker might have had multiple steals and the hint
* records only one of them (usually the most current). Hinting
* isolates cost to when it is needed, rather than adding to
* per-task overhead. (2) It is "shallow", ignoring nesting and
* potentially cyclic mutual steals. (3) It is intentionally
* racy: field currentJoin is updated only while actively joining,
* which means that we miss links in the chain during long-lived
* tasks, GC stalls etc (which is OK since blocking in such cases
* is usually a good idea). (4) We bound the number of attempts
* to find work using checksums and fall back to suspending the
* worker and if necessary replacing it with another.
*
* helpStealer中的算法需要一种"线性帮助"的形式。
* 每个工作人员记录（在currentSteal字段中）从其他工作人员（或提交）偷取的最近任务。它还记录（在currentJoin字段中）当前正在加入的任务。
* 方法helpStealer使用这些标记来试图找到一个工作人员来帮助（即，从任务中取回并执行任务），这可以加快主动联合任务的完成。
* 因此，加盟者执行一项任务，如果被加入的任务没有被盗，那么这个任务本身就是本地的。
* 这是Wagner＆Calder在"跳跃：一种实现高效期货的便携式技术"（SIGPLAN Notices，1993）（http://portal.acm.org/citation.cfm?id=155354）
* 中描述的方法的保守变体。它的不同之处在于：
* （1）我们只保留偷工作中的工人之间的依赖关系，而不是使用按任务记账。这有时需要对workQueues数组进行线性扫描来定位窃听器，
* 但通常不会因为窃听者留下提示（可能变得陈旧/错误）而将其定位到何处。这只是一个暗示，因为工人可能有多次抢断，
* 而提示只记录其中的一次（通常是最新的）。暗示隔离成本需要时，而不是增加到每个任务的开销。
* （2）"浅"，忽略嵌套和潜在的循环互抢。
* （3）故意激活：字段currentJoin只在主动加入时更新，这意味着我们在长期任务，GC停顿等期间错过了链中的链接（这是可以的，因为
* 在这种情况下阻塞通常是个好主意） 。
* （4）我们限制了使用校验和的尝试次数，并回退到暂停工作，必要时替换为另一次。
*
* Helping actions for CountedCompleters do not require tracking
* currentJoins: Method helpComplete takes and executes any task
* with the same root as the task being waited on (preferring
* local pops to non-local polls). However, this still entails
* some traversal of completer chains, so is less efficient than
* using CountedCompleters without explicit joins.
*
* 对计数完成者的帮助操作不需要跟踪当前的联接：方法帮助完成占用和执行任何具有与正在等待的任务相同的根目录的任务
* （首选本地弹出到非本地轮询）。然而，这仍然需要一些完成链的遍历，所以比没有显式连接的使用计数完成者效率低。
*
* Compensation does not aim to keep exactly the target
* parallelism number of unblocked threads running at any given
* time. Some previous versions of this class employed immediate
* compensations for any blocked join. However, in practice, the
* vast majority of blockages are transient byproducts of GC and
* other JVM or OS activities that are made worse by replacement.
* Currently, compensation is attempted only after validating that
* all purportedly active threads are processing tasks by checking
* field WorkQueue.scanState, which eliminates most false
* positives. Also, compensation is bypassed (tolerating fewer
* threads) in the most common case in which it is rarely
* beneficial: when a worker with an empty queue (thus no
* continuation tasks) blocks on a join and there still remain
* enough threads to ensure liveness.
*
* 补偿并不是要确保在任何给定的时间保持未被阻塞的线程的目标并行数量。这个类的一些以前的版本采用立即补偿任何封锁的连接。
* 但实际上，绝大多数堵塞是GC和其他JVM或OS活动的暂时性副产品，通过替换而变得更糟。
* 目前，只有在通过检查字段"工作队列"来验证所有据称活动的线程正在处理任务之后，才会尝试进行补偿。扫描状态，
* 从而消除了大多数误报。而且，在最不常见的情况下，
* 补偿会被绕过（容忍的线程更少）：当队列空闲的工作人员（因此没有连续任务）阻塞连接时，仍然有足够的线程来保证活跃性。
*
* The compensation mechanism may be bounded. Bounds for the
* commonPool (see commonMaxSpares) better enable JVMs to cope
* with programming errors and abuse before running out of
* resources to do so. In other cases, users may supply factories
* that limit thread construction. The effects of bounding in this
* pool (like all others) is imprecise. Total worker counts are
* decremented when threads deregister, not when they exit and
* resources are reclaimed by the JVM and OS. So the number of
* simultaneously live threads may transiently exceed bounds.
*
* 补偿机制可能是有限的。 commonPool的界限（请参阅commonMaxSpares）更好地使JVM能够在耗尽资源之前处理编程错误和滥用。
* 在其他情况下，用户可能会提供限制螺纹结构的工厂。在这个池中的边界的影响（像所有其他）是不精确的。
* 当线程取消注册时，总工作人员计数递减，而不是退出并且JVM和OS回收资源。所以同时活动的线程数量可能暂时超过界限。
*
* Common Pool
* ===========
*
* The static common pool always exists after static
* initialization. Since it (or any other created pool) need
* never be used, we minimize initial construction overhead and
* footprint to the setup of about a dozen fields, with no nested
* allocation. Most bootstrapping occurs within method
* externalSubmit during the first submission to the pool.
* 静态初始化后，静态公共池始终存在。由于它（或任何其他创建的池）不需要被使用，
* 所以我们将最初的构建开销和占用空间最小化到大约十几个字段的设置，没有嵌套的分配。大多数引导在第一次提交到池时在externalSubmit方法中发生。
*
* When external threads submit to the common pool, they can
* perform subtask processing (see externalHelpComplete and
* related methods) upon joins. This caller-helps policy makes it
* sensible to set common pool parallelism level to one (or more)
* less than the total number of available cores, or even zero for
* pure caller-runs. We do not need to record whether external
* submissions are to the common pool -- if not, external help
* methods return quickly. These submitters would otherwise be
* blocked waiting for completion, so the extra effort (with
* liberally sprinkled task status checks) in inapplicable cases
* amounts to an odd form of limited spin-wait before blocking in
* ForkJoinTask.join.
*
* 当外部线程提交到公共池时，他们可以在连接时执行子任务处理（请参阅externalHelpComplete和相关方法）。
* 这个调用者帮助策略使得将公共池并行性级别设置为小于可用内核总数的一个（或更多），
* 或者对于纯粹的调用者运行甚至为零是明智的。我们不需要记录外部提交是否属于公共池，
* 否则外部帮助方法会很快返回。否则这些提交者将被阻塞等待完成，所以在不适用的情况下额外的工作量（大量的任务状态检查）
* 相当于在ForkJoinTask.join阻塞之前的一个奇怪形式的有限旋转等待。
*
* As a more appropriate default in managed environments, unless
* overridden by system properties, we use workers of subclass
* InnocuousForkJoinWorkerThread when there is a SecurityManager
* present. These workers have no permissions set, do not belong
* to any user-defined ThreadGroup, and erase all ThreadLocals
* after executing any top-level task (see WorkQueue.runTask).
* The associated mechanics (mainly in ForkJoinWorkerThread) may
* be JVM-dependent and must access particular Thread class fields
* to achieve this effect.
*
* 作为托管环境中更合适的缺省值，除非被系统属性覆盖，否则当存在SecurityManager时，我们使用子类InnocuousForkJoinWorkerThread的工作者。
* 这些工作人员没有权限设置，不属于任何用户定义的ThreadGroup，并在执行任何顶级任务（请参见WorkQueue.runTask）后清除所有ThreadLocals。
* 相关的机制（主要在ForkJoinWorkerThread中）可能依赖于JVM，并且必须访问特定的Thread类字段才能达到这个效果。
*
* Style notes 样式笔记
* ===========
*
* Memory ordering relies mainly on Unsafe intrinsics that carry
* the further responsibility of explicitly performing null- and
* bounds- checks otherwise carried out implicitly by JVMs. This
* can be awkward and ugly, but also reflects the need to control
* outcomes across the unusual cases that arise in very racy code
* with very few invariants. So these explicit checks would exist
* in some form anyway. All fields are read into locals before
* use, and null-checked if they are references. This is usually
* done in a "C"-like style of listing declarations at the heads
* of methods or blocks, and using inline assignments on first
* encounter. Array bounds-checks are usually performed by
* masking with array.length-1, which relies on the invariant that
* these arrays are created with positive lengths, which is itself
* paranoically checked. Nearly all explicit checks lead to
* bypass/return, not exception throws, because they may
* legitimately arise due to cancellation/revocation during
* shutdown.
*
* 内存排序主要依赖于不安全的内部函数，这些内部函数承担进一步明确执行空白和边界检查的责任，否则由JVM隐式执行。
* 这可能是尴尬和丑陋的，但也反映了需要控制的结果在非常激烈的代码中出现的不寻常的情况下，
* 几乎不变的。所以这些明确的检查将以某种形式存在。所有的字段在使用之前都会被读入本地，如果它们是引用，
* 则会进行空值检查。这通常在方法或块的头部以"C"类型的列表声明的方式完成，并且在首次遇到时使用内联分配。
* 数组边界检查通常是通过使用array.length-1进行掩码来实现的，该数组依赖于这些数组以正长度创建的不变量，这本身是经过偏执检查的。
* 几乎所有显式检查都会导致绕过/返回，而不是异常抛出，因为它们可能会因停机期间的取消/撤销而合法产生。
*
* There is a lot of representation-level coupling among classes
* ForkJoinPool, ForkJoinWorkerThread, and ForkJoinTask. The
* fields of WorkQueue maintain data structures managed by
* ForkJoinPool, so are directly accessed. There is little point
* trying to reduce this, since any associated future changes in
* representations will need to be accompanied by algorithmic
* changes anyway. Several methods intrinsically sprawl because
* they must accumulate sets of consistent reads of fields held in
* local variables. There are also other coding oddities
* (including several unnecessary-looking hoisted null checks)
* that help some methods perform reasonably even when interpreted
* (not compiled).
*
* 在类ForkJoinPool，ForkJoinWorkerThread和ForkJoinTask之间有很多表示级耦合。 WorkQueue的字段维护由ForkJoinPool管理的数据结构，
* 因此可以直接访问。试图减少这一点是没有意义的，因为任何关联的未来表示变化都需要伴随着算法变化。有几种方法本质上是蔓延性的，
* 因为它们必须累积本地变量中保持的字段的一致读取。还有其他的编码怪异（包括几个不必要的提升空检查），
* 即使在解释（不编译）时也可以帮助某些方法合理地执行。
*
* The order of declarations in this file is (with a few exceptions): 这个文件中的声明的顺序是（有一些例外）：
* (1) Static utility functions 静态的效用函数
* (2) Nested (static) classes 嵌套(静态)类
* (3) Static fields 静态字段
* (4) Fields, along with constants used when unpacking some of them 字段，以及在拆包时使用的常量
* (5) Internal control methods 内部控制的方法
* (6) Callbacks and other support for ForkJoinTask methods 回调和对ForkJoinTask方法的其他支持
* (7) Exported methods 导出的方法
* (8) Static block initializing statics in minimally dependent order 在最小依赖顺序中，静态块初始化静态块
*/
|
