Deadlock bei MultiCore-Systemen vermeiden

seit dem 386 gibt es
BTC  Bit test and complement
BTR  Bit test and reset
BTS  Bit test and set

http://en.wikipedia.org/wiki/X86_instruction_listings

achso, und:
http://www.scs.stanford.edu/nyu/04fa/lab/i386/LOCK.htm

Jakob schrieb:

> Was passiert denn wenn beide Cores zur IDENTISCHEN Zeit BTC,...
> aufrufen?

Wenn man es richtig macht: Einer gewinnt, der andere dreht Runden.

Ich nehme an, der Prozessor, um den es geht, ist streng geheim. Und das 
Betriebssystem ist handgehäkelt.

Jakob schrieb:

> Gabs bei den 386ern schon MultiCore- Prozessoren?

Nein, aber das dazu gehörende Bus-Locking gab es bereits anno 8086 in 
Form des LOCK Prefix, denn Multiprozessorsysteme hatte Intel bereits 
damals beim Multibus vorgesehen.

Jakob schrieb:

> Wenn ja, muss es bei synchron laufenden Cores nicht zwangsläufig ein
> Ausschlussverfahren "in Hardware" geben?

Jein. Hardware-Support ja, aber es geht auch ohne Busblockade durch die 
entsprechenden Befehle, wie sie bei x86 üblich ist. Ein Beispiel dafür, 
wie es ohne geht, bietet ARM mit den LDREX/STREX Befehlen.

Jakob schrieb:

> 1. Das bedeuted, der MultiCore wird zum SingleCore, oder?

Nein. Ein konkurrierender Core kann sich auch entschliessen, in der 
Wartezeit Hemdchen zu häkeln, statt Däumchen zu drehen. Ausserdem sind 
nur diejenigen Cores betroffen, die justament gleichzeitig um die 
Semaphore konkurrieren, der Rest kriegt rein garnix davon mit.

> 2. Wie du schon sagst, einer gewinnt. Diese Entscheidung trifft aber die
> Hardware, richtig?

Nicht wirklich. Es gewinnt der, der beim Semaphoren-Request als Erster 
durch Ziel geht, alle anderen die in der kritischen Zeit die Sema wollen 
kriegen signalisiert, dass die belegt ist. Die Hardware muss nur dafür 
sorgen, dass eine solche Semaphoren-Sequenz überhaupt möglich ist.

Jakob schrieb:

> wie wird denn bei einem Multicore-System ein Deadlock vermieden,

Die Verwendung von einzelnen Semas/Mutexen sorgt nur dann für einen 
Deadlock, wenn derjenige, der sie grad besitzt, sie nicht wieder 
freigibt.

Zu einem Deadlock kommt es beispielsweise, wenn ein Thread nacheinander 
2 Mutexe an sich zieht, bei der zweiten scheitert, und dort wartet bis 
sie frei wird. Wenn das ein zweiter Thread das Gleiche tut, nur in 
umgekehrter Reihenfolge, dann hat jeder seine Mutex und wartet ewig auf 
die andere.

Jakob schrieb:

> Das muss doch eigentlich vom Prozessor unterstützt werden, oder gibt es
> sowas wie Atomare Zugriffe, die alle anderen Cores lahmlegen?

Wenn wir mal ganz archaisch von einem einzelnen Bus ausgehen, dann löst 
sich das beispielsweise über einen ununterbrechbaren read-write 
Buszyklus (z.B. 68000, x86). Oder eben über die andere Methode mit 
speziellen Load- und Store-Befehlen, die ohne ununterbrechbare Buszyklen 
auskommt (ARM, PowerPC).

Bei heutigen Multicores mit Caches, Bus-Crossbars und Point-to-Point 
Bussen wird der tatsächliche Ablauf etwas komplexer.

Jakob schrieb:

> Wenn also CORE1 gerade LOCK ausgeführt, und CORE2 ebenfalls gerade LOCK
> ausführt, wer gewinnt dann?

Wenn damit der LOCK Präfix bei x86 gemeint ist: Wenn es nur einen Bus 
gibt, dann kann ihn stets auch nur einer verwenden. Derjenige, dem die 
Busarbitrierung eines Multimaster-Busses den Vorrang eingeräumt hat, der 
zieht seinen gelockten Befehl durch. Der andere wartet die paar Takte 
bis der Bus wieder frei ist und streitet danach erneut um den Bus.

Das ist mit oder ohne LOCK gleich. Der einzige Unterschied ist, dass mit 
LOCK mehrere Buszyklem am Stück durchlaufen, ohne dass ein anderer 
Busmster reinrutschen kann.