03 · 死锁与锁序:一声断言,一张锁序图,两种满
4.2 收卷留了话:门闩毕业了,可锁自己的一生一个字没管,咱们得把这一课补上,生了要登记,死了要销册,那本册子的容量是六十四个身份。双核的实弹里一声容量断言炸响了,满员了,第一个进不去门的,是管道的加写者路径,您带着断言过去。您进门了,咱们补一笔口径:那一声是在机内实弹里炸的,宿主的案册里出不来这一声,正文《锁的生卒》那篇记的全程。其实断言自己当时还坏着嘴,喊了半天没喊出重点。所以开门的次序是,咱们修好证人的嘴,认了病,再把案办了。
本章的活,咱们数下来还是三样。头一样的活是修嘴认病:断言的嘴怎么修,死锁是什么,案子里的两双手谁也不放,谁也等不到自己想要的那把。药方落在全机的次序上,咱们请一张锁序图替机器盯着。第二样的活,咱们添两件新家什:名号与尸检,出了事,头一步亮的就是册子。私册与公图的名目,咱们也提前立好:链是各记各的,图是全机共用的一张。末一样办的是两场满员的案:头一场满的是骨灰,咱们叫它假满,销了户就能治。另一场满的全是活着的锁,咱们叫它真满,病根落在引用那边的欠款上,4.2 讲过的旧案,咱们这里只对一对。
量法还是老的三条,咱们挨条念。码这一头咱们两代对读:旧形状是 r19 的 lockdep.hpp,83 行的身子,配上 lockdep.cpp 的 109 行,那是《锁报名号》那篇带出来的单核版。今天的主角是 r26 的 lockdep.hpp,86 行的身子,配上 lockdep.cpp 的 129 行,实况锚就是 r26_smp 的正身。配角咱们也点了三件。kernel/lib/assert.cpp 是 34 行的文件,断言的嘴就长在那里。还有 kernel/proc/sync.cpp 的 263 行,4.2 量过的,咱们本章只取退役那几段。再有 kernel/init/init_sequence.cpp 里转储的那座桥。屏这一头咱们看两站:头一场 r26_smp,咱们在 4.2 刚走过,起机面板咱们不重印,本章把 lockdep 那块八案的屏升正席。第二场是 r19 的旧形状,对读用的,咱们就不另录屏。您要亲手翻的话,git 里的名字是 r19_lazy_alloc_page。书引的是 xv6 第 7 章,4.1 与 4.2 引过的有六页,那六页里其实有 70。本章新引的页是 69,在 70 上引的是没引过的句子。原话咱们一律整句摘,页号也写明了,您对着书核。
两把锁各自都是好的,门闩的心脏 4.2 也验过是好的。您想:死锁的病,到底生在哪?
病其实不在哪一把锁上,那病生在两把锁相遇的次序里。每一把都尽了职,该做的拿、放、验手、登记,咱们一样不缺。背对背的那一拍谁也没犯规,可谁也走不动了。所以药方落在次序上:给全机的锁排一张座次,谁都是照着座次拿的。可座次是靠人守的,人守着守着就松了,所以正文《无盘起家》那一卷的原话是,咱们不想拿“代码里没这么写”当什么保证,咱们想让机器自己盯。盯的是哪一路,那卷也说了:绕得回来的次序,今天不死锁的话,改天也会死的。
断言的嘴:消息在前,位置在后
案子开审了,咱们得让证人把话说清。开场的容量断言,头一版喊出来的时候嘴是坏的,正文《锁的生卒》记的:模板函数的实名实姓把单行塞满,真正的原因被挤出了屏幕,断言喊了半天没喊出重点。修法的正文只有一句话:消息的打印在前,位置的打印在后。真身您一看就认得,kernel/lib/assert.cpp 的 :27 与 :28:
cinux::print::Println("[panic] %s", k_message);
cinux::print::Println("[kern] %s:%u in %s", loc.file_name(), loc.line(), loc.function_name());喊在前头的是要紧的消息,报在后头的才是名字,单行塞不下也就塞不下了,重点已经落地。函数的后头还有两步::30 把 rbp 抓进了栈帧,:31 交给 PanicDump 把调用栈倒了出来,嘴好了,栈也跟得上了,顺着栈就能找到拿锁的路。它当的差只在内核世界。宿主世界同名的声明,打印是合成一行的,位置在前、消息在后的老次序,链接期各选各的脸,这门手艺您在 4.1 的长凳上见过,这里又照了一面。
还有一条纪律写在它的文件头注里:内核世界的 Check 一响就不回头,打完了这几行,机器就地停住,什么状态也不再碰。现场原样冻在了屏上,您后头读到的所有尸检,吃的就是它留下的现成饭。
死锁:谁也不放,谁也等不到
嘴修好了,咱们认病。xv6 书页 69 的病例最干净:两段执行流,咱们照书里的记法叫它们 C1 与 C2,各自都要过 A 与 B 的两把锁。C1 拿到了 A,伸手去要的是 B。可 B 在 C2 的手里。C2 拿到了 B,伸手去要的是 A。A 在 C1 的手里。谁也不肯放掉手里的,谁也等不到想要的那把。书里一句就定了案,咱们把原话整句摘下:
- “This situation is called deadlock.”
同页给的药方也是一句,咱们摘原话给您:
- “all code paths that hold multiple locks must acquire locks in the same order”
凡是拿多把锁的路径,拿的次序都得是同一条。同页的末尾,它把这句抬进了函数的规约。规约咱们配句白话,就是函数对外承诺的事,您照这个记。原话摘给您:
- “locks are effectively part of each function's specification: callers must invoke functions in a way that causes locks to be acquired in the agreed-on order”
锁实际上是每个函数规约的一部分,调用的人得按约定好的次序把锁拿进来。这句话的分量,咱们到对照节再回来称。咱们自己也真死过一回,不是书上的病例。正文《请第二颗脑子上线》那一卷的《一个队列,两颗核》记下的现场,原话摘给您:唤醒别人发生在持锁登记的路上,等孩子退场发生在持锁扫描名册的路上,等待的等待一层叠一层,每层的操作都抢锁,结果自己等自己,当场就死锁了。
修法的全本,您在正文《一个队列,两颗核》里读全了,那篇的原话:只有从零到一那一拍才真的抢锁。往下的意思是,嵌套记的只是层数,抢锁省了,每一层记在按核的计数上,最外层那一把旗包了全场的门。您在 4.2 见过的影子,是按核计数的那一半。嵌套计数的表,4.1 里对过的,门闩的四层心思不再重讲。咱们这里只记一笔:调度队列的那一场,单方使的是同一把旗。书页 69 的那一场,两把旗是背对背的。得的是同一种病,次序的病。
死锁其实还有一位近亲,4.1 引过的那句次序警句:旗立着,闸是开着的,一个掐得准的中断进来,这就成了死锁。同一科的病,治法是同款的,持锁的日子闸就得落下,拿锁之前的查也得做一遍。那一页 4.1 花过了,咱们本章不重去。
锁序图:不靠自觉,靠机器
药方说的是排座次,座次靠谁守?开篇问框引过那句,咱们不想拿“代码里没这么写”当什么保证,咱们想让机器自己盯。盯梢员是正文《无盘起家》的原词,白话是这么说的:它替咱们守次序。它的真名是 lockdep,展开的白话是 lock dependency,锁与锁的依赖:谁在谁手里的时候去拿了谁,它记的就是这样的依赖。
它手上的图,咱们全章叫锁序图。名字交代一句:正文《无盘起家》那一卷立它的时候叫座次图,正文《锁的生卒》那篇的段落里又写过顺序图,其实同一件东西换过名,引原话的时候,原名是保留的,咱们的话统一叫锁序图。
图上的东西有两样。顶点是锁的身份,而锁的身份证,就是活锁的地址,这一句也是正文的原话。活锁在这儿说的是活着的锁,与 livelock 撞名的这件事正文交代过,咱们不展开。顶点的道理您一听就懂:对象在,地址在。对象没了,身份证成了空号。边记的是次序:手里已经攥着 A,又去拿的是 B,画一条 A 指向 B 的边。边的方向,正文里定死了,新边从手里的锁,指向新拿的锁。查环走的是反向的道理:从新拿的锁出发,咱们顺着边往回走,看回不回得到手里的锁。回得到的话,把边加了上去,图就成了环。正文还有一句压舱的:绕得回来的次序,今天不死锁的话,改天也会死的。
两道关就设在拿锁的路上,咱们看真身,lockdep.cpp 的 :49 到 :56:
for (const auto kHeld : held().view()) {
if (kHeld == index) {
return Status::kRecursive;
}
if (graph_.reaches(index, kHeld)) {
return Status::kCycle;
}
}对手里攥着的每一把,新来的各问一遍。头一问问的是不是同一把:是的话,报的是 kRecursive,案由写的是重入。第二问问的是可达:从新来的那把出发,可不可达手里的那一把。可达的话,报的是 kCycle,案由写的是环。可达咱们配句白话:咱们顺着边一格格走,走得过去的就叫可达,当差的函数叫 reaches。Check 是当场响的,机器响着就停了,您顺着栈就能把次序揪出来,这三句也是正文的原话。两问各报各的案由,诊断是分得清的:重入的归重入,环的归环。
两关都过了,才轮到咱们落笔,顺序落在后头的几行里,您接着看,lockdep.cpp 的 :57 到 :63:
if (locks_.get(index) == nullptr) {
base::safety::Check(locks_.insert(lock) == index, "lockdep identity slot changed");
}
for (const auto kHeld : held().view()) {
graph_.connect(kHeld, index);
}
base::safety::Check(held().push(index), "lockdep held stack lost capacity");身份落了格,身份没在册的当场登记。对手里攥着的每一把,各连了一条边。末了进链,进不去链的又是一声 Check。咱们把这三步连起来看:查在写的前头,判词不过,咱们一笔都没落下。
全册的判词一共六个,lockdep.hpp 的 :44 到 :51,咱们整段摆:
enum class Status : unsigned char {
kOk,
kCycle,
kRecursive,
kCapacity,
kNotHeld,
kOutOfOrder,
};kOk 的意思是放行,kCycle 与 kRecursive 您刚认得,kCapacity 咱们马上讲到。后两个是出门那侧的:放一把手里没有的锁,报的是 kNotHeld,册里查无此锁的也是这一案。放的不是最里层那一把,报的是 kOutOfOrder。出门只许弹的是栈顶,这是正文立过的纪律,中断开关的还原次序,靠的就是这个。
家当咱们点齐。头一件的家当是名册,选的料是 SlotTable,地址住进各自的格子,常量的名字是 kLocks,写死的值是 64,数出来的是六十四格。这个户口本不是新造的,在内核里当差的有三处:挂载表、文件册、锁名册,正文的原话是,三种户口用的,其实是一件家伙。名字占的是一排 names_,跟名册是同长的,咱们下一节讲它。边图的一件是 DirectedGraph,连边、查可达、摘顶点都是它的活。手里攥着的链,咱们也数一件,它的真身是 StaticStack,常量的名字是 kDepth,写死的值是 16,数出来的是十六层,拿一把进的是一格,放一把出的也是一格。名册与链的容量,是刻死在类型上的。容量的态度,正文《无盘起家》那一卷也立了原话,宁响不漏:超了的回 kCapacity,Check 是当场报的,悄悄丢了一条边的话,图的保证就成了纸面上的话。同一门的家风,咱们在 4.1 走过两处岗哨,就绪队列的入队与睡觉的门。这里站的是第三处,册子的门:宁可响亮地死,不许悄悄地丢。
名号与尸检:出事头一步亮册子
名册记的是地址,地址不认人。正文《锁报名号》那篇记的苦,原话摘:串口上响的那一行,报的是一个地址,您拿着地址对源码,翻了好一阵子才对上是谁。药方是预登名号的:set_name,真身在 sync.cpp 的 :124 到 :128,构造完了、还没出事的时候,把人话的名字交给名册存着。名字跟地址,登记的时候一起来,清的时候也得一起来,这件事咱们到销户那里见。
出了事,亮什么?尸检报告,这个叫法也是正文领来的,倒出来的那页持有链就是报告。次序是救命的那一句,正文原话摘:最能救命的是次序:检查失败,头一步把持有链亮了出来,响是第二步的事。真身是有两处的,咱们挨个看。一处是拿锁路上的安排,sync.cpp 的 :30 到 :33:
const LockOrder::Status kOutcome = order.acquire(lock);
if (kOutcome != LockOrder::Status::kOk) {
dump();
}判词出的不是 kOk 的话,头一步倒出来的就是册子,后头的两道 Check 才开了口。咱们看另一处,倒出来的样子,转储的桥架在 init_sequence.cpp 的 :59 到 :65:
proc::InstallLockdepSink(+[](const char* label, unsigned long long address) {
if (label != nullptr) {
print::Println("[lockdep] held: %s", label);
} else {
print::Println("[lockdep] held: lock@%llx", address);
}
});有名字的报名字,没名字的报地址。持有链是从最外层排到最内层的,一行记的是一把,谁套着谁的格局,屏上是一目了然的。这座桥是个函数指针的座,内核世界装的是串口桥,宿主世界装的是捕获器,与 2.4 的假 sink 同门的手艺,4.1 里认过亲的,咱们一句带过。
咱们还得替尸检报告记一笔它自己的案:头一版的转储,把名册槽位的指针当成锁的地址报了,宿主的测试当场按住了,改的法子是解引用再报。丢人的事,正文照实记了,咱们也照实引。
这桩小案顺手立了条家法,两个世界的另一面。声明的正文是同一份,两个世界各链各的实现,这门手艺 4.1 的长凳上教过:链接的时候挑走哪份。这里站的是验收侧,正文原话摘:默认构建里早退的用例,真行为要到开着检查的构建里跑过才算数。同篇还有一句更狠的,这个绿什么都没证明,也摘给您。
私册与公图:链各记各的,图全机一张
回到单核的年代,这套册子一个人看也就够了。咱们看旧形状 r19 的成员,lockdep.hpp 的 :77 到 :80:
base::container::SlotTable<const void*, kLocks> locks_;
const char* names_[kLocks] = {};
base::DirectedGraph<kLocks> graph_;
base::container::StaticStack<unsigned int, kDepth> held_;末一件是手里攥着的链,全机独一份的。方法的门口一件守卫也没有,acquire 进了门就查。双核一上了线,咱们就有两件事得改。头一件的活是把链按核发下去。4.2 里讲过登记簿的搬家,深度从一册发成了一排。手里的 held_ 链,是同一场搬家的另一名成员,搬家本身咱们不重讲,您对着新形状认一遍,就认得出它了。r26 的 lockdep.hpp,咱们抽三行:
using HeldChain = base::container::StaticStack<unsigned int, kDepth>;
HeldChain& held();
HeldChain held_[arch::per_cpu::kMaxCpus];一格管的是一核,机器至多带的也就是八颗核,取格的钥匙是核号,held() 报的就是本核的链。真身只剩了一行,您认一下,lockdep.cpp 的 :23 到 :25:
LockOrder::HeldChain& LockOrder::held() {
return held_[arch::per_cpu::PerCpu::self().cpu_id];
}问的是核号,报的是本核的一格。4.2 的 depth() 同款身材,用的也是同一个 PerCpu,一个取的是深度,一个取的是链。链与图怎么分,正文《请第二颗脑子上线》那一卷的原话讲得最清,摘:每核一条自己的持有链,谁在谁的手里套着谁,一人一册地记,全机共享的是一张记录谁在谁前的有向边图,边图自己另有一把原始的小锁护着,图是共享的财产,链是各核的私册。私册这个词是正文亲造的,公图是咱们给共享的图起的短名,咱们后头就用它俩。
第二件的活是守图:图是全机仅此一张的,两颗核要是赶在同一瞬间来写的话,守卫也就不能再缺了。咱们接着看 r26 每个方法的头两行,拿 acquire 作例的话,lockdep.cpp 的 :37 与 :38:
const arch::IrqGuard kIrq;
const auto kGate = g_graph_gate.guard();头一行的护甲,防的是本核的中断插脚。第二行的 g_graph_gate,防的是对面核同一瞬间动同一张图。您在 4.2 的 console PutString 那儿见过两行证人,护甲防的是本核,门闩防的是对面,这里每个方法的门口都站着同款。
两代的行数也对得上数,您自己加一遍:头文件从 83 到 86,添了三行:两行是链的搬家,剩下一行是 include 的,把按核的那套接进来。源文件的行数从 109 到 129,添的二十行,大头是每个方法门口的守卫两行,外加取格的 held() 与销户时扫全排的那一圈。
咱们停下来问一句:g_graph_gate 为什么是个光秃秃的 base 互斥件,而不是咱们内核的门闩?您推一遍:要是它换成 Spinlock,头一个人进门会发生什么?
咱们推一遍,这段是咱们的推演,不是正文的原话。内核的 Spinlock 拿到手之后,末了一件要办的事就是在登记簿记一笔,记的活落到名册 LockOrder 的方法里,而名册的每个方法,头两行拿的正是 g_graph_gate。旗还在自己的手里,同一颗核又要去拿的还是同一把旗。这一步是走不到转圈的:门闩进了门,转圈的前头还隔着一道重入检查,4.2 修法二认的就是它,当场就叫了,机器响着就停了,响在防死锁的那道岗门口。盯梢员的家什用上了被盯梢的锁,站岗的自己把自己拦下,这班岗也就站不成了。所以它生在 base,零系统耦合的出身,中断是不关的,名册也是不进的。4.2 点过它的五家用处,锁序图的门是其中一家。门里护的财产,恰好是给全内核的锁记名的册子,守门的自己决不能也是册上有名的一把。
骨灰案:生要登记,死要销户
册子是会满的。头一场的满,满的是骨灰,案情正文《锁的生卒》全本记着,咱们顺着捋。管道是这套教材里少有的会死的对象,测试开了关、关了开,一根接一根地生,一根接一根地死。每一根自带的锁有三把,环形缓冲拿的是一把,读写两侧的计数各拿一把,本章是头一回报它们的名号。生的时候,原话摘:锁在构造里自动地登记进锁序图,登的是地址。死的时候呢,跟锁序图说一声的都没有。地址入了册,对象没了,下一根管道落在同一个地址上,倒是能复用身份。可堆不是省油的灯,新管道常常落在新鲜地址上,册子上攒起一条又一条死地址,每条占着身份的一格,没有任何活着的锁用它。几十根管道开合下来了,正文原话:六十四格装的全是骨灰。
咱们说的假满是这样的:格被死地址占着,活锁想进的门没有了。销了户就能治,而这门功课,正文《无盘起家》那一卷里是早教过的,原话讲的是:retire 就是回收前的销户,销户是在前的,还存储是在后的。管道忘了办,给锁补上的礼数,正文里叫的是生卒礼:析构之前挨个退了役。您看真身,sync.cpp 的 :86 到 :91:
void Spinlock::retire() {
const cinux::arch::IrqGuard kGuard;
cinux::base::safety::Check(!held_.test(std::memory_order_relaxed), "destroyed held spinlock");
SpinLedger& ledger = ledger_ != nullptr ? *ledger_ : DefaultSpinLedger();
ledger.forget(this);
}头一道的 Check,确认没被持有:攥着的锁不许销,销了,持锁人手里就成了空旗。销的活本身在 forget,一共走的是三笔,lockdep.cpp 的 :95 到 :97,您逐笔看:
base::safety::Check(locks_.erase(kIndex), "lockdep identity slot vanished");
names_[kIndex] = nullptr;
graph_.erase(kIndex);身份格还了回去,名字清掉了,沾边的边全摘。名字跟地址都要清,这是《锁报名号》立过的教诲:名字不清,下一把锁再落进同一格的话,尸检报告里就是张冠李戴的口供。forget 还有拒绝的一面,仍在某条持有链上的锁,是不许销的。r26 扫的是全排,lockdep.cpp 的 :89 到 :94,哪颗核的私册攥着它都不行。旧形状 r19 扫的只是单册。您想,双核上本核的册子看不见对面核的手,销户得把全机的私册都问一遍。retire 的头一道 Check 之外,SpinLedger 的那一层还有一声 lockdep destroyed held lock,sync.cpp 的 :53 到 :58,两道岗的布防,一道守的是锁身,一道守的是册子。
4.2 的寿命案,咱们在这儿对一对。预分配六十五个地址,任何时刻活着的只有一组锁,历史地址越过六十四,册子是始终不满的,它过的正是销户这道关:死一个,咱们销一个,格是真的还。您反过来看,销户要是没立的话,寿命案的头一个用例是跑不完的。信号量的退役另有一道前置,真身 sync.cpp 的 :187,那一声 Check(waiters_.empty(), “retired semaphore still has waiters”) 说的是:等待册上还有人,锁是不许退的。人没走完锁就走了,那是把还在睡的人反锁在屋里,正文的原话。
反向敲打与还炸:满册的两种满
生卒礼的头一版,自己挨过一记反向的敲打。正文记的:头一版退役为了检查时不被人打扰,进门头一件抢的就是一把自旋锁,而锁一进门就会在顺序图里登记一笔身份。审查指出来了一回:已经满六十四槽的时候,析构反而要申请第六十五个身份,越退越满了。多余的抢锁删掉,退役只做检查与摘除的本分。您回头看上一节印过的 retire,头一行有的只是护甲,没有第二行的抢锁,那行单薄是故意的。forget 门里的那两行守卫,护图的 g_graph_gate 是 base 件,是不进名册的,前头推演立过的道理,这里又站了一岗。
补齐了,案子还是没完的。正文原话:退役补上了之后,生产实弹还是炸了容量,响的还是同一声断言。这回查了个底朝天,原话里是笔笔俱全的,咱们跟着对:调试器把锁序图的原始册子整个倒出来,六十四个身份个个是活的,地址对得上内存里真站着的管道对象,持有链全是空的,深度也个个归了零,占座的事没发生。案子就此翻了面,正文的原话:那么问题换了主语:谁说它们该死。
咱们停下来想一想:同一声断言响了第二回,您在屏前头一步查什么,才不会把两场满认成一场?
头一步的活,是把原始册子倒出来对地址。骨灰案的那一场,死地址对不上任何的活对象。这回的册子,个个是对得上的。满册从此分两种:咱们叫它假满的,满的是骨灰,销了户就能治。咱们叫它真满的,满的是活锁,销户是治不了的。真满的病根,顺着引用的数目走:管道生下来带的是三笔引用,创建者手里的一笔,文件表两端各自的一笔。两个描述符都关得干干净净了,引用也只从三减到了一,创建者那一笔是没人还的。这桩引用的案子,4.2 是全案讲过的,创建者改用带归还的共享指针、每个出口都还,修法也是讲过的,咱们只记落点:锁的生卒背后是对象的生卒,对象的生卒背后是没还清的引用。册子一记到六十四就喊了,喊的就是这个病。
Code: Cinux 实况:八案到齐,那声断言不在此列
实况用的还是 r26_smp。宿主测试座上 lockdep 自己的八案,4.2 的那三块屏里夹着印过,本章咱们升正席:
[PASS] lockdep: CPU held stacks are private while lock order edges cross CPUs
[PASS] lockdep: another CPU observes established lock-order cycles
[PASS] lockdep: remembers AB then rejects BA
[PASS] lockdep: rejects transitive cycle
[PASS] lockdep: invalid operations leave held stack intact
[PASS] lockdep: forgetting a destroyed lock permits address reuse
[PASS] lockdep: held depth exhaustion fails visibly
[PASS] lockdep: graph capacity is reclaimed on destruction
=== Results: 8 passed, 0 failed ===头两案 4.2 讲跨核时点过名:链是各核的私册,边是全机的公图,案一看住的是链的私密,案二看住的是边的共享。后六案的活,咱们逐案一句。咱们头一个看 remembers AB then rejects BA 的一案,拿过 A 再去拿 B 的路,回过头想拿 B 再拿 A 的话,环检查当场就拒了,座次立了就得认。跟着的 rejects transitive cycle 一案,环是隔着层也抓得住的,A 到 B 再到 C 的链,想从 C 回到 A 的话,可达的那关接得住。再往下的 invalid operations leave held stack intact 一案,被拒的申请是不许在册子上留痕的,持有链是原样的。销户侧的 forgetting a destroyed lock permits address reuse 一案,销户之后同一地址再进册,得到的是干干净净一个新身份,骨灰案的药在这案上验。深度侧的 held depth exhaustion fails visibly 一案,十六层的深度用满了,响亮地报,悄悄截断是不干的,宁响不漏落在深度的那一头。末了的 graph capacity is reclaimed on destruction 一案,六十四格销了真还,寿命案六十五个地址能过关,站岗的就是它。
开场的那声容量断言,屏上咱们是见不到的,咱们也不该见到它。它是机内实弹炸的,口供与修案的全程,正文《锁的生卒》里记全了。咱们不造那块屏,口径是开篇立过的,咱们在这里兑现。
对照:同一件事,别的机器怎么做
书页 69 的那句规约,锁是函数规约的一部分,书页 70 紧跟着算了代价,咱们摘原话:
- “Honoring a global deadlock-avoiding order can be surprisingly difficult”
遵守一张全局的死锁规避次序,可以难得出乎您的意料。难在什么地方,它家照页摆了几样,咱们跟着点。叫醒的次序:consoleintr 护着控制台的锁去叫醒等它的人,叫醒又要拿进程的锁,所以 cons.lock 得排在进程锁前头。链条长:翻路径的目录一把,新文件的 inode 一把,再到盘块缓冲、盘驱与进程锁的那几节,一条链上挂的是五把锁,每一节的次序都得排对。次序跟模块的上下级打架:一个模块要调另一个模块,锁序却要求被调那方的锁走在前面。身份是未知的:有一种锁是这样的,上一把还没到手的当口,咱们根本不知道下一把会是谁,像按路径逐级翻目录、扫进程表找孩子这样的走法,都是走一步才知道下一步的路,座次是没法提前写死的。
页上还有一笔总的,咱们按页转述的意思是这样的:锁越多,死锁的机会越多。排得粗了好守,并发也就窄了,排得细了并发宽,次序也就难守了,所以锁序常常是内核实现里的主要约束。4.1 摘过同页的重入之争,立场咱们同站,就不重讲了。
Linux 的那头,这回比得了,但咱们只比一句。生产内核里有一位同名的 lockdep,配置的名字是 CONFIG_PROVE_LOCKING,打开了它,按锁的类建依赖链,报的口径是 possible,可能发生的环,不只当真发生的。六十四格的身份册是教学器物的取舍,静态、定长、满员就喊的路子。它家是跑在生产上的家底。咱们不展开,只认这门亲:盯着的是同一件病,教具归教具的活,家底归家底的活。
这一章留下了什么
| 术语 | 一句话口径 |
|---|---|
| 死锁 | 谁也不放,谁也等不到;病不在哪把锁,在次序 |
| 锁序图 | 记谁在谁前的有向边图,顶点是活锁的地址,边是持 A 拿 B,全机一张 |
| 两关 | 拿之前问两声:同一把报 kRecursive,可达报 kCycle,案由分得清 |
| 宁响不漏 | 容量满了回 kCapacity 当场报,悄悄丢一条边,保证就成了纸面上的话 |
| 私册与公图 | 持有链一核一册,边图全机一张,公图的门由 base 互斥件守 |
| 尸检报告 | 检查失败头一步亮持有链,最外层到最内层一行一把,响是第二步 |
| 销户 | 析构前退役,身份、名字、边三笔全清;销户在前,还存储在后 |
| 两种满 | 骨灰满,死地址占格,销户能治;活锁满,病根在引用那边的欠款 |
4.2 押过来的三笔,咱们清一清。锁生了要登记,死了要销册:生卒礼立了,销户三笔清了,信号量退役的前置立在退役自己的门里,析构的时候挨个调它,那道 Check 也就到场了。册子的容量是六十四个身份:骨灰案的那场假满,销了户就治好了。还炸案的真满,追到了引用那边的欠款上。册子为什么满,满的又是什么:两种满,本章从头到尾就是在教您把它们分开。开场的那声断言,现在可以从头念到尾了:嘴修好了,要紧的话是在前的,名字是在后的。名号与尸检的两件家什,出事头一步亮的就是它们。案犯是有两拨的:头一拨的案犯是骨灰,另一拨的案犯是一笔没人还的引用。
边界咱们也如实挂出来。这套检查眼下只看着自旋锁的获取次序,Mutex 和 Semaphore 是睡得着的,次序另有自己的记法,接到它们是往后的事,正文《无盘起家》那一卷挂下的原话,至今还是挂着的。开关也是有的:CINUX_LOCKDEP,默认是关着的,构建点亮了它,机器出的门才带着这套检查。仓库自带的是 scripts/checks/acceptance.sh,四条的构建线,后三条线开着的都是它,末一条的 build-checks 连机内镜像一起造,机器的肚子里也带着检查跑。醒着的次序,咱们今天办完了。睡觉的那一路,4.1 立谱系时押给《条件等待》的票还押着,票面写的是睡觉的正戏。叫醒丢了是一桩,两颗核一起睡沉的话又是一桩,两行的病名,4.1 的票面上原本没有,正文《锁的生卒》卷末预告的就是那桩案子,咱们把病名记在票背上,咱们点到为止,案卷的开门留到下一章。
练一练
三道题留给您:一道推演的,一道回望的,一道读屏的。
题一考的是推演。 重入那道关要是撤了,只留环检查独自当班的话,同一把锁第二次进门的时机,它拦得住吗?报的案由又是什么?您拿 reaches 的底细推一遍,底细在 base 容器的注释里,连零长路径都是算在内的。
题二考的是回望。 两场死锁:咱们调度队列的那一场,是自己在等自己的案子。书页 69 的那一场,是两双手背对背的案子。您说说,锁序图的两关,各接哪一路?
题三考的是读屏。 八案里有两案带着 CPU 的字样,各站哪一头的岗:私册的私密,还是公图的共享?您再答一问:这八案案案都过,两个世界的家法怎么念,才算数?
参考答案
题一:是拦得住的。锁第二次进门的时候,循环里的那把 kHeld 与 index 是同一格,reaches 是从同一格出发的,查的还是同一格,零长路径也是算够得着的,返回的是真,环检查报的是 kCycle。案子破了,案由报歪:重入报成了环,您顺着环去查两把锁的座次,查不出所以然,真正的病是一把锁进了两次门。环检查独自也是拦得住的,所以单独立了一关,为的是诊断的准头。
题二:答的是自己等自己,同一把旗进了两次门。您今天再走同一条路,旗还没转起来就会响:门闩那一层的重入检查当场叫。要不是它拦在了前头,轮到了册子,报的也是 kRecursive,两级的岗哨,同一款的案由。两把旗是背对背的,手里的与对面手里的一左一右,由环检查的 kCycle 接住。边记在全机的公图上,隔着一双手也是看得见的,机器响着就停了,不等背对背真的成形。两场病一句话总:拿多把锁的路径,走的次序得是同一条,书页 69 的原话。
题三:案一的 CPU held stacks are private while lock order edges cross CPUs,一案里就把两头都验了,链各记各的,边是两核都看得见的。案二的 another CPU observes established lock-order cycles,补的是公图的眼睛,这核立下的环,那核来碰的也是它,照样是响的。家法咱们这么念:宿主绿了不算数,同一用例在开着检查的构建里跑过才算,acceptance.sh 后三条线就是给这句家法备的。
延伸
- xv6 书第 7 章(书页 63 到 74):本章新引的页是 69。70 是引过的页,本章在它上面引的是没引过的句子。连同 4.1、4.2,第 7 章咱们引到第七页。没引的段落里,睡眠锁一段与《条件等待》接边,指令与内存次序归《内存序与缓存一致性》。睡眠与唤醒的正段落在 xv6 第 9 章,那才是《条件等待》的正料,您提前翻也无妨。
- 正文《无盘起家:名字、内存里的盘与随身的行李》那一卷《锁的座次图》一篇:锁序图的出生地,两关、三件家当与宁响不漏的全本。
- 正文《懒到家:从登记册到补页》那一卷《锁报名号》一篇:名号、转储与两个世界家法的全本,单核年代的旧形状也从它身上读。
- 正文《请第二颗脑子上线:APIC、蹦床与共享调度》那一卷:《一个队列,两颗核》是咱们自己那场死锁的现场,《锁的生卒》是开场那声断言与两场满的全案,《同步层的旧债》4.2 已荐,三篇连着读。
- 《条件等待》《信号》《内存序与缓存一致性》在册待写:睡觉的正戏、它的计数亲戚、次序最难的一段,各归各家。