yinfeng 最近的时间轴更新 yinfeng 最近的时间轴更新 |
yinfengV2EX 第 240638 号会员，加入于 2017-07-16 18:40:42 +08:00 |
yinfeng 最近回复了
2023-08-11 15:27:24 +08:00 回复了 CC11001100 创建的主题 › 程序员 › [技术方案讨论] 如何仅使用 set、get 操作实现一个锁？ |
这是非常经典的计科问题，使用任意多个，有读和写方法的，顺序一致的，原子寄存器实现互斥锁。
简单看了下 fast-mutex 用的算法，它试图用两个 SC 的原子寄存器去实现 n 个线程的互斥，假设了一个线程的延迟执行一定能使其他线程执行完 lock 的代码。问题就是如果无视这个假设很容易就能构造反例。
如果非要去做这样的事，有挺多算法可以选择，只是都很慢。最经典的就是，两线程可以用 Peterson lock ，Peterson lock 可以推广到 n 个线程叫作 filter lock ，还有具有公平性的 bakery 算法。
https://en.wikipedia.org/wiki/Peterson%27s_algorithm
https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm
简单看了下 fast-mutex 用的算法，它试图用两个 SC 的原子寄存器去实现 n 个线程的互斥，假设了一个线程的延迟执行一定能使其他线程执行完 lock 的代码。问题就是如果无视这个假设很容易就能构造反例。
如果非要去做这样的事，有挺多算法可以选择，只是都很慢。最经典的就是，两线程可以用 Peterson lock ，Peterson lock 可以推广到 n 个线程叫作 filter lock ，还有具有公平性的 bakery 算法。
https://en.wikipedia.org/wiki/Peterson%27s_algorithm
https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm
Select Language