04 · 条件等待:三步,一扇窗口,三句口径
4.3 收卷的话还贴在门口:睡觉那一路,4.1 立谱系时押给《条件等待》的票还押着,票面写的是睡觉的正戏。叫醒丢了是一桩,两颗核一起睡沉的又是另一桩,咱们把病名记在票背上,名字记了就算,开门翻案是下一章的活。今天咱们开门摊卷。叫醒丢了,名下两份卷宗:一份在词上的等待那边,首版的唤醒只醒一个人,能叫的那声喊完了,另一个还在睡它的觉,QEMU 里安安静静地挂死。另一份是完成件这边的,通知发了,却被中断例程的尾巴当垃圾扫走。两颗核一起睡沉的现场,就在后一份的卷宗里:全员睡熟,就绪的队列里没了可派的活。病名是 4.3 点的,案卷咱们一份份翻。
本章的活,咱们数下来还是三样。头一样是认睡觉的身子:三步怎么走,两把锁怎么睡,窗口怎么敞,前科怎么挨的刀。再一样说的是立口径:三句话把窗口在结构上关死,顺带把 4.2 押下的那笔裁断答了,两步的分家里谁粗谁细。末一样是看叫醒的一侧:唤醒即转移,货递的是单位直达,判决下的是同拍,叫醒的功课是幂等的,末了还有唤醒侧自己的一场次序案。
量法咱们数的还是三条。头一条说的是码:实况的锚仍是 r26_smp:sync.cpp,4.2 与 4.3 量过的都是那 263 行,本章取的是睡觉那几段,scheduler.cpp 的睡觉动词,futex.cpp 的词上等待。老身咱们不另开克隆,老代码印自正文卷:互斥锁的老身抄自《轮流当家》那一卷,词上等待的老身抄自《同一副身家,各一条栈》的那一卷,引的时候注卷。屏:4.2 印过的 test_sync 九案屏不重印,本章您回着看。机内的几桩案子没有屏,咱们也不造。书:咱们记的是 xv6 第 9 章,头一回进的是教科书层,页码从 81 起是单独记的,本章引的是六页。第 7 章的旧页上添一句 72。原话咱们一律整句摘,页号写明白了,您对着书核。
老三拍的每一步,咱们单看:挂的队没错,放的锁没错,切的栈也没错。您想:窗口的病,到底生在哪?
病不生在哪一步的里头,生它的是步与步之间的那道缝。队挂上了,锁放掉了,人却还是醒着的,这道缝敞着:叫醒的人恰好从缝里跑一遍,随后睡的人自己把状态按回阻塞,而唯一会叫他的人已经走了。所以药方干脆绕开改步子,立的是一条口径,管住的是一件更根本的事——把状态翻成阻塞的那一拍,锁在谁的手里。
三步:睡觉是个准确的动词
4.1 的押票,头一张今天兑的是谱系那一段,原话:等得久的活,等一件还没生产出来的货,转圈的话就是烧电,所以睡觉才是正路,那一路的正戏归的是《条件等待》,本章立的只是名。正戏开演了。睡觉在咱们的机器上是个准确的说法,修辞的成分一点没有。写这句的地方,在正文《轮流当家》的那一卷《让出去,还能被叫醒》一篇的段首,咱们把后半句补齐:把自己从就绪的队列里摘下来,挂到某个等待的队列上去,状态标成了 kBlocked,然后发起的是一次切换,调度器从此跳过您,直到有人把您叫醒,重新塞回就绪的队列里。
摘下、挂队、叫醒的三步,归的是《条件等待》,咱们到此收手。4.1 说这话的时候,正文那边的三步早就落成了:摘下、挂上、叫醒的这三步,落在调度器的一对新动词上,block_current 与 unblock 就是它们的名字。咱们看睡这门动词的真身,scheduler.cpp 的 :374 到 :383:
void Scheduler::block_current() {
const arch::IrqGuard kGuard;
base::safety::Check(DefaultSpinLedger().depth() == 0, "task parked while holding a spinlock");
park_current();
}
void Scheduler::park_current() {
prepare_to_wait();
schedule_blocked();
}block_current 的这一关,4.1 领您进过,原话里进门头一件查的就是登记簿:深度不是零,说明的是还有人揣着门闩,Check 会当场叫的。响亮地叫,总比挂了强一万倍。门后调用的 park_current,身子是连写的两步,前一半写的是 prepare_to_wait,后一半写的是 schedule_blocked。切栈这个词今天咱们头一回正用,配句白话:把当前任务连同它的栈换下来,换上去的是下一个任务。正文说的发起一次切换,行话里叫的就是切栈。这两步连着写还是分了家,4.2 押了裁断,咱们到三句口径那里再判,这里只记一笔:门里的家法,是一步没改的。
等待队列这件家具值得咱们写半段。咱们没往堆里 new 节点,节点长在任务自己身上:Task 继承了 base 家的 SelfNode,自个儿的身上带一根链,等待队列拿的就是这根链把人串成一条,行话里叫的是侵入式链表。正文数的好处咱们抄两条:头一条,睡觉的路径上一分钱分配都不花。要不然的话,睡前还提心吊胆地去 new 一个排队节点,堆要是正好满了,这觉就睡不成了。另一条防的是错门:天生就防得住,每个任务名下的节点只有一根,同时排在两条队里的事在物理上就办不到。
两把锁:老身的样子
4.1 还有半张票:Mutex 是睡觉那路的家什,柜子的槽表就是它押的。3.6 柜前露过半张脸的家什,今天咱们看它的全身。睡觉的两把锁都出生在正文《轮流当家》那一卷:互斥锁 Mutex 护一段长活,信号量 Semaphore 护的是一堆货。咱们把互斥锁拿锁的老身整段抄来,卷内是原样的:
void Mutex::lock() {
Task* const kSelf = Scheduler::self().current();
{
const SpinGuard kGuard(spin_);
if (owner_ == nullptr) {
owner_ = kSelf;
return;
}
waiters_.push_back(*kSelf);
}
Scheduler::self().block_current();
}双层结构您一眼看得出来:里层一把自旋锁,护的只有两样家当,现在的主人是谁、等待队列长什么样。外层才是真正的竞争。锁空着的话,当场改了名易了主,三两步就完事了。锁有了主,干的事只有一件:在自旋锁的护短下把自己挂上等待队列,放掉手里的自旋锁,把觉睡了。次序正文点过精细:挂队完成之后才放手里的自旋锁,睡觉发生在自旋锁的外面。持自旋锁入睡的红线,这里是一步也不越的。挂上了队,放了锁,锁外才调的 block_current:入队,把锁放了,栈也切了,老三拍就这么个拍法。
放锁那一侧是这把锁最有戏的地方。有人排着队的话,锁就不放空了,直接把队头改成本锁的新主人,叫醒了他。这一手正文起了名:唤醒即转移。被叫醒的人睁开眼,锁已经划到了自己名下,重新排队、重新抢的功夫全省了。为什么这么设计,正文备了反例:要是 unlock 放空锁再叫醒,队头醒来还得再走一遍拿锁的路,从恢复执行到真正拿到锁的那一段里,新来的谁都可以插进来抢走,睡了一觉醒来发现还得再睡,运气差的话睡到天荒地老,行话叫的就是饿死。信号量的 post 同一个心思,也起了名:单位直达。有等人的人,货是不进仓的,计数也不加了,直接越过柜台交到队头的手里。没人等的话才把计数加一存进仓。零构造的家规落在这一件上,说的就是语义本身,将就的成分一点没有,这也是正文的原话,咱们不展开。
敞着的窗口:单核踩不着,双核天天敞
老三拍在单核上太平了好些站,病藏在三拍的次序里。正文《请第二颗脑子上线》那一卷《睡前与叫醒的口径》一篇讲得最清,案情咱们照卷摘:三拍之间有一条敞着的窗口,叫醒的人恰好趁窗口开着跑了一遍,把状态改成了就绪,塞进了就绪队列,自顾自走了。然后等的人不紧不慢走到切栈那一步,切栈的代码不管三七二十一把状态按回阻塞,人躺下了,而唯一会叫他的人已经走了。这一觉没有下一幕了。
咱们停一停,老三拍在单核上跑了那么多站,叫醒的人一回也没钻进来过。您推一推:窗口在单核上是不存在,还是存在的,只是没人钻得进?
窗口其实一直在,窄是窄的,缝却是没合上的。那篇的原话:叫醒的人要与等的人共用一颗核,中间还隔着一次实打实的调度,几百万次的运行里没有一次交错。到了双核,叫醒跑到了另一颗核上,与等的人真并发,窗口天天敞得大大的。身子还是同一副的,单核上它是没事的,双核上天天出的事,差别只在叫醒的人跟不跟您共用一颗核。
病真发过的,前科咱们记在正文《开门迎客》的那一卷《画像三版,窗口三处》的一篇,挨了两刀。两刀的贼都是本核的中断,另一颗核是冤枉的,而且第二颗核上线是记完前科之后的事。窗口的形状,却是老三拍里就全须全尾的。第一刀落在入睡的那侧,原话摘的是:把自己挂进等待名单,与真正的泊车之间,隔着的是几步活。泊车是老卷的叫法,说的就是把自己停进睡眠、交出处理器那一拍,今天的话叫切栈。一家两代的名字,咱们引老卷时用老名,自己的话用新名。那几步活被一个崩溃循环逼出了原形,修法原话:把置阻塞的那一步挪进自旋锁的临界区。第二刀伤的是更深处:光挪进锁里,放了锁、还没泊车的几步里,本核的中断还插得进脚,修法的原话有两片,各片咱们逐字抄,拼在一起念:从关中断的那一步守到泊车提交为止,窗口整个关上了。互斥锁、信号量、完成件三处统一穿上的那件守卫,就是您马上要在新身子里见的 kParkGuard。
三句口径:新身子与那笔裁断
药方正文立成了三句话,咱们整段照念。第一句管的是把入队与置阻塞收进同一把锁:等的人在持着等待锁的临界区里,查条件、挂队列、把状态标成阻塞的三件事,一口气办完了才放锁。第二句管的是真正切栈放在放锁之后:持着别人的锁睡觉是不许的,轮流当家那一卷立下的就是它,卡口到今天还守在原来的地方。第三句管的是叫醒幂等:叫醒的人也进同一把锁,看见的要么是还没入睡的,条件已经变了,要么是已经标了阻塞的,叫醒了他,把状态置成了就绪,塞进了就绪队列。叫了两声也只醒一次,因为第二声看到的已经是就绪,幂等保证了多余的叫不产生多余的队列项。口径这个词前几章咱们当口语用过,这里咱们把它立成术语,配句白话:提前说定、全内核照办的做法。三句合起来的话,窗口在结构上就没了。
咱们看新身子,r26 的 Mutex::lock 全身,sync.cpp 的 :142 到 :157:
void Mutex::lock() {
// Release the spinlock before switching, but keep IRQs masked until
// park_current() has committed the task's blocked state.
const cinux::arch::IrqGuard kParkGuard;
Task* const kSelf = Scheduler::self().current();
{
const SpinGuard kGuard(spin_);
if (owner_ == nullptr) {
owner_ = kSelf;
return;
}
waiters_.push_back(*kSelf);
Scheduler::self().prepare_to_wait();
}
Scheduler::self().schedule_blocked();
}咱们与老身对读,动的只有一处:老身在锁外调 block_current,新身子在锁内多了一句 prepare_to_wait,把状态标成阻塞的那一拍,从锁外挪进了锁里,口径第一句的载体正是这一句。挂队、置阻塞一口气在自旋锁的临界区里办完,放了锁,才调真正切栈的 schedule_blocked。头一行的 kParkGuard 您认得,前科第二刀的那件守卫:中断从进门掩到泊车提交。这一来叫醒的人进的是同一把自旋锁,要么赶在挂队之前,那时条件已经变了。要么落在置阻塞之后,那就是正经的叫醒。缝还是在的,病却没了。
4.2 押的裁断,咱们现在答。头一件咱们把押下的裁断票念一遍票面:注释念的名字 park_current,说的是连着的两步。门这边早改成分家的走法,注释是旧的,身子是新的,谁粗谁细的分判,归的是《条件等待》。咱们的判词:分家是对的,细的赢。锁里的那半是细活:查条件、挂队、置阻塞,几条指令的活,闸一落全办完了。锁外的那半是粗活,干的是真正切栈,分量是重的。可它自带的是干粮:schedule_blocked 进门自备护甲,护甲记在 scheduler.cpp 的 :386,进门其实还查一遍登记簿(:390),调用人就不用替它张罗了。整存的老写法没死,还立在调度器上:block_current 门后连着的 park_current 就是它,宿主长凳的案子今天还在走 block_current。内核的锁家,连同词上的等待与等孩子退场,全走分家的新道。那句注释的意思没记错,中断确实一直掩到了泊车提交,可名字落后了,念的是化石。判词补半句:身子照分家的走,注释欠的是一次改名。
这套口径不是互斥锁一家的。全查的名单正文如实报过:互斥锁、信号量、完成件、词上的等待,四家用的是同一个形状,挨个改齐了。第五家管的是等孩子退场,形状略不同的地方:扫描名册、挑僵尸、入等待册、置阻塞,这几步都在共享的调度锁里办完,真正的切栈在锁外,同口径对得齐齐整整的。完成件的这一路还有前科,正文里记的是它,当年修的是入睡那一侧,这一回轮到的是唤醒那一侧。那桩案子咱们到被吞的通知一案里翻卷。
叫醒的一侧:转移,直达,同拍,幂等
睡觉的口径立完,咱们过河到叫醒那一侧。头一档是互斥锁的 unlock,r26 的真身在 :159 到 :171:
void Mutex::unlock() {
const SpinGuard kGuard(spin_);
cinux::base::safety::Check(owner_ == Scheduler::self().current(),
"mutex released by a non-owner");
Task* const kNext = waiters_.pop_head();
if (kNext != nullptr) {
owner_ = kNext;
Scheduler::self().unblock(*kNext);
return;
}
owner_ = nullptr;
}验手的那声 Check,4.2 念门闩放锁时您听过这门功课:放这把锁的必须是持有者本人。这里是 Mutex 版的同一门功课,不是主人的话锁是放不得的。您看正戏:有人排队的话,owner_ 直接改成的是队头,unblock 叫醒了人,return 就完事了,锁是不放空的。唤醒即转移的身子,老身以来是没变过的,变的是它如今跑在三句口径的世界里。第二档是信号量的 post,讲的是单位直达,真身在 sync.cpp 的 :206 到 :214:
void Semaphore::post() {
const SpinGuard kGuard(spin_);
Task* const kNext = waiters_.pop_head();
if (kNext != nullptr) {
Scheduler::self().unblock(*kNext);
return;
}
count_++;
}有人排队的话,货是不进仓的:摘队头,递的是货,叫醒的是人,return 就收工了,计数是一格没动的。没人等的话才 count_ 加一进仓。咱们跟 unlock 的转移对一对,一个心思:那边把锁划到的是队头名下,这边把货直接递到的是队头手里。第三档是完成件的 finish,讲的是判决同拍唤醒,到被吞的通知一案里细看。第四档是词上的唤醒,咱们到词上等待那里看。四档的叫醒,末了都落在同一个动词上:
void Scheduler::unblock(Task& task) {
const QueueGuard kGuard(*this);
if (task.state != TaskState::kBlocked) {
return;
}
task.state = TaskState::kReady;
base::safety::Check(task.sched_class->enqueue(task), "ready queue full at unblock");
local().notify_pending = true;
}幂等的机关就在开头两行:task 的状态不是 kBlocked,就直接返回了。头一声的叫醒,把状态置成了就绪、塞进了就绪队列。第二声再来的话,看见的已经是就绪,什么都不做。多余的叫不产生多余的队列项,口径第三句的代码面就在这几行。您再留意一层:unblock 自己进的是调度队列的锁,而真正让睡的人和叫的人错不开的,是外头各家的那把门锁。睡的人和叫的人,进的总是同一把。
窗口里藏着的还有一桩妙事,正文原话咱们照卷引:如果叫醒恰好发生在放锁之后、切栈之前,那个被叫醒的人此刻状态已是就绪,人已进了就绪队列,而他自己还站在自己的栈上。切栈的函数会去挑下一个任务,挑选的条件里本核握着的任务可取,他偏偏挑得中自己。挑中了自己,函数发现下一个恰好是当前的自己,直接返回了事,一次切换的功夫都不用,他就这么接着跑了。三行的真身住在 scheduler.cpp 的 :402 到 :404,挑出来的 next 与手里的 kPrev 是同一个。窗口里的叫醒不但不丢,还省了一趟切换,这是《睡前与叫醒的口径》那篇的收话,咱们原样收来。
醒来必须重查:判决要自己读
叫醒了,可不等于知道了结果。咱们看 Completion::wait 的全身,sync.cpp 的 :229 到 :245:
bool Completion::wait() {
const cinux::arch::IrqGuard kParkGuard;
Task* const kSelf = Scheduler::self().current();
{
const SpinGuard kGuard(spin_);
if (state_ != State::kPending) {
return state_ == State::kSuccess;
}
waiters_.push_back(*kSelf);
Scheduler::self().prepare_to_wait();
}
Scheduler::self().schedule_blocked();
{
const SpinGuard kGuard(spin_);
return state_ == State::kSuccess;
}
}门内的身子您已经认得,跟 Mutex::lock 长的是同一个形状,四家里的第三家。新鲜的是醒来那三行:schedule_blocked 一返回,人重新进了锁,把判决再读了一遍才答话。为什么必须重读?头一个缘故,叫醒声里不带内容:unblock 只说一声有了结果,结果是成是败,写在判决书上的,您得自己进锁去读。醒来直接报成功的人,判词若是 Failed 的话,他就把败案念成了胜诉。再一个缘故是门外的通例,咱们按 xv6 书页 84 转述,不是原句:它家的唤醒语义允许不相干的醒,名目叫的是 spurious wakeup,汉语的叫法是假醒,所以 sleep 的调用总裹着重查条件的循环。咱们的唤醒有同锁同拍与幂等把关,假醒是进不来门的,可重查这个习惯照旧立着:醒来的人,永远是自己进锁读一遍判决的。
一次性判决书:一辈子只宣判一回
Completion 的这件家什,4.2 的屏上点过三案,案名咱们点到为止,正戏归的是《条件等待》,票现在咱们来兑。它的脾气,正文《两种等待》那篇一句话说尽:一次性的判决书,一辈子只肯宣判一回的。出生时是 Pending 的,finish 一到的话,落成的是 Success 或者 Failed,从此是改口不改判的。finish 第二回来的时候,回的是原话,判决是一动不动的。宣判那一下还替睡觉的人办事,finish 的真身在 :216 到 :227:
bool Completion::finish(bool success) {
const SpinGuard kGuard(spin_);
if (state_ != State::kPending) {
return false;
}
state_ = success ? State::kSuccess : State::kFailed;
Task* const kNext = waiters_.pop_head();
if (kNext != nullptr) {
Scheduler::self().unblock(*kNext);
}
return true;
}咱们看:状态翻成终态的同一拍,队头摘了,人叫醒了,名目叫的是判决同拍唤醒,叫醒那一侧的第三档。门内的头一句,状态不是 kPending 的话就答 false 退回,这就是改口不改判的代码面。翻页的动词另有其名,叫的是 rearm,真身在 :257 到 :261 的那几行:
void Completion::rearm() {
const SpinGuard kGuard(spin_);
cinux::base::safety::Check(waiters_.empty(), "rearm with a waiter still parked");
state_ = State::kPending;
}翻页是有条件的,开头的那行 Check:还有睡客没醒,翻页就当场炸了。道理正文讲了,咱们把原话摘来:人家睡得正香,等的正是自己的判决,您把判决抽走重写,人家醒来读到的就是别人的案子。所以翻页之前,总得看清睡客都走了没有。
这套手艺伺候的是任务。开机的那会儿调度器还没开工,手里有的只是主流程的一条执行流,wait 的话想睡也没处睡,另一条路咱们也有,正文在那篇里也给咱们备了:进一个死循环,关了中断查一回判决,没到的话,睡到下一回的中断,醒了从头再查。睡觉那一下的真身一共就两条指令:
void EnableIrqAndHalt() {
__asm__ volatile("sti; hlt" : : : "memory");
}开了中断,然后睡它的觉。为什么非得挨着写,分成两笔就不行了?正文讲了个硬件的善意:STI 指令一执行完,处理器是不马上收中断的,还憋着的一拍,叫的是 STI shadow。sti; hlt 是挨着写的,开中断之后的头一件事就是睡觉,所以醒与睡之间是不存在缝的:中断来了,处理器从 hlt 的下一拍接着跑,睡就是原子的一步。原子这个词咱们书里至今攒了三口锅,意思各是各的,不许一口锅替三家背:4.1 的那口,test_and_set 把检查与写捆在同一拍的指令里。这一口说的是:硬件把开中断与睡觉之间那道缝封死。词上的等待还有一口,查词与进哈希桶收进的是同一把锁,靠的是锁,不是靠指令的。至于指令与内存的次序,那口深锅归的是《内存序与缓存一致性》,咱们一句交棒,就不展开了。
两条禁令正文是写在明处的,咱们照录。头一条说的是持着自旋锁的时候别调它:锁在手里,人睡了,别人来拿锁的话,就转起圈来了,能放人的人也得拿这把锁,也转起了圈,一条锁拴住的就是一串人。第二条说的是别自作聪明把它展开成恢复中断、再睡两笔,那道缝就是这么来的。这两笔咱们头一遍搓内核的时候都真踩过,脚印是留在注释里的。正文还有半句的叮嘱:醒来必须重查条件。能把 hlt 拍醒的,不止您要等的中断,时钟是每 10 毫秒响一回的,谁的线开了它都拍得醒,所以循环长的是那个样子:查了没到就睡,醒了再查。醒来就当判决到手的人,拿到的常常是时钟的问候。这句问候就是假醒在咱们机器上的真身。
睡觉这门手艺后来还伺候了块设备的值班队列,家法的两句抄自正文《一张块脸,一间值班室》的那篇:占了的格,地址不搬家。绝不过设备命令,绝不过睡眠。前一句让睡在格子里的判决永远等得着地方,后一句给值班室划了界,锁是不越设备命令的,也不越睡眠的。咱们一句带过,全本是在那卷里的。
被吞掉的完成通知:唤醒那一侧的次序
完成件的前科,咱们现在翻卷。案发在双核实弹:头一回确实绿了,回头复跑的话,间歇性地停住,崩溃是没有的,画面安静得像下班了。正文原话:首绿跟复跑打了架,这本身就是案情:窗口型的病踩不踩得着,看的全是时序,跑得越多越藏不住了。现场按规程采回来:两颗核都停在睡觉的原语上,就绪的队列里没有活可派,唯一的叶任务,一个普通的进程,阻塞在完成件的等待上,调用链从完成件的等待,经盘驱动的读块、块设备的值班队列,一路念到文件系统的路径解析。全员是睡熟的,两颗核是一起睡沉的,4.3 点的第二桩病名,现场就是这儿了。
病机在唤醒那一侧的次序里,咱们从头看。盘驱动的中断服务,从前的次序两步:头一步唤醒等待者,然后再清设备的状态。等待者是醒在另一颗核上的,手脚飞快地把完成件复位回了未决,布了下一条命令,发了出去,新命令的完成位亮起。而这颗核的服务例程才走到第二步,把状态位照单全清了,清掉的那串名字里,就有新命令刚刚亮起的完成位。新命令确实完成了,完成的通知却被旧例程的尾巴当垃圾扫走了。
修好的次序,正文记成的是四拍:取判定,清设备的状态,回读做的是确认,落在最后的才是唤醒。头一拍取的是判定,成败在这一拍已经算清了。清完了回读一次,确认真清了,回读是给设备的承诺落了地。唤醒是放在最后的,等待者醒来去布置新命令的时候,旧例程的手已经从设备上收回来了,新完成位亮起来了之后,再没有人会碰它了。您要是想问,加个轮询的兜底岂不省事,等了一会儿没等到就再查一遍。正文答了,咱们照录:兜底会把病盖住,复跑是不再停了,病根还是原来的病根,它在等下一次的时序。所以不加轮询,不删完成件的检查,只把次序摆回了正位,病根才是真的没了。
同一场风暴里还连着修了一批双核才现形的缺陷,咱们挑与睡觉接边的一桩:管道文件尾的接力。两个读者都睡了,最后的写者只发一声,头一个醒的拿走了文件尾,第二个还睡它的觉。修法正文原话:醒来的一个发现自己拿到的是等来的文件尾,就把手里的接力棒递给下一位,两位都读到零才算清了场。这一桩是在双核实弹里单独成案的,是个独立的实核,案名记在 test_smp_pipe.cpp 的 :54,名字念的是 all_parked_readers_receive_eof。两颗核都入了场,名册上确认两位读者都阻塞了才关写端,末了两位都读到零。
词上的等待:第四家,丢唤醒怎么关死
口径四家的末一家,睡得最远:不在内核的对象上,在用户世界的一个词上。白话咱们提一句,正文的那篇《一个词,二百五十六只桶》开的头:这个词还是这个值,你就把 CPU 交出来睡,有人把词改了,他来叫你。这套握手的行话叫 futex,咱们照 Linux 的门牌开门。门面名目(系统调用号、操作码、错误码)咱们一句带过,clone 与线程身份归的是第 5 部,名字咱们提过就算。
丢唤醒的经典形状,那篇讲得是最干净的,咱们照卷引:等的人查了词,值对上了,打算睡了,可叫的人赶在他挂上队列以前跑了一遍唤醒,队列里没有他的名字,白叫了,他这才安心睡下了,从此没人再叫了,这一觉就睡到了天荒。防它的办法只有一种形状,原话:查词的那一拍和进桶的那一拍,必须是原子的,跟唤醒看见的那一拍,锁的是同一把。这就是原子的第三口锅,白话再配一遍:几件事收进同一把闸的临界区里一口气办完,谁也是插不进脚的,靠的是锁,不是靠指令的。老身的等待侧,卷内是原样的,咱们整段抄来:
base::KernelError WaitOnUserWord(unsigned long long uaddr, unsigned int expected) {
Task* const kSelf = Scheduler::self().current();
FutexTable& table = shared_table();
{
const cinux::arch::IrqGuard kQuiet;
const SpinGuard kGuard(table.gate);
auto const* const kWord = reinterpret_cast<volatile const unsigned int*>(uaddr);
if (*kWord != expected) {
return base::KernelError::kWouldBlock;
}
kSelf->futex_uaddr = uaddr;
table.buckets[FutexTable::bucket_for(uaddr)].push_back(*kSelf);
}
Scheduler::self().block_current();
return base::KernelError::kOk;
}您对着三句口径读它:读词、记地址、进桶三件事住在括号里,可置阻塞的那一拍 block_current 在括号外头。挂上了桶,闸放了,标阻塞的事还没办,窗口就敞在这两拍之间的,跟互斥锁的老身同一个病。r26 的真身把这一拍挪了进去:futex.cpp 的 :74 到 :76,记地址、进桶、prepare_to_wait 连住在同一把表闸里,:78 的 schedule_blocked 才在闸外切栈。等待与唤醒掀的是同一把闸。桶管的只是把搜索收窄,二百五十六只桶的营生就这么点,真正认人的是等待者自己揣着的那个精确地址,同桶不同词的,一个误醒的也没有。于是那篇的收话在这儿成立:等的和叫的谁也错不过谁,这个窗口在结构上就没了。
词上等待这一路还压着 4.3 病名的头一份卷宗。首版的唤醒人手里只有一面停泊旗,叫了一声,旗翻了一下,收了工。可词上等的可能是两个人,叫的人明明白白递了二,他只醒了一个,另一个还在桶里睡得好好的,而能叫醒他的那一声已经喊完了。实弹一跑的话,QEMU 当场就挂死了,一点声音也没给咱们。正文原话:丢唤醒的凶处就在它的安静里,它没有崩溃的响动,没有断言的字样,它只是让一部分人永远地睡下去,所以它逼着咱们把窗口的结构想透,想透了还不够,还得数着人头一笔笔地清点。修法做的是把唤醒改成清点:进桶沿链走,地址对上的摘链、唤醒、计数,数够了才收工,一面旗的懒办法退场。
Code: Cinux 实况:旧屏回看,守卫一案两段断言
宿主的长凳上,test_sync 的九案屏 4.2 印过,本章就不重印了,您回着看。第五到第七案说的是 completion 三案,案名咱们逐字抄。头一案记在 test_sync.cpp 的 :74,全名念的是 sync: a completion finishes once and publishes its verdict,讲的就是一辈子只宣判一回,判决也是公开可读的。:83 的第二案,全名写的是 sync: a stocked completion answers wait without parking,说的是已有判决的进门读判决就走,车是不停的。:90 的第三案,全名记的是 sync: rearm returns a terminal completion to pending,终态翻回了未决,翻页的那道 Check 站岗。三案对的是三段正文,您回头对号。
调度器的那边还立着一件测试守卫,正文《睡前与叫醒的口径》立的形:守卫穿在身上,睡眠是只标状态不切栈的,宿主长凳自己踩自己的地板,演得出真实的睡眠语义,不需要真的调度器。真身是 schedule_blocked 开头的早退,scheduler.cpp 的 :387 到 :389,no_reschedule_depth 不是零的话,就回身走了。配套的状态机案,案名记在 test_scheduler.cpp 的 :248,scheduler: an explicit nested guard marks a wait without leaving the harness stack。这一案断言的是四种情形:守卫内、守卫外、嵌套守卫、内层退出外层还在,每一步的状态变化都逐拍断言。您再留意嵌套守卫:内层守卫析构了不等于解除,最外层退干净了才恢复真切换。
窗口的断言不另立案,与状态机案同住的是一案。停住切换的是守卫,prepare 之后、切栈之前的那段,测试亲手扮演那颗来叫醒的核。unblock 连喊了两声,咱们只当一声听。信号量、完成件、词上等待咱们挨个走一遍,断言这一叫丢不了、不重复、不多切,末了 sink 只响一回。正文卷记这段时叫它机内的案,真身落在宿主长凳的同一案里,咱们以码为准。这桩断言的来历照实说:审查的单子点出,从前的案子只验了凑起来的总数,这桩补的就是交错那一瞬本身。
对照:同一件事,别的机器怎么做
xv6 的第 9 章,教科书层头一回进的正是它,咱们从书页 81 记起。这门学问它家的名目,原词咱们摘:sequence coordination or conditional synchronization mechanisms,中文叫的是条件同步,《条件等待》这个章名的学名就是从这儿来的。原语配的也是一对:sleep 睡在一个条件上,wakeup 把等这个条件的全叫醒。
窗口的病它家也治,书页 82 到 83 的那段,药方与咱们不同方。它家的 sleep 要调用人递一把锁进来,这把锁是有专名的,原话咱们整句摘下:
- “That lock is called the condition lock.”
进了门之后,放这把条件锁与把自己挂进等待册的两件事,在另一把锁的护下交接,图 9.1 的题名原话摘:“Overlapping locks to avoid lost wake-up”,搭手的是两把锁,把丢唤醒的窗口搭没。咱们的方子您认得:挂队与置阻塞收进同一把锁,切栈是放在放锁之后的。得的是同一种病,下的是两副药:一副靠两把锁交接,另一副靠的是一把锁收拢,治的都是同一件事,把状态翻成阻塞的那一拍,不许叫醒的人看不见。
书页 84 的假醒,咱们在重查那里按页转述过了。书页 87 记的是一段史,与咱们前科第一刀是同一个故事,原话咱们整句摘下:
- “The original Unix kernel's sleep simply disabled interrupts, which sufficed because Unix ran on a single-CPU system. Because xv6 runs on multiprocessors, it adds an explicit lock to sleep.”
白话接着说:最早的 Unix 睡觉就是关中断,单核上是够用的。xv6 要跑的是多处理器,就给 sleep 加了明确的锁。咱们单核窄到踩不着、双核天天敞的那扇窗口,它家一句话把两头都说完了。
书页 88 的两件,咱们只提名目:条件变量这门设计的唤醒分两只手,一只手唤醒的是一个,另一只手唤醒的是全体,行话叫的是 signal 与 broadcast。用户世界还有一路信号能把睡着的人拍醒,回话里带的是一个 EINTR。那是《信号》那章的桥,过了桥再引。第 7 章的旧页添一句,书页 72 的那句,按页转述:睡眠锁的临界区里可以再拿自旋锁,自旋锁的临界区里不许拿睡眠锁,与咱们持自旋锁入睡的红线同一条心,短的住里层,长的住外层,睡觉是只能睡在最外层的。
Linux 的那头,这回有一门实打实的亲:futex 这个名字、等待落在用户词上、桶加精确地址的形状,咱们就是跟它学的,正文里照它家的门牌开的门。它家的桶有几只、路径怎么走,咱们没翻过源码,比不了的就是比不了,认亲是不比深浅的,留给将来的书。
本章留下了什么
| 术语 | 一句话口径 |
|---|---|
| 口径 | 提前说定、全内核照办的做法;本章三句:入队置阻塞同锁,切栈在放锁后,叫醒幂等 |
| 窗口 | 挂上队到切完栈之间敞着的那段缝,叫醒的人恰好跑一遍就出事 |
| 老三拍 | 入队,放锁,切栈;病不在哪一拍,在拍与拍的缝上 |
| 切栈与泊车 | 同一件事两代名:换下当前栈让下一个任务上;老卷叫泊车,今天叫切栈 |
| 唤醒即转移 | unlock 不放空锁,把锁直接划到队头名下,醒来即持有 |
| 单位直达 | post 有等人时货不进仓,越过柜台交到队头手里 |
| 判决书 | Completion 的一次性定案,Pending 落成 Success 或 Failed,改口不改判 |
| 丢唤醒 | 叫的那声没落在人身上,睡的人从此没人叫;凶处是安静 |
| 假醒 | 不相干的事把您拍醒;醒来重查条件,别把叫醒声当判决 |
押出去的票,咱们清一清。4.1 押的是三张:谱系一张连着 Mutex 的那半张,睡觉才是正路那一路的正戏,今天咱们从头演到尾。摘下、挂队、叫醒的三步占一张,三步一段兑了。延伸里报过名字的睡觉正戏一张,开门就兑了。4.2 押的是两张:两步分家里的谁粗谁细,裁断答在了三句口径那里,答完了就回。completion 的三案,实况那里咱们逐案对号。4.3 的两桩病名,销案:叫醒丢了,两份卷宗都翻了,一份是词上首版只醒一个的安静挂死,一份是完成件被吞的通知。两颗核是一起睡沉的,被吞那案的现场就是它,病根追到唤醒侧的次序,次序摆回了正位,案就结了。
边界咱们如实挂上。futex 的门面名目、join 与死亡侧、clone 与线程身份,归的是第 5 部。信号量 P/V 的立场与 badcnt 的对读,4.2 已刊过了。信号量的退役前置,4.3 已刊过了。值班队列的家什立在正文《验明正身》那一卷《一张块脸,一间值班室》的一篇,《破案:被吞掉的完成通知》一篇的现场调用链上也念到过它。写时复制、块设备的真屏障,是那篇同场记下的别的案子。管道的本体不在那篇里,正卷是正文《开门迎客》的那卷,管道一家四号在那里立了起来。等孩子退场的细节,第五家那里咱们提过就算。咱们一句没展开的,都写了去处。
往后的门,咱们指两扇。用户世界的号是另一路:睡着的人还能被信号拍醒,拍醒之后睡觉原语怎么回话,xv6 书页 88 那个 EINTR 就是接头的地方,开的是《信号》那章的门。还有的一扇在更深处:sti; hlt 的那口原子,封死的是中断的缝,不是内存的次序,指令与缓存的那口深锅,开的是《内存序与缓存一致性》的门。
练一练
三道题留给您:推演、回望、读屏各一道。
题一考的是推演。 rearm 开头那行 Check 撤了,翻页翻得自由了,您推一遍:双核的时序里,受害的是谁?他醒来读到的又是什么?
题二考的是回望。 叫醒丢了名下两份卷宗,一份在词上的等待,一份在被吞的通知。您说说:两份的病灶各在哪一侧,为什么第二份的现场是两颗核一起睡沉?
题三考的是读屏。 回 4.2 的九案屏。第四案讲的是有存货的信号量不停车。第六案讲的是 stocked completion 进门不停车。您答:两个不停车,验的东西差在哪儿?再答一问:三句口径的第一句,拿哪一件的身子当载体?
参考答案
题一:您推到的受害者,是还睡在等待册上的睡客。另一颗核上有人把判决抽走重写、布了新案,他醒来进了锁一读,读到的是别人的案子,正文《两种等待》那篇的原话,是一步不差的。新判决迟迟不来的话,他就抱着别人的未决接着睡,又是一场安静的挂死。
题二:词上的卷宗,病灶在叫的人手里:唤醒清点没做全,叫了一声就收工,该醒的两个只醒了一个,错在叫的那侧的数目。被吞的卷宗,病灶也在叫的那侧,错的是次序:唤醒在前,清状态的事在后,旧清理吞了新完成位。两份都落在叫醒的一侧,一份错的是少叫,一份错的是次序。至于现场长什么样,咱们一样一样摆:唯一会派活的叶任务等在完成件上,通知被吞了,它是不醒的。其余的任务全在等孩子退场,退场的没有一个。两颗核的就绪队列都空了,没了可派的活。叫醒丢了的后果,长成的就是这个现场。
题三的两个不停车,差的是条件。信号量的存货是计数大于零,货是还在的,取了一个走,读的是数目。完成件的存货是判决已落,一辈子只肯宣判一回的,进门读的是已定的终态。载体的一问,咱们答:互斥锁的新身子,挂队与置阻塞收进的是同一把自旋锁,sync.cpp:154 那句 prepare_to_wait 就是第一句的载体,信号量、完成件、词上的等待同款。
延伸
- xv6 书第 9 章:教科书层新开的一章,页码从 81 起单独记,本章引 81、82、83、84、87、88 六页。等孩子退场那一门在正文里是第五家,细节咱们没引,留给将来。第 7 章旧页本章添了 72。
- 正文《轮流当家:让出来的,抢出来的,排出来的》那一卷《让出去,还能被叫醒》一篇:三步、侵入式链表、唤醒即转移与单位直达的出生地,老三拍的原版全本。
- 正文《验明正身:找盘、对讲、认盘、排队》那一卷《两种等待》一篇:判决书、翻页、
sti; hlt与两条禁令的全本。同卷《一张块脸,一间值班室》,值班队列的家法。 - 正文《同一副身家,各一条栈:线程、futex 与送行的字》那一卷《一个词,二百五十六只桶》一篇:词上等待与丢唤醒的全本,安静挂死那桩案的原卷。
- 正文《开门迎客:musl、busybox 与行编辑的终端》那一卷《画像三版,窗口三处》一篇:前科两刀的全本。
- 正文《请第二颗脑子上线:APIC、蹦床与共享调度》那一卷:《睡前与叫醒的口径》是三句口径的正卷,《破案:被吞掉的完成通知》是唤醒侧次序案的原卷,两篇连着读。
- 《信号》《内存序与缓存一致性》在册待写:被拍醒的睡眠,指令与内存的次序,各归各家。