时间限制： 1.0 秒

空间限制： 512 MB

题目背景

NUMA（Non-Uniform Memory Access）是一种处理器内存架构，其设计旨在提高计算机系统的性能和可扩展性。在 NUMA 系统中，多个处理器核心和内存模块分布在不同的物理节点上，这些节点之间通常通过互连网络连接。每个处理器核心会有附近的内存块，这样可以更快地访问该内存，从而减少延迟。然而，当处理器需要访问其他节点上的内存时，就会引入额外的延迟。

NUMA 系统的主要优势在于提高性能和可扩展性。通过将处理器核心和内存分布在多个节点中，系统可以更有效地处理大规模并行计算任务。这种架构特别适合于多处理器系统，可以有效减少内存访问延迟，提高整体性能。

然而，NUMA 系统也面临一些挑战。为了充分发挥其优势，需要精心设计软件来优化内存访问模式。合理的内存分配和访问策略对于避免性能下降至关重要。

NUMA感知的锁（NUMA-aware Lock） 是一种处理并发编程时考虑到NUMA系统特性的锁机制。在NUMA系统中，由于不同处理器核心访问不同物理内存节点的延迟不同，传统的锁机制可能导致性能下降。 为了解决这个问题，NUMA感知的锁会考虑到处理器核心与内存之间的距离，以及内存访问的延迟差异。在实现上，这些锁机制会尝试将锁数据结构和相应的线程关联到同一个NUMA节点，以减少跨节点访问造成的性能损失。

题目描述

虽然现在 NUMA 感知的锁在锁内部的结构和设计上，已经充分考虑了 NUMA 架构的特性，但是如果存在较多的跨 NUMA 节点的对于锁的竞争，仍然会导致较差的性能表现。 现在，你接受了一个任务，通过修改内核调度器，避免大量的同步操作发生在跨 NUMA 节点的情况，进一步优化 NUMA 感知的锁的性能表现。

具体来说，你需要实现一个模拟的内核调度器，这个调度器能够接收一系列的操作，这些操作对应着当前系统的进程/线程的创建情况，它们的负载，以及它们和锁相关的语义。

在你实现的调度器中，进程可以包含一个或者多个线程，同一进程内的多线程共享页表和虚拟地址空间。

本题假设机器有2 个 NUMA 节点。

你的内核调度器需要支持以下内容：

1. 进程和线程管理

管理进程的创建和销毁（CREATE_Proc pid load、DESTROY_Thread tid）。 创建进程时会附带对应的负载值（load）和对应的进程ID（pid，测试保证pid始终为非0正整数）。

当创建一个新的进程时，该进程只有1个线程，线程ID（tid）即为进程ID（pid)，线程负载即为load（负载和线程绑定）。

删除时会传入对应的线程ID（tid），如果该线程对应的进程此时只有1个线程，则整个进程被删除；如果删除时线程所在进程包括多个线程，则只有该线程被销毁。

管理进程创建多线程的操作（CREATE_Thread pid tid load）：创建pid进程下对应的新线程，线程ID为tid。

该线程的负载为load。

如果当前不存在进程的ID为pid，则属于异常情况，该命令无效。

注意，pid 和 tid 共用一个ID空间。

即，对于 CREATE_Proc 命令，如果当前存在已创建进程 pid 或已创建线程 tid 的值与该命令所指定的pid冲突，则该操作属于异常情况。

在该调度器中，该命令将无效。

类似的，CREATE_Thread 也需要保证和现有的 pid 和 tid 不冲突。

题目第 5 部分对异常情况进行了具体描述。

2. 共享内存管理

系统中用基于共享内存的锁来实现跨线程、跨进程的同步。因此，调度器需要管理不同的进程间的共享内存关系（同一进程下的多个线程共享全部地址空间）。

需要处理共享内存创建、删除、映射、解除映射的 4 个操作。

首先，CREATE_Shm shm_key size，会创建一个共享内存ID为 shm_key（整型类型），长度为 size（需要大于 0）的共享内存区域。如果 shm_key 已经被使用，该次创建失败。

对应的，DESTROY_Shm shm_key 删除对应的共享内存，如果 shm_key 未使用（即没有shm_key 对应的共享内存资源），或者当前仍然有进程映射该共享内存，该操作失败，否则删除该共享内存，并且将对应的 shm_key 标记为未使用。

其次，MAP_Shm shm_key tid va size，在tid 对应的线程的进程的地址空间，将编号为shm_key 的共享内存区域映射到虚拟地址起始地址为 va，长度为 size 的区域。

如果两个不同的进程 P1 和 P2 的地址空间都完成了相同的映射，则他们可以通过读写自己本地对应的虚拟地址区域，来访问到同一个共享内存区域。 对应的，UNMAP_Shm tid va，将tid对应的起始地址为 va 的共享内存解除映射。 如果当前 va 所在的虚拟地址没有映射共享内存，或者不属于共享内存的起始地址（例如，va 对应一个共享内存的中间的地址），则该次 UNMAP_Shm 操作失败。

注意，为了简化调度器，不对共享内存以及映射操作的大小作对齐限制（例如，不需要考虑按照 4KB 粒度来映射页面）。

3. 锁竞争管理

调度器需要管理锁的竞争情况。

需要处理建锁操作（CREATE_Lock tid lock_addr），即 tid 线程，会在lock_addr的虚拟地址上对一把锁进行竞争。

如果对于另一个线程 tid2 在 lock_addr2 上拿锁，且两锁所对应的虚拟地址映射到同一个物理内存（即这两个地址经过了共享内存的映射）。

那么我们说 tid 和 tid2 在该位置对于同一把锁存在一个竞争关系。

注意，一把锁只占用 1 个字节的空间和对应的地址。

对应的锁删除的操作为 DESTROY_Lock tid lock_addr，即一个线程（对应 ID 为 tid）会删除掉其对该 lock_addr 虚拟地址的锁的竞争。

由于该调度器仅考虑基于共享内存的锁的情况，创建锁所使用的虚拟地址（lock_addr）必须为一段共享内存映射的地址，否则该次锁创建操作失败。

4. 调度

假设调度器的迁移进程/线程的能力非常强，能够实现瞬间的迁移。你的调度器需要支持一个关键命令（SCHEDULE_OPT）。此时，根据当前系统的状态，调度器需要对所有的线程、进程在CPU核心间进行重新调度。注意如下两个情况：

• （a）如果当前存在锁的竞争：如果两个线程 tid1 和 tid2 存在对同一把锁的竞争关系，那么当 tid1 和 tid2 在同一个 NUMA 节点时，竞争开销为 1，当在不同的 NUMA 节点时，竞争开销为 10. tid1 和 tid2 之间如果存在多把锁的竞争关系，则分别计算（例如，在同一个 NUMA 节点内部，且有 3 个锁的竞争，则开销为 3）。如果同一把锁存在大于 2 个的竞争者，例如存在tid1、tid2、tid3 竞争同一把锁，那么两两线程分别计算。例如 tid1 和 tid2 在 NUMA-1 节点上，tid3 在 NUMA-2 节点上，则全局的锁竞争开销为：tid1-tid2 竞争开销（1）+ tid1-tid3 竞争开销（10）+ tid2-tid3 竞争开销（10）=21。SCHEDULE_OPT 需要满足 2 个 NUMA 节点上都至少有 1 个线程在运行（全局至少会有 2 个线程），请设计该函数，使得全局锁竞争开销最小。
• （b）如果当前不存在锁的竞争：请输出 0。注意，如果当前创建了一个锁，但是该锁只有 1 个线程在使用，没有其他线程和其竞争，同样不算锁竞争的情况。

5. 异常处理

作为一个系统开发者，你需要对调度器的各种可能的异常情况进行考虑和处理。

除了上述的描述中的相关内容，系统的整体的异常处理包括：

• 对于系统中创建资源的命令（例如CREATE_Proc、CREATE_Thread 等），如果该操作和此前的操作所创建的状态冲突，那么该命令无效（跳过该命令，不在标准输出中输出错误信息）。例如，如果 1 个 CREATE_Proc 命令中的 pid 已经存在（和现有的 pid 和 tid 冲突），则该次命令直接跳过。类似的，如果 CREATE_Thread 中 tid 出现冲突，同样跳过命令。如果 1 个 MAP_Shm 命令中的 va 和 size 对应的区间，在该进程地址空间中已经被映射或者部分映射（存在交替区域），该次命令跳过。
• 对于系统中删除资源的命令（例如 DESTROY_Thread tid），如果命令对应的资源不存在（即tid线程不存在），该命令跳过。
• 对于线程销毁命令（DESTROY_Thread tid），在删除该线程时，需要对应地删除该线程所创建的所有的锁。如果删除该线程后，线程对应的进程还有其他线程，则该线程所执行的MAP_Shm的区域仍然保留。如果删除该线程后，进程内没有其他线程，则还需要对进程内所有的共享内存区域进行解映射（UNMAP_Shm）。
• 为了避免映射出错，系统内部需要维护共享内存的引用计算。当处理 DESTROY_Shm shm_key时，如果该区域仍然被映射在某个进程地址空间中（对应的区域没有执行 UNMAP_Shm），那么该删除操作失败（直接跳过）。这里，如果不支持这样的依赖维护的处理的话，很有可能程序会错误地删除一个共享内存，然后在之后对其使用，触发类似 use-after-free 的安全问题。
• 类似地，对于 UNMAP_Shm 命令，如果当前进程中的任一线程仍然有锁是基于该命令的地址区域，则该次 UNMAP_Shm 操作失败（直接跳过）。

输入格式

从标准输入读入数据。

输入的第一行包含 1 个正整数 $n$，保证 $n \le 2000$。

随后包括 $n$ 行，每一行为一个具体的命令（包括 1 个字符串的命令名和 0 个或若干个参数），如下（具体的功能在上面题干中已有描述）：

• CREATE_Proc pid load
• CREATE_Thread pid tid load
• DESTROY_Thread tid
• CREATE_Shm shm_key size
• DESTROY_Shm shm_key
• MAP_Shm shm_key tid va size
• UNMAP_Shm tid va
• CREATE_Lock tid lock_addr
• DESTROY_Lock tid lock_addr
• SCHEDULE_OPT

上述参数中，除了地址（即，va、lock_addr）是 64 位非负整型，其余均为 int 类型。

输出格式

输出到标准输出。

针对所有的 SCHEDULE_OPT 命令，打印 2 部分内容。

首先，分别打印出当前所有的线程信息，每行一个线程，顺序以 PID 从低到高，在同一进程内部，按照 TID 从低到高输出。

每行的内容为：Process (PID): pid Thread(Tid): tid Load: load

其中，pid、tid 和 load 需要替换为线程所属进程的PID，线程的TID，以及其负载值。

其次，需要打印出当前调度策略下的全局锁竞争开销，例如：

Contention Cost: 0

注意，输出要以 1 个回车为结尾（'\n'）。

具体的输出格式，请参考样例输出。

14
CREATE_Proc 1 20
CREATE_Proc 2 30
CREATE_Thread 1 3 20
SCHEDULE_OPT
CREATE_Shm 100 4096
MAP_Shm 100 1 4096 4096
MAP_Shm 100 2 8192 4096
CREATE_Lock 1 4096
CREATE_Lock 2 8200
CREATE_Lock 2 8192
CREATE_Lock 3 4100
CREATE_Lock 2 8196
CREATE_Lock 3 4104
SCHEDULE_OPT

Process (PID): 1 Thread(Tid): 1 Load: 20
Process (PID): 1 Thread(Tid): 3 Load: 20
Process (PID): 2 Thread(Tid): 2 Load: 30
Contention Cost: 0
Process (PID): 1 Thread(Tid): 1 Load: 20
Process (PID): 1 Thread(Tid): 3 Load: 20
Process (PID): 2 Thread(Tid): 2 Load: 30
Contention Cost: 12

样例 1 解释

在样例 1 中，对于第一个 SCHEDULE_OPT 命令，此时没有锁的创建操作，因此考虑（b）的情况，直接输出当前的线程信息，并且锁竞争开销为 0。

对于第二个 SCHEDULE_OPT 命令，此时线程 1 和线程 2 之间有 1 个锁的竞争关系，线程 2 和线程 3 之间有 2 个锁的竞争关系。

此时，将线程 1 放在 NUMA 节点 1 的核心上、线程 2、3 放在 NUMA 节点 2 的核心上，此时锁的竞争情况为（$10+1+1$），为最优情况。此时的输出为 $12$。

5
CREATE_Proc 1 20
CREATE_Proc 2 30
SCHEDULE_OPT
DESTROY_Thread 1
SCHEDULE_OPT

Process (PID): 1 Thread(Tid): 1 Load: 20
Process (PID): 2 Thread(Tid): 2 Load: 30
Contention Cost: 0
Process (PID): 2 Thread(Tid): 2 Load: 30
Contention Cost: 0

17
CREATE_Proc 1 20
CREATE_Proc 2 30
CREATE_Thread 1 3 20
CREATE_Shm 100 4096
MAP_Shm 100 1 4096 4096
MAP_Shm 100 2 8192 4096
CREATE_Lock 1 4096
CREATE_Lock 2 8200
CREATE_Lock 2 8192
CREATE_Lock 3 4100
CREATE_Lock 2 8196
CREATE_Lock 3 4104
SCHEDULE_OPT
DESTROY_Lock 3 4104
SCHEDULE_OPT
CREATE_Lock 1 4100
SCHEDULE_OPT

Process (PID): 1 Thread(Tid): 1 Load: 20
Process (PID): 1 Thread(Tid): 3 Load: 20
Process (PID): 2 Thread(Tid): 2 Load: 30
Contention Cost: 12
Process (PID): 1 Thread(Tid): 1 Load: 20
Process (PID): 1 Thread(Tid): 3 Load: 20
Process (PID): 2 Thread(Tid): 2 Load: 30
Contention Cost: 11
Process (PID): 1 Thread(Tid): 1 Load: 20
Process (PID): 1 Thread(Tid): 3 Load: 20
Process (PID): 2 Thread(Tid): 2 Load: 30
Contention Cost: 22

子任务

对于所有数据，保证 $n\le 2000$，当存在锁竞争且要计算锁竞争开销时，参与竞争的线程总数不超过 $30$。

测试点编号	命令数	竞争线程数	测试描述
1	$\le 2000$	$0$	单线程进程管理和调度操作
2			多线程进程管理和调度操作
3	$\le 500$	$\le 30$	全部操作包括异常处理