※ 引述《skyracer (耶125751563)》之铭言： : 请问一下 : 在多CPU的环境下 : 纯软的semophore机制怎麽实做的呢? : (i.e. wait signal是纯软实作 非atomic, 因为多CPU架构下不好用硬体实作之) : 我看恐龙书是说改成如下架构 ==> : busy-waiting entry section(such as Bakery Algorithm's or Peterson Algorithm's) : wait : CS : signal : exit section : remaining CS Peterson Algorithm 是用在 CS 的 mutual exclusive lock , 只限两个 process, 不保证三个以上会正确. 三个以上的是 Eisenberg and McGuire's Algorithm. semaphore 指的是 Dijkstra 提议的 P(wait) & V(signal) operation 及其 配合 dispatcher/scheduler 提供的 block/wake-up 架构. 这是较好使用的 工具, 但其中有些动作, 如 s=s+1; s=s-1; 这种 update operation 需要 lock 或不可分割的 atomic operation 支援. 软体 lock 的运作动作, 都是假设 多个 processor 对 记忆体 的多个读或 写 不会同时发生. 但在各有 local cache 与 multi-port memory multi-path 的情况下, 此假设必需要被维持或考虑. 也就是硬体要支援. 例如 X86 若在多处理机下, swap 指令, 必须配合 lock prefix 由 processor 送出讯号给配合的硬体去锁住共用的 bus, 若没有硬体支援, 这事就不可能完 全正确. : 如此便可以不需要用硬体实作wait, signal : 但如此一来wait, signal也不需要了吧....=_=" : 前面插上Bakery algorithm加上semophore有什麽好处吗?. Bakery algorithm 是分散式系统的方法, 是基於 processor 有事先分配, 且 各个有不同的 ID 机号, 可用於 full order 排序(或分出绝对大小). 硬体或软体都是使用同类的演算法与假设, 譬如两个 CPU 不能 "同时" 写进同 一个位址的同一个记忆体, 这基本上就是要有同时写时必须有的 "互斥" 机制. 硬体的支援是效率的需要, 以原始简单的机制当底层, 软体则是基於底层增加复 杂动作以提供较好用够弹性的工具, 不可能在没有基本的硬体机制支援下, 只靠 原有欠缺基本假设支持的软体指令, 就能合成 "必要" 的功能. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.115.4.12