DE60123396T2

DE60123396T2 - Diskzuordnungssystem mit umordnung einer begrenzten anzahl von anforderungen

Info

Publication number: DE60123396T2
Application number: DE60123396T
Authority: DE
Inventors: A. Michael Los Gatos DEMONEY
Original assignee: Sun Microsystems Inc
Current assignee: Sun Microsystems Inc
Priority date: 2000-02-28
Filing date: 2001-02-28
Publication date: 2007-08-09
Anticipated expiration: 2021-03-01
Also published as: WO2001065835A2; WO2001065835A3; ATE341154T1; KR20030001367A; US20030079080A1; AU2001245457A1; EP1262062B1; JP2003525486A; DE60123396D1; EP1262062A2; US6496899B1

Description

TECHNISCHER HINTERGRUND DER ERFINDUNG
1. Technisches Gebiet der Erfindung
Diese Erfindung betrifft Computerdatenspeicher- und -serversysteme und insbesondere digitale Video-/Videospeicher und Playbacksysteme, die mehrere kontinuierliche Medienströme unterstützen.
2. Beschreibung des relevanten Standes der Technik
Multimedia- oder Videoserversysteme werden in einer Vielzahl von Anwendungen für das Speichern und das Abspielen von Video-, Audio- oder anderen Multimediadatenströmen genutzt. Beispielsweise können Multimediaserver verwendet werden für Sende-, Kabel- oder Satellitenlösungen, um Multimediainformation zu Clients oder zu Konsumenten zu verteilen. Professionelle Sender und damit verbundene Serviceprovider, wie zum Beispiel Netzwerke und Affiliates oder Kabelprovider, können digitale Videoserver einsetzen, um Multimediasendeanwendungen mit hoher Bandbreite einschließlich Multikanalprogrammausspielung, Werbeeinfügung und digitalem Inhaltsmanagement unterstützen. Andere Anwendungen für Multimediaserversysteme können computerbasiertes Training beinhalten, in dem Multimediatrainingsmaterialien oder Vorträge auf dem Serversystem gespeichert sein können, auf welches von Studenten über ein Netzwerk oder das Internet zugegriffen wird.
Die Videoarchivierung, das Durchsuchen und das Abrufen ist eine andere Multimediaserveranwendung. Verschiedene Filme können auf dem Server gespeichert sein und auf Anfrage an Benutzer verteilt werden. Video-on-demand oder Videoliefersysteme können eine Mehrzahl von Benutzern oder Zuschauern in die Lage versetzen, selektiv Filme oder andere Audio-/Videosequenzen, die auf einem oder mehreren Videoservern oder Medienservern abgelegt sind, anzusehen. Die Videoserver können über Datenübertragungskanäle, wie zum Beispiel ein Kabelsendesystem, ein Satellitensendesystem oder das Internet mit der Mehrzahl von Benutzern oder Teilnehmern verbunden sein. Die Videoserver können eine Mehrzahl von Filmen oder anderen Audio-/Videosequenzen speichern und jeder Benutzer kann einen oder mehrere Filme von den Videoservern für das Betrachten auswählen. Jeder Benutzer kann einen Fernseher oder eine andere Betrachtungsvorrichtung sowie die entsprechende Decodierlogik für das Auswählen und Ansehen gewünschter Filme haben. Wenn ein Benutzer einen Film auswählt, kann der ausgewählte Film auf einem der Datenübertragungskanäle zu der Anzeigevorrichtung des jeweiligen Benutzers überfragen werden. Multimediaserver werden ebenso in Webcastinganwendungen verwendet, bei denen eine Veranstaltung mittels Multicast-Verfahren über das Internet zu verschiedenen Teilnehmern übertragen wird. Multimediaserver findet man auch in vielen anderen Anwendungen.
Um die Anforderungen von vielen unterschiedlichen Anwendungen und Benutzern zu erfüllen, ist es für ein Multimediaserversystem wünschenswert, Flexibilität und Erweiterbarkeit zur Verfügung zu stellen. Zwei wichtige Anforderungen für ein Multimediaserversystem sind der Speicherplatz und die Dateisystembandbreite. Multimediadaten, wie beispielsweise digitales Vollbewegungsvideo, erfordert eine große Speichermenge und eine große Datenübertragungsbandbreite. Somit verwenden Multimediasysteme verschiedene Typen von Videokomprimierungsalgorithmen, um die Menge an notwendigem Speicher und notwendiger Datenübertragungsbandbreite zu reduzieren. Im allgemeinen gibt es verschiedene Videokomprimierungsverfahren für stehende graphische Bilder und für Vollbewegungsvideos. Videokomprimierungsverfahren für stillstehende Graphikbilder oder einzelne Videoeinzelbilder können Intraframe-Komprimierungsverfahren sein und Komprimierungsverfahren für bewegtes Video können Intertrame-Komprimierungsverfahren sein.
Beispiele der Videodatenkomprimierung für stillstehende Graphikbilder sind das RLE (Lauflängencodierung) und die JPEG (Joint Photographic Experts Group) Komprimierung. Obgleich JPEG-Komprimierung ursprünglich für die Komprimierung von stilstehenden Bildern anstelle von Video entwickelt wurde, wird die JPEG-Komprimierung in einigen bewegten Videoanwendungen verwendet. Die meisten Videokomprimierungsalgorithmen sind dafür vorgesehen, vollbewegtes Video zu komprimieren. Beispiele von Videokomprimierungstechniken sind MPEG (Moving Pictures Experts Group), MPEG-2, DVI (Digital Video Interactive) und Indeo unter anderen.
Selbst mit der Verwendung von Komprimierungstechniken erfordern Multimediaanwendungen immer noch extrem große Speichermengen. Beispielsweise kann ein zweistündiges Video, das mit 1 Mb pro Sekunde codiert ist, ein Gigybyte (1 Gb) an Speicher erfordern. Ein System, das zahlreiche unterschiedliche Inhalte unterstützt, erfordert bis zu einigen Terabyte (TB) an Speicher. Das Serversystem muß ebenso in der Lage sein, genügend Bandbreite für die verschiedenen Benutzer bereitzustellen, um auf einen ausgewählten Multimediainhalt zuzugreifen, ohne das Speichersystem zu überlasten. Beispielsweise kann für einen Server, um gleichzeitig 100 Teilnehmer, die Multimediainhalt betrachten, der mit 1 Mb pro Sekunde codiert ist, zu unterstützen, eine Bandbreite von mehr als 100 Mb pro Sekunde erforderlich sein, wenn Overhead erlaubt wird. Falls nicht genügend Bandbreite verfügbar ist, dann müssen einige Anfragen abgelehnt werden oder die Abspielqualität kann darunter leiden (Video kann zu langsam abspielen oder kann „holprig" erscheinen). Um solche Speicher- und Bandbreitenanforderungen zu erfüllen, kann ein Multimediaserver ein oder mehrere RAID (Redundant Array of Inexpensive Drives) Speichersysteme erfordern. In einem RAID-System können für eine gegebene Multimediadatei Blöcke aus Multimediadaten über mehrere Festplatteneinheiten gespeichert werden. Die Blöcke können ausgelesen oder zu dem Kommunkationsnetzwerk übertragen werden und zu dem Benutzer oder den Benutzern übertragen oder gesendet werden. Am Empfangsende können die Blöcke für die Betrachtung durch den Benutzer auf einer Anzeigevorrichtung decodiert werden.
Die Platten von jeder Festplatte können als in Zonen unterteilt angesehen werden. Da sie physikalisch größer sind, enthalten Tracks bzw. Spuren in Zonen im Außenbereich der Platte mehr Sektoren als Tracks in Zonen nahe der Rotationsachse der Platte. Nimmt man an, daß die Platten mit konstanter Geschwindigkeit rotieren, ist daher die Datenbandbreite, die durch die äußersten Zonen verfügbar ist, größer als die verfügbare Bandbreite der innersten Zonen. Selbst mit modernen Festplattenlaufwerken kann es eine 2-1 Variation zwischen worst case und durchschnittlicher Plat tenübertragungsbandbreite geben aufgrund von Sektor-/Track-Variationen zwischen äußeren und inneren Zonen.
Viele Multimediaanwendungen erfordern kontinuierliche Medienströme, in denen Datenströme mit einer spezifizierten und möglicherweise in der Zeit variierenden Datenrate und mit einer spezifizierten Gleichförmigkeit dieser Lieferrate geliefert werden müssen. In einigen Fällen kann die Gleichförmigkeit durch die Liefergeschwindigkeit nachteilig beeinflußt werden durch den Algorithmus, der verwendet wird, um die Plattenzugriffsanforderungen zu erfüllen. Die Verwendung eines „first come, first served"-Plattenzugriffsalgorithmus muß nicht immer der effizienteste Weg sein, um Plattenanforderungen zu erfüllen, da die Bewegung des Lese-Schreibkopfes (der verwendet wird, um auf Informationen auf der Platte zuzugreifen) nicht optimal sein kann. Eine Optimierung der Kopfbewegung kann durch die Verwendung von Algorithmen verwirklicht werden, welche die Plattenanforderungen neu ordnen. In solchen Neuordungsalgorithmen können Plattenanforderungen in einer Ordnung erfüllt werden, die sich von der Ordnung unterscheidet, in der sie ausgegeben wurden. Solch ein Neuordnungsalgorithmus ist als ein „Aufzug"-Algorithmus bekannt. In einem typischen Aufzugs-Algorithmus überstreicht der Kopf des Plattenspeichersystems die Platte von außen nach innen und erfüllt Plattenanforderungen und schreibt in die Warteschlange entlang des Weges und kehrt dann die Richtung um. Während dieser Algorithmus eine effizientere Bewegung des Lese-Schreib-Kopfes erlaubt, können sehr ungleichförmige Zugriffszeiten entstehen, da neu einkommende Anforderungen vor vorher in die Warteschlange stehenden Anforderungen erfüllt werden. Eine große Anzahl von neu ankommenden Anforderungen kann lange Verzögerungen bei der Erfüllung von vorher in die Warteschlange gestellten Anforderungen mit sich bringen.
Nicht-gleichmäßige Plattenzugriffszeiten können für viele Anwendungen, insbesondere Multimediaanwendungen, nachteilig sein. Beispielsweise kann eine Videoabspielung von einem Plattenspeichersystem fehlerhaft erscheinen, wenn die Plattenzugriffszeiten nicht gleichförmig sind. Audioabspielung kann in einer ähnlichen Weise beeinflußt werden. Im Grunde genommen kann die Qualität einer Multimediadarstellung, die auf Plattenspeichersystem mit nicht gleichförmigen Zugriffszeiten zugreift, leiden.
Die internationale Patentanmeldung WO 99/15953 beschreibt ein System, in dem Plattenzugriffsanforderungen blockiert werden, bis ein relativ großer Satz von Anforderungen gesammelt wurde. Ein Planer sortiert dann die Ordnung der Anforderungen gemäß der physikalischen Verteilung der Sektoren auf einer Platten, auf die zugegriffen wird.
Die US-Patentanmeldung US-A-5,708,632 beschreibt eine Zugriffssteuervorrichtung, die eine Ordnung einer Mehrzahl von eingehenden Plattenzugriffsanforderungen plant, so daß die Summe der Bewegung des Kopfes gering wird und der Zugriff auf die Aufzeichnungsplatte auf dem Ergebnis der Planung beruht. Die Vorrichtung weist einen Blockzuweiser auf, der bestimmt, wie die Daten auf einer Platte angeordnet werden.
Die US-Patentanmeldung US-A-5,644,786 beschreibt ein Verfahren für das Planen mehrerer Prozeßanforderungen für den Lese-/Schreibzugriff auf eine Plattenspeichervorrichtung innerhalb eines Computersystems. Das Verfahren betrachtet die Platteneigenschaften, wie zum Beispiel die Anzahl von Sektoren pro Spur, die Anzahl von Spuren pro Zylinder, die Geschwindigkeit der Plattendrehung und die Kapazität des Plattencontrollers eine Warteschlange zu bilden, bei der Bestimmung der optimalen Ordnung für das Ausführen von Prozeßanforderungen.
Die europäische Patentanmeldung EP-A-0,716,370 beschreibt ein Verfahren und eine Vorrichtung für das Liefern von Multimediavideodaten von einem Server zu einer Mehrzahl von Clients. Datenpakete werden entlang Platten in Einheiten von festen Abspielzeiten zerlegt, selbst wenn solche Einheiten zu Streifen variabler Länge führen.
Ein Artikel mit dem Titel „I/O issues in a multimedia system" (Computer, IEEE Computer Society, Long Beach, CA, US, Band 27, Nr. 3, 1. März 1994, Seiten 69–74, XP000443072 ISSN: 0018-9162) von Narasimha beschreibt eine Anzahl von Plattenplanalgorithmen, wie zum Beispiel den „earliest deadline first" (EDF) bzw. „früheste Deadline zuerst", „circular scan" (Cscan) bzw. „kreisförmige Abtastung" und „scan EDF".
ZUSAMMENFASSUNG DER ERFINDUNG
Die oben beschriebenen Probleme können zu großem Teil durch ein System und Verfahren der begrenzten Plattenanforderungsneuordnung in Übereinstimmung mit der vorliegenden Erfindung, die durch die Ansprüche 1 und 11 festgelegt ist, gelöst werden. In einer Ausführungsform können die Plattenzugriffsanforderungen während des Passierens eines Plattenkopfes entlang der Platte durchgeführt werden. Jedes Durchlaufen kann eine spezifizierte Bewegungsrichtung haben. Eine Mehrzahl von Plattenzugriffen kann während eines Plattenkopfdurchlaufs durchgeführt werden. In machen Fällen können die Plattenzugriffe in einer Ordnung durchgeführt werden, die sich von der Ordnung unterscheidet, in der die ursprünglichen Plattenzugriffsanforderungen empfangen wurden. Die Gesamtzahl von Plattenzugriffsanforderungen für einen gegebenen Plattenkopfdurchlauf kann auf ein Maximalzahl N beschränkt sein. Durch Beschränken der Anzahl von Plattenanforderungen für jeden Durchlauf kann effektiv die Zeit begrenzt werden, die benötigt wird, um irgendeine einzelne Plattenanforderung ungeachtet jeglicher Neuordnung zu erfüllen. Die Plattenkopfbewegung kann trotzdem optimiert werden.
In einer weiteren Ausführungsform pflegt ein Plattenspeichersystem eine Liste von Plattenkopfdurchläufen, bekannt als Durchlaufsliste. Jeder Durchlauf beinhaltet verschiedene Komponenten. Die erste Komponente eines Durchlaufs ist eine Variable für die Richtung der Plattenkopfbewegung für einen gegebenen Durchlauf und kann einen Wert von „low-to-high" oder „high-to-low" haben. Im Ergebnis bestimmt diese Variable, ob ein gegebener Durchlauf von dem äußeren Abschnitt der Platte zu dem inneren Abschnitt oder umgekehrt liest. Die zweite Komponente des Durchlaufs ist eine geordnete Liste von Plattenzugriffsanforderungen (die Plattenanforderungsliste), die während des gegebenen Durchlaufs erfüllt werden sollen. Die dritte Komponente eines Durchlaufs ist ein Variable, welche die Anzahl von Plattenanforderungen in der Plattenanforderungsliste anzeigt. Diese Variable wird begrenzt von einem Maximalwert („N"), um die Anzahl von Plattenanforderungen zu begrenzen, die für einen bestimmten Durchlauf erfüllt werden sollen. Eine vierte Komponente eines Durchlaufs ist die Boolesche Variable „Active". Die Active-Variable kann auf einen Wert „falsch" vor der Durchführung des Durchlaufs gesetzt werden und kann „wahr" werden, wenn der Durchlauf in Betrieb ist. Die letzte Komponente eines Durchlaufs ist die gegenwärtige Plattenblockadresse oder die Plattenadresse, an der der Plattenkopf zu einem gegebenen Zeitmoment lokalisiert ist. Da die Bewegungsrichtung des Plattenkopfs sich mit jedem neuen Durchlauf umdreht, kann die Anzahl von Durchläufen in der Durchlaufliste auf eine gerade Zahl beschränkt sein.
Das System einer Ausführungsform kann zwei Algorithmen durchführen, einen Warteschlangenalgorithmus für das in-die-Warteschlange-stellen von eingehenden Plattenanforderungen und einen Ausführungsalgorithmus für das Erfüllen der in der Warteschlange stehenden Anforderungen. Der Warteschlangenalgorithmus führt die Funktion des Plazierens einer neu angekommenen Plattenanforderung in einem Durchlauf der Durchlaufliste durch. Die neu angekommene Anforderung kann in die Plattenanforderungsliste eines aktiven Durchlaufs (active = wahr) oder eines anhängigen Durchlaufs (active = falsch) plaziert werden. Der Ausführungsalgorithmus führt die in der Warteschlange stehenden Anforderungen jedes Durchlaufs der Durchlaufliste aus.
Die Struktur der Algorithmen kann die Plattenkopfbewegung optimieren und gleichförmigere Plattenzugriffszeiten ungeachtet jeder Neuordnung erlauben. Da die Anzahl von Plattenzugriffen für einen gegebenen Durchlauf durch einen Maximalwert („N") beschränkt ist, kann die Zeit, um eine gegebene Plattenanforderung zu erfüllen, ebenso begrenzt sein. Im Ergebnis verwendet das System einen Aufzugsalgorithmus mit einer beschränkten Maximalverzögerung für eine gegebene Plattenanforderung.
Somit kann das System und das Verfahren der begrenzten Plattenanforderungsneuordnung es in verschiedenen Ausführungsformen erlauben, daß Plattenanforderungen neu geordnet werden und in spezifizierten Grenzen erfüllt werden. Dies kann zu einer Optimierung der Plattenkopfbewegung führen und weiterhin gleichförmige Plattenzugriffszeiten erlauben. Die Gleichmäßigkeit der Plattenzugriffszeiten kann das System für bestimmte Anwendungen geeigneter machen, in denen ein relativ gleichmäßiger Datenstrom erforderlich ist. Im Grunde genommen kann das System insbesondere für die Verwendung mit verschiedenen Multimediaanwendungen geeignet sein.
KURZE BESCHREIBUNG DER FIGUREN
Andere Ziele und Vorteile der Erfindung werden deutlich anhand der folgenden detaillierten Beschreibung unter Bezug auf die begleitenden Zeichnungen, in denen:
1 einen Datenplazierungs-/-Planungsmechanismus, abhängig von einer konstanten Zeit-/variabler Datenrate darstellt,
2 eine Darstellung eines Videoserver- und -speichersystems ist,
3 eine Darstellung eines verteilten Multimedia-Dateisystems ist, welches eine Anzahl von Videoservern und Dateisystemen einsetzt,
4 ein detailliertes Diagramm eines Videospeichermanagers ist,
5 ein Beispiel eines variablen zeitratenunabhängigen Plazierungsmechanismus für eine konstante Datenrate des Videospeichermanagers für zwei gleichzeitige kontinuierliche Medienströme darstellt,
6 ein Flußdiagramm ist, das einen Zugriffsmechanismus mit konstanten Daten und variabler Zeit darstellt, der Pufferringe und Deadline-Warteschlange einsetzt,
7 eine System darstellt, das sowohl garantierte Geschwindigkeitsströme und nichtgeschwindigkeitsgarantierte Zugriffe mit verfügbarer Geschwindigkeit bereitstellt,
8 ein Beispiel eines Zyklus darstellt, mit dem Anforderungen von der Deadline- und Prioritätswarteschlange zu dem Speichersystem migriert werden,
9 ein Flußdiagramm ist, das ein Verfahren darstellt für das Bereitstellen von Speicherzugriffen für mehrere kontinuierliche Medienströme mit einer garantierten Geschwindigkeit und einem Speicherzugriff für Zugriffe mit nicht garantierter Geschwindigkeit,
10 einen Videospeichermanager darstellt, der die in den 4 und 7 dargestellten Mechanismen kombiniert,
11 ein Flußdiagramm ist, das die Funktion der in 10 gezeigten Suchneuordnung darstellt,
12 ein Flußdiagramm ist, das die Speichercharakterisierung für die Zugriffssteuerung darstellt,
13 ein Flußdiagramm ist, das die Bestimmung der optimalen Zahl von Puffern für einen Pufferring für eine Vielzahl von Stromraten darstellt,
14 ein Flußdiagramm ist, das ein Verfahren zum Planen von Plattenzugriffsanforderungen in einer Durchlaufliste für eine Ausführungsform darstellt,
15 ein Beispiel einer Ausführungsform einer Durchlaufliste ist, die für das Planen von Plattenzugriffsanforderungen verwendet werden kann unter Verwendung des Verfahrens von 14 und
16 ein Flußdiagramm ist, das eine Ausführungsform eines Verfahrens des Ausführens der Plattenzugriffsanforderungen, die unter Verwendung des Verfahrens in 14 geplant wurden. Während die Erfindung verschiedenen Modifikationen und alternativen Formen zugänglich ist, werden hier spezielle Ausführungsformen hiervon beispielhaft in den Figuren gezeigt und im Detail beschrieben. Es versteht sich jedoch, daß die Figuren und die Beschreibung nicht dafür vorgesehen sind, die Erfindung auf die speziellen beschriebenen Formen zu beschränken, sondern die Erfindung im Gegenteil alle Modifikationen, Äquivalente und Alternativen abdecken soll, die in den Geist und den Schutzbereich der vorliegenden Erfindung fallen, wie er durch die angefügten Ansprüche festgelegt ist.
DETAILLIERTE BESCHREIBUNG DER ERFINDUNG
In 2 ist ein Videoserver und -speichersystem 200 dargestellt. Das System 200 beinhaltet einen Server 202 und Speichersysteme 204. Die Speichersysteme 204 können mit dem Server 202 durch ein oder mehrere Busse 205 verbunden sein. Der Server kann ein oder mehrere Prozessoren (nicht gezeigt) beinhalten, der mit den Speichersystemen 204 über einen peripheren Bus, wie zum Beispiel ein oder mehrere PCI-Busse und ein oder mehrere SCSI-Schnittstellen, kommunizieren kann. Der Server 202 kann ebenso eine Anzahl von Codecs (Codierer oder Decodierer) für das Codieren und Decodieren von Multimediadatenströmen beinhalten. Die Codecs können ebenso mit ein oder mehreren PCI-Bussen verbunden sein. Jedes Speichersystem 204 kann ein oder mehrere RAID-Systeme beinhalten, wie gezeigt.
Um mehrere kontinuierliche Medienströme zu unterstützen, in denen Datenströme mit einer spezifizierten und möglicherweise in der Zeit variierenden Datengeschwindigkeit geliefert werden, beinhaltet der Server 202 einen Videospeichermanager 206. Der Videospeichermanager steuert die Speicherung und den Zugriff von Multimediaströmen auf den Speichersystemen 204. In einer bevorzugten Ausführungsform werden die Multimediadateien über den Videospeichermanager 206 im MPEG-2-Hochqualitäts-Format gespeichert, obgleich andere geeignete Komprimierungsformate verwendet werden können. Client oder Anforderer für einen Multimediastrom kontaktieren den Videospeichermanager 206 für den Zugriff auf eine Datei mit einer gewünschten Bitrate. Der Videospeichermanager 206 greift auf verfügbare Speicherbandbreite und verfügbaren Pufferspeicher zu, um zu bestimmen, ob die Anforderung erfüllt werden kann oder ob nicht. Sobald der Videospeichermanager nachgewiesen hat, daß die Anforderung aufgenommen werden kann, wird dem Client Zugriff auf die Datei mit irgendeiner Bitrate bis zur vereinbarten Rate gewährt. Falls die Anforderung eine verfügbare Speicherbandbreite überschreitet und/oder der Pufferspeicher erschöpft ist, muß der Videospeichermanager die Anforderung zurückweisen und der Client ist frei, die Anforderung anzupassen oder die Anforderung zu einem späteren Zeitpunkt erneut zu übertragen. Durch Bereitstellen einer garantierten Stromrate unterstützt der Videospeichermanager variable Bitratenzugriffe zusätzlich zu konstanten Bitratenzugriffen. Ein Client kann willkürlich die Zugriffsrate auf eine Datei von null Bits pro Sekunde zu irgendeinem Punkt bis zu der vereinbarten Rate variieren. Diese Flexibilität unterstützt eine Anzahl von Merkmalen einschließlich der einzelbildgenauen Initiierung und der Jog/Umspul-Funktionalität.
Mehrere unterschiedliche Clients können unterschiedliche Ströme mit unterschiedlichen Bitraten von dem Videospeichermanager anfordern. Diese Ströme können eine willkürliche Mischung aus Lese-, Schreib-, Stromrate und zugegriffenen Dateien sein. Jeder Strom kann eine unterschiedliche vereinbarte Rate haben und ein individueller Strom kann willkürlich in der Geschwindigkeit variieren bis zu der vereinbarten Rate, wobei die Gesamtzahl für alle Stromraten nicht die Gesamtstromkapazität des Serversystems überschreitet. Es gibt keine Anforderung, daß alle Ströme die gleiche Bitrate haben oder daß die Bitrate eines Stroms aus einem Satz von diskreten möglichen Raten ausgewählt wird. Der Videospeichermanager erlaubt es dem Client ebenso, auf dieselben Dateien, unterschiedliche Dateien oder irgendeine Kombination hieraus zuzugreifen. Wie unten beschrieben wird, stellt der Videospeichermanager diese Flexibilität bereit, ohne daß die gesamte Bandbreite des Servers negativ beeinflußt wird.
In 3 ist ein verteiltes Multimediadateisystem 300 dargestellt, das eine Anzahl von Videoservern 202 und Dateisystemen 204 einsetzt. In dieser Ausführungsform kommunizieren die Dateisysteme 204 mit Videoservern 202 über einen Faserkanal. Jedes Speichersystem 204 kann eine Anzahl von RAID-Systemen, die vor einem FCAL (fibre channel arbitrated loop) verbunden sind. Jeder Videoserver 202 kann ebenso mit seinem eigenen lokalen Dateisystem oder einer Bandbibliothek verbunden sein. Zusätzlich kann auf andere Speichersysteme, wie zum Beispiel einer Bandbibliothek, über das System über den Faserkanal zugegriffen werden. Clients können Multimediaströme anfordern, die über das Übertragungsnetzwerk 208 zu senden sind. Das Übertragungsnetzwerk 208 kann ein Computernetzwerk, das Internet, ein Sendesystem oder irgendein anderes geeignetes Übertragungsmedium für Multimediaströme sein. Ein Videospeichermanager, der ein oder mehrere der Videoserver ausführt, steuert die Initüerung und das Hinzufügen von Multimediaströmen für das Zugreifen auf Dateien auf den Speichersystemen 204. Der Videospeichermanager verwaltet mehrere kontinuierliche Medienströme, die über einen breiten Bereich von Hardware-Schnittstellen, wie zum Beispiel MPEG-Codierer und -Decodierer, DVB-Multiplexer, ATM, SONET und Ethernet Übertragungsnetzwerk 208 geliefert werden.
Der Videospeichermanager, wie er in Systemen wie in 2 und 3 dargestellt, eingesetzt wird, behandelt, wie Platten- oder Speicherzugriffe für mehrere kontinuierliche sequentielle Medienströme in einer Art und Weise geplant werden, die Daten für alle kontinuierlichen Medienströme garantiert und einen genauen Mechanismus bereitstellt für das Bestimmen, ob eine neue Anforderung für einen garantierten Geschwindigkeitszugriff aufgenommen werden kann.
In 4 ist ein detailliertes Diagramm eines Videospeichermanagers 206 gezeigt. Der Videospeichermanager 206 beinhaltet einen Anfrageprozessor 402, der eine Schnittstelle zwischen den Clientanforderungen und den Strommanagern 404 herstellt. Jeder Strommanager 404 pflegt einen Pufferring 405. Ein getrennter Strommanager 404 entspricht jedem kontinuierlichen Multimediastrom. Ein Dateisystem 406 wird für das Abbilden von Stromzugriffen auf die Speichersysteme 204 bereitgestellt. Die Plattenplaner 408 werden für jedes Speichersystem 204 bereitgestellt, um den Fluß aus Speicherzugriffen zu jedem Speichersystem zu handhaben. Jeder Plattenplaner kann eine Deadlinewarteschlange 410 haben, wie unten detaillierter beschrieben wird.
Der Videospeichermanager, das Dateisystem und der Plattenplaner plazieren Stromdaten auf den Speichersystemen in einer Art und Weise, die vollständig unabhängig von der inhärenten Bitrate des Materials ist. Dieses Merkmal stellt eine zusätzliche Flexibilität insofern bereit, daß Clients Inhalt von und zu dem Videospeichermanagerdateisystem mit garantiertem Geschwindigkeitsdienst mit Datenraten viele Male höher (oder kleiner) als die inhärente Geschwindigkeit der Stromdaten übertragen können. Der Videospeichermanager, das Dateisystem und der Datenplazierungsmechanismus sind ein Mechanismus mit fester Blockgröße. Beispielsweise werden Daten zu oder von den Speichersystemen in einer konstanten Blockgröße übertragen. In einer bevorzugten Ausführungsform kann eine Blockgröße von 256 KB gewählt werden. Der Videostrommanager kann die Konfiguration der Blockgröße während der Systeminitiierung oder -konfiguration bereitstellen. Der Mechanismus mit fester Blockgröße stellt sicher, daß keine äußere Fragmentierung des Spei chers auftritt und daß die innere Fragmentierung nur bei dem letzten Block der Daten auftritt (da eine Datei wahrscheinlich nicht exakt an einer Blockgrenze endet). Anders als geschwindigkeitsabhängige, variable Blockgrößenmechanismen, die sowohl unter der externen Fragmentierung als auch unter variierenden Graden der inneren Fragmentierung pro Block leiden, was abhängig von der Stromgeschwindigkeit und den gegenwärtigen Dateisysteminhalten, zu großen Variationen und Speicheranforderungen für eine bestimmte Datei führt, stellt der geschwindigkeitsunabhängige Mechanismus mit fester Blockgröße des Videospeichermanagers vorhersagbare Speicheranforderungen für jede Datei ungeachtet der Geschwindigkeit oder der gegenwärtigen Dateisysteminhalte sicher.
In 5 ist ein Beispiel des geschwindigkeitsunabhängigen Plazierungsmechanismus für konstante Datengröße und variable Zeit des Videospeichermanagers für zwei gleichzeitige kontinuierliche Medienströme dargestellt. Wie gezeigt, ist die Datenblockgröße für alle Medienströme fixiert, die Zeit, zu der auf einen Datenblock zugegriffen wird, variiert jedoch für jeden Strom entsprechend der gewünschten Bitrate.
Ein Problem, das sich aus einem Konstantdaten-(fester Block), variablen Zeitzugriffsordnungsmechanismus ergibt, ist, daß mehrere Ströme, jeder mit seiner eigenen Frequenz und Phase der Speicherzugriffe, Anforderungen an das Speichersystem senden und die Wechselwirkung dieser Zugriffsmuster zu Spitzen und Pausen in der Speicheraktivität führen. Die unterschiedliche Frequenz und Phasen der Speicherzugriffe durch die unterschiedlichen Strömungsergebnisse in Zeiten, in denen zahllose Zugriffe gleichzeitig anhängig sind und anderen Zeiten, in denen sehr wenig Zugriffe anhängig sein können. Eine Lösung für dieses Problem ist es, an die Speichersysteme einfach die Anforderung zu stellen, die Spitzenaktivitätsrate zu unterstützen, wobei diese Lösung eindeutig nicht kosteneffektiv ist.
In 4 behandelt der virtuelle Speichermanager der vorliegenden Erfindung das oben erwähnte Problem durch Ausgleichen der Speicheraktivität durch Einfügen eines Pufferrings zwischen jedem Client und dem Dateisystem. Der Medienstrom ist mit einem anderen Pufferring 405, der von einem Strommanager 404 verwaltet wird, verknüpft. Der Strommanager 404 verknüpft somit einen Ring aus Datenpuffern zwischen dem Anfordern von kontinuierlichen Medien und den Plattenuntersystemen. Die Anzahl von Puffern in einem Ring wird bestimmt gemäß der vereinbarten Garantierate des verknüpften Medienstroms und der Charakteristiken des Speichersystems, so daß die garantierte Geschwindigkeit immer erfüllt wird. Die Pufferringe 405 nutzen die Tatsache aus, daß der Videostrom inhärent sequentiell ist und läßt das Dateisystem Speicheranfragen vorher in eine Warteschlange stellen. Diese Ansatz erlaubt es, daß zukünftige Anforderungen während Pausen erfüllt werden, was die Belastung von Spitzenwerten in Belastungstäler verschiebt und die Speicheraktivität über die Zeit glättet.
Jeder Ring 405 aus N-Puffern wird verwendet, um die nächsten N-Blöcke des kontinuierlichen Medienstroms, auf den von dem Anforderer zugegriffen wird, zu halten. Sobald der Anforderer Daten eines Puffers in dem Ring erhalten hat, wird ein Zugriff auf den geeigneten Plattenplaner 408, den nun leeren Puffer zu füllen, in die Warteschlange gestellt, um den leeren Puffer mit dem näch sten Block für den Medienstrom zu füllen. Anforderungen, Puffer der Pufferringe 405 zu füllen (oder zu leeren), werden von dem Dateisystem 406 auf den geeigneten Plattenplaner 408 abgebildet. Das Dateisystem 406 bildet die logischen Blöcke auf die physikalischen Blöcke in den Speichersystemen 204 ab. Das Dateisystem 406 kann eine Abbildung von logischen auf physikalischen Blockort (zum Beispiel ein Knoten) pflegen. Da Anforderungen für mehrere Ströme in jedem Plattenplaner 408 in eine Warteschlange gestellt werden können, muß das System sicherstellen, daß eine zukünftige Anforderung von einem Strom nicht erfüllt wird, bevor eiligere Anforderungen von einem anderen Strom erfüllt werden, so daß die garantierte Übertragungsrate für jeden Strom beibehalten werden kann. Um dieses Ziel zu verwirklichen, werden Deadlines bzw. letzte Fristen mit jeder Anforderung, die zu einem Speicher eines Systems übertragen wird, verbunden. Das System berechnet die Deadline, so daß sie mit der Zeit übereinstimmt, die ein Puffer benötigen wird, um die Blockgröße der Stromrate und die Anzahl von bestehenden nicht konsumierten Puffern zu beachten. Wenn eine Anforderung nach einem leeren Puffer in die Warteschlange gestellt wird, wird eine Deadlinezeit mit der Anforderung in die geeignete Deadlinewarteschlange 410 in dem Plattenplaner 408 gestellt. Die Deadlinezeit zeigt die späteste Zeit an, wenn der Puffer gefüllt werden kann und immer noch die Anforderungen der garantierten Geschwindigkeit des bestimmten Stroms erfüllt. Die Deadlinezeit wird berechnet als: current_time + (N-1)·buff_time, wobei N die Anzahl von Puffern in dem Pufferring 405 ist und buff_time die Minimalzeit ist, in der ein Anforderer einen Puffer konsumieren kann ohne die verabredete Garantierate zu überschreiten. Der Plattenplaner 408 muß nun die Warteschlangenanforderung an das bestimmte Speichersystem 204 in einer Ordnung ausgeben, welche die Deadlines, die mit den Anforderungen verknüpft sind, erfüllt. Der Plattenplaner stellt die Anforderungen von kontinuierlichen Mediaanforderern in jede Deadlinewarteschlange 410 und behält eine Ordnung vom frühesten zum spätesten bei, so daß Anforderungen mit der frühesten Deadline zuerst erfüllt werden.
Damit das System die Deadline eines Stroms erfüllen kann, muß es einen ausreichend großen Pufferring einstellen, um sicherzustellen, daß jede Anforderung in dem Speichersystem früh genug vor seiner Deadline in die Warteschlange gestellt wird, so daß die schlimmstmögliche Servicezeit für die Anforderung die Deadline nicht überschreiten wird. Da die schlimmstmögliche Servicezeit eine Funktion der Gesamtlast auf dem System ist und die Gesamtlast eine direkte Folge der Gesamtstromrate (unabhängig von dem tatsächlichen Stromratenmix) ist, ist die Pufferringgröße für einen bestimmten Strom auf einem gegebenen Speichersystem eine Funktion dieser bestimmten Rate des Stroms und ist unabhängig von den Stromraten anderer Ströme in der Mischung. Aufgrund dieser Unabhängigkeit können geeignete Ringgrößen für verschiedene Stromraten und einer Speichercharakterisierungszeit erzeugt werden, wie unten weiter im Detail ausgeführt wird.
In 6 wird ein Flußdiagramm bereitgestellt, das den Konstantdaten-Variablen Zeitzugriffsmechanismus darstellt, der Pufferringe 405 und Deadline Warteschlangen 410 einsetzt. Wenn ein neuer Strom initiiert wird, bestimmt der Strommanager für den neuen Strom die garantierte Stromrate und die Blockgröße für den Strom, wie in 602 angezeigt. Der Strom ist an der angeforderten Datei über das Dateisystem 406 befestigt und der Strommanager 404 erzeugt einen Puffer ring 405 für den neuen Strom. Anforderungen nach Blöcken von der verknüpften Datei werden dann an die geeigneten Speichersysteme ausgegeben, um den Pufferring zu füllen. Jeder Puffer kann für einen Block dimensioniert sein. Nachdem der Pufferring gefüllt ist (606), kann die Datenübertragung beginnen, wie in 608 angezeigt ist.
Da jeder Puffer von dem Stromanforderer ausgelesen wird, wird eine Blockanforderung zusammen mit einer Deadlinezeit ausgegeben, um den jetzt verbrauchten Puffer zu füllen wie in 610 angezeigt. Die Blockanforderung und die Deadlinezeit werden in die Deadlinewarteschlange 410 für das geeignete Speichersystem entsprechend dem Ort, wo der angeforderte Block lokalisiert ist, gestellt. Die Anforderungen werden in der Deadlinewarteschlange von der frühesten bis zur spätesten Deadlinezeit sortiert. Anforderungen werden von der Deadlinewarteschlange entsprechend der frühesten Deadline ausgegeben, wie bei 612 gezeigt. Während der Datenübertragung wird auf die Puffer des Pufferrings nacheinander in einer kreisförmigen Art und Weise zugegriffen. Die Deadlinezeit stellt sicher, daß jeder Puffer gefüllt ist, bevor er von dem Stromanforderer entsprechend der garantierten Rate benötigt wird. Der Pufferring und die verknüpften Deadlinezeiten nutzen die inhärent sequentielle Natur des Multimediastrom, um Speicheranforderungen vorher in die Warteschlange zu stellen. Dies erlaubt es, daß zukünftige Anforderungen während Pausen der Speicheraktivität erfüllt werden, was die Last von Spitzen in Leistungstäler verschiebt und die Speicheraktivität über der Zeit glättet. Es sei bemerkt, daß, während 6 anhand von Stromleseanforderungen beschrieben wurde, derselbe Mechanismus für Stromschreibanforderungen eingesetzt werden kann. Da jeder Puffer mit einem Block aus Strömungsdaten gefüllt ist, kann eine Anforderung und eine Deadline in eine Deadlinewarteschlange gestellt werden, um den Block in das Speichersystem zu schreiben.
Der Videospeichermanager 206 unterstützt eine Mehrzahl von unterschiedlichen Medienstrom-Clients mit unterschiedlichen garantierten Raten. Ein anderer Medienstrommanager 404 und ein Ringpuffer 405 können für jeden Strom bereitgestellt werden. Ein getrennter Plattenplaner 408 und die Deadlinewarteschlange 410 werden für jedes Speichersystem 204 bereitgestellt. Somit kann jede Deadlinewarteschlange 410 Anforderungen entsprechend einiger unterschiedlicher Medienströme beinhalten. Die Deadlinezeiten für jede Anforderung in den Deadlinewarteschlangen 410 werden alle in Bezug auf eine gemeinsame jetzige Zeit berechnet, so daß die früheste Deadline von irgendeinem Anforderer, die in einer bestimmten Deadlinewarteschlange gespeichert ist, als erste ausgegeben wird. Die Zeit zwischen den Anforderungen, die für einen bestimmten Strom erfüllt werden, variiert, abhängig von der Anzahl von anderen anhängigen Anforderungen, wobei die verknüpfte Deadlinezeit sicherstellt, daß die garantierte Rate erfüllt wird.
Zusätzlich zu dem Bereitstellen von geschwindigkeitsgarantierten kontinuierlichen Medienströmen kann es für einen Multimediaserver wünschenswert sein, Zugriff auf in dem Speichersystemen gespeicherten Daten in einer priorisierten, jedoch nicht geschwindigkeits- bzw. ratengarantierten Art und Weise bereitzustellen. Solche Zugriffe dürfen die Garantien für die kontinuierlichen ratengarantierten Medienströme nicht beeinflussen. Beispielsweise kann ein NFS- oder FTP-Anforderer es wünschen, auf eine Datei zuzugreifen. Typischerweise erfolgen solche Zugriffe nicht in Echtzeit, und es ist keine garantierte Geschwindigkeit erforderlich. Solche Zugriffe können erfüllt werden unter Verwendung der Restplattenbandbreite, die verfügbar ist, nachdem alle Zugriffe mit garantierter Geschwindigkeit erfüllt sind. Jede Speicherbandbreite, die verbleibt, nachdem alle Anforderungen mit garantierter Geschwindigkeit erfüllt wurden, wird einem allgemeinen Pool zugewiesen. Verfügbare Bandbreiten-Clients können auf diese Bandbreite auf einer first-come, first-serve Basis zugreifen. Der Videospeichermanager bestimmt dynamisch die Größe der verfügbaren Bandbreite. Jede Bandbreite von einem nicht verwendeten garantierten Ratenkontrakt kann Teil des Pools aus verfügbarer Bandbreite werden.
In 7 ist ein System dargestellt, das sowohl Ströme mit garantierter Rate und Zugriffe mit nicht garantierter verfügbarer Rate bereitstellt. Wie in 7 gezeigt, kann der Videospeichermanager 206 Anforderungen von sowohl Clients mit garantierter Rate und Clients für verfügbare Rate akzeptieren. Ein Strompuffer 712 kann mit jedem Client für garantierte Rate verknüpft sein. In einer bevorzugten Ausführungsform ist jeder Strompuffer 712 ein Pufferring, wie in Bezug auf die 4 und 6 beschrieben. Anforderungen mit garantierter Rate werden durch das Dateisystem 406 auf einen geeigneten Plattenplaner 408 abgebildet und in eine Warteschlange 706 mit garantierter Rate gestellt. In einer bevorzugten Ausführungsform ist die Warteschlange mit garantierter Rate eine Deadlinewarteschlange, wie in Bezug auf die 4 und 6 beschrieben. Verfügbare Ratenanforderungen, die keine garantierte Rate haben, werden ebenso durch das Dateisystem 406 auf den geeigneten Plattenplaner für das Speichersystem, in dem die angeforderten Daten lokalisiert sind, abgebildet. Ein Datenpool 704 kann als gemeinsam genutzter Puffer für die verfügbaren Ratenanforderungen bereitgestellt werden. Verfügbare Ratenanforderungen werden in eine Prioritätswarteschlange 708, die mit jedem Speichersystem verknüpft ist, gestellt. Eine andere Quelle von Dateianforderungen kann das Dateisystem 406 selbst sein. Diese Anforderungen können Anforderungen für Metadaten beinhalten, die notwendig sind, um die verschiedenen Datenströme zu unterstützen (zum Beispiel Blöcke, die Listen von zu übertragenden Blöcken halten, wie zum Beispiel indirekte Blöcke). Dieser Typ von Metadatenanforderungen kann zeitkritisch insofern sein, daß die Datenübertragung stoppen wird, wenn ein Stromzeigerblock (indirekter Block), der auf den nächsten Datenblock zeigt, für den Strom nicht verfügbar ist. Somit tragen Anforderungen für zeitkritische Metadaten ebenso Deadlines und können direkt zusammen mit Stromdatenanforderungen in der garantierten Rate- oder Deadlinewarteschlange 706 geplant werden. Das Dateisystem überwacht konstant seinen Fortschritt mittels des gegenwärtigen indirekten Blocks. Bei einer geeigneten Grenze berechnet es eine Deadline und plant den Abruf des nächsten indirekten Blocks aus dem Speichersystem. Andre Metadatenabfragen können nicht-kritisch sein, wie zum Beispiel andere Typen des Dateimanagements und Lese- und Schreiboperationen, die nicht mit der Datenströmung in Bezug stehen (zum Beispiel Listen von Dateien in dem Dateisystem). Diese nicht-zeitkritischen Metadatenanforderungen werden in die Prioritätswarteschlange 708 gestellt. Ein Metadatenpool 702 kann mit dem Dateisystem 406 verknüpft sein, von dem die Metadatenanforderungen ausgegeben werden.
Obgleich andere Metadatenanforderungen und verfügbare Bandbreitenanforderungen keine strikten Servicezeitanforderungen haben, können sie eine Prioritätsbeziehung haben. Beispielsweise können Metadatenschreibvorgänge als mit höchster Priorität erachtet werden, da ihre Durchführung wichtig sein kann für das Schließen einer bestimmten Stromepisode. Metadatenlesevorgänge können als nächstes in der Priorität liegen, um die rechtzeitige Verarbeitung von Dateilisten, Dateierzeugungen, usw. sicherzustellen. Verfügbare I/O-Anforderungen können die geringste Priorität haben und können erfüllt werden, wenn Ressourcen verfügbar sind. Anforderungen in den Prioritätswarteschlangen werden von der höchsten zur niedrigsten Prorität geordnet.
Der Plattenplanmechanismus gibt die in der Warteschlange stehenden Anforderungen an das Speichersystem in einer Ordnung aus, welche die Deadlines, die mit den Anforderungen verknüpft sind, erfüllt und weist ebenso die Restbandbreite nach den garantierten Anforderungen den nicht garantierten Anforderungen n einer Art und Weise zu, die konsistent mit deren verknüpften Prioritäten ist. Ein Bandbreitenzuweiser 710 kann eingesetzt werden, um einen bestimmten Teil der Speicherbandbreite garantierten Ratenanforderungen zuzuweisen und den verbleibenden Bandbreitenteil den nicht garantierten Prioritätsanforderungen zuzuweisen. Zur Speichercharakterisierungszeit wird ein konfigurierbarer Prozentsatz der Bandbereite eines Speichersystems reserviert für das Akzeptieren der nicht garantierten Prioritätsanforderungen. Beispielsweise können 90% der Bandbreite für die garantierten Ratenanforderungen von der garantierten Ratewarteschlange 706 reserviert sein und die verbleibenden 10% können den nicht ratengarantierten Anforderungen von der Prioritätswarteschlange 708 zugewiesen werden. Basierend auf den reservierten prozentualen Anteilen für garantierte und nicht garantierte Anforderungen wählt der Plattenplaner eine Anforderung von der einen oder der anderen Warteschlange aus, um sie dem Betriebssystem zu übergeben, so daß sie vom Speichersystem erfüllt werden. Wenn die ausgewählte Anforderungswarteschlange leer ist, versucht der Planer eine Anforderung von der anderen Warteschlage zu erhalten, was somit nicht garantierten und garantierten Anforderungen erlaubt, nicht verwendete Speicherbandbreite zu absorbieren.
In einer bevorzugten Ausführungsform werden Anforderungen von der Deadline- und der Prioritätswarteschlange zu dem Speichersystem gemäß einem Zyklus migriert. Ein Beispiel eines Zyklus ist in 8 gezeigt. Ein Zyklus hat eine feste Anzahl von Slots, wobei jeder Slot entweder der Deadlinewarteschlange oder der Prioritätswarteschlange zugewiesen ist, und zwar in einem Anteil der gewünschten Zuweisung der Plattenbandbreite zwischen garantierten und nicht garantierten Zugriffen. In 8 verweisen Slots, die mit einem D markiert sind, zu der Deadlinewarteschlange und Slots, die mit einem P markiert sind, weisen auf die Prioritätswarteschlange. Die Slots werden wiederholt durchlaufen und eine Anforderung wird von der Warteschlange entsprechend dem gegenwärtigen Slot ausgewählt. In dem Beispiel von 8 ist die Bandbreite verteilt, so daß der Plattenplaner als erstes in der Deadlinewarteschlange für 13 von jeweils 16 Speicherzugriffen nachsieht und für die verbleibenden drei von jeweils 16 Zugriffen als erstes in der Prioritätswarteschlange nachsieht. Diese Zuweisung ist nur ein Beispiel, und in einer bevorzugten Ausführungsform kann die Zuweisung neun von zehn Slots, die auf die Deadlinewarteschlange zeigen, und einen von jeweils zehn Slots, der auf die Prioritätswarteschlange zeigt, sein. In einer bevorzugten Ausführungsform sind die Slots, die zu jeder Verwendung zugewiesen sind, so gleichmäßig wie möglich über den Zyklus verteilt.
In einer bevorzugten Ausführungsform werden Anforderungen von der Deadline- und der Prioritätswarteschlange zu dem Speichersystem migriert entsprechend den gegenwärtigen Slots, und der Zyklus setzt dann mit dem nächsten Slot fort. Wenn die Warteschlange, die durch den gegenwärtigen Slot angezeigt wird, leer ist, dann wird ein Eintrag von der anderen Warteschlange gewählt, wenn sie nicht leer ist. Daher können nicht ratengarantierte Anforderungen tatsächlich mehr als die ihnen zugewiesene Bandbreite erzielen, wenn die volle ratengarantierte Bandbreite durch die Deadlinewarteschlange nicht verwendet wird.
In 9 wird ein Flußdiagramm bereitgestellt, das ein Verfahren darstellt für das Bereitstellen von Speicherzugriff für mehrere kontinuierliche Medienströme mit einer garantierten Rate, und Speicherzugriff für nicht ratengarantierte Anforderungen. Ein Teil der Speicherbandbreite wird ratengarantierten Anforderungen zugewiesen und die Restbandbreite wird den nicht ratengarantierten Anforderungen zugewiesen, wie in 902 gezeigt. Ratenggarantierte Anforderungen werden in eine garantierte Ratenwarteschlange gestellt und nicht ratengarantierte Anforderungen werden in eine Prioritätswarteschlange gestellt, wie in 904 angezeigt. Die ratengarantierten Anforderungen werden in die ratengarantierte Warteschlange eingegeben und von dieser in einer Art und Weise ausgegeben, die sicherstellt, daß sie in einer rechtzeitigen Weise erfüllt werden, um die bestimmte Ratengarantie für jeden Strom zu erfüllen. Die nicht ratengarantierten Anforderungen können in der Prioritätswarteschlange geordnet werden, so daß die Anforderungen mit höherer Priorität vor Anforderungen mit niedriger Priorität erfüllt werden. Das System wählt dann eine Warteschlange aus, um eine Anforderung an das Speichersystem entsprechend einem gegenwärtigen Slot eines Zyklus auszugeben, der die Speicherbandbreite entsprechend der Bandbreitenzuweisung unterteilt, wie in 906 gezeigt. Falls die ausgewählte Warteschlange einen Eintrag erhält, dann wird diese Anforderung aus der ausgewählten Warteschlange ausgegeben, wie in 908, 910 und 912 angezeigt. Falls die ausgewählte Warteschlange leer ist, dann schaut das System in der anderen Warteschlange nach einer auszugebenden Anforderung, wie in 908 und 914 angezeigt. Falls die andere Warteschlange nicht leer ist, dann wird der Eintrag entfernt und ausgegeben, wie in 916 und 912 angezeigt. Das System durchläuft dann den Zyklus zu dem nächsten Slot, wie in 918 angegeben, und wiederholt den Warteschlangenauswahlprozeß. Falls die andere Warteschlange in 914 leer ist, wird der Prozeß wiederholt bis eine Warteschlange gefunden wird, die einen Eintrag enthält. In einer Ausführungsform wird der Slot nicht vorgerückt, wenn beide Warteschlangen leer sind. Alternativ dazu kann der Slot vorgerückt werden, wenn beide Warteschlangen leer sind.
In 10 ist ein Videospeichermanager dargestellt, der die Mechanismen kombiniert, wie in Bezug auf die 4 und 7 erläutert wurde. Der Speichermanager von 10 unterstützt mehrere kontinuierliche Medienströme, in denen Clients Zugriff auf eine Datei mit einer garantierten Bitrate vereinbaren. Jedem Strömungsclient wird es erlaubt, die Rate seines Zugriffs auf seine Datei von irgendeiner Geschwindigkeit bis zur garantierten Geschwindigkeit zu variieren. Zusätzlich unterstützt der Speichermanager von 10 verfügbare-Bandbreiten-Clients. Ein bestimmter Abschnitt der Speicherbandbreite wird der verfügbaren Bandbreite oder den nicht ratengarantierten Clients, wie zum Beispiel dem verfügbaren-Raten-Client 752 zugewiesen. Zusätzlich kann jede Bandbreite, die von den garantierten Ratenclients nicht verwendet wird, für die verfügbaren Raten-Clients verfügbar sein. Somit kann der Videospeichermanager von 10 jede Mischung aus garantierten Rate-Clients unterstützen, während dieselbe Gesamtbandbreite bereitgestellt wird und kann ebenso verfügbare Ratenclients mit einer nicht garantierten Rate unterstützen.
Wie in Bezug auf 4 erörtert, steht jeder garantierte-Raten-Client mit einem verknüpften Strommanager 404 in Verbindung, der einen Pufferring 405 für den bestimmten Strom hält. Der Pufferring wird verwendet, um die nächsten N-Blöcke des kontinuierlichen Medienstroms, auf die von dem Anforderer zugegriffen wird, zu halten, wobei N die Anzahl von Puffern im Pufferring ist. Jeder Puffer kann gleich einem Datenblock pro Puffer dimensioniert sein. Sobald ein Puffer in dem Ring seine Daten an den Anforderer abgegeben hat, wird eine Anforderung für den nun leeren Puffer zusammen mit einer Deadlinezeit mit dem geeigneten Plattenplaner 408, wie durch das Dateisystem 406 bestimmt, in die Warteschlange gestellt. Jede Deadlinezeit zeigt die letzte Zeit an, wenn die Pufferanforderung erfüllt werden kann und erfüllt immer noch die garantierten Ratenanforderungen des Stroms. Die Deadlinezeit kann berechnet werden zu: deadline_time = current_time + (N – 1)·buff_time,wobei N die Anzahl der Puffer im Ring ist und buff_time eine Minimalzeit ist, in der der Anforderer einen Puffer auslesen kann, ohne die vereinbarte garantierte Rate zu überschreiten. Gleichzeitig mit dem in die Warteschlange stellen der garantierten Ratenanforderungen bei dem geeigneten Plattenplaner 408 werden priorisierte, jedoch nicht garantierte Ratenanforderungen ebenfalls in die Warteschlange gestellt. Nicht garantierte Ratenanforderungen tragen keine Deadlines, tragen jedoch Prioritäten. Der Plattenplaner gibt die in der Warteschlange stehenden Anforderungen an die Speichersysteme in einer Ordnung aus, welche die Deadlines, die mit den Anforderungen verknüpft sind, erfüllt, während ein hoher Anteil der Plattensystembandbreite erhalten wird, und weist Restplattenbandbreite nach den garantierten Anforderungen an nicht garantierte Anforderungen zu in einer Art und Weise, die mit deren Prioritäten übereinstimmt.
Garantierte Anfordenungen von kontinuierlichen Stromanforderern werden in die früheste nach Deadlines geordnete Warteschlange 410 in dem geeigneten Plattenplaner plaziert. Nicht garantierte Ratenanforderungen werden in eine getrennte, nach höchster Priorität sortierte Warteschlange 708 plaziert. Zusätzlich zu den Anforderungen von verfügbaren-Raten-Clients 752 und garantierten-Raten-Clients 754 können Anforderungen auch von dem Dateisystem selbst können. Manche Anforderungen von dem Dateisystemkönnen zeitkritisch sein, wie zum Beispiel Anforderungen nach Blöcken, die Zeiger auf zukünftige Stromblöcke enthalten. Deadlines sind mit diesen Anforderungen verknüpft, und sie werden in die geeignete Deadlinewarteschlange 410 eingefügt. Andere Anforderungen, wie zum Beispiel nicht zeitkritische Dateimanagementanforderungen, werden einer Priorität zugewiesen und in die geeignete Prioritätswarteschlange 708 eingefügt. Die Dateisystemanforderungen können in einem Metapool 702 gepuffert werden. Verfügbare-Raten-Clientanforderungen können in einem Datenpool 704 gepuffert werden.
Anforderungen werden von der Deadline- und der Prioritätswarteschlange durch einen Bandbreitenzuweiser 710 entsprechend einem Zyklus migriert, welche Bandbreite nach einer konfi gurierbaren Zuweisung zuweist. Beispielsweise können 90% der Bandbreite eines bestimmten Speichersystems der Deadlinewarteschlange somit den garantierten-Ratenstrom-Clients zugewiesen werden, und 10% können der Priortätswarteschlange für verfügbaren-Raten-Clients zugewiesen werden. Der Bandbreitenzuweiser 710 kann die Anforderungen von den Deadline- und der Prioritätswarteschlangen in eine Suchneuordnungswarteschlange 750 migrieren. Die Anforderungen können in der Suchneuordnungswarteschlange entsprechend der Position des angefragten Datenblocks auf der Speichervorrichtung neu geordnet werden. Die Suchneuordnungswarteschlange kann eine konfigurierbare Maximalgröße haben. Anforderungen von der Deadline- und Prioritätswarteschlange werden zu der Suchneuordnungswarteschlange gemäß einem gegenwärtigen Zyklusslot migriert, wann immer die Suchneuordnungswarteschlange nicht auf deren Maximalgröße aufgefüllt ist. Jede Migration wird von der Warteschlange, die von dem gegenwärtigen Slot des Zyklus an gezeigt wird, migriert, und der Zyklus setzt dann mit dem nächsten Slot fort. Falls die Warteschlange, die von dem Slot angezeigt wird, leer ist, dann wird ein Eintrag von der alternativen Warteschlange ausgewählt, wenn sie nicht leer ist. Der migrierte Eintrag wird in der Suchneuordnungswarteschlange neu geordnet, so daß alle Anforderungen auf einer Seite des Eintrags sich auf Datenblöcke mit Speicheradressen größer oder gleich seiner Adresse beziehen, und alle Einträge auf der anderen Seite der Warteschlange sich auf Datenblöcke beziehen mit Plattenadressen kleiner oder gleich dessen Adresse.
Jede Suchneuordnungswarteschlange 750 wird gleichzeitig kontinuierlich in einer Richtung (d.h. in Richtung ansteigender oder abfallender Plattenadressen) durchlaufen, bis keine weiteren Einträge in der Warteschlange in dieser Richtung mehr existieren, und sie kehrt dann die Richtung um und nimmt den Durchlauf wieder auf. Somit gibt der Plattenplaner Anforderungen von der Suchneuordnungswarteschlange an das Speichersystem in der Ordnung der Plattenadresse aus und setzt mit der nächsten Anforderung fort, wenn die vorher ausgegebene Anforderung von dem Plattensystem erfüllt wurde.
Da die Deadline- und die Prioritätswarteschlange Anforderungen von vielen unterschiedlichen Strömen und Client enthalten, ist die Abfolge von Blöcken, die aus diesen Warteschlangen herrühren, im wesentlichen zufällig. Wenn diese Anforderungen entsprechend ihrer Ordnung in den Deadline- und Prioritätswarteschlangen bedient werden, würde ein exzessiver Plattensuchoverhead aus dem zufälligen Muster der Anforderungen herrühren. Die Suchneuordnungswarteschlange 750 verbessert die Suchzeit durch die Neuordnung der Anforderungen aus den Deadline- und Prioritätswarteschlangen entsprechend ihrer Plattenposition.
In 11 wird ein Flußdiagramm bereitgestellt, das die Funktion der Suchneuordnungswarteschlange 750 illustriert. Wie in Punkt 1102 dargestellt, wenn die Suchneuordnungswarteschlange nicht voll ist, wird eine Anforderung von entweder der Deadline- oder der Prioritätswarteschlange entsprechend dem gegenwärtigen Zyklusslot migriert. Falls die angezeigte Warteschlange leer ist, wird die Anforderung von der andere Warteschlange genommen, falls diese Warteschlange nicht leer ist, wie in 1104 angezeigt. Die migrierte Anforderung wird in die Suchneuordnungswarteschlange entsprechend der Plattenadresse des angefragten Blocks einsortiert, so daß Anforderungen in der Suchneuordnungswarteschlange durch ansteigende oder abfallende Plattenadressen sortiert sind. Gleichzeitig wird die Suchneuordnungswarteschlange in einer Richtung durchquert, und die nächste Anforderung wird an das Plattensystem ausgegeben, wie in 1108 angezeigt. Falls das Ende der Suchneuordnungswarteschlange erreicht wurde, dann wird die Richtung des Warteschlangendurchlaufs umgekehrt, wie in 1110 und 1114 angezeigt. Falls das Ende der Suchneuordnungswarteschlange noch nicht erreicht wurde, dann wird die gegenwärtige Durchlaufrichtung beibehalten, wie in 1110 und 1112 angezeigt. Sobald die gegenwärtige Anforderung von dem Dateisystem erfüllt wurde, wird die nächste Anforderung in der Suchneuordnungswarteschlange an das Dateisystem ausgegeben, wie in 1116 und 1108 angezeigt.
Wie früher erwähnt, sind die Blockanforderungen aus der Sicht des Speichersystems inhärent zufällig, da das Speichersystem mit Anforderungen von vielen Strömen zu tun hat. Bei dieser Zufälligkeit wäre es ineffizient, sequentiell Blöcke für eine bestimmte Datei zuzuweisen. Da I/O-Zylinder einer Platte häufig unterschiedliche Übertragungsgeschwindigkeiten haben, springt die Blockzuweisung innerhalb einer speziellen Datei vor und zurück zwischen I/O-Zonen der Platte. Somit werden für eine bestimmte Stromdatei Blockspeicheranforderungen Plattenadressen zugewiesen, so daß die Blocks in alternierenden I/O-Zonen der Platte lokalisiert sein werden. Dies stellt sicher, daß alle Dateien einen durchschnittlichen Speicherdurchsatz „sehen" und daß keine Datei, die übertragen wird, vollständig von einer Plattenzone mit niedriger Leistung kommen kann.
Wie oben erwähnt, muß der Videospeichermanager den Zutritt von neuen kontinuierlichen Strömen steuern, um sicherzustellen, daß die Summe der garantierten Stromraten nicht die Gesamtspeicherbandbreite, die den kontinuierlichen Medienströmen zugewiesen ist, überschreitet. Bevor irgendeine Übertragung beginnt, werden die Speichersysteme charakterisiert, um ihre Leistung oder Bandbreite zu bestimmen. Sobald eine Speichersystembandbreite bestimmt wurde, wird, wenn Übertragung beginnt, wenn jeder neue Strom angefragt wird, von dem Videospeichermanager bestimmt, ob oder ob nicht die angeforderte Bitrate die verbleibende verfügbare Bandbreite, die für kontinuierliche Ströme zugewiesen ist, überschreiten würde. Falls ja, wird die Anforderung abgelehnt und der Anforderer ist frei, die Anforderung zu einem späteren Zeitpunkt erneut zu übertragen oder mit einer Anforderung mit geringerer Bitrate. Falls ausreichend Bandbreite vorhanden ist, wird die Anforderung erlaubt, und ein Strommanager erzeugt einen verknüpften Pufferring, wie oben erörtert.
Da eine Abfolge von Anforderungen, die dem Speichersystem während der Übertragung präsentiert wird, im wesentlichen zufällig ist, kann das modellieren der Strombelastung, um die Speicherbandbreite zu charakterisieren, vereinfacht werden. Diese Leistung kann mit einer künstlichen Last charakterisiert werden, welche die Charakteristiken einer typischen Last reflektiert. Die künstliche Last kann variieren von einer völlig zufälligen Abfolge von Blöcken, was die Tatsache berücksichtigt, daß Blöcke für eine gegebene Datei in alternierenden I/O-Plattenzonen plaziert sein können. Somit kann eine repräsentative Last konstruiert sein durch Beschränken des Dateisystems, um sequentielle Blöcke in einer zufälligen Zonenanordnung zuzuweisen. Der Plattenblockadreßbereich kann in zwei Hälften unterteilt sein, und sequentielle Dateiblockzuweisungen können ausgewählt werden aus zufälligen Positionen innerhalb einer Zone, die zwischen den beiden Zonen alter nieren. Die Plattenleistung kann charakterisiert sein unter Verwendung dieser künstlichen Last und dann verlangsamt bzw. verringert werden, um eine Sicherheitsmarge bereitzustellen. Die Größe der Verringerung kann als der primäre Verringerungsparameter bezeichnet werden. Der verlangsamte Bandbreitenwert wird dann mit dem Bruchteil der Gesamtbandbreite, die in dem Zyklusprozeß für Anforderungen nach garantierter Geschwindigkeit zugewiesen ist. Die sortierende Bandbreite mit garantierter Rate kann durch einen sekundären Verringerungsparameter weiter verringert werden, um eine zusätzliche Deadlinesicherheitsmarge zu erlauben. Das Ergebnis ist die maximale Zugangsbandbreite für die Summe aller garantierter Ratenanforderungen. Garantierte Ratenanforderungen können dann zugelassen werden, bis sie die gesamte garantierte Ratenbandbreite verbrauch haben.
Die Speichercharakterisierung für die Zugangssteuerung ist in 12 zusammengefaßt. Eine künstliche Last wird durch Zuweisen von Blöcken in einer zufälligen Zonen Art und Weise erzeugt, so daß sequentielle Dateiblockzuweisungen von zufälligen Positionen innerhalb einer Zone, die zwischen einer I/O-Plattenzone alternieren, wie in 1202 angezeigt. Die Speichersystembandbreite wird unter Verwendung dieser künstlichen Last bestimmt, wie in 1204 angezeigt. Die bestimmte Bandbreite wird durch einen primären Verringerungsparameter verringert, um eine bestimmte Marge bereitzustellen, wie in 1206 angezeigt. Die verringerte Bandbreite wird entsprechend dem Abschnitt der für die garantierten Ratenanforderungen zugewiesene Bandbreite reduziert, wie in 1208 angezeigt. Diese geteilte Bandbreite kann dann erneut verringert werden durch einen zweiten Verringerungsparameter, um eine zusätzliche Deadlinemarge bereitzustellen, wie in 1210 angezeigt. Die resultierende Bandbreite kann dann als eine maximale Zugangsummenbandbreite für garantierte Ratenströme verwendet werden, wie in 1212 angezeigt.
Der Charakterisierungsprozeß kann ebenso das Bestimmen geeigneter Pufferringgrößen für verschiedene Stromraten im gewünschten Betriebsbereich des Speichersystems beinhalten. Die optimale Anzahl von Puffern für einen Pufferring kann für eine Vielzahl von Stromraten wie folgt bestimmt werden. In 13 erzeugt die Charakterisierungsroutine für jede bestimmte Stromrate genügend Stromsimulatoren, um den gesamten summierten Durchsatz des Speichersystems zu verbrauchen, wie in 1302 gezeigt. Für jeden Stromsimulator wird ein Ringpuffer modelliert, wie in 1304 gezeigt. Jeder Stromsimulator erzeugt dann Blockanforderungen, die zwischen zufälligen Blöcken zwischen Zonen alternieren, wie in 1306 gezeigt. Die simulierten Ströme laufen dann ab bis zum Ablauf einer Testzeit oder bis irgendeiner der Ströme einem Unterlauf unterliegt. Ein Unterlauf tritt auf, wenn eine Pufferanforderung vor der angeforderten Deadline nicht abgearbeitet wird. In einer bevorzugten Ausführungsform kann ein Vorfüllmargenparameter eingestellt werden, so daß ein Unterlauf auftritt, falls eine Pufferanforderung nicht innerhalb der Vorfüllmargenzeit vor der Anforderungs-Deadline erfüllt wird. Die Anzahl von Ringpuffern in dem Modell kann eingestellt werden und die Simulation wiederholt werden, wie in 1308 und 1310 gezeigt, bis die korrekte Ringpuffergröße erhalten wird. Die gesamte Simulation kann dann für eine andere Stromrate wiederholt werden, wie in 1312 gezeigt. Somit kann eine Tabelle von geeigneten Ringpuffergrößen während der Charakterisierung für eine Vielzahl von Stromraten bis zur Maximalstromrate, die von dem System unterstützt wird, konstruiert werden. Während des Betriebs kann, wenn immer ein neuer Strom zugelassen wird, ein Ringpuffer mit geeigneter Größe für den neuen Strom durch den Zugriff auf diese Tabelle erzeugt werden.
Die Leistung des Videospeichermanagers kann durch Einstellen einer Anzahl von Parametern fein eingestellt werden, wie oben erörtert. Diese Parameter werden in der folgenden Tabelle zusammengefaßt.
Tabelle 1 – System Charakterisierungsparameter
Diese Parameter können verwendet werden, um die Leistung eines Medienspeichersystems, wie zum Beispiel das oben beschriebene System, zu konfigurieren und einzustellen. Der maximal erreichbare Durchsatz des Speichersystems kann wie oben beschrieben charakterisiert sein, beispielsweise durch Verwendung einer künstlichen Last. Um den Betriebslastlevel des Speichersystems relativ zu dem Maximaldurchsatz einzustellen, kann der charakterisierte maximal erhältliche Durchsatz durch den primären Verringerungsparameter verringert werden. Der primäre Verringerungsparameter ist konfigurierbar und kann während der Systemkonfiguration eingestellt werden. Warteschlangen, wie zum Beispiel die oben beschriebenen Deadlinewarteschlangen können basierend auf dem verringerten Maximaldurchsatz, wie er von dem primären Verringerungsfaktor verringert wurde, dimensioniert sein. Der resultierende Durchsatz kann der primäre Durchsatz genannt werden. Der primäre Durchsatz kann für die Dimensionierung der Pufferringe verwendet werden, wie oben beschrieben. Der primäre Verringerungsparameter stellt eine Sicherheitsspanne für das Betriebslastniveau des Speichersystems auf Kosten einer Verringerung des verfügbaren Maximaldurchsatzes bereit. Durch das Einstellen des primären Verringerungsparameters während der Systemkonfiguration kann der Benutzer diesen Ausgleich einstellen, wie für irgendeine bestimmte Anwendung des Speichersystems benötigt.
Der verfügbare I/O-Ratenparameter spezifiziert die Speicherbandbreite, die für nicht-ratengarantierte Anforderungen reserviert ist, wie oben in Bezug auf den Bandbreitenzuweiser erörtert. Die Größe der Bandbreite, die für nicht-garantierte Ratenanforderung gegenüber garantierten Ratenanforderungen reserviert ist, kann unter Verwendung dieses Parameters konfiguriert sein. Abhängig von den Anforderungen eines Systems kann der Benutzer das Verhältnis zwischen nicht-garantierten und garantierten Ratenanforderungen durch Einstellen dieses verfügbaren Ratenparameters einstellen.
Der sekundäre Verringerungsparameter reduziert die für ratengarantierte Ströme verfügbare Bandbreite. Der primäre Durchsatz wird entsprechend dem verfügbaren Ratenparameter dimensioniert und der Anteil, der für ratengarantierte Ströme zugewiesen ist, wird weiter reduziert durch den sekundären Verringerungsparameter, um eine zusätzliche Deadline-Sicherheitsspanne bereitzustellen. Während des Betriebs können zusätzliche Übertragungsströme bis zu dem Punkt zugelassen werden, bei dem die Summe aller Übertragungsstromraten den Teil des primären Durchsatzes, der den garantierten Ratenströmen zugewiesen ist, so wie er von dem sekundären Verringerungsparameter verringert wurde, vollständig verbraucht ist.
Der Vorfüllmargenparameter spezifiziert eine Deadline-Sicherheitsspanne, die während der Berechnung der Pufferringgrößen verwendet wird. Während der Systemkonfiguration können die Pufferringgrößen für verschiedene Übertragungsstromraten berechnet werden, wie in Bezug auf 13 beschrieben. Der Vorfüllmargenparameter spezifiziert eine Marge bzw. eine Spanne, um welche die Deadlines während dieses Pufferringgrößenberechnungsprozesses erfüllt werden müssen, zum Beispiel stellt die Vorfüllmarge eine Marge bereit, um die der Pufferunterlauf vermieden werden muß, wenn die Pufferringgrößen bestimmt werden. Man beachte, daß der Vorfüllmargenparameter einen zusätzlichen Unterlaufschutz auf Kosten von zusätzlichem Speicher, der für größere Ringpuffer verwendet wird, erhält. Eine größere Vorfüllmarge führt zu größeren Ringpuffergrößen, da für bestimmte Stromraten zusätzliche Puffer in dem Pufferring erforderlich sein werden, um zu vermeiden, daß die Deadlines um die spezifizierte Vorfüllmarge verfehlt werden. Im Gegensatz dazu erhält der sekundäre Verringerungsparameter einen zusätzlichen Unterlaufschutz auf Kosten der möglichen Bandbreite für ratengarantierte Ströme. Somit stellt der sekundäre Verringerungsparameter und der Vorerfüllungsmargenparameter einem Benutzer des Speichersystems die Fähigkeit zur Verfügung, die Systemleistung durch Durchführen verschiedener unterschiedlicher Abwägungen einzustellen, so wie es für eine bestimmte Anwendung optimal ist. Wenn beispielsweise ausreichend Speicher verfügbar ist, jedoch zusätzliche Bandbreite benötigt wird, dann kann die sekundäre Verringerung verkleinert werden und die Vorfüllmarge erhöht werden. Wenn jedoch der Speicher bei seiner Höchstauslastung ist, kann die Vorfüllmarge verringert werden und der sekundäre Verringerungsparameter erhöht werden.
Der I/O-Überlapp-Parameter (ebenso bezeichnet als der Suchneuordnungspufferlängenparameter) spezifiziert die Anzahl von Speicheranforderungen, die in dem Betriebssystem für eine Speichereinheit in eine Warteschlange gestellt werden. Beispielsweise wird in dem oben beschriebenen System eine Suchneuordnungswarteschlange verwendet, um die Anforderungen an die Speichereinheiten in eine Ordnung entsprechend der physikalischen Plattenadresse der Speicheranforderungen gestellt werden. Die Länge solch einer Warteschlange kann durch den I/O-Überlapp-Parameter konfiguriert sein. Dieser Parameter wägt die Sucheffizienz gegen die Servicezeitvariabilität ab. Beispielsweise können, je größer die Suchneuordnungswarteschlange gemacht wird, um so mehr Anforderungen der Speichereinheit in einer linearen Ordnung präsentiert werden, was somit die Plattensucheffizienz erhöht. Da jedoch die Anforderungen von ihrer Deadline- und Prioritätsordnungen neu geordnet werden, wird eine längere Suchneuordnungswarteschlange die Variabilität beim Erfüllen von angeforderten Deadlines erhöhen. Dieser Parameter kann berücksichtigt werden, wenn die Pufferringe dimensioniert werden, so daß größere Suchneuordnungswarteschlangengrößen zu größeren Pufferringgrößen führen können, um die Variabilität beim Erfüllen von angeforderten Deadlines zu berücksichtigen. Daher kann der I/O-Überlapp-Parameter es dem Benutzer erlauben, Speicher, der für Puffer verfügbar gemacht wird, gegenüber einer höheren Plattensucheffizienz abzuwägen.
In einer Ausführungsform kann die Blockgröße, auf die Mediadaten in den Speichereinheiten zugreifen, konfiguriert sein entsprechend einem Blockgrößenparameter. Konfigurieren der Blockgröße kann das Abwägen der Suchamortisierung gegenüber der Pufferfragmentierung bei niedrigeren Übertragungsraten erlauben. Eine größere Blockgröße kann eine größere Sucheffizienz erlauben, eine größere Blockgröße kann jedoch zu einer größeren Fragmentierung und weniger effizienten Verwendung der Speicherkapazität für bestimmte Dateigrößen führen.
In 14 ist ein Flußdiagramm gezeigt, das eine Ausführungsform eines Verfahrens zum Planen von Plattenzugriffsanforderungen in einer Durchlaufliste für eine Ausführungsform darstellt. Um eine Plattenzugriffsanforderung zu planen, muß ein geeigneter Plattenkopfdurchlauf gefunden werden. Eine Durchsuchung der Durchlaufsliste wird in Schritt 2001 initiiert. Wenn ein Plattenkopfdurchlauf gesucht wird, muß eine Feststellung gemacht werden, ob der gesuchte Durchlauf aktiv ist (Schritt 2002). Falls der Durchlauf, der gesucht wird, aktiv ist, wird die gegenwärtige Plattenblocqkadresse (d.h. die gegenwärtige Adresse des Plattenkopfes) mit der Adresse der Plattenanforderung verglichen. Die Adresse der Plattenanforderung muß hinter der gegenwärtigen Plattenblockadresse in Bezug auf die spezifizierte Richtung des Plattendurchlaufs sein. Diese Anforderung kann helfen, die Plattenkopfbewegung zu minimieren, da es verhindern kann, daß der Plattenkopf seine Richtung während eines gegebenen Durchlaufs ändern muß. Falls die Adresse der Plattenanforderung nicht hinter der gegenwärtigen Plattenblockadresse liegt, dann muß der Suchprozeß erneut in Schritt 2001 beginnen.
Falls die Plattenblockadresse hinter der Adresse des Plattenkopfes liegt (Schritt 2004) oder der gegenwärtig durchsuchte Durchlauf nicht aktiv ist (active = falsch, Schritt 2002), schaut der Suchalgorithmus dann auf die Anzahl von Plattenanforderungen in der Plattenanforderungsliste (Schritt 2003). Vor Starten des Suchalgorithmus wird eine Maximalzahl N von Plattenanforderungen pro Plattenkopfdurchlauf spezifiziert. Durch Beschränken der Anzahl von Plattenanforderungen pro Plattenkopfdurchlauf kann die Antwortzeit für eine gegebene Plattenzugriffsanforderung effektiv beschränkt werden. Dies kann relativ gleichförmige Plattenzugriffszeiten erlauben, die für bestimmte Anwendungen (insbesondere Multimediaanwendungen) erforderlich sein können. Typische Werte von N liegen zwischen 8 und 10 Anforderungen pro Durchlauf, obgleich der Wert von N verändert werden kann, um an verschiedene Ausführungsformen angepaßt zu werden. Größere Werte von N führen typischerweise zu einer größeren Optimierung der Plattenkopfbewegung, obwohl die Plattenzugriffszeiten weniger gleichförmig sein können. Im Gegensatz dazu führen kleinere Werte von N zu gleichförmigeren Plattenzugriffszeiten mit einer geringeren Optimierung der Plattenkopfbewegung.
Falls die Anzahl von Plattenanforderungen in dem gegenwärtig durchsuchten Durchlauf den spezifizierten Maximalwert N erreicht hat, muß ein neuer Durchlauf durchsucht werden. Eine Bestimmung wird durchgeführt, um zu prüfen, ob alle Durchläufe in Schritt 2005 durchsucht wurden. Falls alle Plattenkopfdurchläufe auf der Durchlaufsliste durchsucht wurden, ohne daß ein geeigneter Ort für die Plattenzugriffsanfordenang gefunden wurde, werden zwei neue Plattenkopfdurchläufe konstruiert und an das Ende der Durchlaufsliste angehängt (Schritt 2006). Die Plattenanforderungsliste von jedem der neu konstruierten Plattenkopfdurchläufe ist leer und somit kann eine nachfolgende Suche leicht einen geeigneten Ort für eine Plattenzugriffsanforderung finden. Verschiedene Ausführungsformen des Systems beschränken die Anzahl von Plattenkopfdurchläufen auf gerade Zahlen, wobei die Richtung der Plattenkopfbewegung sich mit jedem nachfolgenden Durchlauf umkehrt. Somit kann der erste neu konstruierte Durchlauf, der an die Durchlaufsliste angehängt wird, eine Richtung der Kopfbewegung entgegengesetzt zu dem vorherigen Plattenkopfdurchlauf spezifizieren. Der zweite neu konstruierte Durchlauf, der angefügt wird, kann eine Richtung der Plattenkopfbewegung spezifizieren entgegengesetzt zu der des ersten neu konstruierten Durchlaufs. Nach dem Anfügen der beiden neu konstruierten Durchläufe setzt die Suche in Schritt 2001 fort.
Sobald ein geeigneter Plattenkopfdurchlauf gefunden wurde, kann die Plattenzugriffsanforderung dann in die Plattenzugriffsliste des Durchlaufs eingefügt werden (Schritt 2007). Die Plattenanforderung kann an einem Ort auf der Liste eingefügt werden, der es erlaubt, daß die Plattenkopfbewegung fortgesetzt während des Durchlaufs in eine einzelne Richtung stattfindet. Dies kann das Umordnen einiger der Plattenzugriffe, die bereits in die Plattenanforderungsliste eingetragen sind, erfordern. Danach wird eine Variable, welche die Anzahl von Plattenanforderungen in der Plattenanforderungsliste anzeigt, um Eins erhöht (2009). Eine andere Variable, welche die Gesamtzahl von Plattenanforderungen für alle Plattenkopfdurchläufe anzeigt, wird ebenso um Eins erhöht (Schritt 2009).
Andere Ausführungsformen, die andere Verfahren der Neuordnung der Plattenanforderungen verwenden, sind möglich und wurden in Betracht gezogen. Beispielsweise kann eine alternative Ausführungsform eine einzelne Liste mit allen Plattenanforderungen enthalten. Jeder Eintrag auf der Liste, der einer Plattenanforderung entspricht, kann eine Variable beinhalten, welche die Anzahl von nacheinander eingehenden Plattenanforderungen anzeigt, welche neu geordnet wurden und vor der ursprünglichen Plattenanforderung erfüllt werden. Diese Variable kann einen Maximalwert haben, der, sobald erreicht, dazu führen kann, daß alle weiteren Plattenanforderungen nach der ursprünglichen Plattenanforderung geplant wurden. Die Anzahl von Plattenanforderungen, die umgeordnet werden können, um vor einer ursprünglichen Plattenanforderung erfüllt zu werden, ist somit begrenzt, was effektiv die Zeit begrenzt, die erforderlich ist, um die ursprüngliche Plattenanforderung zu erfüllen.
In 15 ist ein Beispiel einer Durchlaufsliste gezeigt, die für das Planen von Plattenzugriffsanforderungen unter Verwendung des Verfahrens von 14 verwendet werden kann. Wie hier dargestellt, beinhaltet die Durchlaufsliste 2500 Einträge entsprechend acht unterschiedlichen Plattenkopfdurchläufen. Jeder Eintrag in der Liste beinhaltet eine Durchlaufsnummer, eine Plattenanforderungsliste, eine aktive Variable, eine Richtungsvariable und eine Variable, welche die Anzahl von Plattenanforderungen für den entsprechenden Plattenkopfdurchlauf anzeigt. In dem gezeigten Beispiel kann jede Plattenanforderungsliste bis zu 10 Plattenanforderungen (d.h. N = 10) enthalten. Jede Plattenanforderung, die in einer Plattenanforderungsliste eingefügt ist, beinhaltet eine Plattenadresse. Die Plattenadresse ist der Ort auf der Platte, wo der Plattenkopf die Daten auszulesen hat, um die Anforderung zu erfüllen. In dem gezeigten Beispiel werden die Adressen von jedem Eintrag in einem Hexadezimalformat dargestellt. Im allgemeinen können Adressen in die Plattenanforderungsliste in jedem für die bestimmte Ausführungsform geeigneten Format eingetragen werden.
Jeder Durchlaufseintrag beinhaltet ebenso eine Richtungsvariable. In der gezeigten Ausführungsform ist die Richtung entweder als niedrig-zu-hoch (niedrige Adressen zu hohen Adressen) oder hoch-zu-niedrig angezeigt. Im Grunde genommen werden die Plattenanforderungen, die in die Plattenanforderungsliste eingefügt werden, in einer Art und Weise geordnet, die konsistent mit dem Zustand der Richtungsvariablen für den gegebenen Plattenkopfdurchlauf sind. In manchen Fällen kann der Eintrag einer Plattenanforderung in einer Plattenanforderungsliste die Umordnung der vorher eingefügten Anforderungen erfordern, um die Richtung, welche durch den Zustand der Richtungsvariablen spezifiziert ist, beizubehalten. Beispielsweise, falls eine Plattenanforderung für eine Plattenadresse 1A2F in den dritten Durchlauf in der Liste eingegeben wird, kann er in der vierten Position auf der Liste eingegeben werden. Die Plattenanforderung vor der vierten Position (Plattenadresse 1FA1) kann zu der fünften Position der Plattenanforderungsliste verschoben werden, was somit die niedrig-zu-hoch-Richtung beibehält, die für den Durchlauf spezifiziert ist.
Jeder Durchlauf beinhaltet ebenso eine Boolesche Variable, um anzuzeigen, ob der Durchlauf aktiv ist. Der Durchlauf wird als aktiv angesehen, wenn Plattenanforderungen von ihrer verknüpften Plattenanforderungsliste ausgeführt werden. Falls aktiv, wird die aktive Variable in einen Wahrzustand gesetzt. Für die verbleibenden Durchläufe verbleibt die aktive Variable in einem Falschzustand, bis das System beginnt, die Plattenanforderungen von dessen verknüpfter Plattenanforderungsliste zu erfüllen.
Die Durchlaufsliste beinhaltet ebenso eine gegenwärtige Plattenblockadresse, welche die gegenwärtige Position des Plattenkopfes in Bezug auf die Platte anzeigt. In dem gezeigten Beispiel ist die gegenwärtige Platteblockadresse 0110. Dies entspricht der ersten Plattenzugriffsanforderung des ersten Durchlaufs auf der Liste. Die gegenwärtige Plattenblockadresse kann von dem Planalgorithmus verwendet werden, wenn er versucht, eine Plattenanforderung in einem aktiven Durchlauf zu planen. Falls beispielsweise der Planer versucht, eine Plattenzugriffsanforderung in einem aktiven Durchlauf mit einer spezifizierten Richtung von niedrig-zu-hoch zu planen, muß die Plattenanforderung eine höhere Adresse aufweisen als die gegenwärtige Plattenblockadresse in dieser Ausführungsform. Falls die Adresse der Plattenanforderung diese Anforderung nicht erfüllt, kann sie dann für einen nicht-aktiven Durchlauf geplant werden.
16 ist ein Flußdiagramm, das ein Verfahren zum Ausführen der Plattenzugriffsanforderungen, die unter Verwendung des Verfahrens in 14 geplant wurden, dargestellt. Schritt 3000 beginnt mit einer Überprüfung der Gesamtzahl von allen Plattenanforderungen, die in der Durchlaufsliste geplant sind. Falls keine Plattenanforderungen geplant werden, tritt das System in einen Wartezustand ein (Schritt 3001), verbleibt in Bereitschaft, bis zumindest eine Plattenanforderung geplant wird. Falls die Anzahl von Plattenanforderungslisten größer als Null ist, dann wird das System die Plattenanforderungsliste des ersten Eintrags der Durchlaufsliste überprüfen (Schritt 3003). Falls die Plattenanforderungsliste leer ist (was anzeigen kann, daß alle Plattenanforderungen des Durchlaufs durchgeführt wurden), wird der Eintrag, der dem Durchlauf entspricht, von der Durchlaufsliste entfernt und die Aktivvariable wird auf falsch gesetzt (Schritt 3008).
Als nächstes wird die Variable, welche die Anzahl von Plattenzugriffen auf der Plattenzugriffsliste des Durchlaufs anzeigt, auf Null gesetzt (Schritt 3009). Schließlich wird der Druchlauf an das Ende der Durchlaufsliste angefügt (Schritt 3010).
Falls die Überprüfung, die in Schritt 3003 durchgeführt wurde, anzeigt, daß die Plattenanforderungsliste nicht leer ist, wird eine Überprüfung durchgeführt, um festzustellen, ob die Aktivvariable wahr ist (Schritt 3004). Typischerweise, wenn keine Plattenanforderungen für den gegenwärtigen Durchlauf durchgeführt wurden, wird die Aktivvariable falsch sein und muß somit auf wahr gesetzt werden (Aschritt 3005). Mit der aktiven Variablen wahr wird die nächste Plattenanforderung aus der Plattenanforderungsliste in Vorbereitung für das Durchführen des Plattenzugriffs (Schritt 3006) entfernt. Nach dem Entfernen der Plattenanforderung von der Plattenanforderungsliste wird die Variable, welche die Gesamtzahl von Plattenanfordenungen für alle Einträge der Durchlaufsliste anzeigt, um Eins verringert (Schritt 3007). Schließlich wird in Schritt 3011 ein Plattenzugriff durchgeführt, wodurch die Plattenzugriffsanforderung erfüllt wird.
Während die vorliegende Erfindung in Bezug auf spezielle Ausführungsformen beschrieben wurde, versteht es sich, daß die Ausführungsformen anschaulich sind und daß der Erfindungsbereich nicht so beschränkt ist. Alle Variationen, Modifikationen, Hinzufügungen und Verbesserungen der beschriebenen Ausführungsformen sind möglich. Diese Variationen, Modifikationen, Hinzufügungen und Verbesserungen können in den Schutzbereich der Erfindung fallen, wie in den folgenden Ansprüchen ausgeführt.

Claims

Plattenspeichersystem, das aufweist: eine Platte für das Speichern von Daten, einen Plattenkopf für das Lesen von Daten von der Platte, und ein Steuerprogramm (408) für das Empfangen einer Mehrzahl von Plattenzugriffsanforderungen, wobei das Steuerprogramm konfiguriert ist, um Plattenzugriffsanforderungen für einen ersten Durchlauf des Plattenkopfes einzuplanen, und in Antwort auf die Bestimmung, daß eine Gesamtzahl von N-Anforderungen für den ersten Durchlauf eingeplant wurde, die verbleibenden Plattenzugriffsanforderungen für einen oder mehrere zusätzliche Durchläufe des Plattenkopfes einzuplanen, wobei jeder der N-Anforderungen eine Anforderung zur Übertragung eines Datenblockes fester Größe aufweist.
Plattenspeichersystem nach Anspruch 1, bei dem das Plattenspeichersystem konfiguriert ist, um eine Liste (2500) von Plattenkopfdurchläufen zu pflegen, wobei die Liste eine Mehrzahl von Einträgen beinhaltet.
Plattenspeichersystem nach Anspruch 2, bei dem jeder der Mehrzahl von Einträgen eine Plattenanforderungsliste beinhaltet, wobei die Plattenanforderungsliste Plattenzugriffsanforderungen für einen verknüpften Plattenkopfdurchlauf beinhaltet.
Plattenspeichersystem nach Anspruch 3, bei dem jeder der Mehrzahl von Einträgen eine Variable für das Anzeigen einer Anzahl von Plattenzugriffsanforderungen in der Plattenanforderungsliste beinhaltet.
Plattenspeichersystem nach Anspruch 2, bei dem jeder der Mehrzahl von Einträgen eine Boolesche Variable beinhaltet für das Anzeigen, ob ein verknüpfter Plattenkopfdurchlauf aktiv ist.
Pattenspeichersystem nach Anspruch 5, bei dem die Boolesche Variable wahr ist, wenn der verknüpfte Plattenkopfdurchlauf aktiv ist.
Plattenspeichersystem nach Anspruch 2, bei dem jeder der Mehrzahl von Einträgen eine Variable beinhaltet, die eine Bewegungsrichtung für den Plattenkopf für einen verknüpften Plattenkopfdurchlauf anzeigt.
Plattenspeichersystem nach Anspruch 7, bei dem die Bewegungsrichtung des ersten Durchlaufs des Plattenkopfes in einer Richtung entgegengesetzt der Bewegungsrichtung für einen zweiten Durchlauf des Plattenkopfes ist, wobei der zweite Durchlauf des Plattenkopfes unmittelbar auf den ersten Durchlauf des Plattenkopfes folgt.
Plattenspeichersystem nach Anspruch 8, bei dem die Liste von Plattenkopfdurchläufen eine gerade Anzahl von Einträgen beinhaltet.
Plattenspeichersystem nach Anspruch 1, bei dem das Plattenspeichersystem konfiguriert ist, um eine Variable beizubehalten, die eine Adresse des Plattenkopfes anzeigt.
Verfahren zum Planen von Plattenzugriffsanforderungen in einem Plattenspeichersystem, wobei das Plattenspeichersystem eine Platte für das Speichern von Daten und einen Plattenkopf für das Lesen von Daten beinhaltet, wobei das Verfahren aufweist: Einplanen (408) einer Mehrzahl von Plattenzugriffsanforderungen für einen ersten Durchlauf des Plattenkopfes, und Einplanen der verbleibenden Plattenzugriffsanforderungen für einen oder mehrere zusätzliche Durchläufe des Plattenkopfes in Antwort auf die Bestimmung, daß eine Gesamtzahl von N-Anforderungen für den ersten Durchlauf des Plattenkopfes eingeplant wurde, wobei jeder der N-Anforderungen eine Anforderung aufweist, um einen Datenblock fester Größe zu übertragen.
Verfahren nach Anspruch 11, das weiterhin aufweist das Pflegen einer Liste (2500) von Plattenzugriffsanforderungen, die für die Ausführung während eines Durchlaufes des Plattenkopfes eingeplant sind.
Verfahren nach Anspruch 12, bei dem das Verfahren das Bestimmen beinhaltet, ob der erste Durchlauf aktiv ist.
Verfahren nach Anspruch 13, bei dem das Verfahren beinhaltet das Bestimmen einer gegenwärtigen Adresse des Plattenkopfes.
Verfahren nach Anspruch 12, wobei das Verfahren das Beibehalten einer Durchlaufsliste beinhaltet, wobei die Durchlaufsliste eine Mehrzahl von Einträgen entsprechend den Plattenkopfdurchläufen beinhaltet.
Verfahren nach Anspruch 15, bei dem jeder der Mehrzahl von Einträgen eine Boolesche Variable für das Anzeigen, ob ein entsprechender Plattenkopfdurchlauf aktiv ist, beinhaltet.
Verfahren nach Anspruch 16, wobei die Boolesche Variable wahr ist, wenn der entsprechende Plattenkopfdurchlauf aktiv ist.
Verfahren nach Anspruch 15, bei dem jeder der Mehrzahl von Einträgen eine Variable für das Anzeigen einer Richtung der Plattenkopfbewegung während eines entsprechenden Plattenkopfdurchlaufs beinhaltet.
Verfahren nach Anspruch 18, bei dem die Richtung der Plattenkopfbewegung eines zweiten Durchlaufs entgegengesetzt zu der Richtung der Plattenkopfbewegung des ersten Plattenkopfdurchlaufes ist, wobei der zweite Plattenkopfdurchlauf unmittelbar auf den ersten Plattenkopfdurchlauf folgt.
Verfahren nach Anspruch 19, bei dem die Durchlaufsliste eine gerade Anzahl von Einträgen enthält.
Verfahren nach Anspruch 15, das weiterhin aufweist das Einplanen von zwei neuen Plattenkopfdurchläufen, wenn ein geeigneter Plattenkopfdurchlauf für eine Plattenzugriffsanforderung nicht gefunden wird, wobei die beiden neuen Plattenkopfdurchläufe an das Ende der Durchlaufsliste angefügt werden.
Verfahren nach Anspruch 14, bei dem eine Variable beibehalten wird, die die Gesamtanzahl von Plattenzugriffsanforderungen für alle der Mehrzahl von Einträgen der Durchlaufsliste anzeigt.