Stack und Multithreading

[Delphi-Laie]

Hallo Delphifreunde!

Gibt es nur einen Stack im Betriebsprogramm / Prozessor, oder wird für jeden Prozeß, womöglich sogar jeden Thread ein eigener Stack angelegt und verwaltet?

Hintergrund: Ich versuchte Quicksort zu parallelisieren. Nach der ersten, der gröbsten Partitionierung der zu sortierenden Ausgangsmenge stehen beide noch zu sortierenden Teilmengen separat zu Verfügung und haben nie wieder etwas miteinander zu tun. Lassen sich demnach parallel sortieren, also jeder in einem eigenen Thread, was ich auch so programmierte. Nur benutzte ich rekursives Quicksort. Da die Ergebnisse lausig waren, kam mir der Verdacht auf, daß beide Threads ein und denselben Stack benutzen (könnten), dann kämen sich je die Stackaufrufe, konkret der Stackabbau ins Gehege.

Da Rekursionen in vielen Prozessen bzw. deren Threads vorkommen können, kann ich mir nicht vorstellen, wie das alles mit nur einem Stack fehlerfrei gelöst werden soll bzw. daß das alles nur mit einem Stack gelöst werden kann. Wie sollten die Stackinhalte dann überhaupt auf die einzelnen Prozesse / Threads wieder zurückübergeben werden?

Wenn es doch separate, threadeigene Stacks gibt, muß der Fehler woanders liegen, ich werde dann weiter probieren.

Besten Dank für Eure Aufmerksamkeit!

Viele Grüße

Delphi-Laie

[Aphton]

Threads laufen im Kontext eines übergeordneten Prozesses und teilen sich den ganzen gemappten/virtuellen Speicher, der dem Prozess zusteht.
Jeder Thread hat seinen eigenen Stack, anders würde es ja auch keinen Sinn machen.

[Delphi-Laie]

Zitat von Aphton:

Jeder Thread hat seinen eigenen Stack, anders würde es ja auch keinen Sinn machen

Ja, das ahnte ich und erarbeitete es mir auch halbwegs selbst heraus, aber nun erst ist es gewiß - dafür danke ich Dir!

[sx2008]

nicht mehr Threads erzeugen als der Prozessor an logischen Core hat!
Da jeder Thread mit voller CPU-Leistung läuft (Quicksort hat keine IO-Operationen) würden mehr Threads als Cores nur bremsen.

Ich würde es für den Anfang mal mit einer 2-Thread-Lösung für Quicksort versuchen.
Zu Beginn einmal die Partition-Funktion aus führen und dann jeweils einen Thread für jede Hälfte des zu sortierenden Arrays starten.
Jeder der beiden Threads verwendet dann rekursives Quicksort.
Dabei würde ich bei der Partitionierung beim ersten Mal die median of three Methode verwenden, damit die Daten zwischen den beiden Threads möglicht gut aufgeteilt werden.

Wenn man perfekt machen möchte braucht man einen Threadpool und einen FIFO der von allen Threads benützt wird.

[Delphi-Laie]

Alles schon durchdacht: Klar, erstmal 2 Threads zum separaten und erfolgreichen Werkeln bringen, später ggf. mehr. Und mehr Threads als Prozessor(kerne) bremst nur aus, auch klar. Mir geht es aber nicht um Geschwindigkeit, sondern um möglichst gut erkennbare Gleichzeitigkeit. Es geht um mein Projekt "Sortierkino".

Auch Dir danke!