Knowledge & Learning

home *** CD-ROM | disk | FTP | other *** search

/ Knowledge & Learning / WISS_LERN.iso / doslern / computer / educard / bs___7.sti < prev next >

Wrap

Text File | 1992-03-14 | 38.9 KB | 1,046 lines

YCPAA #!!# - HSV - @CEInhalt @CPDas Thema von BS___7 ist die Hintergrundspeicher-Verwaltung. Start mit ⌐HSV@BS___7¬ AHBAA #!!# HSV @EH Hintergrundspeicher-Verwaltung @HB Entscheidend für das gute Arbeiten von Multiprogramming-Systemen ist die Transferrate von Informationen zwischen dem Arbeits- und dem Hintergrund- speicher. Man versucht daher, maximale Leistung von den Magnettrommeln- und -platten zu erhalten, die in den meisten Fällen als Hintergrund- speicher dienen. Andere Möglichkeiten dafür sind Magnetband, Disketten, ... weiter mit ⌐Trommelspeicher@BS___7¬ Zum Thema Hintergrundspeicher siehe auch: ⌐Hauptspeicher@BS1¬ ⌐Speicherverwaltung@BS___1¬ ⌐Hauptspeicherverwaltung@BS1¬ AHBAA #!!# Magnettrommelspeicher #!!# Trommelspeicher Ein @HPTrommelspeicher@HB ist ein, um seine Achse mit gleichförmiger Geschwin- digkeit rotierender, Zylinder mit festen Schreib/Lese-Köpfen. Der Mantel ist in @HPSpuren@HB (engl. Tracks) unterteilt, von denen jede mit einem Schreib/Lese-Kopf versehen ist. Die Spuren sind aufgeteilt in eine feste Anzahl gleichlanger Felder. Die Felder, die sich nebeneinander befinden, werden zusammengefaßt zu einem @HPSektor@HB. Eine @HPSeite@HB (Page) wird innerhalb eines Sektors abgelegt. @HEMagnettrommelspeicher @HBSp_1 Sp_2 Sp_3 Sp_n S = Sektor @HP▄┬────┬────┬────┬─.....─┬────▄ @HBSp_x = Spur x @HP█ █│ │ │ │ ..... │ █ @HI▐████▌@HB= Seite @HP█ @HI/@HP█│ │ │ │ ..... │ █ @HP█ @HI/@HBS@HI/ @HP█│ @HI▐████▌@HP │ ..... │ █ @HA──@HBAchse@HA───@HP█@HA───────@HP■@HI/@HA······@HP█│ │ │ │ ..... │ █@HA──────@HBAchse@HA─── @HP█ @HI\@HBS@HI\ @HP█│ │ │ │ ..... │ █ @HP█ @HI\ \@HP█│ │ │ │ ..... │ █ @HP█ █│ │ │ │ ..... │ █ @HP▀┴────┴────┴────┴─.....─┴───▀ @HL╬ ╬ ╬ ╬ ╬ @HL╙────╨────╨────╨───────╜ @HBSchreib/Lese-Köpfe @HBDie Anforderung eines Seitenwechsels von oder zur Magnettrommel wird in eine ⌐Warteschlange@BS2¬ eingereiht, wenn sie zu einem Zeitpunkt auftritt, zu dem eine frühere Anforderung noch nicht abgeschlossen ist. Dort wartet sie darauf, daß sie an die Reihe kommt (queueing delay). Wird eine Anforderung schließlich behandelt, so wird zunächst eine gewisse Zeit vergehen, bis die Trommel so weit gedreht wurde, daß die Schreib/ Lese-Köpfe auf den Beginn des zu schreibenden bzw. zu lesenden Sektors zeigt (latency delay). Jetzt kann die Übertragung beginnen. Die dafür benötigte Zeit nennt man transfer delay. Es wird jeweils nur eine Seite übertragen. @HEVerweilzeit beim Trommelspeicher @HB Anforderung Beginn der Beginn der Ende der in Queue Bedienung Übertragung Übertragung @HP ───────┼───────────────────────┼─────────────┼─────────────┼─────── @HO «──────────@HBw@HO──────────» «─────@HBz@HO─────» «─────@HBτ@HO─────» «────────────@HBB@HO────────────» «───────────────────────@HBV@HO─────────────────────────» @HPw @HB: Wartezeit in der Queue @HPz @HB: Zugriffs- / Positionierzeit (Wartezeit auf Sektor) @HPτ @HB: Übertragungszeit für einen Sektor @HPB = z + τ @HB: Bedienzeit einer Anforderung @HPV = w + B @HB: Verweilzeit einer Anforderung @HB weiter mit ⌐Trommelspeicher-FCFS@BS___7¬ AHBAA #!!# Trommelspeicher - FCFS #!!# Trommelspeicher-FCFS @EH 1. Strategie zur Verwaltung der Warteschlange: FCFS @HB siehe auch ⌐HSV@BS___7¬ Die Anforderungen werden in der Reihenfolge ihres Eintreffens behandelt. @HEMathematische Analyse @HB @HPT @HB: Zeit für eine Umdrehung der Trommel @HPN @HB: Anzahl der Sektoren @HPT τ @HB: Übertragungszeit für einen Sektor = @HP─── N @HB gesucht : Erwartungswert für die Zugriffszeit (latency delay), @HPE [z]@HB @HBFür die @HPZugriffszeit@HB sind zwei verschiedene Ansätze möglich: a) Da die Seiten nicht immer vollständig mit Daten belegt sind, können die Schreib-/Lese-Köpfe nach der Beendigung einer Anforderung an irgendeiner Stelle im Sektor stehen. Die Zugriffszeit ist also eine @HPgleichverteilte stetige Größe@HB, das heißt sie kann jeden beliebigen Wert zwischen 0 und T annehmen und jeder der Werte kommt gleich häufig vor. b) Man geht davon aus, daß die Schreib-/Lese-Köpfe sich nach der Beendigung einer Anforderung immer am Ende eines Sektors befinden. Die Zugriffszeit ist also eine @HPgleichverteilte diskrete Größe@HB, das heißt sie kann mit gleicher 1 T 2T (N-1) * T Wahrscheinlichkeit ─── einen der Werte 0, ───, ────, ..., ─────────── N N N N annehmen. @HEAnsatz a) stetige Verteilung @HB In diesem Fall kommt man zu einer Rechteck-Verteilung. @HP/│\ @HAF (t) = P [z ≤ t] @HP/│\ @HAf (t) @HP│ @HB(Summenfunktion) @HP│ @HB(Verteilungsfunktion) @HP│ │ @HA1 @HP┤ @HO* * * * * * * * @HP│ @HP│ @HO* @HP│ @HP│ @HO* @HA1 @HP│ @HP│ @HO* @HA─── @HP┤@HO* * * * * * * * * * @HP│ @HO* @HAT @HP│ @HO* @HP│ @HO* @HP│ @HO* @HP└───────────┬───────────────> @HAt @HP└──────────────────┬─────────> @HAt @HA T T @HBBei der Rechteck-Verteilung gilt: @HL ┌ │ 0, für t ≤ 0 │ t F (t) = P [z ≤ t] = ┤ ───, für 0 < t ≤ T │ T │ 1, für t > T └ ┌ │ 1 │ ───, für 0 < t ≤ T f (t) = ┤ T │ │ 0, sonst └ @HBFür den Erwartungswert der Zugriffszeit E [z] ergibt sich somit @HL ∞ T ⌠ ⌠ 1 E [z] = │ t * F' (t) dt = │ t * ─── dt ⌡ ⌡ T -∞ 0 T @AO ╔══════════════╗ @HL 1 ⌠ 1 T² @AO ║ T ║ @HL = ─── │ t dt = ─── (──── - 0) = @AO ║ E [z] = ─── ║ @HL T ⌡ T 2 @AO ║ 2 ║ @HL 0 @AO ╚══════════════╝ @HL @HB Im Mittel benötigt man also eine halbe Umdrehung der Trommel, bis die Schreib-/Lese-Köpfe auf den Begin des zu schreibenden bzw. zu lesenden Sektors positioniert sind. @HBFür die @HPVarianz@HB bei der stetigen Verteilung erhält man @HL T T ⌠ T 1 1 ⌠ T² E [z²] = │ (t - ───)² * ──── dt = ─── │ t² - T * t + ──── dt ⌡ 2 T T ⌡ 4 0 0 1 ┌ 1 3 T T² ┐T 1 1 3 1 3 1 3 = ─── │─── t - ─── t² + ─── t│ = ─── (─── T - ─── T + ─── T ) T └ 3 2 4 ┘0 T 3 2 4 @AO ╔══════════════════╗ @HL 1 1 3 @AO ║ 1 ║ @HL = ─── * ──── T = @AO ║ E [z²] = ──── T² ║ @HL T 12 @AO ║ 12 ║ @HL @AO ╚══════════════════╝ @HL @HEAnsatz b) diskrete Verteilung @HB In diesem Fall sieht die Verteilungsfunktion folgendermaßen aus: @HP/│\ F (t) @HA1 @HP┤ @HK┌─@HCo@HO«─»@HK────── @HA(N-1)/N @HP┤ @HK┌─@HCo@HK──┘ @HA: @HP┤ @HK┌─@HCo@HK──┘ @HA: @HB1 @HP┤ @HCo @HA: @HO«─» @HB: ──── @HP┤ @HCo @HA: @HB2N @HP┤ @HK┌─@HCo@HK──┘ @HA: @HA3/N @HP┤ @HK┌─@HCo@HK──┘ @HCooo @HB: G (t) @HA: @HA2/N @HP┤ @HK┌─@HCo@HK──┘ @HA: @HA1/N @HP┤@HK─@HCo@HK──┘ @HA: @HP└────┬────┬────┬────┬────┬────┬────┬────┬────┬───────> @HAt T 2T 3T (N-2)*T ─── ─── ─── ─────── T N N N N @HBDie Verteilungsfunktion ist eine Stufenfunktion, die man durch G (t) approximieren kann.@HL ┌ │ 0, für t ≤ 0 │ │ │ 1 t 2N - 1 T G (t) = ┤ ──── + ───, für 0 < t ≤ ──────── * ─── │ 2N T 2 N │ │ 2N - 1 T │ 1, für t > ──────── * ─── │ 2 N └ @HB 2N - 1 T 2N - 1 1 Anmerkung: ──────── * ─── = ──────── * T = (1 - ────) * T 2 N 2N 2N @HBAls Erwartungswert für die Zugriffszeit erhält man: @HL N-1 i * T 1 T N-1 E [z] = Σ ─────── * ─── = ──── Σ i i=0 N N N² i=0 T (N-1) * N N-1 T = ──── (───────────) = ───── * ─── N² 2 2 N @AO ╔════════════════════╗ @HL @AO ║ T T ║ @HL = @AO ║ E [z] = ─── - ──── ║ @HL @AO ║ 2 2N ║ @HL @AO ╚════════════════════╝ @HB T Bei der diskreten Verteilung ist der Erwartungswert um ──── kleiner als bei der stetigen Verteilung. 2N @HBBerechnung der mittleren Bedienzeit E [B] @HL B = z + τ ==> E [B] = E [z] + E [τ] T T T = (─── - ────) + ─── 2 2N N T T 1 T T = ─── + ─── * (- ─── + 1) = ─── + ──── 2 N 2 2 2N @AO ╔═══════════════════════╗ @HL @AO ║ T N + 1 ║ @HL = @AO ║ E [B] = ─── * ─────── ║ @HL @AO ║ 2 N ║ @HL @AO ╚═══════════════════════╝ @HB @HBFür weitere Berechnungen muß man das M/G/1-Modell (Ankünfte: Poisson verteilt, Bedienzeit: allgemein, eine Bedieneinheit) zu Grunde legen. Setzt man dann E [B] und E [B²] in die PK-Gleichung ∩² * E [B²] E [n] = ∩ * E [B] + ───────────── ein, so kann man E [n] also die 2 * (1-δ) mittlere Anzahl an Anforderungen an das System, bestimmen. Damit erhält man die Größe, mit der man nach dem Satz von ⌐Little@BS___2¬, E [n] = ∩ * E [V], die ⌐Verweilzeit@BS2¬ berechnen kann. Siehe auch ⌐Modellkennzeichnung@BS___2¬ ⌐Poisson, Mittelwert@BS___2¬ ⌐M/G/1-System@BS___2¬ @HEAusnutzungsgrad @HB Der Ausnutzungsgrad H ist das Verhältnis zwischen der Seitenübertragungs- zeit τ und der Bedienzeit B. @HL T T ─── ─── τ N N 2 H = ─── = ─────────── = ───────────────── = ─────── B T T T N 1 N + 1 ─── + ──── ─── (─── + ───) 2 2N N 2 2 @HB für N = 20 ==> H ≈ 10 % Ergebnis: Die Ausnutzung ist gering. für N = 8 ==> H ≈ 22 % Man muß versuchen, die Zugriffszeit (die einzige änderbare Variable) zu minimieren. Ein Beispiel dafür ist die SATF-Strategie. @HB weiter mit ⌐Trommelspeicher-SATF@BS___7¬ AHBAA #!!# Trommelspeicher - SATF #!!# Trommelspeicher-SATF @HESATF (shortest access time first) @HB Bei dieser Strategie wird die Anforderung als nächste behandelt, die die kürzeste Zugriffszeit hat. Zum besseren Verständnis benutzt man folgendes Modell: Man betrachtet den Trommelspeicher als fest und stellt sich vor, die Schreib/-Leseköpfe würden sich um die Trommel mit konstanter Geschwin- digkeit drehen. So kann man sich für jeden Sektor k eine eigene Warte- schlange qk vorstellen, in der sich die Anforderungen für diesen bestimmten Sektor befinden. Die Sektorenwarteschlangen sind voneinander unabhängig. Jedesmal wenn die Schreib/-Lese-Köpfe zu einer nicht-leeren Schlange gelangen, wird aus dieser die erste Anforderung behandelt. @HBDie Ankünfte sind Poisson verteilt mit der Ankunftsrate ∩. Sie werden auf die N Sektoren so verteilt, daß die Ankünfte in einer Queue für Sektor k auch Poisson verteilt sind mit der Ankunftsrate ∩k. Es gilt somit: @HL N ∩ ∩ = Σ ∩k @HBund@HL ∩k = ─── k=1 N @HB Die Schwierigkeit des Modells liegt darin, daß man bei der Interpretation der Sektorschlangen zwei Fälle unterscheiden muß: a) @HPAnkünfte in einer nicht-leeren Schlange@HB sehen konstante Bedienzeiten für die vor ihnen liegenden Anforderungen. Die Bedienzeiten entspre- chen aus ihrer Sicht der Rotationszeit T. Man kann also von einem M/D/1-System sprechen. b) @HPAnkünfte in einer leeren Sclange@HB haben keine konstanten Bedienzeiten. Man hat also ein M/G/1-System vorliegen. @HEZu a) Ankünfte in einer nicht-leeren Schlange @HB Wenn man davon ausgeht, daß hinreichend viele Anforderungen an das System vorhanden sind, so daß keine Sektorschlange leer ist, dann werden die Sektoren nacheinander in der Reihenfolge ihrer Anordnung auf der Trommel bearbeitet. Aus der Sicht des Systems fällt die Zugriffs-/Positionierungszeit weg, es gilt E [z] = 0. Für die @HPBedienzeit@HB ergibt sich somit @HL T E [B] = τ + 0 = ─── N @HB Aus der Sicht irgendeiner Anforderung in einer Schlange beträgt die @HPBedienzeit@HB für die erste Anforderung in seiner Queue (diese wird als nächste aus seiner Queue behandelt) @HL T T E [B] = (N - 1) * ─── + ─── = T N N @HA └──────┬──────┘ └─┬─┘ z τ @HEZu b) Ankünfte in einer leeren Schlange @HB Wenn eine Ankunft in einer leeren Schlange erfolgt, so können sich die Schreib-/Lese-Köpfe an einer beliebigen Stelle auf der Trommel befinden. Die Zugriffszeit für diese Anforderung ist ein nicht vorhersagbarer Wert zwischen 0 und T. Bei einer anderen Ankunft in einer nicht leeren Queue kann der Abstand zwischen den Köpfen und der Schlange ein anderer sein. @HB Diese Anforderung hat also eine andere Zugriffszeit. Ankünfte in nicht- leeren Queues können demnach unterschiedliche Zugriffs- und folglich auch andere Bedienzeiten haben. Zur Berechnung der Zugriffszeit geht man wieder von der allgemeinen Formel für den Mittel-/Erwartungswert einer Verteilung aus: @HL ∞ ∞ ⌠ ⌠ E [z] = │ t * f (t) dt = │ t * F' (t) dt ⌡ ⌡ -∞ -∞ @HB zu F (t) und f (t) siehe auch ⌐Trommelspeicher-FCFS@BS___7¬ @HE Exkurs: partielle Integration @HB Es gilt ganz allgemein: @HL b b ⌠ ┌ ┐b ⌠ │ h (x) * g' (x) dx = │ h (x) * g (x) │ - │ h' (x) * g (x) dx ⌡ └ ┘a ⌡ a a @HB Durch partielle Integration erhält man dann @HL ∞ ∞ ⌠ ┌ ┐∞ ⌠ E [z] = │ t * F' (t) dt = │ t * F (t) │ - │ 1 * F (t) dt ⌡ └ ┘-∞ ⌡ -∞ -∞ @HL 0 ∞ ┌ ┐0 ┌ ┐∞ ⌠ ⌠ E [z] = │ t * F (t) │ + │ t * F (t) │ - │ F (t) dt - │ F (t) dt └ ┘-∞ └ ┘0 ⌡ ⌡ -∞ 0 @HA └──┬──┘ └──────┬──────┘ 0 ┌ t ┐T ┌ ┐∞ für t ≤ 0 │t*───│ + │t*1│ ==> └ T ┘0 └ ┘T @HL ∞ 0 ┌ ┐∞ ⌠ ⌠ E [z] = T + │ t │ - │ F (t) dt - │ F (t) dt └ ┘T ⌡ ⌡ 0 -∞ @HL ∞ 0 ┌ ┐∞ ⌠ ⌠ E [z] = T + │ t │ - T - │ F (t) dt - │ F (t) dt └ ┘0 ⌡ ⌡ 0 -∞ ∞ ∞ 0 ⌠ ⌠ ⌠ = │ 1 dt - │ F (t) dt - │ F (t) dt ⌡ ⌡ ⌡ 0 0 -∞ ∞ 0 ⌠ ⌠ = │ 1 - F (t) dt - │ F (t) dt ⌡ ⌡ 0 -∞ @HB Läßt man für t nur positive Werte zu (die Trommel dreht sich nicht rückwärts), so fällt das letzte Integral weg. Es ergibt sich somit: @HL ∞ ⌠ E [z] = │ 1 - F (t) dt ⌡ 0 ∞ ∞ ⌠ ⌠ = │ 1 - P [z ≤ t] dt = │ P [z > t] dt ⌡ ⌡ 0 0 @HB Gebe es nun n Anforderungen an das System mit den gleichverteilten Zugriffszeiten (s1, ..., sn), die sich in der Warteschlange Q befinden. Betrachtet man nun P [s > t] = P [s1 > t, s2 > t, ..., sn > t], wobei s = min (s1, ..., sn) eine neue Zufallsvariable ist, so erhält man wegen der Unabhängigkeit der si das Produkt der Wahrscheinlichkeiten @HL n n P [z > t] = (P [s > t]) = (1 - F (t)) @HB Damit ergibt sich für die mittlere Zugriffszeit a) stetiger Ansatz @HA┌durch Substitution @HL T T @HA│@HL ⌠ ⌠ t n @HA│ @HLT E [z] = │ 1 - F (t) dt = │ (1 - ───) dt ≈ ────── ⌡ ⌡ T n + 1 0 0 @HB b) diskreter Ansatz mit G (t) als Approximation @HA┌durch Substitution @HL α α @HA│@HL ⌠ ⌠ 1 t @HA│@HL T E [z] = │ 1 - G (t) dt = │ 1 - ──── - ─── dt ≈ ─────── ⌡ ⌡ 2N T n + 1 0 0 2N - 1 T mit α = ──────── * ─── 2 N @HBFür die @HPmittlere Bedienzeit@HB erhält man demnach bei SATF-Strategie: @HL E [B] = E [z] + E [τ] T T = ─────── + ─── n + 1 N @HP Ausnutzungsgrad@HB bei SATF-Strategie: @HL E [τ] H = ─────── ==> E [B] @HL T ─── N @HBfür ein M/D/1-System :@HL H = ───── = 1 T ─── N T T ─── ─── N N @HBfür ein M/G/1-System :@HL H = ─────────────── = ───────────────── ==> T T T (N + n + 1) ─────── + ─── ─────────────── n + 1 N (n + 1) * N @HL n + 1 H = ─────────── @HBfür große n ==> H ≈ 1@HL N + n + 1 @HB Die SATF-Strategie ist bezüglich des Ausnutzungsgrades optimal. weiter mit ⌐Vergleich FCFS - SATF@BS___7¬ AHBAA #!!# Vergleich FCFS - SATF #!!# Vergleich FCFS-SATF @HEVergleich von FCFS und SATF beim Trommelspeicher ??? das stimmt doch vorne und hinten nicht. weiter mit ⌐Plattenspeicher@BS___7¬ AHBAA #!!# Magnetplattenspeicher #!!# Plattenspeicher Ein @HPMagnetplattenspeicher@HB besteht aus einer Anzahl @HPPlatten@HB, die überein- ander um eine senkrechte Achse fest angebracht sind. Auf den Oberflächen der Platten werden Daten gespeichert. Jede der Oberflächen enthält @HPw Spuren@HB, die als konzentrische Kreise um die rotierende Achse angeordnet sind. Für jede Oberfläche (2 pro Platte) gibt es einen Schreib-/Lese-Kopf. Alle Köpfe sind an einem gemeinsamen Arm montiert, den man vertikal bewegen kann. Sie zeigen auf den verschiedenen Platten auf die gleiche Spur. Die @HPSpeicherkapazität@HB aller Spuren ist gleich. Obwohl man auf den äußeren Spuren mehr Daten speichern könnte, wird es wegen des hohen, organisato- rischen Mehraufwandes, den man benötigen würde, nicht gemacht. Alle Spuren bestehen also aus der gleichen Anzahl von @HPSektoren@HB. Die übereinander lie- genden Sektoren faßt man zu einem @HPZylinder@HB zusammen. Bsp.: @HAPlatten : 10, Spuren / Oberfläche : 400, Sektoren / Spur : 18 ==> ??? Kapazität = 72 MByte @HEPlattenspeicher @HAbeweglicher @HB╔═════╗ @HAKopf @HB║ @HA<-> @HB║ @HJ┌─────@HM▄ @HD█ @HB║ @HJ────@HB╫@HJ───┤ @HO▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ @HAPlatte @HB║ ║ @HJ└─────@HM▀ @HD█ @HB║ @HA<-> @HB║ @HJ┌─────@HM▄ @HD█ @HB║ @HJ────@HB╫@HJ───┤ @HO▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ @HAPlatte @HB║ ║ @HJ└─────@HM▀ @HD█ @HB║ @HA<-> @HB║ @HJ┌─────@HM▄ @HD█ @HB║ @HJ────@HB╫@HJ───┤ @HO▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ @HAPlatte @HB║ ║ @HJ└─────@HM▀ @HD█ @HB╚═════╝ @HD█ @HAsenkrechte, sich drehende Achse @HEVerweilzeit beim Plattenspeicher @HB Anforderung Beginn der Spur ist Sektor ist Übertragung in Queue Bedienung eingestellt eingestellt beendet @HP──┼─────────────────┼───────────────┼───────────────┼───────────────┼───── @HO«───────@HBW@HO───────» «──────@HBta@HO─────» «──────@HBtb@HO─────» «──────@HBτ@HO──────» «──────────────@HBz@HO──────────────» «──────────────────────@HBB@HO──────────────────────» «───────────────────────────────@HBV@HO───────────────────────────────» @HEZeiteinteilung beim Plattenspeicher @HPW @HB: Wartezeit in der Schlange (queueing delay) @HPta @HB: Zeit für die Einstellung des Schreib-/Lese-Arms auf die gesuchte Spur (seeking delay) @HPtb @HB: Zeit für die Positionierung auf den gewünschten Sektor (latency delay) @HPτ @HB: Zeit für die Übertragung einer Seite (transfer delay) @HPz = ta + tb @HB: Zugriffszeit, Zeit vom Beginn der Bedienung der Anforderung bis zum Start der Übertragung einer Seite @HPB = z + τ @HB: Bedienzeit @HPV = W + B @HB: Verweilzeit einer Anforderung im System @HBMathematische Analysen des Systems deuten darauf hin, daß von einer gemeinsamen Optimierung der Wartezeiten beim Positionieren auf die gesuchte Spur ta und beim Rotieren auf den gewünschten Sektor tb wenig Vorteile zu erwarten sind. Beide Vorgänge kann man daher getrennt unter- suchen. Dies gilt umso mehr, da in vielen Systemen die Zeit für die Ein- stellung auf die Spur so hoch ist, daß eine Optimierung der Zugriffszeit durch eine Optimierung der Positionierungszeit auf den Sektor nur noch relativ wenig bringt. @HEStrategien zur Verwaltung der Warteschlange @HP 1. FCFS (first come first served)@HB Die Anforderungen werden in der Reihenfolge ihrer Ankunft behandelt. @HP 2. SSTF (shortest seektime first)@HB Analog zur SATF-Strategie bei der Trommel wird die Anforderung als nächste behandelt, deren Spur am nächsten bei der aktuellen Position des Schreib-/Lese Arms liegt. Nachteil: Bei der SSTF-Strategie werden die Zylinder am Rand (sowohl innen wie außen) stark benachteiligt, weil sie im allgemeinen weite Zugriffswege erfordern. @HP 3. SCAN (dt.: Absuchen)@HB Idee: Wenn der Arm sich in eine bestimmte Richtung bewegt, so bediene als nächste Anforderung die, die sich nach dem SSTF-Verfahren für diese Richtung ergibt. Ändere die Richtung des Arms, wenn - die letzte Spur in der alten Richtung erreicht wurde oder - es keine weitere Anforderung in der alten Richtung mehr gibt. Bei dieser Strategie wird kein Zylinder benachteiligt. Jede Anforderung wird also nach endlicher Zeit behandelt. @HEMathematische Analyse @HB Entscheidend für die Berechnung der Zugriffs-, Bedien- und Verweilzeit ist die mittlere Distanz, die der Arm zurücklegen muß, um eine Anforderung bzw. deren Spur zu erreichen. Unabhängig von der Strategie zur Verwaltung der Warteschlange ist der entscheidende Faktor bei der Berechnung der Wartezeiten also die Zahl der Zylinder, die der Arm im Mittel überschreiten muß. @HPProblemstellung:@HB Ausgangspunkt: Zylinder k Zielpunkt : Zylinder i zu berechnen : dk = |k - i| @HBFolgende Abstände sind möglich: @HP k-1, k-2, k-3, ..., 2, 1, 0, 1, 2, ..., w-k @HA k = 1..w ───> <─── k = w..1 @HB Da jede Plattenoberfläche w Spuren hat, befindet sich der Schreib-/Lese- Arm mit der gleichen Wahrscheinlichkeit 1/w auf einer der Spuren 1..w. Mit der gleichen Wahrscheinlichkeit 1/w trifft eine neue Anforderung für die Spur i = 1..w ein. Von Interesse ist nun der Erwartungswert E [dk], der angibt, wieviele Spuren man wahrscheinlich überspringen muß, um von Spur k zur gewünschten Zielspur zu kommen. @HBFür die Summe aller k ergibt sich der Erwartungswert E [dk] @HL k-1 1 w-k 1 E [dk] = Σ i * ─── + Σ i * ─── i=1 w i=1 w @HA └─────┬─────┘ └─────┬─────┘ positive negative Abstände @HL 1 k * (k - 1) (w - k) * (w - k + 1) = ─── * (───────────── + ───────────────────────) w 2 2 @HBGemittelt über alle möglichen Stellungen des Armes erhält man @HL w 1 E [d] = Σ ─── * E [dk] k=1 w w 1 1 = Σ ─── * ──── * (k * (k - 1) + (w - k) * (w - k + 1) k=1 w 2w 1 w = ───── * Σ (2k² - 2 * (w + 1) * k + w * (w + 1)) 2w² k=1 @HL 1 w w E [d] = ───── * (2 * Σ (k²) - 2(w + 1) * Σ (k) + w²(w + 1)) 2w² k=1 k=1 1 w(w+1)(2w+1) w(w+1) = ───── * (2────────────── - 2(w+1) ──────── + w²(w + 1)) 2w² 6 2 1 2w + 1 w + 1 w = ───── * 2w * (w + 1) * (──────── - ─────── + ───) 2w² 6 2 2 w + 1 2w + 1 - 3w - 3 + 3w = ─────── * (──────────────────────) w 6 @HL w + 1 2w - 2 E [d] = ─────── * ──────── w 6 w + 1 w - 1 = ─────── * ─────── w 3 @AO ╔═════════════════════╗ @HL w² - 1 @AO ║ w 1 ║ @HL = ──────── = @AO ║ E [d] = ─── - ──── ║ @HL 3w @AO ║ 3 3w ║ @HL @AO ╚═════════════════════╝ @HL w @HBFür eine große Zylinderzahl w gilt vereinfacht: @HLE [d] = ─── @HL3 @HBBei SSTF und SCAN betrachtet man aber nicht nur die Distanz bis zur nächsten Anforderung, sondern die Distanzen von allen Anforderungen in der Warteschlange. Geht man von n Anforderungen aus, so wird die Platte in w (n+1) Teile geteilt, die alle die mittlere Länge ─────── haben. n + 1 Betrachtet man also alle Anforderungen in der Warteschlange, so erhält man für die mittlere Distanz bei den verschiedenen Strategien: @HP w @HB FCFS : @HPE [d] = ─── 3 w @HB SSTF und SCAN : @HPE [d] = ─────── n + 1 @HBZur @HPAbschätzung der mittleren Suchzeit@HB für die zu behandelnde Spur muß man folgendes beachten: @HA Suchzeit @HB Man benötigt eine maximale Suchzeit @HP/│\ @HB ta_max, wenn der Schreib-/Lese-Arm @HP │ @HM▀ @HB: tatsächlich @HB alle w Spuren überqueren muß. @HAmax @HP┤ @EM▀@HB @HP│ @HE▄ @HB: vermutet @HM▀@HE▄ @HB Man benötigt eine minimale Suchzeit @HP│ @HM▀ @HE▄ @HB ta_min, wenn der Arm von der k-ten @HP│ @HM▀ @HE▄ @HB auf die (k+1)-te Spur bewegt werden @HP│ @HM▀ @HE▄ @HB muß. Wichtig dabei ist, daß dies @HP│ @HM▀ @HE▄ @HB nicht der w-te Teil von ta_max ist, @HP│ @HM▀ @HE▄ @HB sondern ein größerer Wert, weil das @HAmin @HP┤ @EM▀@HB @HAüberquerte Spuren @HB Starten des Schreib-/Lese-Arms eine @HP└─────┬────────────────────┬───> @HB gewisse Zeit benötigt. @HA 1 w @HBFür die mittlere Suchzeit ergibt sich: @HL ta_max - ta_min E [ta] = ta_min + E' [d] * ───────────────── @HA│@HL w - 1 @HA│ └ Zeit zum Starten des Arms + Zeit für Überqueren der 1. Spur @HB wobei bei E' [d] das w durch w - 1 ersetzt wird, weil das Überqueren der ersten Spur innerhalb der Distanz schon in ta_min steckt. @HBMittlere Suchzeit bei den verschiedenen Strategien: @HP ta_max - ta_min @HBFCFS : @HPE [ta] = ta_min + ───────────────── 3 ta_max - ta_min @HBSSTF : @HPE [ta] = ta_min + ───────────────── n + 1 ta_max - ta_min @HBSCAN : @HPE [ta] = ta_min + ───────────────── n + 1 @HBFür die gesamte Zugriffszeit erhält man die Werte: @HP E [z] = ta + tb @HB 1. Fall: FCFS bei der Suche nach der Spur und FCFS bei der Positionierung auf den Sektor @HP ta_max - ta_min (N - 1) T E [z] = ta_min + ───────────────── + ───────── * ─── 3 2 N @HB 2. Fall: SSTF bei der Suche nach der Spur und SATF bei der Positionierung auf den Sektor @HP ta_max - ta_min T E [z] = ta_min + ───────────────── + ─── @HB(= 3. Fall)@HP n + 1 N @HB 3. Fall: SCAN bei der Suche nach der Spur und SATF bei der Positionierung auf den Sektor @HP ta_max - ta_min T E [z] = ta_min + ───────────────── + ─── @HB(= 2. Fall)@HP n + 1 N @HB Obwohl SCAN und SSTF mathematisch die gleichen Erwartungswerte haben, zeigen praktische Messungen (siehe folgendes Bild), daß die SSTF- Strategie etwas besser ist. Dies kommt daher, daß sie immer die tatsäch- lich nächste Anforderung, von der augenblicklichen Position des Schreib-/ Lese-Arms ausgehend, auch als nächste behandelt. Allerdings hat die SSTF-Strategie den Nachteil, daß sie die Spuren am Rand (innen und außen) benachteiligt. @HEMessung der Bedienzeit an der IBM-Platte 2314 @HL+ @HB: FCFS @HA E [B] in msec @HK* @HB: SCAN @HP/│\ @HCo @HB: SSTF @HA100 @HP┤ @HP│ @HA80 @HP┤@HCo@HK*@HL+@HCo@HK*@HL+@HCo@HK*@HL+ @HK*@HL + + + + + + + + + + + + + + + + + + + @HP│ @HCo @HK* @HA60 @HP┤ @HCo @HK* @HP│ @HCo @HK* @HA40 @HP┤ @HCo @HK* @HP│ @HCo @HK* @HA20 @HP┤ @HCo@HK*@HCo@HK*@HCo@HK*@HCo@HK*@HCo@HK*@HCo@HK*@HCo@HK*@HCo@HK*@HCo@HK*@HCo@HK*@HCo@HK*@HCo . @HP│ @HP└─────────┬─────────┬─────────┬─────────┬─────────┬──────> @HA 10 20 30 40 50 Anforderungen pro Sekunde @HEMessung der Wartezeit in der Queue an der IBM-Platte 2314 @HL+ @HB: FCFS @HA E [W] in msec @HK* @HB: SCAN @HP/│\ @HCo @HB: SSTF @HA 10 @HP┤ @HL+ @HCo @HK* @HP│ @HL+ @HCo @HK* @HA 8 @HP┤ @HL+ @HCo @HK* @HP│ @HL+ @HCo @HK* @HA 6 @HP┤ @HL+ @HCo @HK* @HP│ @HL+ @HCo@HK* @HA 4 @HP┤ @HL+ @HCo@HK* @HP│ @HL+ @HCo@HK* @HA 2 @HP┤@HCo@HK*@HCo@HK*@HL+@HK*@HCo@HK* @HK* @HP│@HL+ @HP└─────────┬─────────┬─────────┬─────────┬─────────┬──────> @HA 10 20 30 40 50 Anforderungen pro Sekunde @HBweiter mit ⌐Ablagestrategie@BS___7¬ AHBAA #!!# Ablagestrategie @HEAblagestrategien für Dateien auf Platte @HB Beim Lesen einer Datei muß man zu dem Zylinder, auf dem sie sich befindet. Man kann an der Zugriffszeit nichts mehr ändern. Dateien sollten deshalb möglichst in einem Zylinder liegen. Wenn ein Zylinder nicht ausreicht, muß man die Datei zerstückeln und noch freien Speicherplatz suchen. Dafür wird eine Freispeicherliste verwendet. Da die Freispeicherliste nach einiger Zeit zerstückelt und weit gestreut ist, dauert der Zugriff auf eine zerstückelte Datei mit der Zeit immer länger. Die einzige Möglichkeit, dies zu umgehen, ist eine Neuorganisation der Dateien auf der Platte. @HBFalls noch ausreichend Platz auf der Platte ist, kann die Neuorganisation durch Verlagern der Dateifragmente und anschließendes Zusammenfügen der Fragmente zu zusammenhängenden Speicherblöcken erfolgen. Ist die Platte zu voll belegt, müssen die Dateien auf Band gesichert werden, die Platte neu formatiert und anschließend mit den gespeicherten Dateien wieder beschrieben werden. Beispiel: Messungen unter UNIX Durchsatz 175 kByte / sec Durchsatz nach ca. 3 Wochen : 30 kByte / sec Die Messungen des Durchsatzes erfolgten bei gleicher Belegung der Platte. weiter mit ⌐Hintergrundzugriff@BS___7¬ AHBAA #!!# Hintergrundzugriff @HEZugriff auf Hintergrundspeicher @HB Ziel einer guten Hintergrundspeicher-Verwaltung ist es, die notwendigen Hintergrundzugriffe möglichst schnell zu bearbeiten und ihre Anzahl möglichst gering zu halten. Einen wesentlichen Einfluß darauf nehmen a) @HPdie Sektorgrößen:@HB Je größer die Sektoren sind, desto weniger Hintergrundzugriffe sind notwendig. Der Nachteil ist aber der starke Anstieg der Fragmentierung (Verschnitt). Außerdem geht die eigentliche Idee der dynamischen Speicher- verwaltung, das Paging, verloren. @HB b) @HPdas Arbeiten mit logischen und physischen Sektoren:@HB Beispiel: i) 1. Sektor der Datei 4096 Byte die anderen Sektoren der Datei 1024 Byte 1 logischer Sektor (4096 Byte) entspricht 8 pysikalischen Sektoren (à 512 Byte) ==> Durchsatz: 20 % ii) Datei besteht nur aus Sektoren der Größe 1024 Byte 1 logischer Sektor entspricht 1 physikalischen Sektor ==> Durchsatz: 3 % @HBDas Arbeiten mit logischen Sektoren kann mit einem Zwischenpuffer (Cache) im Arbeitsspeicher realisiert werden. Man muß dann nicht immer gleich auf die Platte zugreifen, sondern benutzt den Zwischenpuffer. Wenn sich der Zwischenpuffer ändert, wird er nach 30 sec auf die Platte geschrieben. Dadurch ist auch der gewaltige Anstieg des Durchsatzes in dem Beispiel von 3 % auf 20 % zu verstehen. weiter mit Ihrer ⌐DIPLOMPRÜFUNG@BS___7¬ YAOME #!!# DIPLOMPRÜFUNG Darf man gratulieren ?!