Transcript
Algorithmen und Programmierung IV: Nichtsequentielle Programmierung
Robert Tolksdorf Freie Universität Berlin
Überblick
Inhalt
• Prozessprioritäten • Auswahlstrategien • Alterungsmechanismen
3
4 Ablaufsteuerung
Ablaufsteuerung
• Ablaufsteuerung (scheduling) = • Zuteilung von Betriebsmitteln (resources) • wieder verwendbaren oder • verbrauchbaren
an Prozesse, z.B. • • • •
Prozessor (wieder verwendbar), Speicher (wieder verwendbar), Nachrichten (verbrauchbar), Ereignisse (verbrauchbar)
5
4.1 Prozeßprioritäten
• Def.:
Priorität eines Prozesses = einem Prozess (task, thread, …) zugeordnetes Attribut, üblicherweise eine natürliche Zahl, das zur Entscheidung über die Zuteilung von Betriebsmitteln herangezogen wird.
• Priorität wird einem Prozess bei der Erzeugung (explizit oder implizit) zugeteilt und kann eventuell programmgesteuert verändert werden.
6
Beispiel Java
• Java: • Thread.MIN_PRIORITY • Thread.NORM_PRIORITY • Thread.MAX_PRIORITY
= 1 = 5 = 10
• Der Urprozess (main thread) hat die Priorität 5. • Ein Thread vererbt seine Priorität an seine Kinder. • Abfragen der Priorität mit • Ändern der Priorität mit
int getPriority() void setPriority(int p)
7
Beispiel Java
• Die JVM kann bei der Zuteilung von Prozessorkapazität an die Threads die Prioritäten berücksichtigen, muss aber nicht.
• Typische, sinnvolle Prioritätenvergabe: • 2-3 • 4-6 • 7-9
Rechnen Ein/Ausgabe schnelle Ein/Ausgabe (Interaktion, harte Realzeit-Anforderungen)
• Nicht vergessen: im Mehrprozessbetrieb erhält die JVM bereits vom Betriebssystem nur ein Teil der Prozessorkapazität!
8
Experiment [Mario Jeckle]
• Programm startet 10 Threads mit unterschiedlichen
Prioritäten • Jeder Thread zählt eine Variable bis zu einer Obergrenze (10000000) hoch • Zeit zwischen Start und Termination der Threads wird gemessen
• Vermutung: • Thread mit höchster Priorität braucht am wenigsten Zeit • Thread mit niedrigster Priorität braucht am meisten Zeit
• [http://www.jeckle.de/vorlesung/javaThreads/script.html#adv]
9
SunOS 5.10 • • • • • • • • • •
Thread Thread Thread Thread Thread Thread Thread Thread Thread Thread
with with with with with with with with with with
priority priority priority priority priority priority priority priority priority priority
10 took 3152ms 9 took 3014ms 8 took 2716ms 7 took 2905ms 6 took 3249ms 5 took 3479ms 4 took 3557ms 3 took 1725ms 2 took 1968ms 1 took 1580ms
• Java(TM) 2 Runtime Environment, Standard Edition (build •
1.5.0_11-b03) Java HotSpot(TM) Client VM (build 1.5.0_11-b03, mixed mode, sharing)
10
Debian GNU/Linux 2.6.14.2 • • • • • • • • • •
Thread Thread Thread Thread Thread Thread Thread Thread Thread Thread
with with with with with with with with with with
priority priority priority priority priority priority priority priority priority priority
10 took 184ms 9 took 160ms 8 took 144ms 7 took 292ms 6 took 501ms 5 took 489ms 4 took 430ms 3 took 375ms 1 took 642ms 2 took 337ms
• Java(TM) 2 Runtime Environment, Standard Edition (build •
1.5.0_06-b05) Java HotSpot(TM) Client VM (build 1.5.0_06-b05, mixed mode, sharing)
11
Win32 Test, Obergrenze 10000000
• • • • • • • • • •
Thread Thread Thread Thread Thread Thread Thread Thread Thread Thread
with with with with with with with with with with
priority priority priority priority priority priority priority priority priority priority
10 took 47ms 9 took 47ms 8 took 46ms 7 took 63ms 6 took 63ms 5 took 46ms 4 took 109ms 3 took 47ms 2 took 47ms 1 took 62ms
• Java(TM) SE Runtime Environment (build 1.6.0_01-b06) • Java HotSpot(TM) Client VM (build 1.6.0_01-b06, mixed mode, sharing)
12
Win32 Test, Obergrenze 500000000
• • • • • • • • • •
Thread Thread Thread Thread Thread Thread Thread Thread Thread Thread
with with with with with with with with with with
priority priority priority priority priority priority priority priority priority priority
10 took 2531ms 9 took 2547ms 8 took 5156ms 7 took 2828ms 5 took 3532ms 6 took 8140ms 4 took 5453ms 3 took 9437ms 2 took 9234ms 1 took 15718ms
• Java(TM) SE Runtime Environment (build 1.6.0_01-b06) • Java HotSpot(TM) Client VM (build 1.6.0_01-b06, mixed mode, sharing)
13
Java ...
•
Die Verwendung von Prioritäten ist völlig der Implementierung der JVM überlassen 1. praktiziert entweder eigenes Threading (user-level) 2. oder nutzt Kernel-Level Threading (falls vorhanden) (Beispiele: Windows, Solaris) 3. oder nutzt schwergewichtige Prozesse mit gemeinsamen Segmenten (Beispiel: Linux)
14
Eigenes Threading in Java
• In verschiedenen (alten) Java Implementierungen wird nicht auf unterliegende Threads des Betriebssystems zurückgegriffen • Die JVM ist ein Prozess mit einer bestimmten Priorität aus Betriebssystemsicht
• Höchste JVM Priorität bewirkt keine hohe Systempriorität! JVM JT1
JT2
JT3
OS
OT1
CPU
CPU 15
Threading in Java Priorisierte präemptive Auswahl
• Einfaches Modell („green threading“, JDK 1.0) • Wenn ein Thread mit höherer Priorität als der aktuell laufende ausführbereit wird, erhält er Vorrang und wird ausgeführt („preemption“, Bevorrechtigung, präemtiv) • Der Thread läuft bis er • Thread.sleep() macht • Eine Sperre mit synchronized haben will (also im Waitset landet) • Bei I/O blockiert • yield() aufruft • Terminiert
• Threads gleicher Priorität werden der Reihe nach bevorrechtigt (Round-Robin)
16
Threading in Java Timeslicing
• Zeitscheibenverfahren:
Ein laufender Thread wird nach einer festen Zeitspanne unterbrochen und der nächste wird nach priorisierter präemptiver Auswahl ausgeführt
priorisiert präemptiv
… mit Zeitscheiben
[Patrick Niemeyer, Josh Peck. Exploring Java. O'Reilly 1998] 17
Betriebssystem Threads in Java
• Moderne Java Implementierungen nutzen Threads die vom Betriebssystem angeboten werden
• Solaris – Pools
Win32 - Bindung JVM
JT1
OT1
CPU
JT2
OT2
JT3
OT3
CPU
JVM JT1
OS
OT1
CPU
JT2
OT2
JT3
OT3
OS
CPU
18
Betriebssystem Threads in Java
• Welche Priorität haben die Betriebssystem Threads? • Win32, JDK 1.4:
• [http://www.jeckle.de/vorlesung/javaThreads/script.html#adv]
19
Prioritätenvergabe vs. Synchronisation
• Achtung 1:
Prioritätenvergabe ist kein Ersatz für Synchronisation! • Achtung 2: Gefahr der Prioritätsumkehr (priority inversion), z.B. bei Einprozessorsystem: • 3 Prozesse A, B, C mit abfallenden Prioritäten a,b,c • C betritt kritischen Abschnitt k, weckt B und wird von B verdrängt, d.h. belegt weiterhin k; • B weckt A und wird von A verdrängt, • A blockiert beim Eintrittsversuch in k; • solange B nicht blockiert, hat A keine Chance!
• Lösungstechnik: spezielle Sperroperationen, die für temporäre Prioritätserhöhung sorgen.
20
4.2 Auswahlstrategien
• Problem:
Wenn mehrere Prozesse auf Betriebsmittelzuteilung bzw. auf ein bestimmtes Ereignis warten (mit when, wait, P, join, ...) und beim Eintreten des Ereignisses nicht alle aufgeweckt werden können/sollen, welche ?
• ¼ Auswahlstrategie (scheduling policy)
21
Fairness • Def.: Eine Auswahlstrategie heißt fair, wenn jedem wartenden
•
Prozess garantiert ist, dass ihm nicht permanent und systematisch andere Prozesse vorgezogen werden. (Auch: Von einer endlichen Anzahl nebenläufiger Prozesse ist in einem unendlichen Betriebsablauf jeder einzelne unendlich oft aktiv) Eine Auswahlstrategie heißt streng fair (strong fairness, compassion): Wenn ein Prozess blockiert, kann eine obere Schranke für die Anzahl der Prozesse angegeben werden, die ihm vorgezogen werden; • (Auch: Wenn ein Prozess unendlich oft ausführbereit ist, wird er unendlich oft aktiviert)
• Eine Auswahlstrategie heißt schwach fair (weak fairness, justice): sonst
• (Auch: Wenn ein Prozess ausführbereit bleibt, wird er unendlich oft aktiviert) 22
Unfairness
• Bei unfairer Auswahlstrategie droht den Prozessen unbestimmte Verzögerung (indefinite delay, starvation)
• Achtung:
In Java gibt es keinerlei Fairness-Garantien !
23
Faire Auswahlstrategien
•
Typische Auswahlstrategien und ihre Fairness: 1. zufällig 2. der Reihe nach (first-come, first-served, FCFS, first-in, first-out, FIFO) 3. prioritätsgesteuert 4. anwendungsspezifisch
schwach fair streng fair
unfair (je nachdem)
24
4.2.1 Anpassung der Auswahlstrategie
• Ausgangslage:
Verfügbare Sprachkonstrukte verfolgen eine unpassende Strategie
• Beispiele: • strenge Fairness benötigt, aber in Java nicht garantiert • Semaphore mit FCFS verfügbar, aber Auswahl sollte eigentlich prioritätsgesteuert erfolgen • anwendungsspezifische Strategie benötigt
25
Anpassung der Auswahlstrategie
•
Konsequenz: im Eigenbau
1. entweder wieder verwendbare Varianten der
Synchronisationskonstrukte bereitstellen ¼ 4.2.1.1 2. oder Ad-hoc-Strategie programmieren ¼ 4.2.1.2
26
4.2.1.1 Prioritätsgesteuerte Semaphore interface ISemaphore { // scheduling unspecified void P(); void V(); } class Semaphore implements ISemaphore { // FCFS ... } class PrioSemaphore implements ISemaphore { public PrioSemaphore(int init) { count = init; } private int count; private final Semaphore mutex = new Semaphore(1); private final PrioSet prios = new PrioSet();
27
Prioritätsgesteuerte Semaphore class PrioSet { // set of pairs (int, Semaphre) ..... public void add(int prio, Semaphore sema) {...} // adds pair (prio,semaphore) public Semaphore rem() {...} // delivers semaphore with highest priority // and removes entry }
28
Prioritätsgesteuerte Semaphore public void P() { // this is the modified P mutex.P(); count--; if(count>=0) mutex.V(); else { Semaphore ready = new Semaphore(0); prios.add(Thread.currentThread().getPriority(), ready); mutex.V(); ready.P(); } }
29
Prioritätsgesteuerte Semaphore public void V() { // this is the modified V mutex.P(); count++; if(count<=0) { Semaphore ready = prios.rem(); ready.V(); } mutex.V(); } }
• Beachte: 1. Die Semaphore ready sind private Semaphore, d.h. bei ihnen blockiert jeweils höchstens ein Thread. 2. Die kritischen Abschnitte (mutex) sind kurz genug, dass sie keinen Engpass darstellen. ¼ Daher ist es irrelevant, welche Auswahlstrategie von Semaphore praktiziert wird. 30
Wahl einer Sperroperation
• langfristiges Sperren realer Betriebsmittel:
Auswahlstrategie wählen, gegebenfalls selbst implementieren
• kurzfristiges Sperren kritischer Abschnitte: Auswahlstrategie irrelevant
• sofern kein Engpass bei der Benutzung der Ressource bzw. des kritischen Abschnitts vorliegt ! • sonst: Entwurf revidieren – lange Prozesswarteschlangen sind in jedem Fall unsinnig – wie auch immer die Auswahl praktiziert wird.
31
4.2.1.2 Anforderungsbezogene Auswahl
• bei jeder Art von Anforderung mehrerer Ressourcen z.B. • verallgemeinerte P/V-Operationen (3.3.1) • request(n) , release(n) • und ähnliche
• Häufig ist Effizienz wichtiger als Fairness, z.B. • gute Ressourcen-Ausnutzung • kurze Reaktionszeiten
32
Anforderungsbezogene Auswahl
• Beispiele für effizienzorientierte Auswahlstrategien bei request(n)/ release(n):
• SRF (smallest request first):
die kleinsten Anforderungen sollen vorrangig bedient werden • LRF (largest request first): die größten Anforderungen sollen vorrangig bedient werden • (jedenfalls nicht die, welche am längsten warten; weitere Alternativen sind möglich.)
33
Anforderungsbezogene Auswahl
• LRF mit Verwendung von PrioSet (4.2.1.1) mit Operationen
• public int top(int limit) • liefert den höchsten prio-Wert im PrioSet , der limit nicht übersteigt (0, falls kein solcher vorhanden)
• public Semaphore rem(int limit) (modifiziert) • liefert das zugehörige Semaphor und löscht den Eintrag
34
Anforderungsbezogene Auswahl class Resources {// LRF – largest request first public Resources(int init) { avail = init; } private int avail; private final PrioSet claims = new PrioSet(); public void request(int claim) { Semaphore ready; synchronized(this) { if (claim<=avail) { avail -= claim; return; } else { ready = new Semaphore(0); claims.add(claim,ready); } } ready.P(); } 35
Anforderungsbezogene Auswahl public synchronized void release(int free) { avail += free; do { int claim = claims.top(avail); if(claim == 0) return; else { avail -= claim; claims.rem(avail).V(); } } while(true); } }
• Beachte: • Das Blockieren in request muß außerhalb des kritischen Abschnitts erfolgen • In release werden i.a. gezielt mehrere Threads aufgeweckt • Durch Modifikation der Klasse PrioSet können verschiedene Strategien realisiert werden 36
4.2.2 Fairness durch Alterungsmechanismen • Gegensätzliche Ziele bei Auswahlstrategien: • • • •
Ziel: Fairness: Beispiel: Kriterium:
Effizienz unfair SRF Anforderungen
Gleichbehandlung streng fair FIFO Wartezeit
• Spektrum von Kriterien: • Anforderungen
Wartezeit
anforderungsorientiert + Alterungsmechanismus (ageing) 37
Alterungsmechanismen
• Beispiel:
Alterungsmechanismus für SRF: • Auswahl nach Rangordnung 1,2,3,... (hoher Rang = kleine Rangzahl) • Rang = Anforderung + Malus • Malus = Zeitpunkt des request, gemessen in Anzahl der begonnenen requests • Einem release wird genau dann stattgegeben, wenn die Anforderung erfüllt werden kann und die kleinste Rangzahl hat. (Bei Gleichrangigkeit zweier erfüllbarer Anforderungen...)
38
Alterungsmechanismen • Buchführung über Anforderungen und Ränge mittels class Ranking { // set of triples (int rank, int claim, EVENT e) ..... public void add(int rank, int claim, EVENT e){...} // adds triple (rank,claim,e) public EVENT rem() {...} // delivers event with highest rank // and removes entry (if any, else null) public int firstRank() {...} // delivers highest rank (if any, else MAX) public int firstClaim() {...} // delivers corresponding claim (or MAX) } 39
Beispiel-Szenario Thread request release counter 0 p q r s t p q u q s
1 4 4 1 1
1 2 3 4 5
added
6 1 1
available 5
p q
4 0 0 0 0
s t
0 2 2 3 0
(7,4,R) (5,1,S) (6,1,T)
1 3 2
grantee
(8,2,U) r
40
Alterungsmechanismen MONITOR Resources { // SRF, with ageing // Monitor and Events! public Resources(int n) {available = n;} protected int available; protected int counter; protected final Ranking ranking = new Ranking(); public void release(int n) { available += n; tryWakeup(); } protected void tryWakeup() { if(ranking.firstClaim() <= available){ available -= ranking.firstClaim()); ranking.rem().SIGNAL(); } } // any version of SIGNAL does the job 41
Alterungsmechanismen public void request(int claim) { counter++; int rank = claim + counter; if (rank <= ranking.firstRank() && claim <= available) { available -= claim; return; } else { EVENT ready = new EVENT(); ranking.add(rank,claim,ready); ready.WAIT(); tryWakeup(); } } } // end monitor
42
Alterungsmechanismen
• Flexible Positionierung im Spektrum der Strategien: • anstelle von rank = claim + counter • Verwendung von rank = claim + k*counter
• k ∈ [0, m] (m = maximal mögliche Anforderung) ermöglicht Tuning • k = 0 : SRF • k = m: FIFO • ranki < ranki+1 für zwei aufeinanderfolgende requests
43
Zusammenfassung
Zusammenfassung
• Prozessprioritäten • Auswahlstrategien • Fairness
• Alterungsmechanismen
45
