01 · 竞态与临界区:一份共享财产,三路对手,一把门闩
3.6 收卷的时候,柜前留的话咱们接下:两把锁各押各的,次序归谁管的官司,咱们这第 4 部的头一章来接手。今天咱们把大门推开,给您交个底:次序那一问,得等两把锁都站稳了才轮得到开口,其实在它底下还压着一问,锁凭什么看得住东西。所以头一章从最底下那层办起,共享的财产为什么会坏,毛病又出在谁的手里,拿什么看住。
现象咱们摆上桌。咱们的机器是单核,执行流却不止一条:您看,轮流上 CPU 的是两位任务,随时进门的是时钟中断,就绪队列、堆的空闲链、名册的位图,全是共用的财产。一个任务把堆的空闲链拆到一半,时间片到了,换上来的另一个任务也去要内存,它看见的是一条断到一半的链。单线程的年代这不算事,拆到一半的中间态轮不到别人看,现在轮得到了。2.4 交过底:堆和名册是不设防的,抢占的总开关因此默认关着,排期的事就这么摆着,等第 4 部的锁家什。咱们等到今天,货到了。
这一章的活,咱们数下来三样。头一样是认对手:弄坏财产的不止换上来的人,三路对手咱们一路配一案。再一样是认门闩:自旋锁的真身、四层心思,外带一本登记簿和一条持锁不许睡的家法。末一样是记两桩案子:编译器删掉等待循环的案中案,一次缺页换来的零构造家规。
量法还是老样子的三条。码的话,咱们的主角有两件:kernel/proc/sync.hpp 有 261 行的身子,锁家三件的户口全在里头立着,另一件 sync.cpp 的 120 行里,住着的全是活动的部件。配角的家安在 arch 里头:SaveAndDisableIrq 与 RestoreIrq 这一对真身,您去 irq_guard.hpp 里找,CpuRelax 的那声 pause 住在 instructions.hpp。客串一场的是 scheduler.cpp,睡觉门前那道岗哨是它的戏。屏的话,实况锚用的还是 r12_process,2.4 那一趟用的就是它:面板与起机命令那边抄全了,咱们不重印,本章回头重看的是小铺子那一场,就是 2.4 印的第三场,演的就是生产与消费,正文《轮流当家》那一卷给它起的名字就是小铺子,再把长凳的 test_sync 四案头一回请进教科书层。书的话,xv6 这回翻到的是第 7 章,书页 63、65、66、70、71 这五页是逐字核过的。CSAPP 2e 翻到的是 12.5 节,badcnt 计数案整段摘进了对照节,咱们按电子版核的正文页是 992 到 995,印本的页码随版式走,您认节名就好。原话咱们一律整句摘,您对着书核。
一把门闩的家当,咱们数下来只有四格成员,凭什么看得住堆的空闲链、就绪的队列?
凭头注自己报的家底。咱们看 sync.hpp 开篇的第一句,
The lock family: one spin, two sleeps,说的就是锁家三件:一件是自旋的,两件是睡觉的。自旋锁的定位,头注写的是Spinlock is the fast lane,咱们译的就是快车道:进门关中断,配的是一记 test_and_set 与一声 pause,睡觉的两件全骑在它背上。纪律其实也报在明处,a spinlock records its holder, unlock verifies the same hand lets go, lock refuses re-entry on one core,咱们挨句对:头一句记的是持有者,第二句放锁验的是手,第三句说的是单核拒重入,底下其实还压着半句狠话,and sleeping with a spinlock held stops the machine loudly instead of deadlocking it quietly,说的就是带着门闩上床:机器响亮地停,不悄悄地挂。四格成员怎么把这四句一句句兑现,正文里咱们对。
对手:换上来的人,进门的中断,看不见的编译器
头一路的对手是换上来的人,案发现场就是开头的断链。您别嫌它朴素,2.4 第二场拉练里的两位主角 spin_a 与 spin_b,留下的就是六行交错,一声 yield 都没喊:交错的权力不在任务手里,握它的是时钟。按两拍一片的尺,片是一路跑到出口的,谁在改共享的财产,被请下场的就是谁,改了一半的东西原样留在内存里,等的是下一位来接手。执行流走的这一路,其实是连恶意都谈不上的:谁也没写错一行,坏掉的只是它们动手的时机凑到了一起。
第二路是进门的中断。它比换上来的人更横:换人好歹要等时间片,中断是说来就来的,您改到一半它就到了。更麻烦的是,就算您想立一把旗把门看住,它也不怕:您拿着旗改链表,改到一半的时候时钟中断进来了,服务程序要碰的也是同一条链表,它要的也是这把旗。可咱们的机器是单核的,持旗的人正悬在中断里出不来,放旗的代码排在它身后,永远轮不到执行的那一步,机器当场就死机了,连转圈的机会都不给。中断这一路教咱们的是:光立旗不够,咱们连中断也得一起防。
第三路的对手最不着痕迹:编译器。第二条执行流它是不要的,中断也是不要的,一个人就能把您的代码改掉:整段循环说删就删,读写的次序说换就换,全在它的职权之内。它其实是没恶意的,它只是按与您签下的约定办事,问题是内存与 C++ 的约定里,压根没有中断与别的执行流的位置。这一路的正戏是一桩完整的案子,咱们留到中段再办,眼下的词得立起来,对手还没名号的话,官司就没法打了。
认词:竞态,临界区
三路对手都认齐了,咱们给病起名。xv6 书页 65 写了一句定义,咱们原句摘来:
- “A race is a situation in which a memory location is accessed concurrently, and at least one access is a write.”
直译过来的话:同一处内存被同时访问,写的至少有一方,这样的局面就叫竞态。竞这个字取的就是赛跑的竞,几条执行流摸的是同一处财产,结局押在谁的手落在谁后头,咱们谁也说不准。xv6 同页把最常见的一种病也点了名,点的就是 lost update,丢更新:两方读的是同一个旧值,各改各的,各写各的,后写的盖掉早写的,一次更新凭空没了。开头的断链是它的亲戚,断链丢的是链的形状,丢更新丢的是数,在竞态的名下,它们其实是一家。
临界区这个词咱们接着认,说的是另一头,被看护起来的那一段。xv6 书页 66 的原话:
- “The sequence of instructions between acquire and release is often called a critical section.”
拿锁到放锁之间的指令序列,行话里叫的就是临界区。您回头看开头的断链:拆空闲链的那几条指令,就住在临界区的里头,毛病出在了当年,咱们还没给它划界。词立齐了:竞态说的是病局,临界区圈的是要守的那段路。至于两把锁谁该走在谁的前头,归《死锁与锁序》那一章的官司,咱们不抢着办。
谱系:三条路,单核的年代
解法的谱系,单核的世界里数下来三条,咱们一条条看。头一条是把中断关了,屋里就没人能进来了:换人要经的时钟中断进不来,中断自己也进不来了,一闸落了下去,头两路的对手同时清了场。干这活的家什名叫 IrqGuard,名字咱们今天头一回叫响,活本身 2.4 是认过的,当时咱们叫它关中断的守卫:进门存旗,出门的时候按快照还原。另一条是原地转圈,旗还攥在别人的手里,您不睡,您就站在门口一遍一遍再问,问到了进门。自旋这个词咱们头一回用,配的白话就是它:拿不到锁不睡,原地一圈一圈地问,人是一直醒着的。末一条的路数是干脆睡觉,把 CPU 让给了别人,等的是别人来叫醒,这是互斥锁与信号量两件家什的活法。
三条路对应的是三件家什配三种仗。关中断的那件最重也最快,一上身短仗立刻清了场,可全屋清场只能护几条指令的路段,堆与名册的每个入口,后来穿的就是它,护甲是它的行话。护甲上了身之后,抢占的总开关才敢常开,2.4 交底时押下的正是这半句。可 2.4 说的锁家什是泛称,堆与名册后来穿的其实是护甲,还称不上锁的名分。短一些的临界区配门闩,它自带的是关中断,带的还有名册与验手,下一节咱们全看。等得久的活,等一件还没生产出来的货,转圈烧的就是电,睡觉才是对路的,那一路的正戏归《条件等待》,本章立的就是名。3.6 柜前露过半张脸的家什,const proc::MutexGuard kGate(gate_),今天咱们把名字补齐:Mutex 是睡觉那路的家什,柜子的槽表就是它押的。
门闩:四层心思,一进一出
正主这就出场了。拿锁的身子,sync.cpp 的 :19 到 :29,咱们整段摆出来:
void Spinlock::lock() {
cinux::base::safety::Check(!held_.test(std::memory_order_relaxed),
"spinlock re-entered on one core");
irq_state_ = cinux::arch::SaveAndDisableIrq();
while (held_.test_and_set(std::memory_order_acquire)) {
cinux::arch::CpuRelax();
}
SpinLedger& ledger = ledger_ != nullptr ? *ledger_ : DefaultSpinLedger();
ledger.note_acquire();
holder_ = Scheduler::self().current();
}这十行里叠着的是四层心思,咱们一层层揭。进门那声 Check 把的是头一层:同一个任务、同一把锁,拿了两回,当场就叫了。为什么拦得这么凶,您想,单核上转圈等的旗攥在自己手里,这样的等待永远没有结果,等出来的只能是死局,而且死的时候一点声息都没有,与其那么挂着,不如响亮地叫,总比挂了强一万倍。第二层是 SaveAndDisableIrq 的那一行,自旋锁在内核里的看家本分,持有期里关的是中断。上一节中断那路对手的死机论证,在这里兑现成了家法:旗在手里,闸也落下了,中断也进不来了,悬在旗里的死局从根上没了。进门存的是旗,出门按的是快照还原,正是 IrqGuard 的纪律穿在锁的身上。第三层是转圈里的那声 CpuRelax,本体是一条名为 pause 的指令,住在 arch 的 instructions.hpp:告诉流水线我在等,劝它从容地往前走,省的是电,也顺手给同核心的兄弟执行流让点喘息。这类对 C++ 毫无意义、对 CPU 一字千金的指令,往后都归回这样的家,不再散落成裸汇编的样子。
第四层轮到转圈的机关,说的就是 test_and_set。白话咱们配给它:把旗改成已占,同时把改之前的样子报给您。改之前是空的,您拿到了,进了门。改之前是占的,说明有人走在您前头,您就转圈再试。这一下既改又报:改与报捆在不可分的一拍里,谁的脚也插不进来。拿锁配的 acquire,放锁配的 release,咱们把这对顺序的白话一次配齐:release 是放行前的承诺,我临界区里的所有写入,在放锁之前就统统落定了,后拿锁的人一定看得见。acquire 是进门时的要求,我拿锁之后的读取,一定读得到上一任留下的一切。一放一拿的工夫,两条执行流之间架起的是一条传话管道,共享的不只是旗,还有旗护着的数据。这对顺序背后还有什么讲究,缓存、重排、屏障那一类的讲究,留给了第 4 部末一章《内存序与缓存一致性》专门讲,本章咱们认下这对白话就够用了。
放锁的半边不该只活在散文里。unlock 的真身,sync.cpp 的 :31 到 :39,您拿它对着 lock 读:
void Spinlock::unlock() {
cinux::base::safety::Check(holder_ == Scheduler::self().current(),
"spinlock released by a non-holder");
holder_ = nullptr;
SpinLedger& ledger = ledger_ != nullptr ? *ledger_ : DefaultSpinLedger();
ledger.note_release();
held_.clear(std::memory_order_release);
cinux::arch::RestoreIrq(irq_state_);
}头一行验的是身份:放这把锁的手,必须跟 holder_ 里记着的一致,别人的手伸过来,门闩当场就叫了。放别人锁的手,十有八九是写错了作用域,响了正好。接着 holder_ 清了空,登记簿减的是一层,note_release 对的正是 lock 里的 note_acquire,一加一减的两笔,正好凑成了一对。真正承重的是倒数第二行,held_.clear(std::memory_order_release),放锁配的是 release,落的正是它。末一行按快照还旗:RestoreIrq 吃的快照,是 lock 里 SaveAndDisableIrq 存下的,进门时中断什么样,出门就还原成什么样。您看这一进一出,跟 IrqGuard 走的是同一门纪律,只是守卫在这里揉进了锁自己的身子。
登记簿:数着层数,拦着睡觉
锁上的家当之外,咱们还置了一件小家具:登记簿。它的大名叫 SpinLedger,数着这个核上活着的自旋锁有几层:拿锁的时候记一笔 note_acquire,放锁的时候减一笔 note_release,报数的是 depth(),零说的就是一层没有。公共的那本由 DefaultSpinLedger 发,它本身就是 constinit 的,落在 sync.cpp 的 :13,出生的时候是全零,数出来的也正好是零。锁还留了自带私册的路,构造的时候递一本进去,不递就挂公共的,长凳上的测试世界各挂各的,谁也不干扰调度器的查。
查什么?查睡觉。持着门闩的人,是不许去睡的。道理您想一遍就通:睡眠是把 CPU 让给别人,可拿着门闩的您,是全机唯一能放这把锁的人,您睡了,等您的人就在门口一圈一圈转下去,您一天不醒,它就一天不停地转。执法现场在 scheduler.cpp 的 :107 到 :113:
void Scheduler::block_current() {
const cinux::arch::IrqGuard kGuard;
cinux::base::safety::Check(current_ != nullptr, "block called outside any task");
cinux::base::safety::Check(DefaultSpinLedger().depth() == 0,
"task parked while holding a spinlock");
park_current();
}block_current 是睡觉的头一关,进门头一件事查的就是登记簿:深度不是零,说明的就是还有人揣着门闩,Check 当场就叫了。响亮地叫,总比挂了强一万倍,家法在门闩那边是立过一遍的,这里又立了一遍。开篇头注报的四句,到这儿一句句都对上了。one spin, two sleeps,谱系节里是见过的。fast lane 的分量,门闩那四层心思扛的就是它。记持有者、放锁验手、单核拒重入的几句,门闩节里都兑现了。带着门闩上床的那一句,机器响亮地停,落的正是眼前这道岗。睡觉本身的正戏,摘下、挂队、叫醒的三步,归的是《条件等待》,咱们到此收手。
您停一停,咱们把登记簿撤走,您推一推:带着门闩上床的病,会以什么样子发作?
咱们把死法走一遍。睡觉的人揣着门闩下了床,等锁的人转着圈,转圈的时候中断是关着的,它连让位的路都没有,只能一圈一圈地转下去。机器是不崩的,屏上是没有字的,日志也是一行不多的,一切看着都是正常的,只是永远这样了。无声的死法比崩溃难查得多,2.4 那句宁可响亮地死,不许悄悄地丢,说的是就绪队列的入队,这里说的是睡觉的门,说的是同一门家风,设的是两处岗哨。登记簿的深度,就是把这场无声的僵持换成一声警报的机关。
案中案:被删掉的等待循环
门闩立好了,咱们回头办那桩案子,第三路对手的正戏。案由说起来小:内核里的十个单例类,每一个都手写着同样的五行 self(),咱们想把它们收进 base 一件 Singleton 模板,继承一下就完事了。咱们把它当纯重构办:不改一行逻辑,长凳那头是全数通过的,机器上的测试却坏了,中断链出了异常,好几台测试内核一启动就退出了。代码是一个字没改的,只是搬了个家,病从哪儿来?
当年的三处误诊,咱们原样摆出来,它们的教学价值比真因还大。头一处咱们看着符号表,断言三个单例的实例地址互相重叠,怪链接器把对象折到了一处。证伪得很干脆:两个起点是紧挨着的,而其中一个类压根没有数据成员,间距是完全正常的。比较两个对象是否重叠:得拿各自的起点加尺寸算区间,咱们拿两个起点直接比,比法就是错的。第二处咱们看模拟日志,发现 IRQ0 只注入了一次,断定是中断应答丢了、时钟停摆。因果整个是反的:循环被删之后测试迅速失败退出,机器只活了一小会儿,日志里当然只有一次注入,一次注入是死亡的结果,真正的死因还在前头。第三处是最值得记的,咱们在 gdb 里单步走完了整个中断处理,iretq 是正常的,时序是毫无问题的。可单步的模式和自由运行是两个世界,单步的时候调试器默认替咱们关着中断、掐着时钟,这样的单步走得通,证明不了自由运行时的任何事。三条记进册子:取证的手艺不过关,下得越自信的判断越危险。
真因出在等待循环的身上。机内测试里有这样的段落:记下当前拍数,原地循环,等拍数涨过了目标再往下走。循环一圈一圈地转,每一圈都要读一次名叫 ticks_ 的普通整数。咱们手写的 self() 住在独立的编译单元里,等待循环调用它是一次跨单元的外部调用,编译器是看不穿的,只好每一圈老老实实地重新读。收进了 base 模板之后,self() 是头文件里的内联,调用没了,编译器眼前只剩一个铁的事实,在这个循环的里头,一行写 ticks_ 的代码都没有。一个没人写的变量,读一万次读到的也是同一个值,按 C++ 的标准,这样的循环整个儿是可以删除的死代码。于是等待循环就这么消失了,测试瞬间就失败了。
您别急,ticks_ 是明明有人写的。写它的是中断服务程序,每个时钟中断的当口写一次,面板上的 irq on, tick 100Hz 那一行,报的就是它的节拍。偏偏这件事,内存与编译器的约定里没有中断的位置:编译器看得见的写,只有这个翻译单元里、这个执行流里的写。旧代码能跑:靠的是外部调用碰巧挡在编译器和循环中间,挡得住的事纯属运气,到了内联一开的时候,运气也就用完了。
修法在原理里写好了:把有人异步写这件事,明明白白地表达给编译器,表达的语言是原子。今天的真身落在 kernel/time/tick.hpp 的 :98,ticks_.fetch_add(1, std::memory_order_relaxed),读的那一边 :108 走的是 load。原子这个词咱们配句白话:一次原子读或写是不可分割的,编译器和硬件都不许把它缓存、合并、重排到别的执行流看不见,它就是跨执行流共享变量的语言。顺序选的 relaxed,最松的一档,只保证这一次操作本身的不可分,不额外承诺它前后的读写次序,单纯数拍子是够用的。您要是想问 volatile 行不行,答案是不行的,口径是笔者讲过的原话:volatile 管的是每次都真读,读改写的不可分它管不了,跨执行流的次序它也管不了,而数拍子要的恰是这两样。旁边的 :114 还立着一枚静态断言 is_always_lock_free,咱们这套原子在咱们机器上真的不靠锁,这句话在编译期白纸黑字地断了下来。
案子结了,顺手清了一笔旁债:内核入口那几行在 C++ 函数里改 rsp 的汇编,一直违反着编译器对内联汇编前后栈指针一致的约定,这一次把入口整个搬进独立的 entry.S,汇编里设好了栈再 call 进 C++,两边就两清了。卷宗收在正文《轮流当家》的那一卷,咱们记一句就走。
学费:一次缺页,一条家规
末一桩案子是用一次缺页换的。锁家族造好的头一天,生产者消费的演示首跑,机器直接缺页崩了,崩的位置匪夷所思,偏偏是登记簿自增的那一行。咱们顺着崩溃地址回去看,看到的东西起初没法理解:那个全局锁对象,躺在 .bss 里的字节全零,咱们给它的构造函数,一个字节的代码都没执行过。对啊,这就是咱们从内核出生那天起的世界的样子,全局构造是没有的,没有任何静态对象的初始化代码会跑。
咱们一边立着零构造的纪律,一边顺手写了带构造参数、带引用成员的锁。要绑定的引用,要设初值的计数,全是要跑代码的事,而那段代码永远不会跑。悬空的引用,没落的初值,一个看似无害的自增踩上去,落下的就是缺页。修法三件:锁对登记簿的引用改成可空指针,空了自动挂公共那本。信号量补上了默认构造,起步是全零的,计数的值是零,等待队列是空的,这是一个完全合法的语义,货还没补的当口,等货的人自然要排队。至于开场要发的存货,发的活归用例自己。三件都修完了,一条家规也就落定了,与单例的 constinit 是同一条:静态寿命的对象,全零字节必须是合法的默认态,凡是需要跑代码才能变得合法的设计,在这个世界里都是错的。
您停一停,家规为什么落在全零必须合法上,而不是干脆下令不许再造全局的锁?您拿小铺子那座货架推一推:把它的锁改成堆里 new 出来的,走得通吗?
是走不通的,咱们一圈就绕回来了。new 走的是堆,堆的头几件共享财产,空闲链、块头块尾的几样,自己就是等着被看护的对象,看堆的锁必须生在堆开张之前。开张之前全世界能放对象的地方只剩静态存储一处,而静态存储在这个世界里出生时一律全零。所以家规落到实处是一道出厂的关卡:凡是全局物件,都得能从全零里合法地醒来。今天小铺子柜台上的门闩、空位与货,全都是从零起步的,全是家规的活证。
Code: Cinux 实况:同一场戏,换一双眼睛
实况锚用的还是 r12_process,与 2.4 走的是同一趟。起机三步、面板十行、三场拉练的排场,2.4 全读过了,咱们不重印,换一双眼睛重看的是第三场。2.4 看的是调度的戏,谁让了位,谁接了手,今天咱们看的是柜台。小铺子那一场的全段十二行,咱们整段摆出来:
[task] tid=5 produced item 1
[task] tid=5 produced item 2
[task] tid=5 produced item 3
[task] tid=5 produced item 4
[task] tid=6 consumed item 1
[task] tid=6 consumed item 2
[task] tid=6 consumed item 3
[task] tid=6 consumed item 4
[task] tid=5 produced item 5
[task] tid=5 produced item 6
[task] tid=6 consumed item 5
[task] tid=6 consumed item 6咱们挨行读。生产者 tid 5 一口气产了四件,消费者 tid 6 才上的手,产到第五件的时候空位一枚不剩,wait 把生产者撂下去睡了,消费者逐件地取,每取一件还的是一枚空位,取完了四件生产者醒来接着产,末了产二消二收场。2.4 那边只看了睡觉与叫醒,今天咱们把柜台认全:货架的门是一道 Mutex,进货出货都打它的门过,押货架那几行的是 MutexGuard,3.6 柜前露过半张脸的就是它。空位与货用的是两枚信号量,取货靠的是 wait,到货靠的是 post,空位开场发的是四枚,发存货的活归用例自己,家规在这里兑现了。锁家的三件,一场戏全上了场,而且全用对了。还有一层您得知道:今天这场跑得顺,当年首跑崩的就是它,学费案的现场正是这里,家规修完了,才有您眼前这十二行。
长凳的那件,您自己跑:
cmake -B build-dbg
cmake --build build-dbg --target test_sync
build-dbg/test/test_sync屏咱们原样抄:
=== Cinux Test Runner ===
Running 4 case(s)...
[PASS] sync: spinlock counts holders and names them
[PASS] sync: nested spinlocks unwind their count
[PASS] sync: uncontended mutex lock and unlock round-trips
[PASS] sync: semaphore counts units and never parks while stocked
=== Results: 4 passed, 0 failed ===四案咱们挨个认。头一案是持有者的计数与报号,验的是 holder_ 记名与登记簿的一加一减。第二案是嵌套锁的层数回卷,两层门闩套着拿的样子,深度从二退回了零,登记簿数的正是它。第三案是无争用的互斥锁一进一出,门闩套门闩的里层结构,下一章咱们细看。第四案是有存货的信号量不停车,计数大于零的话,wait 直接地过,队伍是一眼都不看的。长凳上跑的为什么是真家伙:开发机上 SaveAndDisableIrq 换了一份不碰真旗的实现,链接的时候挑走哪份,机器上挑的是 pushfq 与 cli 那一对,长凳上挑的是这个桩,跑的都是同一份 sync.cpp。2.4 给调度器装的假 sink,走的正是同一门手艺。
对照:同一件事,别的机器怎么做
xv6 的锁章开篇在书页 63,把交错的三条来路一次数齐了,原话咱们摘来:
- “The word concurrency refers to situations in which multiple instruction streams are interleaved, due to multiprocessor parallelism, thread switching, or interrupts.”
说的是多处理器、线程切换、中断这三样。咱们的对手名单跟它对一对:线程切换与中断,两路是同名同姓的。多处理器的那一栏,单核的机器眼下空着。编译器的那一栏,它家的名单上没有,可书页 71 它自己认了,它的原话是 “compilers emit load and store instructions in orders different from those implied by the source code, and may entirely omit them (for example by caching data in registers)”,说的是乱序,甚至整个儿地省略。括号里给的例子是把值缓存进寄存器,正是咱们那桩删循环案里被删的循环踩的机关。
书页 63 还有 kalloc 的一例,与章首的那段引文在同一页,咱们一看,它跟开头的断链同根异代:
- “two CPUs could simultaneously call kalloc, thereby concurrently popping from the head of the free list”
两颗 CPU 同时调了 kalloc,同时从空闲链的头往上弹。它家是两颗核的真并发,咱们是单核上换人看见断链,对手是不一样的,坏的是同一条链。书页 65 的那句竞态定义,认词的时候咱们引过了,同页还有半句值得记:竞态的结局押在编译器产出的机器码、两方的时机与内存系统的次序上,这会让竞态犯下的错难以复现、难以调试,再加一行打印的话,可能就把时机改得足够多了,病就躲了。查过竞态的人,对这半句都是有体会的。
咱们再给临界区拍一张正面照,请的是书页 66:
- “You can think of a lock as serializing concurrent critical sections so that they run one at a time, and thus preserve invariants”
锁把并发的临界区排成一队,一次跑的是一段,保住的是不变量。同页的上一句说得更直白,咱们原样摆一行:
- “When we say that a lock protects data, we really mean the lock protects some collection of invariants that apply to the data.”
锁护的是数据身上的不变量。这一层的意思,正文里是没明说过的,咱们今天补上:空闲链的不变量,是链头永远指着一条完整的链,拆到一半的那几拍,许诺是暂时不成立的,门闩保的就是没人趁着窗口来看。
重入的立场,咱们翻到书页 70:
- “Xv6 takes this latter view, and forbids a CPU that currently holds a lock from re-acquiring it. Detecting this situation is the purpose of the call to holding in acquire.”
重入该允许还是该禁止的问题,书上摆了两派,xv6 站禁的那派,拿 holding 做的检测。咱们的门闩同站:lock 进门那声 Check,拦的就是同一件事,而且咱们拦得更响,断言当场就叫了。
跟咱们贴得最紧的一处在书页 71,它家的嵌套计数:
- “acquire calls push_off (1355) and release calls pop_off (1369) to track the nesting level of locks on the current CPU. When that count reaches zero, pop_off restores the interrupt enable state that existed at the start of the outermost critical section.”
数的是嵌套层数,数到了零,还原的是最外层进门时的中断状态。咱们自己的登记簿,数的正是层数,按快照还的旗,走的是同一门纪律,两家的写法像得很。同页还有一句次序的警句:
- “It is important that acquire call push_off strictly before setting lk->locked (1277). If the two were reversed, there would be a brief window when the lock was held with interrupts enabled, and an unfortunately timed interrupt would deadlock the system.”
关中断必须排在立旗的前头,反过来的话,有那么一小窗,旗是立着的,闸是开着的,一个掐得准的中断进来,系统就死锁了。咱们 lock() 里 Check、SaveAndDisableIrq、test_and_set 三步的次序,生死攸关的正是中间那两步,练一练的题二咱们亲手排一遍。
CSAPP 的那一头,咱们翻到 12.5 节,看的是 badcnt 一案。两个线程各往同一个计数器上加了一百万次,期望的答案是二百万,书页 992 实跑是这样的:
linux> ./badcnt 1000000
BOOM! cnt=1445085
linux> ./badcnt 1000000
BOOM! cnt=1915220
linux> ./badcnt 1000000
BOOM! cnt=1404746它家自己的话,咱们原样摘,“we not only get wrong answers, we get different answers each time!”,不光是错的,每回错的还都不一样。病根它家在书页 994 拿汇编摆开了:计数那一行在机器码里是三拍,装进的是寄存器,加的是一,写回的是内存。原话咱们单摆一行:
- “The problem occurs because thread 2 loads cnt in step 5, after thread 1 loads cnt in step 2, but before thread 1 stores its updated value in step 6. Thus, each thread ends up storing an updated counter value of 1.”
两线程的装与写一交错,各存的是一个一,一次加法就这么没了。丢更新是 xv6 书页 65 点过名的病,在这里有了完整的病历。它家把竞态摆到了汇编层,咱们把案子摆在编译器层,是同一类的病,给的是两层的证据。
Linux 的那一头,本章是一个字不比的。自旋锁、信号量这些名字您兴许在别处听过,咱们手里没有翻过的手册、读过的源码,比不了的就是比不了,留给将来的书。
这一章留下了什么
| 术语 | 一句话口径 |
|---|---|
| 竞态 | 同一处内存被同时访问,至少一方在写,结局押在次序上 |
| 临界区 | 拿锁到放锁之间的那段指令,门闩护的就是它 |
| 自旋 | 拿不到锁原地转圈,一遍一遍再试,人一直醒着 |
| test_and_set | 把旗改成已占,同时报回改前的样子,改与报捆在不可分的一拍 |
| acquire | 进门的要求,拿锁之后的读,读得到上一任留下的一切 |
| release | 放行的承诺,放锁之前,临界区里的写统统落定 |
| 登记簿 | SpinLedger,数本核活着的门闩有几层,零才许睡 |
| 护甲 | 关中断的守卫 IrqGuard,进门存旗,出门按快照还原 |
本章收进兜里的,咱们数一数:一份共享财产的名单,三路的对手各有各的案底。词收了两个:竞态说的是病局,临界区圈的是地。一把门闩的家当,叠的是四层心思,走的是一进一出,配的是一本登记簿,外带一条持锁不许睡的家法。两桩案子换来的是一条底线与一条家规:跨执行流共享的变量必须用原子或屏障表达,静态寿命的对象全零字节必须是合法默认态。
门闩立好了,咱们替它交一句底。后来还没真到双核启用的日子,咱们挨过一场预审,把单核时代的家底盘了一遍,盘出了三句实话,原样转交给您:那把转圈的门闩,单核时代立的,其实不会跨核。重入的检查,到了双核会把正当的争抢误当成自己人。进门存进锁里的中断快照,会被后进门的对手覆盖。这三句是预审里自己招的,病发当日是没冒过头的。招出来的怎么修,快照搬进谁的口袋,重入认谁的手,门闩怎么学会跨核,下一章《锁的实现》开门就办。您带着这三句过去,那一章的每一处修法,病根您都已经攥在手里了。
练一练
三道题留给您:一道是动手的,一道是排次序的,一道是读屏的。
题一:动的是手。 长凳的 test_sync 您自己跑一遍,用的命令在实况节里。跑完翻回 2.4 的实况,consumed 头一回出现之前的那几行里,您数一数 produced 有几行?您拿空位的枚数把这个四讲一遍。
题二:排的是次序。 lock() 里的三步,头一步的 Check,中间的 SaveAndDisableIrq,末一步的 test_and_set。生死攸关的是哪两步谁必须在谁前头,您说一遍理由。再看 Check 的位置,它排在 SaveAndDisableIrq 的前头,中间留着一条闸还开着的窗口,闯不闯祸的问题,您拿单核上持锁必关中断的家法推一推。
题三:读的是屏。 面板上的 irq on, tick 100Hz 那一行,本章哪一桩案子两头都住在这行里?一头是写它的人,一头是读它的人,您给两头对上号。
参考答案
题一的答案:四行,咱们来数。空位开场发的是四枚,生产者一口气产了四件,每一件占的是一枚,产到第五件的时候一枚不剩,wait 这才把它撂下去睡了,消费者这才上的手。所以 consumed 头一回出现之前,屏上有的只是四行 produced,一个 consumed 都是没有的。
题二:生死攸关的是 SaveAndDisableIrq 必须排在 test_and_set 前头,旗立起来之前闸就必须落下了,不然应验的就是 xv6 书页 71 那句警句,旗是立着的,闸是开着的,一个掐得准的中断进来,系统就死锁了。Check 的窗口不闯祸:它只是读一眼旗,读完了就算中断进来,换上去的人把锁拿了又放了,咱们回来接着走 SaveAndDisableIrq 与 test_and_set 的正路,咱们顶多多等一轮。再往深推一步的话,调度器里 yield() 与 exit_current() 两个主动让路的口子没设登记簿的岗,守的仍是持锁不许睡的家法,单核上锁在手里的人就是不睡、不让位、也不退场的,现存的用例里也没有一处持锁让位,把睡觉之外的路都封上,这个 while 其实一圈都不会真正转:旗被立着,说明的是持锁人正占着 CPU,轮不到咱们来读旗。转圈的路,眼下是一步都用不上的,它是给将来第二颗核修的,这话的分量,得收了卷才见得到。
题三答的是删循环案,咱们来对号。写 ticks_ 的是时钟中断,按 100Hz 的拍子每秒写一百次。读它的是等待循环,当年被编译器删掉的就是它。案子两头的当事人,一个按这行报的节拍写,一个在测试里一圈一圈地读,两家住的都在这一行里。
延伸
- xv6 书第 7 章(书页 63 到 74):本章引了 63、65、66、70、71 五页。没引的几页里,67 到 69 是它家锁实现与死锁的正戏,您拿着正文里那五个页号逐句对,咱们借得准不准,您说了算。
- CSAPP 2e 第 12 章 12.5 节(电子版正文页 992 到 995):badcnt 全本,汇编三拍与指令次序表都在,您对原书核,印本页码认节名就好。
- 正文《轮流当家:让出来的,抢出来的,排出来的》一卷:《被删掉的等待循环》《转圈的门闩》《让出去,还能被叫醒》三篇,是本章两桩案子与门闩出生的全本,三处误诊的原文、四层心思的原话,都在那边。
- 正文《请第二颗脑子上线:APIC、蹦床与共享调度》一卷:《同步层的旧债》一篇,收卷那三句实话,在那里一条条还上,您要看单核的家底怎么被预审戳破,那一篇的门开着。
- 《锁的实现》《死锁与锁序》《条件等待》几章在册待写:门闩跨核的修法、锁的次序官司、睡觉的正戏,各归各家。