Scheduling - Revision history

Butzek: ClockRes advise

2007-01-31T09:00:53Z

ClockRes advise

← Older revision		Revision as of 09:00, 31 January 2007
Line 44:		Line 44:

	Einen weitereren Vorteil einer höheren Frequenz zeigt Abbildung 7. Die Billing ratio zeigt das Verhältnis der durch den Scheduler berechneten Zeit durch die wirklich genutzte Zeit, Missed quanta hingegen den prozentualen Anteil der nicht durch den Scheduler berechneten Zeitquanten. Da der Scheduler ja nur mit einer bestimmten Frequenz läuft, muss er annehmen, dass der Prozess, der gerade die Ressource nutzt, die Ressource auch die gesamte Zeit bis zum vorherigen Tick genutzt hat, auch wenn das nur sehr selten wirklich der Fall ist. Auffällig hierbei ist, dass trotz einer extrem hohen Missed quanta Wert, sich die Billing Ratio nahe 1 befindet. Das zeigt den guten Ausgleich zu der hohen Überbewertung der kurzen Quanta, die direkt auf einem Tick des Schedulers liegen. Der niedrige Wert der Billing ration des X Servers liegt daran, dass er mit der Systemuhr synchron läuft, also direkt nach dem Scheduler Tick an der Reihe ist, und somit fast nie für seine genutzte Rechenzeit ''bezahlen'' muss. Durch eine Erhöhung der Systemuhr Frequenz sinkt also die Zahl der nicht bewerteten Quanten, ebenso wie die Überbewertung kleiner Quanten sinkt, womit sich die Billing ratio weiter an 1 annähert.		Einen weitereren Vorteil einer höheren Frequenz zeigt Abbildung 7. Die Billing ratio zeigt das Verhältnis der durch den Scheduler berechneten Zeit durch die wirklich genutzte Zeit, Missed quanta hingegen den prozentualen Anteil der nicht durch den Scheduler berechneten Zeitquanten. Da der Scheduler ja nur mit einer bestimmten Frequenz läuft, muss er annehmen, dass der Prozess, der gerade die Ressource nutzt, die Ressource auch die gesamte Zeit bis zum vorherigen Tick genutzt hat, auch wenn das nur sehr selten wirklich der Fall ist. Auffällig hierbei ist, dass trotz einer extrem hohen Missed quanta Wert, sich die Billing Ratio nahe 1 befindet. Das zeigt den guten Ausgleich zu der hohen Überbewertung der kurzen Quanta, die direkt auf einem Tick des Schedulers liegen. Der niedrige Wert der Billing ration des X Servers liegt daran, dass er mit der Systemuhr synchron läuft, also direkt nach dem Scheduler Tick an der Reihe ist, und somit fast nie für seine genutzte Rechenzeit ''bezahlen'' muss. Durch eine Erhöhung der Systemuhr Frequenz sinkt also die Zahl der nicht bewerteten Quanten, ebenso wie die Überbewertung kleiner Quanten sinkt, womit sich die Billing ratio weiter an 1 annähert.

			Zum Auslesen der System Clock unter Windows gibt es ein kleines Tool von Sysinternals: [http://www.microsoft.com/technet/sysinternals/Utilities/ClockRes.mspx ClockRes], welches mir bei WinXP SP2 eine Frequenz von 64 Hz und bei Windows 2000 SP4 100Hz ausgibt.

Butzek: final?

2007-01-31T07:01:27Z

final?

← Older revision		Revision as of 07:01, 31 January 2007
Line 43:		Line 43:
	Also stellt sich die Frage, warum man die Frequenz der Systemuhr nicht mit steigender Frequenz der Hardwareuhr erhöht hat - erst mit dem Linux Kernel 2.6 wurde sie auf 250 Hz angehoben. Die Antwort damals war einfach der steigende Overhead, der zwangsläufig bei einer erhöhten Frequenz anfällt. Eine Untersuchung dessen zeigt jedoch, siehe Abbildung 6, dass der höhere Aufwand durch Rechenzeit und verlorene Caches relativ klein bei aktuellen Rechensystemen ausfällt, bei einer Steigerung auf 1000Hz sogar fast zu vernachlässigen ist.		Also stellt sich die Frage, warum man die Frequenz der Systemuhr nicht mit steigender Frequenz der Hardwareuhr erhöht hat - erst mit dem Linux Kernel 2.6 wurde sie auf 250 Hz angehoben. Die Antwort damals war einfach der steigende Overhead, der zwangsläufig bei einer erhöhten Frequenz anfällt. Eine Untersuchung dessen zeigt jedoch, siehe Abbildung 6, dass der höhere Aufwand durch Rechenzeit und verlorene Caches relativ klein bei aktuellen Rechensystemen ausfällt, bei einer Steigerung auf 1000Hz sogar fast zu vernachlässigen ist.

	~~Weitere~~ ~~Vorteile~~ einer höheren Frequenz zeigt Abbildung 7. Die Billing ratio zeigt das Verhältnis der durch den Scheduler berechneten Zeit durch die wirklich genutzte Zeit, Missed quanta hingegen den prozentualen Anteil der nicht durch den Scheduler berechneten Zeitquanten. Da der Scheduler ja nur mit einer bestimmten Frequenz läuft, muss er annehmen, dass der Prozess, der gerade die Ressource nutzt, die Ressource auch die gesamte Zeit bis zum vorherigen Tick genutzt hat, auch wenn das nur sehr selten wirklich der Fall ist. Auffällig hierbei ist, dass trotz einer extrem hohen Missed quanta Wert, sich die Billing Ratio nahe 1 befindet. Das zeigt den guten Ausgleich zu der hohen Überbewertung der kurzen Quanta, die direkt auf einem Tick des Schedulers liegen. Der niedrige Wert der Billing ration des X Servers liegt daran, dass er mit der Systemuhr synchron läuft, also direkt nach dem Scheduler Tick an der Reihe ist, und somit fast nie für seine genutzte Rechenzeit ''bezahlen'' muss.		Einen weitereren Vorteil einer höheren Frequenz zeigt Abbildung 7. Die Billing ratio zeigt das Verhältnis der durch den Scheduler berechneten Zeit durch die wirklich genutzte Zeit, Missed quanta hingegen den prozentualen Anteil der nicht durch den Scheduler berechneten Zeitquanten. Da der Scheduler ja nur mit einer bestimmten Frequenz läuft, muss er annehmen, dass der Prozess, der gerade die Ressource nutzt, die Ressource auch die gesamte Zeit bis zum vorherigen Tick genutzt hat, auch wenn das nur sehr selten wirklich der Fall ist. Auffällig hierbei ist, dass trotz einer extrem hohen Missed quanta Wert, sich die Billing Ratio nahe 1 befindet. Das zeigt den guten Ausgleich zu der hohen Überbewertung der kurzen Quanta, die direkt auf einem Tick des Schedulers liegen. Der niedrige Wert der Billing ration des X Servers liegt daran, dass er mit der Systemuhr synchron läuft, also direkt nach dem Scheduler Tick an der Reihe ist, und somit fast nie für seine genutzte Rechenzeit ''bezahlen'' muss. Durch eine Erhöhung der Systemuhr Frequenz sinkt also die Zahl der nicht bewerteten Quanten, ebenso wie die Überbewertung kleiner Quanten sinkt, womit sich die Billing ratio weiter an 1 annähert.

Butzek: Clock 3

2007-01-31T06:53:16Z

Clock 3

← Older revision		Revision as of 06:53, 31 January 2007
Line 41:		Line 41:
	Die Beschränkung auf 100 Hz kann z.B. Auswirkung auf die erreichte Framerate des Xine MPEG viewer haben, und nicht die erwarteten 60 Bilder liefern, siehe Abbildung 4. Die Erklärung dazu liefert das nächste Bild. Xine zeigt ein Frame nur, wenn es bis zur Häfte der Zeit bis das nächste Frame erwartet wird, geliefert wird. Je nachdem wann das erste Frame geliefert wird, fällt in 50% aller Fälle 1/3 der Bilder unter den Tisch, was zu einer Framerate von nur 40 Bildern/s führt.		Die Beschränkung auf 100 Hz kann z.B. Auswirkung auf die erreichte Framerate des Xine MPEG viewer haben, und nicht die erwarteten 60 Bilder liefern, siehe Abbildung 4. Die Erklärung dazu liefert das nächste Bild. Xine zeigt ein Frame nur, wenn es bis zur Häfte der Zeit bis das nächste Frame erwartet wird, geliefert wird. Je nachdem wann das erste Frame geliefert wird, fällt in 50% aller Fälle 1/3 der Bilder unter den Tisch, was zu einer Framerate von nur 40 Bildern/s führt.

	Also stellt sich die Frage, warum man die Frequenz der Systemuhr nicht mit steigender Frequenz der Hardwareuhr erhöht hat - erst mit dem Linux Kernel 2.6 wurde sie auf 250 Hz angehoben. Die Antwort damals war einfach der steigende Overhead, der zwangsläufig bei einer erhöhten Frequenz anfällt. Eine Untersuchung dessen zeigt jedoch, siehe Abbildung 6, dass der höhere ~~Bedarf~~ ~~von~~ Rechenzeit relativ klein bei aktuellen Rechensystemen ausfällt, bei einer Steigerung auf 1000Hz sogar fast zu vernachlässigen ist.		Also stellt sich die Frage, warum man die Frequenz der Systemuhr nicht mit steigender Frequenz der Hardwareuhr erhöht hat - erst mit dem Linux Kernel 2.6 wurde sie auf 250 Hz angehoben. Die Antwort damals war einfach der steigende Overhead, der zwangsläufig bei einer erhöhten Frequenz anfällt. Eine Untersuchung dessen zeigt jedoch, siehe Abbildung 6, dass der höhere Aufwand durch Rechenzeit und verlorene Caches relativ klein bei aktuellen Rechensystemen ausfällt, bei einer Steigerung auf 1000Hz sogar fast zu vernachlässigen ist.

			Weitere Vorteile einer höheren Frequenz zeigt Abbildung 7. Die Billing ratio zeigt das Verhältnis der durch den Scheduler berechneten Zeit durch die wirklich genutzte Zeit, Missed quanta hingegen den prozentualen Anteil der nicht durch den Scheduler berechneten Zeitquanten. Da der Scheduler ja nur mit einer bestimmten Frequenz läuft, muss er annehmen, dass der Prozess, der gerade die Ressource nutzt, die Ressource auch die gesamte Zeit bis zum vorherigen Tick genutzt hat, auch wenn das nur sehr selten wirklich der Fall ist. Auffällig hierbei ist, dass trotz einer extrem hohen Missed quanta Wert, sich die Billing Ratio nahe 1 befindet. Das zeigt den guten Ausgleich zu der hohen Überbewertung der kurzen Quanta, die direkt auf einem Tick des Schedulers liegen. Der niedrige Wert der Billing ration des X Servers liegt daran, dass er mit der Systemuhr synchron läuft, also direkt nach dem Scheduler Tick an der Reihe ist, und somit fast nie für seine genutzte Rechenzeit ''bezahlen'' muss.

Butzek: Clock tuning 2

2007-01-31T06:21:42Z

Clock tuning 2

← Older revision		Revision as of 06:21, 31 January 2007
Line 31:		Line 31:

	== Clock interrupt rate tuning ==		== Clock interrupt rate tuning ==

			[[Image:Scheduling_4.png\|thumb\|Abbildung 4: System Clock 100Hz vs 1000Hz]]
			[[Image:Scheduling_7.png\|thumb\|Abbildung 5: Timing]]
			[[Image:Scheduling_5.png\|thumb\|Abbildung 6: Overhead]]
			[[Image:Scheduling_6.png\|thumb\|Abbildung 7: Billing]]

	Dies ist kein weiteres Scheduling Verfahren, sondern eine Technik, die das bisherige Scheduling mit einer winzigen Änderung im Betriebssystem effizienter machen soll. Dabei geht es um die System clock, die vom Betriebssystem gesetzt und als timer interrupt rate verwendet wird, also dessen Reaktionszeit definiert. Diese Uhr lief bis vor einigen Jahren seit knapp 3 Jahrzehnten mit 100 Hz, was damals bei 1-MHz-Computern 10.000 Instruktionen pro Tick entsprach, heute jedoch schon mehr als 10 Millionen Instruktionen sind.		Dies ist kein weiteres Scheduling Verfahren, sondern eine Technik, die das bisherige Scheduling mit einer winzigen Änderung im Betriebssystem effizienter machen soll. Dabei geht es um die System clock, die vom Betriebssystem gesetzt und als timer interrupt rate verwendet wird, also dessen Reaktionszeit definiert. Diese Uhr lief bis vor einigen Jahren seit knapp 3 Jahrzehnten mit 100 Hz, was damals bei 1-MHz-Computern 10.000 Instruktionen pro Tick entsprach, heute jedoch schon mehr als 10 Millionen Instruktionen sind.

			Die Beschränkung auf 100 Hz kann z.B. Auswirkung auf die erreichte Framerate des Xine MPEG viewer haben, und nicht die erwarteten 60 Bilder liefern, siehe Abbildung 4. Die Erklärung dazu liefert das nächste Bild. Xine zeigt ein Frame nur, wenn es bis zur Häfte der Zeit bis das nächste Frame erwartet wird, geliefert wird. Je nachdem wann das erste Frame geliefert wird, fällt in 50% aller Fälle 1/3 der Bilder unter den Tisch, was zu einer Framerate von nur 40 Bildern/s führt.

			Also stellt sich die Frage, warum man die Frequenz der Systemuhr nicht mit steigender Frequenz der Hardwareuhr erhöht hat - erst mit dem Linux Kernel 2.6 wurde sie auf 250 Hz angehoben. Die Antwort damals war einfach der steigende Overhead, der zwangsläufig bei einer erhöhten Frequenz anfällt. Eine Untersuchung dessen zeigt jedoch, siehe Abbildung 6, dass der höhere Bedarf von Rechenzeit relativ klein bei aktuellen Rechensystemen ausfällt, bei einer Steigerung auf 1000Hz sogar fast zu vernachlässigen ist.



	== Quellen ==		== Quellen ==

Butzek: Clock 1

2007-01-24T12:25:34Z

Clock 1

← Older revision		Revision as of 12:25, 24 January 2007
Line 3:		Line 3:
	== Einführung ==		== Einführung ==

	Scheduling ist generell die Zuteilung begrenzter Ressourcen auf Prozesse. Im folgenden werden 2 jüngere ~~Methoden~~ zur Verbesserung des Scheduling näher betrachtet. Einmal das Verfahren Lottery Scheduling, sowie das Steigern der Clock Interupt Rate. Fachbegriffe in diesem Artikel werden wenn möglich sinnvoll übersetzt.		Scheduling ist generell die Zuteilung begrenzter Ressourcen auf Prozesse. Im folgenden werden 2 "jüngere" Verfahren zur Verbesserung des Scheduling näher betrachtet. Einmal das Verfahren Lottery Scheduling, sowie das Steigern der Clock Interupt Rate. Fachbegriffe in diesem Artikel werden wenn möglich sinnvoll übersetzt.


	== Lottery Scheduling ==		== Lottery Scheduling ==
Line 30:		Line 29:
	===Ticket Währungen===		===Ticket Währungen===
	Ticket Währungen gewährleisten eine Separierung mehrerer Prozessebenen. Ist schwer zu beschreiben, sollte durch Abbildung 2 aber klar werden. Hier haben 2 Benutzer Alice und Bob eine feste Anzahl base-Tickets, die eine relative Ressourcennutzung von 0,33 zu 0,67 also 1 zu 2 bedeuten, und vergeben für ihre Benutzerprozesse jeweils eine eigene Währung. Damit ist gewährleistet, dass das base-Verhältnis bestand hat, egal was die Benutzer auch tun, auch wenn z.B. Bob einen weiteren Prozess startet, siehe Abbildung 3 mit einem base-Verhältnis von 1 zu 1, bleibt Alice unberührt.		Ticket Währungen gewährleisten eine Separierung mehrerer Prozessebenen. Ist schwer zu beschreiben, sollte durch Abbildung 2 aber klar werden. Hier haben 2 Benutzer Alice und Bob eine feste Anzahl base-Tickets, die eine relative Ressourcennutzung von 0,33 zu 0,67 also 1 zu 2 bedeuten, und vergeben für ihre Benutzerprozesse jeweils eine eigene Währung. Damit ist gewährleistet, dass das base-Verhältnis bestand hat, egal was die Benutzer auch tun, auch wenn z.B. Bob einen weiteren Prozess startet, siehe Abbildung 3 mit einem base-Verhältnis von 1 zu 1, bleibt Alice unberührt.


	== Clock interrupt rate tuning ==		== Clock interrupt rate tuning ==

			Dies ist kein weiteres Scheduling Verfahren, sondern eine Technik, die das bisherige Scheduling mit einer winzigen Änderung im Betriebssystem effizienter machen soll. Dabei geht es um die System clock, die vom Betriebssystem gesetzt und als timer interrupt rate verwendet wird, also dessen Reaktionszeit definiert. Diese Uhr lief bis vor einigen Jahren seit knapp 3 Jahrzehnten mit 100 Hz, was damals bei 1-MHz-Computern 10.000 Instruktionen pro Tick entsprach, heute jedoch schon mehr als 10 Millionen Instruktionen sind.


	== Quellen ==		== Quellen ==

Butzek at 12:01, 24 January 2007

2007-01-24T12:01:31Z

← Older revision		Revision as of 12:01, 24 January 2007
Line 8:		Line 8:
	== Lottery Scheduling ==		== Lottery Scheduling ==

	[[Image:Scheduling_1.png\|thumb~~\|350px\|right~~\|Abbildung 1: Beispiellotterie]]		[[Image:Scheduling_1.png\|thumb\|Abbildung 1: Beispiellotterie]]
	[[Image:Scheduling_2.png\|thumb~~\|350px\|right~~\|Abbildung 2: Unterschiedliche Ticket Währungen]]		[[Image:Scheduling_2.png\|thumb\|Abbildung 2: Unterschiedliche Ticket Währungen]]
	[[Image:Scheduling_3.png\|thumb~~\|350px\|right~~\|Abbildung 3: Separierung durch unterschiedliche Währungen]]		[[Image:Scheduling_3.png\|thumb\|Abbildung 3: Separierung durch unterschiedliche Währungen]]

	Dieses Scheduling Verfahren wurde 1994 von Carl A. Waldspurger entwickelt. Ihm liegt ein zufallsbasierter Ressourcen-Verteilungs-Mechanismus zugrunde, der eine einfache und doch sehr flexible Kontrolle über die relativen Ausführungsraten ermöglicht, da der Zufall über längere Sicht ja keinesfalls zufällig sondern relativ genau ist. Zur Abstraktion wird eine Währung eingeführt, sogenannte Lotterie Tickets. Vor jeder Ressourcenzuteilung wird eine Lotterie durchgeführt, wobei der Prozess, der das Gewinnerticket besitzt, die Ressource für ein fest definiertes Zeitquantum nutzen darf.		Dieses Scheduling Verfahren wurde 1994 von Carl A. Waldspurger entwickelt. Ihm liegt ein zufallsbasierter Ressourcen-Verteilungs-Mechanismus zugrunde, der eine einfache und doch sehr flexible Kontrolle über die relativen Ausführungsraten ermöglicht, da der Zufall über längere Sicht ja keinesfalls zufällig sondern relativ genau ist. Zur Abstraktion wird eine Währung eingeführt, sogenannte Lotterie Tickets. Vor jeder Ressourcenzuteilung wird eine Lotterie durchgeführt, wobei der Prozess, der das Gewinnerticket besitzt, die Ressource für ein fest definiertes Zeitquantum nutzen darf.
Line 29:		Line 29:

	===Ticket Währungen===		===Ticket Währungen===
	Ticket Währungen gewährleisten eine Separierung mehrerer Prozessebenen. Ist schwer zu beschreiben, sollte durch Abbildung 2 aber klar werden. Hier haben 2 Benutzer Alice und Bob eine feste Anzahl base-Tickets, die eine relative Ressourcennutzung von 0,33 zu 0,67 also 1 zu 2 bedeuten, und vergeben für ihre Benutzerprozesse jeweils eine eigene Währung. Damit ist gewährleistet, dass das base-Verhältnis bestand hat, egal was die Benutzer auch tun, auch wenn z.B. Bob einen weiteren Prozess startet, siehe Abbildung 3 mit einem base-Verhältnis von 1 zu 1.		Ticket Währungen gewährleisten eine Separierung mehrerer Prozessebenen. Ist schwer zu beschreiben, sollte durch Abbildung 2 aber klar werden. Hier haben 2 Benutzer Alice und Bob eine feste Anzahl base-Tickets, die eine relative Ressourcennutzung von 0,33 zu 0,67 also 1 zu 2 bedeuten, und vergeben für ihre Benutzerprozesse jeweils eine eigene Währung. Damit ist gewährleistet, dass das base-Verhältnis bestand hat, egal was die Benutzer auch tun, auch wenn z.B. Bob einen weiteren Prozess startet, siehe Abbildung 3 mit einem base-Verhältnis von 1 zu 1, bleibt Alice unberührt.

Butzek: lottery 4

2007-01-24T11:44:22Z

lottery 4

← Older revision		Revision as of 11:44, 24 January 2007
Line 8:		Line 8:
	== Lottery Scheduling ==		== Lottery Scheduling ==

	[[Image:Scheduling_1.png\|thumb\|~~300px~~\|right\|Abbildung 1: Beispiellotterie]]		[[Image:Scheduling_1.png\|thumb\|350px\|right\|Abbildung 1: Beispiellotterie]]
		⚫	[[Image:Scheduling_2.png\|thumb\|350px\|right\|Abbildung 2: Unterschiedliche Ticket Währungen]]
			[[Image:Scheduling_3.png\|thumb\|350px\|right\|Abbildung 3: Separierung durch unterschiedliche Währungen]]

	Dieses Scheduling Verfahren wurde 1994 von Carl A. Waldspurger entwickelt. Ihm liegt ein zufallsbasierter Ressourcen-Verteilungs-Mechanismus zugrunde, der eine einfache und doch sehr flexible Kontrolle über die relativen Ausführungsraten ermöglicht, da der Zufall über längere Sicht ja keinesfalls zufällig sondern relativ genau ist. Zur Abstraktion wird eine Währung eingeführt, sogenannte Lotterie Tickets. Vor jeder Ressourcenzuteilung wird eine Lotterie durchgeführt, wobei der Prozess, der das Gewinnerticket besitzt, die Ressource für ein fest definiertes Zeitquantum nutzen darf.		Dieses Scheduling Verfahren wurde 1994 von Carl A. Waldspurger entwickelt. Ihm liegt ein zufallsbasierter Ressourcen-Verteilungs-Mechanismus zugrunde, der eine einfache und doch sehr flexible Kontrolle über die relativen Ausführungsraten ermöglicht, da der Zufall über längere Sicht ja keinesfalls zufällig sondern relativ genau ist. Zur Abstraktion wird eine Währung eingeführt, sogenannte Lotterie Tickets. Vor jeder Ressourcenzuteilung wird eine Lotterie durchgeführt, wobei der Prozess, der das Gewinnerticket besitzt, die Ressource für ein fest definiertes Zeitquantum nutzen darf.
Line 25:		Line 27:
	===Ausgleichstickets===		===Ausgleichstickets===
	Diese Methode soll sicherstellen, dass ein Prozess, der nicht das volle ihm zugeteilte Zeitquantum nutzt, trotzdem die Ressource mit der ihm durch die Tickets zugeteilten relativen Wahrscheinlichkeit nutzen kann. Dazu bekommt er für die nächste Lotterie mehr Tickets in Abhängigkeit der verbrauchten Zeit des aktuellen Quantums. Sollte der Prozess also nach dem halben Quantum die Steuerung abgeben, so erhält er doppelt so viele Tickets für die nächste Lotterie.		Diese Methode soll sicherstellen, dass ein Prozess, der nicht das volle ihm zugeteilte Zeitquantum nutzt, trotzdem die Ressource mit der ihm durch die Tickets zugeteilten relativen Wahrscheinlichkeit nutzen kann. Dazu bekommt er für die nächste Lotterie mehr Tickets in Abhängigkeit der verbrauchten Zeit des aktuellen Quantums. Sollte der Prozess also nach dem halben Quantum die Steuerung abgeben, so erhält er doppelt so viele Tickets für die nächste Lotterie.

⚫	[[Image:Scheduling_2.png\|thumb\|~~300px~~\|right\|Abbildung 2: Unterschiedliche Ticket Währungen]]

	===Ticket Währungen===		===Ticket Währungen===
			Ticket Währungen gewährleisten eine Separierung mehrerer Prozessebenen. Ist schwer zu beschreiben, sollte durch Abbildung 2 aber klar werden. Hier haben 2 Benutzer Alice und Bob eine feste Anzahl base-Tickets, die eine relative Ressourcennutzung von 0,33 zu 0,67 also 1 zu 2 bedeuten, und vergeben für ihre Benutzerprozesse jeweils eine eigene Währung. Damit ist gewährleistet, dass das base-Verhältnis bestand hat, egal was die Benutzer auch tun, auch wenn z.B. Bob einen weiteren Prozess startet, siehe Abbildung 3 mit einem base-Verhältnis von 1 zu 1.
	Ticket Währungen gewährleisten

Butzek: lottery 3

2007-01-24T10:58:41Z

lottery 3

← Older revision		Revision as of 10:58, 24 January 2007
Line 24:		Line 24:

	===Ausgleichstickets===		===Ausgleichstickets===
			Diese Methode soll sicherstellen, dass ein Prozess, der nicht das volle ihm zugeteilte Zeitquantum nutzt, trotzdem die Ressource mit der ihm durch die Tickets zugeteilten relativen Wahrscheinlichkeit nutzen kann. Dazu bekommt er für die nächste Lotterie mehr Tickets in Abhängigkeit der verbrauchten Zeit des aktuellen Quantums. Sollte der Prozess also nach dem halben Quantum die Steuerung abgeben, so erhält er doppelt so viele Tickets für die nächste Lotterie.

			[[Image:Scheduling_2.png\|thumb\|300px\|right\|Abbildung 2: Unterschiedliche Ticket Währungen]]
⚫	===Ticket Währungen===

		⚫	===Ticket Währungen===
			Ticket Währungen gewährleisten

Butzek: lottery 2

2007-01-24T10:46:20Z

lottery 2

← Older revision		Revision as of 10:46, 24 January 2007
Line 10:		Line 10:
	[[Image:Scheduling_1.png\|thumb\|300px\|right\|Abbildung 1: Beispiellotterie]]		[[Image:Scheduling_1.png\|thumb\|300px\|right\|Abbildung 1: Beispiellotterie]]

	Dieses Scheduling Verfahren wurde 1994 von Carl A. Waldspurger entwickelt. Ihm liegt ein zufallsbasierter Ressourcen-Verteilungs-Mechanismus zugrunde, der eine einfache und doch sehr flexible Kontrolle über die relativen Ausführungsraten ermöglicht, da der Zufall über längere Sicht ja keinesfalls zufällig sondern relativ genau ist. Zur Abstraktion ~~der Ressource~~ wird eine Währung eingeführt, sogenannte Lotterie Tickets. Vor jeder Ressourcenzuteilung wird eine Lotterie durchgeführt, wobei der Prozess, der das Gewinnerticket besitzt, die Ressource für ein fest definiertes Zeitquantum nutzen darf.		Dieses Scheduling Verfahren wurde 1994 von Carl A. Waldspurger entwickelt. Ihm liegt ein zufallsbasierter Ressourcen-Verteilungs-Mechanismus zugrunde, der eine einfache und doch sehr flexible Kontrolle über die relativen Ausführungsraten ermöglicht, da der Zufall über längere Sicht ja keinesfalls zufällig sondern relativ genau ist. Zur Abstraktion wird eine Währung eingeführt, sogenannte Lotterie Tickets. Vor jeder Ressourcenzuteilung wird eine Lotterie durchgeführt, wobei der Prozess, der das Gewinnerticket besitzt, die Ressource für ein fest definiertes Zeitquantum nutzen darf.

	Zum visuellen Verständnis ist rechts eine Beispiellotterie angegeben, die den Ablauf verdeutlicht.		Zum visuellen Verständnis ist rechts eine Beispiellotterie angegeben, die den Ablauf verdeutlicht.

			Die Ticket Abstraktion bietet einen besonderen Vorteil, das modulare Ressourcen-Management, welches durch 4 Methoden beschrieben wird:
			===Ticket Transfer===
			Der Ticket Transfer ermöglicht es Prozessen Tickets an Prozesse, von denen sie abhängig sind, abzutreten.
			Angenommen in der Beispiellotterie wäre Prozess1 von Prozess3 abhängig, dann würde Prozess3 mit einer relativen Wahrscheinlichkeit von 5/10=0,5 die Ressource zugeteilt bekommen (Prozess 1 nimmt ja nicht an der Lotterie teil). Durch den Ticket Transfer könnte Prozess1 seine 10 Tickets an Prozess3 abtreten, und würde dessen Wahrscheinlichkeit auf 15/20=0,75 erhöhen.

			===Ticket Inflation===
			Die Ticket Inflation ermöglicht es einem Prozess selbstständig die Anzahl seiner Tickets zu erhöhen oder zu verringern. Diese Methode setzt vorraus, dass die Prozesse untereinander nicht konkurrieren, da ansonsten jeder Prozess unendlich viele Tickets generieren würde.
			Im vorherigen Beispiel könnte so Prozess3 selbst die Anzahl seiner Tickets erhöhen, ohne dass dafür eine Kommunikation zum Ticket Transfer nötig wäre.

			===Ausgleichstickets===

			===Ticket Währungen===



	== Clock interrupt rate tuning ==		== Clock interrupt rate tuning ==

Butzek: Lottery 1

2007-01-24T08:03:03Z

Lottery 1

← Older revision		Revision as of 08:03, 24 January 2007
Line 3:		Line 3:
	== Einführung ==		== Einführung ==

	Scheduling ist generell die Zuteilung begrenzter Ressourcen auf Prozesse. Im folgenden werden 2 jüngere Methoden zur Verbesserung des Scheduling näher betrachtet. Einmal das Verfahren Lottery Scheduling, sowie das Steigern der Clock Interupt Rate.		Scheduling ist generell die Zuteilung begrenzter Ressourcen auf Prozesse. Im folgenden werden 2 jüngere Methoden zur Verbesserung des Scheduling näher betrachtet. Einmal das Verfahren Lottery Scheduling, sowie das Steigern der Clock Interupt Rate. Fachbegriffe in diesem Artikel werden wenn möglich sinnvoll übersetzt.


	== Lottery Scheduling ==		== Lottery Scheduling ==

			[[Image:Scheduling_1.png\|thumb\|300px\|right\|Abbildung 1: Beispiellotterie]]

			Dieses Scheduling Verfahren wurde 1994 von Carl A. Waldspurger entwickelt. Ihm liegt ein zufallsbasierter Ressourcen-Verteilungs-Mechanismus zugrunde, der eine einfache und doch sehr flexible Kontrolle über die relativen Ausführungsraten ermöglicht, da der Zufall über längere Sicht ja keinesfalls zufällig sondern relativ genau ist. Zur Abstraktion der Ressource wird eine Währung eingeführt, sogenannte Lotterie Tickets. Vor jeder Ressourcenzuteilung wird eine Lotterie durchgeführt, wobei der Prozess, der das Gewinnerticket besitzt, die Ressource für ein fest definiertes Zeitquantum nutzen darf.

			Zum visuellen Verständnis ist rechts eine Beispiellotterie angegeben, die den Ablauf verdeutlicht.

	== Clock interrupt rate tuning ==		== Clock interrupt rate tuning ==
Line 18:		Line 22:
	* Carl A. Waldspurger and William E. Weihl. [http://www.usenix.org/publications/library/proceedings/osdi/full_papers/waldspurger.pdf Lottery Scheduling: Flexible Proportional-Share ResourceManagement]. In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 1–11, November 14–17 1994.		* Carl A. Waldspurger and William E. Weihl. [http://www.usenix.org/publications/library/proceedings/osdi/full_papers/waldspurger.pdf Lottery Scheduling: Flexible Proportional-Share ResourceManagement]. In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 1–11, November 14–17 1994.
	* Etsion, Yoav; Tsafrir, Dan; Freitelson, Dror G. [http://portal.acm.org/citation.cfm?doid=781027.781049 Effects of Clock Resolution on the Scheduling of Interactive and Soft Real-time Processes]. In SIGMETRICS ’03 S. 172 - 183.		* Etsion, Yoav; Tsafrir, Dan; Freitelson, Dror G. [http://portal.acm.org/citation.cfm?doid=781027.781049 Effects of Clock Resolution on the Scheduling of Interactive and Soft Real-time Processes]. In SIGMETRICS ’03 S. 172 - 183.
	* [http://www.informatik.uni-hamburg.de/WSV/teaching/sonstiges/EwA-Folien/Drebes-Paper.pdf ~~Andi Drebes:~~ Schedulingalgorithmen und Rechenzeitverteilung auf Betriebssystemebene]		* Andi Drebes [http://www.informatik.uni-hamburg.de/WSV/teaching/sonstiges/EwA-Folien/Drebes-Paper.pdf Schedulingalgorithmen und Rechenzeitverteilung auf Betriebssystemebene]