Re: [問題] multiporcessors' semophore
※ 引述《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
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
