Skip to content

并发分离逻辑中的所有权转移

Ownership transfer in concurrent separation logic · CSL ownership transfer

让锁、消息或线程边界在不复制资源的前提下移动逻辑所有权,使接收方取得访问能力而发送方同步失去它。

条目类型
方法

形式陈述

并发分离逻辑 中,传递一个地址值与传递该地址指向资源的访问权是两件事。设消息谓词 M(v) 描述随值 v 移动的资源。一个可靠、恰好交付一次的通道可提供形如

{PM(v)} send(c,v) {P},{Q} x:=recv(c) {QM(x)}

的规格。发送原子地从线程局部状态移走 M(v);消息尚在缓冲区时由通道协议拥有它;匹配接收再把同一资源交给接收方。资源没有复制,发送者后置中也不再含 M(v)

把所有线程与通道的逻辑资源看成一个可组合总量,成功发送只改变 M(v) 所在的组件,不改变总量;成功接收再做相反移动。若 send 失败且接口承诺“未接纳”,后置应把 M(v) 还给发送者;若返回成功,则不能同时让发送者和缓冲区都持有它。这个守恒条件是为每种错误返回设计规格的基准。

锁取得与释放是另一种转移。锁空闲时持有资源不变式描述的片段,acquire 把它交给线程,release 要求线程重新建立并归还。线程创建也可把一部分前置资源交给新线程,join 时再收回其后置资源。每种原语必须由自己的并发语义说明转移发生在哪个事件以及失败操作是否移动资源。

直觉

发送裸指针像告诉别人仓库地址;所有权转移还要把钥匙交出去,并从自己的钥匙串上取下。接收者得到钥匙后可以按权限读写或释放,发送者即使仍记得地址,也不能再合法开门。逻辑通过前后条件中的资源消失和出现记录这笔交接。

转移比永久共享更容易保持局部性:任一时刻资源只有一个完整所有者,不需要每次访问都重新分析竞争。若只转移一个分数份额,双方可以共享读取,但任何一方都没有写或释放的完整权力;资源谓词精确说明交出去的是多少能力。

例子与边界

发送线程分配一个单元并得到 42,定义

M(p)p42.

调用 send(c,ℓ) 前,它拥有 P(42);调用后只剩 P,因此随后执行 [ℓ]:=0 无法满足写前置。接收线程执行 p:=recv(c) 后取得 p42,可以读出 42,再以完整所有权执行 free(p)。从分配到释放,资源依次由发送者、通道、接收者拥有,账本中从未同时出现两份完整 points-to。

若通道可能重复投递,同一个 M(v) 会被两个接收者取得,规则不再可靠;若消息丢失,资源可能永久留在通道中,影响泄漏和终止性质。广播需要可复制的纯事实或预先拆分的只读份额,不能广播线性写权限。超时与取消还要规定尚未交付的资源退还发送者、留在队列还是转入清理线程。

地址序列化到另一进程也不自动搬运本地堆所有权;跨地址空间消息通常传数据副本、共享内存句柄或协议 token,各有不同资源模型。内存回收中的 ABA、hazard pointer 和 epoch 同时依赖时间与读者存活信息,不能只用一次 send/receive 转移概括。

异步缓冲区还区分“send 已返回”与“receiver 已取得”。两事件之间资源属于通道内部队列,因此队列表示不变式必须把每个待收消息的 M(v) 一并保存。只在发送者和接收者端各写一个三元组、却让缓冲区摘要遗漏资源,会在这段时间造成逻辑资源凭空消失;接收方后来也就不能有根据地取得所有权。

推论与应用

所有权转移为流水线、actor 邮箱、工作窃取队列和生产者—消费者协议提供模块化规格。每个阶段只验证自己持有对象期间的局部操作,消息谓词则承担阶段之间的数据结构表示关系。通道实现若被证明满足消息资源协议,客户端无需展开其锁和缓冲区。

同一思想还能表达 API 生命周期:打开文件返回句柄 token,close 消耗 token;线程 spawn 消耗子任务前置,join 产生其后置。资源守恒能排除 double free 和 use-after-transfer,但不保证消息最终到达或接收者最终释放,后两者属于可靠传输与活性规格。

对于带选择接收或超时的 API,最清楚的规格往往给每个返回分支不同资源后置:收到值时产生 M(v),超时时保持原有 Q,取消成功时说明缓冲中的资源由谁回收。把所有分支写成同一个模糊后置,会丢失所有权究竟停在哪里的关键信息。

参考资料
  • Peter W. O’Hearn, “Resources, Concurrency and Local Reasoning,” Theoretical Computer Science 375(1–3), 2007, pp. 271–307。
  • Stephen Brookes, “A Semantics for Concurrent Separation Logic,” Theoretical Computer Science 375(1–3), 2007, pp. 227–270。
  • Jules Villard, Étienne Lozes, and Cristiano Calcagno, “Tracking Heaps That Hop with Heap-Hop,” TACAS, 2010, pp. 275–279。
  • Alexey Gotsman et al., “Local Reasoning for Storable Locks and Threads,” APLAS, 2007, pp. 19–37。
关系图谱6 个相邻概念 · 1 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组