特别声明:严禁任何形式的转载

前情提要

蛇皮Linux作业4

在操作系统理论课第二章当中，我们接触到了大量的 PV 操作，用于在多个并发进程之间实现互斥和同步。其实，从本质上来说，PV 操作就是加锁和开锁操作; 而锁在并行系统中，也是实现程序结果正确性和一致性最有效的方法。首先，我们阅读“图 1”中的“基于标志（flag）的锁实现方式”伪代码片段，回答下述问题：

1 typedef struct __lock_t { int flag ; } lock_t;
2
3 void init(lock_t *mutex) {
4 // 0 -> lock is available, 1 -> held
5 mutex->flag = 0;
6 }
7
8 void lock(lock_t *mutex) {
9 while (mutex->flag == 1) // TEST the flag
10 ; // spin-wait (do nothing)
11 mutex->flag = 1; // now SET it!
12 }
13
14 void unlock(lock_t *mutex) {
15 mutex->flag = 0;
16 }

4.1.1 第 10 行的注释，spin-wait，是什么意思？

Threading in C# - Part 5 - Parallel Programming (albahari.com)

自旋等待，在循环中轮询事件来避免阻塞开销。也称为忙等待，因为CPU一直忙于执行（不做任何事情的）循环。

4.1.2 假设没有底层硬件或操作系统的相关支持，该锁用于进程间的互斥则其实现方式会有什么问题？请详细说明。

没有划分临界区。

flag值为0时，两个进程若并发运行lock程序，flag值均检测到0并同时（并发）置其为1，则导致两个进程同时进入同一个临界区，都拥有了同一种临界资源。这与互斥性相矛盾。

为了弥补上述“基于标志的锁实现”的不足，出现了原子交换的锁实现方式，该方式一般由硬件或操作系统提供原语支持（例如，在 CPU 支持下，一般对应到一条具体的 CPU 指令），具有原子性。假设该原子指令名为“Test-And-Set”，它实现的具体过程如图 2 所示:

1 int TestAndSet(int *old_ptr, int new) {
2 int old = *old_ptr; // fetch old value at old_ptr
3 *old_ptr = new; //store ‘new’ into old_ptr
4 return old; //return the old value
5 }

从图 2 可以看出，该指令只是一个新旧值交换，然后返回旧值的过程，那么它是如何实现锁的功能呢? 请阅读图 3“基于 Test-And-Set 指令”的锁实现方式的伪代码，尝试回答问题:

1 typedef struct __lock_t {
2 int flag;
3 } lock_t;
4
5 void init(lock_t *lock) {
6 // 0 indicates that lock is available, 1 that it is held
7 lock->flag = 0;
8 } 
9
10 void lock(lock_t *lock) {
11 while (TestAndSet(&lock->flag, 1) == 1)
12 ; // spin-wait (do nothing)
13 } 
14
15 void unlock(lock_t *lock) {
16 lock->flag = 0;
17 }

4.1.3 "基于 Test-and-Set"指令的锁实现方式，是否可以解决 4.1.2 中，“基于标志（flag）的锁实现方式”所存在的问题，为什么？

可以。因为Test-and-Set指令具有原子性，要么一次性执行完，要么不执行。如果多个进程都想进入临界区且flag为0，总是有且仅有一个进程能执行加锁操作，其他所有进程在其后调用TestAndSet指令时会发现返回值是0，从而实现进程间的互斥。

4.1.4 假设系统中有 2 个线程 X 和 Y（优先级相同），它们之间通过“CPU 时间片轮转调度策略”来分享底层唯一的一个 CPU 资源。其中，X 在某个时刻通过图 3 的 lock()获取到了锁，并且需要运行 10 个时间片才会调用 unlock()来释放锁。请问，在此时间段内，Y 会分到时间片吗? 如果可以分到，那么 Y 是个什么运行形态? 此运行形态会带来什么样的负面效果？

可以分到，Y是spin-wait的运行状态，此时CPU一直执行lock程序的无意义循环，导致CPU利用效率下降。

---------------------------------------------------------------------------—

首先阅读图 4 的“基于 Linux 的 Futex 锁实现方式”伪代码:

1 void mutex_lock (int *mutex) {
2 int v;
3 /* Bit 31 was clear, we got the mutex (this is the fastpath) */
4 if (atomic_bit_test_set (mutex, 31) == 0) 
5 return;
6 atomic_increment (mutex);
7 while (1) {
8 if (atomic_bit_test_set (mutex, 31) == 0) {
9 atomic_decrement (mutex);
10 return;
11 } 
12 /* We have to wait now. First make sure the futex value
13 We are monitoring is truly negative (i.e. locked). */
14 v = *mutex;
15 if (v >= 0)
16 continue;
17 futex_wait (mutex, v);
18 }/*end while*/
19 }
20
21 void mutex_unlock (int *mutex) {
22 /* Adding 0x80000000 to the counter results in 0 if and only if
23 there are not other interested threads */
24 if (atomic_add_zero (mutex, 0x80000000))
25 return;
26
27 /* There are other threads waiting for this mutex,
28 wake one of them up. */
29 futex_wake (mutex);
30 }

在此锁的实现方式中，Linux 用一个 int 型的 mutex 变量，来达到 2 个用途：第一，此变量为 32 位，其中，最高位的值（第 31 位）可以是 0，也能够为 1，分别表示，该锁没有被占用和该锁已经被占用（注意：最高位为 1 意味着该变量的值为负数）；第二，此变量的其他位，用于表示有多少个其他的线程正在等待该锁被释放。其中： atomic_bit_test_set (mutex, 31) 的基本作用是用于获取 mutex 第 31 位的值，并置 1，且返回其旧值；atomic_add_zero (mutex, 0x80000000)的基本作用是两个参数相加，并将其和的值赋予 mutex，再判断：如果和等于零, 则返回 true, 否则为 false。接下来尝试回答下述问题:

4.1.5 该图中的第 4～5 行，和图中的第 8～11 行，具体实现什么作用? 它们是否有功能冗余和冲突? 可以去掉当中的一个吗? 为什么?

4~5行，判断锁是否已经被占用，若已被占用则执行下面的语句；若未被占用，把锁占用然后return。

8~11行，判断锁是否已经被占用，若已被占用（最高位等于1时）则执行下面的语句；若未被占用（最高位等于0时），把锁占用然后把mutex值减一，表示该线程进入临界区，等待的线程少了一个（-1操作通过一个专门的原语进行，作用是保证互斥性以及mutex不会溢出）然后return。

不可以去掉其中一个，若去掉4~ 5行，则线程一上来就把mutex值+1，表示等待的线程多了一个（+1操作通过一个专门的原语进行，作用是保证互斥性以及mutex值不会溢出），导致临界资源没有被充分利用；若去掉8~11行，则mutex值不会减而且在检测到锁未被占用后没有把mutex最高位置1，导致实际等待的线程与读取到的数值不符，而且保证不了互斥性.

4.1.6 在第 24～25 行中的 if 语句是用来干什么的? 如果条件语句 atomic_add_zero (mutex, 0x80000000) 为真，为什么要直接 return，为什么不直接执行第 29 行程序呢?

第一个问题：

判断解锁后有没有等待中的线程，若没有则直接return，若没有则执行下面的语句；

第二个问题：

如果条件语句 atomic_add_zero(mutex, 0x80000000) 为真说明没有等待中的线程，也就无从唤醒了，所以不用执行第 29 行程序，免得出现不必要的开销。

4.1.7 图 4 所展示的 Futex 锁实现方式，是否改进了 4.1.4 问题中提到的负面效果，为什么?

解决了，因为等待中的线程化主动为被动，从等待时不断检测锁是否被占用改为了等待时睡眠，直到被唤醒（此时锁未被占用），提高了CPU的利用率。

NVIDIA Reflex：一套用于在竞技游戏中优化和测量延迟的技术

Abstract

随着电竞赛事在收视率与游戏时间上均已达到可与传统运动相媲美的程度，对于游戏玩家来说，优化 PC 和图形硬件以使其发挥最佳性能比以往任何时候都更为重要。英伟达的Reflex就是这样一款革命性的组合：包括可测量和降低系统延迟的硬件和软件技术。

Introduction

在讨论游戏的延迟问题时，人们往往关注的是网络延迟，也即游戏客户端与多人服务器之间的往返时延（ping值），ping值过高导致的游戏体验极差的问题想必不少玩过网络游戏的人都深恶痛绝。而系统延迟就不那么为人所知了，实际上，这也是影响游戏体验的一个很重要的因素。因而，为了优化因系统延迟而起的游戏体验，英伟达公司利用自身的多年硬件技术积累、并借助充足的资本和优良的基础设施优势，研发出了 Reflex 技术。

在探讨这项重磅技术之前，先简单介绍一下系统延迟及其引发的种种问题。

系统延迟的简述

首先，如下图所示，系统延迟可分为几大块：

**外设延迟：**输入设备处理机械输入并将这些输入事件发送到 PC 所需的时间
**游戏延迟：**CPU 处理对游戏世界的输入或更改并提交新帧供 GPU 渲染所需的时间
**渲染延迟：**从待渲染的帧排队列齐到 GPU 完全渲染帧之间的时间
**PC 延迟：**帧在 PC 上传输所需的时间。这包括游戏延迟和渲染延迟
**显示延迟：**GPU 完成帧渲染后，显示器呈现新图像所需的时间
**系统延迟：**涵盖整个端到端测量的时间 – 从外设延迟开始到显示延迟结束

具体其到对游戏的影响，则大致可以分为以下几类:

响应速度延迟，比如说您移动了鼠标，但屏幕上的准星没能及时跟上您的操作。
射击延迟，比如说您开枪射击，但弹孔贴花、弹道和武器后坐力都滞后于实际的鼠标点击操作。
对手定位延迟，也称为“探头优势”。

这些概要定义忽略了某些细节，不过它们确实为我们提供了有效说明延迟的良好基础。

举一个很简单的射击游戏的例子，来说明系统延迟对于游戏的影响：敌人的人物模型在经过自身的十字准星时按下射击键（通常用到鼠标左键），很显然这时应该命中了目标。但由于PC 需要一定的时间来处理信息、渲染帧并将其呈现，此外，鼠标带来的外设延迟也。总而言之，在显示器上的敌人模型往往滞后于游戏引擎。在毫秒必争的竞技游戏中，这样不起眼的系统延迟（或许是额外的 30 到 40 毫秒）也可能是一场比赛的胜负手。

那么，除了印象流，有没有数据支撑这样的系统延迟确实影响了游戏？

在研究*“绝地求生 (PUBG)”和“堡垒之夜 (Fortnite)”*数据后，英伟达团队给出了肯定的答案：

上图横轴是FPS值（每秒帧数），纵轴是K/D 比率的相对改良值。

也就是说，较高的 FPS（较低的延迟）和 K/D 比率（击杀死亡比）之间具有正相关性。

此外，需要注意的是，系统延迟不是简单的将各部分延迟相加求和，因为在渲染过程中具有延迟重叠现象。

如上图所示：大多数重叠发生在模拟和 GPU 渲染完成之间的 PC 延迟核心部分。这是因为帧通过称为 drawcall 的小作业进行渲染并最终会分组到不同的作业包上，这样一来，帧会分为多个小块从而在计算机的各个阶段中共存。

系统延迟的测量

相比于网络延迟，系统延迟无疑更难以精确测量，这是因为想要收集从点击鼠标到显示器做出反应的数据，需要一整套起码花费7000美元的测量设备，包括昂贵且笨重的高速相机、工程设备以及经过改造的鼠标和 LED 灯。

我相信这对于任何竞技游戏的普通玩家而言，都是完全不可接受的负担。对于着手研究系统延迟的开发人员，也是一个大问题。更何况，每一次简单的延迟测量，都要花费约3分钟时间。

分析到这里，我们不难发现，减少系统延迟以提高游戏体验这一需求，已经很清晰了，接下来就要介绍英伟达满足这个需求的具体实现方案了。

Reflex SDK

首先是软件部分

分析游戏时，我们通常会尝试将性能定性为受 GPU 或 CPU 限制。这对于了解系统性能非常有帮助，在现实世界中，竞技游戏情况瞬息万变，其通常会在这两种状态中来回切换。

首先我们从GPU密集型场景入手，以此来描绘 Reflex SDK 的优越性：

大部分游戏都免不了会加入各种爆炸场面，此时游戏中存在大量颗粒物而受GPU限制。

在类似场景中，如上图所示，我们可以看到渲染队列中已经充满了帧，因为CPU 处理帧的速度快于 GPU 渲染帧的速度。在这种情况下，整个管道受GPU效率限制，导致形成CPU反压。

反压是在实时数据处理中，数据管道某个节点上游产生数据的速度大于该节点处理数据速度的一种现象。反压会从该节点向上游传递，一直到数据源，并降低数据源的摄入速度。

在以往，利用显卡驱动的超低延迟模式，通常可以减少渲染队列中的作业，缓解这一情况。但由于驱动只是外部软件，控制能力较低，无法彻底消除游戏和 CPU 方面增加的反压。

而现在，NVIDIA开发人员已经实现直接在游戏和硬件中植入Reflex SDK，以此来动态调整渲染工作提交给GPU的时间，来有效地延缓输入和游戏模拟的采样，以确保能够得到及时的处理。

因此，Reflex SDK 带来的延迟优势通常比驱动中的超低延迟模式要出色得多。

那么，具体到底层，Reflex SDK是如何工作的呢?

在启用了NVIDIA Reflex SDK之后，如下图所示，渲染队列几乎完全消失。这是因为Reflex SDK通过限制CPU的运行速度，使其无法提前运行达到的。这样做带来的好处一是使CPU尽可能地采样到最后一刻的输入，使得外设末端的信号不再需要等待下一次轮询，从而降低系统延迟，二是CPU的反压降低了，清空的渲染队列不会使GPU渲染的压力向CPU传递。此外，根植于硬件的Reflex SDK技术也能及时向GPU提交帧，让GPU马不停蹄地在作业管线中工作——这降低了GPU从待命到工作之间的延迟，在游戏从CPU受限的场合和受GPU受限的场合中来回切换时显得尤为重要。

总而言之，NVIDIA Reflex SDK技术就像一种“动态”的帧率限制技术，它不必将帧率锁定为固定值，而是可以按照超越限制的速度运行。在保持系统延迟最小化的理想情况下，它总能给予玩家更好的帧率显示体验。

在受CPU限制时，通过Reflex SDK启用Reflex 低延迟模式，同样可以降低系统延迟。

这是因为虽然此举并不能提高FPS，但是速度更快的GPU意味着可以更快地将经渲染的图像发送到显示器，这是通过降低显示延迟来降低系统延迟。

此外，即使受 CPU 限制，Reflex 低延迟模式还具有“加速”设置，该设置会禁用省电功能，从而略微减少延迟。在受 CPU 限制、GPU 利用率较低的情况下，GPU 时钟将保持较高频率以加快处理速度，从而可以将帧尽快传递到显示器。通常，这种加速设置能带来的好处并不大，但有助于尽可能降低管线中每一毫秒的延迟，毕竟每一毫秒都可能成为游戏的胜负手，不容小觑。

Reflex 延迟分析器

在硬件方面，NVIDIA Relflex同样表现出色。

过去需要花费数万元才能进行的系统延迟数据测量，现在可以轻易地进行了。兼容的360Hz G-SYNC显示器已经在2020年秋季发布，并搭载一项新功能——NVIDIA Reflex 延迟分析器。这一革命性的新增功能让游戏玩家能够衡量其系统的响应速度，从而使他们能够在开始比赛之前完全了解并优化 PC 的性能，并通过正确的驱动程序和来自游戏开发人员的支持来减少系统延迟。

Reflex 延迟分析器的工作原理是检测鼠标的点击操作与屏幕上显示的像素发生变化（即枪焰）之间的时间，从而检测出系统延迟。

要使用此功能，只需要把兼容该项功能的显示器侧面接口接上鼠标即可。此外，使用者完全不用担心这项新功能会拖慢PC的运算速度，因为兼容显示器的 Reflex USB 端口是一条通向PC的简单直接通道，可以在不增加任何延迟的前提下监控鼠标的输入。

显然，检测鼠标的点击操作需要鼠标的支持与配合，因此只有在使用兼容型鼠标接入时，检测到的才是完整的端到端系统延迟；否则只能获得PC延迟+显示延迟——但即便如此，也能大大节省成本了。

Conclusion

在软件方面，NVIDIA Reflex SDK 用于在GPU密集型的场景降低系统延迟。

在硬件方面，NVIDIA Reflex 延迟分析器和兼容的显示器互相配合，实现了便捷且完整的端到端的系统延迟测量。

对普通玩家而言，几十毫秒的提升貌似并不会影响感知，但实际上积小成多，系统延迟的降低无疑能够带来更好的竞技体验。

正如英伟达为NVIDIA Reflex技术附上的宣传标语所说的：胜负就在毫秒之间。